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 :cry:
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 :D
Armstrong or not Armstrong
Bonsoir,
Citation:
Envoyé par
Anonymouse
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.
