Aggregation in Probabilistic Databases
Robert Fink
Info
|
Date |
25th October 2011 (week 1, Michaelmas Term 2011) |
|
Time |
11:30 |
|
Place |
147 |
Abstract
In this talk I will present a query evaluation technique for positive
relational algebra queries with aggregates on a representation
system for probabilistic data based on the algebraic structures of
semirings, aggregation monoids, and semimodules. The evaluation
technique can compile arbitrary semimodule and semiring expressions
into so-called decomposition trees, for which the computation of the
probability distribution can be done in polynomial time in the size
of the tree and of the distribution. I will also give a
characterisation of tractable queries with aggregates by
exploiting the connection between query tractability and
polynomial-time compilation into decomposition trees.
The technique is incorporated into the probabilistic database engine
SPROUT, which is built on top of PostgreSQL. I will shortly report on
performance experiments with synthetic datasets, RFID and TPC-H
data.
Further info
|
Related series |
|
