On the Computation of the Transitive Closure of Relational Operators
Yannis Ioannidis
Date published: 
Published In: 
12th Int’l VLDB Conference, Kyoto, Japan, August 1986, pp. 403-411
Conference Article

Query processing in the presence of recursively defined views usually involves some form of iteration. For example, computing the transitive closure of a tree involves iterating N times, where N is the depth of the tree, each time computing pairs of vertices that are one edge further apart than the pairs produced in the previous iteration. Applying a divide and conquer technique we devise algorithms that need a logarithmic number of iterations. Assuming that we are looking for complete materializations of the recursively defined relations we show both through analytical and experimental results that this approach is in many cases superior in performance than the N-iteration algorithm.

Related files: 

MaDgIK 2009-2016