天真和半天真的评估有什么区别？
What is the difference between naive and semi naive evaluation?
我一直在尝试实现一种算法来对数据记录程序进行半朴素的评估，但无法在任何地方得到一个简单的答案来解释差异。
根据我的理解，naive 是一种自下而上的评估技术，因此是 semi-naive。
在第一次迭代中，两种评估技术都从一个空集开始。
随着迭代的进一步进行，最终都会有迭代并产生元组，直到达到一个新的元组。
所以半天真者是从规则的头部还是主体开始的？
path (X,Y):- edge(X,Y).
path (X,Y):- edge(X,Z),path (Z,Y).
有人可以解释一下 EDB 和 IDB 在上述程序的每次迭代结束时是如何更新的吗？是存储在每个谓词下的元组。就像边缘的单独列和路径的单独列一样，或者它们被存储为一个集合。
还有全球统一和本地统一有什么区别？
我将向您介绍 Prolog。我不知道它是否同样适用于 Datalog，所以如果我错了，有人会纠正我。
So the semi-naive starts from head or body of the rule?
根据 this handout，您可以继续使用 variable-based 或 tuple-based 算法，但在这两种情况下，您都从 body 开始，并且只有在它成功之后你添加一个代表头部的元组吗：
Variable-based: Consider all possible assignments to the variable of the body. If the assignment makes the body true, add the tuple for the head to the result.
Tuple-based: Consider all assignments of tuples from the nonnegated relational subgoals. If the assignment makes the body true, add the tuple for the head to the result.
这与我对 Prolog 和 backward-chaining 的了解很吻合：你想得出结论，所以你必须先证明 body。
你似乎也在问semi-naive是否有关于你是从头开始还是从body开始的说法。根据我今天的评论，在我看来 semi-naive 是对朴素算法的一种扭曲，而不是一个全新的东西。这就像天真的方法的表格版本；如果有多种朴素的方法，那么您将有同样多的 semi-naive 方法。如果只有一个天真，那就只有一个semi-naive.
Can someone please explain how the EDB and IDB gets updated at the end of each iteration for the above program.
这很简单：他们没有。 EDB 是数据库中的事实集。 IDB 是数据库中的一组规则。查询只是一个查询，它不会修改数据库。查询的元组returns另当别论。
Are the tuples stored under each predicate?
EDB 中表示事实的元组已作为事实存储在 EDB 中。从 IDB 中的规则派生的元组被计算并成为结果集的一部分，并且不被存储。在这两种情况下，商店都不会因执行查询而更新。
如果我们在这里谈论 Prolog，就会有一堆递归调用在进行。最外层的调用可能会说 path(a, z)；在那个调用中可能是类似 edge(a, b), path(b, z) 的东西，它会引发一个调用 edge(b, c), path(c, z)。在 Prolog 术语中，每次您输入另一个调用时，您都会得到一组新的变量，有些是绑定的，有些是 yet-to-be-bound。在您的 Datalog 世界中，在我看来 edge(a,b) 和 edge(b,c) 已经作为元组存在于您的 EDB 中。在查询期间，它们将成为代表您的结果的元组堆栈中元组的一部分。 IDB 包含一个名为 path/2 的规则，一旦您满足递归调用，您将在结果中得到一些新的元组，例如 path(a,z)。但是结果元组不是存储在您的 EDB 中的事实（它只包含 edge/2 之类的事实），也不会替换规则 path/2。这只是您查询结果的一部分。
Also what is the difference between global and local unification?
我无法使用这些术语找到任何内容，我无法想象它们的含义。
所以，这是我的猜测。让我们看看我的分数有多高。
Datalog 中朴素和 semi-naîve 评估之间的区别在于，当您使用朴素实现进行评估时，您将所有初始数据集（现有 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 次迭代时，您将停止，因为已达到 固定点，并且无法推断出新的事实。
但是，在 semi-naïve 方法中，您应用优化，而不是在每次迭代中使用所有派生事实作为规则的输入，可以仅向每次迭代发送在先前迭代中已经学习的元组，以避免重复元组。
| 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)} | {} |
我一直在尝试实现一种算法来对数据记录程序进行半朴素的评估，但无法在任何地方得到一个简单的答案来解释差异。
根据我的理解，naive 是一种自下而上的评估技术，因此是 semi-naive。
在第一次迭代中，两种评估技术都从一个空集开始。
随着迭代的进一步进行，最终都会有迭代并产生元组，直到达到一个新的元组。
所以半天真者是从规则的头部还是主体开始的？
path (X,Y):- edge(X,Y).
path (X,Y):- edge(X,Z),path (Z,Y).
有人可以解释一下 EDB 和 IDB 在上述程序的每次迭代结束时是如何更新的吗？是存储在每个谓词下的元组。就像边缘的单独列和路径的单独列一样，或者它们被存储为一个集合。
还有全球统一和本地统一有什么区别？
我将向您介绍 Prolog。我不知道它是否同样适用于 Datalog，所以如果我错了，有人会纠正我。
So the semi-naive starts from head or body of the rule?
根据 this handout，您可以继续使用 variable-based 或 tuple-based 算法，但在这两种情况下，您都从 body 开始，并且只有在它成功之后你添加一个代表头部的元组吗：
Variable-based: Consider all possible assignments to the variable of the body. If the assignment makes the body true, add the tuple for the head to the result.
Tuple-based: Consider all assignments of tuples from the nonnegated relational subgoals. If the assignment makes the body true, add the tuple for the head to the result.
这与我对 Prolog 和 backward-chaining 的了解很吻合：你想得出结论，所以你必须先证明 body。
你似乎也在问semi-naive是否有关于你是从头开始还是从body开始的说法。根据我今天的评论，在我看来 semi-naive 是对朴素算法的一种扭曲，而不是一个全新的东西。这就像天真的方法的表格版本；如果有多种朴素的方法，那么您将有同样多的 semi-naive 方法。如果只有一个天真，那就只有一个semi-naive.
Can someone please explain how the EDB and IDB gets updated at the end of each iteration for the above program.
这很简单：他们没有。 EDB 是数据库中的事实集。 IDB 是数据库中的一组规则。查询只是一个查询，它不会修改数据库。查询的元组returns另当别论。
Are the tuples stored under each predicate?
EDB 中表示事实的元组已作为事实存储在 EDB 中。从 IDB 中的规则派生的元组被计算并成为结果集的一部分，并且不被存储。在这两种情况下，商店都不会因执行查询而更新。
如果我们在这里谈论 Prolog，就会有一堆递归调用在进行。最外层的调用可能会说 path(a, z)；在那个调用中可能是类似 edge(a, b), path(b, z) 的东西，它会引发一个调用 edge(b, c), path(c, z)。在 Prolog 术语中，每次您输入另一个调用时，您都会得到一组新的变量，有些是绑定的，有些是 yet-to-be-bound。在您的 Datalog 世界中，在我看来 edge(a,b) 和 edge(b,c) 已经作为元组存在于您的 EDB 中。在查询期间，它们将成为代表您的结果的元组堆栈中元组的一部分。 IDB 包含一个名为 path/2 的规则，一旦您满足递归调用，您将在结果中得到一些新的元组，例如 path(a,z)。但是结果元组不是存储在您的 EDB 中的事实（它只包含 edge/2 之类的事实），也不会替换规则 path/2。这只是您查询结果的一部分。
Also what is the difference between global and local unification?
我无法使用这些术语找到任何内容，我无法想象它们的含义。
所以，这是我的猜测。让我们看看我的分数有多高。
Datalog 中朴素和 semi-naîve 评估之间的区别在于，当您使用朴素实现进行评估时，您将所有初始数据集（现有 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 次迭代时，您将停止，因为已达到 固定点，并且无法推断出新的事实。 但是，在 semi-naïve 方法中，您应用优化，而不是在每次迭代中使用所有派生事实作为规则的输入，可以仅向每次迭代发送在先前迭代中已经学习的元组，以避免重复元组。
| 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)} | {} |