Série d’Exercices 2

Exercice 1 - Vérification des dépendances fonctionnelles

Pour vérifier si une dépendance fonctionnelle (DF) X → Y s'applique à une instance de relation, nous devons nous assurer que pour chaque paire de n-uplets (lignes) ayant la même valeur pour l'attribut X, ils ont obligatoirement la même valeur pour l'attribut Y.

Dressons d'abord le tableau de l'instance de la relation R(A, D, E, G) donnée dans l'énoncé :

n-uplet	A	D	E	G
t1	0	0	0	0
t2	1	2	3	5
t3	1	3	3	3
t4	2	5	3	2
t5	2	0	4	0

Testons les dépendances fonctionnelles de l'ensemble F = {A → E; D → G; E → G} :

• A → E : Non vérifiée. Les n-uplets t4 et t5 possèdent la même valeur pour A (A = 2). Cependant, la valeur de E pour t4 est 3, tandis que la valeur de E pour t5 est 4. Puisque 3 ≠ 4, la DF n'est pas vérifiée.
• D → G : Vérifiée. Les valeurs de D sont 0 (t1, t5), 2 (t2), 3 (t3), et 5 (t4). Les seules lignes partageant la même valeur de D sont t1 et t5 (D = 0). Pour ces deux lignes, la valeur de G est identique (G = 0). La contrainte est donc respectée pour toutes les données.
• E → G : Non vérifiée. Les n-uplets t2, t3 et t4 partagent la même valeur pour E (E = 3). Cependant, leurs valeurs pour G sont toutes différentes (5, 3 et 2).

Conclusion : Parmi les dépendances fonctionnelles proposées, seule D → G est vérifiée dans cette instance.

Exercice 2 - Analyse d'une relation et formes normales

Commençons par organiser les instances de la relation R(A, B, C, D, E) sous forme de tableau :

n-uplet	A	B	C	D	E
t1	a1	b2	c2	d3	e2
t2	a1	b2	c2	d1	e4
t3	a2	b3	c2	d1	e5
t4	a2	b4	c5	d1	e5

Question 1 - Dépendances fonctionnelles qui ne s'appliquent pas

Nous devons identifier quelles dépendances fonctionnelles sont fausses au regard des données.

• E → D : S'applique. Les valeurs de E sont e2, e4, e5, e5. Les deux lignes ayant E = e5 (t3, t4) ont la même valeur D = d1.
• C → A : Ne s'applique pas. Les lignes t1 et t3 ont C = c2, mais des valeurs A différentes (a1 pour t1, a2 pour t3).
• E → A : S'applique. Les lignes partageant E = e5 (t3, t4) ont la même valeur A = a2.
• D → E : Ne s'applique pas. Les lignes t2 et t3 ont D = d1, mais des valeurs E différentes (e4 pour t2, e5 pour t3).
• E → B : Ne s'applique pas. Les lignes t3 et t4 ont E = e5, mais des valeurs B différentes (b3 et b4).
• B → A : S'applique. Les lignes partageant B = b2 (t1, t2) ont la même valeur A = a1.
• B → C : S'applique. Les lignes partageant B = b2 (t1, t2) ont la même valeur C = c2.
• B → D : Ne s'applique pas. Les lignes t1 et t2 ont B = b2, mais des valeurs D différentes (d3 et d1).

Réponse : Les dépendances fonctionnelles qui ne s'appliquent pas à R sont C → A, D → E, E → B, et B → D.

Question 2 - Trouver une clé pour R

Pour déterminer une clé valide pour cette relation (en se basant sur les DF qui s'appliquent : E → D, E → A, B → A, B → C), nous devons trouver un ensemble d'attributs qui détermine tous les autres, et qui est minimal.

Prenons la combinaison des attributs sources des DF valides : {B, E}.

• B détermine C (B → C) et B détermine A (B → A).
• E détermine D (E → D) et E détermine A (E → A). Par conséquent, l'ensemble {B, E} permet de déterminer fonctionnellement {A, C, D}. Ainsi, {B, E} → {A, B, C, D, E}.

Vérifions si cet ensemble est unique pour chaque ligne de notre instance : (b2, e2), (b2, e4), (b3, e5), (b4, e5). Les quatre paires sont uniques. Ni B seul, ni E seul ne garantissent l'unicité des lignes.

Réponse : L'ensemble {B, E} est une clé pour R. (Note : sur la seule base des instances, {B, D} ou {C, E} forment également des combinaisons uniques, mais {B, E} est la réponse la plus logique déductible des règles fonctionnelles observées).

Question 3 - Forme normale de la relation

Notre clé primaire est constituée de deux attributs : {B, E}.

• La relation respecte la 1NF car tous ses attributs contiennent des valeurs atomiques.
• Cependant, il existe des dépendances partielles : l'attribut C dépend uniquement de B (B → C), et l'attribut D dépend uniquement de E (E → D). Des attributs non-clés dépendent donc d'une partie de la clé primaire.

Réponse : La relation est en Première Forme Normale (1NF). Elle ne peut pas être en 2NF à cause des dépendances fonctionnelles partielles.

Exercice 3 - Modélisation des bureaux et équipements

Question 1 - Vérification des contraintes métiers

(a) Un bureau peut contenir plusieurs postes téléphoniques.

• Faux (Non vérifiée). La dépendance "NumBureau → NumTelephone" indique que pour un numéro de bureau donné, il ne peut y avoir qu'un seul numéro de téléphone associé dans la base de données.

(b) Il y a une et une seule personne par bureau.

• Faux (Non vérifiée). La dépendance "NumBureau → PersonneID" dans la relation Occupant signifie qu'un bureau contient au plus une personne (il est impossible d'avoir deux lignes avec le même bureau et des personnes différentes). Cependant, si un bureau n'est pas inséré dans la table Occupant, il aura zéro personne. La formulation "une et une seule" implique une présence obligatoire qui n'est pas garantie par cette simple DF.

(c) Un bureau contient un seul ordinateur.

• Faux (Non vérifiée). La dépendance de la table Materiel est "NumPC → NumBureau". Cela signifie qu'un ordinateur spécifique est affecté à un seul bureau. En revanche, l'énoncé ne fournit pas "NumBureau → NumPC", il est donc tout à fait possible d'affecter plusieurs NumPC différents au même NumBureau.

Question 2 - Clés minimales de chaque relation

• Relation Bureau(NumBureau, NumTelephone, Taille) : Nous avons NumBureau → NumTelephone, Taille. Donc {NumBureau} détermine tous les attributs, c'est une clé. Nous avons aussi NumTelephone → NumBureau. Par transitivité, NumTelephone détermine NumBureau qui détermine Taille. Donc {NumTelephone} est aussi une clé. Clés minimales : {NumBureau} et {NumTelephone}.

• Relation Occupant(NumBureau, PersonneID) : Nous avons NumBureau → PersonneID. Clé minimale : {NumBureau}.

• Relation Materiel(NumBureau, NumPC) : Nous avons NumPC → NumBureau. Clé minimale : {NumPC}.

Exercice 4 - Dépendances fonctionnelles d'une société de transport

La relation est : Affectation (N°ligne, N°conducteur, jour)

• 1. Un conducteur ne peut pas travailler sur deux lignes différentes le même jour : La connaissance du conducteur et du jour suffit à déterminer une ligne unique. DF : N°conducteur, jour → N°ligne

• 2. Un conducteur ne fait qu'une seule ligne : Quelle que soit la date, un conducteur est toujours rattaché à la même ligne. DF : N°conducteur → N°ligne

• 3. Une ligne n'est parcourue que par un seul conducteur : La connaissance de la ligne permet d'identifier formellement le conducteur de celle-ci, de manière absolue. DF : N°ligne → N°conducteur

• 4. Un conducteur ne fait pas la même ligne deux jours différents : La connaissance d'un conducteur et d'une ligne spécifique ne peut correspondre qu'à un seul jour d'affectation. DF : N°conducteur, N°ligne → jour

Exercice 5 - Base de données utilisateurs

Relation R(UtilisateurID, Nom, Prénom, AdresseEmail, Login, Passwd, ServeurMail).

Question 1 - Expression des contraintes en dépendances fonctionnelles

• (a) On peut déduire le nom et le prénom d'un utilisateur à partir de son identificateur : UtilisateurID → Nom, Prénom
• (b) Un utilisateur possède un seul login et un seul password par serveur de mails : (UtilisateurID, ServeurMail) → Login, Passwd
• (c) Une adresse email est associée à un et un seul identificateur d'utilisateur : AdresseEmail → UtilisateurID
• (d) Une adresse email est associée à un et un seul serveur de mails : AdresseEmail → ServeurMail

Question 2 - Clés minimales de R

Pour trouver les clés, cherchons la fermeture transitive (notée +) de nos attributs en partant des dépendances énoncées ci-dessus. Regardons l'attribut AdresseEmail. Cet attribut n'apparaît à droite d'aucune dépendance fonctionnelle ; il ne peut donc pas être déduit d'un autre attribut et doit obligatoirement faire partie de la clé. Calculons sa fermeture {AdresseEmail}+ :

1. Par défaut : {AdresseEmail}
2. Grâce à (c) et (d), on obtient : {AdresseEmail, UtilisateurID, ServeurMail}
3. Grâce à (a) avec UtilisateurID, on ajoute Nom et Prénom : {AdresseEmail, UtilisateurID, ServeurMail, Nom, Prénom}
4. Grâce à (b) avec (UtilisateurID, ServeurMail), on ajoute Login et Passwd : {AdresseEmail, UtilisateurID, ServeurMail, Nom, Prénom, Login, Passwd}

L'attribut AdresseEmail permet à lui seul de déterminer la totalité des attributs de la relation R. Puisqu'il est constitué d'un seul attribut, il est obligatoirement minimal.

Réponse : L'unique clé minimale de R est {AdresseEmail}.

Question 3 - Forme normale de la relation R

Évaluons la forme normale par étapes :

1. 1NF : Les attributs sont atomiques. La relation est au moins en 1NF.
2. 2NF : La 2NF exige que tout attribut non-clé dépende de la totalité de la clé primaire. Notre clé {AdresseEmail} étant composée d'un seul attribut, il est impossible d'avoir une dépendance partielle sur une fraction de la clé. La relation est donc en 2NF.
3. 3NF : La 3NF exige de ne pas avoir de dépendances transitives (un attribut non-clé dépendant d'un autre attribut non-clé). Or, nous avons la dépendance UtilisateurID → Nom, Prénom. Ici, l'attribut UtilisateurID n'est pas une clé de la relation. Nous avons donc la chaîne : AdresseEmail → UtilisateurID → Nom. Ceci est une dépendance transitive qui viole la 3NF.

Réponse : La relation R est en Deuxième Forme Normale (2NF).

Méthode

Face à un examen sur les dépendances fonctionnelles (DF) et la normalisation :

1. Valider sur instance (Ex 1 & 2) : Une DF X → Y est une règle absolue. Pour la prouver fausse, il suffit de trouver un seul contre-exemple dans les données (deux lignes avec le même X mais un Y différent). Pour prouver qu'elle s'applique sur un échantillon, il faut s'assurer qu'aucune paire de lignes ne la contredit.
2. Passage au français (Ex 3 & 4) : Identifiez l'élément de départ ("Si je connais ceci...") qui devient la partie gauche de la flèche, et l'élément déduit ("...alors il n'y a qu'une seule réponse possible pour cela") qui devient la partie droite. Les notions de "au plus un" se traduisent directement par une DF.
3. Recherche de clé (Ex 5) : Repérez toujours les attributs qui ne figurent jamais à droite d'une DF. Ils sont les points de départ obligatoires de vos clés. Calculez leur fermeture transitive pour voir s'ils couvrent toute la relation.
4. Normalisation : Mémorisez la progression stricte. Un seul attribut en clé primaire garantit toujours la 2NF. Les dépendances entre deux attributs "non-clés" bloquent toujours l'accès à la 3NF.