\chapter{Arborescences et graphs}

Les arborescences et les graphs sont deux structures de données extrêmement utiles et souvent rencontrées dans les applications modernes. 
Le cas le plus simple pourrait être un forum de discussions \footnote{Anciennement, PhpBB permettait de répondre à un message antérieur, et copiait pour cela le message en question dans le nouveau encart. Niveau traçabilité, on était plus proche du zéro absolu que de la blockchain.}, un réseau social ou une plateforme de discussions chiffrée \footnote{iMessages est sans doute plus évolué que Signal à ce sujet, mais les deux permettent bien de répondre à un message en particulier}, où un intervenant `A` a la possibilité de répondre à un message antérieurement publié.

\section{Arborescences}

Il est possible de voir une arborescence comme un graph dirigé dont chaque noeud n'aurait au maximum qu'une seule relation vers son parent. 
Chaque niveau de l'arborescence est un \texttt{noeud}, tandis que les noeuds n'ayant aucun enfant sont des \texttt{feuilles}.

\begin{graphic}{images/trees/tree01.png}
    \caption{Un exemple d'arborescence sur quatre niveaux}
\end{graphic}

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:

\begin{itemize}
 \item Autant de tables qu'il y a de niveaux
 \item Adjency lists
 \item Path Enumeration ou \textit{jaywalking}
 \item Nested sets
 \item Closure trees
\end{itemize}

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

\subsection{1 table = 1 niveau}

Cette solution est la plus facile à mettre en place, mais a tellement d'inconvénients qu'elle n'a pas vraiment sa place ici. 
Dans le cas d'un réseau social, c'est un peu comme si nous ne pouvions répondre qu'à un certain nombre de messages, ou comme si notre arborescence était artificiellement limitée à un nombre restreint de niveaux. 

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).

\begin{minted}[tabsize=4]{python}
# 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
        )
\end{minted}

Avant d'aller plus loin, nous voyons clairement à l'étape suivante, on voit clairement que les champs \texttt{name} et la fonction \texttt{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:

\begin{minted}[tabsize=4]{python}
# 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)
\end{minted}

\begin{minted}[tabsize=4]{python}
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()
\end{minted}

Ce qui nous affichera le résultat suivant: \texttt{'Niveau 1 / Niveau 2 / Niveau 3'}.

C'est facile à mettre en place, \ldots mais pas très flexible.

\textit{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).

\subsection{Tables liées}

La représentation d'une arborescence grâce à des tables est la plus simple que nous pourrons trouver: elle consiste à créer une table par niveau devant être représenté.

\begin{minted}{python}

from django.db import models


class Level1(models.Model):
    name = models.CharField(max_length=255)


class Level2(models.Model):
    name = models.CharField(max_length=255)
    parent = models.ForeignKey(Level1, null=True, blank=True)


class Level3(models.Model):
    name = models.CharField(max_length=255)
    parent = models.ForeignKey(Level2, null=True, blank=True)


class Level4(models.Model):
    name = models.CharField(max_length=255)
    parent = models.ForeignKey(Level3, null=True, blank=True)

\end{minted}

Cette représentation est réellement simpliste, et même si elle peut répondre rapidement à un besoin, nous nous rendons compte rapidement des limites de ce système:

\begin{enumerate}
    \item Il est impossible de \textbf{déplacer} une instance d'un niveau vers un autre: tant que l'on restera au même niveau, il sera possible de modifier le parent, mais pas de changer un objet de niveau.
    \item Si nous souhaitons ajouter un nouveau niveau, cela reviendra à ajouter une nouvelle classe (et donc, une nouvelle table). 
    \item La récupération de données (ie. \textit{Le chemin complet vers une entité}) reviendra à exécuter autant de requêtes qu'il y a de niveaux avant la racine.
\end{enumerate}

Ces points impliquent que l'évolutivité de la solution sera rapidement compromise.

\subsection{Listes adjacentes}

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, ...).

\begin{minted}[tabsize=4]{python}
# 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
\end{minted}

\begin{minted}{python}
from adjency_list.models import Node

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

n3.breadcrumb()
\end{minted}

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

\begin{minted}{python}
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'
    }
]
\end{minted}

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

\begin{itemize}
    \item La première pour récupérer l'objet dont le nom est `C` (celui que l'on cherche),
    \item Puis son parent (sur base de la propriété `parent = 2`),
    \item Puis le "parent du parent" (sur base de la propriété `parent = 1`).
\end{itemize}

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.

\subsection{\textit{Path enumeration}}

L'énumération du chemin 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.
Et c'est extrêmement compliqué à maintenir, car:

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

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.

\subsection{\textit{Nested sets}}

Les \textit{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 \textbf{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.

\subsection{Closure tables}

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

\begin{itemize}
    \item On doit donc passer par une table connexe pour connaître la structure
    \item 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.
\end{itemize}

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

On a un exemple de remplissage/vidage d'une closure table, mais il faudrait en fait présenter les listes adjacentes et les autres structures de données.
Comme ça on pourra introduire les graphs juste après.

\begin{minted}[tabsize=4]{python}
# <app>/management/commands/rebuild.py
"""This command manages Closure Tables implementation

It adds new levels and cleans links between entities.
This way, it's relatively easy to fetch an entire tree with just one tiny
request.
"""

from django.core.management.base import BaseCommand

from structure.models import Entity, EntityTreePath


class Command(BaseCommand):
    def handle(self, *args, **options):
        entities = Entity.objects.all()

        for entity in entities:
            breadcrumb = [node for node in entity.breadcrumb()]
            tree = set(EntityTreePath.objects.filter(descendant=entity))

            for idx, node in enumerate(breadcrumb):
                tree_path, _ = EntityTreePath.objects.get_or_create(
                    ancestor=node, descendant=entity, weight=idx + 1
                )

                if tree_path in tree:
                    tree.remove(tree_path)
            for tree_path in tree:
                tree_path.delete()
\end{minted}

\section{Graphs}

La représentation de graphs est hors de ce périmètre: il conviendrait d'aborder des bases de données ayant un modèle différent d'un modèle relatonnel, sans quoi les performances seront atrocement complexes et abominables \cite[p. 49-55]{data_intensive}.
