分布式数据库中基于局部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.