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  
******************************************************************************/
-- la procédure P_DERECURSIVE_TREE existe t-elle dans la base ?  
-- Si oui, la supprimer !
IF EXISTS (SELECT *
           FROM   INFORMATION_SCHEMA.ROUTINES
           WHERE  ROUTINE_SCHEMA = 'dbo'
             AND  ROUTINE_NAME = 'P_DERECURSIVE_TREE'
             AND  ROUTINE_TYPE = 'PROCEDURE')
   DROP PROCEDURE P_DERECURSIVE_TREE
GO
 
-- création de la fonction P_EXPLORE_DIR
CREATE PROCEDURE dbo.P_DERECURSIVE_TREE @TABLE_SCHEMA sysname,
                                        @TABLE_NAME   sysname,
                                        @COL_ID       sysname,
                                        @COL_ID_PERE  sysname,
                                        @COL_BG       sysname,
                                        @COL_BD       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                             *
******************************************************************************/
 
DECLARE @SQL NVARCHAR(4000)
 
-- la table TMP_TREE_SQLPRO existe t-elle dans la base B_DATASAPIENS_OS_FILE
-- pour l'utilisateur courant ? Si oui, la virer !
IF EXISTS (SELECT *
           FROM   INFORMATION_SCHEMA.TABLES
           WHERE  TABLE_SCHEMA = 'dbo'
             AND  TABLE_NAME = 'TMP_TREE_SQLPRO')
   BEGIN
      SET @SQL = 'DROP TABLE dbo.TMP_TREE_SQLPRO'
      EXEC (@SQL)
   END
 
-- on créé la table TMP_TREE_SQLPRO pour stocker temporairement les identifiants
-- et autorelations de la table à traiter
CREATE TABLE dbo.TMP_TREE_SQLPRO
(CLEF     INT NOT NULL,
 CLEF_REF INT);
 
-- la table TMP_STACK_SQLPRO existe t-elle dans la base B_DATASAPIENS_OS_FILE
-- pour l'utilisateur courant ? Si oui, la virer !
IF EXISTS (SELECT *
           FROM   INFORMATION_SCHEMA.TABLES
           WHERE  TABLE_SCHEMA = 'dbo'
             AND  TABLE_NAME = 'TMP_STACK_SQLPRO')
   BEGIN
      SET @SQL = 'DROP TABLE dbo.TMP_STACK_SQLPRO'
      EXEC (@SQL)
   END
 
-- on créé la table TMP_STACK_SQLPRO pour gérer une pile afin de dérécursiver l'arbre
CREATE TABLE dbo.TMP_STACK_SQLPRO
(PILE INTEGER NOT NULL,
 CLEF CHAR(10) NOT NULL,
 GAUCHE INTEGER,
 DROITE INTEGER);
 
-- on y insère les valeurs dedans
SET @SQL = 'INSERT INTO dbo.TMP_TREE_SQLPRO SELECT ' + @COL_ID + ', ' + @COL_ID_PERE  
         + ' FROM ' + @TABLE_SCHEMA + '.'  + @TABLE_NAME
EXECUTE (@SQL)
 
 
-- variables locales
DECLARE @COMPTEUR INTEGER;
DECLARE @MAX_CPTR INTEGER;
DECLARE @POINTEUR INTEGER;
 
-- initialisation
SET @COMPTEUR = 2;
SET @MAX_CPTR = 2 * (SELECT COUNT(*) FROM TMP_TREE_SQLPRO);
SET @POINTEUR = 1;
 
-- insertion de la racine de l'arbre dans la pile
INSERT INTO TMP_STACK_SQLPRO
SELECT 1, CLEF, 1, NULL
  FROM dbo.TMP_TREE_SQLPRO
 WHERE CLEF_REF IS NULL;
 
-- et on supprime la référence à la racine
DELETE FROM dbo.TMP_TREE_SQLPRO
 WHERE CLEF_REF IS NULL;
 
-- tant que l'on a pas traité toute l'enveloppe intervallaire
WHILE @COMPTEUR <= (@MAX_CPTR)
BEGIN
 
-- s'il existe des lignes à traiter
   IF EXISTS (SELECT *
              FROM   dbo.TMP_STACK_SQLPRO AS S
                     INNER JOIN dbo.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 dbo.TMP_STACK_SQLPRO
       SELECT @POINTEUR + 1, MIN(T.CLEF), @COMPTEUR, NULL
       FROM   dbo.TMP_STACK_SQLPRO AS S
              INNER JOIN dbo.TMP_TREE_SQLPRO AS T
                    ON S.CLEF = T.CLEF_REF
       WHERE  S.PILE = @POINTEUR;
-- supprime la ligne analysée
       DELETE FROM dbo.TMP_TREE_SQLPRO
       WHERE CLEF = (SELECT CLEF
                     FROM   dbo.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 (calcul de la borne droite)
        UPDATE dbo.TMP_STACK_SQLPRO
        SET    DROITE = @COMPTEUR,
               PILE = - PILE -- pops the Stack
        WHERE  PILE = @POINTEUR
 
-- incrémente compteur et décrémente pointeur
       SET @COMPTEUR = @COMPTEUR + 1;
       SET @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 + ' = S.DROITE' +
           ' FROM   dbo.TMP_STACK_SQLPRO S INNER JOIN ' + @TABLE_NAME + ' T ON S.CLEF = T.'+@COL_ID
EXEC (@SQL)
 
-- suppression des tables pseudo temporaires
IF EXISTS (SELECT *
           FROM   INFORMATION_SCHEMA.TABLES
           WHERE  TABLE_SCHEMA = 'dbo'
             AND  TABLE_NAME = 'TMP_TREE_SQLPRO')
   BEGIN
      SET @SQL = 'DROP TABLE dbo.TMP_TREE_SQLPRO'
      EXEC (@SQL)
   END
IF EXISTS (SELECT *
           FROM   INFORMATION_SCHEMA.TABLES
           WHERE  TABLE_SCHEMA = 'dbo'
             AND  TABLE_NAME = 'TMP_STACK_SQLPRO')
   BEGIN
      SET @SQL = 'DROP TABLE dbo.TMP_STACK_SQLPRO'
      EXEC (@SQL)
   END
 
GO

Voici maintenant comment utiliser cette procédure à traver un exemple…


CREATE TABLE dbo.FAMILLE  
(FAM_ID INTEGER, FAM_LIB VARCHAR(16), FAM_PERE INTEGER)
GO
 
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (0, 'Transport', NULL)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (1, 'Terrestre', 0)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (2, 'Marin', 0)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (3, 'Aérien', 0)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (4, 'Voiture', 1)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (5, 'Camion', 1)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (6, 'Moto', 1)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (7, 'Vélo', 1)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (8, 'Hélico', 3)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (9, 'Avion', 3)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (10, 'ULM', 3)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (11, 'Fusée', 3)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (12, 'Parachute', 3)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (13, 'Planeur', 3)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (14, 'Voilier', 2)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (15, 'Paquebot', 2)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (16, 'Planche à voile', 2)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (17, 'Trail', 6)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (18, 'Side-car', 6)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (19, 'Civil', 9)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (20, 'Tourisme', 9)  
INSERT INTO dbo.FAMILLE (FAM_ID, FAM_LIB, FAM_PERE) VALUES (21, 'Militaire', 9)
GO
 
 
/******************************************************************************
-- transformation du mode auto référence en mode intervallaire
******************************************************************************/
 
-- modification de la table d'origine pour ajout des bornes gauches et droite :
ALTER TABLE dbo.FAMILLE ADD FAM_BG INT;
ALTER TABLE dbo.FAMILLE ADD FAM_BD INT;
GO
 
-- exécution de la transformation
EXEC dbo.P_DERECURSIVE_TREE 'dbo', 'FAMILLE', 'FAM_ID', 'FAM_PERE', 'FAM_BG', 'FAM_BD'
GO
 
-- indexation
CREATE INDEX X_FAM_RECURINTERVAL ON dbo.FAMILLE (FAM_BG, FAM_BD) WITH FILLFACTOR = 90;
 
/******************************************************************************
-- ajout du niveau
******************************************************************************/
 
-- modification de la table d'origine pour ajout du niveau :
ALTER TABLE dbo.FAMILLE ADD FAM_NIVEAU INT;
GO
 
-- mise à jour du niveau :
UPDATE dbo.FAMILLE
SET    FAM_NIVEAU = N
FROM   dbo.FAMILLE AS F
INNER JOIN (SELECT *, (SELECT COUNT(*)  
                       FROM   dbo.FAMILLE AS Tin  
                       WHERE  Tin.FAM_BG < Tout.FAM_BG
                         AND  Tin.FAM_BD > Tout.FAM_BD) AS N
            FROM   dbo.FAMILLE AS Tout) AS FN
            ON F.FAM_ID = FN.FAM_ID;
             
-- vérification :
SELECT *
FROM   dbo.FAMILLE;

CQFD !


Frédéric BROUARD, Spécialiste modélisation, bases de données, optimisation, langage SQL.
Le site sur le langage SQL et les S.G.B.D. relationnels : http://sqlpro.developpez.com/
Expert SQL Server http://www.sqlspot.com : audit, optimisation, tuning, formation
* * * * * Enseignant au CNAM PACA et à l’ISEN à Toulon * * * * *

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

Laisser un commentaire