Concurrency Control Issues in Nested Transactions.

Theo Härder, Kurt Rothermel: Concurrency Control Issues in Nested Transactions. VLDB J. 2(1): 39-74(1993)
  author    = {Theo H{\"a}rder and
               Kurt Rothermel},
  title     = {Concurrency Control Issues in Nested Transactions},
  journal   = {VLDB J.},
  volume    = {2},
  number    = {1},
  year      = {1993},
  pages     = {39-74},
  ee        = {db/journals/vldb/HarderR93.html},
  bibsource = {DBLP,}


The concept of nested transactions offers more decomposable execution units and finer-grained control over concurrency and recovery than "flat" transactions. Furthermore, it supports the decomposition of a "unit of work" into subtasks and their appropriate distribution in a computer system as a prerequisite of intratransaction parallelism. However, to exploit its full potential, suitable granules of concurrency control as well as access modes for shared data are necessary. In this article, we investigate various issues of concurrency control for nested transactions. First, the mechanisms for cooperation and communication within nested transactions should not impede parallel execution of transactions among parent and children or among siblings. Therefore, a model for nested transactions is proposed allowing for effective exploitation of intra-transaction parallelism. Starting with a set of basic locking rules, we introduce the concept of "downward inheritance of locks" to make data manipulated by a parent available to its children. To support supervised and restricted access, this concept is refined to "controlled downward inheritence." The initial concurrency control scheme was based on S-X locks for "flat," non-overlapping data objects. In order to adjust this scheme for practical applications, a set of concurrency control rules is derived for generalized lock modes described by a compatibility matrix. Also, these rules are combined with a hierarchical locking scheme to improve selective accesses to data granules of varying sizes. After having tied together both types of hierarchies (transaction and object), it can be shown how "controlled downward inheritance" for hierarchical objects is achieved in nested transactions. Finally, problems of deadlock detection and resolution in nested transactions are considered.

Copyright © 1993 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Key Words

Nested transactions, concurrency control, locking, object hierarchies.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


[Ahamad et al. 1987]
[Allchin 1983]
[Almes et al. 1985]
Guy T. Almes, Andrew P. Black, Edward D. Lazowska, Jerre D. Noe: The Eden System: A Technical Review. IEEE Trans. Software Eng. 11(1): 43-59(1985) BibTeX
[Anon et al. 1985]
[Astrahan et al. 1976]
Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
[Bancilhon et al. 1985]
François Bancilhon, Won Kim, Henry F. Korth: A Model of CAD Transactions. VLDB 1985: 25-33 BibTeX
[Beeri et al. 1989]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A model for concurrency in nested transactions systems. J. ACM 36(2): 230-269(1989) BibTeX
[Bernstein & Goodman 1981]
Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981) BibTeX
[Bernstein et al. 1987]
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
[Dasgupta et al. 1989]
Partha Dasgupta, Richard J. LeBlanc, William F. Appelbe: The Clouds Distributed Operating System. ICDCS 1988: 2-9 BibTeX
[Eswaran et al. 1976]
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
[Eppinger et al. 1991]
[Gawlick 1985]
[Gray 1978]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[Gray 1981]
Jim Gray: The Transaction Concept: Virtues and Limitations (Invited Paper). VLDB 1981: 144-154 BibTeX
[Gray et al. 1976]
[Härder & Reuter 1983]
Theo Härder, Andreas Reuter: Principles of Transaction-Oriented Database Recovery. ACM Comput. Surv. 15(4): 287-317(1983) BibTeX
[Härder & Rothermel 1987]
Theo Härder, Kurt Rothermel: Concepts for Transaction Recovery in Nested Transactions. SIGMOD Conference 1987: 239-248 BibTeX
[Jessop 1982]
[Kim et al. 1984]
Won Kim, Raymond A. Lorie, Dan McNabb, Wil Plouffe: A Transaction Mechanism for Engineering Design Databases. VLDB 1984: 355-362 BibTeX
[Liskov 1985]
Barbara Liskov: The Argus Language and System. Advanced Course: Distributed Systems 1984: 343-430 BibTeX
[Liskov 1988]
Barbara Liskov: Distributed Programming in Argus. Commun. ACM 31(3): 300-312(1988) BibTeX
[Liskov et al. 1987]
Barbara Liskov, Dorothy Curtis, Paul Johnson, Robert Scheifler: Implementation of Argus. SOSP 1987: 111-122 BibTeX
[Mohan et al. 1986]
[Moss 1985]
[Moss et al. 1986]
J. Eliot B. Moss, Nancy D. Griffeth, Marc H. Graham: Abstraction in Recovery Management. SIGMOD Conference 1986: 72-83 BibTeX
[Moss 1987]
J. Eliot B. Moss: Log-Based Recovery for Nested Transactions. VLDB 1987: 427-432 BibTeX
[Mueller et al. 1983]
Erik T. Mueller, Johanna D. Moore, Gerald J. Popek: A Nested Transaction Mechanism for LOCUS. SOSP 1983: 71-89 BibTeX
[Pu & Noe 1988]
[Rahm 1992]
[Reuter 1982]
Andreas Reuter: Concurrency on High-trafic Data Elements. PODS 1982: 83-92 BibTeX
[Rosenkrantz et al. 1978]
Daniel J. Rosenkrantz, Richard Edwin Stearns, Philip M. Lewis II: System Level Concurrency Control for Distributed Database Systems. ACM Trans. Database Syst. 3(2): 178-198(1978) BibTeX
[Rothermel & Mohan 1989]
Kurt Rothermel, C. Mohan: ARIES/NT: A Recovery Method Based on Write-Ahead Logging for Nested Transactions. VLDB 1989: 337-346 BibTeX
[Rukoz 1991]
Marta Rukoz: Hierarchical Deadlock Detection for Nested Transactions. Distributed Computing 4: 123-129(1991) BibTeX
[Schwarz & Spector 1984]
Peter M. Schwarz, Alfred Z. Spector: Synchronizing Shared Abstract Types. ACM Trans. Comput. Syst. 2(3): 223-250(1984) BibTeX
[Spector & Schwarz 1983]
Alfred Z. Spector, Peter M. Schwarz: Transactions: A Construct for Reliable Distributed Computing. Operating Systems Review 17(2): 18-35(1983) BibTeX
[Spector et al. 1988]
[Walter 1984]
Bernd Walter: Nested Transactions with Multiple Commit Points: An Approach to the Structuring of Advanced Database Applications. VLDB 1984: 161-171 BibTeX
[Weikum 1986]
Gerhard Weikum: A Theoretical Foundation of Multi-Level Concurrency Control. PODS 1986: 31-43 BibTeX
[Weikum 1991]
Gerhard Weikum: Principles and Realization Strategies of Multilevel Transaction Management. ACM Trans. Database Syst. 16(1): 132-180(1991) BibTeX
[Weikum & Schek 1984]
Gerhard Weikum, Hans-Jörg Schek: Architectural Issues of Transaction Management in Multi-Layered Systems. VLDB 1984: 454-465 BibTeX
[Weinstein et al. 1985]
Matthew J. Weinstein, Thomas W. Page Jr., Brian Livezey, Gerald J. Popek: Transactions and Synchronization in a Distributed Operating System. SOSP 1985: 115-126 BibTeX

Referenced by

  1. C. Mohan: Repeating History Beyond ARIES. VLDB 1999: 1-17
  2. Stefan Deßloch, Theo Härder, Nelson Mendonça Mattos, Bernhard Mitschang, Joachim Thomas: Advanced Data Processing in KRISYS: Modeling Concepts, Implementation Techniques, and Client/Server Issues. VLDB J. 7(2): 79-95(1998)
  3. Gerti Kappel, Werner Retschitzegger: The TriGS Active Object-Oriented Database System - An Overview. SIGMOD Record 27(3): 36-41(1998)
  4. Alexander Thomasian: Concurrency Control: Methods, Performance, and Analysis. ACM Comput. Surv. 30(1): 70-119(1998)
  5. Ugur Halici, Ismailcem Budak Arpinar, Asuman Dogac: Serializability of Nested Transactions in Multidatabases. ICDT 1997: 321-335
  6. Javam Machado, Christine Collet: A Parallel Execution Model for Database Transactions. DASFAA 1997: 511-520
  7. Ekaterina Pavlova, Igor Nekrestyanov: Concurrency Control Protocol for Nested Transactions in Real-Time Databases. ADBIS 1997: 23-28
  8. Igor Nekrestyanov, Boris Novikov, Ekaterina Pavlova, Serge Pikalev: Concurrency Control Protocols for Persistent Shared Virtual Memory Systems (Extended Abstract). ADBIS 1997: 35-39
  9. Ge Yu, Kunihiko Kaneko, Guangyi Bai, Akifumi Makinouchi: Transaction Management for a Distributed Object Storage System WAKASHI - Design, Implementation and Performance. ICDE 1996: 460-468
  10. Gerti Kappel, S. Rausch-Schott, Werner Retschitzegger: A Transaction Model For Handling Composite Events. ADBIS 1996: 116-125
  11. Laurent Daynès, Olivier Gruber, Patrick Valduriez: Locking in OODBMS Client Supported Nestd Transactions. ICDE 1995: 316-323
  12. Rainer Unland: A Flexible and Adaptable Tool Kit Approach for Concurrency Control in Non Standard Database Systems. ICDT 1990: 274-288
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sun May 17 00:31:17 2009