AN OPTIMAL PREDICATE LOCKING SCHEDULER

The paper presents a predicate locking scheduler that maximizes concur rency 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 f irst identified, then a predicate language allowing an efficient imple mentation of this strategy is given. The optimal predicate locking sch eduler is successively presented, based on a lattice-theoretic formali zation 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 lan guage accepted by the optimal scheduler causes an irreparable loss of efficiency. (C) 1996 Academic Press, Inc.