Source-linked AI summary
G-CORE: A Core for Future Graph Query Languages
Renzo Angles, Marcelo Arenas, Pablo Barceló, Peter Boncz, George H. L. Fletcher, Claudio Gutierrez, Tobias Lindaaker, Marcus Paradies, Stefan Plantikow, Juan Sequeda, Oskar van Rest, Hannes Voigt
TL;DR
Graph query languages lack a common approach that combines composability with first-class path support. G-CORE addresses this by defining a closed query language and Path Property Graph model, while restricting features for tractable evaluation. The paper concludes that these goals are computationally feasible and approachable for graph users.
Problem
Graph query languages lack a common property-graph language, while composability and first-class path support are needed for the intended design.
Method
G-CORE defines a closed query language on Property Graphs and extends the data model with paths as first-class elements.
Results
The paper reports that composability and first-class paths are computationally feasible and approachable for graph users.
Takeaways & Limitations
G-CORE is intended to guide existing and future graph query languages toward composability and first-class path treatment.
Takeaways & Limitations
The paper notes that SPARQL’s CONSTRUCT cannot flexibly aggregate different properties or reuse constructed RDF graphs as subqueries.
Abstract
from arXiv · showhide
We report on a community effort between industry and academia to shape the future of graph query languages. We argue that existing graph database management systems should consider supporting a query language with two key characteristics. First, it should be composable, meaning, that graphs are the input and the output of queries. Second, the graph query language should treat paths as first-class citizens. Our result is G-CORE, a powerful graph query language design that fulfills these goals, and strikes a careful balance between path query expressivity and evaluation complexity.
PREAMBLE
G-CORE is an industry–academia design intended to guide graph query language evolution, rather than propose a new standard. It aims to support useful, composable graph querying.
- G-CORE was designed by the LDBC Graph Query Language Task Force, comprising industry and academic members.
- LDBC explicitly presents G-CORE as guidance for existing and future graph query languages, not as a new standard.
1 INTRODUCTION
Graph data management spans diverse systems and application needs, creating interoperability challenges and motivating a common, composable query language. G-CORE addresses this through graph outputs, first-class paths, a formal definition, and tractable evaluation.
- Graph database systems have diverse storage models, functionalities, libraries, APIs, and query languages, creating interoperability challenges for the industry.
- Industry use cases require graph pattern matching, reachability, weighted path finding, graph construction, and clustering across application domains.
- 1.1 Three Main Challenges: Composability lets query outputs serve as inputs, supporting modularity, interoperability, abstraction, reuse, and query decomposition.
- 1.1 Three Main Challenges: G-CORE treats paths as first-class citizens, so paths can be returned, manipulated, and assigned identity, labels, and properties.
- 1.2 Contributions: The paper formally defines G-CORE’s syntax and semantics to remove ambiguity and enable correct implementations.
- 1.2 Contributions: G-CORE restricts features so each query can be evaluated efficiently while retaining powerful path-query functionality.
2 PATH PROPERTY GRAPHS
The Path Property Graph model extends property graphs with explicit path identifiers. Paths are represented as sequences of adjacent nodes and edges and can carry labels and properties.
- G-CORE defines the Path Property Graph model as an extension of the Property Graph data model.
- A PPG contains disjoint finite sets of node, edge, and path identifiers, together with endpoint, path, label, and property functions.
- The function δ assigns each path identifier a finite list of alternating nodes and adjacent edges.
- The endpoint function ρ identifies an edge’s starting and ending nodes and permits multiple edges between the same node pair.
- Labels and property values can be assigned to nodes, edges, and paths through λ and σ.
- Paths: Paths are first-class model elements that can carry labels and properties, including built-in properties such as path length.
- Paths: For a path variable p, nodes(p) and edges(p) return its ordered node and edge lists.
3 A GUIDED TOUR OF G-CORE
The guided tour presents G-CORE as a graph-returning language with MATCH, filtering, construction, graph integration, views, optionals, and first-class path patterns. Examples illustrate identity-preserving construction, multi-valued properties, joins, stored paths, and tractable path-query design.
- Core query model: Every G-CORE query returns a graph through a leading CONSTRUCT clause.CONSTRUCT creates graph elements for each MATCH binding.
- Core query model: MATCH binds nodes, edges, and paths from named input graphs, while WHERE filters the resulting bindings.Bindings can be viewed as rows with columns for variables.
- Construction and composition: G-CORE supports multi-graph matching and joins, enabling integration of company nodes with people from separate graphs.The examples match company_graph and social_graph, then construct worksAt edges.
- Properties and filtering: Multi-valued properties can be compared with IN or expanded into individual bindings, while absent properties evaluate to the empty set.CASE expressions can coalesce missing data into other values.
- Construction and composition: CONSTRUCT groups bindings by node identity and by source–destination identity for edges, preserving identities from input graphs.This can produce five new edges between four existing persons and four existing companies.
- Path patterns: Paths are first-class citizens: G-CORE supports powerful path patterns, stores paths with @p, and queries databases containing potentially many stored paths.The examples use shortest paths toward Wagner lovers and score direct friends reached through those paths.
- Views and optionals: G-CORE’s closed graph model supports subqueries and views, and its optional-block semantics do not depend on evaluation order.Graph views can add properties or stored paths to an existing graph.
4 FORMALIZING AND ANALYZING G-CORE
G-CORE formally defines queries as sequences of Path and Graph clauses followed by a full graph query, with Match producing bindings and Construct producing a new graph. Its semantics and evaluation strategy are designed to preserve expressive path queries while ensuring polynomial-time data complexity.
- Query structure: A G-CORE query consists of Path and Graph clauses followed by a full graph query.The language is formally specified through syntax and semantics over property graphs.
- Query semantics: Match evaluates a graph pattern into bindings that can be filtered by Where, while Construct uses the input graph and bindings to produce a new property graph.Construct may reference labels and properties from the input graph through the bindings.
- Path semantics: Path clauses define complex path expressions and associated costs for use in Match graph patterns, enabling rich navigational patterns.Path variables are matched to shortest or cheapest paths satisfying regular expressions.
- Complexity analysis: For every fixed G-CORE query q, evaluating q over an input property graph can be computed in polynomial time in the data size.The analysis covers graph-pattern evaluation, path evaluation, clause sequences, filtering, and construction.
- Complexity analysis: Shortest-path semantics supports polynomial evaluation, unlike simple-path semantics, for which checking a regular-expression-constrained path is NP-complete.The polynomial procedure combines automata-theoretic techniques with Dijkstra-style algorithms.
5 EXTENSIONS OF G-CORE
The paper discusses extensions that connect G-CORE with tabular data through importing tables, interpreting rows as graph nodes, and projecting graph-query results into tables. Tabular projection would broaden relational functionality but would make the language produce either tables or graphs rather than remain strictly closed over graphs.
- Tabular integration: G-CORE extensions address practical tabular-data workflows, including importing tables and constructing graphs from tabular data.The paper presents alternative proposals for bringing tabular data into G-CORE.
- Projecting tabular results: A SELECT clause could project MATCH bindings into tables and support relational operations such as slicing, sorting, and aggregation.The proposal is compared with Cypher RETURN and SQL or SPARQL SELECT clauses.
- Scope boundary: Adding tabular projection would make G-CORE multi-sorted, capable of producing either a table or a graph, and no longer strictly closed over graphs.For this reason, the extension is left to future work.
- Binding table inputs: A FROM <table> clause could import scalar bindings used by CONSTRUCT to connect per-customer and per-product nodes from table rows.The example uses customer names and product codes as inputs to graph construction.
- Interpreting tables as graphs: Another proposal treats each row of a table as an isolated graph node whose properties correspond to the row's fields.This approach uses MATCH .. ON .. to interpret tabular input as a graph.
6 DISCUSSION AND RELATED WORK
The discussion positions G-CORE within graph-query-language research and emphasizes its integration of expressive path and graph features with an explicit complexity analysis. Its distinguishing design choices are graph outputs, first-class paths, and query composition, while tabular and RDF comparisons expose scope and interoperability boundaries.
- Motivation: G-CORE addresses the absence of a standard property-graph query language comparable to SQL for relational data.The paper places its design in a field with many industrial products but no established standard.
- Path queries: G-CORE, Cypher, and PGQL support regular path expressions, while Gremlin supports arbitrary or fixed traversal iteration beyond regular path queries.G-CORE uses shortest-path semantics, whereas the compared languages use different path-evaluation semantics.
- Query output: G-CORE returns graphs with paths as first-class citizens, distinguishing its output model from approaches centered on tables or atomic values.Recent Cypher implementations can also return graphs, but G-CORE is explicitly designed around graph results and paths.
- Query composition: Because query outputs are graphs, G-CORE queries can be composed by querying the output of one query with another.The discussion states that Cypher 9, PGQL, and SPARQL do not support this capability.
- Expressiveness versus efficiency: G-CORE integrates knowledge from industrial language design and theoretical research on expressive power and evaluation complexity.The paper identifies this integration as a main virtue of the design.
- SPARQL comparison: Unlike G-CORE's flexible graph construction and composition goals, SPARQL CONSTRUCT lacks flexible graph aggregation and constructed RDF graphs cannot be reused as subqueries.The discussion also notes that SPARQL lacks full graph-level union or difference operations.
7 CONCLUSIONS
The paper proposes G-CORE as a composable graph query language centered on first-class paths, aiming to improve interoperability while balancing expressivity with feasible evaluation.
- Graph query systems face interoperability challenges as commercial and open-source technologies proliferate.
- G-CORE treats paths as first-class citizens in graph querying.The design explicitly makes paths central to the language rather than treating them as secondary query results.
- The language builds on working-system experience and theoretical results to make its design computationally feasible and approachable for graph users.
- The paper presents G-CORE as a call to action for stakeholders driving the graph database industry.
A A FORMAL DEFINITION OF G-CORE
This formal section defines G-CORE’s syntax and semantics, including regular-expression paths, bindings, expressions, graph locations, and basic graph-pattern evaluation.
- A A FORMAL DEFINITION OF G-CORE: G-CORE’s formal semantics are presented using a simplified syntax that is equally expressive to the full language syntax.
- A A FORMAL DEFINITION OF G-CORE: G-CORE queries are recursively defined by a top-down grammar, with formal notions introduced before the main grammar is detailed.
- A.1 Basic notions: G-CORE expressions support variables, properties, labels, unary and binary operators, built-in functions, existence tests, and aggregation over graph objects and values.
- A.1 Basic notions: G-CORE defines path-expression semantics over arbitrary paths, avoiding simple-path semantics because repeated-node or repeated-edge paths can cause data-complexity intractability.
- A.1 Basic notions: For a regular-expression path from u to v, G-CORE selects the shortest conforming path under a fixed lexicographical order.The existence of such a path and a shortest witness can be computed in polynomial time using automata techniques and depth-first search.
- A.1 Basic notions: Regular expressions combine edge labels, inverse labels, negated node labels, wildcard labels, union, concatenation, and repetition.
- A.1 Basic notions: Bindings map node, edge, and path variables to values of their respective domains; finite bindings are compatible when they agree on shared variables.
- A.2 The MATCH clause: Basic graph patterns can be evaluated on specified graph locations, with node, edge, and path patterns producing bindings and path identifiers for shortest conforming paths.The location syntax supports either a graph identifier or a full graph query.