↓Aller au contenu

Modélisation d'une arborescence dans une DB relationnelle

·1386 mots·7 mins
Sommaire

Il existe plusieurs manières de représenter une hiérarchie ou une arborescence dans une base de données relationnelles. Plus précisément, il existe cinq modélisations principales connues; chaque présentation présente des avantages et désavantages.

La représentation d’une structure hiérarchique peut être faite de plusieurs manières:

  • Autant de tables qu’il y a de niveaux
  • Adjency lists
  • Path Enumeration
  • Nested sets
  • Closure trees

L’une d’entre elles sort du lot (les Closures) avec un tout-petit-micro-inconvénient par rapport à tous ses avantages.

1 table = 1 niveau
#

Cette représentation est la plus naïve du lot: on aurait autant de tables qu’il y a de niveaux à représenter. De cette manière, il est facile de faire des jointures entre les différentes tables.

Le problème est que chacune de ces tables aura les mêmes champs que les autres; une modification dans l’une d’entre elle devra sans doute être répercutée dans toutes les autres tables. Si un nouveau niveau peut être ajouté, cela équivaudra à ajouter une nouvelle table (avec autant de nouvelles contraintes que celles déjà présentes pour les autres tables).

# simple.models.py

from django.db import models


class FirstLevel(models.Model):
    """La racine de l'aborescence."""

    name = models.CharField(max_length=50)

    def breadcrumb(self):
        return self.name


class SecondLevel(models.Model):
    """Le deuxième niveau.

    On y trouve une propriété `parent`.
    Le reste est identique à la modélisation de la racine.
    """
    name = models.CharField(max_length=50)
    parent = models.ForeignKey(FirstLevel)

    def breadcrumb(self):
        return '{0} / {1}'.format(
            self.parent.name,
            self.name
        )


class ThirdLevel(models.Model):
    """Le troisième niveau.

    La modélisation est complètement identique au deuxième niveau;
    Juste que la ForeignKey pointe vers une classe différente.
    """
    name = models.CharField(max_length=50)
    parent = models.ForeignKey(SecondLevel)

    def breadcrumb(self):
        return '{0} / {1} / {2}'.format(
            self.parent.parent.name,
            self.parent.name,
            self.name
        )

Avant d’aller plus loin, nous voyons clairement à l’étape suivante, on voit clairement que les champs name et la fonction breadcrumb() sont copiés/collés entre les différentes classes.

Avec l’ORM de Django, il est possible de simplifier cette représentation en utilisant une notion d’héritage, mais il y a à nouveau une contrainte, dans la mesure où une clé étrangère ne peut pas être déclarée au niveau d’une classe abstraite.

Cela reviendrait à ceci, ce qui est un chouia plus élégant que la version précédente, mais pas parfait non plus:

# simple/models.py

class AbstractNode(models.Model):
    class Meta:
        abstract = True

    name = models.CharField(max_length=50)

    def breadcrumb(self):
        if getattr('parent') is not None:
            return [self,]


class FirstLevel(AbstractNode):
    pass


class SecondLevel(AbstractNode):
    parent = models.ForeignKey(FirstLevel)


class ThirdLevel(AbstractNode):
    parent = models.ForeignKey(SecondLevel)

from simple.models import *

l1 = FirstLevel(name='Niveau 1')
l2 = SecondLevel(name='Niveau 2', parent=l1)
l3 = ThirdLevel(name='Niveau 3', parent=l2)
l3.breadcrumb()

Ce qui nous affichera le résultat suivant: 'Niveau 1 / Niveau 2 / Niveau 3'

Avantage: c’est facile à mettre en place, mais pas très flexible. A priori, ces noeuds seront référencés par d’autres entités de votre base de données; les problèmes arriveront lorsqu’il faudra changer un noeud de niveau - c’est-à-dire lorsqu’un noeud de niveau 3 (par exemple) “déménagera” vers le niveau 2: cela pourra avoir des repercutions un peu partout, sans parler du fait que ce noeud ne conservera pas son identifiant. En termes de cohérences de données, il s’agira donc d’une nouvelle entité à part entière (alors qu’elle aura juste bouger un peu dans la structure).

Adjency Lists
#

Les Adjency lists représentent chaque enregistrement avec une clé vers son parent. Elles permettent une insertion extrêmement rapide, mais posent de gros problèmes de récupération lorsque la profondeur de la structure est inconnue (puisqu’on doit faire autant de jointures qu’il y a de niveaux… et que ceux-ci sont potentiellement infini…). Il est possible de passer par un contexte d’exécution SQL, mais cela ne changera intrinsèquement rien au nombre de requêtes qui sera effectué.

En résumé, c’est une bonne solution s’il y a beaucoup plus d’écritures que de lectures ou si la quantité d’enregistrements/de niveaux est relativement limitée. Dans le cas contraire, oubliez la: les performances vont rapidement se dégrader et les interrogations sur la base seront de plus en plus compliquées, notamment si on cherche à récupérer des noeuds spécifiques (eg. en fonction de leur niveau, d’un de leur ancêtre présent dans l’arborescence, …).

# adjency_list/models.py

from django.db import models


class Node(models.Model):
    name = models.CharField(max_length=50)
    parent = models.ForeignKey('self', null=True)

    def breadcrumb_list(self):
        if self.parent:
            return self.parent.breadcrumb_list() + [self.name]

        return [self.name]

    def breadcrumb(self):
        return ' / '.join(self.breadcrumb_list())

    def __str__(self):
        return self.name

from adjency_list.models import Node

n1 = Node(name='A')
n2 = Node(name='B', parent=n1)
n3 = Node(name='C', parent=n2)

n3.breadcrumb()

Le résultat sera identique à l’exercice précédent: 'A / B / C'. Si nous regardons le résultat des requêtes effectuées, cela nous donne ceci:

from django.db import connection

print(connection.queries)

[
    {
        'sql': 'SELECT * FROM "adjency_list_node" WHERE "adjency_list_node"."name" = \'C\'',
        'time': '0.000'
    },
    {
        'sql': 'SELECT * FROM "adjency_list_node" WHERE "adjency_list_node"."id" = 2',
        'time': '0.000'
    },
    {
        'sql': 'SELECT * FROM "adjency_list_node" WHERE "adjency_list_node"."id" = 1',
        'time': '0.000'
    }
]

Pour obtenir l’arborescence de cette structure, on voit bien que l’ORM de Django exécute trois requêtes:

  1. La première pour récupérer l’objet dont le nom est C (celui que l’on cherche),
  2. Puis son parent (sur base de la propriété parent = 2),
  3. Puis le “parent du parent” (sur base de la propriété parent = 1).

Imaginez maintenant que vous récupériez une arborescence complète sur six niveaux max avec plusieurs centaines de noeuds… 🤪

L’avantage de cette présentation est que l’écriture (ajout ou modification) est extrêmement rapide: il suffit de modifier la valeur de la propriété parent d’une instance pour que l’arborescence soit modifiée. L’intégrité de la base de données est constamment conservée.

Path enumeration
#

L’énumération du path consiste à ajouter une colonne dans laquelle nous conservons le chemin complet (par exemple ancêtre1 / ancêtre2 / enfant). Dans une certaine mesure, cela revient à stocker toutes les relations avec un noeud dans un champ textuel (type jaywalking - d’une certaine manière, un champ sert à conserver toutes les relations vers les ancêtres d’un enregistrement)… Et c’est extrêmement compliqué à maintenir, car:

  • Si un noeud est modifié, il faut modifier tous les champs qui y font référence
  • Il n’existe aucune aide relative aux méthodes d’insertion/mise à jour/suppression
  • Le caractère d’échappement doit être unique.

Et rien ne garantit l’intégrité relationnelle de la base de données: si un petit comique modifie la base sans passer par l’API, toute cohérence sera perdue.

Nested sets
#

Les nested sets ont pour but de simplifier la gestion présentée ci-dessous, en ajoutant un niveau de complexité sur la modélisation: la lecture de toute la hiérarchie peut se faire en une seule requête, mais l’écriture (ajout, modification et suppression) reste compliquée à implémenter. Un autre problème est qu’on perd une partie de la cohérence de la base de données: tant que le processus de mise à jour n’est pas terminée, la base peut se trouver dans un état de Schrödinger.

L’implémentation consiste à ajouter des valeurs gauche et droite sur chaque noeud. L’attribution des valeurs se fait selon un parcours préfixe: pour chaque enregistrement, la valeur gauche est plus petite que toutes les valeurs utilisées dans ses descendants; la valeur droite est plus grande que celle utilisée par tous ses descendants… Et ces valeurs sont entre toutes les valeurs gauches/droites de ses ancêtres.

Le problème intervient lorsque vous souhaitez ajouter, modifier ou supprimer un noeud: il vous faut alors recalculer l’ensemble des arborescences, ce qui est loin d’être performant. En plus de cela, on perd l’intégrité relationnelle, puisqu’un enfant pourrait avoir des valeurs incohérentes: avoir par exemple un parent qui pointe vers un noeud alors que le recalcul des valeurs est en cours.

Il existe des librairies toutes faites pour cela… Regardez du côté du pattern MPTT si vous ne trouvez rien sur les nested sets.

Closure trees
#

Le dernier, la closure consiste à créer une table supplémentaire reprenant toutes les relations d’un noeud vers ses enfants:

  • On doit donc passer par une table connexe pour connaître la structure
  • Cette table peut grandir très rapidement: pour cinq niveaux donnés, le niveau 1 sera lié à tous ses descendants (ainsi qu’à lui-même); le niveau 2 à tous ses descendants; etc. Pour cinq niveaux, on aura donc déjà 5 + 4 + 3 + 2 + 1 entrées.

Parmi les avantages, nous conservons l’intégrité relationnelle dans la mesure où chaque enregistrement sera référencé par une clé étrangère.

En conclusion
#

… MPTT / Closure Trees FTW ❤️

Ressources
#