Discussion :

[gudina]

Bonjour,

Je découvre l'univers des formes normales, et je m'y perds un peu dans tout ce que j'ai pu lire.
Quelques éclaircissements et/ou confirmation sur certains problèmes m'aideront sans doute :

1/ Soit la relation R[A B C D] et les dépendances F{A->B , B->A , B->D}

• La recherche d'une couverture minimale ne m'avait jusque-là jamais posé de problème car j'ai toujours rencontré des cas où tous les attributs étaient présents dans les DF. Or ici il n'y a pas C... Comment ça marche dans ce cas ?
  
  
• Pour trouver les clés d'une relation, faut-il partir d'une couverture minimale ? Avec les DF données ici, les clés seraient AC et BC.
  
  
• À supposer que les clés soient bien AC et BC, la relation serait en 1FN. D ne dépendant que d'une partie de la clé BC.
  
  
• Sur ce même énoncé, un corrigé donné pour la décomposition SPI est : [AB] (pour les dépendances A->B et B->A), [BD] (pour la dépendance B->D) et [AC] pour la clé.
  Le tout est simplifié en [ABD] et [AC]. Si je ne m'abuse, les 2 sont en FNBC.
  => Est-il correct de simplifier en [ABC] et [BD] ? Il me semble que oui, les DF sont préservées et il n'y a pas de perte de données.
  Mais [ABC] est-elle en FNBC ? Les clés sont encore [AC] et [BC], donc tous les attributs sont clés, mais aucun seul n'est surclé. Du coup on serait en 3FN...

2/Soit la fameuse relation [CPHSEN] souvent donnée en exemple, avec les DF {C->P, HS->C, HP->S, CE->N, HE->S}

• Elle est bien en 1FN ?
  Selon moi, la clé de cette relation est HE, et donc P par exemple ne dépend pas de la clé, donc la relation n'est pas 2FN.
  
  
• Y-a-t-il une méthode conseillée pour la décomposition en FNBC ? Du genre simplement prendre les DF dans leur ordre (arbitraire) d'apparition, ou les attributs, ou commencer pas la/les clé(s), ou encore par les DF ayant plusieurs attributs à gauche ?
  
  
• La décomposition [CP] [CHS] [HSEN] est donnée pour FNBC mais je ne comprends pas comment [HSEN] est FNBC... La seule DF qui s'applique à cette relation est HE->S. La clé est donc HEN, non ? Du coup S ne dépend que d'une partie de la clé. Mais je sens que je me trompe sur ce raisonnement...
  
  
• Comme on a HS->C et C->P, et que donc par transitivité HS détermine P, je présume que l'on ne peut pas commencer une décomposition FNBC par [HSC] et [CPHEN] ? (si je suis le niveau b)iii) de l'algorithme ci-après)
  
  
• Soit l'algorithme de décomposition en FNBC suivant (d'un livre de Abiteboul, Hull et Vianu):
  Donnée : un schéma de relation (U,∑), où ∑ est un ensemble de df
  Résultat : un schéma de BD (R,Γ) sous forme FNBC
  1. Posons (R,Γ) := {(U,Σ)}
  2. Répéter jusqu'à ce que (R,Γ) soit sous FNBC
  
  a) Choisir un schéma de relation (S[V],Ω)∈ R qui n'est pas sous FNBC
  b) Choisir des sous ensembles non vides disjoints X,Y,Z ⊂ V tels que :
  (i) XYZ=V ;
  (ii) Ω ⊨ X→Y ;
  (ii) Ω ⊭X→A pour tout A ∈ Z
  c) Remplacer (S[V],Ω) de R par (S1[XY], ΠXY(Ω)) et (S2[XY], ΠXZ(Ω))
  S'il existe (S[V],Ω),(S'[V'],Ω') de R avec V ⊆ V', alors enlever (S[V],Ω) de R
• En suivant cet algorithme, j'obtiens diverses décompositions, dont certaines avec pertes de données.
  
  • Par exemple : [CPHSEN] (avec HP->S) => [HPS] [HPCEN]
    puis [HPCEN] (avec C->P) => [CP] [CHEN]
    
  • Celle-ci semble bonne : [CPHSEN] (avec CE->N)=>[CEN] [CEPHS]
    puis [CEPHS] (avec C->P) => [CP] [CEHS]

Merci par avance pour votre aide !

[fsmrel]

Bonjour Gudina,

La recherche d'une couverture minimale ne m'avait jusque-là jamais posé de problème car j'ai toujours rencontré des cas où tous les attributs étaient présents dans les DF. Or ici il n'y a pas C... Comment ça marche dans ce cas ?

En ce qui concerne la recherche d'une couverture minimale (ou couverture irréductible pour être plus précis), une des deux tâches est de rendre irréductibles les déterminants (parties gauches) des DF. Comme les déterminants des DF en cause sont des singletons (mono-attributs), il n’y a rien à gratter de ce côté-là, les DF sont irréductibles à gauche. La 2e tâche est d’éliminer les DF qui peuvent l’être (inférables des autres). Dans le cas présent, aucune DF ne peut être inférée des autres. Conclusion : la couverture minimale est égale à l’ensemble des DF initial. Dans tout ça, on n’a jamais eu à se préoccuper de C (qui n'est source que de DF triviales) et ça marche très bien.

Pour trouver les clés d'une relation, faut-il partir d'une couverture minimale ?

Ça n’est pas une mauvaise chose mais ça n’est pas une obligation. L’objet de la couverture minimale est d’éliminer les DF qui peuvent l’être, donc par contrecoup de soulager le SGBD quand on traduit ces DF sous forme de contraintes (assertions et triggers SQL par exemple). Cela peut aussi permettre de réduire le temps de recherche des clés : autrement dit, si l’on dispose d’une couverture, tant mieux, mais le travail de mise en évidence d’une couverture peut être passablement rebutant et fastidieux (et en plus il peut y en avoir plusieurs) à moins de s’être développé un programme de calcul ad-hoc...

À supposer que les clés soient bien AC et BC, la relation serait en 1FN. D ne dépendant que d'une partie de la clé BC.

Je suppose que vous voulez dire que la relation (ou plutôt la variable relationnelle, car une relation est une valeur) est seulement en 1FN, ce qui est le cas : en effet la 2FN est violée du fait que {D} ne dépend — comme vous le faites observer— que d’une partie de la clé {B, C}.

Le tout est simplifié en [ABD] et [AC]. Si je ne m'abuse, les 2 sont en FNBC.

Exact, vous ne vous abusez pas ! Mais soyez plus affirmative.

Est-il correct de simplifier en [ABC] et [BD] ? Il me semble que oui, les DF sont préservées et il n'y a pas de perte de données.

La décomposition en {A, B, C} et {B, D} est correcte (notez que j’utilise des accolades plutôt que des crochets, car une relation est un ensemble). Comme vous n’avez pas l’air très sûre de votre fait, il est temps de faire référence au théorème de Heath pour ce qui concerne la préservation des données :
Par application de ce théorème, puisque {B} → {D}, la variable {A, B, C, D} est décomposable sans perte de données en {A, B, C} et {B, D}. Voyez aussi la variante décrite ici.

En ce qui concerne la préservation des DF, vous pouvez vous servir de l’algorithme de Beeri et Honeyman, repris par Ullman et que j’illustre ici. En l’occurrence on montre que les DF sont préservées.

Mais [ABC] est-elle en FNBC ?

Il existe la DF {A} → {B}, mais comme {A} n'est pas clé la BCNF est donc violée.

Du coup on serait en 3FN

Ça n’est parce que la BCNF est violée que la 3NF est respectée ! Le respect de la 3NF ça se démontre...
Pour éviter de perdre du temps en démontrant d’abord que la 2NF est respectée, vous pouvez utiliser la définition de Zaniolo de la 3NF.


Je vais jeter un coup d’œil aux problèmes que vous pose la bête CPHSEN...

[gudina]

Exact, vous ne vous abusez pas ! Mais soyez plus affirmative.

Désolée, cela montre juste à quel point je ne suis pas sûre de moi... Quand je crois l'être, je tombe sur quelque chose qui me fait douter !

Ça n’est parce que la BCNF est violée que la 3NF est respectée ! Le respect de la 3NF ça se démontre...
Pour éviter de perdre du temps en démontrant d’abord que la 2NF est respectée, vous pouvez utiliser la définition de Zaniolo de la 3NF.

Ok, donc si je reprends la définition de Zaniolo :

• J'ai la relvar {A,B,C} et les 2 dépendances fonctionnelles : {A} -> {B} et {B} -> {A}
• Les clés candidates sont AC et BC
• {A} et {B} appartiennent chacun à une clé candidate de la relvar, donc ils respectent la condition 3 de la définition

La relvar est donc en 3FN.

Je vais jeter un coup d’œil aux problèmes que vous pose la bête CPHSEN...

Merci déjà beaucoup pour la 1ère partie fsmrel. Ça m'aide bien. Pour le reste, ce qui me gêne le plus c'est que dans les solutions proposées à droite à gauche pour cet exercice, en appliquant les méthodes pour vérifier la préservation des données, j'arrive à une perte de données la plupart du temps. Et du coup je ne comprends pas que la décomposition en question soit dite FNBC ou 3FN.
Pour vérifier la préservation des données, j'ai appliqué (R1 R2) ➔ (R1 — R2) ou (R1 R2) ➔ (R2 — R1).
J'ai également essayé en utilisant la méthode avec le tableau, et j'obtiens (de manière logique) le même résultat (sauf si on peut éventuellement repasser plusieurs fois avec la même DF).

Pas facile d'être autodidacte...

[fsmrel]

Bonsoir Gudina,

Ok, donc si je reprends la définition de Zaniolo :
J'ai la relvar {A,B,C} et les 2 dépendances fonctionnelles : {A} -> {B} et {B} -> {A} [...] La relvar est donc en 3FN.

La relvar respecte effectivement la 3FN, mais permettez-moi de pinailler car la BCNF mérite qu’une extrême rigueur soit au rendez-vous. Il serait préférable d’écrire :
les 2 dépendances fonctionnelles : {A} -> {B} et {B} -> {A} sont les seules qui ne sont pas triviales . Il existe en effet d’autres DF, par exemple {A, C} -> {C}, mais elles sont toutes triviales et ne sont donc pas perturbatrices pour le respect de la BCNF selon l’énoncé qu’en donne Zaniolo.

ce qui me gêne le plus c'est que dans les solutions proposées à droite à gauche pour cet exercice, en appliquant les méthodes pour vérifier la préservation des données, j'arrive à une perte de données la plupart du temps.

Si vous vous servez du théorème de Heath vous n’aurez pas de perte de données. En revanche, vous pouvez perdre des DF si vous décomposez à tout crin sans tenir compte de la règle de Rissanen.

Pour vérifier la préservation des données, j'ai appliqué (R1 ∩ R2) ➔ (R1 — R2) ou (R1 ∩ R2) ➔ (R2 — R1).

Ça n’est jamais que la version académique du théorème de Heath, lequel est ce qui convient finalement le mieux d’un point de vue pratique.



Concernant CPHSEN.

Elle est bien en 1FN ?

Elle l’est par définition, sinon CPHSEN ne serait pas une relvar (et ses valeurs ne seraient pas des relations).

Selon moi, la clé de cette relation est HE, et donc P par exemple ne dépend pas de la clé, donc la relation n'est pas 2FN.

La paire d’attributs {H, E} est effectivement clé (et c’est la seule). Or une clé détermine fonctionnellement chaque attribut de sa relvar, {P} dépend donc fonctionnellement de {H, E}¹ : {H, E} → {P} contrairement à ce que vous avez écrit. Pour que la 2FN soit violée, il faudrait qu’il existe au moins une DF non triviale dont le déterminant (partie gauche) soit {H} ou {E}, or une telle DF n’existe pas : contrairement à ce que vous avez écrit la 2FN est respectée.

¹ On peut montrer que {H, E} → {P} au moyen des axiomes d’Armstrong :

1. {H, E} → {S} (donné),
2. {H, E} → {S, H} (1 et augmentation),
3. {S, H} → {C} (donné),
4. {H, E} → {C} (2, 3 et transitivité),
5. {C} → {P} (donné),
6. {H, E} → {P} (4, 5 et transitivité).

Y-a-t-il une méthode conseillée pour la décomposition en FNBC ?

Oui. La méthode la plus simple et pragmatique consiste à tenir compte de la règle de Rissanen qui binôme avec le théorème de Heath et dont l’objet est de rappeler qu’il faut privilégier la séquence des décompositions selon laquelle on ne perd pas de DF en toute inconscience (une DF est quand même l’expression d’une règle de gestion des données...) Ainsi dans le cas de CPHSEN, l’attribut N n’appartient à aucun déterminant de DF, donc si l’on suit Rissanen, on appliquera le théorème de Heath en commençant avec la DF {C, E} → {N}, puisqu’en l’occurrence aucune DF n’est perdue.

Ainsi CPHSEN est décomposable sans perte de données et sans perte de DF en CEN et CPHSE :

CEN = {C, E, N} ; CPHSE = {C, P, H, S, E}.

CPHSE est-elle décomposable ? Sans perte de données, oui, grâce au théorème de Heath, mais pas sans perte de DF : la décomposition n’est pas recommandée, mais s’il faut s’y résoudre, on commencera par ce qui fait le moins de dégâts... Ainsi, décomposer CPHSE en HPS et CPHE fait perdre deux DF d’un coup (même chose si l’on décompose CPHSE en HES et CPHE) tandis que décomposer CPHSE en CP et CHSE ne fait perdre qu’une DF (même chose si l’on décompose CPHSE en HSC et PHSE), ce qui est moins répréhensible du point de vue des tribunaux relationnels, mais passible quand même d’une réprimande...

Heureusement, dans la réalité de la modélisation des bases de données ces choix sont rares (en tout cas, c’est mon constat après vingt-cinq ans de traque des viols de BCNF et au-delà, dans tous les secteurs d’activité...)

La décomposition [CP] [CHS] [HSEN] est donnée pour FNBC mais je ne comprends pas comment [HSEN] est FNBC... La seule DF qui s'applique à cette relation est HE->S. La clé est donc HEN, non ? Du coup S ne dépend que d'une partie de la clé. Mais je sens que je me trompe sur ce raisonnement...

Qui a donné la décomposition comme respectant la BCNF ? Des noms ! La relvar HSEN la viole, puisque, comme vous dites, {H, E, N} est clé candidate (non réductible donc) de la relvar, en vertu de quoi la paire {H, E} qui en est un sous-ensemble strict et qui est le déterminant de la DF {H, E} → {S} n’est pas clé candidate, a fortiori surclé : la BCNF est violée. Vous ne vous êtes pas trompée...

Comme on a HS->C et C->P, et que donc par transitivité HS détermine P, je présume que l'on ne peut pas commencer une décomposition FNBC par [HSC] et [CPHEN] ?

Par application du théorème de Heath, à partir de la DF {H, S} → {C} vous produisez la relvar HSC, auquel cas son binôme est PHSEN mais pas CPHEN.

En suivant cet algorithme, j'obtiens diverses décompositions, dont certaines avec pertes de données.

Personnellement je me contente du théorème de Heath et de la règle de Rissanen. Quoi qu'il en soit, à partir de {H, P} → {S}, votre décomposition de CPHSEN en HPS = {H, P, S} et HPCEN = {H, P, C, E, N}, préserve les données. En revanche elle ne préserve pas les DF {H, E} → {S} et {H, S} → {C}. Passons par exemple la DF {H, E} → {S} à la moulinette de l’algorithme de Beeri et Honeyman.

Soit S l’ensemble initial des DF :

S = { {C} → {P}, {H, S} → {C}, {H, P} → {S}, {C, E} → {N}, {H, E} → {S} }

Soit G l’ensemble qui est l’union des décompositions proposées :

G = {HPS, HPCEN}

On veut vérifier si la DF {H, E} → {S} est préservée.

1re itération :

Z = {H, E} (déterminant de la DF)

Puis (en faisant participer le 1er élément de G, à savoir HPS) :

Z = {H, E} ∪ (({H, E} ∩ {H, P, S})⁺ ∩ {H, P, S})
Z = {H, E} ∪ ({H}⁺ ∩ {H, P, S})
Z = {H, E} ∪ {H}
Z = {H, E} (on n’a pas gagné grand-chose...)

2e itération (en faisant participer le 2e élément de G, à savoir HPCEN) :

Z = Z ∪ (({H, E} ∩ {H, P, C, E, N})⁺ ∩ {H, P, C, E, N})
Z = {H, E} ∪ ({H, E}⁺ ∩ {H, P, C, E, N})
Z = {H, E} ∪ ({H, E, S, C, P, N} ∩ {H, P, C, E, N})
Z = {H, E} ∪ {H, E, C, P, N}
Z = {H, E, C, P, N}

On a exploité tous les éléments de G : on a terminé. Pour que la DF {H, E} → {S} soit préservée, il faut que le dépendant {S} de la DF appartienne à Z, or ça n’est pas le cas : la décomposition de CPHSEN en HPS = {H, P, S} et HPCEN = {H, P, C, E, N} ne préserve pas la dépendance. De la même façon on peut vérifier que la DF {H, S} → {C} n’est pas préservée.

En ce qui concerne la décomposition de HPCEN = {H, P, C, E, N} en CEN = {C, E, N}, CP = {C, P} et CEHS = {C, E, H, S} : on peut vérifier que la DF {H, E} → {S} n’est pas préservée. La décomposition est moins peccamineuse que la précédente car on ne perd qu’une DF au lieu de deux, mais ça n’est pas l’idéal...


N.B. Pour mémoire et à toutes fins utiles, l’ensemble S des DF de la relvar CPHSEN représente une couverture minimale (démonstration pas bien compliquée).


J'espère que mes commentaires vous ont été utiles et ne vous ont pas traumatisée plus que cela...

[gudina]

Bonjour fsmrel,

La paire d’attributs {H, E} est effectivement clé (et c’est la seule). Or une clé détermine fonctionnellement chaque attribut de sa relvar, {P} dépend donc fonctionnellement de {H, E} : {H, E} → {P} contrairement à ce que vous avez écrit. Pour que la 2FN soit violée, il faudrait qu’il existe au moins une DF non triviale dont le déterminant (partie gauche) soit {H} ou {E}, or une telle DF n’existe pas : contrairement à ce que vous avez écrit la 2FN est respectée.

D'accord, j'avais mal compris pour la définition de la 2FN. Je pensais que par exemple avec la DF {C, E} → {N}, l'attribut {N} ne dépendait que d'une partie de la clé {H,E} puisque que {H} n'est pas dans le déterminant. Mais ce que vous dites me saute maintenant aux yeux : « Or une clé détermine fonctionnellement chaque attribut de sa relvar. » C'est tellement évident !
Donc pour que la 2FN soit violée ici, il faudrait qu'il y ait une DF (non triviale) avec pour déterminant seulement {H} ou {E}.

Ainsi CPHSEN est décomposable sans perte de données et sans perte de DF en CEN et CPHSE :

CEN = {C, E, N} ; CPHSE = {C, P, H, S, E}.
[...]
décomposer CPHSE en CP et CHSE ne fait perdre qu’une DF

Je ne suis toujours pas sûre de moi question FNBC...
Si on prend la relvar CHSE issue de la décomposition (réprimandable) ci-dessus, elle est en FNBC ?
La clé est la paire {H,E} et l'on a les DF {H, S} → {C} et {H, E} → {S}.
Si je reprends les énoncés de la FNBC (Date ou Zaniolo) :
- pour la DF non triviale {H, E} → {S}, {H,E} est clé, donc surclé, donc ok pour FNBC
- pour la DF non triviale {H, S} → {C}, {H,S} n'est pas clé, ni surclé, donc la relvar n'est pas FNBC... Si ?

Qui a donné la décomposition comme respectant la BCNF ? Des noms !

Honnêtement, j'en ai lu tellement que je ne sais plus ! ;-)

Passons par exemple la DF {H, E} → {S} à la moulinette de l’algorithme de Beeri et Honeyman.

Soit S l’ensemble initial des DF :

S = { {C} → {P}, {H, S} → {C}, {H, P} → {S}, {C, E} → {N}, {H, E} → {S} }

Soit G l’ensemble qui est l’union des décompositions proposées :

G = {HPS, HPCEN}

On veut vérifier si la DF {H, E} → {S} est préservée.

1re itération :

Z = {H, E} (déterminant de la DF)

Puis (en faisant participer le 1er élément de G, à savoir HPS) :

Z = {H, E} ∪ (({H, E} ∩ {H, P, S})⁺ ∩ {H, P, S})
Z = {H, E} ∪ ({H}⁺ ∩ {H, P, S})
Z = {H, E} ∪ {H}
Z = {H, E} (on n’a pas gagné grand-chose...)

2e itération (en faisant participer le 2e élément de G, à savoir HPCEN) :

Z = Z ∪ (({H, E} ∩ {H, P, C, E, N})⁺ ∩ {H, P, C, E, N})
Z = {H, E} ∪ ({H, E}⁺ ∩ {H, P, C, E, N})
Z = {H, E} ∪ ({H, E, S, C} ∩ {H, P, C, E, N})
Z = {H, E} ∪ {H, E, C}
Z = {H, E, C}

Je ne comprends pas pourquoi, dans la 2e itération, {H, E}⁺ donne seulement {H, E, S, C} et pas {H, E, S, C, P, N}

J'espère que mes commentaires vous ont été utiles et ne vous ont pas traumatisée plus que cela...

Très utiles, et je ne suis pas du tout traumatisée (enfin pas par vos réponses, plus par le sujet) ! Au contraire, vous me sauvez la vie (avec à peine d'exagération).

Les cours/tutoriels c'est bien, mais rien ne vaut une bonne explication derrière... un prof quoi !

Merci encore

[fsmrel]

Bonjour Gudina,

Donc pour que la 2FN soit violée ici, il faudrait qu'il y ait une DF (non triviale) avec pour déterminant seulement {H} ou {E}.

Voui ! Mais supprimez les parenthèses, l’expression « non triviale » doit être renforcée et mise en avant.

pour la DF non triviale {H, S} → {C}, {H, S} n'est pas clé, ni surclé, donc la relvar n'est pas FNBC... Si ?

Inutile de chercher à porter secours à la pauvre relvar CHSE : la DF {H, S} → {C} n’est pas triviale et le déterminant {H, S} n’est pas surclé : la relvar n’est donc pas FNBC, c’est irrémédiable.

Je ne comprends pas pourquoi, dans la 2e itération, {H, E}⁺ donne seulement {H, E, S, C} et pas {H, E, S, C, P, N}

Bien vu œil de lynx. Manifestement P et N sont tombés du camion au cours d’un copier/coller intempestif... Je procède en conséquence à la correction de mon message d’hier (merci de vérifier qu’il ne traîne pas d’autre coquille de ce genre...)

Les cours/tutoriels c'est bien, mais rien ne vaut une bonne explication derrière... un prof quoi !

A ceci près que je ne suis pas prof et que je n’ai jamais suivi le moindre cours sur le sujet, je ne suis qu’un autodidacte de la modélisation et de la normalisation des bases de données... En tout cas, un jour ça sera votre tour de donner les bonnes explications.

[gudina]

Bonjour fsmrel

Inutile de chercher à porter secours à la pauvre relvar CHSE : la DF {H, S} → {C} n’est pas triviale et le déterminant {H, S} n’est pas surclé : la relvar n’est donc pas FNBC, c’est irrémédiable.

Ouf, j'ai quand-même compris quelques trucs !

Bien vu œil de lynx. Manifestement P et N sont tombés du camion au cours d’un copier/coller intempestif... Je procède en conséquence à la correction de mon message d’hier (merci de vérifier qu’il ne traîne pas d’autre coquille de ce genre...)

Forcément, si on me tend des pièges au milieu, je ne vais pas m'en sortir
Je n'ai pas vu d'autre coquille, mais je ne suis sans doute pas le meilleur oeil pour les voir.

A ceci près que je ne suis pas prof et que je n’ai jamais suivi le moindre cours sur le sujet, je ne suis qu’un autodidacte de la modélisation et de la normalisation des bases de données... En tout cas, un jour ça sera votre tour de donner les bonnes explications.

C'était juste une façon de parler ;-)

Aller, une petite dernière pour la route, et après je devrais être parée pour quelques temps.

Dans un document d'exercices avec corrections, on donne R{A,B,C,D} et les DF {A}-->{B} , {B}-->{C} , {A}-->{D} , {D}-->{C}.

La décomposition suivante est donnée comme décomposition en 3FN sans perte d'informations : {A,B,D} {B,C} {D,C}

Alors je suis d'accord, les DF sont toutes préservées, mais pour qu'il en soit de même des données, il faudrait que :

• {B,C} ∩ {D,C} --> {B,C} - {D,C} soit {C} --> {B}
• ou {B,C} ∩ {D,C} --> {D,C} - {B,C} soit {C} --> {D}

et je ne vois pas comment retrouver ces DF à partir des DF initiales...
Je ne vois pas de manière générale comment déduire une DF du type {A}-->{B} à partir d'autres DF dans lesquelles {A} n'apparait que dans la partie droite.
Alors c'est moi qui suis une bille en axiomes d'Armstrong, ou le document qui est erroné ? (j'espère que vous allez me dire que je ne suis pas une bille )

Merci encore fsmrel !

[gudina]

En fait non, je ne suis pas du tout parée.
J'essaye de décomposer la relvar {C,P,H,S,E,N} que je donnais en exemple, en 3FN ou FNBC, et même en appliquant le théorème de Heath, soit je me retrouve au mieux avec une décomposition en 2FN, soit je n'arrive pas à prouver que la décomposition obtenue est sans perte de données...
Grrrr !

[fsmrel]

Bonjour Gudina,

on donne R{A, B, C, D} et les DF {A}-->{B} , {B}-->{C} , {A}-->{D} , {D}-->{C}.

La décomposition suivante est donnée comme décomposition en 3FN sans perte d'informations : { {A, B, D} {B, C} {D, C} }

Alors je suis d'accord, les DF sont toutes préservées, mais pour qu'il en soit de même des données, il faudrait que :

• {B ,C} ∩ {D, C} --> {B, C} - {D, C} soit {C} --> {B}
• ou {B, C} ∩ {D, C} --> {D, C} - {B ,C} soit {C} --> {D}

et je ne vois pas comment retrouver ces DF à partir des DF initiales...

Et vous n’y arriverez pas...

En effet, le procédé que vous utilisez ne vaut que pour le cas particulier des décompositions possédant exactement deux éléments, alors qu’ici il y en a trois... Vous tentez une vérification sur la base de la seule décomposition D = { {B, C}, {C, D} }, ce qui, en l’absence de {A, B, D}, est évidemment mission impossible.

Puisque la décomposition comporte plus de deux éléments, on se sert de l’algorithme dû à Aho, Beeri et Ullman et qui met en jeu des tableaux.

Reprenons votre relvar R{A, B, C, D} et la décomposition D = { {A, B, D} {B, C} {D, C} }. Les en-têtes des relvars {A, B, D}, {B, C} et {D, C} figurent en lignes et les attributs de R figurent en colonnes dans le tableau suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
           |   A   |   B   |   C   |   D   |
-----------|-------|-------|-------|-------|
 {A, B, D} |       |       |       |       |
           |       |       |       |       |
 {B, C}    |       |       |       |       |
           |       |       |       |       |
 {D, C}    |       |       |       |       |
           |       |       |       |       |

Vous noterez que {A, B, D} est en bonne place ! Les noms d’attribut figurant à l’intersection de la ligne i et de la colonne j sont symbolisés sous la forme aj :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
           |   A   |   B   |   C   |   D   |
-----------|-------|-------|-------|-------|
 {A, B, D} |  a1   |  a2   |       |  a4   |
           |       |       |       |       |
 {B, C}    |       |  a2   |  a3   |       |
           |       |       |       |       |
 {D, C}    |       |       |  a3   |  a4   |
           |       |       |       |       |

Les noms d’attribut ne figurant pas à l’intersection de la ligne i et de la colonne j sont symbolisés sous la forme bij :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
           |   A   |   B   |   C   |   D   |
-----------|-------|-------|-------|-------|
 {A, B, D} |       |       |  b13  |       |
           |       |       |       |       |
 {B, C}    |  b21  |       |       |  b24  |
           |       |       |       |       |
 {D, C}    |  b31  |  b32  |       |       |
           |       |       |       |       |

D’où le tableau (aux erreurs de copier/coller près) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
           |   A   |   B   |   C   |   D   |
-----------|-------|-------|-------|-------|
 {A, B, D} |  a1   |  a2   |  b13  |  a4   |
           |       |       |       |       |
 {B, C}    |  b21  |  a2   |  a3   |  b24  |
           |       |       |       |       |
 {D, C}    |  b31  |  b32  |  a3   |  a4   |
           |       |       |       |       |

Ceci posé, on fait intervenir les dépendances fonctionnelles pour transformer les bij en aj. Si deux (ou plusieurs lignes) contiennent le même symbole dans une colonne et si cette colonne correspond au déterminant d’une DF, alors la colonne correspondant au dépendant peut comporter à son tour un même symbole (le principe est valable pour un nombre quelconque de colonnes, c'est-à-dire quand le déterminant de la DF est multi-attributs).

Plus précisément considérons la DF {B} -> {C} : la 2e et la 3e colonnes du tableau correspondent respectivement au déterminant et au dépendant de la DF ; comme le symbole a2 (correspondant au déterminant de la DF) est présent en colonne 2, lignes 1 et 2, le symbole b13 de la ligne 1, colonne 3 peut être remplacé par le symbole de la ligne 2, colonne 3, c'est-à-dire a3 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
           |   A   |   B   |   C   |   D   |
-----------|-------|-------|-------|-------|
 {A, B, D} |  a1   |  a2   |  a3   |  a4   |
           |       |       |       |       |
 {B, C}    |  b21  |  a2   |  a3   |  b24  |
           |       |       |       |       |
 {D, C}    |  b31  |  b32  |  a3   |  a4   |
           |       |       |       |       |

Le but de la manœuvre est d’arriver à produire au moins une ligne contenant seulement des ai, auquel cas on a aura prouvé que la décomposition est sans perte de données. De fait, la 1re ligne du tableau ne contenant que des ai, la décomposition (ABD, BC, DC) est bien sans perte de données.

Vous conviendrez qu’en vous limitant à la paire { {B, C}, {C, D} } c’est mission impossible, vous en resteriez désespérément à :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
           |   A   |   B   |   C   |   D   |
-----------|-------|-------|-------|-------|
 {B, C}    |  b21  |  a2   |  a3   |  b24  |
           |       |       |       |       |
 {D, C}    |  b31  |  b32  |  a3   |  a4   |
           |       |       |       |       |

Maintenant, si vous êtes pressée, pour prouver que la décomposition de R qui vous est donnée est bien en 3FN et sans perte de quoi que ce soit, vous pouvez utiliser l’algorithme très efficace de Bernstein permettant de produire une décomposition en 3NF qui préserve les données (c'est-à-dire l’information) ainsi que les dépendances fonctionnelles, voyez ci-dessous son application à la relvar CPHSEN.

En fait non, je ne suis pas du tout parée.
J'essaye de décomposer la relvar {C,P,H,S,E,N} que je donnais en exemple, en 3FN ou FNBC, et même en appliquant le théorème de Heath, soit je me retrouve au mieux avec une décomposition en 2FN, soit je n'arrive pas à prouver que la décomposition obtenue est sans perte de données...
Grrrr !

Faut pas grogner ! Zorro Bernstein va vous aider...


Mais avant cela, finissons le travail de normalisation en BCNF que vous aviez entrepris avec la relvar CPHSEN = {C, P, H, S, E, N}. Vous aviez produit la décomposition suivante (cf. votre 1er message) :

D1 = {CEN, CP, CEHS}

Avec CEN = {C, E, N}, CP = {C, P}, CEHS = {C, E, H, S}.

La relvar CEHS viole la BCNF car elle comporte la DF {H, S} -> {C} dont le déterminant {H, S} n’est pas clé candidate. En appliquant le théorème de Heath, on décompose CEHS en HSC = {H, S, C} et HES = {H, E, S}. La décomposition D1 évolue en conséquence :

D1 = {CEN, CP, HSC, HES}

Et cette fois-ci on ne peut plus décomposer. Comme on a appliqué systématiquement le théorème de Heath depuis le début, la décomposition D1 est sans perte de données. On peut aussi vérifier que les relvars appartenant à D1, à savoir CEN, CP, HSC, HES sont en BCNF. Le seul défaut est que la décomposition n’est pas sans perte de DF : dans la bagarre on a perdu {H, P} -> {S}, mais qu’à cela ne tienne, on d’enhardit et on enrichit D1 de la relvar HPS (en BCNF) correspondante :

D1 = {CEN, CP, HSC, HES, HPS}

Cette fois-ci les relvars appartenant à D1 sont en BCNF, et au moyen de la technique des tableaux façon Aho, Beeri et Ullman on peut vérifier que les données sont préservées, tandis qu’au moyen de l’algorithme de Beeri et Honeyman (cf. mon message du 17/02 à 1h16) on peut vérifier que les DF sont préservées elles aussi : que du bonheur.


Algorithme de Bernstein

Tous les auteurs mentionnent consciencieusement l’algorithme permettant de décomposer une relvar violant la BCNF en un ensemble D de projections qui la respectent. Le problème est qu’en général il n’y a pas qu’une seule décomposition et la recherche des différentes décompositions peut prendre pas mal de temps et donner le tournis pour des résultats certes justes (respect de la BCNF), mais plus ou moins satisfaisants.

Avec moins d’ambition, on peut se limiter à la production d’une décomposition seulement en 3NF, mais préservant les données et les DF. Il existe un algorithme à cet effet et beaucoup moins consommateur de temps et de larmes que l’autre, algorithme aimablement fourni par l’incontournable Philip Bernstein, et repris bien sûr par Serge Abiteboul et ses camarades. La contrainte est que l’ensemble F des DF binômant avec la relvar R à décomposer doit être réduit à une couverture irréductible (minimale) avant mise en œuvre de l’algorithme.

Par exemple, dans le cas de la relvar CPHSEN, l’ensemble F est :

F = { {C} -> {P}, {H, S} -> {C}, {H, P} -> {S}, {C, E} -> {N}, {H, E} -> {S} }

Comme F est aussi une couverture irréductible, c’est cet ensemble dont on va se servir. L’algorithme permet fondamentalement de produire une décomposition D2 dont chaque élément est une relvar dont l’en-tête est composé exactement des attributs d’une DF de F.

Initialement, D2 est vide :

D2 = {}

En 1re itération, D2 est enrichie d’une relvar dont l’en-tête est composé des attributs de la 1re DF qui se présente, disons {C} -> {P} :

D2 = {CP}

En 2e itération, D2 est enrichie d’une relvar dont l’en-tête est composé des attributs de la 2e DF qui se présente à son tour, disons {H, S} -> {C} :

D2 = {CP, HSC}

Et ainsi de suite, jusqu’à exploitation de l’ensemble des DF. Au final :

D2 = {CP, HSC, HPS, CEN, HES}

Et, ô magie ! on retrouve pile-poil la décomposition D1...

Ultime contrainte : les attributs H et E de la clé HE = {H, E} de la relvar CPHSEN doivent figurer dans l’en-tête d’une relvar appartenant à D2, et à défaut il faudrait injecter de toutes pièces HE dans D2. Ici le problème ne se pose pas, parce que HE est un sous-ensemble de l’en-tête de HES.

L’intérêt de la méthode est que, contrairement à ce qui se passe avec l’autre algorithme, on n’a pas à s’échiner à rechercher la moins mauvaise tactique pour parvenir à ses fins, en l'occurrence de tactique il n’y en a qu’une.

Fewer tears ?


Quelques remarques concernant l’algorithme de Bernstein.

1) Supposons que la relvar CPHSEN soit dotée d’un attribut supplémentaire M, tel que {C} -> {P, M}. Du fait de la nécessité d’une couverture minimale, cette DF y figure sous forme décomposée selon les deux DF : {C} -> {P} et {C} -> {M}.

Au final, la décomposition est la suivante :

D2 = {CP, CM, HSC, HPS, CEN, HES}

A ce stade on peut réassembler C, P et M car les relvars CP et CM ont même clé {C} :

D2 = {CPM, HSC, HPS, CEN, HES}

C’est ce qui s’est en fait passé dans le cas de votre relvar R{A, B, C, D} ayant pour décomposition : { {A, B, D} {B, C} {D, C} }.

2) Il est souvent fait mention d’attributs de la relvar R à décomposer qui ne figurent dans aucune DF, tant à gauche qu’à droite. Pour Ullman (in Principles of Database systems), ces attributs constituent une relvar à eux seuls et sont à évacuer de R. Du point de vue de la modélisation des données, ceci est pour le moins étrange et relève d’une modélisation pour le moins non orthodoxe. Si un attribut T ne figure dans aucune DF, soit il correspond à l’âge du capitaine et n’a effectivement rien à faire dan R et doit en être expulsé, soit sa présence est légitime, auquel cas il figurera inexorablement dans la clé de R. Par exemple, si on enrichit la relvar CPHSEN d’un tel attribut et que la présence de celui-ci est légitime, la configuration devient la suivante :

CPHSENT = {C, P, H, S, E, N, T} avec pour clé candidate : HET = {H, E, T} ;
F = { {C} -> {P}, {H, S} -> {C}, {H, P} -> {S}, {C, E} -> {N}, {H, E} -> {S} }.

Mais la décomposition initiale D2 = {CP, HSC, HPS, CEN, HES} doit être enrichie :
D2 = {CP, HSC, HPS, CEN, HES, HET} puisque la clé doit y figurer impérativement soit en tant que sous-ensemble d’une décomposition, soit pour elle-même.

Je ne vois pas de manière générale comment déduire une DF du type {A}-->{B} à partir d'autres DF dans lesquelles {A} n'apparait que dans la partie droite.

Si {A} n’apparaît qu’à droite, il n’apparaîtra jamais à gauche, lapalissade !

Pour vous en convaincre, calculez la fermeture {C}+ de l’attribut C dans votre exemple : vous constaterez qu’elle restera invariablement égale à {C}...

Alors c'est moi qui suis une bille en axiomes d'Armstrong, ou le document qui est erroné ?

Hum... En voilà une alternative ! Je vous laisse conclure...

[gudina]

Et la lumière fut ! (j'ose espérer à tous les étages...)

Bonjour fsmrel

Et vous n’y arriverez pas...

En effet, le procédé que vous utilisez ne vaut que pour le cas particulier des décompositions possédant exactement deux éléments, alors qu’ici il y en a trois... Vous tentez une vérification sur la base de la seule décomposition D = { {B, C}, {C, D} }, ce qui, en l’absence de {A, B, D}, est évidemment mission impossible.

En fait, on m'avait expliqué, à tort donc, que dans le cas de 3 éléments ou plus, on procédait 2 à 2... La vérification entre {A,B,D} et {B,C} et entre {A,B,D} et {C,D} étant concluante, il ne restait plus qu'à la faire entre {B,C} et {C,D}...

Puisque la décomposition comporte plus de deux éléments, on se sert de l’algorithme dû à Aho, Beeri et Ullman et qui met en jeu des tableaux.

Pour tenter de parvenir à une ligne ne contenant que des ai, si une seule utilisation de chaque DF ne suffit pas, je présume que l'on peut les réutiliser, jusqu'à ce plus aucune d'entre elle ne permette d'effectuer une modification dans le tableau ?

Si {A} n’apparaît qu’à droite, il n’apparaîtra jamais à gauche, lapalissade !

Certes

Hum... En voilà une alternative ! Je vous laisse conclure...

Je suis une bille tout court donc ! Mais ce n'est pas que de ma faute, on m'a raconté des bêtises !

Tout me semble beaucoup, beaucoup plus clair grâce à vos explications ! Donc merci infiniment fsmrel. C'est rassurant de savoir qu'il y a des gens compétents disposés à donner de leur temps pour aider les autres à se dépatouiller

[fsmrel]

Bonjour Gudina,

Pour tenter de parvenir à une ligne ne contenant que des ai, si une seule utilisation de chaque DF ne suffit pas, je présume que l'on peut les réutiliser, jusqu'à ce plus aucune d'entre elle ne permette d'effectuer une modification dans le tableau ?

Voui. Sans modération, jusqu’à ce que plus rien ne bouge...

C'est rassurant de savoir qu'il y a des gens compétents disposés à donner de leur temps pour aider les autres à se dépatouiller

Même si mes neurones commencent à rouiller, en tant que papi c’est un devoir mais aussi un plaisir d’aider les plus jeunes qui sont motivés...

Si la lumière s’est faite et si l’assurance vous vient, il ne reste plus qu’à marquer la discussion comme étant résolue. Bonne journée à vous !