Intéressé par des cours d'informatique en ligne ?
Visitez mon nouveau site https://www.yesik.it !

Beaucoup de donnée s'accomodent naturellement d'une représentation hiérarchique. Que ce soient les catégories d'un wiki, des groupes d'utilisateurs ou les messages dans une liste de diffusion, toutes ces données peuvent être organisées sous forme de graphes ou d'arbres. La manière naturelle de représenter cette structure de données est par une liste d'adjascence où chaque élément contient une référence sur son parent. Or cela suppose la possibilité d'effectuer des requêtes récursives pour pouvoir trouver l'ensemble des parents ou enfants d'un noeud.

Malheureusement, Apache Derby, comme beaucoup de SGBD-R (Système de Gestion de Bases de Données Relationnelles) , ne supporte pas directement les requêtes récursives. Heureusement, Derby peut facilement être doté de fonctions utilisateurs – et celles-ci, écrites en Java – permettent de contourner cette limitation. C'est ce que nous allons voir ici.

Le problème

Après cette introduction qui a peut-être soulevée plus de questions qu'elle n'a apporté de réponses, prenons quelques instants pour examiner un cas typique de ce genre de problème. Considérons le groupe de grande distribution Système Z. Ce groupe possède des magasins affiliés en France et en Europe. Au gré de l'évolution du groupe et de l'affiliation de nouveaux magasins, ceux-ci se sont vus rattachés à des zones. Celles-ci peuvent être à l'échelle d'une ville, d'une région voire même d'un pays. Le groupement en zone permet de centraliser les approvisionnements et participe à la gestion administrative de la chaîne de magasins, tout en permettant une relative autonomie et suffisamment de souplesse pour s'adapter aux besoins du marché local. Çà, c'était pour les arguments commerciaux.

D'un point de vue plus technique maintenant. Évidemment la liste des magasins et la zone à laquelle ils appartiennent doivent être enregistrés dans le système d'information de l'entreprise. En ce qui concerne les informations relatives aux différents points de vente, rien de très extraordinaire:

CREATE TABLE Magasins (
    -- Identifiant unique
    code CHAR(10) PRIMARY KEY, 
 
    -- La zone à laquelle est rattaché le magasin 
    zone INT REFERENCES Zones(id)
 
    -- Et autres info sur le magasin:
    -- , gerant CHAR(80) NOT NULL
    -- , adresse CHAR(200) NOT NULL
    -- ...
    -- ...
)

Ben? ça marche pas...

Inutile de vous précipitez sur votre terminal pour rentrer cette requête: elle échouera forcément puisque le table Magasins fait référence à la table Zones ... que nous n'avons pas encore créée!

Quand aux zones de gestion, celle-ci ont la particularité d'être incluses les unes dans les autres. Ainsi, par exemple, la zone Rennes est une sous-zone de Bretagne. Le moyen le plus simple et évident de modéliser cela avec SQL est d'utiliser une liste d'adjascence. C'est à dire d'avoir une relation entre une zone et son parent immédiat:

CREATE TABLE Zones (
    -- Identifiant unique
    id INT PRIMARY KEY GENERATED ALWAYS AS IDENTITY,
 
    -- références à la zone ''parente''
    parent INT REFERENCES Zones(id),
 
    -- désignation
    designation CHAR(80) NOT NULL
)

Maintenant que nous avons les deux tables, nous pouvons peupler la base avec les informations correspondantes à celles de l'organigramme du début:

INSERT INTO Zones ( parent, designation ) VALUES
    ( NULL, 'France');
INSERT INTO Zones ( parent, designation ) VALUES
    ( (SELECT id FROM Zones WHERE designation = 'France'), 'Bretagne' );
INSERT INTO Zones ( parent, designation ) VALUES
    ( (SELECT id FROM Zones WHERE designation = 'Bretagne'), 'Rennes' );
INSERT INTO Zones ( parent, designation ) VALUES
    ( (SELECT id FROM Zones WHERE designation = 'France'), 'Nord' );
INSERT INTO Zones ( parent, designation ) VALUES
    ( NULL, 'Belgique');
 
INSERT INTO Magasins ( code, zone ) VALUES
    ( 'RENNES1', (SELECT id FROM Zones WHERE designation = 'Rennes') ),
    ( 'RENNES2', (SELECT id FROM Zones WHERE designation = 'Rennes') ),
    ( 'STMALO1', (SELECT id FROM Zones WHERE designation = 'Bretagne') ),
    ( 'LILLE1', (SELECT id FROM Zones WHERE designation = 'Nord') ),
    ( 'LIEGES1', (SELECT id FROM Zones WHERE designation = 'Belgique') )
;

Muni de toutes ces informations, il est possible de répondre à des questions comme:

Examinons justement de plus près cette dernière requête. Et en particulier, demandons nous ce qu'il se passerait si l'on voulait les magasins de la zone Bretagne:

SELECT Magasins.code FROM Zones INNER JOIN Magasins ON Zones.id = Magasins.zone
    WHERE Zones.designation = 'Bretagne'
 
-- STMALO1

Cette requête ne renvoie qu'un seul résultat: STMALO1. Ce qui est à la fois vrai et faux. Vrai parce qu'effectivement c'est le seul magasin directement dans la zone Bretagne. Par contre, il existe des magasins indirectement dedans, comme ceux de Rennes. La solution? Utiliser une auto-jointure pour chercher les magasins "inclus dans les zones incluses dans Bretagne":

SELECT Magasins.code FROM Zones AS Parent 
                     INNER JOIN Zones AS Enfants ON Parent.id = Enfants.parent
                     INNER JOIN Magasins ON Enfants.id = Magasins.zone
    WHERE Parent.designation = 'Bretagne'
 
-- RENNES1   
-- RENNES2

Ce qui donne bien RENNES1 et RENNES2, mais plus STMALO1! "Ben oui!", vous dites-vous, puisque je cherche les magasins dans les zones incluses dans la zone Bretagne (deux niveaux d'imbrication), je ne peux pas trouver les magasins inclus directement en Bretagne (un seul niveau d'imbrication). Qu'à cela ne se tienne, on peut corriger cela avec une UNION (par exemple):

SELECT Magasins.code FROM Zones AS Parent INNER JOIN Zones AS Enfants ON Parent.id = Enfants.parent
                                          INNER JOIN Magasins ON Enfants.id = Magasins.zone
    WHERE Parent.designation = 'Bretagne'
UNION 
SELECT Magasins.code FROM Zones INNER JOIN Magasins ON Zones.id = Magasins.zone
    WHERE Zones.designation = 'Bretagne'
 
-- RENNES1   
-- RENNES2
-- STMALO1

Hola! Arrêtons les frais ici: cette requête commence à grossir en dehors de toute proportion alors qu'il n'y a que deux niveaux impliqués. Alors imaginez s'il y en avait 5 ou 10! Par ailleurs, comment faire si l'on ne connaît pas à l'avance le nombre maximum de niveaux imbriqués les uns dans les autres? Pour toutes ces raisons, SQL2003 introduit les requêtes récursives. Que Derby ne supporte malheureusement pas encore. Mais par chance il est possible d'étendre les fonctionnalités de Derby avec des fonctions écrites en Java. Ce qui nous donne l'opportunité de traiter l'aspect récursif de nos requêtes dans le monde Java plutôt que dans le monde SQL. C'est ce que nous allons voir maintenant.

Requêtes récursives en Java

Fonctions-tables

Or donc, la solution réside dans le monde Java. Parce que Derby permet de définir nos propres fonctions-tables (table functions – ou tables virtuelles). Késako? Et bien ce sont des fonctions Java dont le résultat est une table. Autrement dit encore, des fonctions dont le résultat peut servir comme une table ordinaire. Et dont le résultat peut donc être exploité par la machinerie SQL dans une requête SELECT. Pour plus de renseignement sur ce sujet, je vous engage à lire l'article Tables virtuelles sous Derby. En deux mots, il s'agit d'écrire une méthode Java qui renvoit une instance de ResultSet, afin que Derby puisse manipuler ces données comme une table.

Recursive ou itérative

En fait, si en SQL nous aurions besoin de requêtes récursives à cause de la nature déclarative de ce langage, comme Java est un langage impératif, il devient possible d'utiliser une itération à la place.

Ainsi, le contenu de notre table virtuelle peut être généré de manière itérative par des requêtes successives à la base. Ainsi, si l'on voulait coder une table virtuelle qui matérialise le sous-arbre qui prend racine à un certain noeud, on pourrait s'y prendre ainsi:

package fr.chicoree.derby;
 
import ...
 
class SubTree extends EnumeratorTableFunction {
    static final String[] columns = { "Children" };
 
    public SubTree(int rootNode) throws SQLException {
        super(columns);
 
        Set<Integer>    subTree        = new HashSet<Integer>();
        Set<Integer>    parentSet    = new HashSet<Integer>();
        subTree.add(rootNode);
        parentSet.add(rootNode);
 
        Connection      conn    = null;
        Statement       stmt    = null;
 
        try {
            conn    = DriverManager.getConnection( "jdbc:default:connection" );
            stmt    = conn.createStatement();
            final String    query   = "SELECT Children.id " +
                                      " FROM Zones AS Children " +
                                      " INNER JOIN Zones AS Parent " +
                                      " ON Parent.id = Children.parent" +
                                      " WHERE Parent.id in (%s)";
 
            int subTreeSize = subTree.size();
            int subTreePrevSize;
            // Construit itérativement la liste des noeuds fils.
            // Arrête quand on ne trouve plus de nouveau fils.
            //
            // Note: cet algorithme peut être utilisé pour parcourir
            //     non seulement des arbres, mais aussi des graphes,
            //     même contenant des cycles.
            do {
                StringBuilder    args = new StringBuilder();
                String            glue    = "";
                for(Integer node : parentSet) {
                    args.append(glue);
                    args.append(node);
                    glue = ",";
                }
 
                ResultSet rs = null;
                try {
                    rs = stmt.executeQuery(String.format(query, args.toString()));
 
                    parentSet    = new HashSet<Integer>();
                    while(rs.next()) {
                        Integer child = rs.getInt(1);
                        subTree.add(child);
                        parentSet.add(child);
                    }
 
                    subTreePrevSize = subTreeSize;
                    subTreeSize = subTree.size();
                }
                finally {
                    rs.close();
                }
            } while(subTreePrevSize < subTreeSize);
        }
        finally {
            if (stmt != null)
                try { stmt.close(); }
                catch(SQLException e) { Logger.getAnonymousLogger().warning("Can't close stmt. " + e.toString()); }
            if (conn != null)
                try { conn.close(); }
                catch(SQLException e) { Logger.getAnonymousLogger().warning("Can't close conn. " + e.toString()); }
        }
        setEnumeration(subTree);
    }
 
    @Override
    public String[] makeRow(Object node) throws SQLException {
        return new String[] { node.toString() };
    }
}
 
public class Functions {    
    public static ResultSet subTree(int rootNode) throws SQLException
                                { return new SubTree(rootNode); } 
}

Cette table virtuelle permet de retrouver toutes les zones incluses directement ou indirectement dans une zone donnée. Mais avant de pouvoir s'en servir dans Derby, il faut l'y déclarer:

CREATE FUNCTION SubTree(rootNode INT) RETURNS TABLE (Zone INT)
    	 LANGUAGE java
         PARAMETER STYLE DERBY_JDBC_RESULT_SET
	 READS SQL DATA
	 EXTERNAL NAME 'fr.chicoree.derby.Functions.subTree'
;

Et voila: pour obtenir la liste des zones contenues dans la zone 1, voici la requête à effectuer:

ij> SELECT * FROM TABLE (SubTree(1) ) AS T;
ZONE   
-----------
1          
2          
3          
4          

4 rows selected

Et pour connaître tous les magasins dans la zone Bretagne, on pourrait écrire:

ij> SELECT M.* FROM Magasins AS M
               INNER JOIN TABLE (SubTree( 2 )) AS T
               ON M.zone = T.zone;
CODE      |ZONE       
----------------------
RENNES1   |3          
RENNES2   |3          
STMALO1   |2          

3 rows selected

Ou encore:

ij> SELECT M.* FROM Magasins AS M
               INNER JOIN TABLE (SubTree( (SELECT ID FROM Zones WHERE designation = 'Bretagne') )) AS T
               ON M.zone = T.zone;
CODE      |ZONE       
----------------------
RENNES1   |3          
RENNES2   |3          
STMALO1   |2          

3 rows selected

Bien sûr, à partir de là, on peut utiliser la même requête pour atteindre les magasins d'autres zones – et quelque soit la profondeur de l'imbrication des zones entre elles:

ij> SELECT M.* FROM Magasins AS M
               INNER JOIN TABLE (SubTree( (SELECT ID FROM Zones WHERE designation = 'France') )) AS T
               ON M.zone = T.zone;
CODE      |ZONE       
----------------------
RENNES1   |3          
RENNES2   |3          
STMALO1   |2          
LILLE1    |4          

4 rows selected

ij> SELECT M.* FROM Magasins AS M
               INNER JOIN TABLE (SubTree( (SELECT ID FROM Zones WHERE designation = 'Rennes') )) AS T
               ON M.zone = T.zone;
CODE      |ZONE       
----------------------
RENNES1   |3          
RENNES2   |3          

2 rows selected

Conclusion

Pour terminer, un petit avertissement: ce n'est pas parce qu'on peut le faire qu'il faut le faire! Ainsi, si nous avons vu qu'il était possible avec Derby d'écrire une fonction table qui permet d'explorer une structure arborescente définie par une liste d'adjascence, ça n'est pas forcément la panacée. En effet, vous comprenez que cela implique l'exécution d'un certain nombre de requête par le SGBD. Même si ces requêtes sont cachées dans le code Java. Au final, cela peut devenir d'autant plus pénalisant, que la profondeur de l'arbre est importante. Par contre, là où les listes d'adjascence sont imbattables, c'est au niveau de l'ajout: Puisqu'une seule requête est nécessaire.

Ainsi, si vous faites plus de recherche que de modifications dans votre table, peut-être que d'autres modélisations seraient plus adaptées. Comme celle en ensembles imbriqués (nested sets). Mais pour cela, je vous renvoie vers les ouvrages de référence.

Références