Temporal Deductive Databases and Infinite Objects.

Jan Chomicki, Tomasz Imielinski: Temporal Deductive Databases and Infinite Objects. PODS 1988: 61-73
  author    = {Jan Chomicki and
               Tomasz Imielinski},
  title     = {Temporal Deductive Databases and Infinite Objects},
  booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 21-23, 1988, Austin,
  publisher = {ACM},
  year      = {1988},
  isbn      = {0-89791-263-2},
  pages     = {61-73},
  ee        = {, db/conf/pods/ChomickiI88.html},
  crossref  = {DBLP:conf/pods/88},
  bibsource = {DBLP,}


We discuss deductive databases with one fixed occurrence of a monadic function symbol(successor) per predicate. Databases of this kind can be used in a natural way to model simple patterns of events repeated in time, and this is why we term them temporal. Temporal deductive databases are also interesting from a theoretical point of view, because they give rise to infinite least fixpoints and infinite query answers. We study complexity properties of finite query answers and define the notion of infinite objects which makes some infinite least fixpoints computable in finite time.

Copyright © 1988 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 Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 21-23, 1988, Austin, Texas. ACM 1988, ISBN 0-89791-263-2
Contents BibTeX

Online Edition: ACM Digital Library


James F. Allen: Maintaining Knowledge about Temporal Intervals. Commun. ACM 26(11): 832-843(1983) BibTeX
James F. Allen: Towards a General Theory of Action and Time. Artif. Intell. 23(2): 123-154(1984) BibTeX
Martín Abadi, Zohar Manna: Temporal Logic Programming. SLP 1987: 4-16 BibTeX
Federico Barbic, Barbara Pernici: Time Modeling in Office Information Systems. SIGMOD Conference 1985: 51-62 BibTeX
James Clifford, David Scott Warren: Formal Semantics for Time in Databases. ACM Trans. Database Syst. 8(2): 214-254(1983) BibTeX
Thomas Dean, Drew V. McDermott: Temporal Data Base Management. Artif. Intell. 32(1): 1-55(1987) BibTeX
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
Tomasz Imielinski: Intelligent Query Answering in Rule Based Systems. J. Log. Program. 4(3): 229-257(1987) BibTeX
David A. Plaisted: Complete Problems in the First-Order Predicate Calculus. J. Comput. Syst. Sci. 29(1): 8-35(1984) BibTeX
Raghu Ramakrishnan, François Bancilhon, Abraham Silberschatz: Safety of Recursive Horn Clauses With Infinite Relations. PODS 1987: 328-339 BibTeX
A. Prasad Sistla, Edmund M. Clarke: The Complexity of Propositional Linear Temporal Logics. J. ACM 32(3): 733-749(1985) BibTeX
Richard T. Snodgrass: Research Concerning Time in Databases - Project Summaries. SIGMOD Record 15(4): 19-39(1986) BibTeX
Richard T. Snodgrass: The Temporal Query Language TQuel. ACM Trans. Database Syst. 12(2): 247-298(1987) BibTeX
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX
Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) BibTeX

Referenced by

  1. Ouri Wolfson, Bo Xu, Sam Chamberlain, Liqin Jiang: Moving Objects Databases: Issues and Solutions. SSDBM 1998: 111-122
  2. 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)
  3. A. Prasad Sistla, Ouri Wolfson, Sam Chamberlain, Son Dao: Modeling and Querying Moving Objects. ICDE 1997: 422-432
  4. Jan Chomicki: Efficient Checking of Temporal Integrity Constraints Using Bounded History Encoding. ACM Trans. Database Syst. 20(2): 149-186(1995)
  5. Marianne Baudinet, Jan Chomicki, Pierre Wolper: Constraint-Generating Dependencies. ICDT 1995: 322-337
  6. Jan Chomicki, Tomasz Imielinski: Finite Representation of Infinite Query Answers. ACM Trans. Database Syst. 18(2): 181-223(1993)
  7. Marianne Baudinet, Marc Niézette, Pierre Wolper: On the Representation of Infinite Temporal Data and Queries. PODS 1991: 280-290
  8. Froduald Kabanza, Jean-Marc Stévenne, Pierre Wolper: Handling Infinite Temporal Data. PODS 1990: 392-403
  9. Jan Chomicki: Polynomial Time Query Processing in Temporal Deductive Databases. PODS 1990: 379-391
  10. Jan Chomicki, Tomasz Imielinski: Relational Specifications of Infinite Query Answers. SIGMOD Conference 1989: 174-183
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:33:53 2009