Back to Search
Start Over
Efficient Algorithms for the Instantiated Transitive Closure Queries .
- Source :
-
IEEE Transactions on Software Engineering . Mar91, Vol. 17 Issue 3, p296-309. 14p. 3 Color Photographs, 3 Diagrams, 3 Charts, 8 Graphs. - Publication Year :
- 1991
-
Abstract
- This paper studies and compares the performance of several algorithms suitable for processing an important class of recursive queries, the so-called instantiated transitive closure (TC) queries. These algorithms are the two well known algorithms wavefront and .5-wavefront and a newly proposed generic algorithm called super-TC. During the evaluation of a TC query, the first two algorithms may read a given disk page more than once, whereas super-TC reads the disk page at most once. This paper also presents a comprehensive performance evaluation of these three algorithms using rigorous analytical and simulation models. Such a study reveals that the relative performance of the algorithms is a strong function of the parameters which characterize the processed TC query and the relation referenced by that query. Furthermore, it points out the superiority of one of the super-TC variants over all of the other presented algorithms. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00985589
- Volume :
- 17
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Software Engineering
- Publication Type :
- Academic Journal
- Accession number :
- 14303389
- Full Text :
- https://doi.org/10.1109/32.75418