Le but des dépendances fonctionnelles et de la théorie de la normalisation est de s'assurer que le schéma relationnel défini pour une base de données est correctement construit. Un mauvais schéma
relationnel peut en effet entrainer des anomalies lors des manipulations.
Considérons la relation Approvisionnement suivante :
| Produit | Quantité | Couleur | Fournisseur | Adresse |
| parapluie | 110 | rouge | Labaleine | Paris |
| chapeau | 50 | vert | Lemelon | Lyon |
| sac à main | 65 | noir | Toutcuir | Lyon |
| parasol | 15 | jeune | Labaleine | Paris |
| ombrelle | 5 | rouge | Labaleine | Paris |
| ceinture | 25 | vert | Letour | Nantes |
| sac à main | 65 | noir | Legrand | Paris |
Cette relation est mal construite : les informations concernant les fournisseurs sont redondantes. S'il faut mettre à jour l'adresse du fournisseur "Labaleine", il faut absolument vérifier que toute les adresses de Labaleine sont mises à jour. Cette solution n'est pas raisonnable. La base de données va trsè rapidement devenir incohérente.
La solution est dont d'éviter toute redondance dans la base de données. Ceci exige que le schéma de la base de données soit bien construit. La méthode pour cela se décompose en deux étapes :
- étude des dépendances entre données;
- décomposition et normalisation des relation.
Dépendance fonctionnelle sur une
relation (DF)
Définition
Soit R(X,Y,Z) un schéma de relation, avec X, Y, Z des ensembles d'attributs, Z pouvant être éventuellement
vide
On dit qu'il existe une dépendance fonctionnelle entre X ete Y si la connaissance d'une valeur de X détermine au plus
une valeur de Y. La notation adoptée est la suivante :
X -> Y
Cette propriété est définie sur l'intension du schéma
et non son extension (elle est donc invariante dans le temps et ne peut
être extraite à partir d'exemples). C'est une propriété
qui doit être extraite de la connaissance que l'on a de l'application
à modéliser.
Propriétés des dépendances
fonctionnelles (ou axiomes d'Amstrong)
- DF1 : réflexivité Y inclus-ou-egal X => X -> Y
- DF2 : augmentation X -> Y => X,Z -> Y,Z
- DF3 : transitivité X -> Y ET Y -> Z => X ->Z
- DF4 : pseudo-transitivité X -> Y ET Y,W -> Z => X,W -> Z
- DF5 : union X -> Y ET X -> Z => X -> Y,Z
- DF6 : décomposition X -> Y ET Y Z =>
X -> Z
Décomposition binaire d'une relation
R(X,Y,Z) ET X -> Y => R(X,Y,Z) = R[X,Y] * R[X, Z]
Règles:
- on peut toujours décomposer une relation suivant une dépendance
fonctionnelle - on ne peut décomposer une relation s'il n'y a pas de
dépendance fonctionnelle - la décomposition suivant une dépendance fonctionnelle
ne perd pas d'information
Ce principe de décomposition binaire d'une relation est
à la base de l'algorithme de décomposition
Définitions complémentaires
Soit R(X,Y,Z) schéma de relation où X, Y, Z ensemble d'attributs avec Z éventuellement vide
Soit A un attribut quelconque.
Dépendance fonctionnelle élémentaire (DFE)
Une DF X -> Y avec X ne contenant pas Y est une DFE ssi il n'existe aucun sous-ensemble de X ayant une DF sur Y (X est la plus petite quantité d'information donnant Y)
Clé
X est une clé de R ssi X -> Y,Z DFE (une relation peut avoir plusieurs clés)
A est attribut clé s'il appartient à au moins
une clé de R
A est attribut non clé s'il n'appartient pas à
une clé de R
Typologie des dépendances
A est transitivement dépendant de X s'il existe Y, Y
ne contenant pas A tel que
X -> Y, Y -> A, ~(Y-> X), Y n'est pas inclus dans X
A est directement dépendant de X s'il n'est pas transitivement
dépendant
A est pleinement dépendant de X si X -> A est une
DFE
A est partiellement dépendant de X si X -> A n'est
pas une DFE
Fermeture transitive
La fermeture transitive F+ d'un ensemble F de dépendances
fonctionnelles est l'ensemble des DFE qui peuvent être produites
par application des axiomes d'Amstrong sur l'ensemble F.
Normalisation des relations (formes normales)
Objectifs :
- définir une notion de "qualité" de schéma
- pouvoir comparer deux schémas de relation
Les formes normales définissent un ordre partiel sur les schémas
de relation. On peut donc voir une forme normale comme une classe d'équivalence
(on peut comparer deux schémas dans deux classes d'équivalence
différentes mais pas dans la même). Il faut aussi noter que
le seul élément qui est pris en compte par les formes normales
est la non redondance d'informations d'un schéma. Selon les formes
normales un "bon" schéma est un schéma sans redondance
(ce qui ne veut pas forcément dire qu'il est efficace par exemple).
Un schéma relationnel sans qualité particulière est
appelé schéma en 1ère forme normale (on note 1FN)
et si on rajoute certaines qualités on obtient les deuxième
et troisième formes normales (on note 2FN et 3FN).
On ne présente ici que les formes normales dont la définition
utilise exclusivement les dépendances fonctionnelles. Si on prend
en compte d'autres dépendances entre données comme les dépendances
multivaluées on obtient alors les 4FN et 5FN. La 3FN reste cependant
l'objectif de normalisation le plus "classique".
1FN : une relation est en première forme normale ssi tout
attribut a une valeur atomique (vrai par définition du modèle
relationnel)
2FN : une relation est en deuxième forme normale ssi elle
est en 1FN et si tous les attributs non clés sont pleinement
dépendants des clés (toutes les dépendance entre
une clé et un attribut non clé sont élémentaires)
3FN : une relation est en troisième forme normale ssi
elle est en 2FN et si tous les attributs non clés sont directement
et pleinement dépendants des clés (si tout attribut non
clé ne dépend pas d'un autre attribut non clé)
3FNBCK (Boyce-Codd-Kent) : une relation est en 3FNBCK ssi elle
est en 3FN et si les seules DFE sont celles de
la forme C -> X avec C clé (seules les clés sont en partie
gauche de DF).
Dépendances fonctionnelles et conception
de schémas
Une manière de concevoir un schéma relationnel en troisième
forme normale est de partir du schéma complet (ensemble de tous
les attributs) et de décomposer cette "grosse" relation
(appelée également relation universelle) suivant les dépendances
fonctionnelles. Cette approche est appelée approche par décomposition.
Le problème est d'ordonner l'ordre des décompositions de
manière à obtenir un schéma en 3ème
forme normale. En effet, chaque relation produite ne conserve qu'un
certain nombre de DF (celles définies sur ses attributs propres)
et n'est donc pas forcément en 3ème forme normale. De plus,
l'ensemble des DF du schéma complet n'est pas forcément préservé.
Algorithme de décomposition :
- entrée : un schéma relationnel
(ensemble d'attributs) et un ensemble E de DF entre ses attributs - sortie : une ou plusieurs relations en 3FN
dont la jointure redonne la relation initiale (par contre des DF de E ont
pu être perdues) - principe : l'algorithme peut se voir comme la construction
d'un arbre binaire. La racine de cet arbre est la relation à décomposer.
L'arbre se construit récursivement de la manière suivante
:- on choisit une DF dfi dans l'ensemble E des DF
- le fils gauche du noeud racine est une relation composé de
tous les attributs de dfi - dfi est retirée de l'ensemble E
- le fils droit du noeud racine est une relation composée
de tous les attibuts de la racine excepté ceux présents en
partie droite de dfi
Problèmes : la solution dépend du choix des
DF selon lesquelles on choisit de décomposer et il ne préserve
pas nécessairement les DF.
On sait néanmoins que toute relation admet une décomposition
en 3FN qui préserve les DF.
Il existe un algorithme dit de synthèse qui permet d'obtenir
une décomposition 3FN qui préserve les DF. Il est basé
sur le calcul de la couverture minimale (ou irredondante) d'un ensemble
de DF.
Exemple sur les formes normales :
Soit le schéma R = <{P, H, N, Y, T}, {P -> T; P, H -> Y; H, N -> P; H, Y -> N}>
Ensemble des DFE engendrées :
- H, N -> T
- P, H -> N
- H,N -> Y
- H, Y -> P
- P, H -> T
- H, Y -> T
On a donc trois clés potentielles (H, N; P, H; H, Y)
:
- H, N -> P, T, Y
- P, H -> T, Y, N
- H, Y -> N, P, T
Les attributs clés sont donc : H, N, P, Y et les attributs non clés sont : T
Par définition le schéma est en 1ère
forme normale. Est il en 2ème forme normale
?
Non, car P, H -> T n'est pas une DFE (on
a P -> T)
R est donc en 1ère forme normale. N'ayant pas une relation en 3FN, nous décomposons le schéma en applicant l'algorithme de décomposition :
ou bien :
Posté le 1 septembre 2009