skip to main content
10.1145/1620432.1620441acmconferencesArticle/Chapter ViewAbstractPublication PagesideasConference Proceedingsconference-collections
research-article

Concurrent updating transactions on versioned data

Published: 16 September 2009 Publication History

Abstract

Modern database applications increasingly often require access to historical versions of the database. Storing such multiversion data in a single-version B+ -tree database index is inefficient, especially for key-range queries. In this article, we present an index structure called the concurrent multiversion B+ -tree (CMVBT) for efficiently storing and querying multiversion data.
The CMVBT structure uses an asymptotically optimal transactional multiversion B+ -tree (TMVBT) index as the main data storage. and a separate B+ -tree index called the versioned B+ -tree (VBT) to hold the updates of active transactions. The updates of committed transactions are moved, one transaction at a time, from the VBT into the TMVBT. This organization of two separate index structures allows us to maintain the asymptotic optimality guarantees of the TMVBT even in the presence of concurrent updating transactions.
We provide concurrent algorithms for updating and reading the CMVBT structure. Our CMVBT algorithms can be used with the standard snapshot isolation concurrency-control and ARIES-based recovery algorithms to allow multiple read-only and updating transactions, to operate concurrently on the structure. Transaction rollback is also supported for all updating transactions, either entirely or up to a preset savepoint.

References

[1]
R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1(3):173--189, 1972.
[2]
R. Bayer and M. Schkolnick. Concurrency of operations on B-trees. Acta Informatica, 9(1):1--21, 1977.
[3]
B. Becker, S. Gschwind, T. Ohler, B. Seeger, and P. Widmayer. An asymptotically optimal multiversion B-tree. The VLDB Journal---The International Journal on Very Large Data Bases, 5(4):264--275, 1996.
[4]
H. Berenson, P. Bernstein, J. Gray, J. Melton, E. O'Neil, and P. O'Neil. A critique of ANSI SQL isolation levels. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 1--10. ACM New York, NY, USA, 1995.
[5]
D. Comer. Ubiquitous B-tree. ACM Computing Surveys, 11(2):121--137, 1979.
[6]
J. Gray and A. Reuter. Transaction processing: concepts and techniques. Morgan Kaufmann, 1993.
[7]
T. Haapasalo, I. Jaluta, B. Seeger, S. Sippu, and E. Soisalon-Soininen. Transactions on the multiversion B+ -tree. In Proceedings of the 12th International Conference on Extending Database Technology, pages 1064--1075, 2009.
[8]
T. Haapasalo, I. Jaluta, S. Sippu, and E. Soisalon-Soininen. Concurrency control and recovery for multiversion database structures. In Proceedings of the 2nd PhD Workshop on Information and Knowledge Management, pages 73--80, 2008.
[9]
I. Jaluta, S. Sippu, and E. Soisalon-Soininen. Concurrency control and recovery for balanced B-link trees. The VLDB Journal---The International Journal on Very Large Data Bases, 14(2):257--277, 2005.
[10]
I. Jaluta, S. Sippu, and E. Soisalon-Soininen. B-tree concurrency control and recovery in page-server database systems. ACM Transactions on Database Systems, 31(1):82--132, Mar 2006.
[11]
G. Kollios and V. Tsotras. Hashing methods for temporal data. IEEE Transactions on Knowledge and Data Engineering, 14(4):902--919, 2002.
[12]
S. Lang, J. Driscoll, and J. Jou. Batch insertion for tree structured file organizations---improving differential database representation. Information Systems, 11(2):167--175, 1986.
[13]
P. Lehman and B. Yao. Efficient locking for concurrent operations on B-trees. ACM Transactions on Database Systems, 6(4):650--670, Dec 1981.
[14]
D. Lomet, R. Barga, M. Mokbel, G. Shegalov, R. Wang, and Y. Zhu. Immortal DB: transaction time support for SQL server. In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, pages 939--941, 2005.
[15]
D. Lomet, R. Barga, M. Mokbel, G. Shegalov, R. Wang, and Y. Zhu. Transaction time support inside a database engine. In Proceedings of the 22nd International Conference on Data Engineering, pages 35--46, 2006.
[16]
D. Lomet and B. Salzberg. Access methods for multiversion data. In Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, pages 315--324, 1989.
[17]
D. Lomet and B. Salzberg. The performance of a multiversion access method. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 353--363. ACM New York, NY, USA, 1990.
[18]
C. Mohan. ARIES/IM: an efficient and high concurrency index management method using write-ahead logging. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 371--380. ACM Press New York, NY, USA, 1992.
[19]
C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh, and P. Schwarz. ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging. ACM Transactions on Database Systems, 17(1):94--162, 1992.
[20]
C. Mohan and I. Narang. Algorithms for creating indexes for very large tables without quiescing updates. In Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, pages 361--370. ACM Press New York, NY, USA, 1992.
[21]
Oracle. Oracle Database Concepts 11g Release 1 (11.1). http://download.oracle.com/docs/cd/B28359_01/server.111/b28318/toc.htm, Apr 2009.
[22]
K. Pollari-Malmi, J. Ruuth, and E. Soisalon-Soininen. Concurrency control for B-trees with differential indices. In Proceedings of the International Database Engineering and Applications Symposium, pages 287--296, 2000.
[23]
P. Varman and R. Verma. An efficient multiversion access structure. IEEE Transactions on Knowledge and Data Engineering, 9(3):391--409, 1997.

Cited By

View all
  • (2024)TimeCloth: Fast Point-in-Time Database Recovery in The CloudCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3653382(214-226)Online publication date: 9-Jun-2024
  • (2022)A two-part multi-algorithm concurrency control optimization strategy for distributed database systemsInternational Journal of ADVANCED AND APPLIED SCIENCES10.21833/ijaas.2022.07.0169:7(159-171)Online publication date: Jul-2022
  • (2014)MV-IDXProceedings of the 18th International Database Engineering & Applications Symposium10.1145/2628194.2628911(142-148)Online publication date: 7-Jul-2014
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
IDEAS '09: Proceedings of the 2009 International Database Engineering & Applications Symposium
September 2009
347 pages
ISBN:9781605584027
DOI:10.1145/1620432
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 September 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. concurrency control
  2. database indexing methods
  3. recovery
  4. temporal databases

Qualifiers

  • Research-article

Conference

IDEAS '09
Sponsor:
  • ACM
  • Concordia University

Acceptance Rates

Overall Acceptance Rate 74 of 210 submissions, 35%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)TimeCloth: Fast Point-in-Time Database Recovery in The CloudCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3653382(214-226)Online publication date: 9-Jun-2024
  • (2022)A two-part multi-algorithm concurrency control optimization strategy for distributed database systemsInternational Journal of ADVANCED AND APPLIED SCIENCES10.21833/ijaas.2022.07.0169:7(159-171)Online publication date: Jul-2022
  • (2014)MV-IDXProceedings of the 18th International Database Engineering & Applications Symposium10.1145/2628194.2628911(142-148)Online publication date: 7-Jul-2014
  • (2014)Advanced Locking ProtocolsTransaction Processing10.1007/978-3-319-12292-2_9(221-236)Online publication date: 16-Nov-2014
  • (2014)B-Tree Structure ModificationsTransaction Processing10.1007/978-3-319-12292-2_8(185-219)Online publication date: 17-Nov-2014
  • (2014)B-Tree TraversalsTransaction Processing10.1007/978-3-319-12292-2_7(159-183)Online publication date: 17-Nov-2014
  • (2014)Lock-Based Concurrency ControlTransaction Processing10.1007/978-3-319-12292-2_6(125-158)Online publication date: 17-Nov-2014
  • (2014)Transactional IsolationTransaction Processing10.1007/978-3-319-12292-2_5(101-124)Online publication date: 17-Nov-2014
  • (2014)Transaction Rollback and Restart RecoveryTransaction Processing10.1007/978-3-319-12292-2_4(65-99)Online publication date: 17-Nov-2014
  • (2014)Logging and BufferingTransaction Processing10.1007/978-3-319-12292-2_3(45-64)Online publication date: 17-Nov-2014
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media