Parallel evaluation of deductive database queries
Šumit Ganguly · 1992
In this dissertation, we are concerned with the parallel bottom-up evaluation of a subset of deductive database languages called Datalog. We present a family of parametric parallelization strategies for Datalog programs. Several algorithms that were independently proposed for the parallel computation of specific Datalog programs can be obtained by properly choosing the parameters. The choice of the parallelization parameters significantly influences some properties of the resulting parallel executions, such as inter-process communication and fragmentation of the database. We present an algorithm to determine the minimal logical connectivity of the communicating processors, given a choice of the parallelization parameters. We also investigate the converse of the above question; namely, given a Datalog program and a network of processors, is it possible to choose the parallelization parameters such that the resulting parallel execution can be mapped onto the network of processors? This question is similar in nature to the question of mapping numerical algorithms to a systolic array of processors. However, unlike numerical algorithms, Datalog programs display very little structure; for example, there is no notion of a loop index or an array index. It is therefore somewhat surprising that this question can be decided algorithmically for a very large class of Datalog programs. Given a particular database system, it is an interesting question to choose the parallel execution which results in minimum response time. Unfortunately, accurate cost models estimating the computational cost of recursive Datalog programs is not available. Hence, optimizing for the parallel execution of recursive Datalog programs is difficult. We thus restrict our attention to the problem of optimizing non-recursive Datalog programs for parallel executions. Our contributions to this problem domain are: (1) Presentation of a clear execution space and cost model that models data dependency, independent parallelism and pipelined parallelism. (2) The observation that dynamic programming search strategies need to be extended to use partial orders; that is, plans must be compared simultaneously along different dimensions. We show how such metrics may be designed within our model. (3) An initial investigation into modeling resource usage on two different architectures. We propose that inherent symmetry of systems should be used to decrease the dimensions of the search.