不一致数据上查询结果的一致性估计

摘要：

主键约束是描述关系数据一致性的常用方法，基于主键约束的数据一致性修复返回一个极大子集，子集中不同数据的主键不同。对于合取查询 Q，一致性合取查询返回一个答案集合，答案集合是 Q 在数据集合 I 的每一个修复下查询结果的交集。文中将 Q 在 I 中的查询结果满足一致性的个数占总的结果个数的比例定义为查询结果的一致性程度。若 Q 不可一阶表达且不能在多项式时间内得到其一致性解，则当 Q 答案个数超过30时，使用抽样的方法给答案集合一致性程度的一个（ε，δ）-估计。由于布尔合取查询的一致性判定问题是 coNP-完全问题，因此在估计过程中，使用攻击图，通过攻击图对布尔查询 q 进行改写近似判断 q 近似一致性回答。实验表明了估计算法和近似判定算法具有较高的效率和准确率。

关键词：主键约束、一致性查询、合取查询、近似一致性

分类号：TP311(计算技术、计算机技术)

资助基金：国家“九七三”重点基础研究发展规划项目基金2012CB316200;国家自然科学基金61003046，6111113089;国家教育部博士点基金20102302120054资助．This study is fund by the National Basic Research Program 973 Programof China under Grant No．2010CB316200． This project aims to study the basic theory and key technology

在线出版日期：2015-10-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：1727-1738