Back to papers
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
- 1439
- Venue
- PODS
- Year
- 2007
- Pagerank
- 0.00012931993
- Overall Rank
- 1,268 | 91.19%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 26 of 26 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 772 |
Answering Conjunctive Queries under Updates |
2017 |
PODS |
0.00016876498 |
| 1,707 |
Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach |
2008 |
SIGMOD |
0.00010816111 |
| 2,728 |
Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities |
2009 |
SIGMOD |
8.2185032e-05 |
| 2,978 |
Matching Twigs in Probabilistic XML |
2007 |
VLDB |
7.7845728e-05 |
| 3,314 |
Computing Query Probability with Incidence Algebras |
2010 |
PODS |
7.2318581e-05 |
| 3,398 |
Event Queries on Correlated Probabilistic Streams |
2008 |
SIGMOD |
7.141911e-05 |
| 4,080 |
Sliding-Window Top-k Queries on Uncertain Streams |
2008 |
VLDB |
6.4652983e-05 |
| 4,442 |
Approximating Predicates and Expressive Queries on Probabilistic Databases |
2008 |
PODS |
6.186154e-05 |
| 4,521 |
A Temporal-Probabilistic Database Model for Information Extraction |
2013 |
VLDB |
6.1168322e-05 |
| 4,720 |
Read-Once Functions and Query Evaluation in Probabilistic Databases |
2010 |
VLDB |
5.973811e-05 |
| 5,296 |
Running Tree Automata on Probabilistic XML |
2009 |
PODS |
5.5802694e-05 |
| 5,638 |
Circuit Treewidth, Sentential Decision, and Query Compilation |
2017 |
PODS |
5.3965476e-05 |
| 5,977 |
Understanding Cardinality Estimation using Entropy Maximization |
2010 |
PODS |
5.2455909e-05 |
| 6,415 |
Queries with Difference on Probabilistic Databases |
2011 |
VLDB |
5.0731258e-05 |
| 6,681 |
Query Efficiency in Probabilistic XML Models |
2008 |
SIGMOD |
4.9643102e-05 |
| 6,804 |
A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases |
2014 |
PODS |
4.9224361e-05 |
| 6,997 |
Tractable Lineages on Treelike Instances: Limits and Extensions |
2016 |
PODS |
4.8676446e-05 |
| 7,163 |
Probabilistic Query Evaluation: The Combined FPRAS Landscape |
2023 |
PODS |
4.8132033e-05 |
| 8,558 |
Incorporating Constraints in Probabilistic XML |
2008 |
PODS |
4.4937074e-05 |
| 10,377 |
FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds |
2025 |
SIGMOD |
4.1945683e-05 |
| 10,926 |
Complex Event Recognition meets Hierarchical Conjunctive Queries |
2024 |
PODS |
4.1945683e-05 |
| 11,179 |
Probabilistic Reasoning at Scale: Trigger Graphs to the Rescue |
2023 |
SIGMOD |
4.1945683e-05 |
| 12,129 |
Answering Queries using Views over Probabilistic XML: Complexity and Tractability |
2012 |
VLDB |
4.1945683e-05 |
| 12,213 |
Transducing Markov Sequences |
2010 |
PODS |
4.1945683e-05 |
| 12,356 |
Query Evaluation with Soft-Key Constraints |
2008 |
PODS |
4.1945683e-05 |
| 12,378 |
Query Answering Techniques on Uncertain and Probabilistic Data |
2008 |
SIGMOD |
4.1945683e-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.
Semantically Similar Papers