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