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 :

Calcul d'une couverture minimale [DF]


Sujet :

Schéma

  1. #1
    Membre régulier
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    123
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 123
    Points : 85
    Points
    85
    Par défaut Calcul d'une couverture minimale
    Bonjour

    Je cherche à calculer la couverture minimale d'un ensemble de dépendances fonctionnelles.
    Notre professeur nous a donné l'algorithme suivant:

    1 Transformer les df de F en df canoniques.
    2 Transformer les df de F en df élémentaires.
    3 Suppression des df redondantes.

    Si la première et la dernière étape ne me posent pas trop de problèmes je galère bien sur la seconde. Les différents courts sur le net sont plus théorique que pratique

    Si je prend l'exemple suivant:

    F={A->C, ABC-> DE, EDC->AB, ABE-> CD, D->ACE}

    J'obtiens comme couverture canonique
    A->C, ABC->D, ABC->E, EDC->A, EDC->B, ABE-> C, ABE-> D, D->A, D->C, D->E

    Mais je n'arrive pas et ne vois pas comment calculer la couverture de df élémentaires:

    Si quelqu'un pouvait me donner l'algorithme en français si possible illustré avec un exemple je lui en serait très reconnaissant

  2. #2
    Membre actif Avatar de SmileSoft
    Inscrit en
    Mars 2008
    Messages
    436
    Détails du profil
    Informations forums :
    Inscription : Mars 2008
    Messages : 436
    Points : 214
    Points
    214
    Par défaut
    Citation Envoyé par Anonymouse Voir le message

    Si quelqu'un pouvait me donner l'algorithme en français si possible illustré avec un exemple je lui en serait très reconnaissant
    dans un ensemble de dépendances fonctionnelles DF, il se peut qu'un certain nombre de ces dépendances se déduisent d'autres dépendances par application des propriétés des dépendances fonctionnelles. si on élimine toutes ces dépendances fonctionnelles on obtient un ensemble minimal de DF, cette ensemble est appelé couverture minimale des dépendances fonctionnelles

    exemple
    soit l'ensemble de DF: {A->B, B->C,A->C}, alors l'ensemble DF1:{A->B, B->C} forme une couverture minimale car aucune dépendance fonctionnelle n'est déductible de l'autre.

    d'un point de vue pratique, la couverture minimale nous servira dans la décomposition des relations sans perte d'information.
    Un thésard a souvent un problème de motivation jusqu'au moment où il aura un problème de temps....

  3. #3
    Membre régulier
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    123
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 123
    Points : 85
    Points
    85
    Par défaut
    Citation Envoyé par SmileSoft Voir le message
    dans un ensemble de dépendances fonctionnelles DF, il se peut qu'un certain nombre de ces dépendances se déduisent d'autres dépendances par application des propriétés des dépendances fonctionnelles. si on élimine toutes ces dépendances fonctionnelles on obtient un ensemble minimal de DF, cette ensemble est appelé couverture minimale des dépendances fonctionnelles

    exemple
    soit l'ensemble de DF: {A->B, B->C,A->C}, alors l'ensemble DF1:{A->B, B->C} forme une couverture minimale car aucune dépendance fonctionnelle n'est déductible de l'autre.

    d'un point de vue pratique, la couverture minimale nous servira dans la décomposition des relations sans perte d'information.
    Le problème est dans l'application des propriétés. Sur l'exemple que tu me donne on voit rapidement quels sont les données superflues. Comment fait on sur un ensemble plus complexe? Le prof nous a donné un algo mais je ne le comprend pas:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
      Transformer les df de F en df élémentaires.
      ∀f ∈ F , f = X → A, X = {X1 , . . . Xn }
         ∀i ∈ [1, n]
              Si F ∼ (F − {f } ∪ {(X − {Xi }) → A})
              Alors f est remplacée par (X − {Xi }) → A

  4. #4
    Membre actif Avatar de SmileSoft
    Inscrit en
    Mars 2008
    Messages
    436
    Détails du profil
    Informations forums :
    Inscription : Mars 2008
    Messages : 436
    Points : 214
    Points
    214
    Par défaut
    Citation Envoyé par Anonymouse Voir le message
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
      Transformer les df de F en df élémentaires.
      ∀f ∈ F , f = X → A, X = {X1 , . . . Xn }
         ∀i ∈ [1, n]
              Si F ∼ (F − {f } ∪ {(X − {Xi }) → A})
              Alors f est remplacée par (X − {Xi }) → A
    Transformer les df de F en df élémentaires, veut dire que l'attribut situé à droite de la flèche de la dépendance fonctionnelle doit dépendre entièrement de l'attribut/les attribut situant à gauche
    exemple:
    Num-Etudiant,Num-Module→ Nom-Etudiant
    n'est pas élémentaire car seul Num-Etudiant qui détermine le Nom-Etudiant
    transformation:
    Num-Etudiant→ Nom-Etudiant
    par contre
    Num-Etudiant,Num-Module→ note
    est bien une DF élémentaire.
    Un thésard a souvent un problème de motivation jusqu'au moment où il aura un problème de temps....

  5. #5
    Expert éminent sénior
    Avatar de fsmrel
    Homme Profil pro
    Spécialiste en bases de données
    Inscrit en
    Septembre 2006
    Messages
    7 965
    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 965
    Points : 30 777
    Points
    30 777
    Billets dans le blog
    16
    Par défaut Armstrong or not Armstrong
    Bonsoir,


    Citation Envoyé par Anonymouse Voir le message

    Si je prends l'exemple suivant:
    F={A->C, ABC-> DE, EDC->AB, ABE-> CD, D->ACE}
    J'obtiens comme couverture canonique
    A->C, ABC->D, ABC->E, EDC->A, EDC->B, ABE-> C, ABE-> D, D->A, D->C, D->E
    Mais je n'arrive pas et ne vois pas comment calculer la couverture de df élémentaires:
    Si quelqu'un pouvait me donner l'algorithme en français si possible illustré avec un exemple je lui en serais très reconnaissant
    Disons que l’on cherche à simplifier au maximum l’ensemble donné de DF. Cet ensemble est le suivant :
    DF01 : A → C
    DF02 : ABC → D
    DF03 : ABC → E
    DF04 : EDC → A
    DF05 : EDC → B
    DF06 : ABE → C
    DF07 : ABE → D
    DF08 : D → A
    DF09 : D → C
    DF10 : D → E
    Le but de la manœuvre consiste à chercher quelles DF peuvent disparaître car inférées d’autres DF, et vérifier à défaut si les déterminants multi-attributs de degré N peuvent être réduits à des dépendants de degré N-1, N-2, etc. (réduction qui vaudrait pour les déterminants ABC (DF02 et DF03), EDC (DF04 et DF05) et ABE (DF06 et DF07).
    On peut pour cela utiliser les règles définies correspondant aux axiomes d’Armstrong et qui en sont inférées :
    1. Réflexivité : si B est un sous-ensemble (non strict) de A, alors A → B.
    2. Augmentation : si A → B, alors AC → BC
    3. Transitivité : si A → B et B → C alors A → C
    4. Décomposition : si A → BC, alors A → B et A → C
    5. Union : si A → B et A → C, alors A → BC
    6. Pseudo-transitivité : si A → B et BC → D, alors AC → D
    7. Composition : si A → B et C → D, alors AC → BD
    Les auteurs varient dans la présentation des règles. Ainsi, la règle d’augmentation ci-dessus est celle qu’utilisent par exemple Chris Date, Jef Ullman et Georges Gardarin.
    Ces règles ne vous sont pas étrangères, puisque pour produire DF02 et DF03, vous avez utilisé la règle de décomposition à partir de la dépendance fonctionnelle donnée initialement ABC→ DE.

    En vertu de ces règles :

    DF03 peut disparaître.
    En effet, ABC → D (DF02) et D → E (DF10), donc par transitivité, ABC → E.

    DF04 peut disparaître.
    En effet, D → A (DF08), par augmentation DEC → AEC et par décomposition, DEC → A.

    DF06 peut disparaître.
    En effet, A → C (DF01), par augmentation ABE → CBE et par décomposition, ABE → C.

    DF09 peut disparaître.
    En effet, D → A (DF08) et A → C (DF01), donc par transitivité, D → C.

    DF07 peut disparaître.
    En effet, A → C (DF01). Par augmentation A → AC. Par augmentation ABE → ACBE.
    Par décomposition ABE → ABC. Comme ABC → D (DF02), par transitivité ABE → D.

    Je vous laisse le soin de vérifier si le reliquat DF01, DF02, DF05, DF08, DF10 est réductible ou bien constitue une couverture minimale.

    Maintenant, vous évoquez un algorithme qui est indéchiffrable, vu que certains symboles importants ont été remplacés par des carrés.
    Peu importe. Il existe un algorithme qui permet de produire la fermeture d’un ensemble d’attributs, dont j’ai fourni une présentation très informelle à Boubou382002
    L’intérêt de cet algorithme, décrit par exemple par Chris Date dans An Introduction to Database Systems, est qu’il permet d’éviter de jongler avec les axiomes d’Armstrong.

    Ainsi, on va supposer que l’on ne dispose pas de DF03, dont le déterminant est ABC. Intéressons-nous donc à la fermeture ABC+ de ABC. Du fait de DF02, on peut amorcer ainsi la pompe :
    ABC+ = [ A B C _ _ ]
    Les caractères "_" attendant d’être remplacés par D et E quand c’est possible, c'est-à-dire quand D et E jouent le rôle de dépendants dans des DF connues. Par exemple, on dispose de DF02 : ABC → D. Parce que ABC fait partie de ABC+, D est captable et la fermeture peut être enrichie :
    ABC+ = [ A B C D _ ]
    E peut être capté parce que d’après DF10 : D → E d’une part, et le déterminant D appartient à ABC+ d'autre part :
    ABC+ = [ A B C D E ]
    En passant, je cite et traduis Chris Date :
    « Un corollaire important est le suivant : étant donné un ensemble S de DF, on peut facilement dire si une DF spécifique X → Y procède de S. En effet, cette DF procèdera de S si et seulement si Y est un sous-ensemble de la fermeture X+ de X selon S. En d’autres termes, nous disposons désormais d’un moyen simple pour déterminer si une DF donnée X → Y appartient à la fermeture S+ de S, sans avoir réellement à calculer S+. »
    Par conséquent, pour en revenir a ABC+, comme E en fait partie, on infère la DF : ABC → E c'est-à-dire que DF03 peut disparaître et ne pas faire partie de la couverture minimale.

    Prenons le cas de DF04, dont le déterminant est EDC. Amorçons la pompe :
    EDC+ = [ _ _ C D E _ ]
    D appartient à EDC+ et c’est le déterminant de DF08 : D → A, donc A peut être capturé :
    EDC+ = [ A _ C D E _ ]
    Donc EDC → A, en vertu de quoi DF04 peut disparaître et ne pas faire partie de la couverture minimale.

    Etc. Je vous laisse le soin de poursuivre.
    (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.

  6. #6
    Membre régulier
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    123
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 123
    Points : 85
    Points
    85
    Par défaut
    Bonsoirs

    Merci pour cette réponse détaillée. Je pense avoir compris puisque j'ai réussit à faire mes exos.

    Pour l'algo ça doit être un problème d'encodage car moi je le vois parfaitement bien mais je suis sous linux.

    Je note précieusement cette page pleine d'informations

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

Discussions similaires

  1. calcul de couverture minimale
    Par Invité dans le forum Schéma
    Réponses: 4
    Dernier message: 23/12/2013, 22h08
  2. [Normalisation] Calcul d'une couverture minimale
    Par redsaint0 dans le forum Schéma
    Réponses: 8
    Dernier message: 09/02/2010, 15h13
  3. [DF]Clefs candidates d'une couverture minimale
    Par wang_xue dans le forum Schéma
    Réponses: 19
    Dernier message: 17/10/2007, 00h45
  4. Recuperer un champ calculé dans une variable....
    Par vijeo dans le forum MS SQL Server
    Réponses: 4
    Dernier message: 21/12/2004, 15h57
  5. calcul dans une requête
    Par blaz dans le forum Langage SQL
    Réponses: 8
    Dernier message: 22/12/2003, 11h31

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