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.