[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)
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
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.
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
