user3162968
user3162968

Reputation: 1046

SQL Server: recursive self join of a table (no WITH clause)

I have the following table:

CREATE TABLE routes
(
    ID int identity not null primary key,
    from int,
    to int,
    length int not null
)

I need to have all routes from specified ID1 to ID2.

I have heard about WITH clause, but it does not satisfy me at all. It does not allow to search way from ID1 to ID2 easily because it returns just a table of FROM and TO values, and it is hard to search all possible ways.

I need something like recursive inner join - for example:

SELECT * 
FROM routes r1
INNER JOIN routes r2 ON (r1.to = r2.from AND r2.to <> r1.from AND r1.from = ID1)

It lets me look for all ways which consists of 2 routes, starting in ID1, but not those who goes somewhere and then back to ID1. Now I could select all routes which ends on ID2 (might be NULL, but it is possible that something appears). If there will be route or routes finishing at ID2 I want to break, and if there will not be, I want to inner join with routes r3 and repeat procedure until I find a route.

I could do this in a procedure and IF clauses, but I think that there must be better solution.

As I said, WITH clause does not satisfy me because it does not let me find ALL routes easily, just one.

Upvotes: 0

Views: 920

Answers (1)

Karl Kieninger
Karl Kieninger

Reputation: 9129

  1. I changed some stuff around to make it easier to play with. For example, avoid [from] and [to] as column names.
  2. I hard coded ID1 and ID2 rather than using variables.
  3. I didn't worry about "length."
  4. You'll see it find circuitous routes, but doesn't let them repeat any step.
  5. Not optimized--just showing how it works.
  6. I'm having some trouble getting the code formatting to stick. I'll post and try to edit.
  7. Fiddle link at the bottom.

CREATE TABLE routes ( ID int /identity/ not null primary key ,start char(1)--int ,finish char(1)--int --,[length] int not null )

GO

INSERT INTO routes VALUES 
  (1,'a','b')
 ,(2,'a','c')
 ,(3,'a','d')
 ,(4,'b','c')
 ,(5,'b','d')
 ,(6,'c','d')
 ,(7,'d','c')

GO

WITH cte AS (
 --anchor
 SELECT id
       ,start
       ,finish
       ,',' + CAST(id AS VARCHAR(MAX)) + ',' route_ids
   FROM routes
  WHERE start = 'a'

  UNION ALL
 --recursive part    
 SELECT a.id
       ,a.start
       ,b.finish
       ,route_ids + CAST(b.id AS VARCHAR(MAX)) + ','
   FROM cte a
        INNER JOIN
        routes b ON a.finish = b.start 
  WHERE CHARINDEX(',' + CAST(b.id AS VARCHAR(MAX)) + ',',a.route_ids,1)  = 0
)
SELECT start,finish,route_ids 
 FROM cte
WHERE finish = 'c'
ORDER BY LEN(route_ids)

Fiddle

Upvotes: 1

Related Questions