Efficient Transitive Closure Algorithms
Efficient Transitive Closure Algorithms
复制标题
高效的传递闭包算法
DOI：
--
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
R. Ramakrishnan
中科院分区：
文献类型：
--
作者：
Y. Ioannidis;R. Ramakrishnan
我们开发了一些有效的算法来计算有向图的传递闭包。本文提出了可达性问题的算法。然而，这些算法可以适应处理路径计算和基于单向递归的更广泛的查询类。我们分析这些算法并将它们与文献中的算法进行比较。结果表明，这些算法除了能够处理传递闭包生成的查询之外，还可以非常高效地执行，特别是在基于盘的数据库环境中。
We have developed some efficient algorithms for computing the transitive closure of a directed graph. This paper presents the algorithms for the problem of reachability. The algorithms, however, can be adapted to deal with path computations and a signitkantJy broader class of queries based on onesided recursions. We analyze these algorithms and compare them to algorithms in the literature. The resulti indicate that these algorithms, in addition to their ability to deal with queries that am generakations of transitive closure, also perform very efficiently, in particular, in the context of a dish-based database nvironment.