An efficient multiversion access structure

An efficient multiversion access structure for a transaction-time database is presented. Our method requires optimal storage and query times for several important queries and logarithmic update times. Three version operations-inserts, updates, and deletes-are allowed on the current database, while q...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 1997-05, Vol.9 (3), p.391-409
Main Authors: Varman, P.J., Verma, R.M.
Format: Article
Language:English
Subjects:
Applied sciences
Computer science
control theory
systems
Data structures
Exact sciences and technology
History
Indexing
Information retrieval
Information systems. Data bases
Manufacturing
Memory organisation. Data processing
Multidimensional systems
Office automation, teleprocessing
Software
Storage automation
Transaction databases
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An efficient multiversion access structure for a transaction-time database is presented. Our method requires optimal storage and query times for several important queries and logarithmic update times. Three version operations-inserts, updates, and deletes-are allowed on the current database, while queries are allowed on any version, present or past. The following query operations are performed in optimal query time: key range search, key history search, and time range view. The key-range query retrieves all records having keys in a specified key range at a specified time; the key history query retrieves all records with a given key in a specified time range; and the time range view query retrieves all records that were current during a specified time interval. Special cases of these queries include the key search query, which retrieves a particular version of a record, and the snapshot query which reconstructs the database at some past time. To the best of our knowledge no previous multiversion access structure simultaneously supports all these query and version operations within these time and space bounds. The bounds on query operations are worst case per operation, while those for storage space and version operations are (worst-case) amortized over a sequence of version operations. Simulation results show that good storage utilization and query performance is obtained.
ISSN:1041-4347
1558-2191
DOI:10.1109/69.599929