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
(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 ( 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 :
VHC_ID, VHC_BG, VHC_BD, VHC_NIVEAU
FROM T_VEHICULE_VHC
ORDER BY VHC_BG;
Donne un résultat insatisfaisant :
-------------------------------- ----------- ----------- ----------- ----------
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 :
(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 ( 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 :
VHC_ID, VHC_BG, VHC_BD, VHC_NIVEAU
FROM T_VEHICULE2_VHC
ORDER BY VHC_BG;
Le résultat :
-------------------------------- ----------- ----------- ----------- ----------
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 :
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 :
------------------- ----------- ----------- ----------- ---------- ------------------------------------------------------------------------------------------------------------
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
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
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.