  This paper presents a query evaluation technique for positive relational
algebra queries with aggregates on a representation system for probabilistic
data based on the algebraic structures of semiring and semimodule. The core of
our evaluation technique is a procedure that compiles semimodule and semiring
expressions into so-called decomposition trees, for which the computation of
the probability distribution can be done in time linear in the product of the
sizes of the probability distributions represented by its nodes. We give
syntactic characterisations of tractable queries with aggregates by exploiting
the connection between query tractability and polynomial-time decomposition
trees. A prototype of the technique is incorporated in the probabilistic
database engine SPROUT. We report on performance experiments with custom
datasets and TPC-H data.
