IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Schéma Discussion :

Probléme normalisation relation


Sujet :

Schéma

  1. #1
    Membre à l'essai
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    22
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 22
    Points : 20
    Points
    20
    Par défaut Probléme normalisation relation
    Bonsoir ,j'essaye de faire d'autre exemple pour la normalisation pour que je comprend plus pour l'examen que j'ai lundi .
    pour le 1ere Porbléme je l'vais fais il me manque que le calcule de la fermeture .
    II et III Probléme j'ai pas réussi a le faire


    1.I.Peut-on démontrer les dépendances fonctionnelles suivantes à partir de F = {AB->C , B->D, CD->E ,CE->GH , G->A }?Si c'est le cas proposez une démonstration détaillée sinon justifiez votre réponse.
    1. CE->D

    2.BG->C

    la réponse fournis pour 1.CE->D je n'ai pas réussi le calcul de {C,E}->D à partir de F , alors elle est impossible mais je pense que je devrais dire que la fermeture de {C,E}+ de {C,E} n'appartient pas à F Mais pour la fermeture je ne sais pas comment la calculer ?

    pour la deuxième et vrai explication

    R(A,B,C,E,D,G,H}

    R satisfait l'ensemble F de DF suivant :
    DF1: {A,B} -> {c}
    DF2:{B}->D
    DF3:{C,D}->{E}
    DF4:{C,E} ->{G,H}
    DF5 : {G}-> {A}
    à l'aide l'axiome d'amstrong on obtiens :
    1.{B,G} ->{A,B} (DF5 augmentation )
    2.{A,B}->{C}
    3.{B,G}->{C} (1 et 2 transition)
    donc pour la 2 et vrai



    II.Déterminez si les décompositions suivante sont sans perte d'information (SPI).si une décomposition n'est pas SPI vous proposez un contre exemple et montrerez qu'il s'agit bien d'un contre exemple.
    1.U=ABCDE , F={A->E,C->E, D->A ,E->D} , Δ=ABC ,DE,CD
    2.U= ABCDE ,F = {B->A,CE->B,C->E,D->E},Δ=ABC,DE ,CD

    III.Déterminez si la décomposition Δ=AB , BD est sans perte de dépendances par rapport à F = {A->B,B->D}
    merci

  2. #2
    Expert éminent sénior
    Avatar de fsmrel
    Homme Profil pro
    Spécialiste en bases de données
    Inscrit en
    Septembre 2006
    Messages
    7 966
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

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

    Informations forums :
    Inscription : Septembre 2006
    Messages : 7 966
    Points : 30 778
    Points
    30 778
    Billets dans le blog
    16
    Par défaut
    je pense que je devrais dire que la fermeture de {C,E}+ de {C,E} n'appartient pas à F Mais pour la fermeture je ne sais pas comment la calculer ?
    Utilisez l'algorithme qu'on vous a déjà fourni :


    http://www.developpez.net/forums/d93...n/#post5283108
    (a) Faites simple, mais pas plus simple ! (A. Einstein)
    (b) Certes, 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 »)

    __________________________________
    Bases de données relationnelles et normalisation : de la première à la sixième forme normale
    Modéliser les données avec MySQL Workbench
    Je ne réponds pas aux questions techniques par MP. Les forums sont là pour ça.

  3. #3
    Membre à l'essai
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    22
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 22
    Points : 20
    Points
    20
    Par défaut
    Bonsoir
    je pense que la fermeture qu'on j'aurai est ça :
    {C,E}+={C,E,G,H,A}

  4. #4
    Expert éminent sénior
    Avatar de fsmrel
    Homme Profil pro
    Spécialiste en bases de données
    Inscrit en
    Septembre 2006
    Messages
    7 966
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

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

    Informations forums :
    Inscription : Septembre 2006
    Messages : 7 966
    Points : 30 778
    Points
    30 778
    Billets dans le blog
    16
    Par défaut
    Citation Envoyé par yaya125 Voir le message
    Bonsoir
    je pense que la fermeture qu'on j'aurai est ça :
    {C,E}+={C,E,G,H,A}
    Exact. Et comme D n'en fait pas partie, la DF {C,E} -> {D} ne peut pas exister.
    (a) Faites simple, mais pas plus simple ! (A. Einstein)
    (b) Certes, 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 »)

    __________________________________
    Bases de données relationnelles et normalisation : de la première à la sixième forme normale
    Modéliser les données avec MySQL Workbench
    Je ne réponds pas aux questions techniques par MP. Les forums sont là pour ça.

  5. #5
    Membre à l'essai
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    22
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 22
    Points : 20
    Points
    20
    Par défaut
    Merci par contre les 2 dernier probléme je sais pas leur solution , peut être je vais avoir comme ce genre d'exercice a mn examen stp pourrai tu me donner une solution bien explicative .

  6. #6
    Membre à l'essai
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    22
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 22
    Points : 20
    Points
    20
    Par défaut
    II.Déterminez si les décompositions suivante sont sans perte d'information (SPI).si une décomposition n'est pas SPI vous proposez un contre exemple et montrerez qu'il s'agit bien d'un contre exemple.
    1.U=ABCDE , F={A->E,C->E, D->A ,E->D} , Δ=ABC ,DE,CD
    2.U= ABCDE ,F = {B->A,CE->B,C->E,D->E},Δ=ABC,DE ,CD

    pour la 1ere question voilà la réponse que je présente mais je ne pense pas qu'elle est just :

    Δ A B C D E

    ABC a b c x1 x2

    DE x3 x4 x5 d e

    CD x6 x7 c d x8

    on remarque qu'il y a au moins une ligne sans variable donc SPI
    je pense qu'il me manque d'explication !!

  7. #7
    Expert éminent sénior
    Avatar de fsmrel
    Homme Profil pro
    Spécialiste en bases de données
    Inscrit en
    Septembre 2006
    Messages
    7 966
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

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

    Informations forums :
    Inscription : Septembre 2006
    Messages : 7 966
    Points : 30 778
    Points
    30 778
    Billets dans le blog
    16
    Par défaut
    1er cas : U=ABCDE , F={A->E, C->E, D->A ,E->D} , Δ=ABC ,DE, CD

    La représentation tabulaire que vous utilisez ressemble à celle de Ullman, à la notation près :




    Il faut maintenant que vous exploitiez les dépendances fonctionnelles pour faire évoluer le tableau.

    Considérons la dépendance fonctionnelle A -> E. On cherche dans la colonne A du tableau les valeurs égales : il n’y en a pas, donc rien ne se passe.

    Considérons la dépendance fonctionnelle C -> E. On cherche dans la colonne C du tableau les valeurs égales : on trouve la valeur c pour la ligne 1 et pour la ligne 3 : on peut rendre égales les valeurs correspondantes dans la colonne E :



    Considérons la dépendance fonctionnelle D -> A. On cherche dans la colonne D du tableau les valeurs égales : on trouve la valeur d pour la ligne 2 et pour la ligne 3 : on peut rendre égales les valeurs correspondantes dans la colonne A :



    Considérons la dépendance fonctionnelle E -> D. On cherche dans la colonne E du tableau les valeurs égales : on trouve la valeur x2 pour la ligne 1 et pour la ligne 3 : on peut rendre égales les valeurs correspondantes dans la colonne D (en privilégiant la valeur forte d plutôt que la valeur faible x1, car le but de la manœuvre est de faite disparaître les xi) :



    On a exploité toutes les dépendances fonctionnelles. On recommence le processus, tant que le tableau peut évoluer.

    Considérons à nouveau la dépendance fonctionnelle A -> E. On cherche dans la colonne A du tableau les valeurs égales :



    on trouve la valeur x3 pour la ligne 2 et pour la ligne 3 : on peut rendre égales les valeurs correspondantes dans la colonne E (en privilégiant la valeur forte e plutôt que la valeur faible x2) :




    Considérons la dépendance fonctionnelle C -> E. On cherche dans la colonne C du tableau les valeurs égales : on trouve la valeur c pour la ligne 1 et pour la ligne 3 : on peut rendre égales les valeurs correspondantes dans la colonne E (en privilégiant la valeur forte e plutôt que la valeur faible x2) :




    Sans même poursuivre le processus, sachant que pour que la décomposition soit sans perte, il suffit qu'il existe dans le tableau au moins une ligne sans xi, et comme c’est le cas de la 1re ligne, on conclut que la décomposition est sans perte.
    (a) Faites simple, mais pas plus simple ! (A. Einstein)
    (b) Certes, 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 »)

    __________________________________
    Bases de données relationnelles et normalisation : de la première à la sixième forme normale
    Modéliser les données avec MySQL Workbench
    Je ne réponds pas aux questions techniques par MP. Les forums sont là pour ça.

  8. #8
    Membre éprouvé Avatar de Oishiiii
    Homme Profil pro
    Administrateur de base de données
    Inscrit en
    Août 2009
    Messages
    508
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Ain (Rhône Alpes)

    Informations professionnelles :
    Activité : Administrateur de base de données

    Informations forums :
    Inscription : Août 2009
    Messages : 508
    Points : 1 104
    Points
    1 104
    Par défaut
    Citation Envoyé par fsmrel Voir le message
    1er cas : U=ABCDE , F={A->E, C->E, D->A ,E->D} , Δ=ABC ,DE, CD
    ...
    on conclut que la décomposition est sans perte.
    Bonjour fsmrel,

    J'étais sur le point d'envoyer une réponse lorsque j'ai vu votre message.

    J'ai pensé que la décomposition n'était pas correcte, elle perd des DF, par exemple, {D} → {A} n'apparaît dans aucune relvar.

    Je viens de vérifier si la jointure des relvars {A, B, C}, {D, E} et {C, D} ne produisait pas d'anomalies en les représentant dans des tables avec des valeurs, et il n'y a pas de problèmes effectivement.

    Je suis parti de l'ensemble F des DF et en suivant les conseils de Heath et surtout Jorma Rissanen j'ai décomposé U pour obtenir ces relvars:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    Ua = {B, C}
    Ub = {A, E}
    Uc = {C, E}
    Ud = {D, A}
    Ue = {E, D}
    Finalement j'ai une relvar pour la clé candidate {B, C} et des relvars pour chaque DF — il n'y a littéralement aucune perte de DF.

    Comment arrive-t'on à la décomposition donnée dans l'exercice à partir de F ? Quelle est la logique à suivre ?
    Je vois bien que pour la relvar composée des attributs D et E on joue avec la transitivité d'Armstrong à partir des DF {D} → {A} et {A} → {E}, mais il ne me serait jamais venu à l'esprit de créer la relvar {A, B, C} par exemple.
    C'est peut-être simplement l'expérience qui permet d'obtenir une décomposition équivalente à la mienne avec moins de relvar.

  9. #9
    Membre à l'essai
    Profil pro
    Inscrit en
    Décembre 2009
    Messages
    22
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2009
    Messages : 22
    Points : 20
    Points
    20
    Par défaut
    Bonsoir Merci beaucoup j'ai tro bien compris par contre le dernier probléme est ce que peut tu me l'expliquer ?

  10. #10
    Expert éminent sénior
    Avatar de fsmrel
    Homme Profil pro
    Spécialiste en bases de données
    Inscrit en
    Septembre 2006
    Messages
    7 966
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

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

    Informations forums :
    Inscription : Septembre 2006
    Messages : 7 966
    Points : 30 778
    Points
    30 778
    Billets dans le blog
    16
    Par défaut Renvoi vers l'algorithme qui va bien.
    Citation Envoyé par yaya125
    j'ai tro bien compris par contre le dernier probléme est ce que peut tu me l'expliquer ?

    Déterminez si la décomposition Δ=AB , BD est sans perte de dépendances par rapport à F = {A->B, B->D}
    Ayant lu trop vite la question posée par yaya, je renvoie vers le message qui va bien :

    http://www.developpez.net/forums/d94...n/#post5307151

    Ce qui suit vaut pour la décomposition sans perte de données mais ne concerne pas la perte des dépendances...

    Appliquer le théorème de Heath :

    Soit la relvar R {A, B, C} dans laquelle A, B et C sont des ensembles d’attributs de R. Si R satisfait à la dépendance fonctionnelle A -> B, alors R est égale à la jointure de ses projections sur {A, B} et {A, C}.

    En tenant compte de la recommandation de Rissanen :
    Soit la relvar R {A, B, C} dans laquelle A, B et C sont des ensembles d’attributs de R. Si R satisfait aux dépendances fonctionnelles A -> B et B -> C, alors plutôt que de décomposer R en {A, B} et {A, C}, on décomposera R en {A, B} et {B, C}.
    (a) Faites simple, mais pas plus simple ! (A. Einstein)
    (b) Certes, 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 »)

    __________________________________
    Bases de données relationnelles et normalisation : de la première à la sixième forme normale
    Modéliser les données avec MySQL Workbench
    Je ne réponds pas aux questions techniques par MP. Les forums sont là pour ça.

  11. #11
    Expert éminent sénior
    Avatar de fsmrel
    Homme Profil pro
    Spécialiste en bases de données
    Inscrit en
    Septembre 2006
    Messages
    7 966
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

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

    Informations forums :
    Inscription : Septembre 2006
    Messages : 7 966
    Points : 30 778
    Points
    30 778
    Billets dans le blog
    16
    Par défaut
    Citation Envoyé par Oishiiii
    il ne me serait jamais venu à l'esprit de créer la relvar {A, B, C}
    A moi non plus ! En effet, je viens du terrain, et quand j’ai commencé dans le métier, l’informatique n’était pas encore enseignée à l’Université...

    J’ai expertisé, « soigné » des monceaux de modèles conceptuels et de bases de données, et je n’ai jamais eu le temps de jouer à au petit jeu des décompositions multiples, car les délais, les contraintes financières et autres considérations bassement matérielles imposées par nos clients m’obligeaient à aller vite. Pour ne pas me planter, j’ai toujours suivi Heath et Rissanen et je n’ai jamais été déçu.

    Quant à produire des décompositions comportant moins de relvars, ça n’est pas forcément un bon plan. Dans le contexte d’une production informatique, ça n’est qu’en effectuant un prototypage des performances que l’on peut trancher en faveur d’une structure.

    Cela dit, je mets encore Ullman à contribution. Il propose en effet une variante du théorème de Heath qui peut vous intéresser. Ullman précise que cette variante est due à Delobel et Casey ainsi qu’à Rissanen. Le théorème est le suivant :
    Si ρ = (R1, R2) est une décomposition de R, et F est ensemble de dépendances fonctionnelles, alors ρ a une décomposition sans perte par rapport à F si et seulement si
    (R1 R2) (R1 — R2) ou (R1 R2) (R2 — R1)
    En notant que ces dépendances ne font pas nécessairement partie de F, il suffit qu’elles appartiennent à la fermeture F+.

    Pour reprendre l’exemple qui vous interpelle, considérons la décomposition ρ = ({A, B, C}, {C, D, E}). Pour qu’elle soit sans perte, on doit vérifier :

    ({A, B, C} {C, D, E}) ({A, B, C} — {C, D, E}) ou ({A, B, C} {C, D, E}) ({C, D, E} — {A, B, C})
    On a :
    {A, B, C} {C, D, E} = {C}
    {C, D, E} — {A, B, C} = {D, E}
    Or {C} {D, E} appartient à F+ puisque {C}+ = {A, C, D, E} : la décomposition est bien sans perte.

    A son tour, le triple {C, D, E} est-il décomposable sans perte en {C, D} et {D, E} ? Si oui, on doit vérifier :
    ({C, D} {D, E}) ({C, D} — {D, E}) ou ({C, D} {D, E}) ({D, E} — {C, D})
    On a :
    {C, D} {D, E} = {D}
    {D, E} — {C, D} = {E}
    Or {D} {E} appartient à F+ puisque {D}+ = {A, D, E} : la décomposition est bien sans perte.

    Ainsi, R = {A, B, C, D, E} peut être décomposée en ρ = ({A, B, C}, {C, D}, {D, E}). La variante du théorème de Heath permet de produire de nouvelles décompositions, mais notre brave théorème initial suffit quand on construit des bases de données pour de vrai.
    (a) Faites simple, mais pas plus simple ! (A. Einstein)
    (b) Certes, 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 »)

    __________________________________
    Bases de données relationnelles et normalisation : de la première à la sixième forme normale
    Modéliser les données avec MySQL Workbench
    Je ne réponds pas aux questions techniques par MP. Les forums sont là pour ça.

  12. #12
    Expert éminent sénior
    Avatar de fsmrel
    Homme Profil pro
    Spécialiste en bases de données
    Inscrit en
    Septembre 2006
    Messages
    7 966
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

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

    Informations forums :
    Inscription : Septembre 2006
    Messages : 7 966
    Points : 30 778
    Points
    30 778
    Billets dans le blog
    16
    Par défaut
    Citation Envoyé par yaya125
    Déterminez si la décomposition Δ=AB , BD est sans perte de dépendances par rapport à F = {A->B, B->D}
    A l’occasion de ma réponse précédente, j’ai lu trop vite, et je n’ai pas vu qu’il s’agissait de perte de dépendances. C’est vrai que la décomposition Δ est sans perte de dépendance, mais le théorème de Heath n’a rien à voir dans cette affaire. On va donc mettre en oeuvre le marteau-pilon qui va bien pour répondre à la question.

    On définit un ensemble G qui est l’union des projections sur F des éléments de Δ, à savoir AB et BD : G = πAB(F) U πBD(F).

    Ensuite on applique l’algorithme suivant :



    X est le déterminant d’une DF X -> Y appartenant à F. Ri représente successivement les éléments de Δ, à savoir AB puis BD.

    En fin de parcours, si Y est un sous-ensemble de Z, alors X -> Y appartient à G.

    Si chaque DF telle que X -> Y appartenant à F appartient aussi à G, alors Δ préserve F, sinon il y a perte de dépendance.

    On commence avec le déterminant A de la DF A -> B et le 1er élément de Δ, à savoir AB.



    Le dépendant B de la DF A -> B constitue un sous-ensemble de Z, donc A -> B appartient à G.

    On passe au déterminant B de la DF B -> D et le 1er élément de Δ, à savoir AB : en fin d’itération Z est seulement égal à B, aussi on poursuit avec le 2e élément de Δ, à savoir BD :



    Le dépendant D de la DF B -> D constitue un sous-ensemble de Z, donc B -> D appartient à G.

    Toutes les DF appartenant à F appartiennent aussi à G, donc la décomposition Δ préserve les dépendances par rapport à F.
    (a) Faites simple, mais pas plus simple ! (A. Einstein)
    (b) Certes, 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 »)

    __________________________________
    Bases de données relationnelles et normalisation : de la première à la sixième forme normale
    Modéliser les données avec MySQL Workbench
    Je ne réponds pas aux questions techniques par MP. Les forums sont là pour ça.

  13. #13
    Membre éprouvé Avatar de Oishiiii
    Homme Profil pro
    Administrateur de base de données
    Inscrit en
    Août 2009
    Messages
    508
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Ain (Rhône Alpes)

    Informations professionnelles :
    Activité : Administrateur de base de données

    Informations forums :
    Inscription : Août 2009
    Messages : 508
    Points : 1 104
    Points
    1 104
    Par défaut
    Bonjour fsmrel,

    Excusez-moi pour cette question certainement triviale, mais que fait l'opérateur — ?
    Citation Envoyé par fsmrel Voir le message
    ({A, B, C} {C, D, E}) ({A, B, C} — {C, D, E}) ou ({A, B, C} {C, D, E}) ({C, D, E} — {A, B, C})
    On a :
    {A, B, C} {C, D, E} = {C}
    {A, B, C} — {C, D, E} = {A}
    A priori je pencherai sur une Différence, mais {A, B, C} — {C, D, E} donnerait {A, B} dans ce cas ?

    A+

  14. #14
    Expert éminent sénior
    Avatar de fsmrel
    Homme Profil pro
    Spécialiste en bases de données
    Inscrit en
    Septembre 2006
    Messages
    7 966
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

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

    Informations forums :
    Inscription : Septembre 2006
    Messages : 7 966
    Points : 30 778
    Points
    30 778
    Billets dans le blog
    16
    Par défaut
    Citation Envoyé par Oishiiii
    A priori je pencherai sur une Différence, mais {A, B, C} — {C, D, E} donnerait {A, B} dans ce cas ?
    Il s'agit bien d'une opération de différence et donc {A, B, C} — {C, D, E} a pour résultat {A, B}.

    Merci d'avoir tout relu. Je rectifie en conséquence :

    Considérons la décomposition ρ = ({A, B, C}, {C, D, E}). Pour qu’elle soit sans perte, on doit vérifier :

    ({A, B, C} {C, D, E}) ({A, B, C} — {C, D, E}) ou ({A, B, C} {C, D, E}) ({C, D, E} — {A, B, C})
    On a :
    {A, B, C} {C, D, E} = {C}
    {C, D, E} — {A, B, C} = {D, E}
    Or {C} {D, E} appartient à F+ puisque {C}+ = {A, C, D, E} : la décomposition est bien sans perte.

    Si ça ne vous ennuie pas de bien relire, je suis tout endormi...
    (a) Faites simple, mais pas plus simple ! (A. Einstein)
    (b) Certes, 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 »)

    __________________________________
    Bases de données relationnelles et normalisation : de la première à la sixième forme normale
    Modéliser les données avec MySQL Workbench
    Je ne réponds pas aux questions techniques par MP. Les forums sont là pour ça.

  15. #15
    Expert éminent sénior
    Avatar de fsmrel
    Homme Profil pro
    Spécialiste en bases de données
    Inscrit en
    Septembre 2006
    Messages
    7 966
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

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

    Informations forums :
    Inscription : Septembre 2006
    Messages : 7 966
    Points : 30 778
    Points
    30 778
    Billets dans le blog
    16
    Par défaut Attention aux pertes de DF...
    Citation Envoyé par Oishiiii Voir le message
    Je viens de vérifier si la jointure des relvars {A, B, C}, {D, E} et {C, D} ne produisait pas d'anomalies en les représentant dans des tables avec des valeurs, et il n'y a pas de problèmes effectivement.

    Comment arrive-t'on à la décomposition donnée dans l'exercice à partir de F ? Quelle est la logique à suivre ?
    Concernant la logique à suivre, ou plutôt la tactique, il y en a plus d'une, car il y a un bon paquet de DF inférables permettant de produire des décompositions plus ou moins valables...

    Utilisons par exemple les DF {D}{E} et {C}{D} inférées au moyen des règles d'Armstrong (les DF {D}{A} et {A}{E} étant données, par transitivité on produit {D}{E}, de même les DF {C}{E} et {E}{D}, étant données, par transitivité on produit la DF {C}{D}).

    Grâce à la DF {D}{E}, par application du théorème de Heath, on peut décomposer R en :
    R1 {D, E} et R2 {A, B, C, D}
    Grâce à la DF {C}{D}, par application du théorème de Heath, on peut décomposer R2 en :
    R21 {C, D} et R22 {A, B, C}
    On retrouve ainsi la décomposition proposée à yaya125 : {A, B, C}, {D, E}, {C, D}.

    Mais il y a un os : R22 (de clé {B, C}) viole la 2NF à cause de la DF {C}{A} (du fait des DF {C}{E} et {E}{D} par transitivité on produit la DF {C}{D} et comme on a {D}{A} par transitivité à nouveau, on produit la DF {C}{A}).

    La décomposition doit être poursuivie, et au final on obtient la décomposition :
    R221 {C, A}, R222 {B, C}, R1 {D, E}, R21 {C, D}
    Pour laquelle chaque relvar respecte la BCNF, mais qui n'est pas forcément à recommander elle non plus comme on le verra ci-dessous.


    Citation Envoyé par Oishiiii Voir le message
    C'est peut-être simplement l'expérience qui permet d'obtenir une décomposition équivalente à la mienne avec moins de relvars.
    A mon sens, il s’agit d’une kolossale finesse de l’auteur de l’exercice, qui aurait tout aussi bien pu proposer les décompositions :
    ({B, C, D}, {A, E}, {A, C}) ou ({B, C, E}, {D, A}, {E, D}), etc.
    Le problème est que, contrairement à la vôtre, toutes ces décompositions violent elles aussi la 2NF et même si on en poursuit la décomposition, elles ne vont pas non plus sans perte de DF (y-compris évidemment la décomposition proposée à yaya125).

    Par contraste, votre décomposition est la bonne et convient pour les bases de données en production, tandis que les subtilités du monde académique ne sont pas forcément de mise dans ce contexte.

    Je consigne dans ce qui suit tout ce que nous avons pu dire quant à la décomposition sans perte d’information et sans perte de DF, le but étant bien sûr de produire des relvars respectant la BCNF. Oyez !

    Décomposition sans perte d’information et sans perte de DF.

    Reprenons l’exercice II.1 proposé à yaya125. Soit la relvar R dont l’en-tête est composée des attributs A, B, C, D, E :
    R {A, B, C, D, E}
    L’ensemble de DF associé (qui est irréductible) est le suivant :
    F = {{A}{E}, {C}{E}, {D}{A}, {E}{D}}
    La relvar ne comporte qu’une clé candidate : {B, C}. Elle viole la 2NF car, par exemple, le dépendant {E} de la DF {C}{E} dépend d’une partie de la clé. R doit donc subir une décomposition en relvars qui respectent la BCNF.

    1) Cas de la décomposition proposée par Oishiiii
    Ua = {B, C}
    Ub = {A, E}
    Uc = {C, E}
    Ud = {D, A}
    Ue = {E, D}
    Les relvars Ua, ..., Ue respectent la BCNF (et même la 6NF puisqu’elles ne comportent que des paires d’attributs). Montrons que cette décomposition est sans perte d’information et sans perte de DF.

    La décomposition est sans perte d’information. Pour le montrer, utilisons par exemple la méthode du tableau.

    La situation initiale est la suivante (la colonne la plus à gauche contient les relvars issues de la décomposition, chaque autre colonne contient le nom de la colonne sous forme de lettre minuscule si ce nom figure dans la relvar apparaissant dans la colonne la plus à gauche, sinon c’est sous la forme d’un nombre non encore utilisé dans le tableau) :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
                     |   A    B    C    D    E    
    -----------------|---------------------------
             {A, E}  |   a    1    2    3    e
             {C, E}  |   4    5    c    6    e
             {D, A}  |   a    7    8    d    9
             {E, D}  |  10   11   12    d    e
             {B, C}  |  13    b    c   14   15
    Utilisons les DF appartenant à F. Dans le cas de la DF {A}→{E}, comme la lettre a figure dans les lignes 1 et 3, le chiffre 9 de la ligne 3 peut être remplacé par la lettre e figurant dans la ligne 1 :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    {A}→{E}          |   A    B    C    D    E    
    -----------------|---------------------------
             {A, E}  |   a    1    2    3    e
             {C, E}  |   4    5    c    6    e
             {D, A}  |   a    7    8    d    e
             {E, D}  |  10   11   12    d    e
             {B, C}  |  13    b    c   14   15
    Avec les DF suivantes :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    {C}→{E}          |   A    B    C    D    E    
    -----------------|---------------------------
             {A, E}  |   a    1    2    3    e
             {C, E}  |   4    5    c    6    e
             {D, A}  |   a    7    8    d    e
             {E, D}  |  10   11   12    d    e
             {B, C}  |  13    b    c   14    e
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    {E}→{D}          |   A    B    C    D    E    
    -----------------|---------------------------
             {A, E}  |   a    1    2    d    e
             {C, E}  |   4    5    c    d    e
             {D, A}  |   a    7    8    d    e
             {E, D}  |  10   11   12    d    e
             {B, C}  |  13    b    c    d    e
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    {D}→{A}          |   A    B    C    D    E    
    -----------------|---------------------------
             {A, E}  |   a    1    2    d    e
             {C, E}  |   a    5    c    d    e
             {D, A}  |   a    7    8    d    e
             {E, D}  |   a   11   12    d    e
             {B, C}  |   a    b    c    d    e
    La dernière ligne ne contient que des lettres : la décomposition est sans perte d’information. A signaler que sans la présence de la relvar {B, C}, il y aurait perte d’information.

    La décomposition est aussi sans perte de DF, car chaque DF appartenant à F est présente dans la décomposition proposée par Oishiiii.

    2) Cas de la décomposition proposée à yaya125

    La décomposition proposée est la suivante : Δ = ({A, B, C}, {D, E}, {C, D}).

    Les 3 relvars {A, B, C}, {D, E}, {C, D} respectent la BCNF. La décomposition est-elle sans perte d’information et sans perte de DF ?

    Montrons que la décomposition est sans perte d’information. Pour cela, utilisons à nouveau la méthode du tableau. La situation initiale est la suivante :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
                     |   A    B    C    D    E    
    -----------------|---------------------------
          {A, B, C}  |   a    b    c    1    2
          {D, E}     |   3    4    5    d    e
          {C, D}     |   6    7    c    d    8
    Utilisons les DF appartenant à F :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    {C}→{E}          |   A    B    C    D    E    
    -----------------|---------------------------
          {A, B, C}  |   a    b    c    1    2
          {D, E}     |   3    4    5    d    e
          {C, D}     |   6    7    c    d    2
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    {E}→{D}          |   A    B    C    D    E    
    -----------------|---------------------------
          {A, B, C}  |   a    b    c    d    2
          {D, E}     |   3    4    5    d    e
          {C, D}     |   6    7    c    d    2
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    {D}→{A}          |   A    B    C    D    E    
    -----------------|---------------------------
          {A, B, C}  |   a    b    c    d    2
          {D, E}     |   a    4    5    d    e
          {C, D}     |   a    7    c    d    2
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    {A}→{E}          |   A    B    C    D    E    
    -----------------|---------------------------
          {A, B, C}  |   a    b    c    d    e
          {D, E}     |   a    4    5    d    e
          {C, D}     |   a    7    c    d    e
    La 1re ligne ne contient que des lettres : la décomposition est sans perte d’information.

    Montrons qu’il y a en revanche perte de DF.

    Utilisons à cet effet l’algorithme ad-hoc, en exploitant
    Δ = ({A, B, C}, {D, E}, {C, D})
    Cas de la DF {A}→{E}
    Exploitons {A, B, C} :
    Z = {A} (({A} {A, B, C}) {A, B, C}),
    Z = {A} ({A} {A, B, C}), et comme {A} = {A, D, E} :
    Z = {A} ({A, D, E} {A, B, C}),
    Z = {A} {A},
    Z = {A}.

    Exploitons {D, E} :
    Z = {A} (({A} {D, E}) {D, E}),
    Z = {A} {D, E}),
    Z = {A}.

    Exploitons {C, D} :
    Z = {A} (({A} {C, D}) {C, D}),
    Z = {A} {C, D}),
    Z = {A}.
    On a exploité Δ sans que le dépendant {E} de la DF {A}→{E} puisse être inclus dans Z : la DF n’est pas préservée, donc la décomposition Δ proposée n’est pas à recommander.

    Ça serait la même chose si on décomposait Δ en ({C, A}, {B, C}, {D, E}, {C, D}).

    (On montre de la même façon de la DF {D}→{A} n’est pas non plus préservée.)

    Bien sûr, l'exercice proposé à yaya125 ne portait que sur la préservation de l'information, mais j'espère, Oishiiii, que vous voilà rassuré.

    N.B. Merci de me signaler les coquilles qui pourraient traîner...
    (a) Faites simple, mais pas plus simple ! (A. Einstein)
    (b) Certes, 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 »)

    __________________________________
    Bases de données relationnelles et normalisation : de la première à la sixième forme normale
    Modéliser les données avec MySQL Workbench
    Je ne réponds pas aux questions techniques par MP. Les forums sont là pour ça.

  16. #16
    Expert éminent sénior
    Avatar de fsmrel
    Homme Profil pro
    Spécialiste en bases de données
    Inscrit en
    Septembre 2006
    Messages
    7 966
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

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

    Informations forums :
    Inscription : Septembre 2006
    Messages : 7 966
    Points : 30 778
    Points
    30 778
    Billets dans le blog
    16
    Par défaut Le feuilleton des décompositions, suite...
    Citation Envoyé par fsmrel Voir le message
    Citation Envoyé par Oishiiii Voir le message
    C'est peut-être simplement l'expérience qui permet d'obtenir une décomposition équivalente à la mienne avec moins de relvars.
    A mon sens, il s’agit d’une kolossale finesse de l’auteur de l’exercice, qui aurait tout aussi bien pu proposer les décompositions :
    ({B, C, D}, {A, E}, {A, C}) ou ({B, C, E}, {D, A}, {E, D}), etc.
    On a vu que la décomposition Δ = ({A, B, C}, {D, E}, {C, D}) est sans perte d’information, mais avec perte de DF, alors que la décomposition que vous proposez est meilleure puisqu'elle préserve les DF.

    Votre décomposition comporte cinq relvars alors que l’autre n’en comporte certes que trois, mais au prix d'un viol de BCNF (en fait de 2NF), ce qui revient à dire que le processus de décomposition doit être poursuivi, en sorte que l’on passe de :
    Δ = ({A, B, C}, {D, E}, {C, D})
    à :
    Δ’ = ({C, A}, {B, C}, {D, E}, {C, D})
    Les relvars composant Δ’ respectent cette fois-ci la BCNF (et même la 6NF), mais la décomposition ne préserve pas les DF. Existe-t-il quand même des décompositions qui respectent la BCNF, qui soient sans perte d’information et de DF et comportent moins de relvars que la vôtre ?

    Remettons les compteurs à zéro. Les conditions initiales de température et de pression sont toujours les mêmes. L’en-tête de la relvar R est composé des attributs A, B, C, D, E :
    R {A, B, C, D, E}
    L’ensemble de DF associé (qui est irréductible) est le suivant :
    F = {{A}{E}, {C}{E}, {D}{A}, {E}{D}}
    La relvar R ne comporte qu’une clé candidate : {B, C}. Elle viole la 2NF car, par exemple, le dépendant {E} de la DF {C}{E} dépend d’une partie de la clé. R doit donc subir une décomposition en relvars respectant la BCNF.

    Votre propre décomposition est maximale, en ce sens qu'elle ne contient que des relvars binaires :
    ΔOishiiii = ({B, C}, {A, E}, {C, E}, {D, A}, {E, D})
    Si vous voulez une décomposition comportant moins de relvars, il faut y effectuer des jointures qui préservent la BCNF.

    Effectuons par exemple la jointure naturelle {D, A} JOIN {E, D} pour produire la relvar {A, E, D} et permettant de réduire ΔOishiiii à :
    ΔOishiii’= ({B, C}, {A, E}, {C, E}, {A, E, D}).
    Mais la relvar ternaire {A, E, D} respecte-t-elle la BCNF ?

    Avant de répondre à cette question, mettons en évidence un ensemble G qui soit un sous-ensemble de la fermeture F+ de F (avec G+ = F+), limité aux DF non triviales et non réductibles. G présente l’avantage de ne pas être aussi étriqué que F et permet ainsi d’élargir le champ des recherches des décompositions.

    Le calcul de G passe par le calcul de la fermeture des attributs de R, à savoir A+, B+, C+, D+, E+. Ainsi :

    • {A}+ = {A, D, E}, ce qui permet de découvrir la DF non triviale et non réductible {A}{D}.
    • {B}+ = {B}, ce qui ne nous apporte rien d’intéressant.
    • {C}+ = {A, C, D, E}, ce qui permet de découvrir les DF {C}{A} et {C}{D}.
    • {D}+ = {A, D, E}, ce qui permet de découvrir la DF {D}{E}.
    • {E}+ = {A, D, E}, ce qui permet de découvrir la DF {E}{A}.

    Au final, G est égal à F augmenté des DF que l’on vient de mettre en évidence :
    G = {{A}{E}, {C}{E}, {D}{A}, {E}{D}, {A}{D}, {C}{A}, {C}{D}, {D}{E}, {E}{A}}

    On peut maintenant répondre positivement à la question : la relvar {A, E, D} respecte-t-elle la BCNF ?
    En effet, {A}, {E} et {D} sont clés candidates pour {A, E, D} puisque selon G (et en tenant compte des DF triviales {A}{A}, {D}{D}, {E}{E}) :
    {A}{A, E, D},
    {E}{A, E, D},
    {D}{A, E, D}.

    En conséquence, la jointure naturelle {D, A} JOIN {E, D} produit la relvar {A, E, D} respectant la BCNF, ce qui fait que ΔOishiiii peut être effectivement réduite à quatre relvars :
    ΔOishiiii’ = ({B, C}, {A, E}, {C, E}, {A, E, D})
    Mais {A, E} n’est qu’une projection de {A, E, D} sur les attributs A et E et la décomposition peut être réduite à trois relvars :
    Δe = ({B, C}, {C, E}, {A, E, D})
    Les relvars {B, C}, {C, E}, {A, E, D} respectent la BCNF. Elles sont aussi sans perte d’information et sans perte de DF (je vous laisse le soin de le vérifier). On vérifie facilement que la décomposition Δe ne peut pas être réduite à deux relvars, mais en revanche il existe d’autres décompositions réduites à trois relvars que l'on peut chercher découvrir.

    Remettons donc encore une fois les compteurs à zéro...
    Soit la relvar R dont l’en-tête est composé des attributs A, B, C, D, E :
    R {A, B, C, D, E}
    L’ensemble de DF associé (réductible) est le suivant :
    G = {{A}{E}, {C}{E}, {D}{A}, {E}{D}, {A}{D}, {C}{A}, {C}{D}, {D}{E}, {E}{A}}
    La relvar ne comporte qu’une clé candidate : {B, C}.

    Puisque {E}{A} et {E}{D} appartiennent à G, par application de la règle d’union on infère {E}{A, D}. En vertu du théorème de Heath, R {A, B, C, D, E} est décomposable selon :
    R1 {A, E, D} et R2 {E, B, C}.
    Et comme {C}{E} appartient à G, R2 est décomposable à son tour selon :
    R21 {C, E} et R22 {B, C}.
    On retrouve ainsi la décomposition :
    Δe = ({A, E, D}, {C, E}, {B, C}).
    Mais il existe d’autres décompositions du même tonneau.

    Puisque {A}{E} et {A}{D} appartiennent à G, par application de la règle d’union on infère {A}{E, D}. En vertu du théorème de Heath, R {A, B, C, D, E} est décomposable selon :
    R1’ {A, E, D} et R2’ {A, B, C}.
    Et comme {C}{A} appartient à G, R2’ est décomposable à son tour selon :
    R21’ {C, A} et R22’ {B, C}.
    On obtient ainsi la décomposition :
    Δa = ({A, E, D}, {C, A}, {B, C}).
    Puisque {D}{E} et {D}{A} appartiennent à G, par application de la règle d’union on infère {D}{A, E}. En vertu du théorème de Heath, R {A, B, C, D, E} est décomposable selon :
    R1’’ {A, E, D} et R2’’ {D, B, C}.
    Et comme {C}{D} appartient à G, R2’’ est décomposable à son tour selon :
    R21’’ {C, D} et R22’’ {B, C}.
    On obtient ainsi la décomposition :
    Δd = ({A, E, D}, {C, D}, {B, C}).
    Ainsi, on a mis en évidence trois décompositions minimales, Δa, Δd et Δe composées chacune de trois relvars respectant la BCNF, préservant l’information (on a utilisé exclusivement le théorème de Heath pour produire les décompositions) et préservant les DF. A titre d'exemple, montrons que Δd préserve les DF (je vous laisse le soin d’en faire autant pour Δa et Δe).

    Pour cela, on dispose de :
    Δd = ({A, E, D}, {C, D}, {B, C})
    F = {{A}{E}, {C}{E}, {D}{A}, {E}{D}}
    Toutes les DF appartenant à F doivent être préservées (si elles le sont, celles de G le sont aussi, puisqu’inférées de celles de F).

    Test de la préservation de la DF {A}{E}.
    Exploitons le 1er élément de Δd, à savoir {A, E, D} :
    Z = {A} (({A} {A, E, D})+ {A, E, D}),
    Z = {A} ({A}+ {A, E, D}), et comme {A}+ = {A, E, D} :
    Z = {A} ({A, E, D} {A, E, D}),
    Z = {A} {A, E, D},
    Z = {A, E, D}.
    Le dépendant {E} de la DF {A}{E} est inclus dans Z : la DF est préservée.

    Test de la préservation de la DF {C}{E}.
    Exploitons l’élément {C, D} de Δd :
    Z = {C} (({C} {C, D})+ {C, D}),
    Z = {C} ({C}+ {C, D}), et comme {C}+ = {A, C, D, E} :
    Z = {C} ({A, C, D, E} {C, D}),
    Z = {C} {C, D},
    Z = {C, D}.

    Poursuivons avec l’élément {A, E, D} de Δ :
    Z = {C, D} (({C, D} {A, E, D})+ {A, E, D}),
    Z = {C, D} ({D}+ {A, E, D}, et comme {D}+ = {A, E, D} :
    Z = {C, D} ({A, E, D} {A, E, D}),
    Z = {C, D} {A, E, D},
    Z = {C, D, A, E}.
    Le dépendant {E} de la DF {C}{E} est inclus dans Z : la DF est préservée.

    Test de la préservation de la DF {D}{A}.
    Exploitons l’élément {A, E, D} de Δ :
    Z = {D} (({D} {A, E, D})+ {A, E, D}),
    Z = {D} ({D}+ {A, E, D}), et comme {D}+ = {A, E, D} :
    Z = {D} ({A, E, D} {A, E, D}),
    Z = {A, E, D}.
    Le dépendant {A} de la DF {D}{A} est inclus dans Z : la DF est préservée.

    Test de la préservation de la DF {E}{D}.
    Exploitons l’élément {A, E, D} de Δ :
    Z = {E} (({E} {A, E, D})+ {A, E, D}),
    Z = {E} ({E}+ {A, E, D}), et comme {E}+ = {A, E, D} :
    Z = {E} ({A, E, D} {A, E, D}),
    Z = {E} {A, E, D},
    Z = {A, E, D}.
    Le dépendant {D} de la DF {E}{D} est inclus dans Z : la DF est préservée.

    =>

    Toutes les DF appartenant à F sont préservées, la décomposition Δd = ({A, E, D}, {C, D}, {B, C}) est donc sans perte de DF.

    Maintenant, lorsque sur le terrain on a plus de mille relvars telles que R à vérifier quant au respect de la BCNF, avec des contraintes de délai, on n’a pas trop le temps de rechercher la meilleure décomposition, et si la vôtre n’est pas sur la plus haute marche du podium, elle est néanmoins valide et donc acceptable, contrairement à la décomposition Δ de l’exercice proposé à yaya125. Reconnaissons que le but de cet exercice était seulement de démontrer que Δ est sans perte d’information. Le risque eut été d’en conclure que Δ était valide au plan de la normalisation et de la préservation des DF.

    N.B.
    F = {{A}{E}, {C}{E}, {D}{A}, {E}{D}} constitue un ensemble irréductible de DF (couverture minimale) pour la relvar R {A, B, C, D, E}, mais ça n'est pas le seul. Partant de G, on découvre bien sûr F, mais aussi les ensembles irréductibles suivants :
    F2 = {{A}{E}, {C}{D}, {D}{A}, {E}{D}}
    F3 = {{A}{D}, {C}{A}, {D}{E}, {E}{A}}
    F4 = {{A}{D}, {C}{D}, {D}{E}, {E}{A}}
    Si le coeur vous en dit, je vous laisse le soin de compléter la liste...
    (a) Faites simple, mais pas plus simple ! (A. Einstein)
    (b) Certes, 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 »)

    __________________________________
    Bases de données relationnelles et normalisation : de la première à la sixième forme normale
    Modéliser les données avec MySQL Workbench
    Je ne réponds pas aux questions techniques par MP. Les forums sont là pour ça.

  17. #17
    Membre éprouvé Avatar de Oishiiii
    Homme Profil pro
    Administrateur de base de données
    Inscrit en
    Août 2009
    Messages
    508
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Ain (Rhône Alpes)

    Informations professionnelles :
    Activité : Administrateur de base de données

    Informations forums :
    Inscription : Août 2009
    Messages : 508
    Points : 1 104
    Points
    1 104
    Par défaut
    Merci fsmrel pour toutes ces informations et explications très intéressantes et utiles.

    Vous faites la distinction entre les concepts de décompositions sans perte d'information et décomposition sans perte de dépendances et j'ai peur de m'emmêler les pinceaux.

    La décomposition d'une relvar en plusieurs autres relvars (projections) doit être réversible.
    On doit retrouver la relvar initiale en utilisant l'opérateur de jointure naturelle sur ses projections.
    L'utilisation des dépendances fonctionnelles est indispensable pour effectuer une décomposition correctement puisque se sont les règles de gestions, ce sont elles qui donnent un sens à la relvar.

    Finalement le concept de décomposition sans perte d'information sert uniquement à s'assurer que l'opération de jointure permettra d'obtenir une relation dont l'en-tête est strictement identique à celui de la relvar faisant l'objet de la décomposition, ou y-a-t'il d'autres subtilités ?

    Pour revenir sur l'exercice, voici ma copie :

    Citation Envoyé par fsmrel Voir le message
    la décomposition peut être réduite à trois relvars :
    Δe = ({B, C}, {C, E}, {A, E, D})
    Les relvars {B, C}, {C, E}, {A, E, D} respectent la BCNF. Elles sont aussi sans perte d’information et sans perte de DF (je vous laisse le soin de le vérifier).
    Pour vérifier que la décomposition Δe est bien sans perte de dépendances j'ai utilisé l’algorithme que vous nous avez décrit.

    J'utilise toujours l'ensemble de DF suivant:
    F = { {A}{E}, {C}{E}, {D}{A}, {E}{D} }

    Première DF, {A}{E}
    J'exploite l’élément {A, D, E} de Δe :
    Z = {A} (({A} {A, D, E})+ {A, D, E}),
    Z = {A} ({A}+ {A, D, E}), et comme {A}+ = {A, D, E} :
    Z = {A} ({A, D, E} {A, D, E}),
    Z = {A} {A, D, E},
    Z = {A, D, E}.

    Le dépendant {E} de la DF {A}{E} est inclus dans Z : la DF est préservée.
    Seconde DF, {C}{E}
    J'exploite {C, E} :
    Z = {C} (({C} {C, E})+ {C, E}),
    Z = {C} ({C}+ {C, E}), et comme {C}+ = {A, C, D, E} :
    Z = {C} ({A, C, D, E} {C, E}),
    Z = {C} {C, E},
    Z = {C, E}.

    Le dépendant {E} de la DF {C}{E} est inclus dans Z : la DF est préservée.
    Troisième DF, {D}{A}
    J'exploite {A, D, E} :
    Z = {D} (({D} {A, D, E})+ {A, D, E}),
    Z = {D} ({D}+ {A, D, E}), et comme {D}+ = {A, D, E} :
    Z = {D} ({A, D, E} {A, D, E}),
    Z = {D} {A, D, E},
    Z = {A, D, E}.

    Le dépendant {A} de la DF {D}{A} est inclus dans Z : la DF est préservée.
    Dernière DF, {E}{D}
    J'exploite {A, D, E} :
    Z = {E} (({E} {A, D, E})+ {A, D, E}),
    Z = {E} ({E}+ {A, D, E}), et comme {E}+ = {A, D, E} :
    Z = {E} ({A, D, E} {A, D, E}),
    Z = {A, D, E}.

    Le dépendant {D} de la DF {E}{D} est inclus dans Z : la DF est préservée.
    Toutes les DF de F sont préservées, la décomposition Δe est sans perte de dépendances.


    Citation Envoyé par fsmrel Voir le message
    N.B.
    F = {{A}{E}, {C}{E}, {D}{A}, {E}{D}} constitue un ensemble irréductible de DF (couverture minimale) pour la relvar R {A, B, C, D, E}, mais ça n'est pas le seul. Partant de G, on découvre bien sûr F, mais aussi les ensembles irréductibles suivants :
    F2 = {{A}{E}, {C}{D}, {D}{A}, {E}{D}}
    F3 = {{A}{D}, {C}{A}, {D}{E}, {E}{A}}
    F4 = {{A}{D}, {C}{D}, {D}{E}, {E}{A}}
    Si le coeur vous en dit, je vous laisse le soin de compléter la liste...
    Il ne manque que deux nouveaux ensembles pour compléter la liste :
    F1 = {{A}{E}, {C}{E}, {D}{A}, {E}{D}}
    F2 = {{A}{E}, {C}{D}, {D}{A}, {E}{D}}
    F3 = {{A}{D}, {C}{A}, {D}{E}, {E}{A}}
    F4 = {{A}{D}, {C}{D}, {D}{E}, {E}{A}}
    F5 = {{A}{D}, {C}{E}, {D}{E}, {E}{A}}
    F6 = {{A}{E}, {C}{A}, {D}{A}, {E}{D}}

  18. #18
    Expert éminent sénior
    Avatar de fsmrel
    Homme Profil pro
    Spécialiste en bases de données
    Inscrit en
    Septembre 2006
    Messages
    7 966
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

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

    Informations forums :
    Inscription : Septembre 2006
    Messages : 7 966
    Points : 30 778
    Points
    30 778
    Billets dans le blog
    16
    Par défaut
    Bonsoir,


    Citation Envoyé par Oishiiii Voir le message
    La décomposition d'une relvar en plusieurs autres relvars (projections) doit être réversible.
    On doit retrouver la relvar initiale en utilisant l'opérateur de jointure naturelle sur ses projections.
    Exact. C’est ce que les camarades Date, Ullman et consorts, appellent une nonloss decomposition, une décomposition sans perte d’information (que j’abrège souvent en décomposition sans perte, pour faire comme eux). Mais, par référence à ce que vous écrivez :
    « le concept de décomposition sans perte d'information sert uniquement à s'assurer que l'opération de jointure permettra d'obtenir une relation dont l'en-tête est strictement identique à celui de la relvar faisant l'objet de la décomposition, ou y-a-t'il d'autres subtilités ? »
    Je me rends compte que je ferais mieux de parler de décomposition sans perte de contenu (à l’instar de Delobel et Adiba, qui mettent les points sur les i en parlant plus précisément de préservation du contenu de la base de données).

    Considérons par exemple la relvar R {A, B, C, D} avec F = {{A}→{B}, {C}→{D}}.

    Si on décompose R en R1 {A, B} et R2 {C, D}, c'est-à-dire sans tenir compte du théorème de Heath, l'opération R1 JOIN R2 produit une relvar dont l'en-tête {A, B, C, D} est exactement celui de R, mais le contenu de la base de données n’est pas préservé (on a plutôt effectué l’opération R1 TIMES R2, car la jointure dégénère en produit quand le nombre d’attributs participant à la jointure est égal à 0). Par référence à mon message du 21 juin dernier, vous pouvez aussi vous en assurer en observant que les DF (R1 R2) → (R1 — R2) et (R1 R2) → (R2 — R1) n’appartiennent ni l’une ni l’autre à F+.

    Prenons maintenant l’exemple de la relvar suivante : R {A, B, C} avec F = {{A, B}→{C}, {C}→{B}} et appliquons sagement le théorème de Heath : R est décomposable en R1 {B, C} et R2 {A, C} et cette décomposition préserve le contenu de la base de données. Vous pouvez aussi vous en assurer en observant que, par rapport à F+, (R1 R2) → (R1 — R2)).
    En revanche, vous pouvez vérifier que cette décomposition ne préserve malheureusement pas la dépendance fonctionnelle {A, B}→{C}, d’où le dilemme : soit on décompose et on perd une règle de gestion (avec des assertions ou des triggers SQL en perspective pour pallier), soit on ne décompose pas mais la BCNF est alors violée (toujours avec des assertions ou des triggers en perspective pour garantir les redondances...)

    Si vous avez encore peur de vous emmêler les pinceaux ou si vous avez des angoisses métaphysiques, n’hésitez pas à poser des questions.


    Citation Envoyé par Oishiiii Voir le message
    Pour revenir sur l'exercice, voici ma copie
    Pour citer Jean (in Les tontons flingueurs) : vingt sur vingt, et en cotant vache...
    (Mais un lecteur attentif et patient fera peut-être mieux, auquel cas il aura droit à au moins un point de plus que nous...)
    (a) Faites simple, mais pas plus simple ! (A. Einstein)
    (b) Certes, 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 »)

    __________________________________
    Bases de données relationnelles et normalisation : de la première à la sixième forme normale
    Modéliser les données avec MySQL Workbench
    Je ne réponds pas aux questions techniques par MP. Les forums sont là pour ça.

  19. #19
    Membre éprouvé Avatar de Oishiiii
    Homme Profil pro
    Administrateur de base de données
    Inscrit en
    Août 2009
    Messages
    508
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Ain (Rhône Alpes)

    Informations professionnelles :
    Activité : Administrateur de base de données

    Informations forums :
    Inscription : Août 2009
    Messages : 508
    Points : 1 104
    Points
    1 104
    Par défaut
    Bonjour,

    Citation Envoyé par fsmrel Voir le message
    Considérons par exemple la relvar R {A, B, C, D} avec F = {{A}→{B}, {C}→{D}}.

    Si on décompose R en R1 {A, B} et R2 {C, D}, c'est-à-dire sans tenir compte du théorème de Heath, l'opération R1 JOIN R2 produit une relvar dont l'en-tête {A, B, C, D} est exactement celui de R, mais le contenu de la base de données n’est pas préservé (on a plutôt effectué l’opération R1 TIMES R2, car la jointure dégénère en produit quand le nombre d’attributs participant à la jointure est égal à 0). Par référence à mon message du 21 juin dernier, vous pouvez aussi vous en assurer en observant que les DF (R1 R2) → (R1 — R2) et (R1 R2) → (R2 — R1) n’appartiennent ni l’une ni l’autre à F+.
    Je pensait que la préservation des dépendances impliquait forcément la préservation de l'information/du contenu mais ce n'est pas le cas, on le voit très bien dans cet exemple.

    Citation Envoyé par fsmrel Voir le message
    Prenons maintenant l’exemple de la relvar suivante : R {A, B, C} avec F = {{A, B}→{C}, {C}→{B}} et appliquons sagement le théorème de Heath : R est décomposable en R1 {B, C} et R2 {A, C} et cette décomposition préserve le contenu de la base de données. Vous pouvez aussi vous en assurer en observant que, par rapport à F+, (R1 R2) → (R1 — R2)).
    En revanche, vous pouvez vérifier que cette décomposition ne préserve malheureusement pas la dépendance fonctionnelle {A, B}→{C}, d’où le dilemme : soit on décompose et on perd une règle de gestion (avec des assertions ou des triggers SQL en perspective pour pallier), soit on ne décompose pas mais la BCNF est alors violée (toujours avec des assertions ou des triggers en perspective pour garantir les redondances...)
    C'est donc ça le fameux problème de la BCNF. C'est facile à comprendre lorsqu'on a toutes les clés

    Et bien merci encore, il n'y a plus aucune zone d'ombre, c'est très clair.
    A bientôt pour le prochain épisode

Discussions similaires

  1. problème de relations
    Par dolphin96 dans le forum Access
    Réponses: 3
    Dernier message: 23/07/2006, 23h24
  2. Problème de relation double
    Par Rub-n dans le forum Access
    Réponses: 1
    Dernier message: 31/05/2006, 19h07
  3. Problème de relation entre deux tables + autre chose
    Par Goth_sensei dans le forum Langage SQL
    Réponses: 7
    Dernier message: 30/03/2006, 21h49
  4. [conception] Requête de sélection problèmes de relations
    Par snoopy69 dans le forum Modélisation
    Réponses: 26
    Dernier message: 08/11/2005, 15h23
  5. Gestion club sportif (problème de relations )
    Par jemaflo dans le forum Access
    Réponses: 3
    Dernier message: 04/10/2005, 00h00

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo