Parallel computation of direct transitive closures
- 10 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 192-199
- https://doi.org/10.1109/icde.1991.131466
Abstract
To efficiently process recursive queries in a DBMS (database management system), a parallel, direct transitive closure algorithm is proposed. Efficiency is obtained by reorganizing the computation order of Warren's algorithm. The number of transfers among processors depends only on the number of processors and does not depend on the depth of the longest path. The evaluation shows an improvement due to the parallelism and the superiority of the proposed algorithm over recent propositions. The speed of the production of new tuples is very high and the volume of transfers between the sites is reduced.Keywords
This publication has 8 references indexed in Scilit:
- Multiprocessor Transitive Closure AlgorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- On modelling a type of communications in some communications intensive applicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Parallel evaluation of the transitive closure of a database relationInternational Journal of Parallel Programming, 1988
- An amateur's introduction to recursive query processing strategiesACM SIGMOD Record, 1986
- Traversal recursion: a practical approach to supporting recursive applicationsPublished by Association for Computing Machinery (ACM) ,1986
- A sensitive transitive closure algorithmInformation Processing Letters, 1981
- A modification of Warshall's algorithm for the transitive closure of binary relationsCommunications of the ACM, 1975
- A Theorem on Boolean MatricesJournal of the ACM, 1962