Discussion :

[lou93]

Bonjour,

voici un sujet d'examen de Base de données , qui date de 3 ans.
Tout n'est pas clair, peut on m'expliquer les notions vues dans cet exercice et comment le résoudre?

Soit le schéma R(A,B,C,D,E) et l'ensemble de dépendances fonctionnelles : F={A-->D,E ; C,E,D-->B; D-->E; B-->E ; C,E-->D; C,D-->B}

1) Quelle est la fermeture [A,B]_F⁺? quelle est la clé de la relation R?
qu'est ce qu'une fermeture? quand on demande la clé, c'est la clé primaire?

2)Minimiser F, c'est à dire trouver un ensemble de dépendances fonctionnelles minimal équivalent à F

3)On se propose de décomposer la relation R en 6 relations:
R1(A,C) , R2(B,E), R3(A,E) , R4 (C,E,D) , R5(C,D,B) . Rappelez la condition pour qu'une décomposition soit sans perte d'informations. La décomposition proposée est elle sans perte d'information? justifiez.

4)Donner une décomposition légèrement différente qui soit à la fois sans perte et en 3ème forme normale.

Merci d'avance!

[bstevy]

C'est ultra théorique tout ca
Ca fait une éternité que j'avais pas vu ce genre de problème. Je sais même pas si c'est encore enseigné comme cela.

Bref, c'est un peu loin pour moi, mais je t'ai trouvé un cours :
http://pageperso.lif.univ-mrs.fr/~vi...Papers/DF1.pdf

J'espère que ca te sera suffisant.

[fsmrel]

Bonsoir lou93,

Quelle est la fermeture [A,B]_F⁺ ?

Une fermeture est un ensemble : dans votre cas, c'est l’ensemble des noms des attributs qui participent à chaque dépendance fonctionnelle dans laquelle la paire {A, B} joue le rôle de déterminant. Par exemple, les dépendances fonctionnelles {A, B} -> {A} et {A, B} -> {B} sont triviales, donc A et B sont éléments de la fermeture que vous proposez. Comme A appartient à la fermeture, et qu’il existe la dépendance fonctionnelle {A} -> {D, E}, par application de la règle de transitivité, D et E intègrent la fermeture. Je vous laisse poursuivre le travail, réalisable facilement à l’aide de l’algorithme du seau à dépendants.

N.B. Comme une fermeture est un ensemble, j’utilise plutôt des accolades que des crochets : {A, B} plutôt que [A, B], mais faites comme on vous a montré.

quand on demande la clé, c'est la clé primaire?

Dans le cadre de la théorie relationnelle, il y a des clés candidates (clés pour abréger).
La clé primaire (concept obsolète dans le cadre théorique et qui ne perdure qu’en Sorry Query Language) n’est qu’un cas particulier de la clé candidate, disons qu’elle est « plus égale » que les autres, pour des raisons qui relèvent plus de la psychologie que des mathématiques.

Une clé est un ensemble irréductible [de noms] d’attributs dont la fermeture est égale à {A, B, C, D, E}. Déterminer l’ensemble des clés candidates est en général un peu long, mais il faut s’y atteler, par exemple comme ici. Notez que si un attribut n’appartient à aucun dépendant, il appartient nécessairement à chaque clé. Ça tombe bien pour votre exercice, car cela s'y produit, ce qui permet de réduire singulièrement la durée de la recherche...

Minimiser F, c'est à dire trouver un ensemble de dépendances fonctionnelles minimal équivalent à F.

On appelle encore cela une couverture irréductible (ou minimale, irredondante, etc.) Là encore il y a du travail... Je vous renvoie à un exercice où l’on traite du sujet de façon exhaustive. Pour vous, il y a au moins 3 couvertures (trouvez en une, ça sera déjà bien...)

On se propose de décomposer la relation R en 6 relations:
R1(A,C) , R2(B,E), R3(A,E) , R4 (C,E,D) , R5(C,D,B) . Rappelez la condition pour qu'une décomposition soit sans perte d'informations. La décomposition proposée est elle sans perte d'information? justifiez.

La réponse est ici en ce qui concerne la préservation des données et là en ce qui concerne la préservation des dépendances fonctionnelles. Cela dit, qu’entend votre prof par perte d’information : perte de données ? de dépendances fonctionnelles ? Les deux ?

Donner une décomposition légèrement différente qui soit à la fois sans perte et en 3ème forme normale.

Si vous avez réussi à déterminer les clés candidates et au moins une couverture irréductible, cette décomposition est immédiate.


En tout cas, bonne lecture et bon courage !

[lou93]

Bonjour,

merci pour vos réponses!

alors, j'ai essayé de le faire...
1) la fermeture de [A;B] et {A,B,D,E} et la clé est pour moi {A,B,C}

2) Concernant la minimisation, j'ai trouvé A-->E; CED--> B et DC--> E

3)la décomposition est sans pertes d'informations si toute relation R du schéma d'origine peut être retrouvée à partir des relations R1,, Rk : R= pi1(R) jointure .... jointure pik(R).
La décomposition est sans perte d'informations car le schéma d'origine peut être retrouvé?comment le justifier autrement?

4) Concrétement, pour la forme normale 3, je dois faire en sorte que chaque membre de gauche, soit une clé?
Comment faire?

[fsmrel]

Bonsoir lou93,

alors, j'ai essayé de le faire...

Bravo ! Comme disait Virgile : Audaces fortuna juvat !

la fermeture de [A;B] et {A,B,D,E}

Bonne réponse !

la clé est pour moi {A,B,C}

Comme A et C ne font partie d’aucun dépendant, ils appartiennent forcément à chaque clé candidate. Maintenant, posons-nous la question de la participation de B à une clé. Le mieux est de partir de {A, C}⁺ et voir ce qu’il y manque pour obtenir une clé.

C’est parti :

Au départ, {A, C}⁺ = {A, C} ;

Dans un 2e temps, comme {A} -> {D, E}, en vertu de la règle de décomposition, on infère {A} -> {E}, donc l’attribut E est absorbé par la fermeture : {A, C}⁺ = {A, C, E} ;

Dans un 3e temps, comme la paire {C, E} appartient maintenant à la fermeture {A, C}⁺, du fait de l’existence de la dépendance fonctionnelle {C, E} -> {D}, l’attribut D est absorbé à son tour : {A, C}⁺ = {A, C, D, E} ;

Dans un 4e temps, comme la paire {C, D} appartient maintenant à la fermeture {A, C}⁺, du fait de l’existence de la dépendance fonctionnelle {C, D} -> {B}, l’attribut D est absorbé à son tour : {A, C}⁺ = {A, B, C, D, E}.

Puisque l’ensemble des attributs composant l’en-tête de R est en fait contenu dans {A, C}⁺, la paire {A, C} est clé candidate et le triplet {A, B, C} est une surclé sans être pour autant clé candidate (le triplet vérifie la contrainte d’unicité mais pas celle d’irréductibilité).

Comme on a vu que chaque clé candidate doit contenir la paire {A, C}, et doit vérifier les contraintes d’unicité et d’irréductibilité des clés, on conclut que {A, C} est la seule clé candidate de R.


Comme vous n'êtes pas mon seul interlocuteur, je vous quitte provisoirement, mais je reviens dès que possible pour la suite (problème de la perte de données...)

[lou93]

Bonsoir,

Merci pour vos explications, j'ai compris pourquoi B ne fait pas partie de la clé !
Si vous avez le temps, j’apprécierai que vous m'expliquiez la suite

[fsmrel]

Bonsoir lou93,

La décomposition est sans perte d'informations car le schéma d'origine peut être retrouvé? comment le justifier autrement?

On peut retrouver le schéma d’origine, mais il faut s’assurer qu’en utilisant les jointures, on retrouve exactement les données de R, sans tuples (n-uplets) supplémentaires illégaux (spurious tuples).

Pour cela on utilise la technique du tableau déjà évoquée pour s’assurer qu’on préserve les données :

On crée un tableau dans lequel on porte en abscisse les projections proposées et en ordonnée les noms des attributs de R :

             A        B        C        D        E
--------------------------------------------------- 

{A, C}       a1       b12      a3       b14      b15

{B, E}       b21      a2       b23      b24      a5

{A, E}       a1       b32      b33      b34      a5

{C, E, D}    b41      b42      a3       a4       a5

{C, D, B}    b51      a2       a3       a4       b55

Le but de la manœuvre et d’arriver à transformer le tableau de telle sorte qu’une de ses lignes ne soit constituée que de a_j : si c'est le cas, la décomposition est réputée sans perte de données (lossless join decomposition).

A cet effet, on considère une par une les dépendances fonctionnelles appartenant à F. Soit X -> Y une telle DF. Si deux lignes du tableau ont le même symbole pour le déterminant X, alors, en ce qui concerne le dépendant Y, le symbole d’une des deux lignes peut remplacer le symbole de l’autre ligne, sachant que si un des symboles est a_j et l’autre b_ij, c’est a_j qui remplace b_ij (sinon on n’arrivera jamais à nos fins !)

Considérons par exemple la DF {A} -> {D}. Comme le symbole a1 affecté au déterminant {A} figure à la fois aux lignes 1 et 3, pour le dépendant {D}, on peut remplacer b34 par b14 (ou b14 par b34). Le tableau devient :

             A        B        C        D        E
--------------------------------------------------- 

{A, C}       a1       b12      a3       b14      b15

{B, E}       b21      a2       b23      b24      a5

{A, E}       a1       b32      b33      b14      a5

{C, E, D}    b41      b42      a3       a4       a5

{C, D, B}    b51      a2       a3       a4       b55

Passons à la 2e DF figurant dans F, à savoir {A} -> {E}. Comme le symbole a1 affecté au déterminant {A} figure à la fois aux lignes 1 et 3, alors pour le dépendant {E}, on peut remplacer b15 par a5 (mais pas a5 par b15 !). Le tableau devient :

             A        B        C        D        E
--------------------------------------------------- 

{A, C}       a1       b12      a3       b14      a5

{B, E}       b21      a2       b23      b24      a5

{A, E}       a1       b32      b33      b34      a5

{C, E, D}    b41      b42      a3       a4       a5

{C, D, B}    b51      a2       a3       a4       b55

Passons à la 3e DF figurant dans F, à savoir {C, E, D} -> {B}. Comme le symbole b41 affecté au déterminant {C, E, D} ne figure que dans la ligne 4 du tableau, il n’y a aucun changement possible.

Passons à la 4e DF figurant dans F, à savoir {D} -> {E}. Comme le symbole a4 affecté au déterminant {D} figure à la fois aux lignes 4 et 5, alors pour le dépendant {E}, on peut remplacer b55 par a5 (mais pas a5 par b55 !). Le tableau devient :

             A        B        C        D        E
--------------------------------------------------- 

{A, C}       a1       b12      a3       b14      a5

{B, E}       b21      a2       b23      b24      a5

{A, E}       a1       b32      b33      b34      a5

{C, E, D}    b41      b42      a3       a4       a5

{C, D, B}    b51      a2       a3       a4       a5

Passons à la 5e DF figurant dans F, à savoir {B} -> {E}. Comme le symbole a2 affecté au déterminant {B} figure à la fois aux lignes 2 et 5, alors pour le dépendant {E}, on peut chercher un remplacement, mais comme pour les deux lignes 2 et 5 il est déjà égal à a5, rien ne passe.


Passons à la 6e DF figurant dans F, à savoir {C, E} -> {D}. Comme la paire de symboles <a3, a5> affectée au déterminant {C, E} est présente dans les lignes 1, 4, 5, alors dans la 1re ligne, le symbole b14 affecté au dépendant {D} peut être remplacé par celui des lignes 4 et 5, à savoir a4. Le tableau devient :

             A        B        C        D        E
--------------------------------------------------- 

{A, C}       a1       b12      a3       a4       a5

{B, E}       b21      a2       b23      b24      a5

{A, E}       a1       b32      b33      b34      a5

{C, E, D}    b41      b42      a3       a4       a5

{C, D, B}    b51      a2       a3       a4       a5

Passons à la 7e et dernière DF : {C, D} -> {B}. Comme la paire de symboles <a3, a4> affectée au déterminant {C, D} est présente dans les lignes 1, 4, 5, alors dans la 1re ligne, le symbole b12 affecté au dépendant {B} peut être remplacé par celui de la ligne 5, à savoir a2, même chose pour le symbole b42, remplaçable lui aussi par a2. Le tableau devient :

             A        B        C        D        E
--------------------------------------------------- 

{A, C}       a1       a2       a3       a4       a5

{B, E}       b21      a2       b23      b24      a5

{A, E}       a1       b32      b33      b34      a5

{C, E, D}    b41      a2       a3       a4       a5

{C, D, B}    b51      a2       a3       a4       a5

A ce stade, on constate avec joie que la 1re ligne du tableau ne contient que des a_j : la décomposition est donc sans perte de données.


Il faudra vérifier si la décomposition est sans perte de DF. Je reviens dès que je peux...

[fsmrel]

j'ai compris pourquoi B ne fait pas partie de la clé !

That’s a good news! Alors n’oubliez pas de voter

Je reviens dès que je peux...

En attendant, n’oubliez pas de vous frotter à l’algorithme permettant de vérifier si la décomposition est sans perte de DF !

[lou93]

ce n'est pas évident comme méthode.. je ne comprend pas comment vous avez placé les noms des attributs dans le tableau ( les a1, b12...) , pouvez vous s'il vous plait me l'expliquer?
peut on également me dire si ce que j'ai fais à la question 2 est correct

[lou93]

je viens de comprendre la méthode avec les tableaux, mais y'a t'il un moyen plus simple d'arriver à ce résultat?
Concernant le fait de minimiser F, j'ai trouvé A-->E et CD--> E , est ce correct?

[fsmrel]

ce n'est pas évident comme méthode.. je ne comprend pas comment vous avez placé les noms des attributs dans le tableau ( les a1, b12...)

Certes la méthode n’est pas évidente a priori, mais elle évite d’avoir à tâtonner, il suffit d’appliquer l’algorithme. Remettons les compteurs à zéro :

Pour reprendre votre exercice, soit la variable relationnelle (en abrégé relvar) R{A, B, C, D, E} où {A, B, C, D, E} représente l’en-tête de R c'est-à-dire un ensemble, celui des noms des attributs de la relvar (en réalité, l’en-tête est un ensemble d’attributs, de la forme <A, T> où A est un nom d’attribut et T le nom du type de l’attribut A, mai on ne va pas faire dans la tetracapilliculture...)

Soit l’ensemble donné de dépendances fonctionnelles F = { {A} -> {D}, {A} -> {E}, {C, E, D} -> {B}, {D} -> {E}, {B} -> {E}, {C, E} -> {D}, {C, D-> {B} }

Soit la décomposition ρ = (R1, R2, R3, R4, R5), avec :

R1 = {A, C}
R2 = {B, E}
R3 = {A, E}
R4 = {C, E, D}
R5 = {C, D, B}

Il s’agit de montrer si ρ préserve ou non les données (lossless join decomposition), c'est-à-dire si R = JOIN {R1, R2, R3, R4, R5} (ou plus de façon moins ramassée : R1 JOIN R2 JOIN R3 JOIN R4 JOIN R5), autrement dit sans que la jointure ne produise de tuples illégaux.

On construit un tableau à n colonnes et m lignes, où la colonne j correspond à l’attribut A_j (A_j représente le jième attribut de l’en-tête de R) et la ligne i correspond au schéma R_i. A l’intersection de la ligne i et de la colonne j, faire figurer le symbole a_j si A_j appartient à R_i, sinon y faire figurer le symbole b_ij.

On considère une par une les dépendances fonctionnelles appartenant à F. Soit X -> Y une telle DF. Si deux lignes du tableau ont le même symbole pour le déterminant X, alors, en ce qui concerne le dépendant Y, le symbole d’une des deux lignes peut remplacer le symbole de l’autre ligne, sachant que si un des symboles est a_j et l’autre b_ij, c’est a_j qui remplace b_ij (sinon on n’arrivera jamais à nos fins !)

Si ces explications complémentaires ne suffisent pas, dites-le moi.

Concernant la minimisation, j'ai trouvé A-->E; CED--> B et DC--> E

L’ensemble des DF doit pouvoir être inféré d’une couverture irréductible.

L’ensemble G = { {A -> {E} , {C, E, D} -> {B} et {D, C} -> {E} } est-il candidat à être une couverture irréductible ? Si oui, à partir de G, on doit être capable de retrouver l’ensemble initial F des DF, autrement dit G doit couvrir F.

Commençons par vérifier si l’on peut inférer la DF {A} -> {D}, laquelle appartient à F. Calculons la fermeture {A}⁺ par rapport à G : {A}⁺ = {A, E} et c’est tout, donc on ne peut pas inférer la DF {A} -> {D}, donc G ne couvre pas F, G n’est pas une couverture irréductible...

Je viens de voir que vous proposez une autre solution : G’ = { {A} -> {E}, {C, D} -> {E} } : on n’est toujours pas en mesure d’inférer la DF {A} -> {D}, donc G’ ne couvre pas F, G’ n’est pas non plus une couverture irréductible...

[fsmrel]

je viens de comprendre la méthode avec les tableaux, mais y'a t'il un moyen plus simple d'arriver à ce résultat?

L’exercice qui vos a été proposé est assez tordu et c’est évidemment voulu. Dans le cas général, on ne sort pas l’artillerie lourde et le théorème de Heath suffit pour décomposer une relvar en deux relvars, sans perte de données.

Dans votre cas, partant de la relvar R{A, B, C, D, E}, en utilisant par exemple la DF {C, E, D} -> {B}, vous pouvez utiliser ce théorème pour décomposer (sans perte de données) R en R1 et R2 :

R1 = {C, E, D, B}

R2 = {C, E, D, A}

A son tour, grâce à la DF {B} -> {E}, R1 est décomposable selon :

R11 = {B, E}

R12 = {B, C, D}

Pour sa part, grâce à la DF {C, E} -> {D}, R2 est décomposable selon :

R22 = {C, E, D}

R23 = {C, E, A}

Grâce à la DF {A} -> {E}, R23 est décomposable selon :

R231 = {A, E}

R232 = {A, C}

Et R admet donc la décomposition sans perte de données :

ρ = (R232, R11, R231, R22, R12)

C'est-à-dire la décomposition qui vous a été proposée dans l’exercice. Grâce au théorème de Heath on a démontré que cette décomposition est sans perte, mais celui qui n’a pas l’habitude peut tourner en rond pendant longtemps, longtemps, longtemps, avant de trouver le bon chemin, en effet il y a pas mal de décompositions possibles, mais qu'on ne vous a pas demandées, alors que la technique du tableau permet d’aller tout de suite droit au but.

[lou93]

Bonjour,

Merci de nouveau pour vos explications !

Concernant le fait de minimiser F
F={A-->D,E ; C,E,D-->B; D-->E; B-->E ; C,E-->D; C,D-->B}, pouvez vous s'il vous plait m aider à le faire?
Car je comprend le principe, mais la méthode pour le faire me rend perplexe.
J'étais persuadé que A-->E faisait partie de la minimisation car A-->D , A-->E , D--> E, du coup il y a des répétitions et on devrais pouvoir enlever A-->D et D--> E..

[lou93]

Bonsoir,
J ai repenser à la minimisation
Je dirais :
A-->D; C, E, D--> B ; D-->E; B--> E; C, E--> D
Je suis même tenté d enlever C, E--> D.. à cause de la DF C, E, D--> B.

[fsmrel]

Bonsoir lou93,

Voici une réponse à votre avant-dernier message.

J'étais persuadé que A-->E faisait partie de la minimisation car A-->D , A-->E , D--> E, du coup il y a des répétitions et on devrais pouvoir enlever A-->D et D--> E.

Considérons à nouveau l’ensemble initial des dépendances fonctionnelles :

F = { {A} -> {D}, {A} -> {E}, {C, E, D} -> {B}, {D} -> {E}, {B} -> {E}, {C, E} -> {D}, {C, D-> {B} }

L’objet de ce que vous appelez la minimisation est de virer de F les dépendances fonctionnelles inférables des dépendances fonctionnelles disons « invirables », de manière à ne conserver qu'un sous-ensemble de F, appelons-le G, tel que G⁺ = F⁺. Vous me direz : « Oui, mais à quoi bon ? » Je vous répondrai : « Si l’on a démontré que la relvar R n’est pas en 3e forme normale, alors, grâce à l’existence d’une couverture irréductible G, on est en mesure de décomposer R en un ensemble de relvars en 3e forme normale. » Et ça marche à tous les coups, parce que le théorème correspondant a été démontré en 1979 par Biskup, Dayal et Bernstein :

Soit G une couverture minimale de R et K une clé de R. G ∪ {K} est une décomposition dont chaque relvar est en 3e forme normale ; G est une décomposition sans perte de données et qui préserve les dépendances fonctionnelles.

Et ça, pour modéliser correctement une base de données, c’est plutôt important.

Bref, voyons voir les conséquences de l’évacuation de la seule DF {A} -> {D} pour produire :

G = { {A} -> {E}, {C, E, D} -> {B}, {D} -> {E}, {B} -> {E}, {C, E} -> {D}, {C, D-> {B} }

C'est-à-dire : est-on capable d’inférer {A} -> {D} à partir de G ?

Comme je l’ai déjà écrit ici, calculons la fermeture {A}+ par rapport à G :

{A}+ = {A, E}

Et c’est tout, donc on ne peut pas inférer la DF {A} -> {D}, donc G ne couvre pas F, G n’est pas une couverture irréductible, en vertu de quoi {A} -> {D} devra faire partie de la couverture irréductible.


Tentons maintenant l’évacuation de la seule DF {A} -> {E} pour produire :

G = { {A} -> {D}, {C, E, D} -> {B}, {D} -> {E}, {B} -> {E}, {C, E} -> {D}, {C, D-> {B} }

Est-on capable d’inférer {A} -> {E} à partir de G ?

Dans un 1er temps, grâce à la DF {A} -> {D}, la fermeture {A}+ est égale à {A, D}.
Dans un 2e temps, grâce à la DF {D} -> {E} et parce que son déterminant {D} appartient à {A}+ alors {A}+= {A, D, E}.

Du fait de l’appartenance des attributs A et E à {A}+, on sait inférer la DF {A} -> {E}, laquelle n’a pas donc pas à figurer dans la couverture irréductible, dès lors que les DF {A} -> {D} et {D} -> {E} en font partie. Du point de vue des règles d’Armstrong, on démontre aussi que {A} -> {E} :

{A} -> {D}, donné
{D} -> {E}, donné
{A} -> {E}, par transitivité.

G est un sous-ensemble strict de F tel que G+ = F+, mais G n'est pas une couverture irréductible.

Je fais suivre ce message d'une réponse à votre dernier message, laissez-moi une une heure ou deux

[lou93]

Bonsoir!

Merci, j'ai compris les subtilités de la minimisation
Du coup, j'ai fait :
A-->D; C, E, D--> B ; D-->E; B--> E; C, E--> D
Mais j'ai l'impression qu"il y'a une autre DF que je pourrais enlever, comme C,E-->D...
J'ai examen de Base de données demain , du coup si vous pouviez aussi m'eclairer sur la question 4 de l'examen et me dire comment on trouve les dépendances fonctionnelles de la décomposition de R : R1(A,C) , R2(B,E), R3(A,E) , R4 (C,E,D) , R5(C,D,B) ?

[fsmrel]

J ai repensé à la minimisation
Je dirais :
A-->D; C, E, D--> B ; D-->E; B--> E; C, E--> D
Je suis même tenté d enlever C, E--> D.. à cause de la DF C, E, D--> B.

On y est presque !

Mais vous êtes victime de l’effet Dagobert, il faut remettre votre raisonnement à l’endroit...

Revenons à ce que j’ai écrit au paragraphe E.6.2. Propriétés d'un ensemble irréductible de DF de l’article sur la normalisation :

« Le déterminant D (partie gauche) de chaque DF doit être irréductible »

Voyons maintenant le cas de la DF {C, E, D} -> {B}.

Elle est réductible si le déterminant {C, E, D} contient (au moins) un sous-ensemble strict S tel que S -> {B} et tel que S+ par rapport à F = S+ par rapport à G, avec :

F = { {A} -> {D}, {A} -> {E}, {C, E, D} -> {B}, {D} -> {E}, {B} -> {E}, {C, E} -> {D}, {C, D-> {B} }

G = { {A} -> {D}, {A} -> {E}, S -> {B}, {D} -> {E}, {B} -> {E}, {C, E} -> {D}, {C, D-> {B} }

Par exemple, que donne le sous-ensemble S = {C} ?

G = { {A} -> {D}, {A} -> {E}, {C} -> {B}, {D} -> {E}, {B} -> {E}, {C, E} -> {D}, {C, D-> {B} }

{C}+ par rapport à F = {C} et c’est tout.

{C}+ par rapport à G = {B, C, D, E}

Ces deux fermetures sont différentes, donc la DF {C, E, D} -> {B} n’est pas réductible à {C} -> {B}.

Avec S = {E}, on montre de la même façon que la DF {C, E, D} -> {B} n’est pas réductible à {E} -> {B}, car E+ par rapport à F = {E} tandis que E+ par rapport à G = {B, E}.

Avec S = {D}, on montre de la même façon que la DF {C, E, D} -> {B} n’est pas réductible à {D} -> {B}, car D+ par rapport à F = {D, E} tandis que E+ par rapport à G = {B, D, E}.


On vient d’essayer en vain de réduire le déterminant C, E, D} à un singleton. Passons aux paires...

Avec S = {D, E}, on montre encore que la DF {C, E, D} -> {B} n’est pas réductible à {D, E} -> {B}, car {D, E}+ par rapport à F = {D, E} tandis que {D, E}+ par rapport à G = {B, D, E}.

Avec S = {C, D} : {C, D}+ par rapport à F = {B, C, D, E} et {C, D}+ par rapport à G = {B, C, D, E} : les fermetures sont égales, donc la DF {C, E, D} -> {B} est réductible à {C, D} -> {B} (DF qui existe du reste déjà dans F).

=>

G = { {A} -> {D}, {A} -> {E}, {D} -> {E}, {B} -> {E}, {C, E} -> {D}, {C, D-> {B} }

Et comme on sait que {A} -> {E} est inférable, on réduit à :

G = { {A} -> {D}, {D} -> {E}, {B} -> {E}, {C, E} -> {D}, {C, D-> {B} }

Je vous laisse le soin de vérifier que G est une couverture irréductible.

Elle n’est pas la seule, en effet la DF {C, E, D} -> {B} est réductible à {C, E} -> {B}...

[fsmrel]

j'ai compris les subtilités de la minimisation
Du coup, j'ai fait :
A-->D; C, E, D--> B ; D-->E; B--> E; C, E--> D

J’ai envoyé ma réponse précédente (n-1) avant d’avoir lu ce que vous venez de proposer. Mais à la lecture de ma réponse (n-1), vous comprendrez que votre ensemble de DF est encore réductible (parce que la DF {C, E, D} -> {B} est elle-même réductible...)

Je vais aller dîner, mais je sens que ce soir ça va être charrette, comme du temps où j’avais votre âge (en passant, vous ne votez toujours pas ? Vous n’avez pas accès aux pouces ? )

[lou93]

Je vois.. j'ai compris le principe et j'espere pouvoir le refaire demain!
Il ne reste que la derniere question à éclaircir, j'ai compris la Forme normale 2 mais la forme normale 3 me laisse perplexe.
Car on a décomposé R en R1(A,C) , R2(B,E), R3(A,E) , R4 (C,E,D) , R5(C,D,B) mais comment connait on les DF? ce sont les mêmes que celles données au début de l'exercice?

[lou93]

Je vous souhaite alors un bon appétit et peut être à tout à l'heure pour une meilleure compréhension de la derniere question
( je n'avais pas fait attention au pouce , mais ça y'est je vote )