Exemples de CTE récursives : tâches pratiques

Leçon 6.6 · Temps de lecture : ~9 min · Exercices pratiques ↓

Les CTE récursives ne servent pas qu'aux organigrammes. Dans cette leçon, vous appliquerez WITH RECURSIVE à quatre tâches courantes : générer une suite de dates pour combler les trous d'un rapport quotidien, totaliser les ventes sur tous les niveaux d'un arbre de catégories, éclater une nomenclature en liste complète de pièces et trouver tous les itinéraires entre deux villes dans un réseau routier avec cycles.

Dans la leçon précédente, vous avez vu comment fonctionne une CTE récursive : le membre d'ancrage renvoie les lignes de départ, le membre récursif trouve le niveau suivant, et la récursion s'arrête quand rien de nouveau n'apparaît. Ici, le même modèle devient un outil pour les problèmes du quotidien. Chaque exemple montre une technique réutilisable : une séquence générée, des paires ancêtre–descendant, des quantités multipliées et un chemin avec contrôle des cycles.

Le premier exemple s'exécute sur la base d'exemple Sakila. Les autres créent leurs propres tables : exécutez-les dans le bac à sable sur une base sans données d'exemple. La syntaxe est celle de MySQL 8.0 ; elle fonctionne aussi dans MariaDB 10.2+.

1. Générer une suite de dates pour combler les trous

Un rapport « locations par jour » construit avec GROUP BY n'affiche que les jours qui ont des locations. Les jours sans location disparaissent tout simplement, et un graphique tiré de ces données masque le trou. La solution : générer un calendrier de tous les jours et y joindre les données.

Une CTE récursive génère le calendrier : l'ancrage renvoie le premier jour et chaque itération ajoute un jour jusqu'au dernier :

WITH RECURSIVE calendar AS (
    SELECT DATE('2005-05-28') AS day
    UNION ALL
    SELECT day + INTERVAL 1 DAY
    FROM calendar
    WHERE day < '2005-06-16'
)
SELECT c.day, COUNT(r.rental_id) AS rentals
FROM calendar AS c
LEFT JOIN rental AS r
    ON r.rental_date >= c.day
   AND r.rental_date < c.day + INTERVAL 1 DAY
GROUP BY c.day
ORDER BY c.day;

Résultat : 20 lignes, une par jour du 28 mai au 16 juin 2005. Du 1er au 13 juin, il n'y a aucune location, et ces jours affichent 0 au lieu de disparaître.

Trois détails comptent :

• LEFT JOIN conserve les jours sans location ; COUNT(r.rental_id) ne compte que les vraies locations, donc les jours vides obtiennent 0.
• La jointure utilise un intervalle (>= day et < day + 1 jour) plutôt que DATE(r.rental_date) = c.day, ce qui permet encore d'utiliser un index sur rental_date.
• Le même modèle génère n'importe quelle séquence : nombres, heures, mois. Une suite de plus de 1000 pas nécessite d'augmenter cte_max_recursion_depth.

2. Totaux pour tout un sous-arbre

Dans un arbre de catégories, les ventes sont enregistrées dans des catégories précises, mais un rapport a besoin des totaux de chaque branche : « Computers » doit inclure les portables et les ordinateurs de bureau, et « Electronics » doit tout inclure.

CREATE TABLE product_category (
    category_id INT PRIMARY KEY,
    parent_id INT,
    name VARCHAR(50) NOT NULL
);

INSERT INTO product_category VALUES
    (1, NULL, 'Electronics'),
    (2, 1, 'Computers'),
    (3, 1, 'Phones'),
    (4, 2, 'Laptops'),
    (5, 2, 'Desktops'),
    (6, 3, 'Smartphones');

CREATE TABLE sale (
    sale_id INT PRIMARY KEY,
    category_id INT NOT NULL,
    amount DECIMAL(10, 2) NOT NULL
);

INSERT INTO sale VALUES
    (1, 4, 1200), (2, 4, 800), (3, 5, 700),
    (4, 6, 500), (5, 6, 300), (6, 3, 150);

L'astuce consiste à construire d'abord toutes les paires ancêtre–descendant. L'ancrage associe chaque catégorie à elle-même ; chaque itération ajoute les enfants des descendants déjà trouvés :

WITH RECURSIVE subtree AS (
    SELECT category_id AS ancestor_id, category_id
    FROM product_category

    UNION ALL

    SELECT s.ancestor_id, c.category_id
    FROM subtree AS s
    INNER JOIN product_category AS c ON c.parent_id = s.category_id
)
SELECT a.name, SUM(sl.amount) AS total_sales
FROM subtree AS s
INNER JOIN product_category AS a ON a.category_id = s.ancestor_id
LEFT JOIN sale AS sl ON sl.category_id = s.category_id
GROUP BY a.category_id, a.name
ORDER BY a.category_id;

Résultat : Electronics 3650.00, Computers 2700.00, Phones 950.00, Laptops 2000.00, Desktops 700.00, Smartphones 800.00.

Chaque vente est comptée une fois pour sa propre catégorie et une fois pour chaque ancêtre. « Phones » obtient 950 : 150 vendus directement dans cette catégorie plus 800 de « Smartphones ». L'agrégation se fait dans la requête finale, car MySQL n'autorise ni GROUP BY ni fonctions d'agrégation dans le membre récursif.

3. Éclater une nomenclature

Une nomenclature (BOM, bill of materials) liste ce qui compose un produit. Les composants ont leurs propres composants, et la même pièce peut apparaître dans plusieurs branches. Pour commander les pièces d'un vélo, il faut la quantité totale de chaque pièce :

CREATE TABLE part (
    part_id INT PRIMARY KEY,
    part_name VARCHAR(50) NOT NULL
);

INSERT INTO part VALUES
    (1, 'Bicycle'), (2, 'Frame'), (3, 'Wheel'),
    (4, 'Rim'), (5, 'Spoke'), (6, 'Bolt');

CREATE TABLE bom (
    parent_part_id INT,
    child_part_id INT,
    quantity INT NOT NULL,
    PRIMARY KEY (parent_part_id, child_part_id)
);

INSERT INTO bom VALUES
    (1, 2, 1),   -- un vélo a 1 cadre
    (1, 3, 2),   -- et 2 roues
    (2, 6, 4),   -- un cadre a 4 boulons
    (3, 4, 1),   -- une roue a 1 jante
    (3, 5, 36),  -- 36 rayons
    (3, 6, 2);   -- et 2 boulons

À chaque niveau, la quantité d'un composant est multipliée par la quantité de son parent :

WITH RECURSIVE explosion AS (
    SELECT child_part_id AS part_id, quantity
    FROM bom
    WHERE parent_part_id = 1

    UNION ALL

    SELECT b.child_part_id, e.quantity * b.quantity
    FROM explosion AS e
    INNER JOIN bom AS b ON b.parent_part_id = e.part_id
)
SELECT p.part_name, SUM(e.quantity) AS total_quantity
FROM explosion AS e
INNER JOIN part AS p ON p.part_id = e.part_id
GROUP BY p.part_id, p.part_name
ORDER BY p.part_id;

Résultat : Frame 1, Wheel 2, Rim 2, Spoke 72, Bolt 8.

Rayons : 2 roues × 36 = 72. Les boulons viennent de deux branches : 4 dans le cadre et 2 × 2 = 4 dans les roues, et SUM les additionne pour obtenir 8. Pour n'obtenir que les pièces achetées et non assemblées, gardez les lignes dont la pièce n'a pas de composants : ajoutez WHERE NOT EXISTS (SELECT 1 FROM bom AS c WHERE c.parent_part_id = e.part_id).

4. Itinéraires dans un graphe avec cycles

Un arbre a un seul chemin vers chaque nœud. Un réseau routier est un graphe : les routes vont dans les deux sens et forment des cycles, si bien qu'une récursion naïve tournerait en rond indéfiniment. Cherchons tous les itinéraires de Berlin à Vienne :

CREATE TABLE road (
    from_city VARCHAR(30),
    to_city VARCHAR(30),
    distance_km INT NOT NULL,
    PRIMARY KEY (from_city, to_city)
);

INSERT INTO road VALUES
    ('Berlin', 'Prague', 350),
    ('Berlin', 'Leipzig', 190),
    ('Leipzig', 'Prague', 250),
    ('Prague', 'Vienna', 330),
    ('Leipzig', 'Munich', 430),
    ('Munich', 'Vienna', 400);

Chaque route est stockée une fois, donc une CTE ordinaire edge ajoute d'abord le sens inverse. La CTE récursive trip prolonge chaque itinéraire d'une route, ignore les villes déjà présentes dans l'itinéraire et cesse de prolonger un itinéraire quand il atteint Vienne :

WITH RECURSIVE edge AS (
    SELECT from_city, to_city, distance_km FROM road
    UNION ALL
    SELECT to_city, from_city, distance_km FROM road
),
trip AS (
    SELECT
        to_city AS city,
        CAST(CONCAT(from_city, ',', to_city) AS CHAR(500)) AS route,
        distance_km AS total_km
    FROM edge
    WHERE from_city = 'Berlin'

    UNION ALL

    SELECT e.to_city, CONCAT(t.route, ',', e.to_city), t.total_km + e.distance_km
    FROM trip AS t
    INNER JOIN edge AS e ON e.from_city = t.city
    WHERE FIND_IN_SET(e.to_city, t.route) = 0
      AND t.city <> 'Vienna'
)
SELECT route, total_km
FROM trip
WHERE city = 'Vienna'
ORDER BY total_km;

Résultat : 4 itinéraires ; le plus court est Berlin, Prague, Vienne avec 680 km.

FIND_IN_SET(e.to_city, t.route) = 0 est le contrôle des cycles vu dans la leçon précédente : un itinéraire ne revient jamais dans une ville déjà visitée. Notez que WITH RECURSIVE s'écrit une seule fois, et que les CTE qui suivent peuvent être ordinaires ou récursives.

Cette requête énumère tous les itinéraires possibles, et leur nombre croît très vite avec la taille du réseau. C'est adapté aux petits graphes, mais sur de grands réseaux routiers, les plus courts chemins se calculent avec des algorithmes spécialisés, par exemple dans les bases de données orientées graphe ou l'extension PostgreSQL pgRouting.

Quand une CTE récursive n'est pas le meilleur outil

• Arbres profonds et souvent lus. Si une hiérarchie est lue bien plus souvent qu'elle ne change, stockez une structure supplémentaire : un chemin matérialisé (/1/2/4/) ou une table de fermeture (closure table) contenant toutes les paires ancêtre–descendant, comme la CTE subtree ci-dessus, enregistrée dans une table. Un sous-arbre devient alors un simple JOIN sans récursion.
• Grands graphes. L'énumération des itinéraires est exponentielle ; utilisez des algorithmes de graphes.
• Un petit nombre fixe de niveaux. Pour « employé et son responsable », une seule auto-jointure (leçon 5.7) est plus simple.

Points clés :

• Une CTE récursive génère des séquences : un calendrier de dates joint avec LEFT JOIN comble les trous des rapports.
• Les paires ancêtre–descendant construites par une CTE récursive permettent de totaliser des valeurs sur tout un sous-arbre.
• Dans une nomenclature, les quantités sont multipliées niveau par niveau et additionnées avec GROUP BY dans la requête finale.
• Dans les graphes avec cycles, gardez les nœuds visités dans un chemin et ignorez-les avec FIND_IN_SET().
• L'agrégation se fait dans la requête finale : MySQL ne l'autorise pas dans le membre récursif.
• Pour les grands graphes ou les arbres très souvent lus, envisagez les tables de fermeture ou les algorithmes de graphes.

Questions fréquentes

Comment générer une suite de dates dans MySQL ?

Utilisez une CTE récursive : WITH RECURSIVE calendar AS (SELECT DATE('2024-01-01') AS day UNION ALL SELECT day + INTERVAL 1 DAY FROM calendar WHERE day < '2024-01-31') SELECT day FROM calendar;. PostgreSQL dispose aussi de la fonction intégrée generate_series().

Comment combler les dates manquantes dans un rapport SQL ?

Générez un calendrier de toutes les dates avec une CTE récursive, puis joignez-y les données avec LEFT JOIN et comptez une colonne de la table jointe, comme COUNT(r.rental_id). Les dates sans données obtiennent 0 au lieu de disparaître.

Comment calculer un total pour un nœud et tous ses descendants ?

Construisez les paires ancêtre–descendant avec une CTE récursive : l'ancrage associe chaque nœud à lui-même, et le membre récursif ajoute les enfants de chaque descendant. Joignez ensuite les valeurs aux descendants et regroupez par ancêtre avec GROUP BY.

Comment éviter les cycles lors du parcours d'un graphe avec une CTE récursive ?

Conservez le chemin des nœuds visités dans une colonne texte et ajoutez au membre récursif une condition comme FIND_IN_SET(next_node, path) = 0. PostgreSQL 14+ propose aussi une clause CYCLE qui marque et arrête automatiquement les cycles.