db

Les pages d’un site web sont souvent liées entre elles par un système hiérarchique avec des pages parentes, des pages filles… Cela engendre de fait un arbre de données. Il est intéressant de connaître le chemin d’un des nœuds pour, par exemple, en obtenir le fil d’Ariane. C’est ce que cet article vous propose. Avec PostgreSQL bien sûr.



10 min.

Partager l’article Chemin d’un nœud dans un arbre hiérarchique de données avec PostgreSQL sur les réseaux sociaux

Prérequis

Tout d’abord, les codes sources utilisés ici sont valables à partir de PostgreSQL 10.6.

Nous allons nous appuyer sur une table pages contenant les données de bases pour notre démonstration :

  • l’ID de la page,
  • l’ID de la page parente éventuelle,
  • le titre de la page (dans l’idéal, pour un intitulé dans un fil d’Ariane, il faut parfois une version alternative plus courte que le titre, là, on reste simple),
  • le slug (allez voir mon article à ce sujet : Slugs, comment les générer ?).
CREATE TABLE pages (
  id        SERIAL PRIMARY KEY,
  parent_id INTEGER REFERENCES pages(id),
  title     TEXT  NOT NULL  DEFAULT '',
  slug      TEXT  NOT NULL  DEFAULT '',

  UNIQUE(slug)
);

Notez que nous n’autorisons pas une page à être sa propre parente…

Nous allons prendre en compte le remplissage automatique du champ slug comme vu dans l’article « Slugs, comment les générer ? » en créant un trigger :

CREATE FUNCTION slugify(value TEXT, sep TEXT)
RETURNS TEXT AS $$
BEGIN
    -- Chargement de l'extension
    CREATE EXTENSION IF NOT EXISTS "unaccent";

    RETURN trim(
        both sep from regexp_replace(
            lower(unaccent(value)),
            '[^a-z0-9\\-]+',
            sep,
            'gi'
        )
    );
END;
$$ LANGUAGE plpgsql;


CREATE FUNCTION slugify_title() RETURNS trigger AS $slugify_tag$
BEGIN
    SET CONSTRAINTS ALL DEFERRED;
    NEW.slug := slugify(NEW.title, '-');
    
    RETURN NEW;
END;
$slugify_tag$ LANGUAGE plpgsql;

Associons cette action à notre table :

CREATE TRIGGER slugify_page
    BEFORE INSERT OR UPDATE OF title ON pages
    FOR EACH ROW EXECUTE PROCEDURE slugify_title();

Et ajoutons-y des données :

INSERT INTO pages (title)
VALUES      
  ('Page d’accueil'),
  ('Actualités'),
  ('Nous avons maintenant 200 agences en France !'),
  ('Bilan de l’année 2019'),
  ('Qui sommes-nous ?'),
  ('FAQ'),
  ('Au sujet de notre société'),
  ('Au sujet de nos prestations'),
  ('Qui a créé Machin.com ?'),
  ('Puis-je démonter mon bidule sans faire sauter la garantie ?')
;

Vérifions :

 id | parent_id |                            title                            |                           slug                            
----+-----------+-------------------------------------------------------------+-----------------------------------------------------------
  1 |           | Page d’accueil                                              | page-d-accueil
  2 |           | Actualités                                                  | actualites
  3 |           | Nous avons maintenant 200 agences en France !               | nous-avons-maintenant-200-agences-en-france
  4 |           | Bilan de l’année 2019                                       | bilan-de-l-annee-2019
  5 |           | Qui sommes-nous ?                                           | qui-sommes-nous
  6 |           | FAQ                                                         | faq
  7 |           | Au sujet de notre société                                   | au-sujet-de-notre-societe
  8 |           | Au sujet de nos prestations                                 | au-sujet-de-nos-prestations
  9 |           | Qui a créé Machin.com ?                                     | qui-a-cree-machin-com
 10 |           | Puis-je démonter mon bidule sans faire sauter la garantie ? | puis-je-demonter-mon-bidule-sans-faire-sauter-la-garantie
(10 rows)

Et maintenant, définissons qui sera parent de qui :

UPDATE pages SET parent_id = 1 WHERE id = 2;
UPDATE pages SET parent_id = 1 WHERE id = 5;
UPDATE pages SET parent_id = 1 WHERE id = 6;
UPDATE pages SET parent_id = 2 WHERE id = 3;
UPDATE pages SET parent_id = 2 WHERE id = 4;
UPDATE pages SET parent_id = 6 WHERE id = 7;
UPDATE pages SET parent_id = 6 WHERE id = 8;
UPDATE pages SET parent_id = 7 WHERE id = 9;
UPDATE pages SET parent_id = 8 WHERE id = 10;

Comment obtenir le chemin ?

Avec un CTE pardi ! C’est cool les CTE. Si si. Encore plus quand ils sont récursifs comme celui que nous allons réaliser.

Ce CTE sera composé de deux parties :

  • Une pour récupérer les éléments qui n’ont pas de parents, et donc qui correspondent aux différentes racines. Dans notre exemple, il n’y aura qu’une seule racine. Le niveau de la racine sera notée 0.
  • Via un UNION ALL nous récupérons les éléments ayant un parent, nous incrémentons le niveau dans la hiérarchie et nous accumulons le titre aux autres.
WITH RECURSIVE hier (id, level, title, breadcrumb, slugs) AS (
  -- On commence par les éléments racines, ceux qui n’ont pas de parent.
  SELECT  id, 0, title, ARRAY[title], ARRAY[slug]
  FROM    pages
  WHERE   parent_id IS NULL

  UNION ALL

  -- Maintenant, on s’occupe de ceux qui ont un parent
  SELECT      p.id, h.level + 1, p.title, ARRAY_APPEND(h.breadcrumb, p.title), ARRAY_APPEND(h.slugs, p.slug)
  FROM        pages AS p
  INNER JOIN  hier AS h ON h.id = p.parent_id
)

SELECT  id,
        level,
        ARRAY_TO_STRING(breadcrumb, ' -> ') AS breadcrumb
FROM    hier;

L’exécution du code nous donne ceci en sortie :

 id | level |                                                     breadcrumb                                                      
----+-------+---------------------------------------------------------------------------------------------------------------------
  1 |     0 | Page d’accueil
  2 |     1 | Page d’accueil -> Actualités
  5 |     1 | Page d’accueil -> Qui sommes-nous ?
  6 |     1 | Page d’accueil -> FAQ
  3 |     2 | Page d’accueil -> Actualités -> Nous avons maintenant 200 agences en France !
  4 |     2 | Page d’accueil -> Actualités -> Bilan de l’année 2019
  7 |     2 | Page d’accueil -> FAQ -> Au sujet de notre société
  8 |     2 | Page d’accueil -> FAQ -> Au sujet de nos prestations
  9 |     3 | Page d’accueil -> FAQ -> Au sujet de notre société -> Qui a créé Machin.com ?
 10 |     3 | Page d’accueil -> FAQ -> Au sujet de nos prestations -> Puis-je démonter mon bidule sans faire sauter la garantie ?
(10 rows)

Ça ne semble pas mal non ?

Maintenant incluons-y les slugs et les titres.

WITH RECURSIVE hier (id, level, title, breadcrumb, slugs) AS (
  SELECT  id, 0, title, ARRAY[title], ARRAY[slug]
  FROM    pages
  WHERE   parent_id IS NULL

  UNION ALL

  SELECT      p.id, h.level + 1, p.title, ARRAY_APPEND(h.breadcrumb, p.title), ARRAY_APPEND(h.slugs, p.slug)
  FROM        pages AS p
  INNER JOIN  hier AS h ON h.id = p.parent_id
)

SELECT  id,
        level,
        ARRAY_TO_JSON(ARRAY[breadcrumb, slugs])
FROM    hier;
 id | level | array_to_json
----+-------+-------------------------------------------------------------------
  1 |     0 | [["Page d’accueil"],["page-d-accueil"]]
  2 |     1 | [["Page d’accueil","Actualités"],["page-d-accueil","actualites"]]
  5 |     1 | [["Page d’accueil","Qui sommes-nous ?"],["page-d-accueil","qui-sommes-nous"]]
  6 |     1 | [["Page d’accueil","FAQ"],["page-d-accueil","faq"]]

     etc.

(10 rows)

Ce que j’ai fait ici est une manière de faire, à vous de voir si vous souhaitez grouper les title et les slug différemment… Ici pour chaque sous-tableau de array_to_json nous avons le premier avec la liste dans l’ordre des titres, et le second avec dans le même ordre les slugs. Utile pour créer des liens par exemple.

Maintenant que nous avons une requête qui nous plaît, transposons-la sous la forme d’une vue SQL :

CREATE VIEW v_hier AS
  WITH RECURSIVE hier (id, level, title, breadcrumb, slugs) AS (
    SELECT  id, 0, title, ARRAY[title], ARRAY[slug]
    FROM    pages
    WHERE   parent_id IS NULL

    UNION ALL

    SELECT      p.id, h.level + 1, p.title, ARRAY_APPEND(h.breadcrumb, p.title), ARRAY_APPEND(h.slugs, p.slug)
    FROM        pages AS p
    INNER JOIN  hier AS h ON h.id = p.parent_id
  )

  SELECT  id,
          level,
          ARRAY_TO_JSON(ARRAY[breadcrumb, slugs]) AS full_breadcrumb
  FROM    hier;

Comment éviter une boucle infinie ?

Une page qui apparaît comme parente plus d’une fois dans un même chemin et vous avez alors une boucle infinie.

Aïe.

Il serait bon d’y ajouter une (ou plus…) sécurité non ?

En fait il faut 2 sécurités :

  • une à l’insertion/modification de données, pour éviter ce cas,
  • une à la récupération des données, pour casser une boucle infinie.

Sécuriser l’insertion et la mise à jour

Voyons tout d’abord la possibilité de bloquer une insertion ou une mise à jour avec un id déjà dans le chemin.

Pour l’insertion et la mise à jour, le problème est trivial à régler par l’ajout d’une nouvelle contrainte CHECK sur le champ parent_id pour que celui-ci soit NULL, ou soit avec une valeur différente du champ id de la même entrée.

Donc modifions la table en conséquence :

ALTER TABLE     pages
ADD CONSTRAINT  prevent_loop_hier_check
CHECK           (
                  (parent_id <> id)
                  OR
                  (parent_id IS NULL)
                );

Ainsi, il n’est pas possible de fournir l’ID de l’entrée comme son propre parent_id.

Mais ceci est trop trivial, et ne tient pas compte de tout le chemin.

Pour la mise à jour sûre, il faut connaître les ID déjà présents dans le chemin actuel. En fait, il faut faire la même chose qu’avant avec l’accumulation des champs title et slug, mais ici pour le champ parent_id.

Donc aidons-nous de la requête CTE revue pour notre nouveau besoin :

WITH RECURSIVE id_in_hier (id, level, ids) AS (
  SELECT  id, 0, ARRAY[id]
  FROM    pages
  WHERE   parent_id IS NULL

  UNION ALL

  SELECT      p.id, h.level + 1, ARRAY_APPEND(h.ids, p.id)
  FROM        pages AS p
  INNER JOIN  id_in_hier AS h ON h.id = p.parent_id
)

SELECT  id,
        level,
        ids
FROM    id_in_hier;

Nous avons alors à son exécution :

 id | level |    ids     
----+-------+------------
  1 |     0 | {1}
  2 |     1 | {1,2}
  5 |     1 | {1,5}
  6 |     1 | {1,6}
  3 |     2 | {1,2,3}
  4 |     2 | {1,2,4}
  7 |     2 | {1,6,7}
  8 |     2 | {1,6,8}
  9 |     3 | {1,6,7,9}
 10 |     3 | {1,6,8,10}
(10 rows)

Transformons notre requête en vue pour la réutiliser facilement :

CREATE VIEW v_id_in_hier AS
  WITH RECURSIVE id_in_hier (id, level, ids) AS (
    SELECT  id, 0, ARRAY[id]
    FROM    pages
    WHERE   parent_id IS NULL

    UNION ALL

    SELECT      p.id, h.level + 1, ARRAY_APPEND(h.ids, p.id)
    FROM        pages AS p
    INNER JOIN  id_in_hier AS h ON h.id = p.parent_id
  )

  SELECT  id,
          level,
          ids
  FROM    id_in_hier;

Envisageons une première version de notre trigger en utilisant notre nouvelle vue v_id_in_hier se déclenchant dans le cas d’une mise à jour avec une valeur du champ parent_id non NULL.

Pour l’entrée mise à jour, nous regardons, via un SELECT dans v_id_in_hier, les IDs définis dans le chemin.

Voici ce SELECT seul, avec des valeurs en exemple, hors du trigger pour mieux comprendre :

-- Exemple de la requête jouée : pour l’entrée 10, on souhaite changer la page
-- parente par celle ayant l’ID 2. Ici, cela retournera 0, ce qui est bon.
-- Par contre, si à la place de 2 on avait mis 8, là le résultat aurait été 1,
-- ce qui signifie uententative d’insertion de doublon et donc création d’une
-- boucle.
WITH q AS (
  SELECT  unnest(ids) AS path_id
  FROM    v_id_in_hier
  WHERE   id = 10
)
SELECT COUNT(*) FROM q WHERE q.path_id = 2;

Nous comptons le nombre d’IDs égaux à la valeur fournie pour NEW.parent_id. Si ce nombre est différent de zéro… C’est que nous étions en train de créer une boucle. Et pour stopper net ceci rien de mieux que de lever une exception.

Voici donc notre trigger au complet :

CREATE FUNCTION avoid_duplicate_in_hier() RETURNS trigger AS $$
DECLARE
    query TEXT;
    found INTEGER DEFAULT 0;
BEGIN
    IF TG_OP = 'UPDATE' AND NEW.parent_id IS NOT NULL THEN
        query := '
          WITH q AS (
            SELECT  unnest(ids) AS path_id
            FROM    v_id_in_hier
            WHERE   id = $1.id
          )
          SELECT COUNT(*) FROM q WHERE q.path_id = $1.parent_id;
        ';
        EXECUTE query USING NEW INTO found;
    END IF;

    IF found = 1 THEN
      RAISE EXCEPTION 'You cannot use more than once a parent in the same path.';
    END IF;

    RETURN NEW;
END;
$$ LANGUAGE plpgsql;

Sur le papier, ça semble correct. Voyons en pratique :

CREATE TRIGGER avoid_loop_hier_for_page
    BEFORE UPDATE ON pages
    FOR EACH ROW EXECUTE PROCEDURE avoid_duplicate_in_hier();

Testons avec un ID déjà employé :

UPDATE  pages
SET     parent_id = 6
WHERE   id = 10;

Cette tentative de modification échoue comme nous le voulions :

ERROR:  You cannot use more than once a parent in the same path.
CONTEXT:  PL/pgSQL function avoid_duplicate_in_hier() line 19 at RAISE

Testons en utilisant son propre ID comme valeur pour le champ parent_id : même erreur levée. Parfait.

Testons maintenant avec un ID autorisé, disons, le 7 :

UPDATE pages SET parent_id = 7 WHERE id = 10;

Aucune erreur n’est levée. Voyons le résultat :

SELECT * FROM v_id_in_hier WHERE id = 10;

Nous donne bien :

 id | level |    ids     
----+-------+------------
 10 |     3 | {1,6,7,10}
(1 row)

Bien ! La mise à jour est donc elle aussi sécurisée pleinement!

Éviter la boucle lors de la récupération des données

Nous allons adapter la vue v_id_in_hier afin d’utiliser le mot clé ANY pour éviter une boucle si les données de la table ne sont pas fiables pour une raison ou une autre.

CREATE VIEW v_id_in_hier AS
  WITH RECURSIVE id_in_hier (id, level, ids) AS (
    SELECT  id, 0, ARRAY[id]
    FROM    pages
    WHERE   parent_id IS NULL

    UNION ALL

    SELECT      p.id, h.level + 1, ARRAY_APPEND(h.ids, p.id)
    FROM        pages AS p
    INNER JOIN  id_in_hier AS h
    ON          h.id = p.parent_id
    -- Hop ! le changement est juste ici !
    AND         p.id <> ALL (h.ids)
  )

  SELECT  id,
          level,
          ids
  FROM    id_in_hier;

Le fait d’ajouter ce AND … <> ALL dans le JOIN pousse à exclure les ID qui seraient déjà présents dans la liste de IDs du chemin.

Et n’oublions pas notre vue du départ, v_hier, qu’il faut modifier comme suit :

CREATE OR REPLACE VIEW v_hier AS
  WITH RECURSIVE hier (id, level, ids, title, breadcrumb, slugs) AS (
    SELECT  id, 0, ARRAY[id], title, ARRAY[title], ARRAY[slug]
    FROM    pages
    WHERE   parent_id IS NULL

    UNION ALL

    SELECT      p.id,
                h.level + 1,
                ARRAY_APPEND(h.ids, p.id),
                p.title,
                ARRAY_APPEND(h.breadcrumb, p.title),
                ARRAY_APPEND(h.slugs, p.slug)
    FROM        pages AS p
    INNER JOIN  hier AS h ON h.id = p.parent_id
    AND         p.id <> ALL (h.ids)
  )

  SELECT  id,
          level,
          ARRAY_TO_JSON(ARRAY[breadcrumb, slugs]) AS full_breadcrumb
  FROM    hier;

En principe, via cette méthode, vous n’aurez pas de boucle infinie.

Fonction générique bonus

Pour vous récompenser de votre patience, je vous propose une petite fonction PL/pgSQL qui vous permettra de connaître les IDs d’un chemin pour chaque élément, quelque soit la table, pourvu que les champs soient id et parent_id.

Le but de cette fonction est de reproduire la sortie de la vue v_id_in_hier. La valeur de retour sera donc un contenu TABLE. En paramètre, un seul argument, qui prendra le nom de la table. Il suffit de faire en sort que la requète construite prenne le nom de la table en considération et le tour est joué.

Voici cette fonction bonus :

CREATE OR REPLACE FUNCTION get_ids_in_hier_helper (
    IN arg_table_name TEXT
)
RETURNS TABLE (
    id    INTEGER,
    level INTEGER,
    ids   INTEGER[]
)
AS $$
DECLARE
    query TEXT;
BEGIN
    query := '
      WITH RECURSIVE id_in_hier (id, level, ids) AS (
        SELECT  id, 0, ARRAY[id]
        FROM    ' || quote_ident(arg_table_name) || '
        WHERE   parent_id IS NULL

        UNION ALL

        SELECT      p.id, h.level + 1, ARRAY_APPEND(h.ids, p.id)
        FROM        ' || quote_ident(arg_table_name) || ' AS p
        INNER JOIN  id_in_hier AS h
        ON          h.id = p.parent_id
        AND         p.id <> ALL (h.ids)
      )

      SELECT  id,
              level,
              ids
      FROM    id_in_hier;
    ';

	RETURN QUERY EXECUTE query;
END; $$ 

LANGUAGE 'plpgsql';

Et testons-la avec notre table d’exemple pages :

SELECT * FROM get_ids_in_hier_helper('pages');

Ce qui nous donne :

 id | level |    ids     
----+-------+------------
  1 |     0 | {1}
  2 |     1 | {1,2}
  5 |     1 | {1,5}
  6 |     1 | {1,6}
  3 |     2 | {1,2,3}
  4 |     2 | {1,2,4}
  7 |     2 | {1,6,7}
  8 |     2 | {1,6,8}
  9 |     3 | {1,6,7,9}
 10 |     3 | {1,6,8,10}
(10 rows)

Conclusion

Nous avons vu dans cet article comment insérer, mettre à jour et récupérer des données arborescentes d’un point de vu pratique par rapport à un nœud donné.

Il faut donc s’assurer d’insérer des entrées qui ne comportent pas n’importe quelle valeur pour le champ parent_id pour éviter des boucles infinies.

De la même façon, la reconstitution du chemin, qui se fait via une méthode récursive, impose un certain garde-fou en construisant la requête intelligemment.

Dans la même veine « navigation web », en suivant la même logique, vous pouvez également gérer les menus du site de manière très similaire.

Photo de Benjamin Balázs sur Unsplash