Je voudrais représenter dans une base Postgre des données possédant une relation d'ordre partielle (un graphe orienté sans cycle quoi... un peu comme les classes dans les langages à héritage multiple par exemple).
Les deux requêtes auxquels je veux pouvoir répondre rapidement (donc sans procédure récursive) sont "quel est l'ensemble des éléments plus grands que X" (ou "père de X" si le graphe vous parle plus) et "quel est l'ensemble des éléments plus petits que Y" ("fils de Y"). Par contre, les insertions/suppression/maj peuvent elles être coûteuses, parce qu'il y en aura pas souvent.
Mon idée est donc de déclarer les relations directes entre les éléments dans une première table, et d'en maintenir une autre qui en serait la clôture via des triggers et procédures stockées.
Si c'est pas clair, un exemple :
1) état initial
relations directes : {(A,B), (B,C)}
cloture : {(A,B), (A,C), (B,C)}
(A,C) est dans la cloture parcequ'on a A-->B-->C
2) ajout de (A,D)
relations directes : {(A,B), (B,C), (A,D)}
cloture : {(A,B), (A,C), (B,C), (A,D)}
3) ajout de (D,C)
relations directes : {(A,B), (B,C), (A,D), (D,C)}
cloture : {(A,B), (A,C), (B,C), (A,D), (D,C)}
4) suppression de (A,B)
relations directes : {(B,C), (A,D), (D,C)}
cloture : {(A,C), (B,C), (A,D), (D,C)}
(A,C) reste dans la cloture, parcequ'on a encore A-->D-->C.
5) suppression de (D,C)
relations directes : {(B,C), (A,D)}
cloture : {(B,C), (A,D)}
Cette fois (A,C) est supprimé de la clôture parce que plus rien ne lie A et C.
Bon, pouf pouf, en y réfléchissant un peu, ça fait quand même pas mal de code à faire je trouve pour un problème qui doit pourtant être vachement classique. Donc voilà, j'en arrive à ma question : est-ce qu'il existe des repository de code postgresql libre sur lesquels on est susceptible de trouver ce genre de choses prêtes au copier/coller/adapter ? Et puis plus généralement, pour ceux qui se seraient déjà retrouvés confrontés à un problème similaire, est-ce que vous avez des conseils ou mises en gardes à formuler, ou d'autres approches à suggérer ?
Merci d'avance.
# pgfoundry
Posté par mac . Évalué à 3.
Bonne chasse !
[^] # Re: pgfoundry
Posté par tgl . Évalué à 2.
Bon sinon, des fois qu'il y aurait des gens que ça intéresse, j'ai trouvé cette page de bookmarks qui est intérressante :
http://troels.arvin.dk/db/rdbms/links/(...)
Y'a entre autres pas mal de bonnes choses autour de la représentation des arbres, un autre classique je pense.
Et il y avait cet article sur les clôture de graphes :
http://citeseer.ist.psu.edu/dong99maintaining.html(...)
Pas vraiment du code que je je pourrai direct copier/coller, mais bon ça ressemble vraiment à ce que je suis en train d'écrire, donc c'est plutôt rassurant.
[^] # Re: pgfoundry
Posté par mac . Évalué à 1.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.