FORMAL ASPECTS OF SERIALIZABILITY IN DATABASE CONCURRENCY CONTROL

被引：94

作者：

BERNSTEIN, PA

SHIPMAN, DW

WONG, WS

机构：

[1] Computer Corporation of America, Cambridge

[2] Cornputer Corporation of America, Cambridge

[3] Harvard University, Cambridge

来源：

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING | 1979年 / 5卷 / 03期

关键词：

database system; Index Terms-Concurrency control; locking; serializability; transaction synchronization;

D O I：

10.1109/TSE.1979.234182

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

An arbitrary interleaved execution of transactions in a database system can lead to an inconsistent database state. A number of synchronization mechanisms have been proposed to prevent such spurious behavior. To gain insight into these mechanisms, we analyze them in a simple centralized system that permits one read operation and one write operation per transaction. We show why locking mechanisms lead to correct operation, we show that two proposed mechanisns for distributed environments are special cases of locking, and we present a new version of locking that allows more concurrency than past methods. We also examine conflict graph analysis, the method used in the SDD-1 distributed database system, we prove its correctness, and we show that it can be used to substantially improve the performance of almost any synchronization mechanisn. Copyright © 1979 by The Institute of Electrical and Electronics Engineers, Inc.

引用

页码：203 / 216

页数：14

共 17 条

[1] Aho A.V., Hopcroft J., Ullman J., The Design and Analysis of Computer Algorithms, (1975)
[2] Bernstein P.A., Goodman N., Rothnie J.B., Papadimitriou C.H., Analysis of serialization in SDD-1: A system for distributed databases, Proc. 1977 IEEE COMPSAC Conf., (1977)
[3] Bernstein P.A., Shipman D.W., Rothnie J.B., Goodman N., The concurrency control mechanism of SDD-1: A system for distributed databases
[4] Bernstein P.A., Rothnie J.B., Goodman N., Papadimitriou C.H., The concurrency control mechanism of SDD-1: A system for distributed databases (the fully redundant case), IEEE Trans. Software Eng., SE-4, pp. 154-168, (1978)
[5] Bernstein P.A., Shipman D.W., A new analysis of concurrency rency control in SDD-1
[6] A system for distributed databases, Computer Corp. America, Tech. Rep. CCA-78-08, (1978)
[7] Chamberlin D.D., Boyce R.F., Traiger I.L., A deadlock-free free scheme for resource allocation in a data-base environment, 1974 IFIPS Conf. Proc, pp. 340-343, (1974)
[8] Eswaran K.P., Gray J.N., Lorie R.A., Traiger I.L., The notions of consistency and predicate locks in a database system, Commun. Ass. Comput. Mach., 19, pp. 624-633, (1976)
[9] Gray J.N., Lorie R.A., Putzolu G.R., Traiger I.L., Granularity of locks and degrees of consistency in a shared data base
[10] Lamport L., Towards a theory of correctness of multi-user data base systems

← 1 2 →