Embed Size (px)
Citation preview
Les Systèmes de Gestion de Bases de Données (SGBD)
dépendances fonctionnelles - normalisation
1
Le Havre
Bibliographie S. Abiteboul, R. Hull, V. Vianu, Foundations of Databases, Addison-
Wesley J.C. Date, A Guide to the SQL Standard, Addison-Wesley
J.C. Date, A Guide to DB2, Addison-Wesley R. Elmasri, S. Navathe, Conception et architecture des bases de
données, 4ème ed., publié par Pearson Education. H. Garcia-Molina, J. Ullman and J. Widom, Implementation of
Database Systems, Prentice Hall, 1999. G. GARDARIN, Bases de Données, Eyrolles, 6ème tirage, 2005. R. Ramakrishnan et J. Gehrke DATABASE MANAGEMENT
SYSTEMS, MacGraw Hill M. SCHOLL, B. AMANN, P. RIGAUX, V. CHRISTOPHIDES, D.
VODISLAV, Polycopié de Bases de Données, librairie des Arts et Métiers.
Ullman J.D. and Widom J. A First Course in Database Systems, Prentice Hall, 1997
Ullman J.D. Principles of Database and Knowledge-Base Systems, 2 volumes, Computer Science Press
Le Havre
Le modèle relationneldf normalisation
3
Le Havre
Le modèle relationnel
Introduit par E.F. Codd en 1970. Le mieux formalisé (bases mathématiques)
Le Havre
Domaine = ensemble de valeurs. Exemple : l'ensemble des réels entre ]10, 30[ peut être le
domaine de la variable PRIX.– attribut = variable avec valeurs dans un domaine
(exple : l'attribut PRIX)– relation sur A1, A2, …,An de domaines respectifs D1, D2, …, Dn
= sousensemble du produit cartésien : D1xD2x…xDn.= ensemble de tuples (x1, x2, ...xn) où xi est dans Di, i=1,n
Une valeur spéciale (NULL) peut être prise par un attribut.
Eléments du modèle
Le Havre
Produit cartésien
Produit cartésien de la relation R1 par la relation R
2 : R
1 x R
2
Argument : 2 relations quelconques R
1 (A
1, A
2, …, A
n) et R
2 (B
1, B
2, …, B
k)
Schéma de la relation résultat T : R
1 x R
2 : (A
1, …, A
n, B
1, …, B
k)
Occurrences de R = ensemble des tuples ayant n+k attributs :
– dont les valeurs des n premiers attributs sont les tuples de R1
– et les k dernières sont les tuples de R2
Le Havre
Produit cartésien
X
R1
R2R
Le Havre
Exemple
A B
1 1
1 2
3 4
C D E
a b a
a b c
b a a
A B C D E
1 1 a b a
1 2 a b a
3 4 a b a
1 1 a b c
1 2 a b c
3 4 a b c
1 1 b a a
1 2 b a a
3 4 b a a
R SR x S
Le Havre
Exemple de relation : une relation r sur les attributs NOM, ADR, NUM peut être décrite comme un ensemble de tuples :
r={(dupont, paris, 2140), durand, orsay, 1128), dubois, orsay, 3256)}
En général, on utilise une représentation tabulaire :
nom adr num
dupont paris 2140
durand orsay 1128
dubois orsay 3256
Le Havre
Une bases de données relationnelles : est un ensemble de relations.
Une relation R sur les domaines D1xD2x…xDn est représentée sous forme de table.
Chaque ligne est un tuple (a1, a2, …, an) où chaque élément ai est dans le domaine Di (= nuplet).
L ’ordre des lignes n’est pas important.
Les valeurs des colonnes de la tables sont les valeurs prises par les attributs.
Le Havre
Degré d ’une relation (arité) : son nombre d'attributs.
Occurrence : est un élément de l'ensemble figuré par une relation. Autrement dit, une occurrence est une ligne de la table.
Cardinalité d'une relation : son nombre d'occurrences.
Clé candidate : ensemble minimal des attributs de la relation dont les valeurs identifient de manière unique une occurrence.
Le Havre
Exemple Relation personne (nom, adresse, num)
Nom adresse num
Dupond
Durand
Dubois
Paris
Orsay
Orsay
2140
1128
3256
1 colonne
Il y a 3 attributs
==> degré (arité) = 3
1 tuple (= 1 ligne)
1 tuple
1 tuple
3 tuples => cardinalité = 3
Domaines:
nom : domaine de tous les noms de personnes (chaînes de car.)
adresse : domaine de toutes les adresses (chaînes de car.)
num : domaines de tous les numéros de personnes (des entiers naturels)
Le Havre
Contrainte d ’intégrité (CI) : propriété que doit vérifier une relation = p(R)
Clé primaire : attri. (ou ens d ’att) dont les valeurs permettent de distinguer les tuples les uns des autres dans une relation (identifiant) (numetud pour ETUDIANT)
Clé étrangère : attribut(s) non clé qui est clé primaire d ’une autre relation.
FOURNISSEUR (numf, nom, adr), PRODUIT( codep, lib, numf) On a : numf et codep = clés primaires, numf dans PRODUIT est une
clé étrangère de PRODUIT.
Contrainte de domaine : condition sur les valeurs d ’attributs. Ex : prixunitaire >100 ET prixunitaire <150
Quelques Contraintes d ’Intégrité (CI)
Le Havre
REMARQUES
La valeur d'une clé candidate est donc distincte pour toutes les occurrences.
Toute relation a au moins une clé candidate et peut en avoir plusieurs. Cela a pour conséquence qu'il ne peut jamais y avoir deux occurrences identiques au sein d'une relation (sinon ces deux occurrences représenteraient en fait le même objet).
Les clés candidates d'une relation n'ont pas forcément le même nombre d'attributs.
Le contexte du domaine modélisé est essentiel pour déterminer les clés candidates d'une relation.
Le Havre
Conception d'un schéma relationnel
Une mauvaise conception d'un schéma relationnel peut conduire à des problèmes dans l'exploitation de la base => D'où l'intérêt des dépendances fonctionnelles (df), de décomposition de schémas et de formes normales.
Ex. Soit un schéma de relation R (cours, etudiant, note, prof),On suppose que le quadruplet (c, e, n, p) appartient à la relation de schéma R si « l'étudiant e, a obtenu la note n au cours c fait par le prof p ».
Le Havre
Supposons qu'on a 200 étudiants qui suivent le cours c, les problèmes suivants se posent :
- redondance : le nom du prof p est répété 200 fois !
- risque d'incohérence : si le prof change (p devient p1), on doit faire 200 modifications (ou bien il y aura des incohérences)
- anomalie d'insertion : si le prof p n'est pas encore affecté au cours c ou si l'étudiant e n'a pas encore de note, on ne peut traduire l'inscription de l'étudiant au cours c. On peut dans ce cas, convenir d'une valeur NULL (ou absence de valeur) pour p ou n, mais il y a un risque d'oubli de màj des valeurs NULL lorsque les notes sont données ou le prof est nommé.
- anomalie de suppression : si on efface les inscription des étudiants en fin d'année, on perd l'information « l'enseignant p enseigne le cours c »
Le Havre
Comment choisir les schémas pour éviter ces problèmes ?
La théorie des formes normales permet d'atténuer ce problème en classifiant les relations. L'idée est alors de remplacer un schéma de relation qui pose problème par 2 ou plusieurs autres dont la forme est plus optimale. Ceci conduit à la notion de décomposition.
Pour formaliser ce concept, on introduit la notion de DEPENDANCE FONCTIONNELLE (df).
Avant cela, on fait quelques rappels sur les opérations de l'algèbre relationnelle.
Le Havre
Schéma de la relation r, noté R
= nom_rel (att:dom1, att2: dom2, …)– Convention : on omet les domaines : – => VILLE= (code, nom, adr)
Opération sur les relations : rappels
Le Havre
Projection des attributs d’une relation r de schéma R sur un sous ensemble des attributs de R : relation s de schéma S obtenue en ne conservant que les colonnes de r qui correspondent aux attributs de S (et en supprimant les tuples dupliqués éventuellement)
пA1, A2, …, Ak(R) = R(A1, A2, …,Ak)
où A1, A2, …,Ak sont un sous-ensemble du schéma de
la relation R (égal ou inclus).
La projection sur A1, A
2, …, A
k élimine tous les autres
attributs de la relation et supprime les tuples dupliqués.
La projection : п
R R'п
Le Havre
Exemple de projection
X Y Z
a b c
d a b
c b d
a b e
e e a
=>пX,Y(R) =
R = (X,Y,Z) et R' =пX,Y(R) = projection de R sur les attributs X et Y
R'RX Y
a b
d a
c b
e e
Le Havre
Exemple de projection (2)
Requête : Soit la relation Ville (id, nomp, nomv)– Quels sont les villes de résidence des
personnes de la base (projection sur l'attribut nomv)
nomv
Tab2 =nomv(Tab1)
ParisParisJacquesJacques35003500ParisParisDurandDurand33333333HavreHavreMarcMarc15001500nomvnomvnompnompidid
Tab1
ParisParisHavreHavrenomvnomv
Tab2
Le Havre
Jointure naturelle Soient 2 relations R et S ayant des attributs en commun
R(A1, …, Am, X1, …,XK)
S(B1, …, Bn, X1, …, Xk)
Schéma de la relation R S, jointure naturelle de R et S : T (A1, …, Am, B1, …, Bn,X1, …,XK )
Un tuple de R S comporte donc (m+n+k) attributs.
A B C
a b c
d b c
b b f
c a d
B C D
b c d
b c e
a d b
A B C D
a b c d
a b c e
d b c d
d b c e
c a d b
RS
R S
Le Havre
-jointure
C ’est une jointure entre 2 relations R et S avec : R = ( A1, …, Am), S = (B1, …, Bn ) Schéma de T = R
AiBj S = (A1, …, Am, B1, …, Bn )
La valeur de T est : Ai Bj (RxS) : sélection des tuples de
RxS tels que Ai Bj où {=, <, >, , , }
Equijointure : on parle de équijointure quand l’opérateur est l’égalité.
R AiBj
S, où {=, < , >, , , }
Le Havre
Exemple d ’équijointure
A B
1 a
1 b
3 a
C D E
1 b a
2 b c
4 a a
R S A B C D E
1 a 1 b a
1 a 2 b c
1 a 4 a a
1 b 1 b a
1 b 2 b c
1 b 4 a a
3 a 1 b a
3 a 2 b c
3 a 4 a a
A B C D E
1 a 4 a a
1 b 1 b a
1 b 2 b c
3 a 4 a a
RxS
R B=D S
B D = B=D (RxS)
Le Havre
Dépendances fonctionnelles (df)
- C'est un cas particulier de contraintes d'intégrité
- Une df est définie sur l’intension (donc elle est valide quelque soit l'extension)
Le Havre
Schéma de Bd relationnelle : ensemble de schémas de relations
Définition d'une dépendance fonctionnelles (df) : Soient : R, un schéma de relation, A, B, C des attributs et X,
Y, Z des ensembles d ’attributs de R. => la relation r de schéma R vérifie la df X > Y, si la
connaissance des valeurs de X détermine les valeurs de Y (si 2 tuples ont même valeurs sur les attributs de X alors ils ont mêmes valeurs sur les attributs de Y)
càd t1, t2 r : x1 = x2 => y1 = y2
Le Havre
Exemple : A B C D
a b c d
a b c d'
a' b c d'
Cette relation vérifie les dépendances fonctionnelles suivantes :
X → Y et Z → Y avec X={A,B} Y={C} et Z = {D}Mais ne vérifie pas Y → Z (car on a pour une valeur de Y (c-à-d c), on a 2 valeurs de Z (d et d'))
Le Havre
Pour modéliser le monde réel, on se donne un (ou des) schéma(s) de relation(s) et une sémantique pour ce(s) schéma(s). Une partie de cette sémantique est traduite par des df.
Dans la suite, on se donne un ensemble F de df et un schéma de relation. On ne considère ensuite que les relations qui vérifient les df de F. Exemple : Soit le schéma de relation ADR (rue, ville, codepostal) qui modélise une adresse dans un pays.
Le Havre
Soient les relations r1 et r2 :
rue Ville codepostal
Gambetta bordeaux 33000
archangé orsay 91400
rue Ville codepostal
st-jacques paris 75005
st-jacques paris 75014
r1
r2
On a : r1 vérifie F ={df1, df2} r2 ne vérifie pas df1 (rue et ville dans R2 donne deux codes postaux différents)
On a F constitué des df suivantes :df1 : rue, ville → codepostaldf2 : codepostal → ville
Le Havre
Autre exemple : soit un schéma de relation R(prof, codmat, j, h, salle)Un tuple (p, m, s, j, h) d'une relation r de schéma R signifie « l'enseignant p enseigne la matière m dans la salle s le jour j à l'heure h »On impose alors aux relations r l'ensemble F, des df suivant :
df1 : (prof, h, j) → (salle, codmat)C-à-d un enseignant donné, à une heure donné d'un jour donné ne peut se trouver que dans une seule salle et y enseigner une seule matière.
df2 : (h, j, salle) → (prof, codmat)C-à-d à une heure donnée, d'un jour donné, dans une salle donnée, un
seul enseignant peut y enseigner et n'enseigner qu'une seule matière. df3 : prof → codmat
On a dans cet établissement un enseignant qui n'enseigne qu'une seule matière.
Rmq : une df est une propriété qui s'applique à un ensemble de relations : elle ne peut être déduite d'une seule relation.
Le Havre
Une df est une assertion sur le monde réel (une hypothèse) : on ne peut donc pas démontrer !
Ex : la df : num_etu → nom_etu signifie « la connaissance du numéro d'un étudiant détermine la connaissance de son nom », on ne peut pas le démontrer, c'est par construction.
Le Havre
Propriétés des df : soit R un schéma relationnel muni d ’un ensemble F de df.
Par convention, on note par XY la réunion des ensembles d ’attributs X et Y
On note XY leur différence : Si X={A,B} et Y = {B,C} alors XY = {A}
On appelle partie stricte Y d ’un ensemble X, tout sousensemble de cet ensemble non égal à lui,
càd Y X.
Implication de df : la df X Y est impliquée par F si →toute relation r de R qui vérifie F vérifie la df X Y. →On note : F ==> X Y→
Fermeture de F : (notée F+) = ensemble des df impliquées par F.
Le Havre
Règles d ’Armstrong
a) Réflexivité : Si Y est contenu dans X, alors la df X Y est vérifiée. (df triviale)→
b) Augmentation : pour tout Z inclus dans R, si la df X Y est vérifiée, alors la df XZ YZ l’est → →aussi,
soit X Y ==> XZ YZ.→ →
c) Transitivité : Si les df X Y et Y Z sont vérifiées, → →alors la df X Z l ’est aussi. →
{X Y et Y Z } ==> X Z→ → →
Le Havre
Intérêt de ces règles : cf. théorème :
Si la df X Y se déduit de F en appliquant les règles →d ’Armstrong, alors X Y appartient à F→ +.
➢
Réciproquement, toute df X Y de F+ se déduit de F par application de ces règles.
Donc ces règles permettent de calculer F+. Mais cela peut être fastidieux ==> Déduction de règles supplémentaires (déduites des règles
de base) :
Le Havre
Règles supplémentaires
d) additivité : {X Y et X Z } ==> X YZ.→ → →
e) Pseudotransitivité : {X Y et WY Z } ==> XW Z.→ → →
f) Décomposition : X Y ==> X Z si Z est inclus dans Y.→ →
Le Havre
Graphe de dépendances fonctionnelles
Les nœud du graphes sont les attributs de la relation Les arcs du graphes sont les df
Exemple : Soient les relations :Buveurs (nb, nom, prenom, ville)Commandes (nc, datec, nv, qtec, nb)Expeditions (nc, dateexp, qteexp)
On a les df : nb nom, nb prenom, nb ville→ → →nc datec, nc nv, nc qtec, nc nb→ → → →(nc, dateexp,) qteexp→
Le Havre
ncnb
datec nv qtec nom prenom ville dateexp
qteexp
Le Havre
ncnb
datec nv qtec nom prenom ville dateexp
qteexp
Fermeture transitive d'un ensemble F de df = F+
F+ = F U df obtenues via les axiomes
Le Havre
Couverture minimale de F = ensemble minimal de df représentant la même information que F, mais sans redondance (donc qui génère toutes les df).
En général, la couverture minimale n’est pas unique. Il existe des algorithmes pour la calculer.
Le Havre
Calcul de la Couverture minimale de F = ensemble G de df, tel que :
– 1. G+ = F+ (G implique les mêmes df que F)– 2. tout membre droit d ’une df est réduit à un seul attribut.– 3. Pour aucune df X A de G, on n’a : G {X A} ==> G → →
(évite d ’avoir une df X A dont on peut se passer)→
– 4. Pour aucune df X A de G, on n’a : →
G ==> (G {X A}) U Y A, avec Y partie stricte de X.→ →ou pour aucune df X A de G, on n’a : →G ==> Y A, où Y→ X.
Le Havre
Remarques :
La propriété 3 évite d'avaoir dans G une df dont on peut se passer, car on peut l'obtenir par implication à partir des autres. On peut reformuler (3) de manière équivalente en (3') :
(3') : pour aucune df X A de G on n'a →G – {X A} => X A→ →
La propriété (4) permet d'avoir des df les plus simples possible (dont les membres gauches sont minimaux) . On peut reformuler (4) de manière équivalente en (4') :
(4') : pour aucune df X A de G, on n'a →G => Y A avec Y partie stricte de X.→
Le Havre
Clé d ’un schéma de relation : soit R = (A1, A2, …, An) un schéma de relation, F un ensemble de df sur R et X un ensemble d’attributs de R.
On dit que X est une clé de R muni de F si une des conditions suivantes est satisfaite :
la df X R → F+
F => X R→ toute relation r sur R qui satisfait F vérifie X R→
Le Havre
Fermeture d ’un ensemble d ’attributs X relativement à un ens. de df F (noté X+) :
C'est l'ensemble des attributs A pour lesquels la df X A est →dans la fermeture de F. C’est aussi l’ensemble des attributs qui prennent au plus une valeur quand celles des attributs de X sont fixées. (cf. algos de calcul de X+)
Le Havre
Algorithme de calcul de la fermeture d ’un ensemble d ’attributs X (càd X+) :
DEBUT
X+ := X
REPETER
aux := X+ /* aux est une variable auxiliaire */
POUR chaque df Y -> Z de F FAIRE
SI Y est inclus dans X+ ALORS X+ := X+ Z
FINPOUR
JUSQU ’A aux = X+ ou X+ = R
FIN
Le Havre
Exemple :Soit le schéma de relation R = (A, B, C, D , E) et l'ens. de df F = {AB → C, B → D, CD → E}Calcul de (AB)+, la fermeture de l'ensemble d'attributs AB.
Appliquons l'algo. en prenant les df dans l'ordre suivant :CD → E, B → D, AB → C
Le Havre
X+ := AB
1ère boucle REPETERAUX := ABCD → E n'augmente pas X+ := ABB → D augmente X+ et donne X+ := ABDAB-> C donne X+ := ABDC (ou ABCD)
Comme AUX <> X+, on continue :
2ème boucle REPETERAUX := ABCDCD → E augmente X+ et donne X+:= ABCDEB → D et AB → C ne changent rien puisque X+ = RComme X+ = R, l'algorithme s'arrêteDonc (AB)+ := ABCDE
Le Havre
Remarque : l'ordre d'application des df influe sur les performances de l'algorithme :
On prend les df dans un autre ordre :AB → C, B → D, CD → E
X+:= AB1ère boucle REPETER
AUX:= ABAB → C donne X+:= ABCB → D donne X+:= ABCDCD → E donne X+:= ABCDE
Comme X+ = R = ABCDE, l'algo s'arrête.Donc (AB)+:= ABCDE
Le Havre
conséquence : vérifier qu ’un ens. d’attr. K est une clé de R muni de l ’ens. F de df revient à montrer que tous les attributs de R sont dans K+.
Mais seule la notion de clé minimale (appelée souvent clé ou clé candidate) est intéressante, d'où la définition :
X est une clé minimale (de R muni de F) ssi X est une clé et tout sousensemble de X différent de X, n’est pas une clé.
Le Havre
Propriétés utiles
PROP1 : tout attribut qui ne figure pas dans le membre droit d ’une df non triviale de F doit appartenir à toute clé de R.
PROP2 : si l ’ens. des attr. de R qui ne figurent pas en membre droit d ’une df non triviale de F est une clé, alors R possède une clé minimale unique formée par l ’ens. de ces attr.
PROP3 : un schéma de relation muni d ’une seule df possède une clé minimale unique.
Le Havre
Décomposition d ’un schéma de relation : Soit R=(A1, A2, …, An) où les Ai sont des attributs
simples, la décomposition de R est le remplacement de R par un ens de schémas de relations R1, R2, …Rp (p>=1) obtenus à partir de R par projection et tels que :
U i=1i=p Ri= R
Décomposition sans perte d ’information (SPI) :
une décomposition de R = (A1, A2, …, An) est SPI si toutes les relations r sur R considérées sont égales à la jointure des relations ri (1<=i<=p) obtenues par projection de r sur les schémas Ri.
Le Havre
Le théorème suivant (Ulman88) donne une CNS (cond. Necéss. Et suffis.) pour qu ’une décomposition soit SPI :
Théorème : soit R=(X, Y, Z) où X, Y, Z sont des ensembles d ’attributs. Soit la df X Y dans F, alors la décomposition →de R en S =(X,Y) et T =(X, Z) est SPI.
Réciproquement, si la décomposition de R en S et T est SPI alors X Y ou X Z appartient à F→ → + (sont des df)
Préservation des df par décomposition : on dit que la décomposition de R en R1, R2, …, Rp préserve les df (ou sans perte de df, SPD) si la fermeture de la réunion des Fi (1<=i<=p) est égale à F+. Soit U (Fi)+ (1<=i<=p) = F+.
Le Havre
Df élémentaire : R un schéma, X, Y, Z des ens d ’attr. , X Y est une df élémentaire, si c’est une df et il n ’existe pas Z →
inclus dans X avec Z Y.→
df directe : X > Y est directe si : il n ’existe pas Z tel que X Z et Z Y.→ →
Formes normales La classification des relations en fonction de leur propriétés vis
àvis des df est représentée par les formes normales.
Plus le degré de normalité élevé, plus les anomalies de màj sont réduites.
Dépendance fonctionnelle élémentaire/directe
Le Havre
Relation en 1NF : si tous ses attributs ont des valeurs atomiques (attributs non décomposables, Un attribut => Une valeur max)
Relation en 2NF : si elle est en 1NF et aucun attribut non clé ne dépend d ’une partie de la clé, I.e.toutes les df sont élémentaires.
Relation en 3NF : si elle est en 2NF et aucun attribut non clé ne dépend d ’un autre attribut non clé, i.e. toutes les df sont élémentaires directes.
Formes normales
Le Havre
Ou bien une Relation est en 3NF : si tout attribut qui n ’appartient à aucune des clés minimales du schéma ne dépend que des clés du schéma et des ensembles d ’attributs qui le contiennent (cas de df triviales).
Relation en BCNF (BoyceCodd Normal Form) : si aucun attribut nonclé n'est source de df vers la clé (ou partie de la clé)
Le Havre
Remarques
Rmq1. un schéma est en 3NF si :– a. en cherchant ses clés minimales (algo), – b. on déduit les attributs A qui n ’appartiennent à
aucune clé minimale, – c. puis on regarde les df X A de F→ + (où A est déjà
déterminé au (b)), A non inclus dans X (cas de df triviale) et tester pour chacune d ’elle si X est une clé.
Rmq2. Pour montrer qu’un schéma R n ’est pas en 3NF, il suffit de donner une df X A de F→ + avec X non clé, A non inclus dans X et n’appartenant à aucune clé.
Le Havre
Exemple de forme normale de BoyceCodd (BCNF) (aucun attribut nonclé n’est pas source de df vers une partie de la clé).
Exemple : RECOLTE (product, annee, quantite, numvin) On a : (product, annee) quantite→ (product, annee) numvin→
Mais on a aussi : numvin product → d ’où la relation n'est pas en BCNF.
On décompose en : RECOLTE(numvin, annee, quantite) et VIN(numvin, product) qui sont en BCNF.
Le Havre
Propriétés utiles :
PROP4. Un schéma en 3NF qui n’admet qu’une clé minimale est en BCNF.
PROP. Un schéma R muni d’une seule df de la forme X Y, avec X → U Y = R est en BCNF.
Le Havre
Exemple : Soit le schéma M=(S, R, A, C) où S, R, A, C sont des attributs qui caractérisent respectivement une succursale de magasin , (S) un rayon de succursale (R) , un article (A) et un chef de rayon (C). On suppose que les df suivantes sontSatisfaites : SA → R et SR → C
Montrer que SA est une clé de M.Par augmentation par S : SA → R => SA → SRPar transitivité, on a SA → SR et SR → C on aura : SA → CD'après la propriété PROP2, on a SA contient des attributs qui ne sont dans aucun membre droit de df et forme une clé, SA est la seule clé minimale de M.
M en 3NF ?On a C est un attribut qui n'appartient pas à la clé minimale,que SR n'est pas une clé, la df SR → C montre que M n'est pas en 3NF.
Le Havre
Algorithme de recherche d ’une couverture minimale d ’un ensemble de df :
X, Y, … = des ensembles d ’attributs, A, B, C, … = des attributs somples
Données : R=(A1, A2, …,An) un schéma de relation, F un ensemble de df sur RRésultat : G, une couverture minimale de F
(1) G+ = F+ (2) Tout membre droit d ’une df de G est réduit à un seul attribut(3) Pour aucune df X A de G on n ’a G {X A } => X A→ → →(4) Pour aucune df X A de G on n ’a G => Y A avec Y → →partie stricte de X
Le Havre
ALGORITHME
On ordonne les df de F. Soit F = {X1 Y→ 1, X2 Y→ 2, …, Xn Y→ n}
Etape 1 : on décompose les membres droits Yi des df de F : Pour i de 1 à m Faire Si Yi = A1 A2 … As avec s > 1 Alors F := F {Xi Y→ i} U {Xi A→ 1, Xi A→ 2, …, Xi A→ s} On supposera par la suite que l ’on a : F = {X1 A→ 1, X2 A→ 2, …, Xp A→ p}
Le Havre
Etape 2 : on regarde si on peut enlever des df de F sans modifier sa fermeture
Pour i de 1 à p
Si {F - {Xi→ Ai}} => {Xi→ Ai} Alors F := F - {Xi→ Ai}
Quitte à renuméroter les df, on suppose qu’à la fin de cette étape, on a :
F = {X1→ A1, X2→ A2, …, Xq→ Aq}
Le Havre
Etape 3 : On cherche à remplacer les membres gauches des df formés de plus d ’un attribut par des membres gauches ayant moins d ’attributs sans changer la fermeture de F
Pour i de 1 à q Faire
Si Xi = B1 B2 … Br avec r > 1 Alors Pour j de 1 à r Faire Si F => {Xi Bj} A→ i Alors Xi := Xi – Bj (on enlève
l'attribut Bj )
Le Havre
COMMENTAIRES
Etape 1 : propriétés d ’augmentation et de décomposition. X AB est équivalent à X A et X B→ → → Etape 2 : on supprime des df superflues (redondantes) Etape 3 : il suffit de remarquer que si on a
F => ({Xi Bj} A→ i ) alors les ensembles de df F et F ’ = {F {Xi A→ i} U { {XiBj} A→ i} } sont équivalents.
En effet, par augmentation et décomposition, on a : la df {Xi Bj} A→ i implique la df Xi A→ i (donc F ’ implique F)
Le Havre
Remarques :
1. la couverture minimale n’est pas unique (en général) 2. on peut inverser l’ordre des étapes 2 et 3, on obtient
toujours une couverture minimale 3. à l’étape 2, pour tester si {F {Xi A→ i}} =>
{Xi A→ i,}, il suffit de tester si Ai appartient à la fermeture de Xi relativement aux df de F {Xi A→ i}. De même à l ’étape 3, la condition F => {Xi Bj} A→ i peut se tester en regardant si Ai appartient à la fermeture de
{Xi Bj} relativement à F. (=> on peut utiliser l’algo)
Le Havre
Ex. Soit un schéma de relation R, concernant des cours C, des étudiants E, des professeurs P, des notes N, des jours et des horaires de cours J et H, et des salles de cours S.Soit R = (C, E, P, N, J, H, S) muni de l'ensemble de df F :CEP → N (1) JHS → PC (2)EP → C (3)EPS → C (4)
Calculer la couverture minimale de F, notée F+
Etape 1 : tout membre droit d'une df est réduit à un seul attribut. F devient l'ensemble suivant :CEP → N (1)JHS → P (2')JHS → C (2'')EP → C (3)EPS → C (4)
Le Havre
Etape 2 : Enlever des df superflues (enlever des df de F sans modifier sa fermeture) :- On ne peut pas retirer la df (1) car aucune autre df ne contient N dans son membre droit. - La df (2') ne peut pas être retirée pour la même raison (pour P).- Pour voir si on peut retirer la df (2''), on calcule (JHS)+ relativement à F -{(2'')}. On a (JHS)+:= JHSP. Il ne contient pas C, donc on ne peut pas retirer la df (2'') : JHS → C.- Pour voir si on peur retirer la df (3), on calcule (EP)+ relativement à F – {(3)}. On trouve (EP)+:= EP. Il ne contient pas C. Donc, on garde la df (3) : EP → C. Pour la df (4), on remarque que la df (3) implique la df (4), donc F – {(4)} => (4). On peut donc retirer la df (4).Ou bien, on calcule (EPS)+ relativement à F – {(4)}:= EPSC,car EP → C, donc (EPS)+ contient C. On peut la supprimer.A la fin de l'étape 2, F = {(1), (2'), (2''), (3)}
Le Havre
Etape 3 : minimiser le nombre d'attributs dans les membres gauches des df (les faire « maigrir »). - On considère la df (1) (CEP → N), on teste si F implique la df EP → N (donc si C est superflu). On calcule (EP)+ := EPC. Il contient C, donc on peut supprimer C de la df (1). On aura (1') : EP → N.On continue pour voir si on peut supprimer E de (1').On calcule P+:= P, ne contient pas E. Donc, on garde E.On voit si on peut supprimer P. On calcule E+ : = E. Il ne contient pas P. Donc on garde P. On ne peut faire « maigrir » davantage le membre droit de (1'), qui sera : EP → N.- On considère la df (2') (JHS → P). On teste si on peut supprimer des attributs de JHS. On calcule (HS)+:= HS, (JS)+ := JS, (JH)+:= JH. Donc la df (2') ne peut pas être « amaigrie ». (2') : JHS → P
Le Havre
Etape 3 suite :- On considère la df (2'') (JHS → C). On obtient les mêmes résultats. On ne peut pas faire « maigrir » le membre gauche.Donc (2'') : JHS → C.De même que la df (3) : EP → C.
La couverture minimale est donc F = {(1'), (2'), (2''), (3)}
Le Havre
Le Havre
Le Havre
Le Havre
ALGORITHME DE BERNSTEIN X, Y, … = ens d ’attributs, A, B, C, … = ens d ’attributs Données : R=(A1, A2, …,An) un schéma de relation, F un ensemble de df sur R Résultat : une décomposition de R muni de F en schémas
de relations 3NF, SPI, SPD
Etape 1. On remplace F pas sa couverture minimale (algo). On cherche les clés minimales de R et on teste si R est en 3NF.
Si oui, on s ’arrête, Si non on passe à l ’étape 2.
Le Havre
Etape 2. On regroupe les df X A→ i (1 i p) ayant même membre gauche X. Pour chaque membre gauche X, on définit un schéma de relation contenant tous les attr. des df, soit
RX=(X, A1, A2, …, Ap). Le schéma RX est muni de l ’ensemble des df X Ai (1→ i p).
Etape 3. Si aucun des schémas de RX définis à l ’étape 2 ne
contient de clé de R, alors on ajoute un schéma RK =(K), où K est une clé minimale de R, muni d ’aucune df.
Le Havre
REMARQUES :
1. chacun des schémas Ri obtenus à l’étape 2 et muni des df X A→ i (1 i p ), soit encore de la df équivalente X A→ 1 A2…Ap, est bien en 3NF. De même le schéma RK.
2. le schéma RK sert à assurer que la décomposition est bien SPI.
3. La décomposition est trivialement SPD puisque la réunion des df des nouveaux schémas est F.
