Model Counting for Conjunctive Queries Without Self-Joins
share
We study the problem of model counting for Boolean Conjunctive Queries (CQs): given a database, how many of its subsets satisfy the CQ? This problem is computationally equivalent to the evaluation of a CQ over a tuple-independent probabilistic database (i.e., determining the probability of satisfying the CQ) when the probability of every tuple is 1/2. In particular, it follows from the work of Dalvi and Suciu that this problem is solvable in polynomial time (data complexity) for every hierarchical CQ without self-joins. However, while probabilistic query evaluation is intractable for non-hierarchical CQs, it has been open whether this hardness applies already for model counting. We prove that, indeed, model counting is #P-complete for every non-hierarchical CQ without self-joins. Hence, we establish that the dichotomy in the complexity probabilistic query evaluation also holds for model counting.
READ FULL TEXT