Normalisation

La normalisation

Objectifs

Définir des règles pour décomposer les relations tout en préservant les DF
sans perdre d’informations afin de représenter les objets et les associations canoniques du monde réel

La normalisation permet d’éviter les anomalies de mises à jour et les réponses erronées

Les outils de normalisation sont :

• Les dépendances fonctionnelles
• Les formes normales
• Les décompositions des tables

Définition

Définition

La normalisation d’une relation R est la décomposition de celle-ci par un ensemble de relations R1,...,Rn tel que :

• Les attributs de R sont égaux à l’union de tous les attributs des Ri
• Ri est obtenu à partir de R par projection sur les attributs de Ri
• La décomposition est sans perte, de sorte que l’on puisse retrouver exactement l’information de départ
  • Une décomposition est sans perte si et seulement si elle préserve les dépendances fonctionnelles

Exemple

Exemple

La table Livres

Livres
numero	titre	auteur	isbn	dateAchat	rayonnage
1	Le Petit Prince	Antoine de Saint-Exupéry	978-2-01-000000-0	2020-07-29	A1
2	Le Petit Prince	Antoine de Saint-Exupéry	978-2-01-000000-0	2020-07-29	A1
3	Les misérables	Victor Hugo	978-2-01-000000-1	2018-06-21	A2
4	Le portrait de Dorian Gray	Oscar Wilde	978-2-01-000000-2	2010-01-29	F3
5	Le portrait de Dorian Gray	Oscar Wilde	978-2-01-000000-2	2010-01-29	F3
6	Dune	Frank Herbert	978-2-01-000000-3	2015-12-12	B4

Problème : Lorsqu’un livre existe en plusieurs exemplaires, les informations titre, auteur, isbn sont dupliquées

Normalisation de la table Livres

• On va créer une nouvelle table Ouvrages contenant les informations relatives aux livres
• On va créer une nouvelle table Exemplaires contenant les informations relatives aux exemplaires

Ouvrages
isbn	titre	auteur
978-2-01-000000-0	Le Petit Prince	Antoine de Saint-Exupéry
978-2-01-000000-1	Les misérables	Victor Hugo
978-2-01-000000-2	Le portrait de Dorian Gray	Oscar Wilde
978-2-01-000000-3	Dune	Frank Herbert

Exemplaires
numero	isbn	dateAchat	rayonnage
1	978-2-01-000000-0	2020-07-29	A1
2	978-2-01-000000-0	2020-07-29	A1
3	978-2-01-000000-1	2018-06-21	A2
4	978-2-01-000000-2	2010-01-29	F3
5	978-2-01-000000-2	2010-01-29	F3
6	978-2-01-000000-3	2015-12-12	B4

En créant une deuxième table et en utilisant l’ISBN comme clé étrangère dans la table Exemplaires, on a solutionné le problème de redondance !

Comment décomposer une table ?

• Soit une table R possédant 3 attributs A, B et C

• Il existe une dépendance fonctionnelle entre B et C (Si on connait B, alors on connait nécessairement C)

  • On doit donc extraire la colonne C de la table R pour éviter la redondance interne
  • La colonne B doit être présente dans les 2 tables pour pouvoir reconstruire l’information

• On peut aussi remarquer dans cet exemple que :

  • B sera une clé étrangère dans la table R
  • B sera une clé primaire dans la table S

Il peut exister plusieurs dépendances fonctionnelles au sein d’une même table.
Il faudra alors décomposer autant de fois que nécessaire pour éviter la redondance.

Les formes normales

Définition

Les formes normales sont des règles qui permettent de définir des étapes de normalisation pour garantir l’intégrité des données et éviter les anomalies

Nous allons illustrer les différentes formes normales par des exemples concrets, mais on peut toujours rapporter ces exemples à un schéma générique d’une relation R :

Relation R avec 6 attributs (a1 à a6). les trois premiers a1, a2, a3 formant le déterminant, et les trois derniers a4, a5, a6 les déterminés.

Relation R
a1	a2	a3	a4	a5	a6

Les dépendances fonctionnelles (DF) de la relation R sont :

1ère forme normale (1FN ou 1NF)

Définition

Une relation est dite de première forme normale, si et seulement si :

• elle admet une clé (ou un ensemble de clés)
• tout attribut contient une valeur atomique
• tous les attributs sont non répétitifs
• tous les attributs sont constants dans le temps

Exemples de non-respect de la 1FN

Exemples de non-respect de la 1FN

Règle : tout attribut doit contenir une valeur atomique

Exemple de table non normalisée 1FN

Personnes
ID	Nom	Adresse
1	Dupont Jean	12 rue de la Paix, Paris
2	Durand Paul	15 rue de la Liberté, Lyon

• La colonne Nom n’est pas atomique (elle contient le prénom et le nom)
  • Il faudrait décomposer la colonne Nom en 2 colonnes Prénom et Nom
• La colonne Adresse n’est pas atomique (elle contient le numéro, la rue, la ville et le code postal)
  • Il faudrait décomposer la colonne Adresse en colonnes Numéro, Rue, Ville et Code Postal

Exemples de non-respect de la 1FN

Règle : tous les attributs sont non répétitifs

Exemple de table non normalisée 1FN

Produits
IDProduit	Description	Fournisseurs
1	Téléviseur	Sony, Sharp, LG
2	Chaîne Hifi	Philips, Sony

• La colonne Fournisseurs est répétitive (elle contient plusieurs valeurs)
  • Il faudrait décomposer la colonne Fournisseurs en une table Fournisseur

Exemples de non-respect de la 1FN

Règle : tous les attributs sont constants dans le temps

Exemple de table non normalisée 1FN

Personnes
ID	Nom	Prénom	Age
1	Dupont	Jean	25
2	Durand	Paul	30

• La colonne Age n’est pas constante dans le temps
  • Il faudrait transformer la colonne Age en DateDeNaissance
  • On pourra alors toujours calculer l’age à partir de la date de naissance

Danger

Le non-respect de la première forme normale constitue une des plaies les plus importantes en matière de bases de données relationnelles.
Ce non-respect a des conséquences catastrophiques en matière de performances

2ème forme normale (2FN ou 2NF)

Définition

Une relation est en deuxième forme normale (2FN ou 2NF) ssi :

• Elle est en première forme normale
• Tout attribut non clé ne dépend pas d’une partie de clé

Autrement dit, tous les attributs non-identifiants sont totalement dépendants fonctionnellement de la totalité de l’identifiant (et donc de la clé primaire au niveau tabulaire)

Exemples de non-respect de la 2FN

Règle : Tout attribut non clé ne dépend pas d’une partie de clé

Exemple de table non normalisée 2FN

DetailsCommandes
numeroCommande	numeroProduit	descriptionProduit
1	1	Téléviseur
2	2	Chaîne Hifi
3	1	Téléviseur

• Dans cet exemple :
  • L’identifiant de la table est (numeroCommande, numeroProduit)
  • On peut déduire qu’il existe une dépendance fonctionnelle entre numeroProduit et descriptionProduit
    • numeroProduit → descriptionProduit
  • La table n’est pas en 2FN car descriptionProduit dépend d’une partie de la clé

Pour régler ce problème il faudrait décomposer la table en deux tables distinctes

• Commande(numeroCommande, numeroProduit*)
• Produit(numeroProduit, descriptionProduit)

Schématique du non-respect de la 2FN

Si un attribut ne fait pas partie de la clé, il ne doit pas dépendre fonctionnellement d’une partie de la clé

3ème forme normale (3FN ou 3NF)

Définition

Une relation est en troisième forme ssi :

• Elle est en deuxième forme normale
• Tout attribut n’appartenant pas à un identifiant ne dépend pas d’un attribut non identifiant

Exemples de non-respect de la 3FN

Exemple de table non normalisée 3FN

Commandes
numeroCommande	numeroClient	nomClient
1	1	Dupont
2	1	Dupont
3	2	Durand

• Dans cet exemple :
  • L’identifiant de la table est numeroCommande
  • On peut déduire qu’il existe une dépendance fonctionnelle entre numeroClient et nomClient
    • numeroClient → nomClient
  • La table n’est pas en 3FN car nomClient dépend d’un attribut non-clé ( numeroClient ne fait pas partie de la clé)

Pour régler ce problème il faudrait décomposer la table en deux tables distinctes

• Commande(numeroCommande, numeroClient*)
• Client(numeroClient, nomClient)

Schématique du non-respect de la 3FN

Si un attribut ne fait pas partie de la clé, il ne doit pas dépendre fonctionnellement d’un autre attribut non-clé

La troisième forme normale :

• Retire les redondances dues aux dépendances transitives
• Permet de ne pas perdre d’information
• Permet de ne pas perdre des dépendances

À retenir

Un modèle relationnel doit être à minima de troisième forme normale

La troisième forme normale est la plus utilisée du fait de son équilibre entre redondance et performance.

On pourra remarquer que pour certains systèmes (surtout distribués, e.g. pour certaines bases NoSQL), la redondance n’est pas un problème. Dans ces cas, on pourra se passer de la normalisation pour augmenter les performances.

Forme normale de Boyce-Codd (FNBC ou BCNF ou 3.5FN)

Le respect de la 3FN ne garantit pas totalement une absence de redondance des données. C’est pourquoi on doit parfois aller plus loin dans la normalisation avec la FNBC.

Définition

Une relation est en Forme normale de Boyce-Codd ssi :

• Une relation en troisième forme normale a un identifiant composé, aucune des propriétés élémentaires de cet identifiant ne doit être en dépendance fonctionnelle d’une autre propriété

La BCNF est une forme normale plus stricte que la 3FN

Exemples de non-respect de la FNBC

Exemple de table non normalisée FNBC

Universite
enseignantId	matiereId	salleId
DURAND	CHIMIE	LABO CHIMIE 3
DUPONT	ANGLAIS	6A

• Dans cet exemple :
  • Si Durand arrête d’enseigner la Chimie, on supprime la ligne et on perd la relation Matière-Salle
  • On peut déduire qu’il existe une dépendance fonctionnelle entre enseignantId (attributs de la clé) et les 2 autres attributs (aussi attributs de la clé)

Pour régler ce problème, il faudrait une conception différente en plusieurs tables

Attention

Une décomposition en BCNF ne préserve pas toujours les DF.

La normalisation… Quand est-ce que l’on s’arrête ?

• Il existe les 4, 5 et 6ème formes normales. Elles évitent principalement la redondance d’information et sont plus précises
• En pratique, la 3FN est suffisante
• En effet, les projections et les jointures sont coûteuses pour le système, ainsi une trop forte normalisation diminue fortement les performances

Exercice

Énoncé

Soit une relation R1 de schéma :

R1 (A, B, C, D, E, F)

Avec l’ensemble de dépendances suivant :

{
  AB → C
  AB → D
  AB → E
  AB → F
  B → C
  D → E
  D → F
}

1. Quelle est la couverture minimale de dépendances ? Déssinez son graphe.

2. Quelles est la clé de R1 ?

3. Quelle est la forme normale de R1 ?

4. On décompose la relation R1 en R11 et R12 :

R11(A, B, D, E, F)

et

R12(B,C)

Quelles sont les formes normales des relations R11 et R12 ?

5. Proposer une décomposition sans perte d’information de R11.

Solution

Soit une relation R1 de schéma :

R1 (A, B, C, D, E, F)

1. Quelle est la couverture minimale de dépendances ?

L’ensemble des dépendances est :

{
  AB → C
  AB → D
  AB → E
  AB → F
  B → C
  D → E
  D → F
}

Par défaut, on peut dessiner le graphe suivant :

    
flowchart LR
  AB --> C
  AB --> D
  AB --> E
  AB --> F
  B --> C
  D --> E
  D --> F

Par transitivité, on peut :

• supprimer AB → E et AB → F, car AB → D et D → EF :
• Supprimer B → C car AB → C et B → C :

    
flowchart LR
  AB --> C
  AB --> D
  D --> E
  D --> F

L’ensemble minimum de dépendances fonctionnelles de R1 est donc :

{ AB → C, AB → D, D → E, D → F }

Solution alternative :

Par transitivité, on peut :

• supprimer AB → E et AB → F, car AB → D et D → EF :
• Supprimer AB → C car B → C:

    
flowchart LR
  AB --> D
  D --> E
  D --> F
  B --> C

L’ensemble minimum de dépendances fonctionnelles de R1 est donc :

{ AB → C, AB → D, D → E, D → F }
ou
{ AB → D, B → C, D → E, D → F }

2. Quelles est la clé de R1 ?

La clé AB est la seule clé candidate car on observe que les attributs A et B déterminent tous les autres attributs de la relation

3. Quelle est la forme normale de R1 ?

Cette relation est en première forme normale mais :

• pas en 2FN car il y a un attribut qui ne fait pas partie de la clé C qui dépend d’une partie de la clé B
• pas en 3FN car il y a une dépendance transitive D → E et D → F

4. On décompose la relation R1 en R11 et R12 :

La relation R11 est en deuxième forme normale et pas en troisième normale car il subsiste une dépendance transitive. La relation R12 est en BCNF.

5. Proposer une décomposition sans perte d’information de R11.

On peut décomposer R11 en R112(D, E, F) et R112(A,B,D) sans perte d’information.

Conclusion

Lors de la conception d’une base de données, il est important de respecter les règles de normalisation pour éviter les problèmes de redondance et d’incohérence des données.

Voici quelques points clés à retenir sur la normalisation :

• La normalisation est un processus de conception de base de données qui permet de réduire la redondance des données
• La normalisation permet de garantir l’intégrité des données et d’éviter les anomalies
• La normalisation permet de **structurer les données **de manière à ce qu’elles soient faciles à maintenir et à interroger
• La normalisation est un processus itératif qui peut être long et complexe
• La normalisation est un compromis entre la performance et la structure des données

On prendra en compte chaque attribut de chaque table pour déterminer les dépendances fonctionnelles et décomposer les tables en conséquence.

La page Wikipedia sur les formes normales est une bonne ressource pour approfondir vos connaissances sur le sujet.