分层否定 Datalog | Codeboy's Blog

形式陈述

有限、安全的否定规则

正 Datalog从空关系反复添加有规则见证的事实，得到有限最小不动点。若要查询“哪些节点对不可达”，还需要判断某个事实最终没有被推出。分层否定的做法是先完成被查询关系，再允许后续规则读取它的补集。

固定有限、无函数符号的程序 $P$ 与有限输入数据库 $I$ 。规则形如

H(\bar t)\leftarrow B_1(\bar t_1),\ldots,B_m(\bar t_m), \operatorname{not}C_1(\bar s_1),\ldots,\operatorname{not}C_\ell(\bar s_\ell).

项只有变量与常量；不同常量名表示不同值。规则中每个变量都必须出现在至少一个正关系体原子里，包括出现在头或否定原子里的变量。这一安全性条件给变量提供取值范围。允许无变量的事实与零元规则。EDB 是始终固定的输入关系，不出现在规则头中；IDB 是规则定义的关系。关系按集合解释，不含重复行、NULL、聚合或生成新值的运算。

求值载体取

A=\operatorname{adom}(I)\cup\operatorname{Const}(P).

规则变量只需枚举 $A$ 中的值。无变量规则有唯一的空赋值；即使 $A=\varnothing$ ，仍约定 $A^0=\{()\}$ ，所以零元关系可以成立。这并不要求外部一阶论域为空：安全性保证额外加入未使用的值不会为正体提供新的匹配。

分层条件与语义终点

分层是给每个关系符号指定非负整数 $\sigma(R)$ ，使每条规则满足

\sigma(B_i)\leq\sigma(H),\qquad \sigma(C_j)<\sigma(H).

EDB 放在第 $0$ 层。IDB 也可在第 $0$ 层；此时求值仍把 EDB 当作已知输入，只有 IDB 从空关系开始。正依赖允许同层递归，负依赖必须指向已经完成的较低层。

建立带符号依赖图：顶点是关系符号，边从规则体关系指向头关系；正体产生正边，否定体产生负边。同一对顶点可以同时有正边与负边。下列三项等价：程序存在分层；依赖图没有包含负边的有向圈；每条负边的两端都属于不同的强连通分量。

在此条件下，按层递增求值，每层都在固定较低层答案后取本层的正 Datalog 最小不动点。有限求值必定终止，结果满足全部规则，且不依赖合法分层的选择。这个被选定的解释称为分层模型；在这里的有限设置中，它与文献中的唯一完美模型（perfect model）一致。后文证明逐层构造及其分层无关性；与完美模型偏好定义的对应见 Przymusinski 的原始论文。这里的唯一性不表示所有经典模型中存在按集合包含的最小者。

直觉

“还没有推出”与“已经算完且推不出”是不同的信息。在可达关系刚开始计算时，许多实际可达的节点对尚未出现。如果立即把它们判成不可达，后续递归就会推翻先前的否定判断。

分层把这个时间问题变成依赖约束。计算 $R$ 时，可以不断使用新的 $R$ 事实；计算依赖 $\operatorname{not}R$ 的关系时， $R$ 必须已经稳定。此后一个否定测试就是对固定表的成员查询，不会因为本层添加事实而改变真假。本层因此重新成为正的、单调的计算。

SCC 则说明哪些关系必须一起完成。互相递归的关系属于同一分量，可以共同求正不动点；如果分量内含负边，就会出现“完成自己之前，必须先知道自己的最终缺失事实”的循环。把合法分量压缩后，剩下的 DAG 给出了先完成依赖、再读取其答案的顺序。

例子与边界

先求九个可达对，再求十六个不可达对

令输入为

\mathsf{Node}=\{a,b,c,d,e\},\qquad E=\{ab,bc,cb,cd\},

其中 $ab$ 简写有序对 $(a,b)$ ， $e$ 是孤立节点。使用三条安全规则：

\begin{aligned} R(x,y)&\leftarrow E(x,y),\\ R(x,z)&\leftarrow R(x,y),E(y,z),\\ NR(x,y)&\leftarrow\mathsf{Node}(x),\mathsf{Node}(y), \operatorname{not}R(x,y). \end{aligned}

依赖边为 $E\to R$ 、 $R\to R$ 、 $\mathsf{Node}\to NR$ 三条正边，以及 $R\to NR$ 一条负边。每个关系各自构成一个 SCC，唯一负边跨越分量。可取 EDB 在第 $0$ 层、 $R$ 在第 $1$ 层、 $NR$ 在第 $2$ 层。

第 $1$ 层沿用正 Datalog 的可达性计算。每轮都使用上一轮的累计事实，所得增量为：

轮次	新增 $R$ 事实	累计数量
1	$ab,bc,cb,cd$	4
2	$ac,bb,bd,cc$	8
3	$ad$	9
4	$\varnothing$	9

例如 $bb$ 的见证是 $b\to c\to b$ ， $ad$ 的见证是 $a\to b\to c\to d$ 。这一层稳定后，冻结

R_* =\{ab,ac,ad,bb,bc,bd,cb,cc,cd\}.

第 $2$ 层才检查否定。两个 $\mathsf{Node}$ 原子产生 $25$ 个候选对， $\operatorname{not}R$ 排除上述九对。因此第一轮加入的全部 $16$ 个 $NR$ 事实如下，第二轮没有新增：

起点 $x$	满足 $NR(x,y)$ 的全部终点 $y$	本行事实
$a$	$a,e$	$aa,ae$
$b$	$a,e$	$ba,be$
$c$	$a,e$	$ca,ce$
$d$	$a,b,c,d,e$	$da,db,dc,dd,de$
$e$	$a,b,c,d,e$	$ea,eb,ec,ed,ee$

这正是 $NR_*=(\mathsf{Node}\times\mathsf{Node})\setminus R_*$ 。 $e$ 虽未出现在边表里，仍参与所有候选对；因此节点范围必须由 $\mathsf{Node}$ 明确给出。

这里的 $R$ 表示正长度可达性。 $aa$ 不在 $R_*$ 中，而 $bb,cc$ 因环而在其中。若想让长度零的路径也算可达，应在第 $1$ 层增加 $R(x,x)\leftarrow\mathsf{Node}(x)$ ，然后重新求稳定关系。此时不可达表新删除的是 $aa,dd,ee$ 三对，答案共有 $16-3=13$ 对； $bb,cc$ 原本就不在不可达表内。

为什么不能同时累加两层

若从 $R=NR=\varnothing$ 开始，在每轮同时执行所有规则并保留全部旧事实，第一轮会因 $R(a,c)$ 尚不存在而加入 $NR(a,c)$ 。随后正递归推出 $R(a,c)$ ，但累加算子不会删除已经加入的 $NR(a,c)$ ，最终同时声称可达与不可达。

这个错误不会被“有限事实空间保证停止”修复。停止只说明不能再添加事实，并不保证此前否定测试的依据仍然成立。必须先算完 $R$ ，再建立 $NR$ 。

安全性也有独立作用。规则 $NR(x,y)\leftarrow\operatorname{not}R(x,y)$ 没有正体为 $x,y$ 提供范围；若任意扩大外部论域，就可能增加新的补集答案。两个 $\mathsf{Node}$ 守卫明确了补集相对于哪个有限集合计算。即便规则安全且可分层，整个查询也未必对输入单调：增加边 $E(a,e)$ 后，原答案 $NR(a,e)$ 会消失。

被选定的模型不等于经典最小模型

考虑无变量的安全程序

p()\leftarrow\operatorname{not}q(),\qquad q()\leftarrow q().

它可取 $q$ 在第 $0$ 层、 $p$ 在第 $1$ 层。 $q$ 的正自环没有种子，最小不动点为空；冻结这个结果后，否定成立，最终分层模型是 $\{p()\}$ 。

若仅把规则读成经典蕴含， $\{q()\}$ 也满足程序：第一条的前件为假，第二条是自蕴含。 $\{p()\}$ 与 $\{q()\}$ 都是删不掉事实的极小模型，但互不包含；空集又违反第一条，所以不存在包含在所有模型中的最小模型。分层语义通过先取较低层的最少事实，明确选择了前者。

再把第二条改成 $q()\leftarrow\operatorname{not}p()$ ，两个谓词就落在含负边的同一 SCC 内。分层要求同时有 $\sigma(q)<\sigma(p)$ 与 $\sigma(p)<\sigma(q)$ ，不可能成立。这表示本页的分层求值不适用，并不表示程序没有任何模型；稳定模型、良基语义采用其他定义来处理此类程序。

推论与应用

带符号 SCC 判据的两个方向

先假设有合法分层。沿任意正边，层号不下降；沿负边，层号严格增加。若某个有向圈包含负边，绕一圈就会从某个层号回到比它更大的自身，矛盾。因此合法分层排除了所有含负边的圈。

一条负边的两端属于同一 SCC，当且仅当从终点存在返回起点的路径；把这条边与返回路径连接，就得到含负边的圈。反过来，圈上的全部顶点互相可达，必在同一 SCC 中。所以无负圈条件等价于负边不在分量内部。

现在假设不存在分量内部的负边。收缩 SCC 得到 DAG，为分量间每条正边赋权 $0$ 、负边赋权 $1$ ；若同时存在两种边，就保留两条约束。令每个分量 $C$ 的层号为任意源分量到 $C$ 的路径权重之和的最大值，空路径权重为 $0$ 。DAG 中路径有限，最大值存在。对边 $C\to D$ ，把到 $C$ 的最大权路径接上该边，得到

\sigma(D)\geq\sigma(C)+w(C,D).

这满足所有跨分量正、负依赖约束；分量内部只有正边，统一层号也合法。EDB 没有入边，自动处于第 $0$ 层。于是确实构造出了分层。提取依赖图后，SCC 分解、内部负边检查与 DAG 最长权路径都可在 $O(p+e)$ 时间完成，其中 $p$ 是关系符号数， $e$ 是依赖边记录数。

固定较低层后，为什么得到唯一的最少扩展

设第 $k$ 层开始时， $M_{<k}$ 包含固定 EDB 与所有已完成的较低层 IDB；下标只限制 IDB，EDB 在第 $0$ 层开始前也已固定。把本层规则在 $A$ 上实例化。若某个 EDB 或较低层 IDB 正原子不在 $M_{<k}$ 中，或某个否定原子所否定的事实在 $M_{<k}$ 中，就丢弃该实例；其余实例中，删除已经满足的较低层文字和 EDB 文字。由于所有否定都严格跨层，剩下的是只涉及本层 IDB 的正规则，允许空体。

令 $C_k(M_{<k},X)$ 收集这些正规则在本层事实集 $X$ 上产生的头，并从空集迭代

X_0=\varnothing,\qquad X_{i+1}=X_i\cup C_k(M_{<k},X_i).

$M_{<k}$ 已冻结，所以改变 $X$ 不会改变任何否定测试；剩余正体又保证算子单调。令

H_k=\sum_{\substack{R\in\mathrm{IDB}\\\sigma(R)=k}} |A|^{\operatorname{arity}(R)}.

每次严格增长至少增加一个本层事实，因而至多有 $H_k$ 次严格增长，随后一次检查确认稳定。记稳定结果为 $X_*$ 。它闭合于所有剩余正规则，因此满足以本层为头的原规则：被丢弃实例的体为假，其余实例已经得到相应的头。

任取在同一 $M_{<k}$ 上满足本层规则的扩展 $Y$ 。由 $X_0\subseteq Y$ 出发，若 $X_i\subseteq Y$ ，正性和 $Y$ 的闭合性给出

X_{i+1}\subseteq Y\cup C_k(M_{<k},Y)=Y.

归纳得到 $X_*\subseteq Y$ 。所以这一层有唯一的、以既定低层结果为条件的最少扩展。把它加入 $M_{<k}$ 后继续下一层；高层事实不会改变已完成规则的体，有限层数遂给出终止且满足全程序的结果。

为什么改换合法分层不会改变答案

依赖图的 SCC 由程序本身确定。合法分层在每个 SCC 内必须恒定：两点间各有一条路径，层号沿路径不下降，两个方向合起来只能相等。每个 SCC 内部又只有正依赖，因此在它的所有前驱分量完成后，也能取唯一的条件最小不动点。

先考虑逐 SCC 求值。按凝聚 DAG 的拓扑序处理，某个分量只读取其前驱的结果。对拓扑序归纳，源分量的答案唯一，已有唯一前驱答案的分量也有唯一答案。没有依赖关系的分量互不读取，可以交换求值次序。因此逐 SCC 构造的最终结果不依赖所选拓扑序。

还需证明：把几个具有正依赖的 SCC 合在同一层一起饱和，不会改变这个结果。固定较低层后，设 $L$ 是整层正规则的最小模型， $K$ 是把该层 SCC 按前驱优先逐个取最小扩展的结果。 $K$ 满足整层规则，所以 $L\subseteq K$ 。

反向按这一层内部的拓扑序归纳。对源 SCC， $L$ 限制在该分量上的事实满足它的规则，故其最小答案 $K_C$ 包含于 $L_C$ 。对后续 SCC，假设 $K$ 的前驱答案都包含于 $L$ 的相应答案。本层分量之间只有正依赖，故在 $K$ 的前驱答案下成功的规则体，在 $L$ 的前驱答案下也成功。于是 $L_C$ 是当前条件下的一个闭合扩展，最小性再次给出 $K_C\subseteq L_C$ 。遍历完该层便得 $K\subseteq L$ ，所以 $K=L$ 。

每个合法层都能这样换成逐 SCC 求值，而逐 SCC 结果已经唯一。因此，合法的合层、拆层、重新编号或独立分量换序都不影响分层模型。唯一性来自条件最小性与依赖次序，不能简化成“随便找一个满足规则的解释”。

关系实现与固定程序的多项式上界

求值可以落到关系代数：正体用连接和选择产生候选元组，针对冻结的较低层关系用反连接筛掉命中项，再投影出头事实。例子中的反连接就是从 $\mathsf{Node}\times\mathsf{Node}$ 减去 $R_*$ 。同层递归仍可使用正 Datalog 的半朴素增量方法；跨层否定所读取的表必须已经完成。

设程序固定，每条规则至多有 $v$ 个变量，令 $N=\max(1,|A|)$ 。一轮至多检查 $O(N^v)$ 个赋值；在具有常数时间成员查询的索引模型下，每个赋值检查的文字数由固定程序界定。逐层使用上述直接迭代，得到时间与事实存储上界

O\!\left(|I|+\sum_k(H_k+1)N^v\right), \qquad O\!\left(|I|+\sum_kH_k\right).

这里可以逐个枚举实例，无需保存全部实例化规则。元数、变量数、关系符号数和层数均固定，所以两个界都是数据规模的多项式。 $N$ 的取法保证空载体时仍计入无变量规则的检查， $H_k$ 中则按 $|A|^0=1$ 计算零元事实。若程序也属于输入，元数与变量数不再固定，这个论证便不能推出联合复杂度为多项式。

参考资料

Oxford，Lecture 8: Datalog with Stratified Negation，第 8–17、21 张幻灯片：带符号依赖、分层求值、复杂度，以及被选定的分层模型与一般极小模型的区别。该讲义采用头到体的边方向；本文统一使用体到头的方向。
Markus Krötzsch，Modern Datalog: Concepts, Methods, Applications，Reasoning Web 2024/2025 联合论文集，§6，Definitions 29、31：安全否定、分层定义及按层计算。
T. C. Przymusinski，On the Relationship Between Logic Programming and Nonmonotonic Reasoning，AAAI 1988，pp. 444–448，§2，Definition 2.5、Theorem 2.6：体到头的依赖图、分层程序与唯一完美 Herbrand 模型。

形式陈述 ​

有限、安全的否定规则 ​

分层条件与语义终点 ​

先求九个可达对，再求十六个不可达对 ​

为什么不能同时累加两层 ​

被选定的模型不等于经典最小模型 ​

带符号 SCC 判据的两个方向 ​

固定较低层后，为什么得到唯一的最少扩展 ​

为什么改换合法分层不会改变答案 ​

关系实现与固定程序的多项式上界 ​

反向链接