Aggregation in Probabilistic Databases via Knowledge Compilation

Details Aggregation in Probabilistic Databases via Knowledge Compilation Aggregation in Probabilistic Databases via Knowledge Compilation

2012-01-31

arxiv.org/abs/1201.6569v1

Proceedings of the VLDB Endowment (PVLDB), Vol. 5, No. 5, pp. 490-501 (2012)

Computer Science

Databases

VLDB2012

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Aggregation in Probabilistic Databases via Knowledge Compilation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Aggregation in Probabilistic Databases via Knowledge Compilation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Aggregation in Probabilistic Databases via Knowledge Compilation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-57208