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

被引：2

作者：

刘雪莉

李建中

机构：

[1] 哈尔滨工业大学计算机科学与技术学院

来源：

计算机学报 | 2015年 / 38卷 / 09期

关键词：

主键约束; 一致性查询; 合取查询; 近似一致性;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

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

引用

页码：1727 / 1738

页数：12

共 12 条

[1] 大数据的一个重要方面:数据可用性
李建中
刘显敏
[J]. 计算机研究与发展, 2013, (06) : 1147 - 1162
[2] 基于空值修复的数据库一致性查询方法
黄飞
刘杰
叶丹
[J]. 计算机应用研究, 2009, 26 (11) : 4146 - 4150
[3] Certain Conjunctive Query Answering in First-Order Logic
Wijsen, Jef
[J]. ACM TRANSACTIONS ON DATABASE SYSTEMS, 2012, 37 (02):
[4] Polynomial time queries over inconsistent databases with functional dependencies and foreign keys
Molinaro, Cristian
Greco, Sergio
[J]. DATA & KNOWLEDGE ENGINEERING, 2010, 69 (07) : 709 - 722
[5] Querying and Repairing Inconsistent Numerical Databases
Flesca, Sergio
Furfaro, Filippo
Parisi, Francesco
[J]. ACM TRANSACTIONS ON DATABASE SYSTEMS, 2010, 35 (02):
[6] The complexity and approximation of fixing numerical attributes in databases under integrity constraints[J] . Leopoldo Bertossi,Loreto Bravo,Enrico Franconi,Andrei Lopatenko.Information Systems . 2008 (4)
[7] Study on consistent query answering in inconsistent databases[J] . Dong Xie,Luming Yang.Frontiers of Computer Science in China . 2007 (4)
[8] First-order query rewriting for inconsistent databases[J] . Ariel Fuxman,Renée J. Miller.Journal of Computer and System Sciences . 2006 (4)
[9] Database repairing using updates
Wijsen, J
[J]. ACM TRANSACTIONS ON DATABASE SYSTEMS, 2005, 30 (03): : 722 - 768
[10] Minimal-change integrity maintenance using tuple deletions[J] . Jan Chomicki,Jerzy Marcinkowski.Information and Computation . 2005 (1)

← 1 2 →