Research indexJournal article
A suitable algorithm for computing partial transitive closures in databases
Jiang
4 Dec 2002
NobleIDark:/48914/w1/20260521/F77BE586DOI10.1109/icde.1990.113477
A suitable algorithm for computing partial transitive closures in databases
Jiang · 2002 · Subscription
NobleIDark:/48914/w1/20260521/F77BE586DOI10.1109/icde.1990.113477
The full text is at the publisher
You can read the abstract here, or open it at the publisher.
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.< >