To establish the behavior of algorithms in a paging environment, the author analyzes the input/output (I/O) efficiency of several representative shortest path algorithms. These algorithms include single-course, multisource, and all pairs ones. The results are also applicable for other path problems such as longest paths, most reliable paths, and bill of materials. The author introduces the notation and a model of a paging environment. The I/O efficiencies of the selected single-source, all pairs, and multisource algorithms are analyzed and discussed.>

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.>