2015/01/30 by Paraschos Koutris, Koutris, Paraschos, Jef Wijsen +1 · 1 citation
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Databases (cs.DB) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.1501.07864
openalex publication_date 2015/01/30 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
A relational database is said to be uncertain if primary key constraints can\npossibly be violated. A repair (or possible world) of an uncertain database is\nobtained by selecting a maximal number of tuples without ever selecting two\ndistinct tuples with the same primary key value. For any Boolean query q,\nCERTAINTY(q) is the problem that takes an uncertain database db on input, and\nasks whether q is true in every repair of db. The complexity of this problem\nhas been particularly studied for q ranging over the class of self-join-free\nBoolean conjunctive queries. A research challenge is to determine, given q,\nwhether CERTAINTY(q) belongs to complexity classes FO, P, or coNP-complete. In\nthis paper, we combine existing techniques for studying the above complexity\nclassification task. We show that for any self-join-free Boolean conjunctive\nquery q, it can be decided whether or not CERTAINTY(q) is in FO. Further, for\nany self-join-free Boolean conjunctive query q, CERTAINTY(q) is either in P or\ncoNP-complete, and the complexity dichotomy is effective. This settles a\nresearch question that has been open for ten years, since [9].\n