REVIEW 4 major objections 6 minor 27 references
Towards an Integrated Graph Algebra for Graph Pattern Matching with Gremlin (Extended Version)
T0 review · 4 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Gremlin's match()-step graph pattern matching has a formal algebraic specification: every query in the covered subset rewrites into an equivalent expression in an integrated graph algebra.
desk verdict Useful consolidation and a plausible mapping recipe, but the formal core (Eq. 6 and the mapping proof) doesn't hold up; treat as a sketch, not a specification. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing mechanism is the recursive definition of match() (Equation 6) together with the bind() function (Equation 7). match() evaluates each graph pattern inside a match()-step as a single path traversal, with as()-modulated variables marking the start and end of each pattern, and it appends hidden path labels so that every pattern is executed exactly once; bind() then forces the variable named by a label to equal the traverser's current location, or to remain consistent with an earlier binding. Around this recursion the paper builds a twelve-step mapping algorithm (Section 4, steps 1–12) that converts a parsed Gremlin traversal into curried functional form and replaces each step with a consolidated algebra operator, ending with an algebraic expression that mirrors the traversal's structure. The path algebra of concatenation and concatenative join supplies the composition operation that ties patterns together.
What would settle it
Take a Gremlin match() query in the covered subset, translate it with the twelve-step algorithm, and run both the original traversal and the algebraic expression on the same property graph; any disagreement in the returned answers (with duplicates counted), or any valid covered query that the algorithm cannot rewrite, would refute the claimed equivalence. Because the paper leaves pattern execution order to the implementation, reordering the patterns inside match() and observing a different result set would likewise show that the order-independent algebra does not capture the language's actual semantics.
Extended reading notes
Core claim
The paper claims that every Gremlin graph-pattern-matching traversal in the covered subset—a match()-step built from path patterns with as()-labelled endpoints, optionally followed by where(), select(), dedup(), order(), group(), or union()—denotes the same computation as a specific expression in the integrated graph algebra. The equivalence is constructive: each pattern inside match() is first put into curried functional form, then translated step by step into operators (get-vertices, get-edges, traverse, property filter, selection, projection, deduplication, sorting, grouping, concatenative join, union), and the resulting operators are assembled in the order fixed by the query. The paper demonstrates the translation on three queries, producing, for example, a grouped projection over a concatenative join of filtered traversals for the running 'created'-by-people query, and a union expression for a collaborative-creation query. The algebraic reading is faithful because the recursion that defines match() treats each pattern as an independent path traversal and uses bind() to force labelled variables to agree, which is exactly the matching condition that the concatenative join encodes.
Load-bearing premise
The mapping assumes that Gremlin's actual match()-step evaluates each graph pattern as an independent path traversal and joins patterns only by requiring labelled variables to coincide, with the order of pattern execution having no effect on the result.
Editorial extensions
If this is right
- A Gremlin query compilation engine can be built on the algebra: translate a match() pattern query into the integrated algebra, optimize the algebraic expression, and then execute it on any Gremlin-based system.
- The same algebraic foundation allows other declarative graph query languages, such as SPARQL, to be translated into Gremlin pattern-matching traversals, making property graphs and RDF stores interoperable through one query language.
- Query planning for Gremlin pattern matching can be studied at the algebra level, since the mapping fixes the order in which selection, projection, grouping, and joins are composed.
- The three worked examples establish a pattern for formalizing more of Gremlin's declarative surface: each new step type is handled by adding one operator at the corresponding position in the mapping.
Reading between the lines
- A testable extension the paper leaves implicit: if the recursive match() semantics is order-independent, then the algebra's multiset results must coincide for every ordering of patterns within match(); one could verify this on a Gremlin engine by permuting the patterns of Listing 1.2 and checking that the multiset of returned names is unchanged.
- The mapping suggests a natural optimization space: rewrite the algebraic expression by pushing property filters below joins or reordering concatenative joins, in the same spirit as relational query optimization, and compare the resulting plans against the Gremlin machine's default traversal order.
- One could extend the algebra to cover the imperative side of Gremlin (e.g., repeat()-based paths or side-effect steps) by adding operators for path concatenation under repetition; the paper's operator consolidation gives the starting vocabulary for that extension.
- The dependence on hidden path labels in Equation 6 implies that an implementation must track more than visible variables; a future formal proof of the mapping would need to make those labels explicit in the algebra, for instance as an extra projection layer.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper proposes an integrated graph algebra for graph pattern matching (GPM) in Gremlin. After reviewing existing graph algebra operators from the literature and defining a consolidated set including two newly proposed traversal and property-filter operators, the authors present a mapping algorithm (Section 4, steps 1–12) that translates Gremlin match()-based queries into expressions of this algebra. The central claim is that this mapping provides a formal specification of Gremlin's pattern matching construct that can serve as the foundation for a Gremlin query compilation engine. The paper also discusses the Gremlin machine, reproduces a recursive definition of match() from prior work, and gives three worked examples of the mapping.
Significance. If the formalization were correct and complete, the paper would be a useful step toward query interoperability and compilation for Gremlin, a widely used graph traversal language. The paper usefully consolidates operators from prior work and explicitly delimits the fragment of Gremlin under study. However, the technical core—the recursive match() semantics and the mapping algorithm—is presented at a level of precision that is insufficient to support the claimed formal specification. The worked examples are helpful for intuition but do not provide the required correctness evidence. The contribution is therefore currently at the level of a proposal rather than a verified formalization.
major comments (4)
- [Section 3.2, Eq. (6)] The recursive definition of match() is not well-formed. The hidden path labels Δ_m1 through Δ_m4 are never defined; the guard 'Δ_b ≠ φ = Δ_m2' mixes an inequality and an equality in a way that is not syntactically well-formed; no cases are given for pattern sets of size other than four or for disconnected patterns; and no induction measure is specified, so Eq. (6) is not a recursive definition in the usual sense. Since Eq. (6) is the paper's formal handle on Gremlin match() semantics, the mapping in Section 4 lacks a well-defined source semantics.
- [Section 3.2] The paper states that the order of execution of the graph patterns inside match() is 'up to the match()-step implementation,' but Eq. (6) fixes a specific evaluation order and no theorem shows that the result is invariant under reordering. If the real Gremlin match() is not commutative for the supported fragment, the formalization would not be faithful to the language. The authors should either prove commutativity or define the semantics as the set of solutions independent of pattern order.
- [Section 4] The mapping algorithm (steps 1–12) is presented operationally, but no theorem states or proves that the produced algebra expression has the same semantics as the input Gremlin traversal. The worked examples in Eqs. (8)–(10) illustrate the intended translation but cannot establish correctness for the whole covered subset. Without a correctness proof, the claim that the mapping can serve as a 'foundation for implementing a Gremlin based query compilation engine' is not supported.
- [Section 4.1, Eq. (10)] The expression Π_{b,c}( ... union ... ) is ill-typed under the operator signatures given in Section 2.3. The first operand of the union binds variables a and c, while the second binds b and c; projection over b is therefore not defined on the first operand, and the union of two relations with different schemas is not defined in the presented algebra. This example needs to be corrected or removed.
minor comments (6)
- [Section 2.3, Projection] The type signature 'R∪S → Σ*' for the projection operator is unclear; projection should map a bag of matches to a bag of tuples over the projected variables.
- [Section 2.3, Join] The notation γ−(p) and γ+(p) is used in the join definition but is never formally defined; the short explanation 'first and last elements of a path' is insufficient for paths defined as edge sequences.
- [Section 3.2, Eq. (7)] The cases in the definition of bind_x(t) are not mutually exclusive; in particular, the condition 'Δ_x(t) = μ'(t)' needs a clearer statement of what it means for a path label to be equal to a traverser's graph location.
- [Abstract] The phrase 'resulted into an unforeseen race' is ungrammatical, and 'relational data bases' should be 'relational databases.'
- [Section 1, footnote 2] The email address 'dpunjani@di.uoa.gr' does not match the listed author names; this seems to be an artifact of the author list and should be corrected.
- [Section 4.1, Optimizations] The paragraph on optimizations lists several traversal strategies without connecting them to the proposed mapping; either elaborate on their relevance or shorten the paragraph.
Circularity Check
No circularity: the paper translates Gremlin match() into an integrated algebra using independently sourced semantics and operators; its limitations are completeness and proof gaps, not circular derivation.
full rationale
The paper's central construction is a mapping from Gremlin GPM traversals to graph algebra operators (Section 4). The source semantics are taken from Rodriguez's external path-algebra and Gremlin-machine papers [16,17,18], and the algebra operators from [9,13,18]; none of these are the authors' own prior results, so the derivation does not reduce to its own inputs. Equation (6) and bind() (Eq. 7) are imported as assumed definitions of match(), not derived from the algebra; the mapping then composes operators according to those definitions. No parameter is fitted to data, and no 'prediction' is subsequently tested against the same data. The only self-citations ([23,24,25]) concern SPARQL-to-Gremlin interoperability and the earlier version of this report; they are not load-bearing for the algebraic mapping. The stated limitations (incomplete coverage of Gremlin, no proof connecting Eq. (6) to the mapping) are correctness and completeness concerns about under-specification, not instances of equation X reducing to equation Y by construction. Hence no circular step can be exhibited from the text.
Assumptions & free parameters
assumptions (4)
- domain assumption Gremlin traversal machine and match()-step semantics are as defined in [16].
- domain assumption The consolidated graph algebra operators from [9,13,18,17] are sufficient and correctly represent graph pattern matching for the covered Gremlin subset.
- domain assumption Property graph and graph pattern matching definitions from [17,8,1] are valid.
- ad hoc to paper The proposed Traverse and Property filter operators faithfully capture the Gremlin .out()/.in() and .has()/.values() steps.
Cite this review
Pith. "Pith review of Towards an Integrated Graph Algebra for Graph Pattern Matching with Gremlin (Extended Version)." pith.science (2026). https://pith.science/paper/H6ZOSVFT
@misc{pith2026190806265,
author = {Pith},
title = {Pith review of: Towards an Integrated Graph Algebra for Graph Pattern Matching with Gremlin (Extended Version)},
year = {2026},
howpublished = {\url{https://pith.science/paper/H6ZOSVFT}},
note = {Machine review of arXiv:1908.06265}
}
read the original abstract
Graph data management (also called NoSQL) has revealed beneficial characteristics in terms of flexibility and scalability by differently balancing between query expressivity and schema flexibility. This peculiar advantage has resulted into an unforeseen race of developing new task-specific 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 flexible 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 provides a common platform for supporting any graph computing system (such as an OLTP graph database or OLAP graph processors). 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.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
- [1]
- [2]
-
[3]
R. Angles et al. The multiset semantics of SPARQL patterns. In The Semantic Web - ISWC -15th International Semantic Web Conference, Kobe, Japan , pages 20–36, 2016
work page 2016
-
[4]
R. Angles and C. Gutierrez. The expressive power of sparql. In International Semantic Web Conference, pages 114–129. Springer, 2008
work page 2008
- [5]
-
[6]
H. Garcia-Molina, J. D. Ullman, et al. Database systems: the complete book. Pear- son Education India, 2009
work page 2009
-
[7]
L. Gomes-Jr, B. Amann, et al. Beta-algebra: Towards a relational algebra for graph analysis, 2015
work page 2015
-
[8]
A. Gubichev and M. Then. Graph pattern matching: Do we have to reinvent the wheel? In Proceedings of Workshop on GRAph Data management Experiences and Systems, pages 1–7. ACM, 2014
work page 2014
Show all 27 references
-
[9]
H¨ olsch and M
J. H¨ olsch and M. Grossniklaus. An algebra and equivalences to transform graph patterns in neo4j. InEDBT/ICDT 2016 Workshops: EDBT Workshop on Querying Graph Structured Data (GraphQ), 2016
2016
-
[10]
Keswani, H
Y. Keswani, H. Thakkar, M. Dubey, J. Lehmann, and S. Auer. The litmus test: Benchmarking rdf and graph data management systems. In Proceedings of 13th International Conference on Semantic Systems-Poster & Demos , 2017
2017
-
[11]
Krause et al
C. Krause et al. An sql-based query language and engine for graph pattern matching. In International Conference on Graph Transformation , pages 153–169. Springer, 2016
2016
-
[12]
C. Li, K. C.-C. Chang, et al. Ranksql: query algebra and optimization for relational top-k queries. In Proceedings of the 2005 ACM SIGMOD international conference on Management of data , pages 131–142. ACM, 2005. 16
2005
-
[13]
G. S. J. Marton. Formalizing opencypher graph queries in relational algebra. Published online on FTSRG archive , 2017
2017
-
[14]
P´ erez, M
J. P´ erez, M. Arenas, et al. Semantics and complexity of sparql. In International semantic web conference, pages 30–43. Springer, 2006
2006
-
[15]
Prud et al
E. Prud et al. Sparql query language for rdf. Citeulike Online Archive, 2006
2006
-
[16]
M. A. Rodriguez. The gremlin graph traversal machine and language (invited talk). In Proceedings of the 15th Symposium on Database Programming Languages, Pittsburgh, PA, USA, pages 1–10, 2015
2015
-
[17]
M. A. Rodriguez and P. Neubauer. The graph traversal pattern. In Graph Data Management: Techniques and Applications. , pages 29–46. IGI Global, 2011
2011
-
[18]
M. A. Rodriguez and P. Neubauer. A path algebra for multi-relational graphs. In Workshops Proceedings of the 27th International Conference on Data Engineering, ICDE 2011, pages 128–131, 2011
2011
-
[19]
Schmidt, M
M. Schmidt, M. Meier, et al. Foundations of sparql query optimization. In Proceed- ings of the 13th International Conference on Database Theory , pages 4–33. ACM, 2010
2010
-
[20]
Sz´ arnyas et al
G. Sz´ arnyas et al. opencypher specification. Online FTSRG archive, 2017
2017
-
[21]
H. Thakkar. Towards an open extensible framework for empirical benchmarking of data management solutions: LITMUS. In European Semantic Web Conference, pages 256–266. Springer, 2017
2017
-
[22]
Thakkar, Y
H. Thakkar, Y. Keswani, M. Dubey, et al. Trying not to die benchmarking: Orches- trating RDF and graph data management solution benchmarks using LITMUS. In Proceedings of the 13th International Conference on Semantic Systems, SEMAN- TICS 2017, Amsterdam, The Netherlands, Septe...
2017
-
[23]
Thakkar, D
H. Thakkar, D. Punjani, et al. A stitch in time saves nine–SPARQL querying of property graphs using gremlin traversals. arXiv:1801.02911, 2018
2018 arXiv
-
[24]
Thakkar, D
H. Thakkar, D. Punjani, J. Lehmann, and S. Auer. Two for one: Querying property graph databases using SPARQL via gremlinator. InProc. of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA) , p...
2018
-
[25]
Thakkar, D
H. Thakkar, D. Punjani, M.-E. Vidal, and S. Auer. Towards an integrated graph algebra for graph pattern matching with gremlin. In Proceedings of the 28th Inter- national Conference, DEXA 2017, Lyon, France, August 28-31, 2017, Proceedings, Part I, pages 81–91. Springer, 2017
2017
-
[26]
Unger, A
C. Unger, A. N. Ngomo, et al. 6th open challenge on question answering over linked data (QALD-6). In Semantic Web Challenges - Third SemWebEval Challenge at ESWC 2016, Heraklion, Crete, Greece, pages 171–177, 2016
2016
-
[27]
van Rest, S
O. van Rest, S. Hong, et al. Pgql: a property graph query language. In Proceedings of the Fourth International Workshop on Graph Data Management Experiences and Systems, page 7. ACM, 2016. 17
2016
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.