TY - JOUR
T1 - Aggregate operators in probabilistic databases
JF - J. ACM
Y1 - 2005
A1 - Ross,Robert
A1 - V.S. Subrahmanian
A1 - Grant,John
KW - Aggregates
KW - probabilistic relational databases
AB - Though extensions to the relational data model have been proposed in order to handle probabilistic information, there has been very little work to date on handling aggregate operators in such databases. In this article, we present a very general notion of an aggregate operator and show how classical aggregation operators (such as COUNT, SUM, etc.) as well as statistical operators (such as percentiles, variance, etc.) are special cases of this general definition. We devise a formal linear programming based semantics for computing aggregates over probabilistic DBMSs, develop algorithms that satisfy this semantics, analyze their complexity, and introduce several families of approximation algorithms that run in polynomial time. We implemented all of these algorithms and tested them on a large set of data to help determine when each one is preferable.
VL - 52
SN - 0004-5411
UR - http://doi.acm.org/10.1145/1044731.1044734
CP - 1
M3 - 10.1145/1044731.1044734
ER -