Forum Programmation.autre PostrgreSQL : clôture d'une relation binaire

Posté par  .
Étiquettes :
0
24
juin
2005
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  . Évalué à 3.

    Le principal repository, il est là : http://pgfoundry.org/.(...)

    Bonne chasse !
    • [^] # Re: pgfoundry

      Posté par  . Évalué à 2.

      Merci pour le lien. Je n'y ai pas trouvé ce que je cherchais, mais ça reste une bonne URL à avoir sous le coude.

      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  . Évalué à 1.

        A titre d'informations, tu as combien de noeuds environ ? des centaines, milliers, ... ?

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.