Probabilistic object bases

ABSTRACT

Although there are many applications where an object-oriented data model is a good way of representing and querying data, current object database systems are unable to handle objects whose attributes are uncertain. In this article, we extend previous work by Kornatzky and Shimony to develop an algebra to handle object bases with uncertainty. We propose concepts of consistency for such object bases, together with an NP-completeness result, and classes of probabilistic object bases for which consistency is polynomially checkable. In addition, as certain operations involve conjunctions and disjunctions of events, and as the probability of conjunctive and disjunctive events depends both on the probabilities of the primitive events involved as well as on what is known (if anything) about the relationship between the events, we show how all our algebraic operations may be performed under arbitrary probabilistic conjunction and disjunction strategies. We also develop a host of equivalence results in our algebra, which may be used as rewrite rules for query optimization. Last but not least, we have developed a prototype probabilistic object base server on top of ObjectStore. We describe experiments to assess the efficiency of different possible rewrite rules.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: ATKINSON, M., DEWITT, D., MAIER, D., BANCILHON, F., DITTRICH, K., AND ZDONIK, S. 1989. The objectoriented database system manifesto. In Proceedings of DOOD-89, Elsevier Science, Amsterdam, the Netherlands, 40-57.
• 3: François Bancilhon , Claude Delobel , Paris Kanellakis, Building an object-oriented database system: the story of 02, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 4: 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]
• 5: Elisa Bertino , Lorenzo Martino, Object-Oriented Database Systems: Concepts and Architectures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
• 6: BOOLE, G. 1854. The Laws of Thought. Macmillan, London.
• 7: 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
• 8: DEKHTYAR,A.AND SUBRAHMANIAN, V. S. 1997. Hybrid probabilistic programs. In Proceedings of the Fourteenth International Conference on Logic Programming (ICLP '97 ), MIT Press, Cambridge, Mass., 391-405.
• 9: 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]
• 10: Debabrata Dey , Sumit Sarkar, PSQL: a query language for probabilistic relational data, Data & Knowledge Engineering, v.28 n.1, p.107-120, Oct. 30, 1998 [doi>10.1016/S0169-023X(98)00015-9]
• 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: EITER, T., LU,J.J.,LUKASIEWICZ,T.,AND SUBRAHMANIAN, V. S. 1999. Probabilistic object bases. Tech. Rep. INFSYS RR-1843-99-11, Institut f~r Informationssysteme, Technische Universit~t Wien.
• 13: EITER, T., LUKASIEWICZ,T.,AND WALTER, M. 2000a. A data model and algebra for probabilistic complex values. Tech. Rep. INFSYS RR-1843-00-04, Institut f~ur Informationssysteme, Technische Universit~t Wien.
• 14: 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
• 15: 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]
• 16: FUHR,N.AND R~LLEKE, T. 1996. A probabilistic NF2 relational algebra for integrated information retrieval and database systems. In Proceedings of the Second World Conference on Integrated Design and Process Technology, Society for Design and Process Science, 17-30.
• 17: Norbert Fuhr , Thomas Rölleke, A probabilistic relational algebra for the integration of information retrieval and database systems, ACM Transactions on Information Systems (TOIS), v.15 n.1, p.32-66, Jan. 1997 [doi>10.1145/239041.239045]
• 18: 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
• 19: GRAEFE, G. 1995. The cascades framework for query optimization. Data Eng. Bull. 18, 3, 19-29.
• 20: William I. Grosky , Ramesh Jain , Rajiv Mehrotra, The handbook of multimedia information management, Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• 21: U. Güntzer , W. Kießling , H. Thöne, New direction for uncertainty reasoning in deductive databases, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.178-187, May 29-31, 1991, Denver, Colorado, United States
• 22: HADDAWY, P. 1994. Generating Bayesian networks from probability logic knowledge bases. In Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence (UAI-94), Morgan Kaufmann, Los Altos, Calif., 262-269.
• 23: Joseph Y. Halpern, An analysis of first-order logics of probability, Artificial Intelligence, v.46 n.3, p.311-350, Dec. 1990 [doi>10.1016/0004-3702(90)90019-V]
• 24: 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
• 25: 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
• 26: Won Kim, Introduction to object-oriented databases, MIT Press, Cambridge, MA, 1991
• 27: KOLLER,D.AND PFEFFER, A. 1997. Object-oriented Bayesian networks. In Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence (UAI-97), Morgan Kaufmann, Los Altos, Calif., 302-313.
• 28: Yoram Kornatzky , Solomon Eyal Shimony, A probabilistic object-oriented data model, Data & Knowledge Engineering, v.12 n.2, p.143-166, March 1994 [doi>10.1016/0169-023X(94)90012-4]
• 29: KYBURG,JR., H. E. AND PITTARELLI, M. 1996. Set-based Bayesianism. IEEE Trans. Syst. Man Cybern. A: Syst. Humans 26, 3, 324-339.
• 30: 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
• 31: 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
• 32: Laks V. S. Lakshmanan , Nematollaah Shiri, A Parametric Approach to Deductive Databases with Uncertainty, Proceedings of the International Workshop on Logic in Databases, p.61-81, July 01-02, 1996
• 33: 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]
• 34: LASKEY,K.B.AND MAHONEY, S. M. 1997. Network fragments: Representing knowledge for constructing probabilistic models. In Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence (UAI-97), Morgan-Kaufmann, Los Altos, Calif., 334-341.
• 35: M. Pittarelli, An Algebra for Probabilistic Databases, IEEE Transactions on Knowledge and Data Engineering, v.6 n.2, p.293-303, April 1994 [doi>10.1109/69.277772]
• 36: Fereidoon Sadri, Modeling Uncertainty in Object-Oriented Databases, Proceedings of the SOFTEKS Workshop on Incompleteness and Uncertainty in Information Systems, p.56-68, October 08-09, 1993
• 37: Gail M. Shaw , Stanley B. Zdonik, A Query Algebra for Object-Oriented Databases, Proceedings of the Sixth International Conference on Data Engineering, p.154-162, February 05-09, 1990

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages
      H.2.4 Systems
          Subjects: Object-oriented databases

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

General Terms:
Algorithms, Languages, Performance, Theory

Keywords:
Consistency, object-oriented database, probabilistic object algebra, probabilistic object base, probability, query language, query optimization