UE M3106 :

Bases de données avancées

PPN
 Plan du Cours

•  Introduction : Rappels  : SGBD, SQL, schéma, …, PL-SQL

•  Chapitre 1 : Qualité des schémas, Dépendances fonctionnelles,
formes normales à 2C, 2TD
•  Chapitre 3 : Contraintes d’intégrité complexes, déclencheurs
(triggers) à 1C, 1TD  , 2TP
•  Chapitre 4 : Optimisation : index, plan d’exécution 1C, 2TP
•  Chapitre 5 : Transactions, atomicité et gestion de la concurrence
d’accès 1C, 2TP ?
•  Chapitre 6 : Liens avec langage de programmation 1C, 2TP
 Intervenants

• O. Bensadoun (TD/TP)

• M. Boughanem (C/TD/TP)
• G. Cabanac (TD/TP)
• T. Millan (TD/TP)
Introduction : Rappels
 Rappels Notions de bases
Pré-requis

• S1: (M1104) Introduction aux bases de données

–  Modélisation de Bases de données (MCD)
–  Modèle relationnel (MCDà MLD)
–  SQL de base

• S2: (M2016) Programmation et adminsitration de bases de

données
–  SQL et extension procédurale (PL/SQL)
–  Exceptions et Curseurs
–  Administration des SGBD : utilisateurs, rôle, droits, vue
–  Accès BD via un langage de programmation
Chapitre 1 : Dépendances fonctionnelles
 Rappels
Bases de données
Définitions

• BD :
–  Ensemble de données inter-reliées, partagées, non
redondantes, cohérentes (contraintes d’intégrité)
• SGBD logiciel facilitant :
–  La représentation/description des données
–  L’accès et la manipulation des données
–  Le contrôle des accès, sécurité de données
 Rappel Description des données
3 niveaux de description

•  Niveau externe
–  Vue externe (vue de la BD Reccueil des besoins :
Interview, document
par les utilisateurs)
• Niveau Logique/
conceptuel Modélisation
–  Table, relations, Schéma
externe
attributs, .. Schéma conceptuel
T
•  Niveau Physique/interne
T (MCD, UML)
Schéma
externe
Schéma
–  Manière dont les données physique
sont stockées sur disque
 Rappel Conception d’une BD
Etapes de modélisation

Reccueil besoins : …
!

Modélisation (MCD, EA, UML)

Schéma Conceptuel

Conception de schémas normallisés

En exploitant les dépendances fonctionnelles

Transformation : règles de passage

Schéma Conceptuel vers schéma logique
!

Schéma Logique/
Relationnel
UV{code, titre, .. Schéma relationnel normalisé
Etudiant {Num_etud, Nom, …

- Est-ce que le schéma obtenu est normalisé (limiter les redondances) ?

- Est-ce le meilleur schéma possible pour décrire les données
 Conception de BD
Dépendance fonctionnelle
Exemple

NumEt Nom Prénom AdrEt NumDe NomDep AdrDep

p
10 Boughanem Moh Pompert 5 IUT-Info Rangueil
20 Cabanac Guillaume Castanet 5 IUT-Info Rangueil
30 Sauvagnat Karen Toulouse 10 FSI-Info Rangueil
40 Teste Olivier Castres 15 J2-Info Blagnac

Schéma relationnel:
Etudiant (NumEt, Nom, Prénom, AdrEt, NumDep, NomDep, AdrDep)
 Conception de BD
Dépendances fonctionnelles
Définition

–  Soient A et B deux attributs (ou deux groupes

d’attributs) et R une relation, on dit que
•  B est fonctionnellement dépendant de A
• ou A détermine B
–  si à toute valeur de A correspond au plus une valeur de B
–  notation : A→B
 Conception BD
Dépendances fonctionnelles
Exemple

NumEt Nom Prénom AdrEt NumD NomDep AdrDep

ep
10 Boughanem Moh Pompert 5 IUT-Info Rangueil
20 Cabanac Guillaume Castanet 5 IUT-Info Rangueil
30 Sauvagnat Karen Toulouse 10 FSI-Info Rangueil
40 Teste Olivier Castres 15 J2-Info Blagnac

Nom à NumEt?
NumEt à Nom ? Nom à Prénom ?
NumEt à Prénom ? Nom à adrEt ?
NumEt à AdrEt ? Prénom à Nom ?
NumEt à NumDep? NumDep à NomDep ?
NumEt, Nom à adrEt NumEt à NumDep ?
AdrDep à NomDep ?
….

Attention
On détermine les DF sur le schéma en intention et non pas sur son extension
 Conception BD
Dépendances fonctionnelles
Suite Exemple

• On peut déduire plusieurs DFs

NumEt à NumEt
NumEt à Nom
NumEt à Prénom NumEtà NomDep
NumEt à AdrEt
NumEt à NumDep ⇒ NumEt Nom à Prénom
NumDep à NomDep
Num à Nom, Prenom
Dépendances Fonctionnelles Propriètés des DF
Axiomes d’Armstrong

①  Réflexivité
•  ∀X, X →X
NumEt → NumEt
NomDep → NomDep
②  Augmentation
•  X → Y ⇒ X,Z →Y
NumEt → AdrEt ⇒ NumEt, Nom → AdrEt
NumDep → NomDep ⇒ NumDep, NumEt → Adr
③ Pseudo-transitivité
•  X → Y et WY → Z ⇒ WX → Z
NumEt → Nom et (NumDep, Adr) → NomDep
⇒ (NumDep, NumEt) → NomDep
 DFs
Propriètés des DF
Règles additionnelles

① Union
•  X → Y et X →Z ⇒ X →YZ
NumEt→ Nom et NumEt → Prenom
⇒ NumEt à (Nom, Prenom)
② Décomposition
•  X → Y et Z⊆Y ⇒ X → Z
NumEt → (Nom, Prenom)
⇒ NumEt → Nom et NumEt →Prenom
③ Transitivité
•  X →Y et Y →Z ⇒ X →Z
NumEt→NumDep et NumDep→NomDep
⇒ NuEt→ NoDep
 DFs
Qualité d’une DF
DF élémentaire

Définition
Une dépendance fonctionnelle X →A est élémentaire si A est un attribut
unique tel que A ∉ X et il n'existe pas X’ ⊂X tel que X’ → A, ( un
ensemble minimum d’attributs)
On dit que A dépend pleinement de X

Exemple
NumEt, Nom à AdrEt élémentaire : Oui - Non ?
NumEt à AdrEt, Nom élémentaire : Oui - Non ?
NumEt à AdrEt élémentaire : Oui - Non ?
NumEt à Nom élémentaire : Oui - Non ?
 DFs
Qualité d’une DF
DF directe (non transitive)

Définition
Une dépendance fonctionnelle de la forme X →Y est directe si il
n’existe pas Z ⊂X tel que :
X →Z et Z→Y

Remarque

Une DF non directe est déduite (dérivée) par transitivité

Exemple
NumEt à NomDep Transitive : Oui - Non ?
NumEt à NumDep à NomDep
 DFs Fermeture transitive et
couverture minimale
Fermeture transitive

Définition
La fermeture de F, notée F+, est l’ensemble de toutes les DF résultant
de l’application des propriétés des DF

Exemple
soit F={ a→b ;b→c}, F+ est composée de :
a→a ; b→b ; c→c
 DFs Fermeture transitive et
couverture minimale
Couverture minimale

Définition

La couverture minimale (graphe minimum) de F (ensemble de DFs) est

un ensemble minimal de DFs permettant de générer toutes les autres

Conséquence

•  Sont des DFs élémentaires non déduites

•  Toute DF élémentaire de A est dans la fermeture transitive D+

Exemple
F = {a→b ; b→c ; c→d ; a→d ; c,f→g ; a→b,c ; a,f→g},
 Conception BD Fermeture transitive et
couverture minimale
Exemple

NumEt Nom Prénom AdrEt NumD NomDep AdrDep

ep
10 Boughanem Moh Pompert 5 IUT-Info Rangueil
20 Cabanac Guillaume Castanet 5 IUT-Info Rangueil
30 Sauvagnat Karen Toulouse 10 FSI-Info Rangueil
40 Teste Olivier Castres 15 J2-Info Blagnac

NumEt à Nom
NumEt à Prénom
NumEt à AdrEt
NumEt à NumDep
NumEt à NomDep, AdrDep ⇒
NumEt, Nom à AdrEt
NumDep à NomDep
NumDep à adrDep
 DFs
Notions de clés
Notions de clés

Définition
Soit R (A1, A2, … , An) une relation
Un ensemble d’attributs X ⊆ {A1, A2, … , An} est une clé de R
si X → A1 A2 … An
Et Il n'existe pas Y ⊆ X, tel que Y → A1 A2 … An

Conséquence
On peut dériver le schéma d'une relation en partant de la liste des
dépendances fonctionnelles sur un ensemble d'attributs
 DF
Notions de clés
Exemple

•  R(A, B, C, D, E) et DF : A,BàD, DàE, Bà C

•  Clé ?
•  Démarche
–  Prendre toutes les combinaisons d’attributs
–  Calculer tous les attributs que l’on peut déduire en appliquant les DFs et
les propriétés des DF
–  Clé = ensemble minimum d’attributs qui détermine tous les attributs de R

–  Aà A,Bà A,B,Cà

–  Bà A,C à A,B,Dà
–  Cà A,D à A,B,Eà
–  Dà A,E à B,C,Dà
–  E à B,C à .
–  ….. …..
 Conception BD
Notions de clés
Exemple

NumEt Nom Prénom AdrEt NumDe NomDep AdrDep

p
10 Boughanem Moh Pompert 5 IUT-Info Rangueil
20 Cabanac Guillaume Castanet 5 IUT-Info Rangueil
30 Sauvagnat Karen Toulouse 10 FSI-Info Rangueil
40 Teste Olivier Castres 15 J2-Info Blagnac

Et_Dep(NumEt, Nom, Prenom, AdrEt, NumDep, AdrDep)

NumEt à Nom Quelle est la clé de Et_Dep ?

NumEt à Prénom
NumEt à AdrEt
NumEt à NumDep NumEt ?
NumDep à NomDep NumDep ?
NumDep à adrDep NumEt, NumDep?
 Qualité schéma Conception de schéma
logique d’une BD
Deux approches

.. Du déjà vu

Déjà vu le modèle entité association…

MCD .. MLD
 Qualité schéma Conception de schéma
logique d’une BD
Deux approches

• Approche par Décomposition : normalisation

–  Méthodologie de conception descendante pour produire
un «bon schéma» par décomposition d’un schéma
d’origine
–  Notion de Formes normales

• Approche par Synthèse

–  Etude des DFs
–  Construction directe du schéma normalisé
 Qualité schéma
Approche par décomposition
Notions de formes normales

• Une relation est en 1ère forme normale si

–  La relation a une clé
–  Les attributs sont composés de valeurs atomiques (pas
de tableaux)

DFs : (A, B) à C, E ; B à D et
R(A, B, C, D, E) Cà E

Exemple
Et_Dep (NumEt, NumDep, Nom, Prenom, AdrEt, NomDep, AdrDep)
 Qualité schéma
Approche par décomposition
Notions de formes normales

• Une relation est en 1ère forme normale si

–  La relation a une clé
–  Les attributs sont composés de valeurs atomiques (pas
de tableaux)

R(A, B, C, D, E) DFs : (A, B) à C, E ; B à D et

Cà E

Exemple
Et_Dep (NumEt, NumDep, Nom, Prenom, AdrEt, NomDep, AdrDep)
 Qualité schéma
Approche par décomposition
Notions de formes normales

• Une relation est en 2ème forme normale si

–  Elle est en 1e forme normale
–  Toutes les DF issues de la clé sont des DF élémentaires (Tout
attribut n'appartenant pas à la clé ne dépend pas d'une partie
de la clé)

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

Règle de décomposition

R(A, B, C, D, E) et DFs : (A, B) à C, E ; B à D et Cà E

⇒ R1(A, B, C, E) et R2(B, D)
 Qualité schéma
Approche par décomposition
Notions de formes normales

NumEt Nom Prénom AdrEt NumDe NomDep AdrDep

p

10 Boughanem Moh Pompert 5 IUT-Info Rangueil

20 Cabanac Guillaume Castanet 5 IUT-Info Rangueil

30 Sauvagnat Karen Toulouse 10 FSI-Info Rangueil

40 Teste Olivier Castres 15 J2-Info Blagnac

NumEt à Nom
NumEt à Prénom
NumEt à AdrEt Et_Dep (NumEt, NumDep, Nom, Prenom, AdrEt, NomDep, AdrDep)
NumEt à NumDep
NumDep à NomDep
NumDep à adrDep
 Qualité schéma
Approche par décomposition
Notions de formes normales

•  Une relation est en 3ème forme normale si

–  Elle est en 2eme forme normale
–  Toutes les DF issues de la clé sont des DF directes (Tout attribut
n'appartenant pas à la clé, ne dépend pas d'un attribut non clé

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

Règle de décomposition

R1(A, B, C, E) et DFs : A,Bà C, E ; BàD; Cà E

⇒ R12 (A, B, C), R12(C, E) et R2(B,D)

 DFs
Approche par décomposition
Algorithme de décomposition

• Algorithme de décomposition 3FN

①  Considérer tous les attributs comme faisant partie
d’une seule relation (relation universelle)
②  Appliquer les transformations de normalisation pour
obtenir des relations en 3FN
 DFs
Approche par décompositin
Exercice

•  Soit R (A, B, C, D, E, F, G, H, I, J, K) une relation avec

l’ensemble des DFs :
A,B à C, E ; A à F; F à D, G, H et Dà I, J, K
•  Proposer un schéma 3NF pour pour R
 DFs
Approche par synthèse
Présentation

•  Point de départ : F = {1: a→b ; 2: b→c, … }, résultat

schéma relationnel normalisé : R1[a, b, …]...
•  Étapes
–  Construction de l’ensemble de départ des DF
–  Construction de la couverture minimale
•  Suppression des DF redondantes déduites par transitivité, union et
décomposition
–  Regroupement des DF ayant même partie gauche dans des sous
ensembles
–  Regrouper les DF de type x→y et y→x dans le même sous
ensemble
 DFs Approche par synthèse
Exemple

•  Point de départ
–  A = {a, b, c, d, e, f, g, h, j, k}
–  F = {1: a→b ; 2: a→c ; 3: a,b,h→e,g ; 4: h→j ; 5: j→k ; 6: h→k ;
7: b→a}
•  1ére étape : couverture minimale (suppression des DFs
redondantes)
–  6 est redondante car elle peut être obtenue avec 4 et 5 par transitivité :
h→j ; j→k donne h→k
–  1 et 3 permettent de simplifier 3 par pseudo-transitivité a→b et a,b,h→e,g
donne a,a,h→e,g a,a,h→e,g donne a,h→e,g
 DFs
Approche par synthèse
Exemple

•  2éme étape : regroupement des DF

–  même partie gauche
• E1 = {1: a→b ; 2: a→c} ; E2 = { 3: a,h→e,g}
• E3 = {4: h→j} ; E4 = {5: j→k} ; E5 = {7: b→a}
–  x→y et y→x
• E1 = {a→b ; a→c ; b→a} et E5 = {b→a}
•  3éme étape : relations
–  R1[a,b,c]
–  R2[a#,h#,e,g]
–  R3[h,j#]
–  R4[j,k]
 DFs
.. Formes normales
Boyce-Codd

•  Une relation est en forme normale de Boyce-Codd (BCNF) si et

seulement si les seules DFs élémenaires sont celles dans
lesquelles une clé entière détermine un attribut

•  La condition qui définit BCNF est une simplification de 3NF.

BCNF est plus stricte que 3NF, si une relation est BCNF alors
elle 3NF

•  Exemple. R(A,B,C) avec F = {AB à C,C à B} est 3NF mais

pas BCNF, dans C à B la partie gauche n’est pas une clé
candidate.