SQLServerCentral Article

Recursive Queries in SQL:1999 and SQL Server 2005

,

Everybody has at one time in his life, had experience with recursion. When I

was young, I was on leave in Paris in an old building in which the corridor had

two mirrors facing each other. When I passed between theses mirrors my body was reflected ad infinitum, and I was very proud, joyfully admiring my image and having a concrete view of what is the infinite. That is it : recursion... A process which is able to reproduce himself for some period of time.

In mechanical situations, we do not accept infinite recursion. In the real world, we must have a stopping point because our universe is closed. Waiting for the end of an infinite process, which in fact is eternity, is a hard job ! As Woody Allen says : "eternity is really long, especially near the end ..."

In computer management, recursion is a special technique that is able, sometimes, to treat complex algorithms with an elegant coding style : a few lines will do a complete job. But recursion has some perverse effects : the resources to do the job are maximized by the fact that every call of the embedded process needs to open a complete environment space, which has the effect of using a large volume of memory. A mathematician, whose name I cannot recall, says that every recursive algorithm can be reduce to an iterative one by the use of a stack!

But our purpose in this article is to speak about RECURSIVE QUERIES in SQL, regarding the ISO standard and what MS SQL Server 2005 has done with it.

The ISO SQL:1999 standard

Here is the short syntax of a RECURSIVE QUERY :

WITH [ RECURSIVE ] <query_alias_name> [ ( <column_list> ) ]
AS ( <select_query> )
<query_using_query_alias_name>

Simple ! Isn't it? In fact, all the mechanics are inside the <select_query>. We will

show first simple, but not recursive queries, and when we understand what we can do with the keyword WITH, we will tear down the curtain to see how sexy recursion is in SQL.

A simple CTE

The use of only the WITH clause (without the keyword RECURSIVE), is to build a Common Table Expression (CTE). In a way CTE is a view build especially for a query and used in one shot: each time we execute the query. In one sense it can be called a "non persistent view".

The basic use of a CTE is to make clear some expression that contains a query twice or more in a complex query. Here is a basic example :

-- if exists, drop the table we need for the demo
IF EXISTS (SELECT *
            FROM   INFORMATION_SCHEMA.TABLES
           WHERE  TABLE_SCHEMA = USER
             AND  TABLE_NAME = 'T_NEWS')
   DROP TABLE T_NEWS
GO
-- create the table 
CREATE TABLE T_NEWS
(NEW_ID        INTEGER NOT NULL PRIMARY KEY,
 NEW_FORUM     VARCHAR(16),
 NEW_QUESTION  VARCHAR(32))
GO
-- population
INSERT INTO T_NEWS VALUES (1, 'SQL', 'What is SQL ?')
INSERT INTO T_NEWS VALUES (2, 'SQL', 'What do we do now ?')
INSERT INTO T_NEWS VALUES (3, 'Microsoft', 'Is SQL 2005 ready for use ?')
INSERT INTO T_NEWS VALUES (4, 'Microsoft', 'Did SQL2000 use RECURSION ?')
INSERT INTO T_NEWS VALUES (5, 'Microsoft', 'Where am I ?')
-- the traditionnal query :
SELECT COUNT(NEW_ID) AS NEW_NBR, NEW_FORUM
FROM   T_NEWS
GROUP  BY NEW_FORUM
HAVING COUNT(NEW_ID) = ( SELECT MAX(NEW_NBR)
                         FROM ( SELECT COUNT(NEW_ID) AS NEW_NBR, NEW_FORUM
                                FROM   T_NEWS
                                GROUP  BY NEW_FORUM ) T )
-- the result :
NEW_NBR     NEW_FORUM
----------- ----------------
3           Microsoft

This query is one that is very popular in many forums, that is, the one that often has the most of number of questions. Tobuild the query, we need to make a MAX(COUNT(... which is not allowed, and so it must be solved through the use of subqueries. But in the above query, there are two SELECT statements, which are exactly the same :

SELECT COUNT(NEW_ID) AS NEW_NBR, NEW_FORUM
FROM   T_NEWS
GROUP  BY NEW_FORUM

With the use of a CTE, we can now make the query more readable :

WITH 
   Q_COUNT_NEWS (NBR, FORUM)
   AS 
     (SELECT COUNT(NEW_ID), NEW_FORUM
      FROM   T_NEWS
      GROUP  BY NEW_FORUM)
SELECT NBR, FORUM
FROM   Q_COUNT_NEWS 
WHERE  NBR = (SELECT MAX(NBR)
              FROM   Q_COUNT_NEWS)

In fact, we use the non persistent view Q_COUNT_NEWS introduced by the WITH expression, to write a more elegant version of the solution of our problem. Like a view, you must name the CTE and you can give new names to columns that are placed in the SELECT clause of the CTE, but this is not an obligation.

Note the fact, that you can use two, three or more CTE to build a query... Let us see an example:

WITH
   Q_COUNT_NEWS (NBR, FORUM)
   AS 
     (SELECT COUNT(NEW_ID), NEW_FORUM
      FROM   T_NEWS
      GROUP  BY NEW_FORUM),
   Q_MAX_COUNT_NEWS (NBR)
   AS (SELECT MAX(NBR)
       FROM   Q_COUNT_NEWS) 
SELECT T1.*
FROM   Q_COUNT_NEWS T1
       INNER JOIN Q_MAX_COUNT_NEWS T2
             ON T1.NBR = T2.NBR

This gives the same results as the two prior versions! The first CTE, Q_COUNT_NEWS, is used as a table in the second and the two CTEs are joined in the query to give the result. Note the comma which separates the two CTEs.

3 - Two Tricks for Recursion

To do recursion, the SQL syntax needs two tricks :

FIRST : you must give a starting point for recursion. This must be done by a two part query. The first query says where to begin, and the second query says where to go to next step. These two queries are joined by a UNION ALL set operation.

SECOND : you need to make a correlation between the CTE and the SQL inside the CTE (Inside out, outside in, was a popular disco song ... isn't it ? ) to progress step by step. That is made by referencing the <query_alias_name> inside the SQL that builds the CTE.

4 - First example : a simple hierarchy

For this example, I have made a table which contains a typology of vehicles :

-- if exists, drop the table we need for the demo
IF EXISTS (SELECT *
           FROM   INFORMATION_SCHEMA.TABLES
           WHERE  TABLE_SCHEMA = USER
             AND  TABLE_NAME = 'T_VEHICULE')
   DROP TABLE T_VEHICULE
-- create it
CREATE TABLE T_VEHICULE
(VHC_ID         INTEGER NOT NULL PRIMARY KEY,
 VHC_ID_FATHER  INTEGER FOREIGN KEY REFERENCES T_VEHICULE (VHC_ID),
 VHC_NAME       VARCHAR(16))
-- populate
INSERT INTO T_VEHICULE VALUES (1, NULL, 'ALL')
INSERT INTO T_VEHICULE VALUES (2, 1, 'SEA')
INSERT INTO T_VEHICULE VALUES (3, 1, 'EARTH')
INSERT INTO T_VEHICULE VALUES (4, 1, 'AIR')
INSERT INTO T_VEHICULE VALUES (5, 2, 'SUBMARINE')
INSERT INTO T_VEHICULE VALUES (6, 2, 'BOAT')
INSERT INTO T_VEHICULE VALUES (7, 3, 'CAR')
INSERT INTO T_VEHICULE VALUES (8, 3, 'TWO WHEELES')
INSERT INTO T_VEHICULE VALUES (9, 3, 'TRUCK')
INSERT INTO T_VEHICULE VALUES (10, 4, 'ROCKET')
INSERT INTO T_VEHICULE VALUES (11, 4, 'PLANE')
INSERT INTO T_VEHICULE VALUES (12, 8, 'MOTORCYCLE')
INSERT INTO T_VEHICULE VALUES (13, 8, 'BYCYCLE')

Usually a hierarchy must be schematized with an auto reference, which is the case here : a foreign key references the primary key of the table. Theses data can be viewed as :

ALL
|--SEA
|  |--SUBMARINE
|  |--BOAT
|--EARTH
|  |--CAR
|  |--TWO WHEELES
|  |  |--MOTORCYCLE
|  |  |--BYCYCLE
|  |--TRUCK
|--AIR
   |--ROCKET
   |--PLANE

Now let us construct the query. We want to know where does the MOTORCYCLE come from. In other word, what are all the ancestors of "MOTORCYCLE". We must start with the data of the row which contain the motorbyke :

SELECT VHC_NAME, VHC_ID_FATHER
FROM   T_VEHICULE
WHERE  VHC_NAME = 'MOTORCYCLE'

We need to have the father ID to go to next step. The second query, which does the next step, must be written like this :

SELECT VHC_NAME, VHC_ID_FATHER
FROM   T_VEHICULE

As you see, there is no difference between the two queries, except that we do not specify the filter WHERE to go to next step. Remember that we need to join thoses two queries by a UNION ALL, which will specify the stepping method :

SELECT VHC_NAME, VHC_ID_FATHER
FROM   T_VEHICULE
WHERE  VHC_NAME = 'MOTORCYCLE'
UNION ALL
SELECT VHC_NAME, VHC_ID_FATHER
FROM   T_VEHICULE

Now let us place this stuff in the CTE :

WITH 
   tree (data, id)
   AS (SELECT VHC_NAME, VHC_ID_FATHER
       FROM   T_VEHICULE
       WHERE  VHC_NAME = 'MOTORCYCLE'
       UNION ALL
       SELECT VHC_NAME, VHC_ID_FATHER
       FROM   T_VEHICULE)

Now we are close to the recursion. The last step is to make a cycle to execute the stepping techniques. This is done by using the CTE name as a table inside the SQL of the CTE. In our case, we must join the second query of the CTE to the CTE itself, by the chain made with tree.id = (second query).VHC_ID. This can be realized like this :

WITH 
   tree (data, id)
   AS (SELECT VHC_NAME, VHC_ID_FATHER
       FROM   T_VEHICULE
       WHERE  VHC_NAME = 'MOTORCYCLE'
       UNION ALL
       SELECT VHC_NAME, VHC_ID_FATHER
       FROM   T_VEHICULE V
              INNER JOIN tree t
                    ON t.id = V.VHC_ID)
SELECT *
FROM   tree

There is nothing more to do other than make the select as simple as possible to show the data. Now, if you press the F5 button to execute... You will see this :

data             id
---------------- -----------
MOTORCYCLE       8
TWO WHEELES      3
EARTH            1
ALL              NULL

Now have a look back at the relationships that do the stepping, in a graphic view :

                   correlation
        ____________________________________
       |                                    |
       v                                    |
WITH tree (data, id)                        |
AS (SELECT VHC_NAME, VHC_ID_FATHER          |
    FROM   T_VEHICULE                       |
    WHERE  VHC_NAME = 'MOTORCYCLE'          |
    UNION ALL                               |
    SELECT VHC_NAME, VHC_ID_FATHER          |
    FROM   T_VEHICULE V                     |
           INNER JOIN tree t <---------------
                 ON t.id = V.VHC_ID)
SELECT *
FROM   tree

By the way, what stopped the recursive process? The fact that no more chains are possible when arriving with a "NULL" value id, which is the case in this example when we reach "ALL".

Now, you get the technique. Notice that for obscure reasons, MS SQL Server 2005 does not accept the RECURSIVE key word following the WITH introducing CTE. But 2005 is a beta version actually, so we can expect that this will be solved in the final product.

5 - Hierarchical indentation

One more important thing with trees structured data is to view the data as a tree... which means a hierarchical indentation when retrieving the data. Is this possible ? Yes, of course. The order need to knows the path, the level for placing space characters and the id or the timestamp of the row in case of rows of similar tree placement (multileaves data). This can be done by calculating the path inside the recursion. Here is an example of such a query :

WITH tree (data, id, level, pathstr)                        
AS (SELECT VHC_NAME, VHC_ID, 0,
           CAST('' AS VARCHAR(MAX))           
    FROM   T_VEHICULE                       
    WHERE  VHC_ID_FATHER IS NULL          
    UNION ALL                               
    SELECT VHC_NAME, VHC_ID, t.level + 1, t.pathstr + V.VHC_NAME
    FROM   T_VEHICULE V                     
           INNER JOIN tree t 
                 ON t.id = V.VHC_ID_FATHER)
SELECT SPACE(level) + data as data, id, level, pathstr
FROM   tree
ORDER  BY pathstr, id 
data                 id          level       pathstr
-------------------- ----------- ----------- --------------------------------
ALL                  1           0           
 AIR                 4           1           AIR
  PLANE              11          2           AIRPLANE
  ROCKET             10          2           AIRROCKET
 EARTH               3           1           EARTH
  CAR                7           2           EARTHCAR
  TRUCK              9           2           EARTHTRUCK
  TWO WHEELES        8           2           EARTHTWO WHEELES
   BYCYCLE           13          3           EARTHTWO WHEELESBYCYCLE
   MOTORCYCLE        12          3           EARTHTWO WHEELESMOTORCYCLE
 SEA                 2           1           SEA
  BOAT               6           2           SEABOAT
  SUBMARINE          5           2           SEASUBMARINE
 

To do this, we have use a new data type in SQL 2005 which is called VARCHAR(MAX), because we do not know the maximum of chars that will result in an operation a concatenation of a VARCHAR(16) in a recursive query that can be very deep. Notice that it is not a good idea to construct the path with VARCHAR because it can result in some boundaries effects such as concatenating words like 'LAND' and 'MARK' as level 2 of the tree which can be confused as 'LANDMARK' as level 1 in another branch of the same tree, so you must preserve blank space in the concatened path to avoid such problems. This can be done by casting VHC_NAME as a CHAR SQL data type.

6 - Trees without recursion

But I must say that hierarchical data is not very interesting! Why? Because there are other ways to treat the data. Remember that I told you that a mathematician may say "you can avoid recursion by using a stack". Is this

possible in our case?

Yes!

Just put the stack inside the table. How? By using two new columns : RIGHT_BOUND and LEFT_BOUND...

ALTER TABLE T_VEHICULE 
ADD   RIGHT_BOUND INTEGER
ALTER TABLE T_VEHICULE 
ADD   LEFT_BOUND INTEGER

Now, like a magician, I will populate this new columns with some tricky numbers :

UPDATE T_VEHICULE SET LEFT_BOUND = 1 , RIGHT_BOUND = 26 WHERE VHC_ID = 1
UPDATE T_VEHICULE SET LEFT_BOUND = 2 , RIGHT_BOUND = 7  WHERE VHC_ID = 2
UPDATE T_VEHICULE SET LEFT_BOUND = 8 , RIGHT_BOUND = 19 WHERE VHC_ID = 3
UPDATE T_VEHICULE SET LEFT_BOUND = 20, RIGHT_BOUND = 25 WHERE VHC_ID = 4
UPDATE T_VEHICULE SET LEFT_BOUND = 3 , RIGHT_BOUND = 4  WHERE VHC_ID = 5
UPDATE T_VEHICULE SET LEFT_BOUND = 5 , RIGHT_BOUND = 6  WHERE VHC_ID = 6
UPDATE T_VEHICULE SET LEFT_BOUND = 9 , RIGHT_BOUND = 10 WHERE VHC_ID = 7
UPDATE T_VEHICULE SET LEFT_BOUND = 11, RIGHT_BOUND = 16 WHERE VHC_ID = 8
UPDATE T_VEHICULE SET LEFT_BOUND = 17, RIGHT_BOUND = 18 WHERE VHC_ID = 9
UPDATE T_VEHICULE SET LEFT_BOUND = 21, RIGHT_BOUND = 22 WHERE VHC_ID = 10
UPDATE T_VEHICULE SET LEFT_BOUND = 23, RIGHT_BOUND = 24 WHERE VHC_ID = 11
UPDATE T_VEHICULE SET LEFT_BOUND = 12, RIGHT_BOUND = 13 WHERE VHC_ID = 12
UPDATE T_VEHICULE SET LEFT_BOUND = 14, RIGHT_BOUND = 15 WHERE VHC_ID = 13

And here is the magic query, giving the same result as the complex hierarchical recursive query :

SELECT *
FROM   T_VEHICULE
WHERE  RIGHT_BOUND > 12
  AND  LEFT_BOUND < 13
VHC_ID      VHC_ID_FATHER VHC_NAME         RIGHT_BOUND LEFT_BOUND
----------- ------------- ---------------- ----------- -----------
1           NULL          ALL              26          1
3           1             EARTH            19          8
8           3             TWO WHEELES      16          11
12          8             MOTORCYCLE       13          12

The question is : what is the trick ?

In fact we realize a stack by numbering the data slices. I make a picture of it :

A tree as a stack

The only thing I do is to numerate continuously begining by 1, from the right to the left bounds of all stacks made by each piece of data. Then to obtain the above query, I just take the bounds of the MOTORCYCLE, which are LEFT 12 and RIGHT 13, and place it in the WHERE clause asking for datas that have a RIGHT BOUND over 12 and a LEFT BOUND under 13.

By the way, my graphic will be much more clear to understand if we rotate it :

Do you see the stacks? This representation of trees is well known in specialized database litterature, especially writeings by Joe Celko. You will find every thing you want in his famous book "Trees and Hierarchies" in

"SQL for smarties", Morgan Kaufman ed. Another resource if you can read French is to go to my web site in which stored procs are written for MS SQL Server to do all jobs relative to this model : http://sqlpro.developpez.com/cours/arborescence/

Last, can we reproduce the hierarchical indentation as seen in the last query ? Yes of course. This will be much easier by introducing a new column 'LEVEL' to indicate the level of the node. This can be very simple to calculate, because when inserting in the tree, the first node is the root, so the level is 0. Another point to insert in a tree had a level that can simply be calculated with the parent's data : if the point is to insert as a son, the level is the parent level + 1. To insert as a brother, the level is the same as the brother. Here are the ALTER and UPDATE statements that place the levels in the table for our purpose :

ALTER TABLE T_VEHICULE 
ADD LEVEL INTEGER
UPDATE T_VEHICULE SET LEVEL = 0 WHERE VHC_ID = 1
UPDATE T_VEHICULE SET LEVEL = 1 WHERE VHC_ID = 2
UPDATE T_VEHICULE SET LEVEL = 1 WHERE VHC_ID = 3
UPDATE T_VEHICULE SET LEVEL = 1 WHERE VHC_ID = 4
UPDATE T_VEHICULE SET LEVEL = 2 WHERE VHC_ID = 5
UPDATE T_VEHICULE SET LEVEL = 2 WHERE VHC_ID = 6
UPDATE T_VEHICULE SET LEVEL = 2 WHERE VHC_ID = 7
UPDATE T_VEHICULE SET LEVEL = 2 WHERE VHC_ID = 8
UPDATE T_VEHICULE SET LEVEL = 2 WHERE VHC_ID = 9
UPDATE T_VEHICULE SET LEVEL = 2 WHERE VHC_ID = 10
UPDATE T_VEHICULE SET LEVEL = 2 WHERE VHC_ID = 11
UPDATE T_VEHICULE SET LEVEL = 3 WHERE VHC_ID = 12
UPDATE T_VEHICULE SET LEVEL = 3 WHERE VHC_ID = 13

Now, the indentation query is :

SELECT SPACE(LEVEL) + VHC_NAME as data
FROM   T_VEHICULE
ORDER  BY LEFT_BOUND
data
-----------------------
ALL
 SEA
  SUBMARINE
  BOAT
 EARTH
  CAR
  TWO WHEELES
   MOTORCYCLE
   BYCYCLE
  TRUCK
 AIR
  ROCKET
  PLANE

Much more simple, isn't it ?

FIRST IMPRESSIONS ...

The only thing to say about these two ways of navigating through hierarchical data, is that the interval model is much more efficient and performs better than the one using

the SQL:1999 RECURSIVE query technique. In fact, RECURSIVE queries are not so interesting this way... But another way?... Yes !

7 - Second example : a complex network (a much more sexy query !)

Perhaps you never go to France. So you may be interested by the fact that in Paris, there are beautifull girls, and in Toulouse a famous dish called cassoulet, and a small plane constructor call Airbus. So the problem is to go by car from Paris to Toulouse using the speedway network. I just simplify for you (if you are lost and you do not know the prononciation to ask people your way to Toulouse, it is simple. Just say "to loose"...) :

                PARIS
                  |
  ------------------------------------
  |               |                  |
 385             420                470
  |               |                  |
NANTES       CLERMONT FERRAND      LYON
                |   |                |
                |   |  335       305 |    320
                |   ----------  -----------------
                |            |  |               |  
            375 |         MONTPELLIER        MARSEILLE
                |             |                 |
         ----------------------                205
         |            240                       |
      TOULOUSE                                 NICE
-- if exists, drop the table we need for the demo
IF EXISTS (SELECT *
           FROM   INFORMATION_SCHEMA.TABLES
           WHERE  TABLE_SCHEMA = USER
             AND  TABLE_NAME = 'T_JOURNEY')
   DROP TABLE T_JOURNEY
-- create the table :
CREATE TABLE T_JOURNEY 
(JNY_FROM_TOWN  VARCHAR(32),
 JNY_TO_TOWN    VARCHAR(32),
 JNY_MILES      INTEGER)
-- populate  :
INSERT INTO T_JOURNEY VALUES ('PARIS', 'NANTES', 385)
INSERT INTO T_JOURNEY VALUES ('PARIS', 'CLERMONT-FERRAND', 420)
INSERT INTO T_JOURNEY VALUES ('PARIS', 'LYON', 470)
INSERT INTO T_JOURNEY VALUES ('CLERMONT-FERRAND', 'MONTPELLIER', 335)
INSERT INTO T_JOURNEY VALUES ('CLERMONT-FERRAND', 'TOULOUSE', 375)
INSERT INTO T_JOURNEY VALUES ('LYON', 'MONTPELLIER', 305)
INSERT INTO T_JOURNEY VALUES ('LYON', 'MARSEILLE', 320)
INSERT INTO T_JOURNEY VALUES ('MONTPELLIER', 'TOULOUSE', 240)
INSERT INTO T_JOURNEY VALUES ('MARSEILLE', 'NICE', 205)

Now we will try a very simple query, giving all the journeys between towns :

WITH journey (TO_TOWN) 
AS
   (SELECT DISTINCT JNY_FROM_TOWN 
    FROM   T_JOURNEY
    UNION  ALL
    SELECT JNY_TO_TOWN
    FROM   T_JOURNEY AS arrival
           INNER JOIN journey AS departure
                 ON departure.TO_TOWN = arrival.JNY_FROM_TOWN)
SELECT *
FROM   journey
TO_TOWN
--------------------------------
CLERMONT-FERRAND
LYON
MARSEILLE
MONTPELLIER
PARIS
NANTES
CLERMONT-FERRAND
LYON
MONTPELLIER
MARSEILLE
NICE
TOULOUSE
MONTPELLIER
TOULOUSE
TOULOUSE
TOULOUSE
NICE
MONTPELLIER
MARSEILLE
NICE
TOULOUSE
MONTPELLIER
TOULOUSE
TOULOUSE

This query is not very interesting because we do not know from which town we came. We just know the towns where we can go, and the fact that we have probably different ways to go to same place. Let us see if we can have some more information...

First, we want to start from Paris :

WITH journey (TO_TOWN) 
AS
   (SELECT DISTINCT JNY_FROM_TOWN 
    FROM   T_JOURNEY
    WHERE  JNY_FROM_TOWN = 'PARIS'
    UNION  ALL
    SELECT JNY_TO_TOWN
    FROM   T_JOURNEY AS arrival
           INNER JOIN journey AS departure
                 ON departure.TO_TOWN = arrival.JNY_FROM_TOWN)
SELECT *
FROM   journey
TO_TOWN
--------------------------------
PARIS
NANTES
CLERMONT-FERRAND
LYON
MONTPELLIER
MARSEILLE
NICE
TOULOUSE
MONTPELLIER
TOULOUSE
TOULOUSE

We have probably three ways to go to Toulouse. Can we filter the destination? Sure !

WITH journey (TO_TOWN) 
AS
   (SELECT DISTINCT JNY_FROM_TOWN 
    FROM   T_JOURNEY
    WHERE  JNY_FROM_TOWN = 'PARIS'
    UNION  ALL
    SELECT JNY_TO_TOWN
    FROM   T_JOURNEY AS arrival
           INNER JOIN journey AS departure
                 ON departure.TO_TOWN = arrival.JNY_FROM_TOWN)
SELECT *
FROM   journey
WHERE  TO_TOWN = 'TOULOUSE'
TO_TOWN
--------------------------------
TOULOUSE
TOULOUSE
TOULOUSE

We can refine this query by calculating the number of steps involved in the different ways :

WITH journey (TO_TOWN, STEPS) 
AS
   (SELECT DISTINCT JNY_FROM_TOWN, 0
    FROM   T_JOURNEY
    WHERE  JNY_FROM_TOWN = 'PARIS'
    UNION  ALL
    SELECT JNY_TO_TOWN, departure.STEPS + 1
    FROM   T_JOURNEY AS arrival
           INNER JOIN journey AS departure
                 ON departure.TO_TOWN = arrival.JNY_FROM_TOWN)
SELECT *
FROM   journey
WHERE  TO_TOWN = 'TOULOUSE'
TO_TOWN                          STEPS
-------------------------------- -----------
TOULOUSE                         3
TOULOUSE                         2
TOULOUSE                         3

The cherry on the cake will be to know the distances of the different ways :

WITH journey (TO_TOWN, STEPS, DISTANCE) 
AS
   (SELECT DISTINCT JNY_FROM_TOWN, 0, 0
    FROM   T_JOURNEY
    WHERE  JNY_FROM_TOWN = 'PARIS'
    UNION  ALL
    SELECT JNY_TO_TOWN, departure.STEPS + 1, 
           departure.DISTANCE + arrival.JNY_MILES
    FROM   T_JOURNEY AS arrival
           INNER JOIN journey AS departure
                 ON departure.TO_TOWN = arrival.JNY_FROM_TOWN)
SELECT *
FROM   journey
WHERE  TO_TOWN = 'TOULOUSE'
TO_TOWN                 STEPS       DISTANCE
----------------------- ----------- -----------
TOULOUSE                3           1015
TOULOUSE                2           795
TOULOUSE                3           995

The girl in the cake will be to know the different towns we visit by those different ways :

WITH journey (TO_TOWN, STEPS, DISTANCE, WAY) 
AS
   (SELECT DISTINCT JNY_FROM_TOWN, 0, 0, CAST('PARIS' AS VARCHAR(MAX)) 
    FROM   T_JOURNEY
    WHERE  JNY_FROM_TOWN = 'PARIS'
    UNION  ALL
    SELECT JNY_TO_TOWN, departure.STEPS + 1, 
           departure.DISTANCE + arrival.JNY_MILES,
           departure.WAY + ', ' + arrival.JNY_TO_TOWN
    FROM   T_JOURNEY AS arrival
           INNER JOIN journey AS departure
                 ON departure.TO_TOWN = arrival.JNY_FROM_TOWN)
SELECT *
FROM   journey
WHERE  TO_TOWN = 'TOULOUSE'
TO_TOWN           STEPS       DISTANCE    WAY
----------------- ----------- ----------- -------------------------------------------------
TOULOUSE          3           1015        PARIS, LYON, MONTPELLIER, TOULOUSE
TOULOUSE          2           795         PARIS, CLERMONT-FERRAND, TOULOUSE
TOULOUSE          3           995         PARIS, CLERMONT-FERRAND, MONTPELLIER, TOULOUSE

And now, ladies and gentleman, the RECURSIVE QUERY is proud to present to you how to solve a very complex problem, called the traveling salesman problem. (one of the operational research problems on which Edsger Wybe Dijkstra found the first efficient algorithm and received the Turing Award in 1972):

WITH journey (TO_TOWN, STEPS, DISTANCE, WAY) 
AS
(SELECT DISTINCT JNY_FROM_TOWN, 0, 0, CAST('PARIS' AS VARCHAR(MAX))
FROM T_JOURNEY
WHERE JNY_FROM_TOWN = 'PARIS'
UNION ALL
SELECT JNY_TO_TOWN, departure.STEPS + 1,
departure.DISTANCE + arrival.JNY_MILES,
departure.WAY + ', ' + arrival.JNY_TO_TOWN
FROM T_JOURNEY AS arrival
INNER JOIN journey AS departure
ON departure.TO_TOWN = arrival.JNY_FROM_TOWN)
SELECT TOP 1 *
FROM journey
WHERE TO_TOWN = 'TOULOUSE'
ORDER BY DISTANCE

TO_TOWN STEPS DISTANCE WAY
------------------ ----------- ----------- ---------------------------------
TOULOUSE 2 795 PARIS, CLERMONT-FERRAND, TOULOUSE

By the way, TOP n is a non standard SQL... Dislike it... Enjoy CTE !

WITH 
   journey (TO_TOWN, STEPS, DISTANCE, WAY) 
   AS
      (SELECT DISTINCT JNY_FROM_TOWN, 0, 0, CAST('PARIS' AS VARCHAR(MAX)) 
       FROM   T_JOURNEY
       WHERE  JNY_FROM_TOWN = 'PARIS'
       UNION  ALL
       SELECT JNY_TO_TOWN, departure.STEPS + 1, 
              departure.DISTANCE + arrival.JNY_MILES,
              departure.WAY + ', ' + arrival.JNY_TO_TOWN
       FROM   T_JOURNEY AS arrival
              INNER JOIN journey AS departure
                    ON departure.TO_TOWN = arrival.JNY_FROM_TOWN),
   short (DISTANCE)
   AS
(SELECT MIN(DISTANCE)
FROM journey
WHERE TO_TOWN = 'TOULOUSE')
SELECT *
FROM journey j
INNER JOIN short s
ON j.DISTANCE = s.DISTANCE
WHERE TO_TOWN = 'TOULOUSE'

8 - What more can we do?

In fact, one thing that is limiting the process in our network of speedways, is that we have made routes with a single sense. I mean, we can go from Paris to Lyon, but we are not allowed to go from Lyon to

Paris. For that, we need to add the reverse ways in the table, like :

JNY_FROM_TOWN  JNY_TO_TOWN  JNY_MILES
-------------- ------------ ---------
LYON           PARIS        470

This can be done, by a very simple query :

INSERT INTO T_JOURNEY
SELECT JNY_TO_TOWN, JNY_FROM_TOWN, JNY_MILES
FROM T_JOURNEY

The only problem is that, previous queries won't work properly :

WITH journey (TO_TOWN) 
AS
   (SELECT DISTINCT JNY_FROM_TOWN 
    FROM   T_JOURNEY
    WHERE  JNY_FROM_TOWN = 'PARIS'
    UNION  ALL
    SELECT JNY_TO_TOWN
    FROM   T_JOURNEY AS arrival
           INNER JOIN journey AS departure
                 ON departure.TO_TOWN = arrival.JNY_FROM_TOWN)
SELECT *
FROM   journey
TO_TOWN
--------------------------------
PARIS
NANTES
CLERMONT-FERRAND
LYON
...
LYON
MONTPELLIER
MARSEILLE
PARIS
Msg 530, Level 16, State 1, Line 1
The statement terminated. The maximum recursion 100 has been exhausted before statement completion.

What happened? Simply, you are trying all ways including cycling ways like Paris, Lyon, Paris, Lyon, Paris... ad infinitum... Is there a way to avoid cycling routes? Maybe. In one of our previous queries, we have a column that give the complete list of stepped towns. Why don't we use it to avoid cycleing? The condition will be : do not pass through a town that is already in the WAY. This can be written as :

WITH journey (TO_TOWN, STEPS, DISTANCE, WAY) 
AS
   (SELECT DISTINCT JNY_FROM_TOWN, 0, 0, CAST('PARIS' AS VARCHAR(MAX)) 
    FROM   T_JOURNEY
    WHERE  JNY_FROM_TOWN = 'PARIS'
    UNION  ALL
    SELECT JNY_TO_TOWN, departure.STEPS + 1, 
           departure.DISTANCE + arrival.JNY_MILES,
           departure.WAY + ', ' + arrival.JNY_TO_TOWN
    FROM   T_JOURNEY AS arrival
           INNER JOIN journey AS departure
                 ON departure.TO_TOWN = arrival.JNY_FROM_TOWN
    WHERE  departure.WAY NOT LIKE '%' + arrival.JNY_TO_TOWN + '%')
SELECT *
FROM   journey
WHERE  TO_TOWN = 'TOULOUSE'
TO_TOWN        STEPS       DISTANCE    WAY
-------------- ----------- ----------- ---------------------------------------------------------
TOULOUSE       3           1015        PARIS, LYON, MONTPELLIER, TOULOUSE
TOULOUSE       4           1485        PARIS, LYON, MONTPELLIER, CLERMONT-FERRAND, TOULOUSE
TOULOUSE       2           795         PARIS, CLERMONT-FERRAND, TOULOUSE
TOULOUSE       3           995         PARIS, CLERMONT-FERRAND, MONTPELLIER, TOULOUSE

As you see, a new route occurs. The worst in distance, but perhaps the most beautifull !

CONCLUSIONS

A CTE can simplify the expression of complex queries. RECURSIVE queries must be employed where recursivity is needed. If you make a bad query with MS SQL Server, don't be afraid, the cycles of recursions are limited to

100. You can overcome this limit by fixing OPTION (MAXRECURSION n), with n as the value you want. The OPTION clause must be the last one in a CTE expression. But remember one thing : MS SQL Server 2005 is actually

a beta version!

Last but not least, ISO SQL:1999 had some more syntax options that can allow you to navigate in the data DEPTH FIRST or BREADTH FIRST, and also to all the data contained in the steps (in an ARRAY of ROW which must be of "sufficient" in dimension to cover all cases !).

Here is the syntax :

WITH [ RECURSIVE ]  [ ( <liste_colonne> ) ]
  AS ( <requete_select> )
[ <clause_cycle_recherche> ]
with :
<clause_cycle_recherche> ::=
   <clause_recherche>
   | <clause_cycle>
   | <clause_recherche> <clause_cycle>
and : 
   <clause_recherche> ::=
      SEARCH { DEPTH FIRTS BY
             | BREADTH FIRST BY  } <liste_specification_ordre> 
      SET <colonne_sequence>
   <clause_cycle> ::=
      CYCLE <colonne_cycle1> [ { , <colonne_cycle2> } ... ]
      SET <colonne_marquage_cycle> 
          TO <valeur_marque_cycle> 
          DEFAULT <valeur_marque_non_cycle>
      USING <colonne_chemin>

Bonus (CTE, recursive query applied)

Here is a query in a SP, that can give the exact order of tables do delete before deleting a target table, due to referential integrity :

CREATE PROCEDURE P_WHAT_TO_DELETE_BEFORE
    @TABLE_TO_DELETE VARCHAR(128),  -- targettable to delete
 @DB              VARCHAR(128),  -- target database     
 @USR             VARCHAR(128)   -- target schema (dbo in most cases)
AS
WITH T_CONTRAINTES (table_name, father_table_name)
AS (SELECT DISTINCT CTU.TABLE_NAME, TCT.TABLE_NAME
    FROM   INFORMATION_SCHEMA.REFERENTIAL_CONSTRAINTS RFC
        INNER JOIN INFORMATION_SCHEMA.CONSTRAINT_TABLE_USAGE CTU
        ON RFC.CONSTRAINT_CATALOG    = CTU.CONSTRAINT_CATALOG                    
  AND RFC.CONSTRAINT_SCHEMA = CTU.CONSTRAINT_SCHEMA                    
  AND RFC.CONSTRAINT_NAME   = CTU.CONSTRAINT_NAME           
  INNER JOIN INFORMATION_SCHEMA.TABLE_CONSTRAINTS TCT                 
        ON RFC.UNIQUE_CONSTRAINT_CATALOG    = TCT.CONSTRAINT_CATALOG                    
  AND RFC.UNIQUE_CONSTRAINT_SCHEMA = TCT.CONSTRAINT_SCHEMA                    
  AND RFC.UNIQUE_CONSTRAINT_NAME   = TCT.CONSTRAINT_NAME    
  WHERE  CTU.TABLE_CATALOG = @DB      
    AND  CTU.TABLE_SCHEMA  = @USR)
 ,T_TREE_CONTRAINTES (table_to_delete, level)
 AS (SELECT DISTINCT table_name, 0
     FROM   T_CONTRAINTES    
  WHERE  father_table_name = @TABLE_TO_DELETE    
  UNION  ALL    
  SELECT priorT.table_name, level - 1    
  FROM   T_CONTRAINTES priorT           
         INNER JOIN T_TREE_CONTRAINTES beginT                 
      ON beginT.table_to_delete = priorT.father_table_name    
  WHERE  priorT.father_table_name  priorT.table_name) 
SELECT DISTINCT *
FROM   T_TREE_CONTRAINTES
ORDER  BY level
GO

The self-reference case has been integrated. The parameters are :

@DB (database name),

@USR (schema name : dbo),

@TABLE_TO_DELETE (table you want to delete).

Bibliographical list :

  • Le langage SQL : Frédéric Brouard, Christian Soutou

    - Pearson Education 2005 (France)

  • Joe Celko's Trees & Hierarchies in SQL for Smarties : Joe

    Celko - Morgan Kaufmann 2004

  • SQL:1999 : J. Melton, A. Simon - Morgan Kauffman, 2002
  • SQL développement : Frédéric Brouard -

    Campus Press 2001 (France)

  • SQL for Dummies : Allen G. Taylor - Hungry Minds Inc 2001
  • SQL-99 complete really : P. Gulutzan, T. Pelzer - R&D Books,

    1999

  • SQL 3, Implementing the SQL Foundation Standard : Paul Fortier -

    Mc Graw Hill, 1999

  • SQL for smarties : Joe Celko - Morgan Kaufmann 1995

On Dijkstra shortest path algorithm for the traveling salesman problem and other operational research problem, see :
http://www.hsor.org/downloads/Speedy_Delivery_teacher.pdf

About cassoulet :

Discussion : http://www.evevancouver.ca/food/dishes/cassoulet.htm

Impressions : http://www.taunton.com/finecooking/pages/c00081.asp

The Academy of the Cassoulet : http://www.routedescassoulets.com/auc_uk/auc_presentation_uk.htm

Rate

4.83 (64)

You rated this post out of 5. Change rating

Share

Share

Rate

4.83 (64)

You rated this post out of 5. Change rating