图灵完全图查询语言

Question

是否准确地说，在现有的图形查询语言(Cypher、Datalog、Sparql等)中，Gremlin是唯一一个图灵完整的语言？

在重要的情况下，我并不是在寻找像魔法的图灵完备性证明:集合这样的边缘情况；我问题的意图是Gremlin是否是唯一一种适用于在图上执行任意计算的图形查询语言。

Answer 1

我不确定你在etc.中包含了什么。但我认为你的说法是正确的。正如你说的那样，你不是在寻找边缘的情况或外来的语言操纵。

1. Cypher不是图灵完整的
2. SQL不是正确的t.c。
3. 根据任何实际的定义，SPARQL不是t.c。
4. Datalog不是t.c。
5. AQL或多或少与标准SQL一样强大。

然而，我们不应该把图灵完整性看作是一个必须具备的特性。声明性查询语言的强大功能在于系统完成了艰苦的工作，而用户只描述了他们正在寻找的东西。这有一个额外的优点，即系统能够找到获得正确信息的优化计划。

Answer 2

• cypher不是图灵完整的
• GSQL正在图灵完成
• 格里姆林完成了。

见本白皮书中它们的详细比较。

https://info.tigergraph.com/gsql

Answer 3

SPARQL是图灵完整的，如果通过循环或递归扩展，在https://www.brunni.de/pdp1/下的一些代码示例。

但问题是图灵完整性是否实际上是查询语言的一个理想特性，因为这意味着语言中存在不可判定的语句(即无限循环)。因此，将图灵完整性转化为一种或另一种语言的论点几乎没有什么价值。实际上，这就是设计不是图灵的查询语言的基本原理，因为应用程序有两个无限循环的来源，一个在编程语言中，一个在查询语言中，这使得整个程序更难调试。