
A Recursive Temporal Algebra and Temporal Completeness
Mehmet A. Orgun
Department of Computing
Macquarie University
Sydney, NSW 2109, Australia
http://wwwcomp.mpce.mq.edu.au/?mehmet
Abstract
This paper introduces a recursive temporal algebra
based on temporal semantics for querying timevarying
data. The algebra, called <?, is based on a temporal
relational data model in which a temporal database
is modeled as a collection of timevarying relations.
Each timevarying 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. Temporal completeness of <? is established, with
respect to two other temporal algebras based on temporal
semantics which offer linear recursive operators.
1 Introduction
The relational algebra [8] 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 survey of Ozsoyo>=glu and Snodgrass [21], and in the collection by Tansel et al [26]. Included in that effort are temporal extensions of the relational algebra. However, most of the temporal algebras reported in the literature provide operators to manipulate complex timevarying attributes and temporal elements directly [17].
In order to overcome some other limitations of the relational algebra in expressing certain types of queries (such as the transitive closure of a given relation), recursive extensions of the relational algebra and recursive extensions of SQLtype query languages have also been proposed [1, 12, 15]. For example, Houtsma and Apers [12] employ a ?calculus with a fixedpoint operator to express recursive queries. In the context of
temporal databases, Tuzhilin and Clifford [27] propose a temporal algebra with two extra operators of temporal linear recursion. Gabbay and McBrien [9] define a refinement of the algebra of Tuzhilin and Clifford [27]. Neither algebra supports recursive equations.
In this paper we propose a temporal algebra which
supports recursive queries through an equational extension.
The algebra, called <?, is based on an algebra
proposed by Orgun and Muller [20]. <? satisfies
some of the important criteria proposed by McKenzie
and Snodgrass [17]; it is a consistent extension of the
relational algebra, it is an algebra in the mathematical
sense, it has a welldefined formal semantics, it
supports basic algebraic equivalences, and it includes
aggregates. Most of the proposed algebras satisfy only
a few of these criteria, and do not include aggregates
because of complicated interval semantics.
<? is a pointwise extension of the relational algebra
over the set of natural numbers (that is, the collection
of points in time). It is based on temporal semantics,
and hence it does not allow an explicit manipulation
of time. In the underlying relational model based
on temporal semantics, a temporal database is modeled
by a collection of timevarying relations, each of
which is a collection of ordinary relations indexed by
moments in time. <? is also enriched with pointwise
extensions of the standard aggregation operators.
The rest of the paper is organized as follows. In section 2, we outline the underlying temporal data model. In Section 3, we describe the operations of <?. In Section 4, we discuss recursive equations. In Section 5, it is shown that <? with bounded time is temporally complete with respect to the algebras of Tuzhilin and Clifford [27] and Gabbay and McBrien [9]. Section 6 concludes the paper with a brief summary.
2 Temporal Data Model
In our model, a temporal database is modeled by a collection of timevarying relations, each of which is a collection of ordinary relations indexed by mo