La quatrième forme normale (4NF)

Je tiens donc ici à remettre les pendules à l’heure à propos de la normalisation dans le contexte des bases de données relationnelles. En rangeant ma bibliothèque, j’ai redécouvert un petit livre (une centaine de pages) dans lequel la théorie de la normalisation est mise à mal.

Cet ouvrage, daté de 1986, s’intitule Les bases de données relationnelles ou le libre accès aux informations, a pour auteur Claude Jault et a été édité par les éditions d’organisation.

À la page 99 on lit ceci :

[...] un Tableau en Quatrième Forme Normale n’est pas en Troisième Forme Normale, ni même en Deuxième, tout simplement parce qu’il n’est pas en Première Forme Normale.

Tout simplement ! Waouh ! Le mot « tableau » est ambigu et me fait automatiquement penser à Excel, mais passons. Vu le titre de son ouvrage, notre auteur s’intéresse à la relation du Modèle Relationnel de Données de Codd. Ainsi il écrit (page 23) : « Le terme théorique employé est celui de Relation, qui a donné son nom aux Bases de Données Relationnelles : un système composé exclusivement de Relations, c’est-à-dire de Tableaux ».

Ma curiosité a été piquée, car tous les spécialistes du sujet démontrent que la quatrième forme normale (4NF) implique la forme normale de Boyce Codd (BCNF), laquelle comme on le sait implique la troisième forme normale (3NF), qui bien sûr implique la deuxième forme normale (2NF), qui à son tour implique la première forme normale (1NF). Bref, la 4NF implique la 1NF. Et pourtant, cerise sur le gâteau, nos spécialistes Fagin, Maier, Zaniolo, Date, Ullman, Korth, Delobel et Adiba, Gardarin, et j’en passe, sont renvoyés à leurs chères études par notre auteur ! Page 98 de l’ouvrage on lit en effet ceci, à propos de la 4NF et de la 5NF :

Tous les auteurs affirment que ces deux dernières Formes Normales sont incluses dans la Troisième, prolongeant de façon mécanique la série d’inclusion entre les Troisième, Deuxième et Première Formes Normales. Nous allons montrer que cette affirmation est fausse, car elle gêne énormément la compréhension des Quatrième et Cinquième Formes Normales.

Comme disait La Biscotte, « Eh ben, mon colon ! » Rien que ça ! Une enquête s’impose !

Je sollicite l’assistance d’un inspecteur qualifié… Image non disponible

À la page 99 de l’ouvrage, on peut donc lire ceci :

« En fait, un Tableau en Quatrième Forme Normale n’est pas en Troisième Forme Normale, ni même en Deuxième, tout simplement parce qu’il n’est pas en Première Forme Normale. En effet, la condition essentielle pour qu’un Tableau soit en Première Forme Normale est l’existence d’une Clef. »

La 4NF n’impliquerait donc pas la 1NF ? Celle-là je ne la connaissais pas ! j’y reviendrai en insistant lourdement.

Comme on l’a vu, pour l’auteur (page 23), le terme théorique utilisé pour un tableau est celui de Relation : soit. Il s’agit en fait de la variable relationnelle relvar du Modèle Relationnel de Données (cf. par exemple [Date2004]), sachant par ailleurs que l’extension d’un tableau correspond à la relation (valeur de relvar).

Pour les définitions des termes relvar et relation, je vous renvoie à cette occasion au paragraphe 1.3 de mon article Bases de données relationnelles et normalisation (https://fsmrel.developpez.com/basesrelationnelles/normalisation/?page=1#L1.3).

Je traduis en termes relationnels d’usage ce qu’écrit notre auteur (page 99), voir les quelques lignes ci-dessus :

En fait, une relvar en quatrième forme normale n’est pas en troisième forme normale, ni même en deuxième, tout simplement parce qu’elle n’est pas en première forme normale. En effet, la condition essentielle pour qu’une relvar soit en première forme normale est l’existence d’une clé.

Pour confirmer ou invalider un tel propos, il est nécessaire de bien définir quelques concepts fondamentaux à la lumière de la théorie relationnelle.

Qu’est-ce qu’une clé ? On reviendra sur ce concept essentiel après un détour du côté de la modélisation merisienne des données.
Quelle est la définition de la première forme normale (1NF) ?
Quelle est la définition de la dépendance fonctionnelle ?
Quelle est la définition de la dépendance multivaluée ?
Quelle est la définition de la quatrième forme normale (4NF) ?

On passera tout cela en revue.

Avant tout cela, afin d’illustrer son point de vue, page 82, notre auteur part bille en tête sur la structure de ce qu’il appelle donc un tableau, structure correspondant à l’en-tête H d’une relvar, ou d’une table SQL (variable de table pour être précis), c’est-à-dire la liste des attributs composant H. La structure qui nous est proposée est la suivante (façon relation universelle) :

Produit (NoProd, Nofourn, NomFourn, DesignProduit, PA, PV, NoAcheteur, NomAcheteur)

Informations et règles de gestion que l’on peut déduire à la lecture de cette page :

(RG01) La société X achète des produits à des fournisseurs.
(RG02) Un produit a un numéro qui l’identifie, une désignation et un prix de vente.
(RG03) Un acheteur (employé de la société X) est un responsable de l’achat de produits. Un acheteur a un numéro qui l’identifie et son nom.
(RG04) Un fournisseur a un numéro qui l’identifie et son nom.
(RG05) Un fournisseur a des conditions de règlement.
(RG06) Un fournisseur a des conditions de livraison.

Autres règles de gestion glanées :

(RG07) Chaque produit peut être acquis par différents acheteurs de la société X.
(RG08) Un acheteur peut acquérir différents produits.
(RG09) Un fournisseur peut fournir plusieurs produits.
(RG10) Un produit donné peut être fourni par différents fournisseurs.
(RG11) Le prix d'achat d'un produit est fixé par chaque fournisseur.

Page 83 : je prends note que, quels que soient les produits qu'il fournit, un fournisseur définit ses conditions de règlement et de livraison. Je note aussi qu’aucun détail n’est fourni sur ces conditions de règlement et de livraison (par exemple le tarif de livraison lié au montant de la commande, etc.) Mais en l’occurrence ça n’est pas gênant.

Sur ces bases, voulant y voir bien clair, je me précipite vers Looping (mâtin, quel AGL ! Image non disponible ) pour produire un MCD :

Figure 2.1 – MCD Produit

Notre auteur ne proposant pas lui-même de MCD, les cardinalités 1,n sont ici fournies sur la base de leur finalité. Par exemple, un acheteur achètera au moins un produit (sinon ça ne serait pas un acheteur) et un fournisseur propose au moins un produit, etc. Puisque notre auteur est muet sur le détail des conditions de règlement et de livraison, les attributs des entités-types correspondantes (Regl, Liv) se résumeront à un attribut unique (respectivement CondRegl et CondLiv).

Le code SQL proposé par Looping :

Sélectionnez

CREATE TABLE Acheteur
(
   NoAcheteur SMALLINT,
   NomAcheteur VARCHAR(24) NOT NULL,
   CONSTRAINT Acheteur_PK PRIMARY KEY(NoAcheteur)
);
CREATE TABLE Produit
(
   NoProd SMALLINT,
   DesignProd VARCHAR(48) NOT NULL,
   PV SMALLINT NOT NULL,
   CONSTRAINT Produit_PK PRIMARY KEY(NoProd)
);
CREATE TABLE Fournisseur
(
   NoFourn SMALLINT,
   NomFourn VARCHAR(24) NOT NULL,
   CONSTRAINT Fournisseur_PK PRIMARY KEY(NoFourn)
);
CREATE TABLE Liv
(
   NoFourn SMALLINT,
   CondLiv VARCHAR(50),
   CONSTRAINT Liv_PK PRIMARY KEY(NoFourn, CondLiv),
   CONSTRAINT Liv_Fournisseur_FK FOREIGN KEY(NoFourn) REFERENCES Fournisseur(NoFourn)
);
CREATE TABLE Regl
(
   NoFourn SMALLINT,
   CondRegl VARCHAR(50),
   CONSTRAINT Regl_PK PRIMARY KEY(NoFourn, CondRegl),
   CONSTRAINT Regl_Fournisseur_FK FOREIGN KEY(NoFourn) REFERENCES Fournisseur(NoFourn)
);
CREATE TABLE FouPro
(
   NoProd SMALLINT,
   NoFourn SMALLINT,
   PA INT NOT NULL,
   CONSTRAINT FouPro_PK PRIMARY KEY(NoProd, NoFourn),
   CONSTRAINT FouPro_Produit_FK FOREIGN KEY(NoProd) REFERENCES Produit(NoProd),
   CONSTRAINT FouPro_Fournisseur_FK FOREIGN KEY(NoFourn) REFERENCES Fournisseur(NoFourn)
);
CREATE TABLE ProAch
(
   NoAcheteur SMALLINT,
   NoProd SMALLINT,
   CONSTRAINT ProAch_PK PRIMARY KEY(NoAcheteur, NoProd),
   CONSTRAINT ProAch_Acheteur_FK FOREIGN KEY(NoAcheteur) REFERENCES Acheteur(NoAcheteur),
   CONSTRAINT ProAch_Produit_FK FOREIGN KEY(NoProd) REFERENCES Produit(NoProd)
);

Les tables produites par Looping sont-elles en 4NF du point de vue de la théorie relationnelle ? Comme évoqué plus haut, il est d’abord nécessaire de revenir sur certains concepts fondamentaux de cette théorie : clé d’une relvar, dépendance fonctionnelle, dépendance multivaluée, première forme normale (1NF), quatrième forme normale (4NF), et tant qu’à faire les formes normales intermédiaires. Quand faut y aller, faut y aller !

IV-A. À propos des clés▲

IV-A-1. Qu’est-ce qu’une clé selon la théorie relationnelle ?▲

Dans son article fondateur [Codd1970], E.F. Codd écrit :

« A relation may possess more than one nonredundant primary key ».

Autrement dit, en termes d’aujourd’hui, une clé primaire est une clé candidate pour une relvar. Codd précise :

« Whenever a relation has two or more nonredundant primary keys, one of them is arbitrarily selected and called the primary key of that relation ».

De façon équivalente, 20 ans plus tard, dans [Codd1990] page 23 :

The value of the primary key in each row of the pertinent R-table identifies that row uniquely (i.e., it distinguishes that row from every row in that R-Table) ;
If the primary key is composite and if one of the columns is dropped from the primary key, the first property is no longer guaranteed.

Peaufinage par C. J. Date, notamment dans [Date2004], [Date2019] :

Une clé K est un sous-ensemble d’attributs de l’en-tête H d’une variable relationnelle R (table en SQL) ayant pour objet de s’assurer que dans R on ne puisse pas avoir deux tuples (lignes) ayant la même valeur (propriété d’unicité). Par ailleurs, cet ensemble K est ce qu’on appelle une surclé (superkey) de R. Si K est irréductible, c’est-à-dire s’il n’existe pas de sous-ensemble K’ d’attributs (colonnes de) K garantissant lui aussi la propriété d’unicité des tuples, alors la clé K est qualifiée de candidate.

À noter qu’un sous-ensemble d’une clé candidate est appelé sous-clé (sous-ensemble strict si l’inclusion est stricte, mais qui ne garantit pas l’unicité des tuples).

Ici, la variable relationnelle R est une relvar. L’en-tête H de R est constitué de l’ensemble des attributs dont est dotée R.

Ces définitions de Codd et Date sont en phase et n’ont jamais été remises en question par la communauté des théoriciens du Relationnel.

En complément, je fais observer qu’une relation r (valeur d’une relvar R) étant un ensemble, il n’est donc pas possible que deux de ses composants (tuples, n-uplets) aient la même valeur (cf. ci-dessus la règle d’unicité) ; cette relation ne peut pas être un « sac à tuples » ! sinon les opérateurs relationnels (dont les opérandes sont des relations ou des relvars) seraient inexploitables (union, différence, produit cartésien, projection, restriction, jointure, etc.). Pour que l’unicité soit garantie, la relation r (considérée comme relation universelle) possède donc implicitement une clé (plus précisément une surclé) composée de l’ensemble des noms de ses attributs. Dans le sens de ce que dit Date ci-dessus, cette clé est possiblement réductible en fonction des règles de gestion qui sont données, réduction qui devient nécessaire quand on utilise un SGBDR et qu’on ne veut pas transformer la relation r en sac (bag), ce qui est malheureusement possible si le SGBDR propose SQL comme langage.

Les tables qui ont été fournies par Looping ont chacune une clé, en cela elles sont conformes à la théorie relationnelle.

IV-A-2. Qu’est-ce qu’une clé pour notre auteur ?▲

Pages 84-85 de l’ouvrage en cause :

On entend par Clef une Colonne ou un ensemble de Colonnes capable d’identifier de façon unique chacune des autres Colonnes sans exception.

Par « identifier les autres colonnes », on comprend que notre auteur a l’intention de garantir une certaine règle d’unicité, mais le principe fondamental de l’unicité des tuples (lignes) est passé sous silence, donc non formellement garanti. En outre, le principe de l’irréductibilité des clés candidates est passé lui aussi sous silence.

Page 100 :

Une Clef est une Colonne ou groupe de Colonnes identifiant toutes les autres de façon unique, c’est-à-dire qu’elle est l’origine des Dépendances Fonctionnelles.

Comme disait Einstein : « Faites simple, mais pas plus simple ! » Ainsi notre auteur oublie une chose, c’est qu’il n’y a pas que les dépendances fonctionnelles qui soient parties prenantes dans cette affaire. En effet, qui dit clé et DF, dit BCNF, mais c’est très limitatif. Je cite [Date2019], page 249 :

R est en BCNF si et seulement si chaque dépendance fonctionnelle vérifiée par R est impliquée par les clés de R.
R est en 4NF si et seulement si chaque dépendance multivaluée vérifiée par R est impliquée par les clés de R.
R est en 5NF si et seulement si chaque dépendance de jointure vérifiée par R est impliquée par les clés de R.

Ainsi, ce qui vaut pour les dépendances fonctionnelles, mutatis mutandis, vaut aussi pour les dépendances multivaluées et pour les dépendances de jointure ! En oubliant cela, notre auteur va se noyer et partir dans un délire étonnant, du genre (page 100) :

« Il n’y a pas de clé dans un Tableau en Quatrième Forme Normale, et celui-ci n’est pas en Première Forme Normale. »

Sa copie mérite d’être amendée (euphémisme, pour rester poli)…

IV-B. À propos de la normalisation▲

IV-B-1. Première forme normale (1NF)▲

(a) Qu’est-ce que la 1NF pour notre auteur ?

Page 100 :

La condition essentielle pour qu’un tableau soit en première forme normale est l’existence d’une Clef.

(b) Pour [Date2019] :

Soit une relation r (c’est-à-dire une valeur d’une relvar R) dont l’en-tête est constitué des attributs A1, …, An, respectivement de type T1, …, Tn. La relation r est en première forme normale (1NF) si et seulement si pour chaque tuple appartenant à r, la valeur de l’attribut Ai est du type Ti (i = 1, …, n). Voir aussi les contraintes décrites par C.J. Date.

Les deux définitions sont radicalement différentes ! En fait, de par sa nature ensembliste, la relation r est de facto en 1NF. À défaut, les opérateurs ensemblistes de l’algèbre relationnelle ne pourraient être utilisés. Pour mémoire, je rappelle la définition que Codd donne de la relation (cf. [Codd1970]) :

The term relation is used here in its accepted mathematical sense. Given sets S1, S2, …, Sn (not necessarily distinct), R is a relation on these n sets if it is a set of n-tuples each of which has its first element from S1, its second element from S2, and so on. We shall refer to Sj as the jth domain of R.

(c) Dans son article de 1971 (cf. [Codd1971]), Codd définit la première forme normale (1NF) :

A relation is in first normal form if it has the property that none of its domains has elements which are themselves sets.

Dans cet article, Codd utilise l’expression « first normal form » car elle est accompagnée de deux autres formes normales, à savoir la deuxième forme normale (2NF) qui implique la 1NF et la troisième forme normale (3NF) qui implique la 2NF.

Dans [Date2006], C. J. Date remet en cause la définition de Codd (éléments qui sont des ensembles), mais ceci ne nous concerne pas ici. Retenons simplement que, du fait de sa nature ensembliste, une relation (ou une relvar) est ontologiquement en 1NF, et ce n’est qu’au stade SQL qu’il devient nécessaire de définir des clés, pour garantir qu’une table ne soit pas un sac (lignes en double…).

Bref, comme dit Date, « Normalized and first normal form mean exactly the same thing »

IV-B-2. À propos de la dépendance fonctionnelle▲

Par référence à [Date2019] :

Soit H un en-tête de relvar. Une dépendance fonctionnelle (DF) relative à H est une expression de la forme X → Y, où X (le déterminant) et Y (le dépendant) sont deux sous-ensembles d’attributs de H.

Soit r une relation d’en-tête H et F une DF X → Y relative à H. Si pour toutes les paires de tuples t1 et t2 de r on a t1{X} = t2{X} et t1{Y} = t2{Y}, alors F est vérifiée pour r.

Concernant les relvars : la relvar R fait l’objet de la dépendance fonctionnelle F si et seulement si chaque relation qui peut être affectée à R vérifie F.

La description informelle donnée par notre auteur (page 84) est conforme.

À noter le cas particulier de la DF triviale : la DF X → Y est triviale si Y est un sous-ensemble non strict de X (Y ⊆ X).

IV-C. Rappels concernant les formes normales impliquant les dépendances fonctionnelles▲

À partir d’ici, quand je ne cite pas les définitions, je fais référence à [Date2019].

IV-C-1. Deuxième forme normale (2NF)▲

La relvar R est en deuxième forme normale (2NF) si et seulement si, pour chaque clé K de R et chaque attribut non clé A de R, la dépendance fonctionnelle K → {A} dans R est irréductible.

Rappel du principe de l’irréductibilité : K est irréductible s’il n’existe pas K’ ⊂ K tel que K’ → {A}.

Variante (qui a la préférence de Date, qui s’inspire des définitions données par Carlo Zaniolo dans [Zaniolo1982], car il les a trouvées particulièrement élégantes et faciles à retenir, dans le mécanisme de l’enchaînement, c’est-à-dire de l’inférence des formes normales) :

La relvar R est en deuxième forme normale (2NF) si et seulement si pour chaque DF X → Y non triviale vérifiée par R, au moins l'une des conditions suivantes est satisfaite :

X est une surclé.
Y est une sous-clé.
X n’est pas une sous-clé.

IV-C-2. Troisième forme normale▲

La relvar R est en troisième forme normale (3NF) si et seulement si pour chaque DF X → Y non triviale vérifiée par R, au moins l'une des conditions suivantes est satisfaite :

X est une surclé.
Y est une sous-clé.

IV-C-3. Forme normale de Boyce Codd (BCNF)▲

La relvar R est en BCNF si et seulement si pour chaque DF X → Y non triviale vérifiée par R, la condition suivante est satisfaite :

X est une surclé.

Des trois définitions qui précèdent (grand merci à Zaniolo !), on infère que la BCNF implique la 3NF qui à son tour implique la 2NF :

BCNF => 3NF => 2NF

IV-D. Vers la 4NF▲

IV-D-1. À propos de la dépendance multivaluée▲

Soit H un en-tête de relvar. Une dépendance multivaluée (DMV) relative à H est une expression de la forme X →→ Y, où X (le déterminant) et Y (le dépendant) sont deux sous-ensembles d’attributs de H.

Soit r une relation d’en-tête H et M une DMV X →→ Y relative à H ; soit Z le sous-ensemble des attributs de H qui n’appartiennent ni à X ni à Y (en d’autres termes, Z est le complément de l’union de X et Y par rapport à H). Si pour toutes les paires de tuples t1 et t2 de r il existe un tuple t3 tel que t3{X} = t1{X} et t3{Y} = t1{Y}, alors M est vérifiée pour r.

Par symétrie, il y a aussi un tuple t4 dans Y tel que t4{X} = t1{X}, t4{Y} = t2{Y} et t4{Z} = t1{Z}.

Concernant les relvars : la relvar R fait l’objet de la DMV M si et seulement si chaque relation r qui peut être affectée à R vérifie M.

Par référence à [Fagin1977], sa proposition 3 :

Soit une relvar R {X, Y, Z} où X, Y et Z représentent des sous-ensembles d’attributs de R. Étant donnés <x, y, z> et <x, y’, z’> deux tuples appartenant à R, la dépendance multivaluée X →→ Y est vérifiée si et seulement si les tuples <x, y’, z> et <x, y, z’> appartiennent aussi à R.

X et Y ne sont pas nécessairement disjoints. Z est disjoint de X et Y (Z = H — X — Y).

Pour signifier que X →→ Y et X →→ Z sont des dépendances multivaluées indissociables de R, on note ainsi :

X →→ Y | Z

Sous forme tabulaire :

X	Y	Z
x	y	z
x	y	z’
x	y’	z
x	y’	z’

Figure 4.1 – Forme tabulaire

Un exemple repris de [Date2019]

Le cours CNO peut être donné par le professeur TNO, lequel utilisera le support de cours XNO (quel que soit ce professeur).

CNO	TNO	XNO
C1	T1	X1
C1	T1	X2
C1	T2	X1
C1	T2	X2

Figure 4.2 – relvar CTX, exemple de valeur

IV-D-2. Dépendance multivaluée triviale▲

Soit X et Y deux sous-ensembles d’attributs de l’en-tête H d’une relvar R.

La dépendance multivaluée X →→ Y est triviale si et seulement si :

ou bien Y est un sous-ensemble de X ;
ou bien l’union de X et de Y (au sens de la théorie des ensembles) est égale à l’en-tête H de la relvar R. Par exemple, si H est composé de trois attributs A, B et C, la DMV {A, B} →→ {C} est triviale. Mais les DMV {A} →→ {B} et {A} →→ {C} ne le sont pas.

Si {A} →→ {B} | {C} est triviale, alors {C} est l’ensemble vide {}.

IV-D-3. Définition de la 4NF▲

[Fagin1977]

Un schéma de relation R* est en quatrième forme normale (4NF) si, pour chaque dépendance multivaluée non triviale X →→ Y valant pour R, la dépendance fonctionnelle X → A vaut aussi pour chaque nom de colonne A de R*.

[Date2019]

Une relvar R est en 4NF si et seulement si pour chaque dépendance multivaluée non triviale X →→ Y valant pour R, X est une surclé de R (en d’autres termes cette dépendance multivaluée dégénère en dépendance fonctionnelle X → Y).

À noter le théorème 3 de Fagin ([Fagin1977]) :

If a relation schema R* is not in 4NF, then there is a nonloss decomposition of R* into a 4NF family of relation schemata.

On en déduit que si le schéma de relation R* ne comporte que des dépendances multivaluées triviales, celles-ci n’étant pas décomposables sans perte, on ne peut pas en inférer d’autres schémas 4NF, donc R* est en 4NF.

C’est ce que rappelle Zaniolo (cf. [Zaniolo1981] :

A relation which contains only trivial MDs is called atomic. Such a relation is in fourth normal form (4NF) as defined by Fagin.

On peut donc donner une variante de la 4NF (qui du reste est la définition donnée dans [Korth1986], page 358) :

Soit R une relvar et X et Y des sous-ensembles d’attributs quelconques de l’en-tête H de R.
R est en quatrième forme normale (4NF) si pour chaque dépendance multivaluée X →→ Y vérifiée dans R :

ou bien cette dépendance multivaluée est triviale,
ou bien X détermine fonctionnellement tous les attributs de R (X est alors une surclé de R).

Signalons que les tables FouPro et ProAch figurant dans le code SQL issu du MCD décrit dans la figure 2.1 contiennent respectivement les DMV triviales {NoProd, NoFourn} →→ {PA} et (NoAcheteur, NoProd} →→ ∅.

Notons en passant ce qu’écrit C. J. Date [Date2019] (page 248) :

Image non disponible

« The whole point about the 4NF definition is that the only MVDs that hold in a 4NF relvar are ones we cant’ rid of—which means ones implied by keys (including trivial ones as a special case). »

C’est-à-dire que les seules dépendances multivaluées présentes dans une relvar en 4NF sont celles dont on ne peut pas se débarrasser, c’est-à-dire celles qui sont impliquées par les clés (y-compris celles qui sont triviales).

IV-D-4. Une dépendance fonctionnelle est une dépendance multivaluée▲

Reprenons la définition de la dépendance multivaluée :

Soit une relvar R {X, Y, Z} où X, Y et Z représentent des sous-ensembles d’attributs de l’en-tête H de R (X et Y ne sont pas nécessairement disjoints). Étant donnés < x, y, z > et < x, y’, z’ > deux tuples appartenant à R, la dépendance multivaluée X →→ Y est vérifiée si et seulement si les tuples < x, y’, z > et < x, y, z’ > appartiennent aussi à R (cf. Figure 4.1).

Et passons à la règle de réplication.

Maintenant, si une relvar R vérifie la dépendance fonctionnelle X → Y, alors pour tous les tuples < x, y, z > et < x, y’, z’ > de R, on a y = y’. Il s’ensuit que la condition d’existence des tuples < x, y’, z > et < x, y, z’ > est de facto vérifiée, en vertu de quoi la dépendance multivaluée X →→ Y est vérifiée elle aussi, ce qui donne lieu à la règle dite de réplication (très importante pour la suite !) :

Si X → Y alors X →→ Y.

À cette occasion je cite [Fagin 1977]) :

Proposition 1

If X and Y are disjoint, and if the functional dependency X → Y holds for a relation R, then the multivalued dependency X →→ Y also holds for R.

Ou encore Georges Gardarin (https://sgbd.developpez.com/tutoriels/cours-complet-bases-de-donnees/?page=conception-des-bases-de-donnees#LXXII-7) :

(X → Y) ⇒ {(x, y, z) et (x, y’, z’) ∈ R ⇒ y = y’}

Donc (X → Y) ⇒ {(x, y, z) et (x, y’, z’) ∈ R ⇒ (x, y’, z) et (x, y, z’) ∈ R}

Par suite (X → Y) ⇒ X →→ Y)

V-A. Rapports entre la 4NF et la 1NF▲

Je reviens sur ce que nous dit notre auteur (page 99) :

En fait, un Tableau en Quatrième Forme Normale n’est pas en Troisième Forme Normale, ni même en Deuxième, tout simplement parce qu’il n’est pas en Première Forme Normale.

Tout simplement ? Image non disponible Ça mérite évidemment quelques commentaires… Je ne reviens pas sur la 1NF, puisqu’une relvar est de facto en 1NF.

V-B. Rapports entre la 4NF et la BCNF▲

Je rappelle la définition de la BCNF donnée plus haut :

La relvar R est en BCNF si et seulement si pour chaque DF X → Y non triviale vérifiée par R, la condition suivante est satisfaite :
X est une surclé.

Soit R une relvar en 4NF. Si R n’est pas en BCNF, il existe donc forcément une DF X → Y non triviale dans laquelle X n’est pas clé. Par réplication la DF X → Y donne lieu à la DMV X →→ Y, mais X n’étant pas clé, R viole la 4NF : contradiction !

Moralité : Si R est en 4NF, elle respecte nécessairement la BCNF. La 4NF implique la BCNF.

N.B. La DF X → Y provoquant le viol de la BCNF peut éventuellement être la cause d’un viol de 2NF ou de 3NF, peu importe ici.

Notre auteur met en cause cette démonstration de l’implication de la BCNF par la 4NF, en s’attaquant à celle donnée par Delobel et Adiba dans leur ouvrage bases de données et systèmes relationnels ([Delobel1982], page 409) :

La 4FN implique la 3FNBCK. En effet supposons qu’un schéma R soit en 4FN et pas en 3FNBCK. D’après la définition de la 3FNBCK il existe une dépendance X → Y où X ne contient pas une clé. Si X → Y est vérifiée dans R la dépendance multivaluée X →→ Y l’est aussi. Or puisque R est 4FN, X doit contenir une clé, d’où la contradiction.

À noter que la phrase suivante sous-entend la mise en œuvre de la règle de réplication :

Si X → Y est vérifiée dans R la dépendance multivaluée X →→ Y l’est aussi.

Page 98, notre auteur écrit donc :

« Les seuls auteurs apportant une démonstration de cette prétendue inclusion de la Quatrième dans la Troisième Forme Normale sont Delobel et Adiba (dans leur ouvrage Bases de Données et Systèmes Relationnels) »

Heu… Je fais humblement remarquer qu’en 1977, Ronald Fagin (soit dit en passant inventeur de la quatrième forme normale), a fait cette démonstration dans son article Multivalued Dependencies and a New Normal Form for Relational Databases (cf. [Fagin1977]), et dans cet article, la démonstration de Fagin fait l’objet d’un théorème (Theorem 2). Et d’autres l’ont fait à leur tour dans son sillage ! (cf. [Ullman1982], [Maier1983], j’en passe et des meilleurs, avant que ne soit publié l’ouvrage qui met en cause Delobel et Adiba…). Publié la même année (1986), [Korth1986] qui n’oublie pas de démontrer à son tour l’implication de la BCNF par la 4NF.

V-C. Rapports entre la 4NF et la 2NF▲

Etant donné que notre auteur fera référence à l’implication de la 2NF par la 4NF, commençons par démontrer cette implication.

Soit R une relvar en 4NF dotée d’une clé X. Si R n’est pas en 2NF, il existe une DF non triviale X’ → Y avec X’ ⊂ X et Y ⊄ X’. Par application de la règle de réplication (grand merci décidément à cette règle magique !), la DF X’ → Y donne lieu à la DMV X’ →→ Y, mais X’ n’étant pas clé, R viole la 4NF : contradiction !

Ainsi R qui est en 4NF doit aussi respecter la 2NF, elle l’implique.

Comme le reconnaît notre auteur (page 98), la 2NF implique la 1NF, donc quand il prétend qu’un « tableau » en 4NF n’est pas en 1NF, il a encore tout faux.

Notre auteur se substitue à Delobel et Adiba, en leur prêtant des propos qui ne sont pas les leurs ! À savoir une démonstration de son cru de l’implication de la BCNF par la 4NF, dans laquelle il laisse de côté la BCNF pour se cantonner à la 3NF. Voici ce qu’il fait dire à Delobel et Adiba, page 99 :

Si R n’est pas en Troisième Forme Normale, c’est qu’il subsiste au moins une dépendance transitive. Il existe donc au moins un ensemble d’Attributs (Colonnes) X, qui ne soit pas ou ne contienne pas une Clef, tel que X identifie de façon unique un autre Attribut Y : X → Y. Si on a X → Y, on a aussi X →→ Y, puisque la Dépendance Fonctionnelle est un cas particulier de la Dépendance Multivaluée. Or, dans une Relation en 4e FN, l’identifiant X est forcément une Clef (la relation étant composée de deux attributs, l’un est Clef de l’autre). Si X est une Clef, la Dépendance X → Y n’est pas Transitive. S’il n’y a pas de Dépendance Transitive, la Relation est en Troisième Forme Normale.

Dans la foulée, il commente sa propre prose.

Ainsi quand il écrit :

Si R n’est pas en Troisième Forme Normale, c’est qu’il subsiste au moins une dépendance transitive.

C’est qu’il se focalise sur la 3NF, alors que Delobel et Adiba s’intéressent pour leur part à la BCNF. Et il commente :

Ceci suppose que R soit en Deuxième Forme Normale, ce qui reste à démontrer.

Pourquoi pas ? À toutes fins utiles, je signale quand même que j’en ai fourni la démonstration en début de paragraphe.

Plus grave, il se prend les pieds dans le tapis quand il écrit :

Image non disponible

« puisque R est en 4e FN, on ne peut avoir X → Y, mais seulement X →→ Y. »

Il a tout bonnement oublié de tenir compte de la définition donnée par Fagin de la 4NFDéfinition de la 4NF et reprise par les tous les bons auteurs…

Dans sa prétendue démonstration, il énonce d’autres curiosités de son cru du genre :

Image non disponible

« dans une Relation en 4e FN, l’identifiant X est forcément une Clef (la relation étant composée de deux attributs, l’un est Clef de l’autre) »

Qu’il commente ainsi :

Image non disponible

« Le terme de Clef est impropre ici ; Identifiant non discriminant. »

Ainsi, une relation en 4NF n’a pas de clé, mais un « identifiant non discriminant » (sic), concept (page 89) que notre auteur a pêché on ne sait où, si ce n’est pas une pure invention de sa part. Fait-il de loin référence à l’identifiant de l’entité-type merisienne ? Quoi qu’il en soit, dans un MCD, un identifiant authentique fait systématiquement l’objet d’une clé lors du passage au MLD et à SQL (voyez avec Looping). Qui plus est, une relation en 4NF peut être dotée de plus de deux attributsEncore une bourde. Et je rappelle une fois de plus ce qu’a écrit C.J. Date :

R est en BCNF si et seulement si chaque dépendance fonctionnelle vérifiée par R est impliquée par les clés de R.
R est en 4NF si et seulement si chaque dépendance multivaluée vérifiée par R est impliquée par les clés de R.
R est en 5NF si et seulement si chaque dépendance de jointure vérifiée par R est impliquée par les clés de R.

Et notre auteur de conclure en apothéose à propos de la démonstration qu’il prête à Delobel et Adiba :

Image non disponible

« Cette démonstration ne démontre donc rien. En effet elle suppose au départ que le Tableau (Relation) en Quatrième Forme Normale est en Deuxième Forme Normale, ce qui est faux »

De fait mon bon Monsieur, contrairement à Fagin, Delobel et Adiba, vous ne démontrez rien, mais en tout cas, ne vous déplaise, la 4NF implique bien la 2NF, on vous l’a prouvé !

Encore une fausse perle :

Image non disponible

« … de ce présupposé erroné est déduit la présence d’une Dépendance Fonctionnelle entre les Colonnes (Attributs) X et Y, ce qui est impossible puisqu’en Quatrième Forme Normale ne peut subsister qu’une Dépendance Multivaluée élémentaire.»

Vous avez dit « élémentaire » ? Ben voyons, élémentaire, mon cher Watson ! Image non disponible

Et sa conclusion péremptoire :

Image non disponible

« Il n’y a pas de Clef dans un Tableau en Quatrième Forme Normale, et celui-ci n’est donc pas en Première Forme Normale. »

Comme l’écrit Wittgenstein dans sa proposition 7 du Tractatus :

Sur ce dont on ne peut pas parler, il faut garder le silence.

VI-A. Rapports entre la 4NF et la 3NF▲

Pour être complet, je rappelle cette définition de la 3NF, donnée par C. J. Date (définition de la 2NF moins le point (c)) :

La relvar R est en troisième forme normale (3NF) si et seulement si pour chaque DF X → Y non triviale vérifiée par R, au moins l'une des conditions suivantes est satisfaite :

X est une surclé.
Y est une sous-clé.

Soit R une relvar en 4NF. Si R n’est pas en 3NF, X n’est pas surclé et Y n’est pas sous-clé (il existe une DF transitive où Y n’est pas sous-clé). Mais R étant en 4NF, X est surclé : contradiction !

Ainsi R respecte aussi la 3NF.

VI-B. Une relvar BCNF est-elle 4NF ?▲

On peut utiliser un contre-exemple pour montrer qu’une relvar peut être en BCNF, mais pas en 4NF. Partons de celui proposé par C.J. Date (« What's Normal Anyway? », Database Programming & Design, Volume 11 - Number 3, March 1998).

Règles de gestion de données suivantes, appliquées à une variante de l'exemple classique des cours dispensés par des enseignants :

(RG01) Un enseignant enseigne au moins un sujet ;
(RG02) Un sujet est enseigné par au moins un enseignant ;
(RG03) Un sujet comporte au moins un thème ;
(RG04) Un thème fait partie d'au moins un sujet ;
(RG05) Quel que soit le sujet traité, il n'existe pas de relation particulière entre les enseignants et les thèmes ;
(RG06) Toutefois, quand un enseignant traite d'un thème, c'est dans le cadre d'un seul sujet.

Soit STE la relvar obtenue à partir des règles de gestion :

STE {Sujet, Enseignant, Thème}

Ce que veut dire Date avec la règle RG05, c'est que les règles RG02 et RG03 donnent lieu aux dépendances multivaluées :

DMV1 : {Sujet} →→ {Enseignant}

DMV2 : {Sujet} →→ {Thème}

Les deux dépendances multivaluées peuvent être ainsi formulées (en une seule ligne) :

{Sujet} →→ {Enseignant} | {Sujet} →→ {Thème}

Le déterminant {Sujet} de ces dépendances multivaluées n’est pas clé candidate de la relvar STE qui n’est donc pas en 4NF.

La règle RG06 fait quant à elle l'objet de la dépendance fonctionnelle :

DF1 : {Enseignant, Thème} → {Sujet}

Le déterminant {Enseignant, Thème} de cette dépendance fonctionnelle est clé candidate de la relvar STE qui est donc en BCNF.

Conclusion : ce contre-exemple, dans lequel une relvar est en BCNF mais pas en 4NF, montre bien que la BCNF n’implique pas la 4NF.

Un instantané de la relvar STE (clé soulignée) :

STE	Sujet	Enseignant	Thème
	Modélisation Conceptuelle des Données	Paprick	Informatisation des modèles
	Modélisation Conceptuelle des Données	Paprick	Etudes de cas
	Modélisation Conceptuelle des Données	Escartefigue	Informatisation des modèles
	Modélisation Conceptuelle des Données	Escartefigue	Etudes de cas
	Le Modèle Relationnel de Données	Ted	Le calcul relationnel
	Le Modèle Relationnel de Données	Ted	Etudes de cas
	SGBD SQL	Fred	SQL Server
	SGBD SQL	Fred	PostgreSQL
	SGBD SQL	Fred	MySQL
	SGBD SQL	CinePhil	PostgreSQL
	SGBD SQL	CinePhil	MySQL
	SGBD SQL	CinePhil	SQL Server
	Arduino	Fabien	Le manuel de laboratoire
	Arduino	Fabien	Les Quiz
	Arduino	Fabien	Les cahiers pratiques
	Arduino	Fabien	Les sources et outils

VI-C. Encore une bourde▲

Notre auteur écrit ceci (page 100) :

« Le processus de normalisation que nous venons de détailler a donc pour but de se prémunir contre la redondance d’informations et contre les difficultés de mise à jour. »

Jusque-là on ne peut qu’être d’accord. Mais ensuite, ça se gâte :

« Lorsqu’il est conduit à son terme, ne subsistent que deux types de tableaux :

Des tableaux en forme normale de Boyce-Codd c’est-à-dire en troisième forme normale avec éventuellement, normalisation de Boyce-Codd ;
Des tableaux binaires exprimant chacun une dépendance multivaluée élémentaire. »

Certes, les tableaux binaires sont en 4NF. Cela dit, peuvent subsister des tableaux non binaires, eux aussi en 4NF…

Partons du MCD merisien suivant, reprenant l’exemple proposé par C.J. Date (Figure 4.2, relvar CTX) et prenant en compte la durée :

le cours CNO peut être donné par le professeur PNO ;
le support de cours SNO est utilisé pour le cours CNO ;
pour le cours CNO, le professeur PNO passe Jours jours avec le support SNO.

Figure 6.1 - MCD - Association CPSJ

Code SQL produit par Looping :

Sélectionnez

CREATE TABLE Cours(
   CNO VARCHAR(50),
   CONSTRAINT Cours_PK PRIMARY KEY(CNO)
);
CREATE TABLE Support(
   SNO VARCHAR(50),
   CONSTRAINT Support_PK PRIMARY KEY(SNO)
);
CREATE TABLE Prof(
   PNO VARCHAR(50),
   CONSTRAINT Prof_PK PRIMARY KEY(PNO)
);
CREATE TABLE CPSJ(
   CNO VARCHAR(50), PNO VARCHAR(50), SNO VARCHAR(50), Jours INT NOT NULL,
   CONSTRAINT CPSJ_PK PRIMARY KEY(CNO, PNO, SNO),
   CONSTRAINT CPSJ_Cours_FK FOREIGN KEY(CNO) REFERENCES Cours(CNO),
   CONSTRAINT CPSJ_Prof_FK FOREIGN KEY(PNO) REFERENCES Prof(PNO),
   CONSTRAINT CPSJ_Support_FK FOREIGN KEY(SNO) REFERENCES Support(SNO)
);

Un exemple de contenu :

CPSJ	CNO	PNO	SNO	Jours
	C1	P1	S1	7
	C1	P1	S2	8
	C1	P2	S1	9
	C1	P2	S2	6

Figure 6.2 - relvar CPSJ, exemple de valeur

La table CPSJ est bien en 4NF, car les dépendances multivaluées sont emboîtées (embedded), la table n’est pas décomposable par projection, puis recomposable par jointure. Avec SQL, le contrôle des redondances sera à effectuer au moyen d’un trigger…

[Codd1970] E. F. Codd.- A Relational Model of Data for Large Shared Data Banks
https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf
[Codd1971] E. F. Codd. - Further Normalization of the Data Base Relational Model. IBM Research Report, RJ909, San Jose (August 31, 1971).
https://forum.thethirdmanifesto.com/wp-content/uploads/asgarosforum/987737/00-efc-further-normalization.pdf
[Codd1974] E. F. Codd – Recent Investigations into Relational Data Base Systems (Proc. IFIP Congress, Stockholm, Sweden (North-Holland 1974)
https://www.fsmwarden.com/Codd/rec-1975.pdf
[Codd1990] E. F. Codd – The Relational Model For Database Management Version 2. Reading, Mass – Addison-Wesley (1990).
https://dl.acm.org/doi/pdf/10.5555/77708
[Date2004] C. J. Date - An Introduction to Database Systems, Eighth Edition - Addison-Wesley (2004).
https://www.amazon.fr/INTRODUCTION-DATABASE-SYSTEMS-8TH/dp/0321197844
[Date2006] C. J. Date - Date on Database, Writings 2000-2006 – Apress (2006)
https://dl.acm.org/doi/10.5555/2339432
[Date2019] C. J. Date - Database Design and Relational Theory Normal Forms and All That Jazz, Second Edition.
https://www.oreilly.com/library/view/database-design-and/9781484255407
[Delobel1982] C. Delobel, M. Adiba – bases de données et systèmes relationnels – Dunod informatique (Bordas, 1982).
https://openlibrary.org/books/OL3255139M/Bases_de_donne%CC%81es_et_syste%CC%80mes_relationnels
[Fagin1977] Ronald Fagin - Multivalued Dependencies and a New Normal Form for Relational Databases. Transactions on Database Systems ACM, Vol.2, No 3. Pp 262-278.
https://dl.acm.org/doi/10.1145/320557.320571
[Gardarin1982] Bases de données Les systèmes et leurs langages (Editions Eyrolles). L’ouvrage est accessible sous forme de PDF.
http://georges.gardarin.free.fr/Livre_BD_Contenu/XX-TotalBD.pdf
Troisième édition (1985) :
https://ia804601.us.archive.org/28/items/eyrolles-georges-gardarin-bases-de-donnees-les-systemes-et-leurs-langages/Eyrolles%20-%20Georges%20Gardarin%20-%20Bases%20de%20donn%C3%A9es%20-%20Les%20syst%C3%A8mes%20et%20leurs%20langages_text.pdf
[Jault1986] C. Jault - Les bases de données relationnelles ou le libre accès aux informations (éditions d’organisation, 1986)
https://www.le-livre.fr/livres/fiche-r160216774.html
[Korth1986] H.F. Korth, A. Silberschatz. Database System Concepts. (McGraw-Hill International Editions, 1986).
https://codex.cs.yale.edu/avi/db-book/db6/slide-dir/
[Maier1983] D. Maier. The Theory of Relational Databases. (Computer science Press, 1983).
https://web.cecs.pdx.edu/~maier/TheoryBook/TRD.html
https://web.cecs.pdx.edu/~maier/TheoryBook/MAIER/C07.pdf
[Ullman1982] Principles of Databases Systems (Computer Science Press)
https://www.amazon.com/Principles-Database-Systems-Jeffrey-Ullman/dp/0914894366
Ullman, en compagnie de H.G. Molina et J. Widom - Database Systems: The Complete Book - PDF :
https://docs.google.com/file/d/0B4L0JCXT2DekZjM1MDJmNTUtYjY4Mi00MGI2LWEzYjYtNGYxOGQ5NDgyYTFl/view?resourcekey=0-ahFkVDbBIEM8wzoSf_Wv4A
[Zaniolo1981] On the Design of Relational Database Schemata (ACM Transactions on Database Systems, Volume 6, Issue 1 pp 1–47)
https://dl.acm.org/doi/10.1145/319540.319542
[Zaniolo1982] A New Normal Form for the Design of Relational Database Schemata (ACM TODS 7, No 3)
https://web.cs.ucla.edu/~zaniolo/papers/tods82b.pdf

Défense et illustration de la quatrième forme normale (4NF)

L'auteur

L'article

Liens sociaux

I. De la remise à l’heure des pendules▲

II. Retour aux fondamentaux▲

III. À propos du schéma de relation proposé par l’auteur▲

IV. Retour à la théorie relationnelle▲

IV-A. À propos des clés▲

IV-A-1. Qu’est-ce qu’une clé selon la théorie relationnelle ?▲

IV-A-2. Qu’est-ce qu’une clé pour notre auteur ?▲

IV-B. À propos de la normalisation▲

IV-B-1. Première forme normale (1NF)▲

IV-B-2. À propos de la dépendance fonctionnelle▲

IV-C. Rappels concernant les formes normales impliquant les dépendances fonctionnelles▲

IV-C-1. Deuxième forme normale (2NF)▲

IV-C-2. Troisième forme normale▲

IV-C-3. Forme normale de Boyce Codd (BCNF)▲

IV-D. Vers la 4NF▲

IV-D-1. À propos de la dépendance multivaluée▲

IV-D-2. Dépendance multivaluée triviale▲

IV-D-3. Définition de la 4NF▲

IV-D-4. Une dépendance fonctionnelle est une dépendance multivaluée▲

V. Retour à la thèse de l’auteur▲

V-A. Rapports entre la 4NF et la 1NF▲

V-B. Rapports entre la 4NF et la BCNF▲

V-C. Rapports entre la 4NF et la 2NF▲

VI. Annexes▲

VI-A. Rapports entre la 4NF et la 3NF▲

VI-B. Une relvar BCNF est-elle 4NF ?▲

VI-C. Encore une bourde▲

VII. Bibliographie▲