分布式數據庫中基于局部CON模型的記錄匹配方法

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

(1. 蘇州大學 計算機科學與技術學院，江蘇 蘇州 215006；

2. 哈爾濱工業大學 計算機科學與技術學院，黑龍江 哈爾濱 150001)

1 引言

數據記錄匹配是數據質量管理領域十分重要的研究主題之一。其中，對于大規模的分布式數據記錄匹配是一個基礎而又關鍵的任務，因為獲取數據的準確性將對應用產生較大的影響。有統計數據顯示，美國每年平均有19.5萬余人死于醫療事故，而相當數量的醫療事故是由劣質數據(不一致、不匹配或不完全數據)造成的[1]，因此對數據記錄的匹配已被公認為是數據管理的首要問題之一。

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

本文針對分布式數據記錄不匹配嚴重的情況，同時基于現有方法的效率低且匹配不精確，并需區分數據的水平或垂直分布，且無法實現大規模數據匹配的問題，特加入邏輯推理工具tableau，提出了一種負載平衡的結構化局部 CON模型。該模型由兩大模塊構成，首先是匹配依賴發現部分，利用數據挖掘的關聯規則挖掘來實現；其次是記錄匹配的自動檢測，通過改進標準 tableau而實現，tableau的輸入是匹配依賴以及待匹配的數據庫實例，若tableau封閉，表明不匹配；反之匹配。理論和實驗證明，該方法不需對水平和垂直分割區別對待，不僅能準確發現不匹配，而且可以減少工作量，增加了自動化程度，提高了自動匹配的效率。

2 局部CON模型

本文中分布式數據庫模式用邏輯上典型的一階語言L表示，組成語言L的項是滿足下列條件的最小集合：

1) 任意的變量；

2) 任意的常量符；

3) 如果f是一個n元的函數符，e1,…,en是語言L下的項，則f(e1,…,en)是語言L下的項。

如果項不包含變量，那該項是封閉的。語言L包括一個有限的謂詞集以及一個無限的常量集D。對于每一個數據關系，語言L都有對應的謂詞和它相對應；而D集合中的常量與數據庫值域相對應。

分布式數據庫實例為表示在一個數據庫模式下的有限的關系集合，它可以用語言L下的基原子的有限集表示，或者作為這一語言的海伯倫模型，且有海伯倫值域。

2.1 標準tableau

一個公式集的 tableau推理用一棵分支樹來表示，它是通過不斷地使用tableau規則將公式集拆分為子公式而得到的。tableau推理規則如表1所示。α-規則是向分支中加入新公式延長樹干，而β-規則是將公式拆分成2個子公式分別成為樹干的分支。給定一個公式集 φ，用 TP(φ)表示通過 tableau推演產生的分支樹，并且這棵樹是分支的集合，分支常可以用X,Y…來表示。

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

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

表1 tableau推理規則

2.2 關聯規則挖掘

關聯規則挖掘用于尋找給定數據集中數據項之間的關聯或相關關系。關聯規則揭示了數據項間的未知的依賴關系，根據所挖掘的依賴關系，可以用tableau方法進行匹配檢測。

給定一個事務數據庫，人們通常希望發現事務中的關聯事實，即事務中一些項目的出現必定隱含著同次事務中其他項目的出現，這是關聯規則的一個簡單的描述[9]。

設E是事物數據庫，P={p1,p2,…,pm}是所有項目的集合，其中pj(j=1,…,m)是一個項目。每個事務Tp是項集，Tp?P，標識符為TIDp。

定義1 設A、B是項集，蘊涵式A→B稱規則，其中A?p, B?p，且A∩B=Φ。

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

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

項集的支持度也是指包含該項目集的事務在E中所占的比例。置信度表明了蘊涵的強度，而支持度則表明了A→B模式發生的概率。

定義4 設E是事務集，A、B為項集，若A→B滿足置信度c和支持度s，則稱A→B為關聯規則。

對關聯規則 A→B，若同時滿足最小支持度閾值和最小置信度閾值，則稱其為強規則。一般地，由用戶給定最小置信度和最小支持度，發現關聯規則的任務就是從數據庫中發現那些置信度和支持度都大于給定閾值的強規則，也就是說，挖掘相關規則的關鍵是在大型數據庫中發現強規則。從上述概念可知，關聯規則挖掘的過程分成2個步驟：1)發現所有的大項目集，即支持度大于給定最小支持度閾值的項集；2) 從大的項集中產生關聯規則。

2.3 局部CON模型

局部CON模型由2部分組成，匹配依賴挖掘部分和匹配檢測部分。匹配依賴挖掘利用數據挖掘里面的關聯規則挖掘完成。而匹配檢測利用有效的邏輯推理方法tableau擴展完成。取CON是因為它帶有“共同”的意思，代表所判定記錄同是表示一個實例對象，而這一實例對象只是數據庫的一部分，因此稱為局部CON模型。CON模型與tableau樹是一致的，tableau樹封閉，模型封閉；tableau樹開放，模型開放。下面給出此模型的具體定義。

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

本文利用數據挖掘中有名的關聯規則發現算法的擴展 Apriori+來找出數據記錄相匹配所必須滿足的匹配依賴，之后便可利用擴展的tableau進行匹配檢測。

對標準tableau做擴展，使它更易于判定記錄匹配。在數據庫理論中，常做如下假定。

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

定義6 模型封閉準則。令B是一個帶匹配依賴I的數據庫實例R的tableau分支，分支B若滿足下列條件之一，則B封閉[10～12]。若所有的分支封閉，則模型封閉。

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

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

5) 對于任意項a,?a=a ∈B。

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

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

3 分布式數據分布策略及記錄匹配

3.1 分布式數據

分布式數據庫系統是物理上分散而邏輯上集中的數據庫系統。它使用計算機網絡將地理位置分散而管理和控制又需要不同程度集中的多個邏輯單位連接起來，共同組成一個統一的數據庫系統。每個邏輯單位是能夠獨立工作的計算機，這些計算機稱為站點或結點。每個站點是一個集中式數據庫系統，具有自治處理、完成本站點局部應用的能力；而每個站點上的數據并不是互不相關的，它們構成一個邏輯整體，統一在分布式數據庫管理系統管理下，共同參與并完成全局應用。

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

3.2 CON模型檢測記錄匹配

相對于數據質量的其他核心問題而言，學術界對數據匹配的研究投入很大，并開發了許多算法。本文的CON模型就是一種記錄匹配方法，將其應用到分布式數據庫中，有效地識別出了那些不相匹配記錄，解決了分布式數據的一個難題。

3.2.1 匹配依賴

匹配依賴可以用來從匹配規則中自動地推導出匹配鍵，進而提高記錄匹配的質量和記錄匹配的自動化程度。依照分布式數據記錄特點，特修正傳統 Apriori算法產生了適合記錄匹配約束規則推理的Apriori+算法，見圖1。

圖1 Apriori+算法

3.2.2 匹配檢測

考慮分別具有如下模式的來自不同地點的2個數據源：

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

下面給出的約束是利用關聯規則推出的匹配依賴：

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與此類似。因此，無需將t和 t'在 Pcc和 Pcr上的值逐一比對，而僅需檢查t和 t'在 m d1～md3中出現的那些屬性的值。如果t和 t'匹配 m d1～md3中的任何約束，則 t[Pcc]匹配t'[Pcr]。

下面用局部CON模型來檢測t1和 t4是否匹配，見圖2。

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

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

根據模型封閉定理，對于Smith =J ones會導致模型封閉，因此原數據記錄是不匹配的，即是不同的數據記錄。

圖2 CON模型檢測匹配記錄

圖3 CON模型檢測不匹配記錄

匹配依賴可以自動地由關聯規則推導出來。例如，假設 m d1和如下的關聯規則是已知的：1) 如果t[Cphn]匹配 t'[Cphn]，則t[Addr]和 t'[Addr]表示同一個地址；2) 如果 t[Email]匹配 t '[Email]，則t[Fn,Ln]匹配 t'[Fn,Ln]。經過自動推理，由這些規則可以得到 m d2和 m d3。

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

匹配依賴與傳統的約束不同之處可概括為：1)匹配依賴的定義既基于等價性，又基于相似性；2)匹配依賴是定義在多個關系之間的，而不是定義在單個關系上的；3) 為處理不可靠數據，匹配依賴采用了動態語義，這也不同于傳統約束的靜態語義。

3.2.3 理論分析

定義8 語言L下的模型CON是一個有序對，即CON = ＜ D ,I＞,D 是非空集，稱作CON的值域；I是一個映射關系。

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

1) D是L的封閉項的集合；

2) 對于每一個封閉項e， eI= e 。

海伯倫模型是非常特別的，事實上，它在完整性證明中發揮了重要作用。在設計上，海伯倫模型下的一個賦值A同樣也是語言L下的一個替換。反過來，對于語言L的公式φ， φI.A(A是一個賦值)和φA (A是一個替換)同樣是有意義的。

定理1 假定 C ON =＜ D ,I＞是語言L下的海伯倫模型，對于L的任何項e來說，不一定封閉，且eI.A= ( e A)I。

證明通過在項e上的結構歸納法來論證。

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

接下來假定e是語言 L的常量符 c，則有eI.A= cI.A= cI，和(eA)I= ( cA)I= cI,因此常量時論點也成立。

假定結果對于項 e1,…,en是已知的，且有項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)。所以通過歸納假設論n1n證了這一定理。

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

證明 公式φ是項e的有限組合，并且根據上面的證明，本命題成立。

定理 3 對于由分布于不同站點的數據記錄推導出的匹配依賴，與原數據組成的公式集S，經過模型檢測，若模型封閉，表明記錄不匹配；若模型不封閉，則記錄匹配。

3.2.4 驗證及評測

本節將通過實驗驗證 CON模型檢測分布式數據記錄匹配的準確性和效率。實驗在4臺機器組成的局域網下進行，所用操作系統均為Windows XP、Pentium 4 CPU、主頻3GHz、內存1.25GB，數據庫管理系統是SQL Server 2000，算法用Java語言實現。實驗中的兩個關系分別為信用卡信息和信用卡消費記錄信息，并利用 DataFactory產生用于測試的隨機數據。所有方法在8種不同的數據集上做比較，每個表的記錄數為 10～80k幾種情況。實驗結果如圖4所示。

圖4 實驗結果比較

為驗證 CON模型方法在記錄匹配上的準確性和效率，將其與Common方法、Clustering方法進行比較。Common方法是未做改進的一般方法，而Clustering方法是文獻[5]中采用了Canopy聚類技術的方法。準確性用計算得到的匹配對和應得匹配對的百分比來描述；效率用執行時間來描述。

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

本節通過實驗比較驗證了 CON模型檢測分布式數據記錄匹配的準確性和有效性，可以應用到分布式數據的記錄匹配中，提高數據獲取的質量。

4 結束語

本文針對分布式數據記錄離散分布的不匹配，以及工作量大、自動化程度低等問題，提出了一種負載均衡的結構化局部 CON模型。該模型由兩大模塊構成：匹配依賴發現部分和記錄匹配自動檢測部分。它可以對分布于不同站點的數據信息進行匹配，比如信用卡信息和用戶刷卡的信息匹配等；最后通過理論分析和實驗對這一方法進行了驗證，證明了它匹配的準確性與高效性。

對于分布式數據的數據管理，相關的研究還很有限。記錄匹配僅僅是一個方面，數據的正確性、完整性以及快速的數據傳輸都是非常具有挑戰性的領域，其中有很多問題有待解決，那也將是下一步研究的重點。

[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] 唐懿芳,鐘達夫,嚴小衛.基于聚類模式的多數據源記錄匹配方法[J].小型微型計算機系統, 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].計算機學報, 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] 劉全, 孫吉貴, 于萬鈞. 自由變量語義tableau中δ規則的一種改進方法[J].計算機研究與發展, 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.