An optimal predicate locking scheduler

The paper presents a predicate locking scheduler that maximizes concurrency by locking as many of the database entities as possible without compromising the correctness of execution of the database transactions. The scheduling strategy that guarantees the maximal concurrency is first identified, then a predicate language allowing an efficient implementation of this strategy is given. The optimal predicate locking scheduler is successively presented, based on a lattice-theoretic formalization of the underlying concepts. Finally, the range of applicability of the optimal scheduling strategy is circumscribed, by showing that any significant extension to the expressive power of the predicate language accepted by the optimal scheduler causes an irreparable loss of efficiency. © 1996 Academic Press, Inc.