Relix

Problem solving

Reachable, how far, and by what route

Grain: one row per reachable pair · Class: Graph · Signals: reachable, can get to, connected to, within N hops, shortest route, cheapest route, via · Operators: CLOSURE, PATH, TRACE

The problem

"From each airport, where can I get to with any number of connections? Which are within two hops? And what is the cheapest itinerary between two cities, and which airports does it pass through?"

How to recognise it

The question is about following a directed edge repeatedly — reachable, can get to, within N hops, the route via, the cheapest way. What makes it a graph problem rather than a join is the chain: a single join finds the direct edges, but reachable means any number of hops. Three operators answer three sharpenings of the question, and the tell is how much you need to know about the connection:

For undirected "who belongs together", see Things that belong together (CLUSTER); this recipe is directed.

The data

Direct flights with a fare. Edges is the two-column projection the closure operators want.

Flights := [
| origin | dest | cost |
|--------|------|------|
| JFK    | ORD  | 200  |
| ORD    | LAX  | 150  |
| JFK    | LAX  | 500  |
| ORD    | DEN  | 100  |
| DEN    | LAX  | 80   |
];

Edges := { π origin, dest (Flights) };

Recipe 1: everything reachable (CLOSURE)

CLOSURE from, to follows the edge to a fixpoint and returns every pair connected by one or more hops — the direct edges plus every derived one.

Query
query { τ origin, dest (CLOSURE origin, dest (Edges)) };
Result
 origin  dest
 ──────  ────
 DEN     LAX
 JFK     DEN
 JFK     LAX
 JFK     ORD
 ORD     DEN
 ORD     LAX
(6 rows)

"Can I get from JFK to anywhere?" is then a plain σ on the result — and the optimiser folds that σ into the closure as a single-source search, so scoping to one origin is an ordinary selection, not new syntax:

Query
query { σ origin = "JFK" (CLOSURE origin, dest (Edges)) };
Result
 origin  dest
 ──────  ────
 JFK     ORD
 JFK     LAX
 JFK     DEN
(3 rows)

RCLOSURE additionally pairs each node with itself, for when "stay put" is a valid route.

Recipe 2: within a hop budget, with distance (PATH)

When the question caps the distance — within two hops — and wants to know how far, PATH takes a hop window and stamps each pair with its shortest distance:

Query
query { τ hops, dest (σ origin = "JFK" (PATH origin, dest HOPS 1 TO 2 AS hops (Edges))) };
Result
 origin  dest  hops
 ──────  ────  ────
 JFK     LAX      1
 JFK     ORD      1
 JFK     DEN      2
(3 rows)

The distance is the shortest path length, so (from, to) is a candidate key — a pair never appears at two depths. As with CLOSURE, a σ on an endpoint seeds the traversal at that node.

Recipe 3: the optimal route, and its stops (TRACE)

Reachability says whether; TRACE says how, and how much. Give it a weight column and MINIMIZE/MAXIMIZE, and it returns the best route for every reachable pair as an ordered array of nodes:

Query
query { τ origin, dest (TRACE origin, dest VIA cost MINIMIZE AS route (Flights)) };
Result
 origin  dest  cost  route
 ──────  ────  ────  ───────────────
 DEN     LAX     80  [DEN, LAX]
 JFK     DEN    300  [JFK, ORD, DEN]
 JFK     LAX    350  [JFK, ORD, LAX]
 JFK     ORD    200  [JFK, ORD]
 ORD     DEN    100  [ORD, DEN]
 ORD     LAX    150  [ORD, LAX]
(6 rows)

TRACE uses the whole Flights relation (it needs the weight), not the two-column Edges. Explode the route into rows with μ route (…) when you want one stop per row.

Variations

Pitfalls

Check it