Le type hierarchyid a été introduit avec SQL Server 2008. Ce type permet de représenter et manipuler des données hiérarchique. Des données hiérarchiques contiennent la notion de parent/enfant mais également la notion d’ordre entre les éléments ayant le même parent. Les valeurs de ce type sont en fait stockées sous une forme binaire, par exemple 0x5AC0 ou 0x58, mais dans la pratique on utilise des chaines de caractères du type “/” pour la racine ou “/1/” pour un enfant du noeud racine, et ainsi de suite :

noeud racine

Le but de cet article est de présenter les opérations courantes réalisables avec ce type de données.

Création de la table

Pour créer une colonne de type hierarchyid, il n’y a rien de particulier par rapport à d’autres types simples :

CREATE TABLE [dbo].[Employee]( 
     [Id] [int] IDENTITY(1,1) NOT NULL, 
     [FirstName] [nvarchar](50) NOT NULL, 
     [LastName] [nvarchar](50) NOT NULL, 
     [hid] [hierarchyid] NOT NULL, 
 )

On peut également utiliser ce type en tant que clé :

CREATE TABLE [dbo].[Employee]( 
     [Id] [hierarchyid] NOT NULL, 
     [FirstName] [nvarchar](50) NOT NULL, 
     [LastName] [nvarchar](50) NOT NULL 
 )

Insertion de données

Comme indiqué au début, plusieurs méthodes existent pour manipuler le type hierarchyid. Ainsi pour créer un objet de type hierarchyid on peut utiliser :

  • hierarchyid ::Parse (‘/1/1&rsquo ;)
  • CAST (‘/1/’ AS hierarchyid) <=> hierarchyid ::Parse (‘/1/&rsquo ;)
  • hierarchyid ::GetRoot () <=> hierarchyid ::Parse (‘/&rsquo ;)

Pour insérer une ligne dans la table on peut donc utiliser une des commandes suivantes :

INSERT INTO Employee (FirstName, LastName, hid) 
 VALUES ('John', 'Doe', '/') -- conversion implicite 
   
 INSERT INTO Employee (FirstName, LastName, hid) 
 VALUES ('John', 'Doe', hierarchyid::GetRoot()) 
   
 INSERT INTO Employee(FirstName, LastName, hid) 
 VALUES ('John', 'Doe', hierarchyid::Parse('/1/')) 
   
 INSERT INTO Employee(FirstName, LastName, hid) 
 VALUES ('John', 'Doe', CONVERT('/1/' as hierarchyid))

ToString

Le type hierarchyid étant stocké sous forme binaire, le résultat de la commande SELECT n’est pas très lisible :

SELECT * FROM Employee

ToString 1

Pour rendre le résultat lisible par un humain il faut utiliser la méthode ToString :

SELECT [Id], [FirstName], [LastName], [hid].ToString() 
 FROM [Employee]

ToString 2

Comparaison et tri

La comparaison entre 2 hierarchyid est la suivante : A<B signifie que A arrive après B lors d’un parcourt profondeur de l’arbre. Voici des exemples pour illustrer :

  • /1/ = /1/
  • /1/1/ < /1/
  • /1/ < /2/
  • /1/1/ < /2/

Ce tri est intuitif et permet de facilement trier les données :

SELECT [Id], [FirstName], [LastName], [hid].ToString() 
 FROM [Employee] 
 ORDER BY [hid]

Tri et comparaison

GetDescendant

La méthode GetDescendant permet de créer un hierarchyid correspondant à l’enfant d’un autre hierarchyid. Cette méthode a 2 arguments permettant de spécifier l’emplacement de l’enfant (gauche, droite, entre 2 enfants existants) :

hierarchyid 1

SELECT CAST('/1/' AS hierarchyid).GetDescendant(NULL, NULL).ToString() 
 -- /1/1/

Création d’un fils à droite de “/1/2/” :

hierarchyid 2

SELECT CAST('/1/' AS hierarchyid).GetDescendant(CAST('/1/2/' AS hierarchyid), NULL).ToString() 
 -- /1/3/

Création d’un fils à gauche de “/1/2/” :

hierarchyid 3

SELECT CAST('/1/' AS hierarchyid).GetDescendant(NULL, CAST('/1/2/' AS hierarchyid)).ToString() 
 -- /1/1/

Création d’un fils entre “/1/2/” et “/1/3/” :

SELECT CAST('/1/' AS hierarchyid).GetDescendant(CAST('/1/2/' AS hierarchyid), CAST('/1/3/' AS hierarchyid)).ToString() 
 -- /1/2.1/

Création d’un fils entre “/1/1/” et “/1/2/” :

hierarchyid 4

SELECT CAST('/1/' AS hierarchyid).GetDescendant(CAST('/1/1/' AS hierarchyid), CAST('/1/2/' AS hierarchyid)).ToString() 
 -- /1/1.1/

On peut créer autant de sous niveaux que nécessaire et on peut également utiliser des valeurs négatives :

SELECT CAST('/1/' AS hierarchyid).GetDescendant(NULL, CAST('/1/0.0.-1/' AS hierarchyid)).ToString() 
 -- /1/-1/

GetLevel

La méthode GetLevel permet de connaître la profondeur de l’élément dans l’arbre :

SELECT CAST('/' AS hierarchyid).GetLevel() -- 0 
 SELECT CAST('/1/' AS hierarchyid).GetLevel() -- 1 
 SELECT CAST('/1/1/' AS hierarchyid).GetLevel() -- 2 
 SELECT CAST('/1/1.0/' AS hierarchyid).GetLevel() -- 2

Vous vous rappelez de l’article précédent sur les CTE récursive pour afficher la liste complète indentée et triée. Avec le type hierarchyid, la requête est la suivante :

SELECT REPLICATE('--', hid.GetLevel()) + FirstName + ' ' + LastName, hid.ToString() 
 FROM Employee 
 ORDER BY hid

GetLevel

IsDescendantOf

La méthode IsDescendantOf, comme son nom l’indique, permet de déterminer si un hierarchyid est l’enfant d’un autre (quelque soit le niveau dans le hierarchy). Cette requête permet de récupérer tous les éléments dont le parent ou ancêtre est /1/ :

SELECT [Id], [FirstName], [LastName], [hid].ToString() 
 FROM [Employee] 
 WHERE [hid].IsDescendantOf(CAST('/1/' AS hierarchyid)) = 1

IsDescendantOf

GetAncestor

La méthode GetAncestor permet de créer un hierarchyid correspondant au parent de niveau spécifié :

SELECT CAST('/1/2/3.5/' AS hierarchyid).GetAncestor(0).ToString() 
 -- /1/2/3.5/ 
 SELECT CAST('/1/2/3.5/' AS hierarchyid).GetAncestor(1).ToString() 
 -- /1/2/ 
 SELECT CAST('/1/2/3.5/' AS hierarchyid).GetAncestor(2).ToString() 
 -- /1/ 
 SELECT CAST('/1/2/3.5/' AS hierarchyid).GetAncestor(3).ToString() 
 -- / 
 SELECT CAST('/1/2/3.5/' AS hierarchyid).GetAncestor(4).ToString() 
 -- NULL

Sélectionner tous les ancêtres d’un élement

La première requête (mais pas la meilleure) venant à l’esprit pour répondre à cette problématique utilise une CTE récursive :

WITH Ancestors(Id, FirstName, LastName, AncestorId) 
 AS 
 ( 
     SELECT Id, FirstName, LastName, hid.GetAncestor(1) 
     FROM Employee 
     WHERE hid = '/1/2/1/' 
     
     UNION ALL 
     
     SELECT e.Id, e.FirstName, e.LastName, e.hid.GetAncestor(1) 
     FROM Employee e 
     INNER JOIN Ancestors a 
           ON e.hid = a.AncestorId 
 ) 
 SELECT FirstName, LastName, AncestorId.ToString() FROM Ancestors

Maintenant en reformulant la question on se rend compte qu’une requête plus simple existe : Sélectionner tous les élements dont l’élément courant est l’enfant :

SELECT Id, FirstName, LastName, hid.ToString() 
 FROM Employee 
 WHERE CAST('/1/2/1/' as hierarchyid).IsDescendantOf(hid) = 1

Il n’y a jamais qu’une seule façon d’arriver au résultat… Certaines sont plus simple que d’autres :)

GetReparentedValue

La méthode GetReparentedValue permet de déplacer un élément dans l’arbre.

DECLARE @employee as hierarchyid = '/1/1/3/' 
 DECLARE @oldparent as hierarchyid = '/1/1/' 
 DECLARE @newparent as hierarchyid = '/1/2/' 
 SELECT @employee.GetReparentedValue(@oldparent, @newparent).ToString() 
 -- /1/2/3/

Pour déplacer un sous-arbre on peut utiliser la requête suivante :

DECLARE @nold hierarchyid = CAST('/1/' as hierarchyid) -- sous-arbre à déplacer 
 DECLARE @nnew hierarchyid = CAST('/2/' as hierarchyid) -- nouveau parent 
   
 -- Insère en tant que dernier frère 
 -- /@nnew/1/, /@nnew/2/ => /@nnew/3 
 SELECT @nnew = @nnew.GetDescendant(max(hid), NULL) 
 FROM Employee 
 WHERE hid.GetAncestor(1) = @nnew; 
 -- Met à jour les lignes enfants de @nold 
 UPDATE Employee 
 SET hid = hid.GetReparentedValue(@nold, @nnew) 
 WHERE hid.IsDescendantOf(@nold) = 1;

Pour éviter les problèmes ces lignes doivent être placée dans une transaction.

Eviter les noeuds sans parent

Le type hierarchyid indique une position dans une hiérarchie mais ne garantit pas qu’un élément à un parent direct. Les instructions suivantes s’exécutent sans problème :

CREATE TABLE Employee 
 ( 
     Id hierarchyid NOT NULL PRIMARY KEY, 
     Name nvarchar(50) NOT NULL, 
 ) 
 GO 
 INSERT INTO Employee(Id, Name) VALUES ('/', 'John') 
 INSERT INTO Employee(Id, Name) VALUES ('/1/', 'Jane') 
 INSERT INTO Employee(Id, Name) VALUES ('/1/1/', 'Jeff') 
 DELETE FROM Employee WHERE Id = CAST('/1/' AS hierarchyid) -- Aucune erreur

Selon votre besoin, un noeud doit forcément avoir un parent (sauf l’élément racine bien évidemment). La solution est d’ajouter une colonne calculée et persistée correspondant au parent du noeud (méthode GetAncestor (1)). on peut ainsi ajouter une clé étrangère entre cette colonne et la colonne Id :

CREATE TABLE Employee 
 ( 
     Id hierarchyid NOT NULL PRIMARY KEY, 
     Name nvarchar(50) NOT NULL, 
     ManagerId AS Id.GetAncestor(1) PERSISTED REFERENCES Employee(Id), 
 ) 
 GO 
 INSERT INTO Employee(Id, Name) VALUES ('/', 'John') 
 INSERT INTO Employee(Id, Name) VALUES ('/2/', 'Jane') 
 INSERT INTO Employee(Id, Name) VALUES ('/2/1/', 'Jeff') 
 DELETE FROM Employee WHERE Id = CAST('/2/' AS hierarchyid) -- Error

Conclusion

On a maintenant fait le tour des méthodes de l’objet hierarchyid. On a vu qu’il permettait de simplifier certaines requêtes mais il est important de connaitre ses limitations. Une d’entre-elles est sa taille, bien que potentiellement très grande (maximum 892 octets), est limité et ne permet donc pas de sauvegarder des hiérarchies de taille infinie. Il existe d’autres façons de créer une hiérarchie par exemple par représentation intervallaire des arborescences ou les closure tables. A vous de choisir celle qui correspond le mieux à votre besoin.

Ne ratez plus aucune actualité avec la newsletter mensuelle de SoftFluent

Newsletter SoftFluent