Temporal coalescing with now granularity, and incomplete information

ABSTRACT

This paper presents a novel strategy for temporal coalescing. Temporal coalescing merges the temporal extents of value-equivalent tuples. A temporal extent is usually coalesced offline and stored since coalescing is an expensive operation. But the temporal extent of a tuple with now, times at different granularities, or incomplete times cannot be determined until query evaluation. This paper presents a strategy to partially coalesce temporal extents by identifying regions that are potentially covered. The covered regions can be used to evaluate temporal predicates and constructors on the coalesced extent. Our strategy uses standard relational database technology. We quantify the cost using the Oracle DBMS.

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: Toshiyuki Amagasa , Masatoshi Yoshikawa , Shunsuke Uemura, A Data Model for Temporal XML Documents, Proceedings of the 11th International Conference on Database and Expert Systems Applications, p.334-344, September 04-08, 2000
• 3: Claudio Bettini , Sushil G. Jajodia , Sean X. Wang, Time Granularities in Databases, Data Mining and Temporal Reasoning, Springer-Verlag New York, Inc., Secaucus, NJ, 2000
• 4: 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
• 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: Shu-Yao Chien , Vassilis J. Tsotras , Carlo Zaniolo , Donghui Zhang, Efficient Complex Query Support for Multiversion XML Documents, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.161-178, March 25-27, 2002
• 7: 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]
• 8: Nachum Dershowitz , Edward M. Reingold, Calendrical calculations, Cambridge University Press, New York, NY, 1997
• 9: C. E. Dyreson. A Bibliography on Uncertainty Management in Information Systems. In A. Motro, editor, Uncertainty Management in Information Systems: From Needs to Solutions, pages 415--458. Kluwer Academic Publishers, 1997.
• 10: Curtis E. Dyreson, Observing Transaction-Time Semantics with TTXPath, Proceedings of the Second International Conference on Web Information Systems Engineering (WISE'01) Volume 1, p.193, December 03-06, 2001
• 11: Curtis E. Dyreson , William S. Evans , Hong Lin , Richard Thomas Snodgrass, Efficiently Supporting Temporal Granularities, IEEE Transactions on Knowledge and Data Engineering, v.12 n.4, p.568-587, July 2000 [doi>10.1109/69.868908]
• 12: 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]
• 13: 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
• 14: Shashi K. Gadia , Chuen-Sing Yeung, A generalized model for a relational temporal database, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.251-259, June 01-03, 1988, Chicago, Illinois, United States
• 15: C. S. Jensen and C. E. Dyreson (editors). A Consensus Glossary of Temporal Database Concepts - February 1998 Version. In Temporal Databases: Research and Practice, Lecture Notes in Computer Science 1399, pages 367--405. Springer-Verlag, 1998. http://www.cs.auc.dk/~csj/Glossary/.
• 16: Manolis Koubarakis, Databases and Temporal Constraints: Semantics and Complexity, Proceedings of the International Workshop on Temporal Databases: Recent Advances in Temporal Databases, p.93-109, September 17-18, 1995
• 17: 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]
• 18: N. A. Lorentzos, DBMS Support for Nonmetric Measurement Systems, IEEE Transactions on Knowledge and Data Engineering, v.6 n.6, p.945-953, December 1994 [doi>10.1109/69.334884]
• 19: E. McKenzie. Bibliography: Temporal Databases. SIGMOD Record (ACM Special Interest Group on Management of Data), 15(4):40--52, December 1986.
• 20: Jim Melton , Alan R. Simon, Understanding the new SQL: a complete guide, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 21: Giedrius Slivinskas , Christian S. Jensen , Richard Thomas Snodgrass, Adaptable query optimization and evaluation in temporal middleware, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.127-138, May 21-24, 2001, Santa Barbara, California, United States
• 22: Richard Thomas Snodgrass, Developing time-oriented database applications in SQL, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 23: Richard Thomas Snodgrass, The TSQL2 Temporal Query Language, Kluwer Academic Publishers, Norwell, MA, 1995
• 24: M. D. Soo, C. S. Jensen, and R. T. Snodgrass. An Algebra for TSQL2, chapter 27, pages 505--546. Kluwer Academic Press, September 1995.
• 25: A. U. Tansel, Modelling temporal data, Information and Software Technology, v.32 n.8, p.514-520, Oct. 1990 [doi>10.1016/0950-5849(90)90141-D]
• 26: P. Terenziani and R. T. Snodgrass. Reconciling Point-based and Interval-based Semantics in Temporal Relational Databases: A Proper Treatment of the Telic/Atelic Distinction. Technical Report 60, TimeCenter, Aalborg, Denmark, June 2001.
• 27: V. J. Tsotras and A. Kumar. Temporal Database Bibliography Update. SIGMOD Record (ACM Special Interest Group on Management of Data), 25(1):41--63, March 1996.
• 28: X. Sean Wang , Claudio Bettini , Alexander Brodsky , Sushil Jajodia, Logical design for temporal databases with multiple granularities, ACM Transactions on Database Systems (TODS), v.22 n.2, p.115-170, June 1997 [doi>10.1145/249978.249979]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Data manipulation languages (DML)

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Keywords:
coalescing, granularity, incomplete information, now, temporal databases