Regular path queries (RPQ's) are queries that find pairs of vertices of paths satisfying given regular expressions on an edge-labeled, directed multigraph. Evaluating RPQ's is a complex operation in which graph traversal and pattern matching are concurrently performed. When evaluating multiple RPQ's that include a common sub-query, we can avoid its repeated evaluation by evaluating the common sub-query only once and sharing the result among the RPQ's. However, if the common sub-query is a Kleene star or Kleene plus, the evaluation of the common sub-query itself is expensive and the size of the result is large. In this paper, we propose an intermediate representation (IR) as a lightweight structure for efficient sharing of the result of a common sub-query among multiple RPQ's whose common sub-query is a Kleene plus $R^+$ for any regular expression R. The IR is the transitive closure of the two-level reduced graph of the original graph, which has computation and space overheads smaller than those of evaluating the $R^+$ itself. We show that $R^+$ can be easily calculated from the IR (Theorem 1). We also present multiple RPQ evaluation algorithms, the IRSharing and Extended_IRSharing, that share the IR instead of the result of R+. We first present the algorithm IRSharing where the RPQ includes only one Kleene plus $R^+$. In IRSharing, we represent the result of an RPQ including R+ as a relational algebra expression including the IR. We further optimize its evaluation by exploiting its relational algebra expression. We then extended IRSharing to Extended_IRSharing that evaluates an arbitrary RPQ including multiple or nested Kleene plus'. Experiments show that the performance of IRSharing is improved significantly by up to 8.86 times compared with existing methods in terms of query response time.
정규 경로 질의는 엣지에 레이블이 있고, 방향성이 있는 그래프에서 정규 표현식을 만족하는 경로가 존재하는 정점 쌍들을 찾는 질의이다. 정규 경로 질의를 처리하는 것은 그래프 탐색과 패턴 매칭이 동시에 수행되는 복잡한 연산이다. 공통된 부분 질의를 포함하는 다중 정규 경로 질의를 처리할 때 공통된 부분 질의를 한번만 처리하고, 그 결과를 질의들 간에 공유함으로써 같은 부분 질의를 반복해서 처리하는 것을 피할 수 있다. 그런데, 공통된 부분 질의가 Kleene star 혹은 Kleene plus인 경우 그것을 처리하는 것만으로도 연산이 복잡하고 그 결과의 크기가 크다. 본 논문은 임의의 정규 표현식 R에 대해 Kleene plus $R^+$를 공통된 부분 질의로 가지는 다중 정규 경로 질의들 간에 $R^+$의 결과를 효율적으로 공유하기 위한 가벼운 구조로 중간 표현을 제안한다. 중간 표현은 원본 그래프가 2단계 축소된 그래프의 transitive closure로서, $R^+$의 처리 결과와 비교하여 계산 및 공간 오버헤드가 더 작다. 우리는 중간 표현을 이용하여 $R^+$를 쉽게 계산할 수 있음을 보인다 (Theorem 1). 또한, 다중 정규 경로 질의 처리 알고리즘으로 정규 경로 질의들 간에 중간 표현을 공유하는 IRSharing과 Extended_IRSharing을 제안한다. 먼저, IRSharing은 하나의 $R^+$를 포함하는 다중 정규 경로 질의를 처리하는 알고리즘이다. IRSharing에서, 우리는 $R^+$를 포함하는 정규 경로 질의의 결과를 중간 표현을 포함하는 관계형 대수 표현식으로 나타낸다. 또한, 그 관계형 대수 표현식을 이용하여 정규 경로 질의 처리를 최적화한다. 다음으로, IRSharing을 다수의 Kleene plus를 포함하거나 혹은 nested Kleene plus를 포함하는 임의의 정규 경로 질의를 처리하는 Extended_IRSharing으로 확장한다. 실험을 통해서 IRSharing의 성능이 질의 응답 시간의 측면에서 기존의 방법들과 비교하여 8.86배까지 향상됨을 보인다.
