A General Sufficient Condition for Rewriting Horn-ALCHI Atomic Queries into GQL

기술 요약: Horn-ALCHI 원자 쿼리를 GQL로 재작성하기 위한 일반적 충분 조건

문제 정의
ISO 표준인 GQL(Graph Query Language)의 등장은 제어된 정규 재귀(controlled regular recursion)를 통해 1차 논리(first-order logic, FO)를 확장하는 강력한 쿼리 언어를 도입했습니다. 이는 온톨로지 매개 쿼리(Ontology-Mediated Query, OMQ) 답변 문제에 중요한 질문을 던집니다. 즉, 표현력이 풍부한 기술 논리(Description Logics, DL)로 정의된 어떤 규칙 쿼리가 GQL로 재작성될 수 있는가 하는 점입니다.

저자들은 역역할(inverse roles)과 역할 생성자(role constructors)를 지원하는 표현력이 풍부한 DL인 Horn-ALCHI에 주목합니다. DL-Lite 계열과 달리, Horn-ALCHI는 일반적으로 1차 논리로 재작성이 불가능하므로, 표준 SQL 기반 평가 기법은 불충분합니다. GQL은 필요한 표현력(구체적으로는 합집합의 결합형 양방향 정규 경로 쿼리, 즉 UC2RPQ)을 제공하지만, 어떤 Horn-ALCHI 쿼리가 이 파편(fragment)으로 효과적으로 번역될 수 있는지는 여전히 불분명합니다. 본 논문은 이러한 재작성이 가능한 광범위하고 결정 가능한 Horn-ALCHI OMQ 클래스를 식별함으로써 이 간극을 메우고자 합니다.

방법론
저자들은 다단계의 동등성 보존 변환 파이프라인을 제안합니다:

1. Horn-ALC$\not\exists$로의 정규화:
   프로세스는 Horn-ALCHI 쿼리를 동등한 Horn-ALC$\not\exists$ 쿼리로 변환하는 것으로 시작됩니다. 여기에는 다음 과정이 포함됩니다:

   • 역할 포함 공리(예: $R \sqsubseteq S$) 및 역역할 공리를 제거하기 위해, 역할 포함의 재귀적-추이적 폐쇄(reflexive-transitive closure)를 통해 제약 조건을 전파합니다.
   • 규칙 헤드에서의 존재 양화(existential quantification)($\text{예: } A \sqsubseteq \exists R.B$)를 제거하기 위해, Horn-SHIQ에서 확립된 기법을 따라 이를 Datalog 규칙으로 번역합니다. 이 단계는 규칙 세트의 크기에 대해 지수적 팽창(exponential blow-up)을 초래할 수 있으나 의미론적 동등성은 보존합니다.

2. DL 오토마타로의 번역:
   정규화된 Horn-ALC$\not\exists$ 쿼리는 그다음 DL 오토마타라는 새로운 유한 상태 장치로 매핑됩니다.

   • 구조: 오토마타는 개념 이름(concept names)에 대응하는 상태들과 특수한 수락 상태($q_{acc}$)로 구성됩니다. 전이(transition)는 이진(binary, 클래스나 역할 레이블을 사용하여 한 상태에서 다른 상태로 이동)이거나 다항(multi-ary, $\varepsilon$ 레이블을 사용하여 하나의 상태를 여러 상태의 집합으로 분할)입니다.
   • 의미론: 수락 실행(accepting run)은 상태-상수 쌍으로 레이블이 지정된 노드들을 가진 유한 루트 트리(finite rooted tree)로 정의됩니다. 이 트리 구조는 "체이스(chase)" 절차를 통한 사실(fact)의 유도를 반영합니다. 오토마타는 초기 상태와 상수로 시작하여 모든 리프(leaf)가 수락 상태로 레이블링되는 실행이 존재할 때 팩트 세트를 수락합니다.

3. 계층화(Stratification) 및 PQ로의 재작성:
   재작성을 위한 충분 조건인 계층화를 식별하는 것이 핵심 기여입니다.

   • 계층화: 저자들은 오토마타의 전이 함수를 기반으로 상태 간의 의존 관계($\succ_A$)를 정의합니다. 의존성은 이진 전이(역할)가 발생한 후 결과적으로 다항 전이가 나타나는 경로가 있을 때 존재합니다. 오토마타가 계층화되어 있다는 것은 이 의존 관계가 비순환(acyclic)임을 의미합니다.
   • 재작성 알고리즘: 계층화된 오토마타에 대해, 저자들은 동등한 **양의 양방향 정규 경로 쿼리(Positive Two-Way Regular Path Query, PQ)**를 구성합니다. 이는 계층(stratum)에 따라 귀납적으로 수행됩니다:
     • 가장 낮은 계층(의존성이 없는 상태)의 경우, 이진 전이(비결정적 유한 오토마타로 모델링됨)로부터 유도된 정규 표현식을 사용하여 쿼리를 직접 구성합니다.
     • 더 높은 계층의 경우, 다항 전이로 인한 분기를 처리하기 위해 존재 양화(existential quantifiers)를 도입하여 의존적인 하위 계층의 PQ를 재귀적으로 포함시켜 구성합니다.
   • 이 구성은 계층화의 비순환성 덕분에 무한 재귀를 방지하여 유한한 PQ를 보장합니다.

4. GQL로의 매핑:
   마지막으로, 결과물인 PQ는 **결합형 양방향 정규 경로 쿼리의 합집합(Union of Conjunctive Two-Way Regular Path Queries, UC2RPQ)**으로 변환됩니다. UC2RPQ는 GQL의 핵심 파편이므로, 이를 통해 최종적인 재작성이 성립됩니다.

주요 기여

• DL 오토마타 형식론: Horn-ALCHI 의미론과 경로 기반 쿼리 언어 사이의 가교로서 DL 오토마타를 도입했습니다.
• 계층화 조건: GQL 재작성 가능성을 위한 일반적인 충분 조건으로서 계층화를 식별했습니다. 이 조건은 복잡도를 증가시키는 것으로 알려진 특정 순환 의존성을 배제하면서도, 기존 방식보다 더 넓은 범위의 쿼리를 허용합니다.
• 일반적 재작성 절차: 정규화, 오토마타 구성, 계층화된 PQ 생성을 거쳐 Horn-ALCHI 쿼리를 GQL 공식으로 변환하는 완전하고 구성적인 알고리즘을 제공합니다.
• 선행 연구의 포섭: 저자들은 자신들의 클래스가 다음을 엄격히 포섭함을 입증했습니다:
  • DL-Lite: DL-Lite 쿼리는 자연스럽게 계층화된 오토마타(단일 계층)를 생성합니다.
  • Harmless Linear ELHI: 제안된 클래스는 이전 ELHI 재작성 연구의 "무해한(harmless)" 제한 사항을 벗어나는 쿼리들을 포함합니다.
  • ELH$^{ql}_i$: 이 클래스는 Crit와 Acc를 포함하는 예시(논문에 등장하는 예시)와 같이, ELH$^{ql}_i$의 관점에서는 국소적(local)이지 않지만 계층화되어 있어 재작성이 가능한 쿼리들을 포함합니다.

결과 및 의의
본 논문은 GQL로 재작성될 수 있는 실질적이고 관련성 높은 Horn-ALCHI OMQ의 하위 클래스를 확립했습니다.

• 표현력: 이 접근 방식은 역역할과 규칙 본문의 결합(예: $Sens(x) \land Onl(x) \to Crit(x)$와 $Crit(x) \land Acc(x, y) \to Trust(y)$의 결합) 사이의 복잡한 상호작용을 포함하여, 기존에 GQL 파편으로 재작성이 불가능하다고 여겨졌던 쿼리들을 처리합니다.
• 완전성: 저자들은 제시된 조건이 충분 조건임을 인정합니다. GQL로 재작성 가능하지만(예: 중첩된 정규 경로 쿼리가 필요한 경우) 계층화 조건을 만족하지 않는 Horn-ALCHI 쿼리들이 존재합니다.
• 실용성: 저자들은 정규화 단계가 지수적 팽창을 일으킬 수 있음을 언급하면서도, 계층화 체크 자체는 결정 가능하다는 점을 명시했습니다. 또한 실제 저장소(예: Manchester OWL Repository)에 대한 경험적 평가가 얼마나 많은 실질적 쿼리가 이 클래스에 속하는지 판단하기 위한 필수적인 다음 단계라고 제안합니다.

결론
본 논문은 표현력이 풍부한 DL에 대한 온톨로지 매개 쿼리를 평가하기 위해 GQL을 활용하는 이론적 토대를 제공합니다. DL 오토마타와 계층화 개념을 도입함으로써, 저자들은 단순한 DL-Lite 시나리오를 넘어 더 복잡하고 표현력이 풍부한 지식 베이스로 GQL의 적용 범위를 확장하는 견고한 방법을 제시합니다. 이 연구는 GQL을 더 넓은 범위의 OMQ를 위한 유효한 대상 언어로 위치시키며, 표현력이 풍부한 온톨로지 추론과 현대적인 그래프 쿼리 프로세싱 사이의 간극을 메웁니다.