skip to main content
10.1145/1458550.1458563acmconferencesArticle/Chapter ViewAbstractPublication PagescikmConference Proceedingsconference-collections
research-article

Concurrency control and recovery for multiversion database structures

Published: 30 October 2008 Publication History

Abstract

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 straight-forward 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.

References

[1]
R. Bayer and M. Schkolnick. Concurrency of operations on B-trees. Acta Informatica, 9(1):1--21, 1977.
[2]
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.
[3]
N. Beckmann, H. Kriegel, R. Schneider, and B. Seeger. The R*-tree: an efficient and robust access method for points and rectangles. In Proceedings of the 1990 ACM SIGMOD international conference on Management of data, pages 322--331. ACM New York, NY, USA, 1990.
[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 1995 ACM SIGMOD International Conference on Management of data, pages 1--10. ACM New York, NY, USA, 1995.
[5]
J. Chen, Y. Huang, and Y. Chin. A study of concurrent operations on R-trees. Information Sciences, 98(1):263--300, 1997.
[6]
D. Comer. Ubiquitous B-tree. ACM Computing Surveys (CSUR), 11(2):121--137, 1979.
[7]
A. Fekete, D. Liarokapis, E. O'Neil, P. O'Neil, and D. Shasha. Making snapshot isolation serializable. ACM Transactions on Database Systems (TODS), 30(2):492--528, 2005.
[8]
A. Guttman. R-trees: a dynamic index structure for spatial searching. In Proceedings of the 1984 ACM SIGMOD International Conference on Management of data, pages 47--57. ACM Press New York, NY, USA, 1984.
[9]
T. Haapasalo, I. Jaluta, B. Seeger, S. Sippu, and E. Soisalon-Soininen. Transactions on the Multiversion B+-tree. To be submitted for publication.
[10]
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.
[11]
C. Kolovson and M. Stonebraker. Indexing techniques for historical databases. In Data Engineering, 1989. Proceedings. Fifth International Conference on, pages 127--137, 1989.
[12]
M. Kornacker and D. Banks. High-concurrency locking in R-trees. In Proceedings of VLDB, pages 134--145, 1995.
[13]
M. Kornacker, C. Mohan, and J. Hellerstein. Concurrency and recovery in generalized search trees. ACM SIGMOD Record, 26(2):62--72, 1997.
[14]
P. Lehman and B. Yao. Efficient locking for concurrent operations on B-trees. ACM Transactions on Database Systems (TODS), 6(4):650--670, Dec 1981.
[15]
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.
[16]
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, ICDE 2006, pages 35--46, 2006.
[17]
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.
[18]
D. Lomet and B. Salzberg. The performance of a multiversion access method. In Proceedings of the 1990 ACM SIGMOD International Conference on Management of data, pages 353--363. ACM New York, NY, USA, 1990.
[19]
D. Lomet and B. Salzberg. Access method concurrency with recovery. ACM SIGMOD Record, 21(2):351--360, 1992.
[20]
C. Mohan. ARIES/IM: an efficient and high concurrency index management method using write-ahead logging. In Proceedings of the 1992 ACM SIGMOD international conference on Management of data, pages 371--380. ACM Press New York, NY, USA, 1992.
[21]
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.
[22]
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.
[23]
V. Ng and T. Kameda. Concurrent accesses to R-trees. In Proceedings of the Third International Symposium on Advances in Spatial Databases, pages 142--161. Springer-Verlag London, UK, 1993.
[24]
G. Ozsoyoglu and R. Snodgrass. Temporal and real-time databases: a survey. Knowledge and Data Engineering, IEEE Transactions on, 7(4):513--532, 1995.
[25]
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.
[26]
B. Salzberg, L. Jiang, D. Lomet, M. Barrena, J. Shan, and E. Kanoulas. A framework for access methods for versioned data. In Proceedings of the 9th International Conference on Extending Database Technology, pages 730--747, 2004.
[27]
S. Song, Y. Kim, and J. Yoo. An enhanced concurrency control scheme for multidimensional index structures. IEEE Transactions on Knowledge and Data Engineering, pages 97--111, 2004.
[28]
K. Torp, C. Jensen, and R. Snodgrass. Effective timestamping in databases. The VLDB Journal-The International Journal on Very Large Data Bases, 8(3-4):267--288, 2000.

Cited By

View all
  • (2024)A Structure Based on B+ Trees to Represent a Large Number of k-Multisets Stored in Non-volatile MemoryRecent Challenges in Intelligent Information and Database Systems10.1007/978-981-97-5937-8_22(262-274)Online publication date: 13-Aug-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
PIKM '08: Proceedings of the 2nd PhD workshop on Information and knowledge management
October 2008
116 pages
ISBN:9781605582573
DOI:10.1145/1458550
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: 30 October 2008

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. access methods
  2. concurrency
  3. physical design
  4. recovery
  5. transactions
  6. versioned data

Qualifiers

  • Research-article

Conference

CIKM08
CIKM08: Conference on Information and Knowledge Management
October 30, 2008
California, Napa Valley, USA

Acceptance Rates

Overall Acceptance Rate 25 of 62 submissions, 40%

Upcoming Conference

CIKM '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

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

Other Metrics

Citations

Cited By

View all
  • (2024)A Structure Based on B+ Trees to Represent a Large Number of k-Multisets Stored in Non-volatile MemoryRecent Challenges in Intelligent Information and Database Systems10.1007/978-981-97-5937-8_22(262-274)Online publication date: 13-Aug-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
  • (2013)FicklebaseProceedings of the 2013 IEEE International Conference on Data Engineering (ICDE 2013)10.1109/ICDE.2013.6544816(86-97)Online publication date: 8-Apr-2013
  • (2011)Minimal data sets vs. synchronized data copies in a schema and data versioning systemProceedings of the 4th workshop on Workshop for Ph.D. students in information & knowledge management10.1145/2065003.2065017(67-74)Online publication date: 28-Oct-2011
  • (2010)Interacting with public policy: Driving transportation policy through technological innovationInteractions10.1145/1806491.180650217:4(42-48)Online publication date: 1-Jul-2010
  • (2009)Mining concise representations of frequent patterns through conjunctive and disjunctive search spacesACM SIGKDD Explorations Newsletter10.1145/1656274.165628811:1(57-58)Online publication date: 16-Nov-2009
  • (2009)Adaptive learning and mining for data streams and frequent patternsACM SIGKDD Explorations Newsletter10.1145/1656274.165628711:1(55-56)Online publication date: 16-Nov-2009
  • (2009)Correlation clusteringACM SIGKDD Explorations Newsletter10.1145/1656274.165628611:1(53-54)Online publication date: 16-Nov-2009
  • (2009)Challenging research issues in data mining, databases and information retrievalACM SIGKDD Explorations Newsletter10.1145/1656274.165628411:1(49-52)Online publication date: 16-Nov-2009
  • 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