A Compositional Language for Property Graphs

기술 요약: 속성 그래프를 위한 구성적 언어 (A Compositional Language for Property Graphs)

문제 정의
본 논문은 최근 표준화된 그래프 쿼리 언어인 GQL 및 SQL/PGQ의 근본적인 결함인 **구성성(compositionality)**의 부재를 지적한다. 이 언어들은 그래프 도달 가능성(reachability)과 모든 1차 쿼리(first-order queries)를 표현할 수 있지만, NLOGSPACE 복잡도 클래스 내의 특정 문제들을 표현하는 데는 실패한다. 이는 그래프 도달 가능성이 1차 환원(first-order reductions) 하에서 NLOGSPACE-완전(NLOGSPACE-complete)이라는 점을 고려할 때 매우 역설적이다. 이론적으로 도달 가능성과 1차 논리를 모두 갖춘 언어라면 해당 클래스 전체를 포괄해야 하기 때문이다.

핵심 문제는 GQL과 SQL/PGQ가 관계형 컴포넌트(테이블)와 그래프 컴포넌트 사이에서 정보가 양방향으로 흐르는 것을 허용하지 못한다는 점에 있다. 즉, 이 언어들은 관계형 연산의 결과로부터 새로운 그래프 요소를 생성할 수 없다. 이러한 한계는 실무적인 시나리오, 예를 들어 표준 경로 패턴을 사용하여 "엣지 상의 증가하는 값"(예: 타임스탬프가 엄격하게 증가하는 전송 체인 찾기) 쿼리를 표현할 수 없는 문제로 나타난다. 현재의 표준에서는 경로 연결 시 엔드 노드(end-nodes)는 병합하지만 그 사이의 엣지 정보는 소실하며, 노드와 엣지를 다루는 비대칭성 때문에 이러한 속성을 표현할 수 없다.

방법론
저자들은 그래프 패턴과 관계형 쿼리 간의 완전한 구성성을 가능하게 하는 두 가지 핵심 이론적 구성 요소를 포함하는 체계적인 솔루션을 제안한다:

1. 변수를 포함한 정규 경로 쿼리 (Regular Path Queries with Variables, RPQVs):
   저자들은 노드와 엣지를 대칭적으로 다루는 정제된 정의의 경로 쿼리를 도입한다. 노드 사이에 익명의 노드를 삽입하거나 연속된 노드를 축약하는 경향이 있는 GQL/SQL/PGQ와 달리, RPQVs는 변수가 노드와 엣지의 리스트에 바인딩될 수 있는 **주석이 달린 경로(annotated paths)**를 허용한다.

   • 대칭성: 경로 연결 정의를 통해 강제적인 중간 삽입 없이 엣지가 직접 엣지와 연결되거나 노드가 노드와 연결될 수 있다.
   • 리스트 변수: 정규 표현식 내의 변수는 요소의 리스트에 바인딩될 수 있어, 언어가 전체 시퀀스에 걸쳐 요소(엣지 또는 노드)의 순서를 추적하고 조건(예: 값 비교)을 적용할 수 있게 한다.
   • 복잡도: RPQV의 평가는 NLOGSPACE 내에 머물러 있어, 단순 경로(simple paths)나 트레일(trails)과 같은 경로 제약과 관련된 NP-완전성 문제를 피한다.

2. #Datalog (Hash-Datalog):
   저자들은 안전한 부정(safe negation)과 스콜렘 함수(Skolem functions)를 사용하는 Datalog를 기반으로 한 완전한 구성적 그래프-투-그래프 언어를 제안한다. #Datalog 프로그램은 두 가지 교차 단계로 구성된다:

   • 연산 프로그램 (Computation Programs): 이 단계는 (RPQVs가 본문에 포함된 확장된) 표준 Datalog 규칙을 사용하여 인텐셔널 술어(intensional predicates)를 계산한다. 결정적으로, 이들은 튜플에 고유 식별자를 할당하는 해시 술어(예: #A)를 생성하여, 관계형 매치에 기반하여 새로운 노드 및 엣지 ID를 효과적으로 생성한다.
   • 업데이트 프로그램 (Update Program): 이 규칙들은 연산 단계에서 생성된 식별자를 사용하여 새로운 속성 그래프(노드, 엣지, 소스, 타겟, 레이블, 속성)의 구조를 정의한다.
   • 메커니즘: 이 접근 방식은 관계형 연산의 결과가 직접 그래프 구조를 수정하여, 기존의 매치, 리스트 또는 경로로부터 새로운 요소(노드/엣지)를 생성할 수 있도록 한다.

주요 기여

• 이론적 언어 설계: 본 논문은 계산 복잡도를 높이지 않으면서 GQL 및 SQL/PGQ의 표현력 격차를 메우는 이론적 언어를 제시한다. 저자들은 누락된 능력이 바로 관계형 결과로부터 새로운 그래프 요소를 구축하는 능력임을 입증한다.
• 완전성 증명: 저자들은 제안된 언어(RPQVs와 #Datalog의 결합)가 모든 NLOGSPACE 쿼리를 표현할 수 있음을 증명한다. 이는 도달 가능성이 NLOGSPACE-완전임에도 불구하고 표준 언어들이 모든 NLOGSPACE 속성을 표현할 수 없었던 역설을 해결한다.
• 구체적인 표준 제안: 논문은 이러한 이론적 메커니즘을 GQL 및 SQL/PGQ를 위한 구체적이고 하위 호환 가능한 구문 제안으로 변환한다:
  • 패턴 유연성: 자동 노드 삽입을 방지하여 엣지가 직접 연결될 수 있도록 하는 새로운 MATCH COLLAPSE 모드를 도입한다. 또한 내부 변수를 리스트 변수로 취급하기 위한 새로운 ACCUMULATE 키워드를 도입한다.
  • 그래프 구축: 사용자가 패턴 매치나 바인딩 테이블으로부터 새로운 그래프 요소를 생성할 수 있도록 하는 새로운 절(CREATE NODE, CREATE EDGE)을 도입한다. 이 절들은 새로 생성된 노드/엣지의 소스 요소를 참조하기 위한 메커니즘(예: @e 구문)을 포함하여, 관계형 결과와 새로운 그래프 구조 사이의 연결을 유지한다.

결과

• 표현력: 제안된 언어는 엣지 상의 값이 엄격하게 증가하는 경로를 찾는 것과 같이 기존 GQL/SQL/PGQ에서 표현 불가능하다고 여겨졌던 쿼리를 성공적으로 표현한다.
• 복잡도: 핵심 구성 요소(RPQVs)의 평가는 NLOGSPACE 내에 머문다. 유한한 결과 집합(예: 단순 경로)을 강제하는 것은 복잡도를 NP-완전으로 높일 수 있으나, 저자들은 무한 경로의 압축된 표현이 선형 시간 내에 계산될 수 있으므로 엔진이 이러한 쿼리를 내부적으로 효율적으로 처리할 수 있다고 주장한다.
• 하위 호환성: 제안된 구문 확장은 가산적(additive)으로 설계되었다. 기존 쿼리는 유효하게 유지되며, 새로운 기능(COLLAPSE 모드, CREATE 절)은 현재 표준의 의미를 변경하지 않는 선택적 추가 사항이다.

의의
본 논문은 GQL 및 SQL/PGQ의 비구성성을 해결하는 것이 지식 그래프 쿼리의 미래를 위해 필수적이라고 주장한다. 그래프와 관계형 컴포넌트 간의 "자유로운 정보 흐름"을 가능하게 함으로써, 제안된 확장 기능은 원칙적이고 표현력이 풍부하며 상호 운용 가능한 그래프 쿼리를 허용한다. 저자들은 SQL이 기초적인 격차를 해결하기 위해 여러 버전(1986/89/92)을 거쳐 진화했듯이, GQL과 SQL/PGQ 역시 지수적인 우회책에 의존하지 않고 복잡한 분석 및 추론 작업(예: 증가하는 타임스탬프를 이용한 사기 탐지)을 지원하기 위해 유사한 진화가 필요하다고 주장한다. 이 제안은 ISO 표준 위원회가 효율성과 단순성을 유지하면서도 이러한 표현력의 격차를 닫을 수 있는 경로를 제공한다.