Answering Path Queries under Linear and Guarded Existential Rules

당신이 거대하고 혼란스러운 도시에서 특정 친구를 찾으려고 한다고 상상해 보세요. 당신에게는 현재 사람들이 어디에 있는지 보여주는 지도(데이터베이스)가 있지만, 지도가 직접 보여주지 못하는 것들을 알려주는 규칙 책(온톨로지)도 가지고 있습니다. 예를 들어, 규칙 책에는 "앨리스가 밥과 친구라면, 밥도 앨리스와 친구이다"라거나 "누군가를 팔로우하면 그 사람과 연결된다"라는 내용이 적혀 있을 수 있습니다. 컴퓨터 과학의 세계에서는 이를 **온톨로지 매개 쿼리 응답(ontology-mediated query answering)**이라고 부릅니다. 이는 단순히 가공되지 않은 데이터를 보는 것이 아니라, 논리를 사용하여 빈틈을 메우는 매우 똑똑한 가이드가 있는 것과 같습니다.

하지만 경로에 대해 질문하기 시작하면 까다로워집니다. 단순히 "앨리스가 밥과 친구인가?"라고 묻는 대신, "내가 친구 관계의 사슬을 따라가서 앨리스로부터 밥에게 도달할 수 있는가? 설령 그 사슬이 매우 길거나 루프를 돌더라도 말이다"라고 물을 수 있습니다. 이것들은 **경로 쿼리(path queries)**라고 불립니다. 이것들은 소셜 미디어나 시맨틱 웹 같은 복잡한 네트워크를 탐색하는 데 필수적입니다. 하지만 문제는, 이러한 경로 찾기 질문을 강력한 규칙 책과 결합할 때, 컴퓨터의 작업이 믿을 수 없을 정도로 어려워지거나 때로는 해결하는 것이 불가능해질 수도 있다는 점입니다. 과학자들이 고민해 온 핵심 질문은 이것입니다: 서로 다른 유형의 규칙 책이 있을 때, 이 경로 질문에 답하는 것이 실제로 얼마나 어려운가?

이 논문은 일련의 탐정들(Jean-François Baget, Meghyn Bienvenu, Marie-Laure Mugnier, 그리고 Michaël Thomazo)이 두 가지 인기 있는 유형의 규칙 책인 **선형 규칙(Linear Rules)**과 **가드 규칙(Guarded Rules)**에 대한 경로 쿼리의 난이도를 조사하기로 결정한 이야기와 같습니다. "선형 규칙"은 단순한 일단계 지침(예: "A가 참이면 B도 참이다")을 의미하며, "가드 규칙"은 선형 규칙보다 약간 더 복잡하여 특정 "가드(수호자)" 사실이 존재해야 트리거되는 지침(예: "A가 참이고 B가 참이면 C는 참이다")을 의미합니다. 저자들은 단순히 추측한 것이 아니라, 이 퍼즐을 해결하는 데 정확히 어느 정도의 컴퓨팅 파워가 필요한지를 증명하여 컴퓨터 과학자들을 위한 정밀한 "난이도 차트"를 만들어냈습니다.

탐정 작업: 난이도 지도 그리기

저자들은 컴퓨터의 추론 과정을 "추격전" 게임처럼 취급하여 이 문제에 접근했습니다. 몇 가지 알려진 사실에서 시작하여 더 이상 새로운 사실을 만들 수 없을 때까지 규칙을 계속 적용하여 새로운 사실을 생성하는 게임을 상상해 보세요. 이것을 **체이스(chase)**라고 합니다. 경로 쿼리의 어려움은 "체이스"가 무한한 연결망을 만들며 영원히 계속될 수 있다는 점입니다. 연구진은 알고 싶었습니다: 우리가 게임을 조기에 중단해도 여전히 답을 알 수 있는가? 그리고 경로가 존재하는지 확인하는 데 시간이 얼마나 걸리는가?

그들은 조사를 두 가지 주요 시나리오로 나누었습니다: 데이터 복잡도(Data Complexity) (규칙 책은 작고 고정되어 있지만 도시는 거대한 경우)와 결합 복잡도(Combined Complexity) (규칙 책과 도시가 모두 거대한 경우).

단순한 규칙: 선형 규칙

먼저, 그들은 선형 규칙을 살펴보았습니다. 이 규칙들은 규칙의 본체가 단 하나의 사실인 "단순한" 규칙입니다.

• 발견: 만약 특정 데이터셋만을 보고 있다면(데이터 복잡도), 이러한 경로 질문에 답하는 것은 놀라울 정도로 쉽다는 것을 발견했습니다. 이는 휴대폰으로 간단한 미로를 탐색하는 것만큼 쉽습니다. 컴퓨터는 NL-complete 시간 내에 이를 수행할 수 있습니다. 이는 규칙 책이 없는 일반적인 지도에서 경로 질문에 답하는 속도와 같습니다!
• 함정: 만약 규칙 자체를 변경하기 시작한다면(결합 복잡도), 상황은 더 어려워집니다. 규칙이 단순하고 짧다면 여전히 관리 가능한 수준(PTime)입니다. 하지만 규칙이 임의로 길고 복렴해질 수 있다면, 난이도는 ExpTime-complete로 급증합니다. 이는 문제를 해결하는 데 필요한 시간이 눈덩이가 언덕 아래로 굴러 내려가는 것처럼 기하급급수적으로 증가하지만, 여전히 해결은 가능하다는 것을 의미합니다.

복잡한 규칙: 가드 규칙

다음으로, 그들은 가드 규칙을 다루었습니다. 이 규칙들은 더 강력하고 유연하여 더 복잡한 관계를 허용하지만, 반드시 충족되어야 하는 "가드"가 따라옵니다.

• 발견: 여기서 저자들은 영리한 트릭을 사용했습니다. 그들은 이러한 복잡한 "가드" 규칙을 더 단순한 "선형" 규칙으로 변환할 수 있다는 것을 보여주었습니다. 다만, 이 변환 과정에서 규칙의 집합이 폭발적으로 커진다는 반전이 있습니다.
• 결과: 이 폭발 현상 때문에, 가드 규칙 하에서 경로 쿼리에 답하는 것은 훨씬 더 어렵습니다. 일반적인 경우(unbounded arity), 난이도는 2ExpTime-complete로 치솟습니다. 이는 이중 지수적 상승을 의미하며, 입력값이 커짐에 따라 필요한 시간이 거의 상상할 수 없을 정도로 빠르게 증가함을 뜻합니다. 그러나 규칙의 크기를 제한한다면(bounded arity), 난이도는 이 규칙들 하에서 표준 질문(경로 질문이 아닌)을 처리하는 것과 동일한 수준인 ExpTime-complete로 떨어집니다.

"루프(Loop)"와 "증명 스킴(Proof Scheme)"

그들은 어떻게 이 모든 것을 증명했을까요? 그들은 멋진 정신적 도구들을 발명했습니다.

선형 규칙의 경우, 그들은 "체이스"가 무한한 웹을 만들더라도, "미지의 영역(익명의 체이스 부분)"으로 떠돌다가 다시 알려진 사실로 돌아오는 모든 경로는 반드시 하나의 원래 사실의 "그림자" 안에서 시작하고 끝나야 한다는 점을 깨달았습니다. 그들은 이를 **"루프(loops)"**라고 불렀습니다. 모든 유형의 사실에 대해 가능한 모든 루프를 미리 계산함으로써, 그들은 컴퓨터가 무한한 체이스를 시뮬레이션할 필요 없이 경로를 추측할 수 있게 해주는 "치트 시트(표)"를 구축할 수 있었습니다. 이것이 데이터 복잡도가 낮은 이유입니다. 컴퓨터는 치트 시트에서 루프를 찾아보기만 하면 됩니다.

CRPQ(여러 경로에 대해 동시에 질문할 수 있는 더 복잡한 경로 쿼리)의 경우, 그들은 **"증명 스킴(Proof Schemes)"**이라는 개념을 사용했습니다. 증명 스킴을 무한한 체이스의 작고 유한한 청사진이라고 상상해 보세요. 컴퓨터는 전체 무한한 도시를 구축하는 대신, 경로가 존재함을 증명하는 작고 대표적인 모델을 구축합니다. 그들은 만약 경로가 존재한다면, 그것을 증명하는 항상 "작은" 청사진이 존재한다는 것을 보여주었습니다. 이를 통해 그들은 비록 문제가 어렵더라도, 그것이 불가능한 것은 아니라는 것을 증명했습니다. 단지 많은 메모리와 시간이 필요할 뿐입니다.

그들이 밝혀내지 못한 것 (그리고 그것이 중요한 이유)

이 논문은 자신이 주장하지 않는 것에 대해서도 매우 신중합니다. 이 논문은 경로 쿼리가 모든 유형의 규칙 책에 대해 쉽다고 말하지 않습니다. 사실, 어떤 다른 유형의 규칙(예: "끈적한(sticky)" 규칙이나 재작성을 허용하는 규칙)의 경우, 문제가 결정 불가능하거나(해결 불가능) 명확한 상한선 없이 훨씬 더 어려울 수 있음을 강조합니다. 저자들은 자신들이 선형 및 가드 규칙에 대한 복잡도 퍼즐은 풀었지만, 다른 규칙 유형의 풍경은 여전히 미스터리로 남아 있다고 명시적으로 언급했습니다.

또한 그들은 자신들의 결과가 수학적으로 증명되었지만, 가장 어려운 경우(2ExpTime인 경우)의 알고리즘은 현재 실제 사용하기에는 너무 느리다는 점을 분명히 합니다. 그것들은 이론적인 지도이지, 당장 운전할 수 있는 자동차가 아닙니다. 그러나 더 단순한 선형 규칙의 경우, 사용자가 질문을 던지기도 전에 데이터를 전처리하여 빈틈을 메우는 방식으로 그들의 "루프" 방법이 빠르고 실용적인 도구로 변환될 수 있다고 제안합니다.

큰 그림

결국, 이 논문은 두 가지 주요 논리 규칙 하에서의 경로 쿼리 탐색에 대한 최초의 완전한 "난이도 지도"를 제공합니다. 이 논문이 우리에게 알려주는 것은 다음과 같습니다:

1. **단순한 규칙(선형)**은 데이터가 많은 작업에 적합합니다. 왜냐하면 복잡한 경로가 있더라도 쿼리 속도가 빠르기 때문입니다.
2. **강력한 규칙(가드)**은 유연하지만, 특히 규칙이 길어질 때 막대한 계산 비용을 수반합니다.
3. 경로 쿼리는 근본적으로 표준 질문보다 어렵지만, 우리는 이제 그것이 얼마나 더 어려운지를 정확히 알고 있습니다.

이 연구는 기초적인 단계입니다. 단순히 "어렵다"라고 말하는 것이 아니라, 그 어려움의 정밀한 수학적 경계를 제시합니다. 차세대 지식 그래프와 AI 시스템을 구축하는 컴퓨터 과학자들에게, 이것은 서버 파워가 얼마나 필요할지 추측하는 것과 정확히 얼마만큼을 사야 할지 아는 것의 차이를 만들어 줍니다. 이는 안개 낀 불확실한 여정을, 깎아지른 절벽과 매끄러운 도로가 어디에 있는지 정확히 보여주는 밝은 길로 바꾸어 놓습니다.