데이터로그: 규칙, T_P 연산자, 최소 고정점

📍 현재 위치: 4부 · 데이터로그와 체이스 — 12장. 귀결 기반 추론은 두 개의 장부(ledger)를 고정점까지 키워 나가며 포섭(subsumption) 관계를 도출하는 서술 논리(description logic) 추론기를 보여주었습니다; 이제 우리는 그 엔진을 가장 순수한 형태로 — 데이터로그(Datalog)라는 규칙 언어로 — 발라내어, 고정점이 속임수가 아니라 규칙 프로그램이 의미하는 바의 정의 그 자체임을 증명합니다.

지금까지 이 권에 등장한 모든 추론기는 사실 변장한 같은 루프였습니다: 가지고 있는 사실들 위에서 고정된 규칙 집합을 발동시키고, 그것들이 결론짓는 바를 모아들이며, 한 라운드가 아무것도 바꾸지 못할 때까지 반복하는 것입니다. 이 장은 그 루프의 본향에 이름을 붙입니다. 데이터로그는 그 전체 의미론이 바로 그 루프인, 작고 정확한 규칙 언어이며, 전방 연쇄(forward chaining), EL 완비 알고리즘(completion algorithm), 그리고 실제 지식 그래프 뒤에 있는 질의 엔진들의 공통 조상이기 때문에 그 자체로 만나 볼 가치가 있습니다. 우리는 규칙 하나를 해독하고, 그것을 실행하는 연산자를 정의하며, 그 루프가 유일한 답에 도달함을 증명한 다음, 그것이 학계 세계를 원자 하나하나까지 재구축하는 모습을 지켜볼 것입니다.

쉽게 말하면

사무원들로 가득 찬 방 하나를 상상해 보십시오. 각 사무원은 "이 사실들이 게시판에 있으면, 이 새로운 사실을 게시판에 적어라"라는 형태의 작은 규칙을 하나씩 들고 있습니다. 아무도 아무것도 지우지 않습니다. 당신이 종을 울리면, 지금 자기 규칙이 적용되는 모든 사무원이 나서서 자신의 결론을 적습니다. 다시 종을 울리면, 이번에는 방금 적힌 그 새로운 사실들을 필요로 했던 사무원들도 적을 차례가 됩니다. 당신은 어떤 사무원도 더 이상 새로 적을 것이 없는 라운드 전체가 지나갈 때까지 계속 종을 울립니다. 그 순간 게시판에는 그 규칙들이 만들어낼 수 있는 모든 사실이 — 더도 덜도 아니게 — 담겨 있습니다. 데이터로그는 정확히 이 방이고, 종은 연산자 $T_P$ 이며, "종이 더 이상 의미가 없어졌을 때의 게시판"이 바로 최소 고정점입니다.

이 장에서 다루는 내용

데이터로그 규칙 하나, 해독하기 — head :- body₁, …, bodyₙ 형태, 왜 허용되는 항이 오직 상수와 변수뿐인지, 그리고 함수 기호를 금지하는 것이 어째서 도출 가능한 사실들의 풀(pool)을 유한하게 만드는지.
즉시 귀결 연산자(immediate-consequence operator) $T_P$ — 사실 집합 위의 함수로서의 한 라운드의 추론: 몸체가 성립하는 모든 규칙을 발동시키고, 모든 머리를 추가하며, 커진 집합을 되돌려줍니다.
최소 고정점 = 최소 모델 — 더 이상 커지지 않을 때까지 기본 사실들로부터 $T_P$ 를 반복 적용하는 것, 그리고 그 답이 어째서 유일한지 — Knaster–Tarski 정리로 보장되며 1권의 전방 연쇄와 동일하다는 것.
학계 세계 실행하기 — 일곱 개의 실제 혼 규칙(Horn rule)과 커밋된 출력: 세 번의 파동으로 이루어진 최소 고정점, 크기 [23, 41, 47, 47], 총 47개 원자, 그중 24개가 도출됨.
도출된 관계 읽어내기 — 다섯 명의 연구자, 세 개의 grandAdvisor 쌍, 세 개의 전이적 인용, 여덟 개의 colleague 쌍, 그리고 colleague를 비반사적(irreflexive)으로 유지시키는 neq 가드.
재귀가 고정점을 필요로 하는 이유 — citesTransitively(p3, p1)이 어째서 citesTransitively(p2, p1)보다 정확히 한 파동 뒤에서만 나타날 수 있는지, 그래서 어떤 고정된 횟수의 스윕도 안전하지 않은 이유.
아직 풀리지 않은 부분 — 데이터로그는 이미 가지고 있는 상수들만 재조합할 수 있습니다; 규칙이 이름을 붙이지 않고도 무언가가 존재한다고 주장해야 하는 순간, 우리에게는 존재 규칙(existential rule)과 체이스(chase)가 필요합니다.

데이터로그 규칙 하나, 해독하기

데이터로그 프로그램은 규칙(rule)들의 유한 집합입니다. 각 규칙은 다음과 같이 적습니다.

\underbrace{H}_{\text{head}} \;\text{:-}\; \underbrace{B_1, B_2, \ldots, B_n}_{\text{body}}.

목 기호(neck symbol) :-는 "~이면 성립한다"로 읽으십시오: 왼쪽의 단일 원자 $H$ 는, 변수들에 대한 어떤 일관된 값 배정 아래에서 오른쪽 몸체의 원자 $B_1, \ldots, B_n$ 전부가 참일 때마다 참으로 결론지어집니다. 원자(atom)는 advises(alice, bob)처럼 인자에 적용된 술어(predicate)이며, 몸체가 빈 규칙( $n = 0$ )은 그저 저장된 사실(fact)입니다. 다음은 동반 파일에 있는 규칙 하나로, 지도 관계를 그 자신과 합성하는 규칙입니다.

(("grandAdvisor", "?x", "?z"),
 [("advises", "?x", "?y"), ("advises", "?y", "?z")]),

평범한 데이터로그 표기법으로는 grandAdvisor(?x, ?z) :- advises(?x, ?y), advises(?y, ?z)가 되며 — " $?x$ 가 어떤 $?y$ 를 지도하고 그 $?y$ 가 다시 $?z$ 를 지도한다면, $?x$ 는 $?z$ 의 조부모격 지도자(grand-advisor)이다"로 읽습니다. 이 언어 전체를 규정하는 특징은 두 가지입니다. 첫째, 오직 상수와 변수만이 항이며 — 그 밖에는 아무것도 없습니다. 상수(constant)는 고정된 개체 하나의 이름이고(alice, p1, mit), 변수(variable)는 규칙이 발동될 때 상수로 묶이는 자리표시자(placeholder)입니다. 동반 코드는 대문자로 시작하는 개념 이름이 변수로 오인되지 않도록 변수를 앞에 붙는 ?로 표시합니다(datalog.py, 43–46번째 줄):

def is_var(t) -> bool:
    """A Datalog variable is a string beginning with ``?`` (so capitalised
    constants such as ``Professor`` are *not* mistaken for variables)."""
    return isinstance(t, str) and t.startswith("?")

둘째 — 이것이 하중을 떠받치는 제약입니다 — 데이터로그는 함수 기호가 없습니다(function-free): 함수 기호가 전혀 없으므로 어떤 항도 중첩될 수 없고, 규칙은 결코 $f(f(\text{alice}))$ 같은 완전히 새로운 구조화된 객체를 만들어낼 수 없습니다. 규칙이 만들어내는 모든 머리는 이미 프로그램 안에 있던 상수들을 대입하여 접지(ground)됩니다. 프로그램에는 유한개의 술어와 유한개의 상수만 있으므로(학계 세계에는 13개가 있습니다: 다섯 명의 사람, 세 편의 논문, 두 개의 기관, 세 개의 주제), 형성될 수 있는 접지 원자(ground atom)도 유한개뿐입니다. 그 유한한 풀이 바로 허브랜드 기저(Herbrand base) $B_P$ 이며, 그것이 유한하다는 사실이 아래 모든 것이 종료하는 이유입니다: 추론은 오직 $B_P$ 에서 뽑힌 원자만을 추가할 수 있고, 유한한 천장 안에서만 커지는 집합은 반드시 커지기를 멈춰야 합니다 [1]. 이것이 바로 함수 기호 없는 혼 논리(function-free Horn logic)로서의 데이터로그입니다 — 혼(Horn)인 이유는 모든 규칙이 정확히 하나의 양의 머리(positive head)와 양의 몸체 원자들의 논리곱을 가질 뿐, 선언(disjunction)도 부정(negation)도 없기 때문입니다.

즉시 귀결 연산자 $T_P$

한 라운드의 추론은 사실 집합 위의 함수입니다. 현재의 사실들이 주어지면, 그것은 몸체가 충족되는 모든 규칙을 발동시키고 그 사실들에 더해 그렇게 도출된 모든 머리를 반환합니다. 이 함수가 바로 즉시 귀결 연산자(immediate-consequence operator)이며 $T_P$ 라고 적습니다 — 아래 첨자 $P$ 는 규칙들의 프로그램(program)을 가리킵니다. 동반 코드에서는 독스트링(docstring)을 포함해 여덟 줄입니다(datalog.py, 93–100번째 줄):

def t_p(facts: set, rules: list) -> set:
    """One application of the immediate-consequence operator T_P: the given facts
    plus every rule head derivable from them in a single step."""
    out = set(facts)
    for head, body in rules:
        for sub in _match_body(body, facts, {}):
            out.add(_apply(head, sub))
    return out

한 줄씩 보면: out = set(facts)는 현재 사실들을 복사하므로 $T_P$ 는 결코 아무것도 지우지 않습니다; rules에 대한 루프는 각 규칙을 시도합니다; _match_body는 현재 사실들 안에서 몸체 전체를 참으로 만드는 모든 변수-상수 치환을 산출합니다; 그리고 out.add(_apply(head, sub))는 그 치환 아래 머리를 추가함으로써 규칙을 발동시킵니다. 원자들의 집합 $S$ 에 대해 집합 방정식으로 적으면,

T_P(S) \;=\; S \,\cup\, \{\, H\sigma \;:\; (H \text{ :- } B_1, \ldots, B_n) \in P,\ B_i\sigma \in S \text{ for all } i \,\},

여기서 $\sigma$ 는 규칙의 변수들에 대한 상수 치환이고 $H\sigma$ 는 그 치환이 적용된 머리이며; 콜론은 "그러한"으로 읽고 $\cup$ 는 집합 합집합(union)입니다. 이 연산자에는 모든 것이 그 위에 걸려 있는 성질이 하나 있습니다: 바로 단조성(monotone)입니다 — 더 큰 사실 집합을 넣으면 오직 더 큰 결과만 돌려줄 수 있습니다, $S \subseteq S' \Rightarrow T_P(S) \subseteq T_P(S')$ . 이는 정확히 모든 몸체 원자가 양(positive)이기 때문에 성립합니다: 사실을 추가하는 것은 오직 더 많은 규칙 몸체를 충족시킬 수 있을 뿐, 이미 충족된 것을 꺼버리는 일은 결코 없습니다. (몸체 안의 부정(negation)은 이를 깨뜨릴 것이며, 이것이 바로 순수 데이터로그가 부정을 금지하는 이유입니다.)

최소 고정점 = 최소 모델

프로그램으로 추론한다는 것은 $T_P$ 를 계속해서 반복 적용하는 것입니다. $T_P(S) = S$ 를 만족하는 집합 $S$ 는 고정점(fixpoint)입니다: 모든 규칙을 발동시켜도 이미 가지고 있지 않았던 것은 아무것도 나오지 않습니다. 프로그램의 의미는 최소 고정점(least fixpoint)이며, $\mathrm{lfp}(T_P)$ 라고 적습니다 — 그런 집합들 중 가장 작은 것 — 그리고 그것에 도달하는 루프는 상상할 수 있는 가장 단순한 형태입니다(datalog.py, 103–114번째 줄):

def least_fixpoint(edb, rules, trace: bool = False):
    """Iterate T_P from the EDB facts until it stops growing — the least fixpoint
    lfp(T_P), i.e. the least model. With ``trace=True`` also return the per-wave
    size list, exposing how the derivation grows."""
    current = set(edb)
    sizes = [len(current)]
    while True:
        nxt = t_p(current, rules)
        sizes.append(len(nxt))
        if nxt == current:
            return (current, sizes) if trace else current
        current = nxt

씨앗 값 current = set(edb)는 EDB(외연 데이터베이스, extensional database — 직접 단언된 기본 사실들로, 규칙이 도출하는 관계들의 집합인 IDB, 즉 내포 데이터베이스(intensional database)와 대비됩니다)에서 시작합니다. nxt = t_p(current, rules) 줄은 한 번의 적용 $S_{t+1} = T_P(S_t)$ 이며, if nxt == current는 고정점 검사 $T_P(S) = S$ 를 if문으로 옮긴 것입니다. EDB로 씨앗을 심는 것은 그 사실들을 빈 몸체를 가진 규칙으로 취급하여 빈 집합에서 씨앗을 심는 것과 같으므로, 이 오름 전체는 하나의 별도 수식으로 포착됩니다:

\mathrm{lfp}(T_P) \;=\; \bigcup_{n \ge 0} T_P^{\,n}(\varnothing),

여기서 $T_P^{\,n}$ 은 " $T_P$ 를 $n$ 번 적용한 것"을 뜻하고, $\varnothing$ 은 공집합이며, $\bigcup$ 은 어느 라운드에서든 나타나는 원자들을 모읍니다. 1권에서 나온 두 정리가 이것을 희망 사항이 아니라 정당한 것으로 만들어 줍니다. Knaster–Tarski 정리는 허브랜드 기저의 부분집합들로 이루어진 완비 격자(complete lattice) 위의 단조 연산자가 애초에 최소 고정점을 가짐을 보장합니다; 클레이니(Kleene) 구성은 $\varnothing$ 에서부터 반복하면 그것에 도달함을 말해 주며, $B_P$ 가 유한하므로 오름 사슬 $\varnothing \subseteq T_P(\varnothing) \subseteq T_P^2(\varnothing) \subseteq \cdots$ 는 유한하게 많은 엄밀한 성장 단계 뒤에 반드시 멈추어야 합니다. 논리 프로그래밍의 고전적 결과가 이 고리를 닫습니다: 이 최소 고정점은 최소 모델(least model) — 모든 규칙을 참으로 만드는 가장 작은 사실 집합 — 과 같으므로, 절차와 의미가 일치합니다 [1]. 이는 1권의 forward_chain.py와 동일한 엔진입니다; 데이터로그는 그저 데이터베이스 세계가 그것에 붙인 이름일 뿐입니다 [2].

학계 세계 실행하기

동반 코드의 A부는 학계 세계의 규칙들을 ?-변수 관례로 다시 표현하여 처음부터 실행합니다. 일곱 개의 규칙이 내포적 어휘 전체를 이룹니다 — researcher, person, grandAdvisor, colleague, 그리고 전이적 인용(datalog.py, 121–132번째 줄):

HORN_RULES = [
    (("researcher", "?x"), [("professor", "?x")]),
    (("researcher", "?x"), [("student", "?x")]),
    (("person", "?x"), [("researcher", "?x")]),
    (("grandAdvisor", "?x", "?z"),
     [("advises", "?x", "?y"), ("advises", "?y", "?z")]),
    (("colleague", "?x", "?y"),
     [("affiliated", "?x", "?i"), ("affiliated", "?y", "?i"), ("neq", "?x", "?y")]),
    (("citesTransitively", "?a", "?b"), [("cites", "?a", "?b")]),
    (("citesTransitively", "?a", "?c"),
     [("cites", "?a", "?b"), ("citesTransitively", "?b", "?c")]),
]

python3 datalog.py를 실행하면 오름 과정과 도출된 결과가 출력됩니다 — 다음은 실제로 커밋된 출력입니다:

Part A — academic-world Horn rules
  least fixpoint in 3 waves; sizes: [23, 41, 47, 47]
  47 atoms total, 24 derived
  researchers (5): ['alice', 'bob', 'carol', 'dave', 'erin']
  grandAdvisor (3): [('alice', 'carol'), ('alice', 'dave'), ('bob', 'erin')]
  citesTransitively (3): [('p2', 'p1'), ('p3', 'p1'), ('p3', 'p2')]
  colleague pairs: 8

[23, 41, 47, 47]을, 크기 $\lvert S_t\rvert$ 가 단마다 출력되는 오름 사슬 $S_0 \subseteq S_1 \subseteq S_2 \subseteq S_3$ 로 읽으십시오. 마지막의 $47 = 47$ 은 아무것도 바뀌지 않는 파동이며, 그리하여 nxt == current에 의해 고정점에 도달했음을 증명합니다 — 1권에서와 정확히 똑같이, 전체 세 번의 파동 중 두 번은 생산적이고 세 번째는 그저 확인일 뿐입니다. 각 파동에서 어떤 원자들이 들어오는지, 그리고 그 이유는 다음과 같습니다:

파동 $t$	$\lvert S_t\rvert$	이 파동에서 추가된 원자	발동한 규칙
0	23	23개의 EDB 사실(씨앗)	아직 없음
1	41	+18: `researcher`×5, `grandAdvisor`×3, `colleague`×8, `citesTransitively`×2	몸체가 기본 사실을 읽는 모든 규칙
2	47	+6: `person`×5, `citesTransitively(p3, p1)`×1	도출된 사실을 읽는 두 규칙
3	47	+0	모든 발동이 이미 있는 원자를 되풀이함

24개의 도출된 원자는 나머지 없이 5개의 researcher + 5개의 person + 3개의 grandAdvisor + 8개의 colleague + 3개의 citesTransitively로 나뉘며, $23 + 24 = 47$ 입니다.

오름 사슬로서의 데이터로그 평가: 23개의 EDB 사실로부터 $T_P$ 를 반복 적용하면 집합이 $S_0 \subseteq S_1 \subseteq S_2 \subseteq S_3$ (크기 23, 41, 47, 47)을 따라 자라나 최소 고정점에서 멈추며, 두 홉짜리 인용 p3 → p1은 그것이 기반하는 한 홉짜리 p2 → p1보다 한 파동 늦게 도착합니다. 저자가 AI의 도움을 받아 직접 제작한 원본 도해.

도출된 관계 읽어내기

출력된 관계들은 내포 데이터베이스이며, 각각은 눈으로 직접 확인할 수 있는 작은 논거입니다. 다섯 명의 연구자(researcher)는 교수이거나 학생인 모든 사람이며, 그들 모두는 다음 파동에서 사람(person)이 됩니다 — professor/student ⟹ researcher ⟹ person이라는 두 단계 연쇄입니다. 세 개의 grandAdvisor 쌍 — (alice, carol), (alice, dave), (bob, erin) — 은 지도 사슬 alice → bob → carol, alice → bob → dave, bob → carol → erin이 역할-사슬(role-chain) 규칙에 의해 합성된 것입니다. 세 개의 전이적 인용(transitive citation)은 p3 → p2 → p1이라는 사슬을 닫습니다: 두 개의 직접 엣지 (p2, p1)과 (p3, p2)에 도출된 도달 가능성(reachability) (p3, p1)을 더한 것입니다.

여덟 개의 colleague 쌍은 순서가 있는 동일 기관 쌍들입니다: mit에 둘(alice–bob, 양방향), 그리고 세 명의 cmu 학생들 사이에 여섯입니다. 어떤 사람이 자기 자신의 동료(colleague)로 등재되는 것을 막는 것은 몸체 안의 neq 가드입니다. 이는 저장된 사실이 아니라 엔진이 직접 평가하는 내장 술어(built-in)입니다(datalog.py, 81–86번째 줄):

    if first[0] == "neq":
        x = sub.get(first[1], first[1])
        y = sub.get(first[2], first[2])
        if not is_var(x) and not is_var(y) and x != y:
            yield from _match_body(rest, facts, sub)
        return

이 가드는 두 인자가 서로 다른 상수에 묶여 있을 때에만 성공하므로, colleague(carol, carol)은 추가되기도 전에 차단됩니다. 이것이 없다면 이 관계는 반사적(reflexive)이 되어 그 개수가 부풀어 올랐을 것입니다; 이것이 있음으로써 colleague는 비반사적(irreflexive)이 되고, 집계는 정확히 8입니다.

재귀가 한 번의 스윕이 아니라 고정점을 필요로 하는 이유

대부분의 규칙은 유계인 파동 수 안에서 안정됩니다 — person은 researcher를 기다리고, researcher는 professor를 기다리는, 미리 펼쳐 둘 수 있는 고정된 세 겹 사슬입니다. 재귀(recursion)는 다릅니다. 전이적 인용 규칙이야말로 고정점 장치를 고정된 횟수의 순회로 대체할 수 없는 이유입니다:

    (("citesTransitively", "?a", "?b"), [("cites", "?a", "?b")]),
    (("citesTransitively", "?a", "?c"),
     [("cites", "?a", "?b"), ("citesTransitively", "?b", "?c")]),

두 번째 절(clause)은 자신의 머리를 다시 자신의 몸체로 되먹입니다. 인용 사슬 p3 → p2 → p1 위에서 한 번의 스윕이 무엇을 할 수 있고 무엇을 할 수 없는지 지켜보십시오. wave 1에서는 비재귀적인 기본 사례(base-case) 절이 각각의 직접 cites 엣지를 citesTransitively 엣지로 바꾸므로, citesTransitively(p2, p1)과 citesTransitively(p3, p2)가 나타납니다. 그러나 citesTransitively(p3, p1)은 아직 나타날 수 없습니다: 재귀 절은 자신의 몸체에 citesTransitively(p2, p1)이 놓여 있기를 필요로 하는데, wave 1이 시작될 때 그 원자는 존재하지 않았습니다. wave 2에 이르러서야, 이제 게시판에 citesTransitively(p2, p1)이 놓이면서, 재귀 절이 발동하여 citesTransitively(p3, p1)을 만들어냅니다:

wave	존재하는 `citesTransitively` 원자	이유
1	`(p2, p1)`, `(p3, p2)`	두 개의 직접 `cites` 엣지에 대한 기본 사례 절
2	`(p2, p1)`, `(p3, p2)`, `(p3, p1)`	재귀 절: `cites(p3, p2)` ∧ `citesTransitively(p2, p1)`
3	변화 없음	합성할 새 쌍이 없음; 고정점 확인됨

바로 그 하나의 지연된 원자가 핵심입니다. 두 홉 깊이의 결론은 그 아래에 있는 한 홉 결론이 존재하기 전까지는 도달할 수 없으며, 인용 사슬은 어떤 길이든 될 수 있으므로 미리 고정된 어떤 횟수의 스윕도 안전하지 않습니다 — $k$ 편의 논문으로 이루어진 사슬은 그 가장 긴 도달 가능성 원자가 나타나기까지 $k-1$ 번의 파동을 필요로 합니다. 이것이 바로 전이적 폐포(transitive closure)가, 어떤 고정된 관계형 조인(relational join) 집합으로도 표현할 수 없는 진정한 재귀의 교과서적 사례인 이유이며, 데이터로그의 의미론이 유계인 펼침이 아니라 반드시 고정점이어야 하는 이유입니다 [3]. 여기서 추론은 더 이상 고정된 계산이기를 멈추고 한계에 도달하는 것이 됩니다.

아직 풀리지 않은 부분

데이터로그의 보증 — 유한하게 많은 파동 안에 도달되는 유일한 최소 모델 — 은 전적으로 함수 기호 없음이라는 제약으로 얻어진 것이며, 바로 그 동일한 제약이 그 한계이기도 합니다. 데이터로그는 언제나 이미 가지고 있는 상수만을 재조합할 수 있을 뿐입니다. 47개 원자로 이루어진 고정점 안의 모든 원자는 EDB에 이름 붙은 13개의 개체로부터 만들어집니다; 규칙들은 그 상수들을 뒤섞어 새로운 관계로 만들 뿐, 결코 새로운 상수를 불러내지는 않습니다. 이것이 바로 허브랜드 기저를 유한하게 유지하고 오름을 종료시키는 요인입니다.

그러나 실제 온톨로지는 흔히 이름을 붙이지 않고도 무언가가 존재한다고 말해야 합니다: 특정한 지도교수가 기록에 없더라도 "모든 연구자는 지도교수를 가진다"고 말해야 하는 것처럼 말입니다. 머리가 $\exists r.C$ 를 주장하는 규칙 — 이름 붙지 않은 어떤 증인(witness)이 존재해야만 하는 것 — 은 데이터로그일 수 없는데, 그것을 발동시키려면 새로운 개체를 발명해야 하고, 그 발명된 개체 또한 지도교수가 필요한 연구자이므로, 규칙은 방금 자신이 만들어낸 것에 대해서도 다시 발동하기 때문입니다. 이러한 의무를 뒤쫓는 전방 연쇄 과정이 바로 체이스(chase)이며, 그 오름 사슬은 고정점에 결코 도달할 필요가 없습니다: 그것은 영원히 오를 수 있어서, 익명의 증인들로 이루어진 끝없는 탑을 찍어낼 수 있습니다. 유한성 논증은 그 단 하나의 산술적 단계에서 무너집니다 — 허브랜드 기저가 더 이상 유한하지 않으므로 — 그래서 "아무것도 바뀌지 않을 때까지 그저 반복하라"는 것은 더 이상 통하는 계획이 아닙니다. 그렇다면 결정 가능성(decidability)은 어디에 남는지, 그리고 어떤 제한된 규칙 형태가 그것을 다시 되찾아 오는지가 다음 장이 다루는 미해결 질문입니다.

왜 중요한가

데이터로그는 이 권의 더 무거운 모든 추론기와, 앞으로 나올 권들의 모든 학습된 추론기가 견주어지는 명료한 명세(specification)입니다. 그 최소 고정점은 정규(canonical) 답입니다: 정확히 하나의 최소 모델이 존재하고, 그것은 완전하며(도출 가능한 것 중 놓치는 것이 없습니다), 원자 단위까지 재현 가능합니다 — 실행할 때마다 동일한 [23, 41, 47, 47]입니다. 신경-기호(neuro-symbolic) AI에게 이는 이상적인 잣대가 됩니다. 미분 가능한 규칙 계층(differentiable rule layer)이나 그래프 임베딩(graph-embedding) 모델이 "규칙으로 추론한다"고 주장할 때, 질문은 그것이 이 고정점에 도달하는지, 아니면 그저 그럴듯해 보이는 근사에 그치는지이며, 전이적 인용 사례는 정확히 소프트 모델들이 잘라내기 쉬운 종류의 다중 홉(multi-hop) 재귀적 추론입니다. 데이터로그의 답이 유일하며 정확히 계산 가능하다는 것을 안다는 것은, 신경망 근사가 올바른 극한에 착지했는지 아니면 그 근처의 틀린 극한에 착지했는지를 말할 수 있게 해 줍니다 — "요구사항이 곧 테스트다"라는 동일한 규율이되, 이제는 그 요구사항이 고정점에 못박혀 있는 것입니다.

핵심 용어

데이터로그(Datalog) — 함수 기호 없는 혼 논리(function-free Horn logic): 항이 오직 상수와 변수뿐이고 함수 기호가 없는 규칙 head :- body₁, …, bodyₙ들의 유한 집합.
규칙(rule) / 머리(head) / 몸체(body) / 사실(fact) — 규칙은 어떤 치환 아래에서 모든 몸체 원자가 성립할 때마다 그 머리 원자를 결론짓습니다; 사실은 몸체가 빈 규칙입니다.
허브랜드 기저(Herbrand base) $B_P$ — 프로그램이 형성할 수 있는 모든 접지 원자(ground atom)로 이루어진 유한한 풀; 데이터로그에 함수 기호가 없기 때문에 정확히 유한하며, 이것이 평가가 종료하는 이유입니다.
즉시 귀결 연산자(immediate-consequence operator) $T_P$ — 몸체가 성립하는 모든 규칙을 발동시켜 머리를 추가하는 단조 사상(monotone map); 한 번의 적용이 한 번의 파동입니다.
최소 고정점(least fixpoint) / 최소 모델(least model) — $T_P$ 아래에서 닫혀 있는 가장 작은 집합으로, $\bigcup_n T_P^n(\varnothing)$ 과 같습니다; 프로그램의 유일한 의미이며, Knaster–Tarski로 보장되고 유한한 기저 위에서의 클레이니 오름(Kleene climb)으로 도달됩니다.
EDB / IDB — 단언된 기본 사실들로 이루어진 외연 데이터베이스(extensional database)와, 규칙이 도출하는 관계들로 이루어진 내포 데이터베이스(intensional database).
neq 가드 — 두 접지 인자가 서로 다를 때에만 성립하는 내장 술어(built-in); colleague를 비반사적으로 유지시켜 그 개수를 8로 붙잡아 둡니다.
재귀(recursion) — 머리가 자신의 몸체로 다시 들어가는 규칙(전이적 인용); 고정된 횟수의 스윕이 아니라 고정점이 필요한 이유입니다.

이 장이 이끄는 곳

데이터로그는 우리에게 완벽한 보증을 지닌 규칙 엔진을 줍니다 — 언제나 도달되는 하나의 정규(canonical) 답이라는 보증이며, 이는 규칙이 새로운 것이 존재한다고 주장하는 일을 결코 허용하지 않음으로써 얻어진 것입니다. 다음 장인 존재 규칙과 체이스는 바로 그 제약을 없앱니다. 그것은 규칙의 머리가 이름 붙지 않은 증인을 요구하도록 허락하고, 그것을 발명해내는 전방 연쇄 체이스를 따라가며, 그 결과와 정면으로 마주합니다: 이제 오름은 영원히 계속될 수 있고, 결정 가능성은 더 이상 공짜가 아니며, 어떤 존재 규칙 형태가 추론을 종료 가능하게 — 또는 적어도 결정 가능하게 — 유지시키는지에 대한 연구 전체가 시작됩니다. 데이터로그의 유한하고 친절한 세계가 바로 그 더 험난한 이야기가 시작되는 곳입니다.

이 장에서 다루는 내용​

데이터로그 규칙 하나, 해독하기​

즉시 귀결 연산자 TPT_PTP​​

최소 고정점 = 최소 모델​

학계 세계 실행하기​

도출된 관계 읽어내기​

재귀가 한 번의 스윕이 아니라 고정점을 필요로 하는 이유​

아직 풀리지 않은 부분​

왜 중요한가​

핵심 용어​

이 장이 이끄는 곳​