Algorithme de la couverture minimale

Bonjour,

Je suis actuellement en train d'essayer d'utiliser l'algorithme de la couverture minimale en rapport avec les dépendances fonctionnelles mais malheureusement la deuxième partie de celui-ci me laisse perplexe.

Voici l'exercice sur lequel je bloque :

AB -> C
C -> A
BC -> D
ACD -> BC

La première partie de l'algorithme est simple à mettre en place, on obtient la chose suivante :

AB -> C
C -> A
BC -> D
ACD -> B
ACD -> C

Maintenant la seconde partie est de jouer sur les dépendances fonctionnelles de telle façon à ce qu'on ne puisse en retirer aucune. Et là ça commence à coincer. Je vois que je peux enlever les dépendances qui se retrouvent en utilisant à partir des axiomes les autres dépendances mais bon...

Ici je pense qu'on peut jouer au niveau des deux dépendances qui impliquent C mais je ne vois pas comment le justifier proprement.

Si quelqu'un pourrait m'éclairer dans le principe de cet algorithme, ce serait sympa. La plus part des ressources que j'ai trouvé ne détaillent rien et n'ont pas d'exemples corrects.

Merci à vous.

C'est une vraiment question SQL / base de données ou bien une erreur de forum ?

C'est une question liée au base de données mais effectivement je n'ai pas trouvé de sous forum plus générale sur les bases de données. Mais vu que ça concerne les schémas de base de données, je me suis dit que ça pouvait être placé ici.

Si tu penses qu'il vaut mieux déplacer dans un autre forum, pourquoi pas mais je n'ai pas trouvé de forum précis là dessus (je l'ai peut-être loupé...).

Merci à toi.

Bonsoir,

Le sujet a était traité plusieurs fois sur le forum, notamment par fsmrel.
Voyez notamment ces deux messages, très complets avec démonstration :
http://www.developpez.net/forums/d64...s/#post3826559
http://www.developpez.net/forums/d86...s/#post4928839

Quel est précisément le but de l'exercice ?

Re,

Le but de l'exercice est d'appliquer l'algorithme de couverture minimale.

Alors j'ai lu le premier lien, voici mon essai :

De base on définit F l'ensemble de dépendances fonctionnelles suivant :

AB -> C
C -> A
BC -> D
ACD -> BC

Après application de la première règle, on modifie l'ensemble F pour obtenir :

AB -> C
C -> A
BC -> D
ACD -> B
ACD -> C

Maintenant que l'ensemble des parties droites sont réduites, on attaque les parties gauches.

On se penche sur AB -> C.

On calcule la fermeture de AB sur F, on obtient {A, B, C, D}. On essaye de réduire AB -> C en A -> C. On calcule la fermeture de A sur le nouvel ensemble F' constitué de :

A -> C
C -> A
BC -> D
ACD -> B
ACD -> C

A+ = {A, C} ce n'est pas égale à la fermeture de AB sur F.

On essaye avec B -> C, l'ensemble F' devient :

B -> C
C -> A
BC -> D
ACD -> B
ACD -> C

La fermeture de AB sur F n'a pas évolué, on se concentre sur celle de B sur F' :

B+ = {B, C, A, D}

On s'aperçoit que cette fermeture est égale à celle de AB sur F on peut donc réduire la partie gauche de cette dépendance fonctionnelle.

On garde donc F' constitué de :

B -> C
C -> A
BC -> D
ACD -> B
ACD -> C

On passe ensuite à la dépendance BC -> D.

On calcule la fermeture de BC sur F', on obtient :

BC+ = {B, C, D, A}

On essaye de réduire la partie gauche avec B, on obtient l'ensemble F' :

B -> C
C -> A
B -> D
ACD -> B
ACD -> C

On calcule la fermeture de B sur celui-ci :

B+ = {B, C, D, A}

Fermeture de B égale à celle de BC on réduit donc l'ensemble.

On obtient F'' composé de :

B -> C
C -> A
B -> D
ACD -> B
ACD -> C

On s'occupe de ACD -> B.

La fermeture de ACD sur F'' est ACD+ = {A, C, D, B}

On essaye de la réduire en A -> B, l'ensemble devient donc

B -> C
C -> A
B -> D
A -> B
ACD -> C

On calcule la fermeture de A sur celui-ci :

A+ = {A, B, D, C}

Fermeture égale à la précédente on peut donc réduire.

On obtient un ensemble F''' composé des dépendances fonctionnelles suivantes :

B -> C
C -> A
B -> D
A -> B
ACD -> C

On s'attaque à la dernière ACD -> C. En faisant la même chose que précédemment, j'obtiens le fait qu'on puisse la réduire en A -> C.

On a donc l'ensemble de dépendances fonctionnelles équivalent :

B -> C
C -> A
B -> D
A -> B
A -> C

On remarque la dépendance A -> C peut-être obtenue par transitivité, on peut donc l'enlever et obtenir l'ensemble final :

B -> C
C -> A
B -> D
A -> B

J'espère ne pas m'être trop trompé...

Mais si quelqu'un pouvait me corriger ce serait bien.

Merci à vous.

PS : merci au modérateur, je ne connaissais même pas ce forum ;-)

Bonsoir,

Citation:

---

Envoyé par sperca

Maintenant que l'ensemble des parties droites sont réduites, on attaque les parties gauches.

On se penche sur AB -> C.

On calcule la fermeture de AB sur F, on obtient {A, B, C, D}. On essaye de réduire AB -> C en A -> C. On calcule la fermeture de A sur le nouvel ensemble F' constitué de :

A -> C
C -> A
BC -> D
ACD -> B
ACD -> C

A+ = {A, C} ce n'est pas égale à la fermeture de AB sur F.

---

Comme vous tentez de réduire AB -> C à A -> C, il faut calculer la fermeture AF+ de A par rapport à F et la fermeture AF’+ de A par rapport à F’ :

AF+ = {A} et pas autre chose, car A n’apparaît jamais seul à gauche dans F.
AF’+ = {AC} puisque A -> C et par ailleurs AF n’apparaît jamais seul à gauche dans F’.

Quoi qu’il en soit, la DF AB -> C ne peut pas être réduite à A -> C car les fermetures AF+ et AF’+ ne sont pas égales.

Citation:

---

Envoyé par sperca

On essaye avec B -> C, l'ensemble F' devient :

B -> C
C -> A
BC -> D
ACD -> B
ACD -> C

---

Cette fois-ci, il faut calculer la fermeture BF+ de B par rapport à F et la fermeture BF’+ de B par rapport à F’ :

BF+ = {B}
BF’+ = {BC}

La DF AB -> C ne peut pas être réduite à B -> C car les fermetures BF+ et BF’+ ne sont pas égales.

Etc.

Par ailleurs, vous aurez noté que le calcul de la couverture minimale (irréductible) comporte une troisième étape au cours de laquelle on supprime les DF qui peuvent l’être. Je vous renvoie à mon tour à la discussion ouverte par wotan2009.

Merci ;-)

J'obtiens donc l'ensemble de DF suivant :

AB -> C
C -> A
BC -> D
CD -> B

J'ai bon ?

Merci encore.

Bonjour,

Citation:

---

Envoyé par sperca

J'obtiens donc l'ensemble de DF suivant :

AB -> C
C -> A
BC -> D
CD -> B

J'ai bon ?

---

Oui. Mais pour ceux qui sont à la recherche de démonstrations et atterrissent enfin ici, il serait bon que vous en donniez une, sinon ils se sentiront une fois de plus frustrés et surferont encore et encore... Ça ne devrait pas prendre beaucoup de votre temps...

Merci pour eux.

Bonsoir,

J'obtiens un résultat différent, cela me semble bon, mais je ne suis bien sûr pas à l'abri d'une erreur. :mouarf:

Voici la démarche:

Les déterminants des trois premières DF ne peuvent pas être réduits.
On obtient jusque là l'ensemble F suivant:

DF1: {A, B} → {C}
DF2: {C} → {A}
DF3: {B, C} → {D}
DF4: {A, C, D} → {B, C}

Pour réduire le déterminant de la DF4 je démarre avec ces 6 options:

DFa: {A, C} → {B}
DFb: {A, C} → {C}
DFc: {C, D} → {B}
DFd: {C, D} → {C}
DFe: {A, D} → {B}
DFf: {A, D} → {C}

J'enlève de F la DF4 que je remplace par DFa, j'appelle ce nouvel ensemble I.
Je calcule la fermeture de {A, C} par rapport à F:

{A, C}+ = {A, C}

Je calcule la fermeture de {A, C} par rapport à I:

{A, C}+ = {A, B, C, D}

I+ ≠ F+. La DF4 ne peut pas être réduite à DFa. Je passe à DFb.

J'enlève de F la DF4 que je remplace par DFb, l'ensemble s'appelle I.
La fermeture de {A, C} par rapport à F est toujours la même:

{A, C}+ = {A, C}

Je calcule la fermeture de {A, C} par rapport à I:

{A, C}+ = {A, C}

I+ = F+, je remplace DF4 par DFb.
Le déterminant de cette DF n'est pas réductible. F devient:

F = {
DF1: {A, B} → {C}
DF2: {C} → {A}
DF3: {B, C} → {D}
DF4: {A, C} → {C}
}

Les déterminants et dépendants de toutes les DF sont irréductible.
On va essayer de réduire cet ensemble de DF, en les supprimant une par une.

Je commence avec DF1.
Soit I = F - DF1.

Le déterminant de DF1 est {A, B}, il faut calculer la fermeture {A, B}+ par rapport à F et I. Si elles sont égales, la DF peut disparaitre, sinon on passe à la suivante.

La fermeture de {A, B} par rapport à F:

{A, B}+ = {A, B, C, D}

La fermeture de {A, B} par rapport à I:

{A, B}+ = {A, B}

I+ ≠ F+. DF1 ne peut être supprimée. On passe à la suivante, DF2, etc..
DF2 et DF3 ne peuvent pas non plus être supprimées.
J'arrive à DF4.
Soit I = F - DF4.

La fermeture de {A, C} par rapport à F:

{A, C}+ = {A, C}

La fermeture de {A, C} par rapport à I:

{A, C}+ = {A, C}

I+ = F+. DF4 peut disparaître.

L'ensemble de DF irréductible est le suivant:

{A, B} → {C}
{C} → {A}
{B, C} → {D}

Edit:
Arf, je me suis planté bêtement dès le début, j'ai oublié de réduire le dépendant de {A, C, D} → {B, C} en {A, C, D} → {B} et {A, C, D} → {C}.
Je vais revoir ça. :cry:

Edit 2:
Donc en partant bien de l'ensemble suivant, après la première étape (réduction des dépendants):

DF1: {A, B} → {C}
DF2: {C} → {A}
DF3: {B, C} → {D}
DF4: {A, C, D} → {B}
DF5: {A, C, D} → {C}

On réduit les déterminants pour obtenir ceci:

DF1: {A, B} → {C}
DF2: {C} → {A}
DF3: {B, C} → {D}
DF4: {C, D} → {B}
DF5: {A, C} → {C}

Seul la DF5 peut être supprimée. On obtient bien au final l'ensemble irréductible suivant:

{A, B} → {C}
{C} → {A}
{B, C} → {D}
{C, D} → {B}

Citation:

---

Envoyé par Oishiiii

J'obtiens un résultat différent, cela me semble bon, mais je ne suis bien sûr pas à l'abri d'une erreur. :mouarf:

Voici la démarche: ...

... Arf, je me suis planté bêtement dès le début...

---

Faut pas pleurer, personne ne vous en voudra, il fallait essayer, c’est comme cela qu’on progresse... Et c’est en forgeant qu’on devient forgeron (et c’est en sciant que Léonard ...)

Citation:

---

Envoyé par Oishiiii

On obtient bien au final l'ensemble irréductible suivant:
{A, B} → {C}
{C} → {A}
{B, C} → {D}
{C, D} → {B}

---

C’est effectivement meilleur...