Requêtes récursives (WITH RECURSIVE) : hiérarchies et graphes

Parcourez arbres et graphes avec WITH RECURSIVE, en maîtrisant la profondeur et la détection de cycles.

11 min · 3 questions

Une CTE récursive se compose de deux parties reliées par UNION ALL : un terme d'ancrage qui fournit les lignes de départ, et un terme récursif qui référence la CTE elle-même. SQLite exécute l'ancrage une fois, puis applique le terme récursif en boucle sur les nouvelles lignes, jusqu'à ce qu'il n'en produise plus aucune. Créons une hiérarchie de managers pour l'illustrer.

SQL

CREATE TABLE employees (
  id INTEGER PRIMARY KEY,
  name TEXT NOT NULL,
  manager_id INTEGER
);

INSERT INTO employees (id, name, manager_id)
VALUES
  (1, 'Ada',    NULL),
  (2, 'Grace',  1),
  (3, 'Alan',   2),
  (4, 'Edsger', 2);

Ada dirige Grace, qui dirige Alan et Edsger.

Pour dérouler l'organigramme sous Ada, l'ancrage sélectionne la racine avec une profondeur 0, et le terme récursif joint chaque employé à son manager déjà présent dans la CTE, en incrémentant la profondeur. La colonne depth que vous calculez vous-même est le moyen le plus simple de mesurer les niveaux d'une hiérarchie.

SQL

WITH RECURSIVE chain(id, name, depth) AS (
  SELECT id, name, 0
  FROM employees
  WHERE id = 1
  UNION ALL
  SELECT e.id, e.name, c.depth + 1
  FROM employees e
  JOIN chain c ON e.manager_id = c.id
)
SELECT id, name, depth FROM chain;

Ada 0, Grace 1, Alan 2, Edsger 2.

Un graphe se modélise par une table d'arêtes (src, dst). Le parcours suit la même mécanique, mais un graphe peut contenir des cycles : suivre 1 -> 2 -> 3 -> 1 boucle à l'infini. La parade consiste à mémoriser le chemin parcouru dans une colonne texte et à refuser tout nœud déjà visité. La fonction instr cherche un nœud entre deux points dans ce chemin.

SQL

CREATE TABLE edges (
  src INTEGER NOT NULL,
  dst INTEGER NOT NULL
);

INSERT INTO edges (src, dst) VALUES
  (1, 2), (2, 3), (3, 1), (2, 4);

WITH RECURSIVE walk(node, path) AS (
  SELECT 1, '.1.'
  UNION ALL
  SELECT e.dst,
         w.path || e.dst || '.'
  FROM edges e
  JOIN walk w ON e.src = w.node
  WHERE instr(w.path, '.' || e.dst || '.') = 0
)
SELECT node, path FROM walk;

Le chemin '.1.2.3.' bloque le retour vers 1.

Avec UNION ALL, un cycle non gardé produit une récursion infinie : chaque nœud revisité est réinjecté sans dédoublonnage. Remplacer par UNION élimine les lignes *entières* identiques, ce qui aide parfois, mais ne suffit pas dès qu'une colonne comme path diffère à chaque tour. SQLite ne connaît pas la clause standard CYCLE (présente dans PostgreSQL 14+) : la détection de cycle est donc à votre charge.

Une CTE récursive génère aussi des séries de nombres : WITH RECURSIVE seq(n) AS (SELECT 1 UNION ALL SELECT n + 1 FROM seq LIMIT 10) produit 1 à 10, un LIMIT externe suffisant à borner la boucle. Contrainte SQLite : le terme récursif ne peut référencer la CTE qu'une seule fois et n'admet ni agrégat ni ORDER BY interne.

Quiz de validation

Vérifiez que vous avez bien retenu les points clés de cette leçon.

Dans une CTE récursive, quel opérateur relie le terme d'ancrage au terme récursif ?
- UNION ALL (ou UNION)
- JOIN
- INTERSECT
- CROSS APPLY
Pourquoi un graphe cyclique risque-t-il une récursion infinie avec UNION ALL ?
- Parce que UNION ALL trie systématiquement les résultats
- Parce que les mêmes nœuds sont revisités sans dédoublonnage
- Parce que SQLite désactive l'index pendant la récursion
- Parce que l'ancrage est réévalué à chaque tour
Comment éviter une boucle infinie lors du parcours d'un graphe cyclique en SQLite ?
- Ajouter un ORDER BY dans le terme récursif
- Mémoriser le chemin parcouru et exclure les nœuds déjà visités
- Utiliser la clause standard CYCLE
- Augmenter la taille du cache mémoire