Avancé · 25 min

CTE récursives et hiérarchies : parcourir un arbre

WITH RECURSIVE pour parcourir une structure hiérarchique (catégories imbriquées, organigramme) sans connaître sa profondeur à l'avance.

Contexte

Une catégorie de boutique peut avoir des sous-catégories, un employé un manager qui a lui-même un manager : ce sont des hiérarchies de profondeur variable, qu'aucun nombre fixe de JOIN ne peut parcourir en toute généralité. C'est exactement le problème que résout une CTE récursive.

Explication

Une CTE récursive a toujours deux parties reliées par UNION ALL :

le cas de base : le ou les points de départ (les racines, sans parent) ;
le cas récursif : comment passer d'une ligne déjà trouvée à ses enfants, en rejoignant la CTE sur elle-même — SQLite (et la norme SQL) répète ce cas jusqu'à ce qu'il ne trouve plus rien de nouveau.

WITH RECURSIVE arbre AS (
  SELECT id, parent_id, 0 AS profondeur FROM une_table WHERE parent_id IS NULL
  UNION ALL
  SELECT c.id, c.parent_id, a.profondeur + 1
  FROM une_table c INNER JOIN arbre a ON c.parent_id = a.id
)
SELECT * FROM arbre;

On peut accumuler autre chose que la profondeur au passage — un chemin texte (a.chemin || ' > ' || c.nom), une racine d'origine pour ensuite grouper par elle, etc. Sans le mot-clé RECURSIVE, la table arbre ne pourrait pas se référencer elle-même dans sa propre définition.

Exemple guidé

La base boutique a des catégories avec sous-catégories (parent_id) : Boissons se scinde en Sodas et Jus & sirops. Afficher l'arbre avec profondeur :

WITH RECURSIVE arbre AS (
  SELECT id, nom, parent_id, 0 AS profondeur FROM categories WHERE parent_id IS NULL
  UNION ALL
  SELECT c.id, c.nom, c.parent_id, a.profondeur + 1
  FROM categories c INNER JOIN arbre a ON c.parent_id = a.id
)
SELECT id, nom, profondeur FROM arbre ORDER BY profondeur, nom;

Pour compter les produits d'une catégorie EN INCLUANT ses sous-catégories, il faut d'abord calculer, avec la même technique, la liste de tous les descendants d'une catégorie avant de filtrer produits dessus — un simple categorie_id = 1 ignorerait tout ce qui est rangé dans les sous-catégories.

À retenir

WITH RECURSIVE = cas de base (UNION ALL) cas récursif qui se rejoint lui-même sur parent_id = id. On peut accumuler une profondeur, un chemin, ou une racine d'origine au passage. Indispensable dès qu'une hiérarchie n'a pas une profondeur fixe connue à l'avance.

Exercices de cette leçon

Faire les exercices →