prolog - 数据记录分层

Question

所以我试图理解 Datalog 是如何工作的，它和 Prolog 之间的区别之一是它对否定和递归有分层限制。引用维基百科:

If a predicate P is positively derived from a predicate Q (i.e., P is the head of a rule, and Q occurs positively in the body of the same rule), then the stratification number of P must be greater than or equal to the stratification number of Q

If a predicate P is derived from a negated predicate Q (i.e., P is the head of a rule, and Q occurs negatively in the body of the same rule), then the stratification number of P must be greater than the stratification number of 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)

...它的语义不明确。该程序有两个最小模型，即{A(x)}和{B(x)}，因此不太好-在定点语义(无定点)或模型理论语义(无唯一最小模型)下定义。

为了解决这个问题，Datalog 的分层语义对 Datalog 程序的语法施加了限制，如果程序存在分层，那么它将在定点和模型理论语义方面也有一个独特的、最小的模型(我相信反之亦然)。

您可以在文本“Serge Abiteboul、Richard Hull 和 Victor Vianu 的数据库基础”中找到有关 Datalog 分层语义的更多详细信息，该文本恰好可以免费获取 online ，相关详细信息见 Chapter 15 。如果您遇到困难，这篇优秀的文字还解释了我上面使用的大多数其他术语，例如模型、定点等。