如何發現所有可能的方式，其中兩個表可以加入以產生顯着的結果

Question

給定兩個表（僅數據），我想找出所有可能的方式，在這兩種表可以加入以產生顯着的結果。每種方式都對應於從一個表到另一個表的屬性映射。從表T1到T2的映射M的連接強度是T1映射到映射M下的某些T2行的百分比。我有興趣找到所有支持大於閾值t的映射。這是一個非常昂貴的操作，因爲可能的映射數量是屬性數量的指數。因此，我正在考慮爲連接發現考慮採樣技術。

對於示例，考慮TPC-H基準數據庫。假設我們獲得了客戶和訂單的關係表。我們有原始數據。我們不知道每個屬性對應什麼。現在通過查看數據，我們應該能夠推導出customer.customer_id和orders.customer_id是加入支持率高的列，但不是customer.customer_age和orders.customer_id。同樣，我們應該找到所有可能的聯接，並根據他們的支持來排序。由於檢查每個可能的屬性組合是非常昂貴的，因此我們需要使用有效的技術。

實際使用案例：我給出了一個原始的巨大數據集，其中列是隔離的（假設有2個表格是爲了簡單起見）。我想通過有效的支持價值發現可能的聯結。 （注意：因爲我不知道屬性類型的任何內容，所以我在考慮將它們全部視爲字符串並使用採樣）

我清楚需要採樣。我的問題只是以下。

這裏有什麼好的採樣策略？應該計算什麼元數據來決定樣本大小？每個表格的抽樣可以獨立完成還是應該相互關聯？

Answer 1

一種可能性是分析每一列的統計特性。這樣你會發現customers.id和orders.cust_id有類似的分佈，你甚至不會嘗試匹配orders.item_count對customers.age：

      min max average variance ... 
orders.item_count   1  29  3.1782  ... 
customers.age    18  75  38.45  ... 
customers.id    17239 29115 23177  ... 
orders.cust_id   17445 29037 23491  ... 

而且，這些屬性可以從每個表的採樣得到，但是並沒有對整個桌子。但是爲了正確估計支持，您需要進行統一的採樣，這可能與額外的全表掃描一樣昂貴。但是，如果統計屬性看起來很有希望，那麼只能這樣做。你的成本是n + m + k（n * m），希望小k。

我知道這並不多，但也許它可能是一個開始。

（這是的顯著許多可能的含義一個：「兩列指的是同一個實體」您的情況可能會有所不同。）。

更新：MySQL並不是非常適合初步的闡述，我們實際上完全不使用RDBMS特性。您可以考慮使用例如運行初始分析Hadoop的。

如何去做

數據

海賊王這是需要在表A和B的行數約略估計，否則，事情就真的多毛（和性能就走出了窗外的） 。

1. 開始掃描 在這一點上，我們已經閱讀一個行，我們知道領域是什麼表答：我們也知道，表A有一個十億行，我們知道（從特徵我們系統），我們讀不起超過一千萬行，也寫不超過一百萬。

因此，我們開始閱讀A表跳過每100行（1 bil/10 mil）。我們將每1000個樣品（1個1/1 mil）抽樣一行。所以我們會將十行（1000/100）中的一行保存到SampleA中。在我們閱讀的過程中，我們在每列上積累了統計數據，即我們在內存中爲每列指定了一列值，如Col12_Min，Col12_Max，Col12_Sum，Col12_SumSquare ...。我們可以添加其他啓發式參數，例如Col12_Increasing和Col12_Decreasing，並且每當我們讀取的值比前一個更大時，我們就將Col12_Increasing加1，如果減少，我們將_Decreasing加1。這允許在表被聚集時快速識別「計數器」行。

對於每N個採樣/讀取一行的整個概念要求該表格沒有以該頻率進行規則分佈：例如，如果第23列包含除了每百行一次，當其包含零時的客戶ID，通過閱讀第100期的專欄，我們將讀取所有的零，並得出錯誤的結論。如果是這樣的話，我很抱歉;有太多的要求，併爲了滿足他們所有你不能使用快捷方式 - 你需要每行讀取。一個複雜的案例不能以簡單的方式解決。

但是假設案例更真實，我們對錶B執行相同的操作，它將進入SampleB。

完成後，我們有兩個更小的表，列的信息和問題。

的「免費提供給所有」加盟是

 ACol1 ACol2 ACol3 ... AColN 
BCol1  ?  ?  ?   ? 
BCol2  ?  ?  ?   ? 
BCol3  ?  ?  ?   ? 
... 
BColM  ?  ?  ?   ? 

這樣的矩陣通過檢查最大值，最小值，並且列的其它參數，以及它們的數據類型，我們立即重拳出擊所有矩陣數據類型不匹配的單元格，或統計參數與其他數據類型不同的單元格。

 ACol1 ACol2 ACol3 ... AColN 
BCol1   ?     
BCol2  ?    ?   
BCol3     ?   ? 
... 
BColM     ?   

但是現在當我們將SampleA.cust_id加入到SampleB.cust_id中時，我們可以期待什麼？ SampleA每千個只包含一個客戶。所以當試圖加入SampleA和SampleB時，我們可以期望得到不超過0.1％的匹配。給定SampleB的客戶ID，它在SampleA中收穫的可能性是1/1000。

我們現在可以運行額外的檢查：驗證列是否唯一。我們將看到SampleA.cust_id是唯一的，而SampleB.cust_id不是。這告訴我們，加入，如果它持有，將是一對多。

假設我們知道（從統計數據）SampleA.cust_id包含數字範圍10000000-20000000，並擁有53000行，SampleB。cust_id包含相同範圍的數字並保存29000行;如果兩列不相關，但有這些參數，我們可以預料，在一個範圍內隨機產生一個數千萬寬（這是我們做的時候，我們提取SampleB一行，並讀取其cust_it）將有與SampleA中的一行匹配的概率爲53000/10000000 = 0.53％。

兩個概率是不同的就夠了（假設總是我們正在處理的均勻分佈），我們可以嘗試用它們來區分這兩種情況。

當我們已經充分限制列對的數量時，我們可以通過再次讀取整個A（另一個全表掃描）並驗證SampleB.cust_id的所有值確實存在來運行「假連接測試」。

重要：如果有一個表是不完整的，即連接不是原始表中的「完美」，這將引入誤差。如果這個誤差足夠大，那麼就不可能通過比較概率來告訴兩列的關係。此外，一些分佈可能會串通，因此這些概率足夠接近以防止以任何方式確定答案。在所有這些情況下，您需要根據數據的實際性質提出一些不同的啓發式方法。你不能指望找到一個「通用連接算法」。

也：以上所有適用於一列VS一列關係。組合鍵是完全不同的蠕蟲，而統計分析雖然可能需要非常不同的工具--BigData和類似於OLAP的東西 - 而且最重要的是非常不同的（和巨大的）處理成本。

Answer 2

您需要啓動「matchedness」的度量。假設這是值匹配的數量除以兩個表中的總數值。

你可以很容易地生成你需要的東西，如SQL：

select max(name1) as name1, max(name2) as name2, 
     count(*) as totalvalues, 
     sum(in1) as totalvalues_table1, 
     sum(in2) as totalvalues_table2, 
     sum(in1*in2)/count(*) as measure 
from (select value, max(name1) as name1, max(name2) as name2, 
      max(inone) as in1, max(intwo) as in2 
     from ((select 'col1' as name1, NULL, col1 as value, 1 as inone, 0 as intwo from table1 t1) 
      union all 
      (select NULL, 'col1', col1, 0, 1 from table2 t2) 
      ) tt 
     group by value 
    ) v; 

「測量」給出重疊的一些指示，在值水平。您可以使用sum()來獲取行 - 但是您有一個問題，即某些表的行數比其他行多得多。

然後，您可以使用INFORMATION_SCHEMA.COLUMNS表爲所有列自動生成SQL，該表在大多數數據庫中都可用（即使視圖/表名稱不同，所有真實數據庫都有類似的獲取元數據的方法）。

不過，我想你可能很快就會發現，這個問題是很難界定比你想象的。玩弄不同大小和不同重疊量的桌子，看看你是否能想出一個好的啓發式。

Answer 3

你可以什麼假設要去？如果這是一個很大的數據，你可以假設其中的任何一個數據是沒有什麼，那麼你真的已經完成了你的工作。

匹配的數據類型。整數不參加字符串;日期不加入浮動。同上，精確。 4個字節的整數不以2個字節的整數連接;最大50個字符串與128個最大字符串不匹配。如果你將所有東西都轉換爲字符串......你怎麼從字符串到Unicode的時間告訴二進制從浮點數的整數？

「重大」的統計相關性取決於關係的類型。 （一對一），（一對一或更多），（一比零或更多），（一比零或一）都是可行的，但它們看起來不像對方。你能排除你的數據中的（多對多）嗎？

沒有掃描所有的數據，任何採樣統計是毋庸置疑的。數據是按一列排序的嗎？如果稀疏數據聚集在某個地方，會使它看起來比它更普遍？

大重要的假設：單柱之間的連接發生。如果有「複合列標識符」（它確實發生了），並且按順序排列（col1 + col2與col2 + col1），它會比（m * n）分析複雜得多，複雜得多。你的確表明，你知道這個數據，你拿起...

沒有一些合理的起始假設或猜測什麼，你就不會在任何地方得到無嚴重的時間和精力這樣的問題。