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. 1 ASTRAHAN, M:.M., ET AL. System R" Relational approach to database management. ACM Trans. Database Syst. 1, 2 (June 1976), 97-137.
2. 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. 3 CODASYL PROGRAMMING LANGUAGE COMMITTEE. Data Base Task Group Report, April 1971. (Available from ACM, New York.)
4. 4 CODASYL PROGRAMMING LANGUAGE COMMITTEE. CODASYL COBOL Data Base Facility Proposal, March 1973.
5. 5 COFFMAN, E., ET AL. System deadlocks. Computing Surveys 3, 2 (June 1971), 67-78.
6. 6 DATE, C.J. An Introduction to Data Base Systems. Addison-Wesley, Reading, Mass., 1975.
7. 7 ESWARAN, K.P., GRAY, J.H., LORIE, R.A., AND TRAIGER, L.I. The notions of consistency and predicate locks in a database system. Comm. ACM 19, 11 (Nov. 1976), 624-633.
8. 8 FLORENTIN, J.J. Consistency auditing of data bases. Comptr. J. 17, 1 (Feb. 1974), 52-58.
9. 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. 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. 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. 12 MACRI, P. Deadlock detection and resolution in a CODASYL based data management system. Proc. 1976 ACM-SIGMOD int. Conf. on Management of Data, Washington, D.C., June 1976, pp. 45-49.
13. 13 SeITZER, J.F. Performance prototyping of data management applications. Proc. ACM 76 (Annual Conf.), Houston, Tex., Oct. 1976, pp. 287-297.
14. 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. 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. 16 S~ONEBRAKEa, M., ET AL. The design and implementation of INURES. ACM Trans. Database Syst. I, 3 (Sept. 1976), 189-222.

Index Terms

• Computing methodologies

  • Concurrent computing methodologies

• Information systems

  • Data management systems

    • Database management system engines

• Theory of computation

  • Models of computation

    • Concurrency