加入兩個窄格式表

我有場景，我有表（在專有數據存儲）與數千列。導出用於查詢的表格被轉換爲窄格式（http://en.wikipedia.org/wiki/Wide_and_Narrow_Data）。加入兩個窄格式表

我正在開發一個查詢執行器。這個查詢執行器的輸入是窄表而不是原始表。我想在兩個類似的窄表上執行連接，但無法弄清楚它背後的確切一般邏輯。

例如，假設我們已經在原始格式（寬格式）2表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是表之間的公共列。

爲表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

我怎樣才能通過加入狹窄的表（在共同的列），我作爲輸入得到上述表。如果您使用兩個窄表之間的普通表格連接（自然連接，外連接等），您將得到一個分解表，因爲表R上的每個鍵都與表S中的所有鍵相乘。

我沒有使用SQL或Postgres或任何數據庫系統。我正在尋找算法或關係代數表達式的答案。

來源

2014-03-13 sushil

您正在尋找組合運算符：A∪B被定義爲出現在A，B或兩者中的所有元組的集合，假設兩個關係具有相同的模式。窄表全都具有相同的模式（id，key，value），所以它們完全兼容。

而且我有證據：

假設我們有關係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爲「價值」，把表中的變量名稱（通過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'，也就是連接表的窄格式是窄格式表的聯合。

來源

2014-03-19 04:50:11

真的很感謝你用來證明它的努力。我已經實施了使用聯盟，因爲這是唯一的結果是有道理的。但是我無法證明它在數學上是正確的。 – sushil

加入兩個窄格式表

回答

相關問題