1

LES DÉPENDANCES FONCTIONNELLES

2

ETUDIANT Nom-Etudiant
0,n

suit

0,n
COURS Nom-Cours
1,1

enseigne

0,n
PROF Nom-Prof
 3

Définitions

a) Dépendance fonctionnelle
Soit R(U) un schéma de relation, r une relation de schéma R, X š U, Y š U deux
sous-ensembles d’attributs de R. La dépendance fonctionnelle
X › Y
est vrai dans r, ssi (si et seulement si) tous les nuplets de r qui ont même valeur
pour (tous) les attributs de X, ont même valeur pour (tous) les attributs de Y.
Exemple :
ADRESSE(RUE, NUMERO, VILLE, CODE-P)
X = CODE-P
Y = VILLE
 4

b) Superclé
Soit R(U) un schéma et X œ U un sous ensemble d’attributs.
X est une superclé de r de schéma R, si X  U.
Exemple :
NOSS NOM  NOSS NOM PRENOM ADRESSE
NOSS NOM est une superclé
c) Clé
X est une clé, si :
1. X est une superclé : X  U
2. il n’existe pas Y œ X, tel que Y  U

Exemple :
RUE NUMERO VILLE  RUE NUMERO VILLE CODE-P
RUE NUMERO VILLE est une clé (pourquoi?)
 5

Calcul d’une Clé: Exemple

COURS(Nomc, Heure, Salle, Prof)

ž Ÿ
N HS, HS P
ž
Nous pouvons prouver à partir de que si on connaît le nom de cours, on connaît
aussi le nom du professeur (Nomc est une clé) :
1. N HS : deux nuplets qui partagent le nom de cours partagent également
l’horaire et la salle
2. HS P : deux nuplets qui partagent l’horaire et la salle partagent également le
nom du professeur
3. DF 1 et 2 impliquent, que deux nuplets qui partagent le nom de cours partagent
également le nom du prof : N P
On peut définir des propriétés (règles) sur les DF qui permettent de déduire d’autres
DF.
 6

Propriétés des Dépendances Fonctionnelles

(Axiomes d’Armstrong)

1) Réflexivité
si X ¡ Y alors Y ¢ X (pour tous les ensembles d’attributs X et Y)

Exemple :
NOM VILLE ¢ NOM
Trivial : “Deux personnes qui ont le même nom et habitent la même ville, ont le
même nom.”
 7

2) Transitivité
si X £ Y et Y £ Z, alors X £ Z
Exemple :
R(NOSS, CODE-P, VILLE)
¤
NOSS £ CODE-P, CODE-P £ VILLE ¥ ¦ NOSS £ VILLE
“Si on connaît le code postale à partir du numéro de sécurité sociale et la ville à
partir du code postale, on connaît la ville à partir du numéro de sécurité sociale.”
3) Augmentation
X £ Y¦ XZ £ YZ
Exemple :
NOSS £ CODE-P ¦ NOSS VILLE £ CODE-P VILLE
 8

Clôture d’un ensemble de dépendances fonctionnelles

De l’ensemble des dépendances fonctionnelles données par l’analyse du monde réel, en

utilisant les propriétés ci-dessus, appelées Axiomes d’Armstrong, on peut en déduire
d’autres :
Exemples :

­
1) R(A,B,C,D)
= ® A ¯ B, B ¯ C °
­ ± ² on déduit A ¯
Par transitivité, C
Notation : A ¯ C
 9

2) R(Cours, Prof, Heure, Salle, Eleve, Note)

³
= ´ C µ P, HS µ C, HP µ S, CE µ N, HE µ S ¶
³ ·¸
HS µ P, HE µ C,P,N
Donc HE est une clé. Pourquoi?

³
L’union de et de toutes les dépendances ainsi déduites est appelée clôture, ou
³ ³ ¹
couverture de et notée .
 10

Nouvelle définition d’une Superclé

Soit R(U) un schéma de relation, º un ensemble de dépendances fonctionnelles et X »

U un ensemble d’attributs. X est une superclé de R si pour tout A ¼ U

º ½¾ X ¿ A
ou encore si:
X ¿ A ¼ º À

Calculer º À à partir de º peut être très long.

Montrer que º ½¾ X ¿ A est plus facile.
 11

Calcul de la clé d’une relation

Soit R(U) un schéma de relation et X Á U un ensemble d’attributs.

– On définit  à comme ensemble des attributs A tels que Ä ÅÆ X Ç A

– Si A appartient à Â Ã , alors par définition Ä ÅÆ X Ç A
– Â Ã est l’ensemble des attributs fonctionnellement dépendants de X.

Pour calculer une clé on utilise l’algorithme suivant :

1. On cherche un X tel que  à = UÈ X est une superclé

2. X est une clé, s’il n’existe pas Y É X tel que Ê Ã = U
 12

Calcul de Ë Ì

Étape 1: On part de X
Pour toute Y Í A, telle que Y Î X, Y Í A Ï Ð , on rajoute A à X.
On obtient Ñ Ò .

Étape i: On part de Ñ BÓ Ô Ò
Pour toute Y Í A, telle que Y Î Ñ ÓBÔ Ò , Y Í A Ï Ð , on rajoute A à Ñ ÓBÔ Ò .
On obtient Ñ Ó .

On s’arrête quand on ne trouve plus de nouvelle DF (point fixe) :

Ñ Õ = Ñ ÓÖÕ Ò = Ñ Ó
13

Exemples

1. Montrer que HE est une clé pour R(CHENSP) avec l’ensemble × de DF donné
ci-dessus
2. Pour la relation ADRESSE(VILLE, RUE, NUMERO, CODE_P) ci-dessus,
montrer que VILLE RUE NUMERO est une clé. Quelle est l’autre?
 14

Contraintes d’intégrité

La liste des attributs est insuffisante pour décrire la sémantique du monde réel.
Il existe plusieurs types de contraintes sur les nuplets :

1. dépendances (fonctionnelles, d’inclusion, multivaluées, etc.)

2. contraintes qui dépendent du domaine d’un attribut : Taille Ø 2m10, année Ø 2000
3. etc.

Ce sont les dépendances qui permettent la conception d’un bon schéma.

15

ANOMALIES DE MISE À JOUR

 16

Exemple

Soit le schéma S1 :

FOURNISSEUR(FNOM, FADRESSE)
FOURNITURE(FNOM, PNOM, PRIX)

et l’ensemble de DF : Ù Ú Û FNOM Ü FADRESSE, (FNOM PNOM) Ü PRIX Ý

Supposons qu’on remplace S1 par le schéma S2 :
R(FNOM, FADRESSE, PNOM, PRIX)
 17

Anomalies

R (FNOM, FADRESSE, PNOM, PRIX)

Þ ß à
FNOM á FADRESSE, (FNOM PNOM) á PRIX â
Quelle est la clé de R?

TOTO LYON BRIQUES 1000

DUPONT ROUEN BRIQUES 900
TOTO LYON BETON 400

1) REDONDANCE : l’adresse d’une personne apparaît plusieurs fois.

2) MAJ : si on modifie l’adresse dans un nuplet, il faut le faire dans les autres.
 18

3) SUPPRESSION : si DUPONT ne fournit plus de BRIQUES, on supprime le 2e

nuplet, on perd toute info sur DUPONT
4) INSERTION : on ne peut insérer un nouveau fournisseur et son adresse, si on ne
connaît pas au moins un produit qu’il fournit
TOTO PARIS BRIQUES 1000
TOTO LYON BETON 400
DURAND NICE

ã ä LE SCHÉMA INITIAL S1 EST “MEILLEUR”

 19

Qualités d’un bon schéma

1. Éviter les anomalies å æ décomposition

2. La décomposition doit conserver la même information
La jointure d’une relation
f1 de schéma FOURNISSEUR(FNOM, FADRESSE)
et d’une relation
f2 de schéma FOURNITURE(FNOM, PNOM, PRIX)
obtenues par décomposition d’une relation
r de schéma R(FNOM, FADRESSE, PNOM, PRIX)
doit redonner r.
3. La décomposition doit conserver les mêmes contraintes (DF). La décomposition de
R en R1(FNOM, FADRESSE, PRIX) et R2(PNOM, PRIX) ne préserve pas les
DF. Pourquoi?
20

FORMES NORMALES ET DÉCOMPOSITION

21

Relation en première forme normale (1FN)

– Tous les attributs sont atomiques (élémentaires)

– Relations telle qu’on les connaît.
– Relation non normalisée, non en 1e FN :
Certains attributs sont des ensembles de valeurs, des relations elles même
 22

Relation 1FN

NOTES ( COURS ETUDIANT NOTE )

BDB Toto 15
BDB Lulu 17
BDB Lili 0
ARCHI Lili 20
ARCHI Toto 0

Relation N1FN

NOTES ( COURS PERF (ETUDIANT NOTE) )

BDB Toto 15
Lulu 17
Lili 0
ARCHI Lili 20
Toto 0
23

Relation en 3e forme normale

– 2e forme normale :
Purement historique
– 3e forme normale : 3FN
– évite la plupart des anomalies
le but du jeu : décomposer une relation (1FN) en un ensemble de relations 3FN
 24

3FN : Définition

Définition : Une relation R est en 3FN, si quelle que soit la DF X ç A de è é où

– A est un seul attribut et
– A n’est pas l’un des attributs de X,

– soit X est une superclé (contient une clé),

– soit A appartient à l’une des clés.

En fait, il n’est pas nécessaire de vérifier toutes les DF de è é .

Il suffit de vérifier celles de è !
 25

Exemples: 3e Forme Normale

1) Poste(Ville, Rue, Code)

ê
= ë VR ì C, C ì Ví
Clés : {V,R} et {R,C}
R est en 3FN.
2) FOURNITURE(NOMF, ADR, NOMP, PRIX)
ê
= ë NOMF ì ADR, NOMF, NOMP ì PRIX í
Clé : {NOMF, NOMP}
FOURNITURE n’est pas en 3FN.
 26

3) PLANNING(Cours, Heure, Salle)

î
= ï SH ð C, C ð Sñ
Clés : {S,H} et {C,H}
PLANNING est en 3FN.
4) R(A, B, C, D)
î
= ï AB ð C, B ð D, BC ð Añ
Clés : {A, B}, {B, C}
R n’est pas en 3FN.
 27

Décomposition sans perte d’information (SPI)

Exemple

R ( A B C )
a b c
a b a
c b d

et ò =ó Aô Bõ
Décomposons en :

R1 ( A B ) R2 ( B C )
a b b c
c b b a
b d
 28

R1 = ör÷+øúù (R)
R2 = ö ùûøýü (R)
R’ = R1 þ R2 ÿ R :

R’ ( A B C )
a b c
a b a
a b d
c b c
c b a
c b d

La décomposition de R en R1 et R2 est avec perte d’informations.

La jointure crée des nuplets qui n’existaient pas dans R.
 29

Décomposons R’ maintenant en :

R1’( A B ) R2’ ( A C )
a b a c
c b a a
c d


R” = R1’ R2’ = R’ :

R’’ ( A B C )
a b c
a b a
c b d

Cette décomposition est sans perte d’information (SPI)

Il faut qu’après la jointure, on retrouve la même information qu’avant la décomposition.
 30

Définition
Une décomposition de R en R1, R2, ..., Rk par rapport à un ensemble de DF 
est SPI (sans perte d’information), ssi quelle que soit r de schéma R satisfaisant  , on a :

r =  (r)   (r). . .   (r)

Théorème :
Si (R1, R2) est une décomposition de R et  un ensemble de DF, alors (R1, R2)
est SPI par rapport à  , ssi :
R1 R2  R1 - R2
ou
R1 R2  R2 - R1
est une dépendance de   .
 31

Exemples

R (A, B, C)

= A B

1) R1(A, B), R2(B, C)

AB  BC = B
AB - BC = A
BC - AB = C
 
Il n’y a ni la DF B  A, ni la DF B  C dans
 Décomposition avec perte d’information
 32

2) R1(A, B), R3(A, C)

AB  AC = A
AB - AC = B
A B est dans  (  ).
 Décomposition sans perte d’information
 33

Décomposition qui préserve les dépendances fonctionnelles

Définitions
1. Projection d’un ensemble de dépendances sur Z  U
 ( ) = "! #$ %  & '(! $ ) * +
Exemple : R(A,B,C,D),  = AB # C, C # A, A # D +
-, .0/ ( ) = AB # C, C # A +
2. Décomposition qui préserve les DF de 
Soit 1 = (R1,...,Rk) une décomposition, et  un ensemble de DF.
1 préserve les DF de  , si on peut retrouver toutes les DF de  & à partir de
l’union 2 de toutes les DF projetées de  dans 435 ( ), . . . , 3 6 ( ) :
27& =  &
 34

Exemples

8
R(A,B,C,D)
= 9 AB : C, C : A, A : D; 8
<
= (ABC, BD) ne préserve pas les 8 DF de
<
= (ABC, AD) préserve les DF de
8
R(A,B,C)
=9 A: B, B : A, A : C; 8
<
= (AB, BC) préserve les DF de
 35

R(A, B, C, D)
=
=> A? B, B ? C, AB ? D@
La décomposition
R1(AC)
R2(AB)
R3(CD)

=
ne préserve pas les DF de . Pourquoi?
 36

Décomposition d’une relation en relations 3FN

Étant donné un schéma (R, F) non en 3FN, i.e. avec des anomalies, on veut une
décomposition de R :

1. en relations 3FN
2. qui soit SPI
3. qui préserve les DF de A
 37

Remarque :

– une décomposition SPI ne préserve pas forcément les DF et inversement

– le résultat ne donne pas forcément des relations 3FN

Théorème : Toute relation en 1FN possède une décomposition en relations 3FN qui soit
SPI et préserve les dépendances fonctionnelles.
 38

Algorithme de décomposition

On suppose que B est une couverture minimale

1. Pour chaque X C A D B , créer une relation de schéma (XA).

2. Si aucune des clés n’est contenue dans l’un des schémas créés dans l’étape 1,
rajouter une relation de schéma (Y), où Y est une clé.
3. Si après l’étape 1, il existe une relation R1 dont le schéma (X1A1) est contenu dans
le schéma (X2A2) d’une autre relation R2, supprimer la relation R1.
4. Remplacer les relations (XA1),..., (XAk) (correspondant à des dépendances
ayant même membre gauche) par une relation unique : (XA1...Ak).
 39

Exemples

E
1) R(A,B,C,D)
= F AB G C, B G D, C G AH
Clés : AB, BC

– Étape 1 : R1(ABC) R2(BD) R3(CA)

– Étape 2 : Pas la peine de rajouter une relation de schéma la clé AB :
AB est contenue dans R1
– Étape 3 : Supprimer R3 : CA I ABC

Bonne décomposition : R1(ABC) R2(BD)

On peut vérifier que R1 et R2 sont en 3eFN.
 40

J
2) R(A,B,C,D,E)
= K AB L C, C L D, C L A M Clés : ABE, BCE

– Étape 1 : R1(ABC) R2(CD) R3(CA)

– Étape 2 : On rajoute une relation de schéma pour la clé ABE : R4(ABE)
– Étape 3 : Supprimer R3 : CA N ABC

Bonne décomposition : R1(ABC) R2(CD) R4(ABE)

R3 n’a pas de dépendance. Quelles sont les dépendances des autres?
Autre solution :
– Étape 4 : On remplace R2 et R3 de l’étape 1 par une relation de schéma (CAD)
Autre bonne décomposition : R1(ABC) R2’(CAD) R4(ABE)
Que se passe-t-il si on avait choisi la clé CBE?
 41

O
3) R(A,B,C,D)
= P AB Q C, C Q D, C Q A, AB Q DR
Clés : BA, BC
La relation n’est pas en 3e Forme Normale. Pourquoi?

– Étape 1 : R1(ABC) R2(CD) R3(CA) R4(ABD)

– Étape 2 : on ne rajoute pas de relation : clé AB S R1(ABC)
– Étape 3 : Supprimer R3 : CA S ABC
– Étape 4 : On remplace R1 et R4 par R5(ABCD) T on peut supprimer R2.

Décomposition : R5(ABCD)
Cette décomposition n’est pas en 3e Forme Normale. Où est le problème?
 42

Forme Normale Boyce-Codd (BCNF)

Des anomalies subsistent en 3FN.

Exemple : Poste(Ville,Rue,Code), U = V VR W C, C W VX
Clés : VR, RC

Poste ( Ville Rue Code )

Paris St Michel 75005
Paris Champollion 75005
Y Redondance entre le code et la ville.
 43

Définition : Une relation est en forme normale de Boyce-Codd (BCNF), si quelle que soit
la dépendance de Z , le membre de gauche est une clé.
Intérêt : On a éliminé toutes les anomalies
Remarque : Toute relation BCNF est en 3FN
Malheureusement, il n’existe pas toujours une décomposition en relations BCNF

– qui soit SPI

– qui préserve les DF
 44

L’exemple de la poste

Poste(Ville,Rue,Code), [ = \ VR ] C, C ] V^
Clés : VR, RC
R est 3FN mais n’est pas BCNF (dans C ] V, C n’est pas une clé)

Poste ( Ville Rue Code )

Sevres de Gaulle 92310
Chaville de Gaulle 92370
 45

La décomposition R1(Ville,Code), R2(Rue,Code) évite la redondance

Ville,Code, elle est SPI, mais elle ne préserve pas la dépendance VR _ C

R1 ( Ville Code ) R2 ( Rue Code )

Sevres 92310 de Gaulle 92310
Chaville 92370 de Gaulle 92370

L’insertion Sevres de Gaulle 92190, c.a.d. Sevres 92190 et de Gaulle

92190 respecte C _ V mais ne respecte plus VR _ C

R1 ( Ville Code ) R2 ( Rue Code )

Sevres 92310 de Gaulle 92310
Chaville 92370 de Gaulle 92370
Sevres 92190 de Gaulle 92190