A Theory of Safe Locking Policies in Database Systems
Mihalis Yannakakis · Journal of the ACM · 1982
When several transacuons access (read and update) the same database concurrently, there must be some kind of coordmauon to ensure that all transacuons receive a consistent view of the data Such coordination is usually achieved by locking the transactions according to some locking policy A locking policy that guarantees the preservation of consistency of the database is called safe Necessary and sufficient conditions are found for a locking pohcy to be safe, but it is shown that in general it is NPcomplete to test for these conditions.However, when the database has a given structure, a simple set of rules which is sufficient for safety and, moreover, necessary for a wide class of natural locking pohcles is developed Categories and SubJect Descriptors DA I [Operating Systems] Process Management--concurrency, H 2 2 [Database Management] Physical Design--deadlock avoMance General Terms.Theory