[en] 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 characterize the expressiveness of these generalized relations in terms of predicates definable in Presburger arithmetic. Next, we prove that relations formed from generalized tuples are closed under the operations of relational algebra and provide complexity results for the evaluation of first-order queries.
Disciplines :
Computer science
Author, co-author :
Kabanza, Froduald
Stevenne, Jean-Marc
Wolper, Pierre ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique (parallélisme et banques de données)
J. F. Allen and P. J. Hayes, A common-sense theory of time, in “9th IJCAI, Los Angeles, 1985, ” pp. 528-531.
J. F. Allen and J. F. Koomen, Planning using a temporal world model, in “8th IJCAI, 1983” (A. Bundy, Ed.), pp. 741-747.
J. F. Allen, Maintaining knowledge about temporal intervals, Comm. ACM 26, No. 11 (1983), 832-843.
J. F. Allen, Toward a general theory of action and time, Artif. Intell. 23 (1984), 123-154.
M. Abadi and Z. Manna, Temporal logic programming, in “Symposium on Logic Programming, September 1987.” pp. 4-16, IEEE Comput. Soc. Washington, DC, 1988.
A. A. Aaby and K. T. Narayana, Propositional temporal interval logic is PSPACE complete, in “9th International Con-ference on Automated Deduction, May 1988, " Lecture Notes in Computer Science, Vol. 310. pp. 218-237. Springer-Verlag. New York/Berlin, 1988.
G. Ariav, A temporally oriented data model. ACM Trans. Database Systems 11 (1986), 499-528.
M. Baudinet, Temporal logic programming is complete and expressive, in “16th Annual ACM Symposium on Principles of Programming Languages, January 1989, " pp. 267-280.
F. Bacchus, J. Tenenberg, and J. A. Koomen, A non-reified temporal logic, in “Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning, Toronto, Ontario, Canada, May 1989” (R. J. Brachman, H. J. Levesque, and R. Reiter, Eds), pp. 2-10, Morgan Kaufmann, Las Altas, CA, 1989.
E. M. Clarke, E. A. Emerson, and A. P. Sistla, Automatic verification of finite-state concurrent systems using temporal logic specifications, ACM Trans. Programming Languages and Systems 8, No. 2 (1986), 244-263.
J. Chomicki, Polynomial time query processing in temporal deductive databases, in “Proceedings, 9th ACM Symposium on Principles of Database Systems, Nashville, TN, 1990, ” pp. 379-391.
J. Chomicki and T. Imielinski, Temporal deductive databases and infinite objects, in “Proceedings, 7th ACM Symposium on Principles of Database Systems, Austin. TX, 1988, " pp. 61-73.
J. Clifford and D. S. Warren, Formal semantics for time in database, ACM Trans. Database Systems 8. No. 2 (1983), 214-254.
D. E. Denning, “Cryptography and Data Security, ” pp. 43-44, Addison-Wesley, Reading, MA. 1982.
R. J. Duflin, On Fourier’s analysis of linear inequality systems, Math. Programming Study 1 (1974), 71-95.
D. W. Etherington, A. Borgida, R. J. Brachman, and H. Kautz, Vivid knowledge and tractable reasoning, in “IJCAI-89, Aug. 1989, ” Vol. 2, pp. 1146-1152.
H. B. Enderton, “A Mathematical Introduction to Logic, ” pp. 188-192, Academic Press, New York/London, 1972.
G. Grahne, Horn tables-An efficient tool for handling incomplete information in databases, in “Symposium on Principles of Database Systems, Proceedings, Eighth ACM SIGACT-SIGMOD-SIGART, Mar. 1989, ” pp. 75-82.
J. Y. Halpern and Y. Shoham, A prepositional modal logic of [PZ86] time intervals, Proc. IEEE Symp. On Logic in Computer Science, Cambridge, June 86, pp. 279-292, 1986.
J. Jaflar and J.-L. Lassez, Constraint logic programming, in [Sch88] “Proceedings, ACM Symposium on Principles of Programming Languages, 1987, ” pp. 111-119.
P. Kanelakis, G. M. Kuper, and P. Z. Revesz, Constraint query languages, in “Proceedings, 9th ACM Symposium on Principles of Database Systems, Nashville, TN, 1990, ” pp. 299-313.
P. B. Ladkin, First-order constraint satisfaction for time intervals, in “AAAI-88, August 1988, ” Vol. 2, pp. 512-517.
H. J. Levesque, Making believers out of computers, Artif. Intell. 30, No. 1 (1986), 81-108 (originally given as the “computers and thought” lecture at “IJCAI 85”).
O. Lichtenstein and A. Pnueli, Checking that finite state concurrent programs satisfy their linear specification, in “Proceedings, Twelfth ACM Symposium on the Principles of Programming Languages, New Orleans, LA, January 1985, ” pp. 97-107.
M. Presburger, Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchen die Addition als einzige Operation hervortritt, in “Comptes Rendus, I. Congrès des Mathématiques des Pays Slaves, Warsaw, 1929, ” pp. 192-201, 395.
A. Pnueli and L. Zuck, Probabilistic verification by tableaux, in “Proceedings, 1st Symp. On Logic in Computer Science, Cambridge, June 1986, ” pp. 322-331.
A. Schmiedel, “Temporal Constraint Networks, ” KIT-Report 69, Technical University of Berlin, November 1988.
Y. Shoham, “Reasoning about Change: Time and Causation from the Standpoint of Artificial Intelligence, ” Ph.D. thesis, Yale University, Computer Science Department, New Haven, CT, 1986.
A. U. Tansel, Adding time dimension to relational model and extending relational algebra, Inform. Systems (1986), 343-355.
M. Y. Vardi, The complexity of relational query languages, in “Proceedings, Fourteenth ACM Symposium on Theory of Computing, May 1982, ” pp. 137-146.
Y. Venema, “Expressiveness and Completeness of an Interval Tense Logic, " Technical report, University of Amsterdam, February 1988.
M. Vilain and H. Kautz, Constraints propagation algorithms for temporal reasoning, in “AAAI-86, Fifth National Conference on Artificial Intelligence, August 1986, ” Vol. 1, pp. 377-382, Morgan Kaufmann, Las Altas, CA, 1987.
M. Y. Vardi and P. Wolper, Automata-theoretic techniques for modal logics of programs, J. Comput. System Sci. 32, No. 2 (1986), 183-221.
