2026-07-22T11:56:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10325 2024-03-06T10:45:49Z ddc:004 open_access

Consistent Query Answering for Primary Keys in Logspace Koutris, Paraschos Wijsen, Jef conjunctive queries consistent query answering Datalog primary keys We study the complexity of consistent query answering on databases that may violate primary key constraints. A repair of such a database is any consistent database that can be obtained by deleting a minimal set of tuples. For every Boolean query q, CERTAINTY(q) is the problem that takes a database as input and asks whether q evaluates to true on every repair. In [Koutris and Wijsen, ACM TODS, 2017], the authors show that for every self-join-free Boolean conjunctive query q, the problem CERTAINTY(q) is either in P or coNP-complete, and it is decidable which of the two cases applies. In this paper, we sharpen this result by showing that for every self-join-free Boolean conjunctive query q, the problem CERTAINTY(q) is either expressible in symmetric stratified Datalog (with some aggregation operator) or coNP-complete. Since symmetric stratified Datalog is in L, we thus obtain a complexity-theoretic dichotomy between L and coNP-complete. Another new finding of practical importance is that CERTAINTY(q) is on the logspace side of the dichotomy for queries q where all join conditions express foreign-to-primary key matches, which is undoubtedly the most common type of join condition. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paraschos Koutris and Jef Wijsen 2019 Is Part Of LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2019.23 urn:nbn:de:0030-drops-103252 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.23 eng https://creativecommons.org/licenses/by/3.0/legalcode