3

I am wondering of what kind of queries I am able to perform with Cypher and Gremlin, but I didn't manage to find a complete grammar of the language and its translation into an operational semantics. Does anybody know if there is something that clarifies the expressive power of these languages?

jackb
  • 695
  • 8
  • 26

1 Answers1

0

For cypher, the grammar is available as a set of Scala files that use the Parboiled library. You should be able to find those scala files in the neo4j github repo. It's not a formal grammar per se, but if you look at the source files you'll get the same production rules as you would expect out of a formal grammar. You can find that here on github. Look into Query.scala as a starting point on what defines a Cypher query and what its grammatical components are.

For gremlin, I'm not sure how it works but again I'd guess you need to go source code diving, it's likely that they too use a parser generator of some sort, where the grammar is going to be effectively in code.

Your question about "expressive power" is a bit vague though; suffice to say that cypher is a declarative language (focuses on what to return, doesn't specify how to traverse), gremlin looks to me like a declarative language (in that it states how to do the traversals moreso than what data to return). In the end they're both turing complete so while their styles are completely different, one is not more "powerful" than the other in any formal sense.

Depending on the particular task you're doing, and a contextual definition of "powerful", one might be more powerful than the other. Say what you want to do is a breadth-first search of a tree for something specific. In this case, a traversal-oriented approach is best, maybe gremlin is better, since Cypher doesn't allow you to specify traversal order. On the other hand, say you want to express a complex path query that returns a certain data item irrespective of where it is in the graph. Then perhaps arguably cypher is more powerful since it focuses on the "what" not the "how".

FrobberOfBits
  • 17,634
  • 4
  • 52
  • 86
  • 1
    Is there any proof of their turing-completeness, or this is only a suggestion? Gremlin has something similar to a cycle, but Cypher doesn't have it. Moreover, I think that query languages shouldn't be turing complete, as SQL, and hence I was expecting that they weren't so powerful. Why is that? – jackb Oct 28 '15 at 15:14
  • I don't have a proof that they're turing complete, but it's a pretty low bar. They both have storage (via the DB) and they both have conditionals. That's most of what you'd need right there. http://stackoverflow.com/questions/315340/practical-non-turing-complete-languages – FrobberOfBits Oct 28 '15 at 18:56
  • 1
    The proof for Turning Completeness in Gremlin is here: http://arxiv.org/abs/1508.03843 – Marko A. Rodriguez Nov 04 '15 at 01:57