从Datalog到SQL的转换

Question

我仍在思考如何将Datalog程序的递归转换为SQL，例如

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

A/1EDB谓词在哪里。这与P和之间存在相互依赖关系Q。对于较长的查询，该如何解决？

而且，有没有什么系统可以完全实现翻译？如果有，我可以知道我要使用的系统或论文吗？

Answer 1

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

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

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

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

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

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

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