Search

External dynamic hashing has been used in traditional database systems as a fast method for answering membership queries. Given a dynamic set S of objects, a membership query asks whether an object with identity k is in (the most current state of) S. This paper addresses the more general problem of Temporal Hashing. In this setting, changes to the dynamic set are timestamped and the membership query has a temporal predicate, as in: 'Find whether object with identity k was in set S at time t.' We present an efficient solution for this problem that takes an ephemeral hashing scheme and makes it partially persistent. Our solution, also termed partially persistent hashing, uses linear space on the total number of changes in the evolution of set S and has a small (O([log.sub.B](n/B))) query overhead. An experimental comparison of partially persistent hashing with various straightforward approaches (like external linear hashing, the Multiversion B-Tree, and the [R.sup.*]-tree) shows that it provides the faster membership query response time. Partially persistent hashing should be seen as an extension of traditional external dynamic hashing in a temporal environment. It is independent of the ephemeral dynamic hashing scheme used; while the paper concentrates on linear hashing, the methodology applies to other dynamic hashing schemes as well. Index Terms--Hashing, temporal databases, transaction time, access methods, data structures.

By supporting the valid and transaction time dimensions, bitemporal databases represent reality more accurately than conventional databases. In this paper, we examine the issues involved in designing efficient access methods for bitemporal databases, and propose the partial-persistence and the double-tree methodologies. The partial-persistence methodology reduces bitemporal queries to partial persistence problems for which an efficient access method is then designed. The double-tree methodology 'sees' each bitemporal data object as consisting of two intervals (a valid-time and a transaction-time interval) and divides objects into two categories according to whether the right endpoint of the transaction time interval is already known. A common characteristic of both methodologies is that they take into account the properties of each time dimension. Their performance is compared with a straightforward approach that 'sees' the intervals associated with a bitemporal object as composing one rectangle, which is stored in a single multidimensional access method. Given that some limited additional space is available, our experimental results show that the partial-persistence methodology provides the best overall performance, especially for transaction timeslice queries. For those applications that require ready, off-the-shelf, access methods, the double-tree methodology is a good alternative. Index Terms - Bitemporal databases, access methods, transaction-time, valid-time, data structures.

Efficiently managing the history of a time-evolving system is one of the central problems in many database environments, like database systems that incorporate versioning, or object-oriented databases that implicitly or explicitly maintain the history of persistent objects. In this paper we propose algorithms that reconstruct past states of an evolving system for two general cases, i.e., when the system's state is represented by a set or by a hierarchy (a forest of trees). Sets are widely used as a canonical form of representing information in databases or program states. For more complex applications, like schema evolution in object-oriented databases, it becomes necessary to manage the history of data structures that have the form of forests or even graphs. The proposed algorithms use minimal space (proportional to the number of changes occurring in the evolution) and have the advantage of being on-line (in the amortized sense). Any past system state s(t) is reconstructed in time O([abolute value of s(t)] + loglogT), where [absolute value s(t)] is the size of the answer and T is the maximal evolution time. For all practical cases the loglogT factor is a constant, therefore our algorithms provide almost random access to any past system state. Moreover, we show that the presented algorithms are optimal among all algorithms that use space linear in the number of changes in the system's evolution. Index Terms - Temporal databases, historical queries, access methods, data-structures, versioning.