Temporal versus First-Order Logic to Query Temporal Databases

Abstract

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: vdbuss@uia.ua.ac.be.