【作者】 杨辉；

【导师】 于守健；

【作者基本信息】 东华大学 ， 软件工程， 2017， 硕士

【摘要】 数据质量管理已被公认为是数据管理系统的首要任务之一。针对数据质量管理领域的数据一致性和正确性,大量的完整性约束规则只能发现数据中的错误,基于这些约束的数据修复不能保证绝对的正确。论文分别从编辑规则挖掘和不一致数据修复两个方面,研究基于输入样本和主数据的编辑规则挖掘方法与基于编辑规则的不一致数据自动修复方法。在此基础上,以MyEclipse为实验平台,用java语言实现了相关算法,并将其应用到实际数据中。实验结果表明,这些方法应用于关系型数据库,能有效地挖掘出编辑规则,并正确地修复不一致数据。具体研究内容如下。研究了基于条件函数依赖挖掘的编辑规则挖掘技术。分析比较了现有的条件函数依赖挖掘算法CFDMiner、FastCFD和CTANE,对FastCFD算法中计算差集的过程进行了改进,并给出了CFDMiner和FastCFD的具体实现。通过扩展条件函数依赖,重新定义了编辑规则。针对主数据模式和样本数据模式不一致的情况,提出了从源数据到主数据一对一属性关系的挖掘方法。在此基础上,给出了编辑规则的挖掘算法,分析了算法的性能,并结合实例说明算法的执行过程。结合CFDs修复技术,研究了基于编辑规则的数据修复技术。首先分析了基于CFDs修复的相关技术,对相关算法给出了具体实现和理论证明。在此基础上,分析了编辑规则的一致性问题和覆盖问题,并证明了他们是NP-完全问题;为了实现确定的修复,基于图的理论,提出了从编辑规则和主数据中挖掘certain region结构的算法,从而实现了基于编辑规则和主数据的数据修复算法。基于CFDs的修复思想是对违反项用该项的等价类目标值进行修复,最终达到所有元组满足规则集的状态,这难以保证修复绝对的正确。而本文基于编辑规则的修复技术,充分利用干净的主数据,在修复前对元组在规则左边的属性值是否正确进行了校验,防止元组错误地应用于该规则,可以保证正确的修复。最后,通过实例说明了论文所提的算法确实能达到正确的修复结果。通过实验,以时间和规则数为评价指标,对比分析了基于不同CFDs挖掘技术的编辑规则挖掘算法的性能。实验结果表明,基于FastCFD的算法比基于CFDMiner的算法要更加耗时,但能挖掘出更多的规则。此外,还分析对比了基于CFDs的修复算法与基于编辑规则的修复算法。实验结果表明,两者运行时间相近,但从F-measure指标上看,基于编辑规则的修复效果要比基于CFDs的修复效果好,这证明了论文所研究的基于编辑规则数据修复的有效性。更多还原

【Abstract】 Data quality management has been recognised as one of the first tasks of data management system.For the data consistency and accuracy in the field of data quality management,a variety of integrity constraints can only be good to detect errors in the data.Indeed,data repairing based on these constraints may not ensure that the fixes are absolutely correct.This paper respectively considers the editing rules mining and inconsistent data repairing.It provide an algorithm to mine editing rules from source relations and master relations and another algorithm to repair inconsistent data automatic based on editing rules.At the same time,on the basis of the proposed method,put MyEclipse as the experimental development platform,with java implement the above algorithm and applied to real-life data.The experimental results show that the methods applied to relational database can effectively dig out editing rules and on the basis of which can correctly repair inconsistent data.The concrete research content is as follows.The technology of mining editing rules based on conditional functional dependencies mined is researched.Analysis and comparison of existing CFDMiner,FastCFD and CTANE,the procedure of FastCFD computing difference sets is improved,and implemented CFDMiner and FastCFD,by extent conditional functional dependencies,redefine editing rules,in view of master schema different from sample data schema,provide the algorithm of the discovery of one-to-one correspondences from sources to master attributes.On this basis,the algorithm of mining editing rules is given,the performance of the algorithm is analyzed,and the implementation process of the algorithm is illustrated with an example.On the basis of CFDs repair technology,the data repair technology based on editing rules is studied.At first,the related technologies based on CFDs repair are analyzed,and the concrete realization and theoretical proof are given.On this basis,the analysis of the consistency problem and coverage problem of editing rules,and prove that they are NP-complete problem;in order to achieve certain repair,based on graph theory,put forward certain region structure mining algorithm from editing rules and master data,so as to realize data repair algorithm based on the editing rules and master.Based on CFDs repair technology for the violation item,using the target value of the equivalence class that the violation belong to,ultimately achieve the state of all tuples,and the algorithm cannot guarantee that repair is absolutely correct.But the repair technology based on editing rules,which make full use of clean master data,before repairing test whether the attribute value at left of the rule is correct,and prevent mistakenly applied to the rules,so this article proposed repair method based on editing rules can guarantee absolutely correct.Finally,an example shows that the algorithm proposed in this paper can achieve the correct results.By the experiment,the time and number of rules are evaluated,and the performance of the algorithm of editing rules mining based on different CFDs mining is analyzed and compared.Experimental results show that the algorithm based FastCFD is more time consuming than the algorithm based CFDMiner,but it can dig out more rules.In addition,the repair algorithm based on CFDs and the repair algorithm based on editing rules are analyzed and compared.The experimental results show that the running time is similar,but judging from the F-measure,the repairing based on editing rules more effective than the repairing based on CFDs,which proves the validity of the data repairing based on editing rules.更多还原