Graph directed locking

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