A suitable algorithm for computing partial transitive closures in databases
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 264-271
- https://doi.org/10.1109/icde.1990.113477
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
This publication has 34 references indexed in Scilit:
- Moving selections into linear least fixpoint queriesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Semantic query optimization in recursive databasesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Making the Partial Transitive Closure an Elementary Database OperationInformatik-Fachberichte, 1989
- One-sided recursionsPublished by Association for Computing Machinery (ACM) ,1987
- Architecture and implementation of the Darmstadt database kernel systemPublished by Association for Computing Machinery (ACM) ,1987
- Handling redundancy in the processing of recursive database queriesPublished by Association for Computing Machinery (ACM) ,1987
- Data independent recursion in deductive databasesPublished by Association for Computing Machinery (ACM) ,1985
- A fast expected time algorithm for Boolean matrix multiplication and transitive closureInformation and Control, 1973
- Efficient determination of the transitive closure of a directed graphInformation Processing Letters, 1971
- A transitive closure algorithmBIT Numerical Mathematics, 1970