TD1 - Corrigés

Exercice 1 - Corrigé

On considère le bon de commande papier suivant, qu’on se propose d’encoder sous la forme de données à introduire dans la base de données de la boutique présentée ci-après.

Qu’en pensez-vous ?

Problèmes détectés sur le bon de commande :

Données commandes :

• Le numéro de commande n’existe pas en BDD
• Le 31 février n’existe pas
• Le montant total est faux

Données clients :

• Le client numéro 3 n’est pas celui-ci
• L’adresse est incomplète
• Il manque le numéro de téléphone

Données des détails de commande :

• Les détails de respsectent pas les contraintes de la BDD (2 fois le produit 1)
• Les quantités sont écrit en lettres au lieu de chiffres
• Le sous-total de la 2e ligne est faux

Données des produits :

• Le prix unitaire du produit du 3e détail est faux

Exercice 2 - Corrigé

Énoncé

Soit le schéma de la relation R :

R(A, B, C, D, E, G)

et un ensemble donné de dépendances fonctionnelles pour cette relation:

A → BC
AC → E
ADE → BG
CG → D
BG → C
C → B

1. Donner la couverture minimale des dépendances fonctionnelles de R

2. Donner une décomposition de R en relations 3NF sans perte d’informations et sans perte de dépendances

3. Précisez l’identifiant de chaque relation obtenue

Solution

Soit le schéma de la relation R :

R(A, B, C, D, E, G)

et un ensemble donné de dépendances fonctionnelles pour cette relation:

A → BC
AC → E
ADE → BG
CG → D
BG → C
C → B

1. Donner la couverture minimale des dépendances fonctionnelles de R
2. Donner une décomposition de R en relations 3NF sans perte d’informations et sans perte de dépendances
3. Précisez l’identifiant de chaque relation obtenue

Rappel

La couverture minimale d’un ensemble de DFE est un sous-ensemble minimum des DFE permettant de générer toutes les autres DFE.

Pour déterminer la couverture minimale des dépendances fonctionnelles, nous devons suivre trois étapes :

1. la décomposition des dépendances
2. l’élimination des attributs redondants dans les dépendances gauches (réduction des parties gauches)
3. la suppression des dépendances fonctionnelles redondantes

Étape 1 : Décomposer les dépendances

Nous devons décomposer les dépendances qui ont plusieurs attributs à droite.

A -> BC devient :

A -> B
A -> C

ADE -> BG devient :

ADE -> B
ADE -> G

Les autres dépendances n’ont qu’un seul attribut à droite, donc elles restent inchangées.

Ensemble des dépendances après décomposition :

A -> B
A -> C
AC -> E
ADE -> B
ADE -> G
CG -> D
BG -> C
C -> B

Étape 2 : Réduire les parties gauches (si possible)

Nous allons essayer de réduire la partie gauche de chaque dépendance en éliminant les attributs inutiles.

• A -> B : La partie gauche est déjà minimale.
• A -> C : La partie gauche est déjà minimale.
• AC -> E : Tester si A -> E ou C -> E est possible. Ni A ni C seuls ne permettent de déduire E, donc cette dépendance est minimale.
• ADE -> B : Tester si AD -> B, AE -> B, ou DE -> B est possible. Aucune réduction ne permet de déduire B, donc cette dépendance est minimale.
• ADE -> G : Tester si AD -> G, AE -> G, ou DE -> G est possible. Aucune réduction ne permet de déduire G, donc cette dépendance est minimale.
• CG -> D : Tester si C -> D ou G -> D est possible. Aucune réduction n’est possible, donc cette dépendance est minimale.
• BG -> C : Tester si B -> C ou G -> C est possible. B -> C existe déjà, donc on peut éliminer cette dépendance. — ERREUR
• C -> B : La partie gauche est déjà minimale.

Ensemble des dépendances après réduction des parties gauches :

A -> B
A -> C
AC -> E
ADE -> B
ADE -> G
CG -> D
C -> B

Étape 3 : Éliminer les dépendances redondantes

Nous allons maintenant vérifier si certaines des dépendances peuvent être déduites des autres (c’est-à-dire redondantes).

• A -> B : La partie gauche est déjà minimale, mais cette dépendance est redondante car elle peut être déduite par transitivité de A -> C et C -> B (nous l’éliminerons à l’étape suivante).
• A -> C : Ne peut pas être déduite d’autres dépendances.
• AC -> E : Ne peut pas être déduite d’autres dépendances.
• ADE -> B : peut être supprimée car A -> B donc on n’a pas besoin de ADE pour déterminer B.
• ADE -> G : Ne peut pas être déduite d’autres dépendances.
• CG -> D : Ne peut pas être déduite d’autres dépendances.
• C -> B : Ne peut pas être déduite d’autres dépendances.

La couverture minimale des dépendances fonctionnelles est donc :

A -> C
AC -> E
ADE -> G
CG -> D
C -> B

1. Décomposition en 2ème forme normale (2FN)

Une relation est en 2ème forme normale (2FN) si elle est en 1ère forme normale (1FN) et que tous les attributs non-clés dépendent entièrement de la clé primaire, c’est-à-dire qu’il n’y a pas de dépendance partielle (dépendance d’un sous-ensemble de la clé).

Étape 1 : Identifier la clé primaire

À partir des dépendances fonctionnelles, nous devons identifier la clé primaire de la relation. Une clé candidate est un ensemble minimal d’attributs qui permet de déterminer tous les autres attributs de la relation.

D’après les dépendances minimales, nous pouvons observer :

• A détermine C (A -> C)
• Avec A et C, on détermine E (AC -> E)
• Avec A, D et E, on détermine G (ADE -> G)
• Avec C et G, on détermine D (CG -> D)
• C détermine B (C -> B)
• Ainsi, une clé primaire possible est A, D, E, car cet ensemble permet de déterminer tous les autres attributs de la relation.

Étape 2 : Vérifier les dépendances partielles

Pour être en 2FN, il ne doit pas y avoir de dépendances fonctionnelles où un attribut non-clé dépend d’une partie seulement de la clé primaire.

Dans notre cas, plusieurs dépendances montrent des dépendances partielles, comme A -> C et C -> B (C dépend de A, une partie de la clé primaire A, D, E). Il faut donc les éliminer en décomposant la relation.

Étape 3 : Décomposer la relation en 2FN

Nous allons décomposer la relation en plusieurs sous-relations pour éliminer les dépendances partielles :

• R1(A, C) : Relation pour la dépendance A -> C.
• R2(C, B) : Relation pour la dépendance C -> B.
• R3(AC, E) : Relation pour la dépendance AC -> E.
• R4(ADE, G) : Relation pour la dépendance ADE -> G.
• R5(CG, D) : Relation pour la dépendance CG -> D.

Ces relations sont maintenant en 2ème forme normale, car dans chaque relation, chaque attribut non-clé dépend entièrement de la clé.

2. Décomposition en 3ème forme normale (3FN)

Une relation est en 3ème forme normale (3FN) si elle est en 2FN et qu’il n’y a pas de dépendances transitive, c’est-à-dire qu’un attribut non-clé ne doit pas dépendre d’un autre attribut non-clé.

Étape 1 : Vérifier les dépendances transitives

Nous devons examiner chaque relation pour voir si des dépendances transitives existent :

R1(A, C) :

• A -> C
• Pas de dépendance transitive ici. Cette relation reste telle quelle.

R2(C, B) :

• C -> B
• Pas de dépendance transitive ici. Cette relation reste telle quelle.

R3(AC, E) :

• AC -> E
• Pas de dépendance transitive ici. Cette relation reste telle quelle.

R4(ADE, G) :

• ADE -> G
• Pas de dépendance transitive ici. Cette relation reste telle quelle.

R5(CG, D) :

• CG -> D
• Pas de dépendance transitive ici. Cette relation reste telle quelle.

Étape 2 : Résultat en 3ème forme normale

Après avoir éliminé la dépendance transitive dans R1, voici la décomposition finale en 3FN :

• R1'(A, C) : Pour la dépendance A -> C.
• R1''(C, B) : Pour la dépendance C -> B.
• R2(AC, E) : Pour la dépendance AC -> E.
• R3(ADE, B, G) : Pour les dépendances ADE -> B et ADE -> G.
• R4(CG, D) : Pour la dépendance CG -> D.

Conclusion

Décomposition en 2ème forme normale (2FN) :

• R1(A, C) : Relation pour la dépendance A -> C.
• R2(C, B) : Relation pour la dépendance C -> B.
• R3(AC, E) : Relation pour la dépendance AC -> E.
• R4(ADE, G) : Relation pour la dépendance ADE -> G.
• R5(CG, D) : Relation pour la dépendance CG -> D.

Décomposition en 3ème forme normale (3FN) :

• R1(A, C) : Relation pour la dépendance A -> C.
• R2(C, B) : Relation pour la dépendance C -> B.
• R3(AC, E) : Relation pour la dépendance AC -> E.
• R4(ADE, G) : Relation pour la dépendance ADE -> G.
• R5(CG, D) : Relation pour la dépendance CG -> D.

Exercice 3 - Corrigé

On considère une relation R construite sur les attributs :

R ( proprietaire, occupant, adresse, noApt, nbPieces, nbPersonnes )

et un nuplet (p, o, a, n, nb1, nb2) ayant la signification suivante :

La personne o habite avec nb2 personnes l’appartement de numéro n ayant nb1 pièces dont le propriétaire est p

Une analyse de cette relation nous fournit un ensemble initial E de dépendances fonctionnelles :

E {
  occupant → adresse
  occupant → noApt
  occupant → nbpersonnes
  adresse, noApt → proprietaire
  adresse, noApt → occupant
  adresse, noApt → nbPieces
}

1. Donner l’ensemble des dépendances fonctionnelles élémentaires engendrées par E

Fermeture transitive de E :

On a

occupant → adresse
occupant → noApt

On peut donc en déduire que

occupant → adresse, noApt

Par transitivité, on a donc :

occupant → proprietaire
occupant → nbPieces

Les DFE sont donc :

occupant → adresse, noApt, nbpersonnes, proprietaire, nbPieces
adresse, noApt → proprietaire, occupant, nbPieces, nbpersonnes

La DF adresse, noApt → nbpersonnes est obtenue par transitivité avec occupant

2. Quelles sont les clés potentielles de R ?

Une clé est un (ensemble d’) attribut qui dérive tous les autres.

En observant la fermeture transitive de E, on peut déduire que occupant et adresse,noApt les deux clés potentielles de R.

3. R est elle en 3ème forme normale ?

Pour déterminer la forme normale de R, il faut d’abord distinguer les attributs clés des attributs non clés :

• Attributs clés : adresse, occupant, noApt

• Attributs non clés : nbpersonnes, proprietaire, nbPieces

• Une relation est en forcément en 1ere forme normale si pas de données (on considère que les données sont atomiques)

• Elle est en 2eme forme normale si tous les attributs non clés dépendent pleinement des clés. Ici c’est le cas, aucun attribut non clé ne dépend que de adresse ou noApt.

• Une relation est en 3eme forme normale s’il n’existe pas de dépendance fonctionnelle entre deux attributs non clés

C’est le cas ici. R est donc en 3eme forme normale.

(Cela dit, il faudrait décomposer l’attribut adresse en attributs atomiques pour valider la 1ère forme normale )

Exercice 4 - Corrigé

On considère le schéma relationnel R défini sur les attributs suivants :

R (Cours, Professeur, Heure, Salle, Etudiant, Note)

et un nuplet (c, p, h, s, e, n) ayant la signification suivante :

Le cours c est fait par le professeur p à l’heure h dans la salle s par l’étudiant e qui a reçu la note n

L’ensemble E des dépendances fonctionnelles initiales est le suivant :

E {
  C → P
  HS → C
  HP → S
  CE → N
  HE → S
}

1. Donner l’ensemble des dépendances fonctionnelles élémentaires engendrées par E

Fermeture transitive de E

On a :

• C → P et HP → S donc HC → S
• HS → C et C → P donc HS → P
• HP → S et HS → C donc HP → C
• HE → S et HS → C donc HE → C donc HE → P
• HE → C et CE → N donc HE → N

En résumé on a :

C → P
HC → S
HS → CP
HP → SC
CE → N
HE → SCPN

2. Quelle est la clé de la relation R ? Montrer qu’elle est unique

De la fermeture transitive on déduit que HE est une clé potentielle (dérive tous les autres attributs).

Elle est unique car HE sont les seuls attributs qui ne sont pas en partie droite de DF. Donc ils appartiennent forcément à toutes les clés.

Comme HE est déjà une clé, il ne peut y en avoir d’autres (critère de minimalité).

3. Quelle est la forme normale de la relation R ? Si elle n’est pas en 3FN proposer une décomposition en 3FN

R est en 1ere forme normale (pas de données composées) uniquement.

On peut décomposer R en 4 relations R1, R2, R3 et R4 telles que :

• R1 (C, E, N)
• R2 (C, P)
• R3 (H, S, C) ou R3 (H, S, C)
• R4 (H, E, C)

R1 est obtenue en décomposant le schéma initial selon la DF CE → N. C’est la seule DF de R1 donc la clé est CE. R1 est bien évidemment en 3eme forme normale (une seule DF).

R2 est obtenue par la DF C → P. Là encore une seule DF, donc C est la clé de R2 et R2 est en 3eme forme normale.

R3 est obtenue par la DF HS → C ou la DF HC → S. Deux clés possibles HS ou bien HC. R3 est aussi en 3eme forme normale.

R4 est obtenue par la DF HE → C. La clé est donc HE et R4 est en 3eme forme normale.

Exercice 5 - Corrigé

Soit le schéma suivant :

ENSEIGNEMENT (NUM_TD, SALLE, JOUR, HEURE, NUM_ENSEIGNANT, NOM_ENSEIGNANT, PRENOM_ENSEIGNANT, CODE_UV, NOM_UV, NUM_ETUDIANT, NOM_ETUDIANT, PRENOM_ETUDIANT, ADRESSE_ETUDIANT, DATE_INSCRIPTION)

Les étudiants inscrits dans une UV (CODE_UV) sont répartis en groupe de TD (NUM_TD). La date d’inscription porte sur un étudiant dans une UV. Cette inscription l’affecte dans un groupe de TD.

Les hypothèses sont les suivantes :

• Un enseignant peut assurer l’encadrement de plusieurs groupes
• Un seul groupe de TD par salle à la même heure le même jour
• Un étudiant peut être inscrit dans plusieurs UV mais à un seul groupe de TD par UV
• Un enseignement d’une UV pour un groupe de TD a toujours lieu le même jour et dans la même salle à la même heure
• Un seul TD par semaine par UV

Questions :

1. A l’aide d’exemples, montrer quelles anomalies et redondances sont impliquées par ce schéma

   1. Redondance : Les salle et heure de TD figurent autant de fois que d’étudiants inscrits à ce groupe.
   2. Incohérence possible : Une mise à jour de l’heure d’un TD pourrait laisser la relation dans un état incohérent du fait de la redondance.
   3. Anomalies d’insertion : Il est impossible d’inscrire des étudiants si on ne connaît pas exactement les salles, heures et enseignants des TD (à moins d’introduire les valeurs nulles).
   4. Anomalies de suppression : Si l’on détruit le dernier étudiant d’un TD, on détruit en même temps les autres informations NUM_td, salle, heures, enseignants, …

2. Donner une couverture minimale des dépendances fonctionnelles, ainsi que sa fermeture transitive

Rappel

La couverture minimale d’un ensemble de DFE est un sous-ensemble minimum des DFE permettant de générer toutes les autres DFE. Synonymes : Famille génératrice

Couverture minimale des dépendances fonctionnelles :

CODE_UV → NOM_UV
NUM_ETUDIANT → NOM_ETUDIANT
NUM_ETUDIANT → PRENOM_ETUDIANT
NUM_ETUDIANT → ADRESSE_ETUDIANT
NUM_ENSEIGNANT → NOM_ENSEIGNANT
NUM_ENSEIGNANT → PRENOM_ENSEIGNANT
NUM_TD, CODE_UV → NUM_ENSEIGNANT
NUM_ETUDIANT, CODE_UV → NUM_TD
NUM_ETUDIANT, CODE_UV → DATE_INSCRIPTION
NUM_TD, CODE_UV → SALLE
NUM_TD, CODE_UV → HEURE
NUM_TD, CODE_UV → JOUR
SALLE, HEURE, JOUR → NUM_TD
SALLE, HEURE, JOUR → CODE_UV

Fermeture transitive des dépendances fonctionnelles :

• A partir de NUM_TD, CODE_UV → NUM_ENSEIGNANT et NUM_ENSEIGNANT → NOM_ENSEIGNANT, on obtient : NUM_TD, CODE_UV → NOM_ENSEIGNANT
• A partir de NUM_TD, CODE_UV → NUM_ENSEIGNANT et NUM_ENSEIGNANT → PRENOM_ENSEIGNANT, on obtient : NUM_TD, CODE_UV → PRENOM_ENSEIGNANT
• A partir de NUM_ETUDIANT, CODE_UV → NUM_TD et NUM_TD, CODE_UV → SALLE, on obtient : NUM_ETUDIANT, CODE_UV → SALLE
• A partir de NUM_ETUDIANT, CODE_UV → NUM_TD et NUM_TD, CODE_UV → HEURE, on obtient : NUM_ETUDIANT, CODE_UV → HEURE
• A partir de NUM_ETUDIANT, CODE_UV → NUM_TD et NUM_TD, CODE_UV → JOUR, on obtient : NUM_ETUDIANT, CODE_UV → JOUR
• A partir de SALLE, HEURE, JOUR → NUM_TD et NUM_TD → CODE_UV, on obtient : SALLE, HEURE, JOUR → CODE_UV

    
flowchart LR
NUM_TD,CODE_UV --> NOM_ENSEIGNANT
NUM_TD,CODE_UV --> PRENOM_ENSEIGNANT
NUM_ETUDIANT,CODE_UV --> SALLE
NUM_ETUDIANT,CODE_UV --> HEURE
NUM_ETUDIANT,CODE_UV --> JOUR
SALLE,HEURE,JOUR --> CODE_UV

3. Soit la décomposition suivante :

ENSEIGNEMENT (NUM_TD, CODE_UV, HEURE, SALLE, JOUR, NUM_ENSEIGNANT, NOM_ENSEIGNANT, PRENOM_ENSEIGNANT)

INSCRIPTION (NUM_ETUDIANT, NOM_ETUDIANT, PRENOM_ETUDIANT, ADRESSE_ETUDIANT, CODE_UV, NOM_UV, DATE_INSCRIPTION, NUM_TD)

• a. Quelles sont les clés de ces relations ? Montrez que cette décomposition est sans perte et qu’elle préserve les dépendances fonctionnelles.

Clés :

• (NUM_TD, CODE_UV) pour ENSEIGNEMENT
• (NUM_ETUDIANT, CODE_UV) pour INSCRIPTION

Sans perte :

Car on retrouve les tuples de la relation initiale, en effectuant une jointure sur (Code UV, NUM_TD)

Dépendances conservées : En faisant l’union des DF de “ENSEIGNEMENT” et “INSCRIPTION”, on retrouve la couverture minimale des DF, leurs fermetures sont donc les mêmes.

• b. Existe-t-il encore des risques d’anomalies ou des redondances ?

Redondance : A chaque inscription d’un étudiant il y a répétition du nom du module.

• c. Les relations sont-elles en 2ème forme normale ?

2ème forme normale : La première relation est bien en 2ème forme normale, la deuxième n’y est pas car par exemple NOM_ETUDIANT ne dépend que d’une partie de la clé : NUM_ETUDIANT.

4. Soit la décomposition suivante :

ENSEIGNEMENT (NUM_TD, CODE_UV, HEURE, SALLE, JOUR, NUM_ENSEIGNANT, NOM_ENSEIGNANT, PRENOM_ENSEIGNANT)

ETUDIANT (NUM_ETUDIANT, NOM_ETUDIANT, PRENOM_ETUDIANT, ADRESSE_ETUDIANT)

INSCRIPTION (NUM_ETUDIANT, CODE_UV, DATE_INSCRIPTION, NUM_TD)

UV (CODE_UV, NOM_UV)

• • a. Quelles sont les clés de ces relations ? Montrez que cette décomposition est sans perte et qu’elle préserve les dépendances fonctionnelles.
  • b. Existe-t-il encore des risques d’anomalies ou des redondances ?
  • c. Les relations sont-elles en 2ème forme normale ?

Clés :

• (NUM_TD, CODE_UV) pour ENSEIGNEMENT
• (NUM_ETUDIANT) pour ETUDIANT
• (NUM_ETUDIANT, CODE_UV) pour INSCRIPTION
• CODE_UV pour UV

Sans perte :

On retrouve la relation “INSCRIPTION” de la question 3 en effectuant deux jointures :

• une sur NUM_ETUDIANT, entre ETUDIANT et INSCRIPTION
• l’autre sur CODE_UV entre le résultat de la précédente et UV

Dépendances conservées :

De la même manière que précédemment, en faisant l’union de ces DF on retrouve la couverture minimale de la relation INSCRIPTION précédente, et donc cette décomposition conserve les dépendances fonctionnelles.

Redondances :

Dans ENSEIGNEMENT les nom de l’enseignant est répété plusieurs fois.

2ème forme normale : Les quatre relations sont en 2ème forme normale, car aucun attribut ne dépend que d’un sous ensemble d’une clé.

5. Les relations sont-elles en 3ème forme normale ?

Si ce n’est pas le cas, proposez une nouvelle décomposition (sans perte et conservant les dépendances fonctionnelles).

La relation ENSEIGNEMENT n’est pas en troisième forme normale.

En effet, l’attribut NOM_ENSEIGNANT dépend de NUM_ENSEIGNANT qui n’est pas un attribut clé.

Une décomposition possible est :

ENSEIGNANT (NUM_ENSEIGNANT, NOM_ENSEIGNANT, PRENOM_ENSEIGNANT)

TD (NUM_TD, Code UV, HEURE, SALLE, JOUR, NUM_ENSEIGNANT)

Elle est sans perte, on retrouve la relation initiale en effectuant une jointure sur NUM_ENSEIGNANT.

Dépendances fonctionnelles conservées : En faisant l’union des DF, on retrouve celles de “ENSEIGNEMENT” de la question précédente. Leurs fermetures sont donc identiques.

3eme forme normale : La relation TD est bien en 3ème forme normale, car NUM_TD et Code UV dépendent effectivement d’attributs non clés, mais font eux-même partie d’une clé (voir définition de la 3eme forme normale).