Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Systèmes d'information

Normalisation : dépendances fonctionnelles, BCNF et troisième forme normale

Anomalies de mise à jour, d'insertion et de suppression, dépendances fonctionnelles et axiomes d'Armstrong, fermeture et test de clé, théorème de Heath démontré, BCNF, 3NF et dénormalisation.

https://www.electronics-engineering.com/fr/normalisation-dependances-fonctionnelles-bcnf-3nf/

Pas encore de vote : soyez le premier à noter cette page.

Une table qui mélange des informations sur des objets différents fonctionne jusqu’au moment où il faut la modifier : alors les données répétées doivent être mises à jour partout, et tôt ou tard quelqu’un oublie. La normalisation est la théorie qui dit quand un schéma est bien fait et comment le corriger. Dans cette leçon, nous regardons les anomalies avec un exemple, les dépendances fonctionnelles et les axiomes d’Armstrong, la fermeture d’un ensemble d’attributs et le test de clé, le théorème de Heath avec sa démonstration, la forme normale de Boyce-Codd et la troisième forme normale.

Les anomalies

Considérons la table Examens(numéro, nom, code, titre, note), qui enregistre les examens avec le nom de l’étudiant et le titre du cours. Le nom d’un étudiant apparaît dans chacun de ses examens, le titre d’un cours dans chaque examen de ce cours. Trois anomalies apparaissent :

  • mise à jour : pour corriger le titre d’un cours, il faut modifier des centaines de lignes, et si l’on en saute une, les données deviennent incohérentes ;
  • insertion : on ne peut pas enregistrer un nouveau cours tant que personne n’en a passé l’examen, parce que la clé (numéro, code) exige un numéro d’étudiant ;
  • suppression : supprimer le dernier examen d’un cours fait perdre aussi son titre.

La cause est que la table représente trois concepts (étudiants, cours, examens) en un seul. La théorie des dépendances fonctionnelles le précise.

Les dépendances fonctionnelles

Étant donnés deux ensembles d’attributs X et Y d’une relation, X \to Y (X détermine Y) si deux n-uplets égaux sur X sont toujours égaux aussi sur Y. Dans l’exemple : numéro → nom, code → titre, (numéro, code) → note. Les dépendances fonctionnelles sont des règles du monde réel, comme les cardinalités du modèle E-A, et une clé K est exactement un ensemble d’attributs tel que K \to tous les attributs, de façon minimale.

À partir de certaines dépendances, on en déduit d’autres avec les axiomes d’Armstrong :

  • réflexivité : si Y \subseteq X, alors X \to Y ;
  • augmentation : si X \to Y, alors XZ \to YZ ;
  • transitivité : si X \to Y et Y \to Z, alors X \to Z.

Ils sont corrects (ils ne déduisent que des dépendances vraies) et complets (ils déduisent toutes celles qui découlent des dépendances initiales).

La fermeture et le test de clé

La fermeture X^+ d’un ensemble d’attributs est l’ensemble de tous les attributs déterminés par X. On la calcule en partant de X^+ = X et en ajoutant, tant que c’est possible, le membre de droite de chaque dépendance A \to B dont le membre de gauche A est déjà contenu dans X^+. X est une super-clé si et seulement si X^+ contient tous les attributs.

Dans l’exemple, \{number, code\}^+ : on part de {numéro, code}, on ajoute nom (à partir de numéro), titre (à partir de code), note (par la troisième dépendance) : tous les attributs, donc c’est une super-clé, et comme ni numéro ni code seuls ne suffisent, c’est une clé.

Décomposer sans perdre d’information

Normaliser veut dire décomposer une relation en relations plus petites. Mais la décomposition doit être sans perte : en remettant les parties ensemble avec la jointure naturelle, on doit retrouver exactement la relation d’origine, sans n-uplets parasites.

Décomposition sans perte d'une relation guidée par une dépendance fonctionnelle
La relation d’attributs X, Y, Z satisfait X détermine Y. Scindée en deux relations d’attributs X, Y et X, Z, elle se reconstruit exactement en joignant sur X : chaque valeur de X correspond à une seule valeur de Y, donc il ne naît pas de fausses combinaisons.

Théorème (Heath). Si une relation R(X, Y, Z) satisfait X \to Y, alors la décomposition en R_1 = \pi_{XY}(R) et R_2 = \pi_{XZ}(R) est sans perte : R_1 \bowtie R_2 = R.

Démonstration. *R \subseteq R_1 \bowtie R_2.* Chaque n-uplet (x, y, z) de R a pour projection (x, y) dans R_1 et (x, z) dans R_2, qui se recombinent en (x, y, z). *R_1 \bowtie R_2 \subseteq R.* Soit (x, y, z) un n-uplet de la jointure. Il vient de (x, y) \in R_1, projection d’un n-uplet (x, y, z_1) de R, et de (x, z) \in R_2, projection d’un n-uplet (x, y_2, z) de R. Les deux n-uplets de R sont égaux sur X, donc par la dépendance X \to Y ils sont égaux sur Y : y_2 = y. Alors (x, y_2, z) = (x, y, z) appartient à R. ∎

Sans la dépendance, la décomposition peut créer de faux n-uplets : si x_1 correspondait à la fois à y_1 et à y_2, la jointure combinerait chaque y avec chaque z de x_1, même ceux qu’on n’a jamais vus ensemble.

Les formes normales

Une relation est en forme normale de Boyce-Codd (BCNF) si, pour toute dépendance non triviale X \to Y, X est une super-clé. En mots : chaque fait que la table enregistre dépend de la clé, de toute la clé et de rien d’autre. La table Examens n’est pas en BCNF, parce que numéro → nom et que numéro n’est pas une super-clé. En appliquant deux fois le théorème de Heath, on obtient Étudiants(numéro, nom), Cours(code, titre) et Examens(numéro, code, note) : tous en BCNF, et les anomalies disparaissent. C’est le même schéma que la conception E-A aurait produit directement (leçon sur le modèle E-A).

La décomposition en BCNF est toujours possible sans perte, mais elle perd parfois une dépendance : on ne peut plus la vérifier à l’intérieur d’une seule table. Le cas typique : dans Leçons(étudiant, matière, enseignant), chaque enseignant enseigne une seule matière (enseignant → matière) et chaque étudiant a un seul enseignant par matière ((étudiant, matière) → enseignant). La mise en BCNF sépare (enseignant, matière) de (étudiant, enseignant), et la règle qui relie l’étudiant et la matière à l’enseignant ne peut plus être vérifiée dans une seule table. La troisième forme normale (3NF) est un peu plus permissive : elle admet X \to A même si X n’est pas une super-clé, pourvu que A fasse partie d’une clé. On peut démontrer que tout schéma peut toujours être amené en 3NF sans perte et en conservant toutes les dépendances.

En pratique, on normalise jusqu’à la 3NF ou la BCNF, et l’on dénormalise volontairement seulement là où il faut de la vitesse en lecture, comme dans les entrepôts de données (leçon sur les données distribuées), en acceptant de la redondance en échange de moins de jointures.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x