Efficient computation of strong partial transitive-closures

Toroslu İ. H., Qadah G. Z.

1993 IEEE 9th International Conference on Data Engineering, Vienna, Austria, 19 - 23 April 1993, pp.530-537 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume:
  • City: Vienna
  • Country: Austria
  • Page Numbers: pp.530-537
  • Middle East Technical University Affiliated: Yes


The development of efficient algorithms to process the different forms of the transitive-closure (TC) queries within the context of large database systems has recently attracted a large volume of research efforts. In this paper, we present a new algorithm suitable for processing one of these forms, the so called strong partially-instantiated, in which one of the query's argument is instantiated to a set of constants and the processing of which yields a set of tuples that draw their values form both of the query's instantiated and uninstantiated arguments. This algorithm avoids the redundant computations and the high storage cost found in a number of similar algorithms. Using simulation, this paper compares the performance of the new algorithm with those found in literature and shows clearly the superiority of the new algorithm.