Accessing multiversion data in database transactions

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Sippu, Seppo, Prof. Haapasalo, Tuukka 2012-08-28T11:40:58Z 2012-08-28T11:40:58Z 2010
dc.identifier.isbn 978-952-60-3360-0 (electronic)
dc.identifier.isbn 978-952-60-3359-4 (printed) #8195;
dc.identifier.issn 1797-6936
dc.description.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. en
dc.format.extent Verkkokirja (1589 KB, 182 s.)
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher Aalto-yliopiston teknillinen korkeakoulu en
dc.relation.ispartofseries TKK research reports in computer science and engineering, A, 5/10 en
dc.subject.other Computer science
dc.title Accessing multiversion data in database transactions en
dc.type G4 Monografiaväitöskirja fi Aalto-yliopiston teknillinen korkeakoulu fi
dc.contributor.department Tietotekniikan laitos fi
dc.contributor.department Department of Computer Science and Engineering en
dc.subject.keyword temporal database en
dc.subject.keyword multiversion data en
dc.subject.keyword index structure en
dc.subject.keyword concurrency control en
dc.subject.keyword recovery en
dc.identifier.urn URN:ISBN:978-952-60-3360-0
dc.type.dcmitype text en
dc.type.ontasot Väitöskirja (monografia) fi
dc.type.ontasot Doctoral dissertation (monograph) en
dc.contributor.supervisor Soisalon-Soininen, Eljas, Prof.

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive

Advanced Search

article-iconSubmit a publication