Leçon 1 sur 5
Normalisation : les formes normales
Je sais raisonner sur les dépendances fonctionnelles, calculer une fermeture d'attributs, trouver les clés candidates et décomposer une relation jusqu'en forme normale de Boyce-Codd sans perte d'information.
- 1 h 30
- 6 exercices corrigés
- QCM de 7 questions
À la fin de la leçon, vous saurez :
- Définir formellement une dépendance fonctionnelle et utiliser les axiomes d'Armstrong
- Calculer la fermeture d'un ensemble d'attributs et en déduire les clés candidates
- Vérifier les formes normales 1FN, 2FN, 3FN et FNBC
- Décomposer une relation sans perte d'information et discuter la préservation des dépendances
- Reconnaître les anomalies de mise à jour qu'évite la normalisation
Avant de commencer : Bases de données (L1) : modèle relationnel, clés primaires et étrangères, première approche des formes normales.
1Je découvre
Une microfinance de Labé suit les remboursements de ses crédits dans un grand fichier, que le stagiaire veut importer tel quel dans MySQL. Chaque ligne contient : le numéro du crédit, le numéro et le nom de la cliente, son téléphone, l'agence (code et ville), le rang de l'échéance, la date limite, le montant dû et la date de paiement.
Le comptable a déjà constaté des problèmes : une cliente qui a changé de numéro de téléphone apparaît avec deux numéros différents selon les lignes ; quand on a supprimé le dernier crédit d'une cliente, son nom a disparu de la base ; et pour enregistrer une nouvelle agence à Pita, il a fallu inventer un faux crédit. En L1, vous avez appris à repérer « à l'œil » ces défauts. En L2, il faut une méthode démontrable, qui fonctionne aussi sur des tables de vingt colonnes.
Comment déterminer de façon rigoureuse les clés d'une relation et la décomposer en tables sans redondance, sans perdre la moindre information ?
2Je comprends
1. Dépendances fonctionnelles et axiomes d'Armstrong
Soit une relation R et deux ensembles d'attributs X et Y de R. On dit que X détermine fonctionnellement Y, noté X → Y, si deux tuples de R qui ont la même valeur sur X ont nécessairement la même valeur sur Y. Une DF est une règle de gestion : elle doit être vraie pour toutes les extensions possibles de la table, pas seulement pour les lignes observées aujourd'hui.
- X → Y est triviale si Y est inclus dans X (par exemple AB → A).
- X → Y est élémentaire si aucun sous-ensemble strict de X ne détermine Y.
Les axiomes d'Armstrong permettent de déduire toutes les DF qui découlent d'un ensemble F donné :
| Règle | Énoncé |
|---|---|
| Réflexivité | si Y ⊆ X, alors X → Y |
| Augmentation | si X → Y, alors XZ → YZ |
| Transitivité | si X → Y et Y → Z, alors X → Z |
| Union (déduite) | si X → Y et X → Z, alors X → YZ |
| Décomposition (déduite) | si X → YZ, alors X → Y et X → Z |
| Pseudo-transitivité (déduite) | si X → Y et WY → Z, alors WX → Z |
Ces règles sont correctes (elles ne produisent que des DF vraies) et complètes (elles produisent toutes les DF qui découlent de F).
Pour la table de la microfinance, notée REMB, les règles de gestion donnent :
- F1 : num_credit → num_client, code_agence
- F2 : num_client → nom_client, tel_client
- F3 : code_agence → ville_agence
- F4 : num_credit, rang → date_limite, montant_du, date_paiement
2. Fermeture d'attributs et clés candidates
La fermeture de X par rapport à F, notée X⁺, est l'ensemble de tous les attributs que X détermine. On la calcule par un algorithme simple.
Méthode
Pour calculer la fermeture X⁺ :
- Je pose X⁺ = X.
- Je parcours les DF de F : pour chaque DF G → H telle que G ⊆ X⁺, j'ajoute H à X⁺.
- Je recommence le parcours tant que X⁺ grandit.
- Quand plus rien ne s'ajoute, X⁺ est trouvé.
- X est une surclé si X⁺ contient tous les attributs de R ; c'est une clé candidate si, de plus, aucun sous-ensemble strict de X n'est une surclé.
Exemple
Calcul de {num_credit, rang}⁺ dans REMB.
Étape 1 - Départ : {num_credit, rang}.
Étape 2 - F1 (num_credit ⊆ X⁺) ajoute num_client, code_agence.
Étape 3 - F2 ajoute nom_client, tel_client ; F3 ajoute ville_agence ; F4 ajoute date_limite, montant_du, date_paiement.
Étape 4 - Nouveau parcours : rien ne s'ajoute. X⁺ contient les 10 attributs : c'est une surclé.
Étape 5 - Minimalité : {num_credit}⁺ = {num_credit, num_client, code_agence, nom_client, tel_client, ville_agence} ne contient pas rang ; {rang}⁺ = {rang}. Aucun sous-ensemble n'est surclé.
Conclusion : {num_credit, rang} est une clé candidate de REMB.
Astuce pour trouver toutes les clés : un attribut qui n'apparaît jamais à droite d'une DF appartient à toutes les clés (ici num_credit et rang) ; un attribut qui n'apparaît qu'à droite n'appartient à aucune clé. Comme {num_credit, rang} est déjà une clé, c'est la seule.
Un attribut est dit premier (ou clé) s'il appartient à au moins une clé candidate ; sinon il est non premier.
3. Les formes normales 1FN, 2FN et 3FN
| Forme | Condition |
|---|---|
| 1FN | tout attribut est atomique (une seule valeur, non décomposable pour l'usage) et la relation a une clé |
| 2FN | 1FN, et tout attribut non premier dépend de toute clé candidate, pas d'une partie (pas de dépendance partielle) |
| 3FN | 2FN, et aucun attribut non premier ne dépend d'un autre attribut non premier (pas de dépendance transitive) ; formellement : pour toute DF non triviale X → A, X est une surclé ou A est premier |
| FNBC | pour toute DF non triviale X → Y, X est une surclé |
Une colonne « téléphones » contenant « 6xx xx xx 01 ; 6xx xx xx 02 » viole la 1FN : on crée une table TELEPHONE (#num_client, numero).
Application à REMB, de clé (num_credit, rang) :
- 2FN ? Non : num_credit → num_client, code_agence, nom_client, tel_client, ville_agence est une dépendance partielle (num_credit n'est qu'une partie de la clé).
- Décomposition 2FN : ECHEANCE (#num_credit, rang, date_limite, montant_du, date_paiement) et CREDIT_TMP (num_credit, num_client, nom_client, tel_client, code_agence, ville_agence).
- 3FN ? CREDIT_TMP contient deux dépendances transitives : num_credit → num_client → nom_client, tel_client et num_credit → code_agence → ville_agence.
- Décomposition 3FN : CLIENT (num_client, nom_client, tel_client) ; AGENCE (code_agence, ville_agence) ; CREDIT (num_credit, #num_client, #code_agence) ; ECHEANCE inchangée.
Résultat : le téléphone d'une cliente est stocké une seule fois ; une cliente existe même sans crédit ; on crée l'agence de Pita sans crédit fictif.
4. La forme normale de Boyce-Codd (FNBC)
La 3FN tolère une exception : une DF X → A avec X non surclé est acceptée si A est premier. La FNBC supprime cette exception.
Exemple : au guichet, chaque conseiller ne traite qu'un seul service (épargne ou crédit), et chaque cliente a un seul conseiller par service. Relation SUIVI (client, service, conseiller) avec :
- (client, service) → conseiller
- conseiller → service
Clés candidates : (client, service) et (client, conseiller), car {client, conseiller}⁺ = {client, conseiller, service}. Tous les attributs sont premiers : SUIVI est en 3FN. Mais conseiller → service a une partie gauche qui n'est pas surclé : SUIVI n'est pas en FNBC. Conséquence : le service d'un conseiller est répété pour chacune de ses clientes.
Décomposition FNBC : CONSEILLER (conseiller, service) et SUIVI2 (client, conseiller). Elle est sans perte, mais la DF (client, service) → conseiller n'est plus vérifiable dans une seule table : rien n'empêche d'affecter à une cliente deux conseillers du même service. C'est le compromis classique :
| 3FN | FNBC | |
|---|---|---|
| Décomposition sans perte | toujours possible | toujours possible |
| Préservation des DF | toujours possible | pas toujours |
| Redondance résiduelle | possible (rare) | aucune due aux DF |
En pratique, on vise la FNBC ; quand elle ferait perdre une DF importante, on reste en 3FN ou l'on contrôle la DF perdue par un déclencheur.
5. Décomposition sans perte et préservation des dépendances
Une décomposition de R en R1 et R2 est sans perte (ou sans perte d'information) si la jointure naturelle R1 ⋈ R2 redonne exactement R, sans tuples en trop.
Théorème de Heath. Si R(X, Y, Z) vérifie X → Y, alors la décomposition en R1(X, Y) et R2(X, Z) est sans perte. Autrement dit : l'attribut commun doit être une clé de l'une des deux tables.
Contre-exemple : décomposer ECHEANCE en (num_credit, date_limite) et (rang, date_limite, montant_du) est avec perte : l'attribut commun date_limite ne détermine rien ; deux crédits ayant une échéance le même jour produiraient, après jointure, des combinaisons qui n'ont jamais existé (tuples parasites).
Une décomposition préserve les dépendances si chaque DF de F peut être vérifiée dans une seule des tables obtenues (ou se déduit de DF ainsi vérifiables). La décomposition 3FN de REMB préserve F1, F2, F3 et F4 : chacune est contenue dans une table.
Les formes supérieures existent : la 4FN traite les dépendances multivaluées (un client a plusieurs téléphones et plusieurs comptes, indépendamment) ; la 5FN les dépendances de jointure. Elles sont rares quand le MCD a été bien construit.
3Je retiens
Je retiens
X → Y : deux tuples égaux sur X sont égaux sur Y ; une DF est une règle de gestion, pas une observation.
Axiomes d'Armstrong : réflexivité, augmentation, transitivité ; on en déduit union, décomposition, pseudo-transitivité.
X est une surclé si X⁺ contient tous les attributs ; une clé candidate est une surclé minimale.
Un attribut jamais à droite d'une DF appartient à toutes les clés.
2FN : pas de dépendance partielle ; 3FN : pas de dépendance transitive d'un attribut non premier.
FNBC : toute partie gauche de DF non triviale est une surclé.
Heath : si X → Y, R(X, Y, Z) se décompose sans perte en (X, Y) et (X, Z).
La 3FN préserve toujours les DF ; la FNBC peut en perdre.
4Erreurs fréquentes
- Déduire une DF de quelques lignes de données : une DF se justifie par une règle de gestion.
- Chercher la 2FN sur une table dont la clé n'a qu'un attribut : elle est automatiquement en 2FN si elle est en 1FN.
- Oublier qu'une relation peut avoir plusieurs clés candidates : un attribut premier pour l'une ne cause pas de violation de 3FN.
- Décomposer sur un attribut commun qui n'est clé d'aucune table : la jointure produit des tuples parasites.
- Confondre 3FN et FNBC : une table peut être en 3FN sans être en FNBC.
- Normaliser sans vérifier que chaque DF reste contrôlable dans une table.
5Je m’exerce
1Exercice 1
(Questions de cours) a) Énoncez les trois axiomes d'Armstrong. b) Quelle différence entre surclé et clé candidate ? c) Énoncez le théorème de Heath.
Voir le corrigéCacher le corrigé
a) Réflexivité : si Y ⊆ X alors X → Y ; augmentation : si X → Y alors XZ → YZ ; transitivité : si X → Y et Y → Z alors X → Z. b) Une surclé détermine tous les attributs de la relation ; une clé candidate est une surclé minimale (on ne peut lui retirer aucun attribut). c) Si une relation R(X, Y, Z) vérifie X → Y, alors R est égale à la jointure de ses projections sur (X, Y) et (X, Z).
2Exercice 2
Soit R(A, B, C, D, E) et F = {A → B, B → C, CD → E}. a) Calculez {A}⁺ et {A, D}⁺. b) Déterminez toutes les clés candidates. c) Démontrez AD → E avec les axiomes.
Voir le corrigéCacher le corrigé
a) {A}⁺ : A, puis B (A → B), puis C (B → C) ; CD → E ne s'applique pas (D absent). {A}⁺ = {A, B, C}. {A, D}⁺ = {A, D, B, C, E}, tous les attributs.
b) A et D n'apparaissent jamais à droite : ils sont dans toutes les clés. {A, D} est surclé et minimale ({A}⁺ et {D}⁺ = {D} sont incomplets). Seule clé : {A, D}.
c) A → B et B → C donnent A → C (transitivité). Par augmentation par D : AD → CD. Avec CD → E et la transitivité : AD → E.
3Exercice 3
La relation VENTE_PHARMA(num_vente, date_vente, code_med, libelle, prix_unitaire, quantite) vérifie : num_vente → date_vente ; code_med → libelle, prix_unitaire ; num_vente, code_med → quantite. a) Donnez la clé. b) En quelle forme normale est-elle ? c) Décomposez-la en 3FN.
Voir le corrigéCacher le corrigé
a) num_vente et code_med n'apparaissent jamais à droite ; {num_vente, code_med}⁺ contient tout : clé (num_vente, code_med).
b) 1FN seulement : date_vente dépend de num_vente seul, libelle et prix_unitaire de code_med seul (dépendances partielles).
c) VENTE (num_vente, date_vente) ; MEDICAMENT (code_med, libelle, prix_unitaire) ; LIGNE (#num_vente, #code_med, quantite). Chaque table a une clé et aucune dépendance partielle ou transitive : 3FN (et même FNBC). Remarque : si le prix change dans le temps, on ajoute un prix_vente dans LIGNE pour garder le prix réellement payé.
4Exercice 4
Soit R(A, B, C) avec F = {AB → C, C → B}. a) Trouvez les clés candidates. b) R est-elle en 3FN ? en FNBC ? c) Donnez la décomposition FNBC et dites quelle DF est perdue.
Voir le corrigéCacher le corrigé
a) A n'est jamais à droite : il est dans toutes les clés. {A}⁺ = {A}. {A, B}⁺ = {A, B, C} et {A, C}⁺ = {A, C, B} : clés candidates AB et AC.
b) 3FN : pour AB → C, AB est surclé ; pour C → B, C n'est pas surclé mais B est premier : la 3FN est respectée. FNBC : C → B a une partie gauche non surclé : pas en FNBC.
c) Par Heath sur C → B : R1(C, B) et R2(A, C). La DF AB → C n'est plus vérifiable dans une seule table : elle est perdue.
5Exercice 5
On décompose ECHEANCE(num_credit, rang, date_limite, montant_du) en R1(num_credit, rang, date_limite) et R2(num_credit, rang, montant_du). La décomposition est-elle sans perte ? Justifiez avec le théorème de Heath.
Voir le corrigéCacher le corrigé
L'attribut commun est {num_credit, rang}, qui détermine date_limite (et montant_du). Par Heath, avec X = {num_credit, rang}, Y = {date_limite}, Z = {montant_du}, la décomposition est sans perte. Elle est cependant inutile : ECHEANCE était déjà en FNBC ; décomposer davantage n'apporte que des jointures.
6Exercice 6
(Type examen) Une université de Conakry gère les emplois du temps dans la relation EDT(code_ue, intitule_ue, enseignant, tel_enseignant, salle, capacite, creneau). Règles : une UE a un seul intitulé et un seul enseignant ; un enseignant a un seul téléphone ; une salle a une capacité ; une UE peut avoir plusieurs créneaux par semaine ; à un créneau donné, une salle accueille au plus une UE ; à un créneau donné, une UE se déroule dans une seule salle.
a) Écrivez l'ensemble F des DF.
b) Calculez {code_ue, creneau}⁺ et {salle, creneau}⁺, puis donnez toutes les clés candidates.
c) Dites en quelle forme normale est EDT, en justifiant.
d) Proposez une décomposition en FNBC, sans perte, et dites si elle préserve les dépendances.
Voir le corrigéCacher le corrigé
a) F : code_ue → intitule_ue, enseignant ; enseignant → tel_enseignant ; salle → capacite ; code_ue, creneau → salle ; salle, creneau → code_ue.
b) {code_ue, creneau}⁺ = {code_ue, creneau, intitule_ue, enseignant, salle, tel_enseignant, capacite} : tous les attributs. {salle, creneau}⁺ : on ajoute code_ue, puis intitule_ue, enseignant, capacite, tel_enseignant : tous les attributs. creneau n'est jamais à droite : il est dans toutes les clés ; {creneau}⁺ = {creneau} ne suffit pas. Clés candidates : (code_ue, creneau) et (salle, creneau).
c) Attributs premiers : code_ue, salle, creneau. code_ue → intitule_ue est une dépendance partielle d'un attribut non premier sur une partie de clé : EDT n'est qu'en 1FN.
d) UE (code_ue, intitule_ue, #enseignant) ; ENSEIGNANT (enseignant, tel_enseignant) ; SALLE (salle, capacite) ; SEANCE (#code_ue, creneau, #salle), avec la contrainte UNIQUE (salle, creneau). Chaque décomposition s'appuie sur une DF dont la partie gauche devient clé (Heath) : sans perte. Dans SEANCE, les deux DF (code_ue, creneau) → salle et (salle, creneau) → code_ue ont pour partie gauche une clé candidate : FNBC. Toutes les DF de F se vérifient dans une table : les dépendances sont préservées.
Cherchez d’abord seul, sur votre cahier, puis ouvrez le corrigé pour comparer.
6Je vérifie
Choisissez une réponse pour chaque question : la correction s’affiche aussitôt.
Karamö, votre enseignant
Il a lu cette leçon. Posez-lui votre question : il vous répond ici.
Connectez-vous pour poser vos questions à Karamö.
Avec un compte Kharandi gratuit, vous cochez les leçons terminées et vous suivez votre progression, cours par cours.