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
Keywords :
data compression; deductive databases; graph theory; search problems; breadth-first search; deductive database systems; disk I/O; graph compression method; partial transitive closures; simulation; strongly connected components; temporary results; traversal strategy; Computational modeling; Database systems; Deductive databases; Graph theory; Information systems; Minimization methods; Query processing; Spatial databases;
