An Optimality Theory of Concurrency Control for Databases

Summary: Formal theory of concurrency control for time-shared databases; analyzes interleaved transaction steps and scheduler correctness. Defines a fixpoint set as delay-free request sequences; examines how syntactic, semantic, and integrity information shapes scheduling power and information-delay tradeoffs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2165
Venue: SIGMOD
Year: 1979
Pagerank: 0.00014910218
Overall Rank: 695 | 95.24%
DOI: 10.1145/582095.582114

Incoming Non-self Citations Over Time

Authors

1. H. T. Kung (Carnegie Mellon University)
2. C. H. Papadimitriou (Massachusetts Institute of Technology)

BibTeX Citation

@inproceedings{kung_sigmod79,
        title = {{An Optimality Theory of Concurrency Control for Databases}},
        author = {Kung, H. T. and Papadimitriou, C. H.},
        series = {{SIGMOD} '79},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/582095.582114},
        url = {https://dl.acm.org/doi/10.1145/582095.582114},
        year = {1979}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
511	On Concurrency Control by Multiple Versions	1982	PODS	0.00017205623
867	Coordination Avoidance in Database Systems	2015	VLDB	0.00013511197
958	ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging	1992	SIGMOD	0.00012956148
1,189	Sacrificing Serializability to Attain High Availability of Data in an Unreliable Network	1982	PODS	0.00011749508
1,926	An Evaluation of Distributed Concurrency Control	2017	VLDB	9.4705999e-05
2,052	ACIDRain: Concurrency-Related Attacks on Database-Backed Web Applications	2017	SIGMOD	9.251901e-05
2,072	Basic Timestamp, Multiple Version Timestamp, and Two-Phase Locking	1983	VLDB	9.2211825e-05
4,783	Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms	1984	PODS	6.5091522e-05
5,994	On the Power of Locking	1981	SIGMOD	6.0157542e-05
8,776	Concurrent Operations in Extendible Hashing	1986	VLDB	5.3766157e-05
9,912	THEORY OF SERIALIZABILITY FOR A PARALLEL MODEL OF TRANSACTIONS (Extended Abstract)	1982	PODS	5.1972596e-05
12,086	The Case for Invariant-Based Concurrency Control	2015	CIDR	5.093636e-05
13,209	A semantic approach to correctness of concurrent transaction executions	1985	PODS	5.093636e-05
13,221	Locking with Prevention of Cyclic and Infinite Restarting in Distributed Database Systems	1985	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,959	Secure Transaction Processing in Firm Real-Time Database Systems	1997	SIGMOD
2	14,538	A Formal Model for Maximum Concurrency in Transaction Systems with Predeclared Writesets	1982	VLDB
3	4,237	Experimental Evaluation of Real-Time Optimistic Concurrency Control Schemes	1991	VLDB
4	14,477	Maximal Concurrency By Locking	1984	PODS
5	7,984	Parallelism and Concurrency Control Performance in Distributed Database Machines	1989	SIGMOD
6	2,911	The Performance of Concurrency Control Algorithms for Database Management Systems	1984	VLDB
7	260	Models for Studying Concurrency Control Performance: Alternatives and Implications	1985	SIGMOD
8	14,468	The Complexity of Reliable Concurrency Control	1985	PODS
9	4,176	An Abstract Model of Database Concurrency Control Algorithms	1983	SIGMOD
10	3,882	On Being Optimistic about Real-Time Constraints	1990	PODS