A Recursive Temporal Algebra and Temporal Completeness

Mehmet A. Orgun

Department of Computing

Macquarie University

Sydney, NSW 2109, Australia

http://www-comp.mpce.mq.edu.au/?mehmet

Abstract
This paper introduces a recursive temporal algebra based on temporal semantics 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. 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 time-varying 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 SQL-type query languages have also been proposed [1, 12, 15]. For example, Houtsma and Apers [12] employ a ?-calculus with a fixed-point 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 well-defined 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 time-varying 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 time-varying relations, each of which is a collection of ordinary relations indexed by mo-