La représentation intervallaire

Introduction du cours

Une notion bien étrange que voilà...

Pour mieux expliquer, prenons (par exemple) des forums, ayant plusieurs "niveaux" (comprenez sous-forums). Pour accéder aux "enfants" et aux "parents" d'un forum, vous pensez sûrement (et, je pense, vous les utiliserez) les héritages (présence d'une colonne parent_id, méthode également connue sous le nom de représentation classique) par auto-jointures, c'est-à-dire en renseignant récursivement la clause WHERE à l'aide de sous-requêtes.
Mais, ceci peut très vite devenir lourd... et peu pratique, surtout à partir d'un certain niveau (et qui, au grand dam de tous, est vite atteint).

Notez que, tout au long du tutoriel, pour la plupart des exemples, j'utiliserai l'exemple de forums. ;)

Dans ce tuto, nous allons donc voir comment éviter cette lourdeur en employant une "ruse" mise au point par les développeurs : la représentation intervallaire (nommée RI pour les intimes) !
Accrochez-vous, on y va !

La théorieUne (petite) présentation de tout le "schmilblik"

Avant d'attaquer la bête, nous avons, tout d'abord, besoin de la définir. Tout d'abord, qu'est-ce que la repr...

C'est vrai ça, c'est quoi la rapré... représentation invert... cette chose ?

La représentation intervallaire ! Je la voyais arriver à des kilomètres à la ronde, celle-là !

Je commence par un point optionnel (ce sera plus facile à expliquer). Cette technique peut permettre de situer un élément dans une hiérarchie. Pour donner une image de cette notion de hiérarchie, prenons l'exemple d'un immeuble, couplé à un système de forums (vous allez très vite comprendre). Vous savez, un immeuble est constitué d'étages...
Disons que la catégorie d'un système de forums est le rez-de-chaussée de cet immeuble, et les étages, les sous-forums (qui sont chacun des sous-forums de l'étage précédent). Voilà ce qu'est la notion de hiérarchie : si je suis au quatrième étage (non, non, je ne vais pas sauter :D ), ça veut dire que je suis... au quatrième niveau, ou à la quatrième hiérarchie. Il peut, bien entendu, y avoir plusieurs sous-forums ayant le même niveau, comme, toujours à l'image d'un immeuble, il peut y avoir plusieurs appartements à chaque étage.

Ensuite, un point essentiel à retenir dans la représentation intervallaire (je ne vois pas ce qu'il y a de compliqué à retenir là-dedans, ce n'est quand même pas de l'acide acétyli... acide acytéli... bref, un certain médicament :p ), les notions de borne gauche, borne droite.

Pour illustrer cette notion, voici un schéma fait par mes soins (mes capacités en graphisme étant très limitées, vous m'excuserez de la qualité de celui-ci), qui, je dois vous l'avouer, reprend un peu la même idée que le schéma de Frédéric Brouard (le mien étant simplifié, et (surtout) plus adapté à notre cas de développeurs en herbe), qui d'ailleurs présente de très bons tutos sur SQL.

Merci à Shadow_f pour le schéma

Comme vous pouvez le voir, chaque borne de chaque élément se voit attribuer un nombre. Ce nombre permet de déterminer la position de l'élément dans l'ensemble. Notez également que le nombre de la borne gauche est toujours inférieur au nombre de la borne droite. Notez bien ce point, il est très important (je fais une liste de rappels à la fin de cette première sous-partie) !

À propos de points importants, en voilà un autre à noter : si la différence entre sa borne droite et sa borne gauche (et non pas l'inverse !) est égale à 1, on désigne alors l'élément étant une feuille. Sinon, ce sera un noeud, et cette même différence sera égale au double du nombre d'enfants, auquel on ajoute 1.

Je pense que vous constaterez qu'au lieu de mettre des noms aux éléments sur mon schéma, j'ai juste indiqué les niveaux de chaque élément, pour vous montrer la tête que ça peut avoir.

Euh... C'est bien beau tout ça, mais quels sont les points essentiels de la représentation intervallaire ?

J'y viens, et vous posez la question pile au bon moment. Je vous ai fait une petite liste de trucs à retenir....

• La notion de niveaux détermine la hiérarchisation de la feuille, qui, je dois vous l'avouer, n'est pas essentielle à la RI, mais plutôt utile (pour les tris par exemple).

• La notion de bornes, qui détermine la situation de la feuille (ou du noeud) par rapport à l'ensemble.

• Une feuille désigne un élément caractérisé par le fait que la différence entre sa borne droite et sa borne gauche est égale à 1. Un noeud, lui, est un élément caractérisé par les autres cas (donc la différence borne droite - borne gauche supérieure à 1).

• Pour calculer la différence entre les deux bornes, il faut TOUJOURS soustraire la borne gauche à la borne droite, et non pas l'inverse. En effet, la borne gauche est TOUJOURSinférieure à la borne droite.

• La différence entre les deux bornes d'un même noeud (et non pas d'une feuille) est (quoi qu'il advienne) TOUJOURS égale au double du nombre d'enfants, auquel on rajoute 1.

Passons maintenant à la préparation pour pouvoir pratiquer, dans la seconde partie de ce tutoriel (majoritairement des requêtes SQL, pour servir à titre d'exemples). Je montrerai également pourquoi il est difficile (et coûteux) d'utiliser les "auto-jointures" (c'est-à-dire d'utiliser avec abus la clause WHERE et les sous-requêtes) pour accéder aux noeuds parents et aux feuilles... Et que c'est même presque impossible pour nous en ce moment. À moins d'avoir des idées tordues... :lol:

Pourquoi préférer la RI à l'héritage récursif ? Les tables SQL d'exemple

Dans cette sous-partie, je considère que vous savez manipuler SELECT et ses clauses WHERE, ORDER BY, et (éventuellement) comprendre les requêtes d'insertion. Sinon, vous avez la porte, le big tutoriel de M@teo21, "Faire un site dynamique avec PHP - Base de Données", le big tutoriel de Shepard, "Pour aller plus loin..." à disposition.

L'héritage récursif ? Ourf, c'est lourd... et infaisable (pour des Zéros comme nous) :D

Voici la table type que nous allons utiliser pour illustrer la faiblesse ( :p ) de l'héritage récursif :

CREATE TABLE tuto_herit ( forum_id mediumint(8) NOT NULL AUTO_INCREMENT, forum_parent_id mediumint(8) DEFAULT NULL, forum_name varchar(30) NOT NULL, PRIMARY KEY (forum_id), KEY forum_parent_id (forum_parent_id) ); INSERT INTO tuto_herit (forum_id, forum_parent_id, forum_name) VALUES (1, NULL, '1'), (2, 1, '1.1'), (3, 2, '1.1.1'), (4, 3, '1.1.1.1'), (5, 4, '1.1.1.1.1'), (6, 5, '1.1.1.1.1.1'), (7, 6, '1.1.1.1.1.1.1'), (8, 6, '1.1.1.1.1.1.2'), (9, 6, '1.1.1.1.1.1.3'), (10, 4, '1.1.1.1.1.2'), (11, 4, '1.1.1.1.1.3'), (12, 4, '1.1.1.1.2'), (13, 4, '1.1.1.1.3'), (14, 2, '1.1.2'), (15, 1, '1.2'), (16, 1, '1.3'), (17, 1, '1.4'), (18, 11, '1.4.1'), (19, 11, '1.4.2'), (20, NULL, '2')/*,[...]*/;

Notez que j'ai délibérément choisi de nommer les éléments en fonction de leur parent, pour pouvoir les distinguer. Ainsi, X.Y.Z veut dire que l'élément correspondant appartient à un parent X, qui a un fils Y, ... etc. Mais vous êtes libres de nommer les tables comme vous le souhaitez, ce nommage n'étant pas une condition pour l'utilisation de la RI.

À partir d'un des sous-forums (on va dire celui ayant l'id numéro 7, le plus profond :diable: ), comment faire, à l'aide des jointures, pour accéder à la catégorie 1, en affichant tous les forums parents au sous-forum sélectionné ? Je vous laisse 5 minutes pour essayer de faire cette requête... Et bien entendu, en ayant qu'un seul forum par ligne (pas tous, sinon ce serait trop facile, surtout si on connaît la profondeur du sous-forum :p ).

...

...

Vous n'y arrivez pas ? Pour tout vous avouer, moi non plus :D . Ici, on peut facilement avoir tous les forums parents sur la même ligne à l'aide de quelques jointures (en utilisant l'héritage de la colonne forum_parent_id) ; or, ce n'était pas ce qui était demandé : on voulait un forum par ligne. Certes, les jointures, c'est pratique, mais à la longue... c'est vite pesant et peu pratique.

N.d.A. : pour ce problème, je pense qu'il faut soit utiliser la récursivité d'une fonction pour trouver ce qu'on cherche, mais ça reste consommateur de ressource si l'arbre est trop profond (dans notre cas, cela peut être considéré comme trop profond), soit, toujours dans la récursivité, une série de sous-requêtes, ce qui n'est également pas terrible.

La représentation intervallaire ? Yeah !

Reprenons la première table... En l'adaptant quelque peu pour pouvoir la rendre utilisable par la représentation intervallaire... Hop, la voilà prête à l'emploi (toujours avec les insertions, converties qui plus est :magicien: ) !

CREATE TABLE tuto_ri ( forum_id mediumint(8) NOT NULL AUTO_INCREMENT, forum_level mediumint(8) NOT NULL DEFAULT 0, forum_gauche mediumint(8) NOT NULL, forum_droite mediumint(8) NOT NULL, forum_name varchar(30) NOT NULL, PRIMARY KEY (forum_id), KEY forum_gauche (forum_gauche), KEY forum_droite (forum_droite) ); INSERT INTO tuto_ri (forum_id, forum_level, forum_gauche, forum_droite, forum_name) VALUES (1, 0, 1, 38, '1'), (2, 1, 2, 27, '1.1'), (3, 2, 3, 24, '1.1.1'), (4, 3, 4, 23, '1.1.1.1'), (5, 4, 5, 18, '1.1.1.1.1'), (6, 5, 6, 13, '1.1.1.1.1.1'), (7, 6, 7, 8, '1.1.1.1.1.1.1'), (8, 6, 9, 10, '1.1.1.1.1.1.2'), (9, 6, 11, 12, '1.1.1.1.1.1.3'), (10, 5, 14, 15, '1.1.1.1.1.2'), (11, 5, 16, 17, '1.1.1.1.1.3'), (12, 4, 19, 20, '1.1.1.1.2'), (13, 4, 21, 22, '1.1.1.1.3'), (14, 2, 25, 26, '1.1.2'), (15, 1, 28, 29, '1.2'), (16, 1, 30, 31, '1.3'), (17, 1, 32, 37, '1.4'), (18, 2, 33, 34, '1.4.1'), (19, 2, 35, 36, '1.4.2'), (20, 0, 39, 40, '2')/*,[...]*/;

La note concernant les noms des (sous-)forums reste toujours valable dans ce cas-ci.

Allez : même exercice que tout à l'heure ! Vous avez... 10 minutes pour le faire : rechercher l'id, le nom, et la hiérarchie des noeuds parents de la feuille ayant l'id "7", en les triant du parent le plus proche au parent le plus lointain !

...

...

...

...

...

...

Ah, c'est vrai, j'avais oublié le petit indice : utiliser les bornes des feuilles. Si vous n'aviez pas deviné (nan, surtout pas, pas la fenêtre :waw: !), ce n'est pas grave, voici ma solution, et pour tenter de me faire pardonner ( :ange: ), je l'ai commentée pour que vous la compreniez mieux).

SELECT forum_id, forum_name FROM tuto_ri WHERE forum_gauche < 7 AND forum_droite > 8 ORDER BY forum_level DESC;

On retrouve donc ce qu'on recherchait

On cherche à récupérer l'ID, le nom, et la hiérarchisation des noeuds parents, ce qu'on fait en sélectionnant les champs forum_id, forum_name, et forum_level.
Ensuite, dans la clause WHERE, on applique ce qu'on a pu observer sur mon (beau :p ) schéma : la borne gauche d'un des (sous-)forums est toujoursplus grande que celle des noeuds parents. On sélectionne donc tous les noeuds ayant une borne gauche plus petite que (dans notre cas) 7. On applique la même chose à la borne droite, sauf que cette fois-ci, la borne droite de la feuille est toujoursplus petite que celle des noeuds parents.

On a donc les noeuds que l'on désire... Mais ce n'est pas fini, il y avait un petit piège : on souhaite avoir les noeuds... Du plus proche au plus lointain par rapport à la feuille. Il suffisait juste d'ajouter une petite clause ORDER BY, en indiquant le nom de la colonne qui sert à trier (forum_level), et par ordre décroissant. Je vous avais bien dit que la notion de hiérarchisation pouvait s'avérer utile par moments... En voilà la preuve même !

Notez que si je vous avais demandé, dans la liste des forums ressortie, de ressortir également le forum dans lequel on est, à la place des opérateurs < et >, il aurait fallu utiliser <= et >=. En effet, les bornes gauche et droite du forum sont bien plus petites ou égales aux bornes de notre forum. ;)

Ici, on cherche aussi à inclure le forum courant dans le résultat

Bon, je vous pense prêts pour la pratique : à l'assauuuuuut :pirate: !

La pratique

Ici, nous allons voir les différentes techniques et opérations chirurgicales liées à la représentation intervallaire : modifier le statut d'un élément (transformer un noeud en une feuille, et vice-versa), ajouter des feuilles à un noeud, compter le nombre d'éléments dans un noeud, pouvoir mettre à jour les indices aux bornes en fonction du nombre d'éléments (selon que ce sera une feuille ou un noeud), le déplacement de noeuds...

Cette partie du tuto agira donc en tant que plusieurs séries de "minis-TP", qui demandent par moments de la réflexion, et par moments des astuces... que je développerai ici.

Stats sur les différents noeuds

Dans cette sous-partie, nous allons voir comment compter le nombre d'éléments d'un noeud, le nombre de feuilles d'un noeud, le nombre de noeuds dans un même noeud, ... bref, on va compter. :p

Compter le nombre d'éléments d'un noeud

Pour compter le nombre d'éléments d'un noeud, ça va être relativement (très) simple, et (très) vite expédié. Vous vous souvenez, à la fin de la première partie de ce tuto, on a vu comment récupérer tous les parents (et leur caractéristiques) d'une feuille / d'un noeud, en incluant ou non l'élément, non ? Eh bien ici, ça va plus ou moins être le même topo.

Ha ! Laisse-moi deviner : au lieu d'inclure l'élément dans la sélection, on va déjà devoir utiliser les signes strictement supérieur / inférieur, non ?

Bingo ! De plus, vous aurez besoin, comme je l'ai dit, non pas de sélectionner les parents de l'élément, mais ses enfants ! Donc, au lieu de rechercher tous les éléments qui ont une borne gauche inférieure à celle de l'élément recherché, et une borne droite supérieure à celle de l'élément, on va faire l'inverse !
Je vous file la solution dans quelques minutes, le temps pour vous de chercher (et moi d'aller piquer un petit somme :ninja: ). Ah, j'oubliais pour quel forum on va faire cette opération : cette fois-ci, on va chercher le nombre d'enfants pour le forum ayant l'ID numéro... 3 !

Petit indice : utilisez la fonction d'agrégat COUNT(*) (pour les fonctions d'agrégat, voyez le tutorial de Shepard sur le sujet).

...

...

Hmm ? Vous avez (déjà) fini ? Voici donc la correction :) .

SELECT COUNT(*) FROM tuto_ri WHERE forum_gauche > 3 AND forum_droite < 24;

Vous avez vu, ce n'était pas si sorcier, il suffisait donc juste d'inverser les signes pour les deux bornes pour obtenir les enfants et non pas les parents du noeud, et d'utiliser,...