Efficient algorithms for the instantiated transitive closurequeries |
| |
Authors: | Qadah GZ Henschen LJ Kim JJ |
| |
Affiliation: | Dept. of Electr. Eng. & Comput. Sci., Northwestern Univ., Evanston, IL; |
| |
Abstract: | The performances of several algorithms suitable for processing an important class of recursive queries called the instantiated transitive closure (TC) queries are studied and compared. These algorithms are the wavefront, δ-wavefront, and a 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. A comprehensive performance evaluation of these three algorithms using rigorous analytical and simulation models is presented. The 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. The superiority of one of the super-TC variants over all of the other presented algorithms is shown |
| |
Keywords: | |
|
|