数据分层

Question

因此，我试图了解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)的分层数。我的第一个想法是，这是不好的，因为这是一个循环的定义，但分层与循环，只要谓词没有被否定。但是为什么呢？真值只是二进制的。以这种方式以不同的方式对待具有否定符号的公式似乎是极其武断的。在第二种情况下，不是在第一种情况下，这种分层试图阻止什么？

Answer 1

我认为问题在于：

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

...is表示它有模糊的语义。该程序有两个最小模型，即{A(x)}和{B(x)}，因此在不动点语义(无不动点)或模型理论语义(无唯一最小模型)下没有很好的定义。

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

您可以在“Serge、Richard和Victor Vianu的数据库基础”文本中找到更多关于Datalog分层语义的详细信息，该文本恰好是免费提供的在线，并在第15章中提供了相关细节。这篇优秀的文章还解释了我在上面使用过的大多数术语，如模型、定点等等。