Concurrency control and transaction processing in a parallel database machine environment
Ravindran Krishnamurthy · 1982
A parallel program schema model of transaction systems for parallel database machines is presented and the concept of serializability is extended to this model. Two classes of serializable executions (SR- and DSR-classes) are defined and for each class two problems: recognition and scheduling are discussed. It is shown that the results for recognition and online scheduling problems (for the sequential model) generalize to the parallel model. But it is argued that online scheduling is not suitable for a parallel execution environment. Therefore, batch schedulers are defined, and shown that the smallest complete class scheduled by any scheduler is DSR-class. A minimal set of precedence constraints for a DSR-schema (corresponding to a particular SX(,p)) is derived. Finally, it is shown that any optimal batch scheduler that uses syntactic information alone cannot be efficient. To counter this intractability, we propose a two-step technique for producing correct and highly parallel schedules: first, obtain a schema that imposes a minimal set of precedence constraints on correct executions; then, transform the schema using semantic information to increase parallelism. Although the model developed here is theoretical, we believe it to be of practical utility--the proposed scheduling technique can be applied to any MIMD machine such as DIRECT {DeW78}.