Arbres intervallaires : procédure de dérécursivation

Dans cet article sur les arbres intervallaires, je n’ai pas mentionné comment effectuer la transformation d’une table modélisée par auto référence en une table en mode intervallaire. Voici comment procéder…

La procédure ci dessous utilise du code SQL dynamique pour intégrer les données à transformer dans des tables pseudo temporaires pour ensuite les reverser dans la table d’origine. Il convient de créer préalablement les colonnes nécessaire pour recevoir les bornes gauches et droite.

******************************************************************************
-- création d'une procédure de calcul des bornes des intervalles de l'arbre  
******************************************************************************/
-- création de la procédure _P_DERECURSIVE_TREE
CREATE OR ALTER PROCEDURE dbo._P_DERECURSIVE_TREE @TABLE_SCHEMA sysname,
                                        @TABLE_NAME   sysname,
                                        @COL_ID       sysname,
                                        @COL_ID_PERE  sysname,
                                        @COL_BG       sysname,
                                        @COL_BD       sysname,
                                        @COL_NIVO     sysname  
AS
/******************************************************************************
* PROCÉDURE DE CALCUL D'UN ARBRE INTERVALLAIRE ACTUELLEMENT EN AUTO RÉFÉRENCE *
*******************************************************************************
* Frédéric Brouard   -   SQLpro   -   http://www.sqlspot.com   -   2004-06-10 *
*******************************************************************************
* PARAMÈTRES :                                                                *
*    @TABLE_SCHEMA schéma SQL de la table (en principe dbo)                   *
*    @TABLE_NAME   nom de la table                                            *
*    @COL_ID       nom de la colonne colonne clef primaire                    *
*    @COL_ID_PERE  nom de la col. clef étrangère en auto réf. à la clef prim. *
*    @COL_BG       nom de la colonne borne gauche                             *
*    @COL_BD       nom de la colonne borne droite                             *
******************************************************************************/


SET NOCOUNT ON;

-- variables locales
DECLARE @SQL NVARCHAR(MAX),@COMPTEUR BIGINT,@MAX_CPTR BIGINT, @POINTEUR BIGINT;

-- on créé la table ##_TMP_TREE_SQLPRO pour stocker temporairement
-- les clefs et les valeurs en autoréférence de la table à traiter
   CREATE TABLE ##_TMP_TREE_SQLPRO
   (CLEF     BIGINT NOT NULL,
    CLEF_REF BIGINT);

 -- on créé la table ##_TMP_STACK_SQLPRO pour gérer la pile de dérécursivation
   CREATE TABLE ##_TMP_STACK_SQLPRO
   (PILE     BIGINT NOT NULL,
    CLEF     BIGINT NOT NULL PRIMARY KEY,
    GAUCHE   BIGINT,
    DROITE   BIGINT,
    DT       DATETIME2 DEFAULT SYSDATETIME());
   CREATE INDEX X_CC2 ON ##_TMP_STACK_SQLPRO (PILE) WITH (FILLFACTOR = 80);
--END;

-- on y insère les valeurs dedans
SET @SQL = 'INSERT INTO ##_TMP_TREE_SQLPRO SELECT ' + @COL_ID + ', '
         + @COL_ID_PERE + ' FROM ' + @TABLE_SCHEMA + '.'  + @TABLE_NAME
EXECUTE (@SQL)
 
-- initialisation
SELECT @COMPTEUR = 2, @MAX_CPTR = 2 * COUNT_BIG(*), @POINTEUR = 1
FROM ##_TMP_TREE_SQLPRO;
 
-- insertion de la racine de l'arbre dans la pile
INSERT INTO ##_TMP_STACK_SQLPRO (PILE, CLEF, GAUCHE, DROITE)
SELECT 1, CLEF, 1, @MAX_CPTR
  FROM ##_TMP_TREE_SQLPRO
 WHERE CLEF_REF IS NULL;
 
-- et on supprime la référence à la racine
DELETE FROM ##_TMP_TREE_SQLPRO
 WHERE CLEF_REF IS NULL;
 
-- tant que l'on a pas traité toute l'enveloppe intervallaire
WHILE @COMPTEUR <= (@MAX_CPTR - 2)
BEGIN
 
-- s'il existe des lignes à traiter
   IF EXISTS (SELECT *
              FROM   ##_TMP_STACK_SQLPRO AS S
                     INNER JOIN ##_TMP_TREE_SQLPRO AS T
                           ON S.CLEF = T.CLEF_REF
              WHERE  S.PILE = @POINTEUR)
 
   BEGIN  
 
-- empile tant que la ligne analysée a des fils (calcul de la borne gauche)
       INSERT INTO ##_TMP_STACK_SQLPRO (PILE, CLEF, GAUCHE, DROITE)
       SELECT @POINTEUR + 1, MIN(T.CLEF), @COMPTEUR, NULL
       FROM   ##_TMP_STACK_SQLPRO AS S
              INNER JOIN ##_TMP_TREE_SQLPRO AS T
                    ON S.CLEF = T.CLEF_REF
       WHERE  S.PILE = @POINTEUR;
-- supprime la ligne analysée
       DELETE FROM ##_TMP_TREE_SQLPRO
       WHERE CLEF = (SELECT CLEF
                     FROM   ##_TMP_STACK_SQLPRO
                     WHERE  PILE = @POINTEUR + 1);
-- incrémente compteur et pointeur
        SET @COMPTEUR = @COMPTEUR + 1;
        SET @POINTEUR = @POINTEUR + 1;
 
     END
     ELSE
     BEGIN  
 
-- dépile parce que que la ligne analysée n'a plus de fils
        UPDATE ##_TMP_STACK_SQLPRO
        SET    DROITE = @COMPTEUR,
               PILE = - PILE -- pops the Stack
        WHERE  PILE = @POINTEUR
 
-- incrémente lecompteur et décrémente le pointeur
       SELECT @COMPTEUR = @COMPTEUR + 1, @POINTEUR = @POINTEUR - 1;
 
     END;
END;

-- met à jour la table cible avec ces calculs
SET @SQL = ' UPDATE ' + @TABLE_SCHEMA + '.' + @TABLE_NAME +
           ' SET    ' + @COL_BG + ' = S.GAUCHE, ' +
                        @COL_BD + ' = COALESCE(S.DROITE, ' + CAST(@MAX_CPTR-1 AS VARCHAR(32)) +'), '
                      + @COL_NIVO + ' = ABS(PILE) ' +
           ' FROM   ##_TMP_STACK_SQLPRO S INNER JOIN ' + @TABLE_NAME + ' T ON S.CLEF = T.'+@COL_ID
EXEC (@SQL)

-- suppression des tables pseudo temporaires
IF OBJECT_ID('tempdb..##_TMP_TREE_SQLPRO') IS NOT NULL
   EXEC ('DROP TABLE ##_TMP_TREE_SQLPRO' )

IF OBJECT_ID('tempdb..##_TMP_STACK_SQLPRO') IS NOT NULL
   EXEC ('DROP TABLE ##_TMP_STACK_SQLPRO')

GO

Utilisation

Soit la tables des employés de l’entreprise comme suit :

CREATE TABLE dbo.T_EMPLOYE_EMP
(EMP_ID              INT PRIMARY KEY,
 EMP_ID_CHEF         INT REFERENCES T_EMPLOYE_EMP (EMP_ID),
 EMP_NOM             VARCHAR(32) NOT NULL,
 EMP_DATE_NAISSANCE  DATETIME);

Il faut lui ajouter les 3 colonnes composant les bornes gauches et droites ainsi que le niveau. par exemple :

ALTER TABLE dbo.T_EMPLOYE_EMP
   ADD TREE_BG INT, TREE_DB INT, TREE_NIVEAU INT;

Il suffit maintenant de lancer la procédure de dérécursivation. Exemple :

EXEC dbo._P_DERECURSIVE_TREE @TABLE_SCHEMA 'dbo',
                             @TABLE_NAME   'T_EMPLOYE_EMP',
                             @COL_ID       'EMP_ID',
                             @COL_ID_PERE  'EMP_ID_CHEF',
                             @COL_BG       'TREE_BG',
                             @COL_BD       'TREE_BD',
                             @COL_NIVO     'TREE_NIVEAU';

ATTENTION : cette procédure peut prendre beaucoup de temps. Par exemple pour 5000 lignes dans la table comptez au moins 1 minutes sur un PC rapide. Et comme son temps de traitement n’est pas linéaire, cela peut durer très très longtemps sur de très grosses tables. Dans ce cas optez pour des tables « in memory » au lieu de tables temporaires pour ce traitement.

LE CODE ! LE CODE ! LE CODE ! LE CODE ! LE CODE ! LE CODE ! LE CODE ! LE CODE ! LE CODE ! LE CODE !

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’entreprise SQL Spot
Le site web sur le SQL et les SGBDR

MVP Microsoft SQL
Server

Développez et administrez pour la performance avec SQL Server 2014

Développez et administrez pour la performance avec SQL Server 2014

Une réflexion au sujet de « Arbres intervallaires : procédure de dérécursivation »

Laisser un commentaire