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

ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging.

C. Mohan, Frank Levine: ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging. SIGMOD Conference 1992: 371-380
@inproceedings{DBLP:conf/sigmod/MohanL92,
  author    = {C. Mohan and
               Frank Levine},
  editor    = {Michael Stonebraker},
  title     = {ARIES/IM: An Efficient and High Concurrency Index Management
               Method Using Write-Ahead Logging},
  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     = {371-380},
  ee        = {http://doi.acm.org/10.1145/130283.130338, db/conf/sigmod/MohanL92.html},
  crossref  = {DBLP:conf/sigmod/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper provides a comprehensive treatment of index management in transaction systems. We present a method, called ARIES/IM (Algorlthm for Recovery and Isolation Exploiting Semantics for lndex Management), for concurrency control and recovery of B+-trees. ARIES/lM guarantees serializability and uses write-ahead logging for recovery. It supports very high concurrency and good performance by (1) treating as the lock of a key the same lock as the one on the corresponding record data in a data page (e.g., at the record level), (2) not acquiring, in the interest of permitting very high concurrency, commit duration locks on index pages even during index structure modification operations (SMOs) like page splits and page deletions, and (3) allowing retrievals, inserts, and deletes to go on concurrently with SMOs. During restart recovery, any necessary redos of index changes are always performed in a page-oriented fashion (i.e., without traversing the index tree) and, during normal processing and restart recovery, whenever possible undos are performed in a page-oriented fashion. ARIES/lM permits different granularities of locking to be supported in a flexible manner. A subset of ARIES/lM has been implemented in the 0S/2 Extended Edition Database Manager. Since the locking ideas of ARIES/lM have general applicability, some of them have also been implemented in SQL/DS and the VM Shared File System, even though those systems use the shadow-page technique for recovery.

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, 1291 KB]

References

[BaSc77]
Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) BibTeX
[FuKa89]
Ada Wai-Chee Fu, Tiko Kameda: Concurrency Control of Nested Transactions Accessing B-Trees. PODS 1989: 270-285 BibTeX
[GMBLL81]
Jim Gray, Paul R. McJones, Mike W. Blasgen, Bruce G. Lindsay, Raymond A. Lorie, Thomas G. Price, Gianfranco R. Putzolu, Irving L. Traiger: The Recovery Manager of the System R Database Manager. ACM Comput. Surv. 13(2): 223-243(1981) BibTeX
[Gray78]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[KuPa79]
H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. SIGMOD Conference 1979: 116-126 BibTeX
[LeYa81]
Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) BibTeX
[MHLPS92]
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
[Mino84]
...
[Moha90a]
C. Mohan: ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. VLDB 1990: 392-405 BibTeX
[Moha90b]
C. Mohan: Commit_LSN: A Novel and Simple Method for Reducing Locking and Latching in Transaction Processing Systems. VLDB 1990: 406-418 BibTeX
[Moha92]
...
[MoLe89]
...
[MoNa91]
C. Mohan, Inderpal Narang: Recovery and Coherency-Control Protocols for Fast Intersystem Page Transfer and Fine-Granularity Locking in a Shared Disks Transaction Environment. VLDB 1991: 193-207 BibTeX
[MoPi91]
C. Mohan, Hamid Pirahesh: ARIES-RRH: Restricted Repeating of History in the ARIES Transaction Recovery Method. ICDE 1991: 718-727 BibTeX
[RoMo89]
Kurt Rothermel, C. Mohan: ARIES/NT: A Recovery Method Based on Write-Ahead Logging for Nested Transactions. VLDB 1989: 337-346 BibTeX
[Sagi86]
Yehoshua Sagiv: Concurrent Operations on B*-Trees with Overtaking. J. Comput. Syst. Sci. 33(2): 275-296(1986) BibTeX
[ShGo88]
Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988) BibTeX

Referenced by

  1. Seppo Sippu, Eljas Soisalon-Soininen: A Theory of Transactions on Recoverable Search Trees. ICDT 2001: 83-98
  2. Nagavamsi Ponnekanti, Hanuma Kodavalla: Online Index Rebuild. SIGMOD Conference 2000: 529-538
  3. C. Mohan: Repeating History Beyond ARIES. VLDB 1999: 1-17
  4. Tei-Wei Kuo, Chih-Hung Wei, Kam-yiu Lam: Real-Time Data Access Control on B-Tree Index Structures. ICDE 1999: 458-467
  5. Sungchae Lim, Yoon-Joon Lee, Myoung-Ho Kim: A Restructuring Method for the Concurrent B+-Tree Based on Semantic Consistency. DASFAA 1999: 229-236
  6. Sun Hwan Kim, Mi Suk Jung, Jun Hyun Park, Young Chul Park: A Design and Implementation of Savepoints and Partial Rollbacks Considering Transaction Isolation Levels of SQL2. DASFAA 1999: 303-312
  7. Alexander Thomasian: Concurrency Control: Methods, Performance, and Analysis. ACM Comput. Surv. 30(1): 70-119(1998)
  8. Sharad Mehrotra, Henry F. Korth, Abraham Silberschatz: Concurrency Control in Hierarchical Multidatabase Systems. VLDB J. 6(2): 152-172(1997)
  9. David B. Lomet, Betty Salzberg: Concurrency and Recovery for Index Trees. VLDB J. 6(3): 224-240(1997)
  10. 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)
  11. Rajeev Rastogi, S. Seshadri, Philip Bohannon, Dennis W. Leinbaugh, Abraham Silberschatz, S. Sudarshan: Logical and Physical Versioning in Main Memory Databases. VLDB 1997: 86-95
  12. Marcel Kornacker, C. Mohan, Joseph M. Hellerstein: Concurrency and Recovery in Generalized Search Trees. SIGMOD Conference 1997: 62-72
  13. Young Chul Park, Dae Young Huh: Mini-Savepoints: Firewalls for Atomic Updates. DASFAA 1997: 293-302
  14. Theo Härder, Joachim Reinert: Access Path Support for Referential Integrity in SQL2. VLDB J. 5(3): 196-214(1996)
  15. Kerttu Pollari-Malmi, Eljas Soisalon-Soininen, Tatu Ylönen: Concurrency Control in B-Trees with Batch Updates. IEEE Trans. Knowl. Data Eng. 8(6): 975-984(1996)
  16. Marcel Kornacker, Douglas Banks: High-Concurrency Locking in R-Trees. VLDB 1995: 134-145
  17. Brajesh Goyal, Jayant R. Haritsa, S. Seshadri, V. Srinivasan: Index Concurrency Control in Firm Real-Time Database Systems. VLDB 1995: 146-157
  18. Georgios Evangelidis, David B. Lomet, Betty Salzberg: The hBP-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation. VLDB 1995: 551-561
  19. André Eickler, Carsten Andreas Gerlhof, Donald Kossmann: A Performance Evaluation of OID Mapping Techniques. VLDB 1995: 18-29
  20. Lory D. Molesky, Krithi Ramamritham: Recovery Protocols for Shared Memory Database Systems. SIGMOD Conference 1995: 11-22
  21. C. Mohan: Disk Read-Write Optimizations and Data Integrity in Transaction Systems Using Write-Ahead Logging. ICDE 1995: 324-331
  22. C. Mohan, Dick Dievendorff: Recent Work on Distributed Commit Protocolls, and Recoverable Messaging and Queuing. IEEE Data Eng. Bull. 17(1): 22-28(1994)
  23. C. Mohan, Inderpal Narang: ARIES/CSA: A Method for Database Recovery in Client-Server Architectures. SIGMOD Conference 1994: 55-66
  24. C. Mohan, Donald J. Haderle: Algorithms for Flexible Space Management in Transaction Systems Supporting Fine-Granularity Locking. EDBT 1994: 131-144
  25. Gerhard Weikum, Christof Hasse: Multi-Level Transaction Management for Complex Objects: Implementation, Performance, Parallelism. VLDB J. 2(4): 407-453(1993)
  26. V. Srinivasan, Michael J. Carey: Performance of B+ Tree Concurrency Algorithms. VLDB J. 2(4): 361-406(1993)
  27. Theodore Johnson, Dennis Shasha: The Performance of Current B-Tree Algorithms. ACM Trans. Database Syst. 18(1): 51-101(1993)
  28. C. Mohan: A Cost-Effective Method for Providing Improved Data Availability During DBMS Restart Recovery After a Failure. VLDB 1993: 368-379
  29. David B. Lomet: Key Range Locking Strategies for Improved Concurrency. VLDB 1993: 655-664
  30. C. Mohan: IBM's Relational DBMS Products: Features and Technologies. SIGMOD Conference 1993: 445-448
  31. C. Mohan, Kent Treiber, Ron Obermarck: Algorithms for the Management of Remote Backup Data Bases for Disaster Recovery. ICDE 1993: 511-518
  32. C. Mohan: ARIES/LHS: A Concurrency Control and Recovery Method Using Write-Ahead Logging for Linear Hashing with Separators. ICDE 1993: 243-252
  33. John K. Lee: B-Tree Concurrency Control Algorithm for Nested Transaction Systems. DASFAA 1993: 205-215
  34. Betty Salzberg, Allyn Dimock: Principles of Transaction-Based On-Line Reorganization. VLDB 1992: 511-520
  35. C. Mohan, Hamid Pirahesh, Raymond A. Lorie: Efficient and Flexible Methods for Transient Versioning of Records to Avoid Locking by Read-Only Transactions. SIGMOD Conference 1992: 124-133
  36. C. Mohan, Inderpal Narang: Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates. SIGMOD Conference 1992: 361-370
  37. David B. Lomet, Betty Salzberg: Access Method Concurrency with Recovery. SIGMOD Conference 1992: 351-360
  38. David B. Lomet: MLR: A Recovery Method for Multi-level Systems. SIGMOD Conference 1992: 185-194
  39. Mark Sullivan, Michael A. Olson: An Index Implementation Supporting Fast Recovery for the POSTGRES Storage System. ICDE 1992: 293-300
  40. Ragaa Ishak: Semantically Consistent Schedules for Efficient and Concurrent B-Tree Restructuring. ICDE 1992: 184-191
  41. C. Mohan, Inderpal Narang: Recovery and Coherency-Control Protocols for Fast Intersystem Page Transfer and Fine-Granularity Locking in a Shared Disks Transaction Environment. VLDB 1991: 193-207
  42. Christof Hasse, Gerhard Weikum: A Performance Evaluation of Multi-Level Transaction Management. VLDB 1991: 55-66
  43. V. Srinivasan, Michael J. Carey: Performance of B-Tree Concurrency Algorithms. SIGMOD Conference 1991: 416-425
  44. C. Mohan, Hamid Pirahesh: ARIES-RRH: Restricted Repeating of History in the ARIES Transaction Recovery Method. ICDE 1991: 718-727
  45. C. Mohan: Commit_LSN: A Novel and Simple Method for Reducing Locking and Latching in Transaction Processing Systems. VLDB 1990: 406-418
  46. C. Mohan: ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. VLDB 1990: 392-405
  47. C. Mohan, Donald J. Haderle, Yun Wang, Josephine M. Cheng: Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques. EDBT 1990: 29-43
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: Wed Jun 4 18:55:03 2008