第 5 章 · 02 Datalog 与 SPARQL：图查询双引擎

第 5 章 · 02 Datalog 与 SPARQL：图查询双引擎

本节摘要：推理不止"推新事实"，还要"答查询"。本节装配 Semantica 的图查询双引擎：DatalogReasoner（431 行）用 Horn 子句与半朴素（semi-naive）不动点求值支撑递归规则查询——祖先是"传递闭包"这种 LLM 问十次错三次的问题，它一次算死；SPARQLReasoner（410 行）面向 RDF 三元组库做标准模式匹配查询，并把推理规则以查询扩展的方式织入。两引擎各有主场：Datalog 适合递归可达性，SPARQL 适合多模式联查。最后看自然语言如何桥接到这两台确定性机器——LLM 只做"翻译"，执行交还确定性引擎，查询结果因此可复现、可审计。

内容来源：semantica/reasoning/datalog_reasoner.py（431 行）、sparql_reasoner.py（410 行）、graph_reasoner.py（162 行）、README.md（Datalog 递归示例）

⚠️ 注意：两台引擎的"确定性"边界不同。Datalog 引擎是本库自研的完整求值器（解析、合一、不动点、查询全链路闭环）；SPARQL 引擎的 execute_query 在未接入三元组库时返回空结果集，推理扩展（infer_results）部分可独立使用——生产接入三元组库前，把它当作"查询扩展+结果推理"层而非完整 SPARQL 实现。

学习目标

1. 理解 Datalog 的数据形态：DatalogFact/BodyAtom/DatalogRule 与 Horn 子句语法 head :- body。
2. 掌握半朴素不动点求值：delta 集合如何让递归规则在有限图上保证终止。
3. 会用 query("ancestor(tom, ?Y)") 做变量查询，load_from_graph 从图谱装载数据。
4. 理解 SPARQL 引擎的查询扩展与结果推理两层设计。
5. 能为"递归规则"与"模式匹配"两种查询需求选出正确的引擎。

一、Datalog：把查询写成逻辑规则

Datalog 是 Prolog 的函数无关子集，一条规则就是一 Horn 子句：头（结论）:- 体（条件合取）。Semantica 的 datalog_reasoner.py 用三个紧凑的数据类承载它（第 18—34 行）：

@dataclass(frozen=True)
class DatalogFact:
    """Represents a ground truth fact."""
    predicate: str
    args: Tuple[str, ...]           # 冻结 dataclass → 可哈希 → 可入集合

class BodyAtom(NamedTuple):
    """Represents a single predicate condition in a rule's body."""
    predicate: str
    args: Tuple[str, ...]

@dataclass
class DatalogRule:
    """Represents a Horn clause rule."""
    head_predicate: str
    head_args: Tuple[str, ...]
    body: List[BodyAtom]
​

frozen=True 不是审美偏好：事实要进 set 做集合代数（去重、差集、delta 切分），可哈希是硬前提。规则由 add_rule("ancestor(X, Y) :- parent(X, Y).") 这样的字符串解析（第 147—175 行）：:- 切头尾，正则抠出每个原子的谓词与参数。变量约定沿用 Prolog：首字母大写即变量，_is_variable（第 180 行）一行判定——这使得 parent(tom, bob) 里的小写 tom 永远是常量，写错即被 add_fact 的校验当场拦下（第 109 行：Facts must be constants only. Found variable 'X'）。

add_fact（第 70—119 行）同时接受三种来源："parent(tom, bob)" 字符串、Semantica 三元组字典（subject/predicate/object）、图谱节点/边字典——统一做小写化与空格替换后入库。这意味着第 3 章图谱和第 4 章去重后的产物可以原样灌入。

二、合一与实例化：变量的两支笔

求值前先补两块逻辑积木。_unify（第 184—215 行）把规则原子的模式参数对齐到具体事实：

for p_arg, f_arg in zip(pattern_args, fact_args):
    if self._is_variable(p_arg):
        if p_arg in bindings:              # 已绑定 → 必须一致
            if bindings[p_arg] != f_arg:
                return None
        elif p_arg in new_additions:       # 同一原子内变量复用 → 同上
            if new_additions[p_arg] != f_arg:
                return None
        else:
            new_additions[p_arg] = f_arg   # 首次出现 → 绑定
    else:
        if p_arg != f_arg:                 # 常量 → 字面匹配
            return None
​

返回 None 表示合一失败；成功则返回扩充后的绑定表。_instantiate（第 217 行）是反向操作：拿绑定表把头部的变量替换成常量，生成一条接地的（ground）新事实。合一管"条件怎么满足"，实例化管"结论长什么样"，两者共享同一张绑定表——这就是逻辑推理的最小完备件。

三、半朴素不动点：递归的终局

derive_all()（第 242—293 行）是引擎的心脏。朴素求值每一轮都用全量事实重算所有规则，大量重复劳动；半朴素（semi-naive）的改进只有一处——每轮只让一个体原子从 delta（新增事实）里取数，其余原子照旧查全量索引（第 295—339 行 _apply_rule）：

is_seminaive = delta_index is not None
evaluation_paths = range(len(rule.body)) if is_seminaive else [0]

for delta_index_pos in evaluation_paths:      # 每个体原子轮流当"新增侧"
    bindings_list = [{}]
    for i, atom in enumerate(rule.body):
        if is_seminaive and i == delta_index_pos:
            candidate_facts = delta_index.get(atom.predicate, set())  # 只看新增
        else:
            candidate_facts = self._fact_index.get(atom.predicate, set())  # 全量索引
        for bindings in bindings_list:
            for fact in candidate_facts:
                merged = self._unify(atom.args, fact.args, bindings)
                if merged is not None:
                    new_bindings_list.append(merged)
​

为什么必须"轮流当新增侧"？以 ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z). 为例：新推出的祖先事实可能落在体中任意一个原子上，只检查第一个原子会漏掉"新祖先 × 旧父子的"组合。主循环（第 262—283 行）则是一个保证终止的泵：

while self._delta_new:
    self._delta_old = self._delta_new
    self._delta_new = set()
    delta_index = defaultdict(set)
    for f in self._delta_old:
        delta_index[f.predicate].add(f)       # 按谓词预索引，免全表扫
    for rule in self._rules:
        for fact in self._apply_rule(rule, delta_index):
            if fact not in self._all_facts:   # 只收真正的新事实
                self._delta_new.add(fact)
                self._all_facts.add(fact)
​

事实全集有限、每轮至少新增一条才继续——delta 终会变空，循环必终止。这就是模块开篇承诺的"guarantees termination on finite graphs"：递归规则不会把引擎带进死循环，只会收敛到唯一不动点。README 的三层家谱示例（tom→bob→ann→pat）上，两条规则迭代三轮即推出 ancestor(tom, bob/ann/pat) 全集。求值结果被 _derived 标志缓存，重复查询零成本（第 247 行）。

四、查询与图谱装载

不动点到达后，query()（第 344—402 行）在推导事实上做模式匹配：

engine.add_fact("parent(tom, bob)")
engine.add_fact("parent(bob, ann)")
engine.add_rule("ancestor(X, Y) :- parent(X, Y).")
engine.add_rule("ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).")
engine.query("ancestor(tom, ?X)")
# → [{"X": "bob"}, {"X": "ann"}, {"X": "pat"}]
​

?X 这种问号风格是给查询方的便利语法（第 368 行内部转成大写变量），查询前会自动触发 derive_all()。图谱整库装载走 load_from_graph（第 404—430 行）：有 find_edges/find_nodes 的 ContextGraph 走快路径，任意 duck-typed 图对象走 edges/nodes 兜底，返回装载条数——管线里一行代码把第 3 章的图变成 Datalog 的事实库。

五、SPARQL：RDF 的标准问法

SPARQL 是 W3C 为 RDF 三元组定制的标准查询语言，主场是模式匹配：一组三元组模式 { ?s ?p ?o } 在三元组库里做联接筛选，不涉及递归。SPARQLReasoner 的设计重心因此不在"求值"，而在把推理织进查询——两层结构：

第一层，查询扩展 expand_query（第 89—150 行）：遍历内部 Reasoner 持有的推理规则，_rule_to_sparql（第 152—186 行）把 x is_a Person 形态的条件翻译成 SPARQL 模式 ?x a :Person .，作为推理注释拼进原查询——让"凡是 Person 皆是 Human"这类分类规则在查询层生效。

第二层，结果推理 infer_results（第 188—252 行）：对已取回的绑定集追加规则派生的新绑定，_deduplicate_bindings（第 313 行）用 tuple(sorted(binding.items())) 做可哈希键去重，元数据里明确记录 original_count 与 inferred_count——查出来的和推出来的分得清清楚楚，这一点在审计场景很重要。

execute_query（第 329 行）串起全流程：查缓存 → 扩展 → 送三元组库执行 → 结果推理 → 回写缓存。triplet_store 参数接第 8 章的存储后端；add_inference_rule 直接委托门面 Reasoner.add_rule，与 5.1 节共享同一套规则资产。

六、选型与自然语言桥接

两台引擎怎么选，一句话版本：要"可达性/传递性"答案用 Datalog，要"多模式联查"答案用 SPARQL。

自然语言进图画最后一公里，graph_reasoner.py 提供了 LLM 路线：reason(graph, query) 把图谱渲染成文本（第 144—155 行 _prepare_graph_context），套上"Answer strictly based on the provided graph context"的提示词模板交给 LLM 作答。这条路线读起来舒服，但答案出于概率采样；与本章两台引擎正确的组合方式是分层翻译：LLM 把"谁是 Tom 三代以内的祖先"翻译成 ancestor(tom, ?X) 或一段 SPARQL——翻译错了人能看出来，翻译对了执行就是纯确定性的。自然语言的不确定性被压缩在"翻译"一层，"执行"一层交给不动点与联接，审计时每个答案都能回落到规则与事实。这正是本模块 README 标题的承诺："Run explainable rule-based inference, not a black box."

💡 装配要点：双引擎在管线里各守一段——DatalogReasoner.load_from_graph(graph) 一行接图谱，add_rule 装领域递归规则，query 供上层做可达性问答；SPARQLReasoner(triplet_store=...) 对接第 8 章存储后端做标准查询，规则经 add_inference_rule 与 5.1 节共享。半朴素求值的关键心智模型：delta 集合是"上一轮新增"，每个体原子轮流从 delta 取数，其余查全量索引；终止性由"事实全集有限 + delta 必枯竭"保证。LLM 只出现在 GraphReasoner 的翻译位，永远不出现在求值位。

本节要点回顾

• Datalog 三件套：frozen DatalogFact（可哈希入集合）、BodyAtom、DatalogRule；head :- body Horn 子句，大写开头即变量，事实里出现变量直接报错。
• 合一 _unify 管条件匹配（已绑定须一致、常量须字面相等），实例化 _instantiate 管结论落地，共享绑定表。
• 半朴素不动点：每轮每个体原子轮流从 delta 取数、其余走谓词索引；_delta_new 空即收敛，有限图保证终止，不动点唯一 → 查询可复现。
• query("ancestor(tom, ?X)") 自动先 derive_all；load_from_graph 直连 ContextGraph。
• SPARQL 引擎两层：expand_query 把 is_a 规则织入查询文本，infer_results 对绑定集做规则派生并区分 original/inferred 数量。
• 选型口诀：递归可达用 Datalog，模式联查用 SPARQL；LLM 只做自然语言到查询的翻译，执行全程确定性。

下一节：03 溯因/演绎推理与 ExplanationGenerator ★——从结论反推最佳解释的溯因、三段论式的演绎，以及给监管交付"为什么"的 ExplanationGenerator。