PaperlayerView exact revision on arXiv

Source-linked AI summary

The Gremlin Graph Traversal Machine and Language

Marko A. Rodriguez

arXiv:1508.03843v1cs.DBcs.DM

TL;DR

Gremlin addresses the need for a graph-querying framework that supports traversal and pattern matching across graph-computing settings. The paper formalizes Gremlin as a machine and functional language built from graphs, traversals, and traversers, and shows that its structures support flexible execution and Turing completeness. It also identifies constraints on distributed traversal execution and on a fully expressive Universal Gremlin Machine.

  • Problem

    Graph query languages typically emphasize either graph traversal or graph pattern matching, motivating a framework that supports both perspectives.

  • Method

    The paper mathematically models Gremlin as graph G, traversal Ψ, and traverser set T, and analyzes its automaton, functional, execution, and Universal Gremlin Machine properties.

  • Results

    Gremlin’s formal properties support imperative and declarative querying, host-language embedding, extensible optimization, distributed and hybrid execution, and Turing completeness.

  • Takeaways & Limitations

    Gremlin provides a unified traversal machine and language whose computations can be executed across supporting OLTP and OLAP graph systems.

  • Takeaways & Limitations

    Distributed OLAP execution disallows certain traversal sequences, while a fully expressive Universal Gremlin Machine would require additional handling for changing traverser sets and the complete instruction set.

Abstract

from arXiv · show

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 $Ψ$, 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 $Ψ$ 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.

1. Introduction

Gremlin unifies graph traversal and pattern matching within one framework. Its structures support embedding, extension, optimization, distributed execution, multiple evaluation orders, and representation within the graph.

  • Gremlin supports both imperative traversal-style and declarative pattern-match-style graph querying within one framework.
  • Gremlin’s structures facilitate embedding in host languages, user-defined domain terminology, and extensible compile-time optimization.
  • The machine supports multi-machine execution, depth-first, breadth-first, or hybrid evaluation, and theoretical representation within the graph itself.

2. Graph Traversal Machine

The Gremlin traversal machine consists of a graph, traversal instructions, and traversers that move through the graph until computation halts. Traversals are functional structures whose steps transform traverser sets while traversers carry graph and execution state.

  • Graph Traversal Machine: Gremlin computations use graph G as data, traversal Ψ as instructions, and traverser set T as moving read/write heads.Computation ends when traversers are absent or halted; results are the multiset union of halted traverser locations.
  • The Traversal: A traversal Ψ is a tree of functions organized into linear chains or nested motifs.In a linear motif, successive steps consume the previous step’s output; nested motifs pass an internal traversal as a step argument.
  • The Traversal: Gremlin steps map traverser sets through map, flatMap, filter, sideEffect, and branch operations.These operations preserve, change, remove, mutate around, or route traversers according to their functional definitions.
  • The Traverser: A traverser unifies graph and traversal state through references to a graph object and a traversal step.Its metadata includes a labeled path, bulk, sack, and loop counter, with projection functions exposing these components.
  • Evaluation: Traversers are isolated entities, allowing implementations to change evaluation between depth-first and breadth-first ordering.The step functions have no state, while each traverser maintains its own metadata and state.

3. Graph Traversal Language

Gremlin is a functional graph-traversal language embedded in a host programming language. Its steps compose sequentially or nest, allowing traverser sets to grow, shrink, branch, and reduce during execution.

  • Language Design: Gremlin’s functional language design enables users to define Ψ through syntax embedded in their native programming language.Function composition and first-class function types support fluent method chaining and nested traversal arguments.
  • Linear Traversal: A linear traversal composes steps that find Marko, follow knows edges, read ages, and return the maximum age.The traversal is represented as g.V().has("name","marko").out("knows").values("age").max().
  • Traverser Sets: Gremlin traverser sets shrink through filtering, undefined mappings, and reducing barriers, while one-to-many flatMap steps make them grow.Furcating automata take all valid options when multiple traversal choices are available.
  • Branching Traversal: Branch steps may route a traverser to one branch, a subset of branches, or all branches.The examples are choose(), repeat().emit(), and union(), respectively.
  • Branching Traversal: The choose() step implements if/else-if/else branching by selecting nested traversals based on traverser state.Its branches count created projects for person vertices, collaborators for software vertices, or return a label otherwise.

3.3 A Recursive Traversal

Recursive traversals reset a traverser’s program counter to an earlier step and use loop predicates, counters, and emission to control repeated walks. The examples limit repetition to five outgoing steps and optionally emit intermediate results.

  • Recursive Traversal: Recursion requires resetting a traverser’s ψ-program counter to a previously seen traversal step.The loop counter records repeated traversal through the loop sequence and can be incremented or reset.
  • Recursive Traversal: The repeat() traversal follows outgoing edges from Marko for five steps using times(5).The functional definition continues while the loop counter is less than 5, then halts.
  • Recursive Traversal: Adding emit() returns names encountered along the five-step walk rather than only names reached at its endpoint.emit() is a step modulator of repeat(), allowing recursive mappings and emitted traversers together.

3.4 A Path Traversal

Gremlin records traverser path history as labeled locations, supporting path queries, revisiting prior locations, and detection of previously visited locations. A simple traversal can therefore return the shortest non-looping path between two vertices.

  • Example: In g.V().as("a").out().as("b","c").path(), branching creates child traversers whose paths retain earlier locations and labels.A child traverser can preserve x labeled “a” and y labeled “b, c” in sequence.
  • Path representation: A traverser’s labeled path records each visited location together with the labels assigned by traversal steps.When a traverser moves, the new location and its step labels are appended to the child traverser’s path.
  • Path uses: Path history supports finding paths between vertices and returning to a previous traverser location.These uses are stated explicitly as shortest-path determination and backward movement through path history.
  • Path uses: Path history also allows Gremlin to determine whether a location has already been visited.This supports simple-path constraints that prevent looping.
  • Example: g.V(x).repeat(out().simplePath()).until(is(y)).path().limit(1) returns the shortest simple path from vertex x to vertex y.The until() step modulates repeat(), while the filter enforces the non-looping condition.

3.5 A Projecting Traversal

Projecting traversals use labeled paths to select named locations, apply separate traversals to them, and optionally filter the resulting bindings. Gremlin’s syntax also provides shorthand for selecting and constraining labeled locations.

  • Example: g.V().as("a").out("knows").as("b") establishes two labeled vertices for subsequent projection.The labels “a” and “b” are then used by the accompanying projection traversals.
  • Projection: select() generates traversers for labeled path locations so each selected vertex can undergo its own traversal.For labels “a” and “b,” the example computes incoming knows counts for “a” and outgoing knows counts for “b.”
  • Projection: by() specifies the traversal applied to each selected label and produces a map of labeled results.The projected values are represented as a Map<String,Long> in programming.
  • Filtering: where() filters traversers according to their labeled path, including constraints between selected vertices.The example retains selections only when the “a” and “b” vertices are not maternal siblings.
  • Syntax: The syntax as("a")...as("b") is syntactic sugar for select("a")...where(eq("b")).This shorthand combines selection with an equality condition on labeled path values.

3.6 A Centrality Traversal

Gremlin expresses graph statistics and graph mutations through traversal steps and side effects. The section illustrates centrality computation with iterative counting, while also showing how traversals can add or remove graph elements and perform declarative matching.

  • Graph statistics: Graph statistics reduce an n-dimensional graph to a lower-dimensional representation, such as vertex counts or centrality values.The section motivates statistics as tools for extracting meaningful information from complex graphs.
  • Centrality: For a strongly connected and aperiodic graph, larger components of eigenvector v indicate more central vertices.The relation Av = λv is expressed and solved in Gremlin through an iterative traversal.
  • Centrality: g.V().repeat(groupCount("m").out()). uses groupCount("m") to count how often traversers encounter each vertex during iteration.The resulting map m stores vertices as keys and encounter counts as values.
  • Limitation: The centrality example leaves the convergence comparison between normalized vectors at successive iterations for the reader to deduce.The stated comparison is between iteration n and iteration n+1.
  • Mutation: Gremlin mutation steps add or remove vertices, edges, and properties, including inverse createdBy edges and deletion of created edges.The examples use add and drop operations to modify the graph.
  • Pattern matching: The match() step supports nested or negated pattern traversal while preserving labeled-variable bindings.Patterns are taken once, prefixes must already exist, and postfix labels are bound or checked for consistency.
  • Pattern matching: The illustrated match traversal returns names of software creators who collaborated with at least four people, including a collaborator who is their father.The result is obtained after matching the specified created, knows, and father patterns.

3.9 A Domain Specific Traversal

Gremlin supports domain-specific traversal languages by compiling domain terms into compositions of its graph-oriented steps. Users can query in domain language while execution remains grounded in the underlying graph representation.

  • Core language: Gremlin provides approximately 30 core traversal steps that correspond closely to its graph traversal language.These steps process data through graph concepts such as vertices, edges, and properties.
  • DSL compilation: A domain-specific language can compile user-facing domain terms into compositions of the underlying Gremlin steps.The paper illustrates this with a hypothetical social traversal language.
  • DSL compilation: The hypothetical social language maps terms such as people(), named(), who(), know(), and created() to standard Gremlin traversals.Mappings include hasLabel("person"), has("name","marko"), outE("knows"), and out("created").
  • Execution: Users express queries in domain language, but Gremlin evaluates them against the graph structure representing that domain.The domain vocabulary is therefore compiled into graph-structural operations.

4. Traversal Strategies

Gremlin traversal strategies compile traversals through ordered decoration, optimization, vendor optimization, finalization, and verification stages. These rewrites preserve or improve execution while checking validity across execution settings.

  • Strategy categories: Gremlin organizes traversal compilation into five ordered strategy categories: decoration, optimization, vendor optimization, finalization, and verification.Strategies in each category are evaluated before moving to the next category.
  • Decoration: Decoration rewrites syntactic forms, converting infix logical connectors into equivalent prefix representations.For example, a.and().b becomes and(a,b), while nested connectors are regrouped into prefix notation.
  • Optimization: Optimization strategies replace traversal sequences with cheaper equivalents, including direct adjacency steps, identity removal, filter reordering, and bounded counting.FilterRankingStrategy executes cheaper filters first, while RangeByIsCountStrategy limits counting to one more than the required number.
  • Vendor optimization: Vendor optimization folds property filters into vendor-specific indexed lookups, targeting O(log(|V|)) costs instead of O(|V|) linear scans.XGraphStepStrategy incorporates has() steps into a vendor-specific V() step when graph-system indexes are available.
  • Vendor optimization: MatchPredicateStrategy folds where() patterns into match() and exposes eligible has() prefixes for the runtime optimizer and vendor indexes.These rewrites allow match()-based optimization and index lookup opportunities.
  • Finalization and verification: Verification restricts invalid distributed traversals, while finalization inserts profiling steps when profile() is requested.Single-machine OLTP supports more traversal types than multi-machine OLAP, and profile metrics are maintained as side effects.

5. Distributed Graph Traversals

Distributed Gremlin executes traversers with the graph-based BSP model, moving them between vertex partitions as traversal steps change their locations. Bulking compresses equivalent traversers, preventing exponential memory growth in broad traversals.

  • Distributed execution: Gremlin’s graph computer distributes traversal execution using bulk synchronous parallelism, where vertices process state and messages in parallel rounds.The process continues until no more messages are sent.
  • Partition movement: Traversers migrate between partitioned machines when traversal steps place them at vertices owned by different partitions.Generated traversers are serialized and sent to the machines maintaining their destination partitions.
  • Traverser growth: Breadth-first execution can generate exponentially many traversers; a 20×20 lattice traversal yields approximately 138 billion at the bottom-right vertex.The example uses g.V(topLeft).repeat(out()).times(40).
  • Bulking: Bulking losslessly projects equivalent traversers onto at most |U| locations by replacing each equivalence class with one traverser whose bulk is the summed count.Equivalence requires matching location, step, labeled path, sack, and other traverser components except bulk.
  • Bulking: In the 20×20 lattice example, bulking reduces the result to one traverser with bulk β(t) = 137,846,528,820.The number of locations remains bounded by |U|, with |V| = 400 for this lattice.
  • Bulking assumptions: Bulking is more effective when traversers do not require labeled paths, because omitting Δ(t) reduces the number of equivalence classes.When labeled paths are needed, equivalence classes can grow with unique traversal paths and may increase rapidly in broad traversals.

6. Minimal Gremlin Traversal Machines

Gremlin’s minimal machines can reproduce increasingly powerful automata, including a single-headed Turing machine. Its graph-encoded Universal Gremlin Machine represents traversal state in the graph, while parallel machines can execute active traversers concurrently.

  • 6. Minimal Gremlin Traversal Machines: Gremlin’s automaton power depends on reducing its traverser structure and instruction set; Turing completeness requires values(), property(), sack(), choose(), repeat(), in(), and out().These steps provide tape reading and writing, state storage, branching, looping, and left/right movement.
  • 6.1 Turing Completeness: The paper proves that the Gremlin graph traversal machine is Turing Complete.The proof maps a Turing machine’s tape to a line graph and its state to a traverser sack.
  • 6.1 Turing Completeness: A Gremlin traversal can simulate a Turing transition function by reading or writing vertex symbols, updating the sack state, branching, looping, and moving through adjacent vertices.Because the line graph has one left and one right neighbor, the traverser set remains of size 1 during the simulation.
  • 6.2 A Universal Gremlin Machine: A Universal Gremlin Machine encodes both traversal instructions and traversers as subgraphs of G, then repeatedly updates those encoded structures until the traverser halts.The computation’s result is the multiset union of symbols in the tape subgraph outside the encoded traversal and traversers.
  • 6.2 A Universal Gremlin Machine: The proposed Universal Gremlin Machine does not yet cover growing or shrinking encoded traverser sets, all Gremlin steps, or the general complications of nested traversals.Extending the traversal is necessary to preserve the full expressivity of the Gremlin traversal machine.
  • 6.3 Parallel Universal and G-Encoded Machines: Multiple Universal Gremlin Machines can operate in parallel against G, analogous to a multithreaded system.Each machine can locate active traversers and execute steps until no traversers remain or all have halted.
  • 6.4 Traversing a Gremlin Traversal Machine: When G, Ψ, and T are encoded together in G, the machine can in principle traverse and rewrite its own representation.The paper identifies reflection and self-rewriting as consequences, leaving their applied ramifications for future work.
  • 6.5 A Primordial Graph Traversal Machine: The complete computation can also be represented as an undirected graph whose subgraphs transform until the graph reaches a stable equilibrium.This primordial model conceptualizes computation as local graph-structure reactions that create or destroy vertices and edges.

7. Conclusion

Gremlin is a graph traversal machine and language whose traversers follow user-defined instructions through attributed, multidimensional graphs. Traverser branching can generate extremely large numbers of paths before halted traversers provide the traversal’s answer.

  • 7. Conclusion: Gremlin combines a graph traversal machine with a graph traversal language for programming traverser movement through graphs.The language defines the traversal instructions that determine how traversers explore the graph.
  • 7. Conclusion: Graph complexity, rather than Gremlin’s basic constructs alone, can produce billions of traversers on small graphs as paths branch at each step.Traversers split to explore options satisfying the traversal’s constraints, and their halted locations provide the answer.
Loading 1508.03843v1…