Les arbres génériques en SQL
Représentation et gestion des arbres génériques en SQL
Le parcours d'un arbre en SQL repose souvent sur l'utilisation de procédures complexes et coûteuse en ressources ce qui fait qu'elles sont difficilement exploitables lorsque les arbres atteignent une certaine taille. Pour pallier ce problème, il faut pouvoir parcourir l'arbre avec de simples requêtes SQL. Cette méthode nécessite l'usage de structures particulières.
En effet, l'on pourrait se contenter de simplement une table qui stocke les liens père-fils et d'utiliser un algorithme pour reconstruire une repréentation de l'arbre grâce à des langages avancés (PL/SQL, etc.). Mais ces méthodes nécessitent souvent des méthodes utilisant des boucles imbriquées qui se révèlent rapidement très coûteuses en ressources pour le résultat obtenu.
Nous pouvons améliorer la méthode en améliorant les structures utilisées.
Arbre générique
Dans notre exemple, nous étudierons le cas d'un arbre générique, c'est-à-dire que chaque père peut avoir de 1 à n fils et chaque fils de 1 à n pères. Par exemple :
Ou encore :
Terminologie
Dans le reste de l'article, nous utiliserons la terminologie suivante :
Noeud : élément d'un arbre.
Feuille : noeud qui n'a pas de fils.
Racine : noeud qui n'a pas de père.
Principe
Oracle propose une fonction de parcours d'arbre (connect by). Il s'agit d'un algorithme récursif. Il est possible de réaliser la même fonctionnalité, cependant l'exécution devient lente lorsque la quantité de données croît. Pour conserver de bonnes performances, il faut éviter la récursion.
Pour éviter toute récusion en SQL, une solution simple consiste à mettre l'arbre à plat. Ainsi, pour un noeud donné, on retrouve tous les éléments de l'arbre passant par ce noeud (si ce noeud est la racine, on retourne l'arbre en entier).
Cependant, si l'on met l'arbre à plat, on perd une partie de l'information, celle qui concerne notamment l'ordre hiérarchique des noeuds. Conserver le lien père-fils est donc primordial.
Un arbre générique sera donc stocké sous deux informations complémentaires :
hiérarchie : lien père-fils;
parcours : arbre à plat.
Principe de stockage d'une représentation d'arbre
Le stockage d'une représentation d'arbre se fera de la façon suivante : Chaque noeud sera stocké avec tous ses descendants directs ou indirects.
Dans le cas du premier exemple d'arbre :
Si nous nous attachons au parcours 1-2-4-7-8, cette décomposition donnera :
Chaque niveau est stocké avec ses descendants.
Seuls les liens en double sont éliminés.
Cependant, pour savoir ce qui était directement relié et reconstituer l'arbre dans son intégralité, nous avons besoin de conserver les liens directs père-fils egalement.
Création des structures
Pour représenter cet arbre, trois tables sont nécessaires :
Une table de dimension : elle stocke les caractéristiques de chaque noeud, indépendamment les uns des autres.
Une table de lien direct : elle stocke le lien entre un père et son fils.
Une table de chemin : elle stocke une représentation binaire du chemin.
Table de dimension
Rien de plus simple pour la table de dimension. Elle contient la description individuelle de chaque noeud :
| id | Propriété |
|---|---|
1 |
racine |
2 |
noeud numéro 2 |
3 |
noeud numéro 3 |
4 |
... |
Table de lien direct
Les liens directs sont les relation père-fils uniquement. Il faut une table à elle seule car un fils peut avoir plusieurs pères, ce qui exclue de stocker cette information dans la table de dimension (ce qui serait le cas si un fils ne pouvait avoir qu'un seul et unique père, sauf pour la racine) :
| père | fils |
|---|---|
1 |
2 |
2 |
3 |
2 |
4 |
2 |
5 |
4 |
7 |
7 |
8 |
5 |
6 |
6 |
8 |
Remarque
Notons que ces liens sont orientés. En effet, le lien 3-->2 n'est pas la même chose que le lien 2-->3. Ainsi, dans cet arbre, il est possible de faire des boucles. Il faudra donc prendre cela en compte lors du parcours pour éviter de tourner indéfiniment. Mais cette notion de sens est nécessaire, notamment dans le cas de liens à états.
La table des chemins
Pour parcourir l'arbre sans utiliser de boucle, il faut stocker les chemins possibles dans une table. Ainsi, le noeud 4 a pour antécédant le noeud 2 mais aussi le noeud 1 et pour successeur le noeud 7 mais pas le noeud 6. La description complète ressemblera donc à :
| ascendant | descendant |
|---|---|
1 |
2 |
2 |
3 |
2 |
4 |
2 |
5 |
4 |
7 |
7 |
8 |
5 |
6 |
6 |
8 |
1 |
4 |
1 |
7 |
1 |
8 |
2 |
7 |
2 |
8 |
4 |
8 |
1 |
5 |
1 |
6 |
5 |
8 |
Chaque couple ascendant/descendant n'est noté qu'une seule fois. Une partie de la table de chemins est l'exacte reproduction de la table de liens directs. le supplément correspond à des chemins indirectes de 2ème, 3ème et nième niveau. Le chemin 1-8 (noté une seule fois) peut passer par 2-4-7 (2-4, 4-7, 2-7) ou par 2-5-6 (2-5, 5-6, 2-6). etc.
Comme on remarquera que la table chemin contient les mêmes informations père-fils que la table de lien, on peut fusionner ls deux tables en une seule avec la structure suivante :
| champ | description |
|---|---|
ascendant |
stockage de l'ascendant |
descendant |
stockage du descendant |
type (boolean indexé) |
true si lien direct père-fils, false sinon |
Ainsi, avec une simple vue ne sélectionnant que le type père-fils (type=true), nous recréons alors la table tache_lien et toute l'arborescence n'est stockée que dans une seule table.
Les manipulations de données ne se font plus alors que sur une seule table (ici tache_chemin). La table de lien n'étant qu'une vue de la table de chemins.
Alimentation des structures
Tout le potentiel de l'arbre stocké de cette façon repose sur l'alimentation. En effet, il est assez difficile de générer automatiquement d'un seul coup un arbre existant sous une autre forme (par exemple, uniquement sous la forme lien père-fils). En revanche, si l'arbre est construit depuis le départ étape par étape, à partir de rien, noeud par noeud, la cohérence est conservée et l'arbre devient manipulable aisément.
Ajout d'un lien/ d'un noeud
L'ajout d'un lien se traduit de la même façon que l'ajout d'un noeud.
Il y a deux contextes possible. Soit il s'agit de l'ajout d'un lien pour un nouveau noeud (le noeud fils est une feuille : il n'a pas de fils), soit il s'agit de la fusion de deux arbres ou deux branches (le noeud fils est relié à d'autres pères ou d'autres fils).
L'ajout d'un noeud dans l'arbre se fait par l'intermédiaire d'ajout de lien car c'est ce qui constitue l'arbre. Sans lien, pas d'arbre. Le noeud existe déjà dans la table de dimension (une simple insertion avec INSERT). Pour le lien père-fils, rien de plus simple non plus.
Paramètres $1 : père; $2 : fils.
On commence par ajouter le lien père-fils dans la table de car le lien père-fils est aussi un chemin (de degré 0) :
INSERT INTO donnees.tache_chemin(ascendant,descendant,type) VALUES($1,$2,true);
Pour le relier à l'arbre complet (calcul de la table chemin), l'ajout le fait de la façon suivante :
On ajoute toute combinaison de chemin existant étendue à la nouvelle tâche. Dans cette partie on considère que le fils ajouté est une feuille de l'arbre ce qui est le cas lorsque l'arbre est en construction, mais pas lorsqu'on vient faire un raccord (un fils ayant deux arbres pour pères):
INSERT INTO donnees.tache_chemin(ascendant,descendant,type) SELECT tache_chemin.ascendant, tache_lien.fils, false FROM donnees.tache_chemin, donnees.tache_lien WHERE tache_chemin.descendant = tache_lien.pere AND tache_lien.fils = $2 AND tache_lien.pere = $1 -- on ajoute que la branche correspondant au père qu'on vient d'ajouter AND (tache_chemin.ascendant, tache_lien.fils) NOT IN (SELECT ascendant,descendant FROM donnees.tache_chemin); -- et l'on ajoute pas si le chemin existe déjà (ce qui est possible si deux chemins sont possibles)
Dans le cas de fusion de deux arbres, on ajoute le reste de l'arbre en supposant que le fils du lien est en fait le père d'autres feuilles, comme c'est le cas lorsqu'on fusionne deux arbres. Cette combinaison repose sur le produit cartésien entre tous les ascendants du noeud qui sont reliés à tous les descendants du noeud, ainsi que le noeud lui-même, relié à tous ses descendants (sauf lorsque le chemin existe déjà) :
INSERT INTO donnees.tache_chemin(ascendant,descendant,type) SELECT tache_chemin.ascendant, tache_lien.fils, false FROM donnees.tache_chemin, donnees.tache_lien WHERE tache_chemin.descendant = tache_lien.pere AND tache_lien.pere = $2 AND (tache_chemin.ascendant, tache_lien.fils) NOT IN (SELECT ascendant,descendant FROM donnees.tache_chemin);
Suppression d'un lien
Dans le cas d'un suppression de lien, le nombre de noeuds de l'arbre ne change pas. Seuls les chemmins qui menaient aux descendants de ce lien sont rompus également.
$1 : père; $2 : fils.
Si on supprime un lien, le chemin est rompu, il faut supprimer tous les chemins qui passaient par lui
DELETE FROM donnees.tache_chemin WHERE (tache_chemin.ascendant, tache_chemin.descendant) IN (SELECT ascendants.ascendant, descendants.descendant FROM donnees.tache_chemin, (SELECT ascendant, descendant FROM donnees.tache_chemin WHERE descendant = $1) ascendants, (SELECT ascendant, descendant FROM donnees.tache_chemin WHERE ascendant = $2) descendants WHERE tache_chemin.ascendant = ascendants.ascendant AND tache_chemin.descendant = descendants.descendant);
Il ne faut pas oublier de supprimer les liens directs.
DELETE FROM donnees.tache_chemin WHERE tache_chemin.ascendant = $1 AND tache_chemin.descendant = $2;
Tous ceux qui ont pour origine le père et des liens avec les descendants du fils.
DELETE FROM donnees.tache_chemin WHERE (tache_chemin.ascendant, tache_chemin.descendant) IN (SELECT tache_chemin.ascendant, descendants.descendant FROM donnees.tache_chemin, donnees.tache_chemin descendants WHERE descendants.ascendant = $2 AND tache_chemin.ascendant = $1 AND tache_chemin.descendant = descendants.descendant);
Tous ceux qui ont pour cible le fils et des liens avec les ascendants du père.
DELETE FROM donnees.tache_chemin WHERE (tache_chemin.ascendant, tache_chemin.descendant) IN (SELECT tache_chemin.ascendant, ascendants.descendant FROM donnees.tache_chemin, donnees.tache_chemin ascendants WHERE ascendants.descendant = $2 AND tache_chemin.descendant = $1 AND tache_chemin.ascendant = ascendants.ascendant);
Suppression d'un noeud
$1 : père; $2 : fils.
Si on supprime un élément, il faut supprimer tous les chemins qui passaient par lui.
DELETE FROM donnees.tache_chemin WHERE (tache_chemin.ascendant, tache_chemin.descendant) IN ( SELECT tache_chemin.ascendant, tache_chemin.descendant FROM donnees.tache_chemin, (SELECT ascendant, descendant FROM donnees.tache_chemin WHERE descendant = $1) ascendants, (SELECT ascendant, descendant FROM donnees.tache_chemin WHERE ascendant = $1) descendants WHERE tache_chemin.ascendant = ascendants.ascendant AND tache_chemin.descendant = descendants.descendant);
Et tous les chemins qui commencent ou finissent par le noeud supprimé.
DELETE FROM donnees.tache_chemin WHERE tache_chemin.ascendant = $1 OR tache_chemin.descendant = $1;
Modification d'un lien/ d'un noeud
Toute modification se faisant sur un lien binaire, il ne s'agirait en définitive que d'une opération de suppresssion + ajout.