Motivation

Dépendances fonctionnelles
Décomposition des relations
Formes normales
Algorithmes de normalisation

Cours normalisation
Support théorique d’une “bonne” conception d’un schéma relationnel

Anne-Laure Ligozat (repris du cours de Mireille Jouve)

ENSIIE

2018

1/49
 Motivation
Dépendances fonctionnelles
Décomposition des relations
Formes normales
Algorithmes de normalisation

Motivation : problèmes de conception

Mauvaise conception ⇒ relations problématiques

Exemple : relation propriétaire voiture

n prop nom prénom ville n voiture marque date prix
102 durand laure paris 90FE75 renault 10/2005 10000
43 dupond jean chatou 43FT78 citroen 5/2005 17000
365 martin pierre lyon 5GT69 peugeot 7/2004 23000
43 dupond jean chatou 56ER78 renault 12/2004 8000
151 duval jeanne paris
78RX75 peugeot

2/49
 Motivation
Dépendances fonctionnelles
Décomposition des relations
Formes normales
Algorithmes de normalisation

Problèmes soulevés par une mauvaise conception

Redondance des données Exemple dans propriétaire voiture

perte de place, temps de personne répétée pour chaque
traitement accrus voiture
incohérence potentielle

Anomalies de mise à jour Exemple dans propriétaire voiture

nécessité de valeurs nulles insertion d’une personne sans
clé incomplète voiture
⇒ valeurs nulles
suppression de la dernière
voiture d’une personne
⇒ suppression de la personne

3/49
 Motivation
Dépendances fonctionnelles
Décomposition des relations
Formes normales
Algorithmes de normalisation

Intérêt de la normalisation

Besoin
Éviter d’avoir une relation hétérogène sémantiquement
⇒ Décomposition en relations plus petites, limitant la redondance et
les anomalies de mise à jour

Démarche
Décomposer les relations sans perte d’informations ni mauvaises
recompositions
⇒ Décomposition des relations en formes normales

4/49
 Motivation
Dépendances fonctionnelles
Décomposition des relations
Formes normales
Algorithmes de normalisation

Nécessité d’une théorie

Objectifs
Donner des règles de définition d’un “bon” schéma
Donner des algorithmes pour
générer automatiquement un “bon” schéma
ou transformer un schéma en un “bon” schéma

n°prop

nom
n°voiture sémantique des
données
date−achat

personne(...)
voiture(...)
...
5/49
 Motivation Définition
Dépendances fonctionnelles Axiomes d’Armstrong
Décomposition des relations Sélection des DF
Formes normales Représentation des DF
Algorithmes de normalisation Notion de clé

Dépendances fonctionnelles (DF)

Définition
Soit R(A1,A2,...,An) un schéma de relation et X et Y deux
sous-ensembles d’attributs de R
On dit que X → Y (X détermine fonctionnellement Y, ou Y
dépend fonctionnellement de X) si quelle que soit l’extension de
R, pour tous tuples t1 et t2 de R :
t1[X] = t2[X] =⇒ t1[Y] = t2[Y]
≡ à chaque valeur de X correspond toujours une et une seule valeur
de Y

6/49
 Motivation Définition
Dépendances fonctionnelles Axiomes d’Armstrong
Décomposition des relations Sélection des DF
Formes normales Représentation des DF
Algorithmes de normalisation Notion de clé

Exemples

Personne
n carte-id → nom
nom 9 n carte-id

Voiture
(marque,type) → puissance
marque 9 puissance
puissance 9 type

Propriétaire
n voiture → n prop
n prop 9 n voiture
(n voiture,n prop) → date-achat

7/49
 Motivation Définition
Dépendances fonctionnelles Axiomes d’Armstrong
Décomposition des relations Sélection des DF
Formes normales Représentation des DF
Algorithmes de normalisation Notion de clé

Remarques

DF et sémantique des données

Une DF est une assertion sur toutes les valeurs possibles
⇒ Impossible de les déduire des valeurs actuelles d’une relation
Les DF sont des assertions qui traduisent la sémantique des données
du monde réel représenté
⇒ Ce sont des contraintes d’intégrité (règles de gestion)

8/49
 Motivation Définition
Dépendances fonctionnelles Axiomes d’Armstrong
Décomposition des relations Sélection des DF
Formes normales Représentation des DF
Algorithmes de normalisation Notion de clé

Axiomes d’Armstrong

Règles d’inférence des DF

Réflexivité
Y ⊂ X =⇒ X → Y
marque ⊂ (n voiture, marque) =⇒ n voiture, marque → marque
Augmentation
X → Y =⇒ XZ → YZ
n voiture → marque =⇒ n voiture, puissance → marque, puissance
Transitivité
X → Y ET Y → Z =⇒ X → Z
n voiture → type ET type → marque =⇒ n voiture → marque
Pseudo-transitivité
X → Y ET WY → Z =⇒ WX → Z

9/49
 Motivation Définition
Dépendances fonctionnelles Axiomes d’Armstrong
Décomposition des relations Sélection des DF
Formes normales Représentation des DF
Algorithmes de normalisation Notion de clé

Sélection des DF

DF non triviales
Élimination des DF déduites par réflexivité ou par augmentation
⇒ sélection des DF de la forme X → A avec :
- A 6⊂ X
- il n’existe pas X 0 ⊂ X tel que X 0 → A

DF élémentaires
X → A, où A est un seul attribut

10/49
 Motivation Définition
Dépendances fonctionnelles Axiomes d’Armstrong
Décomposition des relations Sélection des DF
Formes normales Représentation des DF
Algorithmes de normalisation Notion de clé

Représentation des dépendances fonctionnelles

Représentations
Graphe des dépendances fonctionnelles
Fermeture transitive (F+ )
Ensemble des DF élémentaires augmenté de celles obtenues par
transitivité
Couverture minimale
Sous-ensemble minimum de DF élémentaires permettant de générer
toutes les autres

11/49
 Motivation Définition
Dépendances fonctionnelles Axiomes d’Armstrong
Décomposition des relations Sélection des DF
Formes normales Représentation des DF
Algorithmes de normalisation Notion de clé

Exemple : voiture(n véhicule,type,marque,puissance,couleur)

F = {n véhicule → type, type → marque, type → puissance, n véhicule
→ couleur}

n°véhicule n°véhicule

couleur couleur
type type
marque puissance marque
puissance

Graphe des DF Fermeture transitive

12/49
 Motivation Définition
Dépendances fonctionnelles Axiomes d’Armstrong
Décomposition des relations Sélection des DF
Formes normales Représentation des DF
Algorithmes de normalisation Notion de clé

Exemple : prod pharma(produit,type,client,remise)

produit type client remise
aspirine A C1 3%
compresse A C2 5%
vitamine B C1 4%

Dépendances fonctionnelles
F = {produit → type; type,client → remise}

produit

type client

remise

Graphe des DF
13/49
 Motivation Définition
Dépendances fonctionnelles Axiomes d’Armstrong
Décomposition des relations Sélection des DF
Formes normales Représentation des DF
Algorithmes de normalisation Notion de clé

Notion de clé

Définition
Soit R(A1,A2,...,An) un schéma de relation avec l’ensemble des DF
F+ et X un sous-ensemble de A1,A2,...,An.
X est clé de R ssi :
X → A1, A2, ..., An
il n’existe pas de sous-ensemble Y ⊂ X tel que Y → A1, A2, ..., An

Exemple : relation voiture

n véhicule ?
n véhicule, type ?
N.B. Il peut y avoir plusieurs clés dans une relation

14/49
 Motivation
Dépendances fonctionnelles Définition
Décomposition des relations Décomposition sans perte d’information
Formes normales Décomposition préservant les DF
Algorithmes de normalisation

Décomposition des relations

But
Remplacer une relation R par de plus petites relations pour éliminer les
problèmes de redondance et les anomalies de màj et clés incomplètes

Définition
La décomposition d’un schéma de relation R(A1,A2,...,An) est son
remplacement par une collection de schémas de relations R1,R2,...,Rp
telle que R = R1 ∪ R2 ∪ ... ∪ Rp

15/49
 Motivation
Dépendances fonctionnelles Définition
Décomposition des relations Décomposition sans perte d’information
Formes normales Décomposition préservant les DF
Algorithmes de normalisation

Exemples

voiture(n véhicule,marque,type,puisance,couleur)
R1(n véhicule,type,couleur)
R2(type,marque,puissance)
R’1(n véhicule,type)
R’2(type,puissance,couleur)
R’3(type,marque)

prod pharma(produit,type,client,remise)
R1(produit,type)
R2(type,client,remise)
R’1(type,client,remise)
R’2(type,client,produit)

16/49
 Motivation
Dépendances fonctionnelles Définition
Décomposition des relations Décomposition sans perte d’information
Formes normales Décomposition préservant les DF
Algorithmes de normalisation

Critères de décomposition

Décomposition sans perte d’information

Une décomposition de R en R1,R2,...,Rp est sans perte ssi pour toute
extension de R :
R = (R{R1} >< R{R2}) >< ... >< R{Rp}

Condition suffisante
La décomposition d’une relation R en R1 et R2 est sans perte si l’attribut
de jointure entre R1 et R2 est clé de R1 ou R2

17/49
 Motivation
Dépendances fonctionnelles Définition
Décomposition des relations Décomposition sans perte d’information
Formes normales Décomposition préservant les DF
Algorithmes de normalisation

Exemples

Exemple : relation voiture

n véhicule marque type puissance couleur
872VXD75 renault clio 6 bleue
975SWT80 renault clio 6 rouge

Première décomposition : sans perte

n véhicule type couleur
type marque puissance
872VXD75 clio bleue
clio renault 6
975SWT80 clio rouge

18/49
 Motivation
Dépendances fonctionnelles Définition
Décomposition des relations Décomposition sans perte d’information
Formes normales Décomposition préservant les DF
Algorithmes de normalisation

Deuxième décomposition : avec perte

R’1 R’2
n véhicule type type puissance couleur R’3
type marque
872VXD75 clio clio 6 bleue
clio renault
975SWT80 clio clio 6 rouge

R 0 1 >< R 0 2 >< R 0 3
872VXD75 clio 6 bleue renault
872VXD75 clio 6 rouge renault
975SWT80 clio 6 bleue renault
975SWT80 clio 6 rouge renault

19/49
 Motivation
Dépendances fonctionnelles Définition
Décomposition des relations Décomposition sans perte d’information
Formes normales Décomposition préservant les DF
Algorithmes de normalisation

Exemple : prod pharma

produit type client remise
aspirine A C1 3%
compresse A C2 5%
vitamine B C1 4%
sirop B C2 6%

Décomposition avec perte

R1 >< R2 6= prod pharma
ex : (vitamine,B,C2,6%) ∈ R1 >< R2 mais 6∈ prod pharma
R1 R2
produit type type client remise
aspirine A A C2 3%
compresse A A C2 5%
vitamine B B C1 7%
sirop B B C2 6%

20/49
 Motivation
Dépendances fonctionnelles Définition
Décomposition des relations Décomposition sans perte d’information
Formes normales Décomposition préservant les DF
Algorithmes de normalisation

Décomposition sans perte des dépendances fonctionnelles

Définition
Une décomposition (R1,R2,...,Rp) de R préserve les DF de R si la
fermeture des DF de R est la même que celle de l’union des DF de
(R1,R2,...,Rp)

21/49
 Motivation
Dépendances fonctionnelles Définition
Décomposition des relations Décomposition sans perte d’information
Formes normales Décomposition préservant les DF
Algorithmes de normalisation

Exemple : voiture(n véhicule,marque,type,puissance,couleur)

R’1(n véhicule,type)
R’2(type,puissance,couleur)
R’3(type,marque) n°véhicule
⇒ ne préserve pas les DF couleur
type
R1(n véhicule,type,couleur)
R2(type,marque,puissance) marque
puissance
⇒ préserve les DF (et est sans
perte)

Exemple : prod pharma(produit,type,client,remise)

R1(produit,type) produit
R2(type,client,remise) type client
⇒ préserve les DF (mais n’est
pas sans perte) remise
22/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Formes normales

Objectif
Définir des règles concernant le schéma des relations pour mieux
représenter le monde réel (sans redondance, sans anomalies de màj et
clés incomplètes)

1FN BCKFN 4FN

2FN 5FN
3FN

23/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Première forme normale (1FN)

Axiome
Une relation est en première forme normale si tout attribut contient
une valeur monovaluée et non composée.

Exemple : relation employé

employé(n employé,identité,diplômes) 1FN ?
identité composée : nom, prénom
diplômes multivalué : liste

24/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Deuxième forme normale (2FN)

Définition
Une relation est en deuxième forme normale si
elle est en 1FN
tout attribut non clé dépend de la totalité de la clé
(pas de dépendance partielle)
ou il n’existe pas de DF MG → MD telle que MG ⊂ clé

25/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Exemples

fournisseur(nom,adresse,article,prix)
DF : {nom,article → prix; nom → adresse }
clé = nom,article
nom → adresse
⇒ pas en 2FN

prod pharma(produit,type,client,remise)
DF : { produit → type; type,client → remise }
clé = produit,client
produit → type ⇒ pas en 2FN

26/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Règle de décomposition en 2FN

Principe de la décomposition
Sortir la(les) DF qui empêche(nt) que la relation soit en 2FN :

REL ( A, B, C, D, E )

DF contradictoire avec la 2FN

R1(B,C)
Reste(A,B,D,E)

27/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Troisième forme normale (3FN)

Définition
Une relation est en troisième forme normale si
elle est en 2FN
il n’y a pas d’attribut n’appartenant pas à la clé qui dépende de la
clé par transitivité (pas de dépendance par transitivité)
ou il n’existe pas de DF MG → MD telle que MG ∩ clé = ∅

Exemple : voiture(n véhicule,type,marque,puissance,couleur)

F = {n véhicule → type, type → marque, type → puissance, n véhicule
→ couleur }
clé = n véhicule
n véhicule → type et type → marque, type → puissance
⇒ pas en 3FN
28/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Règle de décomposition en 3FN

Principe de la décomposition

REL ( A, B, C, D, E )

DF contradictoire avec la 3FN

R1(C,D)
Reste(A,B,C,E)

29/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Décomposition en 3FN

Théorème
Toute relation R a une (ou plusieurs) décomposition(s) (R1,R2,...,Rp) en
troisième forme normale telle(s) que
la décomposition préserve les DF
la décomposition est sans perte d’information

30/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Forme normale de Boyce-Codd-Kent (BCK FN)

[Link](ville,département,code postal)
ville
grenoble isère 38000
code−postal
st-martin isère 38400
département
st-martin loir-et-cher 41200

En 3FN, mais avec des anomalies

la suppression du tuple (st-martin,loir-et-cher,41200) fait perdre
l’information entre code-postal et département
on ne peut introduire un code postal et le département
correspondant qu’en donnant une ville

31/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Forme normale de BCK

Définition
Une relation est en forme normale de Boyce-Codd-Kent ssi les seules
dépendances non triviales sont celles dans lesquelles une clé détermine un
ou plusieurs attributs
ou il n’existe pas de DF MG → MD telle que MG 6= clé

BCK FN et 3FN
Une telle relation est en 3FN.

Décomposition de [Link]
cp-ville(ville,code-postal)
cp-dépt(code-postal,département)
⇒ perte de la DF (ville,département) → code-postal

32/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Dépendances multivaluées (DM)

Motivation
Dépendances fonctionnelles ⇒ 3FN,BCKFN
Insuffisant pour éliminer toutes les redondances et anomalies

Exemple : informations sur les cours d’un étudiant

n étudiant cours sport
100 BD tennis
100 BD football
102 BD velo
102 RS velo

Pas de DF :
n étudiant 9 cours
n étudiant 9 sport
L’ensemble des attributs est clé ⇒ relation en 3FN
33/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Dépendance multivaluée
Définition
Soit R(A1,A2,...,An) et X et Y deux sous-ensembles de A1,A2,...,An.
On dit que X →→ Y (X multidétermine Y, ou il y a une
dépendance multivaluée de Y sur X) si, étant donné une valeur de
X, il y a un ensemble de valeurs de Y associées et cet ensemble est
indépendant de Z = R - (X,Y).

y
y’

Y
x

z
z’
X
z’’

34/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Exemple : vol(n vol,n avion,pilote)

avec les hypothèses :
un ensemble d’avions peut exécuter un vol
plusieurs pilotes sont associés à un vol et pilotent tous les avions de
ce vol
n vol n avion pilote
100 1 Dupont
100 1 Martin
100 1 Portier
100 2 Dupont
100 2 Martin
100 2 Portier

n vol →→ n avion k pilote

n vol →→ pilote k n avion

35/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Remarques

Notation : X →→ Y k Z ou X →→ Z k Y (symétrie)
Différent d’un ensemble d’attributs multivalués
DM triviale X →→ Y dans R :
X ∪ Y = R (il n’y a pas deux DM indépendantes)
=⇒ n vol →→ (n avion,pilote)

36/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Quatrième forme normale (4FN)

Généralisation de la BCKFN avec les DM

Définition
Une relation R est en 4FN ssi pour toute DM X →→ Y avec X ⊂ R et
Y ⊂ R, l’un au moins des faits suivants est vérifié
X →→ Y est triviale
X est clé de R
Une relation 4FN ne contient que des DF (où la clé détermine un attribut
non clé) ou une DM triviale.

37/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Décomposition en 4FN

Théorème
Toute relation a une décomposition (ou plusieurs) en quatrième forme
normale qui est sans perte d’information.

Exemples
(n étudiant,cours,sport)
=⇒ (n étudiant,cours) et (n étudiant,sport)
(n vol,n avion,pilote)
=⇒ (n vol,n avion) et (n vol,pilote)

38/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Cinquième forme normale

Motivation
DF et DM encore insuffisantes pour éliminer toutes les redondances

Exemple
revendeur marque produit
Dupont Renault voiture
Dupont Renault camion
Dupont Volvo voiture
Dupont Volvo camion
Durand Renault voiture

Dépendance de jointure :
si un revendeur vend un certain type de produit et qu’il représente la
marque qui fabrique ce produit, alors il vend le produit fabriqué par la
marque
39/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Décomposition en 5FN
marque produit
revendeur marque revendeur produit
Renault voiture
Dupont Renault Dupont voiture
Renault camion
Dupont Volvo Dupont camion
Volvo voiture
Durand Renault Durand voiture
Volvo camion

marque

revendeur x

produit

40/49
 Introduction
Motivation 1FN
Dépendances fonctionnelles 2FN
Décomposition des relations 3FN
Formes normales BCK FN
Algorithmes de normalisation Dépendances multivaluées et 4FN
Dépendances de jointure et 5FN

Répartition des dépendances

1FN
2FN
DF 3FN
11111111111
00000000000
00000000000
11111111111
00000000000
11111111111
4FN
00000000000
11111111111
00000000000
11111111111
00000000000
11111111111
00000000000
11111111111
00000000000
11111111111
00000000000
11111111111 DF
00000000000
11111111111
5FN
00000000000
11111111111
00000000000
11111111111 00000
11111
11111
00000
00000000000
11111111111
00000000000
11111111111 DM
00000
11111
00000000000
11111111111 00000
11111
00000
11111
00000000000
11111111111
00000000000
11111111111
00000000000
11111111111 DJ
00000000000
11111111111
00000000000
11111111111
DM
DJ

41/49
 Motivation
Définitions
Dépendances fonctionnelles
Algorithme de synthèse
Décomposition des relations
Exemple
Formes normales
Limite
Algorithmes de normalisation

Algorithmes de construction de relations normalisées

Algorithmes de synthèse
préservent les DF
conduisent à des relations 3FN
prise en compte uniquement des DF

Algorithmes de décomposition
préservent le contenu
conduisent à des relations 3FN, 4FN ou 5FN
prise en compte des DF, DM, DJ

42/49
 Motivation
Définitions
Dépendances fonctionnelles
Algorithme de synthèse
Décomposition des relations
Exemple
Formes normales
Limite
Algorithmes de normalisation

Algorithme de synthèse

couverture
relation
minimale
universelle
de DF
élémentaires
non triviales

algorithme
de synthèse

{ relations en 3FN }

43/49
 Motivation
Définitions
Dépendances fonctionnelles
Algorithme de synthèse
Décomposition des relations
Exemple
Formes normales
Limite
Algorithmes de normalisation

Algo récursif

RÉDUIRE(G)
TANT QUE une DF n’inclut pas tous les attributs FAIRE
SI A1,A2,...,Ak isolés FAIRE
ÉDITER (A1,A2,...,Ak)
ÉLIMINER (A1,A2,...,Ak)
FSI
RECHERCHER le plus grand X tel que
n >= 1
et X − > Ai, X − > Aj, ..., X − > An
ÉDITER (X,Ai,Aj,...,An)
ÉLIMINER LES DF UTILISÉES
ÉLIMINER LES SOMMETS ISOLÉS
RÉDUIRE(G)
FTQ

44/49
 Motivation
Définitions
Dépendances fonctionnelles
Algorithme de synthèse
Décomposition des relations
Exemple
Formes normales
Limite
Algorithmes de normalisation

Exemple
Graphe G de départ (couverture minimale de DF)
date
montant
n°comm nom
n°client
adresse

n°produit montant−lc

qtté_comm
prix−unit libellé

Première itération
X = (n comm,n produit)
X → qtté-comm, X → montant-lc
=⇒ rel1(n comm,n produit,qtté-comm,montant-lc)
45/49
 Motivation
Définitions
Dépendances fonctionnelles
Algorithme de synthèse
Décomposition des relations
Exemple
Formes normales
Limite
Algorithmes de normalisation

date
montant
n°comm nom
n°client
adresse

n°produit

prix−unit libellé

Deuxième itération
X = (n comm)
X → date, X → montant, X → n client
=⇒ rel2(n comm,date,montant,n client)

46/49
 Motivation
Définitions
Dépendances fonctionnelles
Algorithme de synthèse
Décomposition des relations
Exemple
Formes normales
Limite
Algorithmes de normalisation

n°client nom
adresse
n°produit

prix−unit libellé

Troisième itération
X = n produit n°client nom
X → prix-unit, X → libellé adresse
=⇒ rel3(n produit,prix-unit,libellé)

Quatrième itération :
X = n client
X → nom, X → adresse
=⇒ rel4(n client,nom,adresse)
47/49
 Motivation
Définitions
Dépendances fonctionnelles
Algorithme de synthèse
Décomposition des relations
Exemple
Formes normales
Limite
Algorithmes de normalisation

Limite
Il ne doit y avoir que des DF (graphe connexe)
Palliatif
Une DM triviale (ou ensemble de DM) doit être extraite sous forme d’une
relation
Exemple
produits fournis(n P,n F,libellé,nomF,adrF)

n°F n°P

nomF adrF libellé

=⇒ R1(n P,n F)
puis traiter chaque partie du graphe
48/49
 Motivation
Définitions
Dépendances fonctionnelles
Algorithme de synthèse
Décomposition des relations
Exemple
Formes normales
Limite
Algorithmes de normalisation

Récapitulatif

1FN: attributs atomiques (monovalués, non composés)

2FN: 1FN + tout attribut non clé dépend de la totalité de la clé
@ MG → MD tq MG ⊂ clé
3FN: 2FN + pas de dépendance par transitivité
@ MG → MD tq MG ∩ clé = ∅
BCKFN: toutes les dépendances non triviales sont celles dans
lesquelles une clé détermine un ou plusieurs attributs
@ MG → MD tq MG 6= clé

49/49