An efficient database transitive closure algorithm
type: Item
instance of: scholarly article
title: An efficient database transitive closure algorithm
zbMATH Open document ID: 0815.68049
DOI: 10.1007/BF00872109
author: G. Z. Qadah
author: Lawrence Henschen
author: Ismail Hakki Toroslu
published in: Applied Intelligence
publication date: 1994-07-21T00:00:00Z
review text: In deductive databases processing of queries in the form of linearly recursive rules requires the computation of the transitive closure of database relations referenced by these rules. Among various algorithms to compute the transitive closure so-called spanning tree algorithm was known to offer the best performance results. In the article drawbacks of the spanning tree algorithm are discussed and it is shown that there is some redundancy during its computation. In large databases where the overall performance is determined by the number of page I/O occurring between the main memory and the disk certain redundancies in computation may unnecessarily decrease the performance. A new transitive closure algorithm is proposed whose performance is improved by ensuring that no such redundant computations may occur. Finally, results of simulations of both spanning tree algorithm and newly proposed one are presented thus confirming that indeed the new algorithm outperforms the spanning tree one.
reviewed by: Jozef Vyskoč
Mathematics Subject Classification ID: 68P15
Mathematics Subject Classification ID: 68W10
Mathematics Subject Classification ID: 68P20
Mathematics Subject Classification ID: 68T35
zbMATH DE Number: 609555
zbMATH Keywords: deductive databases
zbMATH Keywords: queries
zbMATH Keywords: transitive closure
MaRDI profile type: Publication
cites work: Q3340205
cites work: A modification of Warshall's algorithm for the transitive closure of binary relations
cites work: A Theorem on Boolean Matrices
cites work: A sensitive transitive closure algorithm
full work available at URL: https://doi.org/10.1007/bf00872109
OpenAlex ID: W2022531916
description: scientific article; zbMATH DE number 609555