A suitable algorithm for computing partial transitive closures in databases

Abstract

The computation of partial transitive closures is considered as an elementary operation for implementing deductive database systems. A new algorithm supporting this operation is presented. Unlike previously published algorithms, which are based on either matrix manipulations or depth-first search strategy, the algorithm presented uses breadth-first search as its dominant traversal strategy, a graph compression method to minimize temporary results, and Tarjan's technique in a new way to deal with strongly connected components. It is shown that this algorithm is especially suitable for computing partial transitive closures in databases, for it also aims at the minimization of disk I/O. Preliminary results of a simulation confirm this suitability. In addition, considerations about the implementation are presented.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>