Skip to main content

On the Computation of the Transitive Closure of Relational Operators

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.

Citation
Yannis Ioannidis, "On the Computation of the Transitive Closure of Relational Operators ", 12th Int’l VLDB Conference, Kyoto, Japan, August 1986, pp. 403-411, 1986
TAGS
Access
Unknown
Published at
12th Int’l VLDB Conference, Kyoto, Japan, August 1986, pp. 403-411
Related research area
No related research area
Related Organizations
No related organizations