[發(fā)明專利]基于分布擬合的網(wǎng)絡(luò)表格間的外鍵關(guān)系檢測方法

有效

• 申請?zhí)枺?/td>: 201811250624.3
• 申請日: 2018-10-25
• 公開（公告）號: CN109472013B
• 公開（公告）日: 2020-06-16
• 發(fā)明（設(shè)計）人: 王寧;王佳敏
• 申請（專利權(quán)）人: 北京交通大學(xué)
• 主分類號: G06F40/18
• 分類號: G06F40/18;G06F16/28
• 代理公司: 北京市商泰律師事務(wù)所 11255
• 代理人: 黃曉軍

本發(fā)明提供了一種基于分布擬合的網(wǎng)絡(luò)表格間的外鍵關(guān)系檢測方法。該方法包括：檢測網(wǎng)絡(luò)表格間不同屬性列之間的包含覆蓋關(guān)系，根據(jù)包含覆蓋關(guān)系的檢測結(jié)果篩選出所述網(wǎng)絡(luò)表格間的候選外鍵關(guān)系對；構(gòu)建候選外鍵關(guān)系對中候選外鍵和候選主鍵的多維分布圖，計算出候選外鍵和候選主鍵的多維分布圖之間的擬合度；根據(jù)候選外鍵和候選主鍵的多維分布圖之間的擬合度判斷候選外鍵關(guān)系對是否為真正的外鍵關(guān)系對。本發(fā)明既適用于字符類型的外鍵關(guān)系檢測，也適用于數(shù)字類型的外鍵關(guān)系檢測，既能檢測單列的外鍵關(guān)系，也能檢測多列的外鍵關(guān)系，在具有較高的檢測準(zhǔn)確性的同時兼具較高的檢測效率。

技術(shù)領(lǐng)域

本發(fā)明涉及網(wǎng)絡(luò)信息處理技術(shù)領(lǐng)域，尤其涉及一種基于分布擬合的網(wǎng)絡(luò)表格間的外鍵關(guān)系檢測方法。

背景技術(shù)

互聯(lián)網(wǎng)上包含大量的結(jié)構(gòu)化表格，為數(shù)據(jù)集成和檢索提供了非常方便和豐富的數(shù)據(jù)集。為了增強網(wǎng)絡(luò)表格間的聯(lián)系和有效利用網(wǎng)絡(luò)上公開的表格數(shù)據(jù)，Anish等人試圖探測網(wǎng)絡(luò)表格間潛在的關(guān)系，并找到關(guān)聯(lián)表格。而外鍵關(guān)系作為數(shù)據(jù)庫中最重要的約束之一，對于模式設(shè)計者來說是非常有價值的，可以用來指定兩個語義相關(guān)的表格。然而對于來自異構(gòu)數(shù)據(jù)源的大量的網(wǎng)絡(luò)表格，在大多數(shù)情況下不會指定外鍵。因此，發(fā)現(xiàn)外鍵關(guān)系是理解和利用網(wǎng)絡(luò)表格的重要步驟。

目前，現(xiàn)有技術(shù)中的外鍵關(guān)系檢測方法大都集中于識別表格間的包含依賴關(guān)系。但是，僅僅通過包含覆蓋來檢測外鍵關(guān)系是不夠的，最直接的方法是找到真正外鍵關(guān)系應(yīng)該滿足的重要特征。Alexandra Rostin等人提出了一些規(guī)則，例如列名相似度、列值平均長度、列值的唯一性和覆蓋率等一系列特征，并以此來發(fā)現(xiàn)傳統(tǒng)關(guān)系表上的單列外鍵關(guān)系。但是，對于存在模式信息缺失和噪聲數(shù)據(jù)的網(wǎng)絡(luò)表格，以上方法并不適用。

Meihui Zhang等人提出利用隨機性來替代上述外鍵關(guān)系應(yīng)滿足的一系列規(guī)則，并將其應(yīng)用到了單列和多列外鍵關(guān)系檢測中。該方法僅通過屬性列列值的分布評估兩列數(shù)據(jù)分布的隨機性，并且利用隨機性的大小來篩選真正的外鍵關(guān)系。在該方法中，Earth Mover's Distance(EMD，搬土距離)被用來衡量外鍵中的一組屬性值轉(zhuǎn)移到主鍵中另一組屬性值集合上所需要的工作量，并以此值標(biāo)示隨機性大小。當(dāng)外鍵值僅在主鍵的某個區(qū)域內(nèi)均勻分布時，EMD仍會被計算為一個很小的值。

上述現(xiàn)有技術(shù)中的外鍵關(guān)系檢測方法存在的問題如下：

(1)由于網(wǎng)絡(luò)表格并不規(guī)范，數(shù)據(jù)會存在噪聲及表頭缺失的問題，目前大部分依靠表格結(jié)構(gòu)特征的外鍵檢測方法只適用于傳統(tǒng)關(guān)系表，并不適用于網(wǎng)絡(luò)表格。

(2)目前的外鍵檢測算法大都只適用于字符型外鍵關(guān)系的檢測，并不適用于數(shù)字型外鍵關(guān)系的檢測。

(3)目前的外鍵檢測算法是對單列外鍵關(guān)系進(jìn)行檢測，或者，通過隨機性進(jìn)行多列外鍵關(guān)系檢測，這些方法并不能保證外鍵在主鍵中分布的隨機性，由于不能解決局部隨機性問題，效果并不理想。

發(fā)明內(nèi)容

本發(fā)明實施例提供了一種基于分布擬合的網(wǎng)絡(luò)表格間的外鍵關(guān)系檢測方法，以克服現(xiàn)有技術(shù)的問題。

為了實現(xiàn)上述目的，本發(fā)明采取了如下技術(shù)方案。

一種基于分布擬合的網(wǎng)絡(luò)表格間的外鍵關(guān)系檢測方法，包括：

檢測網(wǎng)絡(luò)表格間不同屬性列之間的包含覆蓋關(guān)系，根據(jù)所述包含覆蓋關(guān)系的檢測結(jié)果篩選出所述網(wǎng)絡(luò)表格間的候選外鍵關(guān)系對；

構(gòu)建所述候選外鍵關(guān)系對中候選外鍵和候選主鍵的多維分布圖，計算出所述候選外鍵和候選主鍵的多維分布圖之間的擬合度；

根據(jù)所述候選外鍵和候選主鍵的多維分布圖之間的擬合度判斷所述候選外鍵關(guān)系對是否為真正的外鍵關(guān)系對。

進(jìn)一步地，所述的檢測網(wǎng)絡(luò)表格間不同屬性列之間的包含覆蓋關(guān)系，根據(jù)所述包含覆蓋關(guān)系的檢測結(jié)果篩選出所述網(wǎng)絡(luò)表格間的候選外鍵關(guān)系對，包括：