Tutoriel de Bases de Données Relationnelles

Dépendances fonctionnelles et normalisation

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 :