Informatique
II-2. Les Opérateurs Elémentaires
Yüklə 2,35 Mb.
|
- Bu səhifədəki naviqasiya:
- II-2.1 Lopérateur de SELECTION
- II-2.1.1 Notion dinvalidation et structure de données
- II-2.1.2 Spécification de lopérateur de SELECTION
- II-2.1.3 Illustration par un exemple
II-2. Les Opérateurs ElémentairesLes opérateurs élémentaires correspondent aux opérateurs primitifs du modèle. Ils définissent des opérations sur les graphes et les sous-graphes. Ils sont similaires aux opérateurs de la théorie des graphes et de l'algèbre relationnelle. Trois opérateurs sont définis : les opérateurs de SELECTION, UNION et DIFFERENCE. II-2.1 L'opérateur de SELECTIONAu sens de l'algèbre relationnelle, la sélection est un opérateur unaire. Une sélection sur une relation R1 suivant un critère fournit comme résultat une relation R2, de même schéma que R1, contenant les tuples issus de R1 et vérifiant ce critère. De la même manière, l'opérateur de SELECTION (noté s) est un opérateur unaire. Il permet d'obtenir un ou plusieurs sous-graphes à partir d'un graphe donné (la notion de critère de sélection autorisant à réduire le nombre de noeuds et d'arcs du graphe). Le graphe résultat est un graphe hiérarchisé de même structure que le graphe hiérarchisé initial. La condition de sélection est une expression formalisant des critères et/ou des contraintes agrégatives exprimés par l'utilisateur sur les noeuds et les arcs, au sens défini précédemment. La différence principale avec un opérateur classique de sélection réside dans la notion d'abstraction du modèle de graphe. L'opérateur de SELECTION s'applique sur tous les noeuds et arcs du graphe, puis récursivement, sur tous les réseaux_associés des noeuds et arcs spécialisés.
Figure III-16. Signature de l'opérateur de SELECTION L'opérateur de SELECTION se base sur une fonction élémentaire pour tester la vérification des critères. Cette fonction élémentaire, Vérif_Critère_Noeud (resp. Vérif_Critère_Arc), est définie sur les noeuds (resp. arcs) et sur une condition qui est un critère. Cette fonction permet de tester si un noeud (resp. arc) répond à la condition décrite. Elle teste uniquement les critères individuels sur les noeuds (resp. arcs). La signature de la fonction Vérif_Critère_Noeud est illustrée Figure III-17.
Figure III-17. Signature de la fonction Vérif_Critère_Noeud La signature de la fonction Vérif_Critère_Arc est similaire à la signature de la fonction Vérif_Critère_Noeud, en remplaçant Noeud par Arc. Etablissons tout d'abord deux définitions sur les noeuds et les arcs. Définition : Un master_noeud est appelé un noeud simple s'il ne possède plus aucun réseau_associé. Définition : Un master_arc est appelé un arc simple s'il ne possède plus de réseau_associé. L'opérateur de SELECTION transforme un master_noeud en un noeud simple, à la condition que l'application récursive de cet opérateur sur les réseaux_associés de ce master_noeud rende un graphe vide. Il peut également transformer un master_arc en un arc simple si l'ensemble des noeuds et des arcs composant son réseau_associé ne respecte pas la condition de sélection. Un noeud (resp. arc) ne respectant pas la condition de sélection est soit éliminé de l'ensemble des noeuds (resp. arcs) le contenant, soit transformé. II-2.1.1 Notion d'invalidation et structure de donnéesUn noeud (resp. arc) ne respectant pas la condition de sélection ne peut pas toujours être éliminé de l'ensemble des noeuds (resp. arcs) le contenant. Dans ce cas, il est transformé en un noeud invalidé (resp. arc invalidé). Un noeud (resp. arc) invalidé ne possède aucune existence réelle dans un graphe donné; il ne possède qu'une existence "hiérarchique". Les noeuds (resp. arcs) invalidés permettent de conserver une cohérence hiérarchique dans le graphe en ne mêlant pas des noeuds (resp. arcs) se trouvant à la couche i d'abstraction de la hiérarchie des noeuds (resp. arcs) et des noeuds se trouvant à une couche différente de cette même hiérarchie. Un master_noeud invalidé, par exemple, permet de garder les réseaux_associés à ce master_noeud sous une forme non-développée. Il peut donc exister plusieurs noeuds (resp. arcs) invalidés dans un même niveau hiérarchique.
II-2.1.2 Spécification de l'opérateur de SELECTIONLes fonctions supplémentaires permettant de décrire l'opérateur de SELECTION sont présentées en Annexes. Détaillons cet opérateur de SELECTION pour un graphe G(N,E) et une condition de sélection représentée par l'expression condition. Cette condition est de type critère. Soit G'(N',E') le graphe résultant de l'application de l'opérateur de SELECTION sur G avec l'expression condition. 1) Le graphe G'(N',E') initialisé au graphe vide.
2) Soit un arc e de E. La condition de type critère va être vérifiée sur cet arc. Le résultat de la sélection sur l'ensemble E des arcs résulte des opérations suivantes :
2.1) Un arc simple vérifiant la condition est ajouté à l'ensemble E'.
2.2) Un master_arc vérifiant la condition nécessite l'examen de son réseau_associé. Suivant le résultat de cet examen (graphe vide ou non), l'arc devient ou non un arc simple. Il est rajouté à E' s'il reste un master_arc. Dans le cas contraire, il est ajouté à un ensemble d'arcs ens_arcs_simples.
2.3) Un master_arc ne vérifiant pas la condition nécessite l'examen de son réseau_associé. Suivant le résultat de cet examen (graphe vide ou non), l'arc n'est pas ajouté à E' ou devient un master_arc invalidé.
3) Soit un noeud n de N. La condition de type critère va être vérifiée sur ce noeud. Le résultat de la sélection sur l'ensemble N des noeuds résulte des opérations suivantes :
3.1) Un noeud simple vérifiant la condition est ajouté à N'.
3.2) Un noeud simple n ne vérifiant pas la condition nécessite tout d'abord de trouver un éventuel noeud ancêtre de n dans le graphe (le plus proche ancêtre). Les arcs liés à n sont ensuite examinés, qu'ils appartiennent à E' ou à l'ensemble d'arcs ens_arcs_simples.
3.2.1) L'arc e lié à n est un arc simple. Deux cas peuvent se présenter : n est extrémité initiale de cet arc ou n est extrémité finale de cet arc. Dans les deux cas, l'existence du noeud ancêtre de n dans G (n") conduit à remplacer n par ce noeud n" en tant qu'extrémité de e. La non-existence de ce noeud n" provoque la disparition de l'arc e du graphe G (intégration dans un ensemble d'arcs enlève_arcs).
3.2.2) L'arc e lié à n est un master_arc. Deux cas peuvent se présenter : n est extrémité initiale de cet arc ou n est extrémité finale de cet arc. Dans les deux cas, l'existence du noeud ancêtre de n dans G (n") conduit à remplacer n par ce noeud n" en tant qu'extrémité de e. La non-existence de ce noeud n" provoque l'invalidation du noeud n qui reste alors extrémité de e.
3.2.3) L'arc e lié à n appartient à l'ensemble d'arcs ens_arcs_simples. Deux cas peuvent se présenter : n est extrémité initiale ou finale de cet arc. Dans les deux cas, l'existence du noeud ancêtre de n dans G (n") conduit à remplacer n par n" en tant qu'extrémité de e. La non-existence de ce noeud n" provoque la disparition de l'arc e du graphe G (intégration dans enlève_arcs_simples).
3.3) Un master_noeud n nécessite l'examen de ses réseaux_associés. L'opérateur de SELECTION est appliqué sur chacun de ces réseaux. Le résultat de cette application retourne, pour chaque réseau, un graphe vide ou non vide. Un réseau dont aucun des noeuds et arcs ne vérifie le critère de sélection est ôté de l'ensemble des réseaux de n. Un réseau dont au moins un noeud et/ou arc vérifie le critère est transformé pour ne laisser dans ce réseau que les noeuds et arcs résultant de l'application de l'opérateur de SELECTION. Le master_noeud n peut ou non vérifier le critère de sélection (cas 3.3.1 et 3.3.2).
3.3.1) Le master_noeud n vérifie le critère de sélection. Il est transformé en un noeud simple, et ajouté à un ensemble de noeuds ens_noeuds_simples, si le résultat de l'examen de ses réseaux_associés rend un graphe vide pour chacun de ces réseaux. Qu'il soit ou non transformé en noeud simple, les arcs (provenant de E' ou de l'ensemble d'arcs ens_arcs_simples) auxquels il est attaché en tant qu'extrémité initiale ou finale sont examinés.
3.3.1.1) Le noeud n est remplacé par le noeud n' comme extrémité initiale ou finale de l'arc e, si n était extrémité initiale ou finale de cet arc. 3.3.2) Le master_noeud n ne vérifie pas le critère de sélection, ou était invalidé avant le début de cette application de l'opérateur de SELECTION. Deux cas se présentent suivant si le résultat de l'examen de ses réseaux_associés rend des graphes vides pour chacun de ces réseaux ou si au moins un de ses réseaux n'est pas vide. Un master_noeud n ne possédant plus aucun réseau est invalidé. Il nécessite de trouver un éventuel noeud ancêtre de n dans le graphe (le plus proche ancêtre). Chacun des arcs liés à n (que cet arc appartienne à E' ou à l'ensemble d'arcs ens_arcs_simples) est examinés et les cas 3.2.1 et 3.2.2 sont réitérés. Un master_noeud n possédant encore des réseaux_associés est invalidé et chacun des arcs auxquels il est lié est examiné qu'il appartienne à E' ou à l'ensemble d'arcs ens_arcs_simples (le cas 3.3.1.1 est réitéré).
4) Lors de l'examen des noeuds de N', certains master_noeuds sont devenus des noeuds simples. Pour conserver une cohérence hiérarchique entre les noeuds, un master_noeud n devenu noeud simple doit être placé au plus bas niveau de la hiérarchie des noeuds. Il est donc ajouté au réseau_associé de son noeud fantôme "frère" (c'est-à-dire du noeud fantôme fils du père de n), et placé au plus bas niveau de la filiation de ce noeud frère. L'oid de n est modifié en conséquence et n est modifié dans N'. La même situation est vrai pour les master_arcs de E' devenus arcs simples, et ils sont ajoutés à E' avec ces modifications.
Grâce à la notion d'invalidation, le résultat de l'opération de SELECTION est un graphe où les noeuds et les arcs répondant à la condition de sélection sont validés. Les noeuds et arcs invalidés existant encore dans ce graphe final sont là pour permettre de garder une cohérence du graphe vis-à-vis de la hiérarchie des noeuds et des arcs du graphe initial. II-2.1.3 Illustration par un exempleSoit un graphe G(N,E) contenant un sous-ensemble des noeuds et des arcs du réseau mondial illustré au chapitre II. Ce graphe contient deux master_noeuds (Paris et Lyon), et un master_arc (Paris-Lyon par A6). Paris représente l'abstraction de deux réseaux_associés. Le seul arc_sortant de ces réseaux est Pte d'Orléans-Sortie0 de l'A6 par l'A6. Aucun arc_entrant n'est défini. Lyon représente l'abstraction d'un unique réseau_associé (Bordure de Lyon). Le seul arc_entrant de ce réseau est Sortie21 de l'A6-Car. Europe par l'A6. Aucun arc_sortant n'est défini. Les Figures suivantes représentent tous les niveaux d'abstraction du graphe G. L'opérateur de Sélection va être appliqué sur ce graphe et sur un critère de sélection. Nous ne détaillons pas ici ce critère. Dans les Figures suivantes, les noeuds et arcs ne répondant pas à ce critère sont indiqués en gras. La Figure III-18 représente le plus haut niveau d'abstraction (niveau 3) du graphe G.
Figure III-18. Graphe G - niveau 3 Aucun noeud et arc du réseau_associé au master_noeud Lyon ne vérifie le critère de sélection. La Figure III-19 représente le premier réseau_associé au master_noeud Paris (Réseau Intérieur de Paris). La Figure III-20 représente le deuxième réseau_associé à ce master_noeud (Bordure de Paris). Le master_noeud 14ème ne vérifie pas le critère, non plus que le noeud Pl. Italie.
Figure III-19. Premier réseau_associé au master_noeud Paris Aucun des noeuds et arcs du réseau_associé au master_noeud 12ème Arrondissement (Figure A.II-40 des Annexes) ne vérifie le critère de sélection, à l'exception du noeud Pt Bercy, et de l'arc sortant Pt Bercy-Pl. Italie par Bd V.Auriol. Le master_arc Pte Dorée-Pl. Bastille par Av. Daumesnil vérifie le critère de sélection, mais pas ses extrémités initiales et finales. Seuls le noeud Pl. F.Eboué et l'arc Pte Dorée-Pl. F.Eboue par Av. Daumesnil du réseau_associé à ce master_arc (Figure A.II-73 des Annexes) vérifient le critère. Aucun des noeuds et arcs du réseau_associé au master_noeud 13ème Arrondissement (Figure A.II-41 des Annexes) ne vérifie le critère de sélection, à l'exception de l'arc entrant Pt Bercy-Pl. Italie par Bd V.Auriol, de l'arc sortant Pl. Italie-Pte Orléans par Bd A.Blanqui et du noeud Pte Italie. Le noeud Pte Orléans du réseau_associé au master_noeud 14ème Arrondissement (Figure A.II-42 des Annexes) vérifie le critère de sélection, ainsi que l'arc Pte Orléans-Sortie0 de A6 par A6, et l'arc entrant Pl. Italie-Pte Orléans par Bd A.Blanqui. Aucun des autres noeuds et arcs entrant ou sortant ne vérifie le critère. Aucun des noeuds et arcs du réseau_associé au master_noeud 18ème Arrondissement (Figure A.II-43 des Annexes) ne vérifie le critère de sélection.
Figure III-20. Deuxième réseau_associé au master_noeud Paris Aucun des noeuds et arcs du réseau_associé au master_arc Périphérique Est (Figure A.II-58 des Annexes) ne vérifie le critère de sélection, à l'exception des noeuds Pte Orléans et Pte Italie. Aucun des noeuds et arcs du réseau_associé au master_arc Pte Bercy-Pte Italie par Bd Masséna (Figure A.II-59 des Annexes) et du réseau_associé au master_arc Pte Chapelle-Pte Orléans par *Périphérique Est (Figure A.II-60 des Annexes) ne vérifie le critère de sélection, à l'exception des noeuds Pte Orléans et Pte Italie. La Figure III-21 représente le réseau_associé au master_arc Paris-Lyon par l'A6 (Figure A.II-55 des Annexes). Le master_noeud Paris répond au critère de sélection, alors que le master_noeud Lyon n'y répond pas. Seul le master_arc Paris-Lyon par la N7 vérifie ce critère.
Figure III-21. réseau_associé au master_arc Paris-Lyon par l'A6 Seuls les noeuds Paris, Pte Orléans et Sortie0 de A6 du réseau_associé au master_arc Paris-Lyon par *A6 (Figure A.II-56 des Annexes) vérifient le critère, ainsi que l'arc Pte Orléans-Sortie0 de A6 par l'A6. Aucun des noeuds et arcs du réseau_associé au master_arc Paris-Lyon par la N7 (Figure A.II-57 des Annexes) ne vérifie le critère de sélection. La Figure III-22 représente les deux premiers niveaux d'abstraction du graphe G après application de l'opérateur de Sélection. Le master_noeud Lyon est devenu un noeud simple invalidé. L'arc Pl. Italie-Pte Orléans par Bd A.Blanqui est devenu un arc entre 13ème Arrondissement et Pte Orléans. L'arc Pt Bercy-Pl. Italie par Bd V.Auriol est devenu un arc entre Pt Bercy et 13ème Arrondissement. Le master_noeud 18ème Arrondissement est devenu un noeud simple, fils de *Paris. Le master_arc Paris-Lyon par la N7 a disparu du réseau_associé à Paris-Lyon par l'A6 pour devenir un arc simple appartenant au réseau_associé à Paris-Lyon par *A6. Le master_arc Périphérique Est devient un master_arc invalidé.
Figure III-22. Graphe G - niveaux 3 et 4 La Figure III-23 représente les deux niveaux d'abstraction les plus bas du graphe G après application de l'opérateur de Sélection.
Figure III-23. Graphe G - niveaux 1 et 2 Yüklə 2,35 Mb. Dostları ilə paylaş:
|
