sql - 从 Datalog 到 SQL 的翻译

Question

我还在思考如何将Datalog程序的递归性转化为SQL，比如

P(x,y) <- Q(x,y).
Q(x,y) <- P(x,z), A(y).

其中 A/1 是 EDB 谓词。 P 和 Q 之间存在相互依赖性。对于较长的查询，如何解决这个问题？

另外，有没有系统可以完全实现翻译？如果有的话，请问可以引用什么系统或者论文？

Answer 1

如果采用“列出”先前结论并对其进行前向链推理来推断新结论的方法，则不需要递归“深度”。

请记住，Datalog 需要对规则和变量进行一些限制，以确保有限终止，从而确保有限的多个结论。例如，变量必须具有有限范围的可能值。

假设您的示例引用的是常量而不是变量:

P(x,y) <- Q(x,y).
Q(x,y) <- P(x,z), A(y).

一个问题是您希望将 A/1 实现为扩展存储过程或外部代码。为此，我建议列出对所有可能的参数(有限多个)调用 A 的所有结果。毕竟，这些都是您的系统的结论(可证明的陈述)。

一旦完成，前向链接推理就会迭代而不是递归地进行。在每一步中考虑每条规则，将其与先前获得(列出)结论的前提(右侧)一起应用，如果它产生新的结论。如果当前步骤中没有规则产生新结论，则停止。证明程序已完成。

在您的示例中，在提出所有 A 事实后，证明就会停止，因为没有足以应用任一规则来得出新结论的结论。