The Dichotomy of Conjunctive Queries on Probabilistic Structures

Nilesh Dalvi, Dan Suciu

We show that for every conjunctive query, the complexity of evaluating it on a probabilistic database is either \PTIME or #¶-complete, and we give an algorithm for deciding whether…