On completeness of historical relational query languages

ABSTRACT

Numerous proposals for extending the relational data model to incorporate the temporal dimension of data have appeared in the past several years. These proposals have differed considerably in the way that the temporal dimension has been incorporated both into the structure of the extended relations of these temporal models and into the extended relational algebra or calculus that they define. Because of these differences, it has been difficult to compare the proposed models and to make judgments as to which of them might in some sense be equivalent or even better. In this paper we define temporally grouped and temporally ungrouped historical data models and propose two notions of historical relational completeness, analogous to Codd's notion of relational completeness, one for each type of model. We show that the temporally ungrouped models are less expressive than the grouped models, but demonstrate a technique for extending the ungrouped models with a grouping mechanism to capture the additional semantic power of temporal grouping. For the ungrouped models, we define three different languages, a logic with explicit reference to time, a temporal logic, and a temporal algebra, and motivate our choice for the first of these as the basis for completeness for these models. For the grouped models, we define a many-sorted logic with variables over ordinary values, historical values, and times. Finally, we demonstrate the equivalence of this grouped calculus and the ungrouped calculus extended with a grouping mechanism. We believe the classification of historical data models into grouped and ungrouped models provides a useful framework for the comparison of models in the literature, and furthermore, the exposition of equivalent languages for each type provides reasonable standards for common, and minimal, notions of historical relational completeness.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• 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: ARIAV, G., AND CLIFFORD, J. 1986 Temporal data management: Models and systems. In New Dzrectwns for Database Systems, G. Ariav and J. Clifford, Eds. Ablex, Norwood, N.J, pp. 168 185.
• 4: BANCILHfON, F. 1978. On the completeness of query languages for relational databases. In Proceedings of the 7th Symposium on Mathematical Foundations of Computing. Springer- Verlag, New York, pp. 112-123.
• 5: Jay Banerjee , Won Kim , Hyoung-Joo Kim , Henry F. Korth, Semantics and implementation of schema evolution in object-oriented databases, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.311-322, May 27-29, 1987, San Francisco, California, United States
• 6: Jacov Ben-Zvi, The time relational model, 1982
• 7: CHANDRA, A. K, AND HAREL, D 1980. Computable queries for relational data bases J. Comput Syst. Sci. 21, 2 (Oct.), 156-178.
• 8: CLIFFORD, J. 1982. A model fbr historical databases. In Proceedzngs of Workshop on Logical Bases for Data Bases (Toulouse, France, Dec.), ONERA-CERT, Toulouse, France.
• 9: James Clifford, Indexical Databases, Advanced Database Systems, p.153-173, January 1993
• 10: James Clifford , Albert Croker, The Historical Relational Data Model (HRDM) and Algebra Based on Lifespans, Proceedings of the Third International Conference on Data Engineering, p.528-537, February 03-05, 1987
• 11: 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
• 12: 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]
• 13: CODD, E F. 1972 Relahonal completeness of data base sublanguages. In Data Base Systems, R. Rustin, Ed. Prentice-Hall, Englewood Cliffs, N.J.
• 14: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 15: ENDERTON, H.B. 1972. A Mathematical Introductwn to Logic. Academic Press, New York.
• 16: FISCHER, P. C., AND VAN GUCHT, D. 1985 Determining when a structure is a nested relation. In Ii~ternatzonal Conference on Very Large Databases. pp. 171-180.
• 17: Dov M. Gabbay, The Declarative Past and Imperative Future: Executable Temporal Logic for Interactive Systems, Temporal Logic in Specification, p.409-448, April 08-10, 1987
• 18: Shashi K. Gadia, Toward a Multihomogeneous Model for a Temporal Database, Proceedings of the Second International Conference on Data Engineering, p.390-397, February 05-07, 1986
• 19: Shashi K. Gadia, A homogeneous relational model and query languages for temporal databases, ACM Transactions on Database Systems (TODS), v.13 n.4, p.418-448, Dec. 1988 [doi>10.1145/49346.50065]
• 20: HALL, P., OWLETT, J., AND TODD, S. J.P. 1976. Relations and entitles In Modelling in Data Base Management Systems, G. M. Nijssen, Ed. North-Holland, Amsterdam.
• 21: HALMOS, P. 1960. Naive Set Theory. Van Nostrand, Princeton, N.J.
• 22: JONES, S., AND MASON, P.J. 1980. Handling the time dimension in a data base. In Proceedings of the International Conference of Data Bases (Heyden, U.K., July). British Computer Society, London, pp. 65-83.
• 23: F. Kabanza , J.-M. Stevenne , P. Wolper, Handling infinite temporal data, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.392-403, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298590]
• 24: KAMP, H. 1971. Formal properties of'now'. Theoria 37, 3, 227 273.
• 25: KAMP, H. 1968. On the tense logic and the theory of order. Ph.D. thesis, Philosophy Dept., Univ. of California at Los Angeles.
• 26: Anthony Klug, Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions, Journal of the ACM (JACM), v.29 n.3, p.699-717, July 1982 [doi>10.1145/322326.322332]
• 27: Fred Kröger, Temporal logic of programs, Springer-Verlag New York, Inc., New York, NY, 1987
• 28: LORENTZOS, R. G., aND JOHNSON, N.A. 1987. TRA: A model for a temporal relational algebra. In Proceedings of the Conference on Temporal Aspects in Informatzon Systems. AFCET, pp. 99-112.
• 29: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 30: MCI~zNZIE, E. 1986. Bibliography: Temporal databases. ACM SIGMOD Rec. 15, 4 (Dec.), 40-52.
• 31: E. McKenzie , Richard Thomas Snodgrass, Schema evolution and the relational algebra, Information Systems, v.15 n.2, p.207-232, 1990 [doi>10.1016/0306-4379(90)90036-O]
• 32: McKENzm, E., AND SNODGRASS, R. 1991b. Supporting valid time in an historical relational algebra: Proofs and extensions. Tech. Rep. TR-91-15, Dept. of Computer Science, Univ. of Arizona, Tucson, Aug.
• 33: L. Edwin McKenzie, Jr. , Richard Thomas Snodgrass, Evaluation of relational algebras incorporating the time dimension in databases, ACM Computing Surveys (CSUR), v.23 n.4, p.501-543, Dec. 1991 [doi>10.1145/125137.125166]
• 34: S. B. Navathe , R. Ahmed, A temporal relational model and a query language, Information Sciences: an International Journal, v.49 n.1-3, p.147-175, Oct.-Dec. 1989 [doi>10.1016/0020-0255(89)90026-1]
• 35: QUINE, W. V.O. 1953. From a Logical Poilzt of Vtew. Harvard University Press, Cambridge, Mass.
• 36: RESCHER, N., aND URQUHART, A. 1971. Temporal Logic. Springer-Verlag, New York.
• 37: Mark A. Roth , Herry F. Korth , Abraham Silberschatz, Extended algebra and calculus for nested relational databases, ACM Transactions on Database Systems (TODS), v.13 n.4, p.389-417, Dec. 1988 [doi>10.1145/49346.49347]
• 38: N. L. Sarda, Algebra and query language for a historical data model, The Computer Journal, v.33 n.1, p.11-18, Feb. 1990 [doi>10.1093/comjnl/33.1.11]
• 39: 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
• 40: Richard Snodgrass, The temporal query language TQuel, ACM Transactions on Database Systems (TODS), v.12 n.2, p.247-298, June 1987 [doi>10.1145/22952.22956]
• 41: Richard Snodgrass, Temporal databases status and research directions, ACM SIGMOD Record, v.19 n.4, p.83-89, Dec. 1990 [doi>10.1145/122058.122068]
• 42: Richard Snodgrass , Ilsoo Ahn, A taxonomy of time databases, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.236-246, May 1985, Austin, Texas, United States
• 43: SNODGRASS, R., GOMEZ, S., aND MCKENzIE, E. 1989. Aggregates in the temporal query language tquel. Tech. Rep. TR-89-26, Dept. of Computer Science, Univ. of Arizona, Tucson, Nov.
• 44: Michael D. Soo, Bibliography on temporal databases, ACM SIGMOD Record, v.20 n.1, p.14-23, March 1991 [doi>10.1145/122050.122054]
• 45: STAM, R., AND SNODGRASS, R. 1988. A bibliography on temporal databases. Database Eng. 7, 4 (Dec.), 231-239.
• 46: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• 47: Abdullah U. Tansel , Lucy Garnett, On Roth, Korth, and Silberschatz's extended algebra and calculus for nested relational databases, ACM Transactions on Database Systems (TODS), v.17 n.2, p.374-383, June 1992 [doi>10.1145/128903.128908]
• 48: TANSEL, A., CLIFFORD, J., GADIA, S., JAJODIA, S., SEGEV, A., AND SNODGRASS, R. EDS. 1993. Temporal Databases. Benjamin/Cummings, Menlo Park, Calif.
• 49: Abdullah Uz Tansel, Adding time dimension to relational model and extending relational algebra, Information Systems, v.11 n.4, p.343-355, Oct. 1986 [doi>10.1016/0306-4379(86)90014-1]
• 50: Alexander Sergei Tuzhilin , Zvi M. Kedem, Using relational discrete event systems and models for prediction of future behavior of databases, 1989
• 51: Alexander Tuzhilin , James Clifford, A temporal relational algebra as a basis for temporal relational completeness, Proceedings of the sixteenth international conference on Very large databases, p.13-23, September 1990, Brisbane, Australia
• 52: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 53: VAN BENTHEM, J. F A.K. 1983. The Logic of Time. Reidel, Hingham, Mass.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

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

General Terms:
Languages, Theory

Keywords:
completeness, historical databases, query languages, relational model, temporal databases, temporal grouping, temporal logic