4

Is it accurate to say that of the existing graph query languages (Cypher, Datalog, Sparql etc) Gremlin is the only one that's Turing complete?

In case it matters, I'm not looking for edge cases like the Turing completeness proof of Magic: the Gathering; the intent of my question is whether Gremlin is the only graph query language that is suitable in practice for performing arbitrary computation on graphs.

Erik Kaplun
  • 37,128
  • 15
  • 99
  • 111
rwallace
  • 31,405
  • 40
  • 123
  • 242
  • 2
    SQL isn't turing complete, but it hasn't stopped legions of programmers from building highly effective systems with it, by mixing it with other computation systems. You'll have to be a little more specific. – Sebastian Good Dec 21 '15 at 23:15
  • 1
    It's considered an advantage of Datalog that it isn't turing complete. This means that it can take advantage of efficient resolution algorithms not available to t.c. big brother prolog. – Leo Ware Apr 11 '21 at 07:05
  • 1
    it is also not unfair to say that Prolog, being a superset of Datalog, is a Turing-complete graph query language, especially with tabling and other modern additions to the classical core. When the Prolog fact database doesn’t constitute a graph, it can still be seen as a graph, e.g. a list is a forest of graphs with just a single node. Such “pseudo” graph can be smoothly transitioned or extended into a non-pseudo graph. – Erik Kaplun Apr 05 '22 at 11:09
  • 2
    @LeoWare [Prolog with tabling (SLG resolution)](https://www.swi-prolog.org/pldoc/man?section=tabling) — does Datalog still have more efficient resolution algorithms? – Erik Kaplun Apr 05 '22 at 11:47

3 Answers3

4

I'm not sure about what you include in the etc.. But I think your statement is correct. As you say that you are not looking for edge cases or exotic manipulation of the language.

  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

Yet, we should not look at turing completeness as a must-have feature. The power of declarative query languages is that the hard work is done by the system, while the user just describes what they are looking for. This has the added advantage that the system is able to find optimized plans to get to the right information.

Kuzeko
  • 1,545
  • 16
  • 39
3
  • cypher is not Turing complete
  • GSQL is Turing complete
  • Gremlin is Turing complete.

See the detailed comparison of them at this white paper

https://info.tigergraph.com/gsql

Mingxi Wu
  • 31
  • 1
1

SPARQL is Turing-complete if extended by loops or recursion, some code examples under https://www.brunni.de/pdp1/.

But the question is whether Turing-completeness is actually a desirable feature for a query language, because this means that there are undecidable statements in the language (i.e., infinite loops). So, there is little value of turning Turing-completeness into an argument for one or another language. Actually, that would be the rationale of designing query languages that are not Turing-complete by intent, because applications have two sources of infinite loops then, one in the programming language and one in the query language, which makes the entire thing even harder to debug.

Chiarcos
  • 324
  • 1
  • 10
  • 1
    Datalog is also Turing complete when extended with loops. For example with Datomic’s (in-memory) Datalog engine, only by adding Clojure-level folds/recursion/loops, Turing completeness appears. And why not also SQLite, in memory or not, with host language loops/recursion/folds. – Erik Kaplun Apr 05 '22 at 11:42
  • I think the practical question for a query language is whether it can iterate over a series of results. If the purpose is only to be able to calculate a transitive closure over a graph pattern, this can be achieved with SPARQL property paths. No Turing completeness needed unless you want to bind or manipulate a variable at every step in the path. – Chiarcos May 03 '22 at 10:15