  Existence of incomplete and imprecise data has moved the database paradigm
from deterministic to proba- babilistic information. Probabilistic databases
contain tuples that may or may not exist with some probability. As a result,
the number of possible deterministic database instances that can be observed
from a probabilistic database grows exponentially with the number of
probabilistic tuples. In this paper, we consider the problem of answering both
aggregate and non-aggregate queries on massive probabilistic databases. We
adopt the tuple independence model, in which each tuple is assigned a
probability value. We develop a method that exploits Probability Generating
Functions (PGF) to answer such queries efficiently. Our method maintains a
polynomial for each tuple. It incrementally builds a master polynomial that
expresses the distribution of the possible result values precisely. We also
develop an approximation method that finds the distribution of the result value
with negligible errors. Our experiments suggest that our methods are orders of
magnitude faster than the most recent systems that answer such queries,
including MayBMS and SPROUT. In our experiments, we were able to scale up to
several terabytes of data on TPC- H queries, while existing methods could only
run for a few gigabytes of data on the same queries.
