Temporal Logic in Information Systems

Jan Chomicki
David Toman

November 1997

Abstract:

Temporal logic is obtained by adding temporal connectives to a logic language. Explicit references to time are hidden inside the temporal connectives. Different variants of temporal logic use different sets of such connectives. In this chapter, we survey the fundamental varieties of temporal logic and describe their applications in information systems.

Several features of temporal logic make it especially attractive as a query and integrity constraint language for temporal databases. First, because the references to time are hidden, queries and integrity constraints are formulated in an abstract, representation-independent way. Second, temporal logic is amenable to efficient implementation. Temporal logic queries can be translated to an algebraic language. Temporal logic constraints can be efficiently enforced using auxiliary stored information. More general languages, with explicit references to time, do not share these properties.

Recent research has proposed various implementation techniques to make temporal logic practically useful in database applications. Also, the relationships between different varieties of temporal logic and between temporal logic and other temporal languages have been clarified. We report on these developments and outline some of the remaining open research problems.

Contents

1

Introduction

2

Temporal Databases

2.1

Abstract Temporal Databases

2.2

Relational Database Histories

3

Temporal Queries

3.1

Abstract Temporal Query Languages

3.2

Expressive Power

3.3

Space-efficient Encoding of Temporal Databases

3.4

Concrete Temporal Query Languages

3.5

Evaluation of Abstract Query Languages using Compilation

3.6

SQL and Derived Temporal Query Languages

4

Temporal Integrity Constraints

4.1

Notions of constraint satisfaction

4.2

Temporal Integrity Maintenance

4.3

Temporal Constraint Checking

5

Multidimensional Time

5.1

Why Multiple Temporal Dimensions?

5.2

Abstract Query Languages for Multi-dimensional Time

5.3

Encoding of Multi-dimensional Temporal Databases

6

Beyond First-order Temporal Logic

7

Conclusion

Available as PostScript, PDF, DVI.