The Dichotomy of Conjunctive Queries on Probabilistic Structures

2006/12/20 by Nilesh Dalvi, Dan Suciu, Dalvi, Nilesh +1
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences #Semantic Web and Ontologies

paper · pdf · doi:10.48550/arxiv.cs/0612102

openalex publication_date 2006/12/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 a given conjunctive query is \PTIME or #¶-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.

Citations

• The Complexity of Enumeration and Reliability Problems

Related

• Probabilistic Query Evaluation with Bag Semantics
• A Trichotomy in the Data Complexity of Certain Query Answering for\n Conjunctive Queries
• Lower Bounds for Conjunctive Query Evaluation
• Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum
• Approximate Lifted Inference with Probabilistic Databases