UML 2 pour les bases de données

Dépendances fonctionnelles

Le processus de normalisation permet de construire des bases de données relationnelles en évitant les redondances et en préservant l’intégrité des données. Il est préférable de normaliser les relations au moins jusqu’à la troisième forme normale. La normalisation est basée sur les dépendances fonctionnelles (DF). E.F. Codd fut le premier à publier des écrits sur les DF [COD 72]. Définition Un attribut b dépend fonctionnellement d’un attribut a si à une valeur de a correspond au plus une valeur de b. La dépendance fonctionnelle est notée a Æ b. Le membre droit de l’écriture s’appelle le dépendant, le membre gauche s’appelle le déterminant. Plusieurs attributs peuvent apparaître dans la partie gauche d’une DF. Dans ce cas, il convient de considérer le couple (si deux attributs figurent dans la partie gauche), le triplet (s’il y a trois attributs), etc. Plusieurs attributs peuvent apparaître dans la partie droite d’une DF. Dans ce   cas, il convient de considérer chaque DF en gardant la partie gauche et en faisant intervenir un seul attribut dans la partie droite. Supposons les exemples suivants, qui concernent des pilotes ayant un numéro, un nom, une fonction (copilote , commandant, instructeur…) : ● l’écriture numPilote,jour Æ nbHeuresVol est une DF, car à un couple (numPilote, jour) correspond au plus un nombre d’heures de vol ; ● l’écriture numPilote Æ nomPilote, fonction est équivalente aux écritures numPilote Æ nomPilote et numPilote Æ fonction qui sont deux DF. En conséquence numPilote Æ nomPilote, fonction est une DF ; ● l’écriture nomPilote Æ fonction est une DF s’il n’y a pas d’homonymes dans la population des pilotes enregistrés dans la base de données. Dans le cas contraire, ce n’est pas une DF, car à un nom de pilote peuvent correspondre plusieurs fonctions ; ● l’écriture fonction Æ nomPilote n’est pas une DF, car à une fonction donnée correspondent éventuellement plusieurs pilotes. DF élémentaire Une DF a,b→c est élémentaire si ni a→c, ni b→c ne sont des DF. Considérons les exemples suivants : ● la dépendance fonctionnelle numPilote,jour Æ nbHeuresVol est élémentaire, car numPilote Æ nbHeuresVol n’est pas une DF (un pilote vole différents jours, donc pour un pilote donné, il existe plusieurs nombres d’heures de vol), pas plus que jour Æ nbHeuresVol (à un jour donné, plusieurs vols sont programmés) ; ● la dépendance fonctionnelle numPilote,nomPilote Æ fonction n’est pas élémentaire, car le numéro du pilote suffit pour retrouver sa fonction (numPilote Æ fonction est une DF). DF directe Une DF a Æ c est directe si elle n’est pas déduite par transitivité, c’est-à-dire s’il n’existe pas de DF a Æ b et b Æ c. L’expérience montre qu’il est difficile de savoir si une DF est directe, mais il est aisé de voir si elle est indirecte. En conséquence si une DF n’est pas indirecte, elle est directe (ouf !). Illustrons cette définition par la figure suivante. Soit les trois dépendances fonctionnelles (1), (2) et (3). La dépendance fonctionnelle (3) est non directe et les dépendances (1) et (2) sont directes.

Fermeture d’un ensemble de DF

Nous avons vu précédemment qu’on pouvait déduire des DF à partir de DF par règles d’inférence. La fermeture F+ d’un ensemble de DF F est l’ensemble des DF qu’on peut obtenir par applications successives des axiomes d’Armstrong. La couverture minimale est l’ensemble des DF élémentaires issues de F+ tel que : • le membre droit (dépendant) de chaque DF ne contient qu’un seul attribut ; • le membre gauche (déterminant) de chaque DF est irréductible ; • aucune DF ne peut être supprimée. Figure 2-4 Dépendances fonctionnelles directes et non directes (2) directe c (3) indirecte a b (1) directe C .En considérant seulement a Æ b et b Æ c, la fermeture obtenue contient 21 DF ! (a Æ a, b Æ b, a Æ c, a,c Æ b…). L’exemple suivant décrit la résolution de la fermeture et de la couverture minimale de l’ensemble de DF F = {immat Æ compagnie, immat Æ typeAvion, typeAvion Æ capacite, typeAvion Æ nomConst}. On applique la transitivité entre : ● la DF immat Æ typeAvion et type Avion Æ nomConst et on obtient la DF immat Æ nomConst ; ● la DF immat Æ typeAvion et typeAvion Æ capacite et on obtient la DF immat Æ capacite. On pourrait appliquer l’union entre immat Æ compagnie et immat Æ typeAvion de manière à obtenir la DF immat Æ typeAvion,compagnie. De même, l’union entre typeAvion Æ capacite et typeAvion Æ nomConst donne typeAvion Æ capacite,nomConst. On pourrait appliquer l’augmentation entre chaque DF. Ainsi la DF immat Æ compagnie donnerait lieu à l’écriture des DF suivantes : ● immat,typeAvion Æ compagnie,typeAvion ● immat,capacite Æ compagnie,capacite ● immat,nomConst Æ compagnie,nomConst On pourrait également appliquer les autres propriétés des DF aux DF initiales de manière à obtenir un nombre important de DF pas nécessairement intéressantes. La fermeture de cet ensemble s’écrirait de la sorte : F+ = {immat Æ compagnie ; immat Æ typeAvion ; typeAvion Æ capacite ; typeAvion Æ nomConst ; immat Æ capacite ; immat Æ nomConst ; immat Æ typeAvion,compagnie ; immat,typeAvion Æ compagnie,typeAvion ; immat,capacite Æ compagnie,capacite ; immat,nomConst Æ compagnie, nomConst ; … } Ce qui intéresse le concepteur est l’ensemble des DF composant la couverture minimale de F+ noté : = {immat Æ compagnie ;immat Æ typeAvion ; typeAvion Æ capacite ; typeAvion Æ nomConst}. Nous étudierons en fin de chapitre deux méthodes de conception de schémas relationnels normalisés basées sur les DF. Alors que les DF vont servir à classifier un schéma relationnel en première, deuxième, troisième ou BCFN (Boyce-Codd forme normale), d’autres formes de dépendances vont permettre de définir les quatrième et cinquième formes normales. Ces familles de dépendances sont les dépendances multivaluées et les dépendances de jointure. Néanmoins, la majorité des schémas relationnels en entreprise sont en deuxième (on dénormalise des relations volontairement pour des contraintes d’optimisation) ou en troisième forme normale.