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

Question

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

根据我的理解，天真是一种自下而上的评估技术，半天真也是。

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

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

那么半幼稚是从规则的头还是身体开始的？

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)} 执行评估的过程是：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)}| {}                           |

在第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)}                               | {}                           |

来源：数据记录和递归查询处理