La plupart des utilisateurs ont, à un moment ou à un autre, traité des données hiérarchiques dans une base de données SQL et ont sans doute appris que la gestion de données hiérarchiques n'est pas ce à quoi une base de données relationnelle est destinée. Les tableaux d'une base de données relationnelle ne sont pas hiérarchiques (comme XML), mais sont simplement une liste plate. Les données hiérarchiques ont une relation parent-enfant qui n'est pas naturellement représentée dans une table de base de données relationnelle.

Pour nos besoins, les données hiérarchiques sont une collection de données où chaque élément a un seul parent et zéro ou plusieurs enfants (à l'exception de l'élément racine, qui n'a pas de parent). Les données hiérarchiques peuvent être trouvées dans une variété d'applications de base de données, y compris les fils de discussion des forums et des listes de diffusion, les organigrammes d'entreprises, les catégories de gestion de contenu et les catégories de produits. Pour nos besoins, nous utiliserons la hiérarchie de catégories de produits suivante, provenant d'un magasin d'électronique fictif :

Ces catégories forment une hiérarchie à peu près comme les autres exemples cités ci-dessus.

Généralement, les catégories d'exemple présentées ci-dessus seront stockées dans un tableau comme le suivant :

Dans le modèle de liste adjacente, chaque élément du tableau contient un pointeur vers son parent. L'élément le plus haut, dans ce cas l'électronique, a une valeur nulle pour son parent. Le modèle de liste adjacente a l'avantage d'être assez simple, il est facile de voir que FLASH est un enfant des lecteurs mp3, qui est un enfant de l'électronique portable, qui est un enfant de l'électronique. Alors que le modèle de liste adjacente peut être traité assez facilement dans le code côté client, travailler avec ce modèle peut être plus problématique en SQL pur.

La première tâche courante lorsqu'on traite des données hiérarchiques est l'affichage de l'arbre entier, généralement avec une certaine forme d'indentation. La façon la plus courante de le faire en SQL pur est d'utiliser une auto-jointure :

SELECT t1.name AS lev1
, t2.name AS lev2
, t3.name AS lev3
, t4.name AS lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
LEFT JOIN category AS t4 ON t4.parent = t3.category_id
WHERE t1.name = 'ELECTRONICS';

Nous pouvons trouver tous les nœuds feuilles de notre arbre (ceux qui n'ont pas d'enfants) en utilisant une requête avec une jointure gauche :

SELECT t1.name
FROM category AS t1
LEFT JOIN category AS t2 ON t1.category_id = t2.parent
WHERE t2.category_id IS NULL;

L'auto-jointure nous permet également de voir le chemin complet à travers nos hiérarchies :

SELECT t1.name AS lev1
, t2.name AS lev2
, t3.name AS lev3
, t4.name AS lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
LEFT JOIN category AS t4 ON t4.parent = t3.category_id
WHERE t1.name = 'ELECTRONICS' AND t4.name = 'FLASH';

La principale limite d'une telle approche est qu'il faut une auto-jointure pour chaque niveau de la hiérarchie et les performances se dégraderont naturellement avec chaque niveau ajouté à mesure que la jointure deviendra plus complexe.

Travailler avec le modèle de liste adjacente en SQL pur peut être difficile. Avant de pouvoir voir le chemin complet d'une catégorie, nous devons connaître le niveau auquel elle se trouve. En outre, il faut être particulièrement attentif lors de la suppression de nœuds en raison du risque de création d'orphelin d'un sous-arbre entier au cours du processus (supprimer la catégorie de l'électronique portable rend tous ses enfants orphelins). Certaines de ces limitations peuvent être résolues par l'utilisation de codes côté client ou de procédures stockées. Avec un langage procédural, nous pouvons commencer au bas de l'arbre et itérer vers le haut pour revenir à l'arbre complet ou à un seul chemin. Nous pouvons également utiliser la programmation procédurale pour supprimer des nœuds sans rendre orphelins des sous-arbres entiers en favorisant un élément enfant et en réordonnant les enfants restants pour qu'ils pointent vers le nouveau parent.

Dans le modèle d'ensembles imbriqués, nous pouvons considérer notre hiérarchie d'une nouvelle manière, non pas comme des nœuds et des lignes, mais comme des conteneurs imbriqués. Essayez d'imaginer nos catégories électroniques de cette manière :

Remarquez comment notre hiérarchie est toujours maintenue, puisque les catégories de parents enveloppent leurs enfants. Nous représentons cette forme de hiérarchie dans un tableau en utilisant des valeurs de gauche et de droite pour représenter l'emboîtement de nos nœuds :

Nous utilisons lft et rgt parce que left et right sont des mots réservés à MySQL, voir la liste complète des mots réservés.

Alors comment déterminer les valeurs de gauche et de droite ? Nous commençons à numéroter du côté le plus à gauche du nœud extérieur et nous continuons vers la droite :

Cette conception peut également être appliquée à un arbre classique :

Lorsque l'on travaille avec un arbre, on travaille de gauche à droite, une couche à la fois, en descendant vers les enfants de chaque nœud avant d'attribuer un numéro à droite et de se déplacer vers la droite. Cette approche est appelée l'algorithme de traversée d'arbre pré-ordonné modifié.

Nous pouvons récupérer l'arbre complet grâce à l'utilisation d'un auto-jointure qui relie les parents aux nœuds sur la base que la valeur lft d'un nœud apparaîtra toujours entre les valeurs lft et rgt de son parent :

SELECT node.name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND parent.name = 'ELECTRONICS'
ORDER BY node.lft;

Contrairement à nos précédents exemples avec le modèle de liste adjacente, cette requête fonctionnera quelle que soit la profondeur de l'arbre. Nous ne nous préoccupons pas de la valeur rgt du nœud dans notre clause BETWEEN, car la valeur rgt sera toujours comprise dans le même parent que les valeurs lft.

Trouver tous les nœuds de feuilles dans le modèle d'ensemble imbriqué est encore plus simple que la méthode utilisée dans le modèle de liste adjacente. Si vous regardez le tableau, vous pouvez remarquer que les valeurs lft et rgt pour les nœuds de feuilles sont des nombres consécutifs.

SELECT name
FROM nested_category
WHERE rgt = lft + 1;

Avec le modèle d'ensemble imbriqué, nous pouvons retrouver un seul chemin sans avoir de multiples auto-jointures :

SELECT parent.name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.name = 'FLASH'
ORDER BY parent.lft;

Nous avons déjà examiné comment montrer l'arbre entier, mais que faire si nous voulons également montrer la profondeur de chaque nœud de l'arbre, pour mieux identifier comment chaque nœud s'insère dans la hiérarchie ? Cela peut être fait en ajoutant une fonction COUNT et une clause GROUP BY à notre requête existante pour afficher l'arbre entier :

SELECT node.name
, (COUNT(parent.name) - 1) AS depth
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

Nous pouvons utiliser la valeur de profondeur pour indenter nos noms de catégorie avec les fonctions de chaîne CONCAT et REPEAT :

SELECT CONCAT( REPEAT('…', COUNT(parent.name) - 1), node.name) AS name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

Bien entendu, dans une application cliente, vous serez plus enclin à utiliser directement la valeur de profondeur pour afficher votre hiérarchie. Les développeurs web pourraient faire une boucle dans l'arborescence, en ajoutant les balises <li> et <ul> à mesure que le nombre de profondeur augmente et diminue.

Lorsque nous avons besoin d'informations de profondeur pour un sous-arbre, nous ne pouvons limiter ni le nœud ni les tables parentes dans notre auto-jointure car cela corromprait nos résultats. Au lieu de cela, nous ajoutons une troisième auto-jointure, ainsi qu'une sous-requête pour déterminer la profondeur qui sera le nouveau point de départ de notre sous-arbre :

SELECT node.name
, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
FROM nested_category AS node,
    nested_category AS parent,
    nested_category AS sub_parent,
    (
        SELECT node.name
        , (COUNT(parent.name) - 1) AS depth
        FROM nested_category AS node,
        nested_category AS parent
        WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.name = 'PORTABLE ELECTRONICS'
        GROUP BY node.name
        ORDER BY node.lft
    ) AS sub_tree
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
AND sub_parent.name = sub_tree.name
GROUP BY node.name
ORDER BY node.lft;

Cette fonction peut être utilisée avec n'importe quel nom de nœud, y compris le nœud racine. Les valeurs de profondeur sont toujours relatives au nœud nommé.

Imaginez que vous présentez une catégorie de produits électroniques sur le site web d'un détaillant. Lorsqu'un utilisateur clique sur une catégorie, vous souhaitez afficher les produits de cette catégorie, ainsi que la liste de ses sous-catégories immédiates, mais pas l'arbre entier des catégories. Pour cela, nous devons afficher le nœud et ses sous-nœuds immédiats uniquement. Par exemple, lorsque nous affichons la catégorie ÉLECTRONIQUE PORTABLE, nous voulons afficher les catégories LECTEURS MP3, LECTEURS CD et RADIOS 2 VOIES, mais pas la catégorie FLASH.

Cela peut être facilement réalisé en ajoutant une clause HAVING à notre requête précédente :

SELECT node.name
, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
FROM nested_category AS node,
    nested_category AS parent,
    nested_category AS sub_parent,
    (
        SELECT node.name
        , (COUNT(parent.name) - 1) AS depth
        FROM nested_category AS node,
        nested_category AS parent
        WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.name = 'PORTABLE ELECTRONICS'
        GROUP BY node.name
        ORDER BY node.lft
    ) AS sub_tree
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
AND sub_parent.name = sub_tree.name
GROUP BY node.name
HAVING depth <= 1
ORDER BY node.lft;

Si vous ne souhaitez pas afficher le nœud parent, changez la ligne HAVING depth <= 1 par HAVING depth = 1.

Ajoutons une table de produits que nous pouvons utiliser avec des fonctions agrégées :

CREATE TABLE product (
    product_id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(40),
    category_id INT NOT NULL
);
 
INSERT INTO product (name, category_id) VALUES
    ('20" TV', 3),
    ('36" TV' ,3),
    ('Super-LCD 42"', 4),
    ('Ultra-Plasma 62"', 5),
    ('Value Plasma 38"', 5),
    ('Power-MP3 5gb', 7),
    ('Super-Player 1gb', 8),
    ('Porta CD', 9),
    ('CD To go!', 9),
    ('Family Talk 360', 10);
 
SELECT *
FROM product;

Produisons maintenant une requête qui récupère notre arbre de catégories, ainsi que le nombre de produits pour chaque catégorie :

SELECT parent.name
, COUNT(product.name)
FROM nested_category AS node,
nested_category AS parent,
product
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.category_id = product.category_id
GROUP BY parent.name
ORDER BY node.lft;

C'est notre requête classique de récupération d'arbre entier avec l'ajout de COUNT et GROUP BY et d'une jointure entre le nœud et la table de produits dans la clause WHERE. Comme vous pouvez le voir, il y a un nombre pour chaque catégorie et le nombre de sous-catégories est reflété dans les catégories parentes.

Maintenant que nous avons appris à interroger notre arbre, nous devrions examiner comment le mettre à jour en y ajoutant un nouveau nœud. Examinons à nouveau notre diagramme d'ensembles imbriqués :

Si nous voulions ajouter un nouveau nœud entre les nœuds TELEVISIONS et ELECTRONIQUE PORTABLE, le nouveau nœud aurait des valeurs lft et rgt de 10 et 11, et tous les nœuds à sa droite auraient leurs valeurs lft et rgt augmentées de deux. Nous ajouterions alors le nouveau nœud avec les valeurs lft et rgt appropriées. Bien que cela puisse être fait avec une procédure stockée dans MySQL 5, je vais supposer pour le moment que la plupart des lecteurs utilisent la version 4.1, car c'est la dernière version stable, je vais isoler mes requêtes avec une instruction LOCK TABLES à la place :

-- Verrouillage en écriture de la table
LOCK TABLE nested_category WRITE;
 
-- Récupération des informations de l'élément parent
SELECT @myRight := rgt
FROM nested_category
WHERE name = 'TELEVISIONS';
 
-- Mise à jour des bornes droites des éléments concernés
UPDATE nested_category
SET rgt = rgt + 2
WHERE rgt > @myRight;
 
-- Mise à jour des bornes gauches des éléments concernés
UPDATE nested_category
SET lft = lft + 2
WHERE lft > @myRight;
 
-- Insertion du nouvel élément
INSERT INTO nested_category (name, lft, rgt) VALUES
    ('GAME CONSOLES', @myRight + 1, @myRight + 2);
 
-- Suppression des verrous
UNLOCK TABLES;

Nous pouvons alors vérifier notre arborescence grâce à notre requête d'arbre avec indentation :

SELECT CONCAT( REPEAT( '…', (COUNT(parent.name) - 1) ), node.name) AS name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

Si nous voulons plutôt ajouter un nœud en tant qu'enfant d'un nœud qui n'a pas d'enfant existant, nous devons modifier légèrement notre procédure. Ajoutons un nouveau nœud FRS sous le nœud 2 WAY RADIOS :

LOCK TABLE nested_category WRITE;
 
SELECT @myLeft := lft
FROM nested_category
 
WHERE name = '2 WAY RADIOS';
 
UPDATE nested_category
SET rgt = rgt + 2 WHERE rgt > @myLeft;
 
UPDATE nested_category
SET lft = lft + 2 WHERE lft > @myLeft;
 
INSERT INTO nested_category(name, lft, rgt) VALUES
    ('FRS', @myLeft + 1, @myLeft + 2);
 
UNLOCK TABLES;

Dans cet exemple, nous développons tout à droite du numéro de gauche de notre nouveau nœud parent, puis nous plaçons le nœud à droite de la valeur de gauche. Comme vous pouvez le voir, notre nouveau nœud est maintenant correctement imbriqué :

SELECT CONCAT( REPEAT( '…', (COUNT(parent.name) - 1) ), node.name) AS name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

La dernière tâche de base impliquée dans le travail avec des ensembles imbriqués est la suppression des nœuds. La marche à suivre pour supprimer un nœud dépend de la position du nœud dans la hiérarchie ; il est plus facile de supprimer des nœuds feuilles que des nœuds enfants, car nous devons nous occuper des nœuds orphelins.

Lors de la suppression d'un nœud de feuille, le processus est tout à fait inverse à celui de l'ajout d'un nouveau nœud ; nous supprimons le nœud et sa largeur de chaque nœud à sa droite :

-- Verrouillage en écriture de la table
LOCK TABLE nested_category WRITE;
 
-- Récupération des informations de l'élément à supprimer
SELECT @myLeft := lft
, @myRight := rgt
, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'GAME CONSOLES';
 
-- Suppression de l'élément
DELETE FROM nested_category
WHERE lft BETWEEN @myLeft AND @myRight;
 
-- Mise à jour des bornes droites des éléments concernés
UPDATE nested_category
SET rgt = rgt - @myWidth
WHERE rgt > @myRight;
 
-- Mise à jour des bornes gauches des éléments concernés
UPDATE nested_category
SET lft = lft - @myWidth
WHERE lft > @myRight;
 
-- Suppression des verrous
UNLOCK TABLES;

Et une fois de plus, nous exécutons notre requête d'arbre avec indentation pour confirmer que notre nœud a été supprimé sans corrompre la hiérarchie :

SELECT CONCAT( REPEAT( '…', (COUNT(parent.name) - 1) ), node.name) AS name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

Cette approche fonctionne tout aussi bien pour supprimer un nœud et tous ses enfants :

LOCK TABLE nested_category WRITE;
 
SELECT @myLeft := lft
, @myRight := rgt
, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'MP3 PLAYERS';
 
DELETE FROM nested_category
WHERE lft BETWEEN @myLeft AND @myRight;
 
UPDATE nested_category
SET rgt = rgt - @myWidth 
WHERE rgt > @myRight;
 
UPDATE nested_category
SET lft = lft - @myWidth
WHERE lft > @myRight;
 
UNLOCK TABLES;

Et une fois de plus, nous exécutons notre requête pour valider que nous avons réussi à supprimer un sous-arbre entier :

SELECT CONCAT( REPEAT( '…', (COUNT(parent.name) - 1) ), node.name) AS name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

L'autre scénario que nous devons traiter est la suppression d'un nœud parent mais pas des enfants. Dans certains cas, il est possible de changer le nom en place jusqu'à ce qu'un remplaçant soit présenté, par exemple lorsqu'un superviseur est licencié. Dans d'autres cas, les nœuds enfants doivent tous être déplacés jusqu'au niveau du parent supprimé :

LOCK TABLE nested_category WRITE;
 
SELECT @myLeft := lft
, @myRight := rgt
, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'PORTABLE ELECTRONICS';
 
DELETE FROM nested_category
WHERE lft = @myLeft;
 
UPDATE nested_category
SET rgt = rgt - 1
, lft = lft - 1
WHERE lft BETWEEN @myLeft AND @myRight;
 
UPDATE nested_category
SET rgt = rgt - 2
WHERE rgt > @myRight;
 
UPDATE nested_category
SET lft = lft - 2
WHERE lft > @myRight;
 
UNLOCK TABLES;

Dans ce cas, nous en soustrayons deux de tous les éléments à droite du nœud (puisque sans les enfants, il aurait une largeur de deux), et un des nœuds qui sont ses enfants (pour combler l'écart créé par la perte de la valeur gauche du parent). Une fois de plus, nous pouvons confirmer que nos éléments ont été promus :

SELECT CONCAT( REPEAT( '…', (COUNT(parent.name) - 1) ), node.name) AS name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

D'autres scénarios de suppression de nœuds incluent la promotion d'un des enfants en position parentale et le déplacement des nœuds enfants sous un frère ou une sœur du nœud parent, mais par souci d'espace, ces scénarios ne seront pas couverts dans cet article.

• Représentation intervallaire des arborescences
• Storing Hierarchical Data in a Database

Ici, on ne couvre que le cas du déplacement d'un nœud vers un nœud qui n'est pas un descendant du nœud traité.

-- Verrouillage en écriture de la table
LOCK TABLE nested_category WRITE;
 
-- Récupération des informations de l'élément à déplacer
SELECT @myLeft := lft
, @myRight := rgt
, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'CD PLAYERS';
 
-- Récupération des informations du nouvel élément parent
SELECT @myNewParentLeft := lft
, @myNewParentRight := rgt
FROM nested_category
WHERE name = 'ELECTRONICS';
 
-- Calcul de la valeur de déplacement de l'élément à déplacer
SELECT @offsetWidth := @myNewParentRight - @myRight - 1 + IF( SIGN( @myNewParentRight - @myRight ) < 1 , @myWidth , 0 );
 
-- Calcul de la borne gauche de déplacement des autres éléments
SELECT @offsetLeft := IF( SIGN( @offsetWidth ) = 1 , @myRight , @myNewParentRight );
 
-- Calcul de la borne droite de déplacement des autres éléments
SELECT @offsetRight := IF( SIGN( @offsetWidth ) = 1 , @myNewParentRight - 1 , @myLeft - 1 );
 
-- Calcul de la valeur de déplacement des autres éléments
SELECT @signedNodeWidth := SIGN( @offsetWidth ) * @myWidth;
 
-- Exclusion temporaire de l'élément à déplacer
UPDATE nested_category
SET lft = -lft
, rgt = -rgt
WHERE lft >= @myLeft
AND rgt <= @myRight;
 
-- Mise à jour des bornes droites des éléments concernés
UPDATE nested_category
SET rgt = rgt - @signedNodeWidth
WHERE rgt BETWEEN @offsetLeft AND @offsetRight;
 
-- Mise à jour des bornes gauches des éléments concernés
UPDATE nested_category
SET lft = lft - @signedNodeWidth
WHERE lft BETWEEN @offsetLeft AND @offsetRight;
 
-- Repositionnement de l'élément à déplacer
UPDATE nested_category
SET lft = -lft + @offsetWidth
, rgt = -rgt + @offsetWidth
WHERE rgt < 0;
 
-- Suppression des verrous
UNLOCK TABLES;

Cela implique de déplacer un nœud ainsi que l'ensemble de ses descendants. Le nœud sélectionné pour être un nouveau nœud racine n'aura, de ce fait, plus de parent. À la fin de la transformation, on aura donc deux arborescences côte à cote.

-- Verrouillage en écriture de la table
LOCK TABLE nested_category WRITE;
 
-- Récupération des informations de l'élément à déplacer
SELECT @myLeft := lft
, @myRight := rgt
, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'PORTABLE ELECTRONICS';
 
-- Récupération des informations de déplacement de l'élément
SELECT @offsetWidth := MAX(rgt) - @myRight
FROM nested_category;
 
-- Exclusion temporaire de l'élément à déplacer
UPDATE nested_category
SET lft = -lft
, rgt = -rgt
WHERE lft >= @myLeft
AND rgt <= @myRight;
 
-- Mise à jour des bornes droites des éléments concernés
UPDATE nested_category
SET rgt = rgt - @myWidth
WHERE rgt >= @myRight;
 
-- Mise à jour des bornes gauches des éléments concernés
UPDATE nested_category
SET lft = lft - @myWidth
WHERE lft >= @myRight;
 
-- Repositionnement de l'élément à déplacer
UPDATE nested_category
SET lft = -lft + @offsetWidth
, rgt = -rgt + @offsetWidth
WHERE rgt < 0;
 
-- Suppression des verrous
UNLOCK TABLES;