[SQL] La meilleure méthode pour stocker une arborescence ?

Ge_Off · Janvier 28, 2004, 4:03

Bon voilà, ma question est assez particulière… donc pour éviter de foutre tout le monde hors sujet, je pose mon cas concret :

J’ai une FAQ sur un site web à mettre en place, une grosse FAQ…
Dans les specs on me demande de mettre en place une arborescence de thèmes, cad des thèmes pouvant contenir d’autres thèmes (cardinalité merise parent - enfant 0,n), qui eux n’auront donc qu’un seul parent (0,1).

eux mêmes parents d’autres thèmes (cardinalité merise parent - enfant 0,n), un thème enfant pouvant également être présent dans plusieurs thèmes parents… (0,n aussi).

En bref au final je me retrouve avec une structure sous SQL server de cette gueule (la partie manquante étant bien entendu la liaison avec les fiches qui contiendront le texte et autres joyeusetés) :

La contrainte en haut est la contrainte parent - enfant entre ISI_REP_THE_NUM et ISI_REP_THE_NUM_PAR. Le reste est volontairement écarté.

Au final je veux une arborescence “affichée” du type :

Mon objectif côté code (asp, même si ça n’a pas d’importance), c’était de récupérer tous les parents avec leur nombre d’enfants pour constuire un tableau multidimensionnel, et ainsi manipuler facilement les données pour l’affichage.

Maintenant, vu que j’ai maché tout le travail, je me pose la question :
Est-ce la meilleure solution ???

Voici le genre de requête que j’ai construit pour resortir les infos :

SELECT A.ISI_REP_THE_NUM, A.ISI_REP_THE_NUM_PAR, A.ISI_REP_THE_LIB, ( -- Nombre d'enfants SELECT COUNT(*) FROM ISI_REP_THE AS C WHERE C.ISI_REP_THE_NUM_PAR = A.ISI_REP_THE_NUM FROM ISI_REP_THE AS A LEFT OUTER JOIN ISI_REP_THE AS B ON A.ISI_REP_THE_NUM_PAR = B.ISI_REP_THE_NUM ORDER BY A.ISI_REP_THE_NUM_PAR ASC

Si vous avez une meilleure solution, quitte à repartir de zéro, je suis preneur. En tout cas, l'aspect "temps perdu" est sauf, mon truc marche.

(désolé je suis pressé, je reprendrai le post plus tard)

Edit: merdouille dans le bricolage HTML du post… (et fautes)

Ce message a été édité par Ge-Off le 28/01/2004

Phil · Janvier 28, 2004, 5:00

Plusieurs remarques (je vire les LEFT JOIN pour faciliter la lecture)

Ce type de requête est autorisée:
SELECT T1.A,T1.B,T2.Count(T2.a)
FROM T1,
(SELECT a FROM titi) T2

Ce type de requête c’est mal:
SELECT T1.A,T1.B,(SELECT Count(a) FROM titi)
FROM T1

D’autre part tu peux essayer les IN, EXISTS avec jointure de sous-requêtes, les UNION ALL.

Mais le souci c’est que la requête que tu demandes est récursive. Sous Oracle pour cela il y’a CONNECT BY PRIOR, sous DB2 y’a WITH si je me souviens bien, mais sous SQL server, en tout cas pour les vieilles versions, il n’y a pas de récursivité.

J’aime 100 fois mieux le SQL pur aux curseurs SQL. N’empêche que dans ton cas je pense qu’un curseur serait plus simple.

Dernière solution tu peux utiliser une table mère et une table fille plutôt qu’une sele table avec autojointure.

Ce qui est clair c’est qu’en sortie tu as besoin d’un tableau avec des cases vides ou d’une liste fiable indiquant les décalages.

Ce message a été édité par phili_b le 28/01/2004

Ge_Off · Janvier 28, 2004, 5:25

[quote]Ce type de requête c’est mal:
SELECT T1.A,T1.B,(SELECT Count(a) FROM titi)
FROM T1

[…]

D’autre part tu peux essayer les IN, EXISTS avec jointure de sous-requêtes, les UNION ALL.

[…]

Mais le souci c’est que la requête que tu demandes est récursive […] mais sous SQL server, en tout cas pour les vieilles versions, il n’y a pas de récursivité.

[…]

J’aime 100 fois mieux le SQL pur aux curseurs SQL. N’empêche que dans ton cas je pense qu’un curseur serait plus simple.

[…]

Dernière solution tu peux utiliser une table mère et une table fille plutôt qu’une sele table avec autojointure.[/quote]

Je voyais pas comment gauler un count() autrement, vu que le count() est soumis à un filtre (sur la colonne « père »).
C’est la première chose qui m’est venue à l’esprit pour faire ça, jvais y réfléchir.
Pour la récursivité, je me renseigne…
De toutes façons, cette requête partira dans une procédure stockée avec un paramètre supplémentaire facultatif pour ne filtrer que les sous-thèmes d’un thème père précisé. Donc pour les curseurs, je vais voir ce que ça peut donner.
Impossible, l’arborescence pourra comporter un nombre de niveaux infini, donc autant de tables que de niveaux, impossible de gérer ça donc sans limiter le nombre de niveaux.

Merci pour t’être cassé la tête, je vois tout ça demain

AntoineViau · Janvier 28, 2004, 5:35

Bon je sais pas si je vais vraiment aide, j’en doute fortement même, mais j’ai à peu près la même chose à faire actuellement. Seulement, moi je ne suis pas un gros pro du SQL et des DB donc je fais un peu à la trash.

Dans mon cas, ce sont des articles de presses qui sont “catégorisés”. Un article appartient à une ou plusieurs catégories. Chaque catégorie fait partie d’un groupe. Chaque catégorie mène, ou pas, à un ou plusieurs groupes.
La notion de parenté n’est pas flagrante, c’est plus un arbre bordélique qu’autre chose

Un exemple concret : (les groupes sont en gras, les catégories en italique)
Groupe Pays contient les catégories France et Allemagne.
France et Allemagne mènent au même groupe Région qui contient les catégories Nord et Sud qui ne mènent à rien.
Groupe TypeVéhicule contient 4Roues et 2Roues.
4Roues mène au groupe Type4Roues qui contient Voiture et Camion.
2Roues mène au groupe Type2Roues qui contient Moto et Vélo, et mène aussi au groupe TypeMoteur qui contient 4Temps et 2Temps.
Au départ, l’utilisateur dispose des groupes Pays et TypeVéhicule. En choisissant les catégories il déploit l’arbre des groupes et catégories suivantes, et ainsi de suite.

Définition des tables : (les noms sont bidons, je vous rassure)
Maintenant, voilà comment moi j’ai fait :
- table article (ID, auteur)
- table categorie (ID, groupe_proprietaire_id)
- table groupe (ID,titre_groupe)
- table categorie_destination_lien(categorie_id, groupe_id)
- table article_categorie_lien(article_id,categorie_id) (on va dire ACL)
On voit donc que les 2 dernières tables servent à lier les informations. Cela permet surtout d’avoir plusieurs groupes liés à une catégorie (une catégorie peut mener à plusieurs groupes) et plusieurs catégories pour un article.
Pour la requete finale :
SELECT articles.* FROM articles,ACL WHERE ACL.categorie_id=12 AND ACL.article_id=articles.ID;

Je pressens que ma méthode n’est pas la plus optimum étant donné que SQL offre pas mal de possibilités. Toutefois, ça a l’avantage de fonctionner et d’être simple à gérer (enfin je trouve).
Pour finir, ça doit servir à un moteur de recherche basé sur l’arbre des groupes/catégories. Je charge toute la structure de l’arbre en récursif (PHP) avec les groupes de départs pour construire la page de recherche à grand coup de div visibility:hidden et display:none.
Avantage : aucun chargement entre chaque clic. Toute la gestion se fait en JavaScript (récursif aussi) et pour le moment ça fonctionne sur IE PC/Mac, Mozilla PC, Opéra PC, Netscape PC/Mac.
Inconvénient : y a du boulot sur le serveur et faut compacter à mort la définition de l’arbre pour ne pas avoir 50 Ko à charger. Bémol sur la charge serveur : les groupes/catégories ne changeront pas souvent, donc soit je fais du pur statique(génération de la page en PHP et écriture sur disque du fichier HTML) soit je fous toutes les requêtes et leurs résultats dans le cache SQL.

Valaaaaaaa… Si vous avez des avis, je suis preneur. Essayez de pas être trop méchant quand même

Phil · Janvier 28, 2004, 5:41

Très interessant AntoineViau. si si, sans ironie.
Le seul souci c’est que la solution dont tu parles, qui est souvent utilisée, n’est pas applicable aux arbres et à la récursivité. En effet ton modèle de donnée, et les requêtes qui en découlent, sont adaptés à ton problème relativement standard mais pas à ce problème de récursivité.

Ce message a été édité par phili_b le 28/01/2004

Tupperware_ass · Janvier 28, 2004, 6:06

c’est marrant tout ça. il y a une bonne semaine de ça, j’ai proposé la mise en place d’une base de connaissances (car c’est finalement de ça qu’on parle dans le cas de Ge-Off) aux membres d’un forum pour centraliser un peu toutes les infos qui y transitent.

je me suis contenté de présenter les grands principes du système et en promettant de pondre rapidement les tables à utiliser. malheureusement, je n’ai pas pris le temps de de faire tout ça et maintenant, c’est remis à facile le milieu de la semaine prochaine, si c’est pas plus. quel con.

enfin, je ne peux donc pas vous aidez, sorry, mais je suis les débats avec grand intéret…

boudin · Janvier 28, 2004, 6:20

Voici un article génial qui donne LA structure la plus optimisée que je connaisse pour stocker un arbre:
http://www.labo-dotnet.com/labo-dotnet/?ta…ticle&ID=14

Phil · Janvier 28, 2004, 6:21

Ge-Off, à la lumière des notes que j’ai prise sur certains projets, la solution de simuler la récursivité avec une jointure externe plusieurs fois sur un alias de la même table peut être effectivement une des solutions.

TOTO AS T1—>TOTO AS T2–>TOTO AS T3–>TOTO AS T4.

En fait je reprends ton premier exemple mais je rajoutes plusieurs niveaux.
Avec *= cela s’écrit facilement mais avec la norme ANSI LEFT JOIN bon courage pour sortir une syntaxe correcte.

Mais bonjour la maintenabilité. Avant de continuer là dessus il faut bien étudier les curseurs.

Je pensais aussi aux produits cartésiens provoqués (=en virant de façon volontaire des jointures), afin de créer des “cases vides” mais c’est de la bidouille.

Phil · Janvier 28, 2004, 6:23

[quote]Voici un article génial qui donne LA structure la plus optimisée que je connaisse pour stocker un arbre:
http://www.labo-dotnet.com/labo-dotnet/?ta…ticle&ID=14[/quote]Excellent! Et propre en plus !!

edit: hop! En fait cela ressemble à la solution du chapitre 29 du livre “SQL Avancé” de Joe Celko “Modélisation des arbres par ensembles emboîtés”. Je ne connaissais pas cette solution.

Par contre faut voir si l’exploitation des arbres par ensembles emboités n’est pas un chouilla complexe à utiliser…

Ce message a été édité par phili_b le 28/01/2004

AntoineViau · Janvier 28, 2004, 8:55

[quote]Voici un article génial qui donne LA structure la plus optimisée que je connaisse pour stocker un arbre:
http://www.labo-dotnet.com/labo-dotnet/?ta…ticle&ID=14[/quote]oh ben vala un article qu’il est très très bien. Merci pour le lien, ça vaut vraiment le coup.

Ge_Off · Janvier 28, 2004, 9:28

[quote]Voici un article génial qui donne LA structure la plus optimisée que je connaisse pour stocker un arbre:
http://www.labo-dotnet.com/labo-dotnet/?ta…ticle&ID=14[/quote]Excellent en effet, étonnant que j’ai jamais eu l’idée de faire comme ça tellement ça parait logique… logique également d’avoir le réflexe de la relation « parent - enfant », peut-être dû à notre désir de foutre de l’objet partout

Merci encore pour la technique, en plus ça ne semble pas changer beaucoup de choses à ma structure, excepté que j’ai quelques proc stockée à virer

Tupperware_ass> je te PM demain un lien vers la tronche de mon schéma complet, pour te donner quelques idées. Même si la structure se ressemblera sans doute, elle sera toujours spécifique à ton besoin, et à tes limitations techniques.

AntoineViau> impressionnant ton tour d’europe à moto, j’aurai bien aimé faire le même.

Ce message a été édité par Ge-Off le 28/01/2004

GloP · Janvier 28, 2004, 9:35

C’est LE probleme le plus chiant de la DB relationelle… comment stocker proprement une structure d’arbre et c’est loin d’etre trivial ou meme optimise. En general il vaut mieux essayer a mort d’applatir le truc le plus possible (genre dans un forum ca marche par thread, a plat, les forums ou on repond a chaque message individuellement sont pas super courants et limites en nombre de participation parceque ca implique un arbre et niveau ressource ca tue tout (et en plus c’est illisible)).

Enfin la page de boudin est la lumiere il a ete plus rapide que moi Il se leve plus tot, il triche hehe.

boudin · Janvier 28, 2004, 9:40

[quote]Enfin la page de boudin est la lumiere il a ete plus rapide que moi Il se leve plus tot, il triche hehe.[/quote]Hehe! Tu devrais le savoir, l’avenir est à ceux qui ont le véto. © Coluche

Ge_Off · Janvier 28, 2004, 10:22

Je vois le genre, c’est horrible

LoneWolf · Janvier 29, 2004, 9:03

Bon, juste un petit post qui ne fera pas avancer le schmilblick, mais
pour dire 2 ou 3 trucs.

Meme si je trouve impressionant le systeme donne en lien par boudin, je
ne trouve pas que cette technique est logique ou intuitive. J’ai
pas over regarde le truc, mais d’apres ce que j’en ai compris, c’est un
systeme complexe qui demande de nombreuses requetes en insertion et en
suppression, meme si elle est particulierement adapte en lecture.

Pour moi, c’est pas une structure de donnees adapte a un systeme
d’arbre qui fait moins de 4 niveaux. De plus, il y a moyen d’optimiser
la structure de donnees “intuitive” (celle donnee par Ge-Off en premier
post) en rajoutant simplement un champs “nb_enfant” sur chaque noeud.
Cela evite des requetes alambique pour des systemes simples (par
contre, il reste toujours le probleme de la recursion lorsqu’un ajoute
un noeud, il faut remonter les parents et faire +1 a chaque, mais on
parle de moins de 4 niveaux).

Du coup, je rejoins Glop en disant que c’est pas simple, ce genre de
probleme, mais j’ajouterais que la structure propose n’est pas forcement ideale dans
tous les cas (meme si elle en couvre un grand nombre).

LoneWolf

Pas de precipitation

boudin · Janvier 30, 2004, 2:18

Ouais, c’est clair, les intervalles, c’est bien pour de gros arbres bien profonds, et sur lesquels on fait plus de lectures que d’écritures.
Tu as raison aussi de dire que la redondance de données est aussi un bon moyen d’optimiser les choses. En fait, il y a des tas de structures efficaces, et des tas de solutions intermédiaires qui permettent d’optimiser chaque cas.
Sachant simplement que toute redondance d’information vient avec ses contrôles de cohérence et ses batches de remise en état en cas d’incohérence.
On peut par exemple stocker sur chaque noeud les parents et les enfants, mais on peut aussi stocker le chemin complet de chaque noeud dans un format canonisé. Ou tout ça à la fois si nécessaire. Je l’ait fait moult fois, ça pulse bien aussi.
Et pis comme souvent, savoir faire des index judicieux dans sa base, ça peut aider aussi…

GloP · Janvier 30, 2004, 5:10

Oui pour les petits arbres le chemin canonise ca marche nikel et les requetes sont plutot faciles a ecrire du coup. Niveau perfs c’est pas super mega dechirant mais c’est souvent suffisant. Genre pour la table des links de cafzone (et leur classement par categorie arborescente) je vais surement faire ca comme ca…

Ce message a été édité par GloP le 30/01/2004

Ge_Off · Janvier 30, 2004, 11:01

[quote]On peut par exemple stocker sur chaque noeud les parents et les enfants, mais on peut aussi stocker le chemin complet de chaque noeud dans un format canonisé. Ou tout ça à la fois si nécessaire. Je l’ait fait moult fois, ça pulse bien aussi.
Et pis comme souvent, savoir faire des index judicieux dans sa base, ça peut aider aussi…[/quote]J’avoue ne pas trop saisir ce que tu dis boudin, ou même Glop (pour changer :P)…
J’ai eu la malchance de m’être autoformé sur les différents SGBDR et personne ne m’a jamais rien appris sur le côté « théorique » des choses (ou alors très peu…)

Je manque cruellement de vocabulaire… où est le glossaire ?
Qu’est-ce que vous entendez par « format canonisé » ?
Une sorte de XPath appliqué à une colonne directement dans la table du contenu en clair ?

Je manque aussi cruellement de technique sur le placement des indexs. Ca se placerait plus judicieusement sur les clés étrangères par exemple ?

Merci encore pour vos réponses, sincèrement.
J’ai fait mes procédures stockées après avoir refait mon schéma :
quasi aucune différence côté client, sauf pour le script de génération de l’arbre évidemment. Tout fonctionne top moumoute

mccricri · Janvier 30, 2004, 12:16

[quote]Voici un article génial qui donne LA structure la plus optimisée que je connaisse pour stocker un arbre:
http://www.labo-dotnet.com/labo-dotnet/?ta…ticle&ID=14[/quote]

un autre qui y ressemble étrangement : SQL Pro

le site étant plutôt bien complet pour tout ce qui touche à SQL, il pourra certainement en intéresser plusieurs ici
Ce message a été édité par mccricri le 30/01/2004

AntoineViau · Janvier 30, 2004, 1:38

Je profite de ce thread pour m’adresser aux pros de la gestion de serveur SQL. Plus précisément MySQL. Le site sur lequel je travaille va réunir environ 10000 articles de presses. Chaque article a une quantité d’information très limitée puisqu’il ne devrait y avoir que le titre des articles, ses auteurs et le numéro du magazine auquel il appartient. En gros on peut considérer moins de 512 octets par article.
Le système de groupes/catégories que j’ai exposé plus haut fonctionne sur un système de “table de liens” et ne prend pas énormément de place non plus (moins de 128 octets par lien).
Mon idée est de faire jouer le cache de MySQL à fond notamment avec query_cache_type = 1 (cache all results except SELECT SQL_NO_CACHE … queries).

Ca vous parait valable comme façon de faire ?

Sinon, je réfléchis au système intervallaire. Actuellement mon schéma autorise plusieurs parents pour un enfant (genre les catégories France et Allemagne du groupe Pays mènent toutes les deux au groupe Zone qui contient Nord et Sud). Faut que je vois si c’est réellement utile et si, finalement, le peu de redondances éventuelle rend mon schéma caduque.
Je préfère tout refaire maintenant because c’est un site qui risque de marcher très fort (marché de niche, mais très actif) et il y aura beaucoup (voire énormément) d’utilisation du moteur de recherche.

Antoine