UNIVERSITÉ ASSANE SECK DE ZIGUINCHOR
UFR DES SCIENCES ET TECHNOLOGIES
DÉPARTEMENT D’INFORMATIQUE
CHAPITRE III
OPTIMISATION DE SCHÉMAS
RELATIONNELS
ANNÉE ACADÉMIQUE : 2022 – 2023
FILIÈRE : INGÉNIERIE INFORMATIQUE
NIVEAU : LICENCE 3
SEMESTRE : 5
DR SERIGNE DIAGNE
PLAN DU COURS
Introduction
I. Les dépendances entre attributs
1. Dépendance fonctionnelle
2. Dépendance multi-valué
3. Dépendance de jointure
II. Formes normales
1. Troisième forme normale (3FN)
2. Forme normale de Boyce-Codd (FNBC)
3. La quatrième forme normale (4FN)
4. La cinquième forme normale (5FN)
III. Axiomes d’Armstrong
IV. Fermeture d’un ensemble d’attributs et Couverture minimale
V. Couverture minimale d’ un ensemble de dependences fonctionnelles
VI. Décomposition d’un schéma relationnel
2
VII.Cas pratique
INTRODUCTION
Une base de données est une collection de données cohérentes et
structurées ;
La structuration des données au sein de la base permet :
d’uniformiser leur saisie ;
de standardiser leurs traitements ;
de contrôler leur validité ;
de les partager entre plusieurs traitements.
3
INTRODUCTION
L’optimisation d’un schéma relationnel dépend en grande partie de la bonne
conception de son schéma ;
Elle consiste à faire de sorte à avoir la meilleur structure possible (une
structure performante, cohérente, sans perte de données ni de redondance) ;
Elle passe par la normalisation de ses relations ;
Normaliser un schéma relationnel consiste à normaliser toutes ces relations :
ses relations doivent respecter des FN telles que la 1FN, la 2FN, la 3FN, la FNBC,
etc. ;
pour éviter les redondances, chaque relation doit également respecter la 4FN et la
5FN. 4
I. LES DÉPENDANCES ENTRE ATTRIBUTS
En plus des dépendances déjà vues (Dépendance Fonctionnelles), on va
introduire dans ce chapitre deux autres types de dépendances entre attributs
d’une relation :
Les dépendances multi-valuées ;
Les dépendances de jointure.
5
I. LES DÉPENDANCES ENTRE ATTRIBUTS
I. 1. DÉPENDANCES FONCTIONNELLES
Définition :
Il y’a DF entre deux attributs d’une relation si à chaque valeur de l’un
correspond une et une seule valeur de l’autre : Soit R(X, Y, Z, T, U, V)
Source X, Y T, U, V But
DF simple X Z, T, U, V
DF composée X, Y, Z T, U
Remarque :
Soit la relation R (X, Y, Z) :
Si X Y et Y Z alors X Z ;
Si X Y et X Z Alors X Y, Z 6
I. LES DÉPENDANCES ENTRE ATTRIBUTS
I. 1. DÉPENDANCES FONCTIONNELLES
Graphe minimale :
Si F est l’ensemble des DF entre les attributs d’une relation R, on appelle
graphe minimale de R le sous-ensemble de F contenant les DF
élémentaires non déductibles dont le but contient un seul attribut et tels
que toutes les DF appartenant à F peuvent en être déduites.
7
I. LES DÉPENDANCES ENTRE ATTRIBUTS
I. 2. DÉPENDANCES MULTI-VALUÉES
Définition :
X multi-détermine Y (X Y) si à chaque valeur de X correspond plusieurs
valeurs de Y indépendamment des autres attributs de la relation. Avec :
X et Y des sous-ensembles de {R1, R2, R3, …, Rp} ;
R (R1, R2, R3, …, Rp) une relation.
Remarque :
Soit R (X, Y, Z), alors X et Y sont liés par une dépendance multi-valuée si pour tous
enregistrements (x0, y1, z1) et (x0, y2, z2) dans l’instance de R les enregistrements (x0, y1,
z2) et (x0, y2, z1) appartiennent aussi à l’instance de R.
Si dans la relation R (X, Y, Z), X Y, alors X Z, On note : X 8
Y|Z
I. LES DÉPENDANCES ENTRE ATTRIBUTS
I. 2. DÉPENDANCES MULTI-VALUÉES
Exemple :
1. Soit la relation Etudiant (Nom, AnneeNaiss, VilleNaiss) :
Si (Moussa, 2009, Diourbel) et (Moussa, 2010, Dakar) sont des Etudiants inscrits
Alors (Moussa, 2010, Diourbel) et (Moussa, 2009, Dakar) sont aussi des Etudiants inscrits
Nom AnneeNaiss et Nom VilleNaiss
Alors Nom AnneeNaiss | VilleNaiss
2. Soit la relation Classe (Niveau, Serie, Effectif)
Si (Terminal, S2, 60) et (Terminal, L2, 75) sont des classes qui existent
Alors (Terminal, L2, 60) et (Terminal, S2, 75) sont aussi des classes qui existent
Classe Serie et Classe Effectif
Alors Classe Serie | Effectif 9
I. LES DÉPENDANCES ENTRE ATTRIBUTS
I. 3. DÉPENDANCES DE JOINTURE
Définition : Soient :
R (R1, R2, R3, …, Rp) est une relation ;
A1, A2, …, Am des sous-ensembles non disjoints de {R1, R2, R3, …, Rp}.
Il existe une dépendance de jointure notée *{A1, A2, …, Am} si :
R = ΠA1(R) Π A2 (R) Π A3 (R) … Π Ap(R)
Remarque :
Les dépendances multi-valuées sont des cas particuliers de dépendances de jointure ;
Si une relation R (X, Y, Z) vérifie X Y et donc X Z elle satisfait la
dépendance de jointure *{XY, XZ}.
10
I. LES DÉPENDANCES ENTRE ATTRIBUTS
I. 3. DÉPENDANCES DE JOINTURE
Exemple :
Avec la relation Etudiant (Nom, AnneeNaiss, VilleNaiss) on a la dépendance de jointure
*{A1, A2}
Avec A1 = {Nom, AnneeNaiss} et A2 = {Nom, VilleNaiss}
Ainsi Etudiant = ΠA1(Etudiant) Π (Etudiant)
A2
Etudiant = ΠNom, AnneeNaiss(Etudiant : E1) E1.Nom=E2.Nom Π Nom, VilleNaiss (Etudiant : E2)
11
II. FORMES NORMALES (FN)
II. 1. TROISIÈME FORME NORMALE (3FN)
Définition :
Une relation est en troisième forme normale s’il n’y a pas de dépendance
fonctionnelle :
d’une partie d’une clé vers un attribut non clé ;
entre attributs non clé.
Remarque :
Une relation en 3FN peut comporter des redondances.
12
II. FORMES NORMALES (FN)
II. 2. FORME NORMALE DE BOYCE-CODD (FNBC)
Définition :
Une relation est en forme normale de Boyce-Codd (FNBC) si et
seulement si ses clés candidates sont les uniques sources de DF, c’est-à-
dire :
Pour toute DF A B telle que B n’est pas inclus dans A ;
Alors A est une clé candidate.
Remarque :
Toute dépendance fonctionnelle en FNBC est en 3FN
13
II. FORMES NORMALES (FN)
II. 3. QUATRIÈME FORME NORMALE (4FN)
Définition :
Une relation est en 4FN si les seules dépendances sont celles dans lesquelles
une clé candidate multi-détermine un attribut.
On dit également qu’une relation est en 4FN si :
elle est en FNBC et ;
elle ne contient pas de Dépendance Multi-valuée.
Remarque :
Toute dépendance en 4FN est également en FNBC ;
Les dépendances fonctionnelles sont des cas particuliers de dépendance multi-valuée.
14
II. FORMES NORMALES (FN)
II. 4. CINQUIÈME FORME NORMALE (5FN)
Définition :
Une relation est en 5FN si toutes ses dépendances de jointure sont
impliquées par les clés
Remarque :
Toute relation en 4FN qui n’est pas en 5FN peut être remplacée par des
relations en 5FN
15
III. AXIOMES D’ARMSTRONG
Soient A, B, C des sous-ensembles quelconques d’attributs d’une relation
R et AB l’union de A et B, les axiomes d’Armstrong sont les suivantes :
Réflexivité : si B est inclus dans A, alors A → B ;
Augmentation : si A → B, alors AC → BC ;
Transitivité : si A → B et B → C alors A → C.
A partir des axiomes d’Armstrong, nous pouvons déduire :
Union : X → Y et X → Z, alors X → YZ ;
Pseudo-Transitivité : X → Y et YW → Z, alors XW → Z ;
Décomposition : X → Y et Z inclus dans Y, alors X → Z.
16
IV. LA FERMETURE D’UN ENSEMBLE D’ATTRIBUTS
Définition :
La fermeture d’un ensemble d’attributs X (notée X+) d’une relation R
représente l’ensemble des attributs de cette relation qui peuvent être
déduits de X à partir d’une famille de Dépendances Fonctionnelles F en
appliquant les axiomes d’Armstrong.
Remarque :
Y est inclus dans X+ si et seulement si X → Y ;
La fermeture d’un ensemble d’attributs X sous F contient les attributs de X et
tous les attributs dans le but d’une DF de F dont la source contient des attributs
17
inclus dans X+
V. LA COUVERTURE MINIMALE D’UN ENSEMBLE DE DF
Définition :
La couverture minimale de F contient les DF qui peuvent être déduites
d’un ensemble minimale F' inclus dans F après élimination des DF
redondantes.
18
VI. LA DÉCOMPOSITION D’UN SCHÉMA RELATIONNEL
Objectif :
La décomposition d’un schéma relationnel a pour objectif de remplacer
un schéma R par un ensemble de schémas {R 1, R2, R3, …, Rn} tels que
R = R 1 U R 2 U R 3 U … U R n.
Elle permet :
d’éliminer les redondances et les anomalies de mise à jour ;
d’optimiser le schéma d’une relation ;
de faciliter les tâches d’administration.
Remarque : 19
Les Schémas Ri (1 <= i <= n) ne sont pas obligatoirement disjoints ;
VII. EXERCICE D’APPLICATION
Soit la base de données Usine dont le schéma relationnel est le suivant :
Usine (NomMP, TypeMP, QteMP, PUMP, NomProd, TypeProd, QteProd,
PUProd, Matricule, NomOuv, Prenom, Age, Specialite, Pourcentage,
DateFabrication, QteFabriquer)
1. Donnez la fermeture de {NomMP}, {Age}, {Matricule}
2. Donnez la couverture minimale de cette relation
3. Décomposez cette relation et proposez un schéma optimisé de la base
de données Usine.
20
