Effects of locking granularity in a database management system

ABSTRACT

Many database systems guarantee some form of integrity control upon multiple concurrent updates by some form of locking. Some “granule” of the database is chosen as the unit which is individually locked, and a lock management algorithm is used to ensure integrity. Using a simulation model, this paper explores the desired size of a granule. Under a wide variety of seemingly realistic conditions, surprisingly coarse granularity is called for. The paper concludes with some implications of these results concerning the viability of so-called “predicate locking”.

REFERENCES

• 1: M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
• 2: CHAMBERLIN, D., ~T AL. A deadlock-free scheme for resource locking in a data dase environment. Proc. IFIPS 74 Congr., North-Holland Pub. Co., Amsterdam, 1974, pp. 340-343.
• 3: CODASYL PROGRAMMING LANGUAGE COMMITTEE. Data Base Task Group Report, April 1971. (Available from ACM, New York.)
• 4: CODASYL PROGRAMMING LANGUAGE COMMITTEE. CODASYL COBOL Data Base Facility Proposal, March 1973.
• 5: E. G. Coffman , M. Elphick , A. Shoshani, System Deadlocks, ACM Computing Surveys (CSUR), v.3 n.2, p.67-78, June 1971 [doi>10.1145/356586.356588]
• 6: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 7: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 8: FLORENTIN, J.J. Consistency auditing of data bases. Comptr. J. 17, 1 (Feb. 1974), 52-58.
• 9: GRAr, J.N., LORIE, R.A., AND PUTZOLU, G.R. Granularity of locks in a shared data base. Proc. Int. Conf. on Very Large Data Bases, Framingham, Mass., Sept. 1975, pp. 428-451.
• 10: GRit, J.N., LORIE, R.A., PvrzoT.v, G.R., ~) TR~Io~R, I.L. Granularity of locks and degrees of consistency in a shared data base. Proc. IFIP Working Conf. on Modelling of Data Base Manage. Syst., Freudenstadt, Germany, Jan. 1976, pp. 695~723.
• 11: LIPSON, W., AND LhPEZAK, O. LSL user's manual. Tech. Note No. 9, Comptr. Syst. Res. Group, U. of Toronto, Toronto, Ont., Canada, Aug. 1976.
• 12: Philip P. Macri, Deadlock detection and resolution in a CODASYL based data management system, Proceedings of the 1976 ACM SIGMOD international conference on Management of data, June 02-04, 1976, Washington, D.C.
• 13: James F. Spitzer, Performance prototyping of data management applications, Proceedings of the annual conference, p.287-291, October 20-22, 1976, Houston, Texas, United States [doi>10.1145/800191.805599]
• 14: STEARNS, R.E., ET AL. Concurrency control for data base systems. Proc. IEEE Symp. on Foundations of Comptr. Sci., Oct. 1976, pp. 19-32.
• 15: STONEBRAKER, M. High level integrity assurance in relational data base systems. Memo. ERL-M473, Electron. Res. Lab., U. of California, Berkeley, Aug. 1974.
• 16: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency

General Terms:
Design, Management

Keywords:
concurrency, consistency, database management, locking granularity, multiple updates, predicate locks