“对魔集改写后的同一查询 R(a,Y)，把答案关系写成 Q、需求关系写成 M。旧 IDB 有11条 Q 与5条 M。删除 E(a,b) 后，过删不只涉及 a 行答案，也会沿需求传播规则撤销 M…”
形式陈述
先问哪一部分答案值得计算
给出一张城市交通图，如果问题只是“从 a 能到哪里”，先算出所有城市之间的可达性往往做了无关工作。普通自底向上的规则求值看到输入边就开始推导，并不知道最终只会读取第一列为 a 的答案。魔集改写把这项查询需求也写成关系和规则，使自底向上的引擎能沿着需求计算。
输入是正 Datalog程序 P、有限 EDB 输入 I，以及一个固定的选择查询。程序没有函数项、否定、聚合、生成新值的算术或 SQL 的重复行语义；头变量都出现在正体中，EDB 不作规则头。原有空体常量事实、零元关系、重复变量和相互递归均允许。关系按集合解释。
查询指定一个 IDB 谓词 p、长度等于其元数的标记 α，以及各个 b 位置的常量值。标记中的 b 表示 bound，当前调用的这一列已经给定；f 表示 free，允许返回任意满足规则的值。例如 p 的标记 bf、绑定值 (a)，就是取 p 中第一列为 a 的所有完整元组。bb 是检查指定一对值是否成立，ff 则要求整个二元关系。
输出为新的正 Datalog 程序 Pᵐ 和一个带标记的答案谓词 pᵅ。对给定 I，原查询与新程序中相同绑定条件下的 pᵅ 答案相等。结论只针对这个查询，不要求新程序完整保留所有原 IDB 关系，也不保证改写后的运行时间或总内存一定更小。
绑定是沿规则体传播的
为每个用到的 pᵅ 建立需求谓词 mₚᵅ，其参数仅保留 α 的 b 位置，按原列顺序排列。pᵅ 本身仍保留全部参数。需求事实 mₚᵅ(a) 的意思是“需要第一列为 a 的 p 答案”，不是宣称任何 p(a,y) 已经成立。
从查询的谓词与标记出发，用待处理表遍历可达的带标记谓词。每个 (p,α) 只展开一次。处理一条头为 p(t) 的源规则时，把头的 b 位置中出现的变量加入已绑定集合 B；头和体中的常量本来就已知。然后严格从左到右处理体原子。
遇到 IDB 原子 q(u)，若某个参数是常量，或者它的变量已经在 B 中，就把相应位置标 b，否则标 f。给该调用生成 qᵝ，并安排以后展开 (q,β)。处理完任何体原子后，把该原子的全部变量加入 B，因为在一个成功的前缀匹配中，这些变量已经取得值。b 不是“在全程序中恒定”的性质，同一调用模式可以接受很多不同的绑定值。
这里采用的侧向信息传递策略是完整的左前缀：较早的 EDB 和 IDB 结果都可以给较晚调用提供绑定。规则体在声明语义中是合取，交换顺序不改变原查询；但它会改变这个策略生成的需求模式和计算工作。不能在生成标记时使用右侧尚未匹配的变量值。
实际生成哪些规则
设头的需求守卫为 g=mₚᵅ(t 的绑定列)，改写后的体为 A₁′,…,Aₖ′。其中 EDB 原子不变，IDB 原子换成刚求出的带标记版本。生成主规则
对体中第 j 个 IDB 调用 qᵝ(u)，另外生成需求传播规则
特别注意，右侧不包含第 j 个调用本身，也不包含后面的原子。要先提出请求，才可能得到那个调用的结果。若生成的是完全相同的一项自环 m(x)←m(x)，可以删除这条不会产生新事实的规则。
最后，把查询绑定写成一个空体需求事实，作为固定程序的一部分。所有新符号必须与源谓词分离。参考器以 @a: 和 @m: 开头编码答案与需求，源谓词只接受字母开头的字母数字下划线名字，因此不会撞名。没有任何 b 位置时，需求谓词是零元关系，唯一可能元组为 ()；不能把“没有绑定参数”误解为“无需种子”。
这些前缀匹配可直接用关系代数的连接与投影表达：前缀连接得到当时可用的变量值，再投影到下一调用的绑定列。参考器保留完整前缀，避免把引入的辅助列省略后错误拼接不同见证；实现可以进一步共享前缀，但那是另一个物理执行优化。
直觉
需求关系像一张待办单。起初只写“找出从 a 出发的答案”。处理规则时，如果发现要先知道某个中间点 y 的后续可达性，就把“从 y 出发”也写进待办单。待办单和真正答案都由同一个有限不动点引擎逐步增加，谁先有证据，谁就推动下一条规则。
这种方法仍然是自底向上求值。它没有偷偷改成遇到递归就不断调用自身的过程，也不依赖某次深度优先搜索幸运地绕开环。需求事实本身也按集合去重，因此重复提出同一个请求不会无限扩充状态。
例子与边界
两条源规则变成四条可执行规则
使用非线性的正长度可达性程序：
text
R(X,Y) <- E(X,Y)
R(X,Z) <- R(X,Y), R(Y,Z)查询 R(a,Y)，因此入口模式为 bf。第二条规则开始只有 X 已绑定。第一个 R(X,Y) 的模式是 bf；它成功后 Y 也已绑定，因此第二个 R(Y,Z) 同样为 bf，绑定值却来自前一个结果的 Y。若仅机械复制头的变量名 X，就会向第二个调用传错值。
把 Rᵇᶠ 简写为 Q，把 mᴿᵇᶠ 简写为 M，实际生成的是：
text
M(a) <-
Q(X,Y) <- M(X), E(X,Y)
M(Y) <- M(X), Q(X,Y)
Q(X,Z) <- M(X), Q(X,Y), Q(Y,Z)第一个递归调用本来还会生成 M(X)←M(X)，参考器省略它。第三条规则使用前一个 IDB 的成功结果来确定 Y，是本例的侧向绑定传播；删掉它会使很多后续路径无法完成。
输入九条边为 a→b、b→c、c→b、c→d、a→e、e→d，以及独立的 u→v→w→u。原程序得到20个 R 元组：a 行有 b、c、d、e；b、c 行各有 b、c、d；e 行有 d；u、v、w 三行各能到这三个节点。
新程序从 M(a) 开始，先得到 Q(a,b)、Q(a,e)，再提出 M(b)、M(e)。下一轮可得 Q(b,c)、Q(e,d)，随后得到 Q(a,c)、Q(a,d)，并提出 M(c)、M(d)。最后把 b↔c 的环闭合，稳定于5条需求 M(a)、M(b)、M(c)、M(d)、M(e)，以及11条 Q 事实。没有 M(u)、M(v)、M(w)，因而不生成那一分量的九条 Q。
最终查询答案仍是 (a,b)、(a,c)、(a,d)、(a,e)。这里总 IDB 从20变成16，16包括11条 Q 和5条 M，不能只报11而忽略新关系。EDB 的九条边仍全部存放在输入中；参考器甚至仍扫描关系行，所以“没有派生无关结果”并不等于“完全没有读过无关输入”。
参数位置可以交换
另有规则 P(X,Z)←E(X,Y),Q(Z,Y)，以及 Q(U,V)←F(U,V)。查询 P(a,Z) 的模式为 bf。E 匹配后 Y 已绑定，但 Z 未绑定，所以后一个 Q(Z,Y) 应为 fb，不是 bf。需求规则是 m_Qᶠᵇ(Y)←m_Pᵇᶠ(X),E(X,Y)。
取 E={(a,b)}，F={(c,b),(d,z)}，答案应为 P(a,c)。如果把位置写反，就可能请求 Q 的第一列为 b，错误漏掉 (c,b)。参考器输出逐调用标记、调用之前的已绑定变量以及完整前缀，可逐项核验这一步，而不是只看最终偶然相等的输出。
三条边界不能省略
若查询没有绑定，需求是 M()，仍需一个真零元种子。若删除这个种子，所有主规则的守卫都不成立，即使输入非空也可能返回空答案。若规则本身是常量事实 P(a)←，查询 P(z) 不能因“事实规则无条件”就返回 a；新规则的需求守卫仍需匹配头中的 a。
若头或体重复同一变量，例如 P(X,X)←E(X,Y)，原来的相等约束必须保留。标记记录哪些位置已知，不会替代同名变量必须取同值的条件。参考器按变量环境逐项匹配，而不是只检查参数数量。
魔集不保证只生成最终答案真正使用的事实。某条前缀已经成功，后续原子却可能失败，前缀提出的需求仍会保留。若查询要求全部关系，或图中所有节点本来都被需要，辅助需求关系可能增加成本。因此本页的保证是答案正确与有限终止，不是普遍加速定理。
推论与应用
为什么不会多答，也不会漏答
先证不会多答。取新程序中任一带标记答案事实的有限推导树，擦掉标记并忽略需求守卫。产生该事实的主规则对应一条源规则；其 EDB 叶子不变，体中的带标记答案按树高归纳都对应真实源事实。因此每个新答案事实都来自源最小模型。需求规则只能生成 M 类事实，不能凭空生成 Q 类答案。
完整性要比“新规则是旧规则加条件”多一步。证明更强的命题：若源事实 p(t) 有高度 h 的有限证明树，而且相应需求 mₚᵅ(t 的绑定列) 已在新最小模型中，那么 pᵅ(t) 也在其中。按 h 归纳。选出源证明根部使用的规则，从左到右看它的体。EDB 子事实已经可用；遇到 IDB 子事实时，较早的体事实已经由归纳得到，故需求传播规则能提出它所需的正确绑定。该子证明的高度小于 h，再用归纳得到带标记子答案。
所有体原子都得到后，带头需求守卫的主规则推出所需答案。空体事实是同一论证的基例。入口需求由种子提供，所以对每个符合查询常量的源答案都能应用这个命题。它同时解释为什么需求规则必须使用“前缀”，不能把尚未求出的被调用答案当成自己提出请求的前提。
有限性也可以直接界定。一个元数为 a 的谓词最多有 2ᵃ 个 b/f 模式，待处理表不会无限创造新模式。新程序仍是有限、安全、无函数的正程序；查询常量加入活跃域后，可能的地面事实数仍有限，因此既有 Datalog 求值保证继续适用。并不需要把一个可能有环的调用图强行展开成无穷树。
成本、保存范围与后续更新
改写规模可能随谓词元数指数增长；只展开从查询可达的模式可以减少实际输出，但不能消除最坏情形。若原规则长度总计 K、可达模式数为 A，参考器逐模式扫描原规则有 O(AK) 工作。把所有尝试生成的规则及复制前缀的总语法长度记为 G，构造与去重还需按该长度计费；逐调用已绑定变量以及最终 A 个标记的显示排序另外计算。这里按固定大小项的比较和平均常数时间哈希计费；长名字、长字符串和输出序列化不免费。不能仅以最终保留的规则条数衡量这份实现成本。
求值成本取决于生成后的程序与关系大小，不由“magic”这个名字限定。参考器为清晰使用普通同步不动点：每轮重新匹配规则，候选元组去重后加入。它还为每次规则匹配重建并排序关系索引。输出的 row_tests 只统计尝试匹配的关系行，未包含索引、排序、集合与 JSON 显示，因而不是总运行时间。主例原程序852次行尝试，新程序811次；这只是这份输入和这份实现的实测计数。
若输入后来删除一条边，可以对生成后的整个正程序使用删除与重推。必须一起维护需求和答案关系：某个请求可能只因一条后来被删的路径才存在，不能把旧 M 表永远冻结。查询种子、规则或绑定值改变则是另一种更新，本页终点只承诺固定查询下的 EDB 更新。
可执行终点要求交出真正生成的四条规则、每轮需求与答案的差异、fb 参数交换、零元种子及原查询对照。接着删除 a→b，完整观察哪些旧需求失效，以及替代路径怎样恢复仍应保留的答案。
参考资料
- François Bancilhon、Raghu Ramakrishnan，An Amateur's Introduction to Recursive Query Processing Strategies，SIGMOD1986，§3.3.3，印刷页34–35：原作者给出的标记、需求规则与守卫说明。本页明确选用完整左前缀策略，不将该文较早的绑定传播规则冒充完全相同的实现
- Serge Abiteboul、Richard Hull、Victor Vianu，Foundations of Databases，第13章，1995，§§13.2–13.3，印刷页318–327：侧向信息传递、带标记调用、需求和辅助前缀、查询等价定理。本页直接保存前缀而不另外物化每个辅助关系，并独立证明所用变体