SQLServerCentral Article

CTEs and Trees

,

NOTES : this paper is a complement of an earlier one: Recursive Queries in SQL:1999 and SQL Server 2005

All the examples refer to this earlier article.

1) transforming a tree from auto reference to interval model (nested sets)

The technique is much simpler than it appears. You need a stack table and a tree table. The job is done by a procedure which has been inspired by Joe Celko's book "Trees and Hierarchies in SQL for Smarties".

 /***************************************
 * object needed for the transformation *
 ***************************************/ -----------------------------------------
 -- a table to store the tree in auto ref
 -----------------------------------------
 CREATE TABLE T_ARBRE
 (NOD_ACTUEL INT NOT NULL,  -- actual node
  NOD_PARENT INT);           -- parent node
GO
 -----------------------------------------
 -- a table for the working stack
 -----------------------------------------
 CREATE TABLE T_PILE
 (PIL_TOP INTEGER NOT NULL,     -- top of the stack
 PIL_ID  INT NOT NULL,         -- current value 
 PIL_BG  INT,                 -- left bound 
 PIL_BD  INT);                -- right bound
GO
 --------------------------------------------------------
 -- a procedure to do the transform
 --------------------------------------------------------
 CREATE PROCEDURE P_AUTOREF_VERS_INTERVAL
 AS
 BEGIN
 DECLARE @TID INT, @TID_MAX INT, @TID_TOP INT;
 SELECT @TID = 2, @TID_MAX = 2 * (SELECT COUNT(*) FROM T_ARBRE),
       @TID_TOP = 1;
 -- taking the root
 INSERT INTO T_PILE
 SELECT 1, NOD_ACTUEL, 1, @TID_MAX
 FROM   T_ARBRE
 WHERE  NOD_PARENT IS NULL;
 -- deleting the treated lines
 DELETE FROM T_ARBRE WHERE NOD_PARENT IS NULL;
 -- process loop while the gap is over 1
 WHILE @TID <= @TID_MAX - 1
 BEGIN
 -- if there is some relations between parents and children
   IF EXISTS(SELECT *
             FROM   T_PILE AS S1
                    INNER JOIN T_ARBRE AS T1
                           ON S1.PIL_ID = T1.NOD_PARENT
               WHERE  S1.PIL_TOP = @TID_TOP)
   BEGIN
 -- insert it in the stack
       INSERT INTO T_PILE
      SELECT @TID_TOP + 1,MIN(T1.NOD_ACTUEL), @TID, NULL
      FROM   T_PILE AS S1
             INNER JOIN T_ARBRE AS T1
                    ON S1.PIL_ID = T1.NOD_PARENT
       WHERE  S1.PIL_TOP = @TID_TOP;
 -- delete them from the stack
      DELETE FROM T_ARBRE
       WHERE  NOD_ACTUEL = (SELECT PIL_ID
                          FROM   T_PILE
                          WHERE  PIL_TOP = @TID_TOP + 1)
 -- going on into the hierarchy
      SELECT @TID = @TID + 1, @TID_TOP = @TID_TOP + 1;
   END
    ELSE
 -- no more relations between parents and children
   BEGIN
 -- updating the stack
       UPDATE T_PILE
      SET    PIL_BD = @TID,
             PIL_TOP = - PIL_TOP
      WHERE  PIL_TOP = @TID_TOP;
 -- doing a gap in the tree
      SELECT @TID = @TID + 1, @TID_TOP = @TID_TOP - 1;
   END;
 END;
 END;
GO
 /**************************************
 * doing the transform                *
 **************************************/ -- inserting id from autoref in the T_ARBRE table
 INSERT INTO T_ARBRE (NOD_ACTUEL, NOD_PARENT)
 SELECT VHC_ID, VHC_ID_FATHER
 FROM   T_VEHICULE;
GO
 -- doing the process
 EXECUTE P_AUTOREF_VERS_INTERVAL;
 GO
 -- viewing the result :
 SELECT V.*, PIL_BD, PIL_BG
 FROM   T_VEHICULE AS V
        INNERJOIN T_PILE AS P
              ON V.VHC_ID = P.PIL_ID

At this point two possibilities :

  • altering the actual autoref table by adding the bounds
  • adding a new table in relationship with the autoref one to manage the bounds

Let us see the two methods :

 -------------------------------------------
 -- SOLUTION 1 : modifying the autoref table
 -------------------------------------------
 -- adding the bounds
 ALTER TABLE T_VEHICULE ADD VHC_BORNE_GAUCHE INT;
 ALTER TABLE T_VEHICULE ADD VHC_BORNE_DROITE INT;
GO
 -- updating the bounds
 UPDATE T_VEHICULE
 SET    VHC_BORNE_GAUCHE = PIL_BG,
        VHC_BORNE_DROITE = PIL_BD
 FROM  T_VEHICULE AS V
      INNER JOIN T_PILE AS P
             ON V.VHC_ID = P.PIL_ID;
GO
 ----------------------------------
 -- SOLUTION 2 : adding a new table
 ----------------------------------
 -- creating the new table to manage the interval model
 -- with a referential integrity to the autoref one
 CREATE TABLE T_VEHICULE_INTERVAL_VHI
 (VHC_ID INT NOT NULL PRIMARY KEY,
 VHI_BG INT NOT NULL,
 VHI_BD INT NOT NULL,
 CONSTRAINT FK_VHC FOREIGN KEY(VHC_ID)
                    REFERENCES T_VEHICULE (VHC_ID));
 GO
 -- inserting bounds
 INSERT INTO T_VEHICULE_INTERVAL_VHI
 SELECT PIL_ID, PIL_BD, PIL_BG
 FROM   T_PILE;
GO
   

2) adding and calculating level

At last we can add level's information in the table :

 -- adding the level columns in the tree table
 ALTER TABLE T_VEHICULE ADD VHC_NIVEAU INT;
GO
 -- updating the level column
 UPDATE T_VEHICULE
 SET    VHC_NIVEAU =
           COALESCE(
             (SELECT COUNT(*)
             FROM   T_VEHICULE AS VC1
                     INNER JOIN T_VEHICULE AS VC2
                           ON     VC2.VHC_BORNE_GAUCHE < VC1.VHC_BORNE_GAUCHE
                              AND VC2.VHC_BORNE_DROITE > VC1.VHC_BORNE_DROITE
               WHERE  VC1.VHC_ID = VHC.VHC_ID
               GROUP BY VC1.VHC_ID
            ),  0)
 FROM   T_VEHICULE VHC
GO

3) adding a view to reproduce the autoref table from an interval model table

The problem is : we have a interval model table for a tree and we want to have it, for some needs (like using some graphical components which usually use an auto ref representation) as an autoref table. Can wee do that ? For sure, here is a method...

This is the SQL view doing the job. No difficulties !

 CREATE VIEW dbo.V_VEHICULE_AUTOREF
 AS
 SELECT VHC.*,
 -- calculating father
        (SELECT VHC_ID
         FROM   dbo.T_VEHICULE T
        WHERE  T.VHC_BORNE_GAUCHE < VHC.VHC_BORNE_GAUCHE
          AND  T.VHC_BORNE_DROITE > VHC.VHC_BORNE_DROITE
           AND  T.VHC_NIVEAU = VHC.VHC_NIVEAU -1)AS VHC_ID_PERE
 FROM   dbo.T_VEHICULE VHC;
GO

3) Hierarchical numbering of items in a tree

Recently, Mr. Bruno Petit from Gomez Technologies Corp. asked me this question : in a tree, is it possible to number the elements as a hierarchical matter content table ?

It is a very interesting feature to number a tree in a hierarchical style. You can create a good representation of, for instance, numbering sections such as chapters, items, paragraphs ... from a scriptural document.

This can be seen like this :

N        VHC_NAME
-------- ----------------
1        ALL
1.1      SEA
1.1.1    SUBMARINE
   1.1.2    BOAT
1.2      EARTH
1.2.1    CAR
1.2.2    TWO WHEELES
1.2.2.1  MOTORCYCLE
1.2.2.2  BICYCLE
1.2.3    TRUCK
1.3      AIR
1.3.1    ROCKET
1.3.2    PLANE

For this I proceed in two steps :

  • First, I create a function that calculates the ordinal position regarding any younger brother nodes
  • Second, I use a recursive query with the CTA technique to concatenate the different collateral indexes

The collateral function :

 CREATE FUNCTION dbo.F_COUNTCOLLATERAUX (@VHC_BORNE_GAUCHE INT, @VHC_ID_PERE INT)
 RETURNS INT
 AS
 BEGIN
   RETURN (SELECT COUNT(*)
          FROM   dbo.V_VEHICULE_AUTOREF AS T
          WHERE  T.VHC_ID_PERE = @VHC_ID_PERE
             AND  T.VHC_BORNE_GAUCHE <= @VHC_BORNE_GAUCHE);
 END;
GO

The query that does the hierarchical numbering :

 WITH T AS
 (
 SELECT VHC_ID, VHC_ID_PERE,
      VHC_BORNE_GAUCHE, VHC_BORNE_DROITE,
        VHC_NIVEAU, VHC_NAME,
        CAST(dbo.F_COUNTCOLLATERAUX (VHC_BORNE_GAUCHE, VHC_ID_PERE)+ 1
             AS VARCHAR(max))AS N
 FROM   dbo.V_VEHICULE_AUTOREF AS TOUT1
 WHERE  VHC_ID_PERE IS NULL
 UNION ALL
 SELECT TIN2.VHC_ID, TIN2.VHC_ID_PERE,
      TIN2.VHC_BORNE_GAUCHE, TIN2.VHC_BORNE_DROITE,
        TIN2.VHC_NIVEAU, TIN2.VHC_NAME,
        N +'.' +
        CAST(dbo.F_COUNTCOLLATERAUX (TIN2.VHC_BORNE_GAUCHE, TIN2.VHC_ID_PERE)
             AS VARCHAR(32))AS N
 FROM   dbo.V_VEHICULE_AUTOREF AS TIN2
       INNER JOIN T
            ON TIN2.VHC_ID_PERE = T.VHC_ID
 )
 SELECT N, SPACE(VHC_NIVEAU)+ VHC_NAME AS VHC_NAME
 FROM   T
 ORDER BY VHC_BORNE_GAUCHE;

And the result :

N        VHC_NAME
 -------- ------------
 1        ALL
 1.1      SEA
 1.1.1    SUBMARINE
 1.1.2    BOAT
 1.2      EARTH
 1.2.1    CAR
 1.2.2    TWO WHEELES
 1.2.2.1  MOTORCYCLE
 1.2.2.2  BICYCLE
 1.2.3    TRUCK
 1.3      AIR
1.3.1     ROCKET
1.3.2     PLANE

LAST, but not least...

SQL Server 2008 seems to have a new Transact SQL type for hierarchies. I did not have test it actually. Time seems to be missing for me !

This will be done in a future paper comparing these 5 models :

  • autoref
  • interval
  • hierarchies type
  • path model
  • xml doc

You now should know the first two of these four models. The third one is from SQL Server 2008. The "path model" is the one in which you add a column with the complete path from the root to the node for each item. The last one (XML) is the same as the "path model" in an XML doc.


SQL Server MVPBy Frédéric Brouard - MVP SQL Server

SQL and RDBMS expert, author of :

SQL, Développement, Campus Press 2001

SQL, collection Synthex, Pearson Education 2005, co writer Christian Soutou

http://sqlpro.developpez.com (the most important French web site about the SQL language and RDBMS)

Teacher at Arts & Métiers University and ISEN (engineer school) Toulon

Rate

4.11 (9)

You rated this post out of 5. Change rating

Share

Share

Rate

4.11 (9)

You rated this post out of 5. Change rating