Supporting valid-time indeterminacy

ABSTRACT

In valid-time indeterminacy it is known that an event stored in a database did in fact occur, but it is not known exactly when. In this paper we extend the SQL data model and query language to support valid-time indeterminacy. We represent the occurrence time of an event with a set of possible instants, delimiting when the event might have occurred, and a probability distribution over that set. We also describe query language constructs to retrieve information in the presence of indeterminacy. These constructs enable users to specify their credibility in the underlying data and their plausibility in the relationships among that data. A denotational semantics for SQL's select statement with optional credibility and plausibility constructs is given. We show that this semantics is reliable, in that it never produces incorrect information, is maximal, in that if it were extended to be more informative, the results may not be reliable, and reduces to the previous semantics when there is no indeterminacy. Although the extended data model and query language provide needed modeling capabilities, these extensions appear initially to carry a significant execution cost. A contribution of this paper is to demonstrate that our approach is useful and practical. An efficient representation of valid-time indeterminacy and efficient query processing algorithms are provided. The cost of support for indeterminacy is empirically measured, and is shown to be modest. Finally, we show that the approach is general, by applying it to the temporal query language constructs being proposed for SQL3.

REFERENCES

• 1: James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 [doi>10.1145/182.358434]
• 2: Gad Ariav, A temporally oriented data model, ACM Transactions on Database Systems (TODS), v.11 n.4, p.499-527, Dec. 1986 [doi>10.1145/7239.7350]
• 3: BAIR, J., JENSEN, C. S., SNODGRASS, R. T., AND BOEHLEN, M. 1997. Notions of upward compatibility of temporal query languages. Bus. Inform. 39, 1 (Feb.), 25-34.
• 4: Daniel Barbara , Hector Garcia-Molina , Daryl Porter, A probabilistic relational data model, Proceedings of the international conference on extending database technology on Advances in database technology, p.60-74, March 1990, Venice, Italy
• 5: 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]
• 6: BELNAP, N. 1977. A useful four-valued logic. In Modern Uses of Many-valued Logic. G. Epstein and J. M. Dunn, Eds. D. Reidel Publishing Co., Inc., New York, NY., 8-37.
• 7: Michael H. Böhlen , Richard Thomas Snodgrass , Michael D. Soo, Coalescing in Temporal Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.180-191, September 03-06, 1996
• 8: 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
• 9: 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
• 10: James Clifford , Curtis Dyreson , Tomás Isakowitz , Christian S. Jensen , Richard Thomas Snodgrass, On the semantics of “now” in databases, ACM Transactions on Database Systems (TODS), v.22 n.2, p.171-214, June 1997 [doi>10.1145/249978.249980]
• 11: CLIFFORD, J. AND RAO, A. 1987. A simple, general structure for temporal domains. In Proceedings of the Conference on Temporal Aspects in Information Systems. Association Francaise pour la Cybernetique Economique et Technique, Montreuil, France, 23-30.
• 12: CODD, E. F. 1990. Missing Information. Addison-Wesley Publishing Co., Inc., Redwood City, CA.
• 13: DATE, C.J. 1986. Null Values in Database Management. Addison-Wesley Publishing Co., Reading, MA.
• 14: T. Dean , M. Boddy, Reasoning about partially ordered events, Artificial Intelligence, v.36 n.3, p.375-399, October 1988 [doi>10.1016/0004-3702(88)90087-2]
• 15: David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider, An Evaluation of Non-Equijoin Algorithms, Proceedings of the 17th International Conference on Very Large Data Bases, p.443-452, September 03-06, 1991
• 16: 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]
• 17: DUBOIS, D. AND PRADE, H. 1989. Processing fuzzy temporal knowledge. IEEE Trans. Syst. Man Cybern. 19, 4, 729-744.
• 18: DUBOIS, D., PRADE, H., AND TESTAMALE, C. 1988. Handling Incomplete or Uncertain Data and Vague Queries in Database Applications. Plenum Press, New York, NY.
• 19: Soumitra Dutta, Generalized Events In Temporal Databases, Proceedings of the Fifth International Conference on Data Engineering, p.118-125, February 06-10, 1989
• 20: Curtis Elliott Dyreson, Valid-time indeterminacy, University of Arizona, Tucson, AZ, 1994
• 21: DYRESON, C.E. 1997. A bibliography on uncertainty management in information systems. In Uncertainty Management in Information Systems: From Needs to Solutions, A. Motro, Ed. Kluwer Academic Publishers, Hingham, MA., 415-458.
• 22: Curtis E. Dyreson , Richard Thomas Snodgrass, Valid-time Indeterminancy, Proceedings of the Ninth International Conference on Data Engineering, p.335-343, April 19-23, 1993
• 23: DYRESON, C. E. AND SNODGRASS, R.T. 1995a. A timestamp representation. In The TSQL2 Temporal Query Language, R. T. Snodgrass, Ed. Kluwer Academic Publishers, Hingham, MA., 475-499.
• 24: DYRESON, C. E. AND SNODGRASS, R. 1995b. Temporal indeterminacy. In The TSQL2 Ternporal Query Language. R. T. Snodgrass, Ed. Kluwer Academic Publishers, Hingham, MA, 327-346.
• 25: DYRESON, C. E., Soo, M., AND SNODGRASS, R.T. 1995. The Data Model for Time. In The TSQL2 Temporal Query Language. R. T. Snodgrass, Ed. Kluwer Academic Publishers, Hingham, MA.
• 26: Norbert Fuhr, A probabilistic framework for vague queries and imprecise information in databases, Proceedings of the sixteenth international conference on Very large databases, p.696-707, September 1990, Brisbane, Australia
• 27: 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]
• 28: 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
• 29: Erol Gelenbe , Georges Hebrail, A Probability Model of Uncertainty in Data Bases, Proceedings of the Second International Conference on Data Engineering, p.328-333, February 05-07, 1986
• 30: GOUDSMIT, S. AND CLAIRBORNE, R. 1966. Time. Times Books, New York, NY.
• 31: HERION, M. AND SUERMONDT, g. 1993. Probabilistic and Bayesian representations of uncertainty and information systems: A pragmatic introduction. In Proceedings of the Workshop on Uncertainty Management in Information Systems: From Needs to Solutions (Avalon, Santa Catalina, CA, April 1993), 71-90.
• 32: JENSEN, C. S., AND DYRESON, C. E., EDS. 1998. A consensus glossary of temporal database concepts, February 1998 version. In Temporal Databases--Research and Practice, O. Etzion, S. Jajodia, and S. Sripada, Eds. Springer-Verlag, Berlin, Germany, 367-405.
• 33: KORNATZKY, Y. AND SHIMONY, S. 1993a. A probabilistic object-oriented data model. Tech Rep. FC 93-04. Ben-Gurion University, Negev, Israel.
• 34: Yoram Kornatzky , Solomon Eyal Shimony, A Probabilistic Spatial Data Model, Proceedings of the 4th International Conference on Database and Expert Systems Applications, p.337-348, September 06-08, 1993
• 35: Manolis Koubarakis, Representation and Querying in Temporal Databases: the Power of Temporal Constraints, Proceedings of the Ninth International Conference on Data Engineering, p.327-334, April 19-23, 1993
• 36: KOURAMAJIAN, V. AND ELMASRI, R. 1992. A generalized temporal model. Tech. Rep. University of Texas at Arlington, Arlington, TX.
• 37: KRAUS, S. AND SUBRAHMANIAN, V.S. 1994. Multiagent reasoning with probability, time and beliefs. Int. J. Intell. Syst. 10, 5, 459-499.
• 38: 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]
• 39: Suk Kyoon Lee, An Extended Relational Database Model for Uncertain and Imprecise Information, Proceedings of the 18th International Conference on Very Large Data Bases, p.211-220, August 23-27, 1992
• 40: LEUNG, T. Y. AND MUNTZ, R. 1991. Temporal query processing and optimization in multiprocessor database machines. Tech. Rep. CSD-910077. University of California at Los Angeles, Los Angeles, CA.
• 41: Witold Lipski, Jr., On semantic issues connected with incomplete information databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.262-296, Sept. 1979 [doi>10.1145/320083.320088]
• 42: Ken-Chih Liu , Rajshekhar Sunderraman, Indefinite and maybe information in relational databases, ACM Transactions on Database Systems (TODS), v.15 n.1, p.1-39, March 1990 [doi>10.1145/77643.77644]
• 43: MELTON, J. 1996. SQL/Temporal. Tech. Rep. ISO/IEC JTC 1/SC 21/WG 3/DBL-MCI-012.
• 44: Jim Melton , Alan R. Simon, Understanding the new SQL: a complete guide, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 45: A. Motro, Imprecision and incompleteness in relational databases: survey, Information and Software Technology, v.32 n.9, p.579-588, Nov. 1990 [doi>10.1016/0950-5849(90)90204-5]
• 46: Adegbemiga Ola, Relational Databases with Exclusive Disjunctions, Proceedings of the Eighth International Conference on Data Engineering, p.328-336, February 03-07, 1992
• 47: Simon Parsons, Current Approaches to Handling Imperfect Information in Data and Knowledge Bases, IEEE Transactions on Knowledge and Data Engineering, v.8 n.3, p.353-372, June 1996 [doi>10.1109/69.506705]
• 48: PELTEY, B. W. 1991. Time and frequency in fundamental metrology. Proc. IEEE 79, 9 (July), 1070-1077.
• 49: PRADE, H. 1993. Annotated bibliography on fuzzy information processing. In Readings on Fuzzy Sets in Intelligent Systems, H. Prade, D. Dubois, and R. Yager, Eds. Morgan Kaufmann Publishers Inc., San Francisco, CA.
• 50: SCHIEL, U. 1987. Representation and retrieval of incomplete and temporal information. Tech. Rep. DSC-02/87. Universidade Federal Da Paraiba, Paraiba, Brazil.
• 51: Richard Thomas Snodgrass, Monitoring distributed systems: a relational approach, 1982
• 52: SNODGRASS, R. T., B HLEN, M. H., JENSEN, C. S., AND KLINE, N. 1996. Adding valid time to SQL/Temporal. Tech. Rep. Change Proposal ANSI X3H2-96-501r2, ISO/IEC JTC1/SC21/ WG3 DBL MAD-146r2.
• 53: Richard Thomas Snodgrass, The TSQL2 Temporal Query Language, Kluwer Academic Publishers, Norwell, MA, 1995
• 54: Soo, M. D., SNODGRASS, R., DYRESON, C., JENSEN, C. S., AND KLINE, N. 1992. Architectural extensions to support multiple calendars. Tech. Rep. 32. University of Arizona, Tucson, AZ.
• 55: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• 56: Abdullah Uz Tansel , James Clifford , Shashi Gadia , Sushil Jajodia , Arie Segev , Richard Snodgrass, Temporal databases: theory, design, and implementation, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1993
• 57: Frank S. C. Tseng , Arbee L. P. Chen , Wei-Pang Yang, Answering heterogeneous database queries with degrees of uncertainty, Distributed and Parallel Databases, v.1 n.3, p.281-302, July 1993 [doi>10.1007/BF01263334]
• 58: VAN BEEK, P. 1991. Temporal query processing with indefinite information. Art. Intell. Med. 3, 6 (Dec.), 325-339.
• 59: VASANTHAKUMAR, S. R., COLLAN, J. P., AND CROFT, W.B. 1996. Integrating INQUIRY with an RDBMS to support text retrieval. IEEE Data Engineering 19, 1, 24-33.
• 60: Yannis Vassiliou, Null values in data base management a denotational semantics approach, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582123]
• 61: VITEK, M. 1983. Fuzzy information and fuzzy time. In Proceedings of the IFAC Symposium on Fuzzy Information, Knowledge Representation and Decision Analysis (Marseille, France, 1983), 159-162.
• 62: Eugene Wong, A statistical approach to incomplete information in database systems, ACM Transactions on Database Systems (TODS), v.7 n.3, p.470-488, Sept. 1982 [doi>10.1145/319732.319747]
• 63: ZANIOLO, C. 1984. Database relations with null values. J. Comput. Syst. Sci. 28, 142-166.
• 64: Maria Zemankova , Abraham Kandel, Implementing imprecision in information systems, Information Sciences: an International Journal, v.37 n.1-3, p.107-141, Dec. 1985 [doi>10.1016/0020-0255(85)90008-8]
• 65: ZIM NYI, E. 1992. Incomplete and uncertain information in relational databases. Ph.D. dissertation. Editions de l'Universite de Bruxelles, Brussels, Belgium.

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: Query processing

General Terms:
Algorithms, Languages

Keywords:
SQL, TSQL2, incomplete information, indeterminacy, probabilistic information, temporal dtabase, valid-time database