Repository navigation
Relationship isomorphism constraint fails in a single MATCH clause when using variable-length paths #5068
Description
Memgraph version
memgraph 3.13.1 Latest
Environment
Ubuntu 24.04.3 LTS x86_64
Bug Description
In standard openCypher semantics, there is a strict relationship isomorphism rule: a single relationship cannot be matched more than once in the same MATCH clause.
However, when a MATCH clause contains multiple comma-separated patterns, and one of those patterns utilizes a variable-length path (e.g., *2), Memgraph fails to enforce this implicit uniqueness constraint. Instead, it computes a Cartesian product without filtering, allowing the same relationship to be bound multiple times in the same match, resulting in incorrect cardinality.
To Reproduce
# 1. Initialize the data:
MATCH (n) DETACH DELETE n;
CREATE (a:AQGNoSnapshotCase:A {k: 0}),
(b:AQGNoSnapshotCase:B {k: 0}),
(c:AQGNoSnapshotCase:C {k: 0}),
(b2:AQGNoSnapshotCase:B {k: 1}),
(c2:AQGNoSnapshotCase:C {k: 1}),
(a)-[:R {rid: 1}]->(b),
(b)-[:R {rid: 2}]->(c),
(b2)-[:R {rid: 3}]->(c2);
# 2. Run the baseline query (Explicit disjoint - Returns Correctly):
MATCH p = (:AQGNoSnapshotCase:A {k: 0})-[:R*2]->(:AQGNoSnapshotCase:C {k: 0}),
(:AQGNoSnapshotCase:B)-[r:R]->(:AQGNoSnapshotCase:C)
WHERE NOT (r.rid IN [rel IN relationships(p) | rel.rid])
RETURN count(*) AS cardinality;
# Returns: 1 (correct)
# 3. Run the candidate query (Implicit disjoint - Triggers Bug):
MATCH p = (:AQGNoSnapshotCase:A {k: 0})-[:R*2]->(:AQGNoSnapshotCase:C {k: 0}),
(:AQGNoSnapshotCase:B)-[r:R]->(:AQGNoSnapshotCase:C)
RETURN count(*) AS cardinality;
# Returns: 1 (bug)
Expected Behavior
The candidate query should return a cardinality of 1.
According to Cypher's relationship isomorphism rules, the relationship rid: 2 is already consumed by the first part of the pattern p (A-[:R*2]->C). Therefore, the second part of the pattern [r:R] MUST NOT bind to rid: 2 again. The implicit behavior of the candidate query should be functionally identical to the explicit WHERE NOT... filtering in the baseline query.
Actual Behavior
The candidate query returns a cardinality of 2. Memgraph ignores the relationship uniqueness constraint and binds [r:R] to rid: 2, allowing the same relationship to be traversed twice within the exact same MATCH block.
Some Evidences
memgraph> CREATE (a:AQGNoSnapshotCase:A {k: 0}),
-> (b:AQGNoSnapshotCase:B {k: 0}),
-> (c:AQGNoSnapshotCase:C {k: 0}),
-> (b2:AQGNoSnapshotCase:B {k: 1}),
-> (c2:AQGNoSnapshotCase:C {k: 1}),
-> (a)-[:R {rid: 1}]->(b),
-> (b)-[:R {rid: 2}]->(c),
-> (b2)-[:R {rid: 3}]->(c2);
Empty set (round trip in 0.001 sec)
10 labels have been created.
5 nodes have been created.
3 relationships have been created.
memgraph> MATCH p = (:AQGNoSnapshotCase:A {k: 0})-[:R*2]->(:AQGNoSnapshotCase:C {k: 0}),
-> (:AQGNoSnapshotCase:B)-[r:R]->(:AQGNoSnapshotCase:C)
-> WHERE NOT (r.rid IN [rel IN relationships(p) | rel.rid])
-> RETURN "01_baseline_explicit_disjoint" AS query, count(*) AS cardinality;
+---------------------------------+---------------------------------+
| query | cardinality |
+---------------------------------+---------------------------------+
| "01_baseline_explicit_disjoint" | 1 |
+---------------------------------+---------------------------------+
1 row in set (round trip in 0.000 sec)
memgraph> MATCH p = (:AQGNoSnapshotCase:A {k: 0})-[:R*2]->(:AQGNoSnapshotCase:C {k: 0}),
-> (:AQGNoSnapshotCase:B)-[r:R]->(:AQGNoSnapshotCase:C)
-> RETURN "01_candidate_implicit_same_match" AS query, count(*) AS cardinality;
+------------------------------------+------------------------------------+
| query | cardinality |
+------------------------------------+------------------------------------+
| "01_candidate_implicit_same_match" | 2 |
+------------------------------------+------------------------------------+
1 row in set (round trip in 0.000 sec)
--------
neo4j@neo4j> MATCH (n:AQGNoSnapshotCase) DETACH DELETE n;
CREATE (a:AQGNoSnapshotCase:A {k: 0}),
(b:AQGNoSnapshotCase:B {k: 0}),
(c:AQGNoSnapshotCase:C {k: 0}),
(b2:AQGNoSnapshotCase:B {k: 1}),
(c2:AQGNoSnapshotCase:C {k: 1}),
(a)-[:R {rid: 1}]->(b),
(b)-[:R {rid: 2}]->(c),
(b2)-[:R {rid: 3}]->(c2);
0 rows
ready to start consuming query after 23 ms, results consumed after another 0 ms
0 rows
ready to start consuming query after 57 ms, results consumed after another 0 ms
Created 5 nodes, created 3 relationships, set 8 properties, added 10 labels
neo4j@neo4j> MATCH p = (:AQGNoSnapshotCase:A {k: 0})-[:R*2]->(:AQGNoSnapshotCase:C {k: 0}),
(:AQGNoSnapshotCase:B)-[r:R]->(:AQGNoSnapshotCase:C)
WHERE NOT (r.rid IN [rel IN relationships(p) | rel.rid])
RETURN "01_baseline_explicit_disjoint" AS query, count(*) AS cardinality;
+-----------------------------------------------+
| query | cardinality |
+-----------------------------------------------+
| "01_baseline_explicit_disjoint" | 1 |
+-----------------------------------------------+
1 row
ready to start consuming query after 219 ms, results consumed after another 2 ms
neo4j@neo4j> MATCH p = (:AQGNoSnapshotCase:A {k: 0})-[:R*2]->(:AQGNoSnapshotCase:C {k: 0}),
(:AQGNoSnapshotCase:B)-[r:R]->(:AQGNoSnapshotCase:C)
RETURN "01_candidate_implicit_same_match" AS query, count(*) AS cardinality;
+--------------------------------------------------+
| query | cardinality |
+--------------------------------------------------+
| "01_candidate_implicit_same_match" | 1 |
+--------------------------------------------------+
1 row
Activity