图灵完备图查询语言

Turing complete graph query languages

在现有的图形查询语言(Cypher、Datalog、Sparql 等)中,Gremlin 是唯一一个图灵完备的语言是否准确?

以防万一,我不是在寻找边缘案例,例如《魔法风云会》的图灵完备性证明;我的问题的目的是 Gremlin 是否是唯一适合在实践中对图执行任意计算的图查询语言。

我不确定 etc. 中包含的内容。 但我认为你的说法是正确的。正如您所说,您不是在寻找边缘情况或对语言的奇异操作。

  1. Cypher is not turing complete
  2. SQL is not properly t.c.
  3. By any practical definition, SPARQL is not t.c.
  4. Datalog is not t.c.
  5. AQL is more or less as powerful as standard SQL

然而,我们不应将图灵完备性视为必备功能。声明式查询语言的强大之处在于,繁重的工作由系统完成,而用户 只需 描述他们正在寻找的内容。这具有额外的优势,即系统能够找到优化的计划以获取正确的信息。

  • cypher 不是图灵完备的
  • GSQL 是图灵完备的
  • Gremlin 是图灵完备的。

在本白皮书中查看它们的详细比较

https://info.tigergraph.com/gsql

如果通过循环或递归扩展,SPARQL 是图灵完备的,https://www.brunni.de/pdp1/.

下的一些代码示例

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