Abstract Run-Time Parallelization of Sequential Database Programs

In order to execute a database program written in sequential code efficiently on a parallel processor, we develop the use of transaction concurrency control paradigms to resolve data dependencies dynamically. The sequential code is divided into small units for execution, and these units are executed concurrently as separate “transactions. ” Our approach en. sures that the concurrent execution of the smaller units is logically equivalent to the original sequential program. We present an order-preserving concurrency control strategy to execute concurrently the nested invocations that are generated by the parallelized execution of the database program. We present performance figures from a preliminary imple-mentation to indicate the benefits of our strategy. Finally, we provide a rough analysis to gauge the overheads associated with our approach that would impact performance in a full-fledged implementation.