Un peu de libre dans ce monde propriétaire

On y parle de libre, de configuration et d'autres trucs hermétiques à la plupart des personnes

Aller au contenu | Aller au menu | Aller à la recherche

11avr.

Opérations sur la hiérarchie : suite

Les précédents articles[1][2] sur le stockage et la manipulation des hiérarchies dans MySQL sont loin d'être complets. J'y apporte donc un complément avec 2 nouvelles requêtes de manipulations.
On conserve la même table et les même données que dans les articles précédents afin de rester cohérent.

Déplacer un élément

Dans l'article Un peu d'ordre dans la hiérarchie, nous avons déjà abordé le déplacement d'un élément mais juste vers un autre élément de la hiérarchie. Cette fois ci, nous allons aborder le déplacement d'un élément à la racine, c'est à dire qu'il n'aura plus de parent. Nous allons donc déplacer l'élément B vers la racine. Pour cela, il suffit de lancer ces quelques requêtes :

  1. /* Verrouillage en écriture de la table*/
  2. LOCK TABLE tree WRITE;
  3.  
  4. /* Récupération des informations de l'élément à déplacer */
  5. SELECT @nodeLeft := lft
  6. , @nodeRight := rgt
  7. , @nodeRange := rgt - lft + 1
  8. FROM tree
  9. WHERE name = 'B';
  10.  
  11. /* Récupération des informations de déplacement de l'élément */
  12. SELECT @offsetRange := MAX(rgt) - @nodeRight
  13. FROM tree;
  14.  
  15. /* Exclusion temporaire de l'élément à déplacer */
  16. UPDATE tree
  17. SET lft = -lft
  18. , rgt = -rgt
  19. WHERE lft >= @nodeLeft
  20. AND rgt <= @nodeRight;
  21.  
  22. /* Mise à jour des bornes droites des éléments concernés */
  23. UPDATE tree
  24. SET rgt = rgt - @nodeRange
  25. WHERE rgt >= @nodeRight;
  26.  
  27. /* Mise à jour des bornes gauches des éléments concernés */
  28. UPDATE tree
  29. SET lft = lft - @nodeRange
  30. WHERE lft >= @nodeRight;
  31.  
  32. /* Repositionnement de l'élément à déplacer */
  33. UPDATE tree
  34. SET lft = -lft + @offsetRange
  35. , rgt = -rgt + @offsetRange
  36. WHERE rgt < 0;
  37.  
  38. /* Suppression des verrous */
  39. UNLOCK TABLES;

Ce qui nous donne ceci :

+-----------+------+------+----+
| NAME      | LFT  | RGT  | ID |
+-----------+------+------+----+
| A         |    1 |    8 |  1 |
| ----C     |    2 |    7 |  5 |
| --------F |    3 |    4 |  6 |
| --------G |    5 |    6 |  7 |
| B         |    9 |   14 |  2 |
| ----D     |   10 |   11 |  3 |
| ----E     |   12 |   13 |  4 |
+-----------+------+------+----+
7 rows in set (0.00 sec)

Récupérer le niveau d'un élément

Utilisons la requête suivante :

  1. SELECT COUNT(p.name) - 1 AS level
  2. FROM tree p
  3. , tree n
  4. WHERE n.lft BETWEEN p.lft AND p.rgt
  5. AND n.name = 'G'
  6. GROUP BY n.id

Ce qui nous donne ceci :

+-------+
| level |
+-------+
|     2 |
+-------+
1 row in set (0.00 sec)

15oct.

Opérations sur la hiérarchie

Suite au précédent article sur les hiérarchies avec MySQL, je vais ajouter quelques requêtes pratiques. On utilisera la même table et les mêmes données.

Récupérer le chemin d'un élément

Cet exemple [1] est décrit dans le document qui a initié ce billet ainsi que le précédent. Je le replace ici car il va servir de base aux requêtes suivantes.
Recherchons le chemin pour l'élément E, pour cela, utilisons la requête suivante :

  1. /* Récupération du chemin d'un élément */
  2. SELECT p.name AS NAME
  3. FROM tree AS n
  4. , tree AS p
  5. WHERE n.lft BETWEEN p.lft AND p.rgt
  6. AND n.name = 'E'

Ce qui nous donne ceci :

+------+
| NAME |
+------+
| A    |
| B    |
| E    |
+------+
3 rows in set (0.00 sec)

Nous remarquons que le chemin comporte également l'élément sélectionné.

Récupérer le chemin d'un élément sans l'élément

Utilisons la requête suivante :

  1. /* Récupération du chemin d'un élément sans l'élément en question */
  2. SELECT p.name AS NAME
  3. FROM tree AS n
  4. , tree AS p
  5. WHERE n.lft BETWEEN p.lft AND p.rgt
  6. AND n.name = 'E'
  7. AND n.id <> p.id

Ce qui nous donne ceci :

+------+
| NAME |
+------+
| A    |
| B    |
+------+
2 rows in set (0.00 sec)

Récupérer le parent immédiat d'un élément

Utilisons la requête suivante :

  1. /* Récupération du parent immédiat d'un élément */
  2. SELECT p.name AS NAME
  3. FROM tree AS n
  4. , tree AS p
  5. WHERE n.lft BETWEEN p.lft AND p.rgt
  6. AND n.name = 'E'
  7. AND n.id <> p.id
  8. ORDER BY p.lft DESC
  9. LIMIT 1

Ce qui nous donne ceci :

+------+
| NAME |
+------+
| B    |
+------+

Rien de bien compliqué, mais ça dépanne quand on en a besoin.

Notes

[1] Pour le trouver dans la documentation originale, il faut chercher le titre Retrieving a Single Path. Il y a 2 occurrences dans le document, celle qui nous intéresse est la seconde.

30sept.

Un peu d'ordre dans la hiérarchie

Il y a plusieurs méthodes pour stocker une hiérarchie de données dans une base de données MySQL [1], elles sont toutes les deux décrites dans ce document [2]. Il est assez complet, mais il me manque cependant quelques requêtes pour la manipulation des données selon la méthode de l'arbre. On va donc mettre en place ces requêtes.

Première étape : mise en place de l'environnement

Pour cela, nous avons besoin d'une table et de quelques données.

  1. /* Création de la table */
  2. CREATE TABLE tree
  3. ( id int AUTO_INCREMENT
  4. , name varchar(3)
  5. , lft int
  6. , rgt int
  7. , PRIMARY KEY (id));
  8.  
  9. /* Insertion des données */
  10. INSERT INTO tree (name,lft,rgt)
  11. VALUES ('A',1,14)
  12. , ('B',2,7)
  13. , ('D',3,4)
  14. , ('E',5,6)
  15. , ('C',8,13)
  16. , ('F',9,10)
  17. , ('G',11,12);

Maintenant, nous pouvons vérifier la structure de notre arbre avec la requête suivante [3]:

  1. /* Affichage de l'arbre de manière visuelle */
  2. SELECT concat(repeat('----',(count(p.name)-1)),n.name) AS NAME
  3. , n.lft AS LFT
  4. , n.rgt AS RGT
  5. , n.id AS ID
  6. FROM tree AS n
  7. , tree AS p
  8. WHERE n.lft BETWEEN p.lft
  9. AND p.rgt
  10. GROUP BY n.id
  11. ORDER BY n.lft;

Ce qui nous donne ceci :

+-----------+------+------+----+
| NAME      | LFT  | RGT  | ID |
+-----------+------+------+----+
| A         |    1 |   14 |  1 |
| ----B     |    2 |    7 |  2 |
| --------D |    3 |    4 |  3 |
| --------E |    5 |    6 |  4 |
| ----C     |    8 |   13 |  5 |
| --------F |    9 |   10 |  6 |
| --------G |   11 |   12 |  7 |
+-----------+------+------+----+
7 rows in set (0.00 sec)

Deuxième étape : ajouter un élément

J'ai décidé de n'ajouter un élément que sous un autre élément. Donc le nouvel élément se trouvera être le dernier enfant de son parent. Pour faire cela, il suffit de lancer ces quelques requêtes :

  1. /* Verrouillage en écriture de la table*/
  2. LOCK TABLE tree WRITE;
  3.  
  4. /* Récupération des informations de l'élément parent */
  5. SELECT @parentRight := rgt
  6. FROM tree
  7. WHERE name = 'B';
  8.  
  9. /* Mise à jour des bornes droites des éléments concernés */
  10. UPDATE tree
  11. SET rgt = rgt + 2
  12. WHERE rgt >= @parentRight;
  13.  
  14. /* Mise à jour des bornes gauches des éléments concernés */
  15. UPDATE tree
  16. SET lft = lft + 2
  17. WHERE lft >= @parentRight;
  18.  
  19. /* Insertion du nouvel élément */
  20. INSERT INTO tree (name,lft,rgt)
  21. VALUES ('ZZZ',@parentRight,@parentRight + 1);
  22.  
  23. /* Suppression des verrous */
  24. UNLOCK TABLES;

Ce qui nous donne ceci :

+-------------+------+------+----+
| NAME        | LFT  | RGT  | ID |
+-------------+------+------+----+
| A           |    1 |   16 |  1 |
| ----B       |    2 |    9 |  2 |
| --------D   |    3 |    4 |  3 |
| --------E   |    5 |    6 |  4 |
| --------ZZZ |    7 |    8 | 11 |
| ----C       |   10 |   15 |  5 |
| --------F   |   11 |   12 |  6 |
| --------G   |   13 |   14 |  7 |
+-------------+------+------+----+
8 rows in set (0.00 sec)

Troisième étape : déplacer un élément

J'ai décidé de ne gérer que les déplacements vers un parent qui ne fait pas parti des enfants de l'élément. Pour prendre le cas précédent, je peux déplacer B vers C mais pas vers ZZZ. Pour faire cela, il suffit de lancer ces quelques requêtes :

  1. /* Verrouillage en écriture de la table*/
  2. LOCK TABLE tree WRITE;
  3.  
  4. /* Récupération des informations de l'élément à déplacer */
  5. SELECT @nodeLeft := lft
  6. , @nodeRight := rgt
  7. , @nodeRange := rgt - lft + 1
  8. FROM tree
  9. WHERE name = 'ZZZ';
  10.  
  11. /* Récupération des informations du nouvel élément parent */
  12. SELECT @newParentLeft := lft
  13. , @newParentRight := rgt
  14. FROM tree
  15. WHERE name = 'C';
  16.  
  17. /* Calcul de la valeur de déplacement de l'élément à déplacer */
  18. SELECT @offsetRange := @newParentRight - @nodeRight - 1 + IF( sign( @newParentRight - @nodeRight ) < 1 , @nodeRange , 0 );
  19.  
  20. /* Calcul de la borne gauche de déplacement des autres éléments */
  21. SELECT @offsetLeft := IF( sign( @offsetRange ) = 1 , @nodeRight , @newParentRight );
  22.  
  23. /* Calcul de la borne droite de déplacement des autres éléments */
  24. SELECT @offsetRight := IF( sign( @offsetRange ) = 1 , @newParentRight - 1 , @nodeLeft - 1 );
  25.  
  26. /* Calcul de la valeur de déplacement des autres éléments */
  27. SELECT @signedNodeRange := sign( @offsetRange ) * @nodeRange;
  28.  
  29. /* Exclusion temporaire de l'élément à déplacer */
  30. UPDATE tree
  31. SET lft = -lft
  32. , rgt = -rgt
  33. WHERE lft >= @nodeLeft
  34. AND rgt <= @nodeRight;
  35.  
  36. /* Mise à jour des bornes droites des éléments concernés */
  37. UPDATE tree
  38. SET rgt = rgt - @signedNodeRange
  39. WHERE rgt BETWEEN @offsetLeft AND @offsetRight;
  40.  
  41. /* Mise à jour des bornes gauches des éléments concernés */
  42. UPDATE tree
  43. SET lft = lft - @signedNodeRange
  44. WHERE lft BETWEEN @offsetLeft AND @offsetRight;
  45.  
  46. /* Repositionnement de l'élément à déplacer */
  47. UPDATE tree
  48. SET lft = -lft + @offsetRange
  49. , rgt = -rgt + @offsetRange
  50. WHERE rgt < 0;
  51.  
  52. /* Suppression des verrous */
  53. UNLOCK TABLES;

Ce qui nous donne ceci :

+-------------+------+------+----+
| NAME        | LFT  | RGT  | ID |
+-------------+------+------+----+
| A           |    1 |   16 |  1 |
| ----B       |    2 |    7 |  2 |
| --------D   |    3 |    4 |  3 |
| --------E   |    5 |    6 |  4 |
| ----C       |    8 |   15 |  5 |
| --------F   |    9 |   10 |  6 |
| --------G   |   11 |   12 |  7 |
| --------ZZZ |   13 |   14 | 11 |
+-------------+------+------+----+
8 rows in set (0.00 sec)

Quatrième étape : supprimer un élément

Pour faire cela, il suffit de lancer ces quelques requêtes :

  1. /* Verrouillage en écriture de la table*/
  2. LOCK TABLE tree WRITE;
  3.  
  4. /* Récupération des informations de l'élément à supprimer */
  5. SELECT @nodeRight := rgt
  6. , @nodeLeft := lft
  7. , @range := rgt - lft + 1
  8. FROM tree
  9. WHERE name = 'ZZZ';
  10.  
  11. /* Suppression de l'élément */
  12. DELETE FROM tree
  13. WHERE lft >= @nodeLeft
  14. AND rgt <= @nodeRight;
  15.  
  16. /* Mise à jour des bornes droites des éléments concernés */
  17. UPDATE tree
  18. SET rgt = rgt - @range
  19. WHERE rgt >= @nodeRight;
  20.  
  21. /* Mise à jour des bornes gauches des éléments concernés */
  22. UPDATE tree
  23. SET lft = lft - @range
  24. WHERE lft >= @nodeRight;
  25.  
  26. /* Suppression des verrous */
  27. UNLOCK TABLES;

Ce qui nous donne ceci :

+-----------+------+------+----+
| NAME      | LFT  | RGT  | ID |
+-----------+------+------+----+
| A         |    1 |   14 |  1 |
| ----B     |    2 |    7 |  2 |
| --------D |    3 |    4 |  3 |
| --------E |    5 |    6 |  4 |
| ----C     |    8 |   13 |  5 |
| --------F |    9 |   10 |  6 |
| --------G |   11 |   12 |  7 |
+-----------+------+------+----+
7 rows in set (0.00 sec)

Et voila. J'ai fait les tests de déplacement et de suppression d'arbres et ça fonctionne correctement. Ne me croyez pas sur parole, essayez. Par contre, vous avez remarqué que je n'ai pas fait de test de validation des données. Si vous voulez allez plus loin, je vous laisse le soin de les faire.

Notes

[1] Pour les autres bases de données aussi, mais ce n'est pas le propos du jour.

[2] La lecture de ce document est un pré-requis pour la compréhension de ce qui va suivre.

[3] Nous utiliserons cette requête pour valider l'ensemble des résultats ultérieurs.