Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 

CTEs and Trees

By Frédéric BROUARD,

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

Total article views: 5452 | Views in the last 30 days: 27
 
Related Articles
FORUM

"Select Where In" using a parameter?

select intCol from Tablename where intCol in (@intList)

FORUM

How to select count(*) where count < 4

How to select count(*) where count < 4

FORUM

SELECT statement hangs on certain where conditions

Bizarre issue with certain conditions in where statement cause the select to hang forever

FORUM

Conditional Where Clause

Select how the Where Clause operates

FORUM

Select Where Any Column Equals (or Like) Value

Select row(s) where any of the column names in table equals a value

 
Contribute

Join the most active online SQL Server Community

SQL knowledge, delivered daily, free:

Email address:  

You make SSC a better place

As a member of SQLServerCentral, you get free access to loads of fresh content: thousands of articles and SQL scripts, a library of free eBooks, a weekly database news roundup, a great Q & A platform… And it’s our huge, buzzing community of SQL Server Professionals that makes it such a success.

Join us!

Steve Jones
Editor, SQLServerCentral.com

Already a member? Jump in:

Email address:   Password:   Remember me: Forgotten your password?
Steve Jones