A SURVEY OF PARALLEL EXECUTION STRATEGIES FOR TRANSITIVE CLOSURE AND LOGIC PROGRAMS

An important feature of database technology of the nineties is the use of parallelism for speeding up the execution of complex queries. This technology is being tested in several experimental database architect ures and a few commercial systems for conventional select-project-join queries. In particular, hash-based fragmentation is used to distribut e data to disks under the control of different processors in order to perform selections and joins in parallel. With the development of new query languages, and in particular with the definition of transitive c losure queries and of more general logic programming queries, the new dimension of recursion has been added to query processing. Recursive q ueries are complex; at the same time, their regular structure is parti cularly suited for parallel execution, and parallelism may give a high efficiency gain. We survey the approaches to parallel execution of re cursive queries that have been presented in the recent literature. We observe that research on parallel execution of recursive queries is se parated into two distinct subareas, one focused on the transitive clos ure of Relational Algebra expressions, the other one focused on optimi zation of more general Datalog queries. Though the subareas seem radic ally different because of the approach and formalism used, they have m any common features. This is not surprising, because most typical Data log queries can be solved by means of the transitive closure of simple algebraic expressions. We first analyze the relationship between the transitive closure of expressions in Relational Algebra and Datalog pr ograms. We then review sequential methods for evaluating transitive cl osure, distinguishing iterative and direct methods. We address the par allelization of these methods, by discussing various forms of parallel ization. Data fragmentation plays an important role in obtaining paral lel execution; we describe hash-based and semantic fragmentation. Fina lly, we consider Datalog queries, and present general methods for para llel rule execution; we recognize the similarities between these metho ds and the methods reviewed previously, when the former are applied to linear Datalog queries. We also provide a quantitative analysis that shows the impact of the initial data distribution on the performance o f methods.