8

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

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

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

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

所以半天真从规则的头部或主体开始？

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

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

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

全球统一和地方统一有什么区别？

4

2 回答 2

9

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

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

于 2018-04-04T15:49:07.137 回答
3

我将告诉你有关 Prolog 的信息。我不知道它是否同样适用于 Datalog，所以如果我错了，就必须有人纠正我。

所以半天真从规则的头部或主体开始？

根据这个讲义，您可以继续使用基于变量或基于元组的算法，但在这两种情况下，您都从主体开始，只有在它成功后，您才添加一个表示头部的元组：

基于变量：考虑对主体变量的所有可能分配。如果赋值使主体为真，则将头部的元组添加到结果中。

基于元组：考虑来自非否定关系子目标的所有元组分配。如果赋值使主体为真，则将头部的元组添加到结果中。

这与我对 Prolog 和反向链接的了解非常吻合：你想总结头部，所以你必须首先证明身体。

你似乎也在问半天真的是否有话要说，你是从头开始还是从身体开始。根据我今天所回顾的内容，在我看来，半天真是对天真的算法的一种扭曲，而不是一个全新的事物。这就像天真的方法的桌面版本；如果有多种幼稚方法，那么您将拥有同样多的半幼稚方法。如果只有一个天真，就只有一个半天真。

有人可以解释一下 EDB 和 IDB 如何在上述程序的每次迭代结束时更新。

这很容易：他们没有。EDB 是数据库中的一组事实。IDB 是数据库中的一组规则。查询只是一个查询，它不会修改数据库。查询返回的元组是另一回事。

元组是否存储在每个谓词下？

在 EDB 中表示事实的元组已经作为事实存储在 EDB 中。从 IDB 中的规则派生的元组被计算并成为结果集的一部分并且不被存储。在这两种情况下，存储都不会因执行查询而更新。

如果我们在这里谈论 Prolog，就会有这样的递归调用堆栈。最外面的电话可能会说path(a, z)；在那个调用里面可能是这样的edge(a, b), path(b, z)，它会产生一个调用edge(b, c), path(c, z)。用 Prolog 术语来说，每次你输入另一个调用时，你都会得到一组新的变量，有些是绑定的，有些是尚未绑定的。在您的 Datalog 世界中，在我看来，edge(a,b)并且edge(b,c)已经作为元组存在于您的 EDB 中。在查询期间，它们将成为表示您的结果的元组堆栈中元组的一部分。IDB 包含一个名为 的规则path/2，一旦满足递归调用，您将得到一些新的元组，就像path(a,z)结果中一样。但是那个结果元组不是存储在您的 EDB 中的事实（它只包含像edge/2) 也不会取代规则path/2。这只是查询结果的一部分。

全球统一和地方统一有什么区别？

我无法使用这些术语找到任何东西，我无法想象它们的含义。

所以，这是我的猜测。让我们看看我的标记有多宽。

于 2017-11-01T04:26:41.300 回答