Aggregate operators in probabilistic databases

ABSTRACT

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.

REFERENCES

• 1: Aitchison, J., and Dunsmore, I. R. 1975. Statistical Prediction Analysis. Cambridge University Press, Cambridge.
• 2: D. Barbará , H. Garcia-Molina , D. Porter, The Management of Probabilistic Data, IEEE Transactions on Knowledge and Data Engineering, v.4 n.5, p.487-502, October 1992 [doi>10.1109/69.166990]
• 3: A. F. Bobick , Y. A. Ivanov, Action Recognition Using Probabilistic Parsing, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.196, June 23-25, 1998
• 4: Roger Cavallo , Michael Pittarelli, The Theory of Probabilistic Databases, Proceedings of the 13th International Conference on Very Large Data Bases, p.71-81, September 01-04, 1987
• 5: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Evaluating probabilistic queries over imprecise data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872823]
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: Cramton, P. 1997. The FCC spectrum auctions: An early assessment. J. Econ. Manage. Strat. 6, 3, 431--495.
• 8: Alex Dekhtyar , Robert Ross , V. S. Subrahmanian, Probabilistic temporal databases, I: algebra, ACM Transactions on Database Systems (TODS), v.26 n.1, p.41-95, March 2001 [doi>10.1145/383734.383736]
• 9: Dekhtyar, A., and Subrahmanian, V. S. 1997. Hybrid probabilistic programs. In Proceedings of the 14th International Conference on Logic Program. MIT Press, Cambridge, Mass., 391--405.
• 10: Debabrata Dey , Sumit Sarkar, A probabilistic relational model and algebra, ACM Transactions on Database Systems (TODS), v.21 n.3, p.339-369, Sept. 1996 [doi>10.1145/232753.232796]
• 11: Curtis E. Dyreson , Richard Thomas Snodgrass, Supporting valid-time indeterminacy, ACM Transactions on Database Systems (TODS), v.23 n.1, p.1-57, March 1998 [doi>10.1145/288086.288087]
• 12: Thomas Eiter , Thomas Lukasiewicz , Michael Walter, Extension of the Relational Algebra to Probabilistic Complex Values, Proceedings of the First International Symposium on Foundations of Information and Knowledge Systems, p.94-115, February 14-17, 2000
• 13: R. Fagin , Joseph Y. Halpern , Nimrod Megiddo, A logic for reasoning about probabilities, Information and Computation, v.87 n.1-2, p.78-128, July/August 1990 [doi>10.1016/0890-5401(90)90060-U]
• 14: Melvin Fitting, Bilattices and the semantics of logic programming, Journal of Logic Programming, v.11 n.2, p.91-116, Aug. 1991 [doi>10.1016/0743-1066(91)90014-G]
• 15: Norbert Fuhr , Ulrich Pfeifer, Probabilistic information retrieval as a combination of abstraction, inductive learning, and probabilistic assumptions, ACM Transactions on Information Systems (TOIS), v.12 n.1, p.92-115, Jan. 1994 [doi>10.1145/174608.174612]
• 16: Fuhr, N., and Rolleke, T. 1996. A probabilistic NF2 relational algebra for integrated information retrieval and database systems. In Proceedings of the 2nd World Conference on Integrated Design and Process Technology. Society for Design and Process Science, Austin, Tex. 17--30.
• 17: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 18: Gee, J., Briquer, L., Barillot, C., and Haynor, D. 1995. Probabilistic matching of brain images. In Information Processing in Medical Imaging. Kluwer Academic Publishers, Dordrecht, 113--125.
• 19: Werner Kießling , Helmut Thöne , Ulrich Güntzer, Database Support for Problematic Knowledge, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.421-436, March 23-27, 1992
• 20: M. Kifer , A. Li, On the semantics of rule-based expert systems with uncertainty, Lecture notes in computer science on ICDT '88, p.102-117, October 1988, Bruges, Belgium
• 21: Henry F. Korth , Abraham Silberschatz, Database System Concepts, McGraw-Hill, Inc., New York, NY, 1990
• 22: Laks V. S. Lakshmanan , Nicola Leone , Robert Ross , V. S. Subrahmanian, ProbView: a flexible probabilistic database system, ACM Transactions on Database Systems (TODS), v.22 n.3, p.419-469, Sept. 1997 [doi>10.1145/261124.261131]
• 23: Laks V. S. Lakshmanan , Fereidoon Sadri, Modeling Uncertainty in Deductive Databases, Proceedings of the 5th International Conference on Database and Expert Systems Applications, p.724-733, September 07-09, 1994
• 24: Laks V. S. Lakshmanan , Fereidoon Sadri, Probabilistic deductive databases, Proceedings of the 1994 International Symposium on Logic programming, p.254-268, November 1994, Symposia, Melbourne
• 25: Laks V. S. Lakshmanan , Nematollaah Shiri, A Parametric Approach to Deductive Databases with Uncertainty, IEEE Transactions on Knowledge and Data Engineering, v.13 n.4, p.554-570, July 2001 [doi>10.1109/69.940732]
• 26: R. Mandelbaum , G. Kamberova , M. Mintz, Stereo Depth Estimation: A Confidence Interval Approach, Proceedings of the Sixth International Conference on Computer Vision, p.503, January 04-07, 1998
• 27: Raymond Ng , V. S. Subrahmanian, Probabilistic logic programming, Information and Computation, v.101 n.2, p.150-201, Dec. 1992 [doi>10.1016/0890-5401(92)90061-J]
• 28: Raymond Ng , V. S. Subrahmanian, Stable semantics for probabilistic deductive databases, Information and Computation, v.110 n.1, p.42-83, April 1994 [doi>10.1006/inco.1994.1023]
• 29: Oliver, N., Rosario, B., and Pentland, A. 1998. Statistical modeling of human interactions. In Proceedings of the Symposium on Computer Vision and Pattern Recognition (Santa Barbara, Calif.). IEEE Computer Society Press, Los Alamitos, Calif., 39--46.
• 30: Robert Ross , V. S. Subrahmanian , John Grant, Probabilistic Aggregates, Proceedings of the 13th International Symposium on Foundations of Intelligent Systems, p.553-564, June 27-29, 2002
• 31: Shiri, N. 1997. On a generalized theory of deductive databases. Ph.D. thesis, Concordia University, Montreal.
• 32: Street, W. N., Mangasarian, O. L., and Wolberg, W. H. 1995. An inductive learning approach to prognostic prediction. In Proceedings of the 12th International Conference on Machine Learning. Morgan Kaufmann, San Francisco, Calif. 522--530.
• 33: Subrahmanian, V. S. 1987. On the semantics of quantitative logic programs. In Proceedings of the 4th Symposium on Logic Programming (Washington, D.C.). IEEE Computer Society Press, Los Alamitos, Calif., 173--182.
• 34: Krishnaprasad Thirunarayan , Michael Kifer, A theory of nonmonotonic inheritance based on annotated logic, Artificial Intelligence, v.60 n.1, p.23-50, March 1993 [doi>10.1016/0004-3702(93)90033-8]
• 35: M H van Emden, Quantitative deduction and its fixpoint theory, Journal of Logic Programming, v.30 n.1, p.37-53, April 1986
• 36: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 37: Wolfram, C. D. 1998. Strategic bidding in a multi-unit auction: An empirical analysis of bids to supply electricity in England and Wales. RAND J. Econ. 29, 4, 703--773.
• 38: Kenji Yamanishi , Jun-ichi Takeuchi, Discovering outlier filtering rules from unlabeled data: combining a supervised learner with an unsupervised learner, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.389-394, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502570]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms, Performance, Theory

Keywords:
Aggregates, probabilistic relational databases