Duy Hai Doan

Part 9 of 10 for the series Gremlin Recipes. The purpose is to explain the internal of <a href="http://tinkerpop.apache.org/docs/3.2.5/reference/#traversal">Gremlin</a> and give people a deeper insight into the query language to master it.

This blog post is the 9th from the series Gremlin Recipes. It is recommended to read the previous blog posts first:

<ol>
	<li><a href="https://academy.datastax.com/content/gremlin-traversals">Gremlin as a Stream</a></li>
	<li><a href="https://academy.datastax.com/content/sql-tpo-p">SQL to Gremlin</a></li>
	<li><a href="https://academy.datastax.com/content/gremlin-recipes-3-%E2%80%93-recommendation-engine-traversal">Recommendation Engine traversal</a></li>
	<li><a href="https://academy.datastax.com/content/gremlin-recipes-4-%E2%80%93-recursive-traversals-1">Recursive traversals</a></li>
	<li><a href="https://academy.datastax.com/content/gremlin-recipes-5-%E2%80%93-path-object">Path object</a></li>
	<li><a href="https://academy.datastax.com/content/gremlin-recipes-6-%E2%80%93-projection-and-selection">Projection and selection</a></li>
	<li><a href="https://academy.datastax.com/content/gremlin-recipes-7-%E2%80%93-variables-handling-0">Variable handling</a></li>
	<li><a href="https://academy.datastax.com/content/gremlin-recipes-8-%E2%80%93-sack-operator">sack() operator</a> 
	&nbsp;</li>
</ol>

<h2>I KillrVideo dataset</h2>

To illustrate this series of recipes, you need first to create the schema for KillrVideo and import the data. See <a href="http://www.doanduyhai.com/blog/?p=13224#killrvideo_dataset">here</a> for more details.

The graph schema of this dataset is :

<h3><iframe height="400px" src="https://s3.amazonaws.com/datastax-graph-schema-viewer/index.html#/?schema=killr_video_small.json" width="100%"></iframe></h3>

<h2>II Pattern Matching in Gremlin</h2>

<h3>A. Description</h3>

Until now we always use descriptive traversals with Gremlin. By descriptive traversals I mean we describe all the navigation in the graph using standard steps like <code>in(), out(), ...</code>

However, Gremlin also offers a declarative way to do traversals, using pattern matching. Basically you declare all the properties of your vertices/edges and alias them with label then Gremlin will compute the most appropriate traversals to match your pattern.

A pattern-matching traversal uses the <code>match()</code> step and look like:

<code>gremlin&gt;g.V().match( 
__.as("label").....,&nbsp; &nbsp; &nbsp; // predicate 1 
__.as("label").....,&nbsp; &nbsp; &nbsp; // predicate 2 
... 
__.as("label").where(...) // matching predicate </code>

<code>) 
... </code>

Please note that each predicate must start with a labelling step <code>as()</code>. Each predicate can end with a labelling step <code>as()</code> but it is optional

All the labels you declare in your predicates are global and can be re-called outside of the <code>match()</code> step. Those labels also serve the purpose of matching different predicates together

There are a few things you should know to exploit fully pattern matching with Gremlin:

<ol>
	<li>all the predicates inside the <code>match()</code> are executed concurrently and independently. Consequently the lexical order of the declared predicates does not matter during execution time</li>
	<li>variables(alias) binding need to hold true across multiple predicate. The traversers that succeeded all the variable findings in all predicate are the ones that survive the declared pattern and thus are the result of the <code>match()</code> step</li>
	<li>in other languages like Cypher or SPARQL, reducing barriers (<code>sum(),count()</code> …) or collecting barriers (<code>order(), group()</code>, …) are not allowed. In Gremlin pattern matching they are allowed but their scope is local only, meaning that if you have an <code>order()</code> clause inside a predicate, it is only useful for this predicate but this ordering cannot be used for the other predicates or outside of the <code>match()</code> step</li>
</ol>

The explanation for point 3. is that since each predicate is executed in any order and concurrently, inside a single predicate, at the time the traverser reaches the <code>order().by()</code> step, all the data are being processed concurrently in other predicates so we don’t have all the data to perform a global ordering. Consequently the ordering can only be local to the current predicate

Examples are better than words

<h3>B. Director who played in their own movies</h3>

<code>gremlin&gt;g.V().match( 
&nbsp; &nbsp; __.as("directors").hasLabel("person"), // 1st predicate 
&nbsp; &nbsp; __.as("directors").in("director").as("directed_movies"), 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// 2nd predicate 
&nbsp; &nbsp; __.as("directed_movies").out("actor").as("directors") 
&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;// 3rd predicate ). 
&nbsp; &nbsp; select("directors","directed_movies"). // Iterator<map<string, vertex="Movie|Person">&gt; </map<string,> 
&nbsp; &nbsp; <map<string, vertex="Movie|Person">dedup(). </map<string,> 
&nbsp; &nbsp; <map<string, vertex="Movie|Person">group(). </map<string,> 
&nbsp; &nbsp; &nbsp; &nbsp; <map<string, vertex="Movie|Person">by(select("directors").by("name")). </map<string,> 
&nbsp; &nbsp; &nbsp; &nbsp; <map<string, vertex="Movie|Person">by(select("directed_movies").by("title").fold()). 
&nbsp;</map<string,>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<map<string, vertex="Movie|Person">// Iterator<map<string==director, list="">=movies&gt;&gt; 
unfold()</map<string==director,></map<string,> 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<map<string, vertex="Movie|Person"><map<string==director, list="">// Iterator<mapentry<string==director, list="">=movies&gt;&gt;</mapentry<string==director,></map<string==director,></map<string,></code>

<code><map<string, vertex="Movie|Person"><map<string==director, list=""><mapentry<string==director, list="">==&gt;Charles Chaplin=[The Gold Rush, Modern Times, City Lights, The Great Dictator, The Kid] 
==&gt;Keenen Ivory Wayans=[Scary Movie] 
==&gt;Terry Jones=[Monty Python's Life of Brian, Monty Python's The Meaning of Life, Monty Python and the Holy Grail] 
==&gt;Kenneth Branagh=[Much Ado About Nothing] 
==&gt;Kevin Costner=[Open Range, Dances with Wolves] 
==&gt;Kevin Smith=[Chasing Amy, Clerks] 
==&gt;Buster Keaton=[The General] </mapentry<string==director,></map<string==director,></map<string,></code><code><map<string, vertex="Movie|Person"><map<string==director, list=""><mapentry<string==director, list=""> 
==&gt;Dany Boon=[Welcome to the Sticks] 
==&gt;Ben Stiller=[The Cable Guy, Zoolander] ... </mapentry<string==director,></map<string==director,></map<string,></code>

<ul>
	<li>the 1st predicate is labeled as directors and picks all person vertices</li>
	<li>in the 2nd predicate, we pick the previous directors movies and label them as directed_movies</li>
	<li>in the 3rd predicate, we pick the previous directed_movies and find their actors and label them as directors. This implicitly means that the actors playing in movies directed_movies should be the previously labeled directors themselves!</li>
</ul>

At the step select("directors","directed_movies") we have an Iterator&gt; as follow:

<code>==&gt;{directors=v[{~label=person, community_id=1325149184, member_id=418}], directed_movies=v[{~label=movie, community_id=1757220352, member_id=30}]}</code>

<code>==&gt;{directors=v[{~label=person, community_id=652999808, member_id=184}], directed_movies=v[{~label=movie, community_id=704287872, member_id=7}]}</code>

<code>==&gt;{directors=v[{~label=person, community_id=652999808, member_id=184}], directed_movies=v[{~label=movie, community_id=1026409472, member_id=23}]}</code>

Each map contains a single entry director=director vertex and directed_movies=ONE of the movie he directed/acted in.

The step <code>group().by(select("directors").by("name")).by(select("directed_movies").by("title").fold())</code>

will transform the previous stream into an <code>Iterator==movies&gt;&gt;</code>. Please notice the interesting usage of the <code>select()</code> operator to pick the right map entry by its key. The <code>fold()</code> step in the 2nd <code>by()</code> modulator is necessary to pick ALL the movies for each director/actor

<h3>C. Director who played in their own Sci-Fi movies</h3>

Now we add an extra condition to the previous pattern matching, we only want to look at Sci-Fi movies:

<code>gremlin&gt;g.V().match( 
&nbsp; &nbsp; __.as("directors").hasLabel("person"), // 1st predicate 
&nbsp; &nbsp; __.as("directors").in("director").as("directed_movies"), // 2nd predicate 
&nbsp; &nbsp; __.as("directed_movies").out("actor").as("directors"), // 3rd predicate 
&nbsp; &nbsp; __.as("directed_movies").out("belongsTo").as("genres"), // 4th predicate 
&nbsp; &nbsp; __.as("genres").filter(values("name").is(eq("Sci-Fi"))) // 5th predicate 
&nbsp; &nbsp; ). 
&nbsp; &nbsp; select("directors","directed_movies"). 
&nbsp; &nbsp; dedup(). 
&nbsp; &nbsp; group(). 
&nbsp; &nbsp; &nbsp; &nbsp; by(select("directors").by("name")). 
&nbsp; &nbsp; &nbsp; &nbsp; by(select("directed_movies").by("title").fold()). unfold() 
==&gt;David Cronenberg=[The Fly] 
==&gt;M. Night Shyamalan=[Signs] 
==&gt;Kurt Wimmer=[Equilibrium] 
==&gt;George Lucas=[Star Wars: Episode III Revenge of the Sith] </code>

We added 2 extra predicates (4th and 5th) at the end to force the genres of the movies to contain “Sci-Fi”. The results are now limited to only 4 movies.

<h3>D. Movies that are both Sci-Fi and Action</h3>

<code>gremlin&gt;g.V().match( 
&nbsp; &nbsp; __.as("movies").hasLabel("movie"), 
&nbsp;&nbsp;__.as("movies").filter(out("belongsTo").values("name").is(eq("Sci-Fi"))).as("scifi_movies"), __.as("scifi_movies").filter(out("belongsTo").values("name").is(eq("Action"))).as("scifi_movies") 
). 
select("scifi_movies"). 
project("title","genres"). 
&nbsp; &nbsp;by("title"). 
&nbsp; &nbsp;by(out("belongsTo").values("name").fold()) 
==&gt;{title=Total Recall, genres=[Sci-Fi, Action]} 
==&gt;{title=Battlefield Earth, genres=[Sci-Fi, Action]} 
==&gt;{title=The Avengers, genres=[Sci-Fi, Action, Fantasy]} 
==&gt;{title=Source Code, genres=[Sci-Fi, Thriller, Action]} 
==&gt;{title=R.O.T.O.R., genres=[Sci-Fi, Action]} 
==&gt;{title=Inception, genres=[Mystery, Sci-Fi, Thriller, Action]} ==&gt;{title=Ghost in the Shell, genres=[Sci-Fi, Action, Animation]} ... </code>

It’s quite explanatory, nothing complicated here

<h3>E. Top 5 well rated Sci-Fi movies</h3>

<code>gremlin&gt;g.V().match( 
&nbsp; &nbsp; __.as("movies").hasLabel("movie"), 
&nbsp;__.as("movies").filter(out("belongsTo").values("name").is(eq("Sci-Fi"))).as("scifi_movies"),&nbsp; &nbsp;__.as("scifi_movies").dedup().order().by(inE("rated").values("rating").mean(), decr).as("well_rated_scifi") ). select("well_rated_scifi").limit(5). project("movie","rating"). 
&nbsp; &nbsp; &nbsp; &nbsp; by("title"). 
&nbsp; &nbsp; &nbsp; &nbsp; by(inE("rated").values("rating").mean()) 
==&gt;{movie=Alien Resurrection, rating=5.543478260869565} 
==&gt;{movie=Total Recall, rating=6.714285714285714} 
==&gt;{movie=Battlefield Earth, rating=2.5} 
==&gt;{movie=Eternal Sunshine of the Spotless Mind, rating=7.597701149425287} 
==&gt;{movie=Back to the Future. Part III, rating=6.604651162790698} </code>

Strangely, the results are incorrectly ordered. In fact we are hitting here the limitation I mentioned above. The ordering can only be local to the current step so in <code>__.as("scifi_movies").dedup().order().by(inE("rated").values("rating").mean(), decr).as("well_rated_scifi")</code> the traverser enters the predicate from a single sci-fi movie so there is only 1 mean rating for this single movie and ordering on it is useless. Consequently scifi_movies == well_rated_scifi

If we want the ordering, it should be done outside of the <code>match()</code> step

<code>gremlin&gt;g.V().match( 
__.as("movies").hasLabel("movie"), 
__.as("movies").filter(out("belongsTo").values("name").is(eq("Sci-Fi"))).as("scifi_movies") ). select("scifi_movies"). order().by(inE("rated").values("rating").mean(), decr). limit(5). project("movie","rating"). by("title"). by(inE("rated").values("rating").mean()) 
==&gt;{movie=Metropolis, rating=8.25} 
==&gt;{movie=A Clockwork Orange, rating=8.215686274509803} 
==&gt;{movie=Blade Runner, rating=8.20353982300885} 
==&gt;{movie=Star Wars. Episode V: The Empire Strikes Back, rating=8.121739130434783} 
==&gt;{movie=Stalker, rating=8.03191489361702} </code>

<h3>F. Recommendation engine with pattern-matching</h3>

We can re-write our classical movies recommendation engine seen in previous blog posts using pattern matching

<code>gremlin&gt;g.V().match( __.as("blade_runner").has("movie", "title", "Blade Runner"), __.as("blade_runner").map(inE("rated").values("rating").mean()).as("avg_rating"), __.as("blade_runner").map(out("belongsTo").values("name").fold()).as("genres"), __.as("blade_runner").inE("rated").filter(values("rating").where(gte("avg_rating"))).outV().as("raters_of_blade_runner"), </code>

<code>__.as("raters_of_blade_runner").outE("rated").filter(values("rating").where(gte("avg_rating"))).inV().where(neq("blade_runner")).as("potential_movies"), __.as("potential_movies").where("potential_movies", gte("avg_rating")).by(inE("rated").values("rating").mean()).by().as("filtered_movies1"), __.as("filtered_movies1").filter(out("belongsTo").has("name", where(within("genres")))).as("matching_movies") 
). 
select("matching_movies"). 
project("movie", "average_rating", "genres"). </code>

<code>&nbsp; &nbsp;by("title"). 
&nbsp; &nbsp;by(inE("rated").values("rating").mean()). 
&nbsp; &nbsp;by(out("belongsTo").values("name").fold()) 
Neither the sideEffects, map, nor path has a genres-key: WherePredicateStep(within([genres])) 
Type ':help' or ':h' for help. </code>

Against, the error is due to a bug in Gremlin, reported in <a href="https://issues.apache.org/jira/browse/TINKERPOP-1762">TINKERPOP-1762</a>.

A simple work-around right now is to add an extra <code>dedup()</code> after the <code>select()</code> step

<code>gremlin&gt;g.V().match( __.as("blade_runner").has("movie", "title", "Blade Runner"), __.as("blade_runner").map(inE("rated").values("rating").mean()).as("avg_rating"), __.as("blade_runner").map(out("belongsTo").values("name").fold()).as("genres"), __.as("blade_runner").inE("rated").filter(values("rating").where(gte("avg_rating"))).outV().as("raters_of_blade_runner"), __.as("raters_of_blade_runner").outE("rated").filter(values("rating").where(gte("avg_rating"))).inV().where(neq("blade_runner")).as("potential_movies"), __.as("potential_movies").where("potential_movies", gte("avg_rating")).by(inE("rated").values("rating").mean()).by().as("filtered_movies1"), __.as("filtered_movies1").filter(out("belongsTo").has("name", where(within("genres")))).as("matching_movies") ).&nbsp; 
&nbsp; &nbsp;select("matching_movies").dedup(). 
&nbsp; &nbsp;project("movie", "average_rating", "genres"). 
&nbsp; &nbsp; &nbsp;&nbsp;by("title"). 
&nbsp; &nbsp;&nbsp; &nbsp;by(inE("rated").values("rating").mean()). 
&nbsp; &nbsp;&nbsp; &nbsp;by(out("belongsTo").values("name").fold()) 
==&gt;{movie=Pulp Fiction, average_rating=8.581005586592179, genres=[Thriller, Action]} 
==&gt;{movie=Seven Samurai, average_rating=8.470588235294118, genres=[Action, Adventure, Drama]} 
==&gt;{movie=A Clockwork Orange, average_rating=8.215686274509803, genres=[Sci-Fi, Drama]} </code>

And that’s all folks! Do not miss the other Gremlin recipes in this series.

If you have any question about Gremlin, find me on the <a href="http://datastaxacademy.slack.com/">datastaxacademy.slack.com</a>, channel dse-graph. My id is @doanduyhai

Gremlin Recipes: 9 – Pattern Matching

Duy Hai Doan

Discover more

Share

Share

I KillrVideo dataset

II Pattern Matching in Gremlin

A. Description

B. Director who played in their own movies

C. Director who played in their own Sci-Fi movies

D. Movies that are both Sci-Fi and Action

E. Top 5 well rated Sci-Fi movies

F. Recommendation engine with pattern-matching

More Technology

How Winweb Built its AI Assistant with DataStax Astra DB and LangChain

Vercel + Astra DB: Get Data into Your GenAI Apps Fast

Simplifying Agent Development with Astra DB Connector for Vertex AI Search

Making Astra DB easier for MongoDB developers

One-stop Data API for Production GenAI