Paper Info
Title
The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints
Abstract
A relational database is said to be uncertain if primary key constraints can possibly be violated. A repair (or possible world) of an uncertain database is obtained by selecting a maximal number of tuples without ever selecting two distinct tuples with the same primary key value. For any Boolean query q, CERTAINTY(q) is the problem that takes an uncertain database db as input, and asks whether q is true in every repair of db. The complexity of this problem has been particularly studied for q ranging over the class of self-join-free Boolean conjunctive queries. A research challenge is to determine, given q, whether CERTAINTY(q) belongs to complexity classes FO, P, or coNP-complete. In this paper, we combine existing techniques for studying the above complexity classification task. We show that for any self-join-free Boolean conjunctive query q, it can be decided whether or not CERTAINTY(q) is in FO. Further, for any self-join-free Boolean conjunctive query q, CERTAINTY(q) is either in P or coNP-complete, and the complexity dichotomy is effective. This settles a research question that has been open for ten years.
Year
DOI
Venue
2015
10.1145/2745754.2745769
ACM SIGMOD Conference on Principles of DB Systems
Keywords
Field
DocType
Conjunctive queries, consistent query answering, primary keys
Complexity class,Discrete mathematics,Conjunctive query,Primary Key,Certainty,Relational database,Tuple,Computer science,Theoretical computer science,Boolean conjunctive query,Possible world
Conference
Citations 
PageRank 
References 
14
0.65
16
Authors
2
Name
Order
Citations
PageRank
Paraschos Koutris134726.63
Jef Wijsen2140.65