Time index access structure for temporal databases having concurrent multiple versions

A time index for temporal databases is provided which enables the retrieval of database object versions that are valid during specified time periods. Unlike prior access and retrieval structures, the present index is based on objects whose search values are time intervals rather than time points. A series of ordered indexing points is defined by the start and end of object version intervals and these points are used to build an indexing structure, which may take the form of a B.sup.+ -tree. Each leaf node entry of the B.sup.+ -tree represents an indexing point and has an associated bucket of pointers which identify all object versions that are valid at that time. Storage space is reduced by including only incremental change indicators in the buckets of non-leading leaf entries and calculating needed pointers from such indicators. The time index may be employed in multi-level structures with attribute indexes to greatly improve the efficiency of temporal search operations, such as aggregate functions and temporal selection, as well WHEN and JOIN operators.

BACKGROUND OF THE INVENTION 
Research in temporal computer databases has been mostly concerned with 
defining data models and operations that incorporate the time dimension. 
For example, extensions to the relational data model and its operations 
for handling temporal data have been discussed by Snodgrass and Ahn (R. 
Snodgrass and I. Ahn, "A Taxonomy Of Time In Databases", ACM SIGMOD 
Conference, May 1985) and Gadia and Yeung (S. Gadia and C. Yeung, "A 
Generalized Model For A Temporal Relational Database", ACM SIGMOD 
Conference, June 1988). In addition, some work has been presented by Segev 
and Shoshani (A. Segev and A. Shoshani, "Logical Modeling Of Temporal 
Data", ACM SIGMOD Conference, June 1987) and Elmasri and Wuu (R. Elmasri 
and G. Wuu, "A Temporal Model And Language For ER Databases", IEEE Data 
Engineering Conference, February 1990) defining temporal extensions to 
conceptual data models and query languages. Such temporal data models 
define .powerful operations for specifying complex temporal queries. 
Although there has been some research in the area of defining storage 
structures and access paths for temporal data, for example by Lure (V. 
Lum, "Design Dbms Support For The Temporal Dimension", ACM SIGMOD 
Conference, April 1984), Rotem and Segev (D. Rotem and A. Segev, "Physical 
Organization Of Temporal Data", Proceedings Of IEEE Data Engineering 
Conference, 1987), and Kolovson and Stonebraker (C. Kolovson and M. 
Stonebraker, "Indexing Techniques For Historical Databases", Proceedings 
Of IEEE Data Engineering Conference, February 1989), these works do not 
provide indexing schemes for supporting high-level temporal operators such 
as described by Gadia et al. and Elmasri et al., cited above. 
Storage techniques for temporal data, such as proposed by Lum, index or 
link the versions of each individual object separately. In order to 
retrieve such object versions that are valid during a certain time period, 
it has been necessary to first locate the current version of each object, 
and then search through the version index (or list) of each object 
separately. A method proposed by Rotem et al., noted above, allows a 
search based on time using a multi-dimensional partitioned file, in which 
one of the dimensions is the time dimension. However, in such a scheme 
temporal data items are associated with a time point rather than a time 
interval, and hence it is not useful when a search involving time 
intervals is required. 
In order to conduct an efficient computer search operation in a temporal 
database, some effective form of indexing is required. However, since 
conventional indexing schemes assume that there is a total ordering on the 
index search values, the properties of the temporal dimension make it 
difficult, for a number of reasons to use traditional indexing techniques 
for time indexing. First, the index search values, i.e the valid.sub.-- 
time attribute, are intervals rather than points, because each version of 
an object is typically valid during a time interval [t.sub.1,t.sub.2 ], 
and the valid.sub.-- time intervals of various object versions will 
overlap in arbitrary ways. Because one cannot define a total ordering on 
the interval values, a conventional indexing scheme cannot be used. 
Second, because of the nature of temporal databases, most updates occur in 
an append mode, since past versions are kept in the database. Hence, 
deletions of object versions do not generally occur, and insertions of new 
object versions occur mostly in increasing time value. In addition, the 
search condition typically specifies the retrieval of versions that are 
valid during a particular time interval. 
Although the interval-based search problem is similar in many respects to 
the k-dimensional spatial search problem, the various index methods 
proposed for k-dimensional spatial search, for example by Ooi et al. (K. 
Ooi, B. McDonell, and R. Sack-Davis, "Spatial Kd-tree: Indexing Mechanism 
For Spatial Database", IEEE COMPSAC 87, 1987), are not suitable for the 
time dimension. While these spatial index methods might be adapted to a 
single dimension, for the most part they support spatial search for 
two-dimensional objects in CAD or geographical database applications. The 
index algorithms, such as suggested by Ooi et al., use the concept of a 
region to index spatial objects, wherein a search space is divided into 
regions which may overlap with each other, and a sub-tree in an index tree 
contains pointers to all spatial objects located in a region. Since 
spatial objects can overlap each other, handling the boundary conditions 
between regions is quite complex in these algorithms. In temporal computer 
databases there can be a much higher degree of overlapping between the 
valid.sub.-- time intervals of object versions. For instance, a large 
number of long or short intervals can exist at a particular time point. 
Furthermore, the search space is continuously expanding whereas most 
spatial indexing techniques assume a fixed search space. In addition, 
temporal objects are appended mostly in increasing time value, making it 
difficult to maintain tree balance for traditional indexing trees. Thus, 
because of these added requirements of the temporal over the spatial 
search, the spatial index algorithms are not suitable for temporal data 
even where they are directly adapted from two dimensions to a single 
dimension. 
SUMMARY OF THE INVENTION 
The present invention provides a time indexing procedure which is 
particularly useful with object versioning structured temporal computer 
databases for the efficient processing of temporal operations requiring 
reference to time intervals. For example, where it is desired to retrieve 
object versions that are valid during a given time period, e.g. the names 
of all employees who worked for the company during 1985, this time index 
will lead directly to the desired versions, i.e. the names, without 
requiring the search of a version index for each individual object, i.e. 
employee, separately. In addition, the time index may be used to 
efficiently process temporal aggregate functions, as well as temporal 
WHEN, SELECT, and JOIN operators of Gadia et al., and temporal projection 
suggested in the earlier-noted work of Elmasri et al. 
In a temporal database, the time dimension is usually represented, as 
described in Gadia et al., using the concepts of discrete time points and 
time intervals. A time interval, denoted by [t.sub.1,t.sub.2 ], is defined 
as a set of time instants (points) on a scale of consecutive, regularly 
occurring time points, where t.sub.1 is the first time instant and t.sub.2 
is the last time instant of the interval. The time dimension is 
represented as a time interval [0,now], where 0 represents the starting 
time of a database mini-world application, and now is the current time, 
which is continuously expanding. The time interval between consecutive 
time points of a time scale may be adjusted, based on the granularity of 
the application, to be equal to months, days, hours, minutes, seconds, or 
any other suitable time unit. A single discrete time point t is usually 
represented as an interval [t,t], or simply [t]. 
The present time index may be effectively understood when viewed in 
connection with an underlying record-based storage system which supports 
object versioning, i.e. wherein records are used to store versions of 
objects. In addition to the regular record attributes, A.sub.i, each 
record will have an interval attribute, valid.sub.-- time, consisting of 
two sub-attributes t.sub.s (valid start time) and t.sub.e (valid end 
time). The valid.sub.-- time attribute of an object version is a time 
interval during which the version is valid. In object versioning, a 
record, r, with r.valid.sub.-- time.t.sub.e =now is considered to be the 
current version of some object. However, numerous past versions of the 
object may also exist. These versions of an object are linked to the 
current version and may be recovered through the use of various known 
techniques, such as reverse chaining, clustering, or accession lists, 
which provide access to versions of a particular object through the 
current version of the object. Similarly, the current version of an object 
can be located from any other version; for example, by using a pointer to 
a linked list header, which in turn points to the current version. 
An interval-based search operation over an object versioning record-based 
storage system, TDB, which consists of a collection of object versions, 
i.e. TDB={e.sub.1,e.sub.2, . . . ,e.sub.n }, may be formally defined as 
follows: 
Given a Search Interval, I.sub.S =[t.sub.a,t.sub.b ], find the following 
set of versions: 
EQU S(I.sub.S)={e.sub.j TDB.vertline.(e.sub.j.valid.sub.-- time 
.andgate.I.sub.S).apprxeq.O}. 
A simple but inefficient implementation of this search operation would be 
to sequentially access the entire storage system, TDB, using linear 
search, and retrieve those records whose valid.sub.-- time intersects with 
I.sub.S. Such a search would require O(N*M) accesses to the storage 
system, where N is the number of objects and M is the maximal number of 
versions per object. 0n the other hand, utilizing the present time index, 
the search would be efficiently completed with a fraction of the record 
accesses. 
In structuring such a time index in accordance with the instant invention, 
a set of linearly ordered indexing points is created and maintained on the 
time dimension. An indexing point is specified for each time point at 
which the database changes with respect to a version of an object, i.e. a 
time point where a new version begins or a time point immediately 
following a version termination. This property, PR 1, of the set of all 
indexing points for the temporal database may be formally defined as 
follows: 
##EQU1## 
Since all the indexing points t.sub.i in BP can now be totally ordered, a 
conventional indexing structure (B-tree, ISAM, or the like), such as the 
B.sup.+ -tree described by Comer (D. Comer, "The Ubiquitous B-Tree", ACM 
Computing Surveys, 11(12), June 1979), is employed to index these points. 
In the present index structure, each leaf node entry of the B.sup.+ -tree 
at point t.sub.i is of the form, [t.sub.i,bucket], where bucket is a 
pointer to a bucket containing pointers to object versions. Each bucket, B 
(t.sub.i), thus contains pointers to all object versions whose 
valid.sub.-- time contains the interval [t.sub.i,t.sub.i.sup.+ -1]. This 
property, PR2, can be formally specified as follows: 
##EQU2## 
As a result, all object versions that are valid at a particular indexing 
point can be retrieved directly by means of the bucket of pointers, 
thereby providing the efficiency in time interval processing that has not 
previously been available.

DESCRIPTION OF THE INVENTION 
The manner of designating indexing points for the time index of the present 
invention may be readily seen by reference to the chart of FIG. 1 which 
illustrates the temporal data shown in the following EMPLOYEE table: 
TABLE 1 
______________________________________ 
EMPLOYEE Table 
Name Dept Valid.sub.-- Time 
______________________________________ 
emp1 A [0,3] 
emp1 B [4,now] 
emp2 B [0,5] 
emp3 C [0,7] 
emp3 A [8,9] 
emp4 C [2,3] 
emp4 A [8,now] 
emp5 B [10,now] 
emp6 C [12,now] 
emp7 C [11,now] 
______________________________________ 
In FIG. 1, the intervals of valid.sub.-- time during which each of the 
employees (emp.sub.1,emp.sub.2, . . . ,emp.sub.7) worked in a department 
is shown by the horizontal lines spanning the respective intervals on the 
time scale. Each designation, e.sub.ij, refers to version, j, of object, 
e.sub.i. For example, the second employment interval, or version, 102 for 
employee, emp.sub.3, extends from time point 8 to time point 9, i.e. 
valid.sub.-- time is [8,9]. However, employee version, e.sub.32, remains 
unchanged over this interval and it is only at the following time point 10 
that there begins a changed version. As noted in the above property 
definition, PR1, the term, e.sub.j.valid.sub.-- time.t.sub.e +1, 
designates time point 10 as an index point 104. Similarly, time point 106 
2 is an index point 106, since version e.sub.41 starts at 2; and time 
point 6 is an index point 108, since version e.sub.21 terminates at 5. 
Thus there exist nine indexing points in BP for all employee versions in 
the database of Table 1, i.e. BP={0,2,4,6,8,10,11,12,now}. 
In the ensuing further description of the present index structure, the 
following notations will be employed. Letting t.sub.j be an arbitrary time 
point, which may or may not be a point in BP, t.sub.j.sup.- 
(t.sub.j.sup.+) is defined to be the point in BP such that t.sub.j.sup.- 
&lt;t.sub.j (t.sub.j &lt;t.sub.j.sup.+) and there does not exist a point t.sub.m 
BP such that t.sub.j.sup.- &lt;t.sub.m &lt;t.sub.j (t.sub.j &lt;t.sub.m 
&lt;t.sub.j.sup.+). In other words, t.sub.j.sup.- (t.sub.j.sup.+) is the 
point in BP that is immediately before (after) t.sub.j. Also, 
t.sub.j.sup.-= is defined as follows: 
1. If there exists a point t.sub.k BP such that t.sub.j =t.sub.k, then 
t.sub.j.sup.-= =t.sub.k. 
2. Otherwise, t.sub.j.sup.-= =t.sub.t.sub.j.sup.-. 
In FIG. 2 there is depicted a B.sup.+ -tree 200 which indexes the BP set of 
indexing points of the EMPLOYEE versions shown in FIG. 1. The B.sup.+ 
-tree shown for this simple example is a basic first order tree in which 
each node contains up to two search values and three pointers. Higher 
order trees could, of course, be used for more extensive databases. As can 
be seen in FIG. 2, each of the entries 202, 202, . . . , 209 of the 
B.sup.+ -tree leaf nodes 210 is an indexing point from FIG. 1 and has a 
pointer 211, 212, . . . , 219 to a bucket 221, 222, . . . , 229 which 
contains pointers 221', 222', . . . , to all object versions having a 
valid.sub.-- time represented by that indexing point. The bucket at the 
leaf entry 203 for search indexing point 4, for instance, contains the 
pointers 223, to object versions, {e.sub.12,e.sub.21,e.sub.31 }, which may 
be seen in FIG. 1 to have a valid.sub.-- time at index point 4. Thus, the 
specification given earlier for the property, (PR2), of a bucket indeed 
holds: 
##EQU3## 
In a real temporal database, there would normally be a large number of 
object versions in each bucket, and many of those would be repeated from 
the previous bucket. For example, in FIG. 2 the object version, e.sub.12, 
appears in multiple consecutive buckets 223, . . . , 229, since its 
valid.sub.-- time spans indexing points, [4,now]. To reduce this 
redundancy and make the time index more practical, an incremental scheme 
is used in another embodiment of the invention. Rather than keeping a full 
bucket for each time point entry in BP, a full bucket is only kept for the 
first entry of each leaf node. Since most versions will continue to be 
valid during the next indexing interval, only the incremental changes are 
retained in the buckets of the subsequent entries in a leaf node. The 
incremental bucket B (t.sub.i) for a non-leading entry at time point 
t.sub.i can be computed as follows: 
EQU B(t.sub.i)=B(t.sub.1).orgate.(.orgate..sub.t.sbsb.j.sub. 
BP,t.sbsb.1.sub.&lt;t.sbsb.j.sub..ltoreq.t.sbsb.i 
SA(t.sub.j))-(.orgate..sub.t.sbsb.j.sub. 
BP,t.sbsb.1.sub.&lt;t.sbsb.j.sub..ltoreq.t.sub.i SE(t.sub.j)), 
where B(t.sub.1) is the bucket for the leading entry in the leaf node at 
which point t.sub.i is located, SA(t.sub.j) is the set of object versions 
whose start time is t.sub.j, and SE(t.sub.j) is the set of object versions 
whose end time is t.sub.j -1. 
This variation in a B.sup.+ -tree structure is shown in FIG. 3 where, for 
example, the entry at point 10 stores {-e.sub.32, +e.sub.51 } in its 
incremental bucket 326, indicating that e.sub.51 starts at point 10 and 
e.sub.32 terminates at the point immediately before point 10. The complete 
array of pointers at any non-leading bucket may be readily computed from 
the previous full and incremental buckets. 
One application of the indexing method of the present invention is in a 
search on the B.sup.+ -tree to retrieve, for example, all object versions 
that are valid at some point during a search interval [t.sub.a,t.sub.b ]. 
Conducting such search for a time interval, I.sub.S =[t.sub.a,t.sub.b ], 
entails a B.sup.+ -tree range search to find 
EQU PI(I.sub.S)={t.sub.i P.vertline.t.sub.a .ltoreq.t.sub.i .ltoreq.t.sub.b 
}.orgate.{t.sub.a.sup.-= } 
and a computation to determine the resulting set 
EQU T(I.sub.S)=.orgate..sub.t.sbsb.i.sub. P1 B(T.sub.i) 
In this manner the index is searched to find t.sub.a.sup.-=, the largest 
indexing point that is less than or equal to t.sub.a, and then the buckets 
are determined for all indexing points between t.sub.a.sup.-= and t.sub.b 
inclusive. The result of the search is then the union of these buckets. In 
order to ensure a continued proper index function whenever the temporal 
database is revised, the index structure must be updated to maintain the 
above-noted properties, PR1 and PR2. Upon the insertion of a new object 
version, e.sub.k, the index is revised as follows: 
______________________________________ 
Insert(e.sub.k) 
begin 
t.sub.a .rarw. e.sub.k.valid.sub.-- time.t.sub.s ; 
t.sub.b .rarw. e.sub.k.valid.sub.-- time.t.sub.e + 1; 
search the B.sup.+ -tree for t.sub.a ; 
if ( found) then 
insert t.sub.a in the B.sup.+ -tree; 
if the entry at t.sub.a is not a leading entry in a leaf node 
add e.sub.k into SA (t.sub.a); 
search the B.sup.+ -tree for t.sub.b ; 
if ( found) then 
insert t.sub.b in the B.sup.+ -tree; 
if the entry at t.sub.b is not a leading entry in a leaf node 
add e.sub.k into SE(t.sub.b); 
for each leading entry t.sub.l of a leaf node where t.sub.a .ltoreq. 
t.sub.l .ltoreq. t.sub.b 
add e.sub.k in B(t.sub.l); 
end 
______________________________________ 
Although, in general, deletion of an object version is not encountered in 
an append-only temporal database, there may be occasions when a deletion 
does arise, as in the correction of an error. Maintenance of the index 
structure would then be effected as follows: 
______________________________________ 
Delete(e.sub.k) 
begin 
t.sub.a .rarw. e.sub.k.valid.sub.-- time.t.sub.s ; 
t.sub.b .rarw. e.sub.k.valid.sub.-- time.t.sub.e + 1; 
search the B.sup.+ -tree for t.sub.a ; 
if the entry at t.sub.a is not a leading entry in a leaf node 
remove e.sub.k from SA(t.sub.a); 
search the B.sup.+ -tree for t.sub.b ; 
if the entry at t.sub.b is not a leading entry in a leaf node 
remove e.sub.k from SE(t.sub.b); 
for each leading entry t.sub.l of a leaf node where t.sub.a .ltoreq. 
t.sub.l .ltoreq. t.sub.b 
remove e.sub.k from B(t.sub.l); 
end 
______________________________________ 
The time index can be used to efficiently process the WHEN operator with a 
constant projection time interval. An example of the type of query is: 
List the salary history for all employees during the time interval [4,5]. 
The result of such a query can be directly retrieved using the time index 
on the EMPLOYEE object versions shown in FIG. 3. A simple query such as 
the one given above would be very expensive to process using prior basic 
access structures which provide access to versions only through the 
current version and have no index based on time. The present time index, 
however, provides the capability of retrieving directly only those 
versions that are valid during a particular time period, without the need 
to search through all object versions in the database. 
The present time index may also be used to efficiently process aggregate 
functions at different time points or intervals. In non-temporal 
conventional database, the aggregate functions, such as COUNT, EXISTS, 
SUM, AVERAGE, MIN, and MAX are applied to sets of objects or attribute 
values of sets of objects. For instance, they can be used to count the 
current number of employees or compute the current average of employees' 
salaries. In temporal databases, an aggregate function is applied to a set 
of temporal entities over an interval. For instance, the query, "GET COUNT 
EMPLOYEE: [3,8]", should count the number of employees at each time point 
during the time interval [3,8]. The result of the temporal COUNT function 
is a function mapping from each time point in [3,8] to an integer number 
that is the number of employees at that time point. Thus, the above query 
is evaluated to the following result if applied to the database shown in 
Table 1: 
EQU {[3].fwdarw.4, [4,5].fwdarw.3, [6,7].fwdarw.2, [8].fwdarw.3} 
The time index can be readily used to process such aggregate functions. 
With I.sub.S being the interval over which the temporal aggregate function 
is evaluated, the query performs a range search to find PI(I.sub.S). Each 
point in PI(I.sub.S) represents a point of state change in the database. 
As has been earlier noted, the database mini-world changes its state at 
each indexing point and stays in the same state until the next change 
point. Therefore the aggregate function only needs to be evaluated for the 
points in PI(I.sub.S). The query is evaluated by applying the function on 
the bucket of object versions at each point. If the incremental index 
shown in FIG. 3 is used, the running count from the previous change point 
is updated at the current change point by adding the number of new 
versions and subtracting the number of removed versions at the change 
point. Similar techniques can be used for other aggregate functions that 
must be computed at various points over a time interval. 
The indexing scheme can also be extended to support other important 
temporal operators, such as temporal selection. The specification of a 
temporal selection operator is more complex than that of a non-temporal 
selection. In a non-temporal database, a common form of a selection 
condition is to compare an attribute with a constant or with a range, for 
example, EMPLOYEE.Dept=B or 20K&lt;EMPLOYEE.Salary&lt;30K. Such conditions 
evaluate to a boolean value for each object. In a temporal database, 
however, a .theta. comparison condition evaluates to a function which maps 
from [0,now] to a boolean value. For instance, the condition, 
EMPLOYEE.Dept=B, when evaluated on emp.sub.1 of FIG. 1, will have the 
following result: 
EQU {[0,3].fwdarw.FALSE, [4,now].fwdarw.TRUE} 
This means that the condition is FALSE during [0,3] and TRUE during 
[4,now]. A complete temporal selection should specify not only a condition 
but also when the condition holds. For example, to select employees who 
had worked in department B during the time period [3,4], a SELECT 
condition should be specified as: 
EQU [EMPLOYEE.Dept=B].orgate.[3,4].noteq.O 
The notation [c], where c is a .theta. comparison condition, represents the 
time intervals during which c evaluates to TRUE for each object. A search 
for objects that satisfy such a temporal condition combines selection 
based on a time interval with a selection based on conditions involving 
attribute values. In such a search, the indexing procedure of the present 
invention may be combined with prior indexing methods to derive a 
two-level indexing scheme, such as depicted in FIG. 4. The top-level index 
401 is a common B.sup.+ -tree built on a search attribute; for example, 
the Dept attribute of EMPLOYEE in Table 1. Each leaf node entry 402, 403 
of the top-level index tree includes a value of the search attribute and a 
pointer 404, 405, 406 to a time index 407, 408, 409 structured according 
to the invention. Thus, there is a time index tree for each attribute 
value, although for the sake of clarity only the B.sup.+ -tree 408 for 
Dept. B is shown in FIG. 4. 
In processing the earlier-specified temporal SELECT condition under the 
two-level indexing procedure, the first step is to search the top level 
(the Dept attribute) index for the Dept value, B. This leads to the time 
index for department B, which is then searched for the time interval 
[3,4]. The results of the combined search is the selection of all 
employees who worked in department B during the time interval [3,4]. Note 
that each of these retrieved versions records a partial history of a 
selected object. However, in most temporal data models the SELECT operator 
should return the full set of versions (the entire history) for each 
selected object. Hence, it may be assumed that versions of each object 
will contain back pointers to access the current version as part of the 
basic temporal access structure. Any one of the traditional version access 
structures for object versions (such as clustering, accession list, or 
reverse chaining) can then be used to retrieve the entire version history 
via the current object for the selected objects. 
The time index may also be used to improve the efficiency of certain 
temporal JOIN operations. Most prior join operations are defined for 
joining together a temporal object that is vertically partitioned into 
several relations via time normalization. For example, the attributes of 
temporal EMPLOYEE objects would be partitioned into several relations, 
where each relation would hold the primary key and those attributes 
(usually a single one) that are always modified synchronously. There would 
be a relation for EMP.sub.-- SALARY, one for EMP.sub.-- JOB, and so on. 
The EVENT JOIN is used to build back the temporal objects from the 
partitioned relations. The more general types of JOIN operations that 
correspond to the NATURAL JOIN operation of a non-temporal database could 
also benefit from the efficiencies of the time index. These operations 
join the tuples of two relations based upon an equality join condition on 
attribute values during a common time interval. Hence, the result of the 
join would include an object version whenever two object versions have the 
same join attribute value, and the intersection of the valid time periods 
during which the join attributes are equal is not empty. The valid time of 
the resulting join object would be the intersection of the valid times of 
the two joined object versions. 
As an example of the JOIN application, one might execute the join operation 
to retrieve the time history of employees working for each department 
manager indicated in the following DETMENT database Table: 
TABLE 2 
______________________________________ 
DETMENT Table 
Dept Manager Valid.sub.--Time 
______________________________________ 
A Smith [0,3] 
A Thomas [4,9] 
A Chang [10,now] 
B Cannata [0,6] 
B Martin [7,now] 
C Roberto [0,now] 
______________________________________ 
The effect of the operation is to join each DETMENT object with the 
appropriate EMPLOYEE objects during the time periods when the employees 
worked for that department. Using the described two-level time index on 
the Dept attribute of EMPLOYEE retrieves the employees working for each 
department during specific time periods. The JOIN operation would 
effectively be as follows: 
______________________________________ 
for each DETMENT object do 
begin 
for each version of the DETMENT object to 
begin 
retrieve the Dept value, and valid.sub.-- time 
[t1,t2] of the version; 
use the EMPLOYEE top-level index to locate the 
time index for the Dept value; 
use the time index to retrieve EMPLOYEE versions 
whose time interval overlaps [t1,t2]; 
join each EMPLOYEE version to the DETMENT 
version; 
end; 
end; 
______________________________________ 
The result of this operation would appear as in the following Table 3: 
TABLE 3 
______________________________________ 
EMPLOYEE/MANAGER Table 
Name Dept Valid.sub.-- Time 
Manager 
______________________________________ 
emp1 A [0,3] Smith 
emp1 B [4,6] Cannata 
emp1 B [7,now] Martin 
emp2 B [0,5] Cannata 
emp3 C [0,7] Roberto 
emp3 A [8,9] Chang 
emp4 C [2,3] Roberto 
emp4 A [8,9] Thomas 
emp4 A [10,now] Chang 
emp5 B 110,now] Martin 
emp6 C [12,now] Roberto 
emp7 C [11,now] Roberto 
______________________________________ 
The simple data processing computer arrangement depicted in FIG. 5 is 
typical of database management systems in general and is suitable for 
practice of the present invention. In the usual manner, the system is 
under the control of CPU 502 which, operating over bus 503 and utilizing 
application programs in memory (MEN) 504, directs the addition, deletion, 
search, and retrieval of data located on disks in database (DB) 508. 
Object version updates and searches requested at input/output means (I/O) 
506, e.g., keyboard and CRT monitor screen, follow the time index 
structure set out in the present invention to rapidly and efficiently 
locate, revise, and retrieve the desired data on appropriate disks of DB 
508. 
A simulation of the performance of the time index was conducted in order to 
compare it with traditional temporal access structures. The database had 
1000 objects, and versions where added based on an exponential 
distribution for interarrival time. New versions were assigned to objects 
using a uniform distribution. Objects where also inserted and deleted 
using an exponential distribution with a much larger interarrival time 
than that for version creation. The comparison of the performance of a 
time index was based on traditional access structures of clustering (all 
versions of an object are clustered on disk blocks) and using an accession 
list (each object has an accession list to access its versions based on 
time), and the number of block accesses needed for an interval query was 
calculated (an interval query retrieves all versions .valid during a 
particular time period). The results of the comparison indicated that 
performance for clustering and accession list deteriorates as the number 
of versions per object grows, whereas using a time index maintains a 
uniform performance. 
The temporal selection query employing the two-level time index of FIG. 4 
showed the most dramatic improvement over traditional access structures, 
since only 16 block accesses were needed compared to over 1000 block 
accesses with traditional structures. It was also observed that the 
storage requirements for the two-level index are considerably less than 
for a regular time index because the versions are distributed over many 
time trees resulting in smaller buckets for leading entries in the leaf 
nodes. 
The procedures described and variants suggested herein for the practice of 
this time indexing process and the various other embodiments which will 
become apparent to the skilled artisan in the light of the foregoing 
description are all nonetheless to be included within the scope of the 
present invention as defined by the appended claims.