A Dichotomy on the Complexity of Consistent Query Answering for Atoms with Simple Keys
A Dichotomy on the Complexity of Consistent Query Answering for Atoms with Simple Keys
复制标题
简单键原子一致查询应答复杂性的二分法
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Dan Suciu
中科院分区：
文献类型：
--
作者：
Paraschos Koutris;Dan Suciu
研究了主键违规情况下的一致性查询应答问题。在这种情况下，数据库中的关系违反了键约束，而我们感兴趣的是数据库中满足这些约束的最大子集，我们称之为修复。对于布尔查询Q，问题确定性(Q)询问每个这样的修复是否满足查询；对于合取查询，已知问题总是在coNP中。然而，对于某些查询，它可以在多项式时间内求解。关于合取查询的确定性(Q)的复杂性(Q)，人们猜测存在两种情况：它要么是p时间的，要么是conp完全的。在这篇文章中，我们证明了对于没有自联接的合取查询的情况，该猜想确实成立，其中每个原子以单个属性(简单键)或原子的所有属性作为键。
We study the problem of consistent query answering under primary key violations. In this setting, the relations in a database violate the key constraints and we are interested in maximal subsets of the database that satisfy the constraints, which we call repairs. For a boolean query Q, the problem CERTAINTY(Q) asks whether every such repair satisfies the query or not; the problem is known to be always in coNP for conjunctive queries. However, there are queries for which it can be solved in polynomial time. It has been conjectured that there exists a dichotomy on the complexity of CERTAINTY(Q) for conjunctive queries: it is either in PTIME or coNPcomplete. In this paper, we prove that the conjecture is indeed true for the case of conjunctive queries without self-joins, where each atom has as a key either a single attribute (simple key) or all attributes of the atom.