Abstract
We consider the dichotomy conjecture for consistent query answering under primary key constraints. It states that, for every fixed Boolean conjunctive query q, testing whether q is certain (i.e. whether it evaluates to true over all repairs of a given inconsistent database) is either polynomial time or coNPcomplete. This conjecture has been verified for selfjoinfree and path queries.
We propose a simple inflationary fixpoint algorithm for consistent query answering which, for a given database, naively computes a set Δ of subsets of database repairs with at most k facts, where k is the size of the query q. The algorithm runs in polynomial time and can be formally defined as:
1) Initialize Δ with all sets S of at most k facts such that S⊧ q.
2) Add any set S of at most k facts to Δ if there exists a block B (i.e., a maximal set of facts sharing the same key) such that for every fact a ∈ B there is a set S' ∈ Δ contained in S ∪ {a}. The algorithm answers "q is certain" iff Δ eventually contains the empty set. The algorithm correctly computes certainty when the query q falls in the polynomial time cases of the known dichotomies for selfjoinfree queries and path queries. For arbitrary Boolean conjunctive queries, the algorithm is an underapproximation: the query is guaranteed to be certain if the algorithm claims so. However, there are polynomial time certain queries (with selfjoins) which are not identified as such by the algorithm.
BibTeX  Entry
@InProceedings{figueira_et_al:LIPIcs.ICDT.2023.24,
author = {Figueira, Diego and Padmanabha, Anantha and Segoufin, Luc and Sirangelo, Cristina},
title = {{A Simple Algorithm for Consistent Query Answering Under Primary Keys}},
booktitle = {26th International Conference on Database Theory (ICDT 2023)},
pages = {24:124:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772709},
ISSN = {18688969},
year = {2023},
volume = {255},
editor = {Geerts, Floris and Vandevoort, Brecht},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17766},
URN = {urn:nbn:de:0030drops177663},
doi = {10.4230/LIPIcs.ICDT.2023.24},
annote = {Keywords: consistent query answering, primary keys, conjunctive queries}
}
Keywords: 

consistent query answering, primary keys, conjunctive queries 
Collection: 

26th International Conference on Database Theory (ICDT 2023) 
Issue Date: 

2023 
Date of publication: 

17.03.2023 