Back to papers
The Complexity of Query Reliability
Summary: Demonstrates that computing query reliability over tuple-independent probabilistic databases jumps from PTIME for quantifier-free queries to FP#P-complete already for some conjunctive queries, and that FP#P characterizes reliability for broad classes (incl. all SO queries). Provides randomized approximation algorithms for all polynomial-time-evaluable queries and extends FP#P hardness to metafinite databases with interpreted functions and SQL-style aggregates (first-order queries included).
(summarized by gpt-5-mini on Feb 09 2026)
- Paper ID
- 1155
- Venue
- PODS
- Year
- 1998
- Pagerank
- 0.00019910719
- Overall Rank
- 571 | 96.03%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 19 of 19 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 74 |
Efficient Query Evaluation on Probabilistic Databases |
2004 |
VLDB |
0.00057857292 |
| 627 |
Management of Probabilistic Data: Foundations and Challenges |
2007 |
PODS |
0.00018959005 |
| 1,268 |
The Dichotomy of Conjunctive Queries on Probabilistic Structures |
2007 |
PODS |
0.00012931993 |
| 1,730 |
Conditioning Probabilistic Databases |
2008 |
VLDB |
0.00010736755 |
| 1,970 |
Approximate Lineage for Probabilistic Databases |
2008 |
VLDB |
9.896375e-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 |
| 4,442 |
Approximating Predicates and Expressive Queries on Probabilistic Databases |
2008 |
PODS |
6.186154e-05 |
| 5,296 |
Running Tree Automata on Probabilistic XML |
2009 |
PODS |
5.5802694e-05 |
| 5,537 |
Cleaning Uncertain Data with Quality Guarantees |
2008 |
VLDB |
5.4522327e-05 |
| 5,638 |
Circuit Treewidth, Sentential Decision, and Query Compilation |
2017 |
PODS |
5.3965476e-05 |
| 6,284 |
Probabilistic XML via Markov Chains |
2010 |
VLDB |
5.128131e-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 |
| 7,163 |
Probabilistic Query Evaluation: The Combined FPRAS Landscape |
2023 |
PODS |
4.8132033e-05 |
| 10,010 |
Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries |
2026 |
PODS |
4.1945683e-05 |
| 10,377 |
FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds |
2025 |
SIGMOD |
4.1945683e-05 |
| 12,222 |
GRN Model of Probabilistic Databases: Construction, Transition and Querying |
2010 |
SIGMOD |
4.1945683e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 1 of 1 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Semantically Similar Papers