Handling infinite temporal data

ABSTRACT

In this paper, we present a powerful framework for describing, storing, and reasoning about infinite temporal information. This framework is an extension of classical relational databases. It represents infinite temporal information by generalized tuples defined by linear repeating points and constraints on these points. We prove that relations formed from generalized tuples are closed under the operations of relational algebra. A characterization of the expressiveness of generalized relations is given in terms of predicates definable in Presburger arithmetic. Finally, we provide some complexity results.

REFERENCES

• AH85: J.F. Allen and P.J. Hayes. A common-sense theory of time. In 9fh IJCAI, pages 528-531, Los Angeles, 1985.
• AK83: J.F. Allen and j.F. Koomen. Planning using a temporal world model. In A. Bundy, editor, 8lh IJCAI, pages 741-747, 1983.
• All83: 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]
• All84: 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]
• AM87: Martin Abadi and Zohar Manna. Temporal Logic Programming. in IEEE Computer Society, editor, Symposium on Logic Programruing, pages 4-16, September 1987.
• Ari86: 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]
• Bau89: M. Baudinet, Temporal logic programming is complete and expressive, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.267-280, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75301]
• BTK89: Fahiem Bacchus , Josh Tenenberg , Johannes A. Koomen, A non-reified temporal logic, Proceedings of the first international conference on Principles of knowledge representation and reasoning, p.2-10, December 1989
• CES86: E. M. Clarke , E. A. Emerson , A. P. Sistla, Automatic verification of finite-state concurrent systems using temporal logic specifications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.2, p.244-263, April 1986 [doi>10.1145/5397.5399]
• CI88: Jan Chomicki , Tomasz Imieliński, Temporal deductive databases and infinite objects, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.61-73, March 1988, Austin, Texas, United States [doi>10.1145/308386.308416]
• 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]
• Duf74: R.J. Duffin. On fourier's analysis of linear inequality systems. Mathematical Programruing Study, 1:71-95, 1974.
• EBBK89: David W. Etherington, Alex Borgida, Ronald J. Bra.chman, and Henry Kautz. Vivid knowledge and tractable reasoning. In IJCAI-89, volume 2, pages 1146-1152, aug 1989.
• End72: Herbert B. Enderton. A Mathematical b~troduction to Logic, pages 188-192. Academic Press, 1972.
• Gra89: G. Grahne, Horn tables-an efficient tool for handling incomplete information in databases, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.75-82, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73728]
• HS86: Joseph Y. Halpern and Yoav Shoham. A Propositionnal Modal Logic of Time Intervals. IEEE, pages 279-292, 1986.
• JL87: J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41635]
• Lad88: Peter B. Ladkin. First-order Constra.int Satisfaction for Time Intervals. In AAAI-88, volume 2, pages 512-517, August 1988.
• Lev86: H J Levesque, Making believers out of computers, Artificial Intelligence, v.30 n.1, p.81-108, Oct. 1986 [doi>10.1016/0004-3702(86)90068-8]
• LP85: Orna Lichtenstein , Amir Pnueli, Checking that finite state concurrent programs satisfy their linear specification, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-107, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318622]
• Pre29: M. Presburger. 0ber die Vollst~ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchen die addition als einzige Operation hervortritt. Ill Comptes Rendus, L Congr~s des Math dmatiques des Pays Slaves, pages 192-201, 395, Warsaw, 1929.
• PZ86: A. Pnueli and L. Zuck. Probabilistic verification by tableaux. In Proc. 1st Syrup. on Logic in Computer Science, pages 322-331, Cambridge, June 1986.
• Sch88: Albrecht Schmiedel. Temporal constraint networks. KIT-Report 69, Technical University of Berlin, November 1988.
• Sho86: Yoav Shoham, Reasoning about change: time and causation from the standpoint of artificial intelligence, 1987
• Tan86: 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]
• Var82: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• Ven88: Yde Venema. Expressiveness and Completeness of an Interval Tense Logic. Technical report, University of Amsterdam, February 1988.
• VK86: Marc Vilain and Henry I(autz. Constraints propagation algorithms for temporal reasoning. In AAAI-86, volume 1, pages 377-382. Fith National Conference on Artifitial Intelligenge, Morgan Kaufmann, August 1986.
• VW86: Moshe Y Vardi , Pierre Wolper, Automata-Theoretic techniques for modal logics of programs, Journal of Computer and System Sciences, v.32 n.2, p.183-221, April 1986 [doi>10.1016/0022-0000(86)90026-7]

INDEX TERMS

Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Design