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
1449
Venue
PODS
Year
2008
Pagerank
6.8810237e-05
Overall Rank
4,136 | 71.63%
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,049 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB 0.00012415522
1,520 Conditioning Probabilistic Databases 2008 VLDB 0.00010510496
3,590 On Probabilistic Fixpoint and Markov Chain Query Languages 2010 PODS 7.2801454e-05
4,301 Read-Once Functions and Query Evaluation in Probabilistic Databases 2010 VLDB 6.7737212e-05
5,346 Running Tree Automata on Probabilistic XML 2009 PODS 6.257995e-05
6,527 Queries with Difference on Probabilistic Databases 2011 VLDB 5.8509088e-05
7,306 Local Structure and Determinism in Probabilistic Databases 2012 SIGMOD 5.6499367e-05
12,408 Transducing Markov Sequences 2010 PODS 5.093636e-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.00077458002
50 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00043596705
78 ULDBs: Databases with Uncertainty and Lineage 2006 VLDB 0.00036571789
644 The Complexity of Query Reliability 1998 PODS 0.00015367965
683 MYSTIQ: A system for finding more answers by using probabilities 2005 SIGMOD 0.00015005338
1,041 The Dichotomy of Conjunctive Queries on Probabilistic Structures 2007 PODS 0.00012453494
1,064 Scalable Approximate Query Processing With The DBO Engine 2007 SIGMOD 0.00012336248
2,088 The reliability of queries (Extended Abstract) 1995 PODS 9.1913486e-05
2,514 From Complete to Incomplete Information and Back 2007 SIGMOD 8.4818577e-05
4,653 Query language support for incomplete information in the MayBMS system 2007 VLDB 6.5850987e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 8,476 Anytime Approximation in Probabilistic Databases via Scaled Dissociations 2019 SIGMOD
2 359 Evaluating Probabilistic Queries over Imprecise Data 2003 SIGMOD
3 6,527 Queries with Difference on Probabilistic Databases 2011 VLDB
4 8,260 Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds 2021 SIGMOD
5 4,098 Aggregation in Probabilistic Databases via Knowledge Compilation 2012 VLDB
6 1,520 Conditioning Probabilistic Databases 2008 VLDB
7 644 The Complexity of Query Reliability 1998 PODS
8 9,009 Efficient Approximations of Conjunctive Queries 2012 PODS
9 5,225 Approximate Lifted Inference with Probabilistic Databases 2015 VLDB
10 50 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB