기술 요약: 충돌하는 사실들에 대한 선호도를 명시하고 불일치하는 지식 베이스를 쿼리하기 위한 규칙 기반 접근법

문제 정의

불일치 허용 의미론(inconsistency-tolerant semantics), 특히 부분 집합 수선(subset repairs)에 기반한 방식은 제약 조건을 위반하는 지식 베이스(KB)를 쿼리하기 위한 표준적인 접근법이다. 우선순위 관계(예: Staworko 등이 제시한 우선순위 데이터베이스 프레임워크)를 사용하여 "최적의 수선(optimal repairs)"을 정의하는 프레임워크들이 존재하지만, 결정적인 간극이 남아 있다: 바로 그 우선순위 관계 자체를 어떻게 편리하게 명시할 것인가 하는 점이다.

기존 문헌들은 우선순위 관계가 이미 주어진 것으로 가정하지만, 이는 사용자에게 모든 충돌하는 사실들 사이의 이진 관계를 수동으로 입력하도록 기대하는 것이므로 비현실적이다. 또한, 사용자가 규칙을 통해 선호도를 지정하려고 할 때, 이러한 규칙들이 **순환(cycles)**을 유발할 수 있다(예: 사실 A는 B보다 선호되고, B는 C보다 선호되며, C는 A보다 선호되는 경우). 이러한 순환은 우선순위 관계가 반드시 비순환적(acyclic)이어야 한다는 조건에 위배되어 관계를 무효화한다. 본 논문은 이러한 선호도를 선언적으로 명시하고, 발생하는 순환을 해결하여 불일치하는 지식 베이스를 실용적으로 쿼리할 수 있는 문제를 다룬다.

방법론

1. 규칙 기반 선호도 명시

저자들은 데이터셋 $D$와 메타 데이터베이스 $M$에 대해 평가되는 **선호 규칙(preference rules)**으로부터 우선순위 관계를 도출하는 선언적 프레임워크를 도입한다.

• 메타 데이터베이스: 고유 식별자를 통해 $D$의 사실들과 연결된 메타데이터(예: 날짜, 출처 신뢰도)를 포함하는 데이터셋 $F$.
• 선호 규칙: $Cond(x_1, x_2) \to pref(x_1, x_2)$ 형태의 규칙이며, 조건부 $Cond$는 다음을 참조할 수 있다:
  • $D$ 내 사실의 존재 또는 부재.
  • $F$ 내의 메타데이터 (예: 날짜나 신뢰도 점수 비교).
  • 온톨로지 공리 (예: 하위 클래스 관계).
  • 부정(negation) 및 부등식.
• 유도된 관계: 규칙은 조건이 성립할 경우 선호 $pref(id(\alpha), id(\beta))$를 유도한다. 실제 우선순위 관계 $\succ_{\Sigma, K, M}$는 이러한 유도된 선호들을 필터링하여, 함께 나타나는 쌍 $(\alpha, \beta)$가 실제로 충돌 내에 존재하는 경우만을 포함하여 형성된다.

2. 순환 처리

유도된 관계는 순환을 포함할 수 있으므로, 본 논문은 두 가지 상호 보완적인 전략을 제안한다.

• 정적 비순환성 검사 (Static Acyclicity Checking): 규칙 집합이 임의의 데이터셋에 대해 비순환 관계를 생성할 것인지 조사한다.
  • 본 논문은 일반적인 언어 $PL_{DL}$에 대해 비순환성 검사가 **결정 불가능(undecidable)**함을 증명한다.
  • 그러나 제한된 언어 $PL_{pos}$(온톨로지 원자나 부정이 없는 양의 규칙)와 이진 부정 제약 조건(binary denial constraints)의 경우, 문제는 coNP 내에서 결정 가능하다.
  • 강한 비순환성(strong acyclicity) 개념이 도입된다: 규칙 집합이 충돌 여부와 상관없이 임의의 KB 및 메타 데이터베이스에 대해 유도된 관계가 비순환적이라면, 해당 규칙 집합은 강하게 비순환적이라고 한다.
• 실용적 순환 해결 (Pragmatic Cycle Resolution): 규칙이 비순환성을 보장하지 못할 경우, 사용자가 규칙을 우선순위 레벨($\Sigma_1, \dots, \Sigma_n$)로 분할할 수 있게 하며, 낮은 인덱스일수록 높은 우선순위를 갖는다. 네 가지 전략이 추출된 비순환 부분 관계를 위해 정의된다:
  1. Going Up ($\succ_u$): 가장 낮은 인덱스(가장 높은 우선순위, $\Sigma_1$)부터 시작하여 다음 레벨을 추가했을 때 순환이 형성되면 중단하며 단계적으로 레벨을 추가한다.
  2. Going Down ($\succ_d$): 모든 레벨의 합집합에서 시작하여, 순환에 참여하는 쌍들을 가장 높은 인덱스(가장 낮은 우선순위) 레벨부터 반복적으로 제거하여 비순환성이 달성될 때까지 수행한다.
  3. Refined Going Up ($\succ_{ru}$): 다음 레벨을 추가하기 전에 레벨 내부의 순환을 먼저 제거하는 변형 방식이다.
  4. Grounded ($\succ_g$): 논증 프레임워크(argumentation frameworks)의 그라운디드 확장(grounded extensions)에서 영감을 얻은 고정점(fixpoint) 접근 방식이다.
  • 본 논문은 이러한 전략들 사이의 이론적 관계(예: $\succ_u \subseteq \succ_d \subseteq \succ_g$)를 확립하고, 특정 KB 구조로 매핑될 때 기존의 가능론적 수선(possibilistic repairs) 및 비패배 수선(non-defeated repairs) 개념과 연결한다.

3. 구현

저자들은 **답집합 프로그래밍(Answer Set Programming, ASP)**을 사용하여 엔드 투 엔드 시스템을 구현하였다.

• 입력 인코딩: 로직 프로그램은 데이터셋, 메타 데이터베이스, 제약 조건, 쿼리 및 선호 규칙을 인코딩한다.
• 충돌 및 원인 계산: 시스템은 ASP를 사용하여 충돌과 원인(최소 불일치 부분 집합)을 계산한다. 특히, 이 구현은 기존 도구들이 제한적인 **비이진 충돌(non-binary conflicts, 임의 크기의 충돌)**을 처리할 수 있다.
• 우선순위 계산: 순환 해결 전략들이 최종 우선순위 관계를 도출하기 위해 ASP 프로그램으로 인코딩된다.
• 쿼리 응답: 시스템은 다양한 의미론(Brave, AR, IAR)과 결합된 다양한 수선 유형(Subset, Pareto-optimal, Completion-optimal) 하에서 쿼리를 평가한다.

주요 결과

이론적 기여

• 결정 불가능성: 일반적인 선호 규칙 집합이 비순환 관계를 생성하는지 확인하는 것이 결정 불가능함을 증명하였다.
• 결정 가능성: 양의 규칙($PL_{pos}$)과 이진 부정 제약 조건의 경우, 비순환성 검사가 coNP 내에서 결정 가능함을 증명하였다.
• 전략적 동등성: 제안된 순환 해결 전략들이 특정 KB 구조로 매핑될 때 알려진 수선 개념(Possibilistic, Non-defeated, Grounded)에 대응함을 확립하였다.

실험적 평가

시스템은 CQAPri 벤치마크(합성 DL-Lite KB)를 통해 다양한 크기(최대 약 200만 개의 사실)와 충돌 밀도에서 평가되었다.

• 순환 해결 성능:
  • Going Down ($\succ_d$) 전략이 대부분의 시나리오에서 $\succ_g$ 및 $\succ_u$보다 훨씬 빠르게 계산되었으며, 종종 유사한 결과를 생성하였다.
  • Refined Going Up ($\succ_{ru}$) 전략은 ASP 인코딩의 복잡성으로 인해 작은 데이터셋에서도 메모리 오버플로를 발생시켰다.
  • 시스템은 높은 충돌 비율(최대 46%)과 많은 수의 선호 사실이 있는 데이터셋에서도 성공적으로 우선순위 관계를 계산하였다.
• 쿼리 응답 성능:
  • ASP 기반 시스템은 최적 수선 의미론 하에서 답을 계산할 때 기존의 SAT 기반 도구인 ORBITS보다 일반적으로 (대규모 데이터셋에서 수 차례의 배수만큼) 느렸다.
  • 그러나 ASP 시스템은 ORBITS가 실패한 경우(시간 초과 또는 메모리 오버플로)에도 C-AR 및 C-brave 의미론 하에서 쿼리에 답하는 데 성공하였다.
  • 본 시스템은 비이진 충돌에 대해 최적 수선 기반 의미론을 구현한 첫 번째 사례이다.

의의 및 주장

본 논문은 불일치하는 KB에서 우선순위 관계를 명시하기 위한 최초의 선언적, 규칙 기반 프레임워크를 제공함으로써, 우선순위 수선 의미론의 실질적 채택을 저해해 온 간극을 해결한다고 주장한다.

• 유연성: 규칙이 메타데이터와 온톨로지 공리를 참조할 수 있게 함으로써, 수동적인 이진 관계 입력 없이도 불일치 관리 정책을 정의할 수 있는 유연한 방법을 제공한다.
• 순환 관리: 순환 문제에 대한 실용적인 해결책을 제공하며, 다양한 해결 전략과 특정 규칙 클래스에 대한 이론적 보장을 제공한다.
• 구현: 본 구현은 이 작업을 위해 ASP를 사용하는 것이 타당함을 입증하며, 특히 ORBITS와 같은 최신 도구에서 부족한 비이진 충돌을 처리할 수 있는 능력을 보여준다.
• 겸손함: 저자들은 자신들의 ASP 구현이 이진 충돌에 대해 SAT보다 효율성이 떨어질 수 있음을 인정하면서도, 더 높은 표현력(임의 크기의 충돌 처리)과 모듈성(예: 다른 수선 계산으로의 확장 용이성)을 강조한다. 이들은 단순 속도 면에서 SAT를 능가했다고 주장하는 것이 아니라, 접근 방식의 독특한 역량을 강조한다.

본 연구는 향-후 연구 방향으로 더 넓은 이론 클래스로의 정적 분석 확장, 최적 수선의 유일성 조사, 그리고 표준 데이터 형식으로부터 로직 프로그램을 생성하는 완전 자동화 파이프라인 구축 등을 제시하며 마무리된다.