Efficient computation of strong partial transitive-closures

Toroslu İ. H. , Qadah G. Z.

1993 IEEE 9th International Conference on Data Engineering, Vienna, Avusturya, 19 - 23 Nisan 1993, ss.530-537 identifier

  • Cilt numarası:
  • Basıldığı Şehir: Vienna
  • Basıldığı Ülke: Avusturya
  • Sayfa Sayıları: ss.530-537


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.