CTEs and Trees

By Frédéric BROUARD, 2007/12/26

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
-------------------------------------------
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
```

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.

By 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: 5380 | 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

Tags
 common table expression (cte) t-sql

Join the most active online SQL Server Community

SQL knowledge, delivered daily, free:

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.