Handling Infinite Temporal Data.

Froduald Kabanza, Jean-Marc Stévenne, Pierre Wolper: Handling Infinite Temporal Data. PODS 1990: 392-403
  author    = {Froduald Kabanza and
               Jean-Marc St{\'e}venne and
               Pierre Wolper},
  title     = {Handling Infinite Temporal Data},
  booktitle = {Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee},
  publisher = {ACM Press},
  year      = {1990},
  isbn      = {0-89791-352-3},
  pages     = {392-403},
  ee        = {, db/conf/pods/KabanzaSW90.html},
  crossref  = {DBLP:conf/pods/90},
  bibsource = {DBLP,}


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.

Copyright © 1990 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee. ACM Press 1990, ISBN 0-89791-352-3
Contents BibTeX

Journal Version

Froduald Kabanza, Jean-Marc Stévenne, Pierre Wolper: Handling Infinite Temporal Data. J. Comput. Syst. Sci. 51(1): 3-17(1995) BibTeX

Online Edition: ACM Digital Library


James F. Allen: Maintaining Knowledge about Temporal Intervals. Commun. ACM 26(11): 832-843(1983) BibTeX
Martín Abadi, Zohar Manna: Temporal Logic Programming. SLP 1987: 4-16 BibTeX
Gad Ariav: A Temporally Oriented Data Model. ACM Trans. Database Syst. 11(4): 499-527(1986) BibTeX
Marianne Baudinet: Temporal Logic Programming is Complete and Expressive. POPL 1989: 267-280 BibTeX
Fahiem Bacchus, Josh D. Tenenberg, Johannes A. G. M. Koomen: A Non-Reified Temporal Logic. KR 1989: 2-10 BibTeX
Edmund M. Clarke, E. Allen Emerson, A. Prasad Sistla: Automatic Verification of Finite-State Concurrent Systems Using Temporal Logic Specifications. ACM Trans. Program. Lang. Syst. 8(2): 244-263(1986) BibTeX
Jan Chomicki, Tomasz Imielinski: Temporal Deductive Databases and Infinite Objects. PODS 1988: 61-73 BibTeX
James Clifford, David Scott Warren: Formal Semantics for Time in Databases. ACM Trans. Database Syst. 8(2): 214-254(1983) BibTeX
Gösta Grahne: Horn Tables - An Efficient Tool for Handling Incomplete Information in Databases. PODS 1989: 75-82 BibTeX
Joseph Y. Halpern, Yoav Shoham: A Propositional Model Logic of Time Intervals. LICS 1986: 279-292 BibTeX
Joxan Jaffar, Jean-Louis Lassez: Constraint Logic Programming. POPL 1987: 111-119 BibTeX
Peter B. Ladkin: Satisfying First-Order Constraints About Time Intervals. AAAI 1988: 512-517 BibTeX
Orna Lichtenstein, Amir Pnueli: Checking That Finite State Concurrent Programs Satisfy Their Linear Specification. POPL 1985: 97-107 BibTeX
Amir Pnueli, Lenore D. Zuck: Probabilistic Verification by Tableaux. LICS 1986: 322-331 BibTeX
Abdullah Uz Tansel: Adding time dimension to relational model and extending relational algebra. Inf. Syst. 11(4): 343-355(1986) BibTeX
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX
Marc B. Vilain, Henry A. Kautz: Constraint Propagation Algorithms for Temporal Reasoning. AAAI 1986: 377-382 BibTeX
Moshe Y. Vardi, Pierre Wolper: Automata-Theoretic Techniques for Modal Logics of Programs. J. Comput. Syst. Sci. 32(2): 183-221(1986) BibTeX

Referenced by

  1. Claudio Bettini, Xiaoyang Sean Wang, Sushil Jajodia: Temporal Semantic Assumptions and Their Use in Databases. IEEE Trans. Knowl. Data Eng. 10(2): 277-296(1998)
  2. Xiaoyang Sean Wang, Claudio Bettini, Alexander Brodsky, Sushil Jajodia: Logical Design for Temporal Databases with Multiple Granularities. ACM Trans. Database Syst. 22(2): 115-170(1997)
  3. Paolo Terenziani: Integrating Calendar Dates and Qualitative Temporal Constraints in the Treatment of Periodic Events. IEEE Trans. Knowl. Data Eng. 9(5): 763-783(1997)
  4. Paris C. Kanellakis: Constraint Programming and Database Languages: A Tutorial. PODS 1995: 46-53
  5. Jan Chomicki, Gabriel M. Kuper: Measuring Infinite Relations. PODS 1995: 78-85
  6. Peter Z. Revesz: Datalog Queries of Set Constraint Databases. ICDT 1995: 425-438
  7. Marianne Baudinet, Jan Chomicki, Pierre Wolper: Constraint-Generating Dependencies. ICDT 1995: 322-337
  8. James Clifford, Albert Croker, Alexander Tuzhilin: On Completeness of Historical Relational Query Languages. ACM Trans. Database Syst. 19(1): 64-116(1994)
  9. Jan Chomicki, Tomasz Imielinski: Finite Representation of Infinite Query Answers. ACM Trans. Database Syst. 18(2): 181-223(1993)
  10. Manolis Koubarakis: Representation and Querying in Temporal Databases: the Power of Temporal Constraints. ICDE 1993: 327-334
  11. Marianne Baudinet, Marc Niézette, Pierre Wolper: On the Representation of Infinite Temporal Data and Queries. PODS 1991: 280-290
  12. Alexander Tuzhilin, James Clifford: A Temporal Relational Algebra as Basis for Temporal Relational Completeness. VLDB 1990: 13-23
  13. Peter Z. Revesz: A Closed Form for Datalog Queries with Integer Order. ICDT 1990: 187-201
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:34:02 2009