Arborescences et PostgreSQL

Mise à jour du 18/07/2014 : SQLite intègre les requêtes « récursives » depuis la version 3.8.3. La solution décrite dans cet article ne se limite donc plus à PostgreSQL.

Problématique

Un problème sur lequel je me suis plusieurs fois cassé les dents est celui de la représentation d’une arborescence dans une base de données SQL. Bien souvent, il faut choisir entre une base bien structurée mais peu performante, ou performante mais mal structurée.

En général, le respect des bonnes pratiques nous restreint à utiliser une couche d’abstraction et de n’utiliser que des fonctionnalités communes à chaque SGBD ce qui malheureusement nous fait passer à côté de fonctionnalités réellement intéressantes comme celles des requêtes récursives de PostgreSQL et nous pousse à utiliser d’autres solutions qui ont leurs limites.

Structure de base

Intuitivement et conformément à la définition mathématique d’un arbre (qui est un graphe particulier, et qui contient donc un ensemble de nœuds et un ensemble de couples) une table des relations enfant/parent tombe sous le sens.

Par exemple, pour stocker une arborescence du type:

1
├── 2
└── 3
    └── 4

On aura donc une table similaire à celle-ci :

parent	enfant
1	2
1	3
3	4

Mais le stockage est une chose, la récupération des informations en est une autre. Or, s’il est très simple ici de récupérer le parent d’un nœud, pour connaître l’ensemble de ses ancêtres, c’est une autre paire de manches…

Solution 1: la bidouille applicative

Intuitivement toujours, la solution serait de faire plusieurs requêtes :

SELECT parent FROM arbre WHERE enfant = 4;

Cette requête retourne {3} et on peut donc renchaîner sur

SELECT parent FROM arbre WHERE enfant = 3;

qui retourne {1}

On peut donc réussir à récupérer les ancêtres du nœud numéro 4 mais au prix de 2 requêtes. Globalement, plus l’arborescence est profonde et plus le nombre de requêtes est important. Un nœud qui sera à une profondeur de 10 nécessiterait 9 requêtes.

Par ailleurs, les requêtes ne peuvent pas être rassemblées en une seule transaction puisque chacune dépend du résultat de la précédente, donc si une modification a lieu en même temps, le résultat pourra être erroné.

Solution 2: la bidouille structurelle

Autre solution: ajouter l’information dans une table supplémentaire.

ancetre	descendant
1	2
1	3
1	4
3	4

Cette solution est déjà plus sûre et plus performante car une seule requête est nécessaire pour obtenir l’intégralité des ancêtres d’un noeud.

On est sur la bonne voie, mais le problème c’est que cela introduit de la redondance dans la base. En effet, la liste des relations ancêtre/descendant se déduit des relations parent/enfant. Notre base ne respecterait donc pas la forme normale de Boyce-Codd (et on y tient à cette forme normale n’est-ce pas?)

Et l’on serait confronté à toutes les complications techniques du genre « synchronisation de tables », etc. qui pompent l’air et rendent l’application difficile à maintenir dans le meilleur des cas.

Il nous faut donc une requête (éventuellement stockée dans une vue) qui va nous fournir la deuxième table en fonction de la première, dans un temps suffisamment court et en une seule requête pour préserver les propriétés ACID de notre base.

Solution 3 : PostgreSQL, WITH et RECURSIVE

PostgreSQL est à ce jour le seul SGBD libre que j’ai pu trouver et qui accepte les requêtes récursives. Mais je ne suis pas un expert sur le sujet; il y a peut-être d’autres SGBD qui le supportent ou peut-être que MySQL a prévu de l’implémenter…

Pour PostgreSQL, en tout cas, on utilise le mot-clef WITH qui permet de constituer des tables temporaires pendant la durée d’une requête. Le mot-clef RECURSIVE autorise alors l’utilisation de cette même table dans la requête dont elle est issue.

Dans notre cas, cela donne :

WITH RECURSIVE descendances(ancetre, descendant) AS (

  SELECT arbre.parent, arbre.enfant
  FROM   arbre

UNION 

  SELECT descendances.ancetre, arbre.enfant
  FROM   arbre, descendances
  WHERE  arbre.parent = descendances.descendant
)
SELECT * FROM descendances;

Selon la documentation de PostgreSQL, elle-même, il ne s’agit pas à proprement parler de récursivité, mais le mot-clef RECURSIVE est celui qui a été choisi au niveau de la normalisation SQL.

La table descendances va fournir l’équivalent de la table présentée dans la solution 2. Sauf que celle-ci est volatile et disparaîtra dès la fin de la requête.

On pourra remplacer le SELECT * FROM descendances en fonction de ce que l’on souhaite obtenir.

Pour récupérer les ancetres du noeud 4 :

SELECT ancetre FROM descendances WHERE descendant = 4

Pour récupérer les descendants du noeud 1 :

SELECT descendant FROM descendances WHERE ancetre = 1

Je ne saurai pas expliquer le fonctionnement de cette requête mieux que la page de documentation officielle ne le fait déjà, cela dit les exemples présentés sont cependant légèrement plus complexes car ils s’appliquent à des cas plus génériques. Il existe aussi un post très intéressant avec un cas concret  concernant des employés et leur hiérarchie.

Conclusion

Il est toujours bon de s’appliquer à mettre en place des bonnes pratiques de conception. Cependant il arrive parfois que, faute de solutions techniques suffisamment évoluées,  une entrave au règlement sur l’une puisse améliorer le respect d’une autre.

En faisant le choix d’utiliser la récursivité dans PostgreSQL, on se rend dépendant de ce système, mais on gagne en clarté et en cohérence sur l’ensemble de l’application dès qu’il s’agit de manipuler des arborescences ou toute autre structure complexe à parcourir.

PostgreSQL est donc, selon moi, la meilleure solution actuelle pour travailler avec des structures arborescentes. En attendant le développement de bases de données sémantiques…

---

Arborescences et PostgreSQL par Charles-Edouard Coste est mis à disposition selon les termes de la Licence Creative Commons Paternité – Pas de Modification 3.0 France