sql:requete-recursive

Requête récursive : un exemple de graphe PERT (gestion de projet) extrait en une seule requête

Nb : système visé → MariaDB

Publication originale : blog sur Développez.com

Mon avis a été récemment demandé sur les bases de données et la gestion des stocks via des outils de graphes. Par défaut, les outils classiques du monde SQL (donc relationnel), avaient été exclus dans la demande qui m'avait été formulée. Si effectivement la qualité première des outils de gestion de graphes reste la récursivité, le SQL n’est plus totalement en reste.

Et ce depuis un certain temps, comme nous l’explique la documentation de MariaDB (à partir de 10.2), que je cite : « Common Table Expressions (CTEs) are a standard SQL feature, and are essentially temporary named result sets. CTEs first appeared in the SQL standard in 1999, and the first implementations began appearing in 2007. »

Plutôt que de reprendre strictement la demande, j’essaie ici de présenter un cas typique guère plus complexe mais oh combien utile, qui rapproche le monde relationnel du monde du graphe (bien que les deux aient bien plus de similitudes qu’on le présente souvent).

Mon exemple s’appuie sur l’extraction d’une base relationnelle d’objets quelconque, les données propres à un projet, par exemple si l’on voulait définir un PERT. Notez que j'aurais pu utiliser aussi un exemple routier, de relation de personnes… peu importe.

Voici mon jeu de données au départ :

-- phpMyAdmin SQL Dump
-- version 5.0.2
-- https://www.phpmyadmin.net/
--
-- Hôte : localhost
-- Généré le : ven. 03 avr. 2020 à 15:48
-- Version du serveur :  10.3.22-MariaDB-0ubuntu0.19.10.1
-- Version de PHP : 7.3.11-0ubuntu0.19.10.3
 
SET SQL_MODE = "NO_AUTO_VALUE_ON_ZERO";
START TRANSACTION;
SET time_zone = "+00:00";
 
--
-- Base de données : `pert`
--
 
-- --------------------------------------------------------
 
--
-- Structure de la table `objets`
--
 
CREATE TABLE `objets` (
  `idnoeuds` INT(11) NOT NULL,
  `nom` VARCHAR(125) COLLATE utf8_bin NOT NULL,
  `relation_debut` INT(11) DEFAULT NULL,
  `relation_fin` INT(11) DEFAULT NULL,
  `duree` INT(11) DEFAULT NULL,
  `type` enum('relation','noeud','tâche','étape') COLLATE utf8_bin DEFAULT 'noeud'
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_bin;
 
--
-- Déchargement des données de la table `objets`
--
 
INSERT INTO `objets` (`idnoeuds`, `nom`, `relation_debut`, `relation_fin`, `duree`, `type`) VALUES
(1, 'début', NULL, NULL, NULL, 'étape'),
(2, 'fondation', NULL, NULL, 5, 'étape'),
(3, 'murs', NULL, NULL, 3, 'étape'),
(4, 'cloisons', NULL, NULL, 2, 'étape'),
(5, 'toit', NULL, NULL, 3, 'étape'),
(6, 'finalisation', NULL, NULL, 4, 'étape'),
(7, 'recevoir les produits', 1, 2, 2, 'tâche'),
(8, 'préparer les parpaings', 2, 3, 1, 'tâche'),
(9, 'préparer les placos', 3, 4, 1, 'tâche'),
(10, 'préparer les tuiles', 3, 5, 1, 'tâche'),
(11, 'vérifier le toit', 5, 6, 1, 'tâche'),
(12, 'vérifier les cloisons', 4, 6, 1, 'tâche');
 
--
-- Index pour les tables déchargées
--
 
--
-- Index pour la table `objets`
--
ALTER TABLE `objets`
  ADD PRIMARY KEY (`idnoeuds`),
  ADD KEY `debut` (`relation_debut`),
  ADD KEY `fin` (`relation_fin`);
 
--
-- AUTO_INCREMENT pour les tables déchargées
--
 
--
-- AUTO_INCREMENT pour la table `objets`
--
ALTER TABLE `objets`
  MODIFY `idnoeuds` INT(11) NOT NULL AUTO_INCREMENT, AUTO_INCREMENT=13;
 
--
-- Contraintes pour les tables déchargées
--
 
--
-- Contraintes pour la table `objets`
--
ALTER TABLE `objets`
  ADD CONSTRAINT `debut` FOREIGN KEY (`relation_debut`) REFERENCES `objets` (`idnoeuds`) ON DELETE SET NULL ON UPDATE CASCADE,
  ADD CONSTRAINT `fin` FOREIGN KEY (`relation_fin`) REFERENCES `objets` (`idnoeuds`) ON DELETE SET NULL ON UPDATE CASCADE;
COMMIT;

Vous devriez avoir quelque chose de ressemblant à ceci :

Ne vous préoccupez pas des identifiants qui sont utilisés (leur numéro), seulement de l’esprit de la base : elle met en relation des étapes avec tâches, au sein d'une même table (cependant on aurait pu en utiliser deux, trois, dix - peu importe). SI normalement une étape n’a pas de durée dans un PERT, il est courant d’en rajouter lorsque l'étape s'apparente en réalité à une tâche de contrôle, donc elle-même avec une question de délais (et de coûts). Bref : les puristes me pardonneront.

Imaginez qu’il y ait des milliers d’objets dans cette base, sur des projets divers, et que vous ne pouvez pas savoir (deviner) qui va avec qui et, mieux, vous souhaitez « trier » les résultats en fonction d’un sens (début vers la fin ou l’inverse). L’extraction d’un modèle propre aux graphes exploitables rend cette opération facile. Une extraction avec une requête SQL et des jointures ou des unions, risquent de vous faire passer un sale après-midi (en période de confinement, personne n’a besoin de ça…).

Alors comment fonctionnent les requêtes récursives ? Comme des tables temporaires qui seraient alimentées progressivement, tant que la requête associée est capable de trouver des résultats. Mieux, cette alimentation permet en parallèle de comparer la table ainsi construite à d’autres, en s'appuyant sur les résultats déjà obtenus (c'est ceci le sens de “récursivité”).

Dans la documentation de MariaDB, vous trouverez le détail du fonctionnement, pas-à-pas. Je le passe ici. Dans notre cas, nous devons déterminer un point d’entrée de votre requête récursive. Le plus logique est soit de commencer par la fin (idnoeuds=6) soit par le début (idnoeuds=1).

La présentation se fera donc soit du début vers la fin, si l’on commence par le début ; soit l’inverse.

Ma requête (trois SELECT et deux UNION en réalité) va devoir gérer ici deux cas :

  1. soit l’objet est une tâche (une relation),
  2. soit c’est une étape (un nœud).

Une étape peut avoir plusieurs tâches de départ et/ou d’arrivée, ce qui est le cas dans mon exemple (cloison + toit en parallèle).

WITH RECURSIVE processus AS ( 
	SELECT 
		idnoeuds, 
		nom, 
		relation_debut, 
		relation_fin, 
		duree, 
		TYPE 
	FROM 
		objets
	WHERE 
		`idnoeuds` = 1 
	UNION 
		SELECT 
			o.idnoeuds, 
			o.nom, 
			o.relation_debut, 
			o.relation_fin, 
			o.duree, 
			o.type 
		FROM 
			objets AS o, 
			processus AS p 
		WHERE 
			o.relation_debut = p.idnoeuds 
		AND 
			o.type = "tâche" 
	UNION 
		SELECT 
			o.idnoeuds, 
			o.nom, 
			o.relation_debut, 
			o.relation_fin, 
			o.duree, 
			o.type 
		FROM 
			objets AS o, 
			processus AS p 
		WHERE 
			o.idnoeuds = p.relation_fin 
		AND 
			o.type = "étape" 
) SELECT * FROM processus;

Ma table « processus [de maison] » est créée ici de manière temporaire, elle n’est pas gardée. Nous verrons après ce que nous pouvons en faire. Décortiquons en attendant : vous noterez tout d’abord l’absence de point-virgule entre le SELECT final et mon « bloc » WITH RECURSIVE … AS. C’est bien en un item de requête non-scindable (voir la documentation). Pour ceux qui connaisse Python, pensez à l’équivalent du mot-clé « with », qui permet d’automatiser certaines tâches et de limiter la portée des fonctions au bloc qui suit. C’est ici la même chose.

Au sein de ce bloc, mon premier SELECT définit mon point de départ de parcours (ici le début*: idnoeuds=1). La première UNION gère les tâches et la seconde les étapes ; chacune permettant d’alimenter la table « processus » qui est alors à nouveau consulté pour tenter de trouver de nouvelles entrées.

Ma requête s’arrête lorsque j’atteins un point où il n’y a plus rien à parcourir, sachant que les chemins parallèles ont tous été traversés. Le résultat est conforme aux attentes : la table est correctement remplie, il n’y a pas de manque et cerise sur le gâteau, il n’y a pas besoin de la « trier »…

Si je souhaite disposer d’une extraction vers une table temporaire (ou pas) classique, et éventuellement rajouter un identifiant unique propre à ce processus, rien de bien compliqué :

CREATE TEMPORARY TABLE `processus_extrait` ( 
	idnoeuds INT(11) NOT NULL, 
	nom VARCHAR(125) NOT NULL, 
	relation_debut INT(11) NULL, 
	relation_fin INT(11) NULL, 
	duree INT(11) NULL, 
	TYPE VARCHAR(125) NOT NULL 
); 
 
INSERT INTO `processus_extrait` 
	( 
		idnoeuds, 
		nom, 
		relation_debut, 
		relation_fin, 
		duree, 
		TYPE 
	) 
WITH RECURSIVE processus AS ( 
	SELECT 
		idnoeuds, 
		nom, 
		relation_debut, 
		relation_fin, 
		duree, 
		TYPE 
	FROM 
		objets
	WHERE 
		`idnoeuds` = 1 
	UNION 
		SELECT 
			o.idnoeuds, 
			o.nom, 
			o.relation_debut, 
			o.relation_fin, 
			o.duree, 
			o.type 
		FROM 
			objets AS o, 
			processus AS p 
		WHERE 
			o.relation_debut = p.idnoeuds 
		AND 
			o.type = "tâche" 
	UNION 
		SELECT 
			o.idnoeuds, 
			o.nom, 
			o.relation_debut, 
			o.relation_fin, 
			o.duree, 
			o.type 
		FROM 
			objets AS o, 
			processus AS p 
		WHERE 
			o.idnoeuds = p.relation_fin 
		AND 
			o.type = "étape" 
) SELECT * FROM processus; 
 
ALTER TABLE 
	`processus_extrait` 
ADD 
	`idposition` INT NOT NULL AUTO_INCREMENT FIRST, ADD PRIMARY KEY (`idposition`) 
; 
 
SELECT 
	* 
FROM 
	`processus_extrait` 
;

Ce qui nous donnera les éléments suivants :

En conclusion, dans certains cas, les requêtes récursives permettent d’aller plus loin en restant plus efficace que certaines jointures ou unions traditionnelles, en « automatisant » la création de nouveaux jeux de données – avec cette restriction que la table « temporaire » qui récupère les résultats, ne peut mélanger tous les types de résultats. De plus le monde relationnel a sa vision de la donnée, de son organisation, qui ne correspond pas toujours à son souhait. La possibilité de faire des requêtes récursives n'autorise pas, à mon sens, le parallèle absolu et permanent avec les autres outils de graphe, mais davantage comme une fonctionnalité supplémentaire pour des cas précis et limités.

Une fonction bien utile cependant, qui mérite donc d’être utilisée.

  • sql/requete-recursive.txt
  • Dernière modification: 2020/12/13 17:45
  • (modification externe)