The Gremlin Graph Traversal Machine and Language by Marko A. Rodriguez.
Abstract:
Gremlin is a graph traversal machine and language designed, developed, and distributed by the Apache TinkerPop project. Gremlin, as a graph traversal machine, is composed of three interacting components: a graph $$G$$, a traversal $$\Psi$$, and a set of traversers $$T$$. The traversers move about the graph according to the instructions specified in the traversal, where the result of the computation is the ultimate locations of all halted traversers. A Gremlin machine can be executed over any supporting graph computing system such as an OLTP graph database and/or an OLAP graph processor. Gremlin, as a graph traversal language, is a functional language implemented in the user’s native programming language and is used to define the $\Psi$ of a Gremlin machine. This article provides a mathematical description of Gremlin and details its automaton and functional properties. These properties enable Gremlin to naturally support imperative and declarative querying, host language agnosticism, user-defined domain specific languages, an extensible compiler/optimizer, single- and multi-machine execution models, hybrid depth-and breadth-first evaluation, as well as the existence of a Universal Gremlin Machine and its respective entailments.
Why Marko wants to overload terms, like Gremlin, I don’t know. (Hi! Marko!) Despite that overloading, if you are fond of Gremlin (in any sense) and looking for a challenging read, you have found it.
This won’t be a quick read. 😉
Gremlin3 is a declarative query language. (Excellent!)
Static results are an edge case of the dynamic systems they purport to represent. (An insight suggested to me by Sam Hunting.)
Think about it for a moment. There are no non-dynamic systems, only non-dynamic representations of dynamic systems. Which makes non-dynamic representations false, albeit sometimes useful, but also an edge case.
Sorry, didn’t mean to get distracted.
Deeply recommend this “Gremlin” overloaded paper and that you check into the recently released TinkerPop3 release!
Modified 25 November 2015 to point out Gremlin3 is a declarative query language. Thanks to Marko for the catch!