Réponse à la question

Historique de la question

Le modèle d'ensemble imbriqué a été popularisé par Joe Celko dans les années 1990 comme méthode pour représenter des structures d'arbre en SQL sans jointures récursives. En attribuant à chaque nœud une limite gauche (lft) et droite (rgt), le modèle permet de sélectionner des sous-arbres entiers via de simples requêtes de plage. Cependant, parce que la norme n'impose pas de contraintes d'intégrité des intervalles, des insertions en vrac concurrentes ou des erreurs de migration héritées introduisent fréquemment des corruptions où les intervalles se chevauchent partiellement, détruisant les sémantiques hiérarchiques. Cette question se pose dans des scénarios d'entreposage de données où les hiérarchies doivent être validées avant de soutenir les cubes OLAP ou les moteurs de recommandation.

Le problème

Dans un ensemble imbriqué valide, deux nœuds doivent être soit disjoints (a.rgt < b.lft), soit dans une relation de contenance stricte (a.lft < b.lft ET a.rgt > b.rgt). Un chevauchement partiel - où a.lft < b.lft mais a.rgt se situe entre b.lft et b.rgt - crée une impossibilité logique où un nœud semble être à la fois un frère et un descendant, rompant les requêtes de sous-arbre. Détecter ces violations nécessite de comparer chaque paire d'intervalles pour trouver des intersections qui manquent d'enveloppe appropriée, ce qui est coûteux sur le plan computationnel s'il est fait de manière procédurale.

La solution

Nous utilisons un auto-jointure avec l'algèbre des intervalles pour identifier les croisements sans contenance. Le prédicat détecte quand le nœud a commence avant le nœud b mais se termine à l'intérieur de la plage de b, indiquant un chevauchement partiel.

SELECT a.id AS violating_node_a, 
       b.id AS violating_node_b,
       a.lft AS a_left, a.rgt AS a_right,
       b.lft AS b_left, b.rgt AS b_right
FROM nested_set a
JOIN nested_set b 
  ON a.lft < b.lft           -- a commence avant b
  AND a.rgt > b.lft          -- a se termine après le début de b (intersection)
  AND a.rgt < b.rgt          -- mais a se termine avant que b ne se termine (pas de contenance)
WHERE a.id < b.id;           -- Éviter les doublons symétriques

Cette requête retourne toutes les paires de nœuds qui s'intersectent de manière illégale. Pour la rendre exécutable dans des environnements de production à forte lecture, des index composites sur (lft, rgt) et (rgt, lft) permettent des analyses uniquement basées sur les index, réduisant la complexité de O(n²) à des recherches de plage de O(n log n).

Situation de la vie réelle

Lors d'une migration sans temps d'arrêt d'une taxonomie de produit de vente au détail d'un ancien système IBM DB2 vers un entrepôt de données PostgreSQL, l'équipe d'ingénierie a choisi le modèle d'ensemble imbriqué pour supporter des requêtes de cumul de catégories rapides pour le tableau de bord analytique. Le pipeline ETL a calculé les valeurs lft et rgt à l'aide de fonctions de fenêtre par lots, mais des conditions de concurrence dans l'API d'exportation du système hérité ont produit des erreurs de décalage, entraînant 147 intervalles de catégorie qui se chevauchent. Ces chevauchements ont provoqué un double comptage des produits dans les rapports de revenus, gonflant les ventes projetées de 12 %.

Trois stratégies de remédiation ont été évaluées.

Stratégie 1 : Validation procédurale à l'aide d'un curseur. Une fonction PL/pgSQL itérait à travers chaque nœud, vérifiant récursivement les chevauchements en comparant chaque nœud avec tous les autres ayant des valeurs lft plus élevées. Bien que conceptuellement simple, cette approche entraînait des verrous au niveau des lignes et prenait 38 minutes à s'achever sur 2,3 millions de catégories, violant la SLA de fraîcheur stricte de cinq minutes pour les mises à jour d'inventaire. Elle a été rejetée en raison d'une dégradation de concurrence inacceptable.

Stratégie 2 : Reconstruction via CTE récursive. Nous avons envisagé d'abandonner complètement le modèle d'ensemble imbriqué et de reconstruire l'arbre à partir d'une liste d'adjacence à l'aide d'un CTE récursif pour générer de nouveaux intervalles corrects. Cela aurait corrigé la corruption mais aurait nécessité une réécriture complète de la table et une suspension temporaire de l'API de catalogue, rendant effectivement la recherche de produits hors ligne. Cela traitait également le symptôme plutôt que d'identifier les enregistrements corrompus spécifiques à des fins d'audit.

Stratégie 3 : Algèbre des intervalles basée sur l'ensemble (SQL ANSI). Nous avons implémenté la requête d'auto-jointure utilisant strictement des prédicats SQL standard. En tirant parti des index B-arbre sur les colonnes d'intervalle, la validation a été complétée en 4,2 secondes, identifiant exactement quelles 147 paires de nœuds violaient les règles de contenance. Cela nous a permis de mettre en quarantaine uniquement les sous-catégories affectées pour correction manuelle tout en maintenant le reste du catalogue en ligne.

Nous avons choisi la stratégie 3 car elle a fourni une précision chirurgicale sans bloquer les écrivains ni nécessiter de temps d'arrêt. Le résultat a été une taxonomie propre où les limites d'intervalle formaient des sur-ensembles stricts, restaurant l'intégrité référentielle et s'assurant que les mises à jour conformes aux ACID ultérieures ne pourraient pas introduire de nouveaux chevauchements en raison des contraintes de base de données ajoutées.

Ce que les candidats oublient souvent

Comment faites-vous la distinction entre une relation de contenance valide parent-enfant et un chevauchement partiel invalide lors de l'écriture du prédicat de jointure ?

Les candidats confondent souvent intersection et contenance. Ils écrivent a.lft < b.lft ET a.rgt > b.lft (ce qui ne vérifie que pour l'intersection) et croient à tort que cela détecte des violations. Le détail critique est l'exclusivité du point final : pour une contenance stricte, la limite droite du parent doit dépasser la limite droite de l'enfant (a.rgt > b.rgt). Un chevauchement partiel se produit spécifiquement lorsque a.lft < b.lft ET a.rgt > b.lft ET a.rgt < b.rgt. Les débutants manquent souvent la troisième condition, ce qui entraîne un retour de faux positifs pour des paires parent-enfant valides. De plus, ils oublient d'exclure les paires auto-référencées (a.id != b.id) ou de traiter les doublons symétriques en imposant a.id < b.id, entraînant des rapports de violation redondants.

Pourquoi un nœud peut-il sembler n'avoir aucun chevauchement tout en étant orphelin de la racine, et comment détectez-vous cela en n'utilisant que des opérations sur des ensembles ?

Un nœud orphelin existe lorsqu'aucune ligne unique ne contient son intervalle entier (lft, rgt), ce qui signifie qu'il n'a pas de chemin vers la racine. Les candidats essaient souvent de résoudre ce problème avec un LEFT JOIN cherchant des parents NULL, mais cela échoue à distinguer le nœud racine légitime (qui ne devrait pas avoir de parent) des véritables orphelins. L'approche correcte utilise NOT EXISTS avec une exclusion de la racine globale :

SELECT c.id
FROM nested_set c
WHERE NOT EXISTS (
  SELECT 1 FROM nested_set p
  WHERE p.lft < c.lft AND p.rgt > c.rgt
)
AND c.lft != (SELECT MIN(lft) FROM nested_set);

Le cas particulier que les débutants manquent est le scénario multi-racine : si la table contient accidentellement deux arbres séparés, le nœud avec le deuxième plus petit lft peut sembler n'avoir aucun parent si nous vérifions seulement le minimum de lft. La requête doit identifier explicitement la racine unique (minimum lft) et l'exclure ; sinon, elle marque faussement la racine secondaire comme orphelin.

Comment détecteriez-vous une violation à parents multiples - où un nœud est contenu par deux ancêtres distincts qui ne sont pas hiérarchiquement liés - en utilisant strictement SQL ANSI sans fonctions de fenêtre ?

Ceci est distinct de la détection de chevauchements car les deux ancêtres sont disjoints (frères valides), mais les deux contiennent incorrectement le même nœud enfant. Cela viole la propriété de l'arbre (un seul parent) mais ne crée pas de chevauchement d'intervalle entre les ancêtres. Les candidats essaient souvent de GROUP BY child_id HAVING COUNT(*) > 1 sur tous les ancêtres, mais cela échoue car un nœud valide en profondeur a naturellement de nombreux ancêtres (grands-parents, etc.). La solution nécessite d'identifier le parent immédiat : l'ancêtre avec la valeur lft maximale qui est encore inférieure à celle de l'enfant.

SELECT c.id AS child_id
FROM nested_set c
JOIN nested_set p ON p.lft < c.lft AND p.rgt > c.rgt
WHERE NOT EXISTS (
  SELECT 1 FROM nested_set p2
  WHERE p2.lft > p.lft AND p2.rgt < p.rgt
    AND p2.lft < c.lft AND p2.rgt > c.rgt
)
GROUP BY c.id
HAVING COUNT(*) > 1;

La sous-requête filtre pour les parents immédiats en s'assurant qu'il n'existe aucun nœud intermédiaire entre le candidat et l'enfant. Les débutants manquent cette logique de "plus proche ancêtre", comptant au lieu de cela tous les conteneurs et marquant incorrectement chaque nœud profond comme une violation.