[發明專利]基于分布擬合的網絡表格間的外鍵關系檢測方法

有效

• 申請號: 201811250624.3
• 申請日: 2018-10-25
• 公開（公告）號: CN109472013B
• 公開（公告）日: 2020-06-16
• 發明（設計）人: 王寧;王佳敏
• 申請（專利權）人: 北京交通大學
• 主分類號: G06F40/18
• 分類號: G06F40/18;G06F16/28
• 代理公司: 北京市商泰律師事務所 11255
• 代理人: 黃曉軍

1.一種基于分布擬合的網絡表格間的外鍵關系檢測方法，其特征在于，包括：

檢測網絡表格間不同屬性列之間的包含覆蓋關系，根據所述包含覆蓋關系的檢測結果篩選出所述網絡表格間的候選外鍵關系對；

構建所述候選外鍵關系對中候選外鍵和候選主鍵的多維分布圖，計算出所述候選外鍵和候選主鍵的多維分布圖之間的擬合度；

根據所述候選外鍵和候選主鍵的多維分布圖之間的擬合度判斷所述候選外鍵關系對是否為真正的外鍵關系對；

所述的檢測網絡表格間不同屬性列之間的包含覆蓋關系，根據所述包含覆蓋關系的檢測結果篩選出所述網絡表格間的候選外鍵關系對，包括：

將待檢測的網絡表格集合中的表格按照列存儲到列集合中，對所述列集合中的字符型屬性列進行模糊匹配，對所述列集合中的數字型屬性列進行數值匹配，根據所述模糊匹配和數值匹配的匹配結果查找出所述列集合中的所有單列的屬性對；

從所有單列的屬性對中檢測出來自相同表格的多列的屬性對，對于檢測出的所有單列IND，查找是否存在n個來自同一個表格的屬性列集合A包含于來自另一個表格的n個屬性列的集合B，若存在，則將A與B組成的屬性對作為多列IND；

判斷所有單列的屬性對和多列的屬性對是否滿足設定的主鍵唯一性條件，所述設定的主鍵唯一性條件包括主鍵中的重復值小于設定的閾值λ，將滿足所述設定的主鍵唯一性條件的單列的屬性對和多列的屬性對作為候選外鍵關系對，每個候選外鍵關系對包括候選外鍵F和候選主鍵P；

所述的構建所述候選外鍵關系對中候選外鍵和候選主鍵的多維分布圖，包括：

針對每個候選外鍵關系對，為候選外鍵F的每個列的列值進行排序，并獲得該列中每個值的位置，將每列對應多維空間的一個維度，再對分布于每個維度上的每個列的列值的位置進行哈希映射，得到候選外鍵F的多維分布圖；為候選主鍵P的每個列的列值進行排序，并獲得該列中每個值的位置，將每列對應多維空間的一個維度，再對分布于每個維度上的每個列的列值的位置進行哈希映射，得到候選主鍵P的多維分布圖。

2.根據權利要求1所述的方法，其特征在于，所述的計算出所述候選外鍵和候選主鍵的多維分布圖之間的擬合度，包括：

對所述候選外鍵F和候選主鍵P的多維分布圖進行分區；

根據分區后的所述候選外鍵F和候選主鍵P的多維分布圖，確定候選外鍵F中的值應該落入候選主鍵P的多維分布圖的每個分區的個數，該個數稱為理論頻數，統計候選外鍵F中的值實際落入候選主鍵P的多維分布圖的每個分區的實際個數，該實際個數稱為觀測頻數，根據所述理論頻數和觀測頻數計算出所述候選主鍵P和所述候選外鍵F的多維分布圖之間的整體偏差；

根據所述整體偏差確定所述候選外鍵F和候選主鍵P的兩個多維分布圖之間的擬合度。

3.根據權利要求2所述的方法，其特征在于，所述的對所述候選外鍵F和候選主鍵P的多維分布圖進行分區，包括：

設定子空間的點數閾值s，對于每個k維多維分布圖，在每個維度上將相應的區間劃分成相等的兩個部分，得到2^k個子空間，將所述2^k個子空間中點數超過閾值s的子空間繼續劃分為2^k個子空間，將得到的點數超過閾值s的子空間繼續進行劃分，并且以這種方式迭代，直到每個子空間中的點數都小于或等于閾值s。