Institut National de formation en Informatique

Cours de bases de données

Réalisé par: Groupe n° 1

Année Universitaire: 2007/2008

Introduction Les Bases de Données occupent aujourd'hui une place de plus en plus

importante dans les systèmes informatiques,et sont structurées d’après des modèles

Un modèle (informatique) est une abstraction dont les priorités assurent:

- l’intégrité : toute action sur le modèle se répercute sur les données.- La progammabilité de la structure proposée.- la cohérence : les données ne sont pas

contradictoires,manquantes,floues,incertaines…

Il existe plusieurs types de bases : hiérarchiques, réseaux, relationnelles, objet, semi structurées...

L’objet de notre exposé d’aujourd’hui est le 1er modèle créé « Le modèle hiérarchique » .

Définition

Le premier système de base de données a été conçu pour la gestion des données du programme Apollo (de IBM).

Une base de données hiérarchique est une base de données dont le système de gestion lie les enregistrements dans une structure arborescente où chaque enregistrement n'a qu'un seul possesseur.

Exemples IMS:c’est un SGBD très répandu dans les applications de

production, créé par IBM en 1966 pour le programme APOLLO.

(sert toujours à près de 200 millions d’utilisateurs par jour).

System 2000(1967) sur divers materiels:IBM,UNIVAC,CDC.

ADABAS,(AG software,fin des années 70),fonctionne toujours aujourd’hui et réalise des recherches à grande vitesse.

Concepts Les concepts de base du modèle

hiérarchique sont :

1/ le champ: Plus petite unité de données

possédant un nom.

2/ le segment (article) :

"C’est une collection de champs, portant un nom et constituant l'unité d'échange entre la base de données et les applications".

Les champs d'un segment sont tous au même niveau, si bien qu'une occurrence de segment est parfois qualifiée d'article plat.

un segment a un champ discriminant appelé CLE.

la valeur de la clé permet alors de déterminer une occurrence unique dans le segment.

les segments sont reliés par des liens de 1 vers N qui à un segment père font correspondre N segments fils.

ainsi, un segment possède en général plusieurs segments descendants mais un seul et unique segment père.

3/Les liens:

Ce sont des liens de 1 vers N,orientés du père vers les fils(de haut en bas),ces liens ne sont pas nommés.

4/La racine:

C’est le segment qui se trouve au sommet de la hiérarchie,

elle ne possède pas de père.

produit

fournisseur dépôt

5/La feuille:

Segment ne possédant pas de fils.

produit

fournisseur dépôt

6/L’arbre de segments(occurrence hiérarchique):

"Collection de segments reliés par des associations père-fils organisée sous forme d'une hiérarchie".

chaque arbre possède un segment racine unique, des segments internes et des segments feuille, le niveau d'un segment caractérise sa distance de la racine.

7/la base de donnees hiérarchique:

Une base de données hiérarchiques peut étre considérée comme un ensemble d’arbres,encore appelé foret,dont les nœuds sont des segments,les arbres sont en principe indépendants.

Règles

R1: Entre toute paire de type

enregistrement (Ri,Rj) il y a au plus un lien Li,j.

UNIVERSITE

FACPHARMACIE

FAC MEDECINE

Ex:

UNIVERSITE

FAC MEDECINE

UNIVERSITE

FACPHARMACIE

FAC MEDECINE

R2:

Aucun lien n’est possible entre deux enregistrements(Ri,Ri:de meme niveau).

FAC MEDECINE

FACPHARMACIE

Ex:

UNIVERSITE

FAC MEDECINE

FACPHARMACIE

UNIVERSITE

FACPHARMACIE

FAC MEDECINE

R3: Chaque lien Lij correspond à une

associaton 1-N (parent-enfant).

Ex:

Université

Chef.depart

Département

Etudiant Professeur

Cours Projet

R4: Une entité n’a au plus qu’un parent.

Ex:

departement

Chef.depart chercheur

projet local

laboratoire

departement

Chef.depart chercheur

projet local

laboratoire laboratoire

laboratoire

Modèle conceptuel associé

Racine

A B

C D

Pour un nœud donné ,un seul nœud père. Chaque nœud est une famille d’objets.

Les données sont représentées sous forme d’une structure arborescente d’enregistrements. Ceci entraîne le fait que leur manipulation se fait exactement de la même façon avec laquelle on manipule les fichiers structurés en arbres.

Le principe de la manipulation d'une base hiérarchique (nous prenons ici l'exemple de DL1 de IBM) consiste à parcourir en profondeur la structure arborescente : on part de la racine et on visite successivement tous les fils depuis le fils gauche jusqu'au droit.

Manipulation

Considérons la base hiérarchique suivante :

1. Accès direct :Principe : Trouver toutes les caractéristiques d’un segment donné par son

chemin d’accès complet.

Exemple :Caractéristiques d’une pièce dont on donne l’identifiant :GET UNIQUE SERVICE PIECE (NUMPIE= identifiant)

Résultat : On indique le chemin hiérarchique complet. S'il existe plusieurs

pièces portant le même numéro, c'est la première rencontrée qui est sélectionnée.

2. Accès séquentiel :

Principe : Parcourir tous les descendants d’un père donné par son identifiant et

son chemin d’accès.

Exemple:GET UNIQUE SERVICE PIECE (NUMPIE=identifiant) FOURNISSEUR while DB-STATUS=0 do begin GET NEXT FOURNISSEUR EndRésultat : Caractéristiques de tous les fournisseurs à partir de la pièce dont on

précise l’identifiant.

3. Accès séquentiel sous un même parent :Principe : parcourir les descendants d’un père donné par son identifiant et son chemin

d’accès, et donner toutes leurs propriétés.

Exemple : GET UNIQUE SERVICE (NOMSER=SECURITE)PIECE(NUMPIE=identifiant) while DB-STATUS=0 do begin GET NEXT WITHIN PARENT FOURNISSEUR End

Résultat : Noms et adresses des fournisseurs de la pièce dont on donne l’identifiant pour

le service SECURITE.

3. Insertion :

Objectif : insérer un nouvel élément c'est-à-dire un

nouveau fils pour un pére donné par sa clé.Exemple :INSERT SERVICE PIECE (NUMPIE=identifiant)

FOURNISSEUR

Résultat : Insérer un nouveau fournisseur pour la pièce

dont on donne l’identifiant

4. Suppression :

Objectif : Suppression d’un segment dont on spécifie le

chemin, par conséquent la suppression de tous ses descendants.

Exemple : GET HOLD UNIQUE SERVICE

PIECE(NUMPIE=identifiant)DELETERésultat : Supprimer la pièce dont on spécifie la clé ainsi

que ses descendants.

5. Remplacement :

Objectif : effectuer des modifications sur un segment

donné par son chemin complet.Exemple : GET HOLD UNIQUE SERVICE PIECE (NUMPIE=clé) Effectuer la modification dans la zone E/SREPLACERésultat : Modifier la désignation de la pièce donnée par

clé.

Forme linéaire d’un schéma hiérarchique :• Certains langages de manipulation

reposent sur une exploration linéaire.• Cette exploration est donnée par le

parcours préordre de l’arbre de segments.

Ex:

Le parcours correspondant est:

A,B,F,G,H,C,I,D,E.

A

B C D E

F G H I

Exemple de description avec IMS/DL1 :1 DBD NAME=SERVICEDB, ACCESS=HDAM 2 SEGM NAME=SERVICE, BYTES=30 3 FIELD NAME=(NOMSER, SEQ), BYTES=15,

START=1 4 FIELD NAME=RESPONSABLE, BYTES=15,

START=16 5 SEGM NAME=PIECE, BYTES=40,

PARENT=SERVICE 6 FIELD NAME=(NUMPIE, SEQ), BYTES=10,

START=1 7 FIELD NAME=DESIGNATION, BYTES=30,

START=11 8 SEGM NAME=FOURNISSEUR, BYTES=40,

PARENT=PIECE 9 FIELD NAME=(NOMFOUR, SEQ, M),

BYTES=15, START=1 10 FIELD NAME=ADRESSE, BYTES=25,

START=16 11 SEGM NAME=EMPLOYE, BYTES=45,

PARENT=SERVICE 12 FIELD NAME=(NUEMP, SEQ), BYTES=10,

START=1 13 FIELD NAME=NOM, BYTES=25, START=11 14 FIELD NAME=SALAIRE, BYTES=10,

START=36 15 DBDGEN 16 FINISH 17 END

Interprétation:

Lignes 1 à 7 : Déclaration des différents segments.

Lignes 8 à 10 :description du segment FOURNISSEUR.

Lignes 11 à 14 : description du segment EMPLOYE.

Lignes 15 à 17 : indication de fin de description et fin de programme.

Avantages1/Simple.2/Implémentation facile(juste des relations 1-N).3/Rapidité d’accès et de lecture.4/L’accès aux données se fait de manière

prédictible dans le modèle hiérarchique

optimisation par le SGBD.

5/Efficace pour des données très structurées.

Inconvénients

1/Redondance: Le modèle est incapable de

représenter les liens N:M(possible de les représenter par

la duplication de données).

2/Anomalie de destruction : la destruction d’un nœud cause

l’élimination de ses successeurs:

tree traversal : efface les données ainsi que la structure:si on ne permet pas la valeur « NULL »(IMS).

general selection : efface les données mais garde la structure(SYSTEM 2000).

3/Anomalie d’insertion:

impossible d’insérer des données sans successeur . Il faut trouver un nœud parent pour

ajouter ou insérer des enregistrements (sauf si c’est à la racine).

4/Les requêtes sont limitées aux relations explicitement définies dans la hiérarchie:

Les critères de recherche sont très restreints.

5/S’applique mal aux questions géographique:

où les relations sont multiple sens et où les requêtes ne sont pas connues à l’avance .

Conclusion Le modèle hiérarchique a été longtemps considéré comme

le seul modèle permettant aux SGBD d’atteindre des performances exigées en production, et possédant la performance de traiter rapidement des informations organisées sous formes d’une hiérarchie stricte.

Certains d’entre eux autorisaient les liens entre arbres pour permettre de modéliser des associations de 1 vers N sans avoir a dupliquer des segments. tout segment d’un arbre peut alors pointer vers un segment d’un autre arbre. cela peut être limité à un seul pointeur par segment:on parle ici de lien frère, pour distinguer ce lien du lien vers le fils. on aboutit alors à des modèles hiérarchiques étendus dont les possibilités se rapprochent de celles du modèle réseau, dont la nécessité fut ressentie après constatation des restrictions et des inconvénients du modèle hiérarchique.