  Regular path queries (RPQs) find pairs of vertices of paths satisfying given
regular expressions on an edge-labeled, directed multigraph. When evaluating an
RPQ, the evaluation of a Kleene closure (i.e., Kleene plus or Kleene star) is
very expensive. Furthermore, when multiple RPQs include a Kleene closure as a
common sub-query, repeated evaluations of the common sub-query cause serious
performance degradation. In this paper, we present a novel concept of RPQ-based
graph reduction, which significantly simplifies the original graph through
edge-level and vertex-level reductions. Interestingly, RPQ-based graph
reduction can replace the evaluation of the Kleene closure on the large
original graph to that of the transitive closure to the small reduced graph. We
then propose a reduced transitive closure (RTC) as a lightweight structure for
efficiently sharing the result of a Kleene closure. We also present an RPQ
evaluation algorithm, RTCSharing, which treats each clause in the disjunctive
normal form of the given RPQ as a batch unit. If the batch units include a
Kleene closure as a common sub-query, we share the lightweight RTC instead of
the heavyweight result of the Kleene closure. RPQ-based graph reduction further
enables us to formally represent the result of an RPQ including a Kleene
closure as a relational algebra expression including the RTC. Through the
formal expression, we optimize the evaluation of the batch unit by eliminating
useless and redundant operations of the previous method. Experiments show that
RTCSharing improves the performance significantly by up to 73.86 times compared
with existing methods in terms of query response time.
