Conception d'un forum hiérarchique

Version imprimable

29/07/2009, 20h25
muad'dib

Conception d'un forum hiérarchique

Bonjour à tous

Je m'interroge sur la façon de concevoir un forum hiérarchique (à la manière des mailings list où chaque réponse est susceptible de recevoir une réponse et ainsi créer un "nouveau" sujet). Mon interrogation se porte notamment sur la façon de dérouler l'arborescence des messages.

Je pense actuellement à créer une procédure stockée en base de données pour permettre d'aller chercher récursivement les messages et réponses des messages mais je ne suis pas sûr que ce soit la meilleure stratégie. Qu'en pensez-vous et quelle serait votre démarche pour concevoir ce type de forum ?
30/07/2009, 14h51
oxyde356

Table Message :
id | pid | titre | description

id est un identifiant unique pour le message posté, pid (pour parent id) et l'identifiant du message père (celui auquel l'utilisateur répond).
Ce schéma te donne un arbre (hiérarchie) ou les enfants connaissent leur père mais la réciproque n'est pas vrai. Ce n'est pas génant vu qu'un fils ne peut avoir qu'un père et qu'un père peut avoir plusieurs fils.
Quand tu veux cherché si un message à des réponses tu n'as qu'à vérifier si :
A.id == B.pid avec A ton objet père et B n'importe quel objet que tu parcours qui se révèlera fils si l'égalité est vérifiée.

Salut et merci pour la réponse

J'étais également arrivé à une structure de table similaire pour stocker les messages. Partant de là, si je veux savoir combien de réponses à un message par exemple, chaque sous-message y compris, je pense qu'il faut que je fasse une sorte de requête récursive en base de données..du genre, en algorithmie:
Code:

1 2 3 4 5 6 FONCTION ObtenirReponsesAuMessage(IdMessage) SELECT reponses FROM messages WHERE id = IdMessage; TANTQUE reponses->nextResult() FAIRE ObtenirReponsesAuMessage(reponse->nextResult().Id) FINTANTQUE FINFONCTION
Cependant je ne sais pas si l'approche est la meilleure, ce genre de fonction peut prendre beaucoup de temps processeur dans le cas d'un volume important de messages.

Qu'en pensez vous ?

30/07/2009, 16h07
oxyde356

Code:

SELECT reponses FROM messages WHERE id = IdMessage;

Plutôt ça (id => pid) :

Code:

SELECT reponses FROM messages WHERE pid = IdMessage;

Sinon ouai c'est à peut près ça sauf qu'il faut que tu stocke les résultats dans un tableau par exemple.
Il est vrai qu'avec cette approche tu dois à chaque fois reparcourir tous les message ce qui n'est pas très performant (mais tu peux placer un index sur pid pour avoir une recherche beaucoup plus rapide).

Ce que tu peux faire c'est l'inverse. Au lieu que les fils retiennent leur père, ce sont les pères qui vont retenir leurs fils. Ainsi tu n'as pas besoin de parcourir tous les messages. Par contre cette architecture est moins souple, si tu veux déplacer un sujet par exemple avec la première architecture tu n'as qu'à changer le pid du message à déplacer alors qu'avec la deuxième tu es obliger de parcourir un tableau contenant tous les fils, trouver l'élèment à déplacer, copier son ID dans le message cible et supprimer son ID dans le message source. Mais il est vrai que ça doit être bien plus performant comme ça, ça se discute :P
30/07/2009, 16h51
muad'dib

Il me semble que dans tous les cas, que les pères aient une référence vers leur fils ou l'inverse, il faudra parcourir récursivement l'ensemble des messages pour pouvoir reconstruire l'arbre des réponses !!!

L'idée serait de pouvoir récupérer cet arbre depuis n'importe quel message, (premier, dernier, n-ième). La question est comment implémenter une récupération de cet arbre en base de données de manière efficace !

Je vais faire quelques tests avec une procédure stockée récursive et voir ce que ça donne. J'aimerais pouvoir éviter de reconstruire l'arbre depuis la couche modèle et laisser la couche métier s'en occuper car cela amènerait à multiplier les requêtes !
30/07/2009, 17h10
oxyde356

Citation:

Envoyé par muad'dib

Il me semble que dans tous les cas, que les pères aient une référence vers leur fils ou l'inverse, il faudra parcourir récursivement l'ensemble des messages pour pouvoir reconstruire l'arbre des réponses !!!

Oui en effet tu as raison je suis entrein de dev en C++ là et je voyais l'identifiant comme un pointeur :P donc oui dans tous les cas là il faudra parcourir tous les éléments, moi j'ai opté pour l'approche le fils retient son père, c'est simple et souple. Tu cherche à faire quoi à éliminer la récursivité de la recherche ? Si c'est le cas tu devrais y arriver sans problème mais en utilisant la deuxième approche.
30/07/2009, 17h17
muad'dib

En fait j'essaye d'adopter la meilleure approche possible pour ce type de forum ! J'ai déja réalisé des forums chronologiques mais jamais de hiérarchiques. Je pense que la récursivité sera une condition sine qua non pour des raisons de performances. Je travaille avec Postgresql et struts2. Je pense qu'il serait plus performant de faire s'exécuter la requête récurrente de manière interne à postgresql plutôt qu'en externe !

Cela dit j'ai des doutes quant aux résultats que pourra me renvoyer postgre..je pense qu'il serait bon qu'ils se présentent sous forme de collections d'objets, ordonnés au niveau hiérarchique, chacun ayant une référence vers son message parent.

Ceci dit cela ne résoud pas forcément le thème de "et si je veux récupérer le nombre de réponses à un message et tous ses enfants ?" :?

C'est encore assez confus dans ma tête je dois dire la modélisation d'un tel projet !!!

Code:

1
2
3
4
5
6
7
8
FONCTION ObtenirNbReponsesAuMessage(IdMessage)
   VAR nbMessages = 1;
   SELECT reponses FROM messages WHERE id = IdMessage;
   TANTQUE reponses->nextResult() FAIRE
      nbMessages += ObtenirNbReponsesAuMessage(reponse->nextResult().Id)
   FINTANTQUE
   RETOURNER nbMessages;
FINFONCTION

ça ne te convient pas ?

Dans l'absolu oui c'est niquel. Je crois que je me complique un peu la vie dans le fond!!
En fait la réelle problématique est de pouvoir reconstruire l'arbre de la discussion à partir de n'importe quel message (appelons le n), ce qui implique une recherche récursive des tous les messages enfants de n ainsi qu'une "remontée" récursive des messages parents de n. J'entrevois une solution qui serait depuis le message n, remonter jusqu'au message racine et ensuite faire une sélection de tous les messages enfants. A la fonction précédente viendrait donc s'ajouter une fonction, récursive également, qui permettrait de remonter jusqu'au message racine:
Code:

1 2 3 4 5 6 7 FONCTION ObtenirMessageParent(IdMessage) MessageRacine = NULL MessageParent = SELECT messageParent FROM Messages WHERE id = IdMessage SI MessageParent != NULL ALORS MessageRacine = ObtenirMessageParent(MessageParent) FIN SI RETOURNE MessageRacine
Une fois le message racine récupéré on peut alors appliquer la fonction décrite précedemment permettant de récupérer tous les messages et messages enfants! Cela forme un ensemble de résultats que je peux ensuite manipuler dans struts. La solution parait compliquée mais je crois que c'est la bonne logique à appliquer

30/07/2009, 21h32
oxyde356

Oui c'est correcte, par contre je pense qu'au niveau performance c'est bien plus rapide en faisant des boucles itératives qu'une fonction récursive, surtout que là par exemple pour trouver le message père c'est vraiment pas dur de transformer avec des itérations. C'est peut-être plus compliqué à adapter par contre pour obtenir tous les fils.

J'ai réussi à coder assez simplement les fonctions permettant de récupérer la racine des messages, les messages parents d'un message n et les messages enfants d'un message n (langage plpgsql):

Récupérer les messages enfants

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
CREATE OR REPLACE FUNCTION GetEveryChildrenPosts(id varchar) RETURNS SETOF posts AS $$
 
DECLARE 
 
r posts%rowtype;
r2 posts%rowtype;
 
BEGIN
 
FOR r IN SELECT * FROM posts WHERE id_parent_post = $1 LOOP
	for r2 IN SELECT * FROM GetEveryChildrenPosts(r.id_post) LOOP
		RETURN NEXT r2;
	END LOOP;
	RETURN NEXT r;
END LOOP;
 
END;
$$
LANGUAGE plpgsql;

Récupérer les messages parents

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
CREATE OR REPLACE FUNCTION GetEveryParentPosts(id varchar) RETURNS SETOF posts AS $$
 
DECLARE 
r posts%rowtype;
r2 posts%rowtype;
BEGIN
 
 
FOR r IN SELECT * FROM posts WHERE id_post = $1 LOOP
	FOR r2 IN SELECT * FROM GetEveryParentPosts(r.id_parent_post) LOOP
		RETURN NEXT r2;
	END LOOP;
	RETURN NEXT r;
END LOOP;
END;
$$
LANGUAGE plpgsql;

Récupérer le message racine

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
CREATE OR REPLACE FUNCTION GetRootPost(id varchar) RETURNS varchar AS $$
DECLARE 
postRecord RECORD;
 
BEGIN
SELECT * INTO postRecord FROM posts WHERE id_post = $1;
 
IF postRecord.id_parent_post IS NOT NULL THEN
   RETURN getrootpost(postRecord.id_parent_post);
ELSE
   RETURN postRecord.id_post;
END IF;
END;
$$
LANGUAGE plpgsql;

Je pense que je vais continuer dans cette direction, à voir si les performances sont au rendez-vous quand la base de données a beaucoup de données !!!

30/07/2009, 23h01
oxyde356

Oui génère quelques millions de messages et fais des tests n'oublie pas de bien placer tes index ;)
31/07/2009, 09h13
muad'dib

Yes je vais charger la base de données à bloc et tester les performances, si ça s'avère trop lent j'aviserai (bien que je ne vois pas trop comment des itérations depuis la couche modèle pourraient être plus efficaces :? les requêtes effectuées par l'intermédiaire d'un driver (JDBC en l'occurence) doivent prendre plus de temps que si elles sont exécutées par la base de données elle-même).

Pour l'instant j'utilise des clés de type varchar(30), je pense que je vais avant tout switcher vers des clés de type integer. A la base j'avais utilisé ce type de clé pour cacher à l'utilisateur la continuité entre identifiants (id de message 1, 2, 3 ...). Les performances devraient ainsi se voir beaucoup plus améliorées !!

Je rendrai compte de mes tests une fois que j'aurai les résultat :)
31/07/2009, 10h52
oxyde356

Citation:

Envoyé par muad'dib

Yes je vais charger la base de données à bloc et tester les performances, si ça s'avère trop lent j'aviserai (bien que je ne vois pas trop comment des itérations depuis la couche modèle pourraient être plus efficaces :? les requêtes effectuées par l'intermédiaire d'un driver (JDBC en l'occurence) doivent prendre plus de temps que si elles sont exécutées par la base de données elle-même).

Hum je dois t'avouer que je suis pas un pro du plpgsql, je sais même pas ce qu'est la couche modèle par rapport à la base de donnée, la couche modèle c'est celle qui utilise la base de donnée mais ce n'est pas la base quoi ?
Ce que je sais c'est qu'en C++ quand tu fais une fonction récursive, pour chaque appel le programme est obliger de réallouer toutes les variables de la fonction dans la pile, ce qui peut devenir très lourd au bout de quelques récursions. Par contre en itératifs, tu n'alloue qu'une fois la pile et tu as seulement quelques variables temporaires en plus, ce qui n'est vraiment pas comparable.
Le code récursifs est je trouve assez intuitifs pour un développeur un peu expérimenté et pour certains problèmes on pense d'abord à lui, mais si on cherche les performances je pense qu'une fois la fonction récursive trouvé il faut essayer de la passer en itérative. Bon après je ne connais pas les spécificités de plpgsql, il faudrait que tu m'en dise plus dessus et pourquoi tu pense que le récursif sera plus efficace.

Citation:

Envoyé par muad'dib

Pour l'instant j'utilise des clés de type varchar(30), je pense que je vais avant tout switcher vers des clés de type integer. A la base j'avais utilisé ce type de clé pour cacher à l'utilisateur la continuité entre identifiants (id de message 1, 2, 3 ...). Les performances devraient ainsi se voir beaucoup plus améliorées !!

Ah ça c'est sûr, c'est bien plus facile de traiter un nombre qu'un string :P
Mais il faut avouer que pour certaines phases de conception c'est pratique d'avoir des strings mais après quand on "passe en release" autant utiliser le plus performant.

Citation:

Envoyé par muad'dib

Je rendrai compte de mes tests une fois que j'aurai les résultat :)

Ouai et puis fais voir la tête de ta table SQL :P
Par contre je ne sais pas ce qui est le plus performant. Où tu place ID et PID en clé primaire (les 2 à la fois) avec ID qui recommence à 0 pour chaque PID différent puis s'incrémente. Ou tu ne met que ID en clé primaire (en auto-incremente) et PID en index. J'ai toujours choisi la deuxième solution parce qu'elle était plus simple à mettre en oeuvre mais la première me parait plus naturelle enfaite et peut être même plus performante.
31/07/2009, 11h36
muad'dib

En fait quand je parle de couche modèle je suis dans une optique MVC (Modèle / Vue / Composant) où la vue est l'affichage des résultat, le composant l'entité qui stocke les résultats (donc la BDD) et le modèle est l'entité qui fait le lien entre les 2 (dans mon cas le langage Java)

Citation:

Ce que je sais c'est qu'en C++ quand tu fais une fonction récursive, pour chaque appel le programme est obliger de réallouer toutes les variables de la fonction dans la pile

C'est vrai pour tous les langages je pense et ça le sera probablement également pour le plpgsql! Je ne suis pas expert non plus (en fait j'ai commencé hier :lol:) je vais essayer de voir jusqu'à quel niveau de récurrence peut aller le langage. C'est vrai que je ne pense pas pourvoir descendre plusieurs milliers de niveaux (en considérant quelque milliers de réponses à un message, incluant les sous-réponses). Savoir où se trouve la limite me parait essentiel.

Citation:

mais si on cherche les performances je pense qu'une fois la fonction récursive trouvé il faut essayer de la passer en itérative

En fait je trouve l'utilisation de la récurrence plus simple pour mon problème. C'est vrai que la plupart du temps on peut s'en passer mais dans le cas présent je ne vois pas comment je peux passer mes fonctions en itératif ! :question: Dans tous les cas cela résoudrait le problème de la pile.

Citation:

Où tu place ID et PID en clé primaire (les 2 à la fois) avec ID qui recommence à 0 pour chaque PID différent puis s'incrémente.

Je ne peux pas utiliser cette solution car chaque message est susceptible de recevoir une réponse ! Donc chaque message se doit d'avoir un identifiant unique pour pouvoir y être référé. Je choisirai donc également la 2ème solution
31/07/2009, 11h46
oxyde356

Citation:

Envoyé par muad'dib

je vais essayer de voir jusqu'à quel niveau de récurrence peut aller le langage. C'est vrai que je ne pense pas pourvoir descendre plusieurs milliers de niveaux (en considérant quelque milliers de réponses à un message, incluant les sous-réponses). Savoir où se trouve la limite me parait essentiel.

Oui ça ne sert a rien de sortir l'artillerie lourde si tu n'as en moyenne que quelques récursions.

Citation:

Envoyé par muad'dib

En fait je trouve l'utilisation de la récurrence plus simple pour mon problème.

Oui c'est ce que je voulais dire, pour le programmeur c'est plus simple de passer par la récurrence mais au final c'est pas le plus performant.

Citation:

Envoyé par muad'dib

C'est vrai que la plupart du temps on peut s'en passer mais dans le cas présent je ne vois pas comment je peux passer mes fonctions en itératif ! :question: Dans tous les cas cela résoudrait le problème de la pile.

Je suis en vacance ce soir je regarderais ça demain :P

Citation:

Envoyé par muad'dib

Je ne peux pas utiliser cette solution car chaque message est susceptible de recevoir une réponse ! Donc chaque message se doit d'avoir un identifiant unique pour pouvoir y être référé. Je choisirai donc également la 2ème solution

Je ne vois pas où c'est bloquant dans ton cas, si un message a un "sous message" alors le PID du sous message sera l'ID du message et ainsi de suite et l'ID reflétera le nombre de sous messages à un message donné identifiable par le PID de ces sous messages, ainsi ta clé primaire sera toujours unique.
31/07/2009, 11h55
muad'dib

Citation:

Envoyé par oxyde356

Je ne vois pas où c'est bloquant dans ton cas, si un message a un "sous message" alors le PID du sous message sera l'ID du message et ainsi de suite et l'ID reflétera le nombre de sous messages à un message donné identifiable par le PID de ces sous messages, ainsi ta clé primaire sera toujours unique.

Ah exact j'avais pas envisagé cela comme ça!
Mmmm ça se discute je pense ! Pour identifier un message qui serait d'un 5eme sous-niveau on aurait un attribut du genre n-5.n-4.n-3.n-2.n-1.n où n représenterait l'id du post parent ! Je ne comprends probablement toujours pas la subtilité de la chose mais je trouve cela de prime abord difficile à mettre en oeuvre!

Profites bien du soleil !! :D (si tu en as!)
31/07/2009, 12h33
oxyde356

Bon enfaite je dis des bétises, seule la solution 2 est viable :P
Mais il y en a une qui ressemble à la première est qui est correcte mais c'est peut-être qu'elle n'est pas adaptable a ton problème enfaite :lol: