DocumentCode :
1306541
Title :
An efficient multiversion access structure
Author :
Varman, Peter J. ; Verma, Rakesh M.
Volume :
9
Issue :
3
fYear :
1997
Firstpage :
391
Lastpage :
409
Abstract :
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
Keywords :
configuration management; query processing; transaction processing; key history search; key range search; multiversion access structure; optimal storage; query performance; query times; snapshot query; storage utilization; time range view; transaction-time database; update times; Data structures; History; Indexing; Information retrieval; Manufacturing; Multidimensional systems; Storage automation; Transaction databases;
fLanguage :
English
Journal_Title :
Knowledge and Data Engineering, IEEE Transactions on
Publisher :
ieee
ISSN :
1041-4347
Type :
jour
DOI :
10.1109/69.599929
Filename :
599929
Link To Document :
بازگشت