Affordable Access

Aggregation in Probabilistic Databases via Knowledge Compilation

Authors
  • Fink, Robert
  • Han, Larisa
  • Olteanu, Dan
Type
Published Article
Publication Date
Jan 31, 2012
Submission Date
Jan 31, 2012
Identifiers
arXiv ID: 1201.6569
Source
arXiv
License
Yellow
External links

Abstract

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.

Report this publication

Statistics

Seen <100 times