From AST to rows: the query engine·16 min

Multi-hop & isomorphism in the executor

0 / 1

# grade this stage (from your course directory)
npx theinference test --stage multi-hop --watch

Generalize to multi-segment patterns — the co-star query. Iterate the segments, extending the binding set one relationship at a time, each extension tracking the relationship ids used so far and rejecting reuse (isomorphism). Then WHERE / RETURN / DISTINCT / ORDER BY / LIMIT exactly as before. The coStar.name <> 'Kevin Bacon' predicate keeps an actor from being their own co-star.

Your task

Extend matchPath to N segments

For each segment, from the previous node variable's binding, follow neighborEdges, skip any relationship already in b.usedRels, and bind the new variable. The fixture is the famous query: (bacon)-[:ACTED_IN]->(m)<-[:ACTED_IN]-(coStar).

src/executor.ts

for (const seg of path.segments) {
  const out = [];
  for (const b of bindings) {
    const cur = b.vars.get(prevVar);
    for (const { rel, node } of store.neighborEdges(cur, seg.rel.type, seg.rel.dir)) {
      if (b.usedRels.has(rel)) continue;          // relationship isomorphism
      if (!nodeMatches(store, node, seg.node)) continue;
      const vars = new Map(b.vars); vars.set(seg.node.variable, node);
      const usedRels = new Set(b.usedRels); usedRels.add(rel);
      out.push({ vars, usedRels });
    }
  }
  bindings = out; prevVar = seg.node.variable;
}

Process command

your_program.sh query {fixture}/fixtures/data/nodes.json {fixture}/fixtures/data/relationships.json "MATCH (bacon:Person {name:'Kevin Bacon'})-[:ACTED_IN]->(m)<-[:ACTED_IN]-(coStar) WHERE coStar.name <> 'Kevin Bacon' RETURN DISTINCT coStar.name AS name ORDER BY name"
# -> 15 co-stars across A Few Good Men, Apollo 13, Frost/Nixon

How it's graded

Process mode, stdout_json_match as an exact ordered list (ORDER BY name). 15 distinct co-stars. If only this query is wrong, your isomorphism check is the prime suspect.

WHERE filter + RETURN projection Set semantics & ORDER BY