확실한 답: 준동형사상으로서의 질의 응답

📍 현재 위치: 4부 · 데이터로그와 체이스 — 14장. 존재 규칙과 체이스는 규칙을 발동시키고, 머리가 기록에 없는 증인을 요구할 때마다 새로운 널을 발행하여 하나의 모델을 구축했습니다. 이제 우리는 그 모델이 무엇을 위한 것인지 — 그로부터 신뢰할 수 있는 답을 어떻게 읽어낼지, 그리고 그 읽기가 어째서 체이스가 그 모델을 구축하는 데 사용한 것과 정확히 같은 연산인지를 묻습니다.

여러분에게는 명백히 불완전한 데이터베이스가 있습니다: 몇몇 교수가 몇몇 학생을 지도한다는 것은 알지만, 모든 지도 관계를 빠짐없이 기록했다고 주장한 적은 없습니다. 누군가 "누가 학생을 지도하는가?"라고 묻습니다. 정직한 답은 "내 테이블이 우연히 나열해 놓은 사람"이 아닙니다. 그것은 "내 데이터가 허용하는 모든 세계 상태에서 반드시 학생을 지도해야 하는 모든 사람"입니다. 이 장은 그 발상을 정확하게 다듬고, 단 하나의 연산 — 준동형사상(homomorphism) — 이 그것을 계산해 낸다는 것을 보이며, 학계 세계 위에서 그것을 실행하여 alice와 bob이라는 답을 얻습니다.

쉽게 말하면

부분적인 사건 파일을 든 형사를 상상해 보십시오. 파일에는 도주 차량 운전자가 누구인지는 적혀 있지 않고, 다만 운전자가 있었다는 것만 적혀 있습니다. 부주의한 조수라면 아무도 이름이 나와 있지 않으니 "운전자는 없다"고 답할지도 모릅니다. 무모한 조수라면 아무 이름이나 추측할지도 모릅니다. 형사는 어느 쪽도 하지 않습니다. 그녀는 파일과 부합하는 모든 이야기에서 참인 것만을 보고합니다: 운전자는 존재하지만, 그 운전자로 확실하게 지목할 수 있는 특정 인물은 없습니다. "alice가 지도하는 학생이 존재한다"는 것은 어떤 학생인지가 확실하지 않더라도 확실할 수 있습니다. 확실한 답(certain answers)이란 정확히, 세계에 대한 모든 부합하는 재서술에서 살아남는 사실들입니다.

이 장에서 다루는 내용

확실한 답, 해독하기 — 열린 세계 가정(open-world assumption) 아래에서 의미 있는 답은 "내 데이터에 무엇이 있는가"가 아니라 "내 데이터와 부합하는 모든 세계에서 무엇이 성립하는가"이며, 자리표 널로 이루어진 튜플이 결코 확실할 수 없는 이유.
유일한 원시 연산으로서의 준동형사상 — 질의의 모든 원자를 인스턴스 위에 착지시키는 변수 배정; 이 하나의 검사가 곧 논리곱 질의 평가이자 곧 체이스의 충족 검사입니다.
보편 모델 — 체이스 결과는 준동형사상으로 모든 모델에 사상되므로, 그 위에서 질의를 평가한 다음 널을 제거하면 정확히 확실한 답이 나옵니다.
상수 전용 필터 — certain_answers는 모든 구성 요소가 상수일 때만 튜플을 남기며; query_holds는 단 하나의 준동형사상으로 예/아니오 질의에 답합니다.
커밋된 실행 결과 — 제한된 체이스 위에서 Q(x) :- advises(x, y), Student(y)는 널로 증언된 지도 학생을 제외하고, 둘 다 교수인 alice와 bob을 반환합니다.
데이터로그 대 체이스 — 데이터로그의 답은 이미 모두 상수이므로 필터가 필요 없으며; 존재 규칙은 널을 추가하는데, 바로 그 때문에 확실성에는 필터가 필요합니다.

확실한 답, 해독하기

관계형 데이터베이스는 문자 그대로 읽으면 닫힌 세계 가정(closed-world assumption) 아래에서 답합니다: 진술되지 않은 것은 무엇이든 거짓으로 간주됩니다. 온톨로지는 그 반대입니다. 온톨로지는 열린 세계 가정(open-world assumption) 아래에서 살아갑니다 — 진술되지 않은 것은 거짓이 아니라 알 수 없는 것입니다 — 왜냐하면 지식 베이스는 의도적으로 더 풍부한 현실에 대한 부분적인 기술이기 때문입니다. 일단 그것을 받아들이면, 질의는 답해야 할 세계가 하나가 아니라 여러 개가 됩니다: 지식 베이스 $\mathcal{K}$ 를 만족시키는 모든 모델(model), 즉 모든 완전한 사태 $\mathcal{M}$ 이 후보 현실이 됩니다.

그 모든 세계에 걸쳐 어떤 답을 신뢰할 수 있을까요? 논리곱 질의(conjunctive query) $Q(\bar{x}) \leftarrow \exists \bar{y}\, \varphi(\bar{x}, \bar{y})$ — ∧로 결합된 원자들의 집합 $\varphi$ 이며, 그중 일부 변수 $\bar{x}$ 는 답으로 보고되고 나머지 $\bar{y}$ 는 존재적으로 숨겨집니다 — 는 각 모델에서 답 튜플의 집합 $Q(\mathcal{M})$ 을 가집니다. 확실한 답(certain answers)이란 모든 모델에서 동시에 나타나는 튜플입니다 [1]:

\mathsf{cert}(Q, \mathcal{K}) \;=\; \bigcap_{\mathcal{M}\, \models\, \mathcal{K}} Q(\mathcal{M}).

큰 ∩는 모든 모델에 대한 교집합입니다 — 어떤 튜플이 인정받으려면 예외 없이 모델마다 계속해서 답이어야 합니다. turnstile 기호 $\models$ 는 "~의 모델이다 / ~을 만족한다"로 읽습니다. 바로 이 때문에 널(null) — 레이블 붙은 널(labeled null), _n1과 같이 "이름 붙일 수 없는 어떤 개체"를 나타내는 자리표 기호이며, 명확히 상수가 아닌 것(chase.py에서 is_null("_n1")은 참이고 is_const("_n1")은 거짓입니다; 상수와 널은 서로소입니다) — 을 포함하는 튜플은 결코 확실할 수 없습니다. 널은 정확히, 모델들이 자유롭게 서로 다르게 합의할 수 있는 값입니다: 어떤 모델에서는 _n1이 carol이고, 다른 모델에서는 완전히 새로운 사람입니다. _n1을 이름으로 지닌 튜플은 그러한 불일치 속에서 안정적이지 않으므로 교집합에 들어갈 수 없습니다. 오직 진짜 상수로만 이루어진 튜플만이 교집합에 들어갈 수 있습니다.

준동형사상: 유일한 원시 연산

이 장의 핵심적인 경제성은 여기에 있습니다. 서로 다르게 들리는 두 연산 — 질의를 평가하는 것과 규칙의 머리가 이미 충족되었는지 검사하는 것 — 은 사실 같은 연산이며, 그것에는 이름이 있습니다: 준동형사상(homomorphism)입니다. 패턴(pattern)(?-변수를 지닌 원자들의 목록)과 인스턴스(instance)(접지된 원자들의 집합)가 주어졌을 때, 준동형사상이란 패턴의 모든 원자를 인스턴스의 실제 원자 위에 착지시키는, 패턴 변수에서 인스턴스 항으로의 배정입니다. chase.py에서 이것은 하나의 재귀 제너레이터 homomorphisms입니다(57–81번째 줄):

def homomorphisms(pattern, instance, sub=None):
    """Yield every substitution of the ``?``-variables in ``pattern`` (a list of
    atoms) that maps all of them into ``instance``. This *is* conjunctive-query
    evaluation, and the check the restricted chase uses to test satisfaction."""
    sub = {} if sub is None else sub
    if not pattern:
        yield dict(sub)
        return
    first, rest = pattern[0], pattern[1:]
    for fact in instance:
        if fact[0] != first[0] or len(fact) != len(first):
            continue
        ext = dict(sub)
        ok = True
        for p, f in zip(first[1:], fact[1:]):
            if is_var(p):
                if p in ext and ext[p] != f:
                    ok = False
                    break
                ext[p] = f
            elif p != f:
                ok = False
                break
        if ok:
            yield from homomorphisms(rest, instance, ext)

이것을 실행 가능한 형태로 옮긴 정의라고 읽으십시오. 첫 번째 패턴 원자와 매칭시키려면, 같은 술어와 자릿수를 지닌 fact를 인스턴스에서 찾습니다(fact[0] != first[0] or len(fact) != len(first)); 각 변수 위치 p를 그 사실의 항 f에 묶되, 이미 이루어진 바인딩과 모순되는 바인딩은 거부합니다(if p in ext and ext[p] != f); 패턴 전체가 소진되면(if not pattern), 완성된 대입을 yield합니다. 산출되는 모든 sub가 바로 하나의 준동형사상입니다. 이 독스트링(docstring)은 이 장 전체가 근거하는 핵심 논점을 명시합니다: 이것이 곧 논리곱 질의 평가라는 것입니다 [2]. 형식적으로, 인스턴스 $I$ 위에서 $Q$ 의 답은 다음과 같습니다.

Q(I) \;=\; \{\, h(\bar{x}) \;:\; h \text{ a homomorphism from } \varphi \text{ into } I \,\}.

질의 대신 규칙의 머리를 겨냥한 바로 그 동일한 제너레이터가 _head_satisfied(95–102번째 줄)에서 제한된 체이스의 충족 검사가 됩니다: "이 머리가 이미 참인가?"는 그저 "머리가 인스턴스로의 준동형사상을 가지는가?"일 뿐입니다. 하나의 원시 연산, 두 가지 역할 — 이것이 바로 모델을 구축하는 일과 그것을 질의하는 일이 같은 종류의 작업 비용을 치르는 이유입니다.

보편 모델, 그리고 체이스가 보편 모델인 이유

하나의 모델 위에서 평가하는 것은 쉽습니다; 그 모든 모델 위에서 평가하는 것은 무한히 많은 모델이 있으므로 불가능해 보입니다. 탈출구는 그 전체 무리를 대신할 수 있는, 단 하나의 특별한 모델입니다. 인스턴스 $\mathrm{U}$ 가 $\mathcal{K}$ 를 만족시키고, $\mathcal{K}$ 의 모든 모델 $\mathcal{M}$ 에 대해 모든 상수를 고정하는 $\mathrm{U}$ 에서 $\mathcal{M}$ 으로의 준동형사상이 존재할 때, $\mathrm{U}$ 는 $\mathcal{K}$ 의 보편 모델(universal model)입니다:

h : \mathrm{U} \to \mathcal{M}, \qquad h(c) = c \text{ for each constant } c, \qquad \alpha \in \mathrm{U} \;\Rightarrow\; h(\alpha) \in \mathcal{M}.

$\mathrm{U}$ 의 널들은 여유분(slack)입니다: 준동형사상은 각 널을 그 특정 모델이 필요로 하는 어디로든 자유롭게 보낼 수 있습니다. 보편 모델은 데이터가 강제하는 "가장 일반적인" 세계입니다 — 지식 베이스가 함의하는 모든 것에는 전념하되, 그 이상은 아무것도 전념하지 않습니다. 데이터 교환(data exchange) 이론의 핵심 정리는, 체이스가 정확히 그러한 모델을 산출하며, 확실한 답은 그로부터 널을 제거함으로써 곧바로 읽어낼 수 있다는 것입니다 [1]:

\mathsf{cert}(Q, \mathcal{K}) \;=\; Q\big(\mathrm{chase}(\mathcal{K})\big)\big\downarrow_{\text{const}},

여기서 $\downarrow_{\text{const}}$ 는 상수로만 이루어진 튜플만을 남깁니다. 증명의 발상은 짧고 기억해 둘 가치가 있습니다: $\mathrm{U}$ 위에서 어떤 답을 증언하는 준동형사상은 $h$ 를 통해 모든 모델 $\mathcal{M}$ 으로 밀어붙일 수 있으므로, $\mathrm{U}$ 위에서의 상수 답은 어디에서나 답입니다; 그리고 반대로 $\mathrm{U}$ 자신도 하나의 모델이므로, 확실한 것 중 어느 것도 그로부터 빠질 수 없습니다. 무한 교집합이 하나의 인스턴스 위에서의 단 한 번의 평가로 붕괴합니다.

확실한 답 계산하기: 상수 전용 필터

이 정리는 열 줄의 코드가 됩니다. certain_answers(160–170번째 줄)는 체이스된 인스턴스 위에서 질의를 평가하고 정확히 $\downarrow_{\text{const}}$ 단계를 적용합니다:

def certain_answers(query_body, answer_vars, chased_instance):
    """The certain answers to a conjunctive query: evaluate it over the chase
    (a universal model) by homomorphism, then keep only tuples all of whose
    components are *constants* — a null could stand for many different values, so
    a tuple containing one is not certain."""
    answers = set()
    for h in homomorphisms(query_body, chased_instance):
        tup = tuple(h[v] for v in answer_vars)
        if all(is_const(t) for t in tup):
            answers.add(tup)
    return answers

for h in homomorphisms(...) 루프가 질의 평가이고; if all(is_const(t) for t in tup)이 답을 단지 존재하는 것이 아니라 확실한 것으로 만드는 필터입니다. 예/아니오 질문에는 투영할 것도 필터링할 것도 없습니다 — 불리언 논리곱 질의(boolean conjunctive query)는 정확히 하나의 준동형사상이 존재할 때 확실히 참입니다 — 이를 query_holds(173–178번째 줄)가 세 줄로 진술합니다:

def query_holds(query_body, chased_instance) -> bool:
    """A boolean conjunctive query is *certainly* true iff it has a homomorphism
    into the chase."""
    for _ in homomorphisms(query_body, chased_instance):
        return True
    return False

이 필터가 제 몫을 하는 것을 보려면, 그것이 작동하는 인스턴스를 살펴보십시오. 시작 ABox에는 원자 네 개가 있습니다; bob은 이미 학생 carol을 지도하고 있지만, alice는 아직 아무도 지도하지 않으므로, 제한된 체이스는 증인이 진정으로 결여된 곳에서만 하나를 발행합니다. 그 결과는 원자 열 개 — 발동 세 번, 널 세 개 — 이며, 커밋된 실행이 이를 보고하고, 다음과 같이 분해됩니다:

출처	산출된 원자	이유
주어진 ABox	Professor(alice), Professor(bob), Student(carol), advises(bob, carol)	네 개의 단언된 사실
alice에 대해 TGD 1 발동	advises(alice, `_n1`), Student(`_n1`)	alice는 아무도 지도하지 않으므로 새로운 널 증인이 발행됨
bob에 대한 TGD 1	— (건너뜀)	bob은 이미 진짜 학생 carol을 지도하고 있음 — 머리가 이미 충족됨
carol에 대해 TGD 2 발동	affiliated(carol, `_nᵢ`), Institution(`_nᵢ`)	진짜 학생에게는 소속 기관이 필요함
`_n1`에 대해 TGD 2 발동	affiliated(`_n1`, `_nⱼ`), Institution(`_nⱼ`)	발명된 학생도 학생이므로 마찬가지로 소속 기관이 필요함

첨자에 관한 한 가지 미묘한 점: alice의 지도 학생인 _n1은 언제나 가장 먼저 발행됩니다 — TGD 1이 TGD 2보다 먼저 발동하기 때문입니다 — 그래서 그 색인은 고정되어 있습니다. 두 기관 증인은 남은 첨자인 _n2와 _n3을 차지하지만, carol의 증인과 _n1의 증인 중 어느 쪽이 어느 색인을 받는지는 파이썬의 set이 우연히 순회하는 순서에 달려 있으므로, _nᵢ와 _nⱼ는 서로 다른 실행 사이에서 뒤바뀔 수 있습니다. 그러나 핵심을 떠받치는 사실들은 결코 변하지 않습니다: 원자 열 개, 발동 세 번, 널 세 개, 그리고 아래의 확실한 답입니다.

이 튜플 생성 종속성(tuple-generating dependency, TGD) 집합 위에서 체이스는, 발명된 어떤 널도 자기 자신에게 다시 규칙을 촉발시키도록 되돌아가지 않으므로 멈추며, 실행 결과는 그 개수를 확인해 줍니다:

Terminating TGD set on a 4-atom instance
  restricted chase: terminated=True, 3 firings, 3 nulls, |result|=10
  oblivious  chase: terminated=True, 5 firings, 5 nulls, |result|=14

커밋된 실행: 누가 학생을 지도하는가?

이제 질의를 살펴봅니다. Q_ADVISES_STUDENT는 ([("advises", "?x", "?y"), ("Student", "?y")], ["?x"])입니다 — "누가 어떤 학생을 지도하는가?"이며, 지도자 ?x를 보고하고 지도 학생 ?y는 숨깁니다. 열 개 원자로 이루어진 체이스 위에서 평가하면, homomorphisms는 정확히 두 개의 매칭을 찾아내며, 둘 다 상수로 투영됩니다:

준동형사상 $h$	착지하는 원자	답 $h(?x)$	판정
?x ↦ bob, ?y ↦ carol	advises(bob, carol) ∧ Student(carol)	bob	상수 → 유지됨
?x ↦ alice, ?y ↦ `_n1`	advises(alice, `_n1`) ∧ Student(`_n1`)	alice	상수 → 유지됨

둘 다 필터를 통과하므로, 확실한 답은 alice와 bob입니다 — 정확히 커밋된 실행이 출력하는 그대로입니다:

Certain answers to  Q(x) :- advises(x,y), Student(y)
  ['alice', 'bob']   (both professors — the TGD guarantees each advises some student)
  boolean 'does anyone advise a student?' -> True

여기에는 미묘한 점이 두 가지 있습니다. 첫째, alice는 그녀의 지도 학생으로 이름 붙은 학생이 전혀 기록되어 있지 않음에도 확실한 답입니다. "모든 교수는 어떤 학생을 지도한다"는 TGD는 모든 모델에서 그러한 학생의 존재를 강제하며, 체이스는 그 강제된 존재를 널 _n1로 기록합니다. 보고되는 변수가 지도자 ?x이고 그 값 alice가 진짜 상수이기 때문에, 답은 확실합니다 — 불확실성은 숨겨진 ?y 안에 격리되어 있습니다. 둘째, 바로 이 지점이 널이 탈락했을 자리입니다. 대신 지도 학생을 물어보십시오 — ?y에 투영하면 — alice의 행은 널인 _n1을 산출합니다; 필터는 그것을 폐기하여 carol만 남깁니다. alice의 지도 학생이 존재한다는 것은 확실하지만, 그 정체는 확실하지 않습니다. 같은 체이스, 같은 준동형사상이지만, 널이 어느 열에 놓이는지에 따라 정반대의 판정이 전적으로 결정됩니다.

데이터로그 대 체이스: 필터가 새로운 이유

데이터로그(Datalog)를 다룬 이전 장들이 왜 상수 전용 필터를 전혀 필요로 하지 않았는지 물어볼 가치가 있습니다. 그 이유는 구조적입니다: 데이터로그 규칙은 이미 존재하는 상수들을 재조합할 수 있을 뿐입니다 — 어떤 규칙의 머리도 새로운 무언가가 존재한다고 주장하지 않습니다 — 그래서 최소 고정점이 도출하는 모든 원자는 여러분이 시작할 때 가지고 있던 상수들로 만들어집니다. 모든 답은 자동으로 널이 없으며; 필터가 있어도 결코 아무것도 제거하지 않을 것이므로, 필터는 그저 존재하지 않습니다. 존재 규칙은 그 불변량을 의도적으로 깨뜨립니다. 머리가 $\exists y$ 라고 말하는 순간, 체이스는 그것을 충족시키기 위해 _n-널을 발명해야 할 수 있고, 그 널들은 질의 결과로 흘러 들어갑니다. 확실성이란 상수 전용 필터가 되찾아 주는 것입니다: 그것은 데이터로그의 닫힌 재조합에서 온톨로지가 실제로 필요로 하는 열린 세계의 존재 주장으로 옮겨가는 대가입니다. 준동형사상이라는 원시 연산은 데이터로그의 평가와 달라지지 않습니다; 마지막에 있는 관문만이 새로운 것입니다.

체이스는 모든 부합하는 세계로 준동형사상에 의해 사상되는 하나의 보편 모델을 구축합니다; 그 위에서 질의를 평가하고 상수로만 이루어진 튜플만 남기면 확실한 답인 alice와 bob이 나오며, 널로 증언된 지도 학생은 걸러져 사라집니다. 저자가 AI의 도움을 받아 직접 제작한 원본 도해.

아직 풀리지 않은 부분

이 방법 전체는 정리 속 한 단어에 의존합니다: $\mathrm{chase}(\mathcal{K})$ 입니다. 보편 모델로부터 확실한 답을 읽어내는 것은 그 모델이 완성될 수 있다는 것을 전제합니다. 그러나 체이스가 반드시 종료해야 하는 것은 아닙니다 — 종료하는 규칙들을 "모든 연구자는 어떤 연구자의 지도를 받았다"로 바꾸면, 발명된 지도자마다 그 자신도 연구자여서 새로운 지도자를 요구하게 되어, 무한 퇴행(infinite regress)이 됩니다. 동반 코드는 단계 상한 아래에서 정확히 이것을 실행합니다:

Non-terminating TGD (Researcher(x) -> ∃y advises(y,x) ∧ Researcher(y))
  terminated=False after the 50-firing cap; 50 fresh advisors invented and still growing

주어진 TGD 집합이 유한한 체이스를 가지는지는 일반적으로 결정 불가능(undecidable)하며, 따라서 최악의 경우 제약 없는 존재 규칙 위에서의 확실한 답 계산 역시 결정 불가능합니다 [3]. 이 분야의 대응은 포기하는 것이 아니라, 확실한 답 계산이 결정 가능한 상태로 남는 부분집합(fragment)들을 각기 다른 탈출 경로로 도려내는 것입니다: 약한 비순환(weakly-acyclic) 집합은 체이스가 유한함이 증명 가능하기 때문이고; 끈적한(sticky) 집합은 무한할 수도 있는 체이스를, 원본 데이터가 직접 답할 수 있는 질의로 재작성함으로써 우회할 수 있기 때문이며; 가드된(guarded) 집합은 체이스가 결코 끝나지 않을 수도 있지만 그 위에서 추론할 수 있을 만큼 — 유계 트리너비(bounded treewidth)로 — 충분히 나무 모양을 유지하기 때문입니다. 확실한 답은 그 배후에 있는 보편 모델만큼만 계산 가능하며, 규칙 언어를 선택하는 것은 그 보장을 얼마나 유지할지를 선택하는 것입니다.

왜 중요한가

확실한 답은 열린 세계 추론기의 정직한 계약입니다: 그것은 반드시 성립하는 것만을 반환할 뿐, 그저 성립할 수도 있는 것은 결코 반환하지 않으며, 그것을 원자 단위로 감사(audit)할 수 있는 형태로 진술합니다. 신경-기호(neuro-symbolic) AI에게 이것은 학습된 구성 요소가 견주어 평가받는 정답(ground truth)입니다 — 신경망 링크 예측기는 많은 지도 학생 후보를 그럴듯하다고 순위 매길 수 있지만, 오직 alice와 bob만이 함의되며, 오직 상징적 측면만이 그 차이를 증명할 수 있습니다. 더 깊은 교훈은 두 작업이 하나의 원시 연산으로 붕괴한다는 것입니다: 질의 응답과 모델 구축은 둘 다 준동형사상이므로, 하나를 할 수 있는 시스템은 다른 하나도 할 수 있으며, 준동형사상의 미분 가능한 완화(4권의 소프트 매칭)는 동시에 소프트 질의 엔진이자 소프트 추론기입니다. 명확한 답이 무엇인지 — 널이 걸러진, 정확히 alice와 bob이라는 집합 — 를 아는 것이야말로, 그 근사가 그 답에 도달했는지를 판단할 수 있게 해 주는 것입니다.

핵심 용어

확실한 답(Certain answers) — 지식 베이스의 모든 모델에서 질의에 답하는 상수 튜플들, $\bigcap_{\mathcal{M} \models \mathcal{K}} Q(\mathcal{M})$ ; 열린 세계 추론기가 주장할 수 있는 유일한 답.
열린 세계 가정(Open-world assumption) — 진술되지 않은 사실은 거짓이 아니라 알 수 없는 것; 질의가 하나가 아니라 여러 모델에 걸쳐 있는 이유.
준동형사상(Homomorphism) — 패턴의 모든 원자를 인스턴스의 실제 원자 위에 착지시키는 변수 배정; 논리곱 질의 평가와 체이스의 충족 검사 둘 다의 배후에 있는 단 하나의 원시 연산.
논리곱 질의(Conjunctive query) — 몸체가 원자들의 논리곱인 질의 $Q(\bar{x}) \leftarrow \exists \bar{y}\, \varphi(\bar{x}, \bar{y})$ ; $\varphi$ 에서 인스턴스로의 준동형사상을 찾음으로써 평가됨.
보편 모델(Universal model) — 상수를 고정하는 준동형사상으로 다른 모든 모델에 사상되는 모델; 체이스는 이러한 모델을 산출하므로, 확실한 답은 그 위에서의 단 한 번의 평가로 환원됨.
널(Null) — 강제되었지만 이름 붙지 않은 개체를 나타내는 레이블 붙은 널(labeled null), 즉 자리표 기호(_n1)이며, 상수와는 서로소임(is_const("_n1")은 거짓); 이를 포함하는 튜플은 결코 확실할 수 없는데, 모델마다 그것을 다르게 채우기 때문임.
상수 전용 필터(Constants-only filter) — certain_answers에서 모든 구성 요소가 상수일 때만 튜플을 남기는 $\downarrow_{\text{const}}$ 단계; "체이스에 존재함"을 "확실함"으로 바꾸어 주는 것.
불리언 논리곱 질의(Boolean conjunctive query) — 예/아니오 질의로, 체이스로의 준동형사상이 하나라도 존재할 때 정확히 확실하게 참임(query_holds).

이 장이 이끄는 곳

이제 우리는 열린 세계 파이프라인 전체를 갖추었습니다: 존재 규칙은 체이스에 의해 보편 모델을 구축하고, 확실한 답은 준동형사상과 널을 제거하는 필터에 의해 그로부터 읽어내집니다 — 이 모든 보장은 체이스가 종료한다는 것에 의존하는데, 일반적으로는 그렇지 않을 수도 있습니다. 1부부터 4부까지는 온톨로지가 무엇을 함의하는지에 대한 이론을 구축했습니다; 다음 부에서는 그것을 실질적으로 쓸 만큼 빠르게 결정하는 기계로 눈을 돌립니다. EL 추론기는 다루기 쉬운(tractable) EL 계열로 돌아가 실제 시스템에 대한 연구를 엽니다. 그곳에서는 앞선 장들의 완성 기반 고정점(completion-based fixpoint)과 이 장의 준동형사상 기반 질의가, 수십만 개의 클래스를 가진 온톨로지 위에서 다항 시간(polynomial time)에 실행되도록 공학적으로 설계됩니다. 질문은 무엇이 함의되는가에서 추론기가 무한한 모델을 구축하는 일 없이 그것을 어떻게 계산하는가로 옮겨갑니다.

이 장에서 다루는 내용​

확실한 답, 해독하기​

준동형사상: 유일한 원시 연산​

보편 모델, 그리고 체이스가 보편 모델인 이유​

확실한 답 계산하기: 상수 전용 필터​

커밋된 실행: 누가 학생을 지도하는가?​

데이터로그 대 체이스: 필터가 새로운 이유​

아직 풀리지 않은 부분​

왜 중요한가​

핵심 용어​

이 장이 이끄는 곳​