Normalisation et formes normales

On regarde un modèle de données, constitué d’un certain nombre d’attributs, qui suivent certaines contraintes provenant de la réalité des données décrites.

On aura à envisager différentes instances envisageables de ce modèle, correspondant à différents moments de l’histoire, passés, futurs ou simplement envisageables.

On va réaliser ce modèle par un schéma de base de données, qui décrit une structure de tables, comme par exemple :

Pour chaque instance du modèle, on obtiendra ainsi plusieurs tables effectives, comme

et

Si on modifie ces données, on obtient une nouvelle instance du même schéma.

On considère un modèle avec des attributs a₁, …​ , a_n, et on notera A l’ensemble de tous ces attributs { a₁, …​ a_n}

Pour un enregistrement t, on note a₁(t), …​ , a_n(t) les valeurs de ces attributs pour l’enregistrement t.

On peut aussi considérer un sous-ensemble X de A constitué d’un certain nombre d’attributs, et regarder de même l’ensemble X(t) constitué des valeurs en t des attributs contenus dans X.

Si X et Y sont deux ensembles d’attributs de A, on dit qu’il y a une dépendance fonctionnelle de X vers Y, qu’on note X → Y, si pour toute instance du modèle, et tout couple d’enregistrements s,t, tels que X(s) = X(t), on a Y(s) = Y(t).

Un sous-ensemble C de l’ensemble d’attributs A du modèle est une clé candidate si

Il peut y avoir plusieurs clés candidates dans un modèle et on en privilégie une qu’on appelera la clé.

Etant donné un schéma de bases de données S(a₁, …​ , a_n), on peut le décomposer en plusieurs tables, en écrivant l’ensemble d’attributs A comme réunion de plusieurs sous-ensembles B₁, …​ , B_p, donnant ainsi lieu à p tables. Ainsi le schéma

peut être décomposé en :

Une telle décomposition est sans perte d’information si pour toute instance du modèle, on peut reconstituer le schéma initial par jointure à partir du schéma décomposé.

Une décomposition préserve les dépendances fonctionnelles si toute dépendance fonctionnelle X → Y peut être déduite des dépendances fonctionnelles provenant de chacune des tables du schéma décomposé.

Un schéma est sous première forme normale (1NF en anglais) si tous les attributs sont atomiques, c’est-à-dire si aucune subdivision de la donnée initiale n’apporte d’information complémentaire.

Remarques :

n’est clairement pas sous première forme normale.

Question : comment représenter ce modèle avec un schéma veérifiant 1NF ?

Un schéma est sous deuxième forme normale (2NF) si il est sous 1NF et si tout attribut ne faisant pas partie de la clé ne dépend pas fonctionnellement d’un sous-ensemble de la clé.

Remarque : en particulier, cette condition est trivialement réalisée si la clé est constituée d’un seul attribut.

Le schéma

(Produit, Fournisseur, adresse_fournisseur)

n’est pas sous 2NF, puisque l’adresse du fournisseur dépend seulement d’une partie de la clé.

On peut décomposer ce schéma, sans perte d’information, pour le mettre en 2NF :

(Produit, Fournisseur)

(Fournisseur, adresse_fournisseur)

Un schéma est sous troisième forme normale (3NF) si il est sous 2NF et si tout attribut ne faisant pas partie de la clé ne dépend pas fonctionnellement d’un groupe d’attributs en dehors de la clé.

La table

(Fournisseur, adresse_fournisseur, ville, pays)

n’est pas en 3NF, puisque le pays est entièrement déterminé par la ville.

On peut se ramentr à la troisème forme normale en décomposant :

(Fournisseur, adresse_fournisseur, ville)

(ville, pays)

Un schéma est sous forme normale de Boyce-Codd (BCNF) si il est sous 3NF et si tout groupe d’attributs ne faisant pas partie de la clé n’est pas source de dépendance fonctionnelle vers une partie de la clé.

Considérons la relation

avec les dépendances fonctionnelles

La décomposition suivante :

est sous forme normale de Boyce-Codd et préserve les dépendances fonctionnelles.