Bonsoir,
Envoyé par
Boubou382002
j'ai un exercice à faire, mais je n'ai pas trouvé d'exemples de passage (en 2NF, 3NF ou BCNF) sur le net.
On va tâcher moyen d’arranger ça.
Votre exercice comporte deux parties :
— Production de la liste des clés candidate de la relation.
— Vérification du respect des formes normales.
Première partie. Production de la liste des clés candidates.
Tout d’abord, j’interprète le terme "relation" au sens du Modèle Relationnel de Données et non pas au sens de l’approche Entité/Relation.
Par commodité, je commencerai par remplacer par des lettres les noms des attributs de la relation, qu’elle-même j’appellerai R par la suite :
A pour nomNavire
B pour typeNavire
C pour idVoyage
D pour chargement
E pour port
F pour date.
Le schéma de la relation est donc le suivant :
R {A, B, C, D, E, F}
et la liste des dépendances fonctionnelles (DF) :
DF1 : {A} → {B}
DF2 : {C} → {A}
DF3 : {C} → {D}
DF4 : {A,F} → {C}
DF5 : {A,F} → {E}
Vous noterez l’emploi des accolades : En effet, le déterminant (partie gauche d’une DF) et le dépendant (partie droite de la DF) sont des ensembles.
Je rappelle en passant la définition de la clé candidate :
Une clé candidate est un sous-ensemble d’attributs K de l’en-tête d’une relation R, respectant les deux contraintes suivantes :
— Unicité. Deux tuples distincts de R ne peuvent avoir même valeur de K.
— Irréductibilité (ou minimalité). Il n’existe pas de sous-ensemble strict de K garantissant la règle d’unicité.
Corollaire : K détermine fonctionnellement chaque attribut de R :
K → {A}
K → {B}
K → {C}
K → {D}
K → {E}
K → {F}
Je rappelle en outre qu’une surclé est un sous-ensemble d’attributs de l’en-tête de relation R, vérifiant la propriété d’unicité mais pas nécessairement celle d’irréductibilité. La clé candidate n’est donc qu’un cas particulier de la surclé.
La recherche des clés candidates est un exercice dont la durée croît, en gros, exponentiellement avec le nombre d’attributs composant l’en-tête de la relation R. Aussi, est-il bon de disposer de trucs permettant de prendre des raccourcis et d’alléger la charge de travail. Ainsi, l’attribut F n’apparaît jamais comme élément d’un dépendant des dépendances fonctionnelles DF1 à DF5 : cela veut dire que cet attribut fera partie de chaque clé candidate de R. Appelons Φ cette propriété vérifiée par F.
La recherche peut consister à vérifier s’il existe d’abord des clés candidates parmi les singletons {A}, {B}, {C}, {D}, {E}, {F}, puis parmi les paires {A,B}, {A,C}, ..., {A,F}, {B,C}, ..., {B,F}, ..., {E,F}, puis parmi les triples {A,B,C}, ..., {D,E,F}, puis parmi les quadruples {A,B,C,D}, ...., {C,D,E,F}, puis parmi les quintuples {A,B,C,D,E}, ..., {B,C,D,E,F}. Si aucune clé candidate n’a été découverte dans cet exercice, alors R a pour seule clé candidate {A,B,C,D,E,F}, c'est-à-dire que cette clé est composée de l’ensemble des attributs de R.
Commençons par les singletons. Du fait de Φ, seul le singleton {F} est à examiner. Pour que {F} soit clé candidate, en vertu du corollaire évoqué ci-dessus, on doit vérifier :
{F} → {A}
{F} → {B}
{F} → {C}
{F} → {D}
{F} → {E}
{F} → {F}
Par référence à la liste des DF dont on dispose, ça n’est pas le cas, car seule {F} → {F} est vérifiée (la DF est triviale). Concernant les singletons, aucun d’entre eux n’est donc clé candidate.
Passons aux paires. Du fait de Φ, on ne considère que les paires ayant au moins l’attribut F pour élément. Ces paires sont les suivantes : {A,F}, {B,F}, {C,F}, {D,F}, {E,F}.
Commençons par examiner {A,F}. En théorie, pour accomplir le travail, on doit mettre en œuvre les axiomes d’Armstrong et les règles qui en sont inférées, mais on verra que l’on peut s’en sortir autrement. Servons-nous quand même un instant de ces axiomes.
{A,F} → {A} ; car en vertu du premier axiome d’Armstrong, cette DF est vérifiée ("le tout détermine la partie").
{A,F} → {B} ; en effet, la DF {A} → {B} est donnée et en vertu du 2e axiome d’Armstrong (augmentation), {A,F} → {B}.
{A,F} → {C} ; cette DF est donnée.
{A,F} → {D} ; en effet, {A,F} → {C} et {C} → {D} : en vertu du 3e axiome d’Armstrong (transitivité), {A,F} → {D}.
{A,F} → {E} ; cette DF est donnée.
{A,F} → {F} ; du fait encore du 1er axiome d’Armstrong.
Au résultat, la paire {A,F} est une clé candidate pour R.
Le procédé utilisé peut décourager quand on ne jongle pas avec les axiomes d’Armstrong. On va donc utiliser une méthode pragmatique. Considérons la paire {A,F}, accompagnée à sa droite d’emplacements prévus pour accueillir les attributs A, B, C, D, E, F, dans cet ordre :
{A,F} : [ _ _ _ _ _ _ ]
Le but de la manœuvre consiste à installer chaque attribut à sa place quand c’est possible, en exploitant les DF données, à savoir DF1 à DF5.
Au départ, on amorce la pompe en installant d’office A et F chacun à sa place, puisqu’ils doivent figurer dans le résultat (en notant au passage que la DF {A,F} → {A,F} est triviale) :
{A,F} : [ A _ _ _ _ F ]
Du fait que {A} → {B} et parce que A est un élément de [ A _ _ _ _ F ], B peut être capturé par A est venir s’installer à l’emplacement prévu pour lui :
{A,F} : [ A B _ _ _ F ]
Du fait que {A,F} → {C} et que A et F sont des éléments de [ A B _ _ _ F ], C est capturé et vient s’installer à l’emplacement prévu pour lui :
{A,F} : [ A B C _ _ F ]
Du fait que {A,F} → {E} et que A et F sont des éléments de [ A B C _ _ F ], E est capturé et vient s’installer à l’emplacement prévu pour lui :
{A,F} : [ A B C _ E F ]
Du fait que {C} → {D} et que C est un élément de [ A B C _ E F ], D est capturé et vient s’installer à l’emplacement prévu pour lui :
{A,F} : [ A B C D E F ]
Tous les emplacements sont occupés, ce qui revient à dire que {A,F} → {A,B,C,D,E,F}, donc que {A,F} est clé candidate pour R. Pour le moins, la technique employée n’est pas très formelle, elle n’en est pas moins l’application d’un algorithme que l’on retrouve dans les meilleurs ouvrages traitant de la normalisation.
Passons au couple {B,F}. Au départ, on installe d’office B et F à leur place :
{B,F} : [ _ B _ _ _ F ]
Mais on aura beau passer en revue les DF DF1 à DF5, comme {B} n’est le déterminant d’aucune de ces DF, pas plus que le singleton {F} et la paire {B,F}, aucune capture ne sera possible et les emplacements vides le resteront définitivement, en conséquence de quoi {B,F} n’est pas clé candidate pour R.
Passons au couple {C,F}. Au départ, on installe d’office C et F à leur place :
{C,F} : [ _ _ C _ _ F ]
Du fait que {C} → {A} et que C est un élément de [ _ _ C _ _ F ], A est capturé et vient s’installer à l’emplacement prévu pour lui :
{C,F} : [ A _ C _ _ F ]
Du fait que {C} → {D} et que C est un élément de [ A _ C _ _ F ], D est capturé et vient s’installer à l’emplacement prévu pour lui :
{C,F} : [ A _ C D _ F ]
Du fait que {A} → {B} et que A est un élément de [ A _ C D _ F ], B est capturé et vient s’installer à l’emplacement prévu pour lui :
{C,F} : [ A B C D _ F ]
Du fait que {A,F} → {E} et que A et F sont éléments de [ A B C D _ F], E est capturé et vient s’installer à l’emplacement prévu pour lui :
{C,F} : [ A B C D E F ]
Tous les emplacements sont occupés : {C,F} est une clé candidate pour R.
Je vous laisse le soin de montrer que {D,F} et {E,F} ne sont pas des clés candidates pour R.
A ce stade, on a découvert deux clés candidates pour R : {A,F} et {C,F}. Il s’agit de vérifier s’il existe des triples qui seraient aussi clés candidates. Une fois de plus, l’attribut F doit entrer dans la composition des triples (propriété Φ ci-dessus), mais on peut ignorer ceux dont les paires {A,F} et {C,F} sont des sous-ensembles, puisque ces triples ne vérifieraient pas la propriété de l’irréductibilité des clés candidates (voir ci-dessus la définition de la clé candidate).
Les triples à examiner sont les suivants : {B,D,F}, {B,E,F},{D,E,F}. Je vous laisse le soin de montrer qu’aucun d’eux n’est clé candidate.
On passe ensuite aux quadruples. Une fois de plus, l’attribut F doit entrer dans la composition de ces quadruples, mais on peut encore ignorer ceux dont {A,F} et {C,F} sont des sous-ensembles, puisque ces quadruples ne vérifieraient pas la propriété de l’irréductibilité des clés candidates.
Il n’y a qu’un seul quadruple à examiner : {B,D,E,F}. Je vous laisse le soin de montrer qu’il n’est pas clé candidate.
Il n’y a aucun quintuple à examiner (F n’est pas élément de {A,B,C,D,E} et les autres quintuples sont des surclés).
Il y a donc au final deux clés candidates pour R : {A,F} et {C,F}. La méthode utilisée pour les découvrir tient du rouleau compresseur, mais elle est bien pratique. Elle n’est que l’application d’un algorithme que l’on peut retrouver par exemple dans l’ouvrage "The Theory of Relational Databases" de David Maier (voir au chapitre 9 page 213, l’algorithme PCLOSURE).
Deuxième partie. Vérification du respect des formes normales.
Il est de tradition de vérifier consciencieusement que R vérifie d’abord la 2NF, puis la 3NF, puis la BCNF. Mais si R est en BCNF, elle est nécessairement en 2NF et 3NF. Il est donc plus utile de s’assurer d’entrée de la BCNF, histoire de ne pas perdre de temps. Le but qu’on se fixe est bien de garantir qu’au final, les relations produites sont en BCNF, point barre.
Il existe un certain nombre de définitions de la BCNF. Nous utiliserons par exemple celle-ci :
Une relation R est en BCNF si et seulement si, le déterminant de chaque DF non triviale est une surclé de R.
Une DF est triviale si le dépendant est un sous-ensemble (non nécessairement strict) du déterminant.
Exemple : les DF {A,F} → {A}, {A,F} → {A,F}, {A} → {A} sont triviales.
Revenons maintenant sur les DF initialement fournies :
DF1 : {A} → {B}
DF2 : {C} → {A}
DF3 : {C} → {D}
DF4 : {A,F} → {C}
DF5 : {A,F} → {E}
Je rappelle qu’une clé candidate est un sous-ensemble non strict d’une surclé. Les seules clés candidates de R étant les paires {A,F} et {C,F}, la liste des surclés de R est donc la suivante (à une omission involontaire près de ma part) :
{A,F}, {A,B,F}, {A,B,C,F}, {A,B,C,D,F}, {A,B,C,D,E,F}, {A,C,F}, {A,C,D,F}, {A,C,D,E,F}, {A,D,F}, {A,D,E,F}, {A,E,F}, {C,F}, {B,C,F}, {B,C,D,F}, {B,C,D,E,F}, {C,D,F}, {C,D,E,F}, {C,E,F}.
Cet inventaire de surclés ne présente d’intérêt qu’au plan théorique et concrètement on se focalisera sur celles qui donnent lieu à clés candidates, à savoir {A,F} et {C,F}.
Considérons la 1re DF qui figure dans la liste des DF qu’on vous a fournie. Cette DF, à savoir {A} → {B} n’est pas triviale, et son déterminant {A} ne fait pas partie de la liste des surclés de R : la BCNF est violée et R doit donc faire l’objet d’une projection selon deux relations R1 et R2, telles que par jointure naturelle de R1 et R2 on retrouve R. La projection consiste à décomposer R en ayant à l’esprit le théorème de Heath qui s’énonce ainsi :
Soit la relation R {X, Y, Z} dans laquelle X, Y et Z sont des ensembles d’attributs de R. Si R satisfait à la dépendance fonctionnelle X → Y, alors R est égale à la jointure de ses projections sur {X, Y} et {X, Z}.
Remplaçons X, Y et Z respectivement par {A}, {B} et {C,D,E,F}. Par décomposition on produit les deux relations R1 et R2 telles que R = R1 JOIN R2 :
R1 {A,B} ayant pour clé candidate {A} (du fait de la DF {A} → {B} héritée de R).
R2 {A,C,D,E,F} ayant pour clés candidates {A,F} et {C,F}, héritées de R.
R1 respecte la BCNF. Qu’en est-il de R2 ? Considérons la 2e DF qui figure dans la liste des DF qu’on vous a fournie. Cette DF, à savoir {C} → {A,D}, n’est pas triviale et son déterminant {C} ne fait pas partie de la liste des surclés de R : La BCNF est violée et R2 doit à son tour faire l’objet d’une projection selon deux relations R21 et R22, telles que R2 = R21 JOIN R22.
En utilisant à nouveau le théorème de Heath, et en remplaçant X, Y et Z respectivement par {C}, {A,D} et {E,F} dans R2, on produit les deux relations :
R21 {C,A,D} ayant pour seule clé candidate {C} et qui vérifie la BCNF.
R22 {C,E,F} ayant pour seule clé candidate {C,F} et qui vérifie la BCNF.
Au final, la relation R qui ne vérifie pas la BCNF est égale à la jointure naturelle de 3 relations normalisées :
R {A, B, C, D, E, F} = R1 {A,B} JOIN R21 {C,A,D} JOIN R22 {C,E,F}
La normalisation a quand même engendré un problème. En effet, {A,F} est une clé candidate de R, ce qui est l’expression d’une contrainte, d’une règle de gestion forte de l’entreprise, mais en normalisant R2, en la décomposant en R21 et R22, on a perdu cette règle. En conséquence, lors de la mise en œuvre de la base de données, il faudra mettre en œuvre une contrainte (sous forme par exemple d’un trigger SQL) pour garantir la DF {A,F} → {C,D,E}, ce qui ne permettra pas au demeurant de résoudre d’autres effets secondaires, sur lesquels je suis malheureusement obligé de passer.
Par ailleurs, la décomposition de R {A, B, C, D, E, F} n’est pas forcément unique. On a commencé le processus de normalisation en considérant d’abord la DF {A} → {B}, puis la DF {C} → {A,D}. On aurait pu procéder dans un ordre différent. Par exemple, considérer la DF {A,F} → {C,E} avant de considérer la DF {C} → {A,D}. Dans ces conditions, toujours par application du théorème de Heath, R2 {A,C,D,E,F} donne lieu aux deux relations :
R23 {A,F,C,E} (en notant que les clés candidates {A,F} et {C,F} sont préservées)
R24 {A,F,D} ayant pour seule clé candidate {A,F}.
Mais si R24 respecte la BCNF, ça n’est pas le cas de R23, qui comporte la DF non triviale {C} → {A}, alors que le déterminant {C} n’est pas surclé. R23 doit donc être décomposée. Toujours en application du théorème de Heath, R23 donne lieu à :
R231 {C,A} ayant pour seule clé candidate {C} et qui vérifie la BCNF.
R232 {C,E,F} qui est en fait R22.
R est cette fois-ci décomposée en 4 relations vérifiant la BCNF :
R {A, B, C, D, E, F} = R1 {A,B} JOIN R24 {A,F,D} JOIN R231 {C,A} JOIN R22 {C,E,F}
Mais une fois de plus, les règles de gestion ne sont pas préservées. Ainsi, on ne sait pas garantir la DF {A,F} → {C,E} ou la DF {C,F} → {D}, qui sont des conséquences logiques des clés candidates. Là encore, il faudra mettre en œuvre une contrainte pour garantir malgré tout ces DF.
BCNF et règles de gestion des données.
On vient de voir qu’il y avait un malaise, puisque normaliser à tout prix en BCNF peut conduire à la perte de règles de gestion de données, auquel cas on peut légitimement vouloir préserver ces règles, quitte à violer la BCNF. Cela dit, il est très rare que l’on se retrouve face à cette alternative fâcheuse et: en règle générale, si l’on remet à plat les règles de gestion avec le maître d’ouvrage, celui-ci convient qu’elles peuvent être à reformuler. Ainsi, les DF qu’on vous a fournies traduisent les règles de gestion des petits bateaux qui vont sur l’eau et sont peut-être tout à fait pertinentes, n’empêche que je ferais le siège de l’armateur pour m’assurer qu’elles ne peuvent pas être révisées. Par exemple, je le tannerai jusqu’à ce qu’il prouve le bien fondé de l’existence de idVoyage qui est la cause du malaise, c'est-à-dire quelle perte sémantique il y aurait à s’en débarrasser.
Techniques traditionnelles
Quoi qu’il en soit, pour en revenir aux techniques traditionnelles, si vous souhaitez vraiment savoir si la relation R respecte la 2NF, il faut commencer par donner une définition de celle-ci. Par exemple :
Une relation R est en 2NF si elle est en 1NF et si chaque attribut n’appartenant pas à une clé candidate est en dépendance totale de chaque clé candidate de R.
En observant que cette définition est redondante, en ce sens que, dans le cadre du Modèle Relationnel de Données, "relation en 1NF" est synonyme de "relation". Mais je ne voudrais pas vous traumatiser et je n’insisterai pas sur ce point particulier.
Reste à définir ce qu’est une DF totale (full DF) :
Soit R une relation, X un sous-ensemble quelconque d’attributs de R et C un attribut quelconque de R. La DF X → {C} est dite totale si elle n’est ni triviale ni partielle.
La DF X → {C} est dite partielle si elle n’est pas triviale et s’il existe Y strictement inclus dans X tel que Y → {C}.
(On a vu plus haut ce qu’est une DF triviale.)
La relation R {A, B, C, D, E, F} ne vérifie pas la 2NF, car elle a pour clés candidates {A,F} et {C,F} et le dépendant {B} de la DF {A} → {B} ne dépend que partiellement de la clé candidate {A,F} (en notant qu’il dépend aussi partiellement de la clé candidate {C,F}, du fait que {C} → {A} et {A} → {B} et que par transitivité {C} →{B}).
Pour normaliser, on procède comme on l’a déjà fait. Par décomposition on produit les deux relations R1 et R2 telles que R = R1 JOIN R2 :
R1 {A,B} ayant pour clé candidate {A}.
R2 {A,C,D,E,F} ayant pour clés candidates {A,F} et {C,F}, héritées de R.
R1 respecte la 2NF.
R2 ne respecte pas la 2NF, car il existe la DF {C} → {D}, ce qui fait que la DF {C,F} → {D} est donc partielle.
R2 est donc à décomposer à son tour : je vous renvoie à ce qui a déjà été fait en ce sens.
En tout état de cause, la 2NF et la 3NF contraignent à mettre en oeuvre des concepts finalement inutiles eu égard à la BCNF (celui de DF partielle par exemple), à fournir des énoncés dont on se passe volontiers (2NF, 3NF), et imposent implicitement un ordre dans les tâches à accomplir : vérifier d’abord la 2NF, puis seulement après la 3NF, et enfin la BCNF, véritable but de l’opération. On se complique inutilement la tâche, et au nom du rasoir d’Ockham, intéressons nous seulement à la BCNF. Les 2NF et 3NF ne revêtent plus qu’un intérêt historique.
Fermez le ban.
Exo formes normales
Répondre avec citation
Partager