ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Temporal Versus First-Order Logic to Query Temporal Databases.

Serge Abiteboul, Laurent Herr, Jan Van den Bussche: Temporal Versus First-Order Logic to Query Temporal Databases. PODS 1996: 49-57
@inproceedings{DBLP:conf/pods/AbiteboulHB96,
  author    = {Serge Abiteboul and
               Laurent Herr and
               Jan Van den Bussche},
  title     = {Temporal Versus First-Order Logic to Query Temporal Databases},
  booktitle = {Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 3-5, 1996, Montreal,
               Canada},
  publisher = {ACM Press},
  year      = {1996},
  isbn      = {0-89791-781-2},
  pages     = {49-57},
  ee        = {http://doi.acm.org/10.1145/237661.237674, db/conf/pods/AbiteboulHB96.html},
  crossref  = {DBLP:conf/pods/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A database history can be modeled as a (finite) sequence of instances directely ordered by time. Similarly, the behavior of a system such as an operating system or a reactive system can be modeled by an infinite such sequence. One can view the sequence as one single database where each relation has an additional column holding the time instant of validity of each tuple. The temporal database can then be queried using standard relational calculus (first-oder logic) on this "timestamp" representation. One may alternatively use an implicit access to time and express queries in temporal logic. It is known that these two approaches yield the same expressive power in the propositional case. Their comparison in the predicate/database context remained open. We prove here that there are first-order logic queries on the timestamp representation that are not expressible in (extended) temporal logic. The proof technique is novel and is based on Communication complexity.

Copyright © 1996 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 Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 3-5, 1996, Montreal, Canada. ACM Press 1996, ISBN 0-89791-781-2
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 805 KB]

References

[1]
Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX
[2]
Serge Abiteboul, Laurent Herr, Jan Van den Bussche: Temporal Connectives versus Explicit Timestamps in Temporal Query Languages. Temporal Databases 1995: 43-57 BibTeX
[3]
...
[4]
...
[5]
...
[6]
Dov M. Gabbay, Peter McBrien: Temporal Logic & Historical Databases. VLDB 1991: 423-430 BibTeX
[7]
...
[8]
...
[9]
...
[10]
...
[11]
...
[12]
...
[13]
David Toman, Damian Niwinski: First-Order Queries over Temporal Databases Inexpressible in Temporal Logic. EDBT 1996: 307-324 BibTeX
[14]
Alexander Tuzhilin, James Clifford: A Temporal Relational Algebra as Basis for Temporal Relational Completeness. VLDB 1990: 13-23 BibTeX
[15]
Pierre Wolper: Temporal Logic Can Be More Expressive. Information and Control 56(1/2): 72-99(1983) BibTeX
[16]
Andrew Chi-Chih Yao: Some Complexity Questions Related to Distributive Computing (Preliminary Report). STOC 1979: 209-213 BibTeX

Referenced by

  1. Marc Spielmann: Verification of Relational Transducers for Electronic Commerce. PODS 2000: 92-103
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:14 2009