Faites-le en SQL : Traversée récursive de l'arbre SQL

Dans l'article précédent, j'ai décrit comment utiliser Common Table Expressions pour trouver le plus court chemin dans un graphe dirigé. Cet exemple pouvait être difficile à suivre, je l'admets. Faisons quelque chose de beaucoup plus commun, quelque chose qui est implémenté sur presque tous les sites Web - un menu. Au lieu d'écrire le code, nous allons tirer parti de l'arborescence SQL en écrivant une seule requête. Nous utiliserons les CTE pour PostgreSQL et la clause de requête hiérarchique pour Oracle. Si vous voulez apprendre à écrire des CTEs par vous-même, je vous recommande notre cours interactif Requêtes récursives.

Voyons donc à quoi ressemble un simple menu :

Qu'avons-nous ici ? Il y a un menu principal et un menu déroulant qui apparaît après avoir cliqué sur le bouton du menu principal. Bien sûr, il peut y avoir d'autres sous-menus liés à un autre bouton du menu principal. De plus, il pourrait également y avoir un sous-sous-menu, qui apparaîtrait après avoir cliqué sur l'un des boutons d'un sous-menu.

En général, il peut y avoir un nombre illimité de niveaux de menu. La disposition des données d'un tel menu est une structure arborescente SQL:

Comme vous pouvez le voir, il s'agit d'une structure arborescente SQL typique. Il y a des nœuds de menu qui sont attachés à des nœuds parents. Le seul nœud sans parent est le nœud racine.

C'est ainsi que nous stockons une telle structure arborescente SQL dans la base de données :

Dans l'arborescence SQL, chaque nœud a son propre identifiant unique. Il possède une référence au nœud parent. Pour chaque nœud d'un sous-menu, nous avons besoin de son numéro de séquence à des fins d'ordonnancement. La colonne name est simplement une étiquette qui sera affichée sur le site Web. La colonne url_path peut nécessiter un peu plus d'explications. Chaque nœud stocke une partie du chemin URL complet de la ressource. Son chemin complet est une concaténation de l'adresse url_path de tous les nœuds depuis la racine jusqu'à ce nœud.

Par exemple, pour les données suivantes

> select * from menu_node;
 id | parent_node_id | seq |        name        | url_path  
----+----------------+-----+--------------------+----------- 
  1 |                |   1 | root               | 
  2 |              1 |   1 | Diagram            | diagram 
  3 |              1 |   2 | My models          | my_models 
  4 |              1 |   3 | Share requests     | share 
  5 |              1 |   4 | My account         | account 
  6 |              1 |   5 | Invite people      | invite 
  7 |              1 |   6 | Help               | help 
  8 |              7 |   1 | Documentation      | doc 
  9 |              7 |   2 | FAQ                | faq 
 10 |              7 |   3 | Ask a question     | ask 
 11 |              7 |   4 | Request a feature  | feature 
 12 |              7 |   5 | Report a problem   | problem 
 13 |              7 |   6 | Keyboard shortcuts | shortcuts 
 14 |              8 |   1 | Section 1          | section1 
 15 |              8 |   2 | Section 2          | section2 
 16 |              8 |   3 | Section 3          | section3 
(16 rows) 

le chemin complet du noeud "Section 1" est : /help/doc/section1.

Ayant une telle structure, nous voulons rendre le menu sur la page. Si nous n'utilisions pas une requête SQL pour obtenir les niveaux hiérarchiques de l'arbre, nous devrions soit exécuter plusieurs requêtes (pour chaque nœud afin d'obtenir ses enfants), soit récupérer toutes les données et construire la structure dans le code. Je ne dis pas que c'est une mauvaise approche, mais il est possible de le faire de manière plus simple et plus intelligente.

PostgreSQL - clause WITH récursive

Pour rendre un tel menu, nous devons connaître le chemin URL complet de chaque bouton, des informations sur le niveau du nœud (pour lui donner un style approprié en CSS) et l'endroit où le joindre (l'ID de son parent, bien sûr). Commençons donc à construire notre requête de sélection avec CTE :

WITH RECURSIVE menu_tree 
  (id, name, url, level, parent_node_id, seq) AS (

Tout d'abord, nous devons obtenir le nœud racine :

  SELECT 
    id, 
    name, 
    '' || url_path, 
    0, 
    parent_node_id, 
    1 
  FROM menu_node 
  WHERE parent_node_id is NULL

Ensuite, nous allons récursivement plus loin avec notre requête SQL, en concaténant le chemin et en incrémentant le niveau :

  UNION ALL 
  SELECT 
    mn.id, 
    mn.name, 
    mt.url || '/' || mn.url_path, 
    mt.level + 1, 
    mt.id, 
    mn.seq 
  FROM menu_node mn, menu_tree mt 
  WHERE mn.parent_node_id = mt.id

Et à la fin, nous devons obtenir toutes les lignes sauf le noeud racine (nous n'en avons plus besoin) dans le bon ordre. D'abord, ils doivent être classés par niveau, puis "groupés" par parent, et enfin en suivant l'ordre seq. La requête ressemblera donc à ceci :

SELECT * FROM menu_tree 
WHERE level > 0 
ORDER BY level, parent_node_id, seq; 

La requête finale :

WITH RECURSIVE menu_tree 
  (id, name, url, level, parent_node_id, seq) 
AS ( 
  SELECT 
    id, 
    name, 
    '' || url_path, 
    0, 
    parent_node_id, 
    1 
  FROM menu_node 
  WHERE parent_node_id is NULL 

  UNION ALL 
  SELECT 
    mn.id, 
    mn.name, 
    mt.url || '/' || mn.url_path, 
    mt.level + 1, 
    mt.id, 
    mn.seq 
  FROM menu_node mn, menu_tree mt 
  WHERE mn.parent_node_id = mt.id 
) 
SELECT * FROM menu_tree 
WHERE level > 0 
ORDER BY level, parent_node_id, seq;

Ça a l'air plutôt facile, non ? Nous obtenons donc les données :

 id |        name        |        url         | level | parent_node_id | seq 
----+--------------------+--------------------+-------+----------------+----- 
  2 | Diagram            | /diagram           |     1 |              1 |   1 
  3 | My models          | /my_models         |     1 |              1 |   2 
  4 | Share requests     | /share             |     1 |              1 |   3 
  5 | My account         | /account           |     1 |              1 |   4 
  6 | Invite people      | /invite            |     1 |              1 |   5 
  7 | Help               | /help              |     1 |              1 |   6 
  8 | Documentation      | /help/doc          |     2 |              7 |   1 
  9 | FAQ                | /help/faq          |     2 |              7 |   2 
 10 | Ask a question     | /help/ask          |     2 |              7 |   3 
 11 | Request a feature  | /help/feature      |     2 |              7 |   4 
 12 | Report a problem   | /help/problem      |     2 |              7 |   5 
 13 | Keyboard shortcuts | /help/shortcuts    |     2 |              7 |   6 
 14 | Section 1          | /help/doc/section1 |     3 |              8 |   1 
 15 | Section 2          | /help/doc/section2 |     3 |              8 |   2 
 16 | Section 3          | /help/doc/section3 |     3 |              8 |   3 
(15 rows)

Avec cette seule requête, vous pouvez obtenir toutes les données dont vous avez besoin pour rendre un simple menu à plusieurs niveaux. Grâce à la structure arborescente du SQL, vos données sont représentées de manière claire et facile à digérer.

Pour vous entraîner à écrire des requêtes hiérarchiques comme celle-ci, je vous recommande notre cours interactif Requêtes récursives.

Oracle - requêtes hiérarchiques

Dans Oracle, vous pouvez utiliser soit la clause de requête hiérarchique (également connue sous le nom de "requête CONNECT BY"), soit la factorisation de sous-requêtes récursives (introduite dans la version 11g release 2).

La structure de la seconde est presque la même que celle de la requête pour PostgreSQL. Les seules différences sont :

• l'absence du mot-clé RECURSIVE
• "level" est un mot réservé, nous devons donc le modifier

Le reste reste inchangé et la requête fonctionne bien.

En ce qui concerne la clause de requête hiérarchique, sa syntaxe est totalement différente. La requête ressemble à ceci :

SELECT 
  id, 
  name,
  SYS_CONNECT_BY_PATH(url_path, '/') AS url, 
  LEVEL, 
  parent_node_id, 
  seq 
FROM menu_node 
START WITH id IN 
  (SELECT id FROM menu_node WHERE parent_node_id IS NULL) 
CONNECT BY PRIOR id = parent_node_id;

Une chose à noter est que cette requête ira vraiment de manière récursive, c'est-à-dire - dans un ordre de profondeur d'abord. La clause WITH "récursive" dans PostgreSQL et (par défaut) dans Oracle parcourt la structure dans un ordre en largeur d'abord.

Comme vous pouvez le constater, comprendre le concept de l'arborescence SQL peut nous faire gagner un temps précieux (et quelques lignes de code). C'est à vous de décider si vous utilisez ou non les requêtes récursives, mais cela vaut vraiment la peine de connaître l'alternative.

Pour apprendre à écrire des requêtes récursives en SQL, je vous recommande notre cours interactif. Requêtes récursives. Il contient 114 exercices de codage pratiques qui vous permettront de vous entraîner aux expressions de table communes et aux requêtes récursives comme celles présentées dans cet article.