ERCIM News No.21 - April 1995 - CNR

Temporal Databases

by Cristina De Castro, Fabio Grandi, Maria Rita Scalas and Paolo Tiberio

Temporal databases have become a consolidated research field over the last decade. Several projects under way at the Centro di Studio per l'Interazione Operatore-Calcolatore (CIOC-CNR) Bologna, focus on different aspects of temporal databases, ranging from logical data models and query languages to storage and access structures.

The management of the temporal dimension of data is an important requirement of advanced database applications in which extensions of data models and query languages to include time are needed. Design solutions are also needed to provide physical support for efficient storage and query processing.

Data Models and Query Languages

The CIOC group took part in the activities preceding, concerning and following the ARPA/NSF International Workshop on an Infrastructure for Temporal Databases, held in Arlington (Texas) in 1993. The aim of the workshop was to establish a common infrastructure for the discipline and to develop a consensus report to be used as a foundation for further research, development and standardization.

In particular, CIOC took part in the definition of a consensus glossary of concepts and in the compilation of a semantic benchmark for temporal languages. The CIOC group contributed to the formalization of the concept of "history", consisting in the evolution of a database object (e.g. an entity, a record, a schema, etc.) and composed of a set of temporal versions. This also lead to the introduction of the notion of history-oriented databases, in which histories are considered as first-class objects. As a consequence, history-oriented query languages must provide two kinds of range variables, one to denote single versions (flat tuples) and the other to denote full histories (set of tuples), as first proposed for the HoTQuel language. A history-oriented extension of SQL, along with a prototype implementation, is also currently under development.

Fabio Grandi also participated in the working group for the standardization of data models and query languages and subsequently joined the international TSQL2 language design committee (the committee released a proposal for a standard temporal extension of SQL-92 in September 1994).

Semantic Interoperability and Schema Evolution

Other problems have been studied within the framework of national projects on temporal data management supported by CNR, in which several major Italian universities have participated. Solutions for the interoperability of temporal data based on different temporal models (i.e. including different time dimensions) have been outlined. These solutions are based on the introduction of temporal conversion functions, which can be used for translating heterogeneous data into a common temporal format. The temporal conversion functions have also been used to support schema evolution (without data loss) in the presence of a schema change involving the addition or elimination of a temporal dimension. Several implementation solutions (single-pool versus multi-pool, synchronous versus asynchronous versioning) for the physical support of schema evolution have also been proposed and their semantic and efficiency properties investigated.

Access and Storage Strucures

Another line of activity has concerned the design of physical structures for indexing temporal data, that are amenable to support efficient query processing. An adaptive, modular and symmetric access and storage structure for transaction-time (rollback) databases, called the KT-Index, has been developed. The KT-Index is based on the data clustering techniques proposed by Lomet and Salzberg for their Time-Split B-Tree. The KT-Index modularity provides fast access to current data, support for vacuuming and data migration along a storage hierachy according to aging. An adaptive split policy is introduced in order to limit the data duplication intrinsic to data indexing along the time dimension. The performance of the KT-Index, implemented on a personal computer, is currently under evaluation by extensive simulations.

A Possible Scenario for Multitemporal Interoperability

Current Activities

Present activities include the design of a history-oriented temporal SQL extension (HoT-SQL), the study of a multitemporal relational algebra and query language that generalizes and completes the study of temporal conversion functions, the performance evaluation of the KT-Index plus the design of new access structures (to include valid-time and bitemporal data), and the development of methodologies for efficient temporal query processing.

Please contact:
Fabio Grandi - CIOC-CNR
Tel: +39 (0)51 644 3555
Fax: +39 (051) 644 3540
E-mail: fgrandi@deis.unibo.it

return to the contents page