ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Access Method Concurrency with Recovery.

David B. Lomet, Betty Salzberg: Access Method Concurrency with Recovery. SIGMOD Conference 1992: 351-360
@inproceedings{DBLP:conf/sigmod/LometS92,
  author    = {David B. Lomet and
               Betty Salzberg},
  editor    = {Michael Stonebraker},
  title     = {Access Method Concurrency with Recovery},
  booktitle = {Proceedings of the 1992 ACM SIGMOD International Conference on
               Management of Data, San Diego, California, June 2-5, 1992},
  publisher = {ACM Press},
  year      = {1992},
  pages     = {351-360},
  ee        = {http://doi.acm.org/10.1145/130283.130336, db/conf/sigmod/LometS92.html},
  crossref  = {DBLP:conf/sigmod/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Providing high concurrency in B+-trees has been studied extensively. But few efforts have been documented for combining concurrency methods with a recovery scheme that preserves well-formed trees across system crashes. We describe an approach for this that works for a class of index trees that is a generalization of the Blink-tree. A major feature of our method is that it works with a range of different recovery methods. It achieves this by decomposing structure changes in an index tree into a sequence of atomic actions, each one leaving the tree well-formed and each working on a separate level of the tree. All atomic actions on levels of the tree above the leaf level are independent of database transactions, and so are of short duration.

Copyright © 1992 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Michael Stonebraker (Ed.): Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, San Diego, California, June 2-5, 1992. ACM Press 1992 BibTeX , SIGMOD Record 21(2), June 1992
Contents

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 958 KB]

References

[1]
Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) BibTeX
[2]
Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX
[3]
...
[4]
...
[5]
Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents BibTeX
[6]
Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) BibTeX
[7]
David B. Lomet: Process Structuring, Synchronization, and Recovery Using Atomic Actions. Language Design for Reliable Software 1977: 128-137 BibTeX
[8]
David B. Lomet: Subsystems of Processes with Deadlock Avoidance. IEEE Trans. Software Eng. 6(3): 297-304(1980) BibTeX
[9]
...
[10]
David B. Lomet, Betty Salzberg: Access Methods for Multiversion Data. SIGMOD Conference 1989: 315-324 BibTeX
[11]
David B. Lomet, Betty Salzberg: The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance. ACM Trans. Database Syst. 15(4): 625-658(1990) BibTeX
[12]
...
[13]
C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, Peter M. Schwarz: ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM Trans. Database Syst. 17(1): 94-162(1992) BibTeX
[14]
C. Mohan, Frank E. Levine: ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging. SIGMOD Conference 1992: 371-380 BibTeX
[15]
Yehoshua Sagiv: Concurrent Operations on B*-Trees with Overtaking. J. Comput. Syst. Sci. 33(2): 275-296(1986) BibTeX
[16]
...
[17]
Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988) BibTeX
[18]
V. Srinivasan, Michael J. Carey: Performance of B-Tree Concurrency Algorithms. SIGMOD Conference 1991: 416-425 BibTeX

Referenced by

  1. Seppo Sippu, Eljas Soisalon-Soininen: A Theory of Transactions on Recoverable Search Trees. ICDT 2001: 83-98
  2. C. Mohan: Repeating History Beyond ARIES. VLDB 1999: 1-17
  3. Marcel Kornacker: High-Performance Extensible Indexing. VLDB 1999: 699-708
  4. Sungchae Lim, Yoon-Joon Lee, Myoung-Ho Kim: A Restructuring Method for the Concurrent B+-Tree Based on Semantic Consistency. DASFAA 1999: 229-236
  5. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  6. Sharad Mehrotra, Henry F. Korth, Abraham Silberschatz: Concurrency Control in Hierarchical Multidatabase Systems. VLDB J. 6(2): 152-172(1997)
  7. David B. Lomet, Betty Salzberg: Concurrency and Recovery for Index Trees. VLDB J. 6(3): 224-240(1997)
  8. Georgios Evangelidis, David B. Lomet, Betty Salzberg: The hB-Pi-Tree: A Multi-Attribute Index Supporting Concurrency, Recovery and Node Consolidation. VLDB J. 6(1): 1-25(1997)
  9. Marcel Kornacker, C. Mohan, Joseph M. Hellerstein: Concurrency and Recovery in Generalized Search Trees. SIGMOD Conference 1997: 62-72
  10. Chendong Zou, Betty Salzberg: On-line Reorganization of Sparsely-populated B+trees. SIGMOD Conference 1996: 115-124
  11. David B. Lomet, Mark R. Tuttle: Redo Recovery after System Crashes. VLDB 1995: 457-468
  12. Marcel Kornacker, Douglas Banks: High-Concurrency Locking in R-Trees. VLDB 1995: 134-145
  13. Brajesh Goyal, Jayant R. Haritsa, S. Seshadri, V. Srinivasan: Index Concurrency Control in Firm Real-Time Database Systems. VLDB 1995: 146-157
  14. Georgios Evangelidis, David B. Lomet, Betty Salzberg: The hBP-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation. VLDB 1995: 551-561
  15. Lory D. Molesky, Krithi Ramamritham: Recovery Protocols for Shared Memory Database Systems. SIGMOD Conference 1995: 11-22
  16. V. Srinivasan, Michael J. Carey: Performance of B+ Tree Concurrency Algorithms. VLDB J. 2(4): 361-406(1993)
  17. Georgios Evangelidis, Betty Salzberg: Using the Holy Brick Tree for Spatial Data in General Purpose DBMSs. IEEE Data Eng. Bull. 16(3): 34-39(1993)
  18. David B. Lomet, Betty Salzberg: Exploiting A History Database for Backup. VLDB 1993: 380-390
  19. Betty Salzberg, Allyn Dimock: Principles of Transaction-Based On-Line Reorganization. VLDB 1992: 511-520
  20. David B. Lomet: MLR: A Recovery Method for Multi-level Systems. SIGMOD Conference 1992: 185-194
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:12 2009