Transformation relation en 3FN

**__mathieu__** · 21/12/2020, 16h23

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** · 22/12/2020, 03h46

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** · 22/12/2020, 14h13

Bonjour,

Envoyé par fsmrel

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** · 23/12/2020, 00h17

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** · 23/12/2020, 04h12

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__** · 23/12/2020, 13h57

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

**fsmrel** · 23/12/2020, 15h00

Bonjour Mathieu,

Je vois que vous avez du pain sur la planche...

Je vous félicite de vous accrocher et vous souhaite grand courage. Si vous avez des questions, n’hésitez pas.

En passant, n’oubliez pas de voter pour les réponses qui ont pu vous aider !

**fsmrel** · 24/12/2020, 01h24

Bonsoir Mathieu,

L’exercice 4 ne devrait pas vous poser de problème particulier (vous me direz). On retrouve la relvar {A,B,C}, les dépendances fonctionnelles et les recommandations de Rissanen ad-hoc, tout ce dont je me suis servi il y a plus de 10 ans, au paragraphe 3.3.2 « Théorème de Heath » de mon article sur la normalisation...

Sinon, j’ai jeté un coup d’oeil aux corrigés qui vous ont été donnés.

(1) Quel que soit l’exercice, quand on vous pose la question : « Pourquoi ce schéma n’est-il pas en 3NF » ?
A chaque fois, dans la réponse qui vous est donnée, il est fait mention de la 2NF : « Ce schéma est en 2NF mais pas en 3NF... »

Cette intervention systématique et lancinante de la 2NF est agaçante, car en toute rigueur il faut préalablement prouver que le schéma en question est en 2NF. Comme la définition donnée dans votre cours de la 2NF fait intervenir la 1NF, il faut commencer par prouver que le schéma est en 1NF. Quelle perte de temps

Boulet !

Le mieux est d’utiliser les définitions de Fagin, Date, Zaniolo et autres ténors, avec lesquelles on n’a pas besoin d’utiliser celles, certes justes mais bien lourdes et inélégantes d’il y a encore trente ans. C’est pourquoi de mon côté j’ai utilisé la définition donnée par Zaniolo de la 3NF, avec laquelle on n’a pas besoin de faire référence aux autres formes normales. Je fais d’autant plus volontiers référence à Zaniolo que la définition qu’il donne de la BCNF (forme normale de Boyce Codd) est celle de la 3NF, à un joker près, comme on va le voir.

Rappelons d’abord la définition de la 3NF :

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.

A son tour, la définition de la BCNF est celle de la 3NF, mais dans laquelle Zaniolo élimine le 3e joker (« A appartient à une clé candidate de R »), ce qui rend la BCNF plus stricte, plus forte, donc de loin préférable dans la chasse aux redondances.

Pour la petite histoire, Zaniolo a donné ses définitions il y a un bon moment, en 1982 ! (A New Normal Form for the Design of Relational Database Schemata).

(2) Concernant l’exercice 1, j’ai écrit (cf. post #2) :

« 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. »

Puis j’ai confirmé la perte de certaines DF (cf. post #3) :

« 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... »

De fait, les dépendances fonctionnelles DF3 et DF4 se sont évanouies dans la nature, et Jorma Rissanen (RIP) en eut été fort marri. Le mieux est donc d’effectuer la décomposition proposée dans le corrigé de votre exercice : chaque DF fait l’objet d’une relvar, à l’exception de DF6, qu’on sait inférer à partir de DF5, DF2 et DF4, soit par les axiomes d’Armstrong, soit par l’algorithme du seau.

Ainsi, encore grand merci à Monsieur Heath pour son théorème, usons mais n’en abusons pas, laissons-nous tempérer en suivant aussi les recommandations de Monsieur Rissanen...

(3) Concernant l’exercice 3, point 1, la justification qui vous a été donnée pour la clé de la relvar est plutôt succincte, lapidaire, et mériterait quelques explications complémentaires.

Pour le point 3 de cet exercice, la solution consistant à décomposer R en R1 {P,D,E} et R2 {D,E,S} sont effectivement sans perte d’information (confirmation par le théorème de Heath), mais malheureusement avec perte de DF, en l’occurrence DF1 P → S, contrairement à ce que prétend le corrigé (si j’interprète correctement le terme sibyllin « spdf ») ! En effet, P et S ne sont présents ensemble ni dans R1 ni dans R2 et toutes les infractions sont donc permises...

Une note concernant la définition de la 1NF

Dans votre cours, la définition de la 1NF est la suivante :

Une relation est en première forme normale (1FN) : si et seulement elle ne contient que des attributs atomiques. Un attribut est atomique s’il n’est pas sémantiquement décomposable.

Cette définition est élégante, sympathique mais elle est discutable. Moins poétique et indiscutable est la suivante due à C.J. Date :

Soit la relation r d’attributs A1, ..., An, respectivement de types T1, ..., Tn. r est en première forme normale (1NF) si et seulement si, pour tous les tuples t présents dans r, la valeur de l’attribut Ai dans t est du type Ti (i = 1, ..., n).

Pour plus d’information, je vous renvoie à la discussion entamée par AidezMoiSvp, notamment au post #15. Et surtout ne faites pas confiance à ce perroquet shadock de Wikipédia à ce sujet !

**__mathieu__** · 30/12/2020, 19h06

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é :

de retrouver tous les identifiants de la relation
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** · 31/12/2020, 20h22

Bonsoir Mathieu,

Envoyé par __mathieu__

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

de retrouver tous les identifiants de la relation
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.

Envoyé par __mathieu__

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__** · 02/01/2021, 11h10

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.

Envoyé par fsmrel

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** · 02/01/2021, 18h45

Bonne année 2021, Mathieu,

Envoyé par __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.

Envoyé par __mathieu__

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} »

Envoyé par __mathieu__

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...

Envoyé par __mathieu__

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..

**__mathieu__** · 03/01/2021, 12h37

Bonjour fsmrel,

Belle et heureuse année. Que 2021 soit meilleure que 2020.

Est-ce que vous pourriez SVP me donner quelques pistes pour les questions 2, 3 et 4 de l'exercice 4 sur les extensions de relation.
Je n'y comprends rien. D'où cela sort ces extensions de relation ? Est-ce que l'on doit considérer les mêmes DF que précédemment pour A --> B et B --> C ?

Envoyé par fsmrel

L’exercice 4 ne devrait pas vous poser de problème particulier (vous me direz). On retrouve la relvar {A,B,C}, les dépendances fonctionnelles et les recommandations de Rissanen ad-hoc, tout ce dont je me suis servi il y a plus de 10 ans, au paragraphe 3.3.2 « Théorème de Heath » de mon article sur la normalisation...

Dans le corrigé le prof écrit :

2) La DF B → C n’est pas respectée dans l’extension de R’ car (B1, C1) et (B1, C2), donc
connaître la valeur de B ne permet pas de déterminer la valeur de C.

Cela ne m'avance pas, je ne comprends pas comment on traite l'exercice, je ne saisis pas le corrigé.

Merci par avance

Cordialement

Mathieu

**fsmrel** · 04/01/2021, 02h09

Bonsoir Mathieu,

Merci pour vos voeux, et pour reprendre l’expression de la reine Elisabeth, essayons d’oublier l’annus horribilis, à savoir 2020...

Dans votre exercice 4, il est écrit :

« On considère la relation R(A,B,C) »

Il est préférable de lire :

« On considère le schéma de relation R(A,B,C) »

Tout en sachant qu’un schéma de relation fait intervenir le type des attributs (je vous renvoie à ce sujet au chapitre 2 « Les structures de données de base » de l’ouvrage de référence français Bases de données, que l’on doit au Professeur Georges Gardarin (merci à lui et aux éditions Eyrolles)). Mais on ne va pas chipoter, fi des types, considérons « R(A,B,C) comme étant le schéma de la relation R »...

Une extension correspond à ce qu’on appelle dans la théorie relationnelle le corps (body) d’une relation (je vous renvoie à ce sujet au paragraphe « A.2. Relation, relvar » de mon article..

Le corps est lui-même composé d’un ensemble de n-uplets (tuples en abrégé), (lignes en SQL). Dans votre exercice, le corps de la relation R’(A,B,C) est composé de 4 tuples, selon la représentation schématique :

R’( A     B    C ) 
    A1    B1   C1
    A2    B1   C2
    A3    B2   C1
    A4    B3   C3

Point 2

On vous demande si cette extension (corps) pourrait être une extension valide pour R. Cela n’est possible que si les contraintes valant pour R, à savoir les dépendances fonctionnelles sont respectées.

Cas de la DF {A} → {B}

Par définition des DF, pour une valeur de l’attribut A il ne peut y avoir qu’une valeur pour l’attribut B, et c’est bien ce qui a lieu ici :

Quand A prend la valeur 'A1', B prend la seule valeur 'B1'
Quand A prend la valeur 'A2', B prend la seule valeur 'B1'
Quand A prend la valeur 'A3', B prend la seule valeur 'B2'
Quand A prend la valeur 'A4', B prend la seule valeur 'B3'

Cas de la DF {B} → {C}

Par définition des DF, pour une valeur de l’attribut B il ne peut y avoir qu’une valeur pour l’attribut C, mais ce n’est pas ce qu’il se passe ici :

En effet, quand B prend la valeur 'B1', C prend deux valeurs à savoir 'C1' et 'C2'.
Il s’ensuit que la DF n’est pas respectée, donc l’extension de R’ ne peut pas prétendre être une extension de R.

Point 3

On vous demande de proposer une extension R” compatible pour R.

Il vous est proposé l’extension suivante :

R”( A     B    C ) 
    A1    B1   C1
    A2    B1   C1
    A3    B2   C1
    A4    B3   C3

Dans laquelle la valeur 'C1' a remplacé la valeur 'C2' de l’extension R’ :

Cette fois-ci, la DF {B} → {C} est respectée, donc R” est une valeur légale pour la relation R.

Point 4

On vous demande une décomposition en 3NF sans perte d’information, et la solution qu’on vous donne est orientée perte de DF : il y a là une incohérence, mais passons, on traitera des deux sujets...

Est donné le schéma de relation R(A,B,C) de degré 3 (c’est-à-dire que ce schéma contient 3 attributs, A, B, C), décomposer revient ici à trouver deux schémas R1 et R2 de degré 2 tels que la jointure de leurs extensions permet de retrouver chaque extension de R sans tuples parasites, c’est-à-dire supplémentaires : une telle décomposition est dite sans perte d’information.

Décomposons par exemple R(A,B,C) en R1(A,C) et R2(B,C).

Qu’obtient-on comme extensions de R1 et R2 à partir de l’extension R” de R :

R”( A     B    C ) 
    A1    B1   C1
    A2    B1   C1
    A3    B2   C1
    A4    B3   C3

Réponse :

R1( A     C )          R2( B     C )
    A1    C1               B1    C1
    A2    C1               B2    C1
    A3    C1               B3    C3
    A4    C3

A quoi est égale la jointure de R1 et R2 ?

Réponse :

R3( A     B     C )
    A1    B1    C1
    A1    B2    C1
    A2    B1    C1
    A2    B2    C1
    A3    B1    C1
    A3    B2    C1
    A4    B3    C3

Mais la jointure R1 JOIN R2 n’a été possible que sur les attributs communs à R1 et R2, en l’occurrence le seul attribut C, et manifestement le résultat R3 de cette jointure n’est pas égal à l’extension R”, il y a des tuples parasites. Pour simplifier, on n’a pas appliqué le théorème de Heath, il ne pouvait donc en être autrement, cette décomposition a fait qu’on a perdu de l’information (en fait récupéré de la fausse information).

Appliquons donc sagement le théorème de Heath.

Il existe la DF {A} → {B}, donc R”(A,B,C) est décomposable sans perte en R4(A,B) et R5(A,C) :

R4( A     B )          R5( A     C )
    A1    B1               A1    C1
    A2    B1               A2    C1
    A3    B2               A3    C1
    A4    B3               A4    C3

Et, théorème de Heath oblige ! on vérifie bien R4 JOIN R5 = R”.

Mais il existe aussi la DF {B} → {C}, donc R”(A,B,C) est décomposable sans perte en R7(A,B) et R8(B,C) :

R7( A     B )          R8( B     C )
    A1    B1               B1    C1
    A2    B1               B2    C1
    A3    B2               B3    C3
    A4    B3

Et, théorème de Heath oblige une fois encore ! on vérifie bien R7 JOIN R8 = R”.

On a trouvé deux décompositions possibles qui sont sans perte d’information. Il y en a-t-il une qu’il faille favoriser ?

Certes oui ! la décomposition en R7(A,B) et R8(B,C) est préférable à la décomposition en R4(A,B) et R5(A,C), car avec la 1re de ces décompositions les DF {A} → {B} et {B} → {C}, ainsi que la DF {A} → {C} qu’on sait inférer à partir des deux premières (axiome de transitivité) sont toutes préservées, tandis qu’avec la 2e décomposition, à savoir R4(A,B) et R5(A,C), on a irrémédiablement perdu la DF {B} → {C}.

Pour aller plus loin dans cette histoire de préservation de l’information, toujours dans mon article, vous pouvez vous plonger dans la lecture du paragraphe E.7.1. Préservation du contenu de la base de données.

Cela dit, le corrigé vous parle de couverture minimale, ce qui sans rapport avec la décomposition sans perte d’information... Mais bon, en gros, le but de la manœuvre est d’éliminer les DF inférables à partir d’un ensemble irréductible (minimal) de DF.

Le corrigé propose l’ensemble de DF {{A} → {B} ; {B} → {C}}.

(1) Le dépendant (partie droite) de chacune de ces DF est minimal car mono-attribut ;

(2) Le déterminant (partie gauche) de chacune de ces DF est minimal car mono-attribut ;

(3) Aucune des deux DF ne peut être supprimée, sinon on perdrait une règle de gestion :

Le fait de vérifier ces 3 points fait que l’ensemble de DF {{A} → {B} ; {B} → {C}} est irréductible (minimal). Pour aller plus loin dans cette histoire de préservation des DF, vous pouvez vous plonger dans la lecture du paragraphe E.7.2. Préservation des dépendances fonctionnelles.

Mais dans le cas général, on peut obtenir plus d’une couverture minimale et cela devient intéressant pour choisir la meilleure structure pour la base de données, autrement dit le meilleur MCD (modèle conceptuel des données) ! Si vous avez du temps devant vous (et du doliprane sous la main), vous pourrez consulter le paragraphe Ensemble irréductible de dépendances fonctionnelles.

Accessoirement, on vérifie vite que les décompositions R1(A,B) et R2(B,C) sont en 3NF. Je vous renvoie au post #2 de cette discussion, où j’ai donné la définition de Zaniolo de la 3NF (il y en a d’autres !), définition que j’aime bien parce qu’elle permet de ne pas avoir à traîner le boulet de la 2NF.

Pour mémoire, je rappelle cette définition :

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.

Avez-vous le sentiment de progresser, ou au contraire, de patauger, voire vous enliser ?

Connaissez-vous la jointure (c’est-à-dire l’opérateur relationnel JOIN) ? Sinon ça craint...