sql - 加入两个窄格式表

我有一个场景，其中我有包含数千列的表(在专有数据存储中)。导出查询之前的表被转换为窄格式(http://en.wikipedia.org/wiki/Wide_and_Narrow_Data)。

我正在开发一个查询执行器。该查询执行器的输入是窄表而不是原始表。我想对两个类似的窄表执行连接，但无法弄清楚其背后的确切一般逻辑。

例如假设我们有两个原始格式(宽格式)的表 R 和 S

Table R
C1  C2  C3  R1  R2  R3
5   6   7   1234    4552    12532
5   6   8   4512    21523   434
15  16  17  1254    1212    3576

Table S
C1  C2  C3  S1  S2  S3
5   6   7   5412    35112   3512
5   6   8   125393  1523    6749
15  16  17  74397   4311    1153

C1、C2、C3是表之间的公共(public)列。

表R的窄表是

C1  C2  C3  Key Value
5   6   7   R1  1234
            R2  4552
            R3  12532
5   6   8   R1  4512
            R2  21523
            R3  434
15  16  17  R1  1254
            R2  1212
            R3  3576

表S的窄表是

C1  C2  C3  Key Value
5   6   7   S1  5412
            S2  35112
            S3  3512
5   6   8   S1  125393
            S2  1523
            S3  6749
15  16  17  S1  74397
            S2  4311
            S3  1153

现在，当我加入原始表 R 和 S(在 C1、C2 和 C3 上)时，我得到了结果

C1  C2  C3  R1  R2  R3  S1  S2  S3
5   6   7   1234    4552    12532   5412    35112   3512
5   6   8   4512    21523   434 125393  1523    6749
15  16  17  1254    1212    3576    74397   4311    1153

谁的窄格式

C1  C2  C3  Key Value
5   6   7   R1  1234
            R2  4552
            R3  12532
            S1  5412
            S2  35112
            S3  3512
5   6   8   R1  4512
            R2  21523
            R3  434
            S1  125393
            S2  1523
            S3  6749
15  16  17  R1  1254
            R2  1212
            R3  3576
            S1  74397
            S2  4311
            S3  1153

我如何通过加入我作为输入获得的窄表(在公共(public)列上)来获得上表。如果您在两个窄表之间使用普通表格连接(自然连接、外部连接等)，您将得到一个分解表，因为表 R 上的每个键都与表 S 中的所有键相乘。

我没有使用 SQL、postgres 或任何数据库系统。我正在寻找算法或关系代数表达式方面的答案。

最佳答案

您正在寻找集合并集运算符:A∪B 被定义为出现在 A、B 或两者中的所有元组的集合，假设这两个关系具有相同的模式。窄表都具有相同的架构(id、键、值)，因此它们完全兼容并集。

我有证据:

假设我们有关系 A(id, val1, val2 ... val_n)和 B(id, val_n+1 ... val_n+m) .我们还需要一个包含变量名的关系 V(variable) = {('val1'), ('val2') ... ('val_n+m')} . A 的窄格式等价物是 A'(id, variable, value) ，我们可以这样构造:

$\bigcup_{i=1}^{n} \rho_{value/val_i}( \pi_{id, val_i}(A) ) \times \sigma_{variable="val_i"}(V)$

也就是说，对于我们将 A 投影到 (id, val_i) 的每个值，将 val_i 重命名为“value”，将变量名称放入表中(通过与 V 中的单个元组取叉积)；然后我们采用所有这些关系的联合。让我们也构建B'(id, variable, value)以类似的方式。

可以仅使用基元定义自然连接:

$A \Join B = \pi_{id, val_1 ... val_{n+m}} ( \sigma_{id = x} ( A \times \rho_{x/id}(B) ) )$

因此我们可以构建(A ⋈ B)'像这样(结合了预测):

$\bigcup_{i=1}^{n+m} \rho_{value/val_i}( \pi_{id, val_i}( \sigma_{id = x} ( A \times \rho_{x/id}(B) ) ) ) \times \sigma_{variable="val_i"}(V)$

让我们更早地应用投影:

$\bigcup_{i=1}^{n+m} \rho_{value/val_i}( \pi_{id, val_i}( \sigma_{id = x} ( \pi_{id, val_i}(A) \times \rho_{x/id}(\pi_{id, val_i}(B))) ) ) \times \sigma_{variable="val_i"}(V)$

但是一个val_i只能出现在 A 或 B 中，不能同时出现，使叉积的一项有一半时间为零，因此可以将其减少并重新排序为

$\bigcup_{i=1}^{n} \rho_{value/val_i}( \pi_{id, val_i}(A)) \times \sigma_{variable="val_i"}(V) \cup \bigcup_{i=n+1}^{m} \rho_{value/val_i}( \pi_{id, val_i}(B)) \times \sigma_{variable="val_i"}(V)$

这正是 A' U B' .

所以，我们已经证明(A ⋈ B)' = A' U B' ，也就是说，连接表的窄格式是窄格式表的并集。

关于sql - 加入两个窄格式表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22367680/

sql - 加入两个窄格式表

上一篇：string - Rabin karp字符串匹配算法复杂度

下一篇：algorithm - 散列时预期的空槽数