OWL 2 프로파일: EL, QL, RL, DL

📍 현재 위치: 2부 · 서술 논리 — 6장. EL 계열은 작은 논리 하나 — 논리곱과 존재 제한뿐인 — 가 방대한 용어 체계(terminology)를 다항 시간에 분류해내는 모습을 보여주었습니다; 이제 우리는 한 발 물러나 왜 표준이 그런 방언을 네 개나 갖추고 있는지, 그리고 그중 어떻게 골라야 하는지를 묻습니다.

웹 온톨로지 언어(Web Ontology Language, OWL; 기계가 읽을 수 있는 온톨로지를 작성하기 위한 W3C 표준)는 그 밑바탕에서 서술 논리(description logic)이며, 그것도 매우 표현력이 풍부한 서술 논리입니다. 표현력이 풍부한 논리는 추론하는 데 시간이 오래 걸리며, 때로는 파국적일 만큼 그렇습니다. 그래서 표준은 실용적인 조치를 취합니다: 완전한 언어와 나란히, 프로파일(profile)이라 불리는 세 개의 더 작은 공식 하위 언어를 정의하는데, 각각은 하나의 특정한 추론 과제가 수학적 보증과 함께 빠르게 실행되도록 의도적으로 제한된 부분집합(fragment)입니다 [1]. 이 장은 이 세 프로파일 — EL, QL, RL — 과, 이들이 그로부터 잘라져 나온 완전한 DL 언어를 다루며, 무엇보다 중요한 단 하나의 기술 — 눈앞의 작업에 맞는 프로파일을 고르는 것 — 을 다룹니다.

쉽게 말하면

세 대의 전문 기계와 한 대의 만능 일꾼을 갖춘 인쇄소를 상상해 보십시오. 한 기계는 오직 거대한 카탈로그만 인쇄하지만, 그것을 눈부시게 빠르게 해냅니다. 한 기계는 스프레드시트로부터 곧바로 메일머지 양식만을 채워 넣습니다. 한 기계는 빠른 조립 라인 위의 물건에 도장만 찍습니다. 구석에 있는 만능 일꾼은 무엇이든 인쇄할 수 있지만 — 그 일이 1분 걸릴지 1주일 걸릴지 결코 알 수 없습니다. OWL 2의 프로파일이 바로 그 세 전문가입니다: 각각은 자신의 한 가지 일이 확실히 빠르게 끝나도록 일부러 제한되어 있습니다. 완전한 OWL 2 DL이 그 만능 일꾼입니다. 여러분은 어떤 언어가 가장 강력해 보이는지가 아니라, 여러분이 빠르게 해내야 할 과제가 무엇인지에 따라 프로파일을 골라야 합니다.

이 장에서 다루는 내용

프로파일은 하나의 거래입니다 — 표현력이 풍부한 구성자들을 포기하는 대신 하나의 과제에 대한 최악의 경우 보증을 얻습니다; 취향이 아니라 과제에 따라 골라야 합니다.
EL, 용어 체계 프로파일 — 오직 논리곱과 존재 제한만 있으며; 분류가 다항 시간에 이루어집니다; SNOMED CT와 학계 세계의 논리입니다.
QL, 데이터베이스 프로파일 — DL-Lite 핵심입니다; 논리곱 질의를 SQL로 재작성하여 답하므로, 실제 작업은 데이터베이스가 수행합니다; 1차 재작성 가능하며, 거대한 데이터 위에서 이상적입니다.
RL, 규칙 프로파일 — 공리를 규칙 하나하나에 대응시켜 전방 연쇄 데이터로그 엔진 위에 얹는 부분집합으로, 4부의 규칙 추론과 곧바로 연결됩니다.
나란히 놓은 표 — 유지되는 구성자와 버려지는 구성자, 효율적인 과제, 복잡도 클래스, 그리고 전형적인 용도를 담으며, 프로파일들이 서로 겹치되 어느 것도 다른 것을 포함하지 않는다는 결정적인 사실을 함께 담습니다.
학계 세계가 자리 잡는 곳 — 그 실제 TBox는 ⊓, ∃, ⊥, 그리고 역할 사슬을 사용하므로 OWL 2 EL 안에 자리합니다; 우리는 그 공리들을 그대로 인용하며, 정확히 어떤 공리가 그것을 QL과 RL로부터 몰아낼지 짚어 냅니다.
왜 경계선이 그 자리에 그어졌는가 — 솔직한 답은 계산 복잡도이며, 다음 장이 이를 열어 보입니다.

프로파일은 하나의 거래다: 보증과 맞바꾼 표현력

잘려 나가는 대상부터 시작해 봅시다. 완전한 OWL 2(그 논리적 핵심은 서술 논리 $\mathcal{SROIQ}$ 입니다)는 구성자들을 잔뜩 쌓아 올립니다: 논리곱 ⊓, 논리합 ⊔, 부정 ¬, 전칭 ∀와 존재 ∃ 제한, 개수 제한, 역할의 역, 역할 사슬, 그리고 노미널(nominal)입니다. 바로 그 풍부함 때문에 완전한 언어에서 한 클래스가 다른 클래스를 포섭하는지를 판정하는 것은 최악의 경우 N2ExpTime-완전 [1]이며 — 이는 이중 지수적 폭발이고, 하나의 질의가 그것을 물어본 사람보다 더 오래 살아남게 만들 수도 있는 종류의 비용입니다.

프로파일이란 구문적(syntactic) 제한입니다: 어떤 구성자가 나타날 수 있는지, 그리고 그것이 어디에 나타날 수 있는지 — ⊑의 왼쪽인지, 오른쪽인지, 아니면 양쪽 다인지 — 를 규정하는 문법입니다. 그 거래는 정확합니다. 여러분은 문법이 허용하는 공리만을 쓰겠다고 약속하고; 그 대가로 표준은 하나의 추론 과제에 대한 복잡도 클래스를 약속합니다. 형식적으로, $\mathcal{L}$ 이 그 부분집합이고 $\mathrm{task}$ 가 그것이 보증하는 저렴한 작업이라면, 그 프로파일에 속한다는 것은 다음과 같은 한계를 사 줍니다

\text{axioms} \in \mathcal{L} \quad\Longrightarrow\quad \mathrm{task} \in \mathcal{C},

여기서 화살표 $\Longrightarrow$ 는 "보증한다"로 읽고, $\mathcal{C}$ 는 다루기 쉬운 복잡도 클래스(PTIME 또는 그보다 낮은 것)입니다. 세 개의 프로파일이 존재하는 이유는 보증할 만한 가치가 있는 서로 다른 세 가지 작업 — 용어 체계 분류하기, 데이터베이스 질의하기, 규칙 엔진 실행하기 — 이 있고, 어떤 단일한 부분집합도 이 셋을 한꺼번에 저렴하게 만들 수는 없기 때문입니다. 다음 세 절은 이들을 하나씩 다룹니다.

OWL 2 EL: 논리곱, 존재 제한, 다항 시간 분류

EL이라는 이름은 그 두 핵심 구성자에서 따온 것입니다: 존재 제한(existential restriction)과 논리곱(conjunction)입니다(하나의 논리(logic)로서는 $\mathcal{EL}$ 로 표기하며, 그 표준화된 확장인 $\mathcal{EL}^{++}$ 가 이 프로파일의 실질적 기반입니다). 그 개념 문법은 이렇게 읽으십시오: 하나의 개념은 원자적 이름 $A$ , 최상위 개념 ⊤("모든 것"), 최하위 개념 ⊥("아무것도 아님"), 논리곱 $C \sqcap D$ (" $C$ 이면서 동시에 $D$ "), 또는 존재 제한 $\exists r.C$ ("역할 $r$ 을 통해 어떤 $C$ 와 관계 맺는다")입니다:

C, D \;::=\; A \;\mid\; \top \;\mid\; \bot \;\mid\; C \sqcap D \;\mid\; \exists r.C .

이것이 개념에 대한 언어의 전부입니다 — ∀도, ¬도, ⊔도 없습니다. EL의 독특한 강점은 논리곱 ⊓과 한정된(qualified) 존재 제한(existential restriction) $\exists r.C$ 를 ⊑의 양쪽 모두에 자유롭게 허용한다는 데 있습니다. 오른쪽의 존재 제한 — Professor ⊑ ∃advises.Student("모든 교수는 어떤 학생을 지도한다")를 그저 가정하는 것이 아니라 결론지을 수 있다는 것 — 은 EL이 QL과 공유하는 부분입니다; QL이 따라잡지 못하는 것은 EL의 왼쪽 풍부함입니다: 한정된 존재 제한이나 논리곱이 하위개념 자리(subclass position)에 오는 것인데, QL은 오직 벌거벗은 $\exists r.\top$ 만을 허용합니다. (머리-존재 제한 그 자체는 잠시 뒤에 보겠지만 오직 RL만이 금지합니다.) 동반 모듈은 그 설계 의도를 곧바로 진술합니다(ontology.py 28–30번째 줄):

EL (the logic behind the OWL 2 EL profile) keeps exactly ⊓ and ∃, which is why
subsumption stays decidable in *polynomial* time — the pay-off the completion
algorithm in ``el_completion.py`` cashes in.

그 보증이야말로 핵심 소식입니다: EL에서는 포섭(subsumption) 여부를 판정하는 것( $A \sqsubseteq B$ , "모든 $A$ 는 반드시 $B$ 인가?")과 온톨로지 전체를 분류하는 것이 PTIME-완전입니다 — TBox 크기에 대한 다항식으로 시간이 한정되어 풀 수 있습니다 [2]. 그것을 현금화하는 메커니즘이 바로 완성(completion)(또는 포화(saturation)) 알고리즘입니다: 모든 공리를 네 가지 고정된 형태 중 하나로 정규화한 다음, 고정점에 이를 때까지 작은 완비 규칙 집합을 발동시킵니다. el_completion.py에 있는 처음부터 짠 추론기(규칙 CR1부터 CRχ까지, 25–30번째 줄)가 정확히 이것이며, 그 독스트링은 그 보상에 대해 단도직입적입니다(38–40번째 줄): 이 알고리즘은 "TBox 크기에 대해 다항 시간에 실행되는데 — 바로 이 성질 덕분에 OWL 2 EL은 수십만 개의 개념을 가진 온톨로지(SNOMED CT, Gene Ontology)에도 쓸 수 있다." SNOMED CT(Systematized Nomenclature of Medicine — Clinical Terms)는 35만 개가 넘는 개념을 가지고 있으며, EL이 용어 체계가 커져도 분류 비용이 다항식으로 유지되는 프로파일이기 때문에 OWL 2 EL 온톨로지입니다. 아래에서 확인하겠지만, 학계 세계 역시 마찬가지입니다.

OWL 2 QL: DL-Lite와 재작성을 통한 질의 응답

QL은 "질의(query)"를 가리킵니다 — 그 목적은 데이터가 대규모 관계형 데이터베이스에 담겨 있는 온톨로지 위에서 논리곱 질의(conjunctive query)(데이터베이스 방식의 "…를 만족하는 모든 $x$ 를 찾아라"라는 패턴 매칭)에 답하는 것입니다. 그 논리적 기반은 DL-Lite로, 질의가 추론기로 하여금 데이터를 아예 건드리게 만들지 않도록 공학적으로 설계된 계열입니다 [3]. QL은 ⊑의 왼쪽에서는 검소합니다 — 하위개념 자리는 오직 원자적 이름이나 한정되지 않은 존재 제한 $\exists r.\top$ ("어떤 $r$ -후속자든 적어도 하나는 가진다")만을 허용합니다 — 하지만 오른쪽에는 역할의 역( $r^-$ )과 부정을 더하며, EL이 아끼는 두 가지 — 왼쪽의 논리곱과 역할 사슬 — 를 금지합니다.

QL이 그러한 절제로 사들이는 요령이 바로 1차 재작성 가능성(first-order rewritability)입니다. 논리곱 질의 $q$ 와 QL TBox $\mathcal{T}$ 가 주어지면, 추론기는 $q$ 를 새로운 (대개 더 큰) 1차 질의 $q_{\mathcal{T}}$ — 논리곱 질의들의 합집합, 즉 평범한 SQL — 로 재작성하며, 그 결과 모든 ABox $\mathcal{A}$ 에 대해 온톨로지 위에서의 확실한 답이 평범한 데이터베이스로서 데이터 위에서 곧바로 실행되는 재작성된 질의의 답과 같아집니다:

\mathrm{cert}(q, \mathcal{T}, \mathcal{A}) \;=\; \mathrm{ans}(q_{\mathcal{T}}, \mathcal{A}).

이를 이렇게 읽으십시오: 모든 온톨로지적 추론을 질의 안으로 단 한 번 접어 넣은 다음, 추론기가 루프 안에 전혀 없는 채로 데이터베이스 엔진이 그것에 답하게 둡니다. 그 결과는 척도의 맨 밑바닥에 있는 복잡도 결과입니다. 데이터 복잡도(data complexity)(질의와 TBox를 고정한 채 ABox 크기의 함수로 잰 비용)로 측정하면, QL에서의 논리곱 질의 응답은 $\mathrm{AC}^0$ 안에 있습니다 [3] — 이는 고정된 1차 질의가 이미 속해 있는 클래스이며, LOGSPACE보다 아래이고 PTIME보다 훨씬 아래입니다. 이것이 바로 SQL 문장을 평가하는 것과 정확히 같은 복잡도이며, 그래서 QL이 온톨로지 기반 데이터 접근(ontology-based data access)을 위해 선택되는 프로파일인 이유입니다: 십억 행짜리 데이터베이스 위에 가벼운 온톨로지를 얹어도 모든 질의는 여전히 데이터베이스 속도로 실행됩니다.

OWL 2 RL: 규칙 친화적 부분집합

RL은 "규칙(rule)"을 가리킵니다. 그 공리들이 하나하나 그대로 데이터로그(Datalog) 규칙 — 전방 연쇄 엔진이 발동시킬 수 있는 혼 절(Horn clause) — 로 번역되는 부분집합이며, 그래서 RL 온톨로지는 서술 논리 추론기가 전혀 필요 없이, 정확히 4부의 즉시 귀결 루프(immediate-consequence loop)로 추론됩니다. 그 제한들은 바로 그 목표를 그대로 비춥니다. RL은 ⊑의 왼쪽(규칙의 몸체)에서는 너그럽습니다: 논리곱을 허용하고, 역할의 후속자를 묶는 존재 제한도 허용합니다. 심지어 오른쪽에는 전칭 ∀도 허용합니다(유효한 규칙입니다: $C$ 로부터 $r$ 을 통해 도달되는 모든 것은 $D$ 입니다). 하지만 번역을 깨뜨릴 단 한 가지에는 엄격합니다: RL은 상위개념 자리(superclass position) — 규칙의 머리 — 에 오는 존재 제한 $\exists r.C$ 를 금지합니다.

그 이유는 고정점 장이 체이스(chase)로 만났던 것과 같습니다: 머리에 있는 Professor ⊑ ∃advises.Student 같은 공리는 모든 교수가 지도 학생을 가질 것을 요구하는데, 기록에 아무도 없다면 규칙 엔진은 새로운 익명의 개체를 발명해야 할 것입니다 — 이는 데이터로그 위의 전방 연쇄가 할 수 없는 일입니다. 머리-존재 제한을 금지하면 모든 공리는 몸체가 기존 사실을 읽고 머리가 기존 개체에 대한 사실을 주장하는 안전한 규칙이 됩니다. 그러면 RL 추론은 그저 데이터로그 평가일 뿐입니다: 데이터 복잡도에서 PTIME-완전이며, 어떤 전방 연쇄 규칙/데이터로그 엔진(RDFox 같은 산업용 엔진)에서도 구현 가능하고, 여러분이 이미 알고 있는 바로 그 최소 고정점 오르기(least-fixpoint climb)에 의해 수십억 개의 엣지를 가진 그래프로도 확장됩니다.

세 프로파일을 나란히 놓고 보면

여기 그 거래 전체가 한눈에 있습니다. 각 행은 하나의 프로파일이며; 열은 그것이 유지하는 구성자, 버리는 구성자, 그것이 저렴하게 만드는 과제, 그 결과로 나오는 복잡도, 그리고 그것이 제 몫을 하는 곳입니다.

프로파일	논리	유지	버림	효율적인 과제	복잡도	전형적인 용도
EL	$\mathcal{EL}^{++}$	양쪽 모두의 ⊓, ∃, ⊥, 역할 사슬, ABox	∀, ¬, ⊔, 역할의 역, 개수 제한	분류 / 포섭	PTIME-완전	대규모 용어 체계 (SNOMED CT, Gene Ontology)
QL	DL-Lite	왼쪽의 ∃r.⊤, 오른쪽의 ∃r.C와 ¬, 역할의 역	왼쪽의 ⊓, 역할 사슬, 왼쪽의 한정된 ∃	논리곱 질의 응답	$\mathrm{AC}^0$ (데이터), 1차 재작성 가능	거대한 데이터베이스 질의
RL	DLP / pD*	몸체의 ⊓과 ∃, 머리의 ∀, ⊥, 역할 사슬	머리(상위개념 자리)의 ∃	규칙 / 데이터로그 추론	PTIME-완전 (데이터)	인스턴스 데이터에 대한 확장 가능한 규칙 추론
DL	$\mathcal{SROIQ}$	(거의) 모든 것	— 완전한 언어	— 다루기 쉬움 보증 없음	N2ExpTime-완전	최대의 표현력

이 표에서 가장 중요한 사실은 놓치기 쉽습니다: 세 개의 다루기 쉬운 프로파일은 서로 겹치지만, 어느 것도 다른 것을 포함하지 않습니다 [1]. 역할 사슬은 EL과 RL에는 있지만 QL에는 없습니다. 역할의 역은 QL과 RL에는 있지만 EL에는 없습니다. 머리에 오는 존재 제한은 EL과 QL에는 있지만 RL에는 없습니다 — 오직 RL만이 그것을 금지합니다. 그러므로 언제나 기본값으로 삼을 수 있는 "가장 큰" 다루기 쉬운 프로파일이란 없습니다; 각각은 완전한 언어의 진정으로 서로 다른 한 귀퉁이이며, 어떤 온톨로지는 그중 하나에, 둘에, 셋 모두에, 혹은 어디에도 속하지 않을 수 있습니다. 바로 이런 의미에서 여러분은 과제에 따라 골라야 합니다: 프로파일들은 힘의 사다리가 아니라 저마다 다른 날을 지닌 세 개의 도구입니다.

학계 세계가 자리 잡는 곳

이제 우리가 계속 다루어 온 예제를 자리매김해 봅시다. 온톨로지는 스스로 자신의 형태를 보고합니다(ontology.py, summary, 216–220번째 줄):

10 named concepts, 6 roles, 14 TBox axioms; ABox: 13 concept assertions, 18 role assertions over 13 individuals.

TBox를 출력해 보면(ontology.py, 125–174번째 줄의 공리들) 그것이 정확히 어떤 구성자에 기대고 있는지가 드러납니다:

Professor ⊑ Researcher
Student ⊑ Researcher
Researcher ⊑ Person
Professor ⊑ ∃advises.Student
∃advises.⊤ ⊑ Researcher
Professor ⊓ Student ⊑ ⊥
advises ∘ advises ⊑ grandAdvisor
Dean ⊑ Professor
Dean ⊑ ∃advises.Professor
TenuredStudent ⊑ Professor
TenuredStudent ⊑ Student
TenuredStudentAdvisor ⊑ ∃advises.TenuredStudent
∃advises.∃authored.Paper ⊑ Person
Person ⊓ ∃authored.Paper ⊑ Researcher

구성자들을 눈으로 쭉 훑어보십시오: 하위개념 사슬( $A \sqsubseteq B$ ), 논리곱(Professor ⊓ Student, Person ⊓ ∃authored.Paper), 오른쪽(Professor ⊑ ∃advises.Student)과 왼쪽(∃advises.⊤ ⊑ Researcher, ∃advises.∃authored.Paper ⊑ Person) 양쪽 모두에 있는 존재 제한, 서로소를 위한 바닥 개념 ⊥, 하나의 역할 사슬(advises ∘ advises ⊑ grandAdvisor), 그리고 개념 단언과 역할 단언으로 이루어진 ABox입니다. 이들 하나하나가 모두 $\mathcal{EL}^{++}$ 의 구성자이며, 여기에는 그 밖의 어떤 것도 없습니다 — ∀도, ¬도, ⊔도, 역할의 역도 없습니다. 학계 세계는 OWL 2 EL 온톨로지입니다. 바로 그래서 el_completion.py의 다항 시간 완성 추론기가 그것을 곧바로 판정하며, 세 라운드 만에 고정점까지 포화시켜 분류를 읽어냅니다:

saturation reached a fixpoint in 3 rounds
  round : |S| |R|  (derived subsumers, derived role pairs)
      0 :  23   0
      1 :  34   7
      2 :  39   7
      3 :  39   7

역할 사슬은 한가한 장식이 아닙니다: 도출된 일곱 개의 역할 쌍 가운데, 완성 과정은 grandAdvisor: [('Dean', 'Student'), ('TenuredStudentAdvisor', 'Student')]를 출력하는데 — 이는 오직 advises ∘ advises ⊑ grandAdvisor를 발동시켜야만 만들어지는 쌍들입니다. 그 단 하나의 공리가 역할 사슬이 아예 없는 QL로 향하는 가장 날카로운 단층선입니다. 이제 교훈적인 부분입니다: 어떤 공리들이 이 온톨로지를 나머지 두 다루기 쉬운 프로파일에서 몰아낼까요?

QL에서는 세 가지 이유로 벗어날 것입니다. 역할 사슬 advises ∘ advises ⊑ grandAdvisor(147번째 줄)는 DL-Lite 바깥에 완전히 벗어나 있습니다 — QL에는 역할 사슬이 전혀 없습니다. 왼쪽 논리곱인 Professor ⊓ Student ⊑ ⊥(143번째 줄)와 Person ⊓ ∃authored.Paper ⊑ Researcher(173번째 줄)는 하위개념 자리에 ⊓을 놓는데, QL은 질의가 1차 재작성 가능한 채로 남도록 이를 금지합니다. (이는 구문상의 문제일 뿐, 표현력을 잃는 것은 아닙니다: QL은 여전히 그 분리성 자체를 Professor ⊑ ¬Student로 진술할 수 있는데, 부정이 QL에서 합법적인 상위개념이기 때문입니다 — QL이 거부하는 것은 오직 이 특정한 왼쪽-⊓ 형태일 뿐입니다.) 그리고 한정된 왼쪽 존재 제한 ∃advises.∃authored.Paper ⊑ Person(168번째 줄) 역시 QL을 깨뜨립니다 — 하위개념 자리는 한정된 채움이 아니라 벌거벗은 $\exists r.\top$ 를 원하기 때문입니다.
RL에서는 머리-존재 제한 때문에 벗어날 것입니다. Professor ⊑ ∃advises.Student(133번째 줄), Dean ⊑ ∃advises.Professor(152번째 줄), TenuredStudentAdvisor ⊑ ∃advises.TenuredStudent(163번째 줄)는 각각 상위개념 자리에서 존재를 주장하는데, 데이터로그 규칙은 요구되는 지도 학생을 발명할 수 없습니다. 이와 대조적으로 역할 사슬은 RL에서 전혀 문제가 없습니다 — RL은 속성 사슬(property chain)을 그대로 유지하기 때문입니다 — 그러므로 이를 가로막는 것은 오직 머리에 있는 존재 제한뿐입니다.

분리성 공리는 "겹치지만 포함하지는 않는다"는 그림을 가장 깔끔하게 보여주는 예입니다: Professor ⊓ Student ⊑ ⊥는 EL에 자연스럽게 속하고 RL에서도 표현 가능하지만, 그 왼쪽-논리곱 형태는 QL에서는 불법입니다(QL은 같은 분리성을 Professor ⊑ ¬Student로 고쳐 써야 할 것입니다). 아주 짧게 쓰인 공리 하나가 두 프로파일에서는 합법이고 나머지 하나에서는 그렇지 않은 것입니다.

완전한 OWL 2 DL 언어와, 겹치는 영역들로 표현된 세 개의 다루기 쉬운 프로파일이며, 각각은 그것이 효율적으로 만드는 단 하나의 과제로 태그되어 있고, 학계 세계는 EL 안에 고정되어 있으며 그것을 QL과 RL 밖으로 밀어낼 정확한 공리들과 함께 표시되어 있습니다. 저자가 AI의 도움을 받아 직접 제작한 원본 도해.

아직 풀리지 않은 부분

프로파일들은 하나의 언어를 가로질러 임의로 그어진 세 개의 선처럼 보입니다 — 여기서는 ⊓은 남기되 ∀은 버리고, 저기서는 ∃을 왼쪽에는 허용하되 오른쪽에는 허용하지 않습니다. 왜 하필 이 선들일까요? 이 장이 온전히 내놓을 수 없는 솔직한 답은, 그 경계선이 우아함을 위해 골라진 것이 아니라 하나의 추론 과제가 다루기 쉬움에서 다루기 어려움으로 넘어가는 바로 그 정확한 전선(frontier)이라는 것입니다. 금지된 구성자를 단 하나만 도로 더해도 분류는 PTIME에서 ExpTime으로 옮겨갈 수 있고, 질의 응답은 $\mathrm{AC}^0$ 밖으로 밀려나 더 이상 어떤 SQL 재작성도 존재하지 않게 되어 데이터베이스 엔진이 더는 여러분 대신 답할 수 없게 될 수도 있습니다. 열려 있는, 더 깊은 질문은 왜 구성자 하나가 그토록 큰 비용을 치르게 만드는가 — 왜 그 절벽들이 정확히 프로파일 문법이 울타리를 친 바로 그 자리에 있는가입니다. 이것은 전혀 구문에 관한 질문이 아니라 계산 복잡도에 관한 질문이며, 그것이 바로 다음 장의 주제입니다.

왜 중요한가

신경-기호(neuro-symbolic) AI에게 프로파일은, 신경 쪽이 눈에 띄게 결여하고 있는 공학적 보증에 대한 하나의 교훈입니다. 학습된 모델은 비용도 정확성도 명시되지 않은 답을 내놓지만, OWL 2 EL 온톨로지는 하나의 약속 — 다항 시간에 이루어지는, 건전하고 완전한 분류 — 을 내놓으며, 이는 용어 체계가 아무리 커져도 유지됩니다. 이후의 권들이 학습기를 추론기 위에 얹을 때, 그 계약에서 추론기가 맡은 절반을 고정해 주는 것이 바로 프로파일입니다: EL을 고르면 학습되거나 확장된 온톨로지를 대규모로 분류할 수 있고; QL을 고르면 학습된 단언들에 대한 질의에 데이터베이스 속도로 답할 수 있으며; RL을 고르면 여러분의 상징적 층은 말 그대로 미분 가능성에 친화적인 규칙 엔진이 됩니다. 어떤 과제에 어떤 프로파일이 필요한지를 아는 것은, 신경 쪽 부분을 더할 때 어떤 보증을 계속 지킬 수 있는지를 아는 것이며 — 그리고 그것을 지키고 싶다면 어떤 구성자들이 다시 슬며시 기어들어오게 두어서는 안 되는지를 아는 것입니다.

핵심 용어

프로파일(Profile) — 하나의 추론 과제가 다루기 쉬운 최악의 경우 보증을 갖도록 제한된, OWL 2의 공식적인 구문적 부분집합(EL, QL, 또는 RL).
OWL 2 EL — 논리곱 ⊓과 존재 제한 ∃의 부분집합(논리 $\mathcal{EL}^{++}$ )입니다; 분류는 PTIME-완전입니다; SNOMED CT와 학계 세계의 프로파일입니다.
OWL 2 QL — DL-Lite 부분집합입니다; 논리곱 질의 응답이 1차 재작성 가능하므로, 질의는 원본 데이터에 대한 SQL로 환원되며, 데이터 복잡도는 $\mathrm{AC}^0$ 입니다.
OWL 2 RL — 규칙 부분집합입니다; 공리가 전방 연쇄로 실행되는 데이터로그 규칙에 대응되며, 데이터 복잡도에서 PTIME-완전입니다; 머리에 오는 존재 제한을 금지합니다.
OWL 2 DL — 완전한 언어입니다(논리 $\mathcal{SROIQ}$ ); 최대로 표현력이 풍부하지만 N2ExpTime-완전이며, 다루기 쉬움 보증이 없습니다.
1차 재작성 가능성(First-order rewritability) — 질의와 TBox를 합쳐 ABox 위에서 직접 답해지는 평범한 1차/SQL 질의로 재작성할 수 있다는 (QL의) 속성으로, $\mathrm{cert}(q,\mathcal{T},\mathcal{A}) = \mathrm{ans}(q_{\mathcal{T}},\mathcal{A})$ 입니다.
데이터 복잡도(Data complexity) — 질의와 TBox를 고정한 채 ABox가 커짐에 따라 잰 비용입니다; QL( $\mathrm{AC}^0$ )을 RL 및 EL(PTIME)로부터 갈라 놓는 잣대입니다.
겹치지만 포함하지 않음(Overlap but no containment) — 세 개의 다루기 쉬운 프로파일은 쌍마다 구성자를 공유하지만, 어느 것도 다른 것의 초집합이 아니므로, 단 하나의 가장 강력한 프로파일을 고를 수는 없습니다.

이 장이 이끄는 곳

이 장에 나온 모든 주장 — 여기서는 다항식, 저기서는 $\mathrm{AC}^0$ , 완전한 언어에 대해서는 이중 지수 — 은 사실로서 인용되었을 뿐 설명되지 않은 채로 남겨졌습니다. 다음 장인 추론의 복잡도는 그 복잡도 클래스들을 정밀하게 다듬고, 프로파일의 경계선이 왜 정확히 그 자리에 떨어지는지를 보여줍니다: 포섭이 PTIME-완전이라는 것이 무엇을 뜻하는지, 왜 구성자 하나를 추가하는 것이 지수적 폭발을 일으킬 수 있는지, 그리고 학계 세계를 세 라운드 만에 분류해 낸 바로 그 완성 루프가 어째서 EL이 그 다항식적 약속을 얻어 내는 구체적인 이유인지를 말입니다. 프로파일은 무엇인지를 말해 주고; 복잡도는 왜 그런지를 말해 줍니다.

이 장에서 다루는 내용​

프로파일은 하나의 거래다: 보증과 맞바꾼 표현력​

OWL 2 EL: 논리곱, 존재 제한, 다항 시간 분류​

OWL 2 QL: DL-Lite와 재작성을 통한 질의 응답​

OWL 2 RL: 규칙 친화적 부분집합​

세 프로파일을 나란히 놓고 보면​

학계 세계가 자리 잡는 곳​

아직 풀리지 않은 부분​

왜 중요한가​

핵심 용어​

이 장이 이끄는 곳​