  With the rapid growth of large graphs, we cannot assume that graphs can still
be fully loaded into memory, thus the disk-based graph operation is inevitable.
In this paper, we take the shortest path discovery as an example to investigate
the technique issues when leveraging existing infrastructure of relational
database (RDB) in the graph data management. Based on the observation that a
variety of graph search queries can be implemented by iterative operations
including selecting frontier nodes from visited nodes, making expansion from
the selected frontier nodes, and merging the expanded nodes into the visited
ones, we introduce a relational FEM framework with three corresponding
operators to implement graph search tasks in the RDB context. We show new
features such as window function and merge statement introduced by recent SQL
standards can not only simplify the expression but also improve the performance
of the FEM framework. In addition, we propose two optimization strategies
specific to shortest path discovery inside the FEM framework. First, we take a
bi-directional set Dijkstra's algorithm in the path finding. The bi-directional
strategy can reduce the search space, and set Dijkstra's algorithm finds the
shortest path in a set-at-a-time fashion. Second, we introduce an index named
SegTable to preserve the local shortest segments, and exploit SegTable to
further improve the performance. The final extensive experimental results
illustrate our relational approach with the optimization strategies achieves
high scalability and performance.
