Chapitre 06 - Modèle Hiérarchique 06 - Modèle... · GPA775 Chapitre 6 - Modèle hiérarchique 22 Transformation d’une relation ternaire Ø La transformation des relations d’ordre

Chapitre 6

Modèle Hiérarchique

GPA775 Chapitre 6 - Modèle hiérarchique 2

Contenu du chapitre

Les points abordés seront les suivants:

ØConcepts de base du modèle hiérarchique

ØOrganisation en arbre

ØTransformations E-R vers BDH

ØManipulation des données des BDH


Concepts de base du modèle hiérarchique

ØModèle logique orienté enregistrement;ØLes données sont représentées par des

enregistrements;• qui sont une collection de champs (attributs).

ØLes enregistrements sont associés par des relations qui sont des liens.

• Les liens associent que 2 enregistrements à la fois.Øsemblable au modèle réseau, mais diffère par son

organisation en arborescences;ØLe plus courant SGBD: IMS de IBM (banques,

compagnies d’assurances, agences gouvernementales)


Concepts de base du modèle hiérarchique

Exemple de BD hiérarchique…

nom

NAS rue

ville

Client

numéro

solde

CompteCliCom

SquareLowman Dallas

305 500

DownridgeCamp Garland BaysideKahn Plano

226 336 177 205 155 62


Organisation en arbre

Une base de données hiérarchique (BDH) est composée d'une collection d'arbres. Ces arbres ont les caractéristiques suivantes:Øils ont une racine virtuelle,

w qui sert de structure initiale,w qui conserve les pointeurs vers les sous arbres.

A

B1 B2 Bn

C1 Cm Cl

. . .

. . .. . .

La racine virtuelle “A” est un nœud

bidon.



Øils ne comportent pas de structure cyclique,• Modèle réseau: les données structurées sont

réparties de façon quelconque sur leur graphe.

• Modèle hiérarchique : les données sont répartiessuivant un arbre issu d'une racine définie. w il n'existe pas de pointeur de

Ci → A, donc pas de structure cyclique.

A

B1 B2 Bn

C1 Cm Cl

. . .

. . .. . .



Øils contiennent que des relations 1 vers 1 ou 1 vers N

parent↑

enfant

A

B1 B2 Bn

C1 Cm Cl

. . .

. . .. . .



Øle contenu d'un enregistrement peut être répété:• dans le même arbre,

• dans plusieurs arbres;

Les inconvénients majeurs provenant de cette répétition sont :

• le risque d'inconsistances lors de la mise à jour,

• le gaspillage de la mémoire.

A

B1 B2 Bn

C1 Cm Cl

. . .

. . .. . .


Transformations E-R vers BDH

Relations binaires sans attributsRelation 1 vers 1 :

ruenom ville

numéro position

client

compte

nom

rue

ville

Client

numéro

position

CompteCliCom1 N1

Représentation de la cardinalité 1:1


Relations binaires sans attributs

Relation 1 vers n :

nom

rue

ville

Client

numéro

position

CompteCliCom1 N

ruenom ville

numéro position

client

compte

C’est la flèche qui différencit une relation 1:1 et 1:N.


Exemple de base de données avec relation 1:N

SquareLowman Dallas

305 500

DownridgeCamp Garland BaysideKahn Plano

226 336 177 205 155 62

Dans votre livre, ce n’est pas une présentation 1 vers N


Relations binaires sans attributsRelation n vers n :

Ø Il y a plusieurs solutions possibles qui dépendent

• du type de consultation à effectuer;

• du degré de ressemblance de la structure d'arbre avec le diagramme E-R original.

Procédure pour les relations n vers nØ Il faut créer deux arbres puisque seules les relations 1 vers 1 et 1

vers n sont autorisées dans le modèle hiérarchique.

1.Création de deux arbres T1 et T2 constitués chacun des deux enregistrements:

• Arbre T1 dont la racine est le premier enregistrement

• Arbre T2 dont la racine est le second enregistrement

2.Création des liens n vers 1 ( où 1 représente la racine)


Exemple de transformation N:N

nom

rue

ville

Client

numéro

position

CompteCliComN N

ruenom ville

numéro position

client

compte ruenom ville

numéro position

client

compte

arbre T1 arbre T2


Instanciation des arbres T1 (a) et T2 (b)


Relations binaires avec attribut

Relations 1 vers n• plus compliquées car le lien ne peut avoir d'attribut;

Procédure :

1. créer un nouveau type d'enregistrement intermédiaire avec un champ approprié;

2. créer les 2 liens n vers 1 entre le nouvel enregistrement et les 2 enregistrements originaux.



Exemple de transformation 1 vers N

nom

rue

ville

Client

numéro

position

CompteCliCom1 N

date

ruenom ville

numéro position

client

compte

date date


Instanciation de la relation 1 vers N avec attribut

ruenom ville

numéro position

client

compte

date date



Relations 1 vers 1

Ømême chose que pour 1 vers n;

Øsauf que les liens créés sont de type 1 vers 1.

ruenom ville

numéro position

client

compte

date date



Relations n vers n :Ø nombreuses solutions;Procédure générale:

1. Créer deux structures d'arbre avec l'attribut de la relation comme attribut intermédiaire en utilisant la même procédure que pour 1 vers n :T1: premier enregistrement comme racine,

T2: second enregistrement comme racine.2. Créer deux liens n vers 1

(voir figure page suivante)


Exemple de transformation d’une relation N:N avec attribut

ruenom ville

numéro position

client

compte

date date

arbre T1 arbre T2

ruenom ville

numéro position

client

compte

date date

nom

rue

ville

Client

numéro

position

CompteCliCom1 N

date

N


Instanciation d’une structure arborescente à relation n vers n avec attribut.


Transformation d’une relation ternaire

Ø La transformation des relations d’ordre générale est une tâche complexe.

Procédure :Ø Créer autant de répliques d'enregistrements que

nécessaire et autant d'arbres qu'il convient.

Note : toutes les permutations sont permises mais sont dictées par le type de recherche que l'utilisateur entend effectuer. Plus l'information utile se rapproche de la racine, plus rapide sera la recherche.Ainsi, si nous avons 3 relations n vers n, nous pouvons créer de 3 à 9 arbres!


Exemple de transformation d’une relation ternaire

Ici, les requêtes importantes sur ce modèle sont de retrouver les clients appartenant à une agence et les comptes appartenant à une agence.

Il n’est pas utile de maintenir un arbre client-agence-compte, puisque peu de requêtes de ce genre peut être utile.

Alors, nous allons créer deux arbres : T1 et T2

nom

NAS rue

ville

Client

numéro

solde

CompteCCA

nom avoir

ville

agence



Voici l’arborescence (T1 et T2) correspondant à la relation ternaire de la page précédente :

ruenom ville

numéro position

client

compte

arbre T1 arbre T2

ruenom ville

numéro position

client

compte

avoirsnom ville agence avoirsnom ville agence

retrouver les comptes

appartenant àune agence

retrouver les clients

appartenant àune agence




Transformations des relations multiples

Tous les exemples précédents présentaient des relations uniques entre 2 ou plusieurs entités:

Østructure d'arbre à racine uniqueSi le diagramme E-R comporte plusieurs relations:

Øon ne peut créer d'arbres à racine unique, car ces arbres ne respecteront pas la définition BDH.

• i.e. on aura des relations 1 vers n dirigées vers la racine !

nom

avoir

ville

Agence

numéro

position

CompteAgeCom

nom

rue

ville

ClientCliCom



Pour les relations multiples la procédure générale est :

1. répliquer les enregistrements " racine ",

2. créer autant d'arbres à racine unique qu'il sera nécessaire

Arborescence correspondant à l’exemple précédant:

numéro position compte

arbre T1arbre T2

ruenom ville

numéro position

client

compte

avoirsnom ville agence



Si le modèle E-R renferme un cycle (A ↔ B ↔ C ↔ A), le modèle hiérarchique ne peut représenter cette topologie àl'aide d'un seul arbre.

Il faudra créer deux arborescences pour implanter ce type de modèle.

A B

C

A

B

C

A

C

B


Enregistrements virtuels

REMARQUE:La structure hiérarchique comporte un problème important de redondance inhérent à sa structure. Ø Sur la figure 127 des notes de cours (p.136), nous

remarquons le dédoublement de l'information dans les deux arbres:

• Dans l’arbre T1, le compte 347 est répété

• Dans l'arbre T2, se sont les clients Katz et Doner qui y sont répétés.

• De plus, dans les 2 arbres, nous retrouvons la même information.

Cette redondance apporte les inconvénients suivants:Ø inconsistance des données à long terme Ø perte d'espace



Pour solutionner le problème de redondance de l'information, on peut utiliser des enregistrements virtuels.Avantages:

• ne stocke pas de valeurs redondantes, mais plutôt un pointeur indiquant l'adresse d'un enregistrement physique.

Procédure générale :Ø Lorsqu'un enregistrement doit être répliqué au sein de

plusieurs arbres :• On conserve un seul exemplaire dans l'un des

arbres,• Pour toutes les répliques nécessaires, on crée un

enregistrement virtuel pointant vers l'exemplaire unique.



Exemple : ruenom ville client

compte virtuel

numéro position

client virtuel

compte

Notez que la structure obtenue par l’utilisation des enregistrements virtuels est très proche du modèle réseau.


Manipulation des données des BDH

ØLe modèle hiérarchique utilise le langage commercial DL/1 de IMS ("Information Management System") de IBM;

Ø Il est probablement le système le plus répandu sur les gros ordinateurs (Mainframe) qui sont "encore" sur le marché;

ØLa notation est simplifiée (très peu convivial);

ØLes commandes sont spécifiques;

ØElles peuvent être intégrées dans un langage hôte (ex: Pascal)



Fonctions principales permettant l’accès au sein d’un arbreØ GET: extraction des données de la base.

• GET FIRST : localise le premier enregistrement.

• GET NEXT : localise le suivant.

GET FIRST/NEXT “ type d'enregistrement ”WHERE “ condition ”

où WHERE permet de poser en option un prédicat =, $, #, etc.

Ø INSERT : insertion d'un nouvel enregistrement.INSERT “ type d'enregistrement ”WHERE “ condition ”



ØREPLACE : modification de l'enregistrement courant.

• On l’utilise avec GET HOLD FIRST/NEXTw signifie au système que l'extraction sera pour une

modification.

ØDELETE : élimination d'un enregistrement.

• On l’utilise également avec GET HOLD FIRST/NEXT.


Zone programme utilisateurComme pour le modèle réseau, on retrouve dans la zone programme :

Øgabarits d'enregistrement : un gabarit pour chacun des enregistrements,

Øpointeurs courants : un pointeur par arbre de la BDH qui conserve l'adresse du dernier enregistrement traité par le programme,

Øun indicateur d'état : indique le succès (DB_status =0) ou l'insuccès (DB_status =1) de l'opération.

Voir figure 107, p.122, seuls les pointeurs courants changent.


Exemple de rechercheSoit l’arborescence suivante etl’instanciation correspondante, trouvez la liste des comptes dont le solde est supérieur à 500$.La recherche d’un enregistrement s’effectue en pré-ordre, e.i. que la recherche débute à la racine et en épuise les branche de gauche àdroite.Résultat : 522, 561, 533

ruenom ville

numéro position

client

compte

avoirsnom ville agence

Bay RidgeFleming Brooklyn

522 750

FlatbushFreeman Brooklyn AirportBoyd Queens

533 600 409 27 622 107

100 000 000Parkview Brooklyn 150 000 000Seashore Queens

561 9953


Exemple de rechercheTraduction de la requête en langage de manipulation de BDH:Trouver la liste des comptes dont le solde est supérieur à500 $.

get first comptewhere compte.solde > 500

while DB-status = 0 dobegin

print compte.numéroget next comptewhere compte.solde > 500

end


Exercice complémentaire (pas dans les notes)

À partir du modèle E-R suivant, établir le diagramme hiérarchique équivalent.

CAMION LIVRAISON

PRODUITCONDUCTEUR

EFFECTUE

CONTIENTAPPARTIENT

NO_SÉRIE

NO_PERMIS

NO_SÉRIENOM

NO

PRÉNOM NOM

ADRESSEMODÈLE

CAPACITÉ

N

N

N

1

1

1

DATE

QUANTITÉ

Documents

Chapitre 06 - Modèle Hiérarchique 06 - Modèle... · GPA775 Chapitre 6 - Modèle hiérarchique 22 Transformation d’une relation ternaire Ø La transformation des relations d’ordre