A dichotomy in the complexity of consistent query answering for queries with two atoms

作者：Kolaitis Phokion G^*; Pema Enela

来源：Information Processing Letters, 2012, 112(3): 77-85.

DOI：10.1016/j.ipl.2011.10.018

• Databases
• Key constraints
• Database repairs
• Consistent query answering

We establish a dichotomy in the complexity of computing the consistent answers of a Boolean conjunctive query with exactly two atoms and without self-joins. Specifically, we show that the problem of computing the consistent answers of such a query either is in P or it is coNP-complete. Moreover, we give an efficiently checkable criterion for determining which of these two possibilities holds for a given query.

• 出版日期2012-1-31