Source-linked AI summary
Foundations of Modern Query Languages for Graph Databases
Renzo Angles, Marcelo Arenas, Pablo Barcelo, Aidan Hogan, Juan Reutter, Domagoj Vrgoc
TL;DR
Graph query languages combine graph data models with graph patterns and navigational expressions, but their semantics affect computational complexity. This survey connects theory and practice by explaining these features, comparing SPARQL, Cypher, and Gremlin, and summarizing known expressivity, complexity, and future research directions.
Problem
Graph query-language theory and practical languages need to be related through their shared features, semantics, expressivity, and complexity.
Method
The survey explains graph data models, graph patterns, navigational expressions, evaluation semantics, and their instantiation in SPARQL, Cypher, and Gremlin.
Results
The survey summarizes how feature and semantic choices affect complexity, including NP-completeness for basic graph-pattern evaluation under several semantics and polynomial time under simulation-based semantics.
Takeaways & Limitations
Formalisation helps transfer results between abstract graph-query theory and practical graph database engines.
Takeaways & Limitations
For Datalog, representing the sequences of subgraphs navigated by rules remains unexplored because rule outputs are fixed-arity relations.
Abstract
from arXiv · showhide
We survey foundational features underlying modern graph query languages. We first discuss two popular graph data models: edge-labelled graphs, where nodes are connected by directed, labelled edges; and property graphs, where nodes and edges can further have attributes. Next we discuss the two most fundamental graph querying functionalities: graph patterns and navigational expressions. We start with graph patterns, in which a graph-structured query is matched against the data. Thereafter we discuss navigational expressions, in which patterns can be matched recursively against the graph to navigate paths of arbitrary length; we give an overview of what kinds of expressions have been proposed, and how they can be combined with graph patterns. We also discuss several semantics under which queries using the previous features can be evaluated, what effects the selection of features and semantics has on complexity, and offer examples of such features in three modern languages that are used to query graphs: SPARQL, Cypher and Gremlin. We conclude by discussing the importance of formalisation for graph query languages; a summary of what is known about SPARQL, Cypher and Gremlin in terms of expressivity and complexity; and an outline of possible future directions for the area.
1. INTRODUCTION
This survey organizes modern graph query languages around two data models and two core query features, connecting theoretical foundations with practical languages and semantics. It examines how feature and semantic choices affect expressivity, complexity, and implementation.
- Contribution: The survey complements prior work by combining conceptual feature analysis, semantics and complexity, formalisation, and practical language comparisons.Its stated aim is to bridge theory and practice while covering a broader scope than surveys focused only on models, engines, or individual querying aspects.
- Analysis and comparison: The survey presents graph query features, their evaluation semantics, practical examples, computational complexity, and extensions implemented in modern engines.It treats query features as foundational building blocks rather than focusing only on complete language syntaxes.
- Core query features: Graph patterns match graph-structured queries against databases, while navigational expressions recursively match patterns to traverse paths of arbitrary length.Navigational expressions include path expressions, branch-checking expressions, and recursively matched graph patterns.
- Theory and practice: Examples from SPARQL, Cypher, and Gremlin connect theoretical notions of graph querying to languages used in practice.The survey is designed for both theoretical and applied researchers, as well as practitioners involved with graph engines and query languages.
- Scope and models: The survey focuses on edge-labelled graphs and property graphs, which capture foundational and widely used graph database scenarios.Property graphs extend labelled graphs by allowing nodes and edges to carry additional information.
2. GRAPH DATA MODELS
Graph databases can use edge-labelled graphs to distinguish relationship types, while property graphs add labels, identifiers, and attributes directly to nodes and edges. These models support flexible graph representations, including repeated relationships and metadata, with the survey focusing on single-valued property graphs.
- Edge-labelled graphs: Edge-labelled graphs represent directed relationships with labels, distinguishing multiple relationship types between the same nodes.The movie example uses acts_in and directs edges between Clint Eastwood and Unforgiven.
- Edge-labelled graphs: An edge-labelled graph is formally a finite vertex set together with edges drawn from V × Lab × V.RDF graphs are treated as a special type of edge-labelled graph for the survey’s purposes.
- Edge-labelled graphs: Edge-labelled graphs impose no particular topology, so cycles can be represented by adding appropriately labelled directed edges.The survey illustrates this with a directedBy edge from Unforgiven to Clint Eastwood and social-network cycles.
- Property graphs: Property graphs address the difficulty of adding metadata to edge-labelled relationships and are adopted by major graph engines and an LDBC standardisation effort.The survey identifies Neo4j as an example of a major engine using this model.
- Property graphs: Property graphs attach labels and unique identifiers to nodes and edges, enabling direct storage of property–value attributes without changing graph structure.They can also represent multiple same-labelled edges between the same nodes when the edges have different identifiers.
- Property graphs: The formal property-graph model uses finite nodes and edges, endpoint mapping ρ, label mapping λ, and partial property mapping σ.Nodes and edges are disjoint, edges are directed, and σ maps graph elements and properties to values when defined.
3. GRAPH PATTERNS
Graph patterns match graph-structured queries against graph databases, with basic patterns extended by relational-like operators and evaluated under alternative semantics. The survey connects these features to SPARQL, Cypher and Gremlin, and relates their expressive choices to evaluation complexity.
- Graph patterns in practice: SPARQL, Cypher and Gremlin share graph-pattern matching as a conceptual core, while differing in style, purpose, expressivity and implementation.The survey uses concrete language examples to relate practical features to theoretical graph-query notions.
- Complex graph patterns: Complex graph patterns extend basic patterns with projection, union, optional and difference to refine matches and returned results.Projection selects relevant output variables, such as actor names while omitting node or edge identifiers.
- Basic graph patterns: Basic graph patterns mirror the queried graph model while allowing variables in nodes, edges, or properties; matches map variables to database constants.A match replaces variables so the resulting pattern is contained in the graph database.
- Matching semantics: Homomorphism-based semantics allow variable mappings to repeat terms, whereas isomorphism-based variants restrict mappings by requiring distinct terms or distinct nodes and edges.In the example, all matches are valid homomorphically; stricter semantics retain progressively fewer matches.
- Matching semantics: Simulation-based semantics can represent multiple homomorphic matches in a single relation by allowing one pattern node to match several graph nodes while preserving structure.The survey presents simulation as a more flexible alternative to rigid whole-pattern matching.
- Complexity: Graph-pattern evaluation has NP-complete combined complexity for basic patterns with projection under homomorphism- and isomorphism-based semantics.For SPARQL complex graph patterns, projection, join, union and filter remain NP-complete, while adding difference or optional yields PSPACE-completeness; bag semantics is also PSPACE-complete.
4. NAVIGATIONAL QUERIES
Navigational queries extend bounded graph patterns with paths of arbitrary length, while recursive pattern mechanisms broaden expressivity beyond path recursion. Their evaluation depends strongly on path semantics, with simple-path restrictions causing major complexity increases.
- 4.1. Path Queries: Path queries navigate graph topology through paths of potentially arbitrary length, supporting applications such as social-network reachability, provenance, and route finding.
- 4.1. Path Queries: Regular Path Queries use regular expressions over edge labels to constrain paths through concatenation, union, and repetition.The Kleene operators specify zero-or-more and one-or-more repetitions, as in knows+ for transitive friend-of-a-friend paths.
- 4.3. Repetition of patterns: Queries reasoning about attribute-value changes along paths are relevant but poorly supported in existing systems, leaving their language and implementation unsettled.The survey identifies this as an area for future theoretical and implementation work.
- 4.3. Repetition of patterns: Datalog supports recursive patterns whose base pattern can be an arbitrary basic graph pattern, exceeding recursive forms expressible in the surveyed path languages.Recursive Datalog rules can generate transitive closures, but their fixed-arity relational output does not directly represent sequences of traversed subgraphs.
- 4.4. Navigational queries in practice: Limited negation added to SPARQL-style property paths does not change the complexity of SPARQL query evaluation.
- 4.5. Complexity of evaluating navigational queries: Path-evaluation complexity varies by semantics: arbitrary and shortest-path interpretations are polynomial, whereas no-repeated-node or no-repeated-edge semantics can be NP-complete.For unconstrained paths, shortest paths remain efficiently computable because every shortest path is simple.
- 4.5. Complexity of evaluating navigational queries: Navigational graph-pattern evaluation separates path-query evaluation from graph-pattern evaluation, clarifying how path semantics and the NP-completeness of general pattern matching affect total complexity.
5. FINAL REMARKS
The survey categorizes modern graph query languages around pattern matching and navigation, relates these features to SPARQL, Cypher, and Gremlin, and examines their semantics, complexity, expressivity, and practical implications.
- Feature categorisation: Pattern matching and navigation form the two core feature classes common to modern graph query languages.
- Feature categorisation: Basic graph patterns can be extended with projection, union, optional, and other operators to form complex graph patterns.
- Open questions and scope: The survey identifies open complexity questions, especially for Cypher, and notes that additional operators such as aggregation and graph transformations are outside its core focus.
- Uses of this survey: The survey compares design choices in SPARQL, Cypher, and Gremlin to provide a foundational view of their pattern-matching and navigational capabilities.
- Complexity and expressivity: PSPACE-completeness is known for SPARQL complex graph patterns and navigational queries under the stated semantics, while Cypher complexity remains less understood.
- Complexity and expressivity: Gremlin’s core pattern semantics are almost equivalent to SPARQL’s, and restricted navigational queries have equivalent expressivity and PSPACE-complete evaluation.
- Uses of this survey: Abstracting languages into core features supports comparison, formalisation, standardisation, and analysis of how semantics affect computational guarantees.
- Future directions: The survey also highlights uncertainty about the boundary and overlap between graph query languages and graph analytics languages.
Online Appendix to: Foundations of Modern Query Languages for Graph Databases14
This passage lists the survey’s authors and their institutional affiliations in Chile.
- Renzo Angles is affiliated with Universidad de Talca and the Center for Semantic Web Research.
- Marcelo Arenas is affiliated with Pontificia Universidad Católica de Chile and the Center for Semantic Web Research.
- Pablo Barceló, Aidan Hogan, Juan Reutter, and Domagoj Vrgoč are affiliated with Chilean universities and the Center for Semantic Web Research.
A. ADDITIONAL FEATURES
The survey discusses operators for manipulating graph-query results beyond retrieving nodes, edges, or paths.
- Result-manipulation features include aggregation and transformations, but their available operators vary significantly across graph query languages.
A.1. Aggregation and solution modifiers
Aggregation and solution modifiers extend graph queries with grouping, counting, ordering, limits, and offsets, but navigational uses introduce distinct computational challenges. The section illustrates these features across SPARQL, Cypher, and Gremlin.
- Aggregation: Aggregation operators group matched values and compute statistics such as COUNT, MIN, MAX, SUM, and AVG, paralleling relational database behavior.In SPARQL, GROUP BY creates groups and COUNT can count values within each group.
- Aggregation: SPARQL uses COUNT over matched movie variables, with COUNT(DISTINCT ?movie) excluding duplicate values.The basic query counts movies, while DISTINCT changes duplicate-counting behavior in more complex queries.
- Aggregation: Cypher combines MATCH, WITH, MAX, and a second MATCH to return all movies whose runtime equals the maximum.The first MATCH computes maxTime, and the second retrieves every movie tied at that runtime.
- Solution modifiers: Ordering with LIMIT can select one extreme result, but unlike MAX it returns only one movie when several share the longest runtime.A subquery can restore tie-inclusive behavior, while SKIP and LIMIT can select ranked positions.
- Navigational queries: Counting or measuring navigational paths creates computational challenges, especially when cycles permit infinitely many paths without restrictions.Cypher avoids repeated edges by default, while Gremlin requires simplePath() for node-simple paths; Gremlin orders paths by ascending length.
A.2. Path unwinding
Path unwinding projects nodes or edges from paths so they can be processed by later query operators. Although useful for expressing disjoint-route queries, combining it with other features can yield hard computational problems.
- Path unwinding: Path unwinding projects parts of a path for subsequent processing, such as extracting its nodes or edges.Cypher exposes path elements independently, while Gremlin offers similar processing features.
- Disjoint paths: Cypher can express two routes between cities while requiring their intermediate nodes to be disjoint.The query stores two arbitrary-length paths and uses nodes(path) with none to enforce the disjointness condition.
- Complexity: The two-disjoint-paths problem is NP-complete when two paths may share only their endpoints.This complexity result explains why queries expressing such constraints are inherently difficult to evaluate.
- Complexity: Adding path unwinding can expose well-known hard problems when combined with other query-language features.The survey highlights computational complexity as a consequence of feature combinations rather than path unwinding in isolation.
A.3. Graph-to-Graph queries
Graph-to-graph queries construct or materialise new graph elements from query matches. The section presents mechanisms in SPARQL, Cypher, and Gremlin while noting that their theoretical properties remain insufficiently studied.
- Graph-valued results: Graph query languages can return a graph as the result of a query, extending compositional behavior beyond relational-table outputs.SQL composes table-valued queries, while graph languages provide corresponding graph-valued functionality.
- SPARQL: SPARQL CONSTRUCT evaluates WHERE matches and instantiates triple templates to produce an RDF graph.Variables and constants in the CONSTRUCT template are replaced using assignments generated by the WHERE clause.
- Cypher: Cypher uses CREATE inside a query expression to generate graph elements from matched patterns.The example creates act_together edges between distinct actors connected through a movie.
- Gremlin: Gremlin can add twoHoplink edges between cities reachable through one intermediate node.The query traverses two outgoing steps, labels the endpoints, and creates an edge between each pair.
- Research status: Graph-to-graph queries are relatively new, with few studies of their basic properties or combinations with other query features.SPARQL CONSTRUCT has received some theoretical study, whereas Cypher and Gremlin remain unexplored in the cited literature.
A.4. Further extensions
Modern graph query languages include many extensions beyond core graph matching and navigation. The survey briefly covers official and research-proposed extensions while retaining a foundational focus.
- Scope: The survey’s core focus is graph matching and navigational queries, while extensions are reviewed only briefly.The extensions include features specified officially and proposals from third-party research.
- Official extensions: Official extensions support dataset updates in SPARQL, graph-element updates in Cypher, and updates through Gremlin’s Blueprints API.These mechanisms can add, remove, or modify graph data and associated labels or attributes.
- Research extensions: Research extensions include RDF reification and annotation, query approximation, rules, flexible quantification, trust annotations, scientific arrays, and multimedia metadata functions.The survey names SPARQL*, AnQL, SPARQLAR, SPAR-QLog, tSPARQL, SciS-PARQL, and SPARQL-MM as examples.
- Research direction: Graph query research continues to propose extensions, so graph languages are expected to evolve toward broader feature coverage.The survey therefore emphasizes a foundational feature set shared across modern declarative graph query languages.