Retour à la liste des articles Articles
5 minutes de lecture

Requête SQL longue vs Requête SQL récursive

Table des matières

La récursion est l'une des idées centrales de l'informatique. Nous pouvons la définir comme une méthode de résolution de problèmes dont la solution dépend de la résolution d'une instance plus petite du problème. Si cela vous semble compliqué, ne vous inquiétez pas, dans cet article nous allons apprendre la récursion en SQL que vous pourrez pratiquer et approfondir à la Vertabelo Academy.

La récursion est un moyen de résoudre les problèmes hiérarchiques que nous trouvons dans les données avec le SQL courant. Ces types de requêtes sont également appelés requêtes hiérarchiques. Nous pouvons trouver des capacités de récursion dans le SQL standard depuis SQL:1999 par le biais de CTE récursifs ou expressions de table communes.

Certains systèmes RDMBS ont leur propre façon d'implémenter la récursion, notamment les bases de données d'Oracle avec l'instruction CONNECT BY. Puisque les expressions récursives de table font partie de la norme SQL et qu'elles sont partagées par tous les principaux fournisseurs de SGBDR, nous allons explorer ce type de récursion.

RÉCURSION AVEC CTE

La récursion est mieux maîtrisée en visualisant une structure hiérarchique. Il n'y a pas de meilleur exemple de données hiérarchiques que la structure organisationnelle d'une grande entreprise. Nous allons donc explorer une table typique employees qui contient des données sur les employés et leurs supérieurs directs.

La table a l'identifiant de l'employé actuel et de son supérieur direct comme référence à la même table. En plus des identifiants, nous avons également dans la table le nom et le prénom de l'employé.

Nous allons construire une requête qui recherche dans toutes les lignes de la table, en commençant par la première ligne, généralement appelée ligne d'ancrage. Dans notre table, la ligne d'ancrage est le top manager, il n'y a pas de responsable hiérarchique au-dessus de lui, donc son attribut manager_id est nul.

  SELECT id,
         manager_id,
         first_name,
         last_name,
         0 depth_level
  FROM   employees
  WHERE  manager_id IS NULL
ID MANAGER_ID FIRST_NAME LAST_NAME
1 John McGee

Imaginons que nous voulions savoir qui John gère, à quoi ressemblerait la requête ? Quelque chose comme ceci :

SELECT id,
         manager_id,
         first_name,
         last_name
  FROM   employees cur
  WHERE  manager_id in (
    SELECT id
    FROM   employees
    WHERE  manager_id IS NULL
  )

Et pour les managers de ces managers :

SELECT id,
  manager_id,
  first_name,
  last_name
FROM employees
WHERE manager_id IN
  (SELECT id
  FROM employees
  WHERE manager_id IN
    ( SELECT id FROM employees WHERE manager_id IS NULL
    )
  ) 

Comme vous le voyez, un schéma se dessine : pour chaque nouveau niveau de gestion, nous construisons une nouvelle sous-requête. Cette approche est mauvaise car elle prend en compte un nombre fixe de niveaux.

La récursion est un moyen par lequel nous prenons ces sous-requêtes et les transformons pour qu'elles soient générales de manière à représenter le résultat précédent de la requête.

Dans notre exemple de gestion, la partie générale est construite de telle sorte que nous JOINONS l'ensemble de résultats précédents à l'ensemble actuel sur la base de l'identifiant de gestion.

  SELECT cur.id,
         cur.manager_id,
         cur.first_name,
         cur.last_name
  FROM   employees cur, previous
  WHERE  cur.manager_id = previous.id

Ce jeu de données précédent est défini comme un CTE.

La fonction récursive complète ressemble donc à ceci :

WITH previous(id, manager_id,first_name,last_name) AS (
  SELECT id,
         manager_id,
         first_name,
         last_name
  FROM   employees
  WHERE  manager_id IS NULL
  UNION ALL
  SELECT cur.id,
         cur.manager_id,
         cur.first_name,
         cur.last_name
  FROM   employees cur, previous
  WHERE  cur.manager_id = previous.id
)
SELECT *
FROM   previous;

La récursion commence par le gestionnaire supérieur et est rejointe par chaque nouveau niveau de la hiérarchie de gestion. Le SELECT final renvoie le jeu de données complet.

ID MANAGER_ID FIRST_NAME LAST_NAME
1 John McGee
2 1 Kate Doe
7 1 Ethan Lee
9 1 Emily McPers
3 2 Ethan Smith
4 2 Alexander Lam
8 7 Sophia Wilson
10 9 Jacob Gagnon
12 9 Madison Morin
5 4 Ava Marin
6 4 Olivia Roy
11 10 Logan Tremblay

Nous pouvons étendre cette requête pour la rendre plus utile, disons que nous voulons voir les niveaux de la hiérarchie. Pour ce faire, nous construisons un nouveau paramètre que nous incrémentons, appelons-le depth_level. Pour chaque niveau de la hiérarchie, le nombre est augmenté de 1.

WITH previous(id, manager_id,first_name,last_name,depth_level) AS (
  SELECT id,
         manager_id,
         first_name,
         last_name,
         0 depth_level
  FROM   employees
  WHERE  manager_id IS NULL
  UNION ALL
  SELECT cur.id,
         cur.manager_id,
         cur.first_name,
         cur.last_name,
         previous.depth_level+1 depth_level
  FROM   employees cur, previous
  WHERE  cur.manager_id = previous.id
)
SELECT previous.*
FROM   previous;

Nous obtenons donc les niveaux de la hiérarchie.

ID MANAGER_ID FIRST_NAME LAST_NAME DEPTH_LEVEL
1 John McGee 0
2 1 Kate Doe 1
7 1 Ethan Lee 1
9 1 Emily McPers 1
3 2 Ethan Smith 2
4 2 Alexander Lam 2
8 7 Sophia Wilson 2
10 9 Jacob Gagnon 2
12 9 Madison Morin 2
5 4 Ava Marin 3
6 4 Olivia Roy 3
11 10 Logan Tremblay 3

Nous pouvons utiliser ce niveau de profondeur pour représenter les données d'une manière plus graphique avec la requête

WITH previous(id, manager_id,first_name,last_name,depth_level) AS (
  SELECT id,
         manager_id,
         first_name,
         last_name,
         0 depth_level
  FROM   employees
  WHERE  manager_id IS NULL
  UNION ALL
  SELECT cur.id,
         cur.manager_id,
         cur.first_name,
         cur.last_name,
         previous.depth_level+1 depth_level
  FROM   employees cur, previous
  WHERE  cur.manager_id = previous.id
)
SELECT previous.*,
RPAD('.', (depth_level)*2, '.') || id AS tree
FROM   previous;

et l'ensemble des résultats :

ID MANAGER_ID FIRST_NAME LAST_NAME DEPTH_LEVEL TREE
1 John McGee 0 1
2 1 Kate Doe 1 ..2
7 1 Ethan Lee 1 ..7
9 1 Emily McPers 1 ..9
3 2 Ethan Smith 2 ....3
4 2 Alexander Lam 2 ....4
8 7 Sophia Wilson 2 ....8
10 9 Jacob Gagnon 2 ....10
12 9 Madison Morin 2 ....12
5 4 Ava Marin 3 ......5
6 4 Olivia Roy 3 ......6
11 10 Logan Tremblay 3 ......11

La récursion n'est pas la partie la plus intuitive de l'informatique mais elle en fait partie intégrante. La meilleure façon d'apprendre la récursion est de la pratiquer avec assiduité et persévérance. Il n'y a pas de meilleur endroit pour pratiquer le SQL que sur LearnSQL.fr. Ouvrez donc votre navigateur et suivez les exemples du cours Requêtes récursives et vous serez sur la voie de la maîtrise de SQL.