[Date Prev][Date Next][Date Index]

Vortragsankündigung Dan Olteanu: "Scalable Query Processing in Probabilistic Databases with SPROUT"

Der Arbeitsbereich Datenbanken & AI des Instituts für Informationssysteme
lädt zum folgenden Vortrag ein:


Dan Olteanu:  http://www.comlab.ox.ac.uk/people/dan.olteanu/

DATUM: Freitag, 25. September 2009
ZEIT:  10:00 Uhr s.t.
ORT:   Seminarraum 184/2, Stiege 3, 3.Stock, Favoritenstr. 9-11

TITLE: Scalable Query Processing in Probabilistic Databases with SPROUT

In this talk I will address the problem of query evaluation on
probabilistic databases and present the SPROUT query engine, which is
under development at Oxford. SPROUT is publicly available as an
extension of the PostgreSQL 8.3.3 query engine. It is specifically
tailored to tractable conjunctive queries with inequalities and to
queries that are not tractable in general but become tractable on
probabilistic databases restricted by functional dependencies.

The major components of SPROUT are an aggregation operator for exact
confidence computation, which can be naturally integrated into
existing relational query plans, and optimizations that allow to push
the aggregation operator or parts thereof past joins. The operator is
based on a fundamental connection between tractable queries and
linear-size Ordered Binary Decision Diagrams (OBDDs) representing the
uncertainty in the answers to such queries.

I will then discuss the secondary-storage algorithm for the
aggregation operator. This algorithm can compute the probability of
OBDDs for tractable queries without materializing them, with main
memory requirements only dependent on the query size, and in a few
scans over the data. Experiments with GBs of TPC-H data show orders of
magnitude improvements of SPROUT over competing exact and approximate

Mit Unterstützung des Wolfgang-Pauli-Instituts und des Zentrums für