DBScholar

Back to papers

Approximating Predicates and Expressive Queries on Probabilistic Databases

Summary: Defines an expressive probabilistic-DB language with compositional confidence computation enabling conditional-probability queries and selections over marginal/conditional confidences. Characterizes complexity, gives approximation/error bounds, and an algorithm that efficiently approximates queries except at unavoidable singularities. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
h5214384a599c9121
Venue
PODS
Year
2008
Pagerank
6.7296503e-05
Overall Rank
4,213 | 71.68%
DOI
10.1145/1376916.1376932

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{koch_pods08,
        address = {New York, NY, USA},
        series = {{PODS} '08},
        title = {{Approximating Predicates and Expressive Queries on Probabilistic Databases}},
        url = {https://dl.acm.org/doi/10.1145/1376916.1376932},
        doi = {10.1145/1376916.1376932},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Koch, Christoph},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank Citing Paper Year Venue Pagerank
1,063 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB 0.00012208695
1,549 Conditioning Probabilistic Databases 2008 VLDB 0.00010288725
3,663 On Probabilistic Fixpoint and Markov Chain Query Languages 2010 PODS 7.1188602e-05
4,389 Read-Once Functions and Query Evaluation in Probabilistic Databases 2010 VLDB 6.6226901e-05
5,474 Running Tree Automata on Probabilistic XML 2009 PODS 6.1176063e-05
6,653 Queries with Difference on Probabilistic Databases 2011 VLDB 5.7196642e-05
7,427 Local Structure and Determinism in Probabilistic Databases 2012 SIGMOD 5.5304729e-05
12,699 Transducing Markov Sequences 2010 PODS 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
9 Online Aggregation 1997 SIGMOD 0.00076195956
51 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00042936299
84 ULDBs: Databases with Uncertainty and Lineage 2006 VLDB 0.00035963861
658 The Complexity of Query Reliability 1998 PODS 0.00015051203
696 MYSTIQ: A system for finding more answers by using probabilities 2005 SIGMOD 0.00014697176
1,065 The Dichotomy of Conjunctive Queries on Probabilistic Structures 2007 PODS 0.0001219981
1,090 Scalable Approximate Query Processing With The DBO Engine 2007 SIGMOD 0.00012077577
2,130 The reliability of queries (Extended Abstract) 1995 PODS 8.9957534e-05
2,543 From Complete to Incomplete Information and Back 2007 SIGMOD 8.3182354e-05
4,742 Query language support for incomplete information in the MayBMS system 2007 VLDB 6.4401895e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 8,643 Anytime Approximation in Probabilistic Databases via Scaled Dissociations 2019 SIGMOD
2 370 Evaluating Probabilistic Queries over Imprecise Data 2003 SIGMOD
3 6,653 Queries with Difference on Probabilistic Databases 2011 VLDB
4 8,426 Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds 2021 SIGMOD
5 4,176 Aggregation in Probabilistic Databases via Knowledge Compilation 2012 VLDB
6 1,549 Conditioning Probabilistic Databases 2008 VLDB
7 658 The Complexity of Query Reliability 1998 PODS
8 9,169 Efficient Approximations of Conjunctive Queries 2012 PODS
9 5,340 Approximate Lifted Inference with Probabilistic Databases 2015 VLDB
10 51 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB