PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Pattern Matching in GQL and SQL/PGQ

Alin Deutsch, Nadime Francis, Alastair Green, Keith Hare, Bei Li, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Wim Martens, Jan Michels, Filip Murlak, Stefan Plantikow, Petra Selmer, Hannes Voigt, Oskar van Rest, Domagoj Vrgoč, Mingxi Wu, Fred Zemke

arXiv:2112.06217v1cs.DB

TL;DR

As graph data management expands, the lack of a standard query language for property graphs has become more pressing. This paper summarizes the common GPML core of GQL and SQL/PGQ and reports that both languages match the same path bindings before result projection.

  • Problem

    The expansion of graph data management has exposed a lack of a standard query language and associated schema-definition sublanguages for property graphs.

  • Method

    The paper presents an accessible summary of the GPML shared identically by GQL and SQL/PGQ.

  • Results

    The set of path bindings matching a path pattern is the same in SQL/PGQ and GQL before result projection.

  • Takeaways & Limitations

    GQL and SQL/PGQ differ in how path bindings are projected into query results, while retaining the same pre-projection path-pattern matches.

  • Takeaways & Limitations

    The paper identifies extended capabilities and different uses of graph patterns as future work.

Abstract

from arXiv · show

As graph databases become widespread, JTC1 -- the committee in joint charge of information technology standards for the International Organization for Standardization (ISO), and International Electrotechnical Commission (IEC) -- has approved a project to create GQL, a standard property graph query language. This complements a project to extend SQL with a new part, SQL/PGQ, which specifies how to define graph views over an SQL tabular schema, and to run read-only queries against them. Both projects have been assigned to the ISO/IEC JTC1 SC32 working group for Database Languages, WG3, which continues to maintain and enhance SQL as a whole. This common responsibility helps enforce a policy that the identical core of both PGQ and GQL is a graph pattern matching sub-language, here termed GPML. The WG3 design process is also analyzed by an academic working group, part of the Linked Data Benchmark Council (LDBC), whose task is to produce a formal semantics of these graph data languages, which complements their standard specifications. This paper, written by members of WG3 and LDBC, presents the key elements of the GPML of SQL/PGQ and GQL in advance of the publication of these new standards.

1 INTRODUCTION

Graph databases and property graphs have expanded across applications, while graph query systems remain diverse and lack a common standard. GQL and SQL/PGQ address this gap through an identical graph pattern matching core, GPML, whose matching semantics are shared before result projection.

  • Graph-structured data supports analysis in scientific domains and applications involving fraud detection, market trends, and customer behavior.
  • The growing use of property graphs has exposed the lack of a standard query language and associated schema-definition sublanguages.
  • ISO/IEC projects define GQL as a standard property graph query language and SQL/PGQ as an SQL extension for graph views and read-only queries.
  • GQL and SQL/PGQ share a common data model and an identical graph pattern matching sublanguage called GPML, governed through WG3.
  • GPML matches graph patterns to property graphs, producing path bindings that map variables to graph elements and their properties.
  • The set of path bindings for a given graph and path pattern is the same in SQL/PGQ and GQL before each language projects query results.
  • The paper provides an accessible summary of GPML before the standards are published and before vendors release implementations.

2 PROPERTY GRAPHS

Property graphs represent labeled, attributed nodes and edges in a mixed multigraph that may include directed, undirected, parallel, and self-looping edges. They also have graph and tabular representations used to describe and query the same data.

  • The banking example contains account, location, phone, IP-address, and financial-transaction information connected by graph edges.
  • A property graph is a mixed, attributed multigraph whose nodes and edges can carry labels and property/value pairs.
  • The formal model uses finite node and edge sets, an endpoint function, a label function, and a partial property function.
  • The tabular representation has relations for combinations of labels, with Transfer and signInWithIP representing edges and other shown tables representing nodes.
  • Edges may be directed or undirected, including self-loops and multiple edges connecting the same nodes.
  • A path alternates nodes and edges, starts and ends with a node, and requires consecutive nodes to be connected by the intervening edge.

3 GRAPH PATTERN MATCHING TODAY

Existing graph query languages use graph patterns to match nodes, edges, and paths, but differ in data models, path semantics, result construction, and aggregation facilities. The section compares SPARQL, Cypher, PGQL, and GSQL through a shared fraudulent-account example.

  • The shared example seeks accounts in Ankh-Morpork connected by arbitrarily many transfers, with one blocked account and one unblocked account.
  • Graph patterns specify nodes and connections through edges or paths, filtered by labels and property values, and produce graph-matching results.
  • SPARQL: SPARQL supports property paths under arbitrary path semantics but restricts cyclic-path handling to existence checks rather than path counting or reconstruction.
  • Cypher: Cypher matches the example with property-graph patterns, returns owners, and can return paths and perform shortest-path, path-length, and path-count operations.
  • PGQL: PGQL uses SQL-like clauses and graph patterns in the FROM clause, with group variables supporting aggregation over variable-length paths.
  • PGQL: PGQL supports path selectors including ANY SHORTEST, ALL SHORTEST, TOP k SHORTEST, ANY CHEAPEST, and TOP k CHEAPEST.
  • GSQL: GSQL follows SQL-style query syntax and uses accumulators for aggregation during pattern matching, while its default semantics is ALL SHORTEST.

4 GRAPH PATTERN MATCHING LANGUAGE

GPML is the common graph pattern matching language for SQL/PGQ and GQL. It provides node, edge, path, filtering, direction, and graph-specific predicate constructs for producing graph-element bindings.

  • Pattern matching: GPML patterns explore property graphs by matching nodes, edges, and paths, producing bindings from variables to graph elements and property values.A pattern may be evaluated against a property graph to produce a multiset of variable bindings.
  • Node patterns: Node patterns bind variables to nodes and can restrict matches by labels, properties, and WHERE conditions.Labels support conjunction, disjunction, negation, grouping, and wildcard matching.
  • Edge patterns: Edge patterns bind directed or undirected edges and support direction restrictions, labels, and filtering conditions.Edges can be matched with explicit direction or retrieved as undirected edges using specialized syntax.
  • Path patterns: Chaining node and edge patterns forms paths whose bindings can expose source and target nodes, while unspecified direction may return each edge in both traversal directions.Node and edge filters remain available within chained path patterns.
  • Advanced matching: GPML supports postfix quantifiers, graph-specific predicates, and separate set-based union and multiset alternation semantics.Graph-specific predicates include tests for edge direction, source or destination relationships, and equality of element references; the two union forms address overlapping matches differently.

5 ASSURING TERMINATION

GPML assures termination by requiring unbounded quantifiers to be governed by restrictors, selectors, or both, while distinguishing how each mechanism limits matches. The section also shows that predicate placement and aggregate use affect whether queries remain finite and whether any matches survive.

  • Termination mechanisms: GPML queries must terminate with finitely many matches, because unrestricted path patterns can produce infinitely many cyclic matches.A transfer loop may be repeated indefinitely in an otherwise valid path.
  • Restrictors: Restrictors constrain which paths are accepted, such as TRAIL, which forbids repeated edges and therefore leaves finitely many possible paths.Restrictors may appear at the head of a path pattern or parenthesized path pattern.
  • Selectors: Selectors partition solutions by endpoints and retain a finite subset, such as ALL SHORTEST, which keeps every shortest path within each partition.ANY SHORTEST returns one shortest path per partition, whereas ALL SHORTEST returns all shortest paths and is deterministic.
  • Combining restrictors and selectors: Restrictors operate during pattern matching, whereas selectors conceptually operate afterward, so combining them first restricts candidate paths and then selects among them.The specification describes the potentially infinite solution set declaratively while defining the finite selection returned by a selector.
  • Combining restrictors and selectors: Adding a selector to a query with matches always leaves at least one match, but adding a restrictor may instead produce no matches.Selectors may reduce the number of matches without emptying the result, while restrictors can exclude all paths.
  • Combining restrictors and selectors: A selector can preserve a result that repeats an edge, while adding TRAIL can eliminate every result because the selected shortest path is not a trail.In the example, ALL SHORTEST still returns a result, whereas TRAIL returns none.
  • Prefilters and postfilters: Prefilters constrain paths before selector application, whereas postfilters apply afterward and can remove the selector’s entire result.The example query returns no result because the final WHERE clause filters out the selector’s result when a3 is not blocked.
  • Aggregates of unbounded variables: Predicates on unbounded groups are difficult to reason about for aggregates such as AVG, so GPML is expected to prohibit them to ensure termination.Some aggregates, including MAX, MIN, and COUNT, are monotonic, but general reasoning about arbitrary aggregates remains non-obvious.

6 EXECUTION MODEL BY EXAMPLE

GPML evaluates graph patterns through normalization, expansion, rigid-pattern matching, joining, filtering, reduction, and deduplication. Quantifiers require selectors or restrictors to ensure finite evaluation.

  • Execution model: GPML represents a graph pattern as path patterns whose evaluation produces path bindings.A path binding is a sequence of elementary bindings pairing variables with graph elements.
  • Filtering and termination: Selectors and restrictors constrain evaluation so quantifiers do not produce an infinite result.A WHERE clause can further filter the joined results after matching.
  • Expansion: Expansion generates rigid patterns without quantifiers, union, or multiset alternation, while retaining provenance annotations.Rigid patterns fix quantifier iterations and disjunct choices so they can be evaluated like SQL equi-joins.
  • Rigid-pattern matching: Each rigid pattern is matched independently, then its elementary results are joined on variables with identical names.The resulting bindings are reduced by removing annotations and collected into a set, which deduplicates equal bindings.
  • Normalization: Normalization makes each node-edge sequence structurally consistent and expands syntactic sugar such as + into explicit quantifiers.Sequences start and end with node patterns and alternate between nodes and edges.

6.3 Expansion

Expansion enumerates rigid alternatives by fixing quantifier iteration counts and selecting disjuncts, including for unbounded quantifiers. Cleanup then removes certain anonymous node patterns before matching.

  • 6.3 Expansion: Expansion creates one rigid pattern for each positive quantifier length and each selected path-pattern union alternative.In the example, patterns are denoted θ_n,ℓ for n∈N \ {0} and ℓ∈{City, Country}.
  • 6.3 Expansion: Unbounded quantifiers generate infinitely many rigid patterns, so later techniques are needed to make evaluation feasible.The example expands the quantifier once and chooses one side of the union as a single possible expansion.
  • 6.3 Expansion: Group variables receive superscripts identifying the quantifier iteration in which they occur.These annotations distinguish occurrences before reduction.
  • 6.3 Expansion: Cleanup deletes an anonymous-variable node pattern when it is adjacent to another node pattern, producing π_n,ℓ.The resulting cleaned pattern is the form used for subsequent rigid-pattern matching.

6.4 Computation of Path Binding

Rigid patterns are matched independently against the graph, joined on shared variable names, and checked against labels, predicates, and restrictors. In the example, only specific trail lengths yield matches.

  • 6.4 Computation of Path Binding: Each rigid pattern independently produces path bindings made from elementary variable–graph-element pairs.The bindings are presented as sequences whose columns represent elementary bindings.
  • 6.4 Computation of Path Binding: Node-edge-node components are matched independently and their results are equi-joined on variables with the same name.Labels and WHERE predicates are checked during component matching.
  • 6.4 Computation of Path Binding: Variables with different subscripts or superscripts are not joined, preserving distinctions between quantifier iterations and anonymous elements.Only identical variable names participate in the implicit join.
  • 6.4 Computation of Path Binding: The TRAIL restrictor rejects a candidate that reuses the loop (t4,t5,t2,t3), so π8,City has no match.The restriction is checked after the component results are joined.
  • 6.4 Computation of Path Binding: Only n=4 and n=7 produce matches, with one match for each of π4,City, π4,Country, π7,City, and π7,Country.The longer matches are trails but not acyclic because node a3 appears twice.

6.5 Reduction and Deduplication

Reduction removes iteration annotations and merges variables introduced by anonymous element patterns. Deduplication then keeps one copy of each equal reduced binding, leaving two distinct results in the example.

  • 6.5 Reduction and Deduplication: Reduction strips subscripts and superscripts from path-binding variables and merges variables introduced in anonymous element patterns.This produces reduced path bindings from the annotated matches.
  • 6.5 Reduction and Deduplication: All reduced path bindings are collected into a set, so equal bindings produced by different rigid patterns are kept only once.The running query therefore ends with two distinct reduced path bindings.
  • 6.5 Reduction and Deduplication: A label-expression disjunction can be expressed instead as a path-pattern union.This observation follows the detailed reduction example and its equivalent query form.
  • 6.5 Reduction and Deduplication: Selectors are applied after deduplication, as illustrated by replacing the TRAIL restrictor with ALL SHORTEST.The selector stage follows collection of reduced path bindings.

MATCH ALL SHORTEST

GPML evaluates graph patterns into path bindings, while SQL/PGQ and GQL determine how those bindings become query outputs. Pattern combinations use separate evaluation, cross products, implicit joins, and filtering.

  • Pattern composition: Each path pattern is solved separately, then their binding sets are combined by cross product and filtered through implicit equi-joins and WHERE.
  • Processing model: GPML processing takes a graph pattern and graph database as inputs, producing bindings consumed by the host language.
  • Host-language outputs: SQL/PGQ consumes reduced path bindings to produce a table, whereas GQL can produce a graph view or new graph.
  • Host-language outputs: GQL path bindings define subgraphs of the input graph, including nodes, edges, and variable annotations.
  • Host-language outputs: The initial GQL release aligns outputs with SQL/PGQ, while future versions are anticipated to add more advanced output options.

7 LOOKING FORWARD

The standards are progressing through ISO/IEC procedures while GPML remains an active area for extensions and research. Open directions include richer matching, optimization, recursion, expressiveness, termination, and implementation questions.

  • Standards process: SQL/PGQ and GQL are being developed in ISO/IEC JTC1 SC32 WG3 with input from national bodies and expert groups.
  • Standards process: The standards process moves from draft development through CD and DIS ballots to International Standard publication, with comment resolution after each ballot.
  • Language opportunities: GPML language opportunities include isomorphic match modes, multiple graphs, path macros, nested-quantifier binding output, cheapest-path search, and JSON export.
  • Standards process: The schedule depends on incomplete work and may change, while GPML is expected to be fairly stable when SQL/PGQ begins DIS ballot.
  • Research directions: Research questions concern GPML expressiveness, complexity, termination, shortest-path optimization, recursive patterns, temporal data, and restrictions useful for updates.
  • Research directions: Fully recursive patterns could search for trees and structures more complex than paths, but their syntax, applications, and cost remain open questions.

8 RELATED WORK

GPML builds on established graph-query research while extending prior path-query formalisms with path variables, group variables, and richer matching semantics. Its design also relates to pattern languages for XML, RDF, and other graph systems.

  • Foundations: GPML extends Conjunctive Regular Path Queries with group variables and variables that bind to entire paths.
  • Foundations: Binding variables to paths makes paths first-class citizens in GPML, following the direction advocated by G-CORE.
  • GPML extensions: GPML adds finer-grained matching, multiplicity-sensitive aggregation, and restrictions on returned paths; these are described as original contributions.
  • Related languages: Unlike SPARQL's endpoint semantics, GPML's path-oriented design supports bindings to paths, while XML and XQuery patterns are constrained by tree structure or limited quantification.
Loading 2112.06217v1…