An efficient database transitive closure algorithm (Q1330412)

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.