The Dichotomy of Conjunctive Queries on Probabilistic Structures

Summary: Establishes a dichotomy for conjunctive queries on tuple‑independent probabilistic databases: each query's data complexity is either PTIME or #P‑complete, with no intermediate cases. Provides a decidable algorithm to classify any given conjunctive query. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h212050832e746658
Venue: PODS
Year: 2007
Pagerank: 0.0001219981
Overall Rank: 1,065 | 92.85%
DOI: 10.1145/1265530.1265571

Incoming Non-self Citations Over Time

Authors

1. Nilesh Dalvi (University of Washington)
2. Dan Suciu (University of Washington)

BibTeX Citation

@inproceedings{dalvi_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{The Dichotomy of Conjunctive Queries on Probabilistic Structures}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265571},
        doi = {10.1145/1265530.1265571},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Dalvi, Nilesh and Suciu, Dan},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
637	Answering Conjunctive Queries under Updates	2017	PODS	0.00015341557
1,396	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.0001079253
2,860	Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities	2009	SIGMOD	7.9338024e-05
3,109	Event Queries on Correlated Probabilistic Streams	2008	SIGMOD	7.6387635e-05
3,132	Matching Twigs in Probabilistic XML	2007	VLDB	7.6137556e-05
3,291	Computing Query Probability with Incidence Algebras	2010	PODS	7.4519264e-05
3,326	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	7.4227632e-05
4,213	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.7296503e-05
4,389	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	6.6226901e-05
4,655	A Temporal-Probabilistic Database Model for Information Extraction	2013	VLDB	6.4849316e-05
5,474	Running Tree Automata on Probabilistic XML	2009	PODS	6.1176063e-05
5,973	Understanding Cardinality Estimation using Entropy Maximization	2010	PODS	5.9306716e-05
6,653	Queries with Difference on Probabilistic Databases	2011	VLDB	5.7196642e-05
6,847	Circuit Treewidth, Sentential Decision, and Query Compilation	2017	PODS	5.666154e-05
6,982	A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases	2014	PODS	5.6287253e-05
7,057	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.6113229e-05
7,466	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS	5.5199634e-05
7,794	Tractable Lineages on Treelike Instances: Limits and Extensions	2016	PODS	5.451528e-05
8,886	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	5.2559789e-05
8,923	Incorporating Constraints in Probabilistic XML	2008	PODS	5.2559789e-05
9,363	Complex Event Recognition meets Hierarchical Conjunctive Queries	2024	PODS	5.1868213e-05
11,700	Probabilistic Reasoning at Scale: Trigger Graphs to the Rescue	2023	SIGMOD	4.9793485e-05
12,616	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB	4.9793485e-05
12,699	Transducing Markov Sequences	2010	PODS	4.9793485e-05
12,839	Query Evaluation with Soft-Key Constraints	2008	PODS	4.9793485e-05
12,861	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00042936299
126	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.00030439683
587	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00015933201
658	The Complexity of Query Reliability	1998	PODS	0.00015051203
696	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00014697176

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,262	Maximally Joining Probabilistic Data	2007	PODS
2	5,340	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB
3	5,965	A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join	2024	PODS
4	13,419	Complexity of Query Processing in Databases with OR-Objects	1989	PODS
5	8,009	A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries	2021	PODS
6	3,870	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS
7	7,466	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS
8	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
9	7,858	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS
10	6,982	A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases	2014	PODS