Différences

Ci-dessous, les différences entre deux révisions de la page.

--- informatique:databases:mysql:stockage_utilisation_hierarchie [2024/11/21 18:37] – supprimée - modification externe (Date inconnue) 127.0.0.1
+++ informatique:databases:mysql:stockage_utilisation_hierarchie [2024/11/21 18:37] (Version actuelle) – ↷ Page déplacée de informatique:mysql:stockage_utilisation_hierarchie à informatique:databases:mysql:stockage_utilisation_hierarchie alexis
@@ Ligne 1: / Ligne 1: @@
+====== Stockage et utilisation d'une hiérarchie de données ======
+<WRAP info>
+Cette page contient une traduction partielle d'un article proposé sur //mysql.com//.
+Malheureusement, celui-ci a été supprimé mais on peut encore en trouver une copie sur //[[https://web.archive.org/web/20101206231732/http://dev.mysql.com/tech-resources/articles/hierarchical-data.html|archive.org]]//.
+Cette traduction a été faite en utilisant [[https://www.deepl.com/translator|DeepL]], par conséquent, il se peux que certaines traductions soient approximatives.
+J'ai essayé de reprendre la plus part du texte généré mais il se peut que j'ai oublié certains passages.
+Certaines parties ont été complètement supprimées car elle étaient soit obsolètes soit inutiles.
+</WRAP>
+===== Introduction =====
+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 :
+{{drawio>informatique:mysql:hierarchical-data-tree-1}}
+Ces catégories forment une hiérarchie à peu près comme les autres exemples cités ci-dessus.
+===== Modèle de liste adjacente =====
+Généralement, les catégories d'exemple présentées ci-dessus seront stockées dans un tableau comme le suivant :
+<WRAP prewrap>
+<file sql adjacency.list.tree.sql>
+CREATE TABLE category(
+    category_id INT AUTO_INCREMENT PRIMARY KEY,
+    name VARCHAR(20) NOT NULL,
+    parent INT DEFAULT NULL
+);
+INSERT INTO category VALUES
+    (1, 'ELECTRONICS', NULL),
+    (2, 'TELEVISIONS', 1),
+    (3, 'TUBE', 2),
+    (4, 'LCD', 2),
+    (5, 'PLASMA', 2),
+    (6, 'PORTABLE ELECTRONICS', 1),
+    (7, 'MP3 PLAYERS', 6),
+    (8, 'FLASH', 7),
+    (9, 'CD PLAYERS', 6),
+    (10, '2 WAY RADIOS', 6);
+SELECT *
+FROM category
+ORDER BY category_id;
+</file>
+</WRAP>
+^ category_id ^ name                 ^ parent ^
+|           1 | ELECTRONICS          |   NULL |
+|           2 | TELEVISIONS          |      1 |
+|           3 | TUBE                 |      2 |
+|           4 | LCD                  |      2 |
+|           5 | PLASMA               |      2 |
+|           6 | PORTABLE ELECTRONICS |      1 |
+|           7 | MP3 PLAYERS          |      6 |
+|           8 | FLASH                |      7 |
+|           9 | CD PLAYERS           |      6 |
+|          10 | 2 WAY RADIOS         |      6 |
+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.
+==== Récupération d'un arbre complet ====
+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 :
+<WRAP prewrap>
+<code sql>
+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';
+</code>
+</WRAP>
+^ lev1        ^ lev2                 ^ lev3         ^ lev4  ^
+| ELECTRONICS | TELEVISIONS          | TUBE         | NULL  |
+| ELECTRONICS | TELEVISIONS          | LCD          | NULL  |
+| ELECTRONICS | TELEVISIONS          | PLASMA       | NULL  |
+| ELECTRONICS | PORTABLE ELECTRONICS | MP3 PLAYERS  | FLASH |
+| ELECTRONICS | PORTABLE ELECTRONICS | CD PLAYERS   | NULL  |
+| ELECTRONICS | PORTABLE ELECTRONICS | 2 WAY RADIOS | NULL  |
+==== Trouver tous les nœuds feuille ====
+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 :
+<WRAP prewrap>
+<code sql>
+SELECT t1.name
+FROM category AS t1
+LEFT JOIN category as t2 ON t1.category_id = t2.parent
+WHERE t2.category_id IS NULL;
+</code>
+</WRAP>
+^ name         ^
+| TUBE         |
+| LCD          |
+| PLASMA       |
+| FLASH        |
+| CD PLAYERS   |
+| 2 WAY RADIOS |
+==== Retrouver un chemin unique ====
+L'auto-jointure nous permet également de voir le chemin complet à travers nos hiérarchies :
+<WRAP prewrap>
+<code sql>
+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';
+</code>
+</WRAP>
+^ lev1        ^ lev2                 ^ lev3        ^ lev4  ^
+| ELECTRONICS | PORTABLE ELECTRONICS | MP3 PLAYERS | 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.
+==== Limites du modèle de liste adjacente ====
+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.
+===== Modèle d'ensembles imbriqués =====
+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 :
+{{drawio>informatique:mysql:hierarchical-data-nested-set-1}}
+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 :
+<WRAP prewrap>
+<file sql nested.set.tree.sql>
+CREATE TABLE nested_category (
+    category_id INT AUTO_INCREMENT PRIMARY KEY,
+    name VARCHAR(20) NOT NULL,
+    lft INT NOT NULL,
+    rgt INT NOT NULL
+);
+INSERT INTO nested_category VALUES
+    (1, 'ELECTRONICS', 1, 20),
+    (2, 'TELEVISIONS', 2, 9),
+    (3, 'TUBE', 3, 4),
+    (4, 'LCD', 5, 6),
+    (5, 'PLASMA', 7, 8),
+    (6, 'PORTABLE ELECTRONICS', 10, 19),
+    (7, 'MP3 PLAYERS', 11, 14),
+    (8, 'FLASH', 12, 13),
+    (9, 'CD PLAYERS', 15, 16),
+    (10, '2 WAY RADIOS', 17, 18);
+SELECT *
+FROM nested_category
+ORDER BY category_id;
+</file>
+</WRAP>
+^ category_id ^ name                 ^ lft ^ rgt ^
+|           1 | ELECTRONICS          |   1 |  20 |
+|           2 | TELEVISIONS          |   2 |   9 |
+|           3 | TUBE                 |   3 |   4 |
+|           4 | LCD                  |   5 |   6 |
+|           5 | PLASMA               |   7 |   8 |
+|           6 | PORTABLE ELECTRONICS |  10 |  19 |
+|           7 | MP3 PLAYERS          |  11 |  14 |
+|           8 | FLASH                |  12 |  13 |
+|           9 | CD PLAYERS           |  15 |  16 |
+|          10 | 2 WAY RADIOS         |  17 |  18 |
+Nous utilisons //lft// et //rgt// parce que //left// et //right// sont des mots réservés à MySQL, voir la [[https://dev.mysql.com/doc/refman/5.7/en/keywords.html|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 :
+{{drawio>informatique:mysql:hierarchical-data-nested-set-2}}
+Cette conception peut également être appliquée à un arbre classique :
+{{drawio>informatique:mysql:hierarchical-data-tree-2}}
+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é.
+==== Récupération d'un arbre complet ====
+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 :
+<WRAP prewrap>
+<code sql>
+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;
+</code>
+</WRAP>
+^ name                 ^
+| ELECTRONICS          |
+| TELEVISIONS          |
+| TUBE                 |
+| LCD                  |
+| PLASMA               |
+| PORTABLE ELECTRONICS |
+| MP3 PLAYERS          |
+| FLASH                |
+| CD PLAYERS           |
+| 2 WAY RADIOS         |
+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 feuille ====
+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.
+<WRAP prewrap>
+<code sql>
+SELECT name
+FROM nested_category
+WHERE rgt = lft + 1;
+</code>
+</WRAP>
+^ name         ^
+| TUBE         |
+| LCD          |
+| PLASMA       |
+| FLASH        |
+| CD PLAYERS   |
+| 2 WAY RADIOS |
+==== Retrouver un chemin unique ====
+Avec le modèle d'ensemble imbriqué, nous pouvons retrouver un seul chemin sans avoir de multiples auto-jointures :
+<WRAP prewrap>
+<code sql>
+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;
+</code>
+</WRAP>
+^ name                 ^
+| ELECTRONICS          |
+| PORTABLE ELECTRONICS |
+| MP3 PLAYERS          |
+| FLASH                |
+==== Trouver la profondeur des nœuds ====
+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 :
+<WRAP prewrap>
+<code sql>
+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;
+</code>
+</WRAP>
+^ name                 ^ depth ^
+| ELECTRONICS          |     0 |
+| TELEVISIONS          |     1 |
+| TUBE                 |     2 |
+| LCD                  |     2 |
+| PLASMA               |     2 |
+| PORTABLE ELECTRONICS |     1 |
+| MP3 PLAYERS          |     2 |
+| FLASH                |     3 |
+| CD PLAYERS           |     2 |
+| 2 WAY RADIOS         |     2 |
+Nous pouvons utiliser la valeur de profondeur pour indenter nos noms de catégorie avec les fonctions de chaîne __CONCAT__ et __REPEAT__ :
+<WRAP prewrap>
+<code sql>
+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;
+</code>
+</WRAP>
+^ name                  ^
+| ELECTRONICS           |
+| …TELEVISIONS          |
+| ……TUBE                |
+| ……LCD                 |
+| ……PLASMA              |
+| …PORTABLE ELECTRONICS |
+| ……MP3 PLAYERS         |
+| ………FLASH              |
+| ……CD PLAYERS          |
+| ……2 WAY RADIOS        |
+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 [[https://developer.mozilla.org/fr/docs/Web/HTML/Element/li|<li>]] et [[https://developer.mozilla.org/fr/docs/Web/HTML/Element/ul|<ul>]] à mesure que le nombre de profondeur augmente et diminue.
+==== Trouver la profondeur d'un sous-arbre ====
+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 :
+<WRAP prewrap>
+<code sql>
+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;
+</code>
+</WRAP>
+^ name                 ^ depth ^
+| PORTABLE ELECTRONICS |     0 |
+| MP3 PLAYERS          |     1 |
+| FLASH                |     2 |
+| CD PLAYERS           |     1 |
+| 2 WAY RADIOS         |     1 |
+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é.
+==== Trouver les enfants immédiats d'un nœud ====
+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 :
+<WRAP prewrap>
+<code sql>
+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;
+</code>
+</WRAP>
+^ name                  ^ depth  ^
+| PORTABLE ELECTRONICS  | 0      |
+| MP3 PLAYERS           | 1      |
+| CD PLAYERS            | 1      |
+| 2 WAY RADIOS          | 1      |
+Si vous ne souhaitez pas afficher le nœud parent, changez la ligne ''HAVING depth <nowiki><=</nowiki> 1'' par ''HAVING depth = 1''.
+==== Fonctions d’agrégation dans un ensemble imbriqué ====
+Ajoutons une table de produits que nous pouvons utiliser avec des fonctions agrégées :
+<WRAP prewrap>
+<code sql>
+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;
+</code>
+</WRAP>
+^ product_id  ^ name               ^ category_id  ^
+| 1           | 20" TV             | 3            |
+| 2           | 36" TV             | 3            |
+| 3           | Super-LCD 42"      | 4            |
+| 4           | Ultra-Plasma 62"   | 5            |
+| 5           | Value Plasma 38"   | 5            |
+| 6           | Power-MP3 128mb    | 7            |
+| 7           | Super-Shuffle 1gb  | 8            |
+| 8           | Porta CD           | 9            |
+| 9           | CD To go!          | 9            |
+| 10          | Family Talk 360    | 10           |
+Produisons maintenant une requête qui récupère notre arbre de catégories, ainsi que le nombre de produits pour chaque catégorie :
+<WRAP prewrap>
+<code sql>
+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;
+</code>
+</WRAP>
+^ name                 ^ COUNT(product.name) ^
+| ELECTRONICS          |                  10 |
+| TELEVISIONS          |                   5 |
+| TUBE                 |                   2 |
+| LCD                  |                   1 |
+| PLASMA               |                   2 |
+| PORTABLE ELECTRONICS |                   5 |
+| MP3 PLAYERS          |                   2 |
+| FLASH                |                   1 |
+| CD PLAYERS           |                   2 |
+| 2 WAY RADIOS         |                   1 |
+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.
+==== Ajout d'un nœud ====
+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 :
+{{drawio>informatique:mysql:hierarchical-data-nested-set-2}}
+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, <del>je vais supposer pour le moment que la plupart des lecteurs utilisent la version 4.1, car c'est la dernière version stable</del>, je vais isoler mes requêtes avec une instruction __LOCK TABLES__ à la place :
+<WRAP prewrap>
+<code sql>
+-- 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;
+</code>
+</WRAP>
+Nous pouvons alors vérifier notre arborescence grâce à notre requête d'arbre avec indentation :
+<WRAP prewrap>
+<code sql>
+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;
+</code>
+</WRAP>
+^ name                  ^
+| ELECTRONICS           |
+| …TELEVISIONS          |
+| ……TUBE                |
+| ……LCD                 |
+| ……PLASMA              |
+| …GAME CONSOLES        |
+| …PORTABLE ELECTRONICS |
+| ……MP3 PLAYERS         |
+| ………FLASH              |
+| ……CD PLAYERS          |
+| ……2 WAY RADIOS        |
+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// :
+<WRAP prewrap>
+<code sql>
+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;
+</code>
+</WRAP>
+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é :
+<WRAP prewrap>
+<code sql>
+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;
+</code>
+</WRAP>
+^ name                  ^
+| ELECTRONICS           |
+| …TELEVISIONS          |
+| ……TUBE                |
+| ……LCD                 |
+| ……PLASMA              |
+| …GAME CONSOLES        |
+| …PORTABLE ELECTRONICS |
+| ……MP3 PLAYERS         |
+| ………FLASH              |
+| ……CD PLAYERS          |
+| ……2 WAY RADIOS        |
+| ………FRS                |
+==== Suppression d'un nœud ====
+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 :
+<WRAP prewrap>
+<code sql>
+-- 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;
+</code>
+</WRAP>
+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 :
+<WRAP prewrap>
+<code sql>
+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;
+</code>
+</WRAP>
+^ name                  ^
+| ELECTRONICS           |
+| …TELEVISIONS          |
+| ……TUBE                |
+| ……LCD                 |
+| ……PLASMA              |
+| …PORTABLE ELECTRONICS |
+| ……MP3 PLAYERS         |
+| ………FLASH              |
+| ……CD PLAYERS          |
+| ……2 WAY RADIOS        |
+| ………FRS                |
+Cette approche fonctionne tout aussi bien pour supprimer un nœud et tous ses enfants :
+<WRAP prewrap>
+<code sql>
+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;
+</code>
+</WRAP>
+Et une fois de plus, nous exécutons notre requête pour valider que nous avons réussi à supprimer un sous-arbre entier :
+<WRAP prewrap>
+<code sql>
+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;
+</code>
+</WRAP>
+^ name                  ^
+| ELECTRONICS           |
+| …TELEVISIONS          |
+| ……TUBE                |
+| ……LCD                 |
+| ……PLASMA              |
+| …PORTABLE ELECTRONICS |
+| ……CD PLAYERS          |
+| ……2 WAY RADIOS        |
+| ………FRS                |
+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é :
+<WRAP prewrap>
+<code sql>
+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;
+</code>
+</WRAP>
+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 :
+<WRAP prewrap>
+<code sql>
+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;
+</code>
+</WRAP>
+^ name          ^
+| ELECTRONICS   |
+| …TELEVISIONS  |
+| ……TUBE        |
+| ……LCD         |
+| ……PLASMA      |
+| …CD PLAYERS   |
+| …2 WAY RADIOS |
+| ……FRS         |
+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.
+===== Autres ressources =====
+  * [[https://sqlpro.developpez.com/cours/arborescence/|Représentation intervallaire des arborescences]]
+  * [[https://web.archive.org/web/20101207084854/http://articles.sitepoint.com/article/hierarchical-data-database/|Storing Hierarchical Data in a Database]]
+====== Manipulations de données supplémentaires ======
+<WRAP info>
+Ces manipulations ne sont pas abordées dans l'article traduit, c'est pourquoi elles sont regroupées ici.
+</WRAP>
+===== Retrouver un chemin unique sans le nœud =====
+<WRAP prewrap>
+<code sql>
+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'
+AND node.category_id <> parent.category_id
+ORDER BY parent.lft;
+</code>
+</WRAP>
+^ name                 ^
+| ELECTRONICS          |
+| PORTABLE ELECTRONICS |
+| MP3 PLAYERS          |
+===== Retrouver le parent immédiat d'un nœud =====
+<WRAP prewrap>
+<code sql>
+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'
+AND node.category_id <> parent.category_id
+ORDER BY parent.lft DESC
+LIMIT 1;
+</code>
+</WRAP>
+^ name        ^
+| MP3 PLAYERS |
+===== Déplacement d'un nœud =====
+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é.
+<WRAP prewrap>
+<code sql>
+-- 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;
+</code>
+</WRAP>
+^ name                  ^
+| ELECTRONICS           |
+| …TELEVISIONS          |
+| ……TUBE                |
+| ……LCD                 |
+| ……PLASMA              |
+| …GAME CONSOLES        |
+| …PORTABLE ELECTRONICS |
+| ……MP3 PLAYERS         |
+| ………FLASH              |
+| ……2 WAY RADIOS        |
+| ………FRS                |
+| …CD PLAYERS           |
+===== Transformation d'un nœud en nœud racine =====
+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.
+<WRAP prewrap>
+<code sql>
+-- 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;
+</code>
+</WRAP>
+^ name                 ^
+| ELECTRONICS          |
+| …TELEVISIONS         |
+| ……TUBE               |
+| ……LCD                |
+| ……PLASMA             |
+| …GAME CONSOLES       |
+| PORTABLE ELECTRONICS |
+| …MP3 PLAYERS         |
+| ……FLASH              |
+| …CD PLAYERS          |
+| …2 WAY RADIOS        |
+| ……FRS                |