Static Analysis of Recursive SHACL

요약

본 논문은 RDF 데이터 제약 조건 언어인 SHACL(Shapes Constraint Language)에 대한 정적 분석 문제를 다룹니다. 특히 하나의 SHACL 문서가 만족하는 모든 그래프가 다른 SHACL 문서도 만족하는지 여부를 결정하는 문제입니다. 연구진은 이 문제가 일반적인 의미론에서는 결정 불가능함을 증명했으며, well-founded semantics 하에서는 single exponential time 복잡도로 해결 가능한 새로운 방법을 제시했습니다.

핵심 포인트

• SHACL(Shapes Constraint Language)는 RDF 데이터의 제약 조건 및 검증에 사용되는 언어입니다.
• 연구 목표는 하나의 SHACL 문서가 만족하는 그래프 집합이 다른 SHACL 문서도 만족하는지 여부를 정적으로 분석하는 것입니다.
• 일반적인 의미론 하에서 이 문제는 결정 불가능(undecidable)함을 증명했습니다.
• well-founded semantics를 사용하면, 해당 문제가 single exponential time 복잡도로 해결 가능합니다.
• 핵심 기술 기여는 well-founded semantics의 SHACL을 full hybrid mu-calculus로 번역하여 최적의 자동화 기반 결정 절차를 제공하는 것입니다.