6

因此，我试图了解 Datalog 的工作原理，它与 Prolog 之间的区别之一是它在否定和递归上具有分层限制。引用维基百科：

如果谓词 P 是从谓词 Q 正派生的（即 P 是规则的头部，并且 Q 正出现在同一规则的主体中），则 P 的分层数必须大于或等于分层Q的数量

如果谓词 P 是从否定谓词 Q 派生的（即 P 是规则的头部，并且 Q 否定出现在同一规则的主体中），则 P 的分层数必须大于 Q 的分层数,

因此，这样下去，以下两个谓词不会导致分层错误，因为它们可以简单地分配相同的分层编号。所以这些谓词很好，尽管有循环定义。

  1. A(x) :- B(x)
  2. B(x) :- A(x)

但是，如果我们有一个包含一些否定的定义（其中〜是否定），则会发生什么对比

  1. A(x) :- ~ B(x)
  2. B(x) :- ~ A(x)

在这里分层是不可能的。A(x,y) 的分层数必须大于 B(x,y)，B(x,y) 的分层数必须大于 A(x,y)。我的第一个想法是这不好，因为这是一个循环定义，但只要谓词不被否定，分层就可以循环。但为什么？真值只是二进制的。以这种方式对具有否定符号的公式进行不同的处理似乎是非常武断的。在第二种情况下，这种分层试图防止在第一种情况下是什么？

4

1 回答 1

7

我认为问题在于：

A(x) :- \+ B(x)

B(x) :- \+ A(x)

...是它具有模棱两可的语义。该程序有两个最小模型，{A(x)}和{B(x)}，因此在不动点语义（无不动点）或模型理论语义（无唯一最小模型）下定义不明确。

为了解决这个问题， Datalog 的分层语义对 Datalog 程序的语法施加了限制，这样，如果程序存在分层，那么它在不动点和模型理论语义中也将具有唯一的最小模型（反之亦然，我相信）。

您可以在“数据库基础”一文中找到更多关于 Datalog 分层语义的详细信息，该文本恰好可以在线免费获得，相关细节在第 15 章。这篇优秀的文章还解释了我在上面使用的大多数其他术语，如模型、定点等，如果你被卡住了。

于 2012-09-18T05:25:35.240 回答