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.00019888988
- Overall Rank
- 572 | 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.00057797415 |
| 630 |
Management of Probabilistic Data: Foundations and Challenges |
2007 |
PODS |
0.00018942778 |
| 1,269 |
The Dichotomy of Conjunctive Queries on Probabilistic Structures |
2007 |
PODS |
0.00012911894 |
| 1,730 |
Conditioning Probabilistic Databases |
2008 |
VLDB |
0.00010726683 |
| 1,972 |
Approximate Lineage for Probabilistic Databases |
2008 |
VLDB |
9.8937766e-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 |
| 4,439 |
Approximating Predicates and Expressive Queries on Probabilistic Databases |
2008 |
PODS |
6.1806955e-05 |
| 5,301 |
Running Tree Automata on Probabilistic XML |
2009 |
PODS |
5.5749031e-05 |
| 5,545 |
Cleaning Uncertain Data with Quality Guarantees |
2008 |
VLDB |
5.447418e-05 |
| 5,647 |
Circuit Treewidth, Sentential Decision, and Query Compilation |
2017 |
PODS |
5.3913624e-05 |
| 6,284 |
Probabilistic XML via Markov Chains |
2010 |
VLDB |
5.1232186e-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 |
| 7,162 |
Probabilistic Query Evaluation: The Combined FPRAS Landscape |
2023 |
PODS |
4.8085863e-05 |
| 10,010 |
Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries |
2026 |
PODS |
4.1905499e-05 |
| 10,389 |
FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds |
2025 |
SIGMOD |
4.1905499e-05 |
| 12,230 |
GRN Model of Probabilistic Databases: Construction, Transition and Querying |
2010 |
SIGMOD |
4.1905499e-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