Graph Pattern Matching in GQL and SQL/PGQ

Alin Deutsch
UCSD & TigerGraphUSA

Nadime Francis

LIGM, U Eiffel, CNRSFrance

Alastair Green
LDBC & BirkbeckUK

Keith Hare
JCC Consulting & Neo4jUSA

Bei Li

Leonid Libkin
U Edinburgh & ENS-Paris & Neo4jUK & France

Tobias Lindaaker

Victor Marsault
LIGM, U Eiffel, ENPC, CNRSFrance

Wim Martens
University of BayreuthGermany

Jan Michels

Filip Murlak
U WarsawPoland

Stefan Plantikow

Petra Selmer

Hannes Voigt

Oskar van Rest

Domagoj Vrgoč

PUC Chile & IMFDChile

Mingxi Wu

Fred Zemke

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.

<concept_desc>Computer systems organization Embedded systems</concept_desc>
<concept_desc>Computer systems organization Redundancy</concept_desc>
<concept_desc>Computer systems organization Robotics</concept_desc>
<concept_desc>Networks Network reliability</concept_desc>

[500]Computer systems organization Embedded systems
[300]Computer systems organization Redundancy
Computer systems organization Robotics
[100]Networks Network reliability

§ INTRODUCTION

Graph databases are becoming widely used <cit.>.
Many applications
require graph-structured data for analysis: they are found in a
variety of scientific domains, such as biology and
chemistry<cit.>. Machine learning increasingly centres
on graph networks <cit.>. Business
transaction records, and derived metrics and control data, are
viewed as graphs to detect fraud patterns, understand market
trends and customer behaviours, and to model data lineage and
complex access control rules.

Graphs appeal to many kinds of
users because the graph data model is akin to conceptual models,
which reflect our intuitive view of information as the properties
of entities and their relationships. Human knowledge, when
gathered incrementally as linked data items, naturally falls into
the shape of a graph: this is visible in open-source knowledge
graphs, such as Wikidata and DBpedia, and in the internal
knowledge bases that big tech companies build in order to inform
their decision and service-oriented tasks.

Two of the most popular ways of representing graphs are the  Resource Description Framework (RDF) <cit.>, and  property graphs <cit.>. In RDF, the data is modelled as a directed edge-labelled graph. On the other hand, property graph models the data as a mixed (that is, partially directed) multigraph. Both nodes and edges can be labelled, and also attributed (that is, associated with property/value pairs). In this paper we focus on property graphs.

The property graph data model has gained adoption in many commercial database systems. Examples include  AgensGraph, Amazon Neptune, ArangoDB,  CosmosDB, DataStax Enterprise Graph, HANA Graph, IBM Db2 Graph, JanusGraph, Neo4j, Oracle Server and PGX, RedisGraph, Sparksee, Stardog, and TigerGraph.
Unlike RDF with its query language SPARQL <cit.>, which is a W3C standard, property graph systems possess disparate storage models and querying facilities, present either in the form of APIs like Gremlin, or, since 2010, in the form of declarative graph query languages including Cypher from Neo4j <cit.>, GSQL from TigerGraph <cit.>, and PGQL from Oracle <cit.>, as well as industry/academia prototypes such as G-CORE <cit.>. Pre-existing property graph data languages overlap substantially in core features, but each has also introduced unique innovations. The 2015 openCypher project has led to a widening industrial use of Cypher as a language for property graphs, but did not succeed on its own in establishing a standard.

As graph data management has expanded as a product category, the lack of a standard query language (and associated sub-languages for schema definition) for property graphs has been felt more strongly. The situation resembles the early days of the relational/tabular data model, which led to the standardization of SQL, a hugely successful  lingua franca. In 2019 the Joint Technical Committee 1 of ISO/IEC, which defines information technology standards for the International Organization for Standardization, and International Electrotechnical Commission, approved a project to create GQL, a standard property graph query language with full CRUD (create/read/update/delete) and catalog capability. GQL builds on prior graph languages, as well as a new part 16 of SQL, in development since 2017, called SQL/PGQ. PGQ (short for property graph queries) specifies how to define graph views over an SQL tabular schema, and to run read-only queries over such views, that can be projected by an SQL SELECT statement.

GQL and SQL/PGQ share a common data model, and a common graph pattern matching language, called GPML throughout the paper. Both language projects have been assigned to the ISO/IEC JTC1 SC32 (Subcommittee 32) Working Group for Database Languages (WG3) which continues to be responsible for maintaining and enhancing SQL as a whole. This structure serves a policy that GPML be kept identical in GQL and SQL/PGQ. The common GPML sublanguage is the central subject of this paper.

Graph query languages extract data from a graph that matches a graph pattern. In GPML a graph pattern is a collection of path patterns,
which when applied to a property graph, results in a set of path bindings, each mapping variables in the expression to graph elements (node and edges) forming a path in the graph. These variable bindings can be used to refer to the graph elements and the values of their properties. The way in which path bindings are projected to produce query results varies between SQL/PGQ and GQL, but the set of path bindings matching a path pattern for a given graph (prior to result projection) will be the same for both languages.

The standards process for both languages is governed by WG3, whose expert members represent the national standards bodies
of China, Denmark, Finland, Germany, Japan, Korea, the Netherlands, Sweden, the UK, and the USA.
In addition WG3 has a liaison relationship with Linked Data Benchmark Council (LDBC). LDBC is a consortium of industrial companies, research institutes, academic researchers and consultants. LDBC defines benchmark standards for graph data workloads, but also supports the work of WG3 on GQL and SQL/PGQ by adding the expertise of its members to suggest improvements, or new ideas that may ultimately be incorporated in the official standards (for example, the Property Graph Schema Working Group in LDBC). As part of this process, an academic group was created under the auspices of LDBC, called FSWG (Formal Semantics Working Group). Members of this group previously provided a complete formal semantics of Cypher features <cit.>. The group's goal was to scrutinize and comment on the design of the GPML sublanguage, and to suggest improvements.

This paper gives an accessible summary of the GPML of GQL and SQL/PGQ. It does so before these two standards are published, and before vendors (including those which are represented in the author list) have released  implementations of the features of GPML—but at an advanced stage of consensus on its scope and design.

The paper is organized as follows. In
Section <ref> we review the property graph model and in Section
<ref> we give a brief overview of pattern matching facilities in existing languages and survey related work.
Section <ref> describes the main functionalities of the GPML of GQL and SQL/PGQ. In Section
<ref> we explain how the language ensures finiteness of outputs, as there could be infinitely many cyclic paths in a graph.
<ref> provides a detailed explanation of the pattern-matching algorithm by means of an example. Section <ref> describes future plans in terms of the Standard release, industrial implementations, and new research questions that the GPML poses.

§ PROPERTY GRAPHS

every state=[draw,thick,rectangle,rounded corners,fill=white!85!black,minimum size=5mm, text=black, font=, inner sep=0pt]
every node=[font=]

[state] (acc1) at (-4,3)

owner: Scott

isBlocked: no

[state] (acc2) at (5,3)

owner: Aretha

isBlocked: no

[state] (acc3) at (0,0)

owner: Mike

isBlocked: no

[state] (acc4) at (10,0)

owner: Jay

isBlocked: yes

[state] (acc5) at (-5,-3)

owner: Charles

isBlocked: no

[state] (acc6) at (5,-3)

owner: Dave

isBlocked: no

[rectangle,draw,fill=white] (acc1label) at ($(acc1)+(0.5,0.6)$) Account;
[rectangle,draw,fill=white] (acc2label) at ($(acc2)+(0.5,0.6)$) Account;
[rectangle,draw,fill=white] (acc3label) at ($(acc3)+(0.5,0.6)$) Account;
[rectangle,draw,fill=white] (acc4label) at ($(acc4)+(0.5,0.6)$) Account;
[rectangle,draw,fill=white] (acc5label) at ($(acc5)+(0.5,0.6)$) Account;
[rectangle,draw,fill=white] (acc6label) at ($(acc6)+(0.5,0.6)$) Account;

[text=darkred] at ($(acc1)+(.1,-.6)$) a1;
[text=darkred] at ($(acc2)+(.6,-.6)$) a2;
[text=darkred] at ($(acc3)+(,-.6)$) a3;
[text=darkred] at ($(acc4)+(.1,-.6)$) a4;
[text=darkred] at ($(acc5)+(.1,-.6)$) a5;
[text=darkred] at ($(acc6)+(.1,-.6)$) a6;

[state,dashed,fill=white!95!black] (t1) at (-1.5,2)

date: 1/1/2020

amount: 8M

[state,dashed,fill=white!95!black] (t2) at (1.5,2)

date: 2/1/2020

amount: 10M

[state,dashed,fill=white!95!black] (t3) at (9,2)

date: 3/1/2020

amount: 10M

[state,dashed,fill=white!95!black] (t4) at (9,-2)

date: 4/1/2020

amount: 10M

[state,dashed,fill=white!95!black] (t5) at (1.7,-2)

date: 6/1/2020

amount: 10M

[state,dashed,fill=white!95!black] (t6) at (0,-3.5)

date: 7/1/2020

amount: 4M

[state,dashed,fill=white!95!black] (t7) at (-1.2,-2)

date: 8/1/2020

amount: 6M

[state,dashed,fill=white!95!black] (t8) at (-5,0)

date: 9/1/2020

amount: 9M

[rectangle,draw,dashed,fill=white] (t1label) at ($(t1)+(0.5,0.6)$) Transfer;
[rectangle,draw,dashed,fill=white] (t2label) at ($(t2)+(0.5,0.6)$) Transfer;
[rectangle,draw,dashed,fill=white] (t3label) at ($(t3)+(0.5,0.6)$) Transfer;
[rectangle,draw,dashed,fill=white] (t4label) at ($(t4)+(0.5,0.6)$) Transfer;
[rectangle,draw,dashed,fill=white] (t5label) at ($(t5)+(0.5,0.6)$) Transfer;
[rectangle,draw,dashed,fill=white] (t6label) at ($(t6)+(0.5,0.6)$) Transfer;
[rectangle,draw,dashed,fill=white] (t7label) at ($(t7)+(0.5,0.6)$) Transfer;
[rectangle,draw,dashed,fill=white] (t8label) at ($(t8)+(0.5,0.6)$) Transfer;

[text=darkblue] at ($(t1)+(.1,-.6)$) t1;
[text=darkblue] at ($(t2)+(.1,-.6)$) t2;
[text=darkblue] at ($(t3)+(-.1,-.6)$) t3;
[text=darkblue] at ($(t4)+(-1.5,0)$) t4;
[text=darkblue] at ($(t5)+(.1,-.6)$) t5;
[text=darkblue] at ($(t6)+(1.45,.2)$) t6;
[text=darkblue] at ($(t7)+(.1,-.6)$) t7;
[text=darkblue] at ($(t8)+(.1,-.6)$) t8;

[state] (p1) at (-9,-1)

number: 111

isBlocked: no

[state] (p2) at (3.5,1)

number: 222

isBlocked: no

[state] (p3) at (13,0)

number: 333

isBlocked: no

[state] (p4) at (5,-1)

number: 444

isBlocked: no

[rectangle,draw,fill=white] (p1label) at ($(p1)+(0.45,0.6)$) Phone;
[rectangle,draw,fill=white] (p2label) at ($(p2)+(0.45,0.6)$) Phone;
[rectangle,draw,fill=white] (p3label) at ($(p3)+(0.45,0.6)$) Phone;
[rectangle,draw,fill=white] (p4label) at ($(p4)+(0.45,0.6)$) Phone;

[text=darkred] at ($(p1)+(.1,-.6)$) p1;
[text=darkred] at ($(p2)+(.1,-.6)$) p2;
[text=darkred] at ($(p3)+(.1,-.6)$) p3;
[text=darkred] at ($(p4)+(.3,-.6)$) p4;

[state] (ip1) at (-9,1)

number: 123.111

isBlocked: no

[state] (ip2) at (-9,-3)

number: 123.222

isBlocked: no

[rectangle,draw,fill=white] (ip1label) at ($(ip1)+(0.45,0.6)$) IP;
[rectangle,draw,fill=white] (ip2label) at ($(ip2)+(0.45,0.6)$) IP;

[text=darkred] at ($(ip1)+(.1,-.6)$) ip1;
[text=darkred] at ($(ip2)+(.1,-.6)$) ip2;

[state] (c1) at (-8,3)

name: Zembla

[state] (c2) at (12.5,3)

name: Ankh-Morpork

[rectangle,draw,fill=white] (c1label) at ($(c1)+(0.5,0.4)$) Country;
[rectangle,draw,fill=white] (c2label) at ($(c2)+(0.5,0.4)$) City, Country;

[text=darkred] at ($(c1)+(-.1,-.5)$) c1;
[text=darkred] at ($(c2)+(.3,-.5)$) c2;

(acc1) edge[bend left] (acc3)
(acc3) edge[bend left] (acc2)
(acc2) edge[bend left] (acc4)
(acc4) edge[bend left] (acc6)
(acc6) edge[out=190,in=-10] (acc5)
(acc6) edge[bend left] (acc3)
(acc3) edge[bend left] (acc5)
(acc5) edge[bend left] (acc1)

[-,thick,densely dotted]
(acc1) edge node [above,sloped,text=darkblue] hp1 (p1)
(acc2) edge node [right,text=darkblue] hp2 (p2)
(acc3) edge node [above,text=darkblue] hp3 (p2)
(acc4) edge node [below,text=darkblue] hp4 (p3)
(acc5) edge node [above,sloped,text=darkblue] hp5 (p1)
(acc6) edge node [left,text=darkblue] hp6 (p4)

(acc1) edge [out=180,in=0] node [above,sloped,text=darkblue] li1 (c1)
(acc2) edge [out=10,in=170] node [above,sloped,text=darkblue] li2 (c2)
(acc3) edge [out=160,in=-30] node [above,sloped,near start,text=darkblue] li3 (c1)
(acc4) edge [out=20,in=270] node [above,sloped,text=darkblue] li4 (c2)
(acc5) edge [out=140,in=290] node [above,sloped,text=darkblue] li5 (c1)
(acc6) edge [out=60,in=220] node [above,sloped,text=darkblue] li6 (c2)

(acc1) edge node [above,sloped,near start,text=darkblue] sip1 (ip1)
(acc5) edge node [below,text=darkblue] sip2 (ip2)

at (12,-1.8) Edge labels:;

[-latex,thick] (11,-2.3) edge (12,-2.3);
at (12.8,-2.3) ;

[-latex,thick, dotted] (11,-2.7) edge (12,-2.7);
at (13,-2.7) ;

[-,thick,densely dotted] (11,-3.1) edge (12,-3.1);

at (12.8,-3.1) ;

[-,thick,dashed] (11,-3.5) edge (12,-3.5);
at (13.1,-3.5) ;

A property graph with information on bank accounts, their location, and financial transations.

To describe property graphs, we use a common application scenario involving banking and financial transactions (used, e.g., for fraud detection). Figure <ref> is an example of a property graph containing information about bank accounts, their location, their associated phone numbers and IP addresses, and financial transactions between them. The graph contains nodes, which are connected by edges. Nodes and edges are identified by node identifiers (a1, …, a6, c1, c2, p1,…,p4, ip1, ip2) and edge identifiers (t1,…,t8, li1,…,li6,hp1,…,hp6,sip1,sip2), respectively. Furthermore, both nodes and edges can carry labels (e.g., Account, City, Transfer, isLocatedIn) and property/value pairs (e.g., owner/Mike, isBlocked/no). In figures, we will depict node information in solid boxes, and edge information in dashed boxes. We use the umbrella term element to refer to nodes or edges. When clear from the context,  we do not distinguish between node identifiers and nodes (similarly for edges).

In graph-theoretic literature, graphs are usually defined as pairs $\langle V,E\rangle$ of vertices $V$ and edges $E$ which are either two-element subsets of $V$ for undirected graphs, or pairs of vertices for directed graphs. In contrast, property graphs are multigraphs (there can be multiple edges between two endpoint nodes);  pseudographs (there can be an edge looping from a node to itself); they are mixed, or partially directed: an edge can be undirected, or can have source and target nodes, in which case it is directed from the source to the target. They are also attributed: graph elements can have attributes (a disjoint union of labels and properties).

This is summarized in the following definition.
Assume that $\cL$, $\cP$, and $\val$ are countably infinite sets, containing labels,  property names, and property values, respectively.

A property graph is defined as a tuple $G = (N, E, \rho, \lambda, \pi)$ where:

* $N$ is a finite set of node identifiers;

* $E$ is a finite set of edge identifiers;
such that $N \cap E = \emptyset$;

* $\rho : E \rightarrow (N \times N) \cup \{\{u,v\} \mid u,v \in N\}$ is a total function mapping edges
to ordered or unordered pairs of nodes;

* $\lambda : (N \cup E) \rightarrow 2^{\cL}$ is a total function mapping node and edge identifiers
to sets of labels (including the empty set);

* $\pi : (N \cup E) \times \cP \rightharpoonup \val$ is a partial function mapping elements and property names to property values.

We call an edge $e$ directed if $\rho(e) \in N \times N$ and undirected if $\rho(e) \in \{\{u,v\} \mid u,v \in N\}$. In both cases we say that $e$ connects $u$ and $v$. Notice that both directed and undirected edges allow $u = v$, in which case the edge is a self-loop. Furthermore, the definition allows both directed and undirected edges to carry labels and data. Indeed, $\lambda$ and $\pi$ can be defined for directed and  undirected edges. The definition does not preclude having two different edges connecting the same nodes.
For more details we refer the reader to <cit.>.

A property graph has a graph representation, which is illustrated in Figure <ref>, but it also has a tabular representation, which is illustrated in Figure <ref>. In the graph representation, we depicted the nodes in red and the edges in blue. We depicted the properties and values associated to nodes in grey rounded rectangles (which are dashed for edges) and most of the labels in white rectangles. To avoid clutter however, we have omitted the labels on some edges (namely isLocatedIn, hasPhone, and signInWithIP).
The tabular representation has a relation for every combination of labels that appears on some node or edge in the graph. For instance, every label that appears in Figure <ref> is a relation name in the tabular representation, except City, which does not appear by itself. It does appear together with Country (on node c2), so the tabular representation has a relation named CityCountry, which contains node c2.

ID     owner     isBlocked

a1     Scott     no

a2     Aretha     no

a3     Mike     no

ID     A_ID1     A_ID2     date     amount

t1     a1     a3     1/1/2020     8M

t2     a3     a2     2/1/2020     10M

t3     a2     a4     3/1/2020     10M

ID     A_ID     s_ID

sip1     a1     ip1

sip2     a5     ip2

ID     name

c1     Zembla

ID     name

c2     Ankh-Morpork

Excerpts of five tables of the tabular representation of the property graph in Figure <ref>. The tables Transfer and signInWithIP represent edges, the others represent nodes.

A path is an alternating sequence of nodes and edges such that: (1) it starts and ends with a node; and (2) subsequent nodes in the sequence are connected by the edge between them.[As is usual in the graph database literature <cit.>, we use the term path to denote what is called walk in the graph theory literature <cit.>.]
We write paths as $\pathvalue{c1,li1,a1,t1,a3,hp3,p2}$
indicating a path from node c1 to node p2 that first follows edge li1 in reverse direction, then the edge t1 in forward direction, and then the undirected edge hp3.

§ GRAPH PATTERN MATCHING TODAY

As identified in a recent survey of modern graph query languages <cit.>, when querying graph databases, one usually starts by selecting atomic graph elements, such as nodes, edges, or paths. Coming back to our example from Figure <ref>, basic elements we might want to select are, for instance:

* All the nodes representing a blocked account;

* All the edges representing a money transfer from a blocked to a non-blocked account that occurred on a specific date;

* All the paths whose edges represent money transfers, and that start in a non-blocked account, but end in a blocked one.

In an abstract sense, we could represent these elements as patterns shown in Figure <ref>.
In addition to standard elements of a property graph, these graph patterns also attach variables $x$, $y$, $e$,  to different parts of the patterns. To match such a pattern in a property graph, we need a mapping that links the node patterns to nodes in the graph, and similarly with edge and path patterns. For instance, the pattern (a) from Figure <ref> matches to an  node such that the value of the property  is set to . Similarly, the pattern (b) of Figure <ref> matches the node variables $x$ and $y$ to two accounts (the first one blocked, and the second one not), while $e$ matches an edge of type  connecting these two nodes, with the value of  set to .

The most interesting pattern, shown in Figure <ref>(c), specifies a path of arbitrary length. Starting from <cit.>, specifying paths via regular expressions over edge types has been well established both in the research community <cit.> and in the industry <cit.>. Several ways of defining valid paths (simple, arbitrary, etc.) have been proposed <cit.>; we discuss them in later sections.

every state=[draw,thick,rectangle,rounded corners,fill=white!85!black,minimum size=5mm, text=black, font=, inner sep=0pt]

[state] (n1) at (0,0)

[rt] (n1label) at ($(n1)+(0,0.35)$) $x$ : Account;

[state] (n2) at (-3,-1.3)

[rt] (n2label) at ($(n2)+(0,0.35)$) $x$ : Account;

[state] (n3) at (3,-1.3)

[rt] (n3label) at ($(n3)+(0,0.35)$) $y$ : Account;

[arrout] (n2) to
node[state,fill=white!95!black,dashed] (e1)

[ert] (e1label) at ($(e1)+(0,0.35)$) $e$ : Transfer;

[state] (n4) at (-3,-2.6)

[rt] (n4label) at ($(n4)+(0,0.35)$) $x$ : Account;

[state] (n5) at (3,-2.6)

[rt] (n5label) at ($(n5)+(0,0.35)$) $y$ : Account;

[arrout] (n4) to
node[erect, below] (e2)

[ert] (le2) at (e2.north) :Transfer$^+$;

at (0,-.5) (a);
at (0,-1.8) (b);
at (0,-3.05) (c);

Node pattern, edge pattern, and a path pattern.

With these basic building blocks at hand, we can define more complex graph patterns. For instance, assume that in the property graph from Figure <ref>, we want to identify all pairs of owners with accounts that are located in Ankh-Morpork, and are connected by a path of (arbitrarily many) money transfers. Additionally, we might want to stipulate that the first account is blocked, while the second one is not blocked. Following our graphical representation, one can visualize this query as the graph pattern in Figure <ref>. Notice that the pattern only specifies what we want to match in the graph, not what we want to output (the owners of x and y).

every state=[draw,thick,rectangle,rounded corners,fill=white!90!black,minimum size=5mm, text=black, font=, inner sep=0pt]
every node=[font=]

[state] (n1)

[rt] (n1label) at ($(n1)+(0,0.35)$) :City;

[state] (n2) at (-3,-1.5)

[rt] (n2label) at ($(n2)+(0,0.35)$) $x$ $:$ Account;

[arrout] (n2label) to
node[below, erectw] (e1)

[ert] (le1) at (e1.north) :isLocatedIn;

[state] (n5) at (3,-1.5)

[rt] (n5label) at ($(n5)+(0,0.35)$) $y$ $:$ Account;

[arrin] (n1) to
node[ert] (e6) :isLocatedIn

[arrin] (n5) to
node[ert] (e) :Transfer$^+$

Pattern of fraudulent accounts in Ankh-Morpork.

In general, a graph pattern specifies a set of nodes and their connections via edges and paths, filtered according to labels and values of some of their properties. Such a graph-shaped query gets matched to the graph database  to obtain a (collection of) result(s).
Graph patterns form the core of most existing graph query languages, and have been present in academic research (under the name of conjunctive regular path queries, or CRPQs <cit.>), in W3C recommendations ( SPARQL <cit.>), and in existing property graph engines <cit.>.
We next summarize the support for graph patterns in SPARQL, Neo4j's Cypher, Oracle PGQL, and TigerGraph's GSQL. For historical reasons, we begin with SPARQL.

The SPARQL standard <cit.> prescribes graph pattern matching on edge-labeled graphs represented as a single ternary relation. Neither labels nor properties are present in SPARQL, and  matching is done only between nodes and constants. Path queries are supported by means of property paths <cit.> that permit full 2RPQs <cit.> under arbitrary path semantics. In order to avoid infinite results when cycles are present, SPARQL prescribes that one can only check for the existence of a path between a pair of nodes, but cannot count the number of such paths, or try to reconstruct them <cit.>. A much simplified version of the query from Figure <ref> in SPARQL (assuming cities are identified by their names), would be the following:

SELECT ?x, ?y
WHERE  ?x isLocatedIn "Ankh-Morpork".
?y isLocatedIn "Ankh-Morpork".
?x Transfer+ ?y

The most common query language for property graphs is Cypher <cit.> that originated at Neo4j and has since been implemented by vendors such as Amazon, Agens Graph, Katana Graph, Memgraph, RedisGraph, and SAP HANA <cit.>.
The owners of the accounts in the query from Figure <ref> can be found with Cypher as follows:

MATCH (a:Account isBlocked:'no')-[:isLocatedIn]->
(g:City name:'Ankh-Morpork')<-[:isLocatedIn]-
(b:Account isBlocked:'yes'),
p = (a)-[:Transfer*1..]->(b)
RETURN a.owner, b.owner

The query first matches the variables a and b to an  unblocked and a blocked account located in Ankh-Morpork, using its “ASCII-art” syntax for specifying edges. It then matches p to a whole path of transfers of arbitrary length from a to b, and returns the owners.
Unlike SPARQL, Cypher allows returning  paths: we can return p simply by including it in the RETURN clause.

Cypher's pattern matching has multiple other features.
It permits label disjunctions  and inline predicates in variable-length path patterns: MATCH !(a)-[:X|Y*weight:1]->(b)!. It supports testing for the presence or absence of a path relative to an element specified in a match:
MATCH !(a:Person)->(:Cat)! WHERE NOT !(a)->(:Dog)!.
It also allows custom graph traversals by calling user-defined procedures via CALL, and complex predicates involving nested data, especially paths.
Cypher also allows additional operations on matched paths such as returning a single shortest or all shortest paths, returning all nodes or edges in a path,
the length of a path, as well as the number of paths found.

PGQL (Property Graph Query Language) <cit.> is an SQL-like graph pattern matching query language that is open-sourced by Oracle.
Where features overlap, PGQL follows SQL's syntax and semantics, such as in SELECT, WHERE, GROUP BY, HAVING, and ORDER BY, as well as for functions, aggregations, predicates, existential and scalar subqueries.
The core of a PGQL query is the graph pattern, which is spread over multiple MATCH clauses that are syntactically placed inside the FROM clause.
The owners of the accounts of query in Figure <ref> can be found as follows.

SELECT x.owner AS A, y.owner AS B
MATCH (x:Account)-[:isLocatedIn]->
MATCH ANY (x)-[e:Transfer]->+(y)
WHERE x.isBlocked='no' AND y.isBlocked='yes'
AND g.name='Ankh-Morpork'

We can return the whole path of Transfer edges between x and y by replacing the first line of the query with SELECT x.owner AS A, y.owner AS B, LISTAGG(e.ID, ', '), assuming that e.ID is the ID of edge e.
Here, the variable e is treated as a group variable that matches subsequent edges of the path and can be used to aggregate data along paths of variable length. For example, one can compute the length of the path using COUNT(e), or filter out paths with repeated edges using WHERE COUNT(e) = COUNT(DISTINCT e). The aggregate LISTAGG(e.ID, ', ') produces a comma-separated list of values encoded as a single string of characters.
ANY is used to obtain an arbitrary single
path from x to y.
PGQL supports also
ANY SHORTEST,
ALL SHORTEST,
TOP k SHORTEST,
ANY CHEAPEST, and
TOP k CHEAPEST,
allowing for retrieving multiple paths between a pair of nodes. ALL gives all paths but requires an upper bound on the path length, , !1,4! instead of +.

The design philosophy behind
TigerGraph's GSQL (Graph SQL) language <cit.> is to flatten the learning curve for the largest community of potential adopters, namely SQL programmers.
Like PGQL, GSQL supports
SQL-style SELECT, WHERE,
GROUP BY, HAVING, LIMIT and ORDER BY clauses, aggregation, and graph
patterns in the FROM clause.
The running example query from
Figure <ref> is expressed in GSQL as follows, using table
T to hold the result.

SELECT x.owner AS A, y.owner AS B INTO T
FROM Account:x -(isLocatedIn>)- City:g
-(<isLocatedIn)- Account:y,
:x -(Transfer>+)- :y
WHERE x.isBlocked='no' AND y.isBlocked='yes'
AND g.name='Ankh-Morpork'
GROUP BY A, B

GSQL's default semantics is ALL SHORTEST,
hence there is no upper bound on the + quantifier.
While supporting group and path variables is on the near-future roadmap for GSQL, this is merely a matter of adding syntactic sugar as they
are currently expressible using a GSQL-specific aggregation paradigm
based on accumulators. These are containers that
can be attached at query time to the vertices and written to during the pattern matching phase.
Accumulator inputs are aggregated via pre- or user-defined
binary operators.
Accumulator-based aggregation was shown
to enjoy expressivity and efficiency benefits over SQL-style aggregation <cit.>.

[Compare: proposed summary of concepts of graph pattern matching in SQL/PGQ]

[Actually better this one https://docs.google.com/document/d/175cNEmVQI3AgNUWeGG7DKaQp1hiN4Gbtxiab5kwnbYE/edit]

A few basic examples of PGQ patterns based on the example from Section 2

TEAM: Alin

§ GRAPH PATTERN MATCHING LANGUAGE

Recall that we use the acronym GPML to denote
the common graph pattern matching language
that is shared by SQL/PGQ and GQL. In the database domain there is no
standard or product by those initials to our knowledge;
it is just a convenient abbreviation for this paper. This section is devoted to explaining how GPML works. In general, a GPML pattern is an expression of the form:

MATCH °Pattern°

where Pattern is a pattern specifying the parts of our input property graph we want to explore. The MATCH clause may be optionally followed by a WHERE clause to filter the results; we discuss it later in the section. For example, the following expression
retrieves all the accounts in our graph from Figure <ref> that are not blocked:

MATCH (x:Account WHERE x.isBlocked='no')

Intuitively, this pattern, which is an example of a node pattern, binds to x all the nodes in the graph which have the label Account, and whose isBlocked property has the value no. Another basic pattern, called the edge pattern  extracts edges from our graph. For instance, the following pattern asks for all the edges which represent transfers with a value of more than 5 million:

MATCH -[e:Transfer WHERE e.amount>5M]->

We shall use shorthands such as 5M for readability. The variable e gets bound to an edge in our graph, giving us access to its data. We later explain how one can also retrieve the endpoints of the edge. Generally, node and edge patterns retrieve graph elements – nodes and edges – and can then be combined in more complex ways to define paths and patterns present in our graph. In what follows we specify how all of this is supported in GPML. We start by expanding on our definition of node and edge patterns.

§.§ Accessing Nodes and Edges

*Node patterns. The most basic query pattern allows the user to fetch nodes inside a property graph. For instance, to extract all of the nodes of the graph, the user can write the following[The ascii art !()! used for nodes is meant to be suggestive of how nodes are usually drawn as circles in visual representation of a graph.]

MATCH (x)

The variable x here is called an element variable, since it binds to a graph element. In the case of x, it will be bound to a node in the graph, since it is placed inside the !( )! braces, which signify that we are talking about a node.
For instance, if evaluated on the property graph from Section <ref>, this query will return bindings that map x to accounts, cities, phones, and IPs.[For now we model query evaluation as a process taking a property graph and a query pattern as input, and producing as output a multiset of  bindings from the set of variables to the set containing graph elements and property values. In Section <ref> we extend this to capture more advanced objects such as arbitrary length paths.]

Of course, one rarely wants to obtain all the nodes in a graph, and usually will want to restrict the obtained results in some way. A natural way to do this is to look only for nodes with a specific label. GPML does this via label expressions. For instance,
to return nodes that correspond to accounts, one writes:

MATCH (x:Account)

Here the label is explicitly specified, and only nodes with the label Account will now be bound to x. More generally, label expressions allow conjunctions (&), disjunctions (|), negations (!), and grouping of individual labels by using parentheses. For instance, to capture all the nodes that are either accounts, or IP addresses, we would write MATCH (x:Account|IP). There is also a wildcard symbol % matching any label; e.g., pattern

matches nodes that have no labels.

Further filters on a node restrict the values of some of its properties. As seen earlier, if we are interested only in those accounts that are not blocked, the pattern !(x:Account)! changes to
!(x:Account WHERE x.isBlocked='no')!.
The WHERE clause can be put outside MATCH to be used as a postfilter for produced matches:

MATCH (x:Account)
WHERE x.isBlocked='no'

The WHERE clause can support a host of search conditions, and these may be combined into logical statements using AND, OR, and NOT.

We note that each of the restricting elements in a node pattern (e.g. the variable, the label specification, or the WHERE condition) is optional. That is, any of them can be either present or absent. This makes the following the simplest possible node pattern: !MATCH ()!.
Since there is no variable, there is no syntax
to reference the nodes bound to this pattern; consequently
it is of little use standing alone as the sole element
pattern as in this example. However, below we explain how such a pattern can be combined with edge patterns in order to extract paths and patterns in the graph. Intuitively, this construct will allow us to have a placeholder for any node in the graph, thus allowing us to link it with other graph elements.

It is of more use when
concatenated with edge patterns, as in

MATCH (x)-[:Transfer]->()-[:isLocatedIn]->(y)

In the preceding example, the user is only interested
in the bindings to x and y, consequently the user
omitted the variables from the two edge patterns
and the middle node pattern.

*Edge patterns. These let us explore an edge connecting two nodes. A basic way of doing this is via the pattern[Here again we use the  ascii art !-[]->! to mimic how one draws an edge in a graph.]

MATCH -[e]->

which searches all the directed edges in the graph,
and binds them to the element variable e. That is, the bindings generated by this pattern will map e to any identifier of a directed edge in the graph.
If we wish to use specific types of edges ( undirected), this can be done by special symbols used in the edge pattern. For example, all undirected edges
can be recovered by MATCH  [e] .

The full specification of possible edge direction restrictions and their combinations is provided in Figure <ref>. In the figure, spec is an optional element of the form e:labelExpr WHERE condition, where labelExpr and condition are as in node patterns above; when spec is omitted, the abbreviated version can be used. As an example, if we want edges that are either undirected, or directed from right to left, we could write
< [e] .

Similarly to node patterns, we can restrict which edges we wish to return by specifying their labels, or using the WHERE clause, as was shown earlier with the example that restricted Transfer edges to those with the amount exceeding 5 million.
Both label expressions and the WHERE clause can use the same constructs as in the case of node patterns. Similarly to node patterns, edge patterns need not specify an element variable. This will become useful later on when defining more complex patterns.

Orientation     Edge pattern     Abbreviation

Pointing left     !<-[! spec  !]- !     !<-!

Undirected     !  [!
spec  !]  !     ! !

Pointing right     ! -[! spec  !]->!     !->!

Left or undirected     !< [! spec  !]  !      !< !

Undirected or right     !  [! spec  !] >!      ! >!

Left or right      !<-[! spec  !]->!     !<->!

Left, undirected or right     ! -[! spec  !]- !     !-!

Table of edge patterns.

§.§ Building Path Patterns by Concatenation

Node and edge patterns can be chained together to form a path pattern. The most natural way to do this is to ask for edges in the graph, together with their source and target nodes, as in:

MATCH (x)-[e]->(y)

The bindings generated by this pattern will map
e to an edge in the property graph, and x and y to its source and target node, respectively. If we do not specify direction and write (x)-[e]-(y), then each edge will be returned twice, once for each direction in which it is traversed.

Edge direction, edge (un)directedness, or any filter on nodes/edges can be used as in the examples above. For instance, to ask for a source account of every transfer that reaches an account with the owner equal to !'Aretha'!, we write:

MATCH (y WHERE y.owner='Aretha')<-[e:Transfer]-(x)

Even if the edge pattern is ambiguous about the  orientation of e, we may wish to refer to this orientation in a postfilter. We can do this using the  predicates e IS DIRECTED,
s IS SOURCE OF e, and d IS DESTINATION OF e.

One can keep on alternating edge and node patterns to create more complex path patterns.
For instance, the query

MATCH (s)-[e]->(m)-[f]->(t)

extracts all directed paths of length two in the graph.
Variable s is bound to the id of the source node
of the path, t is bound to the id of the target node, and m to the middle node. Similarly, variables e and f are bound
to the two edge ids of the path, respectively.
Executed on the graph in Fig. <ref>, one of the returned bindings is:

\begin{equation*}
\text{\gqltext{s}}\mapsto \texteltid{a1},
\quad \text{\gqltext{e}}\mapsto \texteltid{t1},
\quad \text{\gqltext{m}}\mapsto \texteltid{a3},
\quad \text{\gqltext{f}}\mapsto \texteltid{t2},
\quad \text{\gqltext{t}}\mapsto \texteltid{a2}.
\end{equation*}

We can still use the constructs previously described (filters, orientation, labels)
in each individual edge or node pattern; for example:

MATCH (p:Phone WHERE p.isBlocked='yes')
[e:hasPhone] (a1:Account)
-[t:Transfer WHERE t.amount>1M]->(a2)

It searches for substantial transfers from accounts into which a login attempt was made from a blocked phone.
The query still extracts paths of length two,
but the first edge is undirected and the second is directed and
in forward orientation.
Hence, each returned binding maps p, a1, a2
to nodes $n_1$, $n_2$, $n_3$,
and e, t to edges $e_1$, $e_2$,
such that $e_1$ links $n_2$ and $n_1$, while $e_2$ goes from $n_2$ to $n_3$.

Moreover, one may use the same variable multiple times in order to
impose topological constraints on the matched paths via an implicit equi-join on the repeated variable.
For instance in the query below, the variable s is used twice; hence this query finds "triangles" of accounts involved in
money transfers; the reuse of variable s ensures that one starts and ends in the same node:

MATCH (s)-[:Transfer]->(s1)-[:Transfer]->(s2)-[:Transfer]->(s)

Path patterns permit the use of path variables: in the returned bindings, such a path variable is
bound to a whole path.

MATCH p = (s)-[:Transfer]->(s1)-[:Transfer]->(s2)-[:Transfer]->(s)

the variable p will be bound to paths of length three of Transfer edges that start and end in the same node.
This variable p could be returned, or used to compute a more complex value, for instance an aggregate over the bound path.

As in previous examples, the presence of variables in node or edge patterns is not compulsory.
For instance, the query

MATCH (p:Phone) [:hasPhone] (s:Account)-[t:Transfer]->
(d:Account) [:hasPhone] (p)

extracts the transfers
between accounts that were accessed from the same phone.
Since the hasPhone edges have no additional property, there is no need to return them.
It thus returns two bindings:

\begin{gather*}
\text{\gqltext{p}} \mapsto {\texteltid{p1}},
\quad \text{\gqltext{s}} \mapsto {\texteltid{a5}},
\quad \text{\gqltext{t}} \mapsto {\texteltid{t8}},
\quad \text{\gqltext{d}} \mapsto {\texteltid{a1}}
\\
\text{\gqltext{p}} \mapsto {\texteltid{p2}},
\quad \text{\gqltext{s}} \mapsto {\texteltid{a3}},
\quad \text{\gqltext{t}} \mapsto {\texteltid{t2}},
\quad \text{\gqltext{d}} \mapsto {\texteltid{a2}}
\end{gather*}

§.§ Graph Patterns

Graph patterns combine several path patterns together. As an example, consider
the fraud detection query looking for substantial transfers from accounts into which a login attempt was made from a blocked phone. It  could be alternatively written as

MATCH (p:Phone WHERE p.isBlocked='yes') [:hasPhone] (s:Account),
(s)-[t:Transfer WHERE t.amount>1M]->()

by splitting the path into two edges and reusing the variable s to indicate that these edges share a node.
In general, we can put arbitrarily many path patterns together.
For example, we can modify the above query by adding a condition that another login attempt into an account was made that did not use a phone:

MATCH (s:Account)-[:SignInWithIP]-(),
(s)-[t:Transfer WHERE t.amount>1M]->(),
(s) [:hasPhone] (p:Phone WHERE p.isBlocked='yes')

This pattern looks for three edges coming out of s which is cumbersome to write as a single path.
In such graph patterns, each path pattern produces a set of mappings, which are then joined using variables that are shared between them.

§.§ Grouping

Subexpressions within a path pattern may be grouped
using matching pairs of either parentheses of square
brackets. In common with many computer languages,
this can be done to override the operator precedence
shown in Figure <ref>, or simply for clarity.

An important capability of a parenthesized path pattern
is an optional WHERE clause. We will see examples of
this when we consider quantification, next.

§.§ Quantifiers and Group Variables

GPML includes quantifiers similar
to those in Perl and other common “regex” tools.
Figure <ref> lists the quantifiers of GPML.
Quantifiers are written as postfix operators on either
a single edge pattern or a parenthesized path pattern
(a path pattern enclosed in parentheses or square brackets with an optional WHERE clause).
For example, a path of length 2 to 5 of Transfer edges can be sought as follows:

MATCH (a:Account)-[:Transfer]->2,5(b:Account)

As an example using a parenthesized path pattern, consider the problem of finding paths of 2 to 5 Transfer edges between accounts with the same owner:

MATCH [(a:Account)-[:Transfer]->(b:Account) WHERE a.owner=b.owner]2,5

The pattern does not provide
a strict alternation of node and edge patterns; it will be unrolled two to five times, to obtain a sequence of bindings of variables a b a b…The WHERE clause here applies to each such pair of a and b bindings separately.
As variables a and b will occur multiple times in such a sequence,
the notion of binding an element variable to a unique
node or vertex is insufficient in this case, and
must be expanded to embrace path bindings
in which each variable in that sequence is mapped to a
graph element.
In addition, at the transition between groups, the previous binding of b must be the same as the next binding of a. More about the exact mechanism of such bindings will follow from the detailed example in Section <ref>.

As for a quantifier on a bare edge pattern, this is
understood by supplying anonymous node patterns to
its left and right. For example, if we are interested in pairs of accounts involved in a chain of large transfers of length between 2 and 5 we could write

MATCH (a:Account)
[()-[t:Transfer]->() WHERE t.amount>1M]2,5

Quantifier     Description

!m,n!     between !m! and !n! repetitions

!m,!     !m! or more repetitions

!*!     equivalent to !0,!

!+!     equivalent to !1,!

Table of quantifiers

Variable references are categorized as either singleton or group.
For example, in predicates such as !x.isBlocked='yes'!, the variable x is referenced as a singleton.
Intuitively, a reference is group if you have to cross a quantifier to get from the reference to the declaration of the variable.
To explain this, consider a modification of the above example where we are only interested in chains of transfers with the total value over 10 million:

MATCH (a:Account)
[()-[t:Transfer]->() WHERE t.amount>1M]2,5
WHERE SUM(t.amount)>10M

In this example, the predicate in the edge pattern
references t as a singleton, since one does not have to
cross the quantifier !2,5! to reach its declaration
which is in the same edge pattern.
The predicate in the final WHERE clause, used here as a postfilter, references t in the aggregate SUM.
In this location one has to cross the quantifier to reach the declaration of t, making it a group reference.

§.§ Path Pattern Union & Multiset Alternation

In GPML there are two forms of union, called path pattern union (with set semantics) and multiset alternation (with multiset semantics). Path pattern union is indicated by an infix vertical bar, whereas multiset alternation uses |+| as its infix operator.

An example of path pattern union is

MATCH (c:City) | (c:Country)

In the sample graph, there are two Country nodes
(c1 and c2) and one City node (c2). Thus the first
operand produces two results  $\text{\gqltext{c}}\mapsto {\texteltid{c1}}$ and $\text{\gqltext{c}}\mapsto {\texteltid{c2}}$

and the second operand produces the single result $\text{\gqltext{c}}\mapsto {\texteltid{c2}}$.

Thus the operands produce a duplicate binding
to c2, which will be reduced to a single solution in
the final result, which has one binding to c1 and one
binding to c2.

Rewriting this example with multiset alternation, we have

MATCH (c:City) |+| (c:Country)

This pattern returns three results,
one result binding c1 and two results binding c2.

Another example of deduplication using path pattern union
is overlapping quantifiers, as in this example:

MATCH ->1,5 | ->3,7

The two quantifiers overlap between 3 and 5;
consequently when the results are deduplicated the query
is equivalent to:

MATCH ->1,7

Using multiset alternation would not deduplicate the overlap in the quantifiers.

It is comparatively easy to see how to
deduplicate these examples at compile time. However, a
general algorithm to simplify arbitrary path pattern
unions in the complete language, including !WHERE! clauses,
restrictors, nested quantifiers, etc., is not so clear.
In addition, even if a transform is known,
an implementer may judge that making such
transforms for patterns that their users do not write
frequently is not worth the implementation cost. Performing
deduplication at run-time is also expensive, and from
a user perspective, it may be acceptable to get a result
that is a multiset, rather than waiting a long time for a set result. (SQL users are known to accept UNION ALL for
its speed over UNION DISTINCT for its set semantics.)
For these reasons GPML provides both path pattern union
and multiset alternation.

While this particular example is easy to
deduplicate at compile time, a general
algorithm to simplify arbitrary path pattern
unions in the language that includes !WHERE! clauses,
restrictors, nested quantifiers, etc., is not so clear and is likely to have a very high complexity, making it an unattractive option for the
Run-time deduplication is also expensive, and from
a user perspective, it may be acceptable to get a result
that is a multiset, rather than waiting a long time for a set result. This is akin to the SQL
situation with UNION ALL chosen for
its speed over UNION DISTINCT guaranteeing set semantics.
For these reasons GPML provides both path pattern union
and multiset alternation.

§.§ Conditional Variables

Consider the following query.

MATCH [(x)->(y)] | [(x)->(z)]

Node variable x will be bound if either operand
of the path pattern union binds. Variables y and z, on
the other hand, are only bound by one operand but not
by the other. We say that x  is an
unconditional singleton whereas y  and z
are conditional singletons.

Implicit equi-joins on conditional
singletons are disallowed, because they lack intuitive semantics.  For instance, in the illegal query

MATCH [(x)->(y)] | [(x)->(z)], (y)->(w)

does the fact that y must bind in  the second path pattern imply that y must bind in the path pattern union, thereby effectively excluding the results of the second operand?
Implicit equi-joins on conditional singletons were forbidden in order to eliminate such doubts.

Conditional singletons are also introduced by
the question mark operator, a postfix operator similar
to the quantifiers; for example

MATCH (x) [->(y)]?

In most “regex” tools,
the postfix question mark operator
is equivalent to the quantifier !0,1!.
In GPML the two operators have almost the same
semantics. The difference is that the quantifier !0,1!
exposes all variables as group, whereas the question
mark operator exposes singletons as conditional singletons.
This distinction was made so that query-generating
tools can solicit upper and lower bounds
for a quantifier from the user without having to watch
for !0,1! as a special case.

To provide an example of the use of conditional variables in our running example, consider a query asking for
accounts from which mobney was transferred to either a blocked account
or an account with a login from a blocked phone. It could be written as path patetrn union:

MATCH [(x:Account)-[:Transfer]->(y:Account WHERE y.isBlocked='yes')] |
[(x:Account)-[:Transfer]->()-[:hasPhone]-(p WHERE p.isBlocked='yes')]

Alternatively, one can use the question mark operator:

MATCH (x:Account)-[:Transfer]->(y:Account) [-(:hasPhone)-(p)]?
WHERE y.isBlocked='yes' OR p.isBlocked='yes'

If the optional part of the pattern is not matched, then the condition p.isBlocked='yes' is not true, and thus the account must be blocked to ensure that the condition in WHERE is true.

§.§ Graphical Predicates

In addition to familiar predicates such as comparison
(e.g., equal to, greater than, etc.) and IS NULL, GPML
specifies some predicates relevant to graphs (applicable to singleton variable references).

Many of the edge patterns are ambiguous about the
orientation of an edge. For example, -[e]-
matches a directed edge pointing either left or right,
or an undirected edge. The user may wish to interrogate
the orientation of the edge bound to e. For this, GPML
provides the following predicates:

e IS DIRECTED is true if e is bound to
a directed edge;

s IS SOURCE OF e is true if s  is bound to
the source of e;

d IS DESTINATION OF e is true if d  is
bound to the target of e.

SQL/PGQ is not able to use the equals sign to test for
equality of element references, because p=q
is interpreted as an equality test on two column values,
therefore p  and q  cannot be interpreted as element
references. GQL, on the other hand, will permit such equality tests of
element references. To provide a portable way to
test equality of element references, GPML provides the
following predicates:

* SAME(p, q, ...): test whether all
element references in the list are bound to the
same graph element.

* ALL_DIFFERENT(p, q, ...): test
whether the element references in the list are
pairwise distinct.

The element references listed in SAME or
ALL_DIFFERENT must be unconditional singletons
because the semantics of such expressions for
conditional singletons would be ambiguous.

§ ASSURING TERMINATION

Written without any restrictions, GPML queries may not terminate as they will return infinitely many matches. Consider for example,

MATCH p = (a WHERE a.owner='Dave')-[t:Transfer]->*
(b WHERE b.owner='Aretha')

It asks for paths with any number of transfers between the account owned by Dave and the account owned by Aretha. If evaluated over the graph of Figure <ref>, this query  would have an infinite number of matches, since the path matched by p could include a Transfer loop
(e.g., $\pathvalue{a3,t7,a5,t8,a1,t1,a3}$) any number of times.

To prevent this behaviour, GPML queries must demonstrably terminate; in particular,
the number of matches must be finite. To achieve this, GPML uses restrictors and selectors. Every unbounded quantifier (such as !*! above) must be contained in the scope of either a restrictor or a selector or both.

§.§ Restrictors and Selectors

A restrictor is a path predicate (that is, it imposes a condition stating which paths are acceptable) such that the number of matches cannot be infinite.
For instance, TRAIL forbids the matched path to repeat edges; there are only finitely many edges, therefore there are only finitely many paths with no repeated edges in a graph. Restrictors are listed in Figure <ref>.
Restrictors may be placed either at the head of a path
pattern, or at the head of a parenthesized path pattern.
If the above example is written as

MATCH TRAIL p = (a WHERE a.owner='Dave')-[t:Transfer]->*
(b WHERE b.owner='Aretha')

then, executed on the graph of Fig. <ref>, returns
three bindings for p:

\begin{gather*}
\pathvalue{a6,t5,a3,t2,a2}\\
\pathvalue{a6,t6,a5,t8,a1,t1,a3,t2,a2}\\
\pathvalue{a6,t5,a3,t7,a5,t8,a1,t1,a3,t2,a2}
\end{gather*}

Note that the last path repeats the node a3; it is allowed by TRAIL
but would be forbidden by the restrictor ACYCLIC.
Note also that

\begin{equation*}
\pathvalue{a6,t5,a3,t2,a2,t3,a4,t4,a6,t5,a3,t2,a2}
\end{equation*}

which traverses the Transfer cycle starting and ending in a6, is not a trail, and is thus not returned.

A selector is an algorithm that
conceptually partitions the solution space on the endpoints
and selects a finite set of matches from each partition.
For instance, ALL SHORTEST keeps all paths
having the same shortest length within each partition
defined by a pair of endpoints for which any solution
exists. Note that the shortest length can differ from
partition to partition. Selectors are listed in
Figure <ref>. Selectors may only be placed
at the head of a path pattern.
As an example,

applying a selector to the example from the beginning of Section <ref> can be done as follows:

MATCH ANY SHORTEST
p = (a WHERE a.owner='Dave')-[t:Transfer]->*(b WHERE b.owner='Aretha')

Here we wish only one of the shortest paths between the nodes a6 and a2.

In this case, there is  only one shortest path between these nodes and thus p is bound to $\pathvalue{a6,t5,a3,t2,a2}$.

*Combining restrictors and selectors.
At the conceptual level, restrictors can be seen as operating during pattern matching
while selectors operate afterwards.
[This is of course
only an intuitive description: in the case of selectors,
the engine will not compute an infinite number of matches
and then only keep some. However, to make the specification
declarative ("tell me what you want, not how to get it")
the specification indeed describes how the
infinite set is defined and then which finite selection from it should be returned.]
That is, if combined, selectors are always applied after restrictors. For instance, consider the query:

MATCH ALL SHORTEST TRAIL
p = (a WHERE a.owner='Dave')-[t:Transfer]->*
(b WHERE b.owner='Aretha')-[r:Transfer]->*(c WHERE c.owner='Mike')

It selects the shortest paths among the trails going from node a6 to node a3 and passing through a2.
It returns two bindings for p:

\begin{gather*}
\pathvalue{a6,t5,a3,t2,a2,t3,a4,t4,a6,t6,a5,t8,a1,t1,a3} \\
\pathvalue{a6,t6,a5,t8,a1,t1,a3,t2,a2,t3,a4,t4,a6,t5,a3}
\end{gather*}

The path $\pathvalue{a6,t5,a3,t2,a2,t3,a4,t4,a6,t5,a3}$
is not considered: it is shorter but it is not a trail.

This difference has one notable consequence.
Consider a query $Q$ with no selector or restrictor, and assume that $Q$ has matches.
Then, adding a selector to $Q$ might reduce the number of matches, but the resulting query will always have at least one match.
On the other hand, adding a restrictor to $Q$ might yield a query with no matches at all.

For example, consider the query

MATCH (p:Account WHERE p.owner='Natalia')->1,10
(q:Account WHERE q.owner='Mike')->1,10
(r:Account WHERE r.owner='Scott')

In the example graph,
is a solution to this query, and in fact it is a shortest
solution in the partition defined by the endpoints
(a5,a1). However, it repeats the edge t8, so it fails
the restrictor TRAIL (as well as
SIMPLE and ACYCLIC. Thus adding a selector
such as ALL SHORTEST will still have a result, whereas
adding a restrictor such as TRAIL will have no result.

Keyword     Description

TRAIL     No repeated edges.

ACYCLIC     No repeated nodes.

SIMPLE     No repeated nodes, except that the first and last nodes may be the same.

Table of restrictors

Keyword     Description

ANY SHORTEST     Selects one path with shortest length from each partition.

ALL SHORTEST     Selects all paths in each partition that have the minimal length in the partition. Deterministic.

ANY     Selects one path in each partition arbitrarily.

ANY $k$     Selects arbitrary $k$ paths in each partition (if fewer than $k$, then all are retained).

SHORTEST $k$      Selects the shortest $k$ paths (if fewer than $k$, then all are retained).

SHORTEST $k$ GROUP
Partitions by endpoints, sorts each partition by path length, groups paths with the same length, then selects all paths in the first $k$ groups from each partition
(if fewer than $k$, then all are retained). Deterministic.

Table of selectors

§.§ Prefilters and Postfilters of Selectors

When working with selectors, it is important to
differentiate prefilters from postfilters.
A prefilter is a predicate applied before selection;
a postfilter is a predicate applied after selection.
In GPML, postfilters are expressed in the final WHERE
clause, whereas prefilters are expressed in element
patterns or parenthesized path patterns within the
selector's path pattern.

For example, suppose we want to find the shortest path
from Scott to Charles passing through an account that is

MATCH ALL SHORTEST (p:Account WHERE p.owner='Scott')->+
(q:Account WHERE q.isBlocked='yes')->+
(r:Account WHERE r.owner='Charles')

Note that all predicates in this example
are expressed
in element patterns, therefore they are all prefilters.
The only solution is the $\pathvalue{a1,t1,a3,t2,a2,t3,a4,
t4,a6,t5,a3,t7,a5}$, in which q is bound to a4 (Jay,
the only blocked account).

It would be a mistake to place the predicate on q in the final WHERE clause, like this:

MATCH ALL SHORTEST (p:Account WHERE p.owner='Scott')->+
(r:Account WHERE r.owner='Charles')
WHERE q.isblocked='yes'

The shortest
path from Scott to Charles is $\pathvalue{a1,t1,a3,t7,a5}$
with q bound to a3,
which will be the result of the selector, but this
result is then filtered out by the final WHERE clause
because a3 is not blocked. Consequently this
query finds no result. The original problem statement
had the predicate
“passing through an Account that is blocked”
as a prefilter, therefore the query placing it
as a postfilter is incorrect.

§.§ Independence of Selectors

As mentioned, a selector can only be expressed at the
head of a path pattern. If a graph pattern contains
two or more selectors, they must be in separate
path patterns. GPML requires that multiple selectors
in the same graph pattern must be independent.

Independence of selectors is defined as follows. An
unconditional singleton node variable that is the first or
the last element pattern in a selector is called a
boundary variable. All other element variables
declared within a selector are called
strict interior variables.

Note that the selectors are defined by partitioning
the solution space on the bindings to the boundary
variables. This means that the bindings to the strict
interior variables depend on the bindings to the
boundary variables. Independence of selectors means that
one selector may not reference or form an implicit
equijoin to a strict interior variable of another
selector. This consideration gives the following rules for
independence of selectors:

* A strict interior variable of one selector may not be equivalent to either a boundary variable or strict
interior variable of another selector.

* A predicate in one selector may not reference
a strict interior variable of another selector.

§.§ Aggregates of Unbounded Variables

There is another subtle way of having non-terminating queries that must be ruled out by GPML. Consider this query:

MATCH ALL SHORTEST [ (x)-[e]->*(y) WHERE COUNT(e.*)/(COUNT(e.*)+1)>1 ]

Note carefully that the predicate is within a parenthesized
path pattern, therefore it is a prefilter. As a prefilter,
the group variable e has not yet passed through the
selector ALL SHORTEST; consequently the
predicate sees e as effectively unbounded.

If a match has 0 edges, the quotient in the WHERE clause
is 0; if it has 1 edge, the quotient is 1/2; if it has
2 edges, the quotient is 2/3; etc. The quotient can
never exceed 1. This is easily seen by human reason,
but generalizing this observation to any aggregate on
an unbounded element reference is not obvious.
For example, suppose the aggregate were AVG(e.x);
the behavior of AVG on an unbounded collection of
property references is not easy to anticipate.
A few aggregates (MAX, MIN, COUNT) are monotonic,
which might permit reasoning on simple expressions
such as linear combinations, but it is currently
expected that GPML will simply prohibit all predicates
on unbounded groups to ensure termination.

The query can be made acceptable – i.e., turned into a terminating one – in several ways.
First, the predicate might be converted to a postfilter,
like this:

MATCH ALL SHORTEST (x)-[e]->*(y)
WHERE COUNT(e.*)/(COUNT(e.*)+1) > 1

Note that all we did was remove the square brackets,
which moved the predicate out of the path pattern and
into the final WHERE clause. This made e
effectively bounded. Of course any results produced by the selector will
be filtered out by the postfilter; therefore the result
of this query is empty. However, turining the predicate into a postfilter and using a selector first ensures the finiteness of the result, and thus termination.

A different approach is to retain the prefilter
but insure that eis effectively bounded
within the selector. Certainly changing the quantifier
to have a static upper bound such as {0,10} would do.
Alternatively a restrictor could be used, like this:

MATCH ALL SHORTEST [ TRAIL (x)-[e]->*(y) WHERE COUNT(e.*)/(COUNT(e.*)+1) > 1 ]

Reasoning about this pattern we can see that the result will be
empty. An implementation is of course free to
implement algorithms that detect some queries that are
unsatisfiable and thereby terminate quickly.
Alternatively, the implementation could actually
tackle the query as written and eventually arrive
at the conclusion that the result set is empty.

§ EXECUTION MODEL BY EXAMPLE

We illustrate GPML evaluation using a step-by-step example. The output of the example query is a set, or a multiset, of reduced path bindings. A path binding is a sequence of elementary bindings, which in turn are pairs of a variable and a graph element.

A variable is either a variable that occurs in the pattern, or a new variable corresponding to an anonymous node or edge.
Each variable, anonymous or not, can be further indexed if it appears under the scope of a quantifier: the index indicates the iteration in which it appears. For the same variable a under the scope of a quantifier  we can have variables $\gqltext{a}^1,\gqltext{a}^2,\gqltext{a}^3,\ldots$ that correspond to different iterations of the quantifier.
Obtained path bindings are then reduced, stripping all annotations, and deduplicated, to remove duplicates. If multiple path patterns appear after MATCH, the process is repeated for all of them, and the result is joined on identical singleton variables, and possibly further filtered if there is a WHERE clause. Selectors and restrictors are used to ensure that the output is finite in the presence of quantifiers.

The key steps in the pattern matching execution model, as reflected in the forthcoming standard, are as follows.

NormalizationGPML provides syntactic sugar to help write patterns; this step puts
patterns in a canonical form.

Expansion The pattern is expanded into a
set of rigid patterns without any kind of disjunction.
Intuitively, a rigid pattern is one that could be expressed by an SQL equi-join query.
Formally, it is a pattern without quantifiers, union or multiset alternation.

The expansion also annotates each rigid pattern to enable tracking the provenance of the syntax constructs.

Rigid-pattern matching  For each rigid pattern, one computes a set of path bindings.
Each elementary construct of the rigid pattern is computed independently and then the results are joined together on variables with the same name.

Reduction and deduplication  The path bindings matched by the rigid patterns are reduced by removing annotations. The reduced path bindings are then collected into a set.
This implies a deduplication step since different path bindings might become equal after reduction, and only one copy is kept.

§.§ Running Example

The remainder of this section gives a detailed account of how pattern matching is computed for the following query.

MATCH TRAIL (a WHERE a.owner='Jay')
[-[b:Transfer WHERE b.amount>5M]->]+
(a) [-[:isLocatedIn]->(c:City) |

This query finds sequences of transfers of arbitrary length that start and end with account owner Jay, as well as the location (city or country) of Jay. To ensure termination, the TRAIL mode is used.

§.§ Normalisation

The first step of normalisation makes each sequence of
node and edge patterns consistent.
More precisely, each such sequence must start and end with a node pattern; and alternate between node and edge patterns.
In addition, syntactic sugar is expanded, e.g., quantifier  is replaced by .
Hence, the pattern becomes:

(a WHERE a.owner='Jay')
[()-[b:Transfer WHERE b.amount>5M ]->()]1,
(a) [()-[:isLocatedIn]->(c:City) |

We then introduce a fresh variable into each anonymous node and edge pattern (that is, a pattern that is not assigned to a variable).
The fresh node and edge variables are denoted by $\rvarnode{x}$
and $\rvaredge{x}$, respectively, for some index $x$. The pattern then becomes

(a WHERE a.owner='Jay')
[($\varnode{1}$)-[b:Transfer WHERE b.amount>5M]->($\varnode{2}$)]1,
(a)[[($\varnode{3}$)-[$\varedge{1}$:isLocatedIn]->(c:City)] |

§.§ Expansion

Expansion turns the pattern into a set of rigid patterns, which fix the
number of iterations for each quantifier and a disjunct for each union or alternation.
In our query, this amounts to choosing a disjunct in the union |, and expanding the  quantifier !1,!.
While unbounded quantifiers such as !1,! make the set infinite,  techniques of Section <ref> will make the evaluation feasible.

The following pattern is one possible expansion, where we  expanded the quantifier once and chose the left side of the path pattern union:

(a WHERE a.owner='Jay')
($\varnode[1]{1}$)-[$\varb{1}$:Transfer WHERE $\varb{1}$.amount>5M]->($\varnode[1]{2}$)
(a) ($\varnode{3}$)-[$\varedge{1}$:isLocatedIn]->(c:City)

In general, one such pattern is obtained for
each $n\in\mathbb{N}\setminus\{0\}$
and each $\ell\in\{\gqltext{City},\gqltext{Country}\}$: we expand the quantifier $n$ times, and choose either the City or the Country option of the path pattern union. Such a
pattern is denoted by $\theta_{n,\ell}$. As an example, the pattern below is

(a WHERE a.owner='Jay')
($\varnode[1]{1}$)-[$\varb{1}$:Transfer WHERE $\varb{1}$.amount>5M]->($\varnode[1]{2}$)
($\varnode[2]{1}$)-[$\varb{2}$:Transfer WHERE $\varb{2}$.amount>5M]->($\varnode[2]{2}$)
$\raisebox{-0.5mm}{\smash{\vdots}}$              $\raisebox{-0.5mm}{\smash{\vdots}}$              $\raisebox{-0.5mm}{\smash{\vdots}}$
($\varnode[n]{1}$)-[$\varb{n}$:Transfer WHERE $\varb{n}$.amount>5M]->($\varnode[n]{2}$)
(a) ($\varnode{3}$)-[$\varedge{1}$:isLocatedIn]->(c:City)

The prototype $\theta_{n,\mathtt{Country}}$ is similar, only the last line changes.

Each group variable is marked by a superscript, corresponding to the iteration of the quantifier the variable is in.

The next step is a clean-up: every node pattern with an anonymous variable is deleted
if it is adjacent to another node pattern.
The resulting pattern is denoted by $\pi_{n,\ell}$.
For instance, $\pi_{n,\gqltext{City}}$ is:

(a WHERE a.owner='Jay')
-[$\varb{1}$:Transfer WHERE $\varb{1}$.amount>5M]->($\varnode[1]{2}$)
-[$\varb{2}$:Transfer WHERE $\varb{2}$.amount>5M]->($\varnode[2]{2}$)
$\raisebox{-0.5mm}{\smash{\vdots}}$              $\raisebox{-0.5mm}{\smash{\vdots}}$              $\raisebox{-0.5mm}{\smash{\vdots}}$
-[$\varb{n-1}$:Transfer WHERE $\varb{n-1}$.amount>5M]->($\varnode[n-1]{2}$)
-[$\varb{n}$:Transfer WHERE $\varb{n}$.amount>5M]->(a)

§.§ Computation of Path Binding

The matches of rigid patterns are computed independently.
The result of the computation is called a path binding,
which in turn is a sequence of elementary bindings. An
elementary binding is a pair of a variable and a graph element. It is convenient to portray these pairs as tables with two rows: the first row contains the variables, the second row contains the graph elements, and each column is an elementary binding.
An example path binding is

a     $\varb{1}$     $\varnode[1]{2}$

a4     t4     a6

Consider the rigid path pattern $\pi_{4,\gqltext{City}}$.
Each node-edge-node pattern is computed independently using the input graph,
and then equi-joined on variables with the same name.
The first node-edge-node part of $\pi_{4,\gqltext{City}}$ is

(a WHERE a.owner='Jay')-[$\varb{1}$:Transfer WHERE $\varb{1}$.amount>5M]->($\varnode[1]{2}$)

In the graph it matches only one path binding, the one shown above.  The second node-edge-node part is

($\varnode[1]{2}$)-[$\varb{2}$:Transfer WHERE $\varb{2}$.amount>5M]->($\varnode[2]{2}$)

and the path bindings it matches are given in the left column below. The path bindings matched by the third, fourth and fifth parts of $\pi_{4,\gqltext{City}}$ are given in the three other columns.

$\varnode[1]{2}$     $\varb{2}$     $\varnode[2]{2}$

$\varnode[2]{2}$     $\varb{2}$     $\varnode[3]{2}$

$\varnode[3]{2}$     $\varb{4}$     a

a     $\varedge{1}$     c

a6     t5     a3

a6     t5     a3

a6     t5     a3

a4     li4     c2

a3     t2     a2

a3     t2     a2

a3     t2     a2

a6     li6     c2

a2     t3     a4

a2     t3     a4

a2     t3     a4

a3     li3     c1

a2     t3     a4

a2     t3     a4

a2     t3     a4

a2     li2     c2

a3     t7     a5

a3     t7     a5

a3     t7     a5

a5     li5     c1

a5     t8     a1

a5     t8     a1

a5     t8     a1

a1     li1     c1

a1     t1     a3

a1     t1     a3

a1     t1     a3

Note that the matches for each part (i.e., each column above) is computed independently.

The labels are matched and the WHERE clauses are checked at this stage. Thus, the edge (a6,t6,a5) does not appear anywhere above as it fails the WHERE condition,  nor does the edge (ip1,sip1,a1) since it has neither the Transfer nor the isLocatedIn label.

Then the path bindings are concatenated by an implicit equi-join on variables with the same name. In the end there is only one path binding for $\pi_{4,\gqltext{City}}$ given below.

$\varb{1}$     $\varnode[1]{2}$
$\varb{2}$     $\varnode[2]{2}$
$\varb{3}$     $\varnode[3]{2}$
$\varb{4}$     a     $\varedge{1}$     c

a4     t4     a6     t5     a3     t2     a2     t3     a4     li4     c2

Note that variables with different subscript or superscript (e.g., $\varb{1}$ and $\varb{2}$) are not joined on.

Restrictors are also checked at this point. For example,  $\pi_{8,\gqltext{City}}$ has no match. Indeed, a path binding
computed by the above join would
use the loop (t4,t5,t2,t3) twice, and thus would not be a trail.

In the end, $\pi_{n,\ell}$ never has any matches unless $n=4$ (as presented above) or $n=7$.
The patterns $\pi_{4,\gqltext{City}}$, $\pi_{4,\gqltext{Country}}$, $\pi_{7,\gqltext{City}}$ and $\pi_{7,\gqltext{Country}}$ each have one match given below.

$\varb{1}$     $\varnode[1]{2}$
$\varb{2}$     $\varnode[2]{2}$
$\varb{3}$     $\varnode[3]{2}$
$\varb{4}$     a     $\varedge{1}$     c

a4     t4     a6     t5     a3     t2     a2     t3     a4     li4     c2

$\varb{1}$     $\varnode[1]{2}$
$\varb{2}$     $\varnode[2]{2}$
$\varb{3}$     $\varnode[3]{2}$
$\varb{4}$     a     $\varedge{2}$     c

a4     t4     a6     t5     a3     t2     a2     t3     a4     li4     c2

$\varb{1}$     $\varnode[1]{2}$
$\varb{2}$     $\varnode[2]{2}$
$\varb{3}$     $\varnode[3]{2}$
$\varb{4}$     $\varnode[4]{2}$
$\varb{5}$     $\varnode[5]{2}$
$\varb{6}$     $\varnode[6]{2}$
$\varb{7}$     a     $\varedge{1}$     c

a4     t4     a6     t5     a3     t7     a5     t8     a1     t1     a3     t2     a2     t3     a4     li4     c2

$\varb{1}$     $\varnode[1]{2}$
$\varb{2}$     $\varnode[2]{2}$
$\varb{3}$     $\varnode[3]{2}$
$\varb{4}$     $\varnode[4]{2}$
$\varb{5}$     $\varnode[5]{2}$
$\varb{6}$     $\varnode[6]{2}$
$\varb{7}$     a     $\varedge{2}$     c

a4     t4     a6     t5     a3     t7     a5     t8     a1     t1     a3     t2     a2     t3     a4     li4     c2

The latter two path bindings are trails, but are not acyclic, since the node a3 appears twice. Thus, they would
have been filtered out if we had used the restrictor ACYCLIC instead of TRAIL.

§.§ Reduction and Deduplication

Reduction of path bindings strips variables from their annotations (subscripts and superscripts). In particular, it
merges together all variables introduced in anonymous element patterns.
The result of reduction in our example is show below:

$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     a     $\rvaredge{}$     c

a4     t4     a6     t5     a3     t2     a2     t3     a4     li4     c2

$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     a     $\rvaredge{}$     c

a4     t4     a6     t5     a3     t2     a2     t3     a4     li4     c2

$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     a     $\rvaredge{}$     c

a4     t4     a6     t5     a3     t7     a5     t8     a1     t1     a3     t2     a2     t3     a4     li4     c2

$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     a     $\rvaredge{}$     c

a4     t4     a6     t5     a3     t7     a5     t8     a1     t1     a3     t2     a2     t3     a4     li4     c2

All reduced path bindings are then collected together in a set.
That is, at this point, deduplication occurs. If two different rigid patterns yield the same reduced path binding, then a single copy of the path binding is kept.
Thus, the final result has only two distinct reduced path bindings.

$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     a     $\rvaredge{}$     c

a4     t4     a6     t5     a3     t2     a2     t3     a4     li4     c2

$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     a     $\rvaredge{}$     c

a4     t4     a6     t5     a3     t7     a5     t8     a1     t1     a3     t2     a2     t3     a4     li4     c2

The consequence of this deduplication is that our running query is
equivalent to:

MATCH TRAIL
(a WHERE a.owner='Jay') [-[b:Transfer WHERE b.amount>5M]->]+

Hence, a user does can turn a disjunction in the label expression into a path pattern union.

Having finished this detailed example, we now look at
some other features of the pattern matching algorithm.

Using selectors
After deduplication, any selectors (if present) would be applied.
Assume that in our running example we replaced the restrictor TRAIL
with the selector ALL SHORTEST:

MATCH ALL SHORTEST
(a WHERE a.owner='Jay') [-[b:Transfer WHERE b.amount>5M]->]+
(a) [-[:isLocatedIn]->(c:City) | -[:isLocatedIn]->(c:Country)]

the number of reduced path bindings would be infinite (since Transfer loops may be taken arbitrarily many times without the trail restriction),
the selector would keep the shortest reduced binding path for each pair of endpoints (in our case,
a4 and c2), thus returning

$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     $\rvarnode[]{}$
$\varb{}$     a     $\rvaredge{}$     c

a4     t4     a6     t5     a3     t2     a2     t3     a4     li4     c2

Multiple patterns
When more than one pattern, separated by commas, appear after MATCH,
each path pattern is
solved separately,

resulting in
finitely many solutions to
each path pattern. At this point the cross product
of the sets of path bindings
is formed, and then filtered on the basis of
implicit equi-joins on the global singleton variables
and the final WHERE clause.

Path pattern union vs multiset alternation
The consequence of using deduplication is that our running query with path pattern union is
equivalent to a query where the last edge pattern is replaced by

To avoid deduplication and to maintain four reduced path bindings in the output, one could use multiset alternation instead, replacing the pattern by

(a) [-[:isLocatedIn]->(c:City) |+| -[:isLocatedIn]->(c:Country)]

§.§ Query Outputs

every state=[draw,rectangle,rounded corners,font=]

[state] (graph_pattern) at (-4,1)

Graph pattern

[state] (graph_db) at (-4,-1)

Graph DB

[state] (gpml_processor) at (-2,0)

GPML processor

[state] (mp_bindings) at (1.5,0)

[state] (pgq) at (3,1)

[state] (pgq_table) at (5,1)

[state] (gql) at (3,-1)

[state] (gql_table) at (5, 0)

[state] (graph_view) at (5,-1)

graph view

[state] (new_graph) at (5,-2)

new graph

(graph_pattern) edge[bend left] (gpml_processor)
(graph_db) edge[bend right] (gpml_processor)
(gpml_processor) edge[] (mp_bindings)
(mp_bindings) edge[bend left] (pgq)
(pgq) edge[] (pgq_table)
(mp_bindings) edge[bend right] (gql)
(gql) edge[bend left] (gql_table)
(gql) edge[] (graph_view)
(gql) edge[bend right] (new_graph)

Conceptual diagram of GPML, SQL/PGQ and GQL

How should the result of pattern matching be represented to produce the output of a query? We have seen that executing a GPML statement results in a set of path bindings. Presenting this to the user depends on the host language, SQL/PGQ or GQL.
Figure <ref> shows
the relationship between GPML and its two
host languages.

The GPML processor is a software component within
an implementation of either SQL/PGQ or GQL.  The two inputs to the GPML processor are the
graph pattern and the graph database.
The output of the GPML processor is
consumed by the host
to produce the final
output requested by the user. For SQL/PGQ, it will be a table, obtained from the computed reduced path bindings.

For GQL, the output could be more varied, including a
graph view, or new graph. Indeed, each path binding defines a subgraph of the input graph given by its nodes and edges, together with annotations, given by variables assigned to them in the path binding. This opens up more possibilities for structuring query outputs. While in the initial release of the GQL standard, outputs will be in line with those of SQL/PGQ, it is anticipated that in the future more advanced options will be added.

§.§ Comma-Separated List of Path Patterns

When there is more than one path pattern, they are
solved separately, including the evaluation of
selectors, if any. Note that after evaluation of
selectors, there are finitely many solutions to
each path pattern. At this point the cross product
of the sets of path bindings
is formed, and then filtered on the basis of
implicit equijoins on the global singleton variables
and the final WHERE clause.

§ LOOKING FORWARD

In this section we outline the ongoing work on the development of the SQL/PGQ and GQL standards and list several research problems that have arisen in the process of designing the GPML.

§.§ Standards Process: Steps and Timing

The SQL/PGQ and GQL standards are being developed in the international standards committee ISO/IEC JTC1 SC32 WG3 "Database Languages"
with input from various national bodies. In particular, the US  committee INCITS DM32 "Data Management and Interchange" and DM32's SQL/PGQ and GQL expert groups review all significant US change proposals before they are considered by WG3.

The ISO/IEC JTC1 process has a number of steps with ballots to transition between the stages. The high-level overview is:

* Initial effort – develop and expand the draft;

* Committee Draft (CD) Ballot – 12 weeks;

* Draft International Standard (DIS) Ballot – 20 weeks;

* International Standard (IS) published.

After each ballot, time is needed to resolve the comments submitted.

The current schedule for the progression of the SQL/PGQ and GQL standards is shown in Figure <ref>.[The schedule depends on work that has not been completed and so could change.] By the time the DIS ballot starts, the technical specification is fairly stable.
Since GPML is the same for GQL and SQL/PGQ, GQL GPML will be fairly stable when SQL/PGQ begins DIS ballot.

Date     SQL/PGQ     GQL

2017     Work started

2018         Work started

2021-02-07     CD Ballot End

2022-02-20          CD Ballot End

2022-12-04     DIS Ballot End

2023-01-30     Final Text to ISO

2023-03-13     SQL/PGQ IS Published

2023-05-21         DIS Ballot End

2023-07-30         Final Text to ISO

2023-09-10         GQL IS Published

SQL/PGQ and GQL Timeline

As SC32 WG3 makes progress on the drafts, it accumulates Language Opportunities (LOs). LOs are capabilities that are potentially useful, but are not yet ready for the current versions of the draft standards. Below we provide a sample of LOs pertaining to GPML:

* Constraining a graph pattern through the introduction of isomorphic match modes: for example, an edge-isomorphic match requires all edges matched across all constituent path patterns in the graph pattern to differ from each other.

* Queries on multiple graphs in a single concatenated MATCH.

Path macros for multiple use in a query.

* Outputting the interleaving of bindings in nested quantifiers, such as ![[(p)->(q)]* ->(r)]*!.

* Cheapest path search, by adding weights to edges.

* Exporting a graph element or path binding to JSON.

GQL also has LOs that go beyond those common with SQL/PGQ. Examples
include property graph keys and constraints <cit.>,
system versioned graphs,

and stored queries, procedures, and functions.
As discussed in Section <ref>, formats such as JSON could potentially be used for
returning a raw multi-path binding.

§.§ Research Questions

There are many open questions related to GPML. Given the novelty of the language, and its goal as the future standard of querying property graphs, it is important to full understand the expressiveness and  complexity of its various fragments, in the spirit of many decades of research tradition in database query languages <cit.>.

Some of the most intriguing questions concern processing unbounded paths. For instance, the innocently looking query below may not terminate.

MATCH (x)-[e]->*(y)
WHERE AVG(e.a)<1
KEEP ANY SHORTEST

With a sufficiently rich pattern language, termination will become an undecidable problem. A natural question is then whether there are interesting classes of predicates on aggregates of group variables for which termination can be guaranteed, or efficiently checked at compile time.

There are many questions related to the implementation of GPML. How does one solve efficiently shortest path queries with arbitrary regular expressions, not just ->* as in Dijkstra's  algorithm? Can we handle more complex optimization problems, such as maximizing an objective function subject to an upper bound on the length or cost of the path (e.g., “What is the most scenic route to the airport in at most 2 hours?”).

Another direction is to consider fully recursive graph patterns, permitting multiple self-references, not just a single one like in the * operator. Such patterns might be used to search for trees and other structures more complex than paths. Is there intuitive syntax to express such patterns? What real-world problems might they address? What is the cost of adding them to GPML?

Yet another line of future works concerns extended capabilities and different uses of graph patterns. One of them concerns extending the language to capture the temporal aspect of data <cit.>. A different line of work is to understand the underpinnings of languages defined by paths in property graphs, which are more than traditional regular languages over a finite alphabet, as they include property values coming from potentially infinite domains. Simple models for this based on data words <cit.> have already been studied in <cit.>, but they disregarded operations on data, such as arithmetic or string operations.  In an opposite direction, we may look at restrictions that will be useful in different applications, such as for example updating property graphs, which tends to be problematic <cit.> with a full power of pattern matching.

* Are there interesting classes of predicates on aggregates of effectively unbounded variables for which there are algorithms which assuredly terminate?

* Can the EXISTS predicate be treated as a way of effectively bounding its variables, similar to the way restrictors and selectors provide effective bounds.

* What are efficient algorithms to solve shortest path queries on arbitrary regular expressions (not just ->* as in Dijkstra's famous algorithm)? What can we say about their computational complexity in the worst case and in the typical case?

* Are there other interesting optimization problems besides shortest or cheapest path? One candidate is to maximize an objective function subject to an upper bound on length or cost of a path (e.g., what is the most scenic route to the airport in at most 2 hours?)

* Are there analogs of selectors that can operate on multi-path patterns and are not reducible to selectors on single paths?

* Characterize the computational complexity of various categories of queries expressible in the proposed language.

* Is there a set of principles, similar to Codd's definition of a relational database, for a graphical database? To what extent does the proposed language meet, exceed or fall short of such principles?

* What enhancements to pattern matching algorithms are required to support predicates on non-local singletons? What is the cost in additional computational complexity compared to algorithms that support only local predicates? Can these can be supported in ways that are easily understood by the users?

* Recursive path patterns (i.e., self-referential, permitting a match to a pattern to nest within another match to the same pattern; not merely iterative as in Kleene star) might be used to search for trees and other more complex structures than paths. Is there intuitive syntax to express such patterns? What real-world problems might such patterns address? What is the cost to adding such patterns to GPL?

§ RELATED WORK

GPML is the culmination of a long evolution of graph query languages, including contributions in research, standards and practice, too rich to survey comprehensively here.
We  discuss related work only in broad strokes and refer the reader to existing surveys <cit.>.

GPML's graph patterns extend the celebrated language of Conjunctive Regular Path Queries (CRPQ) introduced in <cit.> and studied in a plethora of follow-up work (e.g. <cit.>).
CRPQs consist of variables (typically binding only to individual vertices and edges), path patterns specified by regular expressions over the edge labels, and comma-separated lists thereof.
In their first incarnation, CRPQs operated over property-less graphs, but subsequent work considered graphs with data annotations (e.g. <cit.>), which are ancestors of today's property graphs.
Notable early graph query languages derived from CRPQs include G <cit.>, StruQL <cit.>,
Lorel <cit.> and WebSQL <cit.>.
Syntactically, GPML graph patterns extend CRPQs by introducing group variables and variables binding to entire paths.
The latter allows GPML to treat paths as first-class citizens, as advocated in the G-CORE proposal <cit.>.
Semantically, graph patterns extend CRPQs by supporting a finer-grained notion of match, which permits binding variables to paths, using multiplicity-sensitive aggregation such as sum, count, and average, and restricting the number of possible returned paths. These features are original contributions of GPML.

The simple path restrictor was already present in the first paper that introduced CRPQs <cit.>.

However, after it was discovered that the evaluation problem for (C)RPQs with simple path and trail restrictors has a high computational complexity <cit.>, they were put on hold by the research community. They were resurrected by practical query languages (e.g., Cypher <cit.> and early versions of SPARQL 1.1. <cit.>), which generated another wave of fundamental research <cit.> that sheds a clearer light on the relationship between queries that appear in real-life and the high complexity of simple paths and trails in the worst case.

GPML patterns share many features with pattern standards developed for different data models.
XML documents <cit.> correspond to tree-shaped, vertex-labeled graphs.
The XPath <cit.> World-Wide Web Consortium (W3C) standard describes patterns that roughly correspond to GPML path patterns that can be combined into tree-shaped structures; the use of variables is limited.

The XQuery <cit.> standard supports comma-separated lists of XPath patterns, stitched together with node variables.

Like in GPML, XQuery matches are discriminated by the path bindings they correspond to, but the limited use of quantifiers and the tree shape of the graph avoid the query non-termination problem.

Knowledge Graphs <cit.> corresponding to the RDF standard <cit.>, also admit pattern-based querying, for instance using the SPARQL W3C standard query language <cit.>.
Patterns consist once more of variables (binding to the RDF counterpart of nodes and edges) and regular path expressions. To deal with cycles, and potentially infinite number of matching paths <cit.>, SPARQL deploys the “endpoint semantics” of paths, and will only return start/end point of a path, instead of the matching path itself.

ACKNOWLEDGMENTS   The work of the FSWG is supported by grants from Neo4j held at the University of Edinburgh and ENS-Paris. The academic group also gratefully acknowledges support of the following research grants: EPSRC grants N023056 and S003800 (Libkin); DFG grants 369116833 and 431183758 (Martens); NCN grant 2018/30/E/ST6/00042 (Murlak); ANID – Millennium Science Initiative Program – Code ICN17_002 (Vrgoč).

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Abiteboul, Quass, McHugh, Widom, and
WienerAbiteboul et al1997]
authorpersonSerge Abiteboul, personDallan
Quass, personJason McHugh, personJennifer Widom,
and personJanet L. Wiener. year1997.
The Lorel Query Language for Semistructured Data.
journalInt. J. Digit. Libr. volume1,
number1 (year1997), pages68–88.

[Angles, Arenas, Barceló, Boncz, Fletcher,
Gutierrez, Lindaaker, Paradies, Plantikow, Sequeda, van Rest, and
VoigtAngles et al2018]
authorpersonRenzo Angles, personMarcelo
Arenas, personPablo Barceló, personPeter A.
Boncz, personGeorge H. L. Fletcher, personClaudio
Gutierrez, personTobias Lindaaker, personMarcus
Paradies, personStefan Plantikow, personJuan F.
Sequeda, personOskar van Rest, and personHannes
Voigt. year2018.
G-CORE: A Core for Future Graph Query
Languages. In booktitleSIGMOD.

[Angles, Arenas, Barceló, Hogan, Reutter,
and VrgocAngles et al2017]
authorpersonRenzo Angles, personMarcelo
Arenas, personPablo Barceló, personAidan
Hogan, personJuan L. Reutter, and personDomagoj
Vrgoc. year2017.
Foundations of Modern Query Languages for Graph
journalACM Comput. Surv. volume50,
number5 (year2017), pages68:1–68:40.

[Angles, Bonifati, Dumbrava, Fletcher, Hare,
Hidders, Lee, Li, Libkin, Martens, Murlak, Perryman, Savkovic, Schmidt,
Sequeda, Staworko, and TomaszukAngles et al2021]
authorpersonRenzo Angles, personAngela
Bonifati, personStefania Dumbrava, personGeorge
Fletcher, personKeith W. Hare, personJan Hidders,
personVictor E. Lee, personBei Li,
personLeonid Libkin, personWim Martens,
personFilip Murlak, personJosh Perryman,
personOgnjen Savkovic, personMichael Schmidt,
personJuan F. Sequeda, personSlawek Staworko, and
personDominik Tomaszuk. year2021.
PG-Keys: Keys for Property Graphs. In
booktitleSIGMOD '21: International Conference on
Management of Data. publisherACM,

[Arenas, Barceló, Libkin, Martens, and
PierisArenas et al2021]
authorpersonMarcelo Arenas, personPablo
Barceló, personLeonid Libkin, personWim Martens,
and personAndreas Pieris. year2021.
booktitlePrinciples of Databases.
publisherOpen source at

[Arenas, Conca, and PérezArenas
et al2012]
authorpersonMarcelo Arenas,
personSebastián Conca, and personJorge
Pérez. year2012.
Counting beyond a Yottabyte, or how SPARQL 1.1
property paths will prevent adoption of the standard. In
booktitleWorld Wide Web (WWW).

[Bagan, Bonifati, and GrozBagan
et al2013]
authorpersonGuillaume Bagan, personAngela
Bonifati, and personBenoît Groz.
A trichotomy for regular simple path queries on
graphs. In booktitleSymposium on Principles of Database
Systems (PODS), editorpersonRichard Hull and
personWenfei Fan (Eds.). publisherACM,

authorpersonPablo Barceló.
Querying graph databases. In
booktitlePrinciples of Database Systems (PODS).

[Barceló, Libkin, Lin, and
WoodBarceló et al2012]
authorpersonPablo Barceló,
personLeonid Libkin, personAnthony Widjaja Lin, and
personPeter T. Wood. year2012.
Expressive languages for path queries over
graph-structured data.
journalACM Trans. Database Syst.
volume37, number4 (year2012),

[Barceló, Libkin, and
ReutterBarceló et al2014]
authorpersonPablo Barceló,
personLeonid Libkin, and personJuan L. Reutter.
Querying regular graph patterns.
journalJournal of the ACM volume61,
number1 (year2014), pages8:1–8:54.

[Bojanczyk, David, Muscholl, Schwentick, and
SegoufinBojanczyk et al2011]
authorpersonMikolaj Bojanczyk, personClaire
David, personAnca Muscholl, personThomas Schwentick,
and personLuc Segoufin. year2011.
Two-variable logic on data words.
journalACM Trans. Comput. Log.
volume12, number4 (year2011),

authorpersonBéla Bollobás.
booktitleModern Graph Theory.
Vol. volume184.
publisherSpringer Science & Business Media.

[Bray, Paoli, Sperberg-McQueen, Maler, and
YergeauBray et al2008]
authorpersonTim Bray, personJean Paoli,
personC. M. Sperberg-McQueen, personEve Maler, and
personFrançois Yergeau. year2008.
titleExtensible Markup Language (XML) 1.0 (Fifth
howpublishedW3C Recommendation.

[Calvanese, De Giacomo, Lenzerini, and
VardiCalvanese et al2000]
authorpersonDiego Calvanese, personGiuseppe
De Giacomo, personMaurizio Lenzerini, and
personMoshe Y. Vardi. year2000.
Containment of Conjunctive Regular Path Queries
with Inverse. In booktitleKnowl. Representation &
Reasoning (KR). pages176–185.

[Calvanese, De Giacomo, Lenzerini, and
VardiCalvanese et al2003]
authorpersonDiego Calvanese, personGiuseppe
De Giacomo, personMaurizio Lenzerini, and
personMoshe Y. Vardi. year2003.
Reasoning on regular path queries.
journalSIGMOD Record volume32,
number4 (year2003), pages83–92.

[Calvanese, Giacomo, Lenzerini, and
VardiCalvanese et al1999]
authorpersonDiego Calvanese,
personGiuseppe De Giacomo, personMaurizio Lenzerini,
and personMoshe Y. Vardi. year1999.
Rewriting of Regular Expressions and Regular Path
Queries. In booktitleProceedings of the Eighteenth ACM
SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 31 -
June 2, 1999, Philadelphia, Pennsylvania, USA,
editorpersonVictor Vianu and
personChristos H. Papadimitriou (Eds.).
publisherACM Press, pages194–204.

[Cruz, Mendelzon, and WoodCruz
et al1987]
authorpersonIsabel F. Cruz, personAlberto O.
Mendelzon, and personPeter T. Wood.
A Graphical Query Language Supporting Recursion.
In booktitleProceedings of the Association for Computing
Machinery Special Interest Group on Management of Data 1987 Annual
Conference, San Francisco, CA, USA, May 27-29, 1987,
editorpersonUmeshwar Dayal and
personIrving L. Traiger (Eds.). publisherACM
Press, pages323–330.

[Cyganiak, Wood, and LanthalerCyganiak
et al2014]
authorpersonRichard Cyganiak, personDavid
Wood, and personMarkus Lanthaler.
titleRDF 1.1 Concepts and Abstract Syntax.
howpublishedW3C Recommendation.

[Deutsch, Xu, Wu, and LeeDeutsch
et al2019]
authorpersonAlin Deutsch, personYu Xu,
personMingxi Wu, and personVictor E. Lee.
TigerGraph: A Native MPP Graph Database.
journalCoRR  volumeabs/1901.08248.

[Deutsch, Xu, Wu, and LeeDeutsch
et al2020]
authorpersonAlin Deutsch, personYu Xu,
personMingxi Wu, and personVictor E. Lee.
Aggregation Support for Modern Graph Analytics in
TigerGraph. In booktitleProceedings of the 2020
International Conference on Management of Data, SIGMOD Conference 2020,
online conference [Portland, OR, USA], June 14-19, 2020,
editorpersonDavid Maier, personRachel
Pottinger, personAnHai Doan, personWang-Chiew Tan,
personAbdussalam Alawini, and personHung Q. Ngo
(Eds.). publisherACM, pages377–392.

[Fernandez, Florescu, Levy, and
SuciuFernandez et al1997]
authorpersonMary F. Fernandez, personDaniela
Florescu, personAlon Y. Levy, and personDan
Suciu. year1997.
A Query Language for a Web-Site Management System.
journalSIGMOD Rec. volume26,
number3 (year1997), pages4–11.

[Figueira, Godbole, Krishna, Martens, Niewerth,
and TrautnerFigueira et al2020]
authorpersonDiego Figueira, personAdwait
Godbole, personShankara Narayanan Krishna, personWim
Martens, personMatthias Niewerth, and personTina
Trautner. year2020.
Containment of Simple Conjunctive Regular Path
Queries. In booktitleInternational Conference on Principles
of Knowledge Representation and Reasoning (KR). pages371–380.

[Francis, Green, Guagliardo, Libkin, Lindaaker,
Marsault, Plantikow, Rydberg, Selmer, and TaylorFrancis
et al2018]
authorpersonNadime Francis, personAlastair
Green, personPaolo Guagliardo, personLeonid Libkin,
personTobias Lindaaker, personVictor Marsault,
personStefan Plantikow, personMats Rydberg,
personPetra Selmer, and personAndrés Taylor.
Cypher: An Evolving Query Language for Property
Graphs. In booktitleProceedings of the 2018 International
Conference on Management of Data. publisherAssociation for
Computing Machinery, addressNew York, NY, USA,

[Green, Guagliardo, and LibkinGreen
et al2021]
authorpersonAlastair Green, personPaolo
Guagliardo, and personLeonid Libkin.
booktitleProperty graphs and paths in GQL:
Mathematical definitions.
typeTechnical Reports TR-2021-01.
institutionLinked Data Benchmark Council (LDBC).

[Green, Guagliardo, Libkin, Lindaaker,
Marsault, Plantikow, Schuster, Selmer, and VoigtGreen
et al2019]
authorpersonAlastair Green, personPaolo
Guagliardo, personLeonid Libkin, personTobias
Lindaaker, personVictor Marsault, personStefan
Plantikow, personMartin Schuster, personPetra
Selmer, and personHannes Voigt.
Updating Graph Databases with Cypher.
journalProc. VLDB Endow. volume12,
number12 (year2019), pages2242–2253.

[HamiltonHamilton[n. d.]]
authorpersonWilliam L. Hamilton.
year[n. d.].
Graph Representation Learning.
journalSynthesis Lectures on Artificial Intelligence
and Machine Learning volume14, number3
(year[n. d.]), pages1–159.

[Harris and SeaborneHarris and
authorpersonSteve Harris and personAndy
Seaborne. year2013.
titleSPARQL 1.1 Query Language.
howpublishedW3C Recommendation.

[Hogan, Blomqvist, Cochez, d'Amato, de Melo,
Gutiérrez, Kirrane, Gayo, Navigli, Neumaier, Ngomo, Polleres, Rashid,
Rula, Schmelzeisen, Sequeda, Staab, and ZimmermannHogan
et al2021]
authorpersonAidan Hogan, personEva
Blomqvist, personMichael Cochez, personClaudia
d'Amato, personGerard de Melo, personClaudio
Gutiérrez, personSabrina Kirrane,
personJosé Emilio Labra Gayo, personRoberto
Navigli, personSebastian Neumaier,
personAxel-Cyrille Ngonga Ngomo, personAxel
Polleres, personSabbir M. Rashid, personAnisa Rula,
personLukas Schmelzeisen, personJuan F. Sequeda,
personSteffen Staab, and personAntoine Zimmermann.
Knowledge Graphs.
journalACM Comput. Surv. volume54,
number4 (year2021), pages71:1–71:37.

[Jumper, Evans, Pritzel, Green, Figurnov,
Ronneberger, Tunyasuvunakool, Bates, Žídek, Potapenko, Bridgland,
Meyer, Kohl, Ballard, Cowie, Romera-Paredes, Nikolov, Jain, Adler, Back,
Petersen, Reiman, Clancy, Zielinski, Steinegger, Pacholska, Berghammer,
Bodenstein, Silver, Vinyals, Senior, Kavukcuoglu, Kohli, and HassabisJumper
et al2021]
authorpersonJohn Jumper, personRichard
Evans, personAlexander Pritzel, personTim Green,
personMichael Figurnov, personOlaf Ronneberger,
personKathryn Tunyasuvunakool, personRuss Bates,
personAugustin Žídek, personAnna Potapenko,
personAlex Bridgland, personClemens Meyer,
personSimon A A Kohl, personAndrew J Ballard,
personAndrew Cowie, personBernardino Romera-Paredes,
personStanislav Nikolov, personRishub Jain,
personJonas Adler, personTrevor Back,
personStig Petersen, personDavid Reiman,
personEllen Clancy, personMichal Zielinski,
personMartin Steinegger, personMichalina Pacholska,
personTamas Berghammer, personSebastian Bodenstein,
personDavid Silver, personOriol Vinyals,
personAndrew W Senior, personKoray Kavukcuoglu,
personPushmeet Kohli, and personDemis Hassabis.
Highly accurate protein structure prediction with
journalNature volume596,
number7873 (dateAug. year2021),

authorpersonProperty Graph Query Language.
titlePGQL 1.4 Specification.

[Libkin, Martens, and VrgočLibkin
et al2016]
authorpersonLeonid Libkin, personWim
Martens, and personDomagoj Vrgoč.
Querying Graphs with Data.
journalJournal of the ACM volume63,
number2 (year2016), pages14:1–14:53.

[Losemann and MartensLosemann and
authorpersonKatja Losemann and personWim
Martens. year2013.
The complexity of regular expressions and property
paths in SPARQL.
journalACM Trans. Database Syst.
volume38, number4 (year2013),

[Ma and TangMa and Tang2021]
authorpersonYao Ma and personJiliang
Tang. year2021.
booktitleDeep Learning on Graphs.
publisherCambridge University Press.

[Martens, Niewerth, and TrautnerMartens
et al2020]
authorpersonWim Martens, personMatthias
Niewerth, and personTina Trautner.
A Trichotomy for Regular Trail Queries. In
booktitleInternational Symposium on Theoretical Aspects of
Computer Science (STACS) (seriesLIPIcs,
Vol. volume154). publisherSchloss Dagstuhl -
Leibniz-Zentrum für Informatik, pages7:1–7:16.

[Martens and TrautnerMartens and
authorpersonWim Martens and personTina
Trautner. year2018.
Evaluation and Enumeration Problems for Regular
Path Queries. In booktitleInternational Conference on
Database Theory (ICDT) (seriesLIPIcs,
Vol. volume98). publisherSchloss Dagstuhl -
Leibniz-Zentrum für Informatik, pages19:1–19:21.

[Mendelzon, Mihaila, and MiloMendelzon
et al1996]
authorpersonAlberto O. Mendelzon,
personGeorge A. Mihaila, and personTova Milo.
Querying the World Wide Web. In
booktitleProceedings of the Fourth International Conference
on Parallel and Distributed Information Systems, December 18-20, 1996, Miami
Beach, Florida, USA. publisherIEEE Computer Society,

[Mendelzon and WoodMendelzon and
authorpersonAlberto O. Mendelzon and
personPeter T. Wood. year1989.
Finding Regular Simple Paths in Graph Databases.
In booktitleProceedings of the Fifteenth International
Conference on Very Large Data Bases, August 22-25, 1989, Amsterdam, The
Netherlands. pages185–193.

[Mendelzon and WoodMendelzon and
authorpersonAlberto O. Mendelzon and
personPeter T. Wood. year1995.
Finding Regular Simple Paths in Graph Databases.
journalSIAM J. Comput. volume24,
number6 (year1995), pages1235–1258.

[Moffitt and StoyanovichMoffitt and
authorpersonVera Zaychik Moffitt and
personJulia Stoyanovich. year2017.
Temporal graph algebra. In
booktitleProceedings of The 16th International Symposium on
Database Programming Languages (DBPL),
editorpersonTiark Rompf and
personAlexander Alexandrov (Eds.). publisherACM,

titleCypher Query Language Reference, Version 9.

titleUsage of Cypher.

[Prud'hommeaux and SeabornePrud'hommeaux and
authorpersonEric Prud'hommeaux and
personAndy Seaborne. year2008.
titleSPARQL Query Language for RDF.
howpublishedW3C Recommendation.

[Robie, Dyck, and SpiegelRobie
et al2017a]
authorpersonJonathan Robie, personMichael
Dyck, and personJosh Spiegel.
titleXML Path Language (XPath) 3.1.
howpublishedW3C Recommendation.

[Robie, Dyck, and SpiegelRobie
et al2017b]
authorpersonJonathan Robie, personMichael
Dyck, and personJosh Spiegel.
titleXQuery 3.1: An XML Query Language.
howpublishedW3C Recommendation.

[Rost, Gómez, Fritzsche, Thor, and
RahmRost et al2021]
authorpersonChristopher Rost, personKevin
Gómez, personPhilip Fritzsche, personAndreas
Thor, and personErhard Rahm. year2021.
Exploration and Analysis of Temporal Property
Graphs. In booktitleProceedings of the 24th International
Conference on Extending Database Technology (EDBT),
editorpersonYannis Velegrakis,
personDemetris Zeinalipour-Yazti, personPanos K.
Chrysanthis, and personFrancesco Guerra (Eds.).
publisherOpenProceedings.org, pages682–685.

[Sakr, Bonifati, Voigt, Iosup, Ammar, Angles,
Aref, Arenas, Besta, Boncz, Daudjee, Valle, Dumbrava, Hartig, Haslhofer,
Hegeman, Hidders, Hose, Iamnitchi, Kalavri, Kapp, Martens, Özsu,
Peukert, Plantikow, Ragab, Ripeanu, Salihoglu, Schulz, Selmer, Sequeda,
Shinavier, Szárnyas, Tommasini, Tumeo, Uta, Varbanescu, Wu, Yakovets,
Yan, and YonekiSakr et al2021]
authorpersonSherif Sakr, personAngela
Bonifati, personHannes Voigt, personAlexandru Iosup,
personKhaled Ammar, personRenzo Angles,
personWalid G. Aref, personMarcelo Arenas,
personMaciej Besta, personPeter A. Boncz,
personKhuzaima Daudjee, personEmanuele Della Valle,
personStefania Dumbrava, personOlaf Hartig,
personBernhard Haslhofer, personTim Hegeman,
personJan Hidders, personKatja Hose,
personAdriana Iamnitchi, personVasiliki Kalavri,
personHugo Kapp, personWim Martens,
personM. Tamer Özsu, personEric Peukert,
personStefan Plantikow, personMohamed Ragab,
personMatei Ripeanu, personSemih Salihoglu,
personChristian Schulz, personPetra Selmer,
personJuan F. Sequeda, personJoshua Shinavier,
personGábor Szárnyas, personRiccardo
Tommasini, personAntonino Tumeo, personAlexandru
Uta, personAna Lucia Varbanescu, personHsiang-Yun
Wu, personNikolay Yakovets, personDa Yan, and
personEiko Yoneki. year2021.
The future is big graphs: a community view on graph
processing systems.
journalCommun. ACM volume64,
number9 (year2021), pages62–71.

authorpersonTigerGraph Team.
titleTigerGraph Documentation – version 3.1.

[van Rest, Hong, Kim, Meng, and Chafivan Rest
et al2016]
authorpersonOskar van Rest, personSungpack
Hong, personJinha Kim, personXuming Meng, and
personHassan Chafi. year2016.
PGQL: a property graph query language. In
booktitleProceedings of the Fourth International Workshop on
Graph Data Management Experiences and Systems. pages1–6.

authorpersonPeter T. Wood.
Query languages for graph databases.
journalSIGMOD Record volume41,
number1 (year2012), pages50–60.