Stocker et interroger des données hiérarchiques

13/08/2012 Comments off

Cela fait un moment que j’avais envie de faire cette rubrique. Elle rassemblera des retours d’expériences que j’ai pu avoir sur les bases de données relationnelles (MySQL, Oracle, Postgres, H2, Derby, ou tout autre moteur similaire). Bref, des modélisations non triviales, des opérations bizarres, des structures d’index spécialisées, y’a de quoi faire dans ce monde en dehors des connaissances standards.

Aujourd’hui : comment stocker et interroger un arbre dans une BD ? Chaque nœud contiendra une seule donnée value de type integer.

Pourquoi c’est dur, chef ?

Pour comprendre la difficulté de ce problème, il faut revenir à l’algèbre relationnelle. Cette algèbre permet de manipuler les données modélisées sous forme de relations, c’est-à-dire d’ensembles de tuples respectant le même schéma. À son époque Edgar Codd a défini cette algèbre avec 6 opérateurs fondamentaux (sélection, projection, produit cartésien, union, différence ainsi que le renommage). Ensemble ces opérateurs permettent de faire de très nombreuses opérations complexes telles que des jointures, extérieures (outer) ou non.

Bon, ça, c’est bien gentil, mais on n’a pas spécialement avancé dans le problème. Peut-être que ça avancera mieux quand je dirais que le théorème de Codd montre que l’algèbre relationnelle a une puissance d’expression inférieure à la logique du premier ordre. En particulier, elle est équivalente si on enlève la récursion. La conséquence c’est que : le SQL de base n’est pas récursif. Mettez-vous bien ça dans le crâne quand vous faites une modélisation.

Les arbres : la structure récursive de référence. Les approches de « diviser pour mieux régner », les parcours, la programmation dynamique, tout est basé sur la récursion. Ainsi, même une requête simple comme « obtenir tous les fils d’un nœud » est impossible en SQL de base. Personnellement, j’ai eu plusieurs fois à utiliser cette structure pour représenter un réseau hiérarchique (réseau de capteur, réseau domestique).

Solution de l’auto-pilote : le id-parentId

L’approche que beaucoup beaucoup de gens font, car c’est la plus intuitive, la moins coûteuse en stockage. Mais aussi la plus limitée en interrogation. Attention je vous le donne en mile :

Tree(id INTEGER PRIMARY KEY, parentId INTEGER, value INTEGER NOT NULL)

Nous avons la relation indiquant : le nœud id a le parent parentId et la valeur value. Par mesure de simplification parentId peut être NULL. — Dans un schéma parfaitement normalisé par les définitions de Codd-Date, il faudrait une relation TreeSource(id, value) en plus. — Bon, évidemment, je suppose que vous n’êtes pas trop bête et vous m’ajoutez les index qui vont bien là où il y en a besoin.

Très efficace en terme de place, il permet aussi de répondre facilement à deux requêtes : « Quel est le parent d’un nœud ? » et « Quels sont les fils directs d’un nœud ? ». Par contre, oubliez les requêtes comme « TOUS les fils d’un nœud ».

MAIS, il y a une exception. Comme ce genre de modélisation revient régulièrement, les gens n’ont pas hésité à rajouter cette fonctionnalité dans SQL. Lors de la norme SQL-99, il a eu l’ajout de la clause WITH dans les requêtes SQL. Cela permet d’ajouter la récursion. Voilà la structure de ce genre de requête en gros :

WITH vueRecursive(attribut1,...,attributn)
AS (
      Requête d initialisation
      Liaison (UNION ALL, UNION, MINUS, INTERSECT)
      Requête de récursion
)
SELECT ... FROM vueRecursive ...

Des exemples existent pas mal sur la toile, cherchez « with clause sql », vous aurez masse de résultats. Par contre, il ne faut pas compter sur cette syntaxe la plupart du temps ! Il n’est pas implémenté dans tous les moteurs. Actuellement, seules les versions récentes d’Oracle, DB2, SQL Server et Postgres supportent cette syntaxe.

Le coût de cette solution n’est pas si moche au total, puisque vous êtes sur une requête que vous exécutez jusqu’à plus soif. En utilisant l’UNION ALL (qui s’optimise bien), vous vous en sortirez pas si mal la plupart du temps. Par contre, n’oubliez pas que la recherche pourra nécessiter la lecture de plusieurs pages de la relation (ou de l’index) pour trouver le résultat final. Les coûts I/O sont pas si géniaux que ça.

Solution qui a envie d’être intelligente : lft-rgt

Bon maintenant, on va essayer de penser outside the chimney pour trouver un solution qui tiens peut-être un peu mieux la route. Parlons donc de la plus connue : le modèle Nested Set. Voilà le schéma :

Tree(id INTEGER PRIMARY KEY, value INTEGER NOT NULL, lft INTEGER NOT NULL, rgt INTEGER NOT NULL)

Bon, je vous comprends, ça veut pas dire grand chose. Dites vous une chose, la contrainte est la suivante : les valeurs [lft, rgt] forment un intervalle et tous les autres intervalles strictement inclus dans celui-ci sont fils du nœud. Donc là on exploite à mort les propriétés des structures d’arbres.

Les requêtes possibles maintenant : il y en a quand même pas mal !

  • Récupérer un sous-arbre : sélection sur lft > v.lft et rgt < v.rgt, ordonné par lft pour former une réponse structurée.
  • Récupérer le chemin : sélection sur lft < v.lft et rgt > v.rgt, toujours ordonné par lft
  • Compter le nombre de nœuds fils : (rgt-lft-1)/2

Les complexités de sélection sont parfaites car ce sont juste des lookups d’index et ne dépendent pas de la profondeur de l’arbre donc youpi ! Avec des petits agrégats en plus, on est capable de récupérer le niveau d’un nœud ou d’autres opérations sympathiques rapidement.

Si vous voulez mon avis, cette solution est pas ultime ultime et ce pour une raison simple : la construction ou mise à jour est HORRIBLE ! Par exemple, l’insertion d’un nœud implique la modification de la moitié de la relation. L’idée est de décaler les indices lft et rgt des nœuds strictement à droite de 2, et pour les nœuds fils, s’il en existe, de 1. Je ne détaille pas les exemples ici, mais vous pouvez trouver des procédures pour mettre à jour ici.

Si vos données pour chaque nœud sont lourdes, vous pouvez découper la gestion des lft-rgt dans une autre table. Ainsi la modification ne demandera que la lecture-écriture de quelques pages en bloc (mais vous perdez la normalisation et vous savez ce que ça implique bande de coquins).

La solution du bonjour-j’ai-pas-peur : la table de clôture

Soyons bourrin Mesdames et Messieurs, n’ayons pas peur ! La taille n’a plus d’importance, le coût d’entretien, on s’en fiche : voici la table de clôture transitive ! Quant au schéma :

Tree(id INTEGER PRIMARY KEY, value INTEGER NOT NULL)
Closure(id INTEGER PRIMARY KEY, ancestorId INTEGER PRIMARY KEY, level INTEGER)

Oui, vous avez bien vu, oui ! Il y a une deuxième relation ! Et assez grosse en fait puisque si vous regardez bien, il y a une clé primaire composite. La relation Closure indique : le nœud id possède l’ancêtre ancestorId à un profondeur hiérarchique de level. L’idée de cette solution est de précalculer la récursion pour chaque nœud et de la stocker dans une relation.

Bon alors, passons les banalités : oui ça coûte en espace de stockage. Ça coûte même beaucoup, car pour chaque nœud vous allez avoir un n-uplet pour chaque ancêtre ! Ouchy-daisy. Mais bon, ça va très vite, on peut faire des jointures qui vont bien, on peut même sélectionner sur la profondeur de récursivité, wouzi ! De plus, on peut implémenter l’entretien de la clôture transitive de façon assez simpliste à coup de trigger si le SGBD le supporte. Conclusion : pas si moche.

La solution du futé : le lignage

Bonjour, je pète ma NF1, ça ne vous gêne pas ? Au lieu de faire une table spéciale pour faire la clôture, on va faire un attribut spécial qui désigne le lignage d’un nœud. Voici le schéma :

Tree(id INTEGER PRIMARY KEY, value INTEGER NOT NULL, path VARCHAR NOT NULL)

L’attribut path indique la liste des identifiants pour aller jusqu’au nœud actuel, par exemple « 1.21.6.3 ». Là où cette solution est très intelligente c’est que tous les moteurs actuels permettent des manipulations de chaines de caractères sans trop de soucis. Même, vous pouvez faire des recherches à coup d’expression régulières ! Insérer ou supprimer un nœud c’est assez direct et rapide. La seule restriction c’est qu’il ne faut pas avoir des profondeurs trop grandes pour ne pas faire exploser cet attribut. Par contre, il n’y a pas a priori d’index classique pour traiter ces conditions de sélection. Ainsi, toute requête nécessitera un parcours complet de la table pour vérifier que la condition soit correcte.

Petite cerise sur le gâteau : dans Postgres, pour utiliser ce chemin, il y a une structure d’index qui s’appelle ltree, conçue par deux chercheurs russes. Pour l’avoir expérimenté, on obtient des boost de performances monstrueux sur toutes les requêtes similaires aux regexp. C’est très bluffant. Conseil pour les concepteurs d’SGBD : laissez la possibilité à la communauté d’ajouter des structures custom !

En gros voire très gros

C’est chaud ! Il n’y a pas de solution universelle. Vous n’allez quand même pas croire que j’allais faire tout le boulot pour vous, n’est-ce pas ? Donc ce que je vous conseille : maitrisez bien les avantages et inconvénients de chacune des solutions. Et comme je suis gentil, voilà les questions que vous devez vous poser :

  • Est-ce que l’espace disque est limité ?
  • Est-ce que l’arbre sera profond ?
  • Quelles requêtes dois-je poser sur ma structure ?
  • Quelles sont les capacités de votre moteur (index, custom index, with clause) ?
  • Quel est le ratio accès/modification ? Quelles modifications seront faites (append-only, delete, build from scratch) ?

Une fois que vous avez les idées claires sur ça. Vous êtes tranquille. Sachez de plus que vous pouvez combiner des idées pour obtenir des accès plus efficaces, genre ajouter l’attribut parent au lignage par exemple. Enfin, si vous voulez allez un peu plus loin, il y a une super overview sur stackoverflow sur le sujet.

Categories: DB, Informatique