속성 그래프를 위한 구성 가능한 언어 (A Compositional Language for Property Graphs)

최근 표준화된 그래프 질의 언어인 GQL 및 SQL/PGQ의 주요 단점은 구성 가능성 (compositionality)의 결여입니다. 지식 그래프 (knowledge graphs)를 질의하는 데 있어 이러한 언어들의 중요성을 고려할 때, 우리는 이 단점을 해결하고 이론적 해결책과 새로운 표준에 이를 추가하기 위한 경로를 제안합니다. 비구성성 (non-compositionality) 문제의 핵심은 GQL과 SQL/PGQ 모두 그래프 도달 가능성 (graph reachability)과 모든 1차 질의 (first-order queries)를 표현할 수 있음에도 불구하고, NLOGSPACE 문제에는 미치지 못한다는 점입니다. 1차 환원 (first-order reductions) 하에서 NLOGSPACE에 대한 도달 가능성의 완전성을 고려할 때, 이는 매우 직관에 어긋나는 일입니다. 이 문제는 표현 불가능한 특정 질의 수준의 공백을 메우기 위해 언어 확장 기능을 찾아온 표준화 위원회에 의해 잘 인식되고 있습니다. 우리는 이 문제를 체계적인 방식으로 다루며, 그래프 패턴과 관계형 질의 (relational queries) 사이의 완전한 구성 가능성을 허용함으로써 표현력의 공백을 메우는 언어를 제안합니다. 이는 두 가지 핵심 구성 요소를 사용하여 수행됩니다: 변수 및 데이터 값 비교를 포함하여 정제된 정규 경로 질의 (regular path queries) 정의와, 노드, 에지, 노드 및 에지의 리스트, 심지어 전체 경로로부터 새로운 그래프 요소를 구축하기 위한 완전한 지원을 갖춘 완전히 구성 가능한 그래프 대 그래프 언어인 #Datalog입니다. 우리는 결과적으로 도출된 언어가 표준화 위원회가 직면한 문제를 해결함을 보여주며, 주요 특징을 통합하는 GQL 및 SQL/PGQ에 대한 구체적인 추가 사항을 제안합니다.