Automatic deduction of temporal information

ABSTRACT

In many computer-based applications, temporal information has to be stored, retrieved, and related to other temporal information. Several time models have been proposed to manage temporal knowledge in the fields of conceptual modeling, database systems, and artificial intelligence. In this paper we present TSOS, a system for reasoning about time that can be integrated as a time expert in environments designed for broader problem-solving domains. The main intended goal of TSOS is to allow a user to infer further information on the temporal data stored in the database through a set of deduction rules handling various aspects of time. For this purpose, TSOS provides the capability of answering queries about the temporal specifications it has in its temporal database. Distinctive time-modeling features of TSOS are the introduction of temporal modalitites, i.e., the possibility of specifying if a piece of information is always true within a time interval, or if it is only sometimes true, and the capability of answering about the possibility and the necessity of the validity of some information at a given time, the association of temporal knowledge both to instances of data and to types of data, and the development of a time calculus for reasoning on temporal data. Another relevant feature of TSOS is the capability to reason about temporal data specified at different time granularities.

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: James F. Allen, Towards a general theory of action and time, Artificial Intelligence, v.23 n.2, p.123-154, July 1984 [doi>10.1016/0004-3702(84)90008-0]
• 3: ANDERSON, T.L. Modebng time at the conceptual level. In Improving Database Usobzhty and Responsweness, P Scheuermanm Ed., Academic Press, New York, 1982, pp 273 297.
• 4: ARIAV, G, AND CLIFFORD, J. A system architecture for temporally oriented data management. In Proceedings of International Conference on Informatmn Systems (Tucson, Ariz., Nov. 1984), pp. 177-186.
• 5: 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]
• 6: F. Barbic , B. Pernici, Time modeling in office information systems, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.51-62, May 1985, Austin, Texas, United States
• 7: BARBI~', F, AND MAIOCCHI, R. Planning in time. In Proceedings of the Afcet-IFIP WG8 l Conl~erence on Temporal Aspects in Informatmn Systems (Sophm-Antlpohs, France, May 1987), pp 147-161.
• 8: A. Bolour , T. L. Anderson , L. J. Dekeyser , H. K. T. Wong, The role of time in information processing: a survey, ACM SIGMOD Record, v.12 n.3, p.27-50, April 1982 [doi>10.1145/984505.984508]
• 9: BOL{~UR, A., AND DEKEYSER, L. d Abstractions in temporal information. Inf. Syst. 8, 1 (19831, 41 49.
• 10: BUBENKO, J.A. Information modeling m the context of system development. In Proceedings of the IFIP Information Processing '80. North-Holland, Amsterdam, 1980, pp 395-411.
• 11: Croci, S., GOTTLOB, G, AND W}{EDERHOLD, G. Interfacing relational databases and Prolog ef~mently In ProceedzTzgs of the Cotzference on Expert Database Systems (Charleston, N.C., 1986), pp 207-223.
• 12: Stefano Ceri , Letizia Tanca, Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries, Proceedings of the 13th International Conference on Very Large Data Bases, p.31-41, September 01-04, 1987
• 13: CHEN, P.P.S. The time dimension in the entity-relationship model. In Proceedings of the IFIP Information Processing '86. North-Holland, Amsterdam, 1986, pp. 387-390.
• 14: 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]
• 15: CLIFFORD, J. Towards an algebra of historical relational databases, 84-91 (CR), Center for Research and Information Systems, New York Univ., (Dec. 1984).
• 16: CLIFFORD, J., AND RAO, A. A simple, general structure for temporal domains. In Proceedzngs of the Afeet-IFIP WG8.1 Conference on Temporal Aspects in Informatmn Systems (Sophla- Antipolis, France, May 1987), pp. 17-28.
• 17: W F. Clocksin , Christopher S. Mellish, Programming in Prolog (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1984
• 18: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 19: C. J. Date, Defining data types in a database language, ACM SIGMOD Record, v.17 n.2, p.53-76, June 1988 [doi>10.1145/51708.51712]
• 20: 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]
• 21: DOYLE, J. A truth maintenance system. Artif. Intell. 12, 3 (1979), 231-272.
• 22: EQUATOR TEAM. How to apply the GRF. Position Paper of the ESPRIT Project 2409 Equator (Environment for Qualitative TempOral Reasoning) Nov. 1989.
• 23: Shashi K. Gadia , Jay H. Vaishnav, A query language for a homogeneous temporal database, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.51-56, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325412]
• 24: KAHN, K., AND GORRY, G. A. Mechanizing temporal knowledge. Arttf. Intell. 9 (1977), 87 108.
• 25: Manfred R. Klopprogge , Peter C. Lockemann, Modelling Information Preserving Databases: Consequences of the Concept of Time, Proceedings of the 9th International Conference on Very Large Data Bases, p.399-416, October 31-November 02, 1983
• 26: R Kowalski , M Sergot, A logic-based calculus of events, New Generation Computing, v.4 n.1, p.67-95, 1986 [doi>10.1007/BF03037383]
• 27: LANGEFORS, B., AND SUNDGREN, B. Informatzon Systems Architecture. Petrocelli/Charter, New York, 1975.
• 28: V Lum , P Dadam , R Erbe , J Guenauer , P Pistor , G Walch , H Werner , J Woodfill, Designing DBMS support for the temporal dimension, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 29: MAIOCEHI, R., AND PERNICI, B. Time reasoning in the office environment. In Methods and Tools for Office Systems, North-Holland, Amsterdam, (1987), pp. 223-246.
• 30: R. Maiocchi , B. Pernici, Temporal Data Management Systems: A Comparative View, IEEE Transactions on Knowledge and Data Engineering, v.3 n.4, p.504-524, December 1991 [doi>10.1109/69.109111]
• 31: MARCOTULLIO, S., AND SANZO, E. Tesys: Un Sistema per la Rappresentazione e la Gestione di Dati Temporali. Graduation thesis, Dip. Elettronica, Politecnico di Milano 1990. In Italian.
• 32: McK~NZIE, E. Bibliography: Temporal databases. ACM SIGMOD Rec. 15, 4 (Dec. 1986), 40-52.
• 33: NAVATHE, S. B., AND AHMED, R. TSQL: A language interface for history databases. In Proceedings of the Afcet-IFIP WG8.1 Conference on Temporal Aspects in Information Systems (Sophia-Antipolis, France, May 1987), pp. 113-128.
• 34: PERNICI, B., AND PEZZE', M. Temporal analysis of office procedures. CEFRIEL Rep., Oct. 1989.
• 35: RESCHER, N., AND URQUHART, A. Temporal Logic. Springer-Verlag, New York, 1971.
• 36: Fariba Sadri, Three recent approaches to temporal reasoning, Temporal logics and their applications, Academic Press Professional, Inc., San Diego, CA, 1987
• 37: Richard Snodgrass , Ilsoo Ahn, Temporal databases, Computer, v.19 n.9, p.35-41, Sept. 1986 [doi>10.1109/MC.1986.1663327]
• 38: 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]
• 39: Suryanarayana M. Sripada, A logical framework for temporal deductive databases, Proceedings of the 14th International Conference on Very Large Data Bases, p.171-182, August 29-September 01, 1988
• 40: 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]
• 41: John Woodfill , Michael Stonebraker, An Implementation of Hypothetical Relations, Proceedings of the 9th International Conference on Very Large Data Bases, p.157-166, October 31-November 02, 1983
• 42: Z~CARI, R., MAIOCCHI, R., AND FUGINI, MG. Time management in the Office-net system. In Proceedmg.~ of the IFIP WGS.4 Workshop on Of/~ce Knowledge (Toronto, Aug. 1987), pp 163 176

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Deduction (e.g., natural, rule-based)

General Terms:
Design, Languages, Theory

Keywords:
events, meta-level temporal assertions, propositions, temporal database, temporal modalities, time calculus