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事实后停止，因为没有足够的结论来应用这两条规则中的任何一条来获得新的结论。

Answer 2

一种可能的方法是在SQL中使用递归CTE，它提供了传递闭包的功能。关系代数+传递闭包= Datalog。

Answer 3

Logica做了这样的事情。它将类似数据记录的语言翻译成Google BigQuery、PostgreSQL和SQLite的SQL。