H. T. Kung
John T. Robinson
Abstract
Most current approaches to concurrency control in database systems rely on locking of data objects as a control mechanism. In this paper, two families of nonlocking concurrency controls are presented. The methods used are “optimistic” in the sense that they rely mainly on transaction backup as a control mechanism, “hoping” that conflicts between transactions will not occur. Applications for which these methods should be more efficient than locking are discussed.
- 1 BAYER, R., AND MCCREIGHT, E. Organization and maintenance of large ordered indexes. Acta Inf. 1, 3 (1972), 173-189.Google Scholar
Digital Library
- 2 BAYER, R., AND SCHKOLNICK, M. Concurrency of operations on B-trees. Acta Inf. 9, 1 (1977), 1-21.Google ScholarDigital Library
- 3 ELLIS, C.S. Concurrency search and insertion in 2-3 trees. Acta Inf. 14, 1 (1980), 63-86.Google ScholarDigital Library
- 4 ESWARAN, K. P., GRAY, J. N., LORIE, R. A., AND TRAIGER, I.L. The notions of consistency and predicate locks in a database system. Commun. ACM 19, 11 (Nov. 1976), 624-633. Google ScholarDigital Library
- 5 GRAY, J. Notes on database operating systems. In Lecture Notes in Computer Science 60: Operating Systems, R. Bayer, R. M. Graham, and G. Seegmuller, Eds. Springer-Verlag, Berlin, 1978, pp. 393-481. Google ScholarDigital Library
- 6 KUNG, H. T., AND LEHMAN, P.L. Concurrent manipulation of binary search trees. ACM Trans. Database Syst. 5, 3 (Sept. 1980), 354-382. Google ScholarDigital Library
- 7 KUNG, H. T., AND PAPADIMITRIOU, C.H. An optimality theory of concurrency control for databases. In Proc. ACM SIGMOD 1979 Int. Conf. Management of Data, May 1979, pp. 116-126. Google ScholarDigital Library
- 8 LAMPORT, L. Towards a theory of correctness for multi-user data base systems. Tech. Rep. CA- 7610-0712, Massachusetts Computer Associates, Inc., Wakefield, Mass., Oct. 1976.Google Scholar
- 9 LEHMAN, P. L., AND YAO, S.B. Efficient locking for concurrent operations on B-trees. Submitted for publication.Google Scholar
- 10 MILLER, R. E., AND SNYDER, L. Multiple access to B-trees. Presented at Proc. Conf. Information Sciences and Systems, Johns Hopkins Univ., Baltimore, Md., Max. 1978.Google Scholar
- 11 PAPADIMITRIOU, C. H., BERNSTEIN, P. A., AND ROTHNIE, J.B. Computational problems related to database concurrency control. In Conf Theoretical Computer Science, Univ. Waterloo, 1977, pp. 275-282.Google Scholar
- 12 PAPADIMITRIOU, C.H. Serializability of concurrent updates. J. ACM 26, 4 (Oct. 1979), 631-653. Google ScholarDigital Library
- 13 SAMADI, B. B-trees in a system with multiple users. Inf. Process. Lett. 5, 4 (Oct. 1976), I07-112.Google ScholarCross Ref
- 14 STEARNS, R. E., LEWIS, P. M., II, AND ROSENKRANTZ, D.J. Concurrency control for database systems. In Proc. 7th Syrup. Foundations of Computer Science, I976, pp. I9-32. Google ScholarDigital Library
- 15 YAo, A. On random 2-3 trees. Acta Inf. 2, 9 (1978), 159-170.Google Scholar
Index Terms
- On optimistic methods for concurrency control
Recommendations
Distributed Optimistic Concurrency Control Methods for High-Performance Transaction Processing
There is an ever-increasing demand for more complex transactions and higher throughputs in transaction processing systems leading to higher degrees of transaction concurrency and, hence, higher data contention. The conventional two-phase locking (2PL) ...
Real-time optimistic concurrency control protocol with dynamic adjustment of serialization order
RTAS '95: Proceedings of the Real-Time Technology and Applications SymposiumProposes a new real-time optimistic protocol. By using a dynamic adjustment of the serialization order by backward-adjusting the non-serious conflicting transactions before the committing transactions, many unnecessary restarts can be eliminated. In the ...
Checkpointing for Optimistic Concurrency Control Methods
Restart-oriented concurrency control (CC) methods, such as optimistic CC, outperform blocking-oriented methods, such as standard two-phase locking in a high data contention environment, but this is at the cost of wasted processing due to restarts. ...
Comments