A Theory of Safe Locking Policies in Database Systems
- 1 July 1982
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 29 (3) , 718-740
- https://doi.org/10.1145/322326.322333
Abstract
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 NP- complete 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 avoManceKeywords
This publication has 5 references indexed in Scilit:
- A fast algorithm for testing for safety and detecting deadlocks in locked transaction systemsJournal of Algorithms, 1981
- Consistency in Hierarchical Database SystemsJournal of the ACM, 1980
- The serializability of concurrent database updatesJournal of the ACM, 1979
- An optimality theory of concurrency control for databasesPublished by Association for Computing Machinery (ACM) ,1979
- The notions of consistency and predicate locks in a database systemCommunications of the ACM, 1976