A Hash-Based Approach for Computing the Transitive Closure of Database Relations.
Farshad A. Fotouhi, Andrew E. Johnson, Satyendra P. Rana · 1992
Recursive query processing is one of the key problems in integrating database and artificial intelligence technologies. Among the classes of recursive queries, transitive closure queries are the simplest, but most important. Here, we present an efficient hash-based algorithm for computing the transitive closure of database relations. Hashing is used to reduce the data size dynamically. The original data is partitioned once and the partitioning is maintained throughout the computation. Partitions are used in the computation instead of the entire relation. As the new tuples are generated after each iteration of the algorithm, these are placed in the appropriate partitions. We have shown the performance improvement of the proposed algorithm over the existing methods for a wide range of memory sizes, relation depths, and hash selectivity factors. 2 1. Introduction Recursive query processing is an important part of knowledge-base systems. Jagadish and Rakesh 4 showed that any linearly...