Scaling Reachability on Directed Acyclic Graphs

Sandeep Gupta (SDSC)


Reachability is the fundamental operator for any graph-structured data.
Long in the purview of graph-theory this problem is currently being
actively studied within  the database context as graph-centric applications
in semantic web, ontologies, bio-informatics gain prominence.

All algorithms proposed in literature for reachability follow the
labeling/decoding paradigm i.e.  they materialize/encode a subset of
transitive pairs and perform  lookups over the materialized pairs to
accelerate query processing.  They differ, however, in the choice of
transitive pairs to be materialized and their encoding/decoding procedure.
The algorithms for reachability among non-materialized pairs is build upon
the materialized pairs.  In this work we argue that such reachability
algorithms do not scale well.

We present a novel labeling/decoding algorithm that are correspond to
separator-based algorithms for undirected graphs.  To overcome the
scalability barrier we augment the labeling/decoding with a pruning mechanism.
It is inspired by the  principles behind R-tree indexing. Just as in R-tree
it assign ranges (MBR in R-tree nomenclature) to nodes and performs
containment checks as a filter step.

Our scheme achieves more than an order of magnitude improvement over several
classes of directed acyclic graphs over tree-encoding based reachability
algorithms.  Our experiments verify that for different classes of graphs of
varying sizes the algorithms require low preprocessing time and small storage
overhead, and yet deliver significantly better running time than the state of
art.