The processing of a class of transitive-closure queries on uniprocessor and shared-nothing multiprocessor systems

摘要

This paper examines, using probabilistic average-valued analytical models, the performance of the δ-wavefront, a sequential algorithm suitable for processing an important class of recursive queries, the partially-instantiated closure (TC) ones. Moreover, it develops and evaluates several parallel variants to the δ-wavefront algorithm. These variants assume the shared-nothing (message-passing) multi-processor organization. The studies presented in this paper reveal, among other findings, that the performance of the δ-wavefront algorithm and its variants is strongly dependent on the characteristics of the system's hardware, the processed base-relation and, to a less degree, the processed query. Although the speed of the different parallel variants has been found to exhibit anomalous behavior (i.e. an increase in the number of processing nodes in the distributed system beyond a certain value brings a decrease in the speed of these algorithms rather than an increase), nevertheless, this study reveals that the processing of a TC query can be greatly speeded up provided that the proper parallel variant and the proper number of processing nodes are chosen. Two parallel variants to the δ-wavefront algorithm are identified to possess the best performance, one for systems with a slow interconnect and the other for systems with a fast one.