Static Analysis of Recursive SHACL

SHACL (Shapes Constraint Language) 는 RDF 데이터에 대한 제약 조건을 'shapes'라는 개념을 통해 표현합니다. 그 핵심 서비스는 검증 (validation) 입니다: 데이터 그래프가 SHACL 문서를 준수하는지 확인하는 것입니다. 그러나 지금까지, 문서 간 비교를 위한 정적 분석 서비스는 존재하지 않았습니다. 이 논문에서는 다음과 같은 문제를 연구합니다: 하나의 SHACL 문서를 만족하는 모든 그래프가 다른 문서도 만족하는지를 결정하는 문제입니다. 이전 작업들이 shape expression 의 함의 (implication) 만 고려한 것과 달리, 우리는 (recursive) shape definition 과 targets 를 포함하는 문서를 고려합니다. 우리는 함의 (a.k.a. containment) 가 지원되는 semantics 와 stable model semantics 하에서는 undecidable임을 보였습니다. 이는 ALCIO를 사용하여 shape expression 을 표현하는 fragment 에 대해서도 마찬가지입니다. well-founded semantics 하에서는, 놀랍게도, single exponential time 에서 결정 가능합니다. 우리의 핵심 기술적 기여는 well-founded semantics 하의 SHACL 을 full hybrid mu-calculus 로 번역하는 것입니다. 이는 well-founded models 과 fixed point modal logic 간의 새로운 연결을 드러내며, worst-case optimal automata-based decision procedure 를 제공합니다.