我仍在思考如何将Datalog程序的递归性翻译成SQL,例如
P(x,y) <- Q(x,y).
Q(x,y) <- P(x,z), A(y).
其中 A/1
是一个EDB谓词。因此,P
和Q
之间存在相互依赖关系。对于较长的查询,如何解决这个问题?
此外,是否有任何系统完全实现了翻译?如果有,我可以知道是哪个系统或者可以参考哪篇论文吗?
我仍在思考如何将Datalog程序的递归性翻译成SQL,例如
P(x,y) <- Q(x,y).
Q(x,y) <- P(x,z), A(y).
其中 A/1
是一个EDB谓词。因此,P
和Q
之间存在相互依赖关系。对于较长的查询,如何解决这个问题?
此外,是否有任何系统完全实现了翻译?如果有,我可以知道是哪个系统或者可以参考哪篇论文吗?
如果您采用“表格化”以前的结论并在此基础上进行前向推理来推断新的结论的方法,则不需要递归“深度”。
请记住,Datalog对规则和变量有一些限制,以确保有限终止和因此有限的结论。例如,变量必须具有有限的可能值范围。
让我们假设您的示例是指常量而不是变量:
P(x,y) <- Q(x,y).
Q(x,y) <- P(x,z), A(y).
A/1
实现为扩展存储过程或外部代码。为此,我建议将调用所有可能参数(有限多个)上的A
的结果进行制表。毕竟,这些都是您系统中的结论(可证明的陈述)之一。A
事实被引证后,证明停止,因为没有足够的结论来应用任何规则以获得新的结论。A/1
这样的“终端”谓词实现为外部代码,则会将其处理为简单事实,即存储在所有可能输入上调用它们时的任何成功结果(请记住,在Datalog中,任何变量的范围都是有限的)。因此,这个“皱纹”可以简化为标准的Datalog事实和规则。 - hardmath