Foundations of Modern Query Languages for Graph Databases

• The survey bridges theory and practice by organizing graph query languages around features, for researchers and practitioners interested in graph databases.It relates theoretical notions to practical languages and explains how foundational features help understand and compare them.Source: §1 · pp. 1–3
• The survey defines core features, examines their evaluation semantics and computational complexity, and illustrates them with SPARQL, Cypher, and Gremlin examples.It also discusses important extensions implemented in modern graph database engines.Source: §1 · pp. 2–3
• The concluding discussion connects features to expressivity and complexity, and considers formalization, implementation and optimization challenges, and possible future directions.Source: §1 · p. 2
• Its novel contributions include a formalization of property graphs, comparisons of practical language features and semantics, and examples of how language design affects query-evaluation complexity.These contributions complement prior surveys by explaining basic features in practical languages alongside theoretical aspects.Source: §1 · p. 3
• It covers edge-labelled and property graphs, graph patterns and their operators, and navigational expressions for arbitrary-length paths, branches, and recursive pattern matching.The survey focuses on these two models because they are flexible enough for most practical scenarios and contain fundamental graph-querying issues.Source: §1 · pp. 2–3

Edge-labelled graphs

• Edge-labelled graphs represent edges as labelled triples between finite sets of nodes, distinguishing relationship types while allowing unrestricted graph topology, including cycles.For example, acts_in and directs distinguish an actor’s roles in a movie.Source: §2 · pp. 4–5
• Role nodes let edge-labelled graphs represent repeated roles and additional role information, while also supporting more complex n-ary relations.The example records an actor’s multiple roles in one movie and the on-screen time for each character.Source: §2 · p. 5

Property graphs

• Property graphs attach labels and property–value attributes directly to identified nodes and edges, allowing metadata to be added without restructuring complex relations as nodes.They can also represent distinct edges with the same label between the same nodes and add attributes to those edges.Source: §2 · p. 6
• A property graph has finite node and edge sets, directed edges, labels on both, and a partial function assigning attribute values; this section focuses on the single-valued variant.A multi-valued variant can instead allow multiple labels and property values.Source: §2 · pp. 6–7
• The section uses “graph databases” for edge-labelled and property graphs, and “graph database engines” for systems implementing either model.Source: §2 · p. 7

3. GRAPH PATTERNS

• SPARQL, Cypher, and Gremlin share graph pattern matching as a conceptual core, alongside graph navigation, which is covered separately.Graph patterns match a graph-structured query against a graph database and are used in applications including chemical structure analysis, machine learning, planning, semantic networks, and pattern recognition.Source: §3 · p. 8

3.1. Basic graph patterns

• A basic graph pattern uses variables in a graph-shaped query, and a match maps them to constants while preserving the query structure in the database.Homomorphism-based matching permits multiple variables to map to the same term; injective mappings instead yield subgraph-isomorphism-style matching. Homomorphism-based and isomorphism-based decision problems can be NP-complete, and complete matches may be rigid.Source: §3.1 · pp. 8–12
• Simulation-based semantics can match one query node to several graph nodes, offering a more flexible alternative that is computationally lighter for some problems.It can also be more versatile for large graphs with incomplete information, although the surveyed languages do not support simulation-based partial matches for basic graph patterns.Source: §3.1 · pp. 12–13

3.2. Complex graph patterns

• Complex graph patterns extend basic patterns with projection, union, difference, optional, and filter; projection selects a subset of output variables.For basic graph patterns, set and bag semantics are equivalent, but extensions such as projection and union can produce duplicate matches and distinguish them.Source: §3.2 · pp. 13–14, §3.1 · p. 13
• Complex graph patterns compose subquery results with compatible-match joins, set union, and difference, though difference is computationally harder and may be omitted.An explicit join is needed to combine results from operations beyond basic graph patterns.Source: §3.2 · p. 14
• Optional matching preserves unmatched left-side results with undefined values, while filters restrict matches without changing output variables.Optional matching supports partial answers over incomplete information; filters can use inequalities, boolean connectives, and other expressions.Source: §3.2 · pp. 14–15

3.3. Graph patterns in practice

• SPARQL combines triple patterns into basic graph patterns and evaluates them with homomorphism-based bag semantics.In the examples, UNION can return :Unforgiven twice, and OPTIONAL preserves Anna Levine's result with the unavailable value left blank.Source: §3.3 · pp. 16–17
• Cypher uses pictorial patterns over property graphs with isomorphism-based no-repeated-edge bag semantics; separate MATCH clauses perform a natural join that permits repeated actors.Patterns encode nodes, edges, labels, and property values, while RETURN projects results.Source: §3.3 · pp. 17–18
• Cypher also supports union, difference, optional matching, and filters, with UNION ALL retaining duplicates and optional matching preserving Anna Levine's result.The examples use NOT for difference and filter other participation edges by type.Source: §3.3 · pp. 18–19
• Gremlin expresses patterns through imperative, functional-feeling traversals, which are especially natural for paths and use homomorphism-based bag semantics.The co-actor example traverses from Clint Eastwood to movies and then follows acts_in edges in reverse to people.Source: §3.3 · pp. 19–20
• Gremlin uses traversals, as variables, and match to express BGPs with branches and cycles; inner traversals form tree-shaped patterns that are joined.Filters can constrain bindings, and select projects the output, as in the example returning co-stars but not their shared movie.Source: §3.3 · p. 20
• Gremlin’s main focus is navigational queries, and its current version has limited declarative support for complex patterns, with no explicit optional operator.It supports BGPs, filters, and projection; union exists and difference can be emulated with drop [Apache TinkerPop 2016a].Source: §3.3 · p. 20

3.4. The complexity of evaluating graph patterns

• BGPs with projection are NP-complete under homomorphism and the three considered isomorphism-based semantics, but polynomial-time under simulation semantics.These results hold under both set and bag semantics; for fixed queries, evaluation is in logarithmic space across all considered semantics [Abiteboul et al. 1995].Source: §3.4 · p. 21
• More cyclical patterns are generally harder to evaluate, a relationship captured by treewidth.The complexity of conjunctive graph patterns has not been studied for Cypher or Gremlin, leaving open opportunities for investigation.Source: §3.4 · p. 21
• For SPARQL under set semantics, projection, join, union, and filter yield NP-complete combined complexity, while adding difference and optional yields PSPACE-complete complexity.PSPACE-completeness also holds without MINUS, and even when only join and optional are allowed; under bag semantics, SPARQL evaluation remains PSPACE-complete.Source: §3.4 · p. 21

4. NAVIGATIONAL QUERIES

• Navigational queries cover arbitrary-length path queries and repeated graph patterns, with applications including the Semantic Web, provenance, route finding, and biological networks.The section first focuses on path queries, then discusses combining them with graph patterns.Source: §4 · p. 22

4.1. Path Queries

• Regular Path Queries use regular expressions over edge labels to constrain paths; Two-way RPQs add inverse traversal, and RPQ-like features appear in SPARQL property paths and Cypher.Regular expressions support concatenation, union, and repetition; inverse traversal enables following edges backwards.Source: §4.1 · pp. 22–23
• Path-query evaluation may use arbitrary, shortest, no-repeated-node, or no-repeated-edge semantics, which determine which matching paths are included.Arbitrary-path semantics can yield infinitely many paths; shortest-path semantics returns minimal-length matches, while the latter two restrict repeated nodes or edges.Source: §4.1 · pp. 24–25
• Path-query results may be Boolean answers, endpoint nodes, paths, or graphs, but the field lacks consensus on representing paths as query output.Paths have variable rather than fixed arity, and SPARQL CONSTRUCT supports graph creation only as a final step, preventing further manipulation by other operators.Source: §4.1 · p. 25
• Bag semantics can make path queries costly because they count paths; SPARQL property paths use set semantics for unbounded repetition, while Cypher uses bags with no-repeated-edge semantics.Counting simple paths is #P-complete; SPARQL’s set-semantics restriction avoids counting paths of unbounded length.Source: §4.1 · p. 26

4.2. Adding paths to basic graph patterns

• Navigational graph patterns combine basic graph patterns with path queries, allowing selected edges to match paths while using an existential interpretation that checks path existence without returning paths.This existential interpretation keeps match arity bounded by query size.Source: §4.2 · pp. 26–27
• Complex navigational graph patterns extend navigational graph patterns with selection, projection, join, union, difference, and optional operations, and form the core of languages such as SPARQL.Theoretical work also considers variants that compare paths.Source: §4.2 · p. 27
• Combining path-augmented graph patterns with union, intersection, difference, and filters yields complex navigational graph patterns.The examples include posts recommended to Julie but not John, and filtering for more recent posts.Source: §4.2 · pp. 27–28

4.3. Repetition of patterns

• Nested regular expressions (NREs) add branching tests to paths, allowing tree-shaped patterns such as co-star paths whose intermediate nodes each have an outgoing directs edge.This condition does not require the starting node to be a director; NREs form a positive fragment of XPath and have been proposed as a basis for RDF navigation [Pérez et al. 2010; Barceló et al. 2012b; Libkin et al. 2016].Source: §4.3 · pp. 28–29
• Regular data path queries (RDPQs) extend path expressions with attribute-value comparisons between path endpoints, but such queries are poorly supported in existing systems and lack a settled language.The formalism permits equality or inequality comparisons between endpoint attributes; theoretical extensions include first-order path reasoning and unlimited variables [Libkin and Vrgoč 2012; Hellings et al. 2013; Libkin et al. 2016; Barceló et al. 2015].Source: §4.3 · p. 29
• Datalog recursion can repeat arbitrary basic graph patterns, including patterns that are neither paths nor trees, but its fixed-arity output cannot represent the navigated sequence of subgraphs.Rules can generate a base pattern’s matches and recursively compute its transitive closure; declarative recursive BGP evaluation is not widely supported in the surveyed practical languages.Source: §4.3 · pp. 30–31

4.4. Navigational queries in practice

• SPARQL 1.1 property paths support regular-path queries, inverses, limited negation, and navigational graph patterns, but SPARQL cannot express iterations of navigational patterns such as NREs.Adding negated property sets does not affect SPARQL query-evaluation complexity; paths with transitive closure use set semantics, while paths rewritable as basic graph patterns use bag semantics [Kostylev et al. 2015b; Harris and Seaborne 2013].Source: §4.4 · pp. 31–32
• Cypher supports transitive closure over one edge label or property-value pair, but not over more complex expressions; its default path semantics disallow repeated edges and return duplicate node pairs for distinct paths.Cypher also allows queries to request a single shortest path or all shortest paths.Source: §4.4 · pp. 32–33
• Cypher permits restricted path expressions inside basic patterns, bounded path lengths, and path returns; unwinding can simulate similar NRE or RDPQ queries, but Kleene closure applies only to edge labels.Counting in regular expressions improves succinctness.Source: §4.4 · pp. 33–34
• Gremlin’s repeat supports fixed or arbitrary traversal, with emit() outputting nodes after iterations and path() enumerating paths; bag semantics can repeat answers, potentially infinitely, and repeat can combine with graph patterns for recursion [Apache TinkerPop 2016a].emit() can be conditioned, and until() supports while-loop-style stopping conditions.Source: §4.4 · pp. 34–35

4.5. Complexity of evaluating navigational queries

• O(|G| · |L|) time decides RPQ path existence; O(|G|2 ·|L|) computes linked pairs and shortest witnesses, while no-repeated-node/edge evaluation is NP-complete in data complexity.For unconstrained reachability, a single pair takes O(|G|), and all linked pairs take O(|G|2); an unconstrained simple path remains efficient because a shortest path is simple.Source: §4.5 · p. 35
• O(|G|2 ·|Q|) constructs the augmented graph for an ngp under arbitrary- or shortest-path semantics, after which its graph pattern is evaluated separately and may be NP-complete.The path-building phase is intractable under simple-path semantics; graph-pattern evaluation is tractable for some query classes and in data complexity.Source: §4.5 · p. 36
• NREs and XPath admit fast extensions of RPQ algorithms, whereas unrestricted Datalog is EXPTIME-complete, Linear Datalog is PSPACE-complete, and Regular Queries are NP-complete.The cited complexity results are for query evaluation [Abiteboul et al. 1995; Consens and Mendelzon 1990; Reutter et al. 2015a].Source: §4.5 · p. 36
• Adding expressive features to path queries seems difficult because evaluation quickly becomes intractable [Libkin et al. 2016; Barceló et al. 2015]; implementing them with Cypher’s unwinding operator also makes evaluation NP-hard.Source: §4.5 · p. 37

Feature categorisation

• The survey identifies basic graph patterns and regular path queries as core features, extended into complex graph patterns and navigational graph patterns with operators such as union and optional.The authors also classify graph data models and discuss matching and path semantics as design choices.Source: §5 · p. 37

Complexity

• SPARQL evaluation is NP-complete for projected basic graph patterns, PSPACE-complete for complex graph patterns, and PSPACE-complete for complex navigational graph patterns under the final standard’s set-based property-path semantics.SPARQL is the most studied of the three languages.Source: §5 · p. 38
• Cypher’s default semantics make complex graph pattern evaluation NP-hard, while homomorphism-based emulation yields PSPACE-hardness; path-query evaluation is NP-hard, and exact complexity remains unclear.No-repeated-edge semantics is understudied, and Cypher’s path semantics, bag outputs, and lack of full RPQ expressions complicate analysis.Source: §5 · pp. 38–39
• For Gremlin’s core fragments, complex graph patterns remain PSPACE-complete, while node-returning RPQ-style navigation with arbitrary paths matches SPARQL’s expressivity and PSPACE-complete evaluation.Gremlin overall is Turing-complete, but these conclusions concern only the core fragments discussed in the survey.Source: §5 · p. 39

Uses of this survey

• The feature framework supports foundational comparisons of SPARQL, Cypher, and Gremlin, and can guide analysis of existing or proposed languages beyond syntax and superficial model differences.The survey notes that their core capabilities are fundamentally similar despite different models and syntax.Source: §5 · pp. 38–39
• The authors call for rigorous formalization and possible standardization, noting that design choices can alter complexity and that Cypher and Gremlin need further study of expressivity and evaluation.They identify open questions including tractable pattern subclasses under no-repeated-edge semantics and representing infinite sets of paths.Source: §5 · pp. 39–40

Future directions

• A complementary survey could classify graph-engine implementation and optimization strategies, including indexing, query planning, and heuristics.The paper identifies implementation and optimization as important topics it covered only indirectly.Source: §5 · pp. 40–41
• Future work should identify a common core for graph analytics and clarify how analytics languages and operations overlap with or extend graph query languages.The authors also point to comparing database-query tasks with vertex-centric frameworks and to developing more declarative analytics languages.Source: §5 · p. 41

A. ADDITIONAL FEATURES

• The section examines aggregation, path manipulation, graph-to-graph querying, implementation challenges, and proposed extensions including domain-specific features.The operators available for manipulating results vary significantly across graph query languages.Source: A. ADDITIONAL FEATURES · p. 48

A.1. Aggregation and solution modifiers

• For basic graph patterns, graph query languages use relational-style grouping and aggregates, while Cypher’s MAX subquery returns every movie tied for the longest runtime.SQL’s GROUP BY and COUNT, MIN, MAX, SUM, and AVG provide the model; SPARQL examples count movies or distinct actors per movie, and Cypher uses a second MATCH to return movies at the maximum runtime.Source: §A.1 · pp. 48–49
• ORDER BY, LIMIT, and offset modifiers can be used in subqueries; LIMIT 1 returns only one longest-runtime movie, unlike MAX when movies tie.To preserve all tied movies, the query must match movies whose runtime equals the selected maximum; SKIP 2 LIMIT 1 can select a third runtime, with WITH DISTINCT filtering ties.Source: §A.1 · pp. 49–50
• Path aggregation poses challenges absent from relational data: cyclic graphs can have infinitely many paths or infinite-length paths, while restricting repeated nodes makes counting finite but still computationally hard.Cypher supports counting paths or aggregating their lengths; its no-repeated-edge restriction can prevent infinite paths in cyclic graphs.Source: §A.1 · p. 50
• In Gremlin, simplePath() filters paths that repeat nodes, and results are ordered by ascending length, so keeping the first result yields a shortest path.Cypher’s default restriction prevents repeated edges, while Gremlin requires simplePath() to prevent repeated nodes.Source: §A.1 · p. 51
• The expressive power and exact evaluation complexity of aggregation functions on paths remain open questions for further investigation.Source: §A.1 · p. 51

A.2. Path unwinding

• Path unwinding projects parts of a path; Cypher and Gremlin can extract path elements, while SPARQL can only test for paths or return their start and/or end nodes.Gremlin can process extracted nodes and edges with subsequent operators.Source: §A.2 · pp. 51–52
• Cypher can return two arbitrary-length routes between c1 and c5 only when they share no intermediate nodes, using nodes(path) and none.The example matches undirected paths and excludes shared nodes other than the endpoints.Source: §A.2 · p. 51
• Verifying two paths with no shared nodes except their endpoints is NP-complete, illustrating the hardness that feature combinations can express.Adding path unwinding to other language features can make well-known hard problems trivially expressible.Source: §A.2 · pp. 51–52

A.3. Graph-to-Graph queries

• Graph-to-graph queries let a query return a graph, extending the table-to-table compositionality familiar from SQL.The section notes that a query's output graph can serve as the result of a graph query.Source: §A.3 · p. 52
• SPARQL CONSTRUCT evaluates WHERE matches, substitutes bound variables into template triples, omits triples with unbound variables, and returns an unordered set without duplicates.The example constructs directed :act_together edges between distinct actors who co-starred in a movie.Source: §A.3 · p. 52
• Cypher CREATE materializes graph elements from pattern matches; a WHERE inequality avoids vacuous self-loops when an actor has multiple edges to a movie.The example returns the created edges linking pairs of actors who co-starred in a movie.Source: §A.3 · pp. 52–53
• Gremlin can create edges between nodes reached by two successive outgoing-edge traversals, as in adding twoHoplink edges between cities.The example models travel options with at most one bus change.Source: §A.3 · p. 53
• Graph-to-graph queries are a relatively new feature: SPARQL CONSTRUCT has some expressive-power and composition studies, while Cypher and Gremlin remain unexplored in the literature.The section identifies their basic properties and interactions with other query features as possible future research topics.Source: §A.3 · p. 53

A.4. Further extensions

• Official extensions cover SPARQL dataset updates, remote federated queries, and entailment, while Cypher and Gremlin provide update mechanisms [Gearon et al. 2013; The Neo4j Team 2016; Apache TinkerPop 2016b; Prud’hommeaux and Buil-Aranda 2013; Glimm and Ogbuji 2013].SPARQL federation sends nested queries to remote services for local processing; entailment regimes use implicit knowledge to generate further answers.Source: §A.4 · p. 53
• Third-party SPARQL extensions include SPARQL* [Hartig and Thompson 2014] and AnQL, frameworks for reifying or annotating RDF, and SPARQLAR for query approximation and relaxation that returns near answers.Source: §A.4 · pp. 53–54
• Other proposals add rules and flexible quantification in SPAR-QLog, cross-language federation in XSPARQL, and relational-like RDF constraints [Lausen et al. 2008].SPAR-QLog also defines fragments that preserve desirable complexity results.Source: §A.4 · p. 54
• Domain-specific extensions address trust annotations, scientific numeric arrays, multimedia metadata, spatial and temporal queries, and streaming event processing.Streaming proposals support event processing, reasoning, and querying over windows of streaming data.Source: §A.4 · p. 54
• Because graph-query features continue to evolve, the survey focuses on foundational declarative features that form a common backbone of modern graph query languages.The authors say they do not attempt to cover all proposed extensions in detail.Source: §A.4 · p. 54