SQL Route Finder in Oracle - Recursion?

Question

I am trying to build a simple route finder which calculates and stores the nodes of which a route traverses to get from A -- B. I have two tables; One which is made up of stages (The nodes and their 'next possible hops') and a route_stage table which should be able to store each route calculated with a unique route id.

Stage Table

STAGEID START_STATION                  NEXT_HOP_STATION                   LENGTH
---------- ------------------------------ ------------------------------ ----------
     1 Penzance                       Plymouth                               78 
     2 Plymouth                       Exeter                               44.8 
     3 Exeter                         Taunton                              36.6 
     4 Exeter                         Salisbury                            96.6 
     5 Salisbury                      Basingstoke                          38.2 
     6 Basingstoke                    Southampton                          52.7 
     7 Southampton                    Poole                                  37 
     8 Poole                          Weymouth                             31.6 
     9 Taunton                        Reading                              99.5 
    10 Reading                        Basingstoke                            18 
    11 Reading                        Paddington                           40.9 
    12 Taunton                        Bristol                              48.8 
    13 Bristol                        Bath                                   13 
    14 Bath                           Swindon                              37.5 
    15 Swindon                        Reading                              39.8

Route_Stage Table

ROUTEID    STAGEID
---------- ----------
     1          1 
     1          2 
     1          3 
     1          9 
     1         11 
     2          6 
     2          7 
     2          8 
     2         10 
     2         11 

For the case of the above, the route with ID 1 Starts at Penzance and traverses, Plymouth, Exeter, Taunton, Reading and terminates at Paddington. Ideally I want to create a stored procedure that takes the entry parameters of a start and end station so the code inside will be able to calculate a suitable route.

I've had a look at recursion but got a bit lost, as I am not sure how the code should react when there are multiple potential paths from a node? How would it know which one was the correct one to go down.

Any help is greatly appreciated. Thanks!

Answer 1

For a single given starting position, this will (I think.. Sorry, typing by hand on an iPad) provide a row for each route that leaves that starting point.

  SELECT
    LEVEL as route_step,
    t1.next_hop_station as next_station,
    t1.stageid

  FROM 
    stage t1

    INNER  JOIN stage t2 
    ON t2.start_station = t1.next_hop_station

  START WITH
    t1.start_station = 'your start station'

  CONNECT BY 
    PRIOR t1.start_station = t1.next_hop_station

So, for start station Penzance:

Route_Step  Next_Station StageID
1.          Plymouth.    1
2.          Exeter.      2
3.          Taunton.     3
4.          Reading.     9
5.          Basingstoke. 10
6.          Southampton  6
7.          Poole.       7
8.          Weymouth     8
5.          Paddington.  11
3.          Salisbury    4
4.          Basingstoke. 5
5.          Southampton. 6
6.          Poole.       7
7.          Weymouth.    8

* excuse the .'s!

Wrapping that with a join on your distinct starting stations (and removing the explicit START WITH clause so that you get routes from all stations, not just a single station) will give you what you need for your output table (although as per previous comments, I'm not sure what use that structure is to you, as you lose pertinent detail):

SELECT
     First_Stage.stageid as routeid,
     q.stageid

   FROM
   (

      SELECT
        LEVEL as route_step,
        t1.next_hop_station as next_station,
        t1.stageid

      FROM 
        stage t1

        INNER  JOIN stage t2 
        ON t2.start_station = t1.next_hop_station

      CONNECT BY 
        PRIOR t1.start_station = t1.next_hop_station
    ) q

    INNER JOIN stage as first_stage
    ON first_stage.stageid = q.stageid
    AND q.route_step = 1