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.7043637e-05
Overall Rank
4,232 | 71.64%
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,069 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB 0.00012164865
1,551 Conditioning Probabilistic Databases 2008 VLDB 0.00010257014
3,671 On Probabilistic Fixpoint and Markov Chain Query Languages 2010 PODS 7.0929546e-05
4,413 Read-Once Functions and Query Evaluation in Probabilistic Databases 2010 VLDB 6.5979584e-05
5,495 Running Tree Automata on Probabilistic XML 2009 PODS 6.0944915e-05
6,668 Queries with Difference on Probabilistic Databases 2011 VLDB 5.6980608e-05
7,452 Local Structure and Determinism in Probabilistic Databases 2012 SIGMOD 5.510368e-05
12,748 Transducing Markov Sequences 2010 PODS 4.9605343e-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.00076079812
51 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00042804864
85 ULDBs: Databases with Uncertainty and Lineage 2006 VLDB 0.00035848027
661 The Complexity of Query Reliability 1998 PODS 0.00014996933
699 MYSTIQ: A system for finding more answers by using probabilities 2005 SIGMOD 0.00014645232
1,071 The Dichotomy of Conjunctive Queries on Probabilistic Structures 2007 PODS 0.00012154243
1,095 Scalable Approximate Query Processing With The DBO Engine 2007 SIGMOD 0.00012036913
2,145 The reliability of queries (Extended Abstract) 1995 PODS 8.9623192e-05
2,549 From Complete to Incomplete Information and Back 2007 SIGMOD 8.2889756e-05
4,764 Query language support for incomplete information in the MayBMS system 2007 VLDB 6.4169513e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 8,669 Anytime Approximation in Probabilistic Databases via Scaled Dissociations 2019 SIGMOD
2 371 Evaluating Probabilistic Queries over Imprecise Data 2003 SIGMOD
3 6,668 Queries with Difference on Probabilistic Databases 2011 VLDB
4 8,451 Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds 2021 SIGMOD
5 4,196 Aggregation in Probabilistic Databases via Knowledge Compilation 2012 VLDB
6 1,551 Conditioning Probabilistic Databases 2008 VLDB
7 661 The Complexity of Query Reliability 1998 PODS
8 9,205 Efficient Approximations of Conjunctive Queries 2012 PODS
9 5,351 Approximate Lifted Inference with Probabilistic Databases 2015 VLDB
10 51 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB