Processing the transitive-closure logic rules on shared-nothing multiprocessor systems

The author presents and evaluates, using rigorous analytical models, a number of parallel algorithms suitable for processing an important class of recursive queries, the instantiated transitive closure (TC) queries. These algorithms are variants of the sequential δ-wavefront algorithm, designed to run on a shared-nothing (message-passing) type of multiprocessor system. The results obtained indicate that the relative performance of these algorithms is a strong function of not only the parameters which characterize the database and the processed query. Two parallel algorithms have been identified to be the best performing ones, one for systems with slow interconnection networks and the other for systems with fast networks. It is also found that allocating too many nodes to a query which does not need them results in a substantial loss of potential speedup in the processing of the query