article

Free access

A Theory of Safe Locking Policies in Database Systems

Author:

Mihalis YannakakisAuthors Info & Claims

Journal of the ACM (JACM), Volume 29, Issue 3

Pages 718 - 740

https://doi.org/10.1145/322326.322333

Published: 01 July 1982 Publication History

PDF eReader

References

[1]

AHO, A V, HOPCROFT, J E, AND ULLMAN, J D The Deszgn and Analys~s of Computer Algorahms Addlsort Wesley, Reading, Mass, 1974.

Crossref

Google Scholar

[2]

BeRGE, C Graphs and Hypergraphs North Holland, Amsterdam, 1973

Crossref

Google Scholar

[3]

ESWARAN, K.P, GRAY, J N., LORIg, R A, ANt) TRAIGER, I L.On the notions of consistency and predicate locks. Res Rep RJ 1487, IBM Research Lab, San Jose, Cahf, 1974

Google Scholar

[4]

ESWARAN, K P, GRAY, J N, LORIE, R A, AND TRAIGV.R, I L The notions of consistency and predmate locks naa databa~ system Commun ACM 19, 1 t (Nov 1976), 624-633

Crossref

Google Scholar

[5]

GAREY, M R., AND JOHNSON, D.S Computers and Intractabdlty. A Grade to the Theory of NP- Completeness. Freeman, San Francisco, 1978

Crossref

Google Scholar

[6]

GRAY, J N, LORIE, R A, PUTZOLU, G R., AND TRAIGER, L. Granularity of locks and degrees of consistency tn a shared data base Res Rep RJ 1654, IBM Research Lab, San Jose, Cahf., 1975.

Google Scholar

[7]

KEDEM, Z, AND SILBERSCHATZ, A Controlling concurrency using lockxng protocols Proc 20th Ann Symp on Foundattons of Computer Soence, San Juan, Puerto Rico, 1979, pp 274-285.

Google Scholar

[8]

KUNG, H T, AND PAPADIMITRIOU, C H An opttmahty theory of concurrency control for databases ACM-SIGMOD Int Conf. on Managemem of Data, Boston, Mass, 1979, pp. 116-126

Crossref

Google Scholar

[9]

KUNG, H T, AND PAPADIMITRIOU, C H Concurrency control by locking In preparation

Google Scholar

[10]

LIEN, Y E, AND WEINBERGER, P J Conststency, concurrency, and crash recovery ACM-S1GMOD Int. Conf on Management of Data, Austin, Texas, 1978, pp. 9-14.

Crossref

Google Scholar

[11]

LIPSKI, W, AND PAPADIMITRIOU, C H A fast a~gorttha'n for testtag for safety and detectmg deadlocks m locked transaction systems J Atgortthms 2 (1981), 211-226

Google Scholar

[12]

PAPADIMITRIOU, C H The senahzabdlty of concurrent database updates J ACM 26, 4 (Oct t979), 631-653

Crossref

Google Scholar

[13]

PAPADIMITtLIOU, C H, BERNSTEIt', P A, AND ROTHNIE, J II Computattonal problems related to database concurrency control Proc. Conf on Theoretical Computer Scteuce, Umvers~ty of Waterloo, Waterloo, Ontario, Canada, 1977, pp 275-282

Google Scholar

[14]

SILBEr.SCHATZ, A, AND KEDEM, Z Consistency in hierarchical database systems J ACM 27, 1 (Jan ~gs0), 72-80.

Crossref

Google Scholar

[15]

STEARNS, R E, LEwas, P.M., AND ROSENKRANTZ, D J Concurrency control for database systems Proc 17th Ann. Syrup on Foundations of Computer Science, Houston, Texas, 1976, pp 19-32

Google Scholar

[16]

ULLMAN, J D Principles of Database Systems, Computer Science Press, Woodland Hills, Calif, 1979.

Crossref

Google Scholar

[17]

YANNAKAKIS, M. Unpubhshed manuscript

Google Scholar

[18]

YANNAKArdS, M Freedom from deadlock of safe locking pohctes SIAM ~ Comput To appear

Google Scholar

[19]

YANNAKAKIS, M, PAPADIMITRIOU, C.H, AND KUN~, H T Locking pohoes" Safety and freedom from deadlock. Proc 20th Annual Syrup. on Foundauons of Computer Soence, San Juan, Puerto Rico, 1979, pp 286-297

Google Scholar

Cited By

View all

Wieder ABrandenburg B(2014)On the Complexity of Worst-Case Blocking Analysis of Nested Critical Sections2014 IEEE Real-Time Systems Symposium10.1109/RTSS.2014.34(106-117)Online publication date: Dec-2014
https://doi.org/10.1109/RTSS.2014.34
Soisalon-Soininen EYlönen T(2005)Partial strictness in two-phase lockingDatabase Theory — ICDT '9510.1007/3-540-58907-4_12(139-147)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-58907-4_12
Lausen GSoisalon-Soininen E(2005)Locking policies and predeclared transactionsMFDBS 8910.1007/3-540-51251-9_21(317-336)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-51251-9_21
Show More Cited By

Index Terms

A Theory of Safe Locking Policies in Database Systems
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database transaction processing
        Data locking
      2. Distributed database transactions
        Deadlocks
        Distributed data locking
2. Theory of computation
  1. Models of computation
    1. Concurrency
      1. Parallel computing models

Recommendations

Freedom from Deadlock of Safe Locking Policies

The usual method for preserving the consistency of a database when accessed (read and updated) concurrently by several transactions, is by locking the transactions according to some locking policy; a locking policy that guarantees the preservation of ...
Safe Locking Policies for Dynamic Databases
Fourteenth ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems

Yannakakis showed that a locking policy is not safe if and only if it allows a canonical nonserializable schedule of transactions in which all transactions except one are executed serially (Yannakakis, 1982). In the present paper, we study the ...
Analysis of locking policies in database management systems

Consistency control has to be enforced in database management systems (DBMS) where several transactions may concurrently access the database. This control is usually achieved by dividing the database into locking units or granules, and by specifying a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 29, Issue 3

July 1982

302 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322326

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1982

Published in JACM Volume 29, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

67
Total Citations
View Citations
597
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)8

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wieder ABrandenburg B(2014)On the Complexity of Worst-Case Blocking Analysis of Nested Critical Sections2014 IEEE Real-Time Systems Symposium10.1109/RTSS.2014.34(106-117)Online publication date: Dec-2014
Soisalon-Soininen EYlönen T(2005)Partial strictness in two-phase lockingDatabase Theory — ICDT '9510.1007/3-540-58907-4_12(139-147)Online publication date: 2-Jun-2005
Lausen GSoisalon-Soininen E(2005)Locking policies and predeclared transactionsMFDBS 8910.1007/3-540-51251-9_21(317-336)Online publication date: 1-Jun-2005
Lausen GSoisalon-Soininen EWidmayer P(2005)Towards online schedulers based on Pre-Analysis LockingICDT '8610.1007/3-540-17187-8_40(242-259)Online publication date: 2-Jun-2005
Hansdah RPatnaik L(2005)Update serializability in lockingICDT '8610.1007/3-540-17187-8_36(171-185)Online publication date: 2-Jun-2005
Buckley GSilberschatz A(2005)Eliminating cascading rollback in structured databasesFoundations of Software Technology and Theoretical Computer Science10.1007/3-540-13883-8_81(331-343)Online publication date: 31-May-2005
Yu HWeddell GWildberger MHalasz MLufiyya HSinger J(2004)Investigations in tree locking for compiled database applicationsProceedings of the 2004 conference of the Centre for Advanced Studies on Collaborative research10.5555/1034914.1034931(217-231)Online publication date: 4-Oct-2004
Win KWee-Keong Ng Qincai Liu Ee-Peng Lim (2003)Xstamps: a multiversion timestamps concurrency control protocol for XML dataFourth International Conference on Information, Communications and Signal Processing, 2003 and the Fourth Pacific Rim Conference on Multimedia. Proceedings of the 2003 Joint10.1109/ICICS.2003.1292748(1650-1654)Online publication date: 2003
(2002)ReferencesTransactional Information Systems10.1016/B978-155860508-4/50022-3(791-827)Online publication date: 2002
Weikum GVossen G(2001)Transactional Information SystemsundefinedOnline publication date: 30-May-2001
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Freedom from Deadlock of Safe Locking Policies

Safe Locking Policies for Dynamic Databases

Analysis of locking policies in database management systems

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations