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.00012911894
- Overall Rank
- 1,269 | 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 |
| 770 |
Answering Conjunctive Queries under Updates |
2017 |
PODS |
0.0001686092 |
| 1,703 |
Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach |
2008 |
SIGMOD |
0.00010820803 |
| 2,733 |
Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities |
2009 |
SIGMOD |
8.2106718e-05 |
| 2,981 |
Matching Twigs in Probabilistic XML |
2007 |
VLDB |
7.7783189e-05 |
| 3,315 |
Computing Query Probability with Incidence Algebras |
2010 |
PODS |
7.2247513e-05 |
| 3,395 |
Event Queries on Correlated Probabilistic Streams |
2008 |
SIGMOD |
7.1402267e-05 |
| 4,328 |
Sliding-Window Top-k Queries on Uncertain Streams |
2008 |
VLDB |
6.2765138e-05 |
| 4,439 |
Approximating Predicates and Expressive Queries on Probabilistic Databases |
2008 |
PODS |
6.1806955e-05 |
| 4,522 |
A Temporal-Probabilistic Database Model for Information Extraction |
2013 |
VLDB |
6.1109228e-05 |
| 4,722 |
Read-Once Functions and Query Evaluation in Probabilistic Databases |
2010 |
VLDB |
5.9646931e-05 |
| 5,301 |
Running Tree Automata on Probabilistic XML |
2009 |
PODS |
5.5749031e-05 |
| 5,647 |
Circuit Treewidth, Sentential Decision, and Query Compilation |
2017 |
PODS |
5.3913624e-05 |
| 5,983 |
Understanding Cardinality Estimation using Entropy Maximization |
2010 |
PODS |
5.240797e-05 |
| 6,410 |
Queries with Difference on Probabilistic Databases |
2011 |
VLDB |
5.0682868e-05 |
| 6,682 |
Query Efficiency in Probabilistic XML Models |
2008 |
SIGMOD |
4.9596732e-05 |
| 6,800 |
A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases |
2014 |
PODS |
4.918071e-05 |
| 6,996 |
Tractable Lineages on Treelike Instances: Limits and Extensions |
2016 |
PODS |
4.8629707e-05 |
| 7,162 |
Probabilistic Query Evaluation: The Combined FPRAS Landscape |
2023 |
PODS |
4.8085863e-05 |
| 8,555 |
Incorporating Constraints in Probabilistic XML |
2008 |
PODS |
4.4893996e-05 |
| 10,389 |
FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds |
2025 |
SIGMOD |
4.1905499e-05 |
| 10,930 |
Complex Event Recognition meets Hierarchical Conjunctive Queries |
2024 |
PODS |
4.1905499e-05 |
| 11,182 |
Probabilistic Reasoning at Scale: Trigger Graphs to the Rescue |
2023 |
SIGMOD |
4.1905499e-05 |
| 12,137 |
Answering Queries using Views over Probabilistic XML: Complexity and Tractability |
2012 |
VLDB |
4.1905499e-05 |
| 12,221 |
Transducing Markov Sequences |
2010 |
PODS |
4.1905499e-05 |
| 12,364 |
Query Evaluation with Soft-Key Constraints |
2008 |
PODS |
4.1905499e-05 |
| 12,386 |
Query Answering Techniques on Uncertain and Probabilistic Data |
2008 |
SIGMOD |
4.1905499e-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