分布式數(shù)據(jù)庫(kù)中基于局部CON模型的記錄匹配方法

李嬌，劉全，傅啟明，王庭鋼

(1. 蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006；

2. 哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001)

1 引言

數(shù)據(jù)記錄匹配是數(shù)據(jù)質(zhì)量管理領(lǐng)域十分重要的研究主題之一。其中，對(duì)于大規(guī)模的分布式數(shù)據(jù)記錄匹配是一個(gè)基礎(chǔ)而又關(guān)鍵的任務(wù)，因?yàn)楂@取數(shù)據(jù)的準(zhǔn)確性將對(duì)應(yīng)用產(chǎn)生較大的影響。有統(tǒng)計(jì)數(shù)據(jù)顯示，美國(guó)每年平均有19.5萬(wàn)余人死于醫(yī)療事故，而相當(dāng)數(shù)量的醫(yī)療事故是由劣質(zhì)數(shù)據(jù)(不一致、不匹配或不完全數(shù)據(jù))造成的[1]，因此對(duì)數(shù)據(jù)記錄的匹配已被公認(rèn)為是數(shù)據(jù)管理的首要問(wèn)題之一。

記錄匹配最早在20世紀(jì)40年代應(yīng)用于醫(yī)療領(lǐng)域，當(dāng)時(shí)的目的是識(shí)別不同數(shù)據(jù)庫(kù)的相同個(gè)體的醫(yī)療記錄，以用于對(duì)傳染病的研究。隨著近年來(lái)信息的激增，記錄匹配處理也越來(lái)越受到人們的重視。它不僅應(yīng)用于醫(yī)療領(lǐng)域，在商業(yè)領(lǐng)域也有重要的作用，它能檢測(cè)信用卡欺詐和洗錢行為，甚至還能為稅務(wù)局在信息不完全的情況下，識(shí)別相同的納稅人。關(guān)于這一問(wèn)題已有大量的研究工作，但現(xiàn)有的記錄匹配工具需要相關(guān)領(lǐng)域?qū)＜掖罅康娜斯⑴c，或嚴(yán)重依賴于概率式啟發(fā)規(guī)則或者學(xué)習(xí)式的啟發(fā)規(guī)則，并且還沒(méi)有形成成熟的針對(duì)分布式數(shù)據(jù)記錄匹配的研究。相關(guān)的研究如文獻(xiàn)[2]針對(duì) Web數(shù)據(jù)庫(kù)提出了一種無(wú)監(jiān)督的在線的記錄匹配方法UDD，旨在從結(jié)果記錄中去除重復(fù)記錄用作訓(xùn)練實(shí)例，減輕了人工標(biāo)記訓(xùn)練實(shí)例的麻煩。文獻(xiàn)[3]設(shè)計(jì)了一種領(lǐng)域獨(dú)立的匹配方法，它采用矩陣和一些損失參數(shù)計(jì)算記錄之間的匹配值，但這種方法只能應(yīng)對(duì)結(jié)構(gòu)相同的記錄，并且它所用的參數(shù)很難準(zhǔn)確地確定。文獻(xiàn)[4]和文獻(xiàn)[5]均是基于聚類的思想，前者檢測(cè)冗余記錄并消除冗余數(shù)據(jù)，后者利用Canopy技術(shù)對(duì)多數(shù)據(jù)源的記錄進(jìn)行匹配，提高了效率，但是匹配的準(zhǔn)確度會(huì)下降。文獻(xiàn)[6]對(duì)分布式的關(guān)系型數(shù)據(jù)庫(kù)中數(shù)據(jù)的不一致問(wèn)題進(jìn)行了檢測(cè)，并根據(jù)水平和垂直分片的不同而開發(fā)了不同的方法；而文獻(xiàn)[7]則是有關(guān)記錄匹配規(guī)則，利用技術(shù)確定函數(shù)依賴，找出待匹配屬性，并在不可靠關(guān)系中發(fā)現(xiàn)不匹配。

本文針對(duì)分布式數(shù)據(jù)記錄不匹配嚴(yán)重的情況，同時(shí)基于現(xiàn)有方法的效率低且匹配不精確，并需區(qū)分?jǐn)?shù)據(jù)的水平或垂直分布，且無(wú)法實(shí)現(xiàn)大規(guī)模數(shù)據(jù)匹配的問(wèn)題，特加入邏輯推理工具tableau，提出了一種負(fù)載平衡的結(jié)構(gòu)化局部 CON模型。該模型由兩大模塊構(gòu)成，首先是匹配依賴發(fā)現(xiàn)部分，利用數(shù)據(jù)挖掘的關(guān)聯(lián)規(guī)則挖掘來(lái)實(shí)現(xiàn)；其次是記錄匹配的自動(dòng)檢測(cè)，通過(guò)改進(jìn)標(biāo)準(zhǔn) tableau而實(shí)現(xiàn)，tableau的輸入是匹配依賴以及待匹配的數(shù)據(jù)庫(kù)實(shí)例，若tableau封閉，表明不匹配；反之匹配。理論和實(shí)驗(yàn)證明，該方法不需對(duì)水平和垂直分割區(qū)別對(duì)待，不僅能準(zhǔn)確發(fā)現(xiàn)不匹配，而且可以減少工作量，增加了自動(dòng)化程度，提高了自動(dòng)匹配的效率。

2 局部CON模型

本文中分布式數(shù)據(jù)庫(kù)模式用邏輯上典型的一階語(yǔ)言L表示，組成語(yǔ)言L的項(xiàng)是滿足下列條件的最小集合：

1) 任意的變量；

2) 任意的常量符；

3) 如果f是一個(gè)n元的函數(shù)符，e1,…,en是語(yǔ)言L下的項(xiàng)，則f(e1,…,en)是語(yǔ)言L下的項(xiàng)。

如果項(xiàng)不包含變量，那該項(xiàng)是封閉的。語(yǔ)言L包括一個(gè)有限的謂詞集以及一個(gè)無(wú)限的常量集D。對(duì)于每一個(gè)數(shù)據(jù)關(guān)系，語(yǔ)言L都有對(duì)應(yīng)的謂詞和它相對(duì)應(yīng)；而D集合中的常量與數(shù)據(jù)庫(kù)值域相對(duì)應(yīng)。

分布式數(shù)據(jù)庫(kù)實(shí)例為表示在一個(gè)數(shù)據(jù)庫(kù)模式下的有限的關(guān)系集合，它可以用語(yǔ)言L下的基原子的有限集表示，或者作為這一語(yǔ)言的海伯倫模型，且有海伯倫值域。

2.1 標(biāo)準(zhǔn)tableau

一個(gè)公式集的 tableau推理用一棵分支樹來(lái)表示，它是通過(guò)不斷地使用tableau規(guī)則將公式集拆分為子公式而得到的。tableau推理規(guī)則如表1所示。α-規(guī)則是向分支中加入新公式延長(zhǎng)樹干，而β-規(guī)則是將公式拆分成2個(gè)子公式分別成為樹干的分支。給定一個(gè)公式集 φ，用 TP(φ)表示通過(guò) tableau推演產(chǎn)生的分支樹，并且這棵樹是分支的集合，分支?？梢杂肵,Y…來(lái)表示。

公式集的 tableau樹確定以后，會(huì)產(chǎn)生很多分支。如果在同一分支上存在一個(gè)公式和它的否定，那這一分支就稱為是封閉的，否則它就是開放的。如果樹的每一個(gè)分支都是封閉的，那么就稱這棵樹是封閉的；反之，如果有一個(gè)分支不封閉，那么這棵樹就稱為是不封閉的。

tableau的重要應(yīng)用是判定一個(gè)命題是不是定理。假定F是一個(gè)形式化后的命題，首先對(duì)它整體取非，然后用tableau進(jìn)行推演，如果推演完TP(?F)是封閉的，那么即證明?F是矛盾的，并從反面證明F是永真的，是定理[8]。

表1 tableau推理規(guī)則

2.2 關(guān)聯(lián)規(guī)則挖掘

關(guān)聯(lián)規(guī)則挖掘用于尋找給定數(shù)據(jù)集中數(shù)據(jù)項(xiàng)之間的關(guān)聯(lián)或相關(guān)關(guān)系。關(guān)聯(lián)規(guī)則揭示了數(shù)據(jù)項(xiàng)間的未知的依賴關(guān)系，根據(jù)所挖掘的依賴關(guān)系，可以用tableau方法進(jìn)行匹配檢測(cè)。

給定一個(gè)事務(wù)數(shù)據(jù)庫(kù)，人們通常希望發(fā)現(xiàn)事務(wù)中的關(guān)聯(lián)事實(shí)，即事務(wù)中一些項(xiàng)目的出現(xiàn)必定隱含著同次事務(wù)中其他項(xiàng)目的出現(xiàn)，這是關(guān)聯(lián)規(guī)則的一個(gè)簡(jiǎn)單的描述[9]。

設(shè)E是事物數(shù)據(jù)庫(kù)，P={p1,p2,…,pm}是所有項(xiàng)目的集合，其中pj(j=1,…,m)是一個(gè)項(xiàng)目。每個(gè)事務(wù)Tp是項(xiàng)集，Tp?P，標(biāo)識(shí)符為TIDp。

定義1 設(shè)A、B是項(xiàng)集，蘊(yùn)涵式A→B稱規(guī)則，其中A?p, B?p，且A∩B=Φ。

定義2 設(shè)E是事務(wù)集，A、B為項(xiàng)集，且有規(guī)則 A→B。如果E中，包含A·B事務(wù)所占比例為s%，稱A→B有支持度s，即概率P(A·B)。

定義3 設(shè)E是事務(wù)集，A、B為項(xiàng)集，且有規(guī)則A→B。如果E中，c%的事務(wù)包含A的同時(shí)也包含B，則稱A→B有置信度c，即條件概率P(B | A)。

項(xiàng)集的支持度也是指包含該項(xiàng)目集的事務(wù)在E中所占的比例。置信度表明了蘊(yùn)涵的強(qiáng)度，而支持度則表明了A→B模式發(fā)生的概率。

定義4 設(shè)E是事務(wù)集，A、B為項(xiàng)集，若A→B滿足置信度c和支持度s，則稱A→B為關(guān)聯(lián)規(guī)則。

對(duì)關(guān)聯(lián)規(guī)則 A→B，若同時(shí)滿足最小支持度閾值和最小置信度閾值，則稱其為強(qiáng)規(guī)則。一般地，由用戶給定最小置信度和最小支持度，發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的任務(wù)就是從數(shù)據(jù)庫(kù)中發(fā)現(xiàn)那些置信度和支持度都大于給定閾值的強(qiáng)規(guī)則，也就是說(shuō)，挖掘相關(guān)規(guī)則的關(guān)鍵是在大型數(shù)據(jù)庫(kù)中發(fā)現(xiàn)強(qiáng)規(guī)則。從上述概念可知，關(guān)聯(lián)規(guī)則挖掘的過(guò)程分成2個(gè)步驟：1)發(fā)現(xiàn)所有的大項(xiàng)目集，即支持度大于給定最小支持度閾值的項(xiàng)集；2) 從大的項(xiàng)集中產(chǎn)生關(guān)聯(lián)規(guī)則。

2.3 局部CON模型

局部CON模型由2部分組成，匹配依賴挖掘部分和匹配檢測(cè)部分。匹配依賴挖掘利用數(shù)據(jù)挖掘里面的關(guān)聯(lián)規(guī)則挖掘完成。而匹配檢測(cè)利用有效的邏輯推理方法tableau擴(kuò)展完成。取CON是因?yàn)樗鼛в小肮餐钡囊馑?，代表所判定記錄同是表示一個(gè)實(shí)例對(duì)象，而這一實(shí)例對(duì)象只是數(shù)據(jù)庫(kù)的一部分，因此稱為局部CON模型。CON模型與tableau樹是一致的，tableau樹封閉，模型封閉；tableau樹開放，模型開放。下面給出此模型的具體定義。

定義5 匹配依賴(MD，matching dependencies)。匹配依賴是數(shù)據(jù)記錄相匹配必須要滿足的約束規(guī)則或匹配規(guī)則[7]。利用該匹配依賴及其推理，可以確定匹配鍵，以決定2條記錄是否匹配。

本文利用數(shù)據(jù)挖掘中有名的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法的擴(kuò)展 Apriori+來(lái)找出數(shù)據(jù)記錄相匹配所必須滿足的匹配依賴，之后便可利用擴(kuò)展的tableau進(jìn)行匹配檢測(cè)。

對(duì)標(biāo)準(zhǔn)tableau做擴(kuò)展，使它更易于判定記錄匹配。在數(shù)據(jù)庫(kù)理論中，常做如下假定。

1) 唯一名稱假設(shè)(UNA, unique names assumption)：對(duì)于D中的任何2個(gè)相異常量m、n來(lái)說(shuō)，m≠n；2) 封閉世界假設(shè)(CWA, closed world assumption)：對(duì)于數(shù)據(jù)庫(kù)實(shí)例R，任何的基數(shù)據(jù)庫(kù)原子P(c)，若P(c)?r，那么?P(c)∈ r?，F(xiàn)在，把這2條加入作為判定CON模型是否封閉的條件，即樹分支中一旦出現(xiàn)這樣的情況，那么這一分支封閉。

定義6 模型封閉準(zhǔn)則。令B是一個(gè)帶匹配依賴I的數(shù)據(jù)庫(kù)實(shí)例R的tableau分支，分支B若滿足下列條件之一，則B封閉[10～12]。若所有的分支封閉，則模型封閉。

1) 對(duì)于D中的任意相異常量a與b,a = b∈B 。

4) 對(duì)于任意公式φ,φ∈B且?φ∈B。

5) 對(duì)于任意項(xiàng)a,?a=a ∈B。

條件1)和條件5)考慮的是唯一名稱假設(shè)，條件2)和條件4)考慮的是封閉世界假設(shè)，條件4)是標(biāo)準(zhǔn)tableau定義。需要注意的一點(diǎn)是第一條中的a = b ,若出現(xiàn)?(a=b),那分支是不封閉的，是開放的。

定義7 模型匹配方法。對(duì)于給定的數(shù)據(jù)記錄，首先要利用 Apriori+算法挖掘出匹配依賴，然后對(duì)約束規(guī)則整體非操作，與數(shù)據(jù)實(shí)例一起按照推演規(guī)則推演，最后若所有的分支封閉則該模型封閉，表明記錄不相匹配；若有未封閉分支，則表明記錄匹配。

3 分布式數(shù)據(jù)分布策略及記錄匹配

3.1 分布式數(shù)據(jù)

分布式數(shù)據(jù)庫(kù)系統(tǒng)是物理上分散而邏輯上集中的數(shù)據(jù)庫(kù)系統(tǒng)。它使用計(jì)算機(jī)網(wǎng)絡(luò)將地理位置分散而管理和控制又需要不同程度集中的多個(gè)邏輯單位連接起來(lái)，共同組成一個(gè)統(tǒng)一的數(shù)據(jù)庫(kù)系統(tǒng)。每個(gè)邏輯單位是能夠獨(dú)立工作的計(jì)算機(jī)，這些計(jì)算機(jī)稱為站點(diǎn)或結(jié)點(diǎn)。每個(gè)站點(diǎn)是一個(gè)集中式數(shù)據(jù)庫(kù)系統(tǒng)，具有自治處理、完成本站點(diǎn)局部應(yīng)用的能力；而每個(gè)站點(diǎn)上的數(shù)據(jù)并不是互不相關(guān)的，它們構(gòu)成一個(gè)邏輯整體，統(tǒng)一在分布式數(shù)據(jù)庫(kù)管理系統(tǒng)管理下，共同參與并完成全局應(yīng)用。

分布式數(shù)據(jù)庫(kù)由2部分組成：一部分是關(guān)于應(yīng)用所需要的數(shù)據(jù)的集合，是數(shù)據(jù)庫(kù)的主體；另一部分是關(guān)于數(shù)據(jù)庫(kù)中數(shù)據(jù)結(jié)構(gòu)的定義，以及全局?jǐn)?shù)據(jù)的分片、分布的描述，稱為描述數(shù)據(jù)庫(kù)，也稱數(shù)據(jù)字典、數(shù)據(jù)目錄或元數(shù)據(jù)。數(shù)據(jù)分片非常重要，它將分割后得到的各部分元組分布在不同的站點(diǎn)上，因此數(shù)據(jù)存放的單位是數(shù)據(jù)的邏輯片段。對(duì)關(guān)系型數(shù)據(jù)庫(kù)來(lái)說(shuō)，一個(gè)數(shù)據(jù)的邏輯片段是關(guān)系的一部分。數(shù)據(jù)分布有3種基本方法，水平分布、垂直分布和混合分布，它們是通過(guò)關(guān)系代數(shù)的基本運(yùn)算來(lái)實(shí)現(xiàn)的。水平分布是按特定策略將關(guān)系的元組劃分成若干不相交子集，每個(gè)子集為關(guān)系的一個(gè)邏輯片段，各片段分布到不同節(jié)點(diǎn)上；垂直分布則將關(guān)系的屬性集劃分為若干子集，然后將關(guān)系的鍵和屬性子集的值分布到不同節(jié)點(diǎn)上；混合分布則是水平和垂直分布兩種策略的結(jié)合。分片后的各片段之間需要滿足完備性條件、可重構(gòu)條件和不相交條件。

3.2 CON模型檢測(cè)記錄匹配

相對(duì)于數(shù)據(jù)質(zhì)量的其他核心問(wèn)題而言，學(xué)術(shù)界對(duì)數(shù)據(jù)匹配的研究投入很大，并開發(fā)了許多算法。本文的CON模型就是一種記錄匹配方法，將其應(yīng)用到分布式數(shù)據(jù)庫(kù)中，有效地識(shí)別出了那些不相匹配記錄，解決了分布式數(shù)據(jù)的一個(gè)難題。

3.2.1 匹配依賴

匹配依賴可以用來(lái)從匹配規(guī)則中自動(dòng)地推導(dǎo)出匹配鍵，進(jìn)而提高記錄匹配的質(zhì)量和記錄匹配的自動(dòng)化程度。依照分布式數(shù)據(jù)記錄特點(diǎn)，特修正傳統(tǒng) Apriori算法產(chǎn)生了適合記錄匹配約束規(guī)則推理的Apriori+算法，見(jiàn)圖1。

圖1 Apriori+算法

3.2.2 匹配檢測(cè)

考慮分別具有如下模式的來(lái)自不同地點(diǎn)的2個(gè)數(shù)據(jù)源：

ccard(C n,F n,L n,A ddr,C phn,E mail,T ype)

crecord(C n,F n,L n,A ddr,C phn,E mail,I t em,P rice)

其中，ccard關(guān)系中的每條記錄包含了信用卡信息和持卡人信息：1)信用卡(卡號(hào)Cn，類型Type)；2)持卡人(姓Ln，名Fn，地址Addr，電話Cphn，郵件地址 Email)。在 crecord關(guān)系中每條記錄包含了信用卡支付信息和持卡人信息：1)卡號(hào)為 Cn的信用卡支付了一件價(jià)格為Price、名稱為Item的商品；2)持卡人(姓 Ln，名 Fn，地址 Addr，電話 Cphn，郵件地址Email)。這2個(gè)關(guān)系的實(shí)例如表2和表3所示。給定模式(c card,crecord)的任何實(shí)例(Rcc,Rcr)，在偵測(cè)信用卡欺詐時(shí)，必須確保對(duì)任意元組 t ∈Rcc和t'∈Rcr，如果t[Cn ] = t '[Cn]，則t[Pcc]和t'[Pcr]必然表示同一信用卡持有人，其中有如下的表示即Pcc=[Fn,Ln,Addr,Cphn,Email ]，而Pcr=[Fn,Ln,Addr,Cphn,Email ]。然而，由于數(shù)據(jù)源存在錯(cuò)誤數(shù)據(jù)，無(wú)法簡(jiǎn)單將 t[Pcc]和t'[Pcr]相對(duì)應(yīng)的屬性值兩兩比對(duì)來(lái)判斷二者是否匹配。為此引入匹配依賴，以描述匹配規(guī)則。利用匹配依賴及其推理，可以自動(dòng)找到“最佳”匹配鍵，以決定 t[Pcc]和t'[Pcr]是否匹配。

下面給出的約束是利用關(guān)聯(lián)規(guī)則推出的匹配依賴：

md1ccard[Ln]= crecord[Ln ] ?ccard[Addr ]=crecord[Addr ]? c card[Fn ]≈c record[Fn]→ccard[ti] ?crecord[tj]

md2ccard[Email]= crecord[Email]? card[Addr ]=crecord[Addr]→ ccard[ti]? crecord[tj]md3ccard[Ln ]= crecord[Ln ] ?ccard[Cphn]=crecord[Cphn]? c card[Fn ]≈c record[Fn]→ccard[ti]? crecord[tj]

其中， m d1表述如果 t[Ln,Addr]與t'[Ln,Addr]相等且 t[Fn]和 t'[Fn]在相似操作符“≈”下相似，則t[Pcc]匹配t'[Pcr]，即二者表示同一人。約束 m d2和md3與此類似。因此，無(wú)需將t和 t'在 Pcc和 Pcr上的值逐一比對(duì)，而僅需檢查t和 t'在 m d1～md3中出現(xiàn)的那些屬性的值。如果t和 t'匹配 m d1～md3中的任何約束，則 t[Pcc]匹配t'[Pcr]。

下面用局部CON模型來(lái)檢測(cè)t1和 t4是否匹配，見(jiàn)圖2。

因此，該推演樹是開放的，表明原化簡(jiǎn)式是匹配的。

若是不匹配的記錄，那么就會(huì)在最后的分支段出現(xiàn)類似圖3下面的情況。

根據(jù)模型封閉定理，對(duì)于Smith =J ones會(huì)導(dǎo)致模型封閉，因此原數(shù)據(jù)記錄是不匹配的，即是不同的數(shù)據(jù)記錄。

圖2 CON模型檢測(cè)匹配記錄

圖3 CON模型檢測(cè)不匹配記錄

匹配依賴可以自動(dòng)地由關(guān)聯(lián)規(guī)則推導(dǎo)出來(lái)。例如，假設(shè) m d1和如下的關(guān)聯(lián)規(guī)則是已知的：1) 如果t[Cphn]匹配 t'[Cphn]，則t[Addr]和 t'[Addr]表示同一個(gè)地址；2) 如果 t[Email]匹配 t '[Email]，則t[Fn,Ln]匹配 t'[Fn,Ln]。經(jīng)過(guò)自動(dòng)推理，由這些規(guī)則可以得到 m d2和 m d3。

例如，表中的ccard元組t1和crecord元組 t2可由 m d1匹配，這些元組有相同的Ln和Addr，并有類似的Fn，根據(jù) m d1可以判定它們表示同一人。值得注意的是，雖然 t1和 t2的Email和電話號(hào)碼差別很大，但是仍可判定它們之間的匹配。這就是為什么希望使用匹配依賴。

匹配依賴與傳統(tǒng)的約束不同之處可概括為：1)匹配依賴的定義既基于等價(jià)性，又基于相似性；2)匹配依賴是定義在多個(gè)關(guān)系之間的，而不是定義在單個(gè)關(guān)系上的；3) 為處理不可靠數(shù)據(jù)，匹配依賴采用了動(dòng)態(tài)語(yǔ)義，這也不同于傳統(tǒng)約束的靜態(tài)語(yǔ)義。

3.2.3 理論分析

定義8 語(yǔ)言L下的模型CON是一個(gè)有序?qū)?，即CON = ＜ D ,I＞,D 是非空集，稱作CON的值域；I是一個(gè)映射關(guān)系。

定義9 語(yǔ)言L的 C ON=＜ D ,I＞模型是一個(gè)海伯倫模型，若滿足下列的條件：

1) D是L的封閉項(xiàng)的集合；

2) 對(duì)于每一個(gè)封閉項(xiàng)e， eI= e 。

海伯倫模型是非常特別的，事實(shí)上，它在完整性證明中發(fā)揮了重要作用。在設(shè)計(jì)上，海伯倫模型下的一個(gè)賦值A(chǔ)同樣也是語(yǔ)言L下的一個(gè)替換。反過(guò)來(lái)，對(duì)于語(yǔ)言L的公式φ， φI.A(A是一個(gè)賦值)和φA (A是一個(gè)替換)同樣是有意義的。

定理1 假定 C ON =＜ D ,I＞是語(yǔ)言L下的海伯倫模型，對(duì)于L的任何項(xiàng)e來(lái)說(shuō)，不一定封閉，且eI.A= ( e A)I。

證明通過(guò)在項(xiàng)e上的結(jié)構(gòu)歸納法來(lái)論證。

假定e是一個(gè)變量 v，則有 eI.A= vI.A= vA，(e A)I= ( vA)I= v A ,I在封閉的項(xiàng)上是恒等式，并且最終 vA= v A，e是變量這一情況論點(diǎn)成立。

接下來(lái)假定e是語(yǔ)言 L的常量符 c，則有eI.A= cI.A= cI，和(eA)I= ( cA)I= cI,因此常量時(shí)論點(diǎn)也成立。

假定結(jié)果對(duì)于項(xiàng) e1,…,en是已知的，且有項(xiàng)f(e,…,e)， 則eI.A=[f(e , …,e)]I.A=fI( eI.A,…,1n1n1eI.A)，因此(eA)I=[f(e , …,e)A]I=[f(eA,…,n1n1eA)]I=fI( (eA)I, …,( eA)I)。所以通過(guò)歸納假設(shè)論n1n證了這一定理。

定理 2假定 C ON=＜ D ,I＞是語(yǔ)言L下的一個(gè)海伯倫模型。對(duì)于L的公式φ,有 φI.A=( φ A )I。

證明 公式φ是項(xiàng)e的有限組合，并且根據(jù)上面的證明，本命題成立。

定理 3 對(duì)于由分布于不同站點(diǎn)的數(shù)據(jù)記錄推導(dǎo)出的匹配依賴，與原數(shù)據(jù)組成的公式集S，經(jīng)過(guò)模型檢測(cè)，若模型封閉，表明記錄不匹配；若模型不封閉，則記錄匹配。

3.2.4 驗(yàn)證及評(píng)測(cè)

本節(jié)將通過(guò)實(shí)驗(yàn)驗(yàn)證 CON模型檢測(cè)分布式數(shù)據(jù)記錄匹配的準(zhǔn)確性和效率。實(shí)驗(yàn)在4臺(tái)機(jī)器組成的局域網(wǎng)下進(jìn)行，所用操作系統(tǒng)均為Windows XP、Pentium 4 CPU、主頻3GHz、內(nèi)存1.25GB，數(shù)據(jù)庫(kù)管理系統(tǒng)是SQL Server 2000，算法用Java語(yǔ)言實(shí)現(xiàn)。實(shí)驗(yàn)中的兩個(gè)關(guān)系分別為信用卡信息和信用卡消費(fèi)記錄信息，并利用 DataFactory產(chǎn)生用于測(cè)試的隨機(jī)數(shù)據(jù)。所有方法在8種不同的數(shù)據(jù)集上做比較，每個(gè)表的記錄數(shù)為 10～80k幾種情況。實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 實(shí)驗(yàn)結(jié)果比較

為驗(yàn)證 CON模型方法在記錄匹配上的準(zhǔn)確性和效率，將其與Common方法、Clustering方法進(jìn)行比較。Common方法是未做改進(jìn)的一般方法，而Clustering方法是文獻(xiàn)[5]中采用了Canopy聚類技術(shù)的方法。準(zhǔn)確性用計(jì)算得到的匹配對(duì)和應(yīng)得匹配對(duì)的百分比來(lái)描述；效率用執(zhí)行時(shí)間來(lái)描述。

從圖 4(a)中可以看出，Common方法和Clustering方法的準(zhǔn)確性會(huì)隨著數(shù)據(jù)的增大而降低，而CON方法的準(zhǔn)確性卻隨著數(shù)據(jù)集的增大而提高，這是因?yàn)?CON模型算法利用了數(shù)據(jù)挖掘的關(guān)聯(lián)挖掘來(lái)找到匹配依賴，并用改進(jìn)的tableau方法來(lái)實(shí)現(xiàn)匹配記錄的自動(dòng)檢測(cè)，通過(guò)匹配依賴和數(shù)據(jù)記錄的tableau推理，得出匹配結(jié)果，因此準(zhǔn)確性高，尤其在數(shù)據(jù)記錄數(shù)量較大時(shí)效果更加明顯。Common方法和Clustering方法在數(shù)據(jù)集較小時(shí)準(zhǔn)確率比較高，但是隨著數(shù)據(jù)記錄的增大準(zhǔn)確性降低；二者數(shù)據(jù)變化趨勢(shì)相似，匹配的準(zhǔn)確性低。圖4(b)是Clustering方法在單機(jī)上的執(zhí)行時(shí)間和 CON模型在分布式環(huán)境中的執(zhí)行時(shí)間的比較，遺憾的是目前還沒(méi)有針對(duì)分布式數(shù)據(jù)庫(kù)的記錄匹配的，因而這樣的比較還難以準(zhǔn)確顯示 CON方法的高效性。通過(guò)數(shù)據(jù)分析可知，分布式檢測(cè)的時(shí)間復(fù)雜度要高，但是當(dāng)數(shù)據(jù)記錄數(shù)較大時(shí)，差值明顯減少。

本節(jié)通過(guò)實(shí)驗(yàn)比較驗(yàn)證了 CON模型檢測(cè)分布式數(shù)據(jù)記錄匹配的準(zhǔn)確性和有效性，可以應(yīng)用到分布式數(shù)據(jù)的記錄匹配中，提高數(shù)據(jù)獲取的質(zhì)量。

4 結(jié)束語(yǔ)

本文針對(duì)分布式數(shù)據(jù)記錄離散分布的不匹配，以及工作量大、自動(dòng)化程度低等問(wèn)題，提出了一種負(fù)載均衡的結(jié)構(gòu)化局部 CON模型。該模型由兩大模塊構(gòu)成：匹配依賴發(fā)現(xiàn)部分和記錄匹配自動(dòng)檢測(cè)部分。它可以對(duì)分布于不同站點(diǎn)的數(shù)據(jù)信息進(jìn)行匹配，比如信用卡信息和用戶刷卡的信息匹配等；最后通過(guò)理論分析和實(shí)驗(yàn)對(duì)這一方法進(jìn)行了驗(yàn)證，證明了它匹配的準(zhǔn)確性與高效性。

對(duì)于分布式數(shù)據(jù)的數(shù)據(jù)管理，相關(guān)的研究還很有限。記錄匹配僅僅是一個(gè)方面，數(shù)據(jù)的正確性、完整性以及快速的數(shù)據(jù)傳輸都是非常具有挑戰(zhàn)性的領(lǐng)域，其中有很多問(wèn)題有待解決，那也將是下一步研究的重點(diǎn)。

[1] HERZOG T, SCHEUTEN F, WINKLER W. Data Quality and Record Linkage Techniques[M]. New York: Springer, 2007

[2] SU WEIFANG, WANG JIYING, FREDERICK H. Record matching over query results from multiple Web databases[J]. IEEE Transaction on Knowledge and Data Engineering, 2010, 22(4): 578-589

[3] MONGE A, ELKAN C. An efficient domain-independent algorithm for detecting approximately duplicate database records[A]. Proceedings of SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery[C]. Tucson, Arizona, 1997

[4] VERYKIOS S, AHMED K. Automating the approximate record matching process[J]. Information Sciences, 2000, 126(1): 83-98

[5] 唐懿芳,鐘達(dá)夫,嚴(yán)小衛(wèi).基于聚類模式的多數(shù)據(jù)源記錄匹配方法[J].小型微型計(jì)算機(jī)系統(tǒng), 2005, 26(9): 1546-1550.TANG Y F, ZHONG D F, YAN X W. Matching data records among multi data sources based on clustering techniques[J]. Journal of Chinese Computer Systems, 2005, 26(9): 1546-1550

[6] FAN W, GEERTS F, SHU A. Detecting inconsistencies in distributed data[A]. 2010 IEEE 26th International Conference on Data Engineering[C]. California, America, 2010. 64-75

[7] FAN W F, JIA X B, LI J Z. Reasoning about record matching rules[A].Proceedings of the VLDB Endowment[C]. Lyon, France, 2009.407-418.

[8] FITTING M. First-order Logic and Automated Theorem Proving[M].New York: Springer Verlag, 1996

[9] JIAO L C, LIU F, GOU S P. Intelligent Data Mining and Knowledge Discovery[M]. Xi’an: Xi’an University of Electronic Science and Technology Press, 2006.

[10] 劉全, 孫吉貴.提高一階多值邏輯tableau推理效率的布爾剪枝方法[J].計(jì)算機(jī)學(xué)報(bào), 2003, 26(9): 1165-1170.LIU Q, SUN J G. Improvement of the efficiency of tableau reasoning pruning method about the first-order multi valued boolean logic[J].Chinese Journal of Computers, 2003, 26(9): 1165-1170.

[11] BERTOSSI L, SCHWIND C. Database repair and analytic tableaux[A]. Foundations of Information and Knowledge Systems[C].Springer LNCS 2284, 2002. 5-35.

[12] 劉全, 孫吉貴, 于萬(wàn)鈞. 自由變量語(yǔ)義tableau中δ規(guī)則的一種改進(jìn)方法[J].計(jì)算機(jī)研究與發(fā)展, 2004, 41(7): 1068-1073.LIU Q, SUN J G, YU W J. A improvement method of δ rule in free variable semantic tableau[J]. Journal of Computer Research and Development, 2004, 41(7): 1068-1073.