INDEXING TEMPORAL DATA USING EXISTING B-TREES()

Research in temporal databases has largely focused on extensions of ex isting data models for the proper handling of temporal information. On e approach is to store temporal data on existing DBMS and build some n ew indexes to provide support for the efficient retrieval of temporal data. This paper describes mapping strategies to linearize the data su ch that existing B+-trees can be used directly. With such an implement ation, a temporal relation is mapped to points in a multi-dimensional space, with each time interval being translated to a two-dimensional c oordinate, and a temporal selection operation is constructed as a spat ial search operation. The proposed approach has two advantages. First, mapping a temporal relation to a multi-dimensional space provides a u niform framework for dealing with temporal queries involving transacti on and valid time, as well as other non-temporal attributes. Second, l inearization of the multi-dimensional search space allows classical in dexing methods (such as the B+-tree) to be used; this means that index support for temporal selection can be accomplished without modificati on to the underlying storage components of the DBMS. Both analytical a nd simulation study show that the proposed indexing scheme is more eff icient than the time index in both its disk utilization and access tim e.