Counting Database Repairs that Satisfy Conjunctive Queries with Self-Joins
Dany Maslowski, Jef Wijsen · 2014
An uncertain database is defined as a relational database in which primary keys need not be satisfied. A block is a maximal subset of tuples of the same relation that agree on the primary key. A repair (or possible world) of an uncer-tain database is obtained by selecting exactly one tuple from each block. From a probabilistic database perspective, an uncertain database is a restricted kind of block-independent disjoint (BID) probabilistic database, where the restriction is that the probabilities of tuples in a block are equal and sum up to one. For every fixed Boolean query q, the counting problem ♮CERTAINTY(q) takes as input an uncertain database db and asks to determine the number of repairs that satisfy q. A Boolean conjunctive query is self-join-free if no rela-tion name occurs more than once in it. In previous work, it was proved that for every self-join-free Boolean conjunc-tive query q, the problem ♮CERTAINTY(q) is either in FP or ♮P-complete, and it is decidable which of the two cases applies. This complexity dichotomy has its analogue in BID probabilistic databases. The current paper investigates the complexity of the prob-lem ♮CERTAINTY(q) for Boolean conjunctive queries with self-joins. Our most appealing result is that for every Boolean conjunctive query q (possibly with self-joins) in which all pri-mary keys consist of a single attribute, ♮CERTAINTY(q) is either in FP or ♮P-complete, and it is decidable which of the two cases applies. Significantly, no analogous dichotomy for conjunctive queries with self-joins is known for BID proba-bilistic databases.