DAG Deduction and Decomposition: A New Way to Evaluate Reachability Queries

Haihui HUANG, Xin WEN, Zheng LUO, Huixue QIAO

College of Software, CQUPT, Chongqing, China

Abstract: Let G(V, E) be a digraph (directed graph) with n nodes and e arcs. Digraph G* = (V, E*) is the reflexive, transitive closure if v ® u Î E* iff there is a path from v to u in G. Efficient storage of G* is important for supporting reachability queries which are not only common in graph databases, but also serve as fundamental operations used in many graph algorithms. A lot of strategies have been suggested based on the graph labeling, by which each node is assigned with certain labels such that the reachability of any two nodes through a path can be determined by their labels. Among them are interval labeling, chain decomposition, 2- hop labeling, and path-trees. However, due to the very large size of many real world graphs, the computational cost and size of labels using existing methods would prove too expensive to be practical. In this paper, we propose a new approach to deduct and decompose a graph into two graphs: a transitive core graph and a residue graph. Both are much smaller than the original graph. In this way, we transform any reachability query into two queries. One is over the transitive core graph and another is over the residue graph. While the former can always be evaluated in constant time, the latter can be done by using any existing method, but over a much smaller graph. We demonstrate both analytically and empirically the efficiency and effectiveness of our method.

Keyword: Directed Graphs; spanning Trees; Reachability Queries; Transitive Closure Compression.