Direct Algorithms for Computing the Transitive Closure of Database Relations

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 the best of the direct algorithms perform uniformly better than the best of the iterative algorithms for a large range of underlying data sets.