Semantic assumptions and query evaluation in temporal databases

ABSTRACT

When querying a temporal database, a user often makes certain semantic assumptions on stored temporal data. This paper formalizes and studies two types of semantic assumptions: point-based and interval-based. The point-based assumptions include those assumptions that use interpolation methods, while the interval-based assumptions include those that involve different temporal types (time granularities). Each assumption is viewed as a way to derive certain implicit data from the explicit data stored in the database. The database system must use all explicit as well as (possibly infinite) implicit data to answer user queries. This paper introduces a new method to facilitate such query evaluations. A user query is translated into a system query such that the answer of this system query over the explicit data is the same as that of the user query over the explicit and the implicit data. The paper gives such a translation procedure and studies the properties (safety in particular) of user queries and system queries.

REFERENCES

• AKPT91: J. F. Allen, H. Kautz, R. Pelavin, and . Tenenberg. Reasoning about Plans. Morgan-Kaufman, 1991.
• BWBJ95: C. Bettini, X. Wang, E. Bertino, and S. J ajodia. Introducing assumptions in temporal databases. Manuscript, 1995. GMU.
• CCT94: James Clifford , Albert Croker , Alexander Tuzhilin, On completeness of historical relational query languages, ACM Transactions on Database Systems (TODS), v.19 n.1, p.64-116, March 1994 [doi>10.1145/174638.174642]
• Cho92: Jan Chomicki, History-less Checking of Dynamic Integrity Constraints, Proceedings of the Eighth International Conference on Data Engineering, p.557-564, February 03-07, 1992
• CI94: James Clifford , Tomás Isakowitz, On the semantics of (bi)temporal variable databases, Proceedings of the 4th international conference on extending database technology on Advances in database technology, p.215-230, May 1994, Cambridge, United Kingdom
• CT85: James Clifford , Abdullah Uz Tansel, On an algebra for historical relational databases: two views, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.247-265, May 1985, Austin, Texas, United States
• CW83: James Clifford , David S. Warren, Formal semantics for time in databases, ACM Transactions on Database Systems (TODS), v.8 n.2, p.214-254, June 1983 [doi>10.1145/319983.319986]
• DM87: Thomas L. Dean , Drew McDermott, Temporal data base management, Artificial Intelligence, v.32 n.1, p.1-55, April 1987 [doi>10.1016/0004-3702(87)90061-0]
• EMHJ93: Martha Escobar-Molano , Richard Hull , Dean Jacobs, Safety and translation of calculus queries with scalar functions, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.253-264, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153909]
• Sho87: Yoav Shoham, Temporal logics in AI: semantical and ontological considerations, Artificial Intelligence, v.33 n.1, p.89-104, Sept. 1987 [doi>10.1016/0004-3702(87)90052-X]
• Sno84: Richard Snodgrass, The temporal query language TQuel, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588041]
• SS87: Arie Segev , Arie Shoshani, Logical modeling of temporal data, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.454-466, May 27-29, 1987, San Francisco, California, United States
• Tan87: Abdullah Uz Tansel, A Statistical Interface for Historical Relational Databases, Proceedings of the Third International Conference on Data Engineering, p.538-546, February 03-05, 1987
• TCG+93: 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
• Ull88: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• WBBJ94: X. Wang, C. Bettini, A. Brodsky, and S. J ajodia. Logical design for temporal databases with multiple temporal types. Technical Report ISSE-TR-94-111, GMU, 1994.
• WJL91: Gio Wiederhold , Sushil Jajodia , Witold Litwin, Dealing with granularity of time in temporal databases, Proceedings of the third international conference on Advanced information systems engineering, p.124-140, May 1991, Trondheim, Norway
• WJS95: X. Sean Wang , Sushil Jajodia , V. S. Subrahmanian, Temporal modules: an approach toward federated temporal databases, Information Sciences—Informatics and Computer Science: An International Journal, v.82 n.1-2, p.103-128, Jan. 1995 [doi>10.1016/0020-0255(94)00062-G]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.3 Languages
          Subjects: Query languages
          Nouns: MQL

General Terms:
Algorithms, Languages, Theory