Skip to main content
SpringerLink
Log in

Concurrency control issues in nested transactions

  • Published:
The VLDB Journal Aims and scope Submit manuscript

Abstract

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 inheritance.” 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 access 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Ahamad, M., Dasgupta, P., Le Blanc, R.J., and Wilkes, C.T. Fault tolerant computing in object based distributed systems.IEEE 6th Symposium on Reliability in Distributed Software and Database Systems, 1987.

  • Allchin, J.E. An architecture for decentralized systems. Technical Report GIT-ICS83-23, School of Information and Computer Science, Georgia Institute of Technology, 1983.

  • Almes, G.T., Black, A.P., Lazowska, E.D., and Noe, J.D. The Eden system: A technical review.IEEE Trans. Software Engineering, 11(1):43–58, 1985.

    Google Scholar 

  • Anon et al. A measure of transaction processing power.Datamation, April, 1985.

  • Astrahan, M.M., Blasgen, M.W., Chamberlin, D.D., Eswaran, K.P., Gray, J.N., Griffith, P.P., King, W.F., Lorie, R.A., McJones, P.R., Mehl, J.W., Putzolu, G.R., Traiger, I.L., Wade, B., and Watson, V. System R: Relational approach to database management.ACM TODS, 1(2):97–137, 1976.

    Google Scholar 

  • Bancilhon, F., Kim, W., and Korth, H.F. A model of CAD transactions.Proceedings of the 11th International Conference on VLDB, Stockholm, 1985.

  • Beeri, C., Bernstein, P.A., and Goodman, N. A model for concurrency in nested transaction systems.Journal of the ACM, 36(1):230–269, 1989.

    Google Scholar 

  • Bernstein, P.A. and Goodman, N. Concurrency control in distributed database systems.ACM Computing Surveys, 13(2):185–221, 1981.

    Google Scholar 

  • Bernstein, P.A., Hadzilacos, N., and Goodman, N.Concurrency Control and Recovery in Database Systems, Addison-Wesley: Reading, Pennsylvania, 1987.

    Google Scholar 

  • Dasgupta, P., Le Blanc, R., and Appelbe, W. The Clouds distributed operating system: Functional description, implementation details and related work.IEEE 8th International Conference on Distributed Computing Systems, San Jose, California, 1989.

  • Eswaran, K.P., Gray, J.N., Lorie, R.A., and Traiger, I.L. The notions of consistency and predicate locks in a database system.Communications of ACM, 19(11):624–633, 1976.

    Google Scholar 

  • Eppinger, J.L., Mummert, L.B., and Spector, A.Z., eds.Camelot and Avalon—A Distributed Transaction Facility. Morgan Kaufmann: San Mateo, California, 1991.

    Google Scholar 

  • Gawlick, D. Processing “hot spots” in high performance systems.Proceedings of the IEEE, Spring CompCon, San Francisco, 1985.

    Google Scholar 

  • Gray, J.N. Notes on database operating systems. Operating Systems—An Advanced Course. In: Bayer, R., Graham, R.M., and Seegmueller, G., eds.,Lecture Notes in Computer Science 60, Springer-Verlag: Berlin, 1978, pp. 393–481.

    Google Scholar 

  • Gray, J.N. The transaction concept: Virtues and limitations.Proceedings of the Seventh International Conference on VLDB, Cannes, 1981.

  • Gray, J.N., Lorie, R.A., Putzolu, G.R., and Traiger, I. Granularity of locks and degrees of consistency in a shared data base.Proceedings of the IFIP Working Conference on Modeling in Data Base Management Systems, Freudenstadt, Germany, 1976.

  • Härder, T. and Reuter, A. Principles of transaction-oriented database recovery.ACM Computing Surveys, 15(4):287–318, 1983.

    Google Scholar 

  • Härder, T. and Rothermel, K. Concepts for transaction recovery in nested transactions.Proceedings of the ACM SIGMOD, San Francisco, 1987.

  • Jessop, W.H. The EDEN transaction-based file system.Proceedings of the Second Symposium on Reliability in Distributed Software and Databases, Pittsburgh, 1982.

  • Kim, W., Lorie, R., McNabb, D., and Plouffe, W. Nested transactions for engineering design databases.Proceedings of the Tenth International Conference on VLDB, Singapore, 1984.

  • Liskov, B. The ARGUS language and system. Distributed systems-Methods and tools for specification: An advanced course. In: Paul, M. and Siegert, H.J., eds.,Lecture Notes in Computer Science 190, Springer-Verlag: Berlin, 1985, pp. 343–430.

    Google Scholar 

  • Liskov, B. Distributed programming in ARGUS.Communications of the ACM, 31:300–312, 1988.

    Google Scholar 

  • Liskov, B., Curtis, D., Johnson, P., and Scheifler, R.: Implementation of ARGUS. Proceedings of the 11th Symposium on Operating System Principles,ACM Operating Systems Review, 21(5):111–122, 1987.

    Google Scholar 

  • Mohan, C., Lindsay, B., and Obermark, R. Transaction management in R* distributed data base managements systems. IBM Research Report #RJ5037, San Jose, California, 1986.

  • Moss, J.E.B..Nested Transactions: An Approach to Reliable Distributed Computing. M.I.T. Press, Cambridge, 1985.

    Google Scholar 

  • Moss, J.E.B., Griffeth, N.D., and Graham, M.H. Abstraction in recovery management.Proceedings of the International Conference on Management of Data (SIG-MOD), Washington, D.C., 1986.

  • Moss, J.E.B. Log-based recovery for nested transactions.Proceedings of the 13th VLDB Conference, Brighton, 1987.

  • Mueller, E.T., Moore, J.D., and Popek, G.A. Nested transaction mechanism for LOCUS.Proceedings of the 9th Symposium on Operating Systems Principles, ACM/SIGOPS, Bretton Woods, 1983.

  • Pu, C. and Noe, J.D. Nested transactions for general objects: The Eden implementation. Department of Computer Science, University of Washingtion, TR-85-12-03, 1988.

  • Rahm, E. A Framework for Workload allocation in distributed transaction processing systems.Journal of Systems and Software, 18:171–190, 1992.

    Google Scholar 

  • Reuter, A. Concurrency on high-traffic data elements.Proceedings on the Conference on Principles of Database Systems, Los Angeles, 1982.

  • Rosenkrantz, D.J., Stearns, R.E., and Lewis II, PM. System level concurrency control for distributed database systems.ACM Transactions on Database Systems, 3(2): pages? 1978.

    Google Scholar 

  • Rothermel, K. and Mohan, C. ARIES/NT: A recovery method based on write-ahead logging for nested transactions.Proceedings of the 15th International Conference on Very Large Data Bases, Amsterdam, 1989.

  • Rukoz, M. Hierarchical deadlock detection for nested transactions.Distributed Computing, 4:123–129, 1991.

    Google Scholar 

  • Schwarz, P.M. and Spector, A.Z. Synchronizing shared abstract types.ACM TOCS, 2(3):223–250, 1984.

    Google Scholar 

  • Spector, A.Z. and Schwarz, P.M. Transactions: A construct for reliable distributed computing.Operating Systems Review, 17(2):18–35, 1983.

    Google Scholar 

  • Spector, A.Z. Pausch, R.F., and Bruell, G. Camelot: A flexible, distributed transaction proceessing system.Proceedings of the Spring IEEE COMPCON, San Francisco, 1988.

  • Walter, B. Nested transactions with multiple commit points: An approach to the structure of advanced database applications.Proceedings of the Tenth International Conference on VLDB, Singapore, 1984.

  • Weikum, G. A theoretical foundation of multi-level concurrency control.Proceedings of the ACM SIGACT-SIGMOD: Symposium on Principles of Database Systems, Cambridge, Massachussetts, 1986.

  • Weikum, G. Principles and realization strategies of multilevel transaction management,ACM TODS, 16(1):132–180, 1991.

    Google Scholar 

  • Weikum, G. and Schek, H.-J. Architectural issues of transaction management in layered systems.Proceedings of the Tenth International Conference on VLDB, Singapore, 1984.

  • Weinstein, M., Page, T., Livezey, B., and Popek, G. Transactions and synchronization in a distributed operating system.Proceedings of the Tenth Symposium on Operating Systems Principles, ACM/SIGOPS, Orcas Island, Washington, 1985.

Download references

Author information

Authors and Affiliations

  1. University of Kaiserslautern, D-6750, Kaiserslautern, Germany

    Theo Härder Ph.D. (Professor of Computer Science)

  2. University of Stuttgart, D-7000, Stuttgart 80, Germany

    Kurt Rothermel Ph.D. (Professor of Computer Science)

Authors
  1. Theo Härder Ph.D.
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kurt Rothermel Ph.D.
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Härder, T., Rothermel, K. Concurrency control issues in nested transactions. VLDB Journal 2, 39–74 (1993). https://doi.org/10.1007/BF01231798

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01231798

Key Words

Search

Navigation