Discussion :

[laffreuxthomas]

Je recommande la lecture de cet exposé (en anglais), c'est concret, rapide à parcourir, instructif. On y retrouve plusieurs des techniques détaillées en français par sqlpro.

Les diapositives 39 à 69 exposent quatre manières de représenter un arbre en base :

1. L'adjacence : une clé trangère vers l'élément parent.
2. L'énumération de chemins : on stocke les ID dans une colonne textuelle.
3. La "numérotation des bornes" : on stocke des bornes "droite" et "gauche". (Voir aussi le cours de sqlpro).
4. La table des combinaisons ascendants-descendants : une table contenant deux clés étrangères et stockant toutes les combinaisons entre les éléments.

La première méthode est la plus classique, elle est aussi je pense la méthode la plus robuste. Son inconvénient : la syntaxe SQL 99 (WITH RECURSIVE) et les unions sont nécessaires pour récupérer en une requête les descendants et les ascendants. Donc impossible sur les SGBD qui n'implémentent pas cette syntaxe : MySQL notamment.

J'ajoute une variation de la première méthode : plutôt que d'avoir une seule table s'auto-référençant, ce qui oblige à des colonnes nullable donc dénormalisée, utiliser de l'héritage :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
CREATE TABLE element (
	element_id integer NOT NULL PRIMARY KEY,
	les-colonnes-communes-à-tous-les-éléments varchar(255) NOT NULL
);
 
CREATE TABLE child_element (
	element_id integer NOT NULL PRIMARY KEY REFERENCES element(element_id),
	parent_element_id integer NOT NULL REFERENCES element(element_id),
	les-colonnes-des-descendants NOT NULL
);

Ou même avec une troisième table :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
CREATE TABLE root_element (
	element_id integer NOT NULL PRIMARY KEY REFERENCES element(element_id),
	les-colonnes-des-racines NOT NULL
);

Qu'en pensez-vous ? Quelle méthode préconisez-vous ?

[CinePhil]

Pas le temps de lire l'article maintenant mais de ce que je comprends de la solution 2, elle peut partir à la poubelle car ne respectant pas la première forme normale !

Je ne comprends pas bien le sens de la 4.

Je regarderai tout ça plus tard.

[fsmrel]

Prenons le « dossier de conception » proposé par Cézigue :



De mon côté, et CinePhil n’y verra pas d’inconvénient — au contraire —, je commence par représenter un MCD (ou un diagramme de classes) en conséquence, même si c’est avec PAINT...



Pardon CinePhil, je n’ai pas utilisé de verbe pour la nomenclature...

Ceci fait, on passe au MLD :



Ensuite, on peut passer au DDL :

Code SQL :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Create Table PERSONNE (
   PersonneId           CHAR(8)              Not null,
   PersonneNom          Varchar(48)          Not null,
   Constraint PERSONNE_PK Primary Key (PersonneId)
) ;
 
Create Table MESSAGE (
   MessId               Int                  Not null,
   PersonneId           CHAR(8)              Not null,
   Messlibelle          Varchar(48)          Not null,
   Constraint MESSAGE_PK Primary Key  (MessId),
   Constraint MESSAGE_PERSONNE_1 Foreign Key (PersonneId) REFERENCES PERSONNE
) ;
 
Create Table NOMENCLATURE (
   MessId               Int                  Not null,
   MessCommentantId     Int                  Not null,
   Constraint NOMENCLATURE_PK Primary Key  (MessId, MessCommentantId),
   Constraint NOMENCLATURE_MESSAGE_1 Foreign Key (MessId) REFERENCES MESSAGE,
   Constraint NOMENCLATURE_MESSAGE_2 Foreign Key (MessCommentantId) REFERENCES MESSAGE
) ;

On crée un jeu d’essai :

Code SQL :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
INSERT INTO PERSONNE (PersonneId, PersonneNom) VALUES ('fran', 'François') ; 
INSERT INTO PERSONNE (PersonneId, PersonneNom) VALUES ('ollie', 'Ollivier') ; 
INSERT INTO PERSONNE (PersonneId, PersonneNom) VALUES ('kukla', 'Kuklatoff') ; 
 
SELECT '' as 'PERSONNE',  * FROM PERSONNE
 
INSERT INTO MESSAGE (MessId, PersonneId, MessLibelle) VALUES (1, 'fran', 'C’est quoi cet insecte ?') ; 
INSERT INTO MESSAGE (MessId, PersonneId, MessLibelle) VALUES (2, 'ollie', 'Probablement un pointeur nase.') ; 
INSERT INTO MESSAGE (MessId, PersonneId, MessLibelle) VALUES (3, 'fran', 'Non, j’ai déjà vérifié ça.') ; 
INSERT INTO MESSAGE (MessId, PersonneId, MessLibelle) VALUES (4, 'kukla', 'Vérifions la validité des entrées.') ;
INSERT INTO MESSAGE (MessId, PersonneId, MessLibelle) VALUES (5, 'ollie', 'Effectivement, ça coince.') ;
INSERT INTO MESSAGE (MessId, PersonneId, MessLibelle) VALUES (6, 'fran', 'D’accord, ajoutez un contrôle.') ;
INSERT INTO MESSAGE (MessId, PersonneId, MessLibelle) VALUES (7, 'kukla', 'Le problème est résolu.') ;
 
SELECT '' as 'MESSAGE',  * FROM MESSAGE
 
INSERT INTO NOMENCLATURE (MessId, MessCommentantId) VALUES (1, 2) ; 
INSERT INTO NOMENCLATURE (MessId, MessCommentantId) VALUES (2, 3) ; 
INSERT INTO NOMENCLATURE (MessId, MessCommentantId) VALUES (1, 4) ; 
INSERT INTO NOMENCLATURE (MessId, MessCommentantId) VALUES (4, 5) ; 
INSERT INTO NOMENCLATURE (MessId, MessCommentantId) VALUES (4, 6) ; 
INSERT INTO NOMENCLATURE (MessId, MessCommentantId) VALUES (6, 7) ; 
 
SELECT '' as 'NOMENCLATURE',  * FROM NOMENCLATURE
ORDER BY MessCommentantId ;

Au niveau du DML, pour obtenir l’arbre des descendants d’un message donné :

Code SQL :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
WITH Recurs (MessCommentantId, MessId) AS
(
  SELECT MessCommentantId, MessId 
  FROM   NOMENCLATURE 
  WHERE  MessId = 4        -- exemple de point de départ    
    AND  MessId <> MessCommentantId
  UNION ALL
 (SELECT n.MessCommentantId, n.MessId
  FROM   NOMENCLATURE AS n JOIN Recurs AS r ON n.MessId = r.MessCommentantId  
  WHERE n.MessCommentantId <> n.MessId)
 ) 
-- Au résultat 
SELECT MessId, MessCommentantId 
FROM   Recurs
order by MessCommentantId ;

On peut aussi mettre en oeuvre une vue intégrant la requête ci-dessus :

Code SQL :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
CREATE VIEW VUE_RECURSIVE 
AS 
WITH Recurs (MessCommentantId, MessId) AS
(
  SELECT MessCommentantId, MessId 
  FROM   NOMENCLATURE 
  WHERE  MessId = 4  -- ou récupérer cette valeur  
    AND  MessId <> MessCommentantId
  UNION ALL
 (SELECT n.MessCommentantId, n.MessId
  FROM   NOMENCLATURE AS n JOIN Recurs AS r ON n.MessId = r.MessCommentantId  
  WHERE n.MessCommentantId <> n.MessId)
 ) 
-- Au résultat 
SELECT MessId, MessCommentantId 
FROM   Recurs ;

Et partant de là, on effectue les jointures qui vont bien pour afficher les libelles des messages et leurs auteurs.

Maintenant, avec MySQL je ne sais pas traiter de la récursivité au niveau du DML, désolé, mais après tout on est dans le forum Schéma...

[laffreuxthomas]

Maintenant, avec MySQL je ne sais pas traiter de la récursivité au niveau du DML, désolé, mais après tout on est dans le forum Schéma...

Voilà. Je n'ai peut-être pas été clair : si l'on dispose de la syntaxe récursive de SQL 99, la méthode de l'adjacence est la meilleure. Elle est la seule qui n'implique aucune redondance. Ce sujet est donc facile à trancher, et même sans grand intérêt…

… sauf si l'on doit faire avec MySQL. Comment, en une seule requête en syntaxe SQL 92, récupérer l'ensemble des descendants ou des ascendants d'un élément (ou message) donné ? Les méthodes 2, 3 et 4 le permettent au prix à chaque fois d'une redondance des informations.

[laffreuxthomas]

Pas le temps de lire l'article maintenant mais de ce que je comprends de la solution 2, elle peut partir à la poubelle car ne respectant pas la première forme normale !

Les solutions 2, 3 et 4 ne sont pas "normalisables". Elles ne sont pas à mettre à la poubelle, du moins pas sur les SGBD où la première solution est insuffisante.

[CinePhil]

Puisque MySQL ne connaît pas les requêtes récursives, il faut utiliser une procédure stockée pour obtenir le résultat.

Mais comme nous sommes dans le forum schéma, je maintiens que la solution 2 est bonne pour la poubelle !

[Richard_35]

Bonjour à tous,

Intéressant travail de M. Karwin, merci de le diffuser, laffreuxthomas, .

.../... la solution 2 est bonne pour la poubelle !

==> . En effet, concaténer des Id dans un champ texte est une bidouille "maxi-casse-gueule" , à terme, dans une application. Le terme "casse-gueule" pourrait être "légèrement" tempéré par l'utilisation de champs multi-valués... "légèrement", car, de mon point de vue, l'utilisation de champs multi-valués est "mini-casse-gueule" .

De mon point de vue, la solution "1-Adjacency list Design-L'adjacence", version Fsmrel, est la meilleure : l'entité Nomenclature permettant d'éviter le stockage d'une clé étrangère à NULL pour le comment_id=1 :

Externaliser le couple {comment_id, parent_id}.

[laffreuxthomas]

Puisque MySQL ne connaît pas les requêtes récursives, il faut utiliser une procédure stockée pour obtenir le résultat

Une procédure stockée demandera je crois une table temporaire alimentée par l'exécution d'une requête dans une boucle. Au niveau optimisation je ne pense pas que cela puisse fournir de bons résultats.

==> . En effet, concaténer des Id dans un champ texte est une bidouille "maxi-casse-gueule" , à terme, dans une application.

Je trouve pour ma part la solution intéressante : certes c'est une bidouille, certes c'est une redondance, mais elle ne nécessite qu'une petite colonne et de surcroit facile à mettre à jour. J'envisage de l'utiliser en supplément de la première solution.

Le terme "casse-gueule" pourrait être "légèrement" tempéré par l'utilisation de champs multi-valués... "légèrement", car, de mon point de vue, l'utilisation de champs multi-valués est "mini-casse-gueule" .

Qu'est-ce qu'un "champ multi-valué" ?

Je reviens sur la solution donnée par fsmrel. Elle permet inutilement (par rapport au cas discuté ici) de faire des réseaux complexes. On peut la modifier en utilisant "MessId" comme clé primaire :

Code SQL :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Create Table NOMENCLATURE (
   MessId               Int                  Not null,
   MessCommentantId     Int                  Not null,
   Constraint NOMENCLATURE_PK Primary Key  (MessId),
   Constraint NOMENCLATURE_MESSAGE_1 Foreign Key (MessId) REFERENCES MESSAGE,
   Constraint NOMENCLATURE_MESSAGE_2 Foreign Key (MessCommentantId) REFERENCES MESSAGE
) ;

Et ensuite, on ajoute la redondance spéciale pour MySQL :

Code SQL :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
Create Table MESSAGE (
   MessId               Int                  Not null,
   PersonneId           CHAR(8)              Not null,
   Messlibelle          Varchar(48)          Not null,
   Path                 varchar(255),
   Constraint MESSAGE_PK Primary Key  (MessId),
   Constraint MESSAGE_PERSONNE_1 Foreign Key (PersonneId) REFERENCES PERSONNE
) ;

… nullable bien sûr, tant qu'à faire d'être dénormalisé, autant se laisser une facilité d'implémentation de la redondance. :p

[Richard_35]

==> En effet, concaténer des Id dans un champ texte est une bidouille "maxi-casse-gueule" , à terme, dans une application.

Je trouve pour ma part la solution intéressante : certes c'est une bidouille, certes c'est une redondance, mais elle ne nécessite qu'une petite colonne et de surcroit facile à mettre à jour. J'envisage de l'utiliser en supplément de la première solution.

==> une facilité à la création, OK. Pour la maintenance et l'exploitation, ce sera une autre paire de manches... mais bon, c'est toi qui vois.

Qu'est-ce qu'un "champ multi-valué" ?

==> il s'agit d'un champ de type "enum" : affectation d'une liste de valeur "en dur" à la création du champ. Une recherche sur Google, selon ta base de données, te donnera toutes les précisions. Mais, cette solution ne s'applique pas à ce cas, c'était juste pour "tempérer" le "maxi-casse-gueule".

[fsmrel]

Une procédure stockée demandera je crois une table temporaire alimenté par l'exécution d'une requête dans une boucle. Au niveau optimisation je ne pense pas que cela puisse fournir de bons résultats.

On ne dit pas : « je ne crois pas », mais on prouve par A+B. Sinon, comme dit Ludwig Wittgenstein dans l’avant-propos de son Tractatus logico-philosophicus :

Tout ce qui proprement peut être dit peut être dit clairement, et sur ce dont on ne peut parler, il faut garder le silence.

certes c'est une bidouille, certes c'est une redondance

Dans le forum Schéma, on ne bidouille pas, on modélise : on attend toujours votre MCD.

Je reviens sur la solution donnée par fsmrel. Elle permet inutilement (par rapport au cas discuté ici) de faire des réseaux complexes.

Merci pour l’adverbe, votre "délicatesse" me touche. Je vous ai proposé le modèle le plus classique et le plus simple qui soit, que l’on trouve dans tous les ouvrages sérieux (Merise, UML, Relationnel) traitant des nomenclatures et qui respecte le principe important de symétrie. Le MCD que j'ai fourni est suffisant pour traiter du cas « Cézigue ».

Si vous vouliez en réduire les possibilités, mettre en œuvre une hiérarchie stricte, il suffirait de remplacer la cardinalité 0,N par une cardinalité 0,1 sur la patte « référençant ».

[laffreuxthomas]

==> une facilité à la création, OK. Pour la maintenance et l'exploitation, ce sera une autre paire de manches... mais bon, c'est toi qui vois.

Par rapport aux solutions 3 et 4, il me semble qu'elle est à la fois facile à maintenir à jour et pas trop coûteuse en volume de données.
J'ai en revanche un gros doute côté performance : une recherche en LIKE…

==> il s'agit d'un champ de type "enum" : affectation d'une liste de valeur "en dur" à la création du champ. Une recherche sur Google, selon ta base de données, te donnera toutes les précisions. Mais, cette solution ne s'applique pas à ce cas, c'était juste pour "tempérer" le "maxi-casse-gueule".

Ah OK, j'ignorais le nom de cette chose. Jusqu'ici j'ai également toujours évité cette fonctionnalité. Et effectivement elle ne s'applique pas ici.

Je vous ai proposé le modèle le plus classique et le plus simple qui soit, que l’on trouve dans tous les ouvrages sérieux (Merise, UML, Relationnel) traitant des nomenclatures et qui respecte le principe important de symétrie. Le MCD que j'ai fourni est suffisant pour traiter du cas « Cézigue ».

D'accord.
Inutile de se fâcher.

[Richard_35]

Bonjour Laffreuxthomas,

==> une facilité à la création, OK. Pour la maintenance et l'exploitation, ce sera une autre paire de manches... mais bon, c'est toi qui vois.

Par rapport aux solutions 3 et 4, il me semble qu'elle est à la fois facile à maintenir à jour et pas trop coûteuse en volume de données.
J'ai en revanche un gros doute côté performance : une recherche en LIKE…

==> le bémol dont tu parles concerne "l'exploitation" de la base de données. Et, sans doute, y aura-t-il d'autres conséquences... il est difficile d'établir une liste exhaustive des conséquences futures d'une telle solution !... En l’occurrence, c'est vrai que le LIKE "*xxx*" peut "mettre à genou" une base de données.

En fonction de l'expérience de chacun, les "je le sens mal" sont précieux, me semble-t-il... mais bon, comme dit précédemment, c'est toi qui vois, en final.

[laffreuxthomas]

En l’occurrence, c'est vrai que le LIKE "*xxx*" peut "mettre à genou" une base de données.

Cette discussion m'a permis d'y voir plus clair alors merci à tous les participants. Et puis je suis sincèrement désolé pour ceux qui ont été importunés.

Au final je garde la solution 1 améliorée (normalisée) et j'élimine l'option du chemin qui ne tiendra surement pas la charge sur de très gros volumes de données.

L'application que je réalise doit pouvoir tourner sur SQLite, MySQL et PostGreSQL. J'implémenterai la récursion au niveau applicatif pour les deux premiers, et via la syntaxe SQL 99 pour PostGreSQL. Ça devrait aller car ce que je mets en place n'est pas un produit fini mais une API. Je recommanderai simplement aux développeurs des projets SQLite et MySQL d'éviter cette partie de l'API sur trop de niveaux de hiérarchie.

[Fred_34]

J'ai en revanche un gros doute côté performance : une recherche en LIKE…

Il me semble que les recherches sont exclusivement des like "xxx*" et non des like "*xxx*".

[Richard_35]

Bonjour Fred_34,

J'ai en revanche un gros doute côté performance : une recherche en LIKE…

Il me semble que les recherches sont exclusivement des like "xxx*" et non des like "*xxx*".

==> nous parlions, là, de la méthode 2, à savoir :

pour retrouver quel le parent du 4 ainsi que ses enfants, il faut un LIKE "*4*".

[Fred_34]

Bonjour Richard,

Pour retrouver quel est le parent du 4 ainsi que ses enfants, ont peut surement faire quelque chose du genre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
path="1/" 
UNION 
path LIKE "1/4/+"

[Richard_35]

Je ne connais pas cette syntaxe et je ne sais pas si elle sera acceptée par tous les SGBD.

D'autre part, si j'ai bien compris, avec path="1/" et path LIKE "1/4/+" ne pars-tu pas du postulat que 1 est, forcément, le père de 4 ?

[Fred_34]

D'autre part, si j'ai bien compris, avec path="1/" et path LIKE "1/4/+" ne pars-tu pas du postulat que 1 est, forcément, le père de 4 ?

Non, si tu connais 4, tu peux facilement retrouver "1/" et "1/4/" :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
SELECT * FROM the_Table WHERE path =(SELECT replace(path, '/4/', '/') FROM the_Table WHERE commentId=4)
UNION 
SELECT * FROM the_Table WHERE path LIKE(SELECT concat(path, '_%') FROM the_Table WHERE commentId=4);

[laffreuxthomas]

La réponse est donnée sur le slide 48. Lorsqu'on veut sélectionner le parent du 4, on récupère d'abord le contenu de la colonne "path" pour l'identifiant 4, puis on construit les requêtes avec :

• Easy to query ancestors of comment #7:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
SELECT * FROM Comments
WHERE ‘1/4/6/7/’ LIKE path || ‘%’;

• Easy to query descendants of comment #4:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
SELECT * FROM Comments
WHERE path LIKE ‘1/4/%’;

Donc c'est une recherche en LIKE 'xxx%'.

C'est une solution qui a l'avantage d'être facile et qui marche je pense très bien sur des petits volumes de données. Mais, sur de petits volumes de données, la requête exécutée en boucle devrait également donner des résultats décents, du moins tant que le nombre de niveaux est réduit.

[Richard_35]

Bonjour Laffreuxthomas,

Il y a vraiment quelque chose qui m'échappe :

• Easy to query ancestors of comment #7:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
SELECT * FROM Comments
WHERE ‘1/4/6/7/’ LIKE path || ‘%’;

==> ‘1/4/6/ est mis "en dur", alors que nous ne savons pas, a priori, que le début de l'arborescence est celui-ci : il s'agit, uniquement, du début de l'arborescence de l'exemple présenté. En clair, nous ne connaissons pas, a priori, la position du 7 dans l'arborescence.

Si tu pouvais (ou une autre bonne âme) éclairer la chose, cela m'arrangerait .