Model Counting for Conjunctive Queries Without Self-Joins

08/19/2019
by   Antoine Amarilli, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset