Algo de recursion sur une table ?

Version imprimable

28/06/2006, 12h36
lennelei

Algo de recursion sur une table ?
Bonjour,

pour illustrer mon problème, supposons que j'ai une structure où je stocke des informations concernant des programmes et des projet. Pour chaque programme, j'ai la liste des projets dans lesquels il est utilisé.
Bon, l'exemple est bidon, mais je l'espère assez claire...

bref, au final, j'ai une structure de type:
Code:

1 2 3 4 5 6 7 8 9 PROG. | PROJET ------+------- PG0 | P0 PG1 | P1 PG2 | P1 PG2 | P2 PG3 | P2 PG3 | P3 PG4 | P3
On voit bien ici que les programme PG1 est utilisé dans le projet P1 avec le programme PG2. Celui-ci est de son coté utilisé en plus dans le projet P2... etc.

J'en viens donc au but de mon algo: j'ai un super virus qui se propage dans les programmes d'un même projet... je veux donc pouvoir identifier, à partir d'une liste de programmes infectés quels sont les programmes qui vont être touchés.

Par exemple, si je suppose que le programme PG4 est infecté, il va contaminer PG3 qui est dans le même projet P3, mais PG3 étant dans P2, PG2 va être aussi contaminer etc jusqu'à PG1. Bref, seul PG0 s'en sors.
Mon but est donc de trouver la liste des programmes infectés (PG1, 2, 3 et 4) à partir de PG4.

Ca parait con comme ça (et ça l'est peut-être), mais j'ai du mal à trouver une méthode efficace pour traiter ça... pour info, l'algo doit tourner sous cobol et ma strucutre est en DB2 . Je ne peux pas utiliser de requête récursive en DB2 :/
Mon problème est d'arriver (dans des temps de traitement raisonnable) à identifier simplement les programmes/projets par lesquels je suis déjà passé.

Je ne sais pas si c'est suffisement clair ;) mais merci d'avance pour d'éventuelles réponses...
28/06/2006, 22h09
Jedai

Ca revient à déterminer la composante connexe d'un noeud dans un graphe où les noeuds sont les projets et les programmes et où il y a une arête entre le programme et les projets dont il fait partie. Crée ton graphe et fais un parcours classique à partir du noeud infecté et tu auras un programme efficace.

--
Jedaï
29/06/2006, 14h02
lennelei

Merci pour cette réponse qui est pour le moins précise techniquement ;)

j'aurais toutefois une question: je bute sur le parcours justement... en fait, partant de PG4, je retrouve bien mon projet P3, puis le programme PG3. Cela me porte ensuite vers P2, or, si je suppose avoir une ligne supplémentaire PG4 | P2 (relation entre le programme 4 et le projet 2), je risque de boucler indéfiniment. Or, compte tenu de la volumétrie qui risque d'être importante, y'a-t-il un moyen d'éviter d'avoir à reparcourir une liste dans laquelle je mémorise tous les points par lesquels je suis déjà passé ?

Merci d'avance.
30/06/2006, 13h07
Mihaela

Il suffit de marquer comme vu 0/1 les noeuds parcourus.
02/07/2006, 08h32
Christianchristian

Bonjour,

Je te propose, à titre de réflexion, cette ébauche de solution technique.

Pour ce qui suit, j’ai présumé que :
- Tu es maître d'oeuvre sur le traitement et sur la table DB2.
- La clé primaire est constituée, au moins dans sa partie générique, des colonnes : PGM+Projet.........
- C'est un traitement BATCH.
- Que la volumétrie de la table DB2, exprimée en nombre de lignes, est dans les limites du « raisonnable ».

Je ne vois pas d'autres solutions que de créer un index (clé) secondaire sur les colonnes : PROJET+Pgm OU
Un fichier de travail : une table DB2 (ou un cluster VSAM KSDS) temporaire créé dans un STEP (JCL) précédent le traitement en question. Puis détruit en fin d’exploitation des traitements. (CREATE/DROP OU DEFINE/DELETE). Cette seconde proposition semble préférable, elle évite un index secondaire sur la table. Le passage par une structure secondaire permet de disposer de la liste des programmes pour un projet.

FICHIERS :

Clé primaire supposée colonnes : PGM/Projet.
PROG. | PROJET (tous les projets se rapportant à un pgm)
------+-------
PG0....| P0
PG1....| P1
PG2....| P1
PG2....| P2
PG3....| P2
PG3....| P3
PG4....| P3

structure secondaire organisée sur colonnes : PROJET/Pgm
PROJET | PROG. (tous les pgm se rapportant à un projet)
--------+------
P0........| PG0
P1........| PG1
P1........| PG2
P2........| PG2
P2........| PG3
P3........| PG3
P3........| PG4

PGMs CONTAMINES : Liste Supposé trié en ordre ascendant sur: nom PGM
......
......PG4
......

Scénario :

A) RECHERCHE ET PRESERVATION DES (NOMS DE) PGx CONCERNES

RAZ table TAB_COBOL_P.

====>.1)Itération 1jusqu'à fin de liste : Lecture des noms de programmes contaminés. Pour chacun d'eux :
Lecture : ......PG4 SI épuisement de la liste noms des pgm contaminés exploitation de la table TAB_COBOL_P (édition ?)

2)) Accès par la clé primaire générique à la 1ere ligne d'un groupe de (1 ou plusieurs) lignes(s) de la table DB2. ( clé générique : nom de PGM uniquement => avec l'opérateur "> ou = " nom de PGm de la liste" ).
PG3....| P3
PG4....| P3.<==== lu

3) Sauvegarder les identifiants PGM contaminé/PROJETS ( dans une première table TAB_COBOL_P de référence).
STRUCTURE: *nom_pgmcontaminé|nom_pgm-nom_projet|nom_pgm-nom_projet|nom_.... n fois

Cas 1er fois PGx contaminé (1er passage)
TAB_COBOL_P = |*PG4-P3| traitement de P3

===>...Itération 2
RAZ table TAB_COBOL_S. (voir 5))
_____________________________________________
Au 2em.passage PG4 :
TAB_COBOL_P = |*PG4-P3|PG3-P2| traitement de PG3-P2

Au 3em. passage PG4 :
TAB_COBOL_P = |*PG4-P3|PG3-P2|PG2-P1| traitement de PG2-P1

Au 4em. passage PG4 :
TAB_COBOL_P = |*PG4-P3|PG3-P2|PG2-P1|PG1-P1| traitement de PG1-P1
Pour chacun des NOUVEAUX postes de la table TAB_COBOL_P.

4) Jusqu'à fin du groupe (ex : groupe : 2 projets P3),Accés par la "clé secondaire" générique (nom de PROJET uniquement

Au 1er passage PG4 :
P2........| PG3
P3........| PG3.<=====
P3........| PG4.<= = =
______________________________________________
Au 2em. passage PG4 :
P2........| PG2.<=====
P2........| PG3.<= = =
P3........| PG3

Au 3em. passage PG4 :
P0........| PG0
P1........| PG1.<=====
P1........| PG2.<= = =
P2........| PG2

Au 4em. passage PG4 :
P0........| PG0
P1........| PG1.<=====
P1........| PG2.<= = =
P2........| PG2
_______________________________________________
5) Pour un même groupe sauvegarder les identifiants PROJET/PGM ( dans une seconde table TAB_COBOL_S ).
IGNORER le couple PROJET/NOM égale à celui en cours de traitement (relativement à la structure primaire).
STRUCTURE: nom_projet-nom_pgm|nom_projet-nom_pgm|nom_projet-nom....n fois
Charger le groupe (1 ou n) dans la table TAB_COBOL_S

Au 1er. passage PG4 de la liste. (P3_PG4 (..-...) sera traité en 7) :
TAB_COBOL_S = |P3-PG3|..-...|
__________________________________________________
Au 2em. passage PG4 de la liste. (P2-PG3 (..-...) sera traité en 7) :
TAB_COBOL_S = |P2-PG2|..-...|

Au 3em. passage PG4 de la liste. (P1-PG2 (..-...) sera traité en 7) :
TAB_COBOL_S = |P1-PG1|..-...|

Au 4em. passage PG4 de la liste. (P1-PG2 (..-...) sera traité en 7) :
TAB_COBOL_S = |P1-PG1|..-...|
_______________________________________________________

Pour chacun des postes de la table TAB_COBOL_S.
===>.6)Itération 3 jusqu'à fin d’un groupe (présent dans la table TAB_COBOL_S):

7) Faire un accés par la clé primaire générique (idem 2) à la 1ere ligne d'un groupe de (1 ou plusieurs) lignes(s) de la table DB2.

Au 1er. passage PG4 : TAB_COBOL_S = |P3-PG3|..-...|
PG3....| P2.<===== positionnement et lecture
PG3....| P3.<===== lecture
rupture
PG4....|
Fin de fichier
____________________________________________________
Au 2em. passage PG4 : TAB_COBOL_S = |P2-PG2|..-...|
PG2....| P1.<===== positionnement et lecture
PG2....| P2.<===== lecture
rupture
PG3....| P2

Au 3em. passage PG4 : TAB_COBOL_S = |P1-PG1|..-...|
PG0....| P0
PG1....| P1.<===== positionnement et lecture
PG2....| P1

Au 4em. passage PG4 : TAB_COBOL_S = |P1-PG2|..-...|
PG0....| P0
PG1....| P1.<===== positionnement et lecture
PG2....| P1.<===== lecture
____________________________________________________

8) Sauvegarder l’identifiant PGM-PROJET en étendant la table TAB_COBOL_P. Eliminer les doublons possibles. Browsing de la table et stockage des noms de PG et de PROJET uniquement si le nom du PGx à insérer n'est pas déjà présent dans cette table (relativement au nom du pgm contaminé en cours, en l’occurrence *PG4).

Cas 2em. Fois PGx contaminé : (le cas 1ere fois est traité en 3)
TAB_COBOL_P = |*PG4-P3|PG3-P2| PG3 stocké au traitement de : PG3....| P2.
TAB_COBOL_P = |*PG4-P3|PG3-P2| inchangée au traitement de : PG3....| P3.
_____________________________________________________________________
Cas 3em. Fois PGx contaminé :
TAB_COBOL_P = |*PG4-P3|PG3-P2|PG2-P1| PG1 stocké au traitement de : PG1....| P1.
TAB_COBOL_P = |*PG4-P3|PG3-P2|PG2-P1|PG1-P1| PG2 stocké au traitement de : PG2....| P1.

Cas 4em. Fois PGx contaminé :
TAB_COBOL_P = |*PG4-P3|PG3-P2|PG2-P2|PG1-P1| inchangée au traitement de : PG1....| P1.
TAB_COBOL_P = |*PG4-P3|PG3-P2|PG2-P2|PG1-P1| inchangée au traitement de : PG2....| P1.

9) FIN d’une Itération 3
.....FIN d’une Itération 2 *FIN d’une Itération 1 OU épuisement de la liste noms des pgm contaminés (voir en 1))
*La fin du traitement d’UN NOM de la liste des pgm contaminés (FIN d’une Itération 1) est détectée lorsque, pour un groupe d’enregistrements la table TAB_COBOL_P demeure inchangée tel que Cas 4em. Fois (ci-dessus en 8)). Cela sous-entend qu’il ne subsiste plus aucun nom de PGm, associé à un nom de projet, qui soit incriminé ou concerné par l’ "épidémie".

Faute d'environnement je n'ai malheureusement pas pu tester en "réel" ce traitement. Il y a vraisemblablement des réglages et des améliorations à y apporter.
Je ne dispose pas de temps supplémentaire à consacrer à ce problème, je le regrette. Je t’invite si tu es intéressé, à « faire tourner « cette mécanique « a la main » afin de la valider.

En espérant que tout cela t'aidera pour finaliser une solution,

Cordialement,
06/07/2006, 16h36
lennelei

Bonjour Christianchristian,

tout d'abord, toutes mes excuses pour ne pas avoir répondu plus tôt, j'étais occupé par certains autres points chauds ;)

Je voudrais ensuite te dire un grand grand merci pour ton aide... c'est ... très impressionnant 8O
Bon, je l'avoue, je n'ai pas encore tout lu ;) ni tout assimilé, mais rien que le fait d'avoir écrit tout ça montre que tu as du bien y réfléchir ! Et encore une fois merci, et ne t'inquiètes pas, tu n'as rien à regretter (il ne manquerait plus que ça vu ta contribution) !

Pour en revenir à ton algo, je n’ai (naturellement) pas encore pu le tester, mais je suis sur que, même au cas où je ne pourrais l’appliquer à la lettre, je pourrais au moins y trouver des idées pour trouver un truc qui marche. Néanmoins, il y’a un point surlequel je ne peux qu’être d’accord :
Que la volumétrie de la table DB2, exprimée en nombre de lignes, est dans les limites du « raisonnable »

Pour info, il pourrait s’agir d’une table de 15 à 20 millions de lignes :x Ce que je ne connais pas en revanche, c’est la volumétrie des « programmes infectés » pas plus que la dimension des relations programmes <=> projets. Bref, du beau boulot en aveugle pour le moment !

C’est sur que si on avait demandé à des « techniciens » ce qu’ils pensaient de la solution (relations entre programmes et projets ici), ils auraient fait de grands yeux compte tenu de l’ampleur de la tâche de développement…

Bref, encore merci pour ton idée, je vais la potasser en même temps que celle que j’ai eu de mon côté : utiliser une pile pour gérer les éléments à traiter (je ne sais pas encore comment l’implémenter ? Peut-être en DB2 ?!)
06/07/2006, 20h18
Christianchristian

Bonjour Alek-C,

Citation:

Envoyé par Alek-C

,
tout d'abord, toutes mes excuses pour ne pas avoir répondu plus tôt, j'étais occupé par certains autres points chauds ;)

Aucun problème.

Citation:

Envoyé par Alek-C

mais rien que le fait d'avoir écrit tout ça montre que tu as du bien y réfléchir !

Je ne m'étais encore jamais trouvé en présence d'un cas rigoureusement similaire, c'est vrai que ça prend la tête, mais c'est intéressant. Je me suis occupé il y a une vingtaine d'années, du développement d'une petite application de préordonnancement de fabrication automobile chez CITROEN, dans laquelle j'avais appliqué ce principe de fonctionnement qui utilise des tables COBOL et des KSDS VSAM

Citation:

Envoyé par Alek-C

Pour info, il pourrait s’agir d’une table de 15 à 20 millions de lignes :x Ce que je ne connais pas en revanche, c’est la volumétrie des « programmes infectés » pas plus que la dimension des relations programmes <=> projets. Bref, du beau boulot en aveugle pour le moment !

Oui en effet y'a du gros ! Le stockage de la totalité des "pgm infectés" ne pourrait donc pas se faire en table COBOL, seules les données relatives au "pgm infecté" en cours de traitement pourraient l'être. Une fois traitées ces données (relatives au "pgm infecté") devront été stockées dans une table DB2 ou un fichier KSDS VSAM.

Cordialement,