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
9384
Venue
VLDB
Year
2004
Pagerank
0.00043596705
Overall Rank
50 | 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 48 of 98 citing papers.

Rank Citing Paper Year Venue Pagerank
4,431 Database Principles in Information Extraction 2014 PODS 6.7088601e-05
4,698 Rethinking Data Management for Storage-centric Sensor Networks 2007 CIDR 6.5569539e-05
4,935 Querying Probabilistic Information Extraction 2010 VLDB 6.4357418e-05
5,030 Learning-Based Cleansing for Indoor RFID Data 2016 SIGMOD 6.3954412e-05
5,318 Cleaning Uncertain Data with Quality Guarantees 2008 VLDB 6.2672687e-05
5,346 Running Tree Automata on Probabilistic XML 2009 PODS 6.257995e-05
5,450 Indexing Correlated Probabilistic Databases 2009 SIGMOD 6.2142725e-05
5,513 Foundations of Uncertain-Data Integration 2010 VLDB 6.1909879e-05
5,565 Efficient Allocation Algorithms for OLAP over Imprecise Data 2006 VLDB 6.171506e-05
5,657 When is Shapley Value Computation a Matter of Counting? 2024 PODS 6.1313425e-05
5,695 Incrementally Maintaining Classification using an RDBMS 2011 VLDB 6.1183313e-05
5,764 Indexing Uncertain Data 2009 PODS 6.0955299e-05
6,120 Finding Frequent Items in Probabilistic Data 2008 SIGMOD 5.9693818e-05
6,527 Queries with Difference on Probabilistic Databases 2011 VLDB 5.8509088e-05
6,712 Capturing Data Uncertainty in High-Volume Stream Processing 2009 CIDR 5.7962014e-05
6,741 Probabilistic Databases for All 2020 PODS 5.7866368e-05
6,839 A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases 2014 PODS 5.7576811e-05
6,863 Explore or Exploit? Effective Strategies for Disambiguating Large Databases 2010 VLDB 5.7514261e-05
6,913 Evaluation of Probabilistic Threshold Queries in MCDB 2010 SIGMOD 5.7405e-05
6,917 Query Efficiency in Probabilistic XML Models 2008 SIGMOD 5.7400564e-05
7,225 HINT: A Hierarchical Index for Intervals in Main Memory 2022 SIGMOD 5.6673083e-05
7,306 Local Structure and Determinism in Probabilistic Databases 2012 SIGMOD 5.6499367e-05
7,317 Probabilistic Query Evaluation: The Combined FPRAS Landscape 2023 PODS 5.6466593e-05
7,588 Spheres of Influence for More Effective Viral Marketing 2016 SIGMOD 5.5907856e-05
8,032 Lineage Processing over Correlated Probabilistic Databases 2010 SIGMOD 5.5041098e-05
8,059 Probabilistic Histograms for Probabilistic Data 2009 VLDB 5.4979799e-05
8,222 From Statistical Knowledge Bases to Degrees of Belief: An Overview 2006 PODS 5.4636099e-05
8,585 Probabilistic Management of OCR Data using an RDBMS 2012 VLDB 5.4075213e-05
8,597 Beta Probabilistic Databases: A Scalable Approach to Belief Updating and Parameter Learning 2017 SIGMOD 5.4049137e-05
8,599 Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries 2024 PODS 5.4049137e-05
8,743 A Query Engine for Probabilistic Preferences 2018 SIGMOD 5.3766157e-05
8,745 Querying Probabilistic Preferences in Databases 2017 PODS 5.3766157e-05
8,761 Incorporating Constraints in Probabilistic XML 2008 PODS 5.3766157e-05
9,044 Threshold Query Optimization for Uncertain Data 2010 SIGMOD 5.3253644e-05
9,086 Privacy Preservation by Disassociation 2012 VLDB 5.3251649e-05
9,355 Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates 2015 SIGMOD 5.282937e-05
9,936 A*-tree: A Structure for Storage and Modeling of Uncertain Multidimensional Arrays 2010 VLDB 5.1955087e-05
10,183 Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries 2026 PODS 5.093636e-05
10,776 Relevance Queries for Interval Data 2025 SIGMOD 5.093636e-05
11,109 FaDE: More Than a Million What-ifs Per Second 2025 VLDB 5.093636e-05
11,837 Query Evaluation in Election Databases 2019 PODS 5.093636e-05
12,408 Transducing Markov Sequences 2010 PODS 5.093636e-05
12,417 GRN Model of Probabilistic Databases: Construction, Transition and Querying 2010 SIGMOD 5.093636e-05
12,549 Query Evaluation with Soft-Key Constraints 2008 PODS 5.093636e-05
12,571 Query Answering Techniques on Uncertain and Probabilistic Data 2008 SIGMOD 5.093636e-05
12,600 Systems Aspects of Probabilistic Data Management 2008 VLDB 5.093636e-05
12,611 Querying Web-Based Applications Under Models of Uncertainty 2008 VLDB 5.093636e-05
12,673 Suppression and Failures in Sensor Networks: A Bayesian Approach 2007 VLDB 5.093636e-05
Previous Page 2 / 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.0010828372
37 DISCOVER: Keyword Search in Relational Databases 2002 VLDB 0.00048017193
77 XRANK: Ranked Keyword Search over XML Documents 2003 SIGMOD 0.00037048607
160 Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity 1998 SIGMOD 0.0002802209
466 Automated Ranking of Database Query Results 2003 CIDR 0.00018014467
557 The Theory of Probabilistic Databases 1987 VLDB 0.00016541752
644 The Complexity of Query Reliability 1998 PODS 0.00015367965
1,518 The XXL Search Engine: Ranked Retrieval of XML Data using Indexes and Ontologies 2002 SIGMOD 0.00010517242
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 644 The Complexity of Query Reliability 1998 PODS
2 359 Evaluating Probabilistic Queries over Imprecise Data 2003 SIGMOD
3 9,353 On Efficient Approximate Queries over Machine Learning Models 2023 VLDB
4 4,098 Aggregation in Probabilistic Databases via Knowledge Compilation 2012 VLDB
5 2,149 Probabilistic Optimization of Top N Queries 1999 VLDB
6 7,317 Probabilistic Query Evaluation: The Combined FPRAS Landscape 2023 PODS
7 4,301 Read-Once Functions and Query Evaluation in Probabilistic Databases 2010 VLDB
8 4,136 Approximating Predicates and Expressive Queries on Probabilistic Databases 2008 PODS
9 1,844 Probabilistic Ranking of Database Query Results 2004 VLDB
10 5,225 Approximate Lifted Inference with Probabilistic Databases 2015 VLDB