An optimal predicate locking scheduler

This paper addresses the problem of designing a predicate locking scheduler that maximizes concurrency, by granting in lock as much as possible of the database entities without compromising the integrity of the database. The scheduling strategy that guarantees the optimal level of concurrency is first defined, then a language for expressing predicates that allows an efficient realization of this strategy is presented. Based on a lattice theoretic formalization of the underlying concepts, a predicate locking scheduler following the optimal scheduling strategy is given. Finally, the range of applicability of this strategy is traced, by showing that any significant extension to the expressive power of the predicate language handled by the scheduler causes an irreparable 1oss of efficiency.