Modélisation d'un arbre hiérarchique

Bonjour,

J'ai hésité à poster ma question dans le forum de SQL mais je pense qu'elle a plus rapport à de la conception.
Le but est de modéliser un arbre de catégories/sous-catégories, de profondeur variable, pour une base de données de produits stockée dans une base PostgreSQL.

J'ai lu pas mal de choses sur la façon de modéliser un arbre hiérarchique dans une base : relation simple avec champ parent_id, plusieurs relations, utilisation des CTE, de requêtes récursives et de WITH, utilisation de ltree, utilisation de la méthode par ensembles emboités, etc. J'avais opté pour cette dernière méthode dans mon ancienne base mais la technique est lourde à gérer, notamment lors de l'insertion ou du déplacement de catégorie(s).

Une de mes problématiques est que je travaille avec Django et son ORM, pratique pour des taches basiques monotables mais nettement plus retors dès lors que l'on cherche à exploiter des fonctionnalités avancées de la base ; une base de données est optimisée, plus efficace, plus puissante et nettement plus rapide qu'un ORM. Je préfère nettement écrire une procédure stockée, une fonction ou mettre en place un trigger plutôt que d'utiliser la fonction tortueuse d'un ORM.

J'ai donc deux questions :
1 - Quelle est la meilleure méthode pour modéliser un arbre hiérarchique dans une base SQL comme PostgreSQL ?
2 - Qu'elqu'un a t-il eu à gérer cette problématique en utilisant le couple PostgreSQL/Django ?

Vincent

Bonjour Vincent,

Citation:

---

Envoyé par Vincent

Le but est de modéliser un arbre de catégories/sous-catégories, de profondeur variable, pour une base de données de produits stockée dans une base PostgreSQL [...] j'ai lu pas mal de choses sur la façon de modéliser un arbre hiérarchique dans une base : relation simple avec champ parent_id, plusieurs relations, utilisation des CTE, de requêtes récursives et de WITH, utilisation de ltree, utilisation de la méthode par ensembles emboités, etc.

---

Avant de parler de CTE, WITH, etc., il est préférable d’aborder le problème de façon conceptuelle, c’est-à-dire de traiter le quoi avant le comment.

Par exemple, dans une discussion avec antonomas, à un moment donné j’avais écrit :

Citation:

---

Envoyé par fsmrel

Pour en revenir à votre MCD, s’il diffère sensiblement de celui-ci, pourriez-vous le présenter ? Rien de tel qu’une représentation graphique pour aborder un problème et éviter les quiproquos.

---

 
Et j’avais proposé un modeste MCD :

https://www.fsmwarden.com/developpez...CD_MCD_MOO.jpg

Suite à quoi il fut possible de discuter.

Pourrions-nous en faire autant ?

J’ai oublié de préciser qu’il est nécessaire — comme passe son temps escartefigue à le rappeler ! — de présenter les règles de gestion des données, puis d’utiliser un logiciel tel que Looping (gratuit et excellent) pour représenter un MCD (ou un diagramme de classes) et en dériver automatiquement le MLD et le code SQL de création des tables (PostgreSQL dans votre cas).

Bonsoir François,

Désolé de ne pas avoir été plus explicite concernant la modélisation. Voici plus de détails.

Pièce jointe 635244

Les règles sont les suivantes :

- une catégorie contient 0 à n catégories (filles)
- une catégorie fille possède un et un seul parent

Il s'agit d'une association un-à-plusieurs sur la même relation.
Je pense avoir modélisé cela correctement...

Vincent

Bonsoir,
Cela parait correct ; n'hésitez pas à rajouter des rôles sur les pattes de l'association réflexive, ce qui permettra de générer un MLD et un LDD plus explicites.
Bonne continuation !

Bonsoir Vincent,

D’accord, mais il y a un petit problème : du fait de la cardinalité 1,1, chaque catégorie contient plus ou moins directement sa catégorie parente :aie:
Avec une cardinalité 0,1, on pourra éviter le cycle.

Looping produit alors le code SQL suivant :

CREATE TABLE Categorie
(
   CategorieId CHAR(4),
   CategorieNom VARCHAR(50),
   CategorieId_parent CHAR(4),
   CONSTRAINT Categorie_PK PRIMARY KEY(CategorieId),
   CONSTRAINT Categorie_Categorie_parent_FK FOREIGN KEY(CategorieId_parent) REFERENCES Categorie(CategorieId)
);

Mais comme je ne tiens pas à la présence du bonhomme NULL, je procède à une scissiparité :

CREATE TABLE Categorie
(
        CategorieId    Char(4)      NOT NULL
      , CategorieNom   Varchar(32)  NOT NULL
    , CONSTRAINT Categorie_PK PRIMARY KEY (CategorieId)
) ;
CREATE TABLE Contient
(
        EnfantId    Char(4)      NOT NULL
      , ParentId    Char(4)      NOT NULL
    , CONSTRAINT Contient_PK PRIMARY KEY (EnfantId)
    , CONSTRAINT Contient_FK1 FOREIGN KEY (EnfantId) 
             REFERENCES Categorie (CategorieId)
    , CONSTRAINT Contient_FK2 FOREIGN KEY (ParentId) 
             REFERENCES Categorie (CategorieId)
) ;

Quelques inserts :

INSERT INTO Categorie VALUES ('e01', 'Categorie 01') ;
INSERT INTO Categorie VALUES ('e02', 'Categorie 02') ;
INSERT INTO Categorie VALUES ('e03', 'Categorie 03') ;
INSERT INTO Categorie VALUES ('e04', 'Categorie 04') ;
INSERT INTO Categorie VALUES ('e05', 'Categorie 05') ;
INSERT INTO Categorie VALUES ('e06', 'Categorie 06') ;
INSERT INTO Categorie VALUES ('e07', 'Categorie 07') ;
INSERT INTO Categorie VALUES ('e08', 'Categorie 08') ;
INSERT INTO Categorie VALUES ('e09', 'Categorie 09') ;
INSERT INTO Categorie VALUES ('e10', 'Categorie 10') ; 

Recherche de la descendance des catégories à partir de l’ancêtre 'e01' :

WITH DESCENDANCE (ParentId, EnfantId) AS
(
 (
  SELECT   ParentId, EnfantId
  FROM     Contient
  WHERE    ParentId = 'e01'
 )
UNION ALL
 (SELECT   x.ParentId, x.EnfantId
  FROM     Contient AS x JOIN DESCENDANCE AS y
             ON y.EnfantId = x.ParentId
 )
)

Recherche de l’ascendance du jeunot 'e06' :

 
WITH ASCENDANCE (EnfantId, ParentId) AS
(
 (
  SELECT   EnfantId, ParentId
  FROM     Contient
  WHERE    EnfantId = 'e06'
 )
UNION ALL
 (SELECT   x.EnfantId, x.ParentId
  FROM     Contient AS x JOIN ASCENDANCE AS y
             ON x.EnfantId = y.ParentId
 )
)
SELECT DISTINCT y.CategorieNom AS Enfant, z.CategorieNom AS Parent 
FROM   ASCENDANCE x 
         JOIN Categorie y ON x.EnfantId = y.CategorieId
         JOIN Categorie z ON x.ParentId = z.CategorieId 
;

En gros, j‘ai repris ce que j’avais proposé ici, en 2010...

Je constate que nous avions pas mal échangé en 2016, à propos de télescopes :P

Qu'en sera-t-il en 2030 ? :cfou:

Bonjour,

Pour compléter la solution "sans NULL" proposée par fsmrel, la mise en oeuvre avec Looping s'effectue en cochant la case "Générer une table de correspondance dans le MLD" dans la fenêtre de l'association.
Un petite remarque supplémentaire : un identifiant est forcément NOT NULL : il est donc inutile de le préciser.
Voici ce que cela donne avec Looping en renommant les clés étrangères avec les noms des rôles :

Pièce jointe 635261

Bonjour,

Merci pour vos réponses détaillées et pour la correction de cardinalité. La solution de François est séduisante, sans être d'une effrayante complexité.
J'avoue avoir choisi la solution des ensembles emboîtés dans la précédente version de la base car elle était très bien expliquée dans le livre de Joe Celko "SQL avancé". J'ai l'impression que c'est une solution intéressante lorsque l'arborescence est fixe et peu sujette à modification, ce qui n'est pas forcément mon cas.

@fsmrel
Je garde un excellent souvenir de nos discussions et des solutions que vous avez apportées à mes problématiques originales. La base fonctionne (ARAS Spectral Database) et le projet a été repris par un chercheur tchèque, Jaroslav Merc.
Je reviendrai peut-être quérir vos lumières en 2030 pour un autre projet astronomique. :mouarf: J'aime la modélisation des bases mais ce n'est pas forcément le cœur de mon travail.

@paprick
Je viens de découvrir Looping. Un logiciel bien sympathique et facile à prendre en main ! Merci de le partager.
J'ai d'ailleurs commandé le livre que vous avez écrit par le biais de la librairie Eyrolles il y a 1 mois mais je ne l'ai toujours pas reçu... :roll: Je l'attends pour mieux en exploiter les subtilités.

Vincent

Ave,

Citation:

---

Envoyé par Paprick

Pour compléter la solution "sans NULL" proposée par fsmrel, la mise en oeuvre avec Looping s'effectue en cochant la case "Générer une table de correspondance dans le MLD" dans la fenêtre de l'association.

---

Honte à moi de ne pas l’avoir vu... :oops: mais il est vrai que je me suis très vite contenté de reprendre ce que j’avais écrit en 2010. https://www.fsmwarden.com/images/smileys/papi2.png

Citation:

---

Envoyé par Vincent

Je reviendrai peut-être quérir vos lumières en 2030 pour un autre projet astronomique

---

Si entre temps notre soleil n’est pas devenu digne de figurer dans les catalogues d’ARAS...:whistle:

Je viens de découvrir sur ce forum l'existence de ce logiciel: looping et je suis allé sur son site. Question bête: sa prise en main est elle "gratuite"?
FP

Bonsoir,

Citation:

---

Envoyé par tournesol59

Je viens de découvrir sur ce forum l'existence de ce logiciel: looping et je suis allé sur son site. Question bête: sa prise en main est elle "gratuite"? FP

---

Oui, vous pouvez le récupérer sur le site et l'utiliser comme bon vous semble : Looping est gratuit et libre d'utilisation :lun:.

Vous pouvez télécharger Looping gratuitement ICI

Bonjour,

tournesol59, ça serait bien que vous remerciiez Paprick, il a fait un sacré boulot, gratis pro Deo... :hola:

Bonjour, me revoilou.

J'ai complété mon MCD en modifiant le nom de catégories. Le but est d'ajouter un nom de catégorie traduit dans plusieurs langues.

Les règles sont les suivantes :
- une catégorie possède un ou plusieurs noms (UTF-8)
- une catégorie possède au moins un nom dans la langue par défaut (français)
- A chaque nom de catégorie correspond un slug c'est à dire une suite de caractères alphanumériques (ASCII) correspondant à une URL unique, utilisée pour le référencement naturel. Le slug est à la traduction ASCII automatique du nom de la catégorie.
- Le slug doit être unique

La logique m'impose donc de sortir le champ nom de la relation Catégorie, pour ne pas avoir à ajouter un champ par langue dans ma relation et éviter le fameux bonhomme NULL.
En sortant le nom de la catégorie de ma relation Catégorie, je me retrouve sans "référent" dans ma relation. Bien que je pense que cela ne pose aucun problème puisque je vais avoir une clé primaire dans la future table, j'ai ajouté un champ identifiant (non NULL et UNIQUE) pour "identifier" mon futur enregistrement et m'y référer sans avoir à faire appel à la clé primaire. Je m'inquiète en fait pour la future insertion des valeurs dans la table Catégorie et des noms dans la table Nom catégorie, notamment lors de la création d'une nouvelle catégorie.

J'ai traduit cela de deux façons :
Variante 1
Pièce jointe 635488
Variante 2
Pièce jointe 635489

Mon approche est-elle correcte ? Quel modèle est le plus représentatif problème ? est-ce que les cardinalités sont bonnes ?

PS : J'ai oublié d'enlever la clé primaire Id de la relation Langue dans mon modèle. Il me semble que les clés primaires n'ont pas à figurer dans un MCD

Vincent

Bonjour Vincent,

Je suis un peu occupé, mais je vais me pencher sur vos états d’âme.

En attendant, vite fait :

Citation:

---

Envoyé par Vincent

J'ai oublié d'enlever la clé primaire Id de la relation Langue dans mon modèle. Il me semble que les clés primaires n'ont pas à figurer dans un MCD

---

Le terme « clé primaire » fait partie du jargon SQL, mais dans le cas du MCD, on doit déclarer un identifiant pour chaque classe d'entités.

Je cite un grand Merisien, Dominique Nanci (RIP) :

« On doit pouvoir faire référence directement à chaque occurrence de l’entité. Pour cela, l’entité-type sera dotée d’un identifiant. »

Donc id ou tout autre attribut de votre choix peut être identifiant, à condition de respecter la contrainte d'unicité : pas de doublons !
N'oubliez pas non plus que vous pouvez définir des identifiants alternatifs.

Lors du passage aux tables SQL, les identifiants deviennent des clés (contrainte Primary key / Unique).


L’ouvrage de Nanci et Espinasse est référencé chez developpez.com :

Ingénierie des systèmes d'information : Merise deuxième génération (4e édition, 2001)

Je penche pour votre variante 2.

Vous pouvez déclarer l’attribut slug comme identifiant de la classe d'entités CategorieNom, mais j’estime qu’il est préférable de conserver la nature associative de cette clase, donc de l’identifier relativement à ses parents, et de l’attribut slug faire un identifiant alternatif pour lui conserver sa propriété d’unicité :

(rubrique slug > Propriétés > Unique)

https://www.fsmwarden.com/loo/aras-vbo(slug).png

Code SQL :

CREATE TABLE CategorieNom
(
   CategorieId INT,
   LangueId INT,
   slug VARCHAR(50) NOT NULL,
   CategorieNom VARCHAR(50),
   CONSTRAINT CategorieNom_PK PRIMARY KEY(CategorieId, LangueId),
   CONSTRAINT CategorieNom_AK UNIQUE(slug),
   CONSTRAINT CategorieNom_Categorie_FK FOREIGN KEY(CategorieId) REFERENCES Categorie(CategorieId),
   CONSTRAINT CategorieNom_Langue_FK FOREIGN KEY(LangueId) REFERENCES Langue(LangueId)
);

Bonjour François,

Merci pour cette réponse. J'en ai profité pour me rafraichir la mémoire sur les identifiants relatifs et je suis tombé sur cette explication limpide de votre part ici-même : https://www.developpez.net/forums/d3...fiant-relatif/

Vous n'auriez pas l'idée d'écrire un livre ? Parce que vos exposés et exemples sont très didactiques :)

Vincent

Ave,

Ecrire un livre ? En attendant j'essaierai de récupérer des choses que j'ai écrites et d'en faire des articles chez DVP... https://www.fsmwarden.com/images/smileys/pc(50pc).png