Discussion :

[__mathieu__]

Bonjour,

Je suis en train de lutter sur un TD de normalisation pour résoudre des relations qui sont en 1FN ou 2FN afin qu'elles deviennent en 3FN.

Malgré le cours je ne comprends pas quelle méthode/méthodologie employer et si l'on peut/doit utiliser une même approche ou si cela diffère d'un cas à un autre.
Dans le corrigé (je sais que c'est mal le lire le corrigé, mais là je bloque) il est question d'algorithme (que je ne vois pas dans le cours), de groupes et de transitivité.

J'ai cherché sur Internet et je suis tombé sur un lien de l'IUT d'Evry mais je n'ai pas été beaucoup plus éclairé :
http://www-inf.int-evry.fr/cours/BD/...positionDF.pdf

J'aurais sérieusement besoin d'aide pour comprendre et pouvoir avancer.
Est-ce qu'il y aurait un support de cours que vous recommandez ?

Est-ce qu'il y a une méthodologie qui est définie et que l'on devrait respecter pour traiter ces cas ? SVP, ne me dites pas qu'il y a différentes approches
J'ai besoin d'une trame.

Liens vers le cours :
Partie 1 : https://drive.google.com/file/d/1aBz...ew?usp=sharing
Partie 2 : https://drive.google.com/file/d/1bdj...ew?usp=sharing

Liens vers l'exercice et le corrigé :
https://drive.google.com/file/d/1mdq...ew?usp=sharing
https://drive.google.com/file/d/1ADQ...ew?usp=sharing

Exercice 1 :

Question 1 :
En réalisant un tableau des prédécesseurs on obtient :
Cours a pour prédécesseurs Heure et Salle
Prof a pour prédécesseurs Cours
Heure n'a pas de prédécesseurs
Salle a pour prédécesseurs Heure, Prof, Etudiant,
Etudiant n'a pas de prédecesseurs
Note a pour prédécesseur Cours (donc Heure et Salle) et Etudiant

La clé unique est Heure, Etudiant

Question 2:
La relation est en 1FN par elle ne contient que des attributs atomiques.
La relation est en 2FN car il n'existe pas de dépendance fonctionnelle entre une partie de la clé primaire et une colonne non clé de la table.
La relation n'est pas en 3FN car il y a une dépendance fonctionnelle entre Prof et Cours qui sont deux colonnes non-clés.

Question 3 :
Non traitée

Exercice 2:
La relation est Restaurant(Num_Menu, Nom_Menu, Num_Plat, Nom_Plat, Type_Plat)

Question 1 :
En réalisant un tableau des prédécesseurs on obtient :
Num_Menu n'a pas de prédécesseurs
Nom_Menu a pour prédécesseur Num_Menu
Num_Plat a pour prédécesseur Num_Menu
Nom_Plat a pour prédécesseur Num_Plat
Type_Plat a pour prédécesseur Num_Plat

La clé unique est Num_Menu.

Question 2:
La relation est en 1FN car les attributs sont atomiques.
La relation est en 2FN car la clé primaire est mono attribut.
La relation n'est pas en 3FN car il y a des DF entre les colonnes non-clés.

Question 3:
Non traitée

Exercice 4:

Question 1:
A n'a pas de prédécesseurs.
Le prédécesseur de B est A.
Le prédécesseur de C est B.
La clé primaire est donc A.

Question 2 :
Non traitée

Question 3:
Non traitée

Question 4:
Non traitée

Merci par avance pour votre aide

Je ne souhaite pas avoir les réponses mais vraiment une aide pour comprendre

Cordialement

Mathieu

[fsmrel]

Bonsoir Matthieu,

Vous voilà à votre tour aux prises avec la fameuse relation CPHSEN qui se transmet de génération en génération d’étudiants et qui a fait transpirer Gudina en son temps.

Voyons voir la question 1 de l’exercice 1.

Reprenons les dépendances fonctionnelles imposées :

DF1 - C → P

DF2 - H,S → C

DF3 - H,P → S

DF4 - C,E → N

DF5 - H,E → S

DF6 - H,S,E → N

Pour déterminer les clés de la relvar (variable relationnelle) CPHSEN, vous pouvez utiliser l’algorithme du seau à dépendants.

Notez aussi que les attributs H et E ne sont jamais des dépendants dans les dépendances fonctionnelles ci-dessus, autrement dit ils appartiennent à une clé de CPHSEN (cf. Cas des attributs ne figurant pas dans les dépendants des DF).

La paire {H,E} est-elle clé candidate de la relvar ?

Pour cela elle doit au moins déterminer chaque autre attribut.

La méthode académique consiste à s’appuyer sur les axiomes d’Armstrong :

(a) Grâce à la règle d’augmentation (en augmentant la partie gauche et la partie droite de DF5), on produit :

DF7 - H,E → H,S,E

(b) Par transitivité (puisque H,S,E → N), on produit :

DF8 - H,E → H,S,E,N

(c) - Selon DF2, H,S → C. Par augmentation on produit :

DF9 - H,S,E,N → C,E,N

Et par décomposition :

DF10 - H,S,E,N → C

DF11 - Comme H,E → H,S,E,N (cf. DF8), par transitivité on produit :

DF12 - H,E → C

Comme C → P (cf. DF1), par transitivité on produit :

DF13 - H,E → P

Ainsi, tous les attributs de la relvar sont dépendants de la paire {H,E} (y-compris bien sûr H et E par application de la règle de réflexivité) : {H,E} est surclé de la relvar. Pour être clé candidate, elle doit vérifier la règle d’irréductibilité des clés, c’est-à-dire que ses sous-ensembles stricts {H} et {E} ne doivent pas eux aussi déterminer l’ensemble des attributs de la relvar. Etant donné que les seules DF qu’ils vérifient sont triviales (H → H), E → E), la paire {H,E} est bien clé candidate.

Existe-t-il d’autres clés candidates pour la relvar ? Vous vérifierez à l’aide du saut à dépendants évoqué ci-dessus qu’il n’y a pas d’autre clé candidate (en effet H et E ne peuvent jamais tomber dans le seau, quelles que soient les dépendances fonctionnelles DF1 à DF6).


La relvar CPHSEN n’est pas en troisième forme normale.

Prenons la 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 (3NF) si et seulement si, pour chaque dépendance fonctionnelle X → {A} qui doit être vérifiée par R, au moins une des conditions suivantes est satisfaite :

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

Prenons par exemple le cas de la dépendance fonctionnelle DF1 :

C → P

— P n’est pas un élément de {C}

— {C} n’est pas clé candidate (a fortiori surclé)

— P n’est pas un élément de l’unique clé candidate {H,E} de la relvar.

Ainsi, il existe au moins une dépendance fonctionnelle ne répondant pas aux critères exigés pour la troisième forme normale : celle-ci est violée.


Décomposition en troisième forme normale

Il s’agit de décomposer la relvar pour produire des relvars normalisées 3NF, dont la jointure permet de retrouver cette relvar.

Pour cela on applique le théorème de Heath.

Ainsi, du fait de la dépendance fonctionnelle DF1, {C,P,H,S,E,N} est décomposable en deux relvars sans perte de dépendance fonctionnelle :

{C,P} et {C,H,S,E,N}. La 1re relvar est en 3NF, mais pas la 2e, donc on va lui appliquer le théorème, en utilisant la dépendance fonctionnelle DF2, ce qui donne les 2 relvars :
{H,S,C} et {H,S,E,N}. On vérifie facilement que la 1re relvar est en 3NF. Qu’en est-il de la 2e ? Les dépendances fonctionnelles non triviales sont
H,E → S et H,E → N
Comme le déterminant {H,E} est clé, {H,S,E,N} est en 3NF.

Ainsi, par application du théorème de Heath, la relvar non 3NF {C,P,H,S,E,N} est décomposable sans perte en 3 relvars {C,P}, {H,S,C}, {H,S,E,N}, leur jointure permet de retrouver {C,P,H,S,E,N}.

Le risque encouru quand on décompose est de perdre en route une dépendance fonctionnelle qui a été donnée. Rissanen a traité le sujet, je vous renvoie au théorème de Heath évoqué ci-dessus.


Vous voilà armé, vous devriez maintenant être en mesure de résoudre les autres exercices.

[fsmrel]

Bonjour,

Le risque encouru quand on décompose est de perdre en route une dépendance fonctionnelle qui a été donnée. Rissanen a traité le sujet, je vous renvoie au théorème de Heath évoqué ci-dessus.

Ainsi, une fois la décomposition en 3NF effectuée, qu’est-il advenu de la dépendance fonctionnelle DF3, à savoir H,P → S ? Même chose concernant la dépendance fonctionnelle DF4, C,E → N...

A vous d’essayer d’autres décompositions en utilisant la théorème de Heath, tout en ayant en tête l’avertissement de Rissanen.

[fsmrel]

Bonsoir Matthieu,


Concernant l’exercice 2

On vous demande quelle est la clé « primaire » de la relvar :

{Num_Menu, Nom_Menu, Num_Plat, Nom_Plat, Type_Plat}

Pour ne pas traîner tous ces noms à rallonge, je les remplace par un alias d’une lettre et l’en-tête de la relvar devient :

{A, B, C, D, E}

En notant au passage que le restaurant est original : le menu ne comportant qu’un plat, les clients ne doivent pas s’y presser...

En tout cas les dépendances fonctionnelles sont les suivantes :

DF1 : A → B

DF2 : A → C

DF3 : C → D

DF4 : C → E

Pour changer un peu, on va rechercher les clés candidates au moyen de l’algorithme du seau à dépendants.

Commençons par l’attribut A et calculons sa fermeture {A}⁺.

Au départ la situation est la suivante :

A _ _ _ _

Grâce à DF1 et DF2, on peut faire tomber B et C dans le seau :

A B C _ _

Du fait que C est dans le seau, grâce à DF3 et DF4 on peut y envoyer D et E :

A B C D E

Dans le cas de la fermeture {A}⁺, tous les attributs sont tombés dans le seau, {A} est donc clé candidate.

Passons à l’attribut B et calculons sa fermeture {B}⁺.

Au départ la situation est la suivante :

B _ _ _ _

Il n’existe aucune DF dans laquelle B est le déterminant, donc la fermeture {B}⁺ ne contenant pas tous les attributs de la relvar, {B} n’est pas clé candidate.

Passons à l’attribut C et calculons sa fermeture {C}⁺.

Au départ la situation est la suivante :

C _ _ _ _

 

Grâce à DF3 et DF4, on peut envoyer D et E dans le seau :

C D E _ _

Mais il n’existe aucune autre DF dans laquelle C est partie prenante en tant que déterminant, donc la fermeture {C}⁺ ne contenant pas tous les attributs de la relvar, {C} n’est pas clé candidate.

Concernant les attributs D et E, la situation est la même que pour l’attribut B.

En fin de parcours, il n’y a que {A} comme clé candidate (« primaire » dans votre énoncé, mais je signale en passant que cet adjectif a été frappé d’obsolescence dans la théorie relationnelle).

La relvar Restaurant est-elle en 3NF ?

Je reprends l’énoncé 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 (3NF) si et seulement si, pour chaque dépendance fonctionnelle X → {A} qui doit être vérifiée par R, au moins une des conditions suivantes est satisfaite :

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

Prenons le cas de la dépendance fonctionnelle DF3 : C → D

La condition 1 n’est pas respectée car D n’est pas un élément de {C}
La condition 2 n’est pas respectée car {C} n’est pas clé de la relvar
La condition 3 n’est pas respectée car {A} est la seule clé candidate de la relvar et D n’appartient pas à {A}.

Il existe donc au moins une dépendance fonctionnelle, à savoir DF3, ne respectant pas les 3 conditions exigées, la 3NF est donc violée.

La 2NF est-elle respectée ? J’en rappelle un des énoncés pertinents :

La relvar R est en deuxième forme normale (2NF) si et seulement si, pour chaque clé candidate K de R et pour chaque attribut non clé A de R, la DF K → {A} est irréductible.

Où la DF X → Y est dite irréductible si et seulement si il n’existe pas de sous-ensemble strict X’ de X tel que X’ → Y.

La relvar Restaurant ne contient qu’une seule clé candidate, à savoir {A}, et ses attributs non clés B, C, D, E étant singletons, les DF {A} → {B}, {A} → {C}, {A} → {D}, {A} → {E}, sont irréductibles, en conséquence de quoi la relvar respecte la 2NF.

Décomposition de la relvar Restaurant :

Par application du théorème de Heath et en tenant compte de la recommandation de Rissanen, la relvar {A,B,C,D,E} peut être décomposée sans perte en {A,B,C} et {C,D,E}. Ces deux relvars de clés respectives {A} et {C} sont non seulement en 3NF mais aussi en BCNF. En vertu d’un théorème dû à Fagin et Date (Database Design and Relational Theory, Normal Forms and All That Jazz (second edition), page 211), elles sont même en 5NF (soit R une relvar en BCNF, si les clés de R sont singletons, alors R est en 5NF).

[fsmrel]

Concernant l’exercice 3

La barre monte d’un petit cran.

Renommons nopers, nomevt, datevt, salle respectivement en P, E, D, S.

Les DF sont les suivantes :

DF1 : P → S

DF2 : S,D → E

DF3 : E,D → S

l’attribut P n’est nulle part dépendant dans les dépendances fonctionnelles ci-dessus, autrement dit il appartient à une clé candidate de R (cf. Cas des attributs ne figurant pas dans les dépendants des DF).

Le singleton {P} est-il clé candidate de la relvar à lui seul ? Non, car E et S ne dépendent pas de ce singleton. Il faut donc unir P à au moins un des autres attributs de R et voir avec l’algorithme du seau à dépendants si on obtient une fermeture contenant tous les attributs de R.

Que donne l’union de P et S ?

Réponse : P S _ _

C’est insuffisant, car manquent E et D.

Laissons tomber et tentons plutôt l’union de P et E. Que donne cette union ?

Réponse : P S E _ (P et E sont dans le seau, et S les y rejoint grâce à DF1, mais ensuite rien ne peut se passer).

C’est insuffisant, car manque D.

Laissons tomber et tentons plutôt l’union de P et D. Que donne cette union ?

Réponse : P S D E (P et D sont dans le seau, et S les y rejoint grâce à DF1, et E aussi, grâce à DF2).

Conclusion : la paire {P,D} est clé candidate contrairement aux autres paires. C’est du reste la seule clé candidate.

La relvar est-elle en 3NF ?

Je reprends l’énoncé 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 (3NF) si et seulement si, pour chaque dépendance fonctionnelle X → {A} qui doit être vérifiée par R, au moins une des conditions suivantes est satisfaite :

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

Prenons le cas de la dépendance fonctionnelle DF1 : P → S

La condition 1 n’est pas respectée car S n’est pas un élément de {P}
La condition 2 n’est pas respectée car {P} n’est pas clé de la relvar
La condition 3 n’est pas respectée car {P,D} est la seule clé candidate de la relvar et S n’appartient pas à {P,D}.

Il existe donc au moins une dépendance fonctionnelle, à savoir DF1, ne respectant pas les 3 conditions exigées, la 3NF est donc violée.

Examinons le cas de la décomposition en R1 et R2 :

R1 (P,S)

R2 (S,D,E)

Pour reprendre l’énoncé de la 3NF selon Zaniolo, R1 est en 3NF. En effet elle contient la DF P → S dont le déterminant {P} est clé : la condition 2 de la définition de Zaniolo est respectée, ce qui suffit pour que R1 soit en 3NF.

R2 est aussi en 3NF. En effet, avec l’algorithme du seau on montre que R2 contient deux clés candidates, {S,D} telle que {S,D} → E et {E,D} telle que {E,D} → S : la condition 2 de la définition de Zaniolo est bien respectée, ce qui suffit pour que R2 soit en 3NF.

Etant donné que la décomposition de R en R1 et R2 a été effectuée sans tenir compte du théorème de Heath, forcément cette décomposition n’est pas bonne.

En effet, la jointure naturelle de R1 et R2 doit permettre de retrouver R, mais R1 et R2 n’ont que le seul attribut S en commun : en effectuant cette jointure, apparaissent des données parasites, c’est-à-dire absentes de R.

Exemple :

Si R contient les tuples (lignes en SQL) :

<'p1', 'e1', 'd1', 's1'>
<'p2', 'e1', 'd2', 's1'>

R1 contient alors les tuples :

<'p1', 's1'>
<'p2', 's1'>

Et R2 contient les tuples :

<'s1', 'd1', 'e1'>
<'s1', 'd2', 'e1'>

Mais la jointure R1 JOIN R2 de R1 et R2 contient des tuples parasites, c’est-à-dire absents de R :

<'p1', 'e1', 'd1', 's1'>
<'p2', 'e1', 'd2', 's1'>
<'p1', 'e1', 'd2', 's1'> (parasite)
<'p2', 'e1', 'd1', 's1'> (parasite)

Pour obtenir une décomposition en 3NF, il vaut mieux s’appuyer comme d’habitude sur le théorème de Heath.

Par exemple, grâce à DF2 : S,D → E, la relvar R est décomposable en R2 {S,D,E} et R3 {S,D,P}. R2 est en 3NF, mais pas R3 qu’il faut décomposer à tour. Ceci est possible grâce à DF1 : P → S, ce qui donne les deux relvars R1 {P,S} de clé {P} et R4 {P,D} de clé {P,D}.

La décomposition 3NF (sans perte) est finalement la suivante :

R1 {P,S}

R2 {S,D,E}

R4 {P,D}

A noter que R4 vient compléter avec bonheur les relvars R1 et R2 proposées dans l’énoncé du devoir, et faire disparaître les parasites qu’on avait mis en évidence.

Conclusion : grand merci à Monsieur Heath pour son théorème !

[__mathieu__]

Bonjour,

Merci beaucoup pour vos retours. Merci énormément.
Je vais déjà commencer par bien étudier la partie théorie avec l’algorithme proposé ainsi que le lien vers la discussion de Gudina sur ce sujet.

Désolé de ne pas être plus réactif dans mes réponses, j'ai du mal à gérer et le BTS et le CNAM en parallèle.

Je vais prendre le temps d'étudier cette partie et je reviendrai vous posez très probablement tout un tas de questions.

Encore merci pour votre aide.

Cordialement

Mathieu

[__mathieu__]

Bonsoir,

Encore merci pour vos posts très détaillés, vos tutoriels m'aident énormément. Vous devriez postuler comme prof au CNAM, au moins on apprendrait.
C'est tellement frustrant de payer 150 euros pour une formation et avoir le sentiment de ne rien tirer de ce qui devrait y être enseigné...

Dans un de vos tutoriels vous écrivez pour l'algorithme du saut à dépendant au paragraphe :

E.4. Fermeture d'un ensemble d'attributs, l'algorithme du seau à dépendants > Méthode pratique > Autre exemple

https://fsmrel.developpez.com/basesr...n/?page=7#LE.4

Autrement dit, {A,D} ➔ {A,B,C,D,E,F} et {A,D} est une surclé pour R (et c'est aussi une clé candidate, car {A,D}+ est différent de {A}+ et {D}+).

Si je comprends bien pour trouver une clé candidate il faut que l'algorithme du saut à dépendant permette pour un identifiant donné :

1. de retrouver tous les identifiants de la relation
2. s'il est composé de deux identifiants (ici {A, D}+), l'application de ce même algorithme ne devrait pas donner le même résultat pour {A}+ ou pour {D}+

Est-ce que la raison du point 2 est que l'unicité pour la surclé ne serait pas respectée et que donc elle ne pourrait donc pas représenter une clé candidate ?
Ce qui ferait le lien avec la définition que vous donnez sur la clé candidate, mais là vous expliquez que l'unicité s'applique à la clé candidate et non à la surclé.

https://fsmrel.developpez.com/basesr...?page=3#L3.2.4

Un sous-ensemble K d'une relvar R est une surclé de R si et seulement si chaque attribut C de R en dépend fonctionnellement (trivialement, partiellement ou totalement).

Une clé candidate est une surclé spécialisée, car elle est astreinte à respecter le principe d'irréductibilité outre celui d'unicité.

Merci par avance

Cordialement

Mathieu

[fsmrel]

Bonsoir Mathieu,

Si je comprends bien pour trouver une clé candidate il faut que l'algorithme du saut à dépendant permette pour un identifiant donné :

1. de retrouver tous les identifiants de la relation
2. s'il est composé de deux identifiants (ici {A, D}+), l'application de ce même algorithme ne devrait pas donner le même résultat pour {A}+ ou pour {D}+

L’algorithme fait intervenir un seau et non pas un saut. Tous les attributs de la relvar R peuvent effectuer un saut dans le seau, mais c’est tout...

Attention à la terminologie : le terme « identifiant » est inconnu dans la théorie relationnelle, c’est plutôt un terme merisien (plus précisément utilisé dans les MCD). Quel sens donnez-vous ici à ce terme ?

Je rappelle le principe de l’algorithme :

Soit Z un sous-ensemble d’attributs de l’en-tête de la relvar R, et S l’ensemble des DF vérifiées par R.

On pose V := Z.
Pour chaque DF appartenant à S, si le déterminant X de cette DF appartient à V, autrement dit se trouve dans le seau, alors son dépendant Y peut tomber à son tour dans le seau.
Quand on a traité toutes les DF de S et que plus rien ne tombe dans le seau, on arrête.

{A}, {D}, {A,D}, sont quelques uns des très nombreux sous-ensembles d’attributs (et non pas d’identifiants, terme impropre et intraduisible ici) de l’en-tête {A,B,C,D,E,F} de la relvar R.

L’ensemble donné S des DF vérifiées par R est le suivant :

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

Par exemple, si on pose Z = {A}, alors la variable V prend la valeur initiale {A}.
Le contenu du seau est alors :  

A _ _ _ _ _

Où les « _ » symbolisent des places pouvant héberger les autres attributs de R.

1er tour de manège.

Comme l’attribut A est dans le seau et que {A} est le déterminant de la DF {A} → {B,C}, l’algorithme autorise que les attributs composant le dépendant {B,C} de la DF tombent dans le seau, dont le contenu devient :

A B C _ _ _

2e tour de manège.

Comme l’attribut B est dans le seau et que {B} est le déterminant de la DF {B} → {E}, l’algorithme autorise que l’attribut composant le dépendant {E} de la DF tombe dans le seau, dont le contenu devient :

A B C _ E _

3e tour de manège.

Comme l’attribut E est dans le seau et que {E} est le déterminant de la DF {E} → {C,F}, l’algorithme autorise que les attributs composant le dépendant {C,F} de la DF tombent dans le seau (en notant que l’attribut C s’y trouve déjà) :

A B C _ E F

La seule DF non encore exploitée est {C,D} → {E,F}, mais son déterminant {C,D} contient l’attribut D qui malheureusement n’est pas dans le seau, ce qui fait que cette DF n’est pas exploitable et le contenu du seau reste inchangé.

Fin des tours de manège pour Z = {A}.

On peut passer à Z = {B} et repartir pour une nouvelle tournée avec l’algorithme, puis passer à Z = {C}, puis à Z = {D}, etc.

En particulier, grâce à l’algorithme on peut calculer les fermetures {A}⁺ de {A}, {D}⁺ de {D}, {A,D}⁺ de {A,D}.

La fermeture de {A} est composée de l’ensemble des attributs de R tombés dans le seau quand on a posé Z = {A} :

{A}⁺ = {A,B,C,E,F}, sous-ensemble strict de l’en-tête {A,B,C,D,E,F} de R.

La fermeture de {D} est l’ensemble des attributs de R tombés dans le seau quand on a posé Z = {D} :

{D}⁺ = {D}, sous-ensemble strict de l’en-tête {A,B,C,D,E,F} de R.

La fermeture de {A,D} est composée de l’ensemble des attributs de R tombés dans le seau quand on a posé Z = {A,D} :

{A,D}⁺ = {A,B,C,D,E,F}, c’est-à-dire l’en-tête de R.

Recherche des clés candidates

Pour rechercher les clés candidates, il aura fallu exploiter toutes les DF que peut comporter la relvar R, mais ces DF ne se limitent pas à celles qui ont été fournies au départ :

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

En effet puisque {A, D}⁺ = {A,B,C,D,E,F}, il existe aussi la DF :

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

Ce qui veut dire qu’il peut exister comme ici des DF inférables de celles qui ont été données (S). On est donc condamnés à faire tourner l’algorithme pour toutes les combinaisons des attributs de R (et ça fait du monde !), à savoir :

Tous les singletons : {A}, {B}, {C}, {D}, {E}, {F}

Toutes les paires : {A,B}, {A,C}, {A,D}, {A,E}, {A,F}, {B,C}, {B,D}, {B,E}, {B,F}, {C,D}, {C,E}, {C,F}, {D,E}, {D,F}, {E,F}

Tous les triplets : {A,B,C}, {A,B,D}, {A,B,E}, {A,B,F}, {A,C,D}, etc.

Tous les quadruplets : {A,B,C,D}, {A,B,C,E}, {A,B,C,F}, {A,B,D,E}, {A,B,D,F}, {A,B,E,F}, etc.

Tous les quintuplets : {A,B,C,D,E}, {A,B,C,D,F}, {B,C,D,E,F}

Le sextuplet {A,B,C,D,E,F}.

Et chaque combinaison est à soumettre à l’algorithme du seau afin d’en obtenir la fermeture, laquelle est à considérer ensuite comme déterminant de DF (en passant, l’ensemble des DF, données ou inférables est appelé la fermeture des DF de R). Il s’agit d’un travail décourageant, car le nombre de DF (en incluant celles qui sont triviales et en prenant aussi en compte l’ensemble vide {} comme déterminant ou dépendant de DF) est égal à 2²ⁿ où n est le nombre de DF. Puisque l’en-tête de R contient 6 attributs, le nombre possible de DF est théoriquement égal à 2¹², c’est-à-dire 4096 (gloups !)

C’est pour cela qu’on utilise des astuces permettant de gagner du temps. Ainsi, comme je l’ai écrit par ailleurs, si un attribut n’appartient à aucun dépendant d’une DF quelle qu’elle soit, alors on se dépêchera de balancer cet attribut dans le seau pour voir ce que l’on peut en tirer. Contrairement aux attributs B, C, E, F, comme les attributs A et D n’appartiennent à aucun dépendant de DF, on les jette fissa ensemble dans le seau puis on met l’algorithme en branle.

Bien nous en a pris, car on a vu que

{A,D}⁺ = {A,B,C,D,E,F}, c’est-à-dire l’en-tête de R

Ce qui permet de conclure que la paire {A,D} est surclé de R. Mais est-ce une clé candidate ? En tant que surclé, {A,D} respecte la contrainte d’unicité, mais pour être clé candidate, {A,D} doit aussi respecter la règle d’irréductibilité. La paire {A,D} est-elle réductible ? Si oui, au moins un des singletons {A} ou {D} doit être surclé, donc il faudrait que :

{A}⁺ = {A,B,C,D,E,F}

ou {D}⁺ = {A,B,C,D,E,F}.

Or on a vu que :

{A}⁺ = {A,B,C,E,F} sous-ensemble strict de l’en-tête {A,B,C,D,E,F} de R.

{D}⁺ = {D} sous-ensemble strict de l’en-tête {A,B,C,D,E,F} de R.

{A}⁺ et {D}⁺ n’étant que des sous-ensembles stricts de R, ils ne peuvent en être surclés, et par conséquent la surclé {A,D} est irréductible, elle est donc clé candidate.

Tous les sur-ensembles de {A,D} sont évidemment des surclés, mais en même temps tous sont réductibles à {A,D} : ils ne peuvent donc pas prétendre à être clés candidates.

Ainsi, dans la recherche des clés candidates, on peut éliminer ces sur-ensembles, d’où un gain de temps fort appréciable : sur les 4096 cas à examiner, il n’en reste qu’une trentaine :

{A,B}, {A,C}, {A,E}, {A,F},
{B,C}, {B,D}, {B,E}, {B,F},
{C,D}, {C,E}, {C,F},
{D,E}, {D,F},
{E,F},
{A,B,C}, {A,B,E}, {A,B,F},
{B,C,D}, {B,C,E}, {B,C,F},
{C,D,E}, {C,D,F},
{C,E,F},
{D,E,F},
{A,B,C,E}, {A,B,C,F},
{B,C,D,E}, {B,C,D,F},
{C,D,E,F},
{A,B,C,E,F}, {B,C,D,E,F}.

On a vu que {A}⁺ est le sous-ensemble strict {A,B,C,E,F}, donc les paires, triplets et quadruplets que ce sous-ensemble contient ne pourront pas faire plus que lui, à savoir :

{A,B}, {A,C}, {A,E}, {A,F},
{B,C}, {B,E}, {B,F},
{C,E}, {C,F},
{E,F},
{A,B,C}, {A,B,E}, {A,B,F},
{B,C,E}, {B,C,F},
{C,E,F},
{A,B,C,E}, {A,B,C,F},
{A,B,C,E,F}.

Donc on les évacue. Sur la trentaine de cas à examiner il n’en reste qu’une douzaine :

{B,D}, {C,D}, {D,E}, {D,F},
{B,C,D}, {C,D,E}, {C,D,F}, {D,E,F},
{B,C,D,E}, {B,C,D,F}, {C,D,E,F},
{B,C,D,E,F}.

Courageusement, on s’attaque à la 1re paire, {B,D} et on en calcule la fermeture. Verdict de l’algorithme :

{B,D}⁺ = {B,C,D,E,F}

Les paires, triplets et quadruplets que ce sous-ensemble contient ne pourront pas faire plus que lui, ce qui est le cas de la douzaine ci-dessus, on les évacue donc, en conséquence de quoi il ne reste que {B,C,D,E,F}, quintuplet qui est un sous-ensemble strict du sextuplet {A,B,C,D,E,F} et ne peut donc prétendre à être surclé et a fortiori clé candidate.


Conclusion :

On a montré que la paire {A,D} est clé candidate et qu’il n’y en a pas d’autre.

vous expliquez que l'unicité s'applique à la clé candidate et non à la surclé.

Quand j’écris :

« Une clé candidate est une surclé spécialisée, car elle est astreinte à respecter le principe d'irréductibilité outre celui d'unicité. »

Alors je signifie qu’outre le principe d’unicité (qui vaut bien sûr pour toutes les surclés), une clé candidate doit en plus respecter le principe d'irréductibilité.

Je ne comprends donc pas votre remarque. Comment la justifieriez-vous, alors qu’en plus de l’unicité, c’est bien l’irréductibilité qui caractérise spécifiquement la clé candidate !

[__mathieu__]

Bonjour,

Merci beaucoup pour votre réponse détaillée.
J'ai bien compris jusqu'à ce passage. Qu'est-ce que vous appelez des DF inférables ?
D'autre part, pourquoi lors de la recherche des clés candidates on écarte les singletons ?
Au début il est dit que l'on doit tester toutes les clés candidates même les singletons, mais ensuite ils n'apparaissent plus.
Je pense avoir loupé quelque chose.

Après, c'est certainement annexe pour vous mais dans le devoir de l'année précédente correspond à 2 points dans la note finale.
Je me demande comment faire pour traiter tout cela dans les 2 heures (MCD + MySQL).

Dans le corrigé que j'ai mis en lien dans mon premier post il n'y a aucun détail.
D'autre part, n'ayant au départ aucun support j'avais trouvé la clé H, E en faisant un tableau des prédécesseurs et en voyant qu'il n'y avait pas de prédécesseurs pour ces "sommets".
Est-ce que cela se rapproche à ce que vous dites ici

C’est pour cela qu’on utilise des astuces permettant de gagner du temps. Ainsi, comme je l’ai écrit par ailleurs, si un attribut n’appartient à aucun dépendant d’une DF quelle qu’elle soit, alors on se dépêchera de balancer cet attribut dans le seau pour voir ce que l’on peut en tirer. Contrairement aux attributs B, C, E, F, comme les attributs A et D n’appartiennent à aucun dépendant de DF, on les jette fissa ensemble dans le seau puis on met l’algorithme en branle.

Ce qui veut dire qu’il peut exister comme ici des DF inférables de celles qui ont été données (S). On est donc condamnés à faire tourner l’algorithme pour toutes les combinaisons des attributs de R (et ça fait du monde !), à savoir :

Tous les singletons : {A}, {B}, {C}, {D}, {E}, {F}

Toutes les paires : {A,B}, {A,C}, {A,D}, {A,E}, {A,F}, {B,C}, {B,D}, {B,E}, {B,F}, {C,D}, {C,E}, {C,F}, {D,E}, {D,F}, {E,F}

Tous les triplets : {A,B,C}, {A,B,D}, {A,B,E}, {A,B,F}, {A,C,D}, etc.

Tous les quadruplets : {A,B,C,D}, {A,B,C,E}, {A,B,C,F}, {A,B,D,E}, {A,B,D,F}, {A,B,E,F}, etc.

Tous les quintuplets : {A,B,C,D,E}, {A,B,C,D,F}, {B,C,D,E,F}

Ainsi, dans la recherche des clés candidates, on peut éliminer ces sur-ensembles, d’où un gain de temps fort appréciable : sur les 4096 cas à examiner, il n’en reste qu’une trentaine :

{A,B}, {A,C}, {A,E}, {A,F},
{B,C}, {B,D}, {B,E}, {B,F},
{C,D}, {C,E}, {C,F},
{D,E}, {D,F},
{E,F},
{A,B,C}, {A,B,E}, {A,B,F},
{B,C,D}, {B,C,E}, {B,C,F},
{C,D,E}, {C,D,F},
{C,E,F},
{D,E,F},
{A,B,C,E}, {A,B,C,F},
{B,C,D,E}, {B,C,D,F},
{C,D,E,F},
{A,B,C,E,F}, {B,C,D,E,F}.

Merci par avance

Cordialement

Mathieu

[fsmrel]

Bonne année 2021, Mathieu,

Qu'est-ce que vous appelez des DF inférables ?

Une DF inférable est une DF qui peut être obtenue à partir d’autres DF.

Dans l’exemple dont je me suis servi la fois précédente, est donné un ensemble donné S de DF vérifiées par R :

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

Visiblement la DF {A,D} → {A,B,C,D,E,F} ne fait pas partie de S, mais on l’a obtenue (inférée) à partir des DF appartenant à S en soumettant celles-ci à l’algorithme du seau. On aurait pu l’obtenir en se servant seulement des axiomes d’Armstrong, mais ça aurait été beaucoup plus long et pénible, comme je l’ai signalé au paragraphe «E.4. Fermeture d'un ensemble d'attributs, l'algorithme du seau à dépendants» de mon article. Donc merci à Philip Bernstein !

Cela dit, pour reprendre la DF {A,D} → {A,B,C,D,E,F}, grâce aux axiomes et règles d’Armstrong, il est facile d’inférer de nouvelles DF à partir de celle-ci. A titre d’exemple, en utilisant la règle de décomposition, on peut inférer (produire) l’échantillon suivant de DF :

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

Etc.

D'autre part, pourquoi lors de la recherche des clés candidates on écarte les singletons ?

Je n’écarte rien du tout, ainsi j’ai écrit :

« On est donc condamnés à faire tourner l’algorithme pour toutes les combinaisons des attributs de R (et ça fait du monde !), à savoir :

Tous les singletons : {A}, {B}, {C}, {D}, {E}, {F} »

Au début il est dit que l'on doit tester toutes les clés candidates même les singletons, mais ensuite ils n'apparaissent plus.
Je pense avoir loupé quelque chose.

Je n’ai pas écrit « tester », mais « rechercher », ce qui n’est quand même pas la même chose. On ne teste pas des clés, on les cherche, c’est-à-dire chaque combinaison d’attributs Z de l’en-tête {A,B,C,D,E,F} de la relvar R qui vérifient Z → {A,B,C,D,E,F}. Z peut être un singleton, une paire, un triplet, un quadruplet, un quintuplet, et même (trivialement) le sextuplet. Du point de vue théorique, Z peut être l’ensemble vide {}, auquel cas il est avéré que Z → {}, mais ne vous lancez pas dans ce genre d’exploration qui concerne les constantes relationnelles TABLE_DEE et TABLE_DUM...

Dans le corrigé que j'ai mis en lien dans mon premier post il n'y a aucun détail.
D'autre part, n'ayant au départ aucun support j'avais trouvé la clé H, E en faisant un tableau des prédécesseurs et en voyant qu'il n'y avait pas de prédécesseurs pour ces "sommets".
Est-ce que cela se rapproche à ce que vous dites ici

C’est pour cela qu’on utilise des astuces permettant de gagner du temps. Ainsi, comme je l’ai écrit par ailleurs, si un attribut n’appartient à aucun dépendant d’une DF quelle qu’elle soit, alors on se dépêchera de balancer cet attribut dans le seau pour voir ce que l’on peut en tirer. Contrairement aux attributs B, C, E, F, comme les attributs A et D n’appartiennent à aucun dépendant de DF, on les jette fissa ensemble dans le seau puis on met l’algorithme en branle.

Il y a bien sûr un rapprochement. Mais comme disait Henri Poincaré : « L’intuition trouve, le raisonnement prouve » : dans le cas de la fameuse relvar CPHSEN il faut donc prouver que la paire {H,E} est bien clé candidate, cf. le post #2 de la discussion..