A new algorithm for transitive closures and computation of recursion in relational databases

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·d_max·d_out) time and in O(n·d_max·d_out) 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 d_out 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.