Informatique
II- La gestion des différents niveaux d'abstraction
Yüklə 2,35 Mb.
|
- Bu səhifədəki naviqasiya:
- II-1. La hiérarchie des noeuds
- II-2. La hiérarchie des arcs
- II-3. La hiérarchie des réseaux
II- La gestion des différents niveaux d'abstractionAfin de pouvoir gérer les différents niveaux d'abstraction du modèle de graphe, les noeuds et les arcs sont organisés en hiérarchie. Cette hiérarchie est utilisée pour définir la structure de la base de données. Les différentes applications organisent leurs données suivant cette hiérarchie, en utilisant seulement une partie de la hiérarchie, ou en la restructurant totalement. La hiérarchie est définie par un OID logique (Object IDentifier), totalement indépendant de l'OID défini par le Système de Gestion de Base de Données utilisé. Chaque élément de base du modèle de graphe (noeud, arc, réseau) possède un OID global qui est unique dans la base de données. Cet OID global permet de définir un OID logique qui illustre la hiérarchie des noeuds, des arcs et des réseaux. Par la suite, nous appellerons OID cet OID logique. L'OID d'un noeud (resp. arc, réseau) permet d'identifier uniquement ce noeud (resp. arc, réseau) dans la base de données. Il permet de le situer dans la hiérarchie des noeuds (resp. arcs, réseaux) et d'identifier son noeud (resp. arc, réseau) père. Des types de bases sont définis permettant de construire l'OID. Ces types sont les suivants :
type OID_général : list (OID_global); type ordre : list (integer);
II-1. La hiérarchie des noeudsUn noeud appartient à une hiérarchie de noeuds. Chaque niveau de cette hiérarchie est appelé une couche. Ces couches représentent un niveau particulier d'abstraction. Soit L la profondeur de cette hiérarchie. L'OID d'un noeud possède L couches; la couche L représente le plus haut niveau d'abstraction, et la couche 1 représente le plus bas niveau d'abstraction. La Figure II-11 présente un exemple de hiérarchie de noeuds, avec trois niveaux d'abstraction.
Figure II-11. Une hiérarchie de noeuds L’OID d’un noeud est défini par une liste d'entiers. Un élément de cette liste est appelé une couche. L'OID d'un noeud n appartenant à la couche k d'abstraction est défini par les règles suivantes (Figure II-12).
Figure II-12. Les règles pour construire l'OID d'un noeud Soit L le niveau d'un noeud (par exemple, France). Ce noeud est appelé le noeud généralisé de tous ses noeuds dépendants (Paris, dans la Figure II-11) ou encore le noeud "père" de tous ces noeuds. En suivant les règles de définition de l'OID d'un noeud, soit 10 l'OID global associé au noeud France, 100 l'OID global associé au noeud Paris, et 230 l'OID global associé au noeud Porte de la Chapelle. La Figure II-13 illustre les OIDs de ces différents noeuds.
Figure II-13. OIDs de noeuds Dépendant des différents niveaux d'abstraction déjà définis dans la base de données, un noeud appartenant à une couche i (par exemple, Tours appartenant à la couche 1 de la Figure II-11) pourrait dépendre d'un noeud généralisé de la couche i+2 (i.e., France à la couche 3). Pour lier ces deux noeuds dans la hiérarchie des noeuds, un noeud fantôme est utilisé à la couche i+1. L'OID global associé à ce noeud est l'opposé de l'OID global du noeud généralisé de la couche i+2 (i.e., -10). Le nom du noeud fantôme est une chaîne de caractères résultant de la concaténation du caractère "*" et du nom du noeud généralisé (le nom de ce noeud fantôme est donc "*France"). Cette construction est appliquée récursivement chaque fois que le nombre de niveaux manquants entre deux noeuds est supérieur à un, mais l'OID global des différents noeuds fantômes est toujours l'opposé de l'OID global du premier noeud généralisé. Un seul noeud fantôme existe pour chaque réseau de noeuds dépendants. La Figure II-14 et la Figure II-15 représentent la transformation de la Figure II-11 précédente, suite à l'ajout des noeuds Orléans, Blois, Tours, StPierre le Moûtier et Lyon dépendant du noeud France. Elles présentent la hiérarchie du noeud France et les OIDs associés aux différents noeuds de cette hiérarchie.
Figure II-14. Hiérarchie de noeuds
Figure II-15. OIDs de noeuds L'OID d'un noeud possède donc la structure suivante : type OID_noeud : OID_général II-2. La hiérarchie des arcsLa hiérarchie des arcs est similaire à la hiérarchie des noeuds. L'OID d'un arc se divise en trois parties. La première (resp. deuxième) partie contient l'OID du noeud initial (resp. final) de l'arc. La troisième partie (la partie arc) contient l'OID général dans la hiérarchie des arcs. La construction de la troisième partie est similaire à la construction de l'OID d'un noeud. Un arc appartient à une hiérarchie d'arcs. Chaque niveau de cette hiérarchie est appelé une couche. Ces couches représentent un niveau particulier d'abstraction. La Figure II-16 présente un exemple de hiérarchie d'arcs, avec deux niveaux d'abstraction. Le noeud Tours qui apparaît dans les couches 1 et 2 est le même noeud.
Figure II-16. Hiérarchie d'arcs Soit 20 l'OID global associé à l'arc (Paris, Tours), 330 l'OID global associé à l'arc (Pte d'Orléans, Orléans), et 331 l'OID local associé à l'arc (Orléans, Blois), et 332 l'OID local associé à l'arc (Blois, Tours). La Figure II-17 présente les OIDs de ces arcs.
Figure II-17. OIDs d'arcs Dépendant des différents niveaux d'abstraction, une notion d'arc fantôme est créée. Son but est similaire à celui du noeud fantôme. La partie arc d'un arc fantôme suit les mêmes règles que celles des noeuds fantômes. Un unique arc fantôme est défini entre les mêmes noeuds initial et final. La Figure II-18 présente un exemple de hiérarchie d'arcs contenant des arcs fantômes.
Figure II-18. Hiérarchie d'arcs Soit 1 l'OID local de l'arc (Paris, Lyon), 420 de l'arc (Pte de la Chapelle, Pte d'Orléans), 421 de l'arc (Tours, StPierre le Moûtier) et 422 de l'arc (StPierre le Moûtier, Lyon). La Figure II-19 présente les OIDs correspondant à ces arcs. Pour simplifier la lecture, les OIDs des noeuds ne sont pas représentés.
Figure II-19. OIDs d'arcs L'OID d'un arc possède donc la structure suivante : type OID_arc tuple (
extrémité_finale : OID_noeud, hiérarchie_d'abstraction : OID_général );
II-3. La hiérarchie des réseauxCette hiérarchie est similaire à la hiérarchie des noeuds. Les règles de construction sont les mêmes. Cependant la notion de réseau fantôme n'existe pas, à ce niveau-là, puisque la hiérarchie des réseaux est complètement définie par celle des noeuds et des arcs. Notons que la hiérarchie des réseaux représentant les réseaux des noeuds et des arcs, tous les réseaux "feuilles" (c'est-à-dire tous les réseaux ne contenant ni master_noeud ni master_arc) ne se trouvent pas forcément au plus bas niveau de la hiérarchie des réseaux. En effet, si la hiérarchie des noeuds possède, par exemple, trois niveaux, et la hiérarchie des arcs deux niveaux, alors certains réseaux ne possédant plus aucun master_noeud ou master_arc se trouveront au niveau 2 de la hiérarchie des réseaux, alors que d'autres se trouveront au niveau 1 de cette hiérarchie.
type OID_global_réseau tuple (
ordre : ordre );
type OID_réseau : list (OID_global_réseau);
Le réseau de plus haut niveau d'abstraction contient les noeuds et arcs de plus haut niveau. Il contient donc les noeuds France, Paris, Lyon et l'arc Paris-Lyon. Ce réseau représente l'abstraction d'un noeud fictif d'OID global 10000.
Figure II-20. Réseau de plus haut niveau Le master_noeud France représente l'abstraction d'un réseau_associé contenant les noeuds Paris, *France, Lyon et l'arc Paris-Lyon.
Figure II-21. Réseau_associé au master_noeud France Le master_noeud Paris possède un réseau_associé. Ce réseau_associé contient les noeuds Pte de la Chapelle et Pte d'Orléans, et l'arc Périphérique entre Pte de la Chapelle et Pte d'Orléans. Un arc_sortant de ce réseau est l'arc A10 entre Pte d'Orléans et Orléans.
Figure II-22. Réseau_associé au master_noeud Paris Le master_noeud *France possède un réseau_associé. Ce réseau_associé contient les noeuds Tours et Lyon. Les arcs_entrant de ce réseau sont les arcs A10 entre Paris et Tours, et *Paris-Lyon.
Figure II-23. Réseau_associé au master_noeud *France Le master_arc Paris-Lyon représente l'abstraction d'un réseau_associé contenant les noeuds Paris, Lyon, Tours, *France et les arcs A10 entre Paris et Tours et *Paris-Lyon. L'arc_entrant de ce réseau est l'arc A10 entre Paris et Tours, et son arc_sortant est l'arc *Paris-Lyon.
Figure II-24. Réseau_associé au master_arc Paris-Lyon Le master_arc A10 entre Paris et Tours possède un réseau_associé. Ce réseau_associé contient les noeuds Paris, Pte d'Orléans, Orléans, Blois, Tours et *France, et les arcs A10 entre Pte d'Orléans et Orléans, A10 entre Orléans et Blois, A10 entre Blois et Tours. L'arc_entrant de ce réseau est l'arc A10 entre Pte d'Orléans et Orléans. Son arc_sortant est l'arc A10 entre Blois et Tours.
Figure II-25. Réseau_associé au master_arc A10 entre Paris et Tours Le master_arc *Paris-Lyon possède un réseau_associé. Ce réseau_associé contient les noeuds Paris, Pte de la Chapelle, Pte d'Orléans, Tours, StPierre le Moûtier, Lyon et *France, et les arcs Périphérique entre Pte de la Chapelle et Pte d'Orléans, N76 entre Tours et StPierre le Moûtier, N7 entre StPierre le Moûtier et Lyon. L'arc_entrant de ce réseau est l'arc Périphérique entre Pte de la Chapelle et Pte d'Orléans. Son arc_sortant est l'arc N7 entre StPierre le Moûtier et Lyon.
Figure II-26. Réseau_associé au master_arc *Paris-Lyon Les OIDs de ces réseaux sont représentés dans la Figure II-27.
Figure II-27. OIDs de réseaux Yüklə 2,35 Mb. Dostları ilə paylaş:
|
