Author_Institution :
Dept. of Comput. Sci., Southern Methodist Univ., Dallas, TX, USA
Abstract :
A non-two-phase database concurrency control technique is introduced. The technique is deadlock-free, places no restrictions on the structure of the data, never requires data to be reread, never forces a transaction to be rolled back in order to achieve serializability, applies a type of lock conversion, and allows items to be released to subsequent transactions as soon as possible. The method introduced, database flow graph locking (FGL), uses a directed acyclic graph to direct the migration of locks between transactions. Unlike many previous non-two-phase methods, the database need not be structured in any specific fashion. The effect of these changes is that, with the same serializable schedule, FGL obtains a higher degree of concurrency than two-phase locking (2PL). Overhead requirements for database flow graph locking are comparable to those for two-phase locking, with 2PL being better in low conflict situations and FGL better in high conflict
Keywords :
database theory; directed graphs; distributed databases; system recovery; database concurrency control; database flow graph locking; deadlock-free; directed acyclic graph; distributed databases; lock conversion; non-two-phase methods; Concurrency control; Concurrent computing; Control systems; Database systems; Flow graphs; Force control; Protocols; System recovery; Transaction databases; Tree graphs;