This is the authors' abstract. We don't add key points for this paper.
Primary key violations provide a natural means for modeling uncertainty in the relational data model. A repair (or possible world) of a database is then obtained by selecting a maximal number of tuples without ever selecting two distinct tuples that have the same primary key value. For a Boolean query q , the problem CERTAINTY( q ) takes as input a database db and asks whether q evaluates to true on every repair of db . We are interested in determining queries q for which CERTAINTY( q ) is first-order expressible (and hence in the low complexity class AC °). For queries q in the class of conjunctive queries without self-join, we provide a necessary syntactic condition for first-order expressibility of CERTAINTY( q ). For acyclic queries (in the sense of Beeri et al. [1983]), this necessary condition is also a sufficient condition. So we obtain a decision procedure for first-order expressibility of CERTAINTY( q ) when q is acyclic and without self-join. We also show that if CERTAINTY( q ) is first-order expressible, its first-order definition, commonly called certain first-order rewriting, can be constructed in a rather straightforward way.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Jef Wijsen (2012) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: