从 Datalog 到 SQL 的翻译
我仍在思考如何将 Datalog 程序的递归性转换为 SQL，例如
P(x,y) <- Q(x,y).
Q(x,y) <- P(x,z), A(y).
其中 A/1 是 EDB 谓词。 P 和 Q 之间存在相互依赖性。对于较长的查询，如何解决这个问题？
另外，有没有系统可以完全实现翻译？如果有的话，我可以知道我可以参考什么系统或哪篇论文吗？
I am still thinking on how to translate the recursivity of a Datalog program into SQL, such as
P(x,y) <- Q(x,y).
Q(x,y) <- P(x,z), A(y).
where A/1 is an EDB predicate. This, there is a co-dependency between P and Q. For longer queries, how to solve this problem?
Moreover, is there any system completely implement the translation? If there is, may I know what system or which paper may I refer?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果采用“列出”先前结论并对其进行前向链推理来推断新结论的方法，则不需要递归“深度”。
请记住，Datalog 需要对规则和变量进行一些限制，以确保有限的终止，从而确保有限的多个结论。例如，变量必须具有有限范围的可能值。
假设您的示例引用的是常量而不是变量：
一个问题是您希望将
A/1实现为扩展存储过程或外部代码。为此，我建议列出对所有可能的参数（有限多个）调用A的所有结果。毕竟，这些都是您的系统的结论（可证明的陈述）。一旦完成，前向链接推理就会迭代而不是递归地进行。在每一步中考虑每条规则，将其与先前获得（列出）结论的前提（右侧）一起应用，如果它产生新的结论。如果当前步骤中没有规则产生新结论，则停止。证明程序已完成。
在您的示例中，证明在提出所有
A事实后停止，因为没有足以应用任一规则来得出新结论的结论。If you adopt an approach of "tabling" previous conclusions and forward-chain reasoning on these to infer new conclusions, no recursive "depth" is required.
Bear in mind that Datalog requires some restrictions on rules and variable that assure finite termination and hence finitely many conclusions. Variables must have a finite range of possible values, for example.
Let's assume your example refers to constants rather than to variables:
One wrinkle is that you want
A/1to be implemented as an extended stored procedure or external code. For that I would propose tabling all the results of callingAon all possible arguments (finitely many). These are after all among the conclusions (provable statements) of your system.Once that is done the forward-chaining inference proceeds iteratively rather than recursively. At each step consider each rule, applying it with premises (right-hand sides) that are previously obtained (tabled) conclusions if it produces a new conclusion. If no rule produces a new conclusion in the current step, halt. The proof procedure is complete.
In your example the proofs stop after all the
Afacts are adduced, because there are no conclusions sufficient to apply either rule to get new conclusions.一种可能的方法是在 SQL 中使用递归 CTE，它提供传递闭包的功能。关系代数+传递闭包=数据日志。
A possible approach is to use recursive CTEs in SQL, which provide the power of transitive closure. Relational algebra + transitive closure = Datalog.
Logica 做了类似的事情。它将类似数据日志的语言转换为适用于 Google BigQuery、PostgreSQL 和 SQLite 的 SQL。
Logica does something like this. It translates a datalog-like language into SQL for Google BigQuery, PostgreSQL and SQLite.