DBScholar

Back to papers

Efficient Query Evaluation on Probabilistic Databases

Summary: Efficient evaluation of complex SQL on probabilistic databases with rank-based results. Proposes an optimization algorithm that handles most queries; notes some are #P-complete, and offers approximation and Monte-Carlo methods for intractable cases. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h2c061c1e1f3aa132
Venue
VLDB
Year
2004
Pagerank
0.00042936299
Overall Rank
51 | 99.66%
DOI
10.1016/B978-012088469-8.50076-0

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{dalvi_vldb04,
        title = {{Efficient Query Evaluation on Probabilistic Databases}},
        author = {Dalvi, Nilesh and Suciu, Dan},
        journal = {PVLDB},
        series = {{VLDB} '04},
        doi = {10.1016/B978-012088469-8.50076-0},
        url = {https://doi.org/10.1016/B978-012088469-8.50076-0},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 99 citing papers.

Rank Citing Paper Year Venue Pagerank
17 Provenance Semirings 2007 PODS 0.00059752575
84 ULDBs: Databases with Uncertainty and Lineage 2006 VLDB 0.00035963861
126 Trio: A System for Integrated Management of Data, Accuracy, and Lineage 2005 CIDR 0.00030439683
417 MauveDB: Supporting Model-based User Views in Database Systems 2006 SIGMOD 0.00018631353
587 Management of Probabilistic Data: Foundations and Challenges 2007 PODS 0.00015933201
595 ConQuer: Efficient Management of Inconsistent Databases 2005 SIGMOD 0.00015798582
690 Creating Probabilistic Databases from Information Extraction Models 2006 VLDB 0.00014745444
696 MYSTIQ: A system for finding more answers by using probabilities 2005 SIGMOD 0.00014697176
841 BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models 2008 VLDB 0.00013541445
1,062 Tuffy: Scaling up Statistical Inference in Markov Logic Networks using an RDBMS 2011 VLDB 0.0001221201
1,063 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB 0.00012208695
1,065 The Dichotomy of Conjunctive Queries on Probabilistic Structures 2007 PODS 0.0001219981
1,114 Principles of Dataspace Systems 2006 PODS 0.00011964697
1,124 Probabilistic Skylines on Uncertain Data 2007 VLDB 0.00011927351
1,361 Computing Optimal Repairs for Functional Dependencies 2018 PODS 0.00010917917
1,365 A Unified Approach to Ranking in Probabilistic Databases 2009 VLDB 0.00010913898
1,396 Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach 2008 SIGMOD 0.0001079253
1,518 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.00010396565
1,615 Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases 2011 SIGMOD 0.00010067073
1,760 Structured Querying of Web Text: A Technical Challenge 2007 CIDR 9.7106555e-05
1,785 Approximate Lineage for Probabilistic Databases 2008 VLDB 9.6482655e-05
1,827 Querying Data Provenance 2010 SIGMOD 9.5545888e-05
1,917 A Web of Concepts 2009 PODS 9.3790758e-05
2,018 Scalable Probabilistic Databases with Factor Graphs and MCMC 2010 VLDB 9.1750812e-05
2,296 Attacks on Privacy and deFinetti's Theorem 2009 SIGMOD 8.6789249e-05
2,502 Exploiting Shared Correlations in Probabilistic Databases 2008 VLDB 8.3800737e-05
2,543 From Complete to Incomplete Information and Back 2007 SIGMOD 8.3182354e-05
2,598 Complaint-driven Training Data Debugging for Query 2.0 2020 SIGMOD 8.2385793e-05
2,718 Answering Queries from Statistics and Probabilistic Views 2005 VLDB 8.0978764e-05
2,722 The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries 2020 PODS 8.0955983e-05
2,738 Sketching Probabilistic Data Streams 2007 SIGMOD 8.07308e-05
2,984 Materialized Views in Probabilistic Databases: For Information Exchange and Query Optimization 2007 VLDB 7.7830089e-05
3,038 Estimating Statistical Aggregates on Probabilistic Data Streams 2007 PODS 7.7270848e-05
3,088 Learning to Create Data-Integrating Queries 2008 VLDB 7.6596008e-05
3,105 Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers 2009 SIGMOD 7.6445188e-05
3,109 Event Queries on Correlated Probabilistic Streams 2008 SIGMOD 7.6387635e-05
3,132 Matching Twigs in Probabilistic XML 2007 VLDB 7.6137556e-05
3,291 Computing Query Probability with Incidence Algebras 2010 PODS 7.4519264e-05
3,326 Sliding-Window Top-k Queries on Uncertain Streams 2008 VLDB 7.4227632e-05
3,378 On the Complexity of Managing Probabilistic XML Data 2007 PODS 7.3569859e-05
3,542 Consensus Answers for Queries over Probabilistic Databases 2009 PODS 7.2155312e-05
3,694 OLAP over Imprecise Data with Domain Constraints 2007 VLDB 7.0927742e-05
3,769 Optimizing MPF Queries: Decision Support and Probabilistic Inference 2007 SIGMOD 7.0301573e-05
3,820 The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs 2014 SIGMOD 7.005206e-05
4,002 From Shapley Value to Model Counting and Back 2024 PODS 6.8607198e-05
4,057 Uncertainty Management in Rule-Based Information Extraction Systems 2009 SIGMOD 6.8257248e-05
4,143 Hybrid In-Database Inference for Declarative Information Extraction 2011 SIGMOD 6.7813891e-05
4,196 Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance 2010 VLDB 6.7421052e-05
4,213 Approximating Predicates and Expressive Queries on Probabilistic Databases 2008 PODS 6.7296503e-05
4,262 Maximally Joining Probabilistic Data 2007 PODS 6.6984258e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank Cited Paper Year Venue Pagerank
5 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0010679641
38 DISCOVER: Keyword Search in Relational Databases 2002 VLDB 0.00047394041
81 XRANK: Ranked Keyword Search over XML Documents 2003 SIGMOD 0.00036346781
162 Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity 1998 SIGMOD 0.00027536748
474 Automated Ranking of Database Query Results 2003 CIDR 0.00017672562
571 The Theory of Probabilistic Databases 1987 VLDB 0.00016210743
658 The Complexity of Query Reliability 1998 PODS 0.00015051203
1,543 The XXL Search Engine: Ranked Retrieval of XML Data using Indexes and Ontologies 2002 SIGMOD 0.00010306756
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 658 The Complexity of Query Reliability 1998 PODS
2 370 Evaluating Probabilistic Queries over Imprecise Data 2003 SIGMOD
3 5,911 On Efficient Approximate Queries over Machine Learning Models 2023 VLDB
4 4,176 Aggregation in Probabilistic Databases via Knowledge Compilation 2012 VLDB
5 2,181 Probabilistic Optimization of Top N Queries 1999 VLDB
6 7,466 Probabilistic Query Evaluation: The Combined FPRAS Landscape 2023 PODS
7 4,389 Read-Once Functions and Query Evaluation in Probabilistic Databases 2010 VLDB
8 4,213 Approximating Predicates and Expressive Queries on Probabilistic Databases 2008 PODS
9 1,886 Probabilistic Ranking of Database Query Results 2004 VLDB
10 5,340 Approximate Lifted Inference with Probabilistic Databases 2015 VLDB