Bug: Segmentation fault removing transitive edges

[Brad-Edwards]

Imported from kuzudb/kuzu#6049
Original URL: kuzudb#6049
Original author: @mdbenito
Original created at: 2025-10-05T16:06:50Z
Kuzu v0.11.2, Ubuntu 24.04

With this data:

CREATE NODE TABLE People(name STRING PRIMARY KEY);
CREATE REL TABLE LivesWith(FROM People TO People);

CREATE (a:People {name: 'A'});
CREATE (b:People {name: 'B'});
CREATE (c:People {name: 'C'});
CREATE (d:People {name: 'D'});

// A->B->C->D, A->C, A->D
MATCH (a:People {name: 'A'}), (b:People {name:'B'}) CREATE (a)-[:LivesWith]->(b);
MATCH (b:People {name: 'B'}), (c:People {name:'C'}) CREATE (b)-[:LivesWith]->(c);
MATCH (c:People {name: 'C'}), (d:People {name:'D'}) CREATE (c)-[:LivesWith]->(d);
MATCH (a:People {name: 'A'}), (c:People {name:'C'}) CREATE (a)-[:LivesWith]->(c);
MATCH (a:People {name: 'A'}), (d:People {name:'D'}) CREATE (a)-[:LivesWith]->(d);

We can try to count transitive paths A->C and A->D with a naive query:

MATCH (a)-[r:LivesWith]->(d)
MATCH (a)-[:LivesWith*2..]->(d)
WHERE a.name <> d.name
WITH DISTINCT r
RETURN count(r);

and this works, but for larger graphs the plan explodes and kuzu hangs.

If we try to delete paths A->C and A->D with:

MATCH (a)-[t:LivesWith]->(d)
WHERE a.name <> d.name
WITH a, d, t
MATCH p = (a)-[:LivesWith*1..]->(d)
WHERE length(p) >= 2
  AND ALL (r IN relationships(p) WHERE r <> t)
WITH DISTINCT t
RETURN count(t);

The result is a segfault.

If instead we use

MATCH (a)-[t:LivesWith]->(d)
WHERE a.name <> d.name
  AND EXISTS {
    MATCH p = (a)-[:LivesWith*1..]->(d)
    WHERE length(p) >= 2
      AND ALL (r IN relationships(p) WHERE r <> t)
  }
WITH DISTINCT t
RETURN count(t);

Kuzu also segfaults.