Transitive Closure Algorithms Based on Graph Traversal
Authors: 
Yannis Ioannidis
Authors: 
Raghu Ramakrishnan
Authors: 
Linda Winger
Date published: 
1993
Published In: 
ACM Transactions on Database Systems (TODS), Vol. 18, No. 3, Sept. 1993, pp. 512-576
Type: 
Journal Article
Abstract: 

Several graph-based algorithms have been proposed in the literature to compute the transitive closure of a directed graph. We develop two new algorithms (Basic_TC and Global _DFTC) and compare the performance of their implementations in a disk-based environment with a wellknown graph-based algorithm proposed by Schmitz. Our algorithms use depth-first search to traverse a graph and a technique called marking to avoid processing some of the arcs in the graph. They compute the closure by processing nodes in reverse topological order, building descendent sets by adding the descendent sets of children. While the details of these algorithms differ considerably, one important difference among them is the time at which descendent set additions are performed Basic_TC performs a separate depth-first traversal to obtain the topological order of nodes and does additions in a second pass. Global_DFTC performs additions whenever two sets that must be added are in memory, thereby eliminating the need to bring these sets in again later. The Schmitz algorithm is intermediate in this respect, deferring the addition of the descendent set of a child to that of a parent until the root of the strong component containing the parent is identified. Contrary to our expectations, deferring additions as much as possible, as in Basic_TC, results in superior performance. The first reason is that early additions result in larger descendent set sizes on the average over the duration of the execution, thereby causing more I/O; very often this turns out to more than offset the gains of not having to fetch certain sets again to add them. The second reason is that information collected in the first pass can be used to apply several optimizations in the second pass. To the extent possible, we also adapt these algorithms to perform path computations. Again, our performance comparison confirms the trends seen in reachability queries. Taken in conjunction with another performance study our results indicate that all graph-based algorithms significantly outperform other types of algorithms such as Semmaive and Warren.

Related files: 

MaDgIK 2009-2016