I. De la remise à l’heure des pendules▲
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é…
II. Retour aux fondamentaux▲
À 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.
III. À propos du schéma de relation proposé par l’auteur▲
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 !) pour produire un MCD :
![Image non disponible](./images/MCD-produit(80).png)
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 :
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)
)
;
IV. Retour à la théorie relationnelle▲
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 :
|
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) :
|
IV-C-2. Troisième forme normale▲
|
IV-C-3. Forme normale de Boyce Codd (BCNF)▲
|
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) :
|
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) :
|
« 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 !) :
|
À cette occasion je cite [Fagin 1977]) :
Proposition 1 |
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. Retour à la thèse de l’auteur▲
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 ? Ç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 : |
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 :
|
« 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 :
|
« 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 :
|
« 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 :
|
Et notre auteur de conclure en apothéose à propos de la démonstration qu’il prête à Delobel et Adiba :
|
« 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 :
|
« … 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 !
Et sa conclusion péremptoire :
|
« 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. Annexes▲
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)) :
|
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.
![Image non disponible](./images/ctxd-mcd.png)
Figure 6.1 - MCD - Association CPSJ |
Code SQL produit par Looping :
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…
![Image non disponible](./images/Hubuc(70).jpg)
VII. Bibliographie▲
-
[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