分布式數據不一致性檢測的實現與優化

王海潔　黃沈濱　朱振華

摘 要：數據的不一致性檢測是數據清洗中一個重要的主題。傳統集中式數據的不一致性檢測問題可以使用基于SQL的技術得到解決，而對于分布式的數據，往往面臨著諸多挑戰。目前研究者提出了基于函數條件依賴的不一致性檢測技術對該問題進行了深入研究，將分布式不一致性檢測問題轉化成最優化問題，并提出了若干可行的解決算法。本文介紹了分布式數據下的基于函數條件依賴的不一致性檢測問題，并實現了基于最優化問題的分布式檢測算法，最后組織相關實驗進行驗證和改進。

關鍵詞：分布式數據；不一致性；條件函數依賴；最優化

中圖分類號：TP391文獻標識號：A

Inconsistency Detection in Distributed Data： Implement， Meliorate

WANG Haijie1，HUANG Shenbin1， ZHU Zhenhua2

（1 Network and Information Center， Harbin Institute of Technology， Harbin 150001， China；

2 School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）

Abstract： Detecting inconsistency is one of the central issues in data cleaning. There have been effective methods based on SQL techniques to detect inconsistency in centralized database. However， its far more challenging when the database is distributed. There have been some studies on data inconsistency that is based on conditionalfunctionaldependency， formulating the inconsistency detecting problems as optimization problems， in which several effective algorithms were developed. This paper introduces the detection problem of inconsistency on distributed data， which is based on the conditional functional dependencies. Then， the paper develops the characterizations of the conditional functional dependencies， the fragment of dataset and the optimization problem and relevant algorithms of inconsistency detection. Finally， the paperorganizes several experiments to verify and meliorate these algorithms.

Keywords： Distributed Data； Inconsistency； Conditional FunctionalDependency； Optimizations

0 引言

數據庫技術和系統已成為信息化社會基礎建設的重要支撐[1]，數據質量問題也隨即逐漸獲得了人們的矚目和關注。最近統計表明，美國企業每年花費數十億美元用于處理臟數據[2]。數據清洗是一個密集且復雜的過程，據研究估計，一個典型的數據倉儲項目研發中約有30%～80%的時間是在進行數據清洗。數據清洗問題中的一個重要主題就是數據的一致性，因而其在數據質量中也有著關鍵性的核心位置。

數據管理中一個重點技術問題就是信息來源可能隱含的沖突性。這些沖突將會體現在不同的層次上：關系模式的沖突、數據表現的沖突、數據取值的沖突[3]。而數據的不一致性，則常常用來描述這些沖突。不一致性的檢測就是數據質量和數據清洗中核心焦點問題之一。

對于傳統的集中式數據庫，數據的不一致性已開發有較為成熟的基于SQL的檢測技術。然而，當數據關系零散地分布在不同站點之間，現有技術則很難完成不一致性檢測。對于該問題，文[4]給出了一種新穎的不一致性約束的定義，其主要立基于傳統的函數依賴性約束拓展成條件函數依賴性并提供了若干不一致性的檢測技術。文獻[5]又基于該不一致性約束的定義進行了分布式數據下的拓展，并對數據劃分給出了規范定義，由此即將分布式的檢測問題規范化為最優化問題，進而提出了若干有效的檢測算法。

1相關工作

目前，數據清洗方面的研究大多集中于相似性數據去重的合并與清除問題，或者是檢測數據的域差異和結構沖突問題，以及通過制定約束性條件來表示數據的一致性，并檢測數據中違反了約束條件的作為數據的不一致性。現有工作大多都是基于傳統的依賴性約束的拓展，例如函數依賴性或者全依賴性等。傳統的依賴性約束主要是為設計關系模式而形成或產生的，常常不足以涵蓋數據中蘊含的語義關系。文獻[4]拓展了傳統的函數依賴性約束，其中就提出了條件函數依賴性（Conditional Functional Dependencies，CFDs）來描述不一致性的約束條件。在傳統的集中式數據庫中，給定一個CFDs約束條件集，只需一個固定數量的SQL查詢就能夠自動的在多項式時間內找出數據庫中違反了約束條件的元組集。這種SQL技術往往用于檢測eCFDs約束條件下的不一致性，其中的eCFDs則是CFDs的一種支持邏輯析取和邏輯否的有效拓展[5]。然而，這種SQL技術還是不能解決分布式數據的不一致性檢測，而這個主題卻遠遠比集中式數據領域要更具挑戰性。此外，另有文獻[6]基于CFD進行了分布式數據下的拓展，對數據的劃分進行了規范定義，并將分布式的檢測問題規范化成最優化問題，而且也提出了若干有效的檢測算法。

2分布式數據的不一致性檢測

數據中的不一致性，是通過CFDs的違例來描述的。對于給定的一個CFD ：（XY， Tp）和一個的實例D，想要找到D中所有違反了的元組構成的元組集，記作Vio（， D）。對于一個CFDs集，在此定義Vio（， D）來表示所有Vio（， D）并集當。

對于分布式數據的不一致性檢測，本次研究將其轉換成最小化網絡傳輸或者最小化響應時間的最優解問題。研究中考慮關系模式R的一個實例D，且D被水平或者垂直地劃分成若干片段（D1，D2，...，Dn）。為此假設這些片段分布式地部署在不同的站點上，例如對i[1，n]，Di部署在站點Si上，并且若ij則Si和Sj是不同的站點。給定一個定義在關系模式R且有一個分布式部署實例D上的CFDs集，CFDs的檢測問題就是尋找Vio（， D）。

不論是最小化網絡傳輸還是最小化響應時間，分布式數據的不一致性檢測的主要思路均是通過網絡傳輸使得數據在分布式站點上能夠進行本地檢測，從而可以采用傳統集中式數據庫中的基于SQL的檢測技術來完成分布式數據的檢測。

2.1最小化網絡傳輸

為了刻畫網絡傳輸，研究中使用m（i，j，t）來表示一個通信原語，具體表示從站點Sj向Si傳輸一個元組t，也即一個元組傳輸。一個分布式的檢測算法常常不可避免地導致一個元組集的傳輸M。然而，多數情況下，網絡傳輸最小化的條件下不一致性檢測則是重要的。

考慮R上的一個實例D，且D被水平地劃分成（D1，D2，...，Dn），以及一個元組傳輸集M。對于任意i[1，n]，使用M（i）來表示M中形如m（i，j，t），例如，M中所有的傳輸到站點Si的元組集。此處令D'i= DiM（i）。

研究中，稱一個CFD 能夠在網絡傳輸M后進行本地檢測，當Vio（， D）=i[1，n]Vio（， D'i）。同時稱整個CFDs集能夠在網絡傳輸M后進行本地檢測，當CFDs中每一個均能在網絡傳輸M后本地檢測。

最小化網絡傳輸條件下的CFD不一致性檢測問題就是給定一個CFDs集Σ和一個水平分布式部署的數據集D作為輸入，尋找一個網絡傳輸M使得：

（1）Σ能夠在M后本地檢測；

（2）|M|的取值最小。

直觀地，研究的目標便是檢測D上關于Σ的違規元組集，并且網絡傳輸還要是最小。

2.2最小化響應時間

研究中，使用一個簡單的代價模型來估測響應時間，包含網絡傳輸時間和各個站點獨立檢測CFD違規的時間。考慮一個CFDs集合Σ，一個水平劃分的數據實例D =（D1，…，Dn），以及一個網絡傳輸集M使得M完成后能夠被本地檢測。我們用cost（D， Σ，M）表示估計的響應時間如下：

（1）

其中，ct表示網絡傳輸率，p表示數據包的大小，D'i= DiM（i），check（D'i，Σ）則表示通過調用對集中式數據的檢測算法來檢測D'i中違反Σ的元組的時間開銷。直觀地，cost（D， Σ， M）由兩個因素決定：

（1）由每個站點向其他站點的最大網絡傳輸時間；

（2）每個站點各自最大本地檢測不一致性時間。

易知每個站點并行地向其他站點發送數據，且在接受了其他站點發送的數據后，每個站點并行進行本地檢測。

最小化響應時間條件下的CFD不一致性檢測問題便是對于給定的CFDs集Σ和水平劃分的數據集D作為輸入，尋找一個網絡傳輸集M使得：

（1）所有的站點在網絡傳輸M后能夠對Σ進行本地檢測；

（2）cost（D， Σ， M）是最小的。

2.3分布式檢測算法

對于垂直劃分的數據，不一致性檢測往往很復雜甚至是NP難問題。而且，即便在更為簡單的水平劃分的數據下，完成單個CFD的不一致性檢測也是很復雜的，因此本文僅討論水平分布部署在不同站點的數據下如何有效地檢測單個CFD的違例。

水平分布的數據下，對于單個CFD有集中式的檢測算法和并行的檢測算法。這兩類算法均對各個分布式站點的本地數據進行統計，而后基于這些統計數據依照最小化網路傳輸或者最小化響應時間的原則，選定相應的協調站點將需要檢測的數據傳輸到協調站點進行本地檢測。而對于一個CFDs集，通常使用流水處理每一個CFD的方法來完成檢測。

2.3.1 集中式檢測算法（CTRDETECT）

集中式檢測算法的思想是：首先為待檢測的CFD ：（XY， Tp）尋找一個站點Sj作為協調站點；然后，所有非協調站點中所有與待檢測相關的元組都將傳送給協調站點Sj；最后，由協調站Sj在本地完成的檢測任務。算法可以描述如表1所示。

表1 算法CTRDETECT

Tab.1 Algorithm CTRDETECT

輸入：一個CFD：（XY， Tp）以及一個水平劃分的數據實例D =（D1，…，Dn）。

輸出：Vio（， D）

/*在每個站點Sj上并行地執行如下操作*/

1 統計本地數據，求LHS（i），令lstat（i） = |LHS（i）|。

2 將lstat（i）值傳給其他站點。

3 選擇擁有最大lstat（i）值的站點作為協調站點，假設為Sj。

4 任何SiSj，發送M（j，i） = LHS（i）到協調站點Sj，等待Sj的檢測結果；

對于協調站點Sj，令M（j）=i[1，n]M（j，i），則D'j=LHS（i）M（j），對D'j進行本地檢測，將檢測結果Vio（， D'i）發送給其他站點。

5 返回檢測結果Vio（， D）

該算法的關鍵就是協調站點如何選擇，該站點的選擇依據應該滿足最優化的兩個條件之一，即網路傳輸最小或者響應時間最小。對此，研究定義LHS（i）來描述第i個站點上滿足CFD中某個或某些模型元組的左部取值的元組構成的集合，也就是說LHS（i）={tSi|tpTpt[X]tp[X]}，如此將可選擇|LHS（i）|最大的站點作為協調站點，并且使得網絡傳輸最小。顯而易見，對于集中式檢測來說，網絡傳輸最小也就是響應時間最小。

2.3.2 并行式檢測算法（PATDETECT）

并行式算法的關鍵是在集中式算法上增加并行度，先將元組模型集Tp按照元組模型的左側取值中所含有的通配符個數遞增進行排序，假設排序之后為Tp={t1p，t2p，...，tkp}，且對于任意的ij有tip 中左側取值含有的通配符的數量要小于或者等于tip。研究定義一個函數：DiTp，其含義為對于任意一個Di中的元組t，則有 （t）=j，其中tjp 是排序后的Tp中滿足t[X]tjp[X]的首個元組模型。于是，可以通過將站點上的數據片段Di進一步劃分，即Di=H1iH2i...Hki，其中Hji={tDi| （t）=j }。這樣對于給定的=（XY， Tp），： DiTp和Di=j[1，k]Hji，同上可知，Hji={tDi| （t）=j }，那么就有Vio（， D）=j[1，k]Vio（j， i[1，n]Hji），其中j=（XY， {tjp}）。也就是說，CFD的違例可以通過的劃分對每個j單獨檢測而獲得。于是，即可以并行地對j在數據片段Hji上采用集中式的檢測思路完成檢測，再將并行檢測的結果合并便可得最終的檢測結果。

先考慮最小化網絡傳輸的情況，網絡傳輸最小的并行式檢測算法PATDETECTS可以描述則如表2所示。

表2 算法PATDETECTS

Tab.2Algorithm PATDETECTS

輸入：一個CFD ：（XY， Tp={t1p，t2p，...，tkp}）以及一個水平劃分的數據實例D =（D1，…，Dn）。

輸出： Vio（， D）

/*在每個站點Si上并行地執行如下操作*/

1 計算i：DiTp；

2 /*對本地的數據片段進行劃分Di=H1iH2i...Hki*/

for eachl[1，k]do

Hli={tDi|i （t）=l }；lstat（i，l）=|Hli |；將Hli的值傳送給其他站點；

3 for eachl[1，k]do /*選擇協調站點*/

選擇lstat（i，l）值最大的站點作為l的協調站點；

將Hli發送給協調站點；

4 本地檢測Vio（l， i[1，n]Hli）；/*并行地在協調站點上對tlp本地檢測*/

5 合并檢測結果：Vio（， D）=j[1，k]Vio（j， i[1，n]Hji）

6 返回檢測結果Vio（， D）

首先，在各個站點并行地對本地的數據片段依照i：DiTp進行劃分。然后對于每一個本地數據片段Hji執行CTRDETECT，從而并行地完成檢測，再將結果實現合并。在選擇協調站點時，應滿足總的網絡傳輸最小。為了描述這個網絡傳輸開銷，過程中引入：Tp{1，2，...，n}來表示Tp中每個元組模型對協調站點的抉擇方式，也即對于任意tjpTp，其協調站點為 。對于站點Si，其他站點Sj（ji）發送其待檢測的元組到Si，網絡傳輸用 來表示。那么在這種選擇協調點的情況下，網絡傳輸代價可以描述為costS（）=Σni=1|M（i）|=Σni=1Σnj=1|M（i，j）|。

由于|M（i，j）|=sumkl=1lstat（j，l），其中lstat（j，l）=|Hlj|。當Sm是所有站點中需要向其他站點傳輸元組數量最多的，也即擁有最大的lstat（j，l）站點時，則可以令（tlp）=m從而得到最優的傳輸代價。最小化響應時間的并行式檢測算法PATDETECTRT與最小化網絡傳輸的并行式檢測算法有一定的不同之處，最明顯的不同體現在對于協調站點的選擇上。為此將同樣令：Tp{1，2，...，n}來表示Tp中每個元組模型對協調站點的抉擇方式。對于任意一種協調站點的選擇方式，從站點Sj向Si傳輸的元組集合同樣用 表示，且M（i）=j[1，n]M（i，j），甚至|M（i）|和| M（i，j）|均可在本地統計數據中通過計算得出結果。為了使響應時間最小，情況下的響應時間開銷可以描述為：

（2）

其中本地檢測的時間開銷為check（DjM（j），）=| DjM（j）|log（|DjM（j）|）。

選擇協調站點時，采用貪心算法來進行決策。令l-1表示排序后的Tp中前（l-1）個元組模型的協調站點決策，而結合第l個元組模型tlp，對于l的決策，即需考慮在l-1的基礎上選擇l（tlp），且使總的響應時間增量為最少。算法PATDETECTRT的描述和PATDETECTS相似，只是在選擇協調站點時改換成貪心算法即可。

3實驗

3.1 實驗環境

本文中實驗硬件環境為節點個數為10，CPU和內存的配置分別為Interi7-3770（3.40GHz）和32GB。軟件操作系統采用了Ubuntu 12.04.2LTS，開發語言為Java，數據庫則選用了MySQL。

3.2 實驗數據

用于測試的實驗數據來自TPC-H生成的1G數據，使用表lineitem作為測試用的數據集，其中總共包含600多萬條記錄。實驗時，將這六百多萬條元組均分成60份，每份包含約10萬條記錄，各個分布式站點交叉導入這些數據作為本地數據片段。

lineitem表共包含16個屬性，屬性類型包含整型、浮點型、日期型以及字符串型等。針對lineitem表，規劃設計了10條CFD約束規則對應182個元組模型作為不一致性的約束集進行檢測試驗。其中，第1條CFD不含有通配符，可以在本地檢測，第2，3條CFD僅涉及數據集中的少部分數據需要檢測，第4～7條涉及數據集中的大部分數據需要檢測，第8～10條則是傳統的FD。

3.3 分布式站點對算法的影響

研究分別在2、4、6、8和10個節點上測試了CTRDETECT算法和PATDETECT算法，各自比較了多條CFD在響應時間和網絡傳輸上的變化趨勢。

從圖1中可以看出，隨著分布式站點數的增加，PATDETECTS的網絡傳輸會增加。這是因為隨著站點的增多，每個站點上分布的元組少了。類似地，作為協調站點上的待測元組也少了，而總待測元組是不變的，所以相應的網絡傳輸應該更多。與其相應地，CTRDETECT與PATDETECTRT也有相似的實驗結果。

圖1 PATDETECTS的網絡傳輸圖 2 PATDETECTS的響應時間

Fig.1PATDETECTS data shipment Fig.2PATDETECTS response time

從圖2可看出，隨著分布式站點的增多，PATDETECTS的響應時間隨之減少。這是因為站點增多后，各個模型元組并發檢測的協調站點更趨發散地分布于各個分布式站點中，每個站點上執行并發檢測的流程少了，網絡傳輸和本地檢測都會更快。同理，CTRDETECT與PATDETECTRT也有相似實驗結果。

3.4 數據集對算法的影響

研究在10個節點上，分別對不同大小的數據集進行了10條CFD的檢測實驗。鑒于集中式檢測算法的效率過低，將僅是針對PATDETECTS和PATDETECTRT兩個算法進行實驗，由結果來分析網絡傳輸和響應時間的變化趨勢。限于篇幅，只給出了PATDETECTRT的實驗結果，PATDETECTS結果與之類似。

從圖3看出，在并行式檢測算法中，隨著數據集總大小的增加，完成檢測的網絡傳輸開銷也在增長，并且是呈現近乎線性的增長。這是因為待檢測數據往往是隨著數據集的增大而線性遞增的，為此網絡傳輸開銷也必然呈線性增長。

圖3 PATDETECTRT的網絡傳輸 圖4 PATDETECTRT的響應時間

Fig.3PATDETECTRTdata shipment Fig.4PATDETECTRTresponse time

從圖4中可以看出，隨著數據集增大，響應時間開銷在增加，這是顯而易見的，但是這一趨勢不像網絡傳輸那樣表現為線性增長規律，因為與數據集增大呈線性增長的是待檢測數據的規模，也就是本地檢測時間的規模，而這個本地檢測的時間則由于算法的并行性，各個站點存在差別，使其不一定會呈現線性增長。另外，待檢測數據的網絡傳輸開銷也存在不確定性，因為可能會出現網絡阻塞和端口占用阻塞等復雜情況。

4結束語

本文闡述了分布式數據的不一致性檢測問題，并對分布式的檢測算法進行了實現，同時設計了若干組相關的實驗對檢測算法展開了較為全面的分析，最后進行了優化嘗試，且通過實驗對優化效果實施了相應評估。

通過實驗結果可以看出，CTRDETECT算法和PATDETECT算法均能很好地解決分布式數據的不一致性檢測問題。并且隨著分布式站點的增多，分布式檢測算法的網絡傳輸呈明顯的增長趨勢，響應時間則呈一定下降趨勢。而隨著總的數據集的增大，分布式檢測算法的網路傳輸即呈現線性的增長趨勢，而響應時間則呈現一種趨勢漸緩的非線性增長。

參考文獻：

[1] 周傲英， 金澈清， 王國仁， 等. 不確定性數據管理技術研究綜述[J]. 計算機學報， 2009， 32（1）： 1-16.

[2] ECKERSON W W. Data quality and the bottom line： Achieving business success through a commitment to high quality data[J]. The Data Warehousing Institute， 2002： 1-36.

[3] ANOKHIN P， MOTRO A. Data integration： Inconsistency detection and resolution based on source properties[C]//Proceedings of FMII-01， International Workshop on Foundations of Models for Information Integration 2001， Viterbo：FMIDO， 2001：1-15.

[4] FAN W， GEERTS F， JIA X， et al. Conditional functional dependencies for capturing data inconsistencies[J]. ACM Transactions on Database Systems （TODS）， 2008， 33（2）： 1-39.

[5] GUPTA A， SAGIV Y， ULLMAN J D， et al. Constraint checking with partial information[C]//Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems 1994， Minnesota： ACM， 1994： 45-55.

[6] FAN W， GEERTS F， MA S， et al. Detecting inconsistencies in distributed data[C]// Proceedings of IEEE 26th International Conference on Data Engineering 2010， California： IEEEComputer Society， 2010： 64-75.