基于函数依赖与条件约束的数据修复方法-金澈清.pdf

《基于函数依赖与条件约束的数据修复方法-金澈清.pdf》由会员分享，可在线阅读，更多相关《基于函数依赖与条件约束的数据修复方法-金澈清.pdf（14页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、软件学报1SSN 10009825CODEN RUXUEWJournal ofSoftware，2016，27(7)：1671-1684doi：1013328jcnkijos005037中国科学院软件研究所版权所有基于函数依赖与条件约束的数据修复方法金澈清，刘辉平，周傲英木(华东师范大学计算机科学与软件工程学院数据科学与工程研究院，上海200062)通信作者：刘辉平，Email：hpliuStu，ecnuedu cnE-mail：jOSiscasaccahttp：wwwjos org cnTel：+861062562563摘要： 随着经济与信息技术的发展，在许多应用中均产生大量数据然而，受硬件

2、设备、人工操作、多源数据集成等诸多因素的影响，在这些应用之中往往存在较为严重的数据质量问题，特别是不一致性问题，从而无法有效管理数据，因此，首要的任务就是开发新型数据清洗技术来提升数据质量，以支持后续的数据管理与分析现有工作主要研究基于函数依赖的数据修复技术，即以函数依赖来描述数据一致性约束，通过变更数据库中部分元组的属性值(而非增加删除元组)来使得整个数据库遵循函数依赖集合从一致性约束描述的角度来看，函数依赖并非是唯一的表达方式，还存在其他表达方式，例如硬约束、数量约束、等值约束、非等值约束等然而，随着一致性约束种类的增加其处理难度也远比仅有函数依赖的场景要困难考虑以函数依赖与其他一致性约来

3、共同表述数据库的一致性约束，并在此基础上设计数据修复算法，从而提升数据质量实验结果表明，所提方法的执行效率较高关键词： 数据质量：数据修复；函数依赖；条件约束；等价类中图法分类号：TP311中文引用格式：金澈清，刘辉平，厨傲英基于函数依赖与条件约束的数据修复方法软件学报，2016，27(7)：167t一1684htrp：wwwjosorgc“100098255037htm英文引用格式：Jin CQ，Liu HP，Zhou AYFunctional dependency and conditional constraint based data repairRuan Jian XueBaoJou

4、rnal ofSoftware，2016，27(7)：16711684(in Chinese)http：wwwjosorgon100098255037htmFunctional Dependency and Conditional Constraint Based Data RepairJIN Che-Qing，LIU HuiPing，ZHOU AoYing(Institute for Data Science and Engineering，School of Computer Science and Software Engineering，East China Normal Univer

5、sityShanghai 200062，China)Abstract： Along with the development of economy and information technology，a large amount of data are produced in manyapplicationsHowever，due tO the influence of some factors，such as hardware equipments，manual operations，and multisogrce dataintegration，serious data quality

6、issues sunch as data inconsistency arise，which makes it more challenging to manage data effectivelyHence，it is crucial to develop new data cleaning technology to improve data quality to beaer support data management and analysisExisting work in this area mainly focuses on the situation where functio

7、nal dependencies are used to describe data inconsistencyOncesome violations are detected，some tuples must be changed to suit for the functional dependency set via update(instead of insert or delete)Besides functional dependency，there also exist other lypes of constraints，such as the hard constraint，

8、quantity constraint，equivalentconstraint，and nonequivalent constraint However，it becomes more difficult when more inconsistent conditions are involved This paperaddresses the general scenario where functional dependencies and other constraints CO-exist Corresponding data repair algorithm isdesigned

9、to improve the data quality effectivelyExperimental results show that the proposed method performs effectively and efficiently基金项目：国家重点基础研究发展计划(973)(2012CB316203)；国家自然科学基金(61370101，U1501252，61532021)，上海市教委科研创新重点项目(14ZZ045)Foundation item：National Basic Research Program ofChina(973)(2012CB316203)；Nat

10、ional Natural Science Foundation ofChina(6137010l，u1501252，6153202I)；Innovation Program ofShanghai Municipal Education Commission(14ZZ045)收稿时间：201510-09；修改时间：20160112；采用时问：20160222；jOS在线出版时间：2016-0322CNKI网络优先出版：2016-03-22 l 3：23：32，http：www cnkinetkcmsdetail11 2560 TP 20160322 1323 006html万方数据1672 J

11、ournal of Software软件学报V0127，No7，July 20 1 6Key words：data quality；data repair；functional dependency；conditional constraint；equivalence class信息技术极大地推动了国民经济与社会的发展随着数据采集技术的不断进步以及新型应用的不断涌现，待管理数据的规模也飞速增长能否高效地管理、分析数据业已成为衡量一个国家综合国力的重要指标2010年底，美国总统科技顾问委员会(PCAST)提出一份报告，建议“由于数据规模呈指数增长，各联邦机构都需要制定应对大数据的策略”【l J2

12、008年9月和2011年2月，自然和科学分别登载专刊，阐述大数据管理的迫切性和重要性，并展望发展前景【2，3 J学界惯以“3V”来描述大数据的特征，即：量大(volume)、多样(variety)、实时(velocity)数据由多源产生，数据形态可以不同，数据总量庞大以海洋监控应用为例，需要在不同地点布置传感器节点(工业机器人)来采集数据，并最终进行综合分析然而，“量大”并不意味着“质高”；从某种意义上讲，量大往往意味着出现质量问题的几率增加了41因为数据可以从多个来源生成，数据之间往往具有关联性在局部看来是高质量的数据放到全局视角来看，就会出现新的问题据报道，大型机构所产生的数据中60都是冗

13、余的【5】此外，RFID技术现已广泛应用到物流等多个行业之中，而RFID数据的准确度仅达到6070【6 J国外权威机构统计表明，除非经过非常精心的设计与对待，企业里面的数据错误率会在15之间7】质量低下的信息会带来严重的社会问题例如，医生基于低质量的医疗信息无法准确、迅速地为病人就诊，甚至可能引发医疗纠纷因此，定义数据集合的质量高低并且在知悉数据质量不高时能够执行操作来提升数据集合的质量，就显得非常重要函数依赖能够表达一个关系中两组属性(集合)之间的映射关系，已经被广泛应用于数据库规范化设计当中，它也是一种重要的描述数据一致性的手段令尺表示一个关系4和B分别是尺上的两个属性集合，且4一B表示一

14、个函数依赖，则对于任意两个只中的元组，当其在属性集合4上的值相等时，则在属性B上也会相等事实上，可以在一个关系R上定义一个函数依赖集合，包含多个函数依赖如果对于关系尺来说，该集合中的所有函数依赖都能够被满足，则认定该关系的数据质量达到要求；反之，则认为存在数据质量问题，需要进一步提升典型的数据修复策略可以分为两类一类是直接删除不符合要求的记录，使得剩余记录能够符合所有给定的函数依赖由于删除记录时剩余数据集合中存在的错误不会增加，因此总可以不断迭代执行以完成数据修复，即：首先找到违背函数依赖约束的元组集合，然后随机删除一条元组，再检测剩余数据集合这种方法尽管简单，但却会丢失很多信息例如，一条包含

15、数十个属性的元组，可能仅仅由于某一个属性值不符合规范而被整体删除，一些有益信息就丢失了另一种方式是并不增DHi删除任何记录，而是仅仅修改某些字段，使得整个集合能够符合预设的一致性要求这种方式能够最大限度地保留数据集合的原始信息，也是目前的研究重点但是，后一种处理方式做起来并不容易，因为修改某条元组的属性值，有可能又与现有的其他元组之间产生新的不一致性所以，增加了技术难度例1：图1的上部表格是一个包含4条学生记录的小型关系实例在该实例上共有3个函数依赖，例如：邮编一城市，省份然而，这个实例中存在数据不一致性现象例如，f1和f2的邮编相同，根据该条函数依赖关系，则这两个元组的城市和省份也应该相同但

16、在本实例中却并不相同因此，可以修改t：中的相关字段，使之与t。相同如左下方的修复策略1所示。尽管函数依赖非常重要也非常有效，但是仍然存在一些无法由函数依赖表达的重要约束条件，包括硬约束、与数量相关的约束、等值约束、非等值约束等硬约束硬性指定某一个单元格的值，例如“学号为001的同学来自杭州”数量约束此类型中最为典型的约束就是唯一性约束即某个属性或者属性值中的信息都是唯一的除此之外，也可以包括大于1的约束条件，例如：这个学校中的杭州人不超过2人等值约束说明特定条件之下的属性值是相等的例如，“李四和王五是一个城市的”非等值约束除了相等之外的二元操作，包括大于、小于等这些不等于条件下属性值一定不相等

17、例如：“这个学校有两个张三，但是邮编不同”万方数据金澈清等：基于函数依赖与条件约束的数据修复方法 1673可以将这些函数依赖之外的约束条件存放于外部知识库在数据修复过程中，不仅要使得这些修复符合预先设定的函数依赖集合，也必须满足在外部知识库之中的约束条件学号“002”和“004”的同学的城市相同这个学校的杭州人不超过2人修复策略2姓名张三李四张三王五城市 省份浙江浙江浙江浙江邮编杭州温州杭州温州Fig1 An example of data repair图1数据修复样例例2：图1所示的修复策略1能够满足所有函数依赖，但却不能满足外部约束条件该约束表明，杭州的学生不超过2人，但是修复策略1中却出

18、现了3个杭州因此，修复策略1违背了外部约束条件可以修改t2中的字段，从而既满足函数依赖集合，又满足外部知识库中的约束。参见修复策略2然而，针对兼具函数依赖集合与外部知识库的关系数据库的数据修复工作并不容易当前的研究工作主要集中于如何利用函数依赖进行修复这些工作研究各种各样的优化目标，分析其复杂度，并且设计相应的算法8-12】也有学者研究修复的多样性问题，提出了一种返回七种修复方案的方法，且修复方案之间的差异性比较大，从而使得整体修复方案具有多样性，有利于项目实施者进行挑选13,141仅有少数工作考虑到了除函数依赖之外的其他一致性约束条件，例如，文献【8】考虑了一种特殊的包含关系IND，指明某个

19、关系中某一个属性的所有值均需在另外一个关系的某个属性值空间之中，类似于关系数据库中的外键关系；文献12】考虑到了硬约束，即某些单元格的值是强制设定的然而，在这些工作中所考虑的一致性约束条件仍然比较有局限性，无法简单扩展以解决其他一致性约束条件在本文中，我们研究一种数据质量提升方法，既能够应对函数依赖，也能够应对包括硬约束、数量约束、等值约束和非等值约束等多种一致性约束条件本文的主要贡献如下首先，鉴于传统的基于函数依赖集合的数据修复方案在数据一致性表达上具有局限性，因而需要引入新的约束条件，丰富其表达能力，并在此基础上研究数据修复问题其次，本文提出了一种新颖的数据修复算法，该算法采用增量式的修复

20、策略，在初始化阶段首先产生部分正确的单元格，在后续过程中再不断地修复其他单元格最后，我们在模拟数据集合上进行了验证，实验结果表明，本文所提算法具有较好的可行性以及较佳的执行效率本文第1节回顾相关工作第2节正式定义问题第3节给出解决方案第4节通过实验进行验证最后在第5节总结全文1相关工作近年来，数据质量问题得到了广泛的关注李建中等人意识到劣质数据随着大数据的爆炸性增长而来，认为数据可用性是大数据的一个重要方面，需要从战略高度进行思考1 51当待处理的数据质量被检测出来存在较大问题时，必须及时进行修复数据的修复主要针对实体同一性和一致性问题而来所谓的实体同一性错误是指在数据库中存在多条描述同一实体

21、的记录，但是不同记录所记载的信息存在冲突，可以采取数据融合技术进行修复z6,171一致性错误是指数据库违背了预先定义好的一组规则本文主要针对数据的一致性错误一般来说，数”H如如弛强塑耋啷似一“如b“万方数据1674 Journal of Software软件学报V0127，No7，July 2016据一致性的自动修复工作可以分为基于统计学的方法和基于语义规则的方法基于统计学的修复方法充分考虑了概率分布等因素，并以此作为依据进行修复文献18】提出了一种基于概率的数据一致性错误修复方法该方法首先假定存在一个满足一致性约束的合理修复的空间，然后依据合理修复的概率分布进行抽样，最后会用抽取出来的合理修

22、复完成数据的修复文献6，19，20分别以RFID和传感器网络为背景，针对利用统计学定义的数据一致性错误，提出了修复数据一致性错误的方法基于语义规则的方法得到了更多的研究文献【8，9的目标是通过最少的更新操作来修复数据质量，其优化目标就是基数最小策略文献8分析了计算复杂度，提出了一种贪心算法进行处理文献9则设计了一种近似最优的策略来解决这个问题此外，另有一组学者则尝试利用集合最小化策略来进行修复1 0，11文献12提出了基数集合最小化策略，平衡了基数最小化策略的“最少修改”和集合最小化策略的“必要修改”两点同时，文献121中还研究了硬约束，即部分单元格的值是预先设定好的情况文献21也研究了基于函

23、数依赖的一致性修复问题文献22研究针对数据和约束修复的统一模型，不仅考虑在修复过程中最小化数据库更新，也考虑约束条件随时问演化的情况这些约束条件也是由函数依赖所决定的文献13同时考虑了修复的多样性问题，针对一个低质数据库实例，力图返回多个修复，而且这些修复之间具有较大的差异性文献14】则尝试在分布式数据库上对数据进行修复从以上分析可以看出，基于语义规则的方法得到了更为广泛的研究在这些工作中，绝大多数均将函数依赖作为一致性约束的唯一方式仅有文献8，12考虑到了其他依赖关系，即包含关系和硬约束关系但是硬约束关系相对来说比较简单，无法表达更为复杂的语意；包含关系主要适用于多表场景因此，由于约束条件和

24、优化目标不一致，文献8，12】的方法很难直接应用到本文的工作中鉴于此，本文扩充了其他的约束语义，并基于此进行修复2模型与定义21函数依赖令尺表示一个关系，它包含m个属性；dttrs(R)=，爿，)表示R上的属性集合，Dom)表示一个给定属性4的域令j表示关系犬的一个实例，包含若干元组，各元组均属于域Dom口l xxDom。)令Dotal(A)表示属性A的空间，它包括所有出现在实例I中的爿属性值假设，中的每个元组均有一个标识符，即使元组的其他属性都发生变更，该标识符也不会改变令TIDs表示在实例，中的所有元组的标识符的集合令f彳】表示元组t的一个单元，其中4Attrs(R)，fTIDs(1)每一

25、个单元f口】由元组r以及属性A所确定在尺上定义一个函数依赖集合，包含多个函数依赖对于两个属性集合x和E它们均属于dttrs(R)基于实例j的一个函数依赖xy被表示为f丝xy换言之，对于实例，中的任意两个元组t1和f2，如果tl【硼=龟冈成立，则fly=f2明必然成立令廉示基于关系R的函数依赖集合我们假设腥正则最小化的【221每个函数依赖均可以被描述为如下的形式：x彳，其中,XcAttrs(R)，且AeAttrs(R)22外部知识库函数依赖集合是一种描述数据质量的重要方式，但却无法描述所有情况，因此还需要以其他方式进行描述，包括硬约束、数量约束、等值约束、非等值约束等定义1(硬约束，hard c

26、onstraint，HC岱，v)给定一个单元格集合s中各单元格的值必须为v例如，“学号为001的同学的城市是杭州”可以表示为HC(t“城市，杭州)定义2(数量约束，quantity constraint，QC(S，l，力)给定一个单元格集合5，约定在这些单元格的值被设置为v的数量的上限r例如，“这个学校的杭州人不超过2人”可以表示为QC(城市，杭州，2)其中，城市表示数据库实例，的城市属性的所有单元格定义3(等值约束，equality constraint，Ec(s)给定一个单元格集合S，约定在这些单元格中值相等万方数据金澈清等：基于函数依赖与条件约束的数据修复方法 1675参数s是一个固定的

27、集合。例如，“学号是00t和002的同学的城市相同”可以表示为：EC(托城市，龟城市】)在这里，集合“城市，r2城市】)包含两个指定位置的单元格定义4(非等值约束，11011一equality constraint，NC(S)给定一个单元格集合S约定在这些单元格中值均不相等与等值约束类似，单元格集合S也是固定的集合，例如，“学号是001和002的同学的邮编不同”可以表示为NC(tl1自g编】，t2由g编】)定义5(干净数据库，clean database)给定一个数据库，如果该数据库中的所有单元格既满足所有的函数依赖也满足所有的条件约束，则该数据库是干净的例如，图1中的修复策略2生成的数据库是

28、一个干净的数据库23数据库修复给定一个函数依赖集合卵外部约束集合Q如果数据库实例，违背了肿的任意一个函数依赖或者力中的任意一个约束条件，则称，相对于(五g不一致一般来说，针对一个不一致实例J的修复会产生另外一个同时满足卿力的实例，如前所述，本文中所研究的修复是指对于数据集合的修改，而非添加或者删除数据令，)表示在修复，中值发生变更的所有单元格的集合事实上，针对一个给定的数据库实例的修复策略往往并非唯一，而是多元化的目前，典型的修复目标有3种：集合最小化修复(setminimal repair)、基数最小化修复(cardinalityminimal repair)和基数集合最小化修复(cardi

29、nalitysetminimal repair)定义6(集合最小化修复)10，11一个针对数据库实例，的修复，是集合最小化的，当且仅当不存在一个修复，7，使得A(L1”)cA(,7)，并且对于任一单元格CA(1，)，7(o可7(o此外，基数最小化修复返回一个修复，它是针对原始数据库实例，的最小修复，换言之，不存在另外一个修复，7，使得l(L，)llA(If)1基数集合最小化修复则返回一个修复，当且仅当不存在任一修复，使得，)c，)本文研究集合最小化修复3解决方案本节详细介绍数据修复方案我们首先介绍算法的总体框架，然后依次介绍这个框架中的各个重要函数，最后分析算法的性能31算法框架本节介绍算法的

30、框架“等价类(equivalence class)”是由文献8】所提出的一个关键概念，在后续多个文献中延续使用所谓的等价类是指，在关系数据库实例中位于同一列的若干单元格所构成的集合，且这些单元格中的值相同此外，在函数依赖集合的作用下，这些等价类还可以进行合并图2给出了一个等价类例子图2(a)是原始的数据库实例，它有3个属性0，曰，C)，包含3条元组它有两条函数依赖彳一C，曰一C)检查各列数据，可以将整个数据库实例划分为如下6个等价类，如图2(b)中各粗体矩形框所示在每个等价类中的值均相等通过检验各条函数依赖，可以发现等价类3，3和5必须合并成3，3，5，如图2(c)所示鉴于这个新等价类中的数值

31、并不完全相同，可以认定本数据库实例中存在数据质量问题一 曰 C1 4 31 2 36 2 5万方数据1676 Journal of Software软件学报V0127，No7，July 2016本文不仅研究函数依赖，还研究其他外部约束问题因此，传统的方法无法胜任我们提出了一种新的处理算法，其框架如算法1所示给定待修复的数据库实例L函数依赖集合三以及外部知识库Q首先调用Initialize(X,g函数根据函数依赖和外部知识库中的硬约束、等值约束以及非等值约束对干净数据库实例C和等价类集合E进行初始化，即将满足这些约束的单元格先放入c使其不可变，则最后c必然满足硬约束、等值约束和非等值约束(第1行

32、)然后对于待修复数据库实例，中的每一个单元格c，将其依次加入C，并对该单元格c增量构建等价类形成新的等价类集合为了保证修复的多元性，可随机选取，中的单元格(第2行第5行)当，中所有单元格都被插入到C后，C必然满足硬约束、等值约束、非等值约束、数量约束以及函数依赖最后对于C中的变量值，我们对其进行确定使得C是干净的(第6行)可以看出，该算法的特点是在初始化之后的过程中，迭代随机访问各个单元格，但在检测到数据不一致现象时，只会修改该单元格的值，而不去变动原有的存放在C中的单元格的值一旦单元格存在于C中，且其是干净的，则最后这些单元格必然也是干净的算法1算法总体框架Framework输入：数据库实例

33、，函数依赖集合三外部知识库Q输出：干净的数据库实例C1 (C，E),-Initialize五囝； 初始化阶段，生成单元格集合C和等价类集合E，参见第32节2 for each单元格c一C doc可以在C中随机选取3 E。-IncreBuildEquivRel(E，三C，c)；增量式构建新的等价类集合E，参见第33节4 CCufC)；将c插入到单元格集合C中5 endfor6 VarRepair(63； 变量值修复，参见第34节7 return C32初始化阶段算法1的第1个步骤就是基于数据库实例1、函数依赖集合骄口外部知识库Q进行初始化，生成初始实例，和等价类集合E考虑到外部知识库中存在多种约

34、束类型，在本阶段主要处理硬约束(Hc)、等值约束(EC)、非等值约束(NC)和函数依赖(FD)具体处理如下：硬约束HC硬约束限定给定单元格的值如果这个单元格恰巧从属于某一个等价类的话，则需要检查这个等价类中的其他单元格，若值不等于硬约束所给定的值，则需要进行修复等值约束EC对于等值约束而言，给定的若干个单元格的值必须相等因此，需要将这些单元格划分到一个等价类中去非等值约束NC对于非等值约束来说，给定单元格集合中任意两个单元格的值均不相等因此，可以将每个单元格分别设定一个等价类如果存在值相等的单元格，先将其值均设为变量函数依赖FD函数依赖描述属性集合之间的依存关系在初始化阶段，查验预设的函数依赖

35、集合有助于合并等价类具体步骤如算法2所示首先，生成一个空的等价类集合E(第1行)对于舯的每一个硬约束，将其单元格放入同一个等价类中并设置相应的值，然后加入到E中(第2行第6行)对于力中的每一个等值约束，将该约束中的所有单元格划分到同一个等价类中，保证其值相等(第7行第10行)对于口中的每个非等值约束，将该约束中的每个单元格都当作独立的等价类，并将值相等的单元格的值设为变量(第ll行第15行)对于肿的每条函数依赖F：B一爿，考察每对元组(f，t)，判断是否有必要合并等价类检查的规则就是判断检查f别和，陋是否相等，如果相等，则有必要合并f口】和f7叫】所对应的等价类在这个过程中，可能会遇到各个参与

36、的等价类值不相等的情况，则需要在不违背硬约束的前提下进行修改如果无法设置合适的值，则说明约束条件和函数依赖相矛盾，该数据库实例不可修复(第16行第19行)之后，生成单元格集合C，并最终返回c和等价类集合E(第20行第21行1万方数据金澈清等：基于函数依赖与条件约束的数据修复方法 1677算法2初始化阶段Initialize输入：数据库实例上函数依赖集合二外部知识库Q输出：单元格集合c，等价类集合E1 E一：2 for each硬约束HC(S，v)eO do处理硬约束HC3 将S中所有单元格的值设置为v；4 创建一个包含该s中所有单元格的等价类P；5 EEufel；将P插入到E中去6 end f

37、or7 for each等值约束Ec(s)刃do处理等值约束EC8 创建一个包含该等值约束覆盖的所有单元格的等价类P；9 EEufe；将e插入到E中去10 endfoo11 for each非等值约束NC(S)力do处理非等值约束NC12。 针对该非等值约束所覆盖的各个单元格均创建独立的等价类，标记为e1，e2，；13 将值相等的单元格的值设为变量；14 EEwel，P2，；将新创建的等价类添加到E中去15 end fo16 for each函数依赖F三F：B一彳do处理函数依赖集合，尝试合并等价类17 对于辱中所涉及的任意元组对(f，)，如果f【别和r陋】属于同一等价类但fM】和M】属于不同

38、的等价类，则合并E中包含tA和f口的等价类；18 如果在等价类合并过程中，各参与方的值不相同，则可以在不违背硬约束的前提下进行修改；19 endfor20 CE中所有等价类所包含的所有单元格；21 return(C，E)；33等价类增量构建初始化阶段仅处理、修复数据库实例1中的部分单元格，仍然需要进一步操作来修复其余的单元格在本文所提出的总体框架中，需要迭代式地处理剩余单元格，直到所有单元格均被访问完毕在这个过程中，增量式地构建等价类集合就是一个关键性操作，其目的在于高效地生成基于Cwc)的等价类集合，其中C是原始的单元格集合，c是即将加入的单元格在这个函数中，比较重要的一个步骤是测试数量约束

39、QC如果新单元格c加入到已有的等价类之中，会导致违背某一条数量约束QC时，则需要将该单元格单独设置为一个等价类，且其值为变量算法3描述了具体步骤首先，如果在检验等价类集合E7(即输入等价类集合D之后发现存在等价类P，这个等价类的值与单元格c中的值恰巧相等且c与e处于同一属性，则需要将c与e进行合并而这个合并操作又可能会引发后续的等价类合并操作因此，需要再次检查函数依赖集合进行判断鉴于潜在的等价类合并操作都是由于新加入的单元格所导致的，因此仅需要检测与这个插入元组所在的等价类相违背的等价类并将其合并直到F中所有等价类都满足函数依赖更新操作与算法2中的第16行类似(第2行一一第5行)执行上述操作可

40、能导致违反某一个现存的数量约束Qc，此时，则需要将单元格c单独作为一个等价类，将其值设置为变量，再加入到输入等价类E之中(第6行第7行)此外，合并之后的等价类可能不干净，即其中的单元格的值不相等，则说明新插入的单元格C不满足条件此时，如果C属于之前的等价类集合E中的一个等价类中且该等价类不是一个独立等价类，则将C变为该等价类的值；否则为c创建一个独立等价类并加入到E中最后将E赋值给F(第8行第12行)如果这个单元格C不能够与任何等价类进行合并，则无需进一步检查函数依赖集合，同样为C创建一个万方数据1678 Journal of Software软件学报V0127，No7，July 2016独立

41、等价类并加入到E且赋值给F最后算法返回E(第13行第15行)算法3增量构建等价类集合IncreBuildEquivRel输入：单元格集合C，等价类集合E，函数依赖集合五单元格c；输出：新的等价类集合F1 E一E：2 if(3e，PE，C与P中的值相等且属于同一属性)then3 8一Puc：将c加入到e中4 令，代表e所涉及的元组集合；5 基于7依次检查肿所有函数依赖，合并F中相关的等价类；6 if(3e，gF，且e违背了某个数量约束Qc)then7 创建一个仅包含C的等价类P 7，且将其值设置为变量；FEwe)；8 else if(3e，PE7，且e不干净)then9 if(3e，eaE，ce

42、，且e不是单独的独立等价类)then10 将C的值变为e中的值：11 else创建一个仅包含c的等价类P，且将其值设置为变量；FEwe；12 end if13 else14 创建一个仅包含C的等价类et；E 7一Eue；15 end if16 return E34变量值修复最后，我们确定单元格集合C中的变量如果可以将该变量变回原值而又满足约束条件和函数依赖，则将其变为原值；否则将变量变成满足条件的值(第1行第6行)这里，我们采用两种策略第一，遍历该单元格所属属性中己出现的所有值，直到找到一个满足条件的值为止第二，直接随机选取一个在其属性中未出现的值，这种贪心方法由于肯定不会违反函数依赖和约束条

43、件，因此其效率明显很高图3展示了整个算法的运行过程假设外部知识库力中的硬约束为HC(t1)，2)；数量约束为QC(B，2，3)，即属性B中值为2的单元格最多为3个；等值约束为EC(t2阻，73口】)，EC(tlB，t2陋)；非等值约束为NC(t“曰，如旧)；函数依赖集合为A-B图3(b)是根据外部知识库中的条件约束生成的等价类集合；图3(c)在函数依赖的情况下合并等价类；图3(d)表示等价类赋值后单元格以及等价类的情况至此，数据初始化完成，其满足硬约束、等值约束和非等值约束图3(e)表示插入tl彳】后的状态，由于其没有违反函数依赖，所以值无需改变插入t4A：l时，由于其开始加入到1的等价类中，

44、然而此时不满足函数依赖，因为t4B=Var并不属于2的等价类这时需将t4A的值改为变量，如图3(f)所示接着插入t5口=1，其会加入到1的等价类中，此时t5旧会加入到2的等价类中这时2的值会有4个，违反了数量约束，因此需要将t5囡的值改为变量，如图3(g)所示最后插入t5曰】，不违反条件约束和函数依赖，因此不需要更改t5旧的值，此时产生了一个满足约束条件和函数依赖的修复算法4变量值修复VarRepair输入：单元格集合C；输出：无1 for each(变量v in a do2 if f将v变为原值不满足条件)then3 将v变为满足条件的值；4 end if万方数据金澈清等：基于函数依赖与条件

45、约束的数据修复方法5 endforEl：I(e)插入ti阻爿 口，I 2t2 1 1t3 1 砌r(b)使用HC，EC和NC爿 口tl 4 2，2 1 2t3 1 2“ 肠， 砌，15 1I一(D插入f。爿】，改为变量，厂一112LLt3 1 砌rf4 砌r，1(c)使用函数依赖A Bti 4 1t2 1 2t3 1 2“ 陷， 陆rf5 砌，(g)插入tsA，改为变量1679(d)等价类赋值彳 Btl 4 2t2 1 2t3 1 2t4 Var Vart5 砌r 0(h)插入f5剀Fig3 The progress of data repair图3数据修复过程定理1算法1生成的修复都是集合最

46、小化修复证明：令原始数据库为L修复后的数据库为，(厶，)表示，和，中不同值的单元格集合要证明，是集合最小化修复，即说HJqA(S，)中的单元格都不能变为原值而使，得到修复初始化阶段算法为了满足条件约束和函数依赖将必要的单元格划分为相同的或不同的等价类，然后修改同一个等价类中单元格的值使其相等显然，任何一个修改的值变为原值都会使条件约束或函数依赖无法满足，否则算法不会修改对于非等值约束EC中值相同的单元格，我们同时都把它们置为变量但当其中一个或多个变量的值确定后，最后一个变量的值可以变回原值为了处理这种情况，我们修复变量时，优先把变量变回原值综上，初始化后的单元格满足集合最小化修复下面考虑增量构

47、建等价类情况由于从，选取单元格到，中是随机的，不妨令CI,C2，c，为从，插入到，中的单元格的顺序我们通过归纳法证明，对于任意ci(1ij)，它要么是一个不变的单元格，要么是一个需要变化的单元格首先初始化过后，中单元格满足集合最小化修复，即此时，中的单元格要么是不变的单元格，要么是必要变化的单元格接着我们开始往，中插入单元格ci，若C满足条件，则不需要更改值；否则，Cf必定需要修改，我们用反证法来证明假设c。保持原值能使，保持干净，则算法1就不会修改c，因此导致矛盾所以增量构建等价类的过程同样保证满足集合最小化修复因此算法1生成的修复都是集合最小化修复 口35性能分析初始化：假设外部知识库中的单元格个数为P，函数依赖个数为七，则条件约束处理的复杂度为O(p)，函数依赖处理的复杂度为O(p七)，因此数据初始化的时间复杂度为O(p曲等价类构建：假设原始等价类集合中包含n个等价类由于需要遍历所有等价类来确定新单元格的所属等价类，所以其时间复杂度为0(玎)假设函数依赖个数为尼，则对