Efficient Algorithms for the Instantiated Transitive Closure Queries

Ghassan Z. Qadah, Lawrence Joseph Henschen, Jung J. Kim

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

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

Original languageEnglish (US)
Pages (from-to)296-309
Number of pages14
JournalIEEE Transactions on Software Engineering
Volume17
Issue number3
DOIs
StatePublished - Mar 1991

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Efficient Algorithms for the Instantiated Transitive Closure Queries'. Together they form a unique fingerprint.

Cite this