The Gremlin Graph Traversal Machine and Language

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.

To appear in the Proceedings of the 2015 ACM Database Programming Languages Conference

References in corpus (2)

• Grammar-Based Random Walkers in Semantic Networks
• Mapping Semantic Networks to Undirected Networks

Cited by in corpus (8)

• Knowledge Graphs
• The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing: Extended Survey
• Construction of Knowledge Graphs: State and Challenges
• High-Level Programming Abstractions for Distributed Graph Processing
• An analysis of the graph processing landscape
• Formalising opencypher Graph Queries in Relational Algebra
• Representing LLVM-IR in a Code Property Graph
• Optimizing Navigational Graph Queries