Expressive Power of Property Graph Constraint Languages

이 논문은 GQL 표준 개정을 위한 PG-Keys 언어의 표현력을 Graph Functional Dependencies(GFD) 및 Graph Generating Dependencies(GGD) 와 비교 분석하기 위해 통합 프레임워크를 제시하고, 완전하고 엄격한 표현력 위계 구조를 확립하여 PG-Keys 의 고유한 표현 능력을 규명합니다.

핵심

📚 핵심 주제: "규칙을 쓰는 언어의 힘"

우리가 데이터를 관리할 때 (예: SNS, 은행 시스템), 데이터가 엉망이 되지 않도록 **규칙 (제약 조건)**을 정합니다.

• "한 사람이 두 개의 주민등록번호를 가질 수 없다."
• "모든 게시물은 반드시 작성자가 있어야 한다."

이 논문은 **"이러한 규칙을 표현하는 언어들 (PG-Keys, GFD, GGD 등) 중 어떤 언어가 더 강력하고, 어떤 언어가 더 약한가?"**를 비교 분석한 첫 번째 연구입니다. 마치 "영어, 프랑스어, 스페인어 중 어떤 언어로 더 복잡한 이야기를 할 수 있는지"를 연구하는 것과 같습니다.

🕵️‍♂️ 등장하는 세 가지 '규칙 작성자'

연구자들은 세 가지 주요 규칙 언어를 비교했습니다.

1. GFD (그래프 기능적 의존성):

   • 비유: "A 가 있으면 B 도 있어야 한다"는 단순한 연결 규칙을 쓰는 사람입니다.
   • 예시: "게시물이 있으면 작성자가 있어야 한다."
   • 특징: 규칙을 적용할 때, '출발지'와 '도착지'를 연결하는 공통된 변수 (다리) 를 하나만 사용할 수 있습니다.

2. GGD (그래프 생성 의존성):

   • 비유: "A 가 있으면 B 와 C 를 만들어라"는 복잡한 구조를 만드는 사람입니다.
   • 특징: 출발지와 도착지를 연결하는 공통된 변수를 여러 개 사용할 수 있어, 훨씬 더 복잡한 관계를 표현할 수 있습니다.

3. PG-Keys (새로운 표준 언어):

   • 비유: 최근 GQL(그래프 쿼리 언어) 표준에 포함될 예정인 최신형 규칙 작성자입니다.
   • 특징: 'MANDATORY(필수)', 'EXCLUSIVE(배타적/중복 불가)', 'SINGLETON(단일/하나만)' 같은 강력한 명령어를 사용합니다.
   • 핵심 제한: GFD 와 마찬가지로, 출발지와 도착지를 연결하는 공통된 변수를 딱 하나만 쓸 수 있습니다.

---

🔍 연구의 놀라운 발견 (비유로 설명)

연구자들은 이 세 언어가 서로 얼마나 강력한지 실험해 보았습니다.

1. "하나의 다리" vs "여러 개의 다리"

• GGD는 출발지와 도착지를 연결할 때 **여러 개의 다리 (공통 변수)**를 쓸 수 있어서 매우 강력합니다.
• 반면 PG-Keys와 GFD는 다리 하나만 쓸 수 있습니다.
• 결과: 일반적으로는 다리가 많은 GGD가 더 강력한 규칙을 쓸 수 있습니다. (복잡한 관계를 표현하기 쉽기 때문)

2. "비밀 무기" (부등호) 의 등장

그런데 여기서 재미있는 반전이 일어납니다. 연구자들은 규칙에 **'같다 (=)'**뿐만 아니라 **'다르다 (≠)'**라는 조건을 추가해 보았습니다.

• 비유: "A 와 B 는 서로 다르다"는 조건을 쓸 수 있게 된 것입니다.
• 발견: '다르다 (≠)' 조건이 주어지면, PG-Keys는 자신의 강력한 명령어 (EXCLUSIVE, SINGLETON) 를 이용해 GGD가 여러 개의 다리로 해야 했던 일을, 다리 하나만으로도 완벽하게 흉내 낼 수 있게 됩니다.
• 결론: "다르다" 조건이 있으면, PG-Keys 는 GGD 와 똑一样 강력한 언어가 됩니다! (하지만 GGD 는 여전히 더 많은 다리를 쓸 수 있으므로, PG-Keys 가 GGD 를 완전히 대체하는 것은 아닙니다.)

3. "단순함의 승리"

가장 놀라운 사실은, PG-Keys가 가진 복잡한 명령어들 (EXCLUSIVE, SINGLETON) 이 사실은 GGD의 단순한 문법으로 바꿀 수 있다는 것입니다.

• 비유: PG-Keys 는 마치 "고급 스테이크"처럼 들리지만, 사실은 GGD라는 "일반 고기"를 잘게 다듬고 양념만 바꾼 것과 같습니다.
• 의미: PG-Keys 는 사용자에게는 편리한 문법 (시럽) 이지만, 그 아래에 깔린 논리적 힘은 이미 GGD 에 존재했습니다.

---

💡 이 연구가 왜 중요한가요?

1. 표준화 (GQL) 에 기여:
   앞으로 나올 그래프 데이터베이스 표준 언어 (GQL) 를 만들 때, "어떤 규칙을 포함시켜야 할까?"에 대한 명확한 답을 줍니다. PG-Keys 가 얼마나 강력한지, 그리고 어떤 기능이 진짜로 필요한지 알려주기 때문입니다.

2. 효율적인 설계:
   "복잡한 규칙을 쓸 필요가 없다면, 단순한 규칙으로도 충분하다"는 것을 증명했습니다. 개발자들은 불필요하게 복잡한 기능을 만들지 않아도 되며, 시스템 성능을 최적화할 수 있습니다.

3. 데이터 품질 보장:
   데이터가 엉망이 되는 것을 막기 위해, 어떤 규칙 언어를 선택해야 가장 효과적으로 데이터를 보호할 수 있는지 지도를 그려주었습니다.

📝 한 줄 요약

"새로운 규칙 언어 (PG-Keys) 는 복잡한 명령어를 쓰지만, 사실은 기존 언어 (GGD) 의 능력을 '하나의 다리'와 '다르다' 조건만으로 완벽하게 흉내 낼 수 있다는 것을 발견했습니다. 이는 데이터베이스 표준을 설계할 때, 사용 편의성과 기술적 한계를 명확히 구분하는 데 큰 도움이 됩니다."

기술 요약

1. 문제 제기 (Problem)

• 배경: 속성 그래프 (Property Graph) 는 노드와 엣지에 키 - 값 속성을 가진 다중 레이블 그래프로, 현대 데이터베이스 (GQL, SQL/PGQ 등) 의 핵심 데이터 모델입니다. 데이터 품질과 통합을 보장하기 위해 제약 조건 (Constraint) 이 필수적입니다.
• 현황: 관계형 데이터베이스의 제약 조건 (Functional Dependencies 등) 에 대한 연구는 깊지만, 그래프 데이터베이스용 제약 조건 언어의 상대적 표현력 (Comparative Expressiveness) 은 아직 체계적으로 연구되지 않았습니다.
• 주요 이슈: 최근 표준화 논의 중인 PG-Keys 언어가 도입되었으나, 기존에 제안된 GFD (Graph Functional Dependencies) 및 GGD (Graph Generating Dependencies) 와의 표현력 관계가 명확하지 않습니다. 특히 PG-Keys 는 문법적 특징 (예: scope 와 descriptor 간 공유 변수 수 제한, EXCLUSIVE/SINGLETON 키워드 등) 이 다르기 때문에 공정한 비교를 위한 통일된 프레임워크가 부재했습니다.
• 목표: PG-Keys, GFD, GGD 간의 표현력 계층 구조를 엄밀하게 규명하고, GQL 표준 제정에 기여할 수 있는 이론적 기반을 마련하는 것입니다.

2. 방법론 (Methodology)

• 통일된 프레임워크 구축: 서로 다른 문법과 데이터 예측 (predicate) 을 가진 언어들을 비교하기 위해, 결합 정규 경로 쿼리 (CRPQ) 를 기반으로 한 통일된 매개변수 프레임워크를 정의했습니다.
  • 쿼리 언어: CRPQ[=] (등식만 허용), CRPQ[=, ̸=] (등식 및 부등식 허용).
  • 제약 조건 형식: Qs(x, y) ⇒ Qt(x, z) 형태의 의존성으로 재정의.
• 세분화된 하위 클래스 정의: 표현력을 세밀하게 분석하기 위해 공유 변수 (shared variables) 의 개수에 따라 언어를 분류했습니다.
  • nGFD, nGGD: 좌변 (Scope) 과 우변 (Descriptor) 사이에 공유되는 변수 x 의 개수가 n 이하인 부분 집합.
  • PG-Keys 의 경우 원래 정의상 공유 변수가 1 개로 제한되므로 1PG-Keys 와 동일하게 취급되지만, mPG-Keys (MANDATORY 키워드만 사용) 와 같은 하위 집합도 분석 대상에 포함했습니다.
• 포함 관계 (Inclusion) 와 분리 (Separation) 증명:
  • 포함: 한 언어의 제약 조건을 다른 언어로 변환 가능한지 증명.
  • 분리: 특정 제약 조건이 다른 언어 (또는 하위 집합) 로 표현 불가능함을 반례 (Counter-example) 를 통해 증명하여 엄격한 계층 구조를 확립.

3. 주요 기여 (Key Contributions)

1. 정밀한 언어 기능 분석: 식별자 (identifier) 의 등식/부등식 허용 여부와 공유 변수의 개수가 제약 언어의 표현력에 미치는 영향을 규명했습니다. 특히 PG-Keys 의 핵심 설계 결정인 "Scope 와 Descriptor 간 공유 변수는 1 개만 허용"이라는 제한이 표현력에 어떤 영향을 미치는지 분석했습니다.
2. 표현력 포함 관계 확립: 다양한 쿼리 언어 (CRPQ[=], CRPQ[=, ̸=]) 설정 하에서 GFD, GGD, PG-Keys 간의 포함 관계를 증명했습니다.
3. 엄격한 분리 결과 (Separation Results): 일부 제약 조건은 특정 언어나 하위 집합에서는 본질적으로 표현할 수 없음을 증명하여, 각 언어의 한계를 명확히 했습니다.
4. 예상치 못한 결과 도출:
   • SINGLETON 키워드의 힘: PG-Keys 의 SINGLETON 키워드를 사용하면 공유 변수가 1 개뿐임에도 불구하고 GFD 를 시뮬레이션할 수 있음을 보였습니다.
   • 부등식 (Inequality) 의 영향: 부등식 (≠) 이 허용될 경우, 공유 변수가 1 개만 있어도 EXCLUSIVE 및 SINGLETON 키워드를 시뮬레이션할 수 있어, PG-Keys 와 1GGD 가 동등해짐을 증명했습니다.

4. 주요 결과 (Key Results)

논문의 결과는 쿼리 언어가 등식만 허용하는 경우 (CRPQ[=]) 와 등식과 부등식을 모두 허용하는 경우 (CRPQ[=, ̸=]) 로 나뉘어 엄격한 계층 구조를 이룹니다.

A. 등식만 허용하는 경우 (CRPQ[=])

• 계층 구조: 1GGD ⊊ PG-Keys ⊊ GGD
• GFD 와의 관계: GFD ⊊ PG-Keys
  • 발견: PG-Keys 는 공유 변수가 1 개뿐임에도 불구하고 SINGLETON 키워드를 clever하게 사용하여 GFD 를 시뮬레이션할 수 있습니다.
  • 한계: PG-Keys 는 공유 변수가 2 개 이상 필요한 GGD (예: 2GGD) 를 완전히 시뮬레이션할 수 없습니다. 또한 EXCLUSIVE 키워드는 공유 변수 1 개로는 GGD 의 특정 패턴을 완전히 대체할 수 없습니다.
  • 결론: PG-Keys 는 1GGD 보다 강력하지만 GGD 보다는 약합니다.

B. 등식과 부등식을 모두 허용하는 경우 (CRPQ[=, ̸=])

• 계층 구조: GFD ⊊ 1GGD = PG-Keys ⊊ GGD
• 중요한 발견:
  • PG-Keys 와 1GGD 의 동등성: 부등식 (≠) 이 허용되면, PG-Keys 의 EXCLUSIVE 및 SINGLETON 키워드는 1GGD 로 변환 가능합니다. 즉, PG-Keys 는 1GGD 와 표현력이 동등해집니다.
  • 의미: 이 경우 PG-Keys 의 고유 키워드들은 본질적인 표현력 증가가 아닌 문법적 설탕 (Syntactic Sugar) 역할을 합니다.
  • GFD 와의 관계: 부등식이 있으면 1GGD 가 GFD 를 포함하게 되어 GFD ⊊ PG-Keys 관계가 성립합니다.

C. GFD 의 특수한 성질

• 유도 부분 그래프 (Induced Subgraph) 닫힘: GFD 는 유도 부분 그래프에 대해 닫혀 있지만 (Closed under induced subgraph), GGD 와 PG-Keys 는 그렇지 않습니다. 이는 GFD 가 GGD/PG-Keys 와 구별되는 중요한 특성입니다.

5. 의의 및 시사점 (Significance)

1. GQL 표준 제정에 대한 기여: PG-Schema (PG-Keys 의 상위 집합) 가 GQL 표준의 차기 판에 통합될 예정인 시점에서, 이 연구는 PG-Keys 의 표현력 한계와 GGD/GFD와의 관계를 명확히 함으로써 표준 설계에 이론적 근거를 제공합니다.
2. 언어 설계의 최적화:
   • PG-Keys 의 EXCLUSIVE/SINGLETON 키워드가 부등식 지원 시 1GGD 로 변환 가능하다는 결과는, 구현체에서 이러한 키워드를 내부적으로 1GGD 로 컴파일하여 처리할 수 있음을 시사합니다.
   • 공유 변수의 수를 늘리는 것이 표현력을 높이는 핵심 요소임을 확인시켜 주어, 향후 언어 설계 시 복잡성과 표현력의 트레이드오프를 고려하는 데 도움을 줍니다.
3. 이론적 계층 구조의 완성: 기존에 단편적으로 연구되었던 그래프 제약 언어들을 통일된 프레임워크 하에서 비교하여, 엄격한 표현력 계층 구조를 최초로 제시했습니다.
4. 복잡도 분석의 새로운 방향: 공유 변수의 수가 제약 조건 검증 (Validation) 문제의 복잡도 (예: nGGD 검증의 복잡도) 에 미치는 영향을 제시하여, 향후 복잡도 이론 연구의 새로운 방향을 제시했습니다.

요약

이 논문은 속성 그래프 제약 언어인 PG-Keys, GFD, GGD 간의 표현력을 체계적으로 비교 분석했습니다. 핵심 발견은 공유 변수의 개수와 부등식 (Inequality) 의 허용 여부가 표현력을 결정하는 가장 중요한 요소라는 점입니다. 특히 부등식이 허용될 경우 PG-Keys 는 1GGD 와 동등해지며, 이는 PG-Keys 의 고유 키워드들이 문법적 편의성임을 의미합니다. 이러한 결과는 향후 GQL 표준 및 그래프 데이터베이스 시스템의 제약 조건 설계에 중요한 지침이 됩니다.