Les modèles hiérarchiques et réseaux
Mehdi HAJJI [email protected]
Conception BD – II2
Plan du cours
Les modèles hiérarchiques et réseaux
-M. HAJJI-
2
Le modèle réseau
3
Les modèles hiérarchiques et réseaux
-M. HAJJI-
Caractéristiques principales
Un modèle de données Réseau général (ou PLEXE) est
un modèle dans lequel les relations entre les entités sont représentées par des liens qui peuvent être 1:1, 1:N, N:1, ou N:M.
Ces liens en nombre quelconque peuvent associer toute
paire d’entités du modèle.
Ils devront être distingués les uns des autres par un
identificateur.
Exemple
Les modèles hiérarchiques et réseaux
-M. HAJJI-
4
Caractéristiques princpales
Exemple
Les modèles hiérarchiques et réseaux
-M. HAJJI-
5
Caractéristiques princpales Un lien de type 1 : 1
associe à une occurrence de l’entité origine une et une seule
occurrence de l’entité d’arrivée.
dans ce type de lien les cardinalités (1:1) ne suffisent pas pour orienter le lien afin de distinguer l’entité origine du lien de celle d’arrivée. C’est pour cela que la sémantique du lien doit être véhiculée par le nom du lien.
Par exemple le lien 1:1 existant entre les deux entités WILAYAS et
WALI et ayant pour nom A_Pour_Wali sous entend qu’on oriente le lien de l’entité WILAYAS vers l’entité WALI.
On aurait pu utiliser le même lien mais en l’orientant de l’entité
WALI vers l’entité WILAYAS grâce au nom du lien qui serait dans ce cas Est_Wali_De.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
6
Caractéristiques princpales
Un lien de type 1:N
associe à une occurrence de l’entité origine (se trouvant du côté de la flèche simple) zéro (0), une (1) ou plusieurs (N) occurrences de l’entité d’arrivée (se trouvant du côté de la flèche double).
L’orientation du lien est donc entièrement déterminée grâce aux cardinalités 1:N. Le nom attribué au lien permet de rattacher une sémantique au lien.
Par exemple le lien Est_Habité_Par de type 1:N va implicitement
de l’entité VILLES vers l’entité PERSONNES et permet de modéliser le fait qu’une ville v soit habitée par 0, une ou plusieurs personnes.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
7
Caractéristiques princpales
Un lien de type N:1
associe à 0, une ou plusieurs occurrences de l’entité origine (se trouvant du côté de la flèche double, une et une seule occurrence de l’entité d’arrivée (se trouvant du côté de la flèche simple).
Ce lien est donc implicitement orienté de l’entité se trouvant du côté de la flèche double vers l’entité se trouvant du côté de la flèche simple.
Par exemple le lien Habite_Dans de type N:1 allant de l’entités
PERSONNES vers l’entité VILLES modélise le fait que 0, une ou plusieurs personnes Habitent dans une seule ville.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
8
Caractéristiques princpales Un lien de type N:M
associe à 0, une ou plusieurs occurrences de l’entité origine (se trouvant du côté de la première flèche double), 0, une ou plusieurs occurrences de l’entité d’arrivée (se trouvant du côté de l’autre flèche double).
les cardinalités N:M ne suffisent pas pour fixer l’orientation du lien afin de pouvoir distinguer entre l’entité origine et l’entité d’arrivée de ce lien. C’est le même problème que dans le cas d’un lien de type 1:1 et par conséquent la sémantique du lien doit être véhiculée par le nom qui sera attribué au lien.
Par exemple, le lien N:M entre les entités VILLES et SOCIETES et ayant pour
nom Est_Impantée_Dans sous-entend qu’on oriente le lien de l’entité SOCIETES vers l’entité VILLES puisque dans la réalité on dit qu’une société est implantée dans une ville (ou possède un siège dans une ville).
La possibilité qui consisterait à orienter le lien de l’entité VILLES vers l’entité SOCIETES permettrait quant à elle de modéliser une autre réalité qui signifie qu’une ville regroupe 0, une ou plusieurs sociétés. Il faudra dans ce cas donner au lien N:M un nom qui véhicule cette sémantique. Dans notre exemple c’est le nom Regroupe attribué au lien qui renseigne sur cette sémantique.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
9
Diagramme de structure de données de BACHMAN
Un diagramme de BACHMAN (appelé aussi diagramme de structures de données) est un modèle de données de type réseau général mais dans lequel toutes les relations entre les entités sont de type 1:N.
La représentation graphique d’un modèle de données sous forme de boîtes et de flèches a été proposée justement par BACHMAN. Auparavant, on ne représentait un modèle de données que par
le biais de structures de données plus proche du niveau physique telles que des liste chaînées et des fichiers ce qui rendait difficile l’étape de conception du modèle de données.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
10
Diagramme de structure de données de BACHMAN
L’avantage du diagramme de BACHMAN est donc de permettre une représentation simple et uniforme des modèles de données basée sur deux concepts : la boîte (rectangle) modélisant une entité et la flèche modélisant un lien entre deux entités. Pour obtenir un tel modèle, il est bien souvent nécessaire de transformer tous les liens de type N:M en des liens 1:N.
Bien entendu, le modèle ne comportera pas de lien N:M, mais peut cependant avoir plusieurs liens 1:N entre deux mêmes entités qui seront alors différenciés par un nom (i.e. un identificateur).
Les modèles hiérarchiques et réseaux
-M. HAJJI-
11
Méthodes de transformation des liens N:M
Un lien N:M (complexe) entre deux entités peut être
transformé de telle sorte que les liens résultants soient de type 1:N Deux méthodes
Création d’une entité d’intersection Méthode des entités virtuelles et des pointeurs logiques
Les modèles hiérarchiques et réseaux
-M. HAJJI-
12
Méthodes de transformation des liens N:M
Création d’une entité d’intersection
Cette méthode consiste à créer une nouvelle entité appelée entité d’intersection qui possédera une clé obtenue par concaténation des clés des deux entités participant au lien N:M. Exemple
Les modèles hiérarchiques et réseaux
-M. HAJJI-
13
Entité d’intersection
Méthodes de transformation des liens N:M Méthode des entités virtuelles et des pointeurs logiques
Cette méthode consiste à créer des entités virtuelles appelées aussi entités pointeurs qui sont constituées de pointeurs et contenant autant de pointeurs que l’entité pointée.
Un pointeur logique doit être vu à ce niveau comme une clé de
l’entité concernée.
Exemple
Les modèles hiérarchiques et réseaux
-M. HAJJI-
14
Méthodes de transformation des liens N:M
Méthode des entités virtuelles et des pointeurs logiques
Les flèches en pointillés signifient que l’entité virtuelle contient des pointeurs logiques (ou clés) sur l’entité pointée (A ou B).
Cette solution a surtout pour but d’éviter le problème de
duplication des entités qui comme on le sait engendre de la redondance d’information avec tous les problèmes qui en découlent (gaspillage de l’espace mémoire, risque d’incohérence, etc.).
On peut transformer le lien complexe N:M en créant une
copie de chaque entité A et B (i.e. avec les mêmes attributs) mais auxquelles on donnera deux noms distincts par exemple A2 et B2.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
15
Méthodes de transformation des liens N:M
Méthode des entités virtuelles et des pointeurs logiques
Les modèles hiérarchiques et réseaux
-M. HAJJI-
16
Méthodes de transformation des liens N:M Méthode des entités virtuelles et des pointeurs logiques
Les deux entités A2 et B2 seront définies au même niveau que
A et B et de la même façon.
Un SGBD ne peut en aucun cas déduire par exemple que
l’entité A2 et une copie de l’entité A ni que B2 et une copie de l’entité B et ce malgré que celles-ci ont les mêmes attributs. Mis à part les problèmes de redondance d’information et leurs conséquences, cette solution oblige le programmeur de gérer lui même les problèmes de cohérence car toute mise à jour dans A ou B devra obligatoirement être répercutée dans A2 ou B2 respectivement. En effet, ce travail ne peut en aucun être fait par le SGBD qui ignore comme on l’a dit plus haut que A2 est une copie de A et que B2 est une copie de B puisque les entités sont simplement distinguées par leurs noms.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
17
Le modèle de données réseau de Codasyl
Le modèle réseau CODASYL propose deux concepts de base, les enregistrements appelés RECORD dans la terminologie CODASYL et les liens (ou associations) entre enregistrements appelés SET.
L’enregistrement
Publicité
Un enregistrement ou RECORD est décrit par un nom (identificateur) unique permettant de le distinguer parmi l’ensemble des enregistrements du schéma conceptuel et par un ensemble d’attributs chacun possédant un nom et un type (entier, réel, chaîne de caractères, etc.).
Les modèles hiérarchiques et réseaux
-M. HAJJI-
18
Le modèle de données réseau de Codasyl
L’enregistrement
Exemple
Les modèles hiérarchiques et réseaux
-M. HAJJI-
19
Le modèle de données réseau de Codasyl L’enregistrement
Les mots en gras sont des mots clefs du langage de description de
données(LDD) offert par le SGBD.
L’enregistrement ici s’appelle EMPLOYE et possède comme attributs :
un numéro identifié par Numero de type numérique à six (06) chiffres :
PICTURE 9(6)
un nom identifié par Nom de type alphabétique à 12 caractères : PICTURE
A(12)
un nombre d’enfants identifié par Nbre_Enfants de type numérique à 2 chiffres
(PICTURE 99)
de 0 à Nbre_Enfants enfants (variable selon chaque employé) chaque enfant étant
caractérisé par les attributs : un prénom identifié par Prenom_Enfant de type caractère pouvant occuper
jusqu’à 10 au maximum
un âge identifié par Age_Enfant de type numérique à 2 chiffres (PICTURE
99)
une année scolaire identifiée par Annee_Scolaire de type numérique à 2
chiffres (PICTURE 99)
Les modèles hiérarchiques et réseaux
-M. HAJJI-
20
Le modèle de données réseau de Codasyl
Le Lien ou SET
Un lien entre deux entités est appelé un SET dans la
terminologie CODASYL. L’entité origine du SET est dite propriétaire ( ou Owner en anglais ). C’est le cas de l’entité MEDECIN dans la figure suivante. L’entité sur laquelle arrive le SET (l’arc) est dite membre du SET ( ou Member en anglais ). C’est le cas de l’entité MALADES dans la figure suivante. Un SET permet d’associer à une occurrence de l’entité (ou enregistrement) propriétaire une ou plusieurs occurrences de l’entité membre (car tout lien du modèle est de type 1:N) alors qu’inversement à chaque occurrence de l’entité membre ne peut être associé qu’au plus une occurrence de l’entité propriétaire.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
21
Le modèle de données réseau de Codasyl Le Lien ou SET
Exemple
Dans la représentation graphique d’un SET, il n’est pas
nécessaire d’indiquer par une double flèche que le lien est de type 1:N puisque tous les liens sont sous entendus être de type 1:N.
On représente donc simplement un SET à l’aide d’un arc
orienté de l’entité propriétaire vers l’entité membre et on le distingue par un nom.
Pour ce cas le SET a pour nom Examine et est orienté dans
le sens MEDECIN vers MALADES.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
22
Le modèle de données réseau de Codasyl
Le Lien ou SET
Dans le cas où la modélisation conduit à des liens N:M les
transformer en des liens 1:N par l’une des méthodes précédentes, pour passer au modèle Réseau CODASYL.
Le mécanisme d’accès qui permet de passer d’une occurrence de
l’entité propriétaire aux occurrences de l’entité membre qui lui sont associées par le lien est en général celui d’une liste circulaire ayant pour tête de liste l’occurrence de l’entité Propriétaire .
Les modèles hiérarchiques et réseaux
-M. HAJJI-
23
Le modèle de données réseau de Codasyl Cette liste circulaire ne représente qu’une seule occurrence
(réalisation) du SET ayant pour nom Examine. La tête de la liste contient l’occurrence Pasteur de l’enregistrement
MEDECIN qui est le Propriétaire du SET.
Les membres de la liste sont : Ali, Omar,.... et enfin Kamel qui sont
toutes des occurrences de l’enregistrement MALADES.
Cette représentation est possible car chaque occurrence de l’enregistrement de type MALADES (ex : Ali, Omar, ...ou Kamel) n’est associé qu’à une seule occurrence de l’enregistrement de type MEDECIN (ex : Pasteur) et ne peut donc apparaître que dans une seule liste circulaire. En effet, si une occurrence de l’enregistrement de type MALADES pouvait être parcouru par plusieurs listes ayant chacune pour tête une occurrence différente de MEDECIN, il faudrait un nombre variable de pointeurs à rajouter à chaque occurrence de MALADES et aussi à celles de MEDECIN (en tête de chaque liste).
Les modèles hiérarchiques et réseaux
-M. HAJJI-
24
Le modèle de données réseau de Codasyl Au fond, cette solution difficile à implémenter ne vise qu’à
modéliser le fait qu’un malade peut être examiné par plusieurs médecins et qu’un médecin peut examiner plusieurs malades et qui n’est autre qu’un lien complexe N:M.
C’est donc pour des raisons liées à des difficultés
d’implémentation qu’une association de type N:M n’a pas été retenue dans le modèle réseau de CODASYL.
Au niveau physique, il y aura pour chaque SET autant de
listes qu’il y a d’occurrences de l’enregistrement propriétaire de ce SET.
On dit que chaque liste est une réalisation du lien L. Ce sera la même chose pour tous les autres SET existant
entre les enregistrements du modèle.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
25
Le modèle de données réseau de Codasyl
Exemple de transformation d’un lien N:M
Deux entités INSTITUTS et MODULES qui sont associées par
un lien N:M : un module peut être enseigné dans 0, 1 ou plusieurs instituts et inversement : un institut d’informatique qui dispense les modules : INF123, M002 et
P014
un institut de mathématiques qui dispense le module : M002 un institut de physique qui dispense les modules : M002 et P014
Les modèles hiérarchiques et réseaux
-M. HAJJI-
26
Le modèle de données réseau de Codasyl
Exemple de transformation d’un lien N:M
La transformation du lien N:M en utilisant la méthode de
l’entité d’intersection donnerait :
Les modèles hiérarchiques et réseaux
-M. HAJJI-
27
Le modèle de données réseau de Codasyl
Exemple de transformation d’un lien N:M
Les modèles hiérarchiques et réseaux
-M. HAJJI-
28
Propriétés d’un schéma conforme au modèle réseau CODASYL
Les notions de SET (ou lien) et de RECORD (ou enregistrement) servent de support principal à la définition du schéma d’une base de données conforme au modèle réseau proposé par CODASYL.
La structure d’un schéma dépend étroitement de
l’application qui a nécessité sa mise en place.
Cependant, il existe un certain nombre de propriétés qui doivent être respectées lors de l’établissement de tout schéma et ce indépendamment de l’application :
Les modèles hiérarchiques et réseaux
-M. HAJJI-
29
Propriétés d’un schéma conforme au modèle réseau CODASYL
D’un enregistrement on peut faire partir autant de liens
différents que l’on veut
Sur un enregistrement peuvent arriver autant de liens que l’on
veut.
Entre deux enregistrements distincts P et M, il peut y avoir plusieurs liens différents allant de P vers M et inversement. Sur un enregistrement, il ne peut y avoir de lien pouvant
boucler sur ce même enregistrement (lien réflexif)
Les modèles hiérarchiques et réseaux
-M. HAJJI-
30
Propriétés d’un schéma conforme au modèle réseau CODASYL
Cas du lien réflexif
Non autorisé dans le modèle réseau CODASYL pour des
raisons purement techniques
très utile au niveau de la modélisation.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
31
Description d’un schéma avec un LDD de type CODASYL
Exemple
Publicité
Un Fournisseur peut fournir 0, 1 ou plusieurs Produits et
inversement un Produit peut être fourni par 0, 1 ou plusieurs Fournisseurs ;
Un Client peut commander 0, 1 ou plusieurs Produits et inversement un Produit peut être commandé par 0, 1 ou plusieurs Clients.
Non conforme aux spécifications du modèle réseau CODASYL
Les modèles hiérarchiques et réseaux
-M. HAJJI-
32
Description d’un schéma avec un LDD de type CODASYL
Deux entités d’intersection: Fournisseurs – Produits : Prix Clients – Produits : Commandes
Cinq entités qui sont : FOURNISSEURS, PRODUITS, CLIENTS, COMMANDES et PRIX. Quatre SET qui sont : FOURNISEUR_PRIX, PRODUIT_PRIX, COMMANDE_PRODUIT et COMMANDE_CLIENT.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
33
Description d’un schéma avec un LDD de type CODASYL
Structure d’un schéma Quatre types de déclaration
La déclaration du nom du schéma qui servira au SGBD à le
distinguer parmi l’ensemble des schémas gérés par le SGBD ;
Une ou plusieurs déclarations d’AREA précisant les noms des zones physiques du support de stockage dans lesquelles seront écrites les occurrences des enregistrements de la base de données. Une ou plusieurs déclarations de type d’enregistrement (ou
RECORD). Un type d’enregistrement est décrit de manière analogue à une description d’enregistrement en COBOL c’est à dire par un nom et un ensemble d’attributs possédant chacun un type (entier, chaîne de caractères, etc.) et un format ;
Une ou plusieurs déclarations de lien (ou SET), spécifiant les associations entre les types d’enregistrement déjà définis.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
34
Description d’un schéma avec un LDD de type CODASYL
Structure d’un schéma
01 02 03
04 05 06 07 08 09 10 11 12 13 14 15 16 17
SCHEMA NAME IS GESTION_VENTES AREA NAME IS AREA NAME IS
COMMANDES_CLIENTS PRODUITS_FOURNISSEURS
RECORD NAME IS CLIENTS PRIVACY LOCK FOR GET FIND IS 266D PRIVACY LOCK FOR MODIFY, INSERT, DELETE, REMOVE, STORE IS CHEF_VENTES LOCATION MODE IS CALC HASH-PROC1 USING Num_Client IN CLIENTS DUPLICATES ARE NOT ALLOWED WITHIN COMMANDES_CLIENTS IDENTIFIER IS Num_Client IN CLIENTS
02 Num_Client 02 Nom_Client 02 Adr_Client
PICTURE 9(6). PICTURE A(12).
03 Numéro 03 Rue 03 Code_Postal 03 Ville
PICTURE 999. PICTURE X(15). PICTURE 9(5). PICTURE A(20).
Les modèles hiérarchiques et réseaux
-M. HAJJI-
35
Description d’un schéma avec un LDD de type CODASYL
Structure d’un schéma
18 19 20 21 22 23 24 25 26
27 28 29 30 31 32 33
RECORD NAME IS FOURNISSEURS LOCATION MODE IS CALC HASH-PROC2 USING Num_Fourn IN FOURNISSEURS DUPLICATES ARE NOT ALLOWED WITHIN PRODUITS_FOURNISSEURS IDENTIFIER IS Num_Fourn IN FOURNISSEURS
02 Num_Fourn 02 Nom_Fourn 02 Adr_Fourn 02 Téléphone
PICTURE 9(6) PICTURE A(15) PICTURE X(20) PICTURE 9(8)
RECORD NAME IS PRODUITS LOCATION MODE IS CALC HASH-PROC3 USING Num_Produit IN PRODUITS DUPLICATES ARE NOT ALLOWED WITHIN PRODUITS_FOURNISSEURS IDENTIFIER IS Num_Produit IN PRODUITS
02 Num_Produit 02 Nom_Produit
PICTURE 9(4). PICTURE X(15).
Les modèles hiérarchiques et réseaux
-M. HAJJI-
36
Description d’un schéma avec un LDD de type CODASYL
Structure d’un schéma
34 35 36 37 38 39 COMMANDE_PRODUIT 40 COMMANDE_CLIENT
41 42 43 44 45 46 PRODUIT_PRIX 47 FOURNISSEUR_PRIX
RECORD NAME IS COMMANDES LOCATION MODE IS SYSTEM DEFAULT WITHIN COMMANDES_CLIENTS 02 Quantité PICTURE 9(3) 02 Num_Produit IS VIRTUAL SOURCE IS Num_Produit OF OWNER OF
02 Num_Client IS VIRTUAL SOURCE IS Num_Client OF OWNER OF
RECORD NAME IS PRIX LOCATION MODE IS SYSTEM DEFAULT WITHIN PRODUITS_FOURNISSEURS
02 Prix_Unité PICTURE 9999V99 02 Num_Produit IS VIRTUAL SOURCE IS Num_Produit OF OWNER OF
02 Num_Fourn
IS VIRTUAL SOURCE IS Num_Fourn OF OWNER OF
Les modèles hiérarchiques et réseaux
-M. HAJJI-
37
Description d’un schéma avec un LDD de type CODASYL
Structure d’un schéma
48 49 50 51 52 53 54 55 56 57
58 59 60 61 62 63 64 65
FOURNISSEUR_PRIX
SET NAME IS ORDER IS SORTED MODE IS CHAIN OWNER IS FOURNISSEURS MEMBER IS PRIX INSERTION IS AUTOMATIC RETENTION IS MANDATORY ASCENDING KEY IS Num_Fourn DUPLICATES ARE NOT ALLOWED SET SELECTION IS THRU FOURNISSEUR_PRIX OWNER IDENTIFIED BY Num_Fourn IN FOURNISSEURS
PRODUIT_PRIX
SET NAME IS ORDER IS SORTED OWNER IS PRODUITS MEMBER IS PRIX INSERTION IS MANUAL ; RETENTION IS OPTIONAL ASCENDING KEY IS Num_Produit, Prix_Unité DUPLICATES ARE NOT ALLOWED SET SELECTION IS THRU PRODUIT_PRIX OWNER IDENTIFIED BY Num_Produit IN PRODUITS
Les modèles hiérarchiques et réseaux
-M. HAJJI-
38
Description d’un schéma avec un LDD de type CODASYL
Structure d’un schéma
COMMANDE_PRODUIT
66 67 68 69 70 71 72 Num_Produit IN PRODUITS
SET NAME IS ORDER IS NEXT MODE IS CHAIN OWNER IS PRODUITS MEMBER IS COMMANDES INSERTION IS MANUAL ; RETENTION IS OPTIONAL DUPLICATES ARE ALLOWED SET SELECTION IS THRU COMMANDE_PRODUIT OWNER IDENTIFIED BY
COMMANDE_CLIENT
73 74 75 76 77 78 79 Num_Client IN CLIENTS
SET NAME IS ORDER IS NEXT MODE IS CHAIN OWNER IS CLIENTS MEMBER IS COMMANDES INSERTION IS MANUAL ; RETENTION IS OPTIONAL DUPLICATES ARE ALLOWED SET SELECTION IS THRU COMMANDE_CLIENT OWNER IDENTIFIED BY
Les modèles hiérarchiques et réseaux
-M. HAJJI-
39
Langage de manipulation de données dans un modèle réseau
FIND
Permet au programmeur de naviguer dans la base de données en tenant compte de sa structure (i.e. au grès des chemins d’accès).
Elle permet de localiser ou se positionner sur une occurrence
d’un enregistrement sans la délivrer au programme.
GET
Permet au programme de lire l’occurrence courante d’un
enregistrement.
STORE
Permet au programme d’insérer une nouvelle occurrence d’un
enregistrement dans la base.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
40
Langage de manipulation de données dans un modèle réseau MODIFY
Permet au programme de modifier une occurrence d’un
enregistrement se trouvant déjà dans la base.
Modifier une occurrence signifie changer la valeur d’un ou de
plusieurs attributs de cette occurrence.
ERASE
Permet de supprimer l’occurrence d’un enregistrement.
CONNECT
Permet d’insérer manuellement l’occurrence d’un enregistrement se trouvant déjà dans la base de données comme membre dans une réalisation ou occurrence d’un SET
DISCONNECT
Permet de supprimer logiquement l’occurrence d’un enregistrement se trouvant déjà dans la base de données comme membre dans une réalisation ou occurrence d’un SET (suppression d’un élément d’une liste circulaire sans le supprimer physiquement de la base de données) .
Les modèles hiérarchiques et réseaux
-M. HAJJI-
41
Le modèle hiérarchique
42
Les modèles hiérarchiques et réseaux
-M. HAJJI-
Introduction Une base de données hiérarchique est une forme de système de gestion de base de données qui lie des enregistrements dans une structure arborescente de façon à ce que chaque enregistrement n’ait qu’un seul possesseur (par exemple, une paire de chaussures n’appartient qu’à une seule personne).
Les structures de données hiérarchiques ont été
largement utilisées dans les premiers systèmes de gestion de bases de données conçus pour la gestion des données du programme Apollo de la NASA.
Cependant, à cause de leurs limitations internes, elles ne
peuvent pas souvent être utilisées pour décrire des structures existantes dans le monde réel.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
43
Introduction
Publicité
Les liens hiérarchiques entre les différents types de données peuvent rendre très simple la réponse à certaines questions, mais très difficile la réponse à d’autres formes de questions. Si le principe de relation « 1 vers N » n’est pas respecté (par
exemple, un malade peut avoir plusieurs médecins et un médecin a, a priori, plusieurs patients), alors la hiérarchie se transforme en un réseau.
Un segment est défini par un nom et un ensemble d’attributs appelés Fields et constitue l’unité d’échange entre la base de données et les programmes d’application. C’est l’équivalent du RECORD vu avec le modèle réseau. La notion de lien ou SET (modèle réseau) n’existe pas.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
44
Caractéristiques principales d’un modèle hiérarchique
Un modèle hiérarchique est un modèle de type
diagramme de structures de données ou de Bachman dans lequel : Tous les liens entre les entités (segments) sont de type 1:N Sur chaque entité ou segment n’arrive qu’un seul lien (arc) De chaque entité ou segment peuvent partir autant de lien
(arcs) qu’on veut
Il existe une entité ou segment particulier appelé racine sur
lequel n’arrive aucun lien (arc).
Les modèles hiérarchiques et réseaux
-M. HAJJI-
45
Caractéristiques principales d’un modèle hiérarchique
Ce modèle n’est pas conforme au modèle hiérarchique à cause des deux arcs qui arrivent sur le segment D
Ce modèle n’est pas conforme au modèle hiérarchique car il ne possède pas de segment Racine sur lequel n’arrive aucun arc.
Ce modèle est conforme au modèle hiérarchique car il possède un segment Racine qui est C et sur chaque segment n’arrive qu’un seul arc.
Ce modèle n’est pas conforme au modèle hiérarchique à cause des deux arcs qui arrivent sur le segment E
Les modèles hiérarchiques et réseaux
-M. HAJJI-
46
Les liens N:M dans un modèle hiérarchique
De part sa définition, le modèle hiérarchique n’accepte pas de lien N:M entre deux entités ni de structure en réseau.
Si la modélisation produit un modèle de données dans lequel existe un ou plusieurs lien N:M, ou bien une ou plusieurs entités sur lesquelles arrivent plus d’un lien (arc), il faudra le transformer pour le conformer aux caractéristiques du modèle hiérarchique.
La transformation d’un lien N:M dans le cadre du modèle hiérarchique repose essentiellement sur la duplication des entités et la création d’entité d’intersection.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
47
Les liens N:M dans un modèle hiérarchique
Transformation par duplication des entités
La duplication des entités consiste à transformer le lien N:M
en deux liens 1:N en créant des copies des entités impliquées dans le lien.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
48
Les liens N:M dans un modèle hiérarchique
Transformation par duplication des entités
Cette méthode engendre une redondance d’information avec toutes les conséquences qui s’en suivent (perte d’espace, risques d’incohérence des données, ...)
Les modèles hiérarchiques et réseaux
-M. HAJJI-
49
Les liens N:M dans un modèle hiérarchique
Transformation par création d’entités d’intersection
Il est aussi possible de transformer un lien N:M entre deux entités en deux liens 1:N grâce à la création d’une nouvelle entité dite entité d’intersection.
On obtient généralement un réseau qui devra être de nouveau
transformé en arborescence par duplication d’entité.
Création d’une entité d’intersection le modèle obtenu est un modèle Réseau
Duplication de l’entité d’intersection
Les modèles hiérarchiques et réseaux
-M. HAJJI-
50
Les liens N:M dans un modèle hiérarchique
Transformation par création d’entités d’intersection
Afin d’éviter la duplication des occurrences des entités dans les deux bases physiques, on peut utiliser la technique dite des entités virtuelles.
Celle-ci consiste à définir réellement une entité d’intersection
pour une des deux entités, et à la déclarer comme entité virtuelle pour l’autre
Les modèles hiérarchiques et réseaux
-M. HAJJI-
51
Schéma conceptuel d’une Base de données hiérarchique
Une base de données hiérarchique peut être vue au niveau conceptuel comme un ensemble d’arbres dont chacun est composé d’entités ou segments et de liens de
type 1:N
respectant les caractéristiques du modèle hiérarchique.
Chaque arbre appelé aussi un PDB (Physical Data Base) sera décrit indépendamment grâce à un programme de description appelé une DBD (Data Base Description program) en utilisant le langage de description de données offert par le SGBD.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
52
Description d’un schéma dans le cas d’un SGBD Hiérarchique
Compte tenu de la structure du schéma conceptuel d’une
base de données hiérarchique, sa description va comprendre pour chaque PDB composant le schéma : La déclaration du nom du PDB qui servira au SGBD de la
distinguer parmi toutes les PDB
une ou plusieurs déclarations de segments, chaque segment
étant caractérisé par son nom, ses attributs (ou FIELDS) et le nom de son segment PARENT.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
53
Description d’un schéma dans le cas d’un SGBD Hiérarchique Deux PDB.
La première PDB est composée des segments : DEPARTEMENTS,
EMPLOYES, ENFANTS et VEHICULES.
La seconde PDB est composée des deux segments : VILLES et
ECOLES.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
54
Description d’un schéma dans le cas d’un SGBD Hiérarchique
Pour le besoin de l’application, il a été jugé utile de
rajouter un arc allant du segment ECOLES de la seconde PDB vers le segment ENFANTS de la première PDB. Ce lien permettra par exemple de répondre à une question du style : « Quels sont les Enfants inscrits dans une école X ».
Les modèles hiérarchiques et réseaux
-M. HAJJI-
55
Description d’un schéma dans le cas d’un SGBD Hiérarchique
1ère PDB
Les modèles hiérarchiques et réseaux
-M. HAJJI-
56
Description d’un schéma dans le cas d’un SGBD Hiérarchique
2ème PDB
Les modèles hiérarchiques et réseaux
-M. HAJJI-
57
La manipulation de données dans un modèle hiérarchique
GET UNIQUE (GU)
Retrouver un enregistrement dont le type a été spécifié. Cette opération est particulièrement utilisée pour accéder à la racine d’une arborescence connaissant la valeur de la clé d’un enregistrement. GET NEXT (GN).
Se déplacer dans une arborescence en utilisant une fonction de
type successeur ou suivant d’un nœud.
C’est une opération de recherche purement séquentielle qui
consiste donc à explorer la liste des nœuds.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
58
La manipulation de données dans un modèle hiérarchique
GET NEXT WITHIN PARENT
Se déplacer dans une arborescence en utilisant une fonction de
type successeur ou suivant d’un nœud mais en se limitant uniquement à des nœuds qui ont le même père.
INSERT, DELETE et REPLACE
Insérer une nouvelle occurrence d’un nœud (ou segment), supprimer une occurrence d’un nœud, remplacer une occurrence.
Les modèles hiérarchiques et réseaux
-M. HAJJI-
59
Merci…
Les modèles hiérarchiques et réseaux
-M. HAJJI-
60