5.1 - CLE DE RELATION
Une clé de relation R(A1, ..., An) est un sous ensemble X des attributs tel que :
Dans la BD "Avion", NUM-VOL est une clé de la relation VOL.
Toute relation possède au moins une clé : A1, ..., An -> A1, ..., An, il suffit d'éliminer les Ai jusqu'à la vérification des 2 conditions.
Une relation peut avoir plusieurs clés, on en choisit en général une comme clé primaire, les autres sont appelées clés candidates.
5.2 - LES TROIS PREMIERES FORMES NORMALES
Ces formes ont été introduites par Codd pour décomposer les relations sans pertes.
5.2.1 Première forme normale
Une relation est en 1NF si tout attribut est atomique.
Chaque attribut ne peut être décomposé en plusieurs autres. La relation PERSONNE(AGE, ADRESSE) n'est pas en 1NF si par exemple on a ADRESSE(VILLE, RUE, NUMERO).
5.2.2 Deuxième forme normale
Une relation est en 2NF ssi :
1) elle est en 1NF,
2) tout attribut n'appartenant pas à une clé ne dépend pas que d'une partie de cette clé.
Si l'on choisit la clé primaire NUM-VOL, la relation VOL est en 2NF.
Si l'on choisit la clé (NUM-AV, H-D), la relation VOL n'est pas en 2NF car NOM-AV, LOC-AV, CAP-AV ne dépendent que d'une partie de la clé NUM-AV.
Dans le cas précédent, on doit décomposer la relation VOL de manière à n'avoir que des relations en 2NF.
Par exemple :
AVION(NUM-AV, NOM-AV, LOC-AV, CAP-AV)
VOL1(NUM-VOL, NUM-AV, NUM-PIL, NOM-PIL, ADR-PIL, H-D, V-D, H-A, V-A)
5.2.3 Troisième forme normale
Une relation est en 3NF ssi
1) elle est en 2NF,
2) tout attribut n'appartenant pas à une clé ne dépend pas d'un attribut non clé.
PILOTE(NUM-PIL, NOM-PIL, ADR-PIL) est en 3NF.
AVION(NUM-AV, NOM-AV, LOC-AV, CAP-AV) n'est pas en 3NF car NOM-AV -> CAP-AV.
dans ce cas il faut décomposer la relation de la manière suivante :
TYPE(NOM-AV, CAP-AV)
AVION1(NUM-AV, NOM-AV, LOC-AV)
5.3 - PROPRIETES DES DECOMPOSITIONS EN 3NF
Une décomposition {R1, R2, ..., Rn} d'une relation R qui préserve les DF est telle que la fermeture transitive des DF de R est la même que celle de l'union des DF de R1, R2, ..., Rn.
Si l'on décompose maladroitement la relation AVION en AVION1(NUM-AV, NOM-AV) et AVION2(NOM-AV, CAP-AV, LOC-AV), alors cette décomposition ne préserve pas les DF car on perd la DF NUM-AV -> LOC-AV.
Toute relation a au moins une décomposition en 3FN telle que :
1) la décomposition préserve les DF,
2) la décomposition est sans perte.
Cette décomposition peut ne pas être unique.
5.4 - ALGORITHME DE DECOMPOSITION EN 3NF
On utilise cet algorithme si toutes les dépendances sont des DF.
Entrée : Schéma R ne contenant que des DF
Sortie : Schéma {R1, R2, ... , Rn} avec Ri en 3NF pour tout i
Etape 1 :
Soit F l'ensemble des DF. Pour toute DF f, rendre f élémentaire. Soit F' l'ensemble obtenu.
Etape 2 :
Rechercher une couverture minimale de F' notée MIN(F').
Etape 3 :
Partitionner MIN(F') en groupes F'1, F'2, ..., F'k tels que toutes les DF d'un même groupe aient la même partie gauche.
Etape 4 :
Pour chaque groupe F'i, i = 1, ..., k, construire un schéma contenant les attributs de F'i et les DF de F'i. Les éléments isolés (non déterminés par une DFE) sont regroupés dans une relation dont ils constituent la clé.
La relation AVION peut se décomposer de la manière suivante :
Etape 1 :
Toutes les DF sont élémentaires (voir graphe des DF).
Etape 2 :
Une couverture minimale de cet ensemble de DF comprend :
NUM-VOL -> NUM-AV NUM-VOL -> H-D NUM-VOL -> H-A NUM-VOL -> V-D
NUM-VOL -> V-A NUM-VOL -> NUM-PIL NUM-AV -> NOM-AV NUM-AV -> LOC-AV
NOM-AV -> CAP-AV NUM-PIL -> NOM-PIL NUM-PIL -> ADR-PIL
NUM-PIL,H-A -> NUM-VOL NUM-PIL,H-D -> NUM-VOL NUM-AV,H-A ->
NUM-VOL NUM-AV,H-D -> NUM-VOL
Etape 3 :
F'1 = {NUM-VOL -> NUM-AV, NUM-VOL -> H-D, NUM-VOL -> H-A, NUM-VOL -> V-D, NUM-VOL -> V-A, NUM-VOL -> NUM-PIL}
F'2 = {NUM-AV -> NOM-AV, NUM-AV -> LOC-AV}
F'3 = {NOM-AV -> CAP-AV}
F'4 = {NUM-PIL -> NOM-PIL, NUM-PIL -> ADR-PIL}
F'5 = {NUM-PIL,H-A -> NUM-VOL}
F'6 = {NUM-PIL,H-D -> NUM-VOL}
F'7 = {NUM-AV,H-A -> NUM-VOL}
F'8 = {NUM-AV,H-D -> NUM-VOL}
Etape 4 :
R1(NUM-VOL, NUM-AV, H-D, H-A, V-D, V-A, NUM-PIL)
R2(NUM-AV, NOM-AV, LOC-AV)
R3(NOM-AV, CAP-AV)
R4(NUM-PIL, NOM-PIL, ADR-PIL)
R5(NUM-PIL,H-D,NUM-VOL)
R6(NUM-PIL,H-A,NUM-VOL)
R7(NUM-AV,H-D,NUM-VOL)
R8(NUM-AV,H-A,NUM-VOL)
Les relations en 3NF comportent encore des redondances. Par exemple si l'on considère la relation :
CODE-POSTAL(VILLE, RUE, CODE)
avec la DFE : CODE -> VILLE
Cette relation est en 3NF car aucun attribut non clé ne dépend d'une partie de la clé ou d'un attribut non clé. Elle comporte cependant des redondances.
5.5 - FORME NORMALE DE BOYCE-CODD
Une relation est en BCNF si et seulement si les seules DFE sont celles dans lesquelles une clé détermine un attribut.
Toute relation a une décomposition en BCNF qui est sans perte. Par contre une décomposition en BCNF ne préserve pas les DF.
La relation CODE-POSTAL peut se décomposer en 2 relations :
VILLE-CODE(VILLE, CODE)
RUE-CODE(RUE, CODE)
Ces 2 relations sont en BCNF, leur jointure naturelle coïncide exactement avec la relation initiale CODE-POSTAL.