prolog - 天真和半天真评估有什么区别？

Question

我一直在尝试实现一种算法来对数据记录程序进行半天真的评估，但在任何地方都无法得到一个直接的答案来解释简单单词的差异。

根据我的理解，naive 是一种自下而上的评估技术，因此是半幼稚的。

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

随着迭代的进一步进行，最终都会进行迭代并生成元组，直到达到新的元组。

那么半天真的是从规则的头部还是主体开始呢？

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

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

有人可以解释一下在上述程序的每次迭代结束时 EDB 和 IDB 是如何更新的。是存储在每个谓词下的元组。就像一个单独的边缘列和一个单独的路径列，或者它们被存储为一个集合。

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

Answer 1

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)}执行评估的程序是:

首先假设所有 IDB 关系都是空的。

使用 EDB 和之前的 IDB 重复评估规则以获得新的 IDB。

当 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)}| {}                           |

在第 4 次迭代时，您将停止，因为 定位点 已达成，并且无法推断出新的事实。
然而，在半朴素的方法中，您应用优化，而不是在每次迭代时使用所有派生事实作为规则的输入，可以仅将先前迭代中已经学习的元组发送到每次迭代，以避免重复元组。

 | 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 and Recursive Query Processing