article

Free access

The serializability of concurrent database updates

Author:

Christos H. PapadimitriouAuthors Info & Claims

Journal of the ACM (JACM), Volume 26, Issue 4

Pages 631 - 653

https://doi.org/10.1145/322154.322158

Published: 01 October 1979 Publication History

PDF eReader

References

[1]

AHO, A V, HOPCROI:T, J E, AND ULLMAN, J D The Design and Analysts of Computer Algoruhms Addtson- Wesley, Readtng, Mass, 1974

Crossref

Google Scholar

[2]

BERNSTEIN, P A, GOODMAN, N. ROTHNIE, J B, AND PAPADIMITRIOU, C H Analysts of senahzabdtty of SDD-1' a system of d,stnbuted databases (the fully redundant case). IEEE Trans. on Software Eng SE-4, 3 (May 1978), 154-168

Google Scholar

[3]

BERNSTEIN, P A, PAPADIMITRIOU, C H., AND ROTHNIE, J B Resolving certam concurrent update problems wnhout locking an abstract Proc IEEE Workshop on OS and DBMS, Chtcago, I11, 1977

Google Scholar

[4]

BERNSTEIN, P A, AND SHIPMAN, D W A formal model of concurrency control mechamsms for database systems Proc 1978 Berkeley Workshop on Dtstdbuted Databases and Comptr Networks, Berkeley, Cahf, Sept 1978, pp 189-205~

Google Scholar

[5]

BERNSTEIN, P A, SHIPMAN, D W, ROTHNIE, J B, AND GOODMAN, N The concurrency control mechanism of SDD-1 a system for d~stnbuted databases (the general case) TR CCA-77-09, Computer Corporation of America, Cambridge, Mass, 1977

Google Scholar

[6]

COFFMAN, E G, AND DENNING, P Operatmg Systems Theory Prentice-Hall, Englewood Cliffs, N J., 1973.

Crossref

Google Scholar

[7]

ESWARAN, K P, GRAY, J N, LORIE, R A, AND TRAIGER, I L The notions of consistency and predicate locks Jn a database system, Comm,4 CM 19, 11 (Nov 1976), 624-633

Crossref

Google Scholar

[8]

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

Crossref

Google Scholar

[9]

KARP, R M Reducibdmes among combinatorial problems In Complexay of Computer Computaoons, R E Miller and J W Thatcher, Eds, Plenum Press, New York, 1972, pp 85-103

Google Scholar

[10]

KUNG, H T, AND LEHMAN, P L A concurrent database problem binary search trees, an abstract. Proc 4th Int Conf on Very Large Databases, West Berlin, Germany, 1978, p 498 (Full paper to appear in A CM Trans Data Base Syst )

Google Scholar

[11]

KUNG, H T, AND PAPADIMITRIOU, C H An optimahty theory of concurrenc} control for databases. Proc 1979 SIGMOD Conf, Boston, Mass., May, 1979

Crossref

Google Scholar

[12]

LAMPORT, L Towards a theory of correctness for multi-user data base systems. TR CA-7610-0712, Massachusetts Computer Associates, 1976

Google Scholar

[13]

LAMPORT, L Time, clocks and ordering of events m a distributed system TR CA-7603-2911, Massachusetts Computer Associates, 1976

Google Scholar

[14]

LUCKHAM, D C, PARK, D M R, AND PATERSON, M S. On formalized computer programs J Comptr. Syst Sct 4, 3 (1970), 220-249

Google Scholar

[15]

PAPADIMITRIOLI, C H, BERNSTEIN, P A, AND ROTHNIE, J B Computational problems related to database concurrency control Proc Conf on Theor Comptr Sci, U of Waterloo, Ontario, Canada, 1977.

Google Scholar

[16]

PAPADIMITRIOU, C H, AND STEIGLITZ, K Combinatorial Opmnlzat~on Algorahms. (In preparation )

Google Scholar

[17]

ROTHNIE, J B, AND GOODMAN, N An overview of the preliminary design of SSD-I: a system of distributed databases Proc 1977 Berkeley Workshop on Distributed Data Management and Comptr. Networks, Berkeley, Cahf, May 1977

Google Scholar

[18]

SILBERSCHATZ, A, AND KEDEM, Z Consistency in hierarchical database systems (To appear in Jr. ACM.)

Crossref

Google Scholar

[19]

STEARNS, R C, LEWIS, P M, AND ROSENKRANTZ, D J Concurrency control for database systems Proc. 16th Conf Found Comptr Sct, 1976, pp 19-32

Google Scholar

[20]

TARJAN, R E Depth-first search and linear graph algorithms Slam J Comptg 1, 2 (1973), 146-160.

Google Scholar

[21]

THOMAS, R H A solution to the update problem for multiple copy databases which uses distributed control TR 3340, Bolt, Beranek and Newman, Cambridge, Mass, 1976

Google Scholar

[22]

WONG, W Analysis of senahzable logs Unpublished manuscript, Harvard Umversity, Cambridge, Mass, 1978

Google Scholar

Cited By

View all

Schellhorn GBodenmüller SReif W(2025)Verification of forward simulations with thread-local, step-local proof obligationsScience of Computer Programming10.1016/j.scico.2024.103227241(103227)Online publication date: Apr-2025
https://doi.org/10.1016/j.scico.2024.103227
Cheng AKabcenell AChan JShi XBailis PCrooks NStoica I(2024)Towards Optimal Transaction SchedulingProceedings of the VLDB Endowment10.14778/3681954.368195617:11(2694-2707)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681956
Liu SGu LWei HBasin D(2024)Plume: Efficient and Complete Black-Box Checking of Weak Isolation LevelsProceedings of the ACM on Programming Languages10.1145/36897428:OOPSLA2(876-904)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689742
Show More Cited By

Index Terms

The serializability of concurrent database updates

Recommendations

Concurrent updates with RCU: search tree as an example
PODC '14: Proceedings of the 2014 ACM symposium on Principles of distributed computing

Read copy update (RCU) is a novel synchronization mechanism, in which the burden of synchronization falls completely on the updaters, by having them wait for all pre-existing readers to finish their read-side critical section. This paper presents citrus,...
Formal Aspects of Serializability in Database Concurrency Control

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 ...
SERIALIZABILITY OF CONCURRENT DATA BASE UPDATES

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 26, Issue 4

Oct. 1979

231 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322154

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1979

Published in JACM Volume 26, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

800
Total Citations
View Citations
2,902
Total Downloads

Downloads (Last 12 months)363
Downloads (Last 6 weeks)35

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Schellhorn GBodenmüller SReif W(2025)Verification of forward simulations with thread-local, step-local proof obligationsScience of Computer Programming10.1016/j.scico.2024.103227241(103227)Online publication date: Apr-2025
https://doi.org/10.1016/j.scico.2024.103227
Cheng AKabcenell AChan JShi XBailis PCrooks NStoica I(2024)Towards Optimal Transaction SchedulingProceedings of the VLDB Endowment10.14778/3681954.368195617:11(2694-2707)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681956
Liu SGu LWei HBasin D(2024)Plume: Efficient and Complete Black-Box Checking of Weak Isolation LevelsProceedings of the ACM on Programming Languages10.1145/36897428:OOPSLA2(876-904)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689742
Vandevoort BKetsman BNeven F(2024)When View- and Conflict-Robustness Coincide for Multiversion Concurrency ControlProceedings of the ACM on Management of Data10.1145/36515922:2(1-16)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651592
Dumbrava SJin ZKulahcioglu Ozkan BQiu JRoychoudhury APaiva AAbreu RStorey M(2024)GRAIL: Checking Transaction Isolation Violations with Graph QueriesProceedings of the 2024 IEEE/ACM 46th International Conference on Software Engineering: Companion Proceedings10.1145/3639478.3643094(320-321)Online publication date: 14-Apr-2024
https://dl.acm.org/doi/10.1145/3639478.3643094
Liu SMultazzu LWei HBasin D(2024)NOC-NOC: Towards Performance-optimal Distributed TransactionsProceedings of the ACM on Management of Data10.1145/36392642:1(1-25)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639264
Tzialla IWang JZhu JPanda AWalfish M(2024)Efficient Auditing of Event-driven Web ApplicationsProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3650089(1208-1224)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3650089
Clark JDonaldson AWickerson JRigger M(2024)Validating Database System Isolation Level Implementations with Version Certificate RecoveryProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3650080(754-768)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3650080
Gupta AKulkarni S(2024)Tolerance to Asynchrony of an Algorithm for Gathering Myopic Robots on an Infinite Triangular Grid2024 19th European Dependable Computing Conference (EDCC)10.1109/EDCC61798.2024.00023(61-68)Online publication date: 8-Apr-2024
https://doi.org/10.1109/EDCC61798.2024.00023
Vafeiadi Bila EDongol B(2024)A verified durable transactional mutex lock for persistent x86-TSOFormal Methods in System Design10.1007/s10703-024-00462-1Online publication date: 31-Jul-2024
https://doi.org/10.1007/s10703-024-00462-1
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

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

Concurrent updates with RCU: search tree as an example

Formal Aspects of Serializability in Database Concurrency Control

SERIALIZABILITY OF CONCURRENT DATA BASE UPDATES

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

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations