+ Répondre à la discussion
Affichage des résultats 1 à 12 sur 12
  1. #1
    Invité régulier
    Inscrit en
    juin 2008
    Messages
    92
    Détails du profil
    Informations forums :
    Inscription : juin 2008
    Messages : 92
    Points : 7
    Points
    7

    Par défaut Exo formes normales

    Bonsoir,
    j'ai un exercice à faire, mais je n'ai pas trouvé d'exemples de passage (en 2NF, 3NF ou BCNF) sur le net.
    Voilà l'énoncé.

    Considérons les relations suivantes :
    Navigation (nomNavire, typeNavire, idVoyage, chargement, port, date)
    La date correspond à l'arrivée du navire dans un port donné

    Dependances fonctionnelles:
    nomNavire -> typeNavire
    idVoyage -> nomNavire, chargement
    nomNavire, date -> idVoyage, port

    (a) Identifier les clés candidates
    (b) Passage en 2NF
    (c) Passage en 3NF
    (d) Passage en BCNF

  2. #2
    Membre Expert
    Avatar de Ayana
    Inscrit en
    décembre 2005
    Messages
    901
    Détails du profil
    Informations forums :
    Inscription : décembre 2005
    Messages : 901
    Points : 1 134
    Points
    1 134

    Par défaut

    Bonjour,


    En cherchant un petit peu, il y a des exemples, mais il faut prendre la peine de les creuser un peu.

    Pour le sommaire :
    http://www.gaudry.be//nav/sommaire-rf-43.html

    Et pour les formes normales :
    http://www.gaudry.be/sgbdr-formes-normales.html
    [B]--= Ayana =--
    Team BAB - Spécialistes BO

    Rubrique BI de developpez.com

  3. #3
    Expert Confirmé Sénior
    Avatar de fsmrel
    Homme Profil pro François de Sainte Marie
    Spécialiste en bases de données
    Inscrit en
    septembre 2006
    Messages
    4 836
    Détails du profil
    Informations personnelles :
    Nom : Homme François de Sainte Marie
    Localisation : Autre

    Informations professionnelles :
    Activité : Spécialiste en bases de données
    Secteur : Conseil

    Informations forums :
    Inscription : septembre 2006
    Messages : 4 836
    Points : 13 819
    Points
    13 819

    Par défaut

    Bonsoir,


    Citation Envoyé par Boubou382002 Voir le message
    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.
    Faites simple, mais pas plus simple ! (A. Einstein)
    E=mc², mais si on discute un peu, on peut l’avoir pour beaucoup moins cher... (G. Lacroix, « Les Euphorismes de Grégoire »)
    => La relativité n'existerait donc que relativement aux relativistes (Jean Eisenstaedt, « Einstein et la relativité générale »)


    De grâce, pas de questions techniques par MP, ma boîte de réception explose !
    __________________________________
    Bases de données relationnelles et normalisation : de la première à la sixième forme normale (Bonne lecture !)

  4. #4
    Invité régulier
    Inscrit en
    juin 2008
    Messages
    92
    Détails du profil
    Informations forums :
    Inscription : juin 2008
    Messages : 92
    Points : 7
    Points
    7

    Par défaut

    Bonjour et merci beaucoup pour cette réponse détaillée.
    Par contre je devais le faire pour vendredi ....
    Mais ce n'est pas grave, elle m'apprends encore des choses.
    De plus, je me suis rendu compte qu'en tapant des mots du sujet dans google, je trouvais un site où la correction de cet exercice est disponible.
    Merci encore

  5. #5
    Candidat au titre de Membre du Club
    Inscrit en
    octobre 2006
    Messages
    15
    Détails du profil
    Informations forums :
    Inscription : octobre 2006
    Messages : 15
    Points : 13
    Points
    13

    Par défaut

    Bonsoir fsmrel

    Même si Boubou382002 n'a pas pu se servir de votre réponse pour rendre son devoir, je suis sure que sa lecture attentive lui sera autrement plus utile qu'un corrigé tout prêt.
    Pour tous les autres en tous cas, ceux qui n'avaient pas de devoir à rendre, merci de cette leçon magistrale illustrée. Je conserve ce post pour des relectures ultérieures lorsque le doute me (re)prendra sur l'application de la BCNF.

    Citation Envoyé par fsmrel Voir le message

    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.
    Puis-le rouvrir, ce ban, si je puis me permettre ? Je voudrais être sure d'avoir bien compris cette conclusion.
    Il est clair que notre cher Monsieur d'Ockham nous incite à nous rendre directement à la case "BCNF" au lieu de perdre bêtement notre temps sur les 2NF et 3NF.
    Mais lorsqu'on s'aperçoit que la relation n'est pas en BCNF, doit-on, comme vous l'avez fait dans cette exemple, essayer de valider en 2NF puis, le cas échéant en 3NF ?
    Ou bien n'avez-vous fait ce test que parce qu'il fallait bien répondre à l'énoncé de l'exercice des petits bateaux ?

    Autrement dit, si on ne valide pas en BCNF, y-a-t-il une démarche adéquate et quelle est-elle ?
    Je me suis inspirée de votre post pour proposer quelques "solutions". Certaines vous feront sans doute sauter au plafond, mais allons-y quand même.
    - on se contente, si cela est possible, de la 3NF. Dans ce cas, quel risque prend-on avec notre base de données ?
    - on décompose et on normalise coûte que coûte en BCNF toutes les relations après décomposition, quitte à perdre en route la conformité avec quelques règles de gestion.
    - On revient sur l'analyse pour traquer les règles de gestion abusives qu'il conviendra d'assouplir afin d'obtenir des relations BCNFisables.

    Merci d'avance,
    catcat

  6. #6
    Expert Confirmé Sénior
    Avatar de fsmrel
    Homme Profil pro François de Sainte Marie
    Spécialiste en bases de données
    Inscrit en
    septembre 2006
    Messages
    4 836
    Détails du profil
    Informations personnelles :
    Nom : Homme François de Sainte Marie
    Localisation : Autre

    Informations professionnelles :
    Activité : Spécialiste en bases de données
    Secteur : Conseil

    Informations forums :
    Inscription : septembre 2006
    Messages : 4 836
    Points : 13 819
    Points
    13 819

    Par défaut

    Bonsoir catcat,


    Citation Envoyé par catcat Voir le message
    Mais lorsqu'on s'aperçoit que la relation n'est pas en BCNF, doit-on, comme vous l'avez fait dans cette exemple, essayer de valider en 2NF puis, le cas échéant en 3NF ?
    Ou bien n'avez-vous fait ce test que parce qu'il fallait bien répondre à l'énoncé de l'exercice des petits bateaux ?
    J’ai une approche descendante de la normalisation, mais d’autres ont pris l’habitude d’une approche ascendante, et je dois en tenir compte. Par exemple, si je procède à une expertise (validation, audit, ...), j’avertis que j’attaque bille en tête avec la BCNF. Si mes interlocuteurs y tiennent, en complément du travail effectué, j’illustre la démarche ascendante, en commençant donc par la 2NF, à partir d’exemples simples, du genre de celui des petits bateaux. Mais, quand la base de données comporte mille tables, vous comprendrez que je ne m’éterniserai pas sur cette approche. Dans le cadre d’un cours, il est évident qu’après avoir traité de la BCNF, j’en viens à ses sœurs aînées, puisqu’elles font partie de la culture relationnelle, tout en expliquant pourquoi la méthode descendante me paraît préférable. Ensuite, à chacun de choisir l’approche qu’il estimera lui convenir.

    Une petite observation en passant. Ted Codd a présenté la 2NF et la 3NF en 1970 (octobre) et ce n’est qu’en 1974 que Raymond Boyce (mort d’une rupture d’anévrisme la même année) lui souffla la BCNF. Ce qui revient à dire que pendant près de 4 ans, les viols de BCNF n’ont pas été détectés, ou à tout le moins signalés, ce qui laisse à réfléchir... Et imaginez que Codd ait eu directement l’intuition de la BCNF et donc que les grandes sœurs d'icelle n’aient jamais vu le jour : quelle serait aujourd’hui la démarche pour normaliser ? Le plus étonnant est que cette forme normale date bien de 1971 ! mais c’est Ian Heath qui l’inventa et la BCNF devrait en toute logique être appelée HNF. Je ne sais pas pourquoi Codd (IBM), Boyce (IBM), Heath (IBM) ne se sont pas concertés à l’époque, histoire d’envoyer la 2NF et la 3NF aux oubliettes. Ces gens faisaient partie de la même entreprise (gigantesque il est vrai, avec des labos un peu partout) et ils ont laissés des écrits. Je me perds en conjectures. Peu importe, on ne refait pas l’histoire.

    Pour reprendre l’exemple des petits bateaux, même si l’on se s'intéresse qu'à la BCNF, le fait que la 2NF ne soit pas respectée saute aux yeux, car une fois que l’on sait que {A,F} est clé candidate, la présence fautive de DF partielle {A}→{B} est détectée sur le champ. Mais dans mon rapport d’expertise, j’écrirai simplement que la BCNF n’est pas respectée, sans perdre de temps à expliquer que la faute en incombe à une DF partielle provoquant un viol de 2NF.


    Citation Envoyé par catcat Voir le message
    Autrement dit, si on ne valide pas en BCNF, y-a-t-il une démarche adéquate et quelle est-elle ?
    Je me suis inspirée de votre post pour proposer quelques "solutions". Certaines vous feront sans doute sauter au plafond, mais allons-y quand même.
    - on se contente, si cela est possible, de la 3NF. Dans ce cas, quel risque prend-on avec notre base de données ?
    - on décompose et on normalise coûte que coûte en BCNF toutes les relations après décomposition, quitte à perdre en route la conformité avec quelques règles de gestion.
    - On revient sur l'analyse pour traquer les règles de gestion abusives qu'il conviendra d'assouplir afin d'obtenir des relations BCNFisables.
    Structurellement parlant, se contenter de respecter la seule 3NF est possible, c'est-à-dire en ne décomposant pas la relation en cause. En contrepartie, il faut mettre en œuvre un système automatique interdisant la présence des redondances, au nom du respect des règles de gestion des données de l’entreprise. Du point de vue de la norme SQL, on peut utiliser pour cela une assertion. Si votre SGBD ne propose pas l’instruction Create assertion, vous pouvez en passer par un trigger pour garantir que lors des ajouts et des modifications, la DF (ou les DF) en cause seront respectées.

    Normaliser coûte que coûte en BCNF est préférable, mais là encore, il est hors de question de perdre en route la conformité avec quelque règle de gestion que ce soit. Une fois de plus, assertions ou triggers doivent être mis en oeuvre à cet effet.

    Revenir sur l’analyse pour essayer de faire évoluer les règles de gestion est ce qui doit être entrepris en premier. Les rares fois où j’ai été confronté au problème (et croyez-moi, j’ai des heures de vol, dans tous les secteurs d’activité), le maître d’ouvrage a toujours convenu que les règles étaient révisables, m’évitant ainsi de cauchemarder sur le dilemme dont nous venons de débattre. Je ne dis pas que la révision des règles est toujours possible, mais en l'occurrence, je n’ai trouvé jusqu’ici que des cas d’école. Il est probable aussi que je n’ai pas détecté quelques anomalies...

    Pour conclure, je vous invite à lire ce qu’a écrit Date au sujet de l’histoire de la normalisation. Récupérez (tant que ces articles sont en ligne) :
    Vous y trouverez notamment la remarquable définition des 3NF et BCNF par Carlo Zaniolo, montrant bien comment on peut entamer une approche descendante.
    Faites simple, mais pas plus simple ! (A. Einstein)
    E=mc², mais si on discute un peu, on peut l’avoir pour beaucoup moins cher... (G. Lacroix, « Les Euphorismes de Grégoire »)
    => La relativité n'existerait donc que relativement aux relativistes (Jean Eisenstaedt, « Einstein et la relativité générale »)


    De grâce, pas de questions techniques par MP, ma boîte de réception explose !
    __________________________________
    Bases de données relationnelles et normalisation : de la première à la sixième forme normale (Bonne lecture !)

  7. #7
    Candidat au titre de Membre du Club
    Inscrit en
    octobre 2006
    Messages
    15
    Détails du profil
    Informations forums :
    Inscription : octobre 2006
    Messages : 15
    Points : 13
    Points
    13

    Par défaut

    Bonsoir fsmrel,

    Merci pour cette réponse claire, ces portes ouvertes pour en savoir plus, et ces petites histoires. C'est aussi avec elles que l'histoire des bases de données s'est construite.

    A une prochaine fois,
    Catcat

  8. #8
    Invité de passage
    Inscrit en
    novembre 2012
    Messages
    4
    Détails du profil
    Informations forums :
    Inscription : novembre 2012
    Messages : 4
    Points : 1
    Points
    1

    Par défaut

    Je profite d'une question pour remonter la discussion.

    Pour produire la liste des clés candidates : Dois-on utiliser les axiomes d'Armstrong pour établir la couverture minimal (ou s'il existe un moyen moins barbant) ou est-ce qu'une fermeture transitive marche pour cet algorithme ?

    Merci

  9. #9
    Expert Confirmé Sénior
    Avatar de fsmrel
    Homme Profil pro François de Sainte Marie
    Spécialiste en bases de données
    Inscrit en
    septembre 2006
    Messages
    4 836
    Détails du profil
    Informations personnelles :
    Nom : Homme François de Sainte Marie
    Localisation : Autre

    Informations professionnelles :
    Activité : Spécialiste en bases de données
    Secteur : Conseil

    Informations forums :
    Inscription : septembre 2006
    Messages : 4 836
    Points : 13 819
    Points
    13 819

    Par défaut

    Bonsoir,


    Attention au terme « fermeture transitive » dont la définition est la suivante (cf. l'ouvrage de Chris Date The Relational Database Dictionary) :

    Soit r une relation binaire d’attributs A et B, tous deux de type T. La fermeture transitive TCLOSE(r) est une relation r+ ainsi définie :
    Le tuple <a,b> apparaît dans r+ si et seulement si (a) il apparaît dans r, ou bien (b) il existe une valeur c de type T tel que le tuple <a,c> apparaît dans r et le tuple <c,b> apparaît dans r+.
    Voyez à ce sujet l’exemple des arbres entremêlés.


    La fermeture qui vous intéresse est une fermeture de dépendances fonctionnelles et se définit ainsi (je fais référence à Chris Date) :
    On appelle fermeture S+ d’un ensemble S de dépendances fonctionnelles, l’ensemble de toutes les dépendances fonctionnelles qui sont impliquées par S.

    Autrement dit, S+ est l’ensemble des dépendances fonctionnelles inférables à partir de S au moyen des axiomes et règles d’Armstrong.

    Attention à l’usage que fait Date de l’implication : S est donné, donc S+ est plus précisément la conséquence logique de S (par application des axiomes et règles d’Armstrong).

    Prenons par exemple la règle d’union (notation de Ullman ou Fagin) :
    {X -> Y, X -> Z} X -> YZ
    X, Y, Z sont des sous-ensembles d’attributs d’une relation R et YZ se lit : Y UNION Z.


    Pour répondre à votre question, il est évident que la seule application des axiomes d’Armstrong n’est pas à recommander vu le temps nécessaire pour calculer la fermeture, même avec un ordinateur (si l’en-tête d’une relation comporte n noms d’attributs, le nombre maximum de DF peut être égal à 2^2n)...

    Je vous renvoie à mon article : Bases de données relationnelles et normalisation : de la première à la sixième forme normale, à l’annexe E. Il est évident que l’utilisation de l’algorithme du seau (officiellement algorithme de Bernstein) est à recommander pour rechercher les clés candidates : vous pouvez même écrire une procédure SQL pour y arriver (c’est moins barbant...)

    Si DFx est une DF et si au moyen de l’algorithme on montre que DFx+ contient l’ensemble des attributs de l’en-tête de la relation r, alors on conclut que le déterminant (partie gauche de DFx) est clé candidate de r.

    N'hésitez pas à poser vos questions (je pense qu'Oishiiii se fera un plaisir de participer...)
    Faites simple, mais pas plus simple ! (A. Einstein)
    E=mc², mais si on discute un peu, on peut l’avoir pour beaucoup moins cher... (G. Lacroix, « Les Euphorismes de Grégoire »)
    => La relativité n'existerait donc que relativement aux relativistes (Jean Eisenstaedt, « Einstein et la relativité générale »)


    De grâce, pas de questions techniques par MP, ma boîte de réception explose !
    __________________________________
    Bases de données relationnelles et normalisation : de la première à la sixième forme normale (Bonne lecture !)

  10. #10
    Membre à l'essai
    Inscrit en
    décembre 2010
    Messages
    27
    Détails du profil
    Informations personnelles :
    Âge : 22

    Informations forums :
    Inscription : décembre 2010
    Messages : 27
    Points : 20
    Points
    20

    Par défaut Interrogations

    Citation Envoyé par fsmrel Voir le message
    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.
    Cher fsmrel, puis-je me permettre de rouvrir ce sujet, j'ai quelques interrogations.

    Pour mémoire :
    Les DFs de l'exercice sont :

    A -> B
    C -> A
    C -> D
    A,F -> C
    A,F -> E

    et les clés candidates de R{A,B,C,D,E,F} : {A,F},{C,F}

    L'algorithme de décomposition de relations en 2FN n'est pas encore précis dans mon esprit.

    - On calcul les clés candidates de la relation R
    - On vérifie que la relation R est en 2FN en vérifiant qu'il n'y-ait pas de DF que satisfait R qui puisse rendre partielles les DF définies pas les clés candidates calculés de R.
    - Si elle ne l'est pas, on la décompose en 2 relations R1 et R2 : on trouve un attribut pivot grâce au DFs et au théorème de Heath, si possible celui de Jorma Rissanen. Ainsi R1 contient les attributs isolés des DFs posant problème pour la satisfaction de la 2FN pour R et R2 les autres attributs restants de la relation R plus son attribut pivot bien sur.

    - On continue jusque que toutes les relations soient en 2FN..

    Si je tente une normalisation en 2FN :

    1ère étape :
    R1(A,B) - Respecte la 2FN car A, clé candidate singleton donc la DF A-> B ne peut pas être partielle.
    R2(A,C,D,E,F) ne respecte pas la 2FN car il existe {C} -> {D} et D est un sous ensemble strict d'attributs de la dépendance {C,F} -> {D} donné par une des clés candidates

    2ème étape : on décompose de la même manière R2 :
    R21(C,A,D) - Respecte la 2FN car à pour clé candidate C : un singleton
    R22(C,E,F) respecte aussi la 2NF car la clé candidate calculé est {A,F} et les attributs C,E dépendent de la globalité de la clé candidate

    - Est-ce correct ?
    - Qu'en est-il pour la décomposition en 3FN ?
    - Apparemment ces relations décomposées satisfaient chacune la BCNF car nous avons le même résultat que pour la décomposition de R pour la satisfaction de la BCNF
    - Par ailleurs, comment d'après l'énoncé de la 2NF, est-il est possible qu'une relation soit en dépendance totale de plusieurs clés candidates ?

    Je vous remercie.

  11. #11
    Expert Confirmé Sénior
    Avatar de fsmrel
    Homme Profil pro François de Sainte Marie
    Spécialiste en bases de données
    Inscrit en
    septembre 2006
    Messages
    4 836
    Détails du profil
    Informations personnelles :
    Nom : Homme François de Sainte Marie
    Localisation : Autre

    Informations professionnelles :
    Activité : Spécialiste en bases de données
    Secteur : Conseil

    Informations forums :
    Inscription : septembre 2006
    Messages : 4 836
    Points : 13 819
    Points
    13 819

    Par défaut

    Bonsoir lagra007,


    Citation Envoyé par lagra007 Voir le message

    1ère étape :
    R1(A,B) - Respecte la 2FN car A, clé candidate singleton donc la DF A-> B ne peut pas être partielle.
    R2(A,C,D,E,F) ne respecte pas la 2FN car il existe {C} -> {D} et D est un sous ensemble strict d'attributs de la dépendance {C,F} -> {D} donné par une des clés candidates
    Correct.


    Citation Envoyé par lagra007 Voir le message
    2ème étape : on décompose de la même manière R2 :
    R21(C,A,D) - Respecte la 2FN car à pour clé candidate C : un singleton
    R22(C,E,F) respecte aussi la 2NF car la clé candidate calculé est {A,F} et les attributs C,E dépendent de la globalité de la clé candidate
    D’accord pour R21. D’accord pour R22, à condition de préciser que la clé en est {C,F} : en effet, {A,F} ne vaut pas puisque l’attribut A ne figure pas dans l’en-tête de R22, aussi je suppose qu’il s’agit d’une coquille de votre part.

    Quoi qu’il en soit, votre ensemble de décompositions est le suivant, P1 :
    R1 {A, B}
    R21 {C,A,D}
    R22 {C,E,F}
    Comme vous avez systématiquement appliqué le théorème de Heath, les données sont préservées par les décompositions successives. Par contre, comme prévient Rissanen, décomposer ainsi ne préserve pas forcément les dépendances fonctionnelles, et il est un fait que la DF : {A,F} -> {C,E} est perdue.

    Pour éviter cette perte de DF, on complète les décompositions R1, R21, R22 avec R3 {A,C,E,F}, d’où l’ensemble P2 :
    R1 {A, B}
    R21 {C,A,D}
    R22 {C,E,F}
    R3 {A,C,E,F}
    Mais on observe que R22 est incluse dans R3 et peut donc disparaître, il reste P3 :
    R1 {A, B}
    R21 {C,A,D}
    R3 {A,C,E,F}
    R3 viole la BCNF, mais on ne perd pas de DF. Si on préfère s’accrocher à Heath, on peut décomposer R3 grâce à la DF : {C,F} -> {E} ou à la DF : {C,F} -> {A} et l’ensemble des décompositions devient P4 :
    R1 {A, B}
    R21 {C,A,D}
    R22 {C,E,F}
    R31 {A,C,F}
    Mais si les DF sont préservées et la 2NF toujours respectée (ainsi que la 3NF d’ailleurs), R31 (de clés {A,F} et {C,F}) viole la BCNF du fait de la DF {C} -> {A} dont le déterminant ne constitue pas une clé.

    Tout ceci est certes un peu tordu, mais c’est un bon exercice...

    D’un point de vue scolaire, l’usage est en général de procéder autrement : on détermine un ensemble irréductible I de DF pour R {A,B,C,D,E,F}, c'est-à-dire un ensemble de DF totales et non inférables des autres DF (on emploie plus souvent l’expression « couverture minimale ») et on met à profit un théorème dû à Bernstein :
    Soit un en-tête de relvar R auquel est associé un ensemble irréductible I de DF : I est une décomposition de R en 3NF, préservant les DF.
    La partie fastidieuse et prenant du temps étant évidemment imputable au calcul de la fameuse couverture minimale...

    On a par exemple les couvertures pour R :
    CM1 = {{A -> B}, {C -> A}, {C -> D}, {A,F -> C}, {C,F -> E}}
    CM2 = {{A -> B}, {C -> A}, {C -> D}, {A,F -> C}, {A,F -> E}}
    A partir desquelles on sait retrouver les décompositions P2, P3, P4 ci-dessus.

    Un autre théorème de Bernstein montre que si K est une clé de R, alors I {K} est une décomposition en 3NF, préservant les DF et sans perte de données.

    Comme les décompositions P2, P3, P4 et les couvertures minimales CM1 et CM2 préservent ne serait-ce que la clé {A,F}, la 3NF est préservée (donc la 2NF).

    Citation Envoyé par lagra007 Voir le message
    Par ailleurs, comment d'après l'énoncé de la 2NF, est-il est possible qu'une relation soit en dépendance totale de plusieurs clés candidates ?
    Exemple 1 :
    R = {A,B}

    DF : {{A}->{B}, {B}->{A}}
    Les clés sont {A} et {B} et R est au moins en 2NF.

    Exemple 2 :
    R = {A,B,C,D,E,F}

    DF : {{A,B} -> {C,D,E}, {C,D} -> {A,B}, {E} -> {F}}
    Les clés sont {A,B} et {C,D}, et R est en 2NF (sans être en 3NF).
    Faites simple, mais pas plus simple ! (A. Einstein)
    E=mc², mais si on discute un peu, on peut l’avoir pour beaucoup moins cher... (G. Lacroix, « Les Euphorismes de Grégoire »)
    => La relativité n'existerait donc que relativement aux relativistes (Jean Eisenstaedt, « Einstein et la relativité générale »)


    De grâce, pas de questions techniques par MP, ma boîte de réception explose !
    __________________________________
    Bases de données relationnelles et normalisation : de la première à la sixième forme normale (Bonne lecture !)

  12. #12
    Membre à l'essai
    Inscrit en
    décembre 2010
    Messages
    27
    Détails du profil
    Informations personnelles :
    Âge : 22

    Informations forums :
    Inscription : décembre 2010
    Messages : 27
    Points : 20
    Points
    20

    Par défaut

    Citation Envoyé par fsmrel Voir le message
    Merci beaucoup !

+ Répondre à la discussion
Cette discussion est résolue.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •