Discussion :

[boobs60]

Bonjour tout le monde.

Voila j'ai un besoin urgent d'aide car j'ai un examen vendredi et j'ai pas du tout comprit les trucs de normalisation. J'ai lu plusieurs poste de "fsmrel" qui parlait de mon problème mais je reste toujours dans le flou.

voici un énoncé d'exercice :

Soit la relation R(A,B,C,D,E) et F, l’ensemble des dépendances fonctionnelles
suivant : F= {A→C, A→D, BC→A, E→B, E→D}.
3.1) Calculez la liste des clés candidates de R, F+
3.2) Calculez la fermeture élémentaire élé(F+)
3.3) Calculez la couverture minimale
Je suis dans le flou total quant à ces notions.

Merci d'avance de votre aide.

NB : fsmrel désolé pour votre boite mail.

Amicalement Boobs60

[fsmrel]

1) Vous pouvez affirmer que E fait partie de chaque clé, parce que cet attribut n'appartient à aucune partie droite des dépendances fonctionnelles données. Inutile donc de calculer A+, B+, C+, D+.

2) Dans votre cas, une clé candidate a pour fermeture {A,B,C,D,E}.

Vous calculez d'abord la fermeture de E+ : celle-ci est égale à {B,D,E}, ce qui est insuffisant pour en faire une clé.

Ensuite vous calculez la fermeture de AE+, BE+, CE+, DE+ (combinaison de deux attributs dont l'un est E) :

AE+ = {A,B,C,D,E} : c'est tout bon.

BE+ = {B,D,E} : c'est insuffisant.

CE+ = {A,B,C,D,E} : c'est tout bon.

En notant qu'au départ CE+ = {C,E}

puis CE+ = {B,C,E} car {E} -> {B} et {E} est inclus dans {C,E}, ce qui autorise la capture de B,

puis CE+ = {B,C,D,E} car {E} -> {D} et {E} est inclus dans {B,C,E}, ce qui autorise la capture de D,

puis CE+ = {A,B,C,D,E} car {B,C} -> {A} et {B,C} est inclus dans {B,C,D,E}, ce qui autorise la capture de A.

DE+ = {B,D,E} : c'est insuffisant.

=> AE+ et CE+ sont effectivement des clés candidates.

Inutile de chercher par combinaison de 3 attributs (E toujours présent, A et C absents, sinon on aura des surclés, réductibles à AE et CE), car la combinaison B,D,E ne suffit pas.

élé(F+) : ça veut dire quoi ? Encore un prof avec son vocabulaire à lui. Peut-être "Couverture minimale" ?
__________________

[boobs60]

OK OK merci beaucoup maintenant j'ai comprit pour les clés candidates. Maintenant il reste a voir pour la fermeture élémentaire qui est écrit élé (F+)
En gros faut calculer la fermeture élémentaire de F+

Si tu peu toujours m'aider.

Merci

[fsmrel]

Le problème est que le loustic qui a parlé de élé(F+) (ou de fermeture élémentaire de F+) est bien gentil, mais c’est son jargon bien à lui. En recherchant sur la toile, on ne trouve guère qu’un article où est utilisée l’expression « fermeture élémentaire », mais sans que la définition en soit donnée. Il faudrait demander à votre prof ou à vos camarades de quoi il en retourne.

S’il s’agit de décomposer la relation R de telle sorte que les relations résultantes respectent la forme normale de Boyce-Codd (BCNF, ou FNBC), vous pouvez vous servir du théorème de Heath :
Soit la relation R {X, Y, Z} dans laquelle X, Y et Z sont des ensembles d’attributs de R. Si R satisfait à la dépendance fonctionnelle X → Y, alors R est égale à la jointure de ses projections sur {X, Y} et {X, Z}.

Par exemple, du fait de la DF {A} → {C}, R est décomposable en
R1 {A, C} et R2 {A, B, D, E}
Puis, du fait de la DF {A} → {D}, R2 est décomposable en R21 {A, D} et R22 {A, B, E}
Puis du fait de la DF {E} → {B}, R22 est décomposable en R221 {B, E} et R222 {A, E}

Mais si vous attaquez autrement, vous obtenez d’autres décompositions.
Par exemple, du fait de la DF {B,C} → {A}, R est décomposable en
R1’ {A, B, C} et R2’ {B, C, D, E}
Puis du fait de la DF {A} → {C}, R1’ est décomposable en R11’ {A, C} et R12’ {A, B}
Du fait des DF ayant même déterminant (partie gauche), R2’ est décomposable en R21’ {B, D, E} et R2’ {B, C}

Etc., etc.

Maintenant, si tout ceci n’a rien à voir avec la question posée, au moins connaîtrez-vous le théorème de Heath...

[boobs60]

ok merci beaucoup de vos explication. Elles sont vraiment bien construite.

En faite je ne sais pas à quoi correspond cette fermeture élémentaire.
Si sa peu aider je vais mettre un exemple corrigé. Sur celui ci j'arrive bien a retrouver mes clé candidate mais pas élé (F+)
Donc

soit un ensemble F = { A -> B ; BC -> E ; ED -> A }
Après calcul de la fermeture transitive F+ nous trouvons les clés candidates suivantes : { ACD ; BCD ; CDE }
Et la il y a marqué :
Nous allons maintenant calculer l'ensemble des dépendances élémentaire non-triviales à partir de F+.
élé (F+) = { A -> B ; AC -> E ; BC -> E ; DE -> A ; DE -> B ; BCD -> A }

Voila. Je vais essayer de faire un tour sur le web encore une fois mais si quelqu'un passe par la merci d'avance pour son aide.

Amicalement Boobs60

[boobs60]

ok donc j'ai trouvé mon bonheur pour élé (F+).
Maintenant il me reste encore pas mal de chose à voir. Je poste mais je regarde à coté sur le net sa me permet d'avoir sur ce forum des explications concrètent par rapport à mon exercice et sur le net le théorique. Malgré que je n'arrive pas souvent à bien comprend avec le théorique.

Donc je dois voir encore comment faire une couverture minimale.
Après j'ai une autre question qui est : R est elle en 3NF ? Pourquoi ? Sinon appliquer l'algorithme de mise en forme 3NF. R est elle en 3BCNF ? Pourquoi ? Sinon appliquer l'algorithme de mise en forme 3BCNF.

Donc comment reconnaitre l'une ou l'autre et comment l'expliquer. Mon problème est que sur internet je trouve des exemples mais directement avec des tuples d'une base de données. Je n'arrive pas à le mettre en application sur mon exercice.

[fsmrel]

Bonjour,

Soit un ensemble F = { A -> B ; BC -> E ; DE -> A }

élé (F+) = { A -> B ; AC -> E ; BC -> E ; DE -> A ; DE -> B ; BCD -> A }

Apparemment il s’agit de calculer la fermeture transitive de F, c'est-à-dire trouver l’ensemble des dépendances fonctionnelles non triviales inférables de F à partir des 2e et 3e règles d’Armstrong, à savoir les règles d’augmentation et transitivité.

Au départ, élé(F+) contient les dépendances fonctionnelles A -> B ; BC -> E ; ED -> A car aucune d’elles n’est triviale.

Ensuite, il faut, un peu à la manière d’un syllogisme, rechercher par transitivité de nouvelles DF :

Comme DE -> A et A -> B, par transitivité, DE -> B (par analogie, A joue le rôle du moyen terme dans un syllogisme).

Ensuite ça se corse (chef-lieu Ajaccio), on aimerait bien aller de A à E car B est partie droite de A -> B et appartient à la partie gauche de BC -> E, mais n’en est qu’un élément :
Il faut d'abord procéder par augmentation : De A -> B, on produit AC -> BC.

Comme BC -> E, par transitivité on produit AC -> E.

De même, comme E appartient à la partie droite de BC -> E et à la partie gauche de DE -> A, on aimerait bien aller de BC à A.

De BC -> E, par augmentation on produit BCD -> DE, et comme DE -> A, par transitivité on produit BCD -> A.

A vous de jouer.

[boobs60]

Merci infiniment j'ai enfin comprit. Donc maintenant par rapport à mon exercice de départ j'ai :
- R { A, B, C, D, E }
et
- F= {A→C, A→D, BC→A, E→B, E→D}.

J'ai comme clé candidate { AE , CE }
Je trouve donc en élé ( F+ ) = { A -> C ; A -> D ; E -> B ; E -> D; AE -> B ; BC -> A ; CE -> A }

Après sa on me demande de calculer une couverture minimale. Et on me demande si R est en 3NF et de dire pourquoi. Comment faire ces 2 étapes.

fsmrel je crois savoir que vous avez déjà répondu à ces questions sur un auter poste mais je ne le retrouve pas.

Merci.

Amicalement Boobs60

[fsmrel]

on me demande de calculer une couverture minimale.

Voir la discussion avec wotan2009 : http://www.developpez.net/forums/d86...s/#post4928839

[fsmrel]

par rapport à mon exercice de départ j'ai :
- R { A, B, C, D, E }
et
- F= {A→C, A→D, BC→A, E→B, E→D}.

J'ai comme clé candidate { AE , CE }
Je trouve donc en élé ( F+ ) = { A -> C ; A -> D ; E -> B ; E -> D; AE -> B ; BC -> A ; CE -> A }

Caveat :

Soit R une relation, X un sous-ensemble d’attributs de l’en-tête de R et A un attribut appartenant à cet en-tête.

Je rappelle que la DF X -> {A} est élémentaire si A n’est pas un élément de X (sinon la DF serait triviale) et s’il n’existe pas X’ strictement inclus dans X tel que X’ -> {A} (sinon la DF serait partielle).

Votre DF : AE -> B n’est pas élémentaire, mais partielle, car E -> B.

[boobs60]

OK donc du coup la DF AE -> B n'est pas à inclure dans les DF élémentaires.

Maintenant je viens de passer 2 bonne heures à regarder votre explication sur 3NF et 2NF et BCNF. Vous dites qu'il n'y a pas besoin de passer par la forme 3NF puisque si l'on prouve directement que R est en BCNF alors R est forcément en 3NF. Je suis totalement d'accord avec vous. Cependant dans mon exercice et probablement à l'examen la prof demandera si R est en 3NF. Malgré une lecture studieuse et appliqué de votre explication je n'arrive pas très bien à comprend. On me demande si R est en 3NF et sinon de le mettre en 3NF.

Je ne connais pas la marche à suivre.

J'ai chopé sur le net ceci :

3NF : Une relation est en 3NF si et seulement si pour toute dépendance élémentaire X -> A défini sur R on a : X n'est pas une clé candidate et A est une partie de clé.

3BCNF : Une relation R est en 3BCNF si et seulement si R est en 1NF et que les seuls DF élémentaires sont celle dans lequelles une clé détermine un attribut ( pour toute DF élémentaire X -> A, X est une clé de R)

Est ce bon ??

Donc d'après ceci, pour vérifier si R est en 3NF ou autre il nous faut utiliser R, la liste des DF F et la liste des clés candidates. Je ne suis pas du tout sur de sa.

En faite j'ai l'impression que pour savoir si c'est du 3NF ou BCNF il faut exécuter une décomposition. Je crois que c'est cette étape que je ne vois pas comment faire

[fsmrel]

Dans mon exercice et probablement à l'examen la prof demandera si R est en 3NF

D’accord.

Personnellement je préfère la définition de Zaniolo, notamment parce que si on élimine la condition 3 ci-dessous, on retrouve l’énoncé de la BCNF et d’autre part parce que l’on n’a pas besion de faire mention des dépendances fonctionnelles élémentaires et de la 2NF.

Définition de Zaniolo :

Soit R une relvar, X un sous-ensemble d’attributs de l’en-tête de R et A un attribut de cet en-tête. R est en troisième forme normale si et seulement si, pour chaque dépendance fonctionnelle X → {A} vérifiée dans R, au moins une des conditions suivantes est satisfaite :

1. Cette dépendance fonctionnelle est triviale (A est un élément de X).
2. X est une surclé de R.
3. A appartient à une clé candidate de R.

Mais on va se donner une définition antique, solennelle et néanmoins incontestable de la 3NF, celle du père de la théorie relationnelle, Ted Codd :

Une relation R est en troisième forme normale si elle est en deuxième forme normale et si chaque attribut n’appartenant à aucune clé candidate ne dépend directement que des clés candidates de R.

(« A relation R is in third form normal if it is in second normal form and every non-prime attribute of R is non-transitively dependant on each candidate key of R. »)

Du fait de cette définition, il faut prouver que la relation est en 2NF.

Définition de Codd :

Une relation R est en deuxième forme normale si elle est en première forme normale et si chaque attribut n’appartenant à aucune clé candidate de R est en dépendance totale de chaque clé candidate de R.

(« A relation R is in second form normal if it is in first normal form and every non-prime attribute of R is fully dependant on each candidate key of R. »)

Reprenons les éléments dont vous disposez :

R {A, B, C, D, E}

Clés candidates : {AE} et {CE}.

Dépendances fonctionnelles { A -> C ; A -> D ; E -> B ; E -> D; BC -> A ; CE -> A }

Considérons par exemple la dépendance fonctionnelle E -> B. L’attribut B dépend seulement partiellement de {AE} ou {CE} : la deuxième forme normale est violée. Il faut donc utiliser le théorème de Heath (dont je vous ai déjà parlé) pour éliminer l’anomalie. R est à décomposer en :

R1 {E, B} (avec la DF : E -> B et la clé candidate {E}).

R2 {A, C, D, E} (avec les clés candidates {AE} et {CE}, et les dépendances fonctionnelles :

{ A -> C ; A -> D ; E -> D; BC -> A ; CE -> A }

R1 respecte la 2NF, la 3NF, la BCNF, la 4NF, la 5NF (et même la 6NF...)

R2 : je vous laisse le soin de poursuivre le travail de décomposition.

[boobs60]

Merci infiniment. Je vais sans doute vous paraître un peut débile mais bon sa ne fait rien. Donc si j'ai bien comprit on décompose tant que Ri viole un 2NF.
Cependant, nous aurons donc une liste tel que :

R1 = {}
R2 =
R21 =
R22 =
R221 =
R222 =
...

Donc on va pouvoir dire que les Ri respecte la 2NF ou 3NF mais ce que je ne comprend pas c'est que moi on me demande si R est en 3NF. Donc si tout les Ri sont en 3NF alors R est en 3NF sinon il ne l'est pas ???

[fsmrel]

Donc on va pouvoir dire que les Ri respecte la 2NF ou 3NF mais ce que je ne comprend pas c'est que moi on me demande si R est en 3NF. Donc si tout les Ri sont en 3NF alors R est en 3NF sinon il ne l'est pas ???

J’ai écrit :

Considérons par exemple la dépendance fonctionnelle E -> B. L’attribut B dépend seulement partiellement des clés {AE} et {CE} : la deuxième forme normale est violée.

On est bien d’accord que c’est R qui viole la 2NF, donc la 3NF.
En revanche, à force de décomposer en appliquant le théorème de Heath, on arrivera à un ensemble de relations en 3NF. Ce qu’il faut savoir, c’est que la décomposition est sans perte, c'est-à-dire que par jointure des décompositions, on retrouve R.

Ainsi, j’ai montré que, grâce au théorème de Heath, R était décomposable en

R1 {E, B}

et

R2 {A, C, D, E}

Avec R = R1 JOIN R2.

R1 est en 3NF (vous pouvez le vérifier), mais R2 viole la 2NF et doit être décomposée en R21 et R22 :

R21 {E, D} (avec la DF : E -> D et la clé candidate {E}) : R21 est en 3NF (vous pouvez le vérifier).

R22 {A, C, E} (avec les DF : A -> C et CE -> A, et les clés candidates {AC} et {CE}). La DF : A -> C pose encore problème car son déterminant {A} n’est pas clé candidate : il faut poursuivre. A partir du théorème de Heath, R22 est décomposable en :

R221 {A, C} (avec la DF : A -> C et la clé candidate {A}) : R221 est en 3NF (vous pouvez le vérifier).

R222 {A, E} qui n’est pas décomposable, a pour clé candidate {AE} et respecte la 3NF (vérifiez).

La relation R qui viole outrageusement la 2NF (donc la 3NF) a été cassée en plein de morceaux (R1, R21, R221, R222) qui eux respectent la 3NF (et la même la BCNF et au delà), mais qui par jointure permettent de retrouver R qui n’est donc pas perdue, même si quelque part elle est devenue virtuelle :

R = R1 JOIN R21 JOIN R221 JOIN R222

Et on dit : Merci M. Heath ! (Qui a pondu son théorème en 1971...)

Il y a d’autres décompositions possibles, à vous de faire l’exercice.


Quand vous écrivez :

Donc si tout les Ri sont en 3NF alors R est en 3NF sinon il ne l'est pas ???

Parce que R est la jointure des Ri, automatiquement R viole la 3NF (et/ou la 2NF), vous pouvez le vérifier.

[fsmrel]

Bonsoir,


J’ai effectué quelques recherches concernant la fameuse «Fermeture élémentaire élé(F+) ». Via Internet : a priori, rien qui puisse nous aider. Par contre, en fouillant dans ma bibliothèque, j’ai retrouvé un ouvrage datant de 1982 et qui s’y intéresse de très près. Cet ouvrage — auquel je ferai référence sous le nom de [DELADI] — est intitulé Bases de données et systèmes relationnels (Dunod informatique) et on le doit à Claude Delobel et Michel Adiba, à l’époque tous deux professeurs à l’Université scientifique et médicale de Grenoble. Cet ouvrage fut publié avec le concours du C.N.R.S.

La fermeture élémentaire y est définie comme l’ensemble des dépendances fonctionnelles élémentaires appartenant à la fermeture F+ de l’ensemble F des dépendances fonctionnelles associé à R.

Dans votre cas :

R {A, B, C, D, E}
F = {A → C, A → D, BC → A, E → B, E → D}.

Et la fermeture transitive est la suivante :

ELE(F+) = {A → C, A → D, BC → A, E → B, E → D, BC → D, CE → A}

ELE(F+) est constituée des dépendances fonctionnelles appartenant à F (puisqu’elles y sont toutes élémentaires), plus les deux dépendances fonctionnelles inférées, celle que vous aviez découverte : CE → A, plus BC → D qui était passée au travers des mailles du filet. Cette dépendance fonctionnelle est du reste facile à inférer, car :

BC → A (donnée)
A → D (donnée)
BC → D (par transitivité).

Maintenant, on peut se poser la question de l’utilité de ELE(F+)...

En fait, [DELADI] montre que ELE(F+) peut donner lieu à plus d’une couverture minimale (qu’il appelle couverture irredondante, ce qui est du reste sémantiquement plus pertinent). Dans votre cas, il n’y en a qu’une, mais [DELADI] donne un exemple dans lequel la chose se produit.

Mais, quel intérêt à chercher toutes les couvertures minimales ? Pour [DELADI], cela permet de découvrir différents schémas de relations normalisables en 3NF.

Ainsi, [DELADI] propose la variable relationnelle

R {P, T, H, Y, N}

A laquelle on associe l’ensemble F de dépendances fonctionnelles

F = {P → T, PH → Y, HN → P, HY → N}

R représente l’emploi du temps dans une école. P symbolise le professeur, H l’heure, N la salle, Y la classe, T la matière enseignée. D’après F, un professeur n’enseigne qu’une matière ; à une heure donnée il ne peut enseigner qu’à une seule classe ; dans une salle donnée, à une heure donnée on ne peut trouver qu’un professeur ; à une heure donnée, une classe donnée ne peut se trouver que dans une salle. Bref, des problèmes de bilocation à surveiller.

Par calcul on obtient

ELE(F+) = {P → T, PH → Y, HN → P, HY → N, PH → N, HN → Y, HY → P, HN → T, HY → T}

Ayant pour couvertures minimales :

F1 = {P → T, PH → Y, HN → P, HY → N} (c'est-à-dire F)

Et

F2 = {P → T, PH → N, HN → Y, HY → P}

Ce qui fait que par décomposition, on peut produire des schémas relationnels (en 3NF ou en BCNF si on préfère) différents selon que l’on part de F1 ou de F2. Quoi qu’il en soit, que l’on normalise ou non, l’essentiel est de préserver les règles de gestion qu’expriment les dépendances fonctionnelles, au besoin à l’aide contraintes (assertions de la norme SQL, ou triggers si votre SGBD ne propose pas l’instruction CREATE ASSERTION).

[boobs60]

bonsoir tout le monde.

Et oui c'est encore moi et sur le même sujet en plus.
Donc toujours dans l'espoir de comprendre, j'aimerais que l'on m'explique la décomposition pour mettre en 3NF.

En faite fsmrel m'avait répondu mais je n'ai pas comprit car pour que R soit en 3NF il faut que chaque relation X -> A de R respect au moins une des 3 conditions suivantes :
- A est un élément de X
- X est une super clé de R
- A est une partie de clé candidate.

le problème c'est que d'après fsmrel il dit que la relation A -> C pose problème car A n'est pas clé candidate. Mais quand je regarde les conditions que dois respecter la 3NF je ne vois pas cette dernière. De plus la relation A -> C respecte au moins une des conditions de la 3NF, celle qui dit que A doit être une partie de clé. ICI, mes clés candidates sont AE et CE donc on vois bien que C fait partie de CE donc normalement A -> C est en 3NF.

Donc voilà si quelqu'un passe par la et peut éclairer ma lanterne.

Merci d'avance.

Amicalement boobs60

[fsmrel]

Bonsoir boobs,

si quelqu'un passe par la et peut éclairer ma lanterne.

C'est un plaisir de vous revoir. Je passais par là et il y avait de la lumière...

mes clés candidates sont AE et CE donc on vois bien que C fait partie de CE donc normalement A -> C est en 3NF.

R {A, B, C, D, E} ne respecte pas la 3NF.

En effet, s’il est exact que la DF {A}->{C} n’est pas délinquante, ses petites sœurs {A}->{D}, {E}->{B} et {E}->{D} ne sont peut-être pas innocentes et méritent que vous enquêtiez à leur sujet...

Dans l’énoncé de la 3NF il est bien précisé que chaque DF doit vérifier une des 3 conditions. Vous avez raisonné sur la base d’au moins une DF, ce qui n’est quand même pas la même chose...

N.B. Attention au vocabulaire, vous confondez "DF" (qui est une contrainte) avec "relation" (qui dans le contexte est une variable, même si ce terme représente plutôt une valeur dans le cadre de la théorie relationnelle).

[boobs60]

Merci beaucoup de votre réponse.

En effet après une relecture du cours que vous m'avez enseigné j'ai compris. J'ai été plutôt long à la détente mais j'ai fini par y arriver.

Je vous remercie fsmrel pour le temps que vous m'avez accordé et de l'enseignement que vous m'avez apporté.
Ce cour fut très instructif.

Amicalement Boobs60.