Accessing multiversion data in database transactions

Thumbnail Image

Files

isbn9789526033600.pdf (1.52 MB)

URL

Journal Title

Journal ISSN

Volume Title

Aalto-yliopiston teknillinen korkeakoulu | Doctoral thesis (monograph)
Checking the digitized thesis and permission for publishing
Instructions for the author
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2010

Department

Tietotekniikan laitos
Department of Computer Science and Engineering

Major/Subject

Mcode

Degree programme

Language

en

Pages

Verkkokirja (1589 KB, 182 s.)

Series

TKK research reports in computer science and engineering, A, 5/10

Abstract

Many important database applications need to access previous versions of the data set, thus requiring that the data are stored in a multiversion database and indexed with a multiversion index, such as the multiversion B+-tree (MVBT) of Becker et al. The MVBT is optimal, so that any version of the database can be accessed as efficiently as with a single-version B+-tree that is used to index only the data items of that version, but it cannot be used in a full-fledged database system because it follows a single-update model, and the update cannot be rolled back. We have redesigned the MVBT index so that a single multi-action updating transaction can operate on the index structure concurrently with multiple concurrent read-only transactions. Data items created by the transaction become part of the same version, and the transaction can roll back. We call this structure the transactional MVBT (TMVBT). The TMVBT index remains optimal even in the presence of logical key deletions. Even though deletions in a multiversion index must not physically delete the history of the data items, queries and range scans can become more efficient, if the leaf pages of the index structure are merged to retain optimality. For the general transactional setting with multiple updating transactions, we propose a multiversion database structure called the concurrent MVBT (CMVBT), which stores the updates of active transactions in a separate main-memory-resident versioned B+-tree index. A system maintenance transaction is periodically run to apply the updates of committed transactions into the TMVBT index. We show how multiple updating transactions can operate on the CMVBT index concurrently, and our recovery algorithm is based on the standard ARIES recovery algorithm. We prove that the TMVBT index is asymptotically optimal, and show that the performance of the CMVBT index in general transaction processing is on par with the performance of the time-split B+-tree (TSB-tree) of Lomet and Salzberg. The TSB-tree does not merge leaf pages and is therefore not optimal if logical data-item deletions are allowed. Our experiments show that the CMVBT outperforms the TSB-tree with range queries in the presence of deletions.

Description

Supervising professor

Soisalon-Soininen, Eljas, Prof.

Thesis advisor

Sippu, Seppo, Prof.

Keywords

temporal database, multiversion data, index structure, concurrency control, recovery

Other note

Citation

Permanent link to this item

https://urn.fi/URN:ISBN:978-952-60-3360-0

Collections

[diss] Perustieteiden korkeakoulu / SCI