1 Les Formes Normales

Les formes normales de schémas de relations sont définies dans le but de réduire les
redondances de données, par rapport aux contraintes de données. Ce cours présente

les formes normales par rapport aux dépendances fonctionnelles.

EXEMPLE 1 Soit R = ABC et F = {A → B, BC → A}. Soit r une relation (voir

Figure 1) sur le schéma R. On peut observer que r ∈ Sat(F ).

La relation r n’a pas de redondance par rapport à la DF BC → A, car chaque n-uplet

satisfaisant BC → A est unique dans r. Cependant, Par rapport à la DF A → B, la

relation r contient de redondance de données: Les deux n-uplets de r sont identiques

sur AB. Or avec la dépendance A → B, la répétition de a b est inutile.

r: A B C
a b c
a b c0
Figure 1:

Notons que BC et AC sont les deux clé de R, et A n’est pas une clé de R.

Définition 1 (Forme Normale Boyce-Codd (FNBC)) Soit R un schéma de re-

lation, et F un ensemble de DFs définies sur R. Le schéma R est en FNBC par rapport
à F ssi pour toute DF f = X → Y ∈ F + , f est triviale ou X est une sur-clé de R.

Remarque: Par la définition 2, tout schéma de relation composé d’un ou de deux

attributs est en FNBC.

Dans l’exemple 1, le schéma R = ABC n’est pas en FNBC par rapport à F = {A →

B, BC → A}, car A → B n’est pas triviale et A n’est pas une sur-clé de R. En

revanche, on peut vérifier que le schéma U = ABCD est en FNBC par rapport à
F = {A → B, B → C, C → D, D → A}.

Bases de Données - V. Phan Luong 1

Théorème 1 Soit F un ensemble de DFs définies sur un schéma de relation R. Si R
est en FNBC par rapport à F , alors pour toute relation r sur R, r ∈ Sat(F ), r n’a pas
de redondance de données, par rapport à F .

Théorème 2 Soit F un ensemble de DFs définies sur un schéma de relation R. Alors

R est en FNBC par rapport à F ssi pour toute DF f = X → Y ∈ F , f est triviale ou

X est une sur-clé de R.

Un schéma de relation en forme normale Boyce-Codd n’aura pas de redondance de

données. Cependant, dans le contexte de décomposition SPI et SPD,la contrainte

imposée par cette forme normale n’est pas toujours satisfaite. Une autre forme normale,
dont la contrainte est plus faible, mais plus facile à être satisfaite dans le contexte de

décomposition SPI et SPD, est connue sous le nom de la troisième forme normale. Un
schéma en cette forme normale peut avoir de redondance de données.

Définition 2 (Troisième Forme Normale (3FN)) Soit R un schéma de relation,

et F un ensemble de DFs définies sur R. Le schéma R est en 3FN par rapport à F ssi

pour toute DF f = X → A ∈ F + , où A est un attribut, telle que A 6∈ X, X est une

sur-clé de R ou A est premier.

Il est clair qu’un schéma en FNBC est aussi en 3FN, mais l’inverse n’est pas vrai. Par

exemple, on a montré que le schéma R = ABC n’est pas en FNBC par rapport à
F = {A → B, BC → A}. Cependant, R est en 3FN par rapport à F . En effet, les
clés de R sont AC et BC, et pour toute X → I ∈ F + , où I est un attribut, telle que

I 6∈ X, on a X = A ou X = AC ou X = BC (d’après les dérivations en utilisant le

système d’Armstrong). Si X = A, alors I = B ∈ BC, donc I est premier. Si X = AC

ou X = BC alors X est une sur-clé de R. Donc, R est en 3FN par rapport à F .

Théorème 3 Soit R un schéma de relation, et F un ensemble de DFs définies sur R.

R est en 3FN par rapport à F ssi pour toute DF f = X → Y ∈ F , X est une sur-clé
de R ou pour tout attribut A ∈ Y \ X, A est premier.

Bases de Données - V. Phan Luong 2

2 Décompositions et formes normales

Définition 3 Soit S = {R1 , ..., Rk } une décomposition d’un univers U . Soit F un

ensemble de DFs définies sur U . S est une décomposition en forme normale Boyce-
Codd (ou en 3FN) de U , par rapport à F ssi pour tout schéma Ri , 1 ≤ i ≤ k, Ri est

en forme normale Boyce-Codd (ou en 3FN) par rapport à FRi .

La décomposition est nécessaire lors de la présence de redondance de données. Si U

est en FNBC (par rapport à F ), alors la décomposition n’est pas nécessaire. Sinon, on
cherche une bonne décomposition de U . L’idéale est de trouver une décomposition S
qui satisfait les trois conditions suivantes:

1. S est SPI par rapport à F , et

2. S est SPD par rapport à F , et

3. S est en FNBC par rapport à F .

Cependant, une telle décomposition peut ne pas exister. Dans l’exemple 1, on sait
que le stockage de données sur R = ABC peut avoir de redonndance de données, par

rapport à F = {A → B, BC → A}, mais toute décomposition de R ne satisfait pas à

la fois les trois critères ci-dessus.

Bases de Données - V. Phan Luong 3

2.1 Décomposition SPI et FNBC

Algorithme DecomposeF N BC (voir plus loin) appliqué à un schéma U et un ensemble

F de DFs produit une décomposition SPI de U en forme normale FNBC. Cet algorithme
successivement décompose U , si cela est nécessaire, en appelant l’algorithme F N BC

ci-dessous.
Algorithme FNBC

Entrée: Un schéma Z ⊆ U (|Z| ≥ 3) et un ensemble F de DFs (non triviales)

définies sur U .

Sortie: {Z} si Z est en FNBC, sinon {XF+ ∩ Z, (Z − XF+ ) ∪ X}.

Méthode:

1. Tant qu’il existe X → Y ∈ F qui n’est pas encore utilisée telle que X ⊂ Z faire

(a) X 0 = X; // Garder la valeur initiale de X

(b) Tant que |Z − X| ≥ 2 et XF+ ∩ Z ⊂ Z faire

Si X ⊂ XF+ ∩ Z alors retourne {XF+ ∩ Z, X ∪ (Z − XF+ )};

S’il existe P ⊂ Z (P 6= ∅ et P n’est pas encore utilisé) tel que

|Z − X 0 P | ≥ 2, alors X = X 0 P ;

Sinon, X = Z; // Pour terminer la boucle

(c) fait;

2. fait;

3. Retourne Z;

Remarques:

– Dans la boucle au point (b), si X ⊂ XF+ ∩ Z (déjà on a XF+ ∩ Z ⊂ Z), alors Z

est non FNBC, par la DF X → XF+Z . Donc, l’algorithme s’arrête en retournant la

décomposition SPI {XF+ ∩ Z, X ∪ (Z − XF+ )}.

Bases de Données - V. Phan Luong 4

– Sinon (X = XF+ ∩ Z) on cherche à augmenter X (d’un ensemble P ) pour trouver une
nouvelle DF applicable sur Z. Si cela est possible on re-exécuter la boucle. Autrement,
on termine la boucle au point (b), pour passer à la boucle au point (a) et chercher une

autre DF de F .
– Finalement, s’il n’existe aucune violation de FNBC par les DFs applicales sur Z,

alors Z est FNBC, et on le retourne intact.

Algorithme DecomposeFNBC

Entrée: Un univers U et un ensemble F de DFs définies sur U .

Sortie: Une décomposition S = {R1 , ..., Rk } de U , qui est SPI et FNBC.

Méthode:

1. S := {U };

2. Tant que S change et il existe Z ∈ S tel que |Z| ≥ 3 faire

S := (S − {Z}) ∪ F N BC(Z, F, U )

3. fait

4. Retourne S.

EXEMPLE 2 Soit U = CP HSEN , et

F = {C → P, HS → C, HP → S, CE → N, HE → S}

Une exécution de l’algorithme DecomposeFNBC sur U et F :

S = {U }.

Pour Z = U = CP HSEN ; X = C; XF+ ∩ Z = CP 6= X et CP ⊂ Z. Donc,

S = {CP, CHSEN }

Bases de Données - V. Phan Luong 5

Pour Z = CHSEN ; X = HS; XF+ ∩ Z = HSC 6= X et HSC ⊂ Z. Donc,

S = {CP, CHS, HSEN }

Pour Z = CHS, Notons que déjà on a utilisé les DFs C → P et HS → C, et il n’y

a pas d’autre DF de F dont la partie gauche est inclus dans CHS. Donc, on ne peut
pas décomposer CHS (d’après l’algorithme FNBC). CHS est en FNBC.

Pour Z = HSEN , Pour X = HE (HE → S n’est pas encore utilisée), XF+ ∩ Z =

HSEN = Z. Pour la même raison que ci-dessus, on ne cherche pas à augmenter X.
Et on ne trouve pas d’autres parties gauches de DF de F qui satisfont les conditions

ci-dessus. Donc, on ne peut pas décomposer HSEN (d’après l’algorithme FNBC).

Ainsi, on on obtient le résultat final

S = {CP, CHS, HSEN }

Une autre exécution de l’algorithme DecomposeFNBC sur U et F :

S = {U }.

Pour Z = U = CP HSEN ; X = CE; XF+ ∩ Z = CEN P ⊂ Z. Donc,

S = {CEN P, CEHS}

Pour Z = CEN P ; pour X = C; XF+ ∩ Z = CP ⊂ Z. Donc, Z est décomposé en

{CP, CEN }, où CP et CEN sont en FNBC.

Pour Z = CEHS; pour X = HS; XF+ ∩ Z = HSC ⊂ Z. Donc, Z est décomposé en

{HSC, HSE}, où HSC et HSE sont en FNBC.

Ainsi, le résultat final est

S = {CP, CEN, HSC, HSE}

Bases de Données - V. Phan Luong 6

Théorème 4 L’algorithme DecomposeFNBC (versions 1 et 2) est correct, c’est-à-dire,
le résultat retourné est une décomposition SPI et FNBC.

2.2 Décomposition SPI, SPD et 3FN

Algorithme 3FN
Entrée: Un univers U et un ensemble F de DFs définies sur U .

Sortie: Une décomposition S = {R1 , ..., Rk } de U , qui est SPI, SPD et 3FN.
Méthode:

1. Soit G une couverture minimale de F , R = att(G), ensemble des attributs figurés

dans les DFs de G, et Z = U − att(G).
2. S = {}.

3. Si Z 6= ∅, alors S = S ∪ {Z}.
4. S’il existe X → A ∈ G telle que R ⊆ XA alors S = S ∪ {XA},

5. Sinon, pour chaque X → A ∈ G faire S = S ∪ {XA}.

6. Si S ne contient pas de clé de U , alors chercher une clé K de U , et

S = S ∪ {K}

7. Retourne S.

Théorème 5 L’algorithme 3FN est correct, c’est-à-dire, le résultat retourné est une

décomposition SPI, SPD et 3FN, par rapport à F .

Bases de Données - V. Phan Luong 7

EXEMPLE 3 Soit U = ABCDE et

F = {A → BC, C → A, D → E, C → B}

Réduire les parties droites de DFs de F :

F 0 = {A → B, A → C, C → A, D → E, C → B}

Les parties gauches de DFs sont déjà réduites. En enlevant les DFs redondantes, on

obtient une couverture minimale de F :

G = {A → C, C → A, D → E, C → B}

R = U et Z = ∅.

A l’étape 5 de l’algorithme, S = {AC, BC, DE} qui ne contient pas de clé de U . En

ajoutant AD une clé de U :

S = {AC, AD, BC, DE}

est une décomposition SPI, SPD et 3FN de U , par rapport à F .

Bases de Données - V. Phan Luong 8