Arbres
Les bases de données relationnelles sont conçues pour modéliser et organiser des informations structurées sous forme de tables, reliées entre elles par des relations. Dans la plupart des cas, les données s’organisent naturellement sous une forme tabulaire simple (par exemple une liste de clients, de commandes ou de produits).
Cependant, certaines situations nécessitent de représenter des données hiérarchiques, c’est-à-dire des données organisées en arbres. C’est le cas, par exemple, lorsqu’on souhaite gérer :
- une arborescence de catégories de produits et leurs sous-catégories,
- une structure d’entreprise avec ses départements et sous-départements,
- ou encore des commentaires imbriqués dans un forum.
Adjacency List (modèle d’adjacence)
Chaque nœud stocke l’identifiant de son parent.
Avantages
- Simple à comprendre.
- Facile à insérer et à modifier.
Limites
- Difficile d’interroger plusieurs niveaux sans récursivité.
CREATE TABLE familles (
id SERIAL PRIMARY KEY,
nom TEXT NOT NULL,
parent_id INT REFERENCES familles(id)
);
Primeur
├── Légumes
│ ├── Racines
│ └── Feuilles
└── Fruits
└── Pépins
Lire la famille de premier niveau
SELECT code, famille, code_parent
FROM famille
WHERE code = '02'
Lire les enfants directs du premier niveau
SELECT code, famille, code_parent
FROM famille
WHERE code_parent = '02'
| code | famille | parent |
|---|---|---|
| 02RACINE | **** Racines & Tubercules | 02 |
| 02CUCURB | **** Cucurbitacées | 02 |
| 02LEGUM | **** Légumineuses | 02 |
| 02COMPOS | *** Produits composés | 02 |
| 02FEUILLE | **** Feuilles et tiges v02 | |
| 02SOLAN | **** Solanacées | 02 |
| 02CHAM | Champignons | 02 |
| 02CHOU | Chou | 02 |
| 02MAIS | Maïs | 02 |
Combiner les résultats
SELECT code, famille, code_parent
FROM famille
WHERE code = '02'
UNION ALL
SELECT code, famille, code_parent
FROM famille
WHERE code_parent = '02'
Utiliser la récursivité pour descendre en profondeur
WITH RECURSIVE famille_parent AS (
SELECT code, famille, code_parent
FROM famille
WHERE code = '01'
UNION ALL
SELECT f.code, f.famille, f.code_parent
FROM famille f
join famille_parent on f.code_parent = famille_parent.code
)
SELECT * FROM famille_parent;
Remonter les familles jusqu'à la racine
WITH RECURSIVE ancetre AS (
SELECT code, famille, code_parent, 1 AS niveau
FROM famille
WHERE code = '02CUCURB'
UNION ALL
SELECT f.code, f.famille, f.code_parent, a.niveau + 1
FROM famille f
JOIN ancetre a ON a.code_parent = f.code
)
SELECT *
FROM ancetre
ORDER BY niveau DESC; -- de la racine vers le nœud
Récupérer la hiérarchie dans une chaine de caractères formatée.
SELECT string_agg(famille, ' > ' ORDER BY niveau DESC) AS fil_ariane
FROM ancetre;
représentation intervallaire
Le modèle d’adjacency list (parent_id) est simple, mais certaines requêtes deviennent complexes, surtout :
- récupérer tous les descendants d’un nœud,
- récupérer le chemin complet d’un nœud.
La représentation intervallaire ou modèle d’ensembles imbriqués (Nested Sets) résout ce problème en attribuant à chaque nœud deux valeurs entièrement déterministes :
inf (gauche) sup (droite)
Ces valeurs définissent un intervalle [inf, sup] qui contient tous les descendants du nœud.
Principe
Chaque nœud reçoit deux nombres (inf et sup) de telle sorte que :
- la racine a l’intervalle le plus large [1, 2n] pour n nœuds,
- un enfant est strictement inclus dans l’intervalle de son parent,
- aucun nœud n’a un intervalle qui chevauche celui d’un nœud non descendant.
La représentation intervallaire est très efficace pour les lectures d’arbres complexes. Elle est particulièrement adaptée aux arbres stables. En cas de modifications il faut recalculer les bornes de tous les noeuds.
SELECT *
FROM famille
WHERE inf BETWEEN 2 AND 7
ORDER BY inf;
Récupérer tous les ancêtres
SELECT *
FROM familles
WHERE inf <= 5 AND sup >= 6
ORDER BY inf;
Calculer la profondeur
SELECT COUNT(parent.id) AS profondeur
FROM famille AS node
JOIN famille AS parent
ON parent.inf < node.inf AND parent.sup > node.sup
WHERE node.code = '02CUCURB';
Materialized Path (chemin matérialisé)
Dans les bases de données relationnelles, représenter une hiérarchie peut être complexe. Les modèles classiques, comme Adjacency List ou Nested Sets, nécessitent des requêtes récursives ou des mises à jour délicates pour récupérer les descendants, ancêtres ou construire un fil d’Ariane.
PostgreSQL propose l’extension ltree, spécialement conçue pour représenter des arborescences de manière simple et efficace. Elle permet de stocker un chemin complet pour chaque nœud et fournit des opérateurs et fonctions pour manipuler ces chemins.
L’extension introduit le type ltree, qui est une chaîne de labels séparés par des points, représentant le chemin depuis la racine jusqu’au nœud. Chaque segment (label) correspond à un nœud de l’arbre. Il représente le chemin complet depuis la racine, ce qui simplifie toutes les opérations sur l’arbre.
Trouver toutes les familles descendantes d’une catégorie
Utilisation d'un nouvel opérateur <@
select famille
FROM famille
WHERE famille.arborescence <@ 'Jardin.Primeur.Legumes';
Trouver toutes les ancetres d’une famille
SELECT f.*
FROM famille f
JOIN famille cible ON cible.code = '02POTIR'
WHERE f.arborescence @> cible.arborescence
ORDER BY nlevel(f.arborescence);