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: 1438
Venue: PODS
Year: 2007
Pagerank: 0.00012453494
Overall Rank: 1,041 | 92.86%
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
636	Answering Conjunctive Queries under Updates	2017	PODS	0.0001551856
1,363	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00011025316
2,831	Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities	2009	SIGMOD	8.0788784e-05
3,050	Event Queries on Correlated Probabilistic Streams	2008	SIGMOD	7.8140428e-05
3,075	Matching Twigs in Probabilistic XML	2007	VLDB	7.7839831e-05
3,229	Computing Query Probability with Incidence Algebras	2010	PODS	7.6209731e-05
3,599	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	7.2710351e-05
4,136	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.8810237e-05
4,301	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	6.7737212e-05
4,556	A Temporal-Probabilistic Database Model for Information Extraction	2013	VLDB	6.6335067e-05
5,346	Running Tree Automata on Probabilistic XML	2009	PODS	6.257995e-05
5,860	Understanding Cardinality Estimation using Entropy Maximization	2010	PODS	6.0636893e-05
6,527	Queries with Difference on Probabilistic Databases	2011	VLDB	5.8509088e-05
6,713	Circuit Treewidth, Sentential Decision, and Query Compilation	2017	PODS	5.7961371e-05
6,839	A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases	2014	PODS	5.7576811e-05
6,917	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.7400564e-05
7,317	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS	5.6466593e-05
7,640	Tractable Lineages on Treelike Instances: Limits and Extensions	2016	PODS	5.5766474e-05
8,724	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	5.3766157e-05
8,761	Incorporating Constraints in Probabilistic XML	2008	PODS	5.3766157e-05
9,184	Complex Event Recognition meets Hierarchical Conjunctive Queries	2024	PODS	5.3058708e-05
11,385	Probabilistic Reasoning at Scale: Trigger Graphs to the Rescue	2023	SIGMOD	5.093636e-05
12,325	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB	5.093636e-05
12,408	Transducing Markov Sequences	2010	PODS	5.093636e-05
12,549	Query Evaluation with Soft-Key Constraints	2008	PODS	5.093636e-05
12,571	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD	5.093636e-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
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
125	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.00030932014
574	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00016278855
644	The Complexity of Query Reliability	1998	PODS	0.00015367965
683	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00015005338

Semantically Similar Papers

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