Efficient Algorithms for the Instantiated Transitive Closure Queries

This paper studies and compares the performance of several algorithms suitable for processing an important class of recursive queries, the so-called instantiated transitive closure (TC) queries. These algorithms are the two well known algorithms wavefront and δ -wavefront and a newly proposed generic algorithm called super-TC. During the evaluation of a TC query, the first two algorithms may read a given disk page more than once, whereas super-TC reads the disk page at most once. This paper also presents a comprehensive performance evaluation of these three algorithms using rigorous analytical and simulation models. Such a study reveals that the relative performance of the algorithms is a strong function of the parameters which characterize the processed TC query and the relation referenced by that query. Furthermore, it points out the superiority of one of the super-TC variants over all of the other presented algorithms.