The strong partial transitive-closure problem: Algorithms and performance evaluation

Toroslu I., Qadah G.

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, cilt.8, sa.4, ss.617-629, 1996 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 8 Sayı: 4
  • Basım Tarihi: 1996
  • Doi Numarası: 10.1109/69.536254
  • Dergi Adı: IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.617-629
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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