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

2、on in Distributed Data： Implement， Meliorate1 Network and Information Center， Harbin Institute of Technology， Harbin 150001， China；2 School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， ChinaAbstract： Detecting inconsistency is one of the central issues in data c

3、leaning. 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

4、 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 characterization

5、s 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 Funct

6、ionalDependency； Optimizations0 引言數據管理中一個重點技術問題就是信息來源可能隱含的沖突性。這些沖突將會表達在不同的層次上：關系形式的沖突、數據表現的沖突、數據取值的沖突3。而數據的不一致性，那么常常用來描繪這些沖突。不一致性的檢測就是數據質量和數據清洗中核心焦點問題之一。對于傳統的集中式數據庫，數據的不一致性已開發有較為成熟的基于SQL的檢測技術。然而，當數據關系零散地分布在不同站點之間，現有技術那么很難完成不一致性檢測。對于該問題，文4給出了一種新穎的不一致性約束的定義，其主要立基于傳統的函數依賴性約束拓展成條件函數依賴性并提供了假設干不一致性的檢測技術。文

7、獻5又基于該不一致性約束的定義進展了分布式數據下的拓展，并對數據劃分給出了標準定義，由此即將分布式的檢測問題標準化為最優化問題，進而提出了假設干有效的檢測算法。1相關工作目前，數據清洗方面的研究大多集中于相似性數據去重的合并與去除問題，或者是檢測數據的域差異和構造沖突問題，以及通過制定約束性條件來表示數據的一致性，并檢測數據中違犯了約束條件的作為數據的不一致性?，F有工作大多都是基于傳統的依賴性約束的拓展，例如函數依賴性或者全依賴性等。傳統的依賴性約束主要是為設計關系形式而形成或產生的，常常缺乏以涵蓋數據中蘊含的語義關系。文獻4拓展了傳統的函數依賴性約束，其中就提出了條件函數依賴性Conditi

8、onal Functional Dependencies，CFDs來描繪不一致性的約束條件。在傳統的集中式數據庫中，給定一個CFDs約束條件集，只需一個固定數量的SQL查詢就可以自動的在多項式時間內找出數據庫中違犯了約束條件的元組集。這種SQL技術往往用于檢測eCFDs約束條件下的不一致性，其中的eCFDs那么是CFDs的一種支持邏輯析取和邏輯否的有效拓展5。然而，這種SQL技術還是不能解決分布式數據的不一致性檢測，而這個主題卻遠遠比集中式數據領域要更具挑戰性。此外，另有文獻6基于CFD進展了分布式數據下的拓展，對數據的劃分進展了標準定義，并將分布式的檢測問題標準化成最優化問題，而且也提出了假

9、設干有效的檢測算法。 2分布式數據的不一致性檢測數據中的不一致性，是通過CFDs的違例來描繪的。對于給定的一個CFD ：XY， Tp和一個的實例D，想要找到D中所有違犯了的元組構成的元組集，記作Vio， D。對于一個CFDs集，在此定義Vio， D來表示所有Vio， D并集當。不管是最小化網絡傳輸還是最小化響應時間，分布式數據的不一致性檢測的主要思路均是通過網絡傳輸使得數據在分布式站點上可以進展本地檢測，從而可以采用傳統集中式數據庫中的基于SQL的檢測技術來完成分布式數據的檢測。2.1最小化網絡傳輸為了刻畫網絡傳輸，研究中使用mi，j，t來表示一個通信原語，詳細表示從站點Sj向Si傳輸一個元組

10、t，也即一個元組傳輸。一個分布式的檢測算法常常不可防止地導致一個元組集的傳輸M。然而，多數情況下，網絡傳輸最小化的條件下不一致性檢測那么是重要的。研究中，稱一個CFD 可以在網絡傳輸M后進展本地檢測，當Vio， D=i1，nVio， D'i。同時稱整個CFDs集可以在網絡傳輸M后進展本地檢測，當CFDs中每一個均能在網絡傳輸M后本地檢測。最小化網絡傳輸條件下的CFD不一致性檢測問題就是給定一個CFDs集和一個程度分布式部署的數據集D作為輸入，尋找一個網絡傳輸M使得：1可以在M后本地檢測；2|M|的取值最小。直觀地，研究的目的便是檢測D上關于的違規元組集，并且網絡傳輸還要是最小。2.2最

11、小化響應時間研究中，使用一個簡單的代價模型來估測響應時間，包含網絡傳輸時間和各個站點獨立檢測CFD違規的時間?？紤]一個CFDs集合，一個程度劃分的數據實例D =D1，Dn，以及一個網絡傳輸集M使得M完成后可以被本地檢測。我們用costD， ，M表示估計的響應時間如下：1其中，ct表示網絡傳輸率，p表示數據包的大小，D'i= DiMi，checkD'i，那么表示通過調用對集中式數據的檢測算法來檢測D'i中違犯的元組的時間開銷。直觀地，costD， ， M由兩個因素決定：1由每個站點向其他站點的最大網絡傳輸時間；2每個站點各自最大本地檢測不一致性時間。易知每個站點并行地向其

12、他站點發送數據，且在承受了其他站點發送的數據后，每個站點并行進展本地檢測。最小化響應時間條件下的CFD不一致性檢測問題便是對于給定的CFDs集和程度劃分的數據集D作為輸入，尋找一個網絡傳輸集M使得：1所有的站點在網絡傳輸M后可以對進展本地檢測；2costD， ， M是最小的。2.3分布式檢測算法對于垂直劃分的數據，不一致性檢測往往很復雜甚至是NP難問題。而且，即便在更為簡單的程度劃分的數據下，完成單個CFD的不一致性檢測也是很復雜的，因此本文僅討論程度分布部署在不同站點的數據下如何有效地檢測單個CFD的違例。程度分布的數據下，對于單個CFD有集中式的檢測算法和并行的檢測算法。這兩類算法均對各個

13、分布式站點的本地數據進展統計，而后基于這些統計數據按照最小化網路傳輸或者最小化響應時間的原那么，選定相應的協調站點將需要檢測的數據傳輸到協調站點進展本地檢測。而對于一個CFDs集，通常使用流水處理每一個CFD的方法來完成檢測。2.3.1 集中式檢測算法CTRDETECT集中式檢測算法的思想是：首先為待檢測的CFD ：XY， Tp尋找一個站點Sj作為協調站點；然后，所有非協調站點中所有與待檢測相關的元組都將傳送給協調站點Sj；最后，由協調站Sj在本地完成的檢測任務。算法可以描繪如表1所示。表1 算法CTRDETECTTab.1 Algorithm CTRDETECT輸入：一個CFD：XY， Tp

14、以及一個程度劃分的數據實例D =D1，Dn。輸出：Vio， D/*在每個站點Sj上并行地執行如下操作*/1 統計本地數據，求LHSi，令lstati = |LHSi|。2 將lstati值傳給其他站點。3 選擇擁有最大lstati值的站點作為協調站點，假設為Sj。4 任何SiSj，發送Mj，i = LHSi到協調站點Sj，等待Sj的檢測結果；對于協調站點Sj，令Mj=i1，nMj，i，那么D'j=LHSiMj，對D'j進展本地檢測，將檢測結果Vio， D'i發送給其他站點。5 返回檢測結果Vio， D該算法的關鍵就是協調站點如何選擇，該站點的選擇根據應該滿足最優化的兩個

15、條件之一，即網路傳輸最小或者響應時間最小。對此，研究定義LHSi來描繪第i個站點上滿足CFD中某個或某些模型元組的左部取值的元組構成的集合，也就是說LHSi=tSi|tpTptXtpX，如此將可選擇|LHSi|最大的站點作為協調站點，并且使得網絡傳輸最小。顯而易見，對于集中式檢測來說，網絡傳輸最小也就是響應時間最小。 2.3.2 并行式檢測算法PATDETECT先考慮最小化網絡傳輸的情況，網絡傳輸最小的并行式檢測算法PATDETECTS可以描繪那么如表2所示。表2 算法PATDETECTSTab.2Algorithm PATDETECTS輸出： Vio， D/*在每個站點Si上并行地執行如下操

16、作*/1 計算i：DiTp；for eachl1，kdoHli=tDi|i t=l ；lstati，l=|Hli |；將Hli的值傳送給其他站點；3 for eachl1，kdo /*選擇協調站點*/選擇lstati，l值最大的站點作為l的協調站點；將Hli發送給協調站點；4 本地檢測Viol， i1，nHli；/*并行地在協調站點上對tlp本地檢測*/5 合并檢測結果：Vio， D=j1，kVioj， i1，nHji6 返回檢測結果Vio， D2其中本地檢測的時間開銷為checkDjMj，=| DjMj|log|DjMj|。選擇協調站點時，采用貪心算法來進展決策。令l-1表示排序后的Tp中前

17、l-1個元組模型的協調站點決策，而結合第l個元組模型tlp，對于l的決策，即需考慮在l-1的根底上選擇ltlp，且使總的響應時間增量為最少。算法PATDETECTRT的描繪和PATDETECTS相似，只是在選擇協調站點時改換成貪心算法即可。3實驗3.1 實驗環境3.2 實驗數據用于測試的實驗數據來自TPC-H生成的1G數據，使用表lineitem作為測試用的數據集，其中總共包含600多萬條記錄。實驗時，將這六百多萬條元組均分成60份，每份包含約10萬條記錄，各個分布式站點穿插導入這些數據作為本地數據片段。3.3 分布式站點對算法的影響 研究分別在2、4、6、8和10個節點上測試了CTRDETE

18、CT算法和PATDETECT算法，各自比較了多條CFD在響應時間和網絡傳輸上的變化趨勢。從圖1中可以看出，隨著分布式站點數的增加，PATDETECTS的網絡傳輸會增加。這是因為隨著站點的增多，每個站點上分布的元組少了。類似地，作為協調站點上的待測元組也少了，而總待測元組是不變的，所以相應的網絡傳輸應該更多。與其相應地，CTRDETECT與PATDETECTRT也有相似的實驗結果。從圖2可看出，隨著分布式站點的增多，PATDETECTS的響應時間隨之減少。這是因為站點增多后，各個模型元組并發檢測的協調站點更趨發散地分布于各個分布式站點中，每個站點上執行并發檢測的流程少了，網絡傳輸和本地檢測都會更

19、快。同理，CTRDETECT與PATDETECTRT也有相似實驗結果。3.4 數據集對算法的影響研究在10個節點上，分別對不同大小的數據集進展了10條CFD的檢測實驗。鑒于集中式檢測算法的效率過低，將僅是針對PATDETECTS和PATDETECTRT兩個算法進展實驗，由結果來分析網絡傳輸和響應時間的變化趨勢。限于篇幅，只給出了PATDETECTRT的實驗結果，PATDETECTS結果與之類似。從圖3看出，在并行式檢測算法中，隨著數據集總大小的增加，完成檢測的網絡傳輸開銷也在增長，并且是呈現近乎線性的增長。這是因為待檢測數據往往是隨著數據集的增大而線性遞增的，為此網絡傳輸開銷也必然呈線性增長。

20、圖3 PATDETECTRT的網絡傳輸 圖4 PATDETECTRT的響應時間Fig.3PATDETECTRTdata shipment Fig.4PATDETECTRTresponse time從圖4中可以看出，隨著數據集增大，響應時間開銷在增加，這是顯而易見的，但是這一趨勢不像網絡傳輸那樣表現為線性增長規律，因為與數據集增大呈線性增長的是待檢測數據的規模，也就是本地檢測時間的規模，而這個本地檢測的時間那么由于算法的并行性，各個站點存在差異，使其不一定會呈現線性增長。另外，待檢測數據的網絡傳輸開銷也存在不確定性，因為可能會出現網絡阻塞和端口占用阻塞等復雜情況。4完畢語本文闡述了分布式數據的不一致性檢測問題，并對分布式的檢測算法進展了實現，同時設計了假設干組相關的實驗對檢測算法展開了較為全面的分析，最后進展了優化嘗試，且通過實驗對優化效果施行了相應評估。通過實驗結果可以看出，CTRDETECT算法和PATDETECT算法均能很好地解決分布式數據的不一致性檢測問題。并且隨著分布式站點的增多，分布式檢測算法的