《基于可能世界模型的关系数据不一致性的修复-徐耀丽.pdf》由会员分享，可在线阅读，更多相关《基于可能世界模型的关系数据不一致性的修复-徐耀丽.pdf（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、软件学报ISSN 10009825，CODEN RUXUEWJournal ofSoftware，2016，27(7)：16851699doi：1013328jcnkijos005041中国科学院软件研究所版权所有基于可能世界模型的关系数据不一致性的修复徐耀丽，李战怀，陈群，钟评(西北工业大学计算机学院，陕西西安 710129)通讯作者：李战怀，E-mail：lizhhnwpuedu cnEmail：jOSiscasaccnhttp：llwwwjosorgcnTel：+861 062562563摘要： 针对关系数据的不一致性虽然已有各种修复方法被提出，但这些修复策略在构建最终修复方案的过程中只
2、分析函数依赖包含属性的信息(即，数据集的部分信息)，且偏向于修复代价最小的方案，而忽略了数据集的其他属性以及这些属性与函数依赖包含属性之间的相关性为此，提出一种基于可能世界模型的不一致性修复方法庀首先构造可能的修复方案，然后从修复代价和属性值相关性两个方面量化各个候选修复方案的可信性程度，并最后找出最优的修复方案实验结果验证了所提出的修复方法取得了比现有基于代价的修复方法更好的修复效果同时也分析了错误率和不同类型概率量化对所提出的修复方法的影响关键词： 不一致性；函数依赖；修复代价；可能世界；修复质量中图法分类号：TP311中文引用格式：徐耀丽，李战怀，陈群，钟评基于可能世界模型的关系数据不一
3、致性的修复软件学报，2016，27(7)：16851699hnp：wwwjosorgcrdl00098255041htm英文引用格式：Xu YL，Li ZH，Chen Q，Zhong PRepairing inconsistent relational data based on possible world modelRuanJian Xue BaoJournal ofSoftware，2016，27(7)：16851699(in Chinese)http：wwwjosorgcn1000-98255041htmRepairing Inconsistent Relational Data Ba
4、sed on Possible World ModelXU Yao-Li，LI ZhanHuai， CHEN Qun，ZHONG Ping(School ofComputer Science and Technology，Northwestern Polytechnical University，Xian 710129，China)Abstract： Various techniques have been proposed to repair inconsistent relational data that violate functional dependencies byoptimiz
5、ing the repair plan by the metric of repair costHowever,they may fall short in the circumstances where the erroneous data OCCURSin the left-hand side of a functional dependency or repair cost is not a reliable optimization indicator In this paper，a novel repairingapproach based on possible world mod
6、el is proposedIt first constructs candidate repair plans and then estimates their possible worldprobabilitiesThe possible world probabilities are measured by quantifying both repair cost and candidate value appropriateness withregard to other related attribute values presented in relational dataFina
7、lly,extensive experiments on synthetic datasets show that theproposed approach performs considerably better than the cost-based approach on repair qualityKey words：inconsistency；functional dependency；repair cost；possible world；repair quality随着信息技术的普及，各行各业逐渐建立起各自的信息化系统，并在实践中积累大量的业务数据互联网时代的到来，数据的种类和来源
8、呈多样化发展，更新周期大为缩短，数据量大幅度飙升如何有效而可靠地分析处理这些数据，为各行各业的经营决策服务，成为亟待解决的问题然而在收集这些数据的过程中，由于人为因素，基金项目：国家重点基础研究发展计划(973)(2012cB316203)；国家自然科学基金(61332006，61472321，61502390)；西北工业大学基础研究基金f3102014JSJ0013，3102014JSJ0005)Foundation item：National Basic Research Program ofChina(973)(201 2CB316203)；National Natural Scienc
9、e Foundation ofChina(61332006，6147232I，61502390)；Northwestern Polytechnical University Foundation for Fundamental Research(3102014JSJ0013，3102014JSJ0005)收稿时间：20151014；修改时间：2016-0112；采用时间：2016-0222；iOS在线出版时间：20160322CNKI网络优先出版：2016-0322 13：23：37，http：wwwcnkineVkcmsdetail1l 2560 TP 201603221323009html
10、万方数据1686 Journal of Software软件学报V0127，No7，July 20 1 6如拼写错误、录入格式不相同和数据更新不及时等原因，导致数据集存在数据缺失、不一致等数据质量问题这些问题的存在，使得数据的价值大打折扣，相关部门或企业在使用这些数据前需要花费大量的时间和人力审查并纠正存在的错误数据质量专家指出，4050的工程预算用于耗时费力地纠正错误数据数据的不一致性是指给定的数据集不满足预先给定的数据约束f如函数依赖、条件函数依赖等)不一致性修复是指通过某些数据操作，如插入、删除或更新，使得修复后的数据集满足给定的数据约束不一致性修复问题面临两大挑战：一是满足给定数据约束
11、的候选修复方案有很多池就是说，候选修复方案的数目随着数据集的增加呈爆炸式增长；二是数据约束数目的增多以及它们之间的相互制约关系增加了不一致性修复问题的难度，可能会导致同一条元组的属性在上一轮策略中得到修改，在下一轮又被改回这些挑战要求修复策略一定要高效且合理现有的数据修复方法2，3】采用最小代价原则，也就是修复后的数据集与修复前的数据集的修改代价最小的方案，但文献2】仅仅考虑出现在函数依赖的右边的属性然而现实场景中，错误的出现位置是随机的，可能是函数依赖左边的属性，也可能是右边的属性例如，函数依赖s：CK-NN由于数字之间的差别不大，相比用户所属国家(NN)，疲惫的录入人员更可能在输入用户编号
12、(CK)时因走神而录入错误虽然文献3提供含有变量的修改方案V-repair，可能将函数依赖左边的属性值替换为变量v，但该修复方案给数据集应用人员带来很大的不便，因为变量v的正确值是什么，还需要专家费神分析才能确定为了叙述上方便起见，ORDERKEY,0 ORDERSTATUS，R NAME，P MFGR，P BRAND，O SHIPPRIORlTY,CUSTKEY和N NAME属性名分别代表订单编号、订单状态、地区名、供应商名、供应商标、订单船舶优先权、用户编号和用户所属国家，依次简记为OR，OO，RN，PM，PB，OS，CK和NN另一方面，一个修复代价小的修复方案并不一定是一个修复质量高的修
13、复方案现有的修复策略仅仅考虑了数据集中与数据依赖相关的属性信息，并未考虑数据依赖以外的其他属性以及这些属性之间的相互关系例如，在修复如图1所示的数据依赖时，只关注与数据依赖相关的属性，也就是订单编号(0R)和订单状态(00)，而没有考虑数据依赖以外的属性，如地区名(RN)、供应商名(PM)署H供应商标(PB)等，以及这些属性与订单编号(ORl、订单状态(oo)的相关信息数据集中，元组属性列之间的相关性信息反映了数据的某些内在规律，使用机器学习方法可以抽取出这部分有用的信息，为修复方案的确定提供更坚实的推理支撑然而，目前的修复研究中没有涉及相关性信息本文的修复框架能够分析属性列之间的相关性并尝试
14、修复错误出现在数据依赖左边的场景，且修复后数据集不包含变量(I)数据集，；(II)函数依赖集仁饼：OR-OO五：PB-PM山：CK-NNFig1 Dataset and functional dependencies图1数据集和函数依赖集随着数据采集和处理技术在各行各业的广泛应用，数据的不确定性普遍存在针对这些应用场景，研究者提供了多种描述数据不确定性的数据模型，这些模型的核心思想是可能世界模型41可能世界模型能够有效地刻画数据集合的不确定性而概率数据库作为可能世界模型的表述方式，用概率值量化每个可能世界实例存在的可能性，是一种不确定性的数据库本文借助概率数据库表述可能世界的思想，把满足函数依
15、赖的某个候选修复方案视为一个可能世界实例，并用概率值量化该候选修复方案正确的可能性其中，概率值计算是综合分析属性万方数据徐耀丽等：基于可能世界模型的关系数据不一致性修复 1687列之间的相关性、修复代价而得到的，本文设计并实现基于可能世界模型的不致性修复算法，以解决给定函数依赖下关系数据的不一致性修复问题本文的主要贡献如下：f11 提出了一种基于可能世界模型的不一致性修复框架该框架综合分析数据集的有用信息，如相关信息、统计信息等等，并为候选修复方案的选择提供信息支撑；f21 设计并实现了一种融合了修复代价和基于相关性概率量化的关系数据不一致性修复算法该算法将候选修复方案类比为可能世界实例，将候
16、选修复方案正确的可能性量化为可能世界实例的概率，搜索概率值较高的可能世界实例作为修复方案该算法具有较好的修复效果；(31 在模拟数据集上进行大量实验，对本文提出的算法进行验证和分析本文第1节综述数据修复相关工作第2节介绍相关基础知识并定义不一致性修复问题第3节介绍基于可能世界的不一致修复框架，详细讲述如何构建候选属性记录，如何筛选候选属性值，如何量化候选属性值的概率(用于表示该属性值正确的可能程度)第4节设计启发式贪心算法，用于在满足给定数据依赖的可能世界实例集合中搜索概率值较高的作为修复方案，第5节验证算法的修复效果，并分析各个参数对算法的影响最后总结全文工作并对未来工作加以展望1相关工作在
17、信息化时代，数据成为企事业单位的重要资源之一数据修复问题作为数据质量问题的重要组成部分，一直被学术界广泛关注早期的数据修复系统或ETL商业工具包的主要目的是进行数据格式的转换pJ，或者标记差异61，或者由用户定制数据转换操作7这些修复方法并不能处理由函数依赖检测出的冲突情况早期的数据修复方面的研究51主要关注使用插入和删除操作，但这样可能使得修复后的数据库实例信息流失，特别地，对于重要的信息，这是无法容忍的大数据时代的到来，数据修复问题等数据质量问题重新得到了企事业单位和专家学者的广泛重视，并进行了广泛的研究，涌现出各式各样的修复算法和框架【l。湛-1这些修复算法的核心思想是：计算出一个数据集
18、JD，使得D满足函数依赖，并且从源数据集D转换成D的修改量最小若这个转换操作采用修改元组属性值的方式，那么检测是否存在这样一个修复后数据集D 7己被证明是NP难问题【21文献2】提出了一个以修改量最小为优化目标的启发式修复模型，该模型借助等价类技术将冲突的检测阶段和修复属性值的确定阶段在一定程度上解耦，这样，修复属性值的确定阶段便能汇集更多有效信息，使得修复属性值的确定是全局最优的文献3提出了一种近似最优修复算法，该算法利用超图可以产生一个与最优修复的差异在常数范围内的V-repair文献8针对概率数据库的不一致性问题，将概率数据库描述的可能世界划分成互不重叠的组，然后在每个组中使用文献2】的
19、启发式修复算法解决数据不一致性问题这些修复方法在代价最小的假设下能够得到较好的实验效果，但是代价最小并不一定就是最合理的，而且数据集的信息很多，不仅有构成函数依赖的那些属性，还有其他的属性而上述基于代价最小的修复框架和算法仅仅使用了函数依赖相关的属性列，其他属性列的信息被忽略若函数依赖包含的属性和函数依赖未包含的属性之间有一定的关系，深入分析这部分信息有助于改进修复方案部分文献19-11】将数据挖掘或机器学习的信息挖掘和学习技术引入数据修复领域文献9融合了置信传播和关系依赖网络的技术，提出了一个以数据库为中心的数据清洗框架，该框架主要是清洗缺失的数据值文献10针对互联网上数据错误的形式多样化现
20、象，模拟各类错误的产生过程，提出了一个彻头彻尾的概率清洗框架，该框架包括一个基于贝叶斯的生成模块和采用最大熵综合各个错误产生过程的错误模块生成模块主要是计算整个Intemet中每个元组f的候选元组f出现的概率，错误模块主要是综合各类错误产生过程中每个候选元组f+变成数据集中元组，的概率文献1统计分析数据集的概率分布，综合各类机器学习方法为脏元组提供多个局部候选修复，将全局修复的预测问题转换为图优化问题，试图找到具有最大可能性并且修改量最小化的修复方案文献11提出了一个最大限度地减少用户参与的交互式修复框架，主要包括排序模块和学习模块排序模块主要是使用决策理论的信息价值，记为VOI，来为待咨询的
21、一系列修复更新组排序学习模块主要是综合用户的反馈确定修复更新的不确定性，使用了主动学习技术上述文献在进行数据清洗或修复时都使用了机器学万方数据1688 Journal of Software软件学报V0127，No7，July 20 1 6习的相关技术，从数据集中抽取出了有用信息来提升修复的质量或者减少用户的参与，但这些信息大都分散到数据修复过程的各个模块中，而且有些文献19m1完全忽略了数据依赖本文的修复框架考虑了数据依赖对修复的有用信息，并将学习得到的有用信息以概率的信息形式统一整合在一起，使得信息的效用得到最大程度的使用2不一致性修复简介在数据质量领域中，现有的数据约束形式有很多种，如函
22、数依赖(FDs)、条件函数依赖(CFDs)、匹配依赖(MDs)和拒绝约束(DCs)等等数据的不一致性是指给定数据集D和数据约束集C，至少存在某些元组T：tlteDl不满足某个ceC，本文的数据约束形式是函数依赖，主要是修复函数依赖检测出的不一致数据。本节首先介绍函数依赖，然后介绍数据不一致，并引出不一致性修复问题21函数依赖函数依赖表示数据库中两个属性集合之间的约束关系每个函数依赖均有如下形式：X-Y,XcAttr(R)，Y亡_Attr(R)，其中,Attr(R)是指R中所有属性名构成的集合平凡的函数依赖在数据库实例中始终是成立的，它的定义为XjY，Y_酬,Xw_,4ttr(R)，YcAttr
23、(R)数据库中任意元组tz和tj,如果V工五ffB-0旺】成立，那么由于y崮必然有VyY,t，陟_0陟也就是说，始终满足平凡函数依赖所以，我们仅仅考虑非平凡的函数依赖，其定义为彤专y，耀墨xrC爿f以天)，YcAttr(R)，任意函数依赖，斗Y总能使用一元形式的函数依赖集合来等价表示如果某函数依赖，!轴y的右边属性集，的秩为l，则称厂是一元的由于一般的函数依赖集总能够直接转换成一元的函数依赖集，为了简化讨论，本文假设给定的函数依赖集F中每个函数依赖继F都是一元的22不一致性修复问题描述所谓数据不一致是指给定数据库实例I不满足函数依赖集F若给定数据库实例，不满足函数依赖，n4，记为，：它的语义是
24、指Jr中存在两个元组t1和f2，它们的z属性值一一对应相同，但是A的属性值不相同，其数学描述为：3t1，t2，t1【加=f2嘲且qAlet2口】类似地，如果数据库实例，不满足函数依赖集F中某个函数依赖扣F，则称数据库实例I不满足只记为胆F也就是说，相对于F是不一致的若给定数据库实例，满足某个函数依赖o爿，记为俨厂它的语义是指：，中任意两个元组，I和t2，如果它们的x属性值一一对应相同，那么它们的彳的属性值也相同其数学描述为Vtl，f2L如果fl闪=f2加，那么tlMf2】，如果对于函数依赖集F中任意函数依赖厂F，I均满足，=则称，满足只记为作F也就是说，相对于F是一致的所谓不一致性修复问题是指
25、：给定函数依赖集F和不一致的数据库实例J，通过某些操作，如插入、删除或更新，使得修复后的数据库实例IR满足函数依赖集，记为厶F考虑到删除操作会导致有用信息的丢失，插入操作会在数据库中引入意义不大的记录信息，本文仅采用更新操作完成修复任务3不一致性修复框架在本节中，我们提出了一个基于可能世界模型的不一致性修复框架，如图2所示该框架在借鉴前人的基于修复代价思路的基础上，融合机器学习方法和信息论中基于互信息的相关性分析，将数据中对修复有用的信息量化为候选修复值的正确的可能性，具体描述形式是概率值，取值范围是O，1】，使得从候选修复方案中筛选出更具合理性且修复质量更高的修复方案该框架以给定的不一致数据
26、库实例，和函数依赖集合F作为输入，输出的是满足函数依赖集F，即IRF，且概率值较高的可能世界实例厶如图2所示，该框架主要包括3个阶段，依次是冲突元组候选属性记录和属性值的构建阶段(Gcarav)、候选属性值的概率量化阶段(Ccavp)以及满足给定函数依赖集F且概率值较高的可能世万方数据徐耀丽等：基于可能世界模型的关系数据不一致性修复界实例的搜索阶段(Sqi)数据集 依蠹羹合L一一丫候选属性记录和属性值的构建阶段4，H“4)(Gcarav)T候选属性值的概率量化阶段，珞妒(Ccavp)满足给定函数依赖集且概率值较高的可能世界实例的搜索阶段(Sqi)Fig2 Framework for repai
27、ring inconsistent relational data based on possible world model图2基于可能世界的不一致性修复框架图1689冲突元组候选属性记录和属性值的构建阶段(Gcarav)主要是解决两个问题第一，候选属性记录的确定，就是错误出现的位置所谓冲突元组，是指那些导致数据库实例，不满足函数依赖集F的那些元组例如图l中，对于：OR专00，tl和f2的OR属性值一一对应相等，但00的属性值不相同，也就是说，tI和t2不满足，所以tl和t2是冲突元组对于f，而言，可能是订单编号(oR)也可能是订单状态(00)由于我们认为错误的位置是随机的，所以产生两条候选
28、属性记录，分别是(，l，OR，Vs(t1，0R)和(fl，00，Vs(tI，00)候选属性记录的形式是三元组(ff4，Vs(t。4I)，其中，t，是指中第f个元组的唯标识4t是指t。的第k个属性，Vs(t4)是t。的AI属性的候选属性值构成的集合第二候选属性值的选择对于某个候选属性记录，有哪些可能的候选属性值，也就是Vs(tj40的定义，具体详见第31节候选属性值的概率量化阶段(Ccavp)主要是从数据角度分析候选属性记录的每个候选属性值作为修复属性值的正确的可能性，并量化为概率值简而言之，就是候选属性值的概率量化计算我们综合考虑修复代价和相关性两方面信息来量化候选属性值的可信程度直观上，假如
29、一个候选属性值作为修复属性值的修复代价较小，那么该候选属性值是正确值的可能性就比较大，概率值比较高直观上，如果函数依赖脚彳不包含的B属性值，与候选属性值有比较大的正相关性，其中，B仨恩，那么该候选属性值正确的可能性比较大基于相关性的概率量化就是借助这些函数依赖以外的属性信息，分析候选属性值的正确的可能性，具体详见第32节在可能世界模型中，一个元组的某属性可能有多个取值将某元组的所有属性进行笛卡尔乘积可得到该元组的取值的所有可能情况所谓一个可能世界实例就是从数据集中选择某些元组，然后对每个元组，选择它取值的一种可能情况，所有被选中元组的取值汇聚在一起就构成了该数据集的一个可能世界实例考虑到修复问
30、题需要求解所有元组的取值，对可能世界实例进行了约束一个可能世界实例，不是针对数据集中的部分元组，而是针对所有元组也就是说，对于数据集中每个元组选择它的一种可能情况，所有元组的可能情况就构成一个可能世界实例例如图l所示，假设数据集为，函数依赖集为，-，；：OR-OO)，可得冲突元组集1F=t，f)，进而可得候选属性记录集CARs所谓候选属性记录集，是由所有冲突元组的所有候选属性记录构成的集合对候选属性记录集C船中每个元素的候选属性值进行过滤操作订单状态(oo)出现在函数依赖的右边，所以它的候选属性值有P，F，不包含0，而订单编号(OR)出现在函数依赖的左边，对于rl而言，与tl【oo取值相同的元
31、组有tl,t3，t4，5，t9)，所以它的订单编号(OR)的候选属性值是96，131，64，99，70)类似地，对于12而言，它的订单编号(OR)的候选属性值是96，65)对候选属性记录集中属性值的取值进行过滤操作后，可得CARs，它由4个候选属性记万方数据1690 Journal of Software软件学报V0127，No7，July 2016录构成，分别是(fl，OR，96，13l，64，99，70)，(fl，OO，P，F)，(，2，OR，96，65)和(f2，OO，P，F)为了减少搜索概率值较高可能世界实例的计算量，直接忽略候选属性记录不包括的属性，如t，的地区名(RN)、供应商名(
32、PM)等属性可能世界实例的构建过程是任取两个候选属性记录，对这两个候选属性值集合进行笛卡尔乘积，得到一个超级候选属性记录将已经处理的候选属性记录从CARs中移除，并将得到的超级候选属性记录加入CARs，循环执行，直到只剩下一个超级候选属性记录，该超级候选记录的属性值集合的每一个元素就是一个可能世界实例所谓超级候选记录是扩展了候选属性记录的定义后所得，是由形式为(TIDs,As，avs)的三元组构成的集合其中，TIDs是一个n元组，目P(tidl，rid2，tia，该元组的元素由元组标识组成，与属性值集合avs中元素的属性值列表建立一一对应关系，表示属性值的唯一元组标识，类似地4s也是一个n元组
33、，即翻424。)，该元组的元素由元组属性名组成，与aYS中元素的属性值列表建立一一对应关系，表示属性值的唯一属性标识TIDs和爿s元组的维度胛由候选属性记录的数目决定avs是爿s取值情况构成的集合，该集合的元素是一个n元组，即(v，v：。)如将(tI,OR，96，13l，64，99，70)和(tl,OO，P，F)经过笛卡尔乘积操作后，可得珊s=(亿t1)4s=(OR，oo，avs=(96，D，(96，P)，概率数据库可以很好地描述一个可能世界，例如，冲突元组集，i=t，描述的可能世界可表示成如图3所示，其中，每个属性值都附加一个概率值，该概率值是融合候选属性值的概率量化阶段(Ccavp)得到的
34、候选属性值的基于相关性的概率和基于修复代价的概率而得TID OR OOtl (96，036)，(99，0 24)，(131，0 2)，(64，0 1 5)，(70，0 05) (尸，0 37)，(F,063)12 il!：!：竺2：竖i：!：j12 2 i!：!：j；2：l：!：!婴Fig3 Probabilistic database图3概率数据库一个可能世界实例的概率值计算分如下3步来计算 首先，从候选属性值的量化阶段(Ccavp)得到每个属性值的两个概率并融合为一个； 然后，计算每个元组的概率，也就是对该元组所有属性值的概率进行累加和操作，记为p(t)，其计算公式为p(f。)2乞p(，A
35、j，u)，其中护(，一。h)是指元组的彳，属性值为的概率值； 最后，将可能世界实例的所有元组的概率进行累加和操作，记为p(取肋)，它的计算公式如下所示：p(I(PD)=p(t。)，-忙其中，PD是指表述可能世界的概率数据库，I(PD)指的是该概率数据库所描述的某个可能世界实例满足给定函数依赖且概率值较高的可能世界实例的搜索阶段(Sqi)主要是以可能世界的所有可能世界实例集合作为搜索空间，从中选择出满足F且实例的概率值较高的实例Itz作为修复方案选择概率值较高的实例是因为可能世界实例的概率值是由候选属性值的概率值表示的，该概率值越高，那么表示构成实例的属性值的正确性越高、越可信然而，采用这种直观
36、的先构建再判断的搜索策略是很低效的特别是当，i中元组数目、候选属性数目和候选属性值的取值增大时，可能世界实例的数目呈爆炸式增长假设，i中的元组数目为以，属性列的数目为七，且某个元组ti(iE1，2，刀】)、某个属性彳j(，12纠)的取值都有m种，那么该概率数据库包含的可能世界实例数目为N=nnm n k鉴于先构建再判断的搜索策略是很低效的，为此，在第4节设计并实现了贪婪的搜索算法31候选属性记录的构建候选属性记录的构建主要用来确定哪些冲突元组是有错误的、错误元组的哪个属性含有错误、错误属性的可能取值有哪些，它们分别对应于候选属性记录三元组形式中的t,A和Vs(t,A)的取值冲突元组的候选属性记
37、录的数目和候选属性值的数目直接决定了可能世界的实例数目减少不必要的候选属性记录数目和过滤完全万方数据徐耀丽等：基于可能世界模型的关系数据不一致渺复 1691不可能的候选属性值，可以减少错误值的干扰，同时减少概率量化阶段的计算量直观上，错误总是出现在小部分里面对于违反某函数依赖，卫辛彳的冲突元组集，?而言，我们假设小部分元组是有错误的，而大部分的元组是正确的，因此只需为小部分元组构建候选属性记录所谓小部分元组是指，中与该元组t的和A属性取值相同的元组数目，记为Num(tXA)，J、于与该元组的X属性取值相同的元组数目，记为Num(tIX)的一半如图1中五：PBjPM的冲突元组集tl,t3，t4)
38、中，t4就属于小部分元组因为供应商标(PB)取值为Brand#53的元组数目为3，而供应商标(PB)取值为Brand#53且供应商名(PM)取值为Manufacturer#4的元组数目为l，小于3的一半，所以属于小部分元组，而t。和t3则属于大部分元组，不需要为它们构建候选属性记录如果Num(tXA)等于Num(tX)的一半，那么我们为所有的冲突元组构建候选属性记录，因为这些元组虽然不属于小部分元组，但是有05的概率是含有错误的如图l中：oROO的冲突元组集l，龟)，订单编号(OR)为96的元组数目为2，订单编号(0R)为96且订单状态(00)为F的元组数目为1，所以tI虽然不属于小部分元组，
39、但需要为f，构建候选属性记录对于某些含有错误的元组，可以对该元组违反的函数依赖集进行分析，事先辨别该错误元组哪部分属性含有错误这样就可以只为含有错误的属性构建候选属性记录，而不必为不含错误的属性构建候选属性记录，减少了不必要的计算和干扰假设t为违反，。n彳的小部分元组，且l剧大于3，有如下两种情况可以事先辨别t的哪部分属性含有错误 情况1：，的x中含有错误假设该元组t违反了，：同时违反了给定函数依赖集几中所有的函数依赖，那么我们认为错误出现在函数依赖x属性中其中，氏是指给定函数依赖集F中所有左边为x的函数依赖反证法：假设对于该元组错误出现在A中，那么它必定违反，=但不一定同时违反所有左边为X的
40、函数依赖 情况2：t的A中含有错误假设该元组f违反了，=同时不违反给定函数依赖集而中除去厂以外的所有函数依赖，那我们认为t的4中含有错误反证法：假设t的中含有错误，那么t至少违反艮中两个函数依赖如果属于上述情况，那么只需为含有错误的属性构建候选属性记录；反之不属于上述两种情况，那么，我们假设错误元组的x属性和A属性均有可能含有错误，为A属性构建一个候选属性记录，即(卅，妇(卅)，为x中每个属性Xx构建一个候选属性记录(t,Xi，冶(f)候选属性值Vs(t,A)的过滤原则是：只添加可能的候选值，以排除完全不可能的候选值的干扰假设是给定函数依赖集，中包含A的那些函数依赖，过滤的方法是：找出t为满足
41、n需要保持一致的那些相关联元组，将这些相关联元组的爿属性值作为候选属性值对于凡中某函数依赖，占，若A与曰相同，也就是在函数依赖的右边，那么计算f为满足需要保持一致的所有相关元组集合，记为refTs=It冈=fIX)若爿与曰不相同，也就是在函数依赖的左边，那么相关元组集refrsq)是指与f的c属性值相同的那些元组构成的集合的并集，即：reJTs(f)=U川rc-fc】)，其中，C是指除去爿以外的函数依赖属性CXuBL4然后，将n中所有相关元组集的并集作为t的爿属性相关的元组集，这些元组的所有A属性值就构成了候选属性值妇(f4)，其数学定义如公式(1)所示f Vs(t，A)=tAlt 7U re
42、fFs(f) (1)【e J如图1所示，tl的订单状态(00)在Z的右边，所以tl为满足凡。的相关联元组集合refFs)为f1，如，那么候选属性值Vs(tl，oo)Yq(F，P而fI的订单编号(0R)在的左边，所以tl为满足凡R的相关联元组集合reJT姒)为ll,t3，t4，f5，9，也就是所有订单状态(Oo)值为F的那些元组32候选属性值的概率量化候选属性值的概率值量化包括基于相关性的概率量化和基于修复代价的概率量化两部分，那么，候选属性万方数据1692 Journal of Software软件学报V0127，No7，July 20 1 6值的总概率是两者的平均值，以表示该候选属性值正确的
43、可能程度321 基于相关性的概率量化数据集中属性列之间的相关性暗含的推理信息，可以协助确定更合理的修复方案鉴于本文在处理数据时把所有的属性都视为标称属性来处理，而信息处理的互信息在量化标称属性的相关性较好，采用互信息来进行独立性判断和相关程度度量相关性分析的核心思想是对某函数依赖，H4，使用互信息量化函数依赖的属性A与数据集中属性B之间的相关程度，其中4B硭昨凡彳，研是函数依赖的属性集所谓函数依赖的属性集是指出现在函数依赖的属性构成的集合若把属性A和日视为随机变量，那么A和B的互信息记为删；B)，其取值范围是0，min(H(A)，坝曰)，其数学定义为“彳；曰)=觑4)一日(AIB)熵是随机变量
44、不确定性的度量，熵越大，变量的不确定性越高对于随机变量爿，它的数学定义如公式(2)所示H(A)=一p(口)logp(a) (2)口其中，p(口)是指变量彳的取值为a事件发生的概率值给定日后4的条件熵川4I曰)是指观察到变量曰后A的不确定性，它的数学定义如公式(3)所示H(AIB)=H(A JB=6)p(B=b) (3)b将B的取值为b条件下变量爿视为随机变量，那么川爿I曰=6)表示该随机变量的熵；p(B=6)是指变量日的取值为b事件发生的概率值由于4的熵肌爿)量化了观察到变量曰之前A的不确定程度，而条件熵H(AIB)是观测到B后A尚存的不确定性，所以，互信息删；B)表示变量曰包含多少彳的信息当
45、删；B)为0时，表明B与爿是相互独立的；当“爿；B)不为0时，表明曰与4是相关的，并且两个变量的互信息越大，那么它们之间的相关程度越高所谓无冲突数据集扛是指，中去掉那些冲突元组后，得到的元组集合，即廿，如图1所示，假设数据集为L函数依赖集为户：OR-+OO)，可得无冲突元组集：，F=t3,t4，t5，t6，t7，t8，t9，Uji 2OR，oo，OOU，PM硅U依据后，可得00变量的值域为F,O，JD护(刁=47护(P)=l7,p(O)=27进而，依据公式(2)可得OO的熵H(00)约为096类似地，PM变量取值为Manufacturer#5，Manufacturer#4，Manufactur
46、er#3，Manufacturer#2发生的概率分别为37，17，27，17OO变量在PM=Manufacturer#5的条件下取值为FO，P发生的概率分别为23，13，0可得H(OOlPM=Manufacturer#5)O63，依据公式(2)，可得：川OOlPM=Manufacturer#4)=0，4(OOlPM=Manufacturer#3)069，4(OO LPM=Manufacturer#2)=0将这些值代入公式(3)，可得给定PM后OO的条件熵4(OOIPM)z047最后，依据互信息的定义，可得I(00；PM)zO49类似地，可得I(OO；OS)=0，表明订单船舶优先权(OS)与订单
47、状态是独立的I(OO；RN)z007比047小，表明供应商名(PM)与订单状态(OO)相关程度比地区名(RN)与订单状态(00)相关程度要高相关性分析的处理流程以无冲突数据集后和函数依赖集F为输入，输出相关信息矩阵arrayc，如过程l所示L3是将后的属性分为两类和【，i，其中，坼是函数依赖的属性集，ui是非函数依赖的属性集L5L12用来判断UF中每个属性A与其他属性之fnl是否独立：若不独立，则量化它们之间的相关性程度L7是依据定义计算属性4和曰的互信息几4；B)L8L1 l则是依据互信息的性质，如果几4；日)为0，那么将日添加到A的独立属性列表(indANs)O?；否则，将口添加到A的相关属性列表(aAUs)eF，并将删；曰)作为两者相关程度的量化值L12是将计算得到的相关信息存储在array。中过程1数据相关性分析输入：无冲突数据集扛，函数依赖集F；输出：相关信息矩阵array。1 BEGIN2 array。卜g3 ，6-splitAttributes(1F，F)万方数据徐耀丽等：基于可能世界模型的关系数据不一致性修复 16934- U_UFuUi5 FOREACHADO6 FOREACHBUD071(A；B)-computeMl(A，曰)8 IF m4；曰)=0 THEN AindANs口删曰)9 ELSEl 0 Ad