기술 요약: PathFinder: 그래프 쿼리에서의 경로 반환

문제 정의

SPARQL, Cypher, SQL/PGQ, 그리고 새롭게 등장하는 GQL 표준을 포함한 현대적 그래프 쿼리 언어들은 경로 쿼리에 크게 의존하고 있다. SPARQL은 정규 표현식에 부합하는 경로로 연결된 노드 쌍을 식별하기 위해 정규 경로 쿼리(RPQ)를 지원하지만, 종단 노드(endpoints)만을 반환한다. 반면, Cypher, SQL/PGQ, GQL은 사용자가 해당 쿼리를 만족하는 전체 경로(witnesses)를 반환할 수 있도록 허용한다.

그러나 이러한 언어들의 이론적 능력과 실제 구현 사이에는 상당한 격차가 존재한다. 현재의 그래프 데이터베이스 엔진들은 GQL 및 SQL/PGQ 표준에서 정의된 27가지 경로 모드의 전체 스펙트럼을 지원하는 포괄적인 경로 반환 기능을 갖추지 못하고 있다. 이 모드들은 다양한 제약 조건(예: WALK, TRAIL, SIMPLE, ACYCLIC)과 선택자(예: ANY, ALL SHORTEST, SHORTEST k, SHORTEST k GROUPS)를 포함한다. 기존 엔진들은 다음과 같은 한계를 보인다:

1. 모든 RPQ를 지원하지만 경로는 반환할 수 없다 (SPARQL 엔진).
2. 경로를 반환할 수는 있지만, 제한된 정규 표현식이나 경로 모드만을 지원한다 (Neo4j, Kuzu, Nebula와 같은 프로퍼티 그래프 엔진).
3. 경로 쿼리의 잠재적인 지수적 경로 수로 인해 확장성 문제로 고통받으며, 효율적인 경로 쿼리 처리에 실패하곤 한다.

또한, 단순 경로(simple paths)나 트레일(trails)을 찾는 것의 이론적 복잡도는 NP-완전(NP-complete)으로 알려져 있지만, 실제 구현체들은 실제 데이터에 대한 이론적으로 난해한 쿼리에 대해서도 안정적인 성능을 제공하는 데 어려움을 겪는 경우가 많다.

방법론

본 논문은 RPQ를 평가하고 27가지 GQL 경로 모드에 따라 경로를 반환하기 위한 통합 프레임워크인 PATHFINDER를 소개한다. 이 접근 방식의 핵심은 입력 그래프 데이터베이스 $G$와 쿼리의 정규 표현식으로부터 유도된 비결정적 유한 오토마타(NFA) $A$를 결합하는 곱 그래프(product graph) 구축에 있다.

핵심 알고리즘 원칙

1. 곱 그래프 구축 (Product Graph Construction): 프레임워크는 노드가 그래프의 노드 $v$와 오토마타의 상태 $q$의 쌍 $(v, q)$로 구성되는 곱 그래프 $G \times A$를 구축한다. 곱 그래프의 엣지는 그래프의 엣지 레이블과 일치하는 오토마타의 전이(transition)에 대응한다.
2. 지연 구축 (Lazy Construction): 곱 그래프는 지연 방식으로 구축된다. 즉, 쿼리 평가에 필요한 부분만 생성되므로, 결과가 탐지되는 즉시 파이프라인 방식으로 실행되어 반환될 수 있다.
3. 경로 멀티셋 표현 (Path Multiset Representation, PMR): 알고리즘은 탐색 상태를 사용하여 모든 일치하는 경로를 압축된 형태로 유지한다. 탐색 상태는 일반적으로 현재 노드, 오토마타 상태, 깊이, 그리고 이전 상태에 대한 포인터를 포함하며, 이를 통해 탐색 과정에서 경로를 명시적으로 저장하지 않고도 경로를 재구성할 수 있게 한다.

경로 모드별 특정 알고리즘

논문은 다양한 경로 모드에 따른 곱 그래프 탐색의 구체적인 적응 방식을 상세히 설명한다:

• WALK 모드 (ANY, ANY SHORTEST, ALL SHORTEST, ANY k, SHORTEST k, SHORTEST k GROUPS):

  • ANY/ANY SHORTEST: 곱 그래프 상에서 표준 BFS 또는 DFS를 사용한다. 비결정성을 처리하고 엔드포인트 쌍당 단일 경로를 보장하기 위해, 알고리즘은 방문한 상태 $(n, q)$를 추적하고 중복 반환을 방지하기 위해 ReachedFinal 집합을 사용한다.
  • ALL SHORTEST: 노드까지의 모든 최단 경로를 추적하도록 BFS를 확장한다. 탐색 상태에는 최단 경로를 생성하는 모든 선행 상태들에 대한 포인터 리스트(prevList)가 포함되어 여러 최단 경로를 열거할 수 있게 한다.
  • SHORTEST k / ANY k: 한계값 $k$까지 증가하는 길이의 경로를 추적한다. 알고리즘은 각 상태에 도달하는 경로의 수를 유지하여 종료를 보장하고 $k$개의 최단 경로를 반환한다.
  • SHORTEST k GROUPS: 위와 유사하지만 경로를 길이별로 그룹화하여, 발견된 $k$번째 서로 다른 길이까지의 모든 경로를 반환한다.

• 제한 모드 (TRAIL, SIMPLE, ACYCLIC):

  • 이 모드들은 최악의 경우 NP-완전인 것으로 알려져 있다. 프레임워크는 **가지치기(pruning)**를 동반한 곱 그래프의 브루트 포스(brute-force) 탐색을 채택한다.
  • isValid 함수는 경로를 확장하는 것이 특정 제약 조건(예: TRAIL의 경우 엣지 반복, SIMPLE의 경우 노드 반복)을 위반하는지 확인한다.
  • 최악의 시간 복잡도는 여전히 지수적이지만, 이 접근 방식은 실제 그래프에서 유효한 경로의 수가 관리 가능한 수준인 경우 효율적으로 작동하도록 설계되었다.

구현 및 통합

• 프로퍼티 그래프 (Property Graphs): 오픈 소스 그래프 엔진인 MillenniumDB 상에 구현되었다. 구문은 경로 변수와 모드를 포함하도록 Cypher 스타일의 패턴을 확장한다 (예: MATCH (src)=[MODE ?p rgx]=>(tgt)).
• SPARQL 확장: 경로 반환을 지원하도록 SPARQL 구문을 확장하여 (예: src MODE (path AS ?p) tgt), 기존 RDF 엔진이 이러한 기능을 갖출 수 있음을 입증한다.
• 실행 모델: 알고리즘은 파이프라인 실행을 위한 선형 이터레이터(linear iterators)를 사용하여 구현되었으며, 이를 통해 전체 솔리션 세트를 구축하기 전에 경로가 온더플라이(on-the-fly)로 반환되도록 보장한다.

주요 기여

1. 최초의 통합 프레임워크: PATHFINDER는 GQL 및 SQL/PGQ 표준에서 규정한 모든 27가지 경로 모드에 대해 경로를 반환하는 최초의 시스템이다.
2. 알고리즘적 참신함: 비결정적 오토마타 처리, 다중 최단 경로 열거 등을 포함한 경로 모드의 복잡성을 처리하는 곱 그래프 구축 기반의 구현 가능한 알고리즘을 제공한다.
3. SPARQL 확장: 경로 증거(witness)를 반환하기 위한 SPARQL 확장의 타당성을 입증함으로써, RDF와 프로퍼티 그래프 쿼리 능력 사이의 간극을 메운다.
4. 실질적 실현 가능성: 광범에한 실험을 통해, 특정 모드(TRAIL)의 이론적 난해함에도 불구하고 본 접근 방식이 실제 데이터에서 안정적인 성능을 낸다는 것을 보여준다.

실험 결과

저자들은 Pokec(소셜 네트워크), Wikidata(대규모 지식 그래프), 그리고 Diamond 그래프(지수적으로 많은 경로를 갖도록 설계된 합성 그래프)의 세 가지 데이터셋을 사용하여 PATHFINDER를 평가하였다.

• 성능: PATHFINDER는 최신 엔진들(Neo4j, Nebula, Kuzu, Jena, Blazegraph, Virtuoso)보다 12 자릿수(10배100배) 더 빠른 속도로 일관되게 우수한 성능을 보였다.
• 확장성:
  • Pokec에서 PATHFINDER는 경로 길이가 증가함에 따라 안정적인 성능을 유지했으나, 다른 시스템들은 빈번하게 타임아웃이 발생했다.
  • Wikidata에서 PATHFINDER는 659개의 복잡한 쿼리를 성공적으로 처리한 반면, SPARQL 엔진(경로를 반환하지 않음)은 훨씬 느렸고, 프로퍼티 그래프 엔진(Neo4j)은 대다수의 쿼리에서 타임아웃이 발생했다.
  • Diamond 그래프에서 PATHFINDER는 WALK 모드에 대해 선형 시간 복잡도를 입증한 반면, 다른 엔진들은 지수적 증가를 보였다. TRAIL 모드의 경우, PATHFINDER의 DFS 변형이 방대한 수의 경로를 처리하는 데 있어 BFS보다 우수함을 입증했다.
• 견고성: 시스템은 이론적으로 난해한 쿼리(예: 대규모 그래프에서의 TRAIL)를 안정적인 성능으로 처리하였으며, 이는 실제 데이터 분포가 최악의 이론적 복잡도를 완화함을 시사한다.

의의 및 주장

본 논문은 PATHFINDER가 GQL/SQL/PGQ의 이론적 역량과 실제 구현을 통합함으로써 그래프 쿼리 프로세싱의 중요한 진전을 이루었다고 주장한다.

• 경로 반환의 실현 가능성: 본 연구는 복잡한 RPQ에 대해 전체 경로 증거를 반환하는 것이 이론적으로 가능할 뿐만 아니라, 이전에 난해하다고 여겨졌던 모드들에 대해서도 실질적으로 효율적임을 입 증한다.
• 표준 준수: GQL 표준의 27가지 경로 모드를 완전히 지원하는 최초의 엔진으로서, 현재의 데이터베이스 기술의 공백을 메운다.
• 확장성: MillenniumDB로의 성공적인 통합과 SPARQL 확장은 이러한 알고리즘들이 기존 데이터베이스 엔진을 완전히 새로 작성하지 않고도 기존 파이프라인에 통합될 수 있음을 보여준다.
• 미래 전망: 저자들은 현재 구현이 표준 RPQ를 처리하지만, 향후 노드 및 엣지 데이터 속성을 포함하는 더 표현력이 풍부한 쿼리를 탐구할 것이며, SPARQL의 특정 프로퍼티 경로 구문과 경로 반환 의미론이 어떻게 통합될지에 대한 추가적인 조사가 필요하다고 언급하였다.

결론적으로, PATHFINDER는 경로 반환 쿼리가 확장성을 희생하거나 쿼리 언어의 표현력을 제한해야 한다는 통념에 도전하며, 건실하고 고성능인 전략을 제공한다.