Temporal databases: Access structures, search methods, migration strategies, and declustering techniques

Temporal databases maintain the complete history of all the states of a database. This permits users to query the current state of the database, as well as past states, and even future states that are planned to occur. To provide these capabilities and realize the promise of temporal databases, several technical challenges must be first addressed and resolved. One challenge is to develop techniques for storing and searching the very large amounts of data that are often generated by temporal database systems. Another challenge is the effective use of the storage technology that is currently available, such as write-once optical disks and disk arrays.; This dissertation presents an in-depth analysis of several access structures and search methods for temporal databases. A formal characterization of an efficient access structure, the time index, is given. This structure permits efficient searches on temporal data that often overlaps and has a non-uniform distribution. The data structures for the time index are defined and efficient search algorithms for point and interval based operations are described.; The main drawback of the time index is that it requires a large amount of storage. This dissertation presents a temporal incremental access structure, the time index{dollar}sp+,{dollar} which requires less storage and performs better than the time index. Extensive simulation studies are performed in order to compare the storage requirements and search performance of the time index{dollar}sp+{dollar} with that of the time index, the packed R-tree, and the parameterized R-tree.; In addition, an access structure called the monotonic {dollar}Bsp+{dollar}-tree for append-only temporal databases is presented. Comprehensive archiving techniques for the monotonic {dollar}Bsp+{dollar}-tree are provided and search algorithms for magnetic-optical storage media are given.; Finally, the issue of declustering temporal access structures for a single processor multiple independent disk architecture is addressed. Several disk allocation schemes are described for distributing temporal access structures on multiple disks in order to increase concurrent disk accesses in response to point and range queries. The techniques proposed are validated through extensive simulation studies.