A Temporal Algebra with Recursive Equations

Mehmet Al_? Orgun
Department of Computing, Macquarie University
Sydney, NSW 2109, Australia
E-mail: [email protected]

Abstract

This paper introduces a recursive temporal algebra for querying time-varying data. The algebra, called <?, is based on a temporal relational data model in which a temporal database is modeled as a collection of time-varying relations. Each time-varying relation is a collection of ordinary relations indexed by moments in time. In <?, recursive queries (such as the transitive closure of a given relation) can be formulated through equations. It is shown that other forms of recursion, such as linear recursion, can also be expressed using iteration through time. The meaning of recursive equations is formulated using a standard approach based on fixed-point semantics. Temporal completeness of <? with bounded time is established, with respect to two other temporal algebras based on temporal semantics which also offer linear recursive operators.

Keywords: Temporal databases, temporal algebras, time-varying relations, recursive queries, recursive equations, fixed-point semantics, linear recursion, temporal completeness.

1 Introduction

The relational algebra [11] operates on a model which cannot naturally deal with the notion of a history, or how each relation has evolved into what it is now. Having recognized the need to incorporate the time dimension into the relational model, a significant number of research efforts have been directed towards studying various aspects of this problem; the status of research on temporal databases can be found in the recent survey of Ozsoyo>=glu and Snodgrass [30], and in the collection by Tansel et al [36], with a recent bibliography in Kline [20]. Included in that effort are temporal extensions of the relational algebra. The prevailing approach to modelling the time dimension in databases is, in one form or another, the use of an explicit representation of time at both the tuple level and the attribute level [10, 13, 31]. Also, most of the temporal algebras reported in the literature provide operators for an explicit manipulation of complex time-varying attributes and temporal elements directly, and for switching from one representation of time to another.

McKenzie and Snodgrass [26] give an extensive evaluation of temporal algebras based on a number of criteria. Some of the important criteria are: (1) a temporal algebra should be a consistent extension of the relational algebra, (2) its formal semantics is well-defined, (3) it is an algebra in the mathematical sense (it has the closure property), (3) it supports basic algebraic equivalences, (4) it reduces to the relational algebra (over moments in time), (5) it supports the standard definitions of intersection (), ?-join, natural join (./), and quotient (?), and (6) it includes aggregates. Most of the proposed algebras satisfy only a few of these criteria, and do not include aggregates because of the complicated interval semantics.