Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases

기술 요약: 불일치하는 가중치 지식 베이스 쿼리를 위한 비용 기반 의미론

문제 정의
온톨로지 매개 쿼리 응답(OMQA)은 TBox(온톨로지)와 ABox(데이터)로 구성된 기술 논리(Description Logic, DL) 지식 베이스(KB)에 의존한다. 고전적인 OMQA 의미론은 일차 논리에 기반하며, 지식 베이스가 불일치할 경우 모든 것이 함의되는 문제를 가진다. 기존의 접근 방식들은 수리(repairs)를 통해 불일치를 처리하지만(예: AR 및 brave semantics), 이는 일반적으로 TBox는 신뢰할 수 있다고 가정하고 ABox만을 수정한다. 또한, 표준 수리 의미론은 모든 단언(assertion)을 동일하게 신뢰하거나 카디널리티 기반의 극대성을 활용하는데, 이는 서로 충돌하는 정보에 대해 다양한 신뢰도에 따라 우선순위를 부여하는 미묘한 방식을 결여하고 있다.

본 논문은 정량적 프레임워크를 도입하여 불일치하는 DL KB를 쿼리하는 과제를 해결한다. 핵심 문제는 TBox 공리(axiom)와 ABox 단언 모두가 위반될 수 있으며, 위반 시 할당된 가중치에 따라 벌점이 부과되는 상황에서 의미 있는 확정적(certain) 답변과 가능한(possible) 답변을 정의하는 것이다.

방법론 및 프레임워크
저자들은 $K_\omega = (\langle \mathcal{T}, \mathcal{A} \rangle, \omega)$로 표기되는 가중치 지식 베이스(Weighted Knowledge Base, WKB) 프레임워크를 제안한다.

• 가중치: 가중치 함수 $\omega$는 $\mathcal{T}$의 모든 공리와 $\mathcal{A}$의 모든 단언에 $\mathbb{N}_{>0} \cup \{+\infty\}$ 값을 할당한다. 무한한 가중치는 반드시 만족되어야 하는 "경성(hard)" 제약을 나타내며, 유한한 가중치는 더 높은 값이 더 높은 신뢰도를 나타내는 "연성(soft)" 제약을 나타낸다.
• 해석의 비용: 해석 $I$의 비용은 위반된 모든 공리와 단언의 가중치 합으로 정의된다. 구체적으로, 개념 포함(concept inclusion) $\tau$에 대하여, 비용은 $\omega_\tau \times |vio_\tau(I)|$를 포함한다(여기서 $vio_\tau(I)$는 해당 포함 관계를 위반하는 도메인 요소들의 집합이다). 단언은 최대 한 번만 위반될 수 있다.
• 의미론: 논문은 해석의 비용에 기반하여 네 가지 쿼리 함의 의미론을 정의한다:
  1. $k$-비용 제한 확정 ($K_\omega \models^k_c q$): 비용이 $k$ 이하인 모든 해석에서 $q$가 성립함.
  2. $k$-비용 제한 가능 ($K_\omega \models^k_p q$): 비용이 $k$ 이하인 적어도 하나의 해석에서 $q$가 성립함.
  3. 최적 비용 확정 ($K_\omega \models^{opt}_c q$): 최소 비용($optc(K_\omega)$)을 갖는 모든 해석에서 $q$가 성립함.
  4. 최적 비용 가능 ($K_\omega \models^{opt}_p q$): 최소 비용을 갖는 적어도 하나의 해석에서 $q$가 성립함.

이 프레임워크는 기존의 수리(repair) 의미론을 일반화한다. 구체적으로, TBox 공리가 무한한 가중치를 가질 때, 최적 비용 확정 의미론은 유지된 단언의 가중치 합을 최대화하는 수리를 선택하는 $\le_\omega$-AR 의미론(Bienvenu, Bourgaux, and Goasdoué 2014)과 일치한다.

주요 기여
본 논문의 주요 기여는 이 설정에서의 주요 결정 문제들에 대한 **결합 복잡도(combined complexity)와 데이터 복잡도(data complexity)**에 대한 종합적인 분석이다:

1. 유한 비용 만족 가능성 (Bounded Cost Satisfiability, BCS): 비용이 $\le k$인 해석이 존재하는지 결정함.
2. 확정 및 가능 답변 인식: 정의된 네 가지 의미론 하에서의 함의를 결정함.

연구 범위는 경량 모델인 $\mathcal{EL}^\bot$부터 표현력이 풍부한 $\mathcal{ALCO}$(및 상한 증명을 위한 $\mathcal{ALCO}^\mathcal{Q}$)에 이르기까지 다양한 기술 논리를 다루며, 인스턴스 쿼리(IQ)와 결합 쿼리(CQ)를 모두 처리한다.

복잡도 결과
논문은 다음과 같이 정리된 엄격한 복잡도 경계를 설정한다:

• 결합 복잡도 (Combined Complexity):

  • 대부분의 문제는 EXPTIME-complete이다.
  • CQ에 대한 확정 답변 인식(bounded 및 opt-cost 모두)은 2EXPTIME-complete이다. 이 높은 복잡도는 특정 비용을 갖는 모든 모델에 걸쳐 함의를 검증해야 하는 필요성에서 기인하며, 이는 circumscribed KB와 관련이 있다.
  • 이러한 경계는 가중치와 비용 제한 $k$가 이진법(binary)으로 인코딩된 경우에도 유효하다.

• 데이터 복잡도 (Data Complexity):

  • 유한 비용 만족 가능성 (BCS): NP-complete.
  • 유한 비용 답변 (IQs/CQs): NP-complete (가능) 및 coNP-complete (확정).
  • 최적 비용 답변: 복잡도는 가중치의 인코딩 방식에 따라 크게 달라진다:
    • 가중치가 **단항식(unary)**으로 인코딩되거나 ABox 크기와 독립적으로 유계(bounded)인 경우, 문제는 $\Theta^p_2$-complete이다 (NP 오라클에 대한 로그 횟수의 다항 시간 호출로 해결 가능).
    • 가중치가 **이진법(binary)**으로 인코딩되어 ABox 크이에 비해 지수적으로 커질 수 있는 경우, 문제는 $\Delta^p_2$-complete가 된다 (NP 오라클에 접근 가능한 다항 시간 내 해결 가능).
  • 논문은 이진 가중치를 가진 opt-cost 확정 의미론의 경우 상한(upper bound)이 아직 열려 있으나, 하한(lower bound)은 $\Delta^p_2$-hard임을 명시한다.

의의 및 주장
저자들은 비용 기반 의미론 하에서 불일치하는 KB를 쿼리하는 복잡도 지형에 대해 "거의 완전한 그림"을 제공한다고 주장한다. 본 연구의 의의는 다음과 같다:

1. 정량적 유연성: 이진적인 일치 여부를 넘어, 답변을 그들의 "강건성"(즉, 최적 비용에 근접한 해석에서 성립하는지 여부)에 따라 순위화하거나 필터링할 수 있는 단계적 접근 방식을 제공한다.
2. 일반화: 데이터베이스의 연성 제약(soft constraints)(Carmeli et al. 2021)과 온톨로지의 가중치 수리(weighted repairs) 개념을 통합하여, 최적 비용 의미론이 선호 수리(preferred repair) 의미론을 자연스럽게 일반화함을 보여준다.
3. 기술적 깊이: 복잡도 증명은 다음을 포함한 고급 DL 추론 기법을 활용하고 적응시킨다:
   • 상한을 설정하기 위한 여과(Filtration) 및 유계 모델 속성(bounded model properties).
   • 하한을 설정하기 위한 카디널리티 쿼리 답변 및 circumscribed KB로부터의 환원(reduction).
   • 가중치 위반의 특수한 제약을 처리하기 위해 counting 쿼리 문헌(Manière 2022)의 "인터레이싱(interlacing)" 및 "quotient" 구조를 적응시킨 것.

논문은 향-후 연구 방향으로 역 롤(inverse roles), 롤 포함(role inclusions), 기능적 롤(functional roles)을 포함하는 DL(예: DL-Lite 계열)로의 확장을 식별하며, 현재의 상한 결정 기술이 이러한 구조들로 쉽게 전이되지 않음을 언급한다. 또한 실제 구현을 위한 알고리즘 개발의 과제도 강조한다.