EFFICIENT MANAGEMENT OF TIME-EVOLVING DATABASES

Efficiently managing the history of a time-evolving system is one of t he central problems in many database environments, like database syste ms that incorporate versioning, or object-oriented databases that impl icitly or explicitly maintain the history of persistent objects. In th is paper we propose algorithms that reconstruct past states of an evol ving system for two general cases, i.e., when the system's state is re presented by a set or by a hierarchy (a forest of trees). Sets are wid ely used as a canonical form of representing information in databases or program states. For more complex applications, like schema evolutio n in object-oriented databases, it becomes necessary to manage the his tory 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 recon structed in time O(Is(t)I + loglogT), where Is(t)I is the size of the answer and T is the maximal evolution time. For all practical cases th e loglogT factor is a constant, therefore our algorithms provide almos t random access to any past system state. Moreover, we show that the p resented algorithms are optimal among all algorithms that use space li near in the number of changes in the system's evolution.