6 – Arbres SQL sans récursion

: vous pouvez vous passer de la récursion à condition de disposer d’une pile. Est-ce possible ? Oui : il suffit de rajouter la pile à la table… Comment ? En utilisant deux nouvelles colonnes RIGHT_BOUND et LEFT_BOUND…

ALTER TABLE T_VEHICULE ADD RIGHT_BOUND INTEGER
ALTER TABLE T_VEHICULE ADD LEFT_BOUND INTEGER

Maintenant, à la manière d’un magicien, je vais ajouter des données a ces deux nouvelles colonnes. Des chiffres astucieusement calculés pour rendre inutile le recours à la récursivité pour toutes nos interrogations :

UPDATE T_VEHICULE SET LEFT_BOUND = 1 , RIGHT_BOUND = 26 WHERE VHC_ID = 1
UPDATE T_VEHICULE SET LEFT_BOUND = 2 , RIGHT_BOUND = 7 WHERE VHC_ID = 2
UPDATE T_VEHICULE SET LEFT_BOUND = 8 , RIGHT_BOUND = 19 WHERE VHC_ID = 3
UPDATE T_VEHICULE SET LEFT_BOUND = 20, RIGHT_BOUND = 25 WHERE VHC_ID = 4
UPDATE T_VEHICULE SET LEFT_BOUND = 3 , RIGHT_BOUND = 4 WHERE VHC_ID = 5
UPDATE T_VEHICULE SET LEFT_BOUND = 5 , RIGHT_BOUND = 6 WHERE VHC_ID = 6
UPDATE T_VEHICULE SET LEFT_BOUND = 9 , RIGHT_BOUND = 10 WHERE VHC_ID = 7
UPDATE T_VEHICULE SET LEFT_BOUND = 11, RIGHT_BOUND = 16 WHERE VHC_ID = 8
UPDATE T_VEHICULE SET LEFT_BOUND = 17, RIGHT_BOUND = 18 WHERE VHC_ID = 9
UPDATE T_VEHICULE SET LEFT_BOUND = 21, RIGHT_BOUND = 22 WHERE VHC_ID = 10
UPDATE T_VEHICULE SET LEFT_BOUND = 23, RIGHT_BOUND = 24 WHERE VHC_ID = 11
UPDATE T_VEHICULE SET LEFT_BOUND = 12, RIGHT_BOUND = 13 WHERE VHC_ID = 12
UPDATE T_VEHICULE SET LEFT_BOUND = 14, RIGHT_BOUND = 15 WHERE VHC_ID = 13

Et voici maintenant la requête "magique" qui donne le même résultat que notre précédente requête exprimée sous la forme complexe de la CTE récursive :

SELECT *
FROM T_VEHICULE
WHERE RIGHT_BOUND > 12
AND LEFT_BOUND < 13

VHC_ID VHC_ID_FATHER VHC_NAME RIGHT_BOUND LEFT_BOUND
———– ————- —————- ———– ———–
1 NULL ALL 26 1
3 1 EARTH 19 8
8 3 TWO WHEELES 16 11
12 8 MOTORCYCLE 13 12

La question est maintenant la suivante : quel est le truc ? En fait, nous avons réalisé la pile en numérotant les données par tranches. Comme rien ne vaut une image pour visualiser un tel concept, voici ce que j’ai dessiné : (voir figure 1)

La seule chose que j’ai fait, c’est de numéroter continuellement en commençant par 1 toutes les bornes droites et gauches des empilements de données constitués par chacune de nos données. Afin d’obtenir la requête précédente, j’ai simplement pris les bornes de MOTORCYCLE, c’est à dire 12 gauche et 13 droite afin de les placer dans la clause WHERE et demandé d’extraire les lignes de la table pour lesquelles les valeurs des colonnes RIGHT BOUND étaient supérieures à 12 et LEFT BOUND inférieures à 13. Notez d’ailleurs que mon joli dessin serait plus compréhensible si je l’avais fait pivoter de 90° : ( voir figure 2)

J’espère ainsi que vous voyez mieux les piles ! Cette représentations est d’ailleurs connue dans la littérature spécialisée sous le nom de "représentation intervallaire des arborescences", en particulier dans le livre de Joe Celko "SQL Avancé" (Vuibert éditeur) ainsi que sur mon site web SQLpro sur lequel vous trouverez en outre toutes les requêtes et les procédures stockées MS SQL Server adéquates pour faire fonctionner un tel arbre (http://sqlpro.developpez.com/ cours/arborescence/).

Dernière question sur ce modèle : pouvons nous reproduire l’indentation hiérarchique présentée dans la dernière requête construite avec la CTE ? Oui bien sûr, et cela d’autant plus facilement si l’on ajoute une nouvelle colonne indiquant le niveau du noeud. C’est simple à calculer puisque le niveau d’un noeud est celui du noeud de rattachement +1 si l’insertion se fait en fils, ou encore le même si l’insertion se fait en frère, et qu’a la première insertion, donc à la racine de l’arbre, le niveau est 0. Voici maintenant les ordres SQL modifiant notre table pour assurer cette fonction :

ALTER TABLE T_VEHICULE
ADD LEVEL INTEGER

UPDATE T_VEHICULE SET LEVEL = 0 WHERE VHC_ID = 1
UPDATE T_VEHICULE SET LEVEL = 1 WHERE VHC_ID = 2
UPDATE T_VEHICULE SET LEVEL = 1 WHERE VHC_ID = 3
UPDATE T_VEHICULE SET LEVEL = 1 WHERE VHC_ID = 4
UPDATE T_VEHICULE SET LEVEL = 2 WHERE VHC_ID = 5
UPDATE T_VEHICULE SET LEVEL = 2 WHERE VHC_ID = 6
UPDATE T_VEHICULE SET LEVEL = 2 WHERE VHC_ID = 7
UPDATE T_VEHICULE SET LEVEL = 2 WHERE VHC_ID = 8
UPDATE T_VEHICULE SET LEVEL = 2 WHERE VHC_ID = 9
UPDATE T_VEHICULE SET LEVEL = 2 WHERE VHC_ID = 10
UPDATE T_VEHICULE SET LEVEL = 2 WHERE VHC_ID = 11
UPDATE T_VEHICULE SET LEVEL = 3 WHERE VHC_ID = 12
UPDATE T_VEHICULE SET LEVEL = 3 WHERE VHC_ID = 13

Voici la requête présentant les données sous forme d’une arborescence avec indentation hiérarchique :

SELECT SPACE(LEVEL) + VHC_NAME as data FROM T_VEHICULE ORDER BY LEFT_BOUND

data
 ———————–
ALL
    SEA
        SUBMARINE
        BOAT
    EARTH
        CAR
        TWO WHEELES
            MOTORCYCLE
            BYCYCLE
        TRUCK
    AIR
        ROCKET
        PLANE

Beaucoup plus simples n’est-ce pas ?

PREMIERES IMPRESSIONS…

La seule chose à dire au sujet de ces deux techniques de navigation dans les arbres est que le modèle par intervalle est beaucoup plus performant pour l’extraction des données que l’utilisation de l’expression de table récursive (CTE) introduite avec la norme SQL:1999.

En fait la récursivité dans SQL n’est pas si intéressante que cela dans ce cadre… Mais qu’en est-il dans un autre ? C’est ce que nous allons voir !