Gremlin (programming language)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Gremlin
Gremlin Logo.png
Designed by Marko A. Rodriguez
Developer Apache TinkerPop of the Apache Software Foundation
First appeared 2009; 6 years ago (2009)
Stable release Gremlin 3.0.0[1]
OS Cross-platform (multi-platform)
License Apache License
Website Official Site
Dialects
Gremlin-Java8, Gremlin-Groovy, Gremlin-Scala, Gremlin-Clojure, Gremlin-PHP, Gremlin-JavaScript, Gremlin-Typeset
Influenced by
Regular expression, XPath, SPARQL, SQL, Java/JVM

Gremlin is a graph traversal language and virtual machine developed by Apache TinkerPop of the Apache Software Foundation. Gremlin works for both OLTP-based graph databases as well as OLAP-based graph processors. Gremlin's automata and functional language foundation 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 Turing Completeness.[2]

As an explanatory analogy, Apache TinkerPop and Gremlin are to graph databases what the JDBC and SQL are to relational databases. Likewise, the Gremlin traversal machine is to graph computing as what the Java virtual machine is to general purpose computing.

Vendor Integration[edit]

Gremlin is an Apache2-licensed graph traversal language that can be used by an graph system vendor. There are typically two types of graph system vendors: OLTP graph databases and OLAP graph processors. The table below outlines those graph vendors that support Gremlin.

Vendor Graph System
Titan[3] [4] graph database
Neo4j graph database
OrientDB graph database
Hadoop (Giraph) graph processor
Hadoop (Spark) graph processor
InfiniteGraph graph database
BlazeGraph graph database
DEX graph database
Sqlg graph database
Bitsy graph database

Traversal Examples[edit]

The following examples demonstrate Gremlin-Groovy over a graph representation of the MovieLens dataset.[5] The dataset includes users who rate movies. Users each have one occupation and movies have one or more categories associated with it. The MovieLens graph schema is detailed below.

user--rated[stars:0-5]-->movie
user--occupation-->occupation
movie--category-->category

Simple Traversals[edit]

gremlin> g.V().label().groupCount()
==>[occupation:21, movie:3883, category:18, user:6040]
gremlin> g.V().hasLabel('movie').values('year').min()
==>1919
gremlin> g.V().has('movie','name','Die Hard').inE('rated').values('stars').mean()
==>4.121848739495798

Projection Traversals[edit]

gremlin> g.V().hasLabel('category').as('a','b').
           select('a','b').
             by('name').
             by(inE('category').count())
==>[a:Animation, b:105]
==>[a:Children's, b:251]
==>[a:Comedy, b:1200]
==>[a:Adventure, b:283]
==>[a:Fantasy, b:68]
==>[a:Romance, b:471]
==>[a:Drama, b:1603]
==>[a:Action, b:503]
==>[a:Crime, b:211]
==>[a:Thriller, b:492]
==>[a:Horror, b:343]
==>[a:Sci-Fi, b:276]
==>[a:Documentary, b:127]
==>[a:War, b:143]
==>[a:Musical, b:114]
==>[a:Mystery, b:106]
==>[a:Film-Noir, b:44]
==>[a:Western, b:68]
gremlin> g.V().hasLabel('movie').as('a','b').
           where(inE('rated').count().is(gt(10))).
           select('a','b').
             by('name').
             by(inE('rated').values('stars').mean()).
           order().by(select('b'),decr).
           limit(10)
==>[a:Sanjuro, b:4.608695652173913]
==>[a:Seven Samurai (The Magnificent Seven), b:4.560509554140127]
==>[a:Shawshank Redemption, The, b:4.554557700942973]
==>[a:Godfather, The, b:4.524966261808367]
==>[a:Close Shave, A, b:4.52054794520548]
==>[a:Usual Suspects, The, b:4.517106001121705]
==>[a:Schindler's List, b:4.510416666666667]
==>[a:Wrong Trousers, The, b:4.507936507936508]
==>[a:Sunset Blvd. (a.k.a. Sunset Boulevard), b:4.491489361702127]
==>[a:Raiders of the Lost Ark, b:4.47772]

Declarative Pattern Matching Traversals[edit]

Gremlin supports declarative graph pattern matching similar to SPARQL. For instance, the following query below uses Gremlin's match()-step.

gremlin> g.V().
           match(
             __.as('a').hasLabel('movie'),     
             __.as('a').out('category').has('name','Action'),
             __.as('a').has('year',between(1980,1990)),
             __.as('a').inE('rated').as('b'),
             __.as('b').has('stars',5),
             __.as('b').outV().as('c'),
             __.as('c').out('occupation').has('name','programmer'),
             __.as('c').has('age',between(30,40))).
           select('a').groupCount().by('name').
           order(local).by(valueDecr).
           limit(local,10)
==>Raiders of the Lost Ark=26
==>Star Wars Episode V - The Empire Strikes Back=26
==>Terminator, The=23
==>Star Wars Episode VI - Return of the Jedi=22
==>Princess Bride, The=19
==>Aliens=18
==>Boat, The (Das Boot)=11
==>Indiana Jones and the Last Crusade=11
==>Star Trek The Wrath of Khan=10
==>Abyss, The=9

OLAP Traversal[edit]

gremlin> g = graph.traversal(computer(SparkGraphComputer))
==>graphtraversalsource[hadoopgraph[gryoinputformat->gryooutputformat], sparkgraphcomputer]
gremlin> g.V().repeat(outE('rated').has('stars', 5).inV().
                 groupCount('m').by('name').
                 inE('rated').has('stars', 5).outV()).
               times(4).cap('m')
==>Star Wars Episode IV - A New Hope	  35405394353105332
==>American Beauty	  31943228282020585
==>Raiders of the Lost Ark	31224779793238499
==>Star Wars Episode V - The Empire Strikes Back  30434677119726223
==>Godfather, The	30258518523013057
==>Shawshank Redemption, The	28297717387901031
==>Schindler's List	27539336654199309
==>Silence of the Lambs, The	26736276376806173
==>Fargo	 26531050311325270
==>Matrix, The	 26395118239203191

Gremlin Graph Traversal Machine[edit]

Gremlin is a virtual machine composed of an instruction set as well as an execution engine. An analogy is drawn between Gremlin and Java.

Java Ecosystem Gremlin Ecosystem
Groovy programming language Gremlin-Groovy
Scala programming language Gremlin-Scala
Clojure programming language Gremlin-Clojure
... ...
Java programming language Gremlin-Java8
Java instruction set Gremlin step library
Java virtual machine Gremlin traversal machine

Gremlin Steps (Instruction Set)[edit]

The following traversal is a Gremlin traversal in the Gremlin-Java8 dialect.

g.V().as("a").out("knows").as("b").
  select("a","b").
    by("name").
    by("age")

The Gremlin language (i.e. the fluent-style of expressing a graph traversal) can be represented in any host language that supports function composition and function nesting. Due to this simple requirement, there exists various Gremlin dialects including Gremlin-Groovy, Gremlin-Scala, Gremlin-Clojure, etc. The above Gremlin-Java8 traversal is ultimately compiled down to a step sequence called a traversal. A string representation of the traversal above provided below.

[GraphStep([],vertex)@[a], VertexStep(OUT,[knows],vertex)@[b], SelectStep([a, b],[value(name), value(age)])]

The steps are the primitives of the Gremlin graph traversal machine. They are the parameterized instructions that the machine ultimately executes. The Gremlin instruction set is approximately 30 steps. These steps are sufficient to provide general purpose computing and what is typically required to express the common motifs of any graph traversal query.

Given that Gremlin is a language, an instruction set, and a virtual machine, it is possible to design another traversal language that compiles to the Gremlin traversal machine (analogous to how Scala compiles to the JVM). For instance, the popular SPARQL graph pattern match language can be compiled to execute on the Gremlin machine. The following SPARQL query

SELECT ?a ?b ?c 
WHERE {
  ?a a Person .
  ?a ex:knows ?b .
  ?a ex:created ?c .
  ?b ex:created ?c .
  ?b ex:age ? d .
    FILTER(?d < 30)
}

would compile to

[GraphStep([],vertex), MatchStep(AND,[[MatchStartStep(a), LabelStep, IsStep(eq(Person)), MatchEndStep], [MatchStartStep(a), VertexStep(OUT,[knows],vertex), MatchEndStep(b)], [MatchStartStep(a), VertexStep(OUT,[created],vertex), MatchEndStep(c)], [MatchStartStep(b), VertexStep(OUT,[created],vertex), MatchEndStep(c)], [MatchStartStep(b), PropertiesStep([age],value), MatchEndStep(d)], [MatchStartStep(d), IsStep(gt(30)), MatchEndStep]]), SelectStep([a, b, c])].

In Gremlin-Java8, the SPARQL query above would be represented as below and compile to the identical Gremlin step sequence (i.e. traversal).

g.V().match(
  as("a").label().is("person"),
  as("a").out("knows").as("b"),
  as("a").out("created").as("c"),
  as("b").out("created").as("c"),
  as("b").values("age").as("d"),
  as("d").is(gt(30))).
    select("a","b","c")

Gremlin Machine (Virtual Machine)[edit]

The Gremlin graph traversal machine can execute on a single machine or across a multi-machine compute cluster. Execution agnosticism allows Gremlin to run over both graph databases (OLTP) and graph processors (OLAP).

References[edit]

  1. ^ "Gremlin 3.0.0". Retrieved July 31, 2015. 
  2. ^ "The Gremlin Graph Traversal Machine and Language". Retrieved August 21, 2015. 
  3. ^ "Titan Graph Database Homepage". Retrieved August 27, 2015. 
  4. ^ "Titan GraphDB Integration in DynamoDB". Retrieved August 21, 2015. 
  5. ^ "The Gremlin Graph Traversal Language". Retrieved August 22, 2015. 

External links[edit]

  1. Apache TinkerPop Homepage
  2. GremlinDocs.com (TinkerPop2)
  3. sql2gremlin.com (TinkerPop2)
  4. Rodriguez, M.A., "The Gremlin Graph Traversal Machine and Language," Proceedings of the ACM Database Programming Languages Conference, October, 2015.