Exercices

Une solution possible :

Dans cette relation on peut identifier les DF :

• \((X,Y) \rightarrow Z\).
• \(Y \rightarrow Z\).

Puisque à chaque couple de valeurs de \((X,Y)\) ou à chaque valeur de \(Y\) correspond une seule valeur de \(Z\).

\(Y\) est le seul attribut pour lequel à chaque valeur correspond une seule et même valeur de l’attribut \(Z\).

En effet :

• \(Y \nrightarrow X\)

  • \(y1 \rightarrow x1\)
  • \(y1 \rightarrow x2\)

• \(X \nrightarrow Y\)

  • \(x2 \rightarrow y1\)
  • \(x2 \rightarrow y2\)

• \(X \nrightarrow Z\)

  • \(x2 \rightarrow z1\)
  • \(x2 \rightarrow z2\)

• \(Z \nrightarrow X\)

  • \(z1 \rightarrow x1\)
  • \(z1 \rightarrow x2\)

• \(Z \nrightarrow Y\)

  • \(z2 \rightarrow y2\)
  • \(z2 \rightarrow y3\)

De la même manière :

• \(Y \nrightarrow X\):

  • \(y1 \rightarrow x1\)
  • \(y1 \rightarrow x2\)

• \(X \nrightarrow Y\).

  • \(x2 \rightarrow y1\)
  • \(x2 \rightarrow y2\)

• \(X \nrightarrow Z\)

  • \(x2 \rightarrow z1\).
  • \(x2 \rightarrow z2\).

• \(Z \nrightarrow Y\)

  • \(z1 \rightarrow x1\)
  • \(z1 \rightarrow x2\)

Une solution possible :

Oui, le prix dépend fonctionnellement du produit :

• \(produit \rightarrow prix\).

C’est le seul attribut pour lequel à chaque valeur correspond une seule et même valeur de l’attribut \(prix\).

Par contre \(client \nrightarrow produit\) (connaître un client ne veut pas dire que l’on sait exactement le produit qu’il va acheter)

En effet à une même valeur de \(client (ex: Maxime)\) correspond deux valeurs différentes de \(produit (poivre,piment)\)

De la même manière :

• \(prix \nrightarrow produit\) : le prix ne permet pas de retrouver le produit
• \(prix \nrightarrow client\) : le prix ne détermine pas le client (mais peut le dissuader d’acheter le produit)
• \(produit \nrightarrow client\) : connaître le produit ne veut pas dire qu’on connait le client (quoique …)
• \(client \nrightarrow prix\) : connaître le client ne permet pas de retrouver le prix du produit

Une solution possible :

Pour chaque enregistrement la valeur de l’attribut \(C\) est différente. Donc si on connait la valeur de \(C\) on retrouve les valeurs des attributs \((A,B,D,E)\).

• \(C \rightarrow (A,B,D,E)\) représente donc une DF.

En utilisant l’axiome de décomposition on peut décomposer la DF en faisant apparaître un seul attribut cible :

• \(C \rightarrow A\)
• \(C \rightarrow B\)
• \(C \rightarrow D\)
• \(C \rightarrow E\)

Comme il n’y a qu’un seul attribut source, il ne peut donc y avoir de sous-ensemble qui soit une DF sur l’attribut cible.

La DF :

• \(C \rightarrow (A,B,D,E)\)

représente donc 4 DFE.

Une solution possible :

Un sous-ensemble de l’ensemble des attributs \((A,B,C)\) suffit pour déterminer les valeurs des attributs \((D,E)\)

Les DF \((A,B,C) \rightarrow D\) et \((A,B,C) \rightarrow E\) ne peuvent donc pas être retenues dans l’ensemble des DFE.

Une solution possible :

1. \(A \rightarrow E\)
2. \(B \rightarrow E\)
3. \(C \rightarrow (A,B,D,E)\)
4. \(D \rightarrow E\)
5. \((A,B) \rightarrow D\)
6. \((A,D) \rightarrow B\)
7. \((B,D) \rightarrow A\)

Les quatre premières DF s’expliquent du fait qu’il n’y a qu’un seul élément (une seule valeur) dans l’ensemble \(E\) sur tous les enregistrements, l’attribut E dépend donc fonctionnellement de chaque attribut de la relation \((A,B,C,D)\). Ce sont des DFE car il n’y a qu’un attribut cible et, du fait que la source de la DF n’est constitué que d’un seul attribut, il n’existe pas de sous-ensemble des attributs source qui pourraient représenter une DF sur l’attribut \(E\) .

Comme les valeurs de l’attribut \(C\) sont toutes différentes, chacun des autres attributs dépend fonctionnellement de l’ensemble \(C\). En utilisant des axiomes d’additivité et de décomposition on peut donc grouper les DFE en une seule DF \(C \rightarrow (A,B,D,E)\) puis les dégrouper pour obtenir les DFE.

Il ne pourra y avoir de combinaison des attributs \((A,B,C,D)\) en tant qu’attributs source pour déterminer l’attribut cible \(E\) puisqu’avec les DFE précédentes il y aura toujours un sous-ensemble de ces combinaisons qui suffira à déterminer les valeurs de \(E\).

La cinquième DF peut-être retenue en tant que DFE car pour chaque valeur combinée des attributs \((A,B)\), il n’y a qu’une seule valeur associée de l’attribut \(D\). Ce ne sera pas le cas pour les 2 sous-ensembles possibles de ces 2 attributs source. Par contre \((A,B) \rightarrow C\) ne sera pas une DF car il peut correspondre des valeurs différentes de l’attribut cible pour un même combinaison des valeurs des attributs sources \(A,B\).

De même, la sixième DF peut-être retenue en tant que DFE car pour chaque valeur combinée des attributs \((A,D)\), il n’y a qu’une seule valeur associée de l’attribut \(B\). Par contre il n’y a pas une seule valeur correspondante de l’attribut \(C\).

La dernière DF peut aussi être retenue en tant que DFE car pour chaque valeur combinée des attributs \((B,D)\), il n’y a qu’une seule valeur associée de l’attribut \(A\). Par contre il n’y a pas une seule valeur correspondante de l’attribut \(C\).

Une solution possible :

SELECT X,Y,Z FROM R1 NATURAL JOIN R2;

C’est la seule décomposition pour laquelle la différence des groupes d’attributs des deux relations \(R_1(X,Y), R_2(Y,Z)\)

• \(Z=\setminus((Y,Z),(X,Y))\)

dépend fonctionnellement de l’intersection de ces mêmes groupes d’attributs :

• \(Y=\cap((Y,Z),(X,Y)))\)

Du fait de la seule DF du schéma relationnel : \(Y \rightarrow Z\)

Alors que pour les relations \(R_2(Y,Z),R_3(X,Z)\)

• \(Y=\setminus((Y,Z),(X,Z))\)
• \(X=\setminus((X,Z),(Y,Z))\)

\(X,Y\) ne dépendent pas fonctionnellement de \(Z\)

• \(Z=\cap((Y,Z),(X,Z))\)

Ainsi que pour les relations \(R_1(X,Y),R_3(X,Z)\)

• \(Y=\setminus((X,Y),(X,Z))\)
• \(Z=\setminus((X,Z),(X,Y))\)

\(Y,Z\) ne dépendent pas fonctionnellement de \(X\)

• \(X=\cap((X,Y),(X,Z))\)

Une solution possible :

SELECT client,produit,prix FROM preferences NATURAL JOIN produits;

C’est la seule décomposition pour laquelle la différence :

• \(prix=\setminus((produit,prix),(client,produit))\)

des groupes d’attributs des deux relations :

• \(preferences(client,produit), produits(produit,prix)\)

dépend fonctionnellement de l’intersection de ces mêmes groupes d’attributs :

• \(produit=\cap((client,produit),(produit,prix))\)

Du fait de la DFE identifiée dans l’instance de la relation d’origine :

• \(produit \rightarrow prix\)

Pour la décomposition :

• \(preferences(client,produit),depenses(client,prix)\) :

La différence (\(produit\) ou \(prix\)):

• \(produit=\setminus((client,produit),(client,prix))\)
• \(prix=\setminus((client,prix),(client,produit))\)

des groupes d’attributs ne dépendent pas fonctionnellement de l’intersection (\(client\)) de ces mêmes groupes d’attributs:

• \(client=\cap((client,prix),(client,produit))\)

Connaître le client ne permet pas de retrouver le produit ou le prix.

De même, pour la décomposition en relations :

• \(produits(produit,prix),depenses(client,prix)\)

La différence (\(produit\) ou \(client\)) :

• \(produit=\setminus((produit,prix),(client,prix))\)
• \(client=\setminus((client,prix),(produit,prix))\)

des groupes d’attributs ne dépendent pas fonctionnellement de l’intersection (\(prix\)) de ces mêmes groupes d’attributs:

• \(prix=\cap((client,prix),(produit,prix))\)

Connaître le prix ne permet pas de retrouver le produit ou le client.

Tests SQL :

Une solution possible :

On est en 2NF :

• par transitivité (\(A \rightarrow B,B \rightarrow C\)) on trouve la DF : \(A \rightarrow C\)
• donc par additivité on obtient la DF : \(A \rightarrow (B,C)\)
• par conséquent la clé est constitué d’un seul attribut \(A\) ce qui veut dire qu’on est en 2NF car il ne peut y avoir de sous-ensemble de la clé qui détermine les autres attributs.
• Cette relation n’est pas en 3NF du fait de la dépendance transitive \(A \rightarrow B, B \rightarrow C\)

Une solution possible :

Non car à une même valeur de l’attribut \(B\) correspond deux valeurs différentes de l’attribut \(C\):

• \(b1 \rightarrow c1\)
• \(b1 \rightarrow c2\)

ce qui contredit la dépendance fonctionnelle \(B \rightarrow C\).

Il suffirait d’enlever le deuxième enregistrement \((a2,b1,c2)\) pour que la DF \(B \rightarrow C\) soit respectée.

Une solution possible :

On peut identifier dans cette instance de relation la DF \(A \rightarrow (B,C)\). En effet, à chaque valeur de l’attribut \(A\) correspond une seule valeur de l’attribut \(B\) :

• \(A \rightarrow B\)

A chaque valeur de l’attribut \(A\) correspond une seule valeur de l’attribut \(C\) :

• \(A \rightarrow C\)

L’instance de relation est en 3NF car un seul attribut permet de retrouver les deux autres et il n’y a pas de dépendances transitive entre les attributs.

Une solution possible :

La jointure naturelle :

• \(\Join_{[R_1.A=R_2.A]}(R_1,R_2)\)

permettra de reconstituer la table d’origine du fait de la DF \(A \rightarrow (B,C)\) que l’on a sur l’instance de la relation \(R(A,B,C)\).

En effet, d’après le théorème de Heath lors de la décomposition, la différence des ensembles d’attributs devra dépendre fonctionnellement de l’intersection des deux ensembles d’attributs.

Or :

• \(A=\cap((A,B),(A,C))\)
• \(B=\setminus((A,B),(A,C))\)
• \(C=\setminus((A,C),(A,B))\)

Donc :

• \(\cap((A,B),(A,C)) \rightarrow \setminus((A,B),(A,C))\)
• \(\cap((A,B),(A,C)) \rightarrow \setminus(((A,C),A,B))\)

Par conséquent on peut décomposer la table :

• \(R(A,B,C)\)

en deux tables :

• \(R_1(A,B)\)
• \(R_2(A,C)\)

sans perte d’information.

Création de la table \(R(A,B,C)\)

CREATE TABLE R (
                A  char(2),
                B  char(2),
                C  char(2)
               );

INSERT INTO R VALUES('a1','b1','c1');
INSERT INTO R VALUES('a2','b1','c2');
INSERT INTO R VALUES('a3','b1','c1');
INSERT INTO R VALUES('a4','b2','c2');


CREATE TABLE R1 (
                A  char(2),
                B  char(2)
               );

INSERT INTO R1 VALUES('a1','b1');
INSERT INTO R1 VALUES('a2','b1');
INSERT INTO R1 VALUES('a3','b1');
INSERT INTO R1 VALUES('a4','b2');


CREATE TABLE R2 (
                A  char(2),
                C  char(2)
               );

INSERT INTO R2 VALUES('a1','c1');
INSERT INTO R2 VALUES('a2','c2');
INSERT INTO R2 VALUES('a3','c1');
INSERT INTO R2 VALUES('a4','c2');


CREATE TABLE R3 (
                 B  char(2),
                 C  char(2)
                );

INSERT INTO R3 VALUES('b1','c1');
INSERT INTO R3 VALUES('b1','c2');
INSERT INTO R3 VALUES('b2','c2');

-- Vérification des jointures naturelles.

SELECT * FROM R;
SELECT * FROM R1 NATURAL JOIN R2;
SELECT * FROM R1 NATURAL JOIN R3;
SELECT A,B,C FROM R2 NATURAL JOIN R3;

Une solution possible :

Une solution possible :

Non car un sous-ensemble de la clé (attributs soulignés) permet de retrouver les attributs non-primitifs (attributs cible):

• \(prod\_id \rightarrow producteur\_nom\)

Quelle décomposition sans perte d’information peut-on faire ?

En appliquant le théorème de Heath on peut répartir les informations dans les deux relations suivantes :

• \(pieces(\underline{piece\_id, prod\_id},quantite)\)
• \(producteur(\underline{prod\_id},producteur\_nom)\)

car la différence des groupes d’attributs dépend fonctionnellement de l’intersection des groupes d’attributs

• \(producteur\_nom=\setminus((prod\_id,producteur\_nom),(piece\_id, prod\_id,quantite))\)
• \(prod\_id=\cap((prod\_id,producteur\_nom),(piece\_id, prod\_id,quantite))\)

On obtient ainsi un schéma relationnel en 2NF :

• Il faut connaître l’identifiant de la pièce et du producteur pour connaître la quantite produite
• L’identifiant du producteur suffit pour retrouver son nom.

Une solution possible :

On est en 2NF car la clé ne contient qu’un seul attribut mais la relation n’est pas en 3NF du fait de la dépendance transitive (\(avion \rightarrow pilote\)) entre attributs non-clés.

Il y aura donc des problèmes de mises à jour. En effet, il ne sera pas possible d’introduire un nouvel avion sur un nouveau vol sans préciser un nom de pilote.

Pour éviter ce problème on pourrait proposer la décomposition suivante de la relation :

• \(vols(\underline{vol},avion)\)
• \(pilotes(\underline{vol},pilote)\)

qui permet de résoudre ce problème de dépendance entre attributs non-clés et de respecter la 3NF mais pas celui de la mise à jour (on perd la DF \(avion \rightarrow pilote\)).

Une décomposition basée sur le théorème de Heath permettra de préserver cette DF :

• \(avions(\underline{avion},pilote)\)
• \(vols(\underline{vol},avion)\)

où la différence des ensembles d’attributs :

• \(pilote=\setminus((avion,pilote),(vol,avion))\)

dépend fonctionnellement de l’intersection :

• \(avion=\cap((avion,pilote),(vol,avion))\)

Avec cette décomposition on évitera les problèmes de mises à jour et on pourra retrouver les informations de la relation initiale par jointure naturelle entre les deux relations.

Une solution possible :

CREATE TABLE compagnies (
                         vol char(7),
                         avion  char(5),
                         pilote  char(20)
                         );

INSERT INTO compagnies VALUES('AA 1234','B 747','Roger');
INSERT INTO compagnies VALUES('AA 5678','B 747','Roger');
INSERT INTO compagnies VALUES('AF 1234','A 320','Alfred');
INSERT INTO compagnies VALUES('AF 5678','A 380','Alfred');

Une solution possible :

On identifie sur cette instance de relation les DFE suivantes :

• \(vol \rightarrow avion\)
• \(avion \rightarrow pilote\)
• \(vol \rightarrow pilote\)

puisqu’à un vol correspond un seul avion, à un avion correspond un seul pilote et (donc) à un vol correspond un seul pilote.

Par contre à un avion peut correspondre plusieurs vols et à un pilote peut correspondre plusieurs avions ou vols.

• \(avion \nrightarrow vol\)
• \(pilote \nrightarrow avion\)
• \(pilote \nrightarrow vol\)

Une solution possible :

CREATE TABLE vols (
                   vol char(7),
                   avion  char(5)
                  );

INSERT INTO vols VALUES('AA 1234','B 747');
INSERT INTO vols VALUES('AA 5678','B 747');
INSERT INTO vols VALUES('AF 1234','A 320');
INSERT INTO vols VALUES('AF 5678','A 380');


CREATE TABLE pilotes (
                      vol char(7),
                      pilote  char(20)
                     );

INSERT INTO pilotes VALUES('AA 1234','Roger');
INSERT INTO pilotes VALUES('AA 5678','Roger');
INSERT INTO pilotes VALUES('AF 1234','Alfred');
INSERT INTO pilotes VALUES('AF 5678','Alfred');

SELECT * FROM vols NATURAL JOIN pilotes;

Une solution possible :

La décomposition de la table compagnies(vol,avion,pilote) en :

• vols(vol,avion)
• pilotes(vol,pilote)

permettra par jointure naturelle de retrouver l’instance de table initiale.

Par contre après mise à jour de l’élément :

UPDATE vols SET avion='A 380' WHERE vol='AA 1234';

la jointure naturelle entre les relations vols,pilotes :

• \(\Join_{[vols.vol=pilotes.vol]}(vols,pilotes)\)

donnera un résultat qui ne respectera pas la dépendance fonctionnelle :

• \(avion \rightarrow pilote\)

puisqu” Alfred et Roger pourront tous les deux piloter le boeing A 380.

Cette décomposition fait perdre la DFE identifiée dans la relation d’origine :

• \(avion \rightarrow pilote\)

Une solution possible :

Si sur la relation :

• \(compagnies(vol,avion,pilote)\)

on a les DFE :

• \(vol \rightarrow avion\)
• \(avion \rightarrow pilote\)
• \(vol \rightarrow pilote\)

On peut faire la décomposition suivante

• \(vols(vol,avion)\)
• \(avions(avion,pilote)\)

qui permettra de préserver la DFE :

• \(vol \rightarrow pilote\)

par l’axiome d’Armstrong de transitivité :

• \(X \rightarrow Y, Y\rightarrow Z \Longrightarrow X \rightarrow Z\)

On peut donc créer les tables suivantes :

CREATE TABLE vols (
                   vol char(7),
                   avion  char(5)
                  );

INSERT INTO vols VALUES('AA 1234','B 747');
INSERT INTO vols VALUES('AA 5678','B 747');
INSERT INTO vols VALUES('AF 1234','A 320');
INSERT INTO vols VALUES('AF 5678','A 380');

CREATE TABLE avions (
                avion  char(5),
                pilote  char(20)
               );

INSERT INTO avions VALUES('B 747','Roger');
INSERT INTO avions VALUES('A 320','Alfred');
INSERT INTO avions VALUES('A 380','Alfred');

A partir desquelles on pourra reconstituer la table d’origine par joiture naturelle :

• \(\Join_{[vols.avion=avions.avion]}(vols,pilotes)\)

SELECT * FROM vols NATURAL JOIN avions;
-- ou
SELECT vol,vols.avion,avions.pilote
FROM vols, avions
WHERE vols.avion=avions.avion;

après la mise à jour (UPDATE), on vérifie bien que le résultat de la jointure naturelle :

UPDATE vols SET avion='A 380' WHERE vol='AA 1234';
SELECT * FROM vols NATURAL JOIN avions;

préservera la DFE :

• \(avion \rightarrow pilote\)