数据记录分层

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)

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

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

您可以在"Abzenboul,Richard Hull和Victor Vianu的数据库基础"一文中找到有关Datalog的分层语义的详细信息,这些内容恰好可以在线免费获得,第15章中的相关细节.这篇优秀的文字还解释了我上面使用的大多数其他术语,如模型,定点等,如果你被卡住了.