Concurrency control and recovery for multiversion database structures

T.K. Haapasalo, I. M. Jaluta, S. S. Sippu, E. O. Soisalon-Soininen

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


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 straightforward 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.
Translated title of the contributionVersioivien tietokantarakenteiden samanaikaisuuden hallinta ja elvytys
Original languageEnglish
Title of host publicationProceeding of the 2nd PhD workshop on Information and knowledge management, Napa Valley, California, USA, October 30, 2008 : PIKM'08
Number of pages8
Place of PublicationNew York
Publication date30 Oct 2008
ISBN (Print)978-1-60558-257-3, 978-160558387-7
Publication statusPublished - 30 Oct 2008
MoE publication typeA4 Article in conference proceedings
EventConference on Information and Knowledge Management - Napa Valley, United States
Duration: 26 Oct 200830 Oct 2008
Conference number: 17th

Bibliographical note


Fields of Science

  • 113 Computer and information sciences

Cite this