New transitive closure algorithm for recursive query processing in deductive databases

Toroslu İ. H., Qadah G.

4th International Conference on Tools with Artificial Intelligence, ICTAI 1992, Virginia, United States Of America, 10 - 13 November 1992, pp.268-275 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume:
  • Doi Number: 10.1109/tai.1992.246414
  • City: Virginia
  • Country: United States Of America
  • Page Numbers: pp.268-275
  • Middle East Technical University Affiliated: No


© 1992 IEEE.The development of effic1.e11t algorithms to process the different forms of the transitive-closure (TC) queries within the context of large database systems has recently attracted a large amom1t of research efforts. In this paper, we present a neic algorithm suitable for full transitive closure problem, which zs used to solve uninstentiated recursive qi1enes in deductive databases. In this new algorithm there are two phases. In the first phase a general graph is condensed into an acyclic graph and at the same time a special sparse matrix is formed from the acyclic graph. The second phase is the main one where all of the page I/ 0 operations are minimized. Using szmulatwn, this paper also studies and examines the performance of thzs algorithm and compares it with the pruiovs algorithms.