论文部分内容阅读
违反完整性约束的数据叫不一致数据。虽然完整性约束被用于防止不一致已经很长时间了,但由于各类原因,不一致数据仍然普遍存在于多类现实应用中。这些应用不单单包括数据整合、数据交换、数据挖掘、数据抽取、科学数据管理、传感网络等关系数据应用,还包括XML网络信息交换和集成等。不一致数据蕴含着错误信息,在这样的数据库上回答用户提出的查询,得到的结果也可能是错误的。本文在保持信息准和全的前提下,从语义层面重新思考了不一致数据上的查询结果的确定性、可信性及其价值,针对关系数据,提出了一种带标记的不一致数据表示模型。根据这个模型,不一致性被看作是数据的一个属性,并能使用标记符号加以说明,也就是说,所有数据库及其查询回答的单元值上都可以附上0到多个标记,如果没附上任何标记,该单元值可信,反之不可信。为了在查询结果中正确地保持标记的语义,本文还定义了该模型上的7种基本查询操作、处理规则及其语义。并证明了整个研究方案的正确性和完备性。本研究方案把不一致的认定细化到属性级别,从而避免了信息丢失。上述模型及其上的查询操作要能真正在实际中得到应用,需要一个可以兼容一致数据模型及其查询处理的实现方案,以便能在不影响传统数据管理和查询的基础上,实现不一致数据的管理和查询处理。本文采纳了基于查询重写的实现策略。在函数依赖和综合约束两个范围内,对任意类型的查询,提出了其重写算法,并针对不同的应用环境,提出了不同的重写算法优化方法。并在人造数据和TPC-H数据上开展了丰富的实验。实现了其Demo系统。XML数据模型复杂,语法灵活,缺乏约束方面的严格规范,并常用于数据交换和数据集成,因此XML文档中的不一致问题甚至比关系数据更为严重。本文采用基于修复的数据查询处理方法来计算可信的查询结果,其核心是寻找不一致XML文档的最优修复。但求解最优修复是一个NP完全问题,特别是当XML文档同时违反函数依赖约束和主键约束时。本文提出一个基于代价模型,能同时解决置等和置不等约束,且可以在多项式时间内完成的启发式修复求解算法。该算法首先借助索引表,在一遍扫描原始XML文档的情况下,寻找不一致数据集,然后为每一类约束的不一致数据集构造候选修复,同时计算其修复代价,最后启发式地求解一个代价最小的修复方案。实验证明,该算法的时间复杂度不超过冲突类的3次方,即便是不一致数据大量、噪声比例大、且涉及多类语义约束时,也能较快地完成修复。