Mises à jour et cohérence

Bases de Données Relationnelles

n But d'un schéma logique : décrire une bd qui va
effectivement être utilisée
uchargée , accédée , mise à jour (maj)

Normalisation d’un n Les maj (insertions, suppressions, modifications) doivent

conserver la cohérence de la base de données
schéma relationnel uintégritéréférentielle
utoute contrainte d'intégrité
uen particulier les dépendances entre attributs

n Selon le schéma c'est + ou - facile

uPlus la bd contient de redondances, plus les maj avec
maintien de la cohérence est difficile

BDA 7.2

Exemple d'anomalies de maj Qu’est-ce qu’une BD relationnelle

LivraisonTot ( N°f , adrF , N°p , typeP , qté )
‘incorrecte’ ?
3 Lausanne 52 meuble 12
22
22
Bienne
Bienne
10
25
ordinateur
papier
6
210
Une relation n’est pas correcte si :
3 Lausanne 25 papier 560 n elle implique des répétitions au niveau de sa population
3 Vevey 10 ordinateur 15
elle pose des problèmes lors des maj (insertions,
Définition : Le fournisseur N°f, qui est actuellement à telle
n
n

adresse adrF, a livré au total telle quantité du produit N°p, modifications et suppressions)
produit qui est de tel type. n Les conditions pour qu'une relation soit correcte peuvent
n Si un fournisseur change d’adresse et qu’un seul tuple est être définies formellement :
mis à jour ⇒ incohérence
=> règles de normalisation
n Si un nouveau tuple est inséré pour un fournisseur connu,
avec une adresse différente ⇒ incohérence
n Impossibilité d'enregistrer un nouveau fournisseur sans
livraison
BDA 7.3 BDA 7.4
Exemple (suite) Normalisation d'un schéma logique
LivraisonTot ( N°f , adrF , N°p , typeP , qté ) n Processus de transformation d'un schéma S1 pour
3 Lausanne 52 meuble 12
obtenir un schéma S2 :
22 Bienne 10 ordinateur 6
22 Bienne 25 papier 210 uquiest équivalent (même contenu)
3 Lausanne 25 papier 560 udont les maj assurant la cohérence de la bd sont simples
3 Vevey 10 ordinateur 15
n maj simple :
n L’adresse du fournisseur ne dépend que du fournisseur et pas
uun changement élémentaire dans le monde réel se traduit
du produit.
par une mise à jour d'un tuple
n Le type du produit ne dépend que du produit et pas du
fournisseur n Exemples de changements élémentaires
⇒ REDONDANCES u LivraisonTot (N°f, adrF, N°p, typeP, qté)
u La quantité totale pour un produit et un fournisseur est
⇒ Anomalies de mise à jour mise à jour => 1 tuple à m.a.j.
n Cette relation n'est pas correcte. Il faut la normaliser. u Un fournisseur change d'adresse => N tuples à m.a.j.
BDA 7.5 BDA 7.6

Normalisation d'une relation Normalisation

n Processus de décomposition d'une relation à maj n On mesure la qualité d'une relation par son degré de
complexes en plusieurs relations à maj simples normalisation :
n Processus sur le schéma relationnel formel n 1FN (première forme normale), 2FN, 3FN, FNBC
(forme normale de Boyce Codd), 4FN, etc.
n Exemple :
La relation
LivraisonTot (N°f, adrF, N°p, typeP, qté) 1FN
sera décomposée en :
n LivraisonTot’ (N°f, N°p, qté) 2FN 3FN FNBC 4FN
Fournisseur (N°f, adrF)
Produit (N°p, typeP)

BDA 7.7 BDA 7.8

Normalisation ou traduction EA Exemple
Fournisseur Livraison Produit
Schéma EA 0-n 0-n
Nom Adr. Date Qté Tel Nom Type
Niveau conceptuel (EA) VALIDATION Fournisseur (NF, Nom, Adr)
Règles Produit (NP, Nom, Type) Livraison VALIDATION
(NP, NF, Date, Qté, Tél) Règles
Schéma EA valide
Décomposition Fournisseur Livraison Produit
0-n 0-n
Niveau logique des relations NORMALI-
incorrectes Nom Adr. Tel Qté Date Nom Type
(Relationnel) Schéma Relationnel SATION
TRADUCTION
EA - R
TRADUCTION
NORMALISATION

Produit (NP, Nom, Type)

Schéma relationnel normalisé Fournisseur’ (NF, Nom, Adr, Tél)
Livraison’ (NP, NF, Date, Qté)
BDA 7.9 BDA 7.10

Dépendance fonctionnelle Dépendance fonctionnelle (suite)

n L’adresse d’un fournisseur ne dépend que du
fournisseur, ..… R: X Y Z
x1 y1 z1
..........................
⇒ DÉPENDANCE FONCTIONNELLE (DF) x1 y1 z2
..........................
n Notation :
u A, B, C … attributs
u X, Y, Z … ensembles d'attributs n X‡Y: X détermine Y Y dépend de X

n Définition : n X : source de la DF, Y : cible de la DF

Soit une relation R (X, Y, Z)
il existe une DF : X‡Y si et seulement si dans R à
n La source peut être un ensemble d’attributs :
une même valeur de X correspond toujours une (nom, prénom) ‡ adresse
même valeur de Y
BDA 7.11 BDA 7.12
Propriétés des DF Graphe des DF
n Transitivité : n Pour chaque relation il faut recenser toutes ses DF
si X ‡ Y et Y ‡ Z alors X‡Z élémentaires et non déduites.
(DF déduite) n On les représente sous forme d'un graphe orienté
graphe minimum des DF de la relation
n Augmentation :
si X ‡ Y alors (A, X) ‡ Y quelque soit A n Une relation peut avoir plusieurs graphes minimum.
Ils sont alors équivalents
(DF non élémentaire)
n Exemple de graphe minimum :
n On ne s’intéresse qu’aux DF élémentaires non
R (A, B, C, D, E)
déduites
E‡A E‡B E‡C (≡ E ‡ A, B, C)
uElles expriment les faits élémentaires du monde réel C‡D
uCe sont elles qui permettent de déterminer si une relation E
est bonne
et sinon comment la décomposer A B C D
BDA 7.13 BDA 7.14

Utilité du graphe des DF Vérifier qu'un graphe est minimum

n Vérifier que le graphe est bien minimum
n Trouver les identifiants de la relation n DF déduite X
X‡D est déduite s'il existe un autre X
n Tester si la relation est bonne (bien normalisée) chemin X‡A1… ‡...An‡D D
n Sinon trouver les décompositions
Exemple de graphe non minimum
n DF non élémentaire
E
X‡D est non élémentaire s'il existe A B C
E‡D est déduite de E‡C et C‡D
X une DF Y‡D telle Y est un sous-
A B C D Il faut supprimer E‡D du graphe ensemble des attributs de X X
D
(A,B,C)‡D est non élémentaire
BDA 7.15 BDA 7.16
Exemple de graphe des DF Un autre exemple
LivraisonTot (N°f, adrF, N°p, typeP, qté) n RU (N°E, nom, prénom, adr, dateN, nomC, année,
n N°f ‡ adrF nbCrédits, prof, note)
u l’adresse d’un fournisseur ne dépend que du fournisseur
n Définition :
n N°p ‡ typeP
u le type d’un produit ne dépend que du produit L'étudiant de numéro N°E a tel nom, tel prénom et
habite actuellement à telle adresse (adr).
n (N°f, N°p) ‡ qté
u la quantité totale livrée dépend du produit et du fournisseur L'étudiant (N°E) a obtenu telle année tel cours
(nomC) avec telle note.
[faux : N°f ‡ qté, N°p ‡ qté ]
Cette année là le cours était sous la responsabilité
de tel prof et valait tant de crédits (nbCrédits).
N°f N°p
n Faire le graphe minimum des DF

adrF qté typeP

BDA 7.17 BDA 7.18

Graphe des DF de RU DFs et identifiants

n Le graphe minimum des DF permet de trouver les identifiants
nom de la relation
prénom L’identifiant d’une relation est l’ensemble (minimal) des nœuds
N°E
n

adr du graphe minimum à partir desquels on peut atteindre tous

les autres nœuds (via les DF)
dateN n Preuve :
note Pour que ce soit faux il faudrait qu’il y ait deux lignes avec la
même valeur de l’« identifiant » et des valeurs différentes pour
nomC nbCrédits les autres attributs, ce qui est en contradiction avec les DF.
année prof n Exemple : R (A, B, C, D, E)
E
E est l'identifiant de R
A B C‡D
BDA 7.19 BDA 7.20
DFs et identifiants - Exemple Normalisation par décomposition
n Autre exemple : R (A, B, C, D, E, F, G) n Soit une relation R qui contient des redondances et pose des
problèmes lors des maj
"Elle n'est pas normalisée"
n Il faut la décomposer en plusieurs relations meilleures
F G ("normalisées") …
n par projection …
A B C E
n en suivant les DF
u cela assure d'obtenir des relations normalisées.
D
n Il faut s'assurer de conserver le même contenu
La jointure des nouvelles relations = R

(F, G) est l'identifiant de R

BDA 7.21 BDA 7.22

Normalisation par décomposition (2) Théorème de Heath

n THEOREME :
on
compositi R1 = π[A1, A2,… Ai] R R (X, Y, Z) est décomposable sans perte
dé R2 = π[Ai, Ai+1,… Aj] R
R (A1, A2, … , An) d’information en
…. R1 = π[X,Y]R
joint
ure Rk = π[Al, Al+1,… An] R
R2 = π[X,Z]R
nouvelle BD si la DF X‡Y existe
Si R = R1*R2* …*Rk n R1 est alors nécessairement normalisée (en 3FN).
la décomposition est sans perte d'information Elle décrit le fait élémentaire X‡Y
n Les requêtes posées sur R et celles posées sur
Les requêtes sur R et celles sur la nouvelle BD
R1*R2 donnent le même résultat
donneront toujours le même résultat

BDA 7.23 BDA 7.24

Exemple : décomposition sans perte Exemple : décomposition avec perte
d'info d'info
R (NomEmp, adresse, poste, age) R1' (NomEmp, adresse, poste) R2' (poste, age)
Zoé Lausanne secrétaire 27 Zoé Lausanne secrétaire secrétaire 27

Armand Genève secrétaire 32 Armand Genève secrétaire secrétaire 32

Marie Bienne directeur directeur 38
Marie Bienne directeur 38

R1' * R2'
R1 (NomEmp, adresse, poste) R2 (NomEmp, age) Zoé Lausanne secrétaire 27
Zoé Lausanne secrétaire Zoé 27 Zoé Lausanne secrétaire 32
Armand Genève secrétaire Armand 32
Armand Genève secrétaire 27 ≠R
Marie Bienne directeur Marie 38
Armand Genève secrétaire 32

R = R1*R2 Marie Bienne directeur 38

NB Cette décomposition est sans perte d'information,
Cette décomposition ne suit pas Heath
mais inutile BDA 7.25 BDA 7.26

Application de Heath Qualité d’une décomposition

Une « bonne » décomposition est une décomposition
LivraisonTot (N°f, adrF, N°p, typeP, qté)
n

1) sans perte d’information

N°f N°p
2) sans perte de DF
3) qui produit des relations meilleures (mieux normalisées)
adrF qté typeP

n N°f ‡ adrF => R1 (N°f, adrF) ok n Sans perte de DF :

LivraisonTot' (N°f, N°p, typeP, qté) Toute DF doit être dans l’une des relations obtenues par
décomposition
n N°p ‡ typeP => R2 (N°p, typeP) ok
LivraisonTot'' (N°p, N°f, qté) Une DF ayant comme source un identifiant sera
automatiquement vérifiée par le SGBD
n (N°p, N°f) ‡ qté =>
LivraisonTot'' (N°p, N°f, qté) ok Une DF perdue => une contrainte d'intégrité implicite => le
SGBD ne peut pas la vérifier
BDA 7.27 BDA 7.28
Vérification des DF par le SGBD Formes normales : 1FN
n LivraisonTot ( N°f, adrF, N°p, typeP, qté ) n Une relation est en 1FN si chaque valeur de chaque
DF vérifiées par le SGBD : attribut de chaque tuple est une valeur simple (tous
(N°f, N°p) ‡ adrF, typeP, qté les attributs sont simples et monovalués).
u Un même fournisseur peut avoir deux adresses
u Un même produit peut avoir deux types n Exemple :
LivraisonTot (N°f, adrF, N°p, typeP, qté)
n LivraisonTot2 ( N°f, N°p, qté ) est en 1FN
Fournisseur ( N°f, adrF )
Produit ( N°p, typeP ) n Pratiquement, en relationnel on ne travaille que sur
DF vérifiées par le SGBD : des relations en 1FN
N°f ‡ adrF
N°p ‡ typeP
(N°f, N°p) ‡ qté
BDA 7.29 BDA 7.30

2ème forme normale : 2FN 2ème forme normale : définition

n Permet d’éliminer les attributs qui ne décrivent pas LivraisonTot (N°f, adrF, N°p, typeP, qté)
l’«objet» représenté par la relation
N°f N°p
LivraisonTot (N°f, adrF, N°p, typeP, qté)
N°f N°p adrF qté typeP
n Des DF partent de composants de l’identifiant =>
adrF qté typeP Livraison n’est pas en 2FN
Livraison mélange la description : n Définition : une relation est en 2FN si
- de la livraison cumulée ( N°f, N°p, quantité) - elle est en 1FN, et
- du fournisseur ( N°f, adresse) - chaque attribut qui ne fait pas partie de
- du produit ( N°p, type) l’identifiant dépend d’un identifiant entier
BDA 7.31 BDA 7.32
Décomposition selon les DF 3FN : 3ème forme normale
n Pour chaque source de DF créer une relation n Permet d’éliminer des sous-relations incluses dans
comprenant : une relation
ula source n Exemple : Fournisseur (N°fourn, ville, pays)
uet tous les attributs cibles de DF ayant cette source
N°fourn
X
N°f N°p ville pays
R1 (N°f, adrF)
R1 R2 R2 (N°p, typeP)
adrF qté typeP N°fourn
R3 (N°f, N°p, qté)
doit être décomposée en :
R3 F (N°fourn, ville) ville pays
G (ville, pays)
BDA 7.33 BDA 7.34

3ème forme normale : définition Importance de la 3FN

n Fournisseur (N°fourn, ville, pays) n Toute relation peut toujours être décomposée en
N°fourn relations en 3FN sans aucune perte
usans perte de DF, et
usans perte d'information
ville pays
n Profondeur de l’arbre des DF > 1 => Fournisseur n Ce n'est pas vrai pour les formes supérieures
n'est pas en 3FN n Il faut donc toujours faire des schémas au moins en
n Définition : Une relation est en 3FN si 3FN
- elle est en 1FN, et
- chaque attribut qui ne fait partie d’aucun
identifiant dépend directement d’un identifiant
entier
BDA 7.35 BDA 7.36
Forme normale de Boyce-Codd FNBC - exemple : Fournisseur
n Généralise la 3FN aux relations à plusieurs n Fournisseur (N°fourn, nom-fourn, N°produit, prix)
identifiants
N°fourn nom-fourn
n Fournisseur (N°fourn, nom-fourn, N°produit, prix) prix (2 graphes possibles)
avec 2 identifiants : N°produit
u (N°fourn +N°produit)
u (nom-fourn + N°produit) • Identifiants : (N°fourn + N°produit)
u 3NF (nomfourn + N°produit)
u Mais des redondances : N°fourn et nom-fourn • Fournisseur est en 3FN mais pas en FNBC
n Définition : Une relation est en FNBC si : n On doit décomposer pour obtenir des relations en
- elle est en 1FN, et FNBC
- si toute source complète de DF est un identifiant
entier n Attention : Ce passage en FNBC n’est pas toujours
BDA 7.37
possible sans perte de dépendances BDA 7.38

Décompostion de Fournisseur FNBC - exemple : Place

n Fournisseur (N°fourn, nom-fourn, N°produit, prix)
n Place (N°Etud, Matière, Rang)
N°fourn nom-fourn F1 rang sans ex aequo

prix N°Etud Matière

N°produit
F2
Rang

n F1 (N°fourn, nom-fourn) avec 2 identifiants

F2 (N°fourn, N°produit, prix)
2 identifiants : (N°Etud + Matière)
ou (si l'on prend l'autre graphe des DF)
n

(Rang + Matière)
n F1 (N°fourn, nom-fourn) avec 2 identifiants n Place est en 3FN et est en FNBC
F2’ (nom-fourn, N°produit, prix)
BDA 7.39 BDA 7.40
FNBC contre-exemple Décomposition de Enseignement
n Enseignement (N°Etud, Matière, Prof) n Enseignement (N°Etud, Matière, Prof)
n La décomposition selon Heath :
N°Etud Matière R1 (Prof, Matière) R2 (Prof, N°Etud)
est sans perte d’information
Prof mais avec perte de la DF (N°Etud, Matière)‡Prof
n On peut insérer des tuples qui transgressent la DF
uINSERT INTO R1 : (Rochat, BD)
n 2 identifiants : (N°Etud + Matière) uINSERT INTO R1 : (Walis, BD)
(N°Etud + Prof)
uINSERT INTO R2 : (Rochat, 12345)
n Enseignement est en 3FN mais n’est pas en FNBC uINSERT INTO R2 : (Walis, 12345)

BDA 7.41 BDA 7.42

Enseignement : 2 solutions Algorithmes de décomposition / DF

n Solution 1 n Plusieurs algorithmes pour décomposer selon les DF
uEnseignement (N°Etud, Prof, Matière)
n Algorithme 1 (d'après Heath)
uavec la CI : un prof n'enseigne qu'une seule matière
uR (A1, A2, A3, … An)
n Solution 2 uTant qu'il existe une DF élémentaire non déduite faire :
uR1 (Prof, Matière) Soit Ai‡Aj la DF
uR2 (Prof, N°Etud) Soient Ak,… Al les autres attributs qui dépendent
uavec la CI : un étudiant suit une matière donnée avec un directement de Ai : Ai‡(Aj, Ak, …Al)
seul prof Remplacer R par
R1 (Ai, Aj, Ak, … Al)
n Pas de solution idéale R2 (Ai, attributs de R autres que Aj, Ak, …Al)
La solution 1 est préférable uRecommencer l'algorithme pour R1 et R2
uellegénère moins de jointures lors des requêtes
ula CI est mono-relation
BDA 7.43 BDA 7.44
Algorithme 1 Méthode pragmatique
n Algorithme 2 (à partir des sources de DF)
F G R1 (F, A, B) R1 (F, A, B) uR (A1, A2, A3, … An)
R2 (G, E) R2 (G, E) uTant qu'il existe une source de DF élémentaire non déduite
A B C E
R3 (C, D, H) R3' (F, G, C) faire :
H R4 (F, G, C) R4' (F, G , D, H)
Choisir si possible une source dont toutes les cibles sont
D des extrémités terminales du graphe
CI : C‡D,H
Soient Ai la source et Ai‡(Aj, Ak,… Al) les DF
n Avantages Créer la relation Ri (Ai, Aj, Ak, … Al)
u relations en FNBC Supprimer les attributs Aj, Ak, …Al de R
n Inconvénients uSi aucune des relations Ri ne contient un identifiant de R

u dépend de l'ordre selon lequel les DF sont traitées alors ajouter la relation : R0 (un identifiant de R)
u peut perdre des DF
u peut trop décomposer NB La jointure avec R0 assure la non perte d'information
BDA 7.45 BDA 7.46

Algorithme 2 Un autre type de dépendance

n Certaines relations en FNBC peuvent encore contenir
F G R1 (F, A, B) des redondances, et poser des problèmes lors des
R2 (G, E) maj
A B C E
R3 (C, D, H)
n Exemple : Cours (nomC, prof, livre)
H R4 (F, G, C)
D uCI : Pour chaque cours, il y a un ensemble de profs et un
ensemble de livres; ces deux ensembles sont
indépendants.
n Avantages
u relationsen FN3
u ne perd pas de DF
nomC prof livre
Relation en Programmation Duval Algorithmes
u ne perd pas d'information (grâce à R0)
non 1FN Schmidt Progr.1
n Inconvénients BD Jouve Date
Rochat Ullmann
u peut trop décomposer (cf. Enseignement)
Gardarin
BDA 7.47 BDA 7.48
Un autre type de dépendance (2) Un autre type de dépendance (3)
Cours (nomC, prof, livre) en 1FN n Cours pose des problèmes de maj
uajouter un nouveau professeur, Alex, au cours de BD
nomC prof livre
ucorriger le nom d'un livre
Programmation Duval Algorithmes
Programmation Duval Progr.1 u…
Programmation Schmidt Algorithmes
Programmation Schmidt Progr.1 n Cependant Cours est déja bien normalisée
BD Jouve Date
BD Jouve Ullmann Cours est en FNBC
BD Jouve Gardarin uparce qu'il n'y a pas de DF
BD Rochat Date
BD Rochat Ullmann n En EA, Cours aurait deux attributs multivalués
BD Rochat Gardarin
uprofs

Cours contient beaucoup de redondances ulivres

indépendants l'un de l'autre

BDA 7.49 BDA 7.50

Dépendance multivaluée (DM) Graphe des dépendances de Cours

n Définition :
Cours (nomC, prof, livre)
Soit une relation R (X, Y, Z) nomC
Il y a dépendance multivaluée
X --->> Y
si à toute valeur de X correspond un ensemble de prof livre
valeurs de Y qui est totalement indépendant de Z
La relation Cours contient une DM :
n Propriété : nomC -->> prof | livre
S'il y a la DM X-->>Y alors il y a aussi X-->>Z
On note : X-->>Y|Z
L'identifiant de livre est (nomC, prof, livre)

n Remarque : DF est un cas particulier de DM

BDA 7.51 BDA 7.52
4ème forme normale (4FN) Décomposition selon une DM
n Sémantique : La 4FN permet de séparer des faits n Théorème de Heath n°2
multivalués indépendants qui auraient été réunis Si R(X, Y, Z) contient la DM X-->>Y|Z
dans une même relation alors la décomposition en :
nomC
R1 = π[X,Y]R et
n Définition : R est en 4FN si : R2 = π[X,Z]R
- elle est en 1ère FN, et est sans perte d'information. prof livre
- si toute DF ou DM de R a pour source un identifiant
entier de R n Exemple : Cours (nomc, prof, livre) FNBC
uRemarque : 4FN implique FNBC est décomposé en :
n Autre définition : R est en 4FN si elle est en FNBC et CoursProf (nomc, prof) 4FN
ne contient pas de DM CoursLivre (nomC, livre) 4FN
uCes deux relations ne contiennent ni DF ni DM

BDA 7.53 BDA 7.54