Accessing multiversion data in database transactions

dc.contributorAalto Universityen
dc.contributor.advisorSippu, Seppo, Prof.
dc.contributor.authorHaapasalo, Tuukka
dc.contributor.departmentTietotekniikan laitosfi
dc.contributor.departmentDepartment of Computer Science and Engineeringen
dc.contributor.schoolAalto-yliopiston teknillinen korkeakoulufi
dc.contributor.supervisorSoisalon-Soininen, Eljas, Prof.
dc.description.abstractMany 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.extentVerkkokirja (1589 KB, 182 s.)
dc.identifier.isbn978-952-60-3360-0 (electronic)
dc.identifier.isbn978-952-60-3359-4 (printed)#8195;
dc.publisherAalto-yliopiston teknillinen korkeakouluen
dc.relation.ispartofseriesTKK research reports in computer science and engineering, A, 5/10en
dc.subject.keywordtemporal databaseen
dc.subject.keywordmultiversion dataen
dc.subject.keywordindex structureen
dc.subject.keywordconcurrency controlen
dc.subject.otherComputer science
dc.titleAccessing multiversion data in database transactionsen
dc.typeG4 Monografiaväitöskirjafi
dc.type.ontasotVäitöskirja (monografia)fi
dc.type.ontasotDoctoral dissertation (monograph)en
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
1.52 MB
Adobe Portable Document Format