|
Abstract : |
We present new algorithms for computing the transitive closure of large database relations. Unlike iterative algorithms, such as the semi-naive and the logarithmic algorithms, the termination of our algorithms does not depend on the length of paths in the underlying graph (hence, the name direct algorithms). We also present simulation results that show that these direct algorithms perform uniformly better than the best of the iterative algorithms. A side benefit of this work is that we have proposed a new methodology for evaluating the performance of recursive queries. 1. INTRODU~ION With the increasing ?non-traditional ? uses of relational databases, several extensions have been proposed to the relational query languages in order to efficiently support these applications. A common operator that appears in many of these proposals is the transitive closure operation (see, for example, Zloofs QBE Il71, Guttman?s l extension to Quel 171, Probe?s traversal recursion [lll, and Agrawal?s (r-extended relational algebra I1 I). In [91, it has been shown that every linearly recursive query can be expressed as a transitive closure possibly preceded and followed by operations already available in relational algebra, once again emphasizing the importance of Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VWB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data, |
