Common Foundations for Recursive Shape Languages

1. 문제 정의 (Problem)

• 배경: RDF 데이터의 스키마 언어 (ShEx, SHACL) 가 성숙해지면서 순환적 의존성 (cyclic dependencies) 을 처리하기 위해 재귀 기능이 필수적으로 요구되고 있습니다.
• 현재 상황:
  • ShEx: 공식적으로 최대 고정점 (Greatest Fixpoint, GFP) 기반의 재귀 시맨틱스를 채택하고 있습니다.
  • SHACL: 재귀 시맨틱스에 대한 논의가 진행 중이며, **최소 고정점 (Least Fixpoint, LFP)**으로 수렴하는 추세이지만, 아직 W3C 작업 그룹에서 공식적으로 결정되지 않았습니다.
• 핵심 문제:
  • ShEx 와 SHACL 이 서로 다른 시맨틱스 (GFP vs LFP) 를 따르면서, 두 언어 간의 상호 운용성 (interoperability) 이 저해되고 예측 가능성이 떨어집니다.
  • 실제 구현체 (validators) 들이 일관되지 않은 시맨틱스를 따르고 있어, 동일한 스키마와 데이터에 대해 서로 다른 검증 결과가 도출될 수 있습니다.
  • 재귀와 부정 (negation) 이 결합되었을 때의 시맨틱스 (SMS, LFP, GFP) 간의 이론적 관계와 계산 복잡도가 명확히 규명되지 않았습니다.

2. 방법론 (Methodology)

저자들은 이 문제를 해결하기 위해 다음과 같은 다각적인 접근을 취했습니다.

1. 통일된 형식적 프레임워크 (Simple Shape Language, SSL) 정의:

   • ShEx 와 SHACL 의 핵심 기능을 추상화한 단순한 스키마 언어 (SSL) 를 정의했습니다.
   • 이 언어를 통해 SMS (Supported Model Semantics), GFP, LFP 세 가지 재귀 시맨틱스를 정형화하고 비교 분석했습니다.
   • **이중성 원리 (Duality Principle)**를 활용하여, 계층화 (stratified) 된 부분 문법에서 LFP 와 GFP 가 서로 어떻게 변환 가능한지 수학적으로 증명했습니다.

2. 실제 검증 엔진에 대한 실험적 연구:

   • ShEx 및 SHACL 에 대한 주요 오픈소스 및 상용 검증기 (pySHACL, Jena, Topbraid, ShEx-S 등) 를 대상으로 실험을 수행했습니다.
   • 재귀 시맨틱스를 구분할 수 있는 13 가지 테스트 케이스 (분리 테스트 및 기능 테스트) 를 설계하여 각 엔진이 실제로 어떤 시맨틱스 (LFP, GFP, Brave/Cautious SMS) 를 구현하고 있는지 파악했습니다.

3. 표현력과 복잡도 분석:

   • 실제 ShEx 와 SHACL 언어의 큰 부분 집합 (fragments) 에 대해 GFP 와 LFP 간의 표현력 동등성 (equi-expressiveness) 을 증명했습니다.
   • 데이터 복잡도 (Data Complexity) 와 결합 복잡도 (Combined Complexity) 를 분석하여 세 가지 시맨틱스 간의 계산 비용 차이를 규명했습니다.

3. 주요 기여 (Key Contributions)

1. 통일된 형식적 프레임워크 및 이중성 원리:

   • LFP, GFP, SMS 를 아우르는 통일된 형식적 정의를 제시했습니다.
   • 계층화된 (stratified) 스키마에서 LFP 와 GFP 가 서로 이중적 (dual) 관계에 있음을 증명했습니다. 즉, ShEx 의 GFP 기반과 SHACL 의 LFP 기반이 특정 조건 하에서 동일한 표현력을 가질 수 있음을 보였습니다.

2. 검증기 행동에 대한 실증적 발견:

   • ShEx 검증기: 공식 명세 (GFP) 에 일관되게 부합하는 것으로 확인되었습니다.
   • SHACL 검증기: 매우 이질적입니다. 일부는 Brave SMS (어떤 올바른 할당이라도 만족하면 통과) 를 따르지만, 일부는 GFP 나 LFP 와도 일치하지 않는 고유한 동작을 보이거나, 단순한 스키마에서도 실패하는 등 예측 불가능한 행동을 보입니다.

3. 표현력 동등성 증명:

   • ShEx (GFP 사용) 와 SHACL (LFP 사용) 의 제한된 문법적 부분 집합 (Restricted ShEx, Restricted SHACL) 이 서로 동일한 표현력을 가지며, 서로 간에 유효한 변환이 가능함을 증명했습니다. 이는 두 언어 간의 호환성 문제를 해결할 이론적 근거를 제공합니다.

4. 복잡도 분석 및 SMS 의 비용:

   • LFP/GFP: 모든 언어에서 데이터 복잡도가 **다항 시간 (Polynomial Time, P)**에 속합니다.
   • SMS: 데이터 복잡도가 **NP-완전 (NP-complete)**으로 급격히 증가하여 계산적으로 비효율적 (intractable) 임을 보였습니다. 이는 SMS 가 이론적으로나 실용적으로나 비추천됨을 의미합니다.

4. 연구 결과 (Results)

• 테스트 결과 (Table 2):
  • ShEx 검증기 (rudof, Jena ShEx, ShEx-S) 는 GFP 시맨틱스를 따릅니다.
  • SHACL 검증기 중 pySHACL, SHACL-S, Jena SHACL, rudof 는 Brave SMS 와 일치하는 경향을 보이지만, Topbraid 는 어떤 표준 시맨틱스에도 부합하지 않는 독특한 동작을 보입니다.
  • 재귀가 없는 부정 (non-stratified negation) 이 포함된 테스트에서 많은 검증기가 예외 처리를 하거나 실패했습니다.
• 복잡도 결과 (Table 3):
  • LFP 와 GFP 를 사용하는 경우 데이터 검증이 효율적으로 수행 가능 (P) 합니다.
  • 반면, SMS 를 사용하는 경우 단순한 언어 (SSL) 에서조차 NP-완전 문제가 발생하여 대규모 데이터 처리에 적합하지 않습니다.
• 표현력:
  • ShEx 와 SHACL 은 서로 다른 시맨틱스를 사용하지만, 핵심적인 부분 집합에서는 동일한 표현력을 가지며, 이를 통해 상호 변환이 가능합니다.

5. 의의 및 결론 (Significance)

1. 표준화 및 상호 운용성 개선:

   • ShEx 와 SHACL 이 서로 다른 시맨틱스를 사용하더라도, 이론적으로 호환 가능한 영역이 크다는 것을 증명하여 두 언어 간의 격차를 줄일 수 있음을 보였습니다.
   • SHACL 이 LFP 를 채택하고 ShEx 가 GFP 를 유지하는 것이 상호 운용성 측면에서 문제없음을 이론적으로 입증했습니다.

2. 실무적 권고:

   • SMS 는 비추천: 계산 복잡도가 너무 높기 때문에 실제 도구 구현에서 SMS 를 사용하는 것은 권장되지 않습니다.
   • LFP/GFP 권장: 알고리즘적 처리가 용이하고 (다항 시간), 예측 가능한 행동을 보장하므로 재귀 구현 시 LFP 또는 GFP 를 사용하는 것이 바람직합니다.

3. 미래 방향:

   • SHACL 의 재귀 시맨틱스 표준화가 시급하며, 이 논문에서 제시된 통일된 프레임워크와 복잡도 분석 결과가 W3C 작업 그룹의 의사결정에 중요한 근거가 될 것입니다.
   • 검증기 개발자들은 일관된 시맨틱스 (LFP 또는 GFP) 를 따르도록 하여 사용자의 예측 가능성을 높여야 합니다.

요약하자면, 이 논문은 ShEx 와 SHACL 간의 재귀 시맨틱스 불일치 문제를 이론적 (이중성 원리, 복잡도) 과 실증적 (검증기 테스트) 으로 분석하여, LFP 와 GFP 가 상호 호환 가능하고 계산적으로 효율적임을 증명함으로써, 차세대 RDF 스키마 언어 표준화와 도구 개발에 중요한 방향성을 제시했습니다.