Matière : Bases de Données (BD)
Niveau : Licence 2ème Année (L2)
Conception de bases de données relationnelles :
La normalisation
Pr. F. Magra-Benchikha
Faculté : NTIC Institut : TLSI
[Link]@[Link]
Université Constantine 2 2022/2023 Semestre 2
Plan
1. Problématique
2. Les dépendances fonctionnelles (DF)
2.1. Définition
2.2. Types de dépendance fonctionnelles
2.3. Propriétés des dépendances fonctionnelles
2.4. Fermeture transitive et couverture minimale
2.5. Graphe de dépendances fonctionnelles
2.6. Clé minimale de relation
2.7. Application1
3. La normalisation
3.1. Degrés de normalisation
3.2. Les formes normales (1FN, 2FN, 3FN)
3.3. Schéma relationnel normalisé
3.4. Décomposition de relation (Algorithme de synthèse)
3.5. Application 2
3.6. Application 3
Université Constantine 2 Pr. F. Magra-Benchikha 2
Conception de BDs relationnelles/ Problématique
On désire concevoir une base de données relationnelle gérant le stock des produits dans des
dépôts.
• On a le dictionnaire de données et les règles de gestion suivantes :
Règles de gestion :
• Chaque produit, identifié par un code, possède un nom et un prix
• Chaque dépôt est localisé à une certaine adresse
• Un produit peut être stocké dans plusieurs dépôts
• Dans un dépôt sont stockés plusieurs produits
• Un produit est stocké dans un dépôt avec une certaine quantité
Université Constantine 2 Pr. F. Magra-Benchikha 3
Conception de BDs relationnelles/ Problématique
On considère les deux propositions de conception suivantes :
Proposition 1 : La base de données est représentée par une seule table (relation) contenant
tous les attributs. On appelle cette table la relation universelle (RU).
RU (code_prod, nom_prod, prix, code_dep, adr_dep, qté)
Soit l'extension suivante de RU :
Problèmes :
il y'a de la redondance d'information qui engendre les anomalies suivantes :
1. Anomalie de mise à jour : si on change le prix d'un produit, on doit le faire dans toutes
les lignes de son stockage dans les différents dépôts,
2. Anomalie d'insertion : on ne peut pas ajouter un nouveau dépôt (code et adr) vide
(sans produits stockés) car la clé primaire de la relation est (code_prod, code_dep)
3. Anomalie de suppression: si on supprime le dernier produit du dépôt D2 (soit le
deuxième tuple dans l'extension de la bases ci-dessus), on perd toute information
(code et adr) concernant ce dépôt.
Université Constantine 2 Pr. F. Magra-Benchikha 4
Conception de BDs relationnelles/ Problématique
Proposition 2 : La base de données est représentée par les trois tables suivantes :
Produit (code_prod, nom_prod, prix)
Dépôt (code_dep, adr_dep)
Stock (code_prod, code_dep, qté)
Soit l'extension suivante de la BD :
Cette base de données ne présente
aucune anomalie elle est normalisée
Université Constantine 2 Pr. F. Magra-Benchikha 5
Conception de BDs relationnelles/ Normalisation
• La normalisation est le processus qui permet de construire des relations
complètes et non redondantes.
• Cette théorie est basée sur les "dépendances fonctionnelles" (DF) qui
traduisent des contraintes sur les données.
• Les dépendances fonctionnelles et des propriétés particulières, sont à la base
d’une suite de formes normales (FN).
• Une relation est dite normalisée si, au moins, elle vérifié la troisième forme
normale (3FN).
• La troisième forme normale est obtenue au moyen d'algorithmes de
décomposition. Le point de départ de ces algorithmes est la relation
universelle, c'est-à-dire la relation qui regroupe toutes les informations à
stocker (dans notre exemple, le schéma de la première proposition représente
cette relation universelle) .
Université Constantine 2 Pr. F. Magra-Benchikha 6
Conception de BDs relationnelles/ Dépendance fonctionnelle
Notion de dépendance fonctionnelle
Définition
Soit R(A1,A2,...An) un schéma de relation, X et Y des sous-ensembles de (A1,
A2,…An).
Il existe une dépendance fonctionnelle (DF) de X vers Y, notée X →Y, si et
seulement si: étant donné une valeur de X, il lui correspond une et une seule
valeur de Y. On dit que X détermine Y ou Y dépond fonctionnellement de X.
Exemple :
code_prod → prix,
code_prod →nom-prod
code_dep → adr_dep
Remarque : la partie gauche d'une dépendance fonctionnelle peut être formée de
la concaténation de plusieurs attributs. Cette concaténation est indissociable.
Exemple : code_prod, code_dep → qté (code_prod → qté et code_dep → qté)
Université Constantine 2 Pr. F. Magra-Benchikha 7
Conception de BDs relationnelles/ Dépendance fonctionnelle
Types de dépendances fonctionnelles
1. Dépendance fonctionnelle élémentaire
Une dépendance fonctionnelle X → Y est dite élémentaire si :
• Y est un attribut unique n'appartenant pas à X,
• il n'existe pas W inclus dans X tel que W → Y (en d'autres termes, Y ne dépend pas
fonctionnellement d'une partie de X)
Exemple :
code_prod, nom_prod → prix (DF non élémentaire car on a: code_prod → prix)
code_prod, code_dep →qté (DF élémentaire)
code_dep → adr_dep (DF élémentaire)
2. Dépendance fonctionnelle directe
Une dépendance fonctionnelle X → Y est dite directe si :
• il n'existe aucun attribut Z tel que l'on puisse avoir X → Z et Z → Y (En d'autres
termes, X ne détermine pas Y de façon transitive)
Exemple :
Code_etudinat → id_salle n'est pas directe car on a :
Code_etudiant → code_enseignant
Code_enseignant → id_salle
Université Constantine 2 Pr. F. Magra-Benchikha 8
Conception de BDs relationnelles/ Dépendance fonctionnelle
Propriétés des dépendances fonctionnelles (Axiomes d'Armstrong)
Les dépendances fonctionnelles obéissent à certaines propriétés connues sous le
nom d'axiomes d'Armstrong.
• Réflexivité :
YX ALORS X→Y
• Augmentation :
X→Y ALORS X,Z → Y , Z
• Transitivité :
X → Y et Y → Z ALORS X→Z
• D'autres propriétés se déduisent de ces axiomes :
• Union :
X → Y et X → Z ALORS X → Y , Z
• Pseudo-transitivité :
X → Y et Y, W → Z ALORS X, W → Z
• Décomposition :
X → Y et Z Y ALORS X → Z
Université Constantine 2 Pr. F. Magra-Benchikha 9
Conception de BDs relationnelles/ Dépendance fonctionnelle
Fermeture transitive et couverture minimale d'un ensemble de DFs
1. Fermeture transitive
• La fermeture transitive d'un ensemble de dépendances fonctionnelles est ce
même ensemble enrichi de toutes les dépendances fonctionnelles déduites par
transitivité (DF non directes).
2. Couverture minimale
• On appelle la couverture minimale d'un ensemble de dépendances
fonctionnelles F, un sous ensemble des dépendances fonctionnelles de F qui
sont élémentaires et non déduites (ou directes). La couverture minimale F' est
équivalente à F en ce sens que toute dépendance fonctionnelle de F peut être
déduite de F'.
Université Constantine 2 Pr. F. Magra-Benchikha 10
Conception de BDs relationnelles/ Dépendance fonctionnelle
Graphe de dépendances fonctionnelles (GDF)
Le graphe de dépendances fonctionnelles (GDF) est la représentation graphique
d'un ensemble de DFs.
Graphe minimal des dépendances fonctionnelles
Le GDF est dit minimal s'il représente une couverture minimale d'un ensemble de
dépendances fonctionnelles.
code_prod code_dep
nom_prod prix
adr_de
p
qté
Exemple de GDF
Université Constantine 2 Pr. F. Magra-Benchikha 11
Conception de BDs relationnelles/ Dépendance fonctionnelle
Clé minimale de relation
Une clé minimale X d'une relation R est un attribut (ou groupe d'attributs) de R dont :
• X est le plus petit ensemble d'attributs qui identifie R,
• X détermine tous les autres attributs de R.
Remarque
Tout graphe (minimum ou pas) des DFs peut être employé pour la recherche des identifiants
(clés) des relations de la façon suivante:
Chercher, sur le graphe des DFs de la relation, tout ensemble minimum d'attributs, X, tel que
tous les chemins partant de X et suivant les DF atteignent tous les autres attributs du
graphe. Alors X est un identifiant de la relation.
Exemple :
La clé primaire de la relation Stock est : (code-prod + code-dep)
Université Constantine 2 Pr. F. Magra-Benchikha 12
Conception de BDs relationnelles/ Dépendance fonctionnelle
Application 1
Soit la relation R (A , B , C , D , E , F , G , H) avec la suite de dépendances fonctionnelles
suivantes :
DF = { A →B ,
A →C ,
D →E ,
F →A ,
F→C,
F →G ,
AD →C ,
AD →H }
1. Démontrer en utilisant les axiomes d’Amstrong et les règles d’inférence la validité de la
dépendance fonctionnelle suivante : FD →CE
2. Proposer une couverture minimale pour DF.
3. Trouver une clé minimale de R en considérant la couverture minimale de DF.
Université Constantine 2 Pr. F. Magra-Benchikha 13
Conception de BDs relationnelles/ Normalisation
Degré de normalisation
● Il existe plusieurs degrés de normalisation, de la 1ère à la 5ème forme normale:
– 1NF - première forme normale
– 2NF – deuxième forme normale
– 3NF – troisième forme normale (« minimum »)
– BCNF – forme normale de Boyce-Codd
– 4NF – quatrième forme normale
– 5NF – cinquième forme normale
Université Constantine 2 Pr. F. Magra-Benchikha 14
Conception de BDs relationnelles/ Normalisation
1ère Forme Normale (1FN)
Une relation R est dite en 1FN si et seulement si :
• Tous les attributs de R sont atomiques et monovalués.
Exemple1
Dans la relation suivante, tout attribut est atomique et monovalué.
Produit (codeProd, nomProd, prix, couleur)
Produit est en 1FN
Exemple 2
Pour l'exemple précédent, si on suppose qu'un produit peut être de plusieurs couleurs. La
relation Produit n'est plus en 1FN car l'attribut "couleur" est dans ce cas multivalué.
Solution : Décomposition de la relation Produit en :
Produit (code_prod, nom_prod, prix)
Couleur-Produit (code_prod, couleur)
Université Constantine 2 Pr. F. Magra-Benchikha 15
Conception de BDs relationnelles/ Normalisation
2ème Forme Normale (2FN)
Définition 1
Une relation R est en 2FN si et seulement si :
- R est en 1FN;
- tout attribut n'appartenant pas à une clé de R (attribut non clé) ne dépend pas d'une
partie de cette clé.
Définition 2
On dit qu'une relation R est en 2FN si et seulement si :
• R est en 1FN,
• toutes les DFs entre la clé et les autres attributs sont élémentaires.
Exemple
La relation : RU (code_prod, nom_prod, prix, code_dep, adr_dep, qté)
N'est pas en 2FN car on a : code_prod → nom_prod
Université Constantine 2 Pr. F. Magra-Benchikha 16
Conception de BDs relationnelles/ Normalisation
3ème Forme Normale (3FN)
Définition 1 :
Une relation R est en 3FN ssi :
• R est en 2FN;
• tout attribut non clé ne dépend pas d'un attribut non clé.
Définition 2 :
On dit qu'une relation est en 3FN si toutes les DFs entre la clé et les autres attributs sont
élémentaires et directes.
Exemple
Etudiant (NumE, CodeDept, NomDept)
DF ={NumE→ CodeDept,
CodeDept →NomDept }
La clé est : La relation Etudiant n'est pas en 3FN car on : CodeDept →NomDept
Université Constantine 2 Pr. F. Magra-Benchikha 17
Conception de BDs relationnelles/ Normalisation
Schéma relationnel normalisé
Définition
Un schéma relationnel est dit normalisé si toutes les relations qui le composent sont, au
moins, dans la troisième forme normale (3FN).
Normalisation
Normaliser un schéma relationnel c'est le transformer en un schéma relationnel normalisé
équivalent, c'est-à-dire, contenant les mêmes informations que le schéma de départ et ne
présentant pas de redondance. La normalisation se base principalement sur la
décomposition des relations non normalisées en plusieurs relations normalisées.
Décomposition
On dit que la relation R est décomposable en relations R1, R2, …, Rn sans perte
d'informations et sans perte de DFs si :
R= R1[] R2 [] …[]Rn
Important
Pour toute relation non normalisée, il existe au moins une décomposition en 3FN sans
perte d’information et sans perte de DFs. Une telle décomposition est générée par un
algorithme dit algorithme de synthèse.
Université Constantine 2 Pr. F. Magra-Benchikha 18
Conception de BDs relationnelles/ Normalisation
Algorithme de synthèse
Entrée : La relation R non normalisée et une couverture minimale de l’ensemble des DFs.
Sortie : Des relations en 3FN.
A partir du GDF minimal (ou de la couverture minimale soit DF) :
1. Éditer l’ensemble des attributs isolés dans une même relation,
2. Rechercher le plus grand ensemble X d’attributs qui déterminent d’autres attributs,
A1, A2,…An,
3. Éditer la relation R (X, A1, A2, …, An) avec X sa clé primaire,
4. Supprimer les DFs (X →A1, X →A1,…., X →An) du GDF minimal (ou de DF),
5. Supprimer les attributs isolés du GDF,
6. Répéter l’opération de réduction à partir de l’étape 2, jusqu’à ce que le GDF (ou DF)
soit vide.
Fin
Université Constantine 2 Pr. F. Magra-Benchikha 19
Conception de BDs relationnelles/ Normalisation
Application
Dans un club sportif universitaire, des étudiants peuvent s’inscrire à la semaine.
Une semaine est connue par un numéro annuel de semaine unique (de 1 à 52), une
date de début et une date de fin. On connaît ainsi, semaine par semaine, la liste
des étudiants inscrits au club sportif. Pour chaque étudiant, on connaît le code, le
nom et le prénom. On connaît également l'activité sportive qu'il pratique dans la
semaine. Chaque activité possède un nom unique.
Le club sportif prend en charge le transport des étudiants par bus. Ainsi, pour
chaque jour (identifié par un numéro de 1 à 7) d’une semaine donnée est affecté
un bus aux étudiants exerçant la même activité sportive. Chaque bus est identifié
par un code.
Question1 : Quelle est la base de données relationnelle normalisée qui permet de
gérer ce club ? (On passe par toutes les étapes de conception : Dictionnaire de
données, graphe minimal des dépendances fonctionnelles de RU, forme normale
Université Constantine 2 Pr. F. Magra-Benchikha 20
de RU, la normalisation de RU).