A propos de la deuxième forme normale (2NF)
Considérons l’énoncé suivant, que l’on retrouve un peu partout, car compatible avec ce qu’a écrit Codd en 1971 (voir par exemple A Data Base Sublanguage Founded on the Relational Calculus, IBM Research Report RJ893 (July 26th 1971)) :
Pour qu’une relation soit en 2NF, il faut qu’elle soit en 1NF et que toutes les dépendances fonctionnelles entre la clé primaire et les autres attributs de la relation soient élémentaires.
En fait, il l y a un trou dans la raquette. Il s’agit de démontrer que cette définition est incomplète, qu’elle doit être renforcée.
On peut commencer par lui faire subir une cure d’amaigrissement, en effet on a vu précédemment (post #15 par exemple) qu’une relation est forcément en 1NF, il est donc inutile de rappeler cette contrainte dans la définition de la 2NF. Par contre, on doit la conserver si au lieu d’une relation coddienne, on a une table SQL, car les doublons y sont autorisés (cf. post #15).
Il faut aussi se mettre d’accord sur ce qu’est une dépendance fonctionnelle, et plus précisément ce qu’est une dépendance fonctionnelle élémentaire.
Soit une relvar R, et X et Y deux sous-ensembles quelconques d'attributs inclus dans l'en-tête H de R.
Une dépendance fonctionnelle (DF pour abréger) est une expression de la forme X → Y dans laquelle X joue le rôle de déterminant et Y celui de dépendant. Pour faire court, une DF est une contrainte voulant que pour une valeur de X il y ait exactement une valeur de Y. Pour une définition formelle, se reporter au dictionnaire de C. J. Date, The New Relational Database Dictionary.
Par référence aux définitions données ici, je rappelle qu’une dépendance fonctionnelle est soit triviale, soit partielle, soit irréductible (l’adjectif élémentaire peut être utilisé à la place de celui d’irréductible, mais il est plus vague).
La dépendance fonctionnelle X → Y est dite triviale si Y est inclus dans X (inclusion au sens large). Une DF triviale est inviolable (axiome de réflexivité).
Pour illustrer, prenons l’exemple ci-dessous de la relvar FPV des fournisseurs, des pièces des quantités et des villes (ce qu’on montre sous forme tabulaire est un instantané de la relvar, autrement dit une valeur, plus formellement une relation) :
Le fournisseur Four_No fournit la pièce Piece_No selon la quantité Quantite et réside dans la ville Ville.
Règles de gestion particulières, imposées en amont par le chef de projet et la maîtrise d’oeuvre :
(RG01) Un fournisseur donné ne fournit une pièce donnée qu’en une quantité donnée, unique.
(RG02) Un fournisseur donné ne réside que dans une seule ville
FPV {Four_No Piece_No Quantite Ville}
S1 P1 300 Lille
S1 P2 200 Lille
S1 P3 400 Lille
S1 P4 200 Lille
S1 P5 100 Lille
S1 P6 100 Lille
S2 P1 300 Paris
S2 P2 400 Paris
S3 P2 200 Paris
S4 P2 200 Lille
S4 P4 300 Lille
S4 P5 400 Lille
{Four_No} → {Four_No}
{Piece_No, Quantite} → {Quantite}
{Four_No, Piece_No, Quantite, Ville} → {Four_No, Piece_No, Quantite, Ville}
Etc.
Revenons à la relvar R et ses sous-ensembles d’attributs X et Y, et soit C un attribut quelconque de l’en-tête de R.
La dépendance fonctionnelle X → {C} est dite partielle si elle n'est pas triviale et s'il existe Y strictement inclus dans X tel que Y → {C}.
Par exemple, du fait de la règle de gestion RG02, la relvar FPV contient la DF {Four_No} → {Ville}. Cette DF n’est pas triviale car {Ville} n’est pas un sous-ensemble de {Four_No}. Elle n’est pas non plus partielle car {Four_No} ne contient pas de sous-ensemble non vide qui y soit strictement inclus.
Par contre, la DF {Four_No, Piece_No} → {Ville} inférée de la règle RG01 est partielle, car le déterminant {Four_No, Piece_No} contient le sous-ensemble {Four_No} tel que {Four_No} → {Ville}.
La dépendance fonctionnelle X → Y est dite irréductible (ou élémentaire ou totale, au choix) si elle n’est ni triviale ni partielle.
Dans le cas de la relvar FPV, la DF {Four_No} → {Ville} n’étant ni triviale ni partielle, elle est irréductible.
Comme on l’a vu, il existe la DF {Four_No, Piece_No} → {Quantite} traduisant la règle RG01. Cette DF n’est ni triviale ni partielle, elle est donc irréductible elle aussi.
Passons au clés.
Soit une relvar R d’en-tête H = {A1, A2, ..., An}, où A1, A2, ..., An sont les (noms des) attributs.
Soit K un sous-ensemble (non strict) d’attributs de H.
Je rappelle que K est surclé de R si et seulement si K vérifie la propriété suivante :
—
Unicité : deux
tuples (lignes en SQL) distincts de R ne peuvent avoir la même valeur pour K.
Ou encore, histoire de faire intervenir les dépendances fonctionnelles (cf. Principles of Database Systems de J. D. Ullman) :
K est surclé si et seulement si
K → {A1}
K → {A2}
...
K → {An}
Je rappelle en outre que K est clé candidate de R si et seulement si K vérifie les deux propriétés suivantes (dont la propriété d’unicité qui vient d’être énoncée) :
— Unicité : deux tuples distincts de R ne peuvent avoir la même valeur pour K.
— Irréductibilité : il n’existe pas de sous-ensemble strict de K garantissant la règle d’unicité.
Ainsi, la clé candidate est un cas particulier de la surclé.
A noter qu’un sous-ensemble non strict S d’une clé candidate K est appelé sous-clé. Ainsi, la clé candidate est une sous-clé particulière. Si S est un sous-ensemble strict de K, alors S est une sous-clé stricte.
Dans le cas de la relvar FPV, le quadruplet {Four_No, Piece_No, Quantite, Ville} est une surclé. Est-ce une clé candidate ? Démontrons-le.
Jusque-là on a les DF irréductibles suivantes :
{Four_No} → {Ville}
{Four_No, Piece_No} → {Quantite}
Pour trouver l’ensemble des clés candidates d’une relvar, on sort l’artillerie lourde, à savoir l’algorithme du seau. Dans notre exemple, on peut prendre un raccourci selon lequel si un attribut n’est élément d’aucun dépendant de DF non triviale, alors il appartient nécessairement aux clés candidates de la relvar.
En vertu de quoi, dans le cas de la relvar FPV, les attributs Four_No et Piece_No appartiennent aux clés de cette relvar. La paire {Four_No, Piece_No} est-elle clé candidate ? Autrement dit vérifie-t-elle les règles d’unicité et d’irréductibilité des clés candidates ?
Pour qu’il en soit ainsi, en reprenant la règle d’unicité selon Ullman, on doit montrer que :
{Four_No, Piece_No} → {Four_No}
{Four_No, Piece_No} → {Piece_No}
{Four_No, Piece_No} → {Quantite}
{Four_No, Piece_No} → {Ville}
La 1re et la 2e DF sont triviales, donc automatiquement vérifiées.
La 3e DF est donnée (conséquence de la règle de gestion RG01).
Concernant la 4e DF, c’est un peu moins simple, pour l’obtenir on est obligé de partir de la DF donnée {Four_No} → {Ville} et de la soumettre à l’algorithme du seau, ou directement aux axiomes d’Armstrong. Utilisons ceux-ci :
Partant de la DF {Four_No} → {Ville}, dans un 1er temps, par augmentation on produit la DF
{Four_No, Piece_No} → {Ville, Piece_No}
Puis dans un 2e temps, en utilisant la règle de décomposition, on produit les deux DF :
{Four_No, Piece_No} → {Piece_No}
{Four_No, Piece_No} → {Ville}
La 1re DF est triviale, la 2e est celle que l’on voulait obtenir pour compléter la liste des DF permettant de garantir la règle d’unicité. On vérifie sans problème que la propriété d’irréductibilité est respectée.
Il ne manque pas une seule des DF voulues, la paire {Four_No, Piece_No} est donc clé candidate de la relvar FPV. En existe-t-il d’autres ? Prenez votre seau à dépendants et remplissez-le, vous verrez bien (ça occupe...).
Quoi qu’il en soit, revenons à l’énoncé initial de la deuxième forme normale. Je le reprends ici (débarrassé de la contrainte de 1NF), car il met en scène « la clé primaire » :
Pour qu’une relation soit en 2NF, il faut que toutes les dépendances fonctionnelles entre la clé primaire et les autres attributs de la relation soient élémentaires.
Jusqu’ici on a parlé des clés candidates mais pas des clés primaires. En fait, le concept de clé primaire a été défini par Codd dans son article fondateur de 1970, A Relational Model of Data for Large Shared Data Banks, alors qu’il n’a défini le concept de clé candidate qu’un peu plus tard (voir par exemple A Data Base Sublanguage Founded on the Relational Calculus, IBM Research Report RJ893 (July 26th 1971) ou encore Further Normalization of the Data Base Relational Model, IBM Research Report RJ909 (August 31st 1971)).
Je cite (et traduis) Codd :
Pour chaque relation R, une de ses clés candidates est arbitrairement désignée comme clé primaire.
On voit immédiatement qu’il s’agit d’un choix arbitraire, menant donc à des considérations plus psychologiques que mathématiques. Autant dire qu’aujourd’hui la théorie relationnelle a été nettoyée, le concept de clé primaire en est sorti et ne relève plus que de l’histoire du relationnel, on n’a plus que des clés candidates (on peut faire désormais l’économie de l’adjectif candidate). Evidemment, si on regarde du côté SQL, du fait du poids de l’héritage, on ne peut décemment pas évacuer le concept et modifier tous les CREATE/ALTER TABLE pondus depuis le début des années quatre-vingts, et concernant des tables encore bien vivantes...
Bon, conservons les clés primaires :D. La relvar FPV est-elle en 2NF ?
La paire {Four_No, Piece_No} étant clé candidate on la prend pour clé primaire de la relvar. On a vu qu’elle est le déterminant dans les DF suivantes :
{Four_No, Piece_No} → {Four_No}
{Four_No, Piece_No} → {Piece_No}
{Four_No, Piece_No} → {Quantite}
{Four_No, Piece_No} → {Ville}
En particulier, la DF {Four_No, Piece_No} → {Ville} n’est pas triviale, mais partielle. Je rappelle la définition :
La dépendance fonctionnelle X → {C} est dite partielle si elle n'est pas triviale et s'il existe Y strictement inclus dans X tel que Y → {C}.
Symbolisons {Four_No, Piece_No} par X, {Four_No} par Y et Ville par C.
Du fait de la DF donnée {Four_No} → {Ville}, c’est-à-dire Y → {C}, comme Y est bien strictement inclus dans X, la DF {Four_No, Piece_No} → {Ville} est de facto partielle, elle n’est donc pas élémentaire.
La relvar FPV a pour clé primaire la paire {Four_No, Piece_No} qui intervient en tant que déterminant dans la DF {Four_No, Piece_No} → {Ville}. Cette DF n’est pas élémentaire mais seulement partielle. Conclusion : la relvar n’est pas en 2NF.
So far so good. L’histoire n’est pourtant pas terminée. Ajoutons à l’en-et tête de FPV un attribut fpvId, tel que {fpvId} soit clé candidate. On a donc désormais deux clés candidates, {fpvId} et {Four_No, Piece_No}.
Dans le style SQL :
CREATE TABLE FPV
(
fpvId INTEGER NOT NULL
, Four_No INTEGER NOT NULL
, Piece_No INTEGER NOT NULL
, Quantite INTEGER NOT NULL
, Ville VARCHAR(48) NOT NULL
, CONSTRAINT FPV_PK PRIMARY KEY (fpvId)
, CONSTRAINT FPV_AK UNIQUE (Four_No, Piece_No)
) ;
{fpvId} → {fpvId}
{fpvId} → {Four_No}
{fpvId} → {Piece_No}
{fpvId} → {Quantite}
{fpvId} → {Ville}
La DF {fpvId} → {fpvId} est triviale, elle compte pour du beurre. Quant aux autres, leur déterminant {fpvId} étant singleton, elles sont élémentaires.
Pour reprendre une fois de plus l’énoncé proposé de la 2NF :
Pour qu’une relation soit en 2NF, il faut que toutes les dépendances fonctionnelles entre la clé primaire et les autres attributs de la relation soient élémentaires.
En l’occurrence, on voit qu’est élémentaire chaque DF ayant pour déterminant la clé primaire {fpvId} et pour dépendant un autre attribut de l’en-tête de la relvar.
Cette fois-ci la relvar FPV, de clé primaire {fpvId} est en 2NF.
Le constat : selon la clé candidate retenue pour être clé primaire, dans un cas la relvar FPV viole la 2NF, dans l’autre cas elle la respecte... Autrement dit, la définition de la 2NF est à changer ! 8O
Allons-y. Appelons attribut non-clé tout attribut de l’en-tête d’une relvar R qui n’appartient à aucune clé candidate de R.
On peut alors donner la définition suivante, due à C. J. Date (Database Design and Relational Theory, Normal Forms and All That Jazz) :
La relvar R est en deuxième forme normale (2NF) si et seulement si pour chaque clé candidate K de R et chaque attribut non-clé A de R, la DF K → {A} est élémentaire.
Comme je l’ai écrit, le préfère irréductible à élémentaire, car plus précis, mais bon.
Avec cette nouvelle définition de la 2NF, comment les choses se passent-elles avec la relvar FPV (d’en-tête {fpvId, Four_No, Piece_No, Quantite, Ville}) ?
On dispose des clés candidates suivantes :
K1 = {fpvId}
K2 = {Four_No, Piece_No}
Certes, K1 ne pose pas de problème, mais avec K2 ça coince. il existe en effet la DF K2 → {Ville} qui n’est pas élémentaire, mais partielle, la 2NF est donc violée.
Moralité : Mieux vaut s’appuyer sur la bonne définition de la 2NF et évacuer la définition fautive.
■
Dans l’ouvrage que j’ai cité, C. J. Date donne une définition supplémentaire, mais évidemment équivalente de la 2NF :
La relvar R est en deuxième forme normale (2NF) si et seulement si pour chaque DF non triviale X → Y valant pour R, au moins une des conditions suivantes est vérifiée :
(a) X est surclé
(b) Y est sous-clé
(c) X n’est pas sous-clé
Cas de FPV :
Passons par exemple à la moulinette la DF {Four_No, Piece_No} → {Ville} : le déterminant {Four_No, Piece_No} est clé candidate, donc surclé, il s’ensuit que la condition (a) est vérifiée, ainsi cette DF n’est pas délinquante, même si les conditions (b) et (c) ne sont pas vérifiées (notamment concernant (c), puisqu’une clé candidate est un cas particulier de la sous-clé).
Passons à son tour la DF {Four_No} → {Ville} à la moulinette. {Four_No} n’est pas surclé, la condition (a) n’est donc pas vérifiée. {Ville} n’est pas sous-clé, la condition (b) n’est donc pas vérifiée. {Four_No} est sous-clé, la condition (c) n’est donc pas vérifiée. Conclusion : à cause de cette DF qui ne satisfait à aucune des conditions, FPV viole la 2NF.
Je ne vais repasser le film avec la 3NF, je préfère énoncer celle-ci, telle que nous la fournit C. J. Date :
La relvar R est en troisième forme normale (3NF) si et seulement si pour chaque DF non triviale X → Y valant pour R, au moins une des conditions suivantes est vérifiée :
(a) X est surclé
(b) Y est sous-clé
On observera que la définition de la 3NF est celle de la 2NF, sauf que la condition (c) en est absente. Il s’ensuit que la 3NF implique de facto la 2NF, qu’une relvar en 3NF est forcément en 2NF, et que l’on peut faire l’économie du sempiternel « R est en 3NF si elle est en 2NF et... ».
Dans la foulée, allons-y pour la forme normale de Boyce Codd (BCNF) :
La relvar R est en forme normale de Boyce Codd (BCNF) si et seulement si pour chaque DF non triviale X → Y valant pour R, X est une surclé.
La définition de la BCNF est celle de la 3NF, sauf que la condition (b) en est absente. Il s’ensuit que la BCNF implique de facto la 3NF, qu’une relvar en BCNF est forcément en 3NF, et que l’on peut faire l’économie du sempiternel « R est en BCNF si elle est en 3NF et... ».
On observera encore qu’avec la 2NF on a jusqu’à 3 possibilités de s’en sortir, seulement 2 d’entre elles dans le cas de la 3NF, et seulement une d’entre elles dans le cas de la BCNF.
D’un point de vue heuristique, on a toutes ses chances de perdre moins de temps à vérifier la normalisation si on s’attaque directement à la BCNF.
