Organisation de données hiérarchiques, récursivité ou pas

Carine REIGNAULT - mardi 27 octobre 2009 à 11:42

Problématique

Dans un modèle relationnel, les données sont enregistrées dans des tables non hiérarchiques, comparables à un tableau plat où les colonnes représentent des champs et les lignes des enregistrements. Celles-ci ne rendent pas naturellement les relations de parentèles entre les données hiérarchiques. Avec une base relationnelle, il est donc nécessaire de trouver des moyens d’enregistrer les données hiérarchiques sous forme plate, en se ménageant des moyens de reconstruire leur hiérarchie.

Méthode classique

Souvent la première méthode qui vient à l’esprit lorsqu’on est confronté à cette problématique est l’utilisation d’une table « qui se mord la queue », c’est-à-dire avec des auto-jointures. Par exemple :

Figure n°1 : Données représentées sous forme hiérarchique

Figure n°2 : Données enregistrées en base

categorie_id	libelle	parent_id
1	Régime alimentaire	NULL
2	Carnivore	1
3	Félin	2
4	Lion	3
5	Léopard	3
6	Tigre	3
7	Canin	2
8	Loup	7
9	Renard	7
10	Herbivore	1
11	Vache	10
12	Chèvre	10

Cette structure permet de retrouver simplement pour un enregistrement quel est l’enregistrement père. Il est simple de retrouver tous les enregistrements fils d’un enregistrement en particulier. De plus la liaison des données entre elles restant relativement limitée, l’ajout et/ou la suppression de données n’affectent qu’un petit nombre d’enregistrements correspondant à une petite portion de l’arbre. Cela se corse lorsqu’il s’agit de retrouver tous les ascendants ou de reconstruire l’arbre complet (figure n°1) à partir des données enregistrées en base (figure n°2), car une seule requête SQL ne suffit généralement pas.

Dans le cadre du développement d’une application avec PHP, l’utilisation de fonctions récursives est de mise pour reconstruire l’arbre. Il s’agit de fonctions susceptibles de s’appeler elle-même lors de leur exécution. Dans notre exemple, pour la reconstitution de l’arbre, on exécute une fonction qui part d’un élément donné, recherche tous ses éléments fils et qui descend dans l’arbre en s’appelant elle-même pour chacun d’eux.

Ces fonctions ont l’inconvénient majeur d’exécuter autant de requêtes SQL qu’elles ne renvoient d’éléments, ce qui pourrait ressembler à du gaspillage. Pour les arbres de taille importante, cela peut devenir critique en termes de performance. De plus, de nombreux développeurs connaissent ou ont connu des problèmes pour programmer ce genre de fonctions. Leur mise en place est assez lourde car il est nécessaire de prévoir les cas d’erreurs pour que le système soit robuste, notamment celui où l’arbre est mal construit. Cela devient rapidement fastidieux.

Ajouter un commentaire

Aucun commentaire pour cet article