COURS PECA
Normalisation
d’une relation
Frédéric Gava (MCF)
[email protected]
LACL, bâtiment P2 du CMC, bureau 223
Université de Paris XII Val-de-Marne
61 avenue du Général de Gaulle
94010 Créteil cedex
Introduction
Lors de la définition d’un schéma conceptuel dans le modèle relationnel, le
choix des relations est primordiale. Ce choix doit être guidé par les
dépendances qui existent entre les données, dans la réalité et qui sont des
contraintes que doivent vérifier les données effectivement dans la base.
Exemple :
Produit(NºP, NomP, Couleur, Poids)
Fournisseur(NºF, NomF, Adresse, Tél)
Livraison(NºF, NºP,Quantité, Date, Tél)
DF =
NºP→{NomP, Couleur, Poids}
NºF→{NomF, Adresse, Tél}
NºF, NºP,Date→Quantité, Tél
Problèmes :
Si un fournisseur n’a pas fait de livraison, on ne connaît pas son nº de tél
S’il fait plusieurs livraisons, le nº de tél sera stocké plusieurs fois
S’il faut changer de nº de tél, il faut le faire autant de fois qu’il apparaît dans la
table des livraisons.
Ce schéma est mal défini
2/19
Définitions (1)
Définition : Normaliser une relation consiste à la représenter sous
une forme qui respecte certains critères afin de s’assurer de l’intégrité
des données
La normalisation est un moyen fondamentale mis à la disposition du
concepteur de la base pour éviter un bon nombre d’erreur
Définition : Une dépendance est une contrainte exprimé par une règle
qui doivent vérifier les données pour que la BD soit dans un état
cohérent. Exemple : un salarié travail dans un et un seul service. Nous
avons 3 sortes de dépendance
Fonctionnelle (forme normale 1, 2 et 3)
Multi-valué (forme norme 4)
Jointure (forme normal 5)
Définition : Une DF traduis le fait qu’à une valeur d’une donnée, on
associe dans une relation, une valeur au plus d’une autre donnée à un
instant considéré
3/19
Décomposer une relation (1)
Étant donnée une relation non satisfaisante
(répétitions, pbs d’intégrités etc.) on peut trouver un
sous-ensemble de sous-relation satisfaisant et qui
décrivent les mêmes informations
NOM
STATUT AGE
Exemple :
NOM
STATUT AGE COURS
GAVA MCF
26
Parallélisme
HAINS Pr
40
Sécurité
HAINS Pr
40
Sémantique
GAVA MCF
26
HAINS Pr
40
NOM
COURS
GAVA Parallélisme
HAINS Sécurité
HAINS Sémantique
4/19
Décomposer une relation (2)
On dira qu’une décomposition est « bonne » si on
peut retrouver les informations de la relation initiale
à partir des sous-relations
Pour retrouver les informations d’une relation à
partir des relations « filles », on utilisera l’opérateur
de jointure naturelle
5/19
Jointure naturelle
L’opération de jointure naturelle permet de composer des
sous-relations pour en obtenir une plus grosse relation :
R1(X,Y)⊗R2(Y,Z)=R(X,Y,Z)
C’est donc un lien entre plusieurs tables disposant de
colonnes commune sémantiquement
Chaque ligne de R est fabriquée avec une ligne de R1 et
une ligne de R2 de telle sorte que les valeurs sur les attributs
de Y soient identiques dans les ligne de R1 et de celle de R2
Elle permet donc de recomposer une relation qui avait été
préalablement décomposée (voir forme normale)
Une décomposition est dite « sans perte d’informations » si
les jointures naturelles des sous-relations redonne la relation
initiale
6/19
Jointure et produit cartésien
Produit cartésien :
concaténation de toutes les lignes de la première table avec toutes
les lignes de la seconde table.
Table 1 Table 2
Produit
a
x
a,x
Exemple
b
y
c
a,y
b,x
b,y
c,x
Jointure :
c,y
lien entre 2 tables disposant d’au moins une colonne commune
(sémantiquement). On associe a chaque ligne de la première table
toutes les lignes de la seconde table
Exemple
Table 1 Table 2 Jointure
a1,b1
b1,c1
a1,b1,c1
a2,b1
b2,c2
a2,b1,c1
a3,b2
b3,c3
a3,b2,c2
7/19
Exemple Jointure
Nom
Prénom
Numéro avocat
R1 = Collard
Bebert
1
Vergès
Jacquy
2
Numéro avocat
Procès
Résultat
HLM
Perdu
2
Serial Killer
Gagné
1
Outreau
Perdu
2
Du siècle
Gagné
R2 = 1
R1⊗R2 =
Nom
Prénom
Numéro avocat
Procès
Résultat
Collard
Bebert
1
HLM
Perdu
Vergès
Jacquy
2
Serial Killer
Gagné
Collard
Bebert
1
Outreau
Perdu
Vergès
Jacquy
2
Du siècle
Gagné
8/19
Différentes jointures
Définition : une équi-jointure est une jointure dont
la condition est une comparaison d’égalité de 2
colonnes appartenant aux 2 tables
Définition : une theta-jointure est est une jointure
dont la condition est une comparaison autres que
l’égalité de 2 colonnes appartenant aux 2 tables
Définition : une jointure multiple met en relation
plus de 2 tables.
Définition : une auto-jointure est une jointure d’une
table avec elle-même
9/19
Définitions
(2)
Définition : Une DF est élémentaire si un sous-ensemble de la clé
n’est pas source de la DF.
Exemple :
A, B, C→D est élémentaire s’il existe pas les DF
A, B→D ; A, C→D ; B, C→D et aussi
A→D ; B→D ; C→D
Définition : Une DF A→B est directe (non transitive) s’il n’existe
pas un autre attribut C tel que A→C et C→B
Définition : Une relation est normalisée si aucun attribut n’est
présent plus d’une fois dans la relation et si aucun attribut n’est luimême décomposable en d’autres attributs et qu’il n’est pas luimême une relation
Théorème de Heath : Une relation R(X,Y,Z) est décomposable
SPI en 2 sous-relations R1(X,Y) et R2(X,Z) s’il existe pour R1 une
DF X→Y ou pour R2 une DF X→ Z (c’est le cas si X est une clé
10/19
de R1 ou de R2)
Formes normales 1
Toute relation normalisée est en FN1
R(N°_Client, N°_Article, Nom_Client, Nom_Article)
N°_Client→Nom_Client ; N°_Article→Nom_Article ;
N°_Client, N°_Article→Nom_Article
Table suivante :
23
23
26
A5
A6
A5
Fred
Fred
Bob
Chaise
Table
Chaise
Il faudrait plutôt les relations suivantes :
Client(N°,Nom)
Article(N°, Nom)
Commande(N°_Article, N°_Client)
11/19
Forme normal 2
Une relation est en FN2 si
Elle est en FN1
si tout attribut n’appartenant pas à une clé dépend
élémentairement d’une clé
Suffisant ?
R(N°_Client, Nom_Client, N°_Repr, Nom_Repr)
DF= N°_Client→Nom_Client, N°_Repr, Nom_Repr ;
N°_Repr→Nom_Repr
25
26
Fred
R1
Patrick R1
Nicole
Nicole
Repr(N°_Repr, Nom) Client(N°_Client, Nom, N°_Repr)
12/19
Exemple
Fournisseur(Nom, Adresse, Tél, NomProduit, Prix)
Nom, NomProduit→Prix, Adresse, Tél
Nom→Adresse
FN2 ?
ok pour Nom, NomProduit→Prix
par contre Nom, NomProduit→Adresse n’est pas élémentaire car
Nom→Adresse
donc que FN1
Décomposition possible et SPI d’après théorème de Heath
Fournisseur(Nom, Adresse, Tél)
Catalogue(Nom_Fournisseur, NomProduit, Prix)
13/19
Forme normal 3
Une relation est en FN3 si
Elle est en FN2 (donc en FN1)
Tout attribut n’appartenant pas à une clé dépend de
façon direct d’une clé
Définition : un ensemble d’attribut X est une clé
candidate d’une relation R si et seulement si
{X}+=R
Remarque : lorsqu’une relation est en FN3 aucune
DF n’est issue d’un sous-ensemble de la clé et
aucune DF n’est issue d’un attribut non clé vers un
autre
14/19
Exemple
Fournisseur(Nom, Pays, Ville)
Nom→Ville, Pays
Ville→Pays (pas de ville homonyme dans des pays différents)
FN2 ? Oui car l’attribut Nom est la seule clé
FN3 ? Non car Nom→Pays n’est pas direct (on peut passer
par Ville). Il y a donc des répétitions de noms de pays.
Décomposition SPI
Fournisseur(Nom, Ville)
Géographie(Ville, Pays)
15/19
Forme normal 4
Aussi appelé Forme normal de Boyse-Codd
Une relation R est en en FNBC si tout attribut
dépend de façon élémentaire et direct d’une clé
Remarque : quand une relation n’a qu’une clé
candidate (donc qu’une unique clé appelé atomique),
alors si elle est en FN3 cela implique qu’elle est
aussi en FNBC
Remarque : FNBC⇒FN3⇒FN2⇒FN1
Remarque : Il existe une FN5 mais nous la verrons
pas dans ce cours (trop rare)
16/19
Exemple
Catalogue(N°F, NomF, NomP, Prix)
2 clés (N°F, NomP) et (NomF, NomP)
DF :
N°F, NomP→NomF,Prix
NomF, NomP→N°F, Prix
N°F→NomF
NomF→N°F
FN3 ? Oui car seul Prix n’appartient pas à une clé et dépend
élémentairement et directement de 2 clés
FNBC ? Non car NomF ne dépend pas élémentairement d’une
clé : N°F,NomP→NomF n’est pas élémentaire car il existe et
N°F→NomF et NomF ne dépend pas de l’autre clé
Décomposition possible
Fournisseur(N°F, NomF) avec N°F→NomF et si l’on veut NomF→N°F
Catalogue(N°F, NomP, Prix) avec N°F, NomP→Prix
17/19
Exemple complet
La relation Place(N°Etu, Matière, Rang) représente le rang
de chaque étudiant par matière. On suppose qu’il n’y a pas
d’ex-aequo. Nous avons les DF suivantes :
Rang, Matière → N°Etu (pas d’ex-aequo)
N°Etu, Matière → Rang
2 clés candidates : (Rang, Matière) et (N°Etu, Matière)
Quelles sont les formes normales vérifiées ?
Tout attribut appartient à une clé donc c’est en FN3
Les 2 DF sont directes et élémentaires avec des membres gauches
(de la DF) qui sont des clés donc la relation Place est en FNBC
18/19
Version simplifiée (pratique)
On ne touche pas à la définition de FN1
Quand on n’a qu’une clé (clé primaire ou atomique)
Définition d’une relation R en FN2 :
La relation R est en FN1
Toutes les DF issues de la clé sont élémentaires
Définition d’une relation R en FN3 :
La relation R est en FN2
Toutes les DF issues de la clé sont directes
Pas de FNBC
19/19
Atelier
Pour la BD suivante :
R1(N°_Client, N°_Produit, QtComm, Nom_Produit)
R2(N°_Commande, N°_Produit, QtComm)
R3(N°_Client, Nom_Client, Nom_Repr)
R4(N°_Produit, Nom_Produit, N°_Atelier, Nom_Chef_Atelier)
R5(N°_Client, Nom_Client, N°_Repr)
R6(N°_Produit, N°_Fournisseur, Prix, Nom_Fournisseur)
Trouvez les clés externe et déduisez les DF
Trouvez les formes normales des relations suivantes
20/19
Correction Atelier
1. N°_Produit→Nom_Produit donc pas élémentaire donc
FN1
2. N°_Commande, N°_Produit→Qt_Commandé donc FN3
3. N°_Client→Nom_Client, Nom_Repr donc FN3
4. N°_Produit→Nom_Produit et
N°_Atelier→Nom_Chef_Atelier donc indirect donc FN2
5. N°_Client→Nom_Client, Nom_Repr et
N°_Repr→Nom_Repr donc indirect donc FN2
6. N°_Produit→Prix et N°_Fournisseur→Nom_Four donc
pas élémentaire donc FN1
21/19
Société
de
Tourisme
(1)
Une société de tourisme possède une vingtaine de centres
sur le territoire français et une douzaine dans d’autres pays.
Cette société a implanté une BD dont vous trouverez la
structure ci-dessous :
Cette BD a, entre autre, pour but de mieux cibler les activités
pratiquées par les clients dans les centres
Un centre est ouvert pendant un certain nombre de semaines de
l’année suivant son implantation
Un animateur est en général un saisonnier, il n’anime qu’une seule
activité et est rattaché à un seul centre
Un responsable d’activité est un permanent de la société. Il peutêtre responsable de plusieurs activités et travaille suivant les
saisons dans différents centres. Cependant, un responsable d’une
activité est responsable de cette activité dans tous les centres où il
travaille (lorsque cette activité existe)
Donner et justifier les formes normales des relations
22/19
Société de Tourisme (2)
1.
2.
Client(N°, Nom, Adresse, Age)
Inscription(N°_client, N°_Centre, N°_Semaine, N°_activité,
N°_animateur)
3. Animateur(N°_Animateur, N°_Activité, N°_Responsable,
Nom_Responsable, Adresse_Responsable, N°_Centre, N°_SS, Nom)
4. Centre(N°, Nom, Adresse)
5. Responsable(N°, N°_SS, Ancienneté, Nom, Adresse)
6. Employé(N°_SS, Nom, Adresse, Date_Naissance)
7. Activité(N°, Nom)
8. Fonctionnement(N°_Centre, Type_Appart, N°_Semaine)
9. Séjour(N°_Client, N°_Centre, N°_Semaine, Type_Appart)
10. Responsabilité(N°_Responsable, N°_Centre, N°_Activité)
11. Statistique(N°_Responsable, N°_Centre, N°_Activité,
Nombre_Heures_Effectués)
23/19
Correction Tourisme
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
FN3
FN3
FN2
FN3
FN1
FN3
FN3
FN3
FN1
FN3
FN3
24/19