形式陈述
有限、安全的否定规则
正 Datalog理路Datalog 与有限最小不动点Datalog · Positive Datalog · Datalog least model在固定有限活跃域上反复应用正规则,证明所得关系是最小模型,并用有环可达性逐轮推导半朴素求值。从空关系反复添加有规则见证的事实,得到有限最小不动点。若要查询“哪些节点对不可达”,还需要判断某个事实最终没有被推出。分层否定的做法是先完成被查询关系,再允许后续规则读取它的补集。
固定有限、无函数符号的程序 与有限输入数据库 。规则形如
项只有变量与常量;不同常量名表示不同值。规则中每个变量都必须出现在至少一个正关系体原子里,包括出现在头或否定原子里的变量。这一安全性条件给变量提供取值范围。允许无变量的事实与零元规则。EDB 是始终固定的输入关系,不出现在规则头中;IDB 是规则定义的关系。关系按集合解释,不含重复行、NULL、聚合或生成新值的运算。
求值载体取
规则变量只需枚举 中的值。无变量规则有唯一的空赋值;即使 ,仍约定 ,所以零元关系可以成立。这并不要求外部一阶论域为空:安全性保证额外加入未使用的值不会为正体提供新的匹配。
分层条件与语义终点
分层是给每个关系符号指定非负整数 ,使每条规则满足
EDB 放在第 层。IDB 也可在第 层;此时求值仍把 EDB 当作已知输入,只有 IDB 从空关系开始。正依赖允许同层递归,负依赖必须指向已经完成的较低层。
建立带符号依赖图:顶点是关系符号,边从规则体关系指向头关系;正体产生正边,否定体产生负边。同一对顶点可以同时有正边与负边。下列三项等价:程序存在分层;依赖图没有包含负边的有向圈;每条负边的两端都属于不同的强连通分量理路强连通分量算法Strongly connected components algorithm在线性时间内把有向图划分为互相可达的极大顶点集合。。
在此条件下,按层递增求值,每层都在固定较低层答案后取本层的正 Datalog 最小不动点。有限求值必定终止,结果满足全部规则,且不依赖合法分层的选择。这个被选定的解释称为分层模型;在这里的有限设置中,它与文献中的唯一完美模型(perfect model)一致。后文证明逐层构造及其分层无关性;与完美模型偏好定义的对应见 Przymusinski 的原始论文。这里的唯一性不表示所有经典模型中存在按集合包含的最小者。
直觉
“还没有推出”与“已经算完且推不出”是不同的信息。在可达关系刚开始计算时,许多实际可达的节点对尚未出现。如果立即把它们判成不可达,后续递归就会推翻先前的否定判断。
分层把这个时间问题变成依赖约束。计算 时,可以不断使用新的 事实;计算依赖 的关系时, 必须已经稳定。此后一个否定测试就是对固定表的成员查询,不会因为本层添加事实而改变真假。本层因此重新成为正的、单调的计算。
SCC 则说明哪些关系必须一起完成。互相递归的关系属于同一分量,可以共同求正不动点;如果分量内含负边,就会出现“完成自己之前,必须先知道自己的最终缺失事实”的循环。把合法分量压缩后,剩下的 DAG 给出了先完成依赖、再读取其答案的顺序。
例子与边界
先求九个可达对,再求十六个不可达对
令输入为
其中 简写有序对 , 是孤立节点。使用三条安全规则:
依赖边为 、、 三条正边,以及 一条负边。每个关系各自构成一个 SCC,唯一负边跨越分量。可取 EDB 在第 层、 在第 层、 在第 层。
第 层沿用正 Datalog 的可达性计算。每轮都使用上一轮的累计事实,所得增量为:
| 轮次 |
新增 事实 |
累计数量 |
| 1 |
|
4 |
| 2 |
|
8 |
| 3 |
|
9 |
| 4 |
|
9 |
例如 的见证是 , 的见证是 。这一层稳定后,冻结
第 层才检查否定。两个 原子产生 个候选对, 排除上述九对。因此第一轮加入的全部 个 事实如下,第二轮没有新增:
| 起点 |
满足 的全部终点 |
本行事实 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
这正是 。 虽未出现在边表里,仍参与所有候选对;因此节点范围必须由 明确给出。
这里的 表示正长度可达性。 不在 中,而 因环而在其中。若想让长度零的路径也算可达,应在第 层增加 ,然后重新求稳定关系。此时不可达表新删除的是 三对,答案共有 对; 原本就不在不可达表内。
为什么不能同时累加两层
若从 开始,在每轮同时执行所有规则并保留全部旧事实,第一轮会因 尚不存在而加入 。随后正递归推出 ,但累加算子不会删除已经加入的 ,最终同时声称可达与不可达。
这个错误不会被“有限事实空间保证停止”修复。停止只说明不能再添加事实,并不保证此前否定测试的依据仍然成立。必须先算完 ,再建立 。
安全性也有独立作用。规则 没有正体为 提供范围;若任意扩大外部论域,就可能增加新的补集答案。两个 守卫明确了补集相对于哪个有限集合计算。即便规则安全且可分层,整个查询也未必对输入单调:增加边 后,原答案 会消失。
被选定的模型不等于经典最小模型
考虑无变量的安全程序
它可取 在第 层、 在第 层。 的正自环没有种子,最小不动点为空;冻结这个结果后,否定成立,最终分层模型是 。
若仅把规则读成经典蕴含, 也满足程序:第一条的前件为假,第二条是自蕴含。 与 都是删不掉事实的极小模型,但互不包含;空集又违反第一条,所以不存在包含在所有模型中的最小模型。分层语义通过先取较低层的最少事实,明确选择了前者。
再把第二条改成 ,两个谓词就落在含负边的同一 SCC 内。分层要求同时有 与 ,不可能成立。这表示本页的分层求值不适用,并不表示程序没有任何模型;稳定模型、良基语义采用其他定义来处理此类程序。
推论与应用
带符号 SCC 判据的两个方向
先假设有合法分层。沿任意正边,层号不下降;沿负边,层号严格增加。若某个有向圈包含负边,绕一圈就会从某个层号回到比它更大的自身,矛盾。因此合法分层排除了所有含负边的圈。
一条负边的两端属于同一 SCC,当且仅当从终点存在返回起点的路径;把这条边与返回路径连接,就得到含负边的圈。反过来,圈上的全部顶点互相可达,必在同一 SCC 中。所以无负圈条件等价于负边不在分量内部。
现在假设不存在分量内部的负边。收缩 SCC 得到 DAG,为分量间每条正边赋权 、负边赋权 ;若同时存在两种边,就保留两条约束。令每个分量 的层号为任意源分量到 的路径权重之和的最大值,空路径权重为 。DAG 中路径有限,最大值存在。对边 ,把到 的最大权路径接上该边,得到
这满足所有跨分量正、负依赖约束;分量内部只有正边,统一层号也合法。EDB 没有入边,自动处于第 层。于是确实构造出了分层。提取依赖图后,SCC 分解、内部负边检查与 DAG 最长权路径都可在 时间完成,其中 是关系符号数, 是依赖边记录数。
固定较低层后,为什么得到唯一的最少扩展
设第 层开始时, 包含固定 EDB 与所有已完成的较低层 IDB;下标只限制 IDB,EDB 在第 层开始前也已固定。把本层规则在 上实例化。若某个 EDB 或较低层 IDB 正原子不在 中,或某个否定原子所否定的事实在 中,就丢弃该实例;其余实例中,删除已经满足的较低层文字和 EDB 文字。由于所有否定都严格跨层,剩下的是只涉及本层 IDB 的正规则,允许空体。
令 收集这些正规则在本层事实集 上产生的头,并从空集迭代
已冻结,所以改变 不会改变任何否定测试;剩余正体又保证算子单调。令
每次严格增长至少增加一个本层事实,因而至多有 次严格增长,随后一次检查确认稳定。记稳定结果为 。它闭合于所有剩余正规则,因此满足以本层为头的原规则:被丢弃实例的体为假,其余实例已经得到相应的头。
任取在同一 上满足本层规则的扩展 。由 出发,若 ,正性和 的闭合性给出
归纳得到 。所以这一层有唯一的、以既定低层结果为条件的最少扩展。把它加入 后继续下一层;高层事实不会改变已完成规则的体,有限层数遂给出终止且满足全程序的结果。
为什么改换合法分层不会改变答案
依赖图的 SCC 由程序本身确定。合法分层在每个 SCC 内必须恒定:两点间各有一条路径,层号沿路径不下降,两个方向合起来只能相等。每个 SCC 内部又只有正依赖,因此在它的所有前驱分量完成后,也能取唯一的条件最小不动点。
先考虑逐 SCC 求值。按凝聚 DAG 的拓扑序处理,某个分量只读取其前驱的结果。对拓扑序归纳,源分量的答案唯一,已有唯一前驱答案的分量也有唯一答案。没有依赖关系的分量互不读取,可以交换求值次序。因此逐 SCC 构造的最终结果不依赖所选拓扑序。
还需证明:把几个具有正依赖的 SCC 合在同一层一起饱和,不会改变这个结果。固定较低层后,设 是整层正规则的最小模型, 是把该层 SCC 按前驱优先逐个取最小扩展的结果。 满足整层规则,所以 。
反向按这一层内部的拓扑序归纳。对源 SCC, 限制在该分量上的事实满足它的规则,故其最小答案 包含于 。对后续 SCC,假设 的前驱答案都包含于 的相应答案。本层分量之间只有正依赖,故在 的前驱答案下成功的规则体,在 的前驱答案下也成功。于是 是当前条件下的一个闭合扩展,最小性再次给出 。遍历完该层便得 ,所以 。
每个合法层都能这样换成逐 SCC 求值,而逐 SCC 结果已经唯一。因此,合法的合层、拆层、重新编号或独立分量换序都不影响分层模型。唯一性来自条件最小性与依赖次序,不能简化成“随便找一个满足规则的解释”。
关系实现与固定程序的多项式上界
求值可以落到关系代数理路关系代数Relational algebra · Set relational algebra用选择、投影、积、重命名与集合运算组合有限关系查询,并在集合语义下解释连接和存在见证。:正体用连接和选择产生候选元组,针对冻结的较低层关系用反连接筛掉命中项,再投影出头事实。例子中的反连接就是从 减去 。同层递归仍可使用正 Datalog 的半朴素增量方法;跨层否定所读取的表必须已经完成。
设程序固定,每条规则至多有 个变量,令 。一轮至多检查 个赋值;在具有常数时间成员查询的索引模型下,每个赋值检查的文字数由固定程序界定。逐层使用上述直接迭代,得到时间与事实存储上界
这里可以逐个枚举实例,无需保存全部实例化规则。元数、变量数、关系符号数和层数均固定,所以两个界都是数据规模的多项式。 的取法保证空载体时仍计入无变量规则的检查, 中则按 计算零元事实。若程序也属于输入,元数与变量数不再固定,这个论证便不能推出联合复杂度为多项式。
参考资料