routing.sql

-- more notes on this issue at http://gist.github.com/106582 and http://gist.github.com/109036
-- Here are the table definitions I’m using.
create table visits (plano text,
                     "column" text,
                     "row" text,
                     route text);

create table square (plano text,
                     "column" text,
                     "row" text,
                     x int,
                     y int);

-- Suppose I want to find a bus route number that serves both square
-- 9b4 and some square within one square of square 16c4.

-- This verbose query uses an explicit neighbor test to find such a route:
select
  distinct a.route
from
  visits a
  join visits b using (route)
  join square c using (plano, "column", "row"),
  square d
where
  a.plano = '9' and a."column" = 'b' and a."row" = '4' and
  c.x between d.x-1 and d.x+1 and
  c.y between d.y-1 and d.y+1 and
  d.plano = '16' and d."column" = 'c' and d."row" = '4';

-- In Prolog:
-- visits("9", "b", "4", Route), 
-- square("16", "c", "4", X, Y), 
-- visits(Plano, Column, Row, Route), 
-- square(Plano, Column, Row, X2, Y2),
-- X - 1 =< X2, X + 1 >= X2,  
-- Y - 1 =< Y2, Y + 1 >= Y2.

-- In the relational algebra, you could write something like:
-- start  ← σ_(plano = '9' ∧ column = 'b' ∧ row = '4')(visits)
-- routes ← σ_(route = b.route) (start × ρ_b(visits))
-- dest   ← ρ_dest (σ_(plano = '16' ∧ column = 'c' ∧ row = '4')(square))
-- dests  ← σ_(x-1 ≤ dest.x ≤ x+1 ∧ y-1 ≤ dest.y ≤ y+1)(ρ_c(square) × dest)
-- dr     ← dests × routes
-- out    ← σ_(b.plano = c.plano ∧ b.column = c.column ∧ b.row = c.row)(dr)
-- Π_route(out)
-- 
-- Or you could factor it a little differently:
-- routes_to ← σ_(start.route = end.route)(ρ_start(visits) × ρ_end(visits))
-- squarepairs ← ρ_a(square) × ρ_b(square)
-- neighbor ← σ_(a.x-1 ≤ b.x ≤ a.x+1 ∧ a.y-1 ≤ b.y ≤ a.y+1)(squarepairs)
-- rtn ← σ_(end.plano = a.plano ∧ end.row = a.row ∧ end.column = a.column)( \
--          routes_to × neighbor)
-- out ← σ_(start.plano = '9' ∧ start.column = 'b' ∧ start.row = '4' ∧
--          b.plano = '16' ∧ b.column = 'c' ∧ b.row = '4')(rtn)
-- Π_route(out)

-- Vadim Tropashko reduces the selection/projection/cartesian product
-- algebra to two binary operations: “natural join” (or “generalized
-- intersection”) and “generalized union”, which drops all columns not
-- in common, in his paper “Relational Algebra as non-Distributive
-- Lattice” <http://arxiv.org/abs/cs.DB/0501053>.  These operations
-- suffice to provide selection, projection, cartesian product, and
-- union.  He also finds that they produce a lattice of relations,
-- with those two operations being the meet and join operations.
-- 
-- To do this, he includes some infinite relations in his set of
-- relations, relations he sort of pulls out of a hat.  In general, any
-- function can be treated as a two-column relation, and if it has an
-- infinite domain, it is an infinite relation.
-- 
-- I am going to use & for his “natural join” operation and | for his
-- “generalized union”, and I am adopting his notation `Y(a, b, c)`
-- for an empty relation with columns `a`, `b`, `c`, and `EQ(y, z)`
-- for the infinite equality relation with columns `y` and `z` which
-- contains all possible rows where y = z.
-- 
-- So what does our `routes_to` relation look like now?
-- a ← EQ(plano, start_plano) & EQ(column, start_column) & EQ(row, start_row)
-- b ← (visits & a) | Y(start_plano, start_column, start_row, route)
-- routes_to ← b & visits

-- That’s not as bad as I feared.  How about `neighbor`?  I need
-- primitives for addition and comparison; I’ll invent a relation
-- schema like EQ called `≤(a, b)` which has a row in all cases where
-- a ≤ b, and another one called `+(a, b, c)`, which has a row
-- wherever a+b = c.  Now I can write:
-- c ← EQ(plano, neigh_plano) & EQ(column, neigh_column) & EQ(row, neigh_row)
-- d ← square & c & EQ(x, neigh_x) & EQ(y, neigh_y)
-- e ← d | Y(neigh_plano, neigh_column, neigh_row, neigh_x, neigh_y)
-- f ← square & e & ≤(x, nxp1) & +(neigh_x, 1, nxp1)
-- g ← f          & ≤(nxm1, x) & +(nxm1, 1, neigh_x)
-- h ← g          & ≤(y, nyp1) & +(neigh_y, 1, nyp1)
-- i ← h          & ≤(nym1, y) & +(nym1, 1, neigh_y)
-- neighbor ← i | Y(plano, column, row, neigh_plano, neigh_column, neigh_row)
-- That’s pretty bad, 8 lines instead of 2.  It’s as bad as SQL!
-- The connection to Prolog is starting to become apparent, though.

-- Here’s the “neighbor” view to factor out the neighborhood logic, in SQL:
create view neighbor as 
select 
  a.plano as plano, a."column" as "column", a."row" as "row", 
  b.plano as bplano, b."column" as bcolumn, b."row" as brow
from 
  square a, square b
where 
  a.x between b.x-1 and b.x+1
  and a.y between b.y-1 and b.y+1;

-- In Prolog:
-- neighbor((Plano, Column, Row), (Plano2, Column2, Row2)) :-
--   square(Plano, Column, Row, X, Y), square(Plano2, Column2, Row2, X2, Y2),
--   X - 1 =< X2, X + 1 >= X2,  
--   Y - 1 =< Y2, Y + 1 >= Y2.


-- if you use the neighbor view, the route-finding query gets simpler:
select
  distinct a.route
from
  visits a
  join visits b using (route)
  join neighbor c using (plano, "column", "row")
where
  a.plano = '9' and a."column" = 'b' and a."row" = '4' and
  c.bplano = '16' and c."bcolumn" = 'c' and c."brow" = '4';

-- In Prolog:
-- visits("9", "b", "4", Route),
-- neighbor(("16", "c", "4"), (Plano, Column, Row)),
-- visits(Plano, Column, Row, Route).

-- suppose we additionally have a routes-to view:
create view routes_to as
select
  a.plano as plano, a."column" as "column", a."row" as "row",
  b.plano as bplano, b."column" as bcolumn, b."row" as brow,
  route
from
  visits a join visits b using (route);

-- In Prolog:
-- visits((Plano, Column, Row), Route) :- visits(Plano, Column, Row, Route).
-- routes_to(A, B, Route) :- visits(A, Route), visits(B, Route).
-- If you had special syntax for binary relations, you could say:
-- routes_to(A, B, Route) :- A.route = B.route, A.route = Route.

-- that simplifies it further, slightly:
select
  distinct a.route
from
  routes_to a
  join neighbor c using (plano, "column", "row")
where
  a.bplano = '9' and a."bcolumn" = 'b' and a."brow" = '4' and
  c.bplano = '16' and c."bcolumn" = 'c' and c."brow" = '4';

-- In Prolog:
-- routes_to(("9", "b", "4"), Place, Route), neighbor(("16", "c", "4"), Place).
-- If you had special syntax for binary relations, you could say:
-- routes_to(("9", "b", "4"), ("16", "c", "4").neighbor, Route).