MPI-I-2012-5-002
Top-k query processing in probabilistic databases with non-materialized views
Dylla, Maximilian and Miliaraki, Iris and Theobald, Martin
June 2012, 59 pages.
.
Status: available - back from printing
In this paper, we investigate a novel approach of computing confidence bounds
for top-k ranking queries in probabilistic databases with non-materialized views.
Unlike prior 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, where also the rules themselves may
be uncertain, i.e., be valid with some degree of confidence. To our knowledge,
this work is the first to address integrated data and confidence computations in the
context of probabilistic databases by considering confidence bounds over partially
evaluated query answers with first-order lineage formulas. We further extend our
query processing techniques by a tool-suite of scheduling strategies based on se-
lectivity estimation and the expected impact of subgoals on the final confidence
of answer candidates. Experiments with large datasets demonstrate drastic run-
time improvements over both sampling and decomposition-based methods—even
in the presence of recursive rules.
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2012-5-002
BibTeX
@TECHREPORT{DyllaMiliarakiTheobald2012,
AUTHOR = {Dylla, Maximilian and Miliaraki, Iris and Theobald, Martin},
TITLE = {Top-k query processing in probabilistic databases with non-materialized views},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-2012-5-002},
MONTH = {June},
YEAR = {2012},
ISSN = {0946-011X},
}