Survey of Parallel Execution Strategies for Transitive Closure and Logic Programs

摘要

The authors survey the approaches to parallel execution of recursive querieswhich have been presented in the recent literature. They observe that research on parallel execution of recursive queries is separated into two distinct sub-areas, one focused on the transitive closure of Relational Algebra expressions, the other one focused on Datalog optimization. Though the sub-areas seem radically different for the approach and formalism used, indeed they have many features in common; actually, the most typical Datalog queries have exactly the same expressive power as transitive closure of simple algebraic expressions. Thus, the first goal of the paper is establishing the equivalence among solution methods developed in each sub-area. The authors present a graphic formalism for describing parallel executions; they review algorithms developed in the frame of algebraic transitive closures which operate on entire relations; then they introduce fragmentation, distinguishing between hash-based and semantic fragmentation; finally, they consider general Datalog queries.