On the consistent rewriting of conjunctive queries under primary key constraints

This article deals with the computation of consistent answers to queries on relational databases that violate primary key constraints. A repair of such inconsistent database is obtained by selecting a maximal number of tuples from each relation without ever selecting two distinct tuples that agree on the primary key. We are interested in the following problem: Given a Boolean conjunctive query q  , compute a Boolean first-order (FO) query ψψ such that for every database dbdb, ψψ evaluates to true on dbdb if and only if q   evaluates to true on every repair of dbdb. Such ψψ is called a consistent FO rewriting of q.We use novel techniques to characterize classes of queries that have a consistent FO rewriting. In this way, we are able to extend previously known classes and discover new ones. Finally, we use an Ehrenfeucht–Fraïssé game to show the non-existence of a consistent FO rewriting for ∃x∃y(R(x̲,y)∧R(y̲,c)), where c is a constant and the first coordinate of R is the primary key.