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.7264836e-05
Overall Rank
4,215 | 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,064 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB 0.00012202916
1,548 Conditioning Probabilistic Databases 2008 VLDB 0.00010288842
3,664 On Probabilistic Fixpoint and Markov Chain Query Languages 2010 PODS 7.115538e-05
4,390 Read-Once Functions and Query Evaluation in Probabilistic Databases 2010 VLDB 6.6197307e-05
5,478 Running Tree Automata on Probabilistic XML 2009 PODS 6.1147103e-05
6,657 Queries with Difference on Probabilistic Databases 2011 VLDB 5.7169618e-05
7,431 Local Structure and Determinism in Probabilistic Databases 2012 SIGMOD 5.528036e-05
12,705 Transducing Markov Sequences 2010 PODS 4.9769913e-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.00076265429
51 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00042926566
84 ULDBs: Databases with Uncertainty and Lineage 2006 VLDB 0.00035960573
660 The Complexity of Query Reliability 1998 PODS 0.00015045167
696 MYSTIQ: A system for finding more answers by using probabilities 2005 SIGMOD 0.00014691377
1,066 The Dichotomy of Conjunctive Queries on Probabilistic Structures 2007 PODS 0.00012194105
1,090 Scalable Approximate Query Processing With The DBO Engine 2007 SIGMOD 0.00012074369
2,133 The reliability of queries (Extended Abstract) 1995 PODS 8.9917097e-05
2,543 From Complete to Incomplete Information and Back 2007 SIGMOD 8.3143504e-05
4,744 Query language support for incomplete information in the MayBMS system 2007 VLDB 6.4376285e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 8,650 Anytime Approximation in Probabilistic Databases via Scaled Dissociations 2019 SIGMOD
2 370 Evaluating Probabilistic Queries over Imprecise Data 2003 SIGMOD
3 6,657 Queries with Difference on Probabilistic Databases 2011 VLDB
4 8,435 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,548 Conditioning Probabilistic Databases 2008 VLDB
7 660 The Complexity of Query Reliability 1998 PODS
8 9,177 Efficient Approximations of Conjunctive Queries 2012 PODS
9 5,342 Approximate Lifted Inference with Probabilistic Databases 2015 VLDB
10 51 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB