Stanford InfoLab Publication Server

Temporal versus First-Order Logic to Query Temporal Databases

Abiteboul, S. and Herr, L. and Bussche, J. (1996) Temporal versus First-Order Logic to Query Temporal Databases. Technical Report. Stanford InfoLab. (Publication Note: Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 3-5, 1996, Montreal, Canada.)




A database history can be modeled as a (finite) sequence of instances discretely 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-order 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. On leave from INRIA-Rocquencourt y Work performed while on leave at INRIA-Rocquencourt. Post-doctoral research fellow of the Belgian National Fund for Scientific Research. Contact address: Jan Van den Bussche, Informatica , UIA, Universiteitsplein 1, B-2610 Antwerpen, Belgium. E-mail:

Item Type:Techreport (Technical Report)
Subjects:Computer Science > Query Processing
Related URLs:Project Homepage
ID Code:148
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:08 Dec 2008 14:20

Download statistics

Repository Staff Only: item control page