Aggregate operators in probabilistic databases
Robert B. Ross, V. S. Subrahmanian, John Grant · Journal of the ACM · 2005
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.
Cited by 81 works. doi:10.1145/1044731.1044734
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Introduction to Algorithms
- Database System Concepts
- Statistical Prediction Analysis
- Strategic Bidding in a Multiunit Auction: An Empirical Analysis of Bids to Supply Electricity in England and Wales
- Evaluating probabilistic queries over imprecise data
- The management of probabilistic data
- A logic for reasoning about probabilities
- The FCC Spectrum Auctions: An Early Assessment
- ProbView