Top-k query processing in probabilistic databases with non-materialized views
Authors:
- 1 April 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 122-133
Abstract
We investigate a novel approach of computing confidence bounds for top-k ranking queries in probabilistic databases with non-materialized views. Unlike related approaches, we present an exact pruning algorithm for finding the top-ranked query answers according to their marginal probabilities without the need to first materialize all answer candidates via the views. Specifically, we consider conjunctive queries over multiple levels of select-project-join views, the latter of which are cast into Datalog rules which we ground in a top-down fashion directly at query processing time. To our knowledge, this work is the first to address integrated data and confidence computations for intensional query evaluations in the context of probabilistic databases by considering confidence bounds over first-order lineage formulas. We extend our query processing techniques by a tool-suite of scheduling strategies based on selectivity estimation and the expected impact on confidence bounds. Further extensions to our query processing strategies include improved top-k bounds in the case when sorted relations are available as input, as well as the consideration of recursive rules. Experiments with large datasets demonstrate significant runtime improvements of our approach compared to both exact and sampling-based top-k methods over probabilistic data.Keywords
This publication has 32 references indexed in Scilit:
- Probabilistic databases with MarkoViewsProceedings of the VLDB Endowment, 2012
- Threshold query optimization for uncertain data2010
- SPROUT: Lazy vs. Eager Query Plans for Tuple-Independent Probabilistic DatabasesInternational Conference on Data Engineering, 2009
- Orion 2.02008
- Fast and Simple Relational Processing of Uncertain Data2008
- Exploiting Lineage for Confidence Computation in Uncertain and Probabilistic Databases2008
- Provenance in databases2007
- Markov logic networksMachine Learning, 2006
- Probabilistic Datalog---a logic for powerful retrieval methods1995
- On the representation and querying of sets of possible worldsTheoretical Computer Science, 1991