Abstract
Abstract In this paper, we propose a new algorithm for computing recursive closures. The main idea behind this algorithm is tree labeling and graph decomposition, based on which the transitive closure of a directed graph can be computed in O(e?dmax?dout) time and in O(n?dmax?dout) space, where n is the number of the nodes of the graph, e is the numbers of the edges, d max is the maximal indegree of the nodes, and dout is the average outdegree of the nodes. Especially, this method can be used to efficiently compute recursive relationships of a directed graph in a relational environment.