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 -