Formal semantics for time in databases

ABSTRACT

The concept of a historical database is introduced as a tool for modeling the dynamic nature of some part of the real world. Just as first-order logic has been shown to be a useful formalism for expressing and understanding the underlying semantics of the relational database model, intensional logic is presented as an analogous formalism for expressing and understanding the temporal semantics involved in a historical database. The various components of the relational model, as extended to include historical relations, are discussed in terms of the model theory for the logic ILs, a variation of the logic IL formulated by Richard Montague. The modal concepts of intensional and extensional data constraints and queries are introduced and contrasted. Finally, the potential application of these ideas to the problem of natural language database querying is discussed.

REFERENCES

• 1: BENNETT, M.R. Some extensions of a Montague fragment of English. Ph.d dissertation, University of California at Los Angeles, 1974.
• 2: BENNETT, M.R. Questions in Montague grammar. Indiana University Linguistics Club, Bloomington, Indiana, 1979.
• 3: BILLER, H,, AND NEUHOLD, E.J. Semantics of data bases: The semantics of data models. Inf. Syst. 3, 1 (1978), 11-36.
• 4: BoBRow, D.G., AND WINOGRAD, T. An overview of KRL--A knowledge representation language. Cognitive Science I, 1 (1977), 3-46.
• 5: BUBENKO, J.A., JR. The temporal dimension in information modelling. In Architecture and Models in Data Base Management Systems, G.M. Nijssen (Ed.), North Holland, Amsterdam, 1977.
• 6: CARNAP, R. Meaning and Necessity. University of Chicago Press, Chicago, 1947.
• 7: Marco A. Casanova , Philip A. Bernstein, The logic of a relational data manipulation language, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.101-109, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567762]
• 8: CHANG, C.L. DEDUCE 2: Further investigations of deduction in relational data bases. In Logic and Data Bases, H. Gallaire and J. Minker (Eds.), Plenum Press, New York, 1978.
• 9: Peter Pin-Shan Chen, The entity-relationship model—toward a unified view of data, ACM Transactions on Database Systems (TODS), v.1 n.1, p.9-36, March 1976 [doi>10.1145/320434.320440]
• 10: Alonzo Church, The Calculi of Lambda Conversion. (AM-6) (Annals of Mathematics Studies), Princeton University Press, Princeton, NJ, 1985
• 11: James Clifford, A logical framework for the temporal semantics and natural-language querying of historical databases, 1982
• 12: CODASYL DATA BASE TASK GROUP. CODASYL data base task group report. ACM, New York, 1971.
• 13: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 14: DowTY, D.R., WALL, R.E., AND PETERS, S. Introduction to Montague Semantics. D. Reidel, Dordrecht, Germany, 1981.
• 15: DOWTY, D.R. Word Meaning and Montague Grammar. D. Reidel, Dordrecht, Germany, 1979.
• 16: FREGE, G. On sense and reference, in Translations from the Philosophical Writings of Gottlob Frege, P. Geach and M. Black (Eds.), Basil Blackwell Publisher, 1952.
• 17: Herve Gallaire , Jack Minker, Logic and Data Bases, Perseus Publishing, 1978
• 18: GALLIN, D. Intensional and Higher-Order Modal Logic. North-Holland, Amsterdam, 1975.
• 19: GOLDSTEIN, B.S. Constraints on null values in relational databases. Tech. Rep. 80/015, Dep. Computer Science, State University of New York at Stony Brook, 1981.
• 20: GREINER, R., AND LENAT, D.B. A representation language language. In Proc. l st Annual National Conference on Artificial Intelligence, Stanford Ca. American Ass. for Artificial Intelligence, Menlo Park, Ca.
• 21: Michael Hammer , Dennis McLeod, The semantic data model: a modelling mechanism for data base applications, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509264]
• 22: HAYES, P.J. In defence of logic. In Proc. 5th International Joint Conference on Artif. Intell., Cambridge.
• 23: HOBBS, J.R., AND ROSENSCHEIN, S.J. Making computational sense of Montague's intensional logic. Artif Intell 9, 3 (1977), 287-306.
• 24: IBM. IMS/360--Application Description Manual. GH-20.0765, IBM, White Plains, New York.
• 25: KARTUNNEN, L. Syntax and semantics of questions. Linguistics and Philosophy, 1 (1977), 3-44.
• 26: Manfred R. Klopprogge, TERM: An Approach to Include Time Dimension in the Entity-Relationship Model, Proceedings of the Second International Conference on the Entity-Relationship Approach to Information Modeling and Analysis, p.473-508, October 12-14, 1981
• 27: Robert Kowalski, Logic for problem-solving, North-Holland Publishing Co., Amsterdam, The Netherlands, 1986
• 28: LAINE, H., MAANAVILJA, O., AND PELTONA, E. Grammatical data base model. Inf. Syst. 4, 4 (1979).
• 29: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 30: MAIER, D., AND WARREN, D.S. A theory of computed relations. Tech. Rep. 80/012, Dep. Computer Science, S.U.N.Y. at Stony Brook, i980.
• 31: David Maier , David S. Warren, Specifying connections for a universal relation scheme database, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582355]
• 32: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 33: MINKER, J. An experimental relational data base system based on logic. In Logic and Data Bases, H. Gallaire and J. Minker (Eds.), Plenum Press, New York, 1978.
• 34: MINSKY, M. A framework for representation knowledge. In The Psychology of Computer Vision, P.H. Winston (Ed.), New York, 1975.
• 35: MONTAGUE, R. The proper treatment of quantification in ordinary English. In Approaches to Natural Language, K.J.J. Hintikka (Ed.), Dordrecht, Germany, 1973.
• 36: J. M. Nicolas, First order logic formalization for functional, multivalued and mutual dependencies, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509269]
• 37: NICOLAS, J.M., AND GALLAIRE, n. Data base: theory vs. interpretation. In Logic and Data Bases, H. Gallaire and J. Minker (Eds.), Plenum Press, New York, I978.
• 38: NICOLAS, J.M., AND YAZDANIAN, K. Integrity checking in deductive data bases. In Logic and Data Bases, H. Gallaire and J. Minker (Eds.), Plenum Press, New York, 1978.
• 39: QUINE, W.V.O. From a Logical Point of View. Harper and Row, New York, 1953.
• 40: QUINE, W.V.O. Word and Object. MIT Press, Cambridge, Mass., 1960.
• 41: REITER, R. On closed world data bases. In Logic and Data Bases, H. Gallaire and J. Minker (Eds.), Plenum Press, New York, 1978.
• 42: RESCHER, N., AND URQUHART, A. Temporal Logic. Springer-Verlag, New York, 1971.
• 43: Hans Albrecht Schmid , J. Richard Swenson, On the semantics of the relational data model, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500110]
• 44: SERNADAS, A. Temporal aspects of logical procedure definition. Inf. Syst. 5 {1980), 167-187.
• 45: David W. Shipman, The functional data model and the data languages DAPLEX, ACM Transactions on Database Systems (TODS), v.6 n.1, p.140-173, March 1981 [doi>10.1145/319540.319561]
• 46: John Miles Smith , Diane C. P. Smith, Database abstractions: aggregation and generalization, ACM Transactions on Database Systems (TODS), v.2 n.2, p.105-133, June 1977 [doi>10.1145/320544.320546]
• 47: Michael Stonebraker , Kenneth Keller, Embedding expert knowledge and hypothetical data bases into a data base system, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582261]
• 48: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983

INDEX TERMS

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

General Terms:
Design, Languages, Theory

Keywords:
entity-relationship model, historical databases, intensional logic, relational database, temporal semantics