concurrency control and recovery for multiversion database structures
In modern database applications access to historical versions of the dataset is becoming increasingly important. Several multiversion structures with corresponding concurrency-control and recovery algorithms exist, but none of these have optimal logarithmic execution times for all actions in all situations. The time-split B + tree by Lomet et al. (TSBT) is used in the Immortal DB database prototype, but it does not consolidate pages. The multiversion B + tree by Becker et al. (MVBT) is an asymptotically optimal multiversion structure that guarantees logarithmic execution times for all actions, but it lacks concurrency-control algorithms. It is our plan to design and implement several multiversion index structures with full concurrency-control and ARIES-based recovery algorithms and evaluate their performance. We will experiment with using a multiversion B + tree as a historical storage, to which the updates of committed transactions are moved one at a time from a separate B + tree. We will also consider using an optimized R-tree to store the multiversion data as two-dimensional line segments. To evaluate these solutions, we will also implement a straight-forward B + tree based solution that stores the different versions of a data item consecutively; and a solution based on the existing time-split B + tree. We expect that the solution that uses a multiversion B + tree will be the most efficient.
concurrency recovery transactions versioned data access methods physical design