Probabilistic temporal databases, I: algebra

ABSTRACT

Dyreson and Snodgrass have drawn attention to the fact that, in many temporal database applications, there is often uncertainty about the start time of events, the end time of events, and the duration of events. When the granularity of time is small (e.g., milliseconds), a statement such as “Packet p was shipped sometime during the first 5 days of January, 1998” leads to a massive amount of uncertainty (5×24×60×60×1000) possibilities. As noted in Zaniolo et al. [1997], past attempts to deal with uncertainty in databases have been restricted to relatively small amounts of uncertainty in attributes. Dyreson and Snodgrass have taken an important first step towards solving this problem. In this article, we first introduce the syntax of Temporal-Probabilistic (TP) relations and then show how they can be converted to an explicit, significantly more space-consuming form, called Annotated Relations. We then present a theoretical annotated temporal algebra (TATA). Being explicit, TATA is convenient for specifying how the algebraic operations should behave, but is impractical to use because annotated relations are overwhelmingly large. Next, we present a temporal probabilistic algebra (TPA). We show that our definition of the TP-algebra provides a correct implementation of TATA despite the fact that it operates on implicit, succinct TP-relations instead of overwhemingly large annotated relations. Finally, we report on timings for an implementation of the TP-Algebra built on top of ODBC.

REFERENCES

• 1: James F. Allen, Towards a general theory of action and time, Artificial Intelligence, v.23 n.2, p.123-154, July 1984 [doi>10.1016/0004-3702(84)90008-0]
• 2: J. F. Baldwin, Evidential support logic programming, Fuzzy Sets and Systems, v.24 n.1, p.1-26, Oct. 1987 [doi>10.1016/0165-0114(87)90110-2]
• 3: 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]
• 4: BOOLE, G. 1854. The Laws of Thought, Macmillan, London.
• 5: Vittorio Brusoni , Luca Console , Paolo Terenziani , Barbara Pernici, Extending Temporal Relational Databases to Deal with Imprecise and Qualitative Temporal Information, Proceedings of the International Workshop on Temporal Databases: Recent Advances in Temporal Databases, p.3-22, September 17-18, 1995
• 6: 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
• 7: DEKHTYAR, A., ROSS, R., AND SUBRAHMANIAN, V. S. 2001. Probabilistic temporal databases, Indexes, query optimization and updates, in preparation.
• 8: DEKHTYAR, A., AND SUBRAHMANIAN, V. S. 1997. Hybrid probabilistic logic programs, In Proceedings of the 1997 International Conference on Logic Programming, L. Naish, Ed., MIT Press.
• 9: DEKHTYAR, A., ROSS, R., AND SUBRAHMANIAN, V. S. 1998. Probabilistic temporal databases. Tech. Rep. CS-TR-3987, University of Maryland. http://www.cs.umd.edu:80/Dienst/UI/2.0/ Describe/ncstrl.umcp/CS-TR-3987?abstract=Dekhtyar.
• 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: DUBOIS,D.,AND PRADE, H. 1988. Certainty and uncertainty of vague knowledge and generalized dependencies in fuzzy databases. In Proceedings of the International Fuzzy Engineering Symposium, (Yokohama, Japan), 239-249.
• 13: DUBOIS,D.,AND PRADE, H. 1989. Processing Fuzzy Temporal Knowledge, IEEE Trans. Syst. Man Cybern. 19, 4, 729-744.
• 14: DUDA,R.O.,HART,P.E.,AND NILSSON, N. J. 1976. Subjective bayesian methods for rule-based inference systems, In Proceedings of the National Computer Conference, 1075-1082.
• 15: Soumitra Dutta, Generalized Events In Temporal Databases, Proceedings of the Fifth International Conference on Data Engineering, p.118-125, February 06-10, 1989
• 16: 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]
• 17: Shashi K. Gadia , Sunil S. Nair , Yiu-Cheong Poon, Incomplete Information in Relational Temporal Databases, Proceedings of the 18th International Conference on Very Large Data Bases, p.395-406, August 23-27, 1992
• 18: 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
• 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: Henry F. Korth , Abraham Silberschatz, Database system concepts, McGraw-Hill, Inc., New York, NY, 1986
• 21: Manolis Koubarakis, Database models for infinite and indefinite temporal information, Information Systems, v.19 n.2, p.141-173, March 1994 [doi>10.1016/0306-4379(94)90008-6]
• 22: Sarit Kraus , Yehoshua Sagiv , V. S. Subrahmanian, Representing and integrating multiple calendars, University of Maryland at College Park, College Park, MD, 1997
• 23: 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]
• 24: 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
• 25: 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
• 26: 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]
• 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: NG, R., AND SUBRAHMANIAN, V. S. 1993. A semantical framework for supporting subjective and conditional probabilities in deductive databases, J. Autom. Reasoning, 10, 2, 191-235.
• 29: 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]
• 30: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 31: SCHMIDT, H., KIESSLING, W., GUNTZER,U.,AND BAYER, R. 1987. Combining deduction by uncertainty with the power of magic. In Proceedings of the DOOD-89, (Kyoto, Japan), 205-224.
• 32: SHIRI, N. 1997. On a generalized theory of deductive databases, Ph.D. dissertation, Concordia University, Montreal, Canada, Aug.
• 33: SHOENFIELD, J. 1967. Mathematical Logic, Addison Wesley.
• 34: Richard Thomas Snodgrass, Monitoring distributed systems: a relational approach, 1982
• 35: SNODGRASS, R. T. 1996. Personal communication to V.S. Subrahmanian.
• 36: SUBRAHMANIAN, V. S. 1987. On the semantics of quantitative logic programs, In Proceedings of the 4th IEEE Symposium on Logic Programming, Computer Society Press, 173-182.
• 37: SUBRAHMANIAN, V. S. 1988. Generalized triangular norm and co-norm based semantics for quantitative rule set logic programming, Logic Programming Research Group Tech. Rep. LPRG-TR- 88-22, Syracuse University.
• 38: V. S. Subrahmanian, Principles of multimedia database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 39: THONE, H., KIESSLING,W.,AND GUNTZER, U. 1995. On cautious probabilistic inference and default detachment, Ann. Oper. Res. 55, 195-224.
• 40: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 41: Carlo Zaniolo , Stefano Ceri , Christos Faloutsos , Richard Thomas Snodgrass , V. S. Subrahmanian , Roberto Zicari, Advanced database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Temporal logic

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning

General Terms:
Theory