分布式数据不一致性检测的实现与优化

王海洁　黄沈滨　朱振华

摘 要：数据的不一致性检测是数据清洗中一个重要的主题。传统集中式数据的不一致性检测问题可以使用基于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.