An efficient database transitive closure algorithm

I. H. Toroslu*, G. Z. Qadah, L. Henschen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 I/O 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.

Original languageEnglish (US)
Pages (from-to)205-218
Number of pages14
JournalApplied Intelligence
Volume4
Issue number2
DOIs
StatePublished - May 1 1994

Keywords

  • Knowledge bases
  • deductive databases
  • recursive query processing
  • recursive rules
  • transitive closure queries

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint Dive into the research topics of 'An efficient database transitive closure algorithm'. Together they form a unique fingerprint.

Cite this