기술적 요약: 등호를 포함한 1 차 및 2 차 의존성에 대한 목표 주도 쿼리 응답

1. 문제 제기

데이터베이스에서의 의존성 (dependencies) 은 무결성 제약 조건을 표현하고, 데이터 불완전성을 처리하며, 스키마 변환을 지정하는 데 사용됩니다. 1 차 의존성 (Tuple-Generating Dependencies, TGDs 및 Equality-Generating Dependencies, EGDs 등) 은 표준적이지만, 특정 클래스의 스키마 매핑의 합성을 표현하기 위해서는 2 차 (SO) 의존성이 필요합니다. 결과부에 등호 원자 (equality atoms) 를 추가하여 확장된 SO 의존성은 매우 표현력이 풍부한 스키마 매핑들의 합성을 표현할 수 있습니다.

이러한 의존성들에 대한 쿼리를 응답하는 표준 접근법은 chase 알고리즘의 변형을 사용하여 **범용 모델 (universal model)**을 계산하는 것입니다. 그러나 이 접근법에는 다음과 같은 중대한 한계가 있습니다:

1. 비효율성: 전체 범용 모델을 계산하는 과정은 종종 특정 쿼리와 무관한 방대한 수의 추론을 생성합니다.
2. 확장성: 데이터가 자주 변경되는 경우 전체 chase 를 다시 계산하는 것은 과도하게 비용이 많이 듭니다.
3. 등호의 복잡성: 기존 목표 주도 기법 (Magic Sets 등) 은 등호와 함수 변수를 포함하는 의존성을 처리하는 데 어려움을 겪습니다. 등호를 명시적으로 공리화하는 (동치성과 함수적 반사성 공리를 사용하는) 단순한 접근법은 중복 추론의 폭주로 인해 비효율적인 추론과 비종결 고정점 계산을 초래합니다.

본 논문은 불필요한 추론을 피하면서도 정확성과 종결성을 보장하는, 등호를 포함한 1 차 및 2 차 의존성에 대한 효율적인 목표 주도 쿼리 응답 기법을 개발하는 미해결 문제를 다룹니다.

2. 방법론

저자들은 입력 의존성을 변형하여 후속 chase 계산이 쿼리에 불필요한 추론을 최소화하면서 쿼리에 응답하도록 하는 변환 기반 접근법을 제안합니다. 이 기법은 7 가지 주요 단계로 구성된 파이프라인 (알고리즘 1) 으로 구현됩니다:

2.1 2 차 양화사 제거

입력 SO 의존성 $\Sigma$는 2 차 양화사를 제거하고 함수 변수를 함수 기호로 변환하여 1 차 (FO) 공식 집합 ($\Sigma_1$) 으로 변환됩니다. 이 변환은 쿼리 응답을 보존하므로, 후속 단계들은 함수 기호를 포함하더라도 1 차 논리 프레임워크 내에서 작동할 수 있습니다.

2.2 단일화 (Singularisation)

전체 동치성 공리의 오버헤드 없이 등호를 효율적으로 처리하기 위해, 저자들은 Marnette 의 작업을 확장한 **단일화 (singularisation)**의 새로운 변형을 적용합니다.

• 메커니즘: 이 기법은 의존성 본체 (body) 를 수정하여 중복 추론을 "가지치기"합니다. 동치성 공리를 사용하여 등호를 가진 항들 간에 사실을 복사하는 대신, 의존성을 등호를 통해 원자들을 명시적으로 조인 (join) 하도록 다시 씁니다.
• 이전 작업의 수정: 저자들은 ten Cate 등이 제시한 이전 공식화에서 함수적 반사성 (만약 $a \approx b$이면 $f(a) \approx f(b)$인 성질) 에 관한 불완전성을 식별합니다. 완전한 함수적 반사성 공리를 단순히 추가하는 것은 비종결을 초래합니다.
• 해결책: 저자들은 D-제한 함수적 반사성 공리를 도입합니다. 이 공리들은 도메인 술어 $D$에 의해 추적되는 관계 사실에 나타나는 항들에 대해서만 등호를 유도합니다. 이는 모든 관련 쿼리 응답을 보존하면서도 범용 모델이 유한하게 유지되도록 보장합니다.

2.3 스코렘화 (Skolemisation)

존재 양화사를 스코렘 함수 기호로 대체하여 FO 의존성을 논리 프로그램 ($P_3$) 으로 변환합니다. 중요한 점은 원래 SO 의존성에서 온 "진짜" 함수 기호와 스코렘 기호 사이의 구분을 유지한다는 것입니다. 함수적 반사성 공리는 스코렘 항에 대한 무한한 유도를 방지하기 위해 "진짜" 함수 기호에만 적용됩니다.

2.4 관련성 분석

역방향 체이닝 (backward-chaining) 기법을 사용하여 쿼리 응답에 기여함이 증명된 전체 규칙들을 제거합니다.

• 추상화: 기본 인스턴스는 각 술어에 대한 대표 상수를 포함하는 더 작은 "임계 인스턴스 (critical instance)"로 추상화됩니다.
• 분석: 이 추상 인스턴스에서의 프로그램 고정점이 계산됩니다. 추상 인스턴스에서 발동할 수 없는 규칙들은 관련이 없다고 판단되어 제거됩니다.
• 최적화: 이 알고리즘은 등호 원자가 종종 관계 원자와 도메인 규칙으로부터 유도될 수 있다는 사실을 활용하여, 모든 잠재적 매칭에 대해 반사성 규칙을 고려할 필요를 없앱니다.

2.5 Magic Sets 변환

남은 규칙들에 Magic Sets 알고리즘의 변형을 적용하여 관련 없는 규칙 인스턴스(전체 규칙이 아닌) 를 가지치기합니다.

• 장식 (Adornments): 술어들은 측면 정보 전달을 시뮬레이션하기 위해 "바운드 (bound, b)" 또는 "프리 (free, f)" 마커로 장식됩니다.
• 등호 처리: 이 변환은 등호 술어를 대칭적으로 처리하고, 그렇지 않으면 모든 술어를 발동시킬 반사성 규칙의 처리를 피함으로써 등호에 대해 최적화됩니다.
• 종결성: 저자들은 원래 chase 가 종결한다면, 마술 술어의 도입에도 불구하고 변환된 프로그램의 고정점 또한 종결함을 증명합니다.

2.6 본체에서의 상수 및 함수 기호 제거

Magic Sets 변환은 규칙 본체에 함수 항을 도입할 수 있으며, 이는 표준 chase 변형이 처리할 수 없습니다. 저자들은 본체 내의 상수와 함수 항을 새로운 변수와 보조 술어 ($F_f$) 로 대체하는 변환 (defun) 을 적용하여, 항을 본체에 포함시키지 않고 함수 적용을 공리화합니다.

2.7 비단일화 (Desingularisation)

마지막으로, 단일화 과정에서 도입된 등호들을 변수를 그들의 등호 항으로 대체하여 규칙 본체에서 제거합니다. 그 결과 본체에 등호, 상수, 함수 기호가 없는 "안전한" 논리 프로그램 ($P_7$) 이 생성되어 효율적인 평가를 준비합니다.

2.8 최종 평가

최종 프로그램 $P_7$은 등호를 "진짜" 등호로 취급하는 (함수 적용을 추적하기 위해 $V_f$ 술어 사용) chase 변형으로 평가되지만, 스코렘 기호에 대해서는 함수적 반사성을 강제하지 않습니다. 이는 최종 단계가 효율적이며 명시적 등호 공리화의 오버헤드로부터 자유로워지도록 보장합니다.

3. 주요 기여

1. 등호를 포함한 SO 의존성에 대한 첫 번째 목표 주도 기법: 본 논문은 등호를 포함한 일반화된 2 차 의존성에 대한 목표 주도 쿼리 응답이 가능한 첫 번째 기법을 제시합니다.
2. 수정된 단일화: 함수 변수를 처리하고 비종결을 초래하지 않으면서 함수적 반사성을 해결함으로써 완전성을 보장하는 수정되고 확장된 단일화 기법.
3. 등호를 위한 관련성 분석: 범용 모델의 추상화를 계산하여 불필요한 의존성을 식별하는 새로운 분석 기법으로, 등호의 존재 하에서도 쿼리 응답에 기여할 수 없는 규칙들을 효과적으로 필터링합니다.
4. 최적화된 Magic Sets: 대칭성을 활용하고 일반적으로 오버헤드의 원인이 되는 반사성 규칙의 처리를 피함으로써 등호를 효율적으로 처리하는 Magic Sets 변형.
5. 벤치마크 생성: 이 도메인의 기존 벤치마크가 부족하다는 문제를 해결하기 위해, 비자명한 추론을 보장하는 합성 2 차 의존성 및 데이터셋을 생성하는 새로운 기법.
6. 구현 및 평가: 등호를 포함한 2 차 의존성에 대한 최초의 chase 구현 및 광범위한 경험적 평가.

4. 실험 결과

저자들은 Java 로 프로토타입을 구현하고, 고정점 계산을 위해 RDFox 시스템을 활용했습니다. 그들은 다음에서 접근법을 평가했습니다:

• 1 차 벤치마크: Benedikt 등이 제공한 표준 데이터셋 (LUBM, Deep, Ont).
• 2 차 벤치마크: 그들의 도구에 의해 생성된 새로운 합성 데이터셋 (Gen-26, Gen-27, Gen-28).

주요 발견:

• 성능 향상: 목표 주도 쿼리 응답은 전체 범용 모델을 계산하는 것보다 수십 배에서 수백 배 더 빠를 수 있습니다. 일부 경우 (예: Deep300 시나리오) 전체 chase 는 시간 제한 내에 종결되지 못했지만, 목표 주도 접근법은 모든 쿼리에 성공적으로 응답했습니다.
• 기법 비교:
  • 관련성 분석은 성능 향상의 주요 동인으로 식별되었으며, 종종 유도된 사실의 수를 크게 줄였습니다.
  • Magic Sets은 특히 관련성 분석과 결합되었을 때 추가적인 이점을 제공했지만, 일부 경우 (예: Ont-256) 마술 규칙의 오버헤드가 이점을 상쇄할 수도 있었습니다.
  • 2 차 오버헤드: 2 차 의존성의 경우, 함수 적용을 위한 사실 생성 ( $F_f$ 술어를 통해) 의 오버헤드가 상당했습니다. 관련성 분석은 이러한 사실들을 생성해야 하는 항의 수를 줄였기 때문에 특히 효과적이었습니다.
• 사실 감소: 이 기법들은 전체 chase 에 비해 "유용한" 유도 사실의 수를 종종 수 배에서 수백 배까지 크게 줄였습니다.

5. 중요성과 주장

본 논문은 매핑의 합성이 종종 등호를 포함한 복잡한 2 차 의존성으로 이어지는 데이터 통합 및 스키마 매핑 합성에서의 중요한 병목 현상을 해결했다고 주장합니다. 목표 주도 기법이 이러한 복잡한 설정에 적용 가능함을 입증함으로써, 저자들은 다음을 보여줍니다:

• 전체 범용 모델을 계산하는 것과 관련된 "차원의 저주"를 피할 수 있습니다.
• 단일화, 관련성 분석, 그리고 Magic Sets 의 결합은 등호와 함수 변수의 특정 과제를 처리하기 위한 강력한 프레임워크를 제공합니다.
• 전통적인 방법이 실패하는 대규모 합성 벤치마크를 성공적으로 처리한 사례가 입증하듯, 이 접근법은 실용적입니다.

저자들은 향후 작업에 대해 겸손하게 언급하며, 종결하지 않는 chase 시나리오 (예: 가드된 의존성) 로 이러한 기법을 확장하고 보조 사실 (예: $D$ 및 $F_f$ 술어) 의 오버헤드를 더욱 줄이는 것이 여전히 열린 과제임을 지적합니다.