Graph data management (also called NoSQL) has revealed bene cial characteristics in terms of exibility and scalability by di erently balancing between query expressivity and schema exibility. This peculiar advantage has resulted into an unforeseen race of developing new task-speci c graph systems, query languages and data models, such as property graphs, key-value, wide column, resource description framework (RDF), etc. Present-day graph query languages are focused towards exible graph pattern matching (aka sub-graph matching), whereas graph computing frameworks aim towards providing fast parallel (distributed) execution of instructions. The consequence of this rapid growth in the variety of graph-based data management systems has resulted in a lack of standardization. Gremlin, a graph traversal language, and machine provide a common platform for supporting any graph computing system (such as an OLTP graph database or OLAP graph processors). In this extended report, we present a formalization of graph pattern matching for Gremlin queries. We also study, discuss and consolidate various existing graph algebra operators into an integrated graph algebra.
Upon observing the evolution of information technology, we can observe a trend from data models and knowledge representation techniques being tightly bound to the capabilities of the underlying hardware towards more intuitive and natural methods resembling human-style information processing. This evolution started with machine assembly languages, went over procedural programming, object-oriented methods and resulted in an ever more loosely coupling of data and code with relational data bases, declarative query languages and object-relational mapping (ORM). In recent years, we can observe an even further step in this evolution { graph Copyright c 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
based data models, which organize information in conceptual networks.
Graphs are valued distinctly, when it comes to choosing formalisms for
modelling real-world scenarios such as biological, transport,
communication and social networks due to their intuitive data model. In particular,
the property graph data model is capable of representing complex domain
networks [
Graph analysis tools have turned out to be one of pioneering
applications in understanding these natural and man-made networks [
These modern graph query languages focus either on traversal, where
traversers move over vertices and edges of a graph in a user de ned
fashion or on pattern-matching, where graph patterns are matched against the
graph database. Gremlin [
In this work, we present an extended version of our earlier work [
As a result, the formalization of graph query algebra supports the
integration and interoperability of di erent graph data models [
The remainder of this article is organised as follows: section 2 describes the preliminaries including property graphs, graph pattern matching, and foundations of relational algebra. section 3 elaborates on Gremlin as a traversal language and machine, and discusses synergy of GPM and its evaluation in Gremlin. section 4 proposes the Gremlin to graph algebra mapping algorithm. section 5 surveys related work. In section 6 we conclude this article and discuss future work. 2
In this section, we present and summarise the mathematical concepts
used in this article. Our notation closely follows [
Property graphs, also referred to as directed, edge-labeled, attributed
multi-graphs, have been formally de ned in a wide variety of texts, such
as [
is the set of Labels, { is a function that assigns labels to the edges and vertices (i.e.
V [ E ! )3, and
V ) where Lab
:
3 set of strings ( )
is a partial function that maps elements and keys to values (i.e.
: (V [ E) R ! S) i.e. properties (key r 2 R, value s 2 S). tu
For simplicity, we de ne disparate sets (of and ) for the labels and
properties of vertices and edges respectively, adapting the terminology
used in [
GPM queries can represented by two types of graph patterns [
A GPM is evaluated by matching, a sub-graph pattern over a graph G.
Matching has been formally de ned in various texts and we summarise
a formal de nition in our context which closely follows the de nition
provided by [
Example 2. We illustrate the evaluation of graph patterns (a) and (b) from Figure 2, over the graph G from Figure 1.
(a) v[
In Gremlin, GPM is performed by traversing9 over a graph G. A
traversal t over G derives paths of arbitrary length. Therefore, a GPM
query in Gremlin can be perceived as a path traversal. Rodriguez et al. [
Moreover, from [
We present a consolidated summary of various graph query operators
de ned in the literature [
Projection ( a;b;::) : R [ S ! : operator projects values of a speci c set of variables a; b; ::; n (i.e. keys and elements), from the solution of a matched input graph pattern P , against the graph G. Moreover, the results returned by ( a;b) are not deduplicated be default, i.e. the result will contain as many possible matched values or items as the input pattern P . This operator is present in all standard graph query languages (e.g. SELECT in SPARQL, and MATCH in CYPHER).
Selection (9(p)), is analogous to the lter operator ( ), as de ned in [
Concatenation [
Union operator (]): P (E ) P (E ) ! P (E ) : is the multiset union11
(bag union) of two path traversals or graph patterns. For instance, f(1,2),
(3,4), (3,4), (4,5)g ] f(1,2), (3,4)g = f(1,2), (1,2), (3,4), (3,4), (3,4),
(4,5)g. The results of this operator, like projection, are not deduplicated
by default.
11 Note that the domains and ranges of each of these sets are the power sets.
Join [
P ./ R = f(v1; e1; v2; v2; e2; v3); (v1; e1; v2; v2; e2; v1)g, where v1; v2; v3 2 V ; e1; e2 2 Le.
Left -join (d|><|), Right -join (|><|d) and the Anti -join (.) operators: these
operators, are not explicitly implemented in Gremlin, unlike in other graph
query languages [
General Extensions. We borrow the extended relational operators
Grouping (ya(p)), Sorting (<*a;+b(p)) and Deduplication ( a;b;::(p)) which
have been de ned in [
Graph-speci c Extensions. Various graph/traversal-speci c operators
have been de ned in works such as [
{ The Get-vertices/Get-edges nullary operators (Vg/ Eg): return the list of vertices/edges, respectively. These operators, w.r.t. Gremlin query construct, denote the start of a traversal. It is also possible to traverse from a speci c vertex/edge in a graph, given their id's. Furthermore, they can be used to construct custom indexes over elements depending on user's choice. 12 Here, ( ; +) denote the rst and last elements of a path respectively. Gremlin is the query language of Apache TinkerPop13 graph computing framework. Gremlin is system agnostic, and enables both { pattern matching (declarative) and graph traversal (imperative) style of querying over graphs.
The Machine. Theoretically, a set of traversers in T move (traverse) over a graph G (property graph, cf. Section 2.1) according to the instruc13 Gremlin: Apache TinkerPop's graph traversal language and machine (https:// tinkerpop.apache.org/) tion in ( ), and this computation is said to have completed when there are either: 1. no more existing traversers (t), or 2. no more existing instructions ( ) that are referenced by the traversers (i.e. program has halted).
Result of the computation being either a null/empty set (i.e. former case)
or the multiset union of the graph locations (vertices, edges, labels,
properties, etc.) of the halted traversers which they reference. Rodriguez et
al. [
The Traversal. A Gremlin graph traversal can be represented in any
host language that supports function composition and function nesting.
These steps are are either of:
1. Linear motif - f g h, where the traversal is a linear chain of steps;
or
2. Nested motif - f (g h) where, the nested traversal g h is passed
as an argument to step f [
A step (f 2 ) can be, de ned as f : A? ! B?15. Where, f maps a set of traversers of type A (located at objects of A) to a set of traversers of type B (located at objects of B). Given that Gremlin is a language 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). As a result, there exists various Gremlin dialects such as Gremlin-Groovy, Gremlin-Python, etc.
A Gremlin traversal ( ) can be compiled down to a collection of steps
or instructions which form the Gremlin instruction set. The Gremlin
instruction set comprises approximately 30 steps which are su cient to
provide general purpose computing and for expressing the common motifs of
14 The bulk of a traverser is number of equivalent traversers a particular traverser
represents.
15 The Kleene star notation (A?; B?) denotes that multiple traversers can be in the
same element (A,B).
any graph traversal query, as highlighted by [
Gremlin provides the GPM construct, analogous to SPARQL [
Each traversal is a path query starting at a particular source (A)
and terminating at a destination (B) by visiting vertices (v 2 V) and
edges (e 2 E (V V) ) in an alternating fashion (i.e. referred to as
traversing [
Listing 1.1. Return the age of the oldest person marko knows
Here, g.V() i.e. Vg is the traverser de nition bijective to V where, ]i ((Vg)i)
= V. Functionally, this query be written using function currying as:
(2)
The terms outknows, valuesage and hasname are the single-step
Gremlin operations/traversals. In [
The match()-step17 evaluates the input graph patterns over a graph G
in a structure preserving manner binding the variables and constants to
their respective values (cf. De nition 2). We denote the evaluation of
a traversal t over a graph G, using the notation [[t]]g which is borrowed
from [
However, the order of execution of each graph pattern is up to the match()-step implementation, where the variables and path labels are local only to the current match()-step. Due to this uniqueness of the Gremlin match()-step it is possible to: 1. treat each graph pattern individually as a single step traversal and thus, construct composite graph patterns by joining (path-joins) each of these single step traversals; 2. combine multiple match()-steps for constructing complex navigational traversals (i.e. multi-hop queries), where each composite graph pattern (from a particular match()-step) can be joined using the concatenative join (ref. Section 2.3).
For instance, consider the GPM gremlin query as shown in Listing 1.2. 1 g .V( ) . match ( 2 . as ( ' a ' ) . out ( ' c r e a t e d ' ) . as ( ' b ' ) , 3 . as ( ' b ' ) . has ( ' name ' , ' l o p ' ) , 4 . as ( ' b ' ) . i n ( ' c r e a t e d ' ) . as ( ' c ' ) , 5 . as ( ' c ' ) . has ( ' age ' , 3 0 ) ) . s e l e c t ( ' a ' , ' c ' ) . by ( ' name ' ) Listing 1.2. This traversal returns the names of people who created a project named 'lop' that was also created by someone who is 30 years old.
Each of the comprising four graph patterns (traversals) of the query
(listing 1.2), can be individually represented using the curried functional
notation as described in Equation 2. Thus,
17 http://tinkerpop.apache.org/docs/3.2.3/reference/#match-step
18 Meaningful names can be used as variable names for enhancing query readability.
19 Rodriguez et al. [
The input arguments of the match()-step are the set of graph patterns de ned above in equations 4,5, which form a composite graph pattern (the nal traversal ( )). At run-time, when a traverser enters match()step, it propagates through each of these patterns guaranteeing that, for each graph pattern, all the pre x and post x variables (i.e. "a", "b", etc) are binded with their labelled path values. It is only then allowed to exit, having satis ed this condition. In simple words, though each of these graph patterns is evaluated individually, it is made sure that at runtime, the overall structure of the composite graph pattern is preserved by mapping the path labels to declared variables.
For instance, in the query (ref. listing 1.2), the starting vertex of g(i) labelled as "b" which is the terminal vertex of f (i), similarly for h(i) and j(i) with vertex labelled as "c". It is therefore necessary, to keep a track of the current location of a traverser in the graph, to preserve traversal structure. This is achieved in Gremlin by match() and bind() functions respectively, which we outline next.
The evaluation of an input graph pattern/traversal in Gremlin is taken care by two functions: 1. the recursively de ned match() function- which evaluates each constituting graph pattern and keeps a track of the traversers location in the graph (i.e. path history), and, 2. the bind() function- which maps the declared variables (elements and keys) to their respective values.
Using equations (4, 5) (curried functional form of path traversals) in the
recursive de nition of match() by [
In this section, we present a mapping algorithm for encoding a given Gremlin pattern-matching traversal, relational graph algebra. Figure 4, describes the conceptual architecture for formalizing Gremlin traversals. We follow a bottom-up approach in order to construct the relational graph algebra based on the traversal. 4.1
Mapping Gremlin traversals to Graph Algebra 1. The input query is parsed and its constituent individual graph patterns are extracted from the match()-step and the optional where() step. /* Parse step 2. For each single graph patterns (single path traversals) in the query, we rst construct the curried functional form (ref. equation 2). 3. We then map the get-vertices/get-edges operator for the encountered g.V()/g.E() step (i.e. to the rst graph pattern) respectively. /* Steps 2-12 are the Build steps 4. Append a traverse-operator to all the respective in-coming and outgoing edge traversals for each, that appear inside the match()-step. 5. Append a property- lter operator to all the respective has() and values() steps based on the match()-step. 6. Multiple match() steps can be connected processed using the concatenative join operator. 7. Append a selection operator, if the match() step is succeeded by a where() step (this is an optional in gremlin queries). 8. Append a projection operator, if select()-step is declared with a match() or where() step. 9. Append a deduplication operator, based on whether the dedup() step is declared after the select() step. 10. Append a sorting operator, if the order() step with an optional by() modi er is declared after the select() step. 11. Append a grouping operator, if the group() step with an optional by() modi er is declared after the select() step. 12. Map the union operator if the query contains a union()-step20. Union is technically a binary operator, however, a union of multiple patterns can be constructed using a left deep join tree representation.
Next we present three examples of gremlin traversals which have been formalised using the proposed graph relational algebra.
Example Query 1. The sample query as shown in listing 1.2, can be formalized as: yname a;c J age=30 #bc [created] nbame=lop "ba [created](Vg)Kg
c | {tz } (8) Example Query 2. Consider the following gremlin traversal shown in listing 1.3 below: 1 g .V( ) . match ( 2 . as ( ' a ' ) . h a s L a b e l ( ' p e r s o n ' ) . v a l u e s ( ' age ' ) . as ( ' b ' ) ) .
s e l e c t ( ' b ' ) . o r d e r ( ) . by ( a s c )
Listing 1.3. This traversal returns the list all the persons in the ascending order of
the age.
20 It is not a common practice to use a union()-step in Gremlin GPM traversals, as
multiple match()-steps in conjunction with where()-steps can be used as per required
(the ad in nitium style of traversing [
The gremlin traversal shown above (Listing 1.3) can be formalized as follows:
b a bJ age label=person(Vg)Kg | {tz } (9) (10) 1 g .V( ) . union ( 2 . match ( 3 . match ( . as ( ' a ' ) . out ( ' c r e a t e d ' ) . as ( ' c ' ) ) , . as ( ' b ' ) . out ( ' c r e a t e d ' ) . as ( ' c ' ) ) ) . s e l e c t ( ' a ' , ' c ' ) Listing 1.4. This traversal returns the list of all the people who have collaboratively created a software.
The gremlin traversal shown above (Listing 1.4) can be formalized as follows: b;c J"ca [created](Vg)Kg ] J"bc [created](Vg)Kg | }
t = {t1z] t2
Optimizations. The Gremlin graph traversal machine inherently o ers a
wide variety of machine and query level optimizations as traversal
strategies including (i) query rewriting (decoration), (ii) traversal optimization,
(iii) vendor optimization (using byte-code for gremlin language variants),
(iv) nalization, and (v) veri cation. We will not go into the speci c
details, rather we point the interested reader to (Section 4, page 6-7 of [
This section summarizes work towards formalizing query algebras for
different data models and corresponding query languages.
Property graphs. The Property Graph data model is one of the
popular graph data models that provides a rich set of features for the user
to model domain-speci c real world data. Various query languages have
been proposed over the years for querying over PGs. The Cypher query
language21, native to the Neo4J PG database, is a high-level declarative
pattern matching-based graph query language. The developers of Neo4J
& Cypher strive at standardizing Cypher by providing open formal
speci cation via the OpenCypher22 project [
RDF: The Resource Description Framework (RDF), is another graph
data model, popular in the semantic web domain. In RDF the data (i.e.,
entity descriptions) are stored as triples, similar to the node-edge
formalism in PGs. SPARQL [
SQL: Relational databases cater rather limited support for executing
graph queries. However, certain databases such as PostgreSQL allow the
execution of recursive queries. The SAP HANA Graph Scale-Out
Extension prototype (GSE), using a SQL-type language proposed by [
In this extended paper, we presented the initial e orts on formalizing
GPM traversals, which is a subset of the Gremlin traversal language
and machine. Since, Gremlin is both a query language and a machine,
it enables the graph (pattern-match) traversals to be represented in any
formal query language, given that it supports function composition and
nesting. Our current work provides a theoretical foundation to leverage
21 https://neo4j.com/developer/cypher-query-language/
22 http://www.opencypher.org/
this advantage of Gremlin for querying graphs on various graph engines.
Furthermore, our current work lays the foundation for supporting query
interoperability by allowing translation of SPARQL queries to Gremlin
GPM traversals [
This work is supported by the funding received from EU-H2020 Framework Programme under grant agreement No. 780732 (BOOST4.0)