Getting paths between records using SQL?

Question

This SQLFiddle example describes 2 tables and their relationship:

1. Primary Routes: A direct route between 2 places. Indirect primary routes are for relationship purposes with the secondary routes table

2. Secondary Routes: A route between 2 places where no direct primary route exists

Now, a user wants to go from one place to another. So, for this example, a user selects the following points:

1. London->Harlow:

A direct route exists. The SQL is simple:

SELECT * 
FROM primary_routes 
WHERE 
    (
        (point1 = 'London' AND point2 = 'Harlow') 
        OR (point1 = 'Harlow' AND point2 = 'London')
    ) 
    AND direct = 1 

A route is only entered once in the DB, however a route goes both ways.

2. Stanmore->Waltham:

No direct route exists, however both these points lie on the same route. The SQL is:

SELECT DISTINCT primary_id 
FROM secondary_routes 
WHERE point IN ( 'Stanmore', 'Waltham')

Now, the complexity will increase because there might be other kinds of connections, for example:

3. London-Sheering: No route from 1 and 2 above fits. However, routes exist between London->Harlow and Harlow-Sheering.

4. Wembley-Shenley: No route from 1, 2, or 3 fits. However, routes exist between Wembley->London->Watford->Shenley, or Wembley->London->Harlow->Shenley

Is it possible to build a (not so complex) SQL statement that will return the routes for 3 and 4, and furthermore, for each route found (including in 2), the distance between the 2 points must be calculated and be part of the route.

Answer 1

In a word, no, there is no simple SQL query given your data structure that would easily find those routes.

You would probably be better off pre-calculating those routes and distances and populating those into a third table. e.g. StartPoint, EndPoint, TransferPoint, ToTransfer_Primary_id, FromTransfer_PrimaryID2, Distance.

You would have to build it up in stages.

For example for London -> Harlow you can use the primary routes

select firstroute.point1 as startpoint, firstroute.id as ToTransfer_Primary_id, firstroute.point2 as transferpoint, secondroute.id as FromTransfer_Primary_id , secondroute.point2 as endpoint
from primary_routes as firstroute
inner join primary_routes as secondroute on secondroute.point1 = firstroute.point2
WHERE firstroute.point1 = 'London'
AND secondroute.point2 = 'Harlow'

Which gives you

startpoint  ToTransfer_Primary_id   transferpoint   FromTransfer_Primary_id endpoint
London      2                       Watford         4                       Harlow

Then you would have to write a query to test for a transfer point at one of the secondary routes.

Answer 2

I didn't see the direct route distance in the link you posted (which you would need to calculate total distance), but you can compare points in two copies of the table which join wherever a.point1 is what you'd like as well as b.point2 and the two have a common point a.point2=b.point1

select 
   a.point1 as startpoint,
   b.point2 as endpoint, 
   a.point2 as midpoint,
from primary_routes a
join primary_routes as b on b.point1=a.point2   
where a.point1 like '%London%'
    and
    b.point2 like '%Harlow%'