Evaluation of Reachability Queries Based on Recursive DAG Decomposition

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 proposed 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, as well as partial index based methods. 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 a series of spanning trees and transform a query
q
to a series of subqueries each evaluated against a spanning tree. Using the so-called tree labeling, each subquery needs only O(1) time. More importantly, the number of such subqueries is
$\ll$

n
. Thus,
q
can be evaluated very efficiently. We demonstrate both analytically and empirically the efficiency and effectiveness of our method. While the query time of our method is orders of magnitude better than almost all the existing strategies, its indexing time and index sizes are comparable to them.