Anonymous node and edge patterns

[Dtenwolde]

What happens?

Currently, all patterns must bind to a label so they can be bound to a table. The PGQ specification does allow for anonymous node or edge patterns, for example:

• MATCH (n1:n)-[]->(n2:n) -- anonymous edge pattern.
• MATCH ()-[e1:e]->(n2:n) -- anonymous node pattern.
• MATCH (n1:n)->(n2:n) -- anonymous edge pattern.
• MATCH ()->() -- This will be collapsed into a single anonymous vertex pattern:

  i) If there are two adjacent anonymous vertex bindings, then the second is removed.

• MATCH (n1:n)->() -- The anonymous vertex pattern will be removed

  ii) If there is a binding of a vertex variable adjacent to an anonymous vertex binding, then
  the anonymous vertex binding is removed.

Unclear:

• MATCH (n1:n)-[]->(n2:n), (n1:n-[]->(n2:n) -- Would the two separate anonymous edge patterns bind to the same variable binding or would these be two separate bindings? The specification defines the following:

  NOTE 88 — Anonymous symbols are not s; there is no requirement that two anonymous
  symbols bind to the same graph element.

Queries containing anonymous patterns will currently lead to an error: Constraint Error: All patterns must bind to a label. We enforce that every pattern must bind to a single table and will not deviate from this since we use rowids for path-finding.

There are cases where we can deduce the label of the anonymous pattern. Given the following schema:

CREATE TABLE nodes (id INTEGER); INSERT INTO nodes VALUES (1), (2), (3);
CREATE TABLE edges (src INTEGER, dst INTEGER);

-CREATE PROPERTY GRAPH testgraph
  	VERTEX TABLES (
	    nodes LABEL N
	)
	EDGE TABLES (
  	    edges SOURCE KEY (src) REFERENCES nodes (id)
        	  DESTINATION KEY (dst) REFERENCES nodes (id)
  		  LABEL E
);

Only a single edge pattern can be in the anonymous edge pattern having the same source and destination node, namely E. If multiple labels can be used as the anonymous pattern we will throw an error stating it is ambiguous which one to choose.

During the binding phase, after resolving the label, these anonymous patterns can be given a variable binding such as unnamed_pattern (appending a number whenever there are multiple within a query). This is similar to unnamed_graphtable or unnamed_subquery.

To Reproduce

CREATE TABLE nodes (id INTEGER); INSERT INTO nodes VALUES (1), (2), (3);
CREATE TABLE edges (src INTEGER, dst INTEGER);

-CREATE PROPERTY GRAPH testgraph
  	VERTEX TABLES (
	    nodes LABEL N
	)
	EDGE TABLES (
  	    edges SOURCE KEY (src) REFERENCES nodes (id)
        	  DESTINATION KEY (dst) REFERENCES nodes (id)
  		  LABEL E
);

-FROM GRAPH_TABLE (testgraph MATCH ANY SHORTEST (n1:N)->(n2:N));

OS:

macOs 13 - Apple M1 Pro

DuckDB Version:

v1.1.3

DuckDB Client:

CLI

Full Name:

Daniel ten Wolde

Affiliation:

CWI

How did you load the extension?

Community extension version

Did you include all relevant data sets for reproducing the issue?

Yes

Did you include all code required to reproduce the issue?

• Yes, I have

Did you include all relevant configuration (e.g., CPU architecture, Python version, Linux distribution) to reproduce the issue?

• Yes, I have

[Dtenwolde]

The first implementation could start by omitting the variable. In that case, we would allow patterns such as:
(:N)-[e:E]->(n2:N) <- This is valid because we can allow the first one to get the name of the label (n). (:N)-[e:E]->(:N)<- Without variables (in this case:(:N)) should either: (i) lead to a constraint error saying that it is ambigious or (ii) be given an alias such as n_1, n_2. I prefer (i) because this is more in line with DuckDB's behaviour -> select * from n, nleads to an error for instance.(:N)-[n:E]->(n2:N)<- This won't be valid because again we get ambigious variable names. The first vertex pattern will be given the aliasn, equal to the label. Then [n:E]cannot have the same variable.select * from n: e, n` also leads to an error.

This is best handled in the binder rather than the transformer, because there we have all the information we need. In the transformer we would only keep track of the fact that the variable is empty ("").