The Dichotomy of Conjunctive Queries on Probabilistic Structures
<|reference_start|>The Dichotomy of Conjunctive Queries on Probabilistic Structures: We show that for every conjunctive query, the complexity of evaluating it on a probabilistic database is either \PTIME or #\P-complete, and we give an algorithm for deciding whether a given conjunctive query is \PTIME or #\P-complete. The dichotomy property is a fundamental result on query evaluation on probabilistic databases and it gives a complete classification of the complexity of conjunctive queries.<|reference_end|>
@article{dalvi2006the,
    title={The Dichotomy of Conjunctive Queries on Probabilistic Structures},
    author={Nilesh Dalvi and Dan Suciu},
    journal={arXiv preprint arXiv:cs/0612102},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0612102},
    primaryClass={cs.DB}
}