This talk addresses the problem of query evaluation for tuple
independent probabilistic databases and conjunctive queries.
In the first part of the talk I show how this query evaluation problem
can be approached as a construction problem for ordered binary
decision diagrams (OBDDs): Given a query and a probabilistic
database, we construct in polynomial time an OBDD such that the
confidences of the answer tuples can be computed linearly in the size
of that OBDD. This approach is applicable to a large class of queries,
including the hierarchical queries, i.e., the Boolean conjunctive
queries without self-joins that admit PTIME evaluation on any
tuple-independent probabilistic database, hierarchical queries
extended with inequalities, and non-hierarchical queries on restricted
databases.
In the second part of the talk I will present an efficient
secondary-storage operator for exact confidence computation of
hierarchical queries on tuple-independent probabilistic
databases. This operator is based on the OBDD construction procedure
discussed in the first part of the talk, and uses structural properties
of the query and functional dependencies that hold on the database to decide on the number of scans of the answer tuples necessary to compute the confidences.
A case study on the TPC-H benchmark reveals that most TPC-H queries
obtained by removing aggregations admit efficient evaluation using our
operator. Experimental evaluation on probabilistic TPC-H data shows
substantial efficiency improvements when compared to the state of the
art. This operator is part of an open-source query engine for probabilistic databases called Merlin, which is under development at Oxford. Merlin is currently used in MayBMS, a general-purpose database management system for uncertain and probabilistic data.
This talk includes joint work with Jiewen Huang of Oxford.
