Tri combiné dans un arbre intervallaire

Trier des données dans le sens de l’arborescence et quand elle sont aux même niveau (frères) par ordre alphabétique (tri mixte arbre et alfa) est difficile à réaliser dans un arbre modélisé par intervalle. Mais le principe est assez simple. Il suffit de composer une nouvelle colonne constitué d’une alternance de nœud et d’ordre alphabétique relatif dans la fratrie, et de trier dessus. Voici comment faire. Cette technique s’appelle en anglais « sibling ordering ».

1 – LE PROBLÈME

Voici notre jeu de test :

Tout d’abord la table

CREATE TABLE T_VEHICULE_VHC
(VHC_ID         INTEGER NOT NULL PRIMARY KEY,
 VHC_BG         INTEGER,
 VHC_BD         INTEGER,
 VHC_NIVEAU     SMALLINT,
 VHC_NOM        VARCHAR(16));

Et ses données :

INSERT INTO T_VEHICULE_VHC VALUES ( 1,  1, 26, 0, 'ALL');
INSERT INTO T_VEHICULE_VHC VALUES ( 2,  2,  7, 1, 'SEA');
INSERT INTO T_VEHICULE_VHC VALUES ( 3,  8, 19, 1, 'EARTH');
INSERT INTO T_VEHICULE_VHC VALUES ( 4, 20, 25, 1, 'AIR');
INSERT INTO T_VEHICULE_VHC VALUES ( 5,  3,  4, 2, 'SUBMARINE');
INSERT INTO T_VEHICULE_VHC VALUES ( 6,  5,  6, 2, 'BOAT');
INSERT INTO T_VEHICULE_VHC VALUES ( 7,  9, 10, 2, 'CAR');
INSERT INTO T_VEHICULE_VHC VALUES ( 8, 11, 16, 2, 'TWO WHEELS');
INSERT INTO T_VEHICULE_VHC VALUES ( 9, 17, 18, 2, 'TRUCK');
INSERT INTO T_VEHICULE_VHC VALUES (10, 21, 22, 2, 'ROCKET');
INSERT INTO T_VEHICULE_VHC VALUES (11, 23, 24, 2, 'PLANE');
INSERT INTO T_VEHICULE_VHC VALUES (12, 12, 13, 3, 'MOTORCYCLE');
INSERT INTO T_VEHICULE_VHC VALUES (13, 14, 15, 3, 'BICYCLE');

Premier essai :

Une simple requête telle que celle-ci :

SELECT CAST(SPACE(VHC_NIVEAU) + VHC_NOM AS VARCHAR(32)) AS NOM_IDENTE,
       VHC_ID, VHC_BG, VHC_BD, VHC_NIVEAU
FROM   T_VEHICULE_VHC  
ORDER  BY VHC_BG;

Donne un résultat insatisfaisant :

NOM_IDENTE                       VHC_ID      VHC_BG      VHC_BD      VHC_NIVEAU
-------------------------------- ----------- ----------- ----------- ----------
ALL                              1           1           26          0
 SEA                             2           2           7           1
  SUBMARINE                      5           3           4           2
  BOAT                           6           5           6           2
 EARTH                           3           8           19          1
  CAR                            7           9           10          2
  TWO WHEELS                     8           11          16          2
   MOTORCYCLE                    12          12          13          3
   BICYCLE                       13          14          15          3
  TRUCK                          9           17          18          2
 AIR                             4           20          25          1
  ROCKET                         10          21          22          2
  PLANE                          11          23          24          2

Au niveau 1, « SEA » est avant « EARTH » qui lui même est avant « AIR ». Dans les deux roues (« TWO WHEELS »), « MOTORCYCLE » précède « BICYCLE ». Enfin, « CAR », « TWO WHEELS » et « TRUCK » sont mélangés.
Il n’est pas possible d’obtenir un meilleur ordonnancement directement basé sur les valeurs des colonnes actuelles de la table.

Mais la technique de l’arbre intervallaire permet d’ordonner les frères entre eux. Il suffit donc de bouger les bornes droites et gauches pour que cela corresponde à l’ordre demandé.

2 – PREMIÈRE SOLUTION

Elle consiste donc à réordonner les bornes gauche et droite.

La nouvelle table pour ce faire :

CREATE TABLE T_VEHICULE2_VHC
(VHC_ID         INTEGER NOT NULL PRIMARY KEY,
 VHC_BG         INTEGER,
 VHC_BD         INTEGER,
 VHC_NIVEAU     SMALLINT,
 VHC_NOM        VARCHAR(16));

Les données réarrangées :

INSERT INTO T_VEHICULE2_VHC VALUES ( 1,  1, 26, 0, 'ALL');
INSERT INTO T_VEHICULE2_VHC VALUES ( 2, 20, 25, 1, 'SEA');
INSERT INTO T_VEHICULE2_VHC VALUES ( 3,  8, 19, 1, 'EARTH');
INSERT INTO T_VEHICULE2_VHC VALUES ( 4,  2,  7, 1, 'AIR');
INSERT INTO T_VEHICULE2_VHC VALUES ( 5, 23, 24, 2, 'SUBMARINE');
INSERT INTO T_VEHICULE2_VHC VALUES ( 6, 21, 22, 2, 'BOAT');
INSERT INTO T_VEHICULE2_VHC VALUES ( 7,  9, 10, 2, 'CAR');
INSERT INTO T_VEHICULE2_VHC VALUES ( 8, 13, 18, 2, 'TWO WHEELS');
INSERT INTO T_VEHICULE2_VHC VALUES ( 9, 11, 12, 2, 'TRUCK');
INSERT INTO T_VEHICULE2_VHC VALUES (10,  5,  6, 2, 'ROCKET');
INSERT INTO T_VEHICULE2_VHC VALUES (11,  3,  4, 2, 'PLANE');
INSERT INTO T_VEHICULE2_VHC VALUES (12, 16, 17, 3, 'MOTORCYCLE');
INSERT INTO T_VEHICULE2_VHC VALUES (13, 14, 15, 3, 'BICYCLE');

La requête :

SELECT CAST(SPACE(VHC_NIVEAU) + VHC_NOM AS VARCHAR(32)) AS NOM_IDENTE,
       VHC_ID, VHC_BG, VHC_BD, VHC_NIVEAU
FROM   T_VEHICULE2_VHC  
ORDER  BY VHC_BG;

Le résultat :

NOM_IDENTE                       VHC_ID      VHC_BG      VHC_BD      VHC_NIVEAU
-------------------------------- ----------- ----------- ----------- ----------
ALL                              1           1           26          0
 AIR                             4           2           7           1
  PLANE                          11          3           4           2
  ROCKET                         10          5           6           2
 EARTH                           3           8           19          1
  CAR                            7           9           10          2
  TRUCK                          9           11          12          2
  TWO WHEELS                     8           13          18          2
   BICYCLE                       13          14          15          3
   MOTORCYCLE                    12          16          17          3
 SEA                             2           20          25          1
  BOAT                           6           21          22          2
  SUBMARINE                      5           23          24          2

Critique de la première solution

La requête finale est simple. En revanche le coût est reporté lors des mises à jours (généralement peu nombreuses dans les arborescences) mais cela oblige souvent à réordonner tout l’arbre (ce qui peut se minimiser en modélisant l’arbre intervallaire à côté de la table contenant les données).
De plus, elle n’est pas satisfaisante si d’autres colonnes complique la structure de la table et qu’il faut en tenir compte dans la solution (par exemple de multiples arborescences).

3 – UNE SOLUTION GÉNÉRIQUE

Il existe une façon de faire globale, mais elle nécessite hélas une requête récursive en sus d’être gourmande en données. Cette solution consiste à rajouter un « chemin » composé d’une mixité de données comprenant les ancêtres alternés avec la position ordinale des frères entre eux. Pour la faire fonctionner correctement il est nécessaire d’utiliser une fonction de remplissage que j’ai intitulé PADMASK :

--===========================================================================--
-- Masque de caractères avec fusion alignée
--===========================================================================--
CREATE FUNCTION  [F_PADMASK](@DATA NVARCHAR(1024),
                             @MASK NVARCHAR(1024),
                             @ALIGN CHAR(6))
RETURNS NVARCHAR(1024)
AS
/******************************************************************************
* Fonction de masque pour une donées polymorphe retournée en chaine de car.   *
*******************************************************************************
* Fred. Brouard - http://sqlpro.developpez.com - www.sqlspot.com - 2012-07-12 *
*******************************************************************************
* Fusionne une donnée chaine avec un masque aligné à droite ou à gauche       *
* Exemples :                                                                  *
* SELECT dbo.F_PADMASK('ABC', '*****', 'LEFT' )   --> 'ABC**'                 *
* SELECT dbo.F_PADMASK(123, '00000', 'RIGHT')     --> '00123'                 *
* SELECT dbo.F_PADMASK('ABCDEFG', '***', 'LEFT')  --> 'EFG'                   *
* SELECT dbo.F_PADMASK('ABCDEFG', '***', 'RIGHT') --> 'ABC'                   *
******************************************************************************/
BEGIN
   IF @MASK IS NULL RETURN '';
   IF @DATA IS NULL RETURN @MASK;
   IF UPPER(@ALIGN) IN ('RIGHT', 'DROIT', 'DROITE')
      SET @ALIGN = 'RIGHT'
   ELSE
      SET @ALIGN = 'LEFT';    
-- masque avec alignement à gauche (alpha)  
   IF @ALIGN = 'LEFT'
   BEGIN
      IF LEN(@MASK) > LEN(@DATA)
         SET @DATA = @DATA + SUBSTRING(@MASK, LEN(@DATA) + 1, LEN(@MASK) - LEN(@DATA));
      IF LEN(@MASK)  LEN(@DATA)
         SET @DATA = SUBSTRING(@MASK, 1, LEN(@MASK) - LEN(@DATA)) + @DATA;
      IF LEN(@MASK) < LEN(@DATA)
         SET @DATA = SUBSTRING(@DATA, LEN(@DATA) - LEN(@MASK) + 1, LEN(@MASK));
   END;
   RETURN @DATA;  
END
GO

NOTA : la fonction F_PADMASK a été écrite pour MS SQL Server, et peut aisément être traduite en PGPL/SQL pour PostGreSQL.

Voici maintenant la requête :

WITH
TA AS -- crée un indice numérique global d'ordonnancement alphabétique des libellés et le transforme en chaine complété avec des zéros
(SELECT VHC_ID, VHC_BG, VHC_BD, VHC_NIVEAU, VHC_NOM,
        dbo.F_PADMASK(CAST(ROW_NUMBER() OVER(ORDER BY VHC_NOM) AS VARCHAR(10)), '00000000000', 'RIGHT')  AS ORDRE
 FROM   T_VEHICULE_VHC),
T0 AS -- concatène un mixte de chemin et d'indice alphabétique dans une colonne intitulée PATH_MIXTE
(SELECT VHC_ID, VHC_BG, VHC_BD, VHC_NIVEAU, VHC_NOM, ORDRE,
        CAST(dbo.F_PADMASK(VHC_NOM, '****************', 'LEFT') + ORDRE AS NVARCHAR(max)) AS PATH_MIXTE
 FROM   TA
 WHERE  VHC_NIVEAU = 0
 UNION ALL
 SELECT T1.VHC_ID, T1.VHC_BG, T1.VHC_BD, T1.VHC_NIVEAU, T1.VHC_NOM, T1.ORDRE,
        T0.PATH_MIXTE + dbo.F_PADMASK(T1.VHC_NOM, '****************', 'LEFT') + T1.ORDRE
 FROM   TA AS T1
        INNER JOIN T0
               ON T1.VHC_NIVEAU = T0.VHC_NIVEAU + 1
               AND T1.VHC_BG > T0.VHC_BG
               AND T1.VHC_BD < T0.VHC_BD)
SELECT CAST(SPACE(VHC_NIVEAU) + VHC_NOM AS VARCHAR(32)) AS NOM_IDENTE,
       VHC_ID, VHC_BG, VHC_BD, VHC_NIVEAU, PATH_MIXTE
FROM   T0  
ORDER  BY PATH_MIXTE;

Comme indiqué, la colonne surnuméraire de tri, PATH_MIXTE, va contenir le chemin jusqu’au nœud en cours avec entre chaque nom d’élément sa position relative dans la fratrie. Le nécessité d’utiliser la fonction de remplissage est lié au fait que notre colonne de tri contient une alternance de données numérique et alphabétique qu’il faut ordonner ensemble. or les nombres sont alignés à droite et les mots à gauche. la fonction F_PADMASK permet de coordonner ces alignements. On comprend mieux la chose en voyant ce quelle contient :

NOM_IDENTE          VHC_ID      VHC_BG      VHC_BD      VHC_NIVEAU PATH_MIXTE                                                                                                    
------------------- ----------- ----------- ----------- ---------- ------------------------------------------------------------------------------------------------------------
ALL                 1           1           26          0          ALL*************00000000002
 AIR                4           20          25          1          ALL*************00000000002AIR*************00000000001
  PLANE             11          23          24          2          ALL*************00000000002AIR*************00000000001PLANE***********00000000008
  ROCKET            10          21          22          2          ALL*************00000000002AIR*************00000000001ROCKET**********00000000009
 EARTH              3           8           19          1          ALL*************00000000002EARTH***********00000000006
  CAR               7           9           10          2          ALL*************00000000002EARTH***********00000000006CAR*************00000000005
  TRUCK             9           17          18          2          ALL*************00000000002EARTH***********00000000006TRUCK***********00000000012
  TWO WHEELS        8           11          16          2          ALL*************00000000002EARTH***********00000000006TWO WHEELS******00000000013
   BICYCLE          13          14          15          3          ALL*************00000000002EARTH***********00000000006TWO WHEELS******00000000013BICYCLE*********00000000003
   MOTORCYCLE       12          12          13          3          ALL*************00000000002EARTH***********00000000006TWO WHEELS******00000000013MOTORCYCLE******00000000007
 SEA                2           2           7           1          ALL*************00000000002SEA*************00000000010
  BOAT              6           5           6           2          ALL*************00000000002SEA*************00000000010BOAT************00000000004
  SUBMARINE         5           3           4           2          ALL*************00000000002SEA*************00000000010SUBMARINE*******00000000011

NOTA : le nombre de caractères de remplissage pour la partie alphabétique (ici colonne VHC_NOM) dépend de la longueur de la colonne (ici 16) définit à la construction de la table.

ATTENTION : Certaines formulations, comme celle données ici sur Internet « Ordering recursive result set in SQL Server » sont fausses. Je vous laisse deviner pourquoi !

Le site web sur le SQL et les SGBDR
MVP Microsoft SQL Server


Frédéric Brouard, alias SQLpro, ARCHITECTE DE DONNÉES
Expert  S.G.B.D  relationnelles   et   langage  S.Q.L
Moste  Valuable  Professionnal  Microsoft  SQL Server
Société SQLspot  :  modélisation, conseil, formation,
optimisation,  audit,  tuning,  administration  SGBDR
Enseignant: CNAM PACA, ISEN Toulon, CESI Aix en Prov.

L’ntreprise SQL Spot

Une réflexion au sujet de « Tri combiné dans un arbre intervallaire »

  1. Avatar de fredochefredoche

    Bonjour
    M’étant inspiré de tes premières publications sur le sujet pour réaliser un moteur d’arborescence, j’avais cette problématique de tri alphabétique comme contrainte.
    J’avais choisi quelque chose qui se rapproche de la 1ère voie : je maintenais l’ensemble de l’arbre ordonné alphabétiquement. Pour ce faire, n’ayant pas ton talent en SQL, j’avais une procédure qui en cas de changement dans l’arbre (update de label ou insert de nouveaux noeuds), parcourait récursivement l’arbre à partir du niveau de modification, utilisait un curseur pour construire des requêtes de mises à jour des bornes gauche et droite.
    Les updates à exécuter étaient stockés dans une table temporaire, et l’ensemble de ces updates exécutés à la fin, le tout dans une transaction.

    Je n’ai plus cette contrainte désormais. Avec AJAX, je requête mes noeuds à visualiser par niveau de manière récursive (parent -enfants) et j’ordonne à chaque niveau(requête). L’ordre alpha n’est utile que dans ces interfaces de visualisation. Je n’ai donc plus de coût de mise à jour.

    Effectivement les mises à jour d’arbres sont peu fréquentes. Le cout de la mise à jour était assez important, le cout des lectures qui récupéraient l’arbre entier par contre étaient insignifiants puisqu’il suffisait d’ordonner la requête selon la borne gauche. Ce qui m’intéressait était la performance en lecture de l’ensemble de l’arbre, ordonné.

    Je ne sais pas trop ce que tu penses de ma solution qui doit être très très « bricolage » à tes yeux ?

    Ta seconde solution est elle rapide en lecture sur de grands arbres, pour une lecture entière ?
    C’était une autre époque, je n’ai plus désormais le besoin de rendre l’arbre en entier sur une seule requête, avec AJAX.

Laisser un commentaire