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

Question

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.

You need a recursive statement and a recursive CTE is what you need. — Gordon Linoff
– Gordon Linoff, Commented Mar 25, 2014 at 16:45
SQL Server, I corrected description. As I see, recursive CTE uses WITH clause and returns all routes in single rows, so that it is not possible to easily select all ways which finishes on specified ID2 — user3162968
– user3162968, Commented Mar 25, 2014 at 16:49
As Gordon mentioned, recursive CTE should be the way to go. Recently wrote one HERE-post link, if you want to refer for a start. — SoulTrain
– SoulTrain, Commented Mar 25, 2014 at 16:50
Recursive CTEs can be tricky, so I'll grant you may not find them "easily," but they can handle branching and will likely be more elegant other loops recursive procedure efforts. Can we assume an particular limit to the number of steps along a route? 5? 10? 100? 1000? — Karl Kieninger
– Karl Kieninger, Commented Mar 25, 2014 at 16:55

Karl Kieninger · Accepted Answer · 2014-03-25 20:09:54Z

1

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

answered Mar 25, 2014 at 20:09

Karl Kieninger

9,1692 gold badges36 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user3162968 Over a year ago

Your answer is really great, and I have got what I needed. Next question is: how can I get values from ,a,b,c,... string (numbers) into separate table? I need something like (1,a), (2,b), (3,c) etc, in one table.

Karl Kieninger Over a year ago

Ah. Yes, you need a split function as well. Take a look here stackoverflow.com/questions/43249/….

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related