Graph Query

Graph pattern matching is added to the PartiQL grammar as a new production for the non-terminal <expr_query> (which defines constructs like scalar, struct, and collection literals; function calls; parenthesized SELECT-FROM-WHERE, etc.):

where <graph_pattern>, as well as the non-terminals on which it depends, are defined as in GPML (see the following section).

After this, the match expression becomes available, as an <expr_query>, to be used as a source in the FROM clause of SELECT-FROM-WHERE queries, which is defined in PartiQL as

Note that there are mandatory parentheses ( …​ ) around the MATCH expression. These are necessary for parsing FROM clauses with one-token lookahead. Otherwise, there could be uses of , in a FROM clause for which it would be impossible to decide whether they separate instances of <path_pattern> or instances of <from_item>.

However, the parenthesation restriction can be relaxed in a FROM clause when its pattern consists of a single path pattern. For this, we add an extra production to <from_item>:

The grammar in this section is a reverse-engineered reconstruction based on the examples in ^[1]. It is followed in the current experimental implementation of graph query parsing in partiql-lang-kotlin, starting in 0.8.0.
This grammar is subject to change, taking into account any details that might appear in SQL/PGQ but were not covered in ^[1]. It also does not cover several features mentioned in the paper in passing only (label patterns, predicates for node/edge relationships).

To clarify how graph pattern and the "host" PartiQL grammars are combined, PartiQL non-terminals are indicated with double angle brackets, specifically [integer], [identifier], and [where_clause].

It is worthy of a note that [where_clause], referenced in the above grammar in node, edge, and group patterns, is, syntactically, the WHERE clause of host PartiQL, where it is defined as

where the expression <expr_query> is meant to evaluate to a boolean. This expession, however, can contain, as references, variables introduced as <node_variable>, <edge_variable>, or <path_variable> elsewhere in the pattern, as well as graph-specific predicates and functions applied to these references.

The details of graph pattern matching semantics are available in ^[1] (Section 6). For the purposes of this RFC, it is sufficient to describe the structure of a pattern-matching result.

Suppose we have a GPML graph pattern of the form

where P_i are path patterns. (We abstract away from the possibility that a <graph_pattern> can start with a selector, since that does not affect the structure of the result.) The path patterns can contain variables marking node, edge, or path subpatterns. The variables that occur in the scope of a quantifier (such as +, *, {2,7}, or {2,}) are group variables, while the remaining ones are singleton variables.

The intent of pattern matching is to find all (possibly overlapping) fragments of the graph, each of which is described by the pattern P₁ , …​ , P_n, and associate the pattern’s variables with elements of the graph from the fragment. In a given match result (fragment), a singleton variable gets associated to one graph element, while a group variable can get associated to none or several elements — one for each repetition of the containing quantified subpattern.
A singleton variable x for a node or an edge can occur in more than one path pattern P_i, in which case it is meant to be bound, in a given result, to the same node or edge across all path patterns. For the sanity of this semantics, it follows that this is not allowed for group variables.

Inferring from ^[1] (Section 6), the result of evaluating a GPML pattern on a graph can be characterized as a bag of matching graph fragments, each being an ordered tuple of the form

with each p_i being an annotated path from the graph corresponding to the path pattern P_i. In turn, an annotated path p_i is a path from the graph (a sequence of alternating nodes and edges) that is annotated with variables from the corresponding path pattern P_i. Among these annotations,

It is important to note that the variables are annotated to entities in the graph (nodes, edges, paths) that are "aware" of their identity and location within the graph. This capability is essential within the pattern matching process, to determine sameness of nodes and edges when they are probed for being annotated with the same (singleton) pattern variable.

Example. In its Section 6, the GPML paper^[1] works though pattern match computation of an example query pattern

that is evaluated against the graph from Section 2 of the paper. This pattern has singleton node variables a and c and a group edge variable b. This is also a valid PartiQL graph pattern as proposed here, provided its input graph uses structs as payloads at node and edges, to model property graphs. (Making subexpressions a.owner and 'b.amount` valid.)

The final result of this pattern matching, given in Subsection 6.5 of the paper, is a bag with two graph fragments, each consisting of one annotated path (because the pattern consists of only one path pattern):

where, for each of the two fragments, the second row is a sequence of internal identifiers for the nodes and edges in the graph and the first row are the pattern-variable annotations.

In the context of this RFC, the notion of a PartiQL value has been extended, according to RFC-0025, to include graph values, while the notion of an expression is being extended in this RFC by adding graph matching expressions. Furthermore, a graph matching expression can contain PartiQL expressions, notably within the filtering WHERE clauses.

A PartiQL expression is evaluated in an environment that maps variables to PartiQL values, with the result of an evaluation being a PartiQL value.
The above-outlined evaluation semantics of graph pattern matching in GPML is structured differently (for one, it produces a bag of tuples of annotated paths) and operates over values of a kind that are not part of PartiQL data model, even after the RFC-0025 extension (such as nodes and edges that have awareness of their identity and location within a graph). In a sense, graph matching is a distinct query language of its own, embedded within PartiQL as a MATCH expression form.

Consequently, our goal here is to describe how the two semantics are combined, specifically addressing:

For evaluating a graph matching expression

this RFC proposes the following.

This semantics naturally supports the important property lookup use case from GPML^[1] on property graphs. That is, evaluating an expression of the form v*.a* where v is a node or an edge and a is a property name:

Example. Continuing the example from the previous section, the result of the PartiQL match expression is a bag of two structs containing attributes named as pattern variables and carrying values drawn from payloads of the matched nodes and edges:

A path subpattern in a graph pattern can be marked with a TRAIL or ACYCLIC restrictor (also SIMPLE) that restricts the result bag of otherwise-matching paths to those that additionally do not repeat an edge (for TRAIL) or do not repeat a node (for ACYCLIC).

It is conceivable to have similar restrictors that apply to the whole graph pattern, but it appears this is not the design in GPML and SQL/PGQ.
Instead, PartiQL defines this as an implementation-dependent behavior. That is, dependent on an application’s choice, the bag of annotated graph fragments computed as matches for any graph pattern is allowed to contain only certain fragments:

Note that these modes, when enabled, can render relevant path restrictors (TRAIL, ACYCLIC, SIMPLE) unnecessary.

The pattern grammar proposed in this RFC supports a variant of WHERE clause within node, edge, and path (grouping) patterns. In a few places, ^[1] also mentions WHERE clause that is not a part of any node, edge, or path fragment of a pattern, but rather applies to the entirety of the pattern in a graph MATCH expression. This WHERE is sometimes referred to as a "postfilter" of a pattern. From the limited discussion in the paper and the lack of examples on the matter, it is not fully clear whether such WHERE is meant to be the WHERE of the "host" select-from-where query (in SQL or PartiQL) or it is a new kind of WHERE that is coupled with MATCH.

In the case of the latter, the syntax of graph match expression would have to accommodate this possibility with a grammar production like

Currently, this is not being proposed for the reasons of economy of design — until and unless it becomes certain that the "host" WHERE cannot support necessary use cases.

GPML^[1] supports several graphical predicates, such as e IS DIRECTED, n IS SOURCE OF e, n IS DESTINATION OF e, SAME(`v1,` v2`,` …​), ALL_DIFFERENT(`v1,` v2`,` …​), which can be used in WHERE filters associated with nodes, edges, and paths (groupings), as well as, presumably, in the post-filter WHERE associated with the overall pattern (see the previous section).

Evaluation of these predicates, naturally, requires that nodes n and edges e to which they are applied are entities that are "aware" of their location within a graph G to which they belong.
In particular, the values n and e cannot be merely the payloads taken from nodes and edges of G.

Since the semantics proposed in this RFC equates graph elements with their payloads for all purposes except the internal mechanics of pattern matching computation, this RFC does not specify support for the graphical predicates.

Properly supporting them would require modeling values of nodes and edges as something like in-graph references of the form (id, G) or similar and, if we are to support property lookups v*.a* as naturally as possible so far, introducing rules on when an in-graph reference is treated as itself vs. when it is reduced to its payload.

Then, an important question would be whether these in-graph references were to become first-class values in PartiQL or be limited to the scope of MATCH expressions.

While GPML patterns support path variables, which bind to graph paths within graph fragments that constitute the result of a pattern match, this RFC does not specify how to represent these path bindings in the final result of a PartiQL MATCH expression. This is obvious from the explicit exclusions in two places in the evaluation semantics where paths are encountered.

While representing a singleton variable bound to a node or an edge as the latter’s payload fairly naturally translates to representing a group variable as a sequence of payloads for the nodes or edges that the variable annotates, settling on a natural way to extend this approach to path variables is not straightforward.

In the first approximation, the MATCH-result residual of a graph path bound to a path variable should probably be a list composed of payloads of certain nodes and edges on the path. However, clarifying details of this idea leads to questions such as

While it could be possible to cobble together a "reasonable" solution based on some choices from the above, the choices would be essentially arbitrary. At the same time, this design challenge is likely to be addressed in SQL/PGQ, so it would be fitting for the PartiQL solution to be consistent.