A multi-version concurrency scheme with no rollbacks

ABSTRACT

The multi-version data item concept is a method for increasing concurrency in a database system. All previously proposed schemes utilizing this concept relied on transaction rollback as a means for preserving consistency. These rollbacks require a considerable amount of overhead which degrades performance. In this paper we develop a new scheme that utilizes the multi-version data item concept. Our proposed scheme ensures consistency without the use of rollbacks. It is based upon the non-two phase tree locking protocol previously proposed by Silberschatz and Kedem.

REFERENCES

• 1: 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]
• 2: Gray, J., Notes on database operating systems. Research Report, IBM Research Lab, San Jose, Feb. 1978.
• 3: Reed, D.P. Naming and synchronization in a decentralized computer system. Ph.D. Thesis, M.I.T. Dept. of Electrical Engineering and Computer Science, Sept.1978
• 4: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• 5: Bernstein, P.A. and Goodman, N. Time-stamp-based algorithms for concurrency control in distributed database systems. Proceedings Sixth International Conference on Very Large Data Bases (Oct. 1980), 285-300.
• 6: Honeywell File Management Supervisor, Order Number DB54, Honeywell Information Systems Inc., 1973.
• 7: Stearns, R.E., Lewis, P.M. and Rosenkrantz, D.J. Concurrency control for database systems. Proceedings IEEE Symposium on Foundations of Computer Science (Oct. 1976), 19-32.
• 8: R. Bayer , H. Heller , A. Reiser, Parallelism and recovery in database systems, ACM Transactions on Database Systems (TODS), v.5 n.2, p.139-156, June 1980 [doi>10.1145/320141.320146]
• 9: Bayer, R., Elhardt, E., Heller, H. and Reiser, A. Distributed concurrency control in database systems. Proceedings Sixth International Conference on Very Large Data Bases (Oct. 1980), 275-284.
• 10: Richard E. Stearns , Daniel J. Rosenkrantz, Distributed database concurrency controls using before-values, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582330]
• 11: Abraham Silberschatz , Zvi Kedem, Consistency in Hierarchical Database Systems, Journal of the ACM (JACM), v.27 n.1, p.72-80, Jan. 1980 [doi>10.1145/322169.322176]
• 12: Kedem, Z., and Silberschatz, A. Non-two-phase locking protocols with shared and exclusive locks. Proceedings International Conference on Very Large Data Bases (Oct. 1980).
• 13: Kedem, Z., and Silberschatz, A. Controlling concurrency using locking protocols. Proceedings 20th IEEE Symposium on Foundations of Computer Science (Oct. 1979), 274-285.
• 14: Yannakakis, M., Papadimitriou, C.H., and Kung, H.T., Locking policy: safety and freedom from deadlock. Proceedings 20th IEEE Symposium on Foundation of Computer Science (Oct. 1979), 286-297.
• 15: Silberschatz, A., and Kedem, Z. A family of locking protocols for database systems that are modeled by directed graphs. IEEE Transactions on Software Engineering (to appear).
• 16: Fussell, D., Kedem, Z., and Silberschatz, A. A theory of correct protocols for database systems, Proceedings Seventh International Conference of Very Large Data Bases (Sept. 1981), 112-124.
• 17: C. Mohan , D. Fussell , A. Silberschatz, Compatibility and commutativity in non-two-phase locking protocols, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588157]
• 18: Daniel J. Rosenkrantz , Richard E. Stearns , Philip M. Lewis, II, System level concurrency control for distributed database systems, ACM Transactions on Database Systems (TODS), v.3 n.2, p.178-198, June 1978 [doi>10.1145/320251.320260]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing; Distributed databases

General Terms:
Design, Management