我仍在思考如何将Datalog程序的递归性翻译成SQL，例如
P(x,y) <- Q(x,y).
Q(x,y) <- P(x,z), A(y).
其中 A/1 是一个EDB谓词。因此，P和Q之间存在相互依赖关系。对于较长的查询，如何解决这个问题？
此外，是否有任何系统完全实现了翻译？如果有，我可以知道是哪个系统或者可以参考哪篇论文吗？
将Datalog翻译成SQL
5
- zfm
5
示例应进行更正。请注意，变量y未出现在第二条规则的前提条件中，尽管它在头部中使用。Datalog是受限制的，以使所有程序终止。您是在询问有关消除递归以获得（可能）单个SQL查询等效的方法，还是在考虑在SQL上下文中实现递归，这可能是可能的（具有严格限制），使用存储过程？ - hardmath
@hardmath：抱歉，打错了...谢谢纠正。是的，我想在SQL中实现递归，这可能吗？ - zfm
可能是可以的，但我们可能会受到直接递归深度的限制。例如，MS SQL Server 2008将存储过程调用的嵌套深度限制为32。这可能足以证明一个概念，但不适用于生产应用程序。请注意，MS SQL Server允许调用外部编码（扩展存储过程），其中不监视调用的嵌套。 - hardmath
您可能会对一种间接递归方法感兴趣，其中“datalog”规则被重复应用以推断新的结果，并且这些结果可以插入到一个或多个表中，直到不再有新的推论为止。 - hardmath
@hardmath：这是我的想法！递归将在程序中完成，而不是在SQL中...然而，如果存在非平凡的依赖关系，这对我来说仍然是如此难以管理... - zfm
3个回答
1
如果您采用“表格化”以前的结论并在此基础上进行前向推理来推断新的结论的方法，则不需要递归“深度”。
请记住，Datalog对规则和变量有一些限制，以确保有限终止和因此有限的结论。例如，变量必须具有有限的可能值范围。
让我们假设您的示例是指常量而不是变量：
P(x,y) <- Q(x,y).
Q(x,y) <- P(x,z), A(y).
一个问题是，您希望将
A/1实现为扩展存储过程或外部代码。为此，我建议将调用所有可能参数（有限多个）上的A的结果进行制表。毕竟，这些都是您系统中的结论（可证明的陈述）之一。完成这一步骤后，前向链接推理将以迭代而非递归的方式进行。在每一步中，考虑每个规则，并使用先前获得（制表）的结论作为前提条件（右侧）。如果它产生新的结论，则应用该规则。如果在当前步骤中没有规则产生新的结论，则停止。证明过程完成。
在您的示例中，当所有
A事实被引证后，证明停止，因为没有足够的结论来应用任何规则以获得新的结论。- hardmath
2
在这种情况下，它可能有效，但是在更大的情况下，如果存在更大的非平凡递归，会怎样呢？ - zfm
1我所概述的是一个过程，对于符合Datalog规范的程序，将推导出所有（有限数量的）可证明结论。如果您有像
A/1这样的“终端”谓词实现为外部代码，则会将其处理为简单事实，即存储在所有可能输入上调用它们时的任何成功结果（请记住，在Datalog中，任何变量的范围都是有限的）。因此，这个“皱纹”可以简化为标准的Datalog事实和规则。 - hardmath0
一种可能的方法是在SQL中使用递归CTE，这提供了传递闭包的能力。关系代数+传递闭包=Datalog。
- John Cowan
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接