我一直在尝试为Datalog程序实现半朴素评估的算法，但始终找不到一个简单明了的解释来说明它们的区别。

根据我的理解，朴素评估是一种自底向上的评估技术，半朴素评估也是如此。

在第一次迭代中，两种评估技术都从一个空集开始。

随着迭代的进行，两者最终都会进行迭代并生成元组，直到达到新的元组为止。

那么，半朴素评估是从规则的头部还是主体开始的呢？

path (X,Y) :- edge(X,Y).path (X,Y) :- edge(X,Z), path(Z,Y).

请问有人能解释一下在上述程序的每次迭代结束时，EDB和IDB是如何更新的吗？元组是存储在每个谓词下的吗？比如说，edge和path分别有一个单独的列，还是它们被存储为一个集合？

另外，全局统一和局部统一有什么区别？

回答：

在Datalog中，朴素评估和半朴素评估的区别在于，使用朴素实现时，每次迭代都会使用所有初始数据集（现有的EDB）加上新推断出的EDB。例如，如果你有如下IDB：

reachable(X,Y) :- link(X,Y).reachable(X,Y) :- link(X,Z), reachable(Z,Y).

以及一组EDB如下：link = {(a,b), (b,c), (c,c), (c,d)}执行评估的过程是：

1. 首先假设所有IDB关系为空。
2. 重复使用EDB和前一次的IDB来评估规则以获得新的IDB。
3. 当IDB没有变化时结束。

当使用朴素方法时，每一步你将有以下数据作为输入和输出：

 | Iteration |Input for the current iteration I_{i}            | New facts inferred           | |-----------|-------------------------------------------------|------------------------------| |  1        | {}                                              | {(a,b), (b,c), (c,c), (c,d)} | |  2        | {(a,b), (b,c), (c,c), (c,d)}                    | {(a,c),(b,c),(b,d),(c,d)}    | |  3        | {(a,b), (b,c), (c,c), (c,d), (a,c), (b,d)}      | {(a,d)}                      | |  4        | {(a,b), (b,c), (c,c), (c,d), (a,c), (b,d),(a,d)}| {}                           |

在第四次迭代时，你将停止，因为达到了不动点，无法推断出新的事实。然而，在半朴素方法中，你应用了一种优化，而不是在每次迭代中将所有推导出的 facts 作为规则的输入，而是只将之前迭代中已经学习到的元组发送到每次迭代中，以避免重复元组。

 | Iteration |Input for the current iteration I_{i}  | New facts inferred           | |-----------|---------------------------------------|------------------------------| |  1        | {}                                    | {(a,b), (b,c), (c,c), (c,d)} | |  2        | {(a,b), (b,c), (c,c), (c,d)}          | {(a,c),(b,c),(b,d),(c,d)}    | |  3        | {(a,c), (b,d)}                        | {(a,d)}                      | |  4        | {(a,d)}                               | {}                           |

来源：Datalog和递归查询处理