We discuss a technique for query evaluation based on storing intermediary results as trees and study two applications. We first consider the problem of computing the transitive closure of a graph for a specific set of source nodes. Algorithms for this problem can be directly applied to many nonrecursive queries as well. We give a new algorithm and show that it is superior to several previous algorithms. We then consider Warshall's transitive closure algorithm. This algorithm is not O(n e), but we show that by using trees instead flat representations of intermediary results, we can derive a new version of the algorithm with an O(n e> upper bound.

We study two different approaches for computing the transitive closure of a directed graph and show that, in some sense, they are "dual" on edge-reversed graphs but, nevertheless, can differ asymptotically in cost on the same family of graphs.We show how the two approaches can be mixed into a new algorithm using reachability trees.We show that the new algorithm is o(~(~,yj~vxv CON~(Z, y)) where COMV(z, y) is the pairwise connectivity of z and y, and give a more exact connectivity-based upper bound that is better than the lower bound for a wide class of other algorithms on every family of graphs.