AN EFFICIENT DATABASE TRANSITIVE CLOSURE ALGORITHM


TOROSLU I. , QADAH G., HENSCHEN L.

APPLIED INTELLIGENCE, vol.4, no.2, pp.205-218, 1994 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 4 Issue: 2
  • Publication Date: 1994
  • Doi Number: 10.1007/bf00872109
  • Title of Journal : APPLIED INTELLIGENCE
  • Page Numbers: pp.205-218

Abstract

The integration of logic rules and relational databases has recently emerged as an important technique for developing knowledge management systems. An important class of logic rules utilized by these systems is the so-called transitive closure rules, the processing of which requires the computation of the transitive closure of database relations referenced by these rules. This article presents a new algorithm suitable for computing the transitive closure of very large database relations. This algorithm proceeds in two phases. In the first phase, a general graph is condensed into an acyclic one, and at the same time a special sparse matrix is formed from the acyclic graph. The second phase is the main one, in which all the page 1/0 operations are minimized by removing most of the redundant operations that appear in previous algorithms. Using simulation, this article also studies and examines the performance of this algorithm and compares it with the previous algorithms.