Embed Size (px)
1
Les dépendances entre les données et les moyens de
les vérifier Y Kermarrec
(à partir des transparents de J Ullman et de son livre)
2
Les dépendances fonctionnelles
X -> A est une assertion sur une relation R : lorsque deux n-uplets ont les même valeurs d’attributs sur X alors ils doivent avoir les même valeurs sur les attributs A
X -> A : X détermine A
3
Exemple
Drinkers(name, addr, beersLiked, manf, favBeer).
DF évidentes :1. name -> addr2. name -> favBeer3. beersLiked -> manf
4
Exemple
name addr beersLiked manf favBeerJaneway Voyager Bud A.B. WickedAleJaneway Voyager WickedAle Pete’s WickedAleSpock Enterprise Bud A.B. Bud
Car name -> addr car name -> favBeer
Car beersLiked -> manf
5
Clés des Relations
K est une clé de la relation R si:1. L’ensemble K détermine tous les
attributs de R2. Pour aucun sous ensemble de K, (1)
est vrai Si K vérifie (1), et pas (2), on dira
que K est une super-clé
6
Comment trouver les DFs ?
Analyser le problème et produire un cahier des charges précis
Mettre en évidence les liens entre les données
Reformuler le tout au client …
7
Comment trouver les clés ?
1. Au hasard ou en relisant le cahier des charges , en essayant de trouver une super clé puis une clé
1. Ex : deux cours ne peuvent pas avoir lieu dans la même salle en même temps
2. Salle heure -> cours
2. Détermination des clés à partir des DF
8
Fermeture des DF
Fermeture de Y notée Y + Point de départ : Y + = Y itération: trouver une DF dont la
partie gauche est un sous-ensemble de Y +. Si cette DF est X -> A, rajouter A à Y +.
9
Y+new Y+
X A
10
A quoi ça sert ? Vérifier que K est une clé Utile pour la normalisation cad la
décomposition de relations Exemple: ABCD avec comme DF AB
->C, C ->D, et D ->A. Décomposer R en ABC, AD. Quelles
sont les DFs sur ABC AB ->C, mais aussi C ->A !
11
Anomalies
La conception d’un schéma relationnel doit éviter les anomalies Anomalie de mise à jour : une
occurrence d’une donnée est mise à jour mais pas toutes
Anomalie de destruction : une information est perdue lorsque le n-uplet est enlevé
12
Exemple de mauvaise conception
Drinkers(name, addr, beersLiked, manf, favBeer)
name addr beersLiked manf favBeerJaneway Voyager Bud A.B. WickedAleJaneway ??? WickedAle Pete’s ???Spock Enterprise Bud ??? Bud
Les données sont redondantes car les ??? Peuvent être déduits À partir des DFsname -> addr favBeer etbeersLiked -> manf.
13
D’autres anomalies
name addr beersLiked manf favBeerJaneway Voyager Bud A.B. WickedAleJaneway Voyager WickedAle Pete’s WickedAleSpock Enterprise Bud A.B. Bud
• anomalie de mise à jour• anomalie de destruction
14
Décomposition
Les 2 extrêmes : Une seule relation avec tous les
attributs (aussi appelée relation universelle)
Autant de relations que d’attributs (un attribut par relation)
Avantages et inconvénients ?
15
L’idéal
Ne pas perdre de données Ne pas perdre de DFs Ne pas générer de nouvelles
informations lors de jointures (afin de reconstituer la relation universelle)
16
Boyce-Codd Normal Form
Une relation R est en BCNF si pour toute DF X ->A (non-triviale) X est une super-clé. Non trivial A n’est pas un sous
ensemble de X
17
Exemple
Drinkers(name, addr, beersLiked, manf, favBeer)
DFs: name->addr favBeer, beersLiked->manf
Seule clé {name, beersLiked}. Pour chaque DF, la partie gauche
n’est pas une super clé Drinkers n’est pas en BCNF
18
Exemple
Beers(name, manf, manfAddr) DF: name->manf, manf->manfAddr Clé : {name}. name->manf respecte la règle BCNF,
mais pas manf->manfAddr
19
Décomposition en BCNF
Soit R avec F l’ensemble des DFs Trouver une DF qui ne respecte pas
la règle BCNF, soit X ->B. calculer X +
Ne doit pas générer tous les attributs car sinon X est une super clé.
20
Décomposer R avec X -> B
- Remplacer R par :- R1 = X +.
- R2 = (R – X +) U X.
- Projeter les DFs de R sur les 2 nouvelles relations R1 et R2
- Calculer la fermeture de F = toutes les DFs- Ne garder les DFs que celles dont tous les
attributs sont dans R1 ou dans R2.
21
Principe de décomposition
R-X + X X +-X
R2
R1
R
22
Exemple
Drinkers(name, addr, beersLiked, manf, favBeer)
F = name->addr, name -> favBeer, beersLiked->manf
Drinkers n’est pas BCNF car name->addr. Calcul de la fermeture {name}+ = {name,
addr, favBeer}. Décomposer en 2 relations:
1. Drinkers1(name, addr, favBeer)2. Drinkers2(name, beersLiked, manf)
23
Exemple
Drinkers1 et Drinkers2 sont elles BCNF? Projeter les DFs est compliqué mais
simple dans cet exemple. Pour Drinkers1(name, addr, favBeer),
les DFs sont name->addr et name->favBeer Donc name est la seule clé et la relation
est BNCF.
24
Exemple
Pour Drinkers2(name, beersLiked, manf), la seule DF beersLiked->manf et la seule clé est {name, beersLiked}.
Violation de la règle BCNF. beersLiked+ = {beersLiked, manf},
on décompose Drikers2 en 1. Drinkers3(beersLiked, manf)2. Drinkers4(name, beersLiked)
25
Exemple
Le résultat de la décomposition de Drinkers:
1. Drinkers1(name, addr, favBeer)2. Drinkers3(beersLiked, manf)3. Drinkers4(name, beersLiked)
A noter Drinkers1 nous parle des buveurs, Drinkers3 nous parle de bières, et Drinkers4 nous parle des relations entre bière et buveurs.
26
Contraintes et Triggers
Une contrainte est une relation entre les données que le SGBD doit vérifier Exemple: contraintes de clés.
Triggers : ce sont des actions qui sont déclenchées sur événement
27
Les contraintes
Les clés Les clés étrangères. Les contraintes de domaine
Contraindre le domaine d’un attribut donné
Des contraintes sur des tuples Assertion : une expression
booléenne SQL
28
Les clés étrangères
Soit la relation Sells(bar, beer, price). On peut s’attendre à ce que la valeur de
l’attribut “beer” apparaisse dans la relation Beers.Name
Une contrainte qui impose qu’une bière dans Sells soit une bière dans Beers est appelée “contrainte de clé étrangère”
29
Clé étrangère
Utiliser le mot clé REFERENCES soit :1. Lors de la déclaration de l’attribut (s’il est
seul)2. En tant qu’élément du schéma
FOREIGN KEY ( <list of attributes> )REFERENCES <relation>
( <attributes> ) Les attributs ainsi référencés doivent être
déclarés PRIMARY KEY ou UNIQUE.
30
Exemple
CREATE TABLE Beers (
nameCHAR(20) PRIMARY KEY,
manfCHAR(20) );
CREATE TABLE Sells (
bar CHAR(20),
beerCHAR(20) REFERENCES Beers(name),
price REAL );
31
Exemple (autre formulation)
CREATE TABLE Beers (nameCHAR(20) PRIMARY KEY,manfCHAR(20) );
CREATE TABLE Sells (bar CHAR(20),beerCHAR(20),price REAL,FOREIGN KEY(beer) REFERENCES Beers(name));
32
Vérifier une clé étrangère
S’il y a une clé étrangère sur des attributs de R vers une clé primaire de la relation S, 2 cas de violations sont possibles:
1. Une insertion ou mise à jour de R introduit une valeur absente dans S.
2. Une destruction ou mise à jour de S qui provoque des références fantômes (« dangling reference »)
33
Action -- 1
Suppose R = Sells, S = Beers Une insertion ou mise à jour de Sells
qui introduit une bière non existante doit être rejetée
Une destruction ou mise à jour de Beers qui enlève une valeur de bière présente dans un n-uplet de Sells peut être traité de 3 manières
34
Action -- 2
Les 3 manières de réagir à la disparition de bières sont :
1. Default : rejeter la modification2. Cascade : réaliser les mêmes
modifications dans Sells Deleted beer : destruction des tuples de
Sells Updated beer: modifier les valeurs dans
Sells.
3. Set NULL : mettre bière à NULL
35
Exemple: Cascade
On retire Bud de la liste des bières On enlève tous les n-uplest de Sells
qui ont Bud comme valeur d’attribut pour bière
On modifie ’Bud’ en ’Budweiser’. On modifie tous les tuples de Sells
avec beer = ’Bud’ par beer = ’Budweiser’.
36
Exemple: Set NULL
On enlève BUD de Beers Modifie tous les n-uplets avec beer =
’Bud’ et remplacer cet attribut par beer = NULL.
On modifie le tuple en changeant de nom ’Bud’ vers ’Budweiser’. Même modification que
précédemment
37
Choix d’une politique
Lorsqu’on déclare une clé étrangère, il faut aussi préciser la politique SET NULL ou CASCADE pour les destructions ET les mises à jour
La précision est donnée lors de la déclaration de la clé étrangère:
ON [UPDATE, DELETE][SET NULL CASCADE]
L’action par défaut est de rejeter
38
Exemple
CREATE TABLE Sells (bar CHAR(20),beer CHAR(20),price REAL,FOREIGN KEY(beer)
REFERENCES Beers(name)ON DELETE SET NULLON UPDATE CASCADE );
39
Vérification sur attributs
Donner une contrainte sur le domaine de valeur d’un attribut
CHECK( <condition> ) : à utiliser lors de la définition de l’attribut
La condition peut référencer l’attribut en direct mais aussi n’importe quelle autre requête (relation et attribut).
40
Exemple
CREATE TABLE Sells (
bar CHAR(20),
beer CHAR(20) CHECK ( beer IN
(SELECT name FROM Beers)),
price REAL CHECK ( price <= 5.00 )
);
41
Les vérifications
La vérification est réalisée uniquement sur ajout ou mise à jour du n-uplet. Exemple: CHECK (price <= 5.00) Exemple: CHECK (beer IN (SELECT
name FROM Beers))
42
Tuple-Based Checks
CHECK ( <condition> ) peut faire partie de la déclaration du schéma de relation
La condition peut référencer n’importe quel attribut de la relation (ou d’une autre avec une requête)
Vérification sur insertion et mise à jour uniquement
43
Exemple: Tuple-Based Check
seul Joe’s Bar peut vendre des bières à plus de $5:CREATE TABLE Sells (
bar CHAR(20),beer CHAR(20),price REAL,CHECK (bar = ’Joe’’s Bar’ OR
price <= 5.00));
44
Assertions
Un élément d’une schéma d’une base de données
Définies par :CREATE ASSERTION <name>
CHECK ( <condition> ); La condition peut faire intervenir
n’importe quelle relation ou attribut de la base
45
Exemple: Assertion
pour Sells(bar, beer, price), aucun bar ne doit faire payer plus de $5 en moyenne
CREATE ASSERTION NoRipoffBars CHECK (NOT EXISTS (
SELECT bar FROM SellsGROUP BY barHAVING 5.00 < AVG(price)
));
Bars avec unPrix moyenDe 5 USD
46
Exemple: Assertion
Il ne peut pas y avoir plus de bars que de buveurs
CREATE ASSERTION FewBar CHECK (
(SELECT COUNT(*) FROM Bars) <=
(SELECT COUNT(*) FROM Drinkers)
);
47
Triggers
Les contraintes sur attributs ou tuples sont parfois limitées
Les assertions sont puissantes mais difficiles à mettre en oeuvre par les SGBD Il faut ne faire que les vérifications
nécessaires
48
Triggers
Un trigger permet à l(utilisateur de décider quand faire une action donnée
Comme une assertion, un trigger peut spécifier une condition générale et surtout exécuter n’importe quelle action sur la base
49
Des règles
Une règle : un événement + une condition + action
événement: classiquement une modification de la base, e.g., “insert on Sells.”
Condition : une expression SQL Action : une suite d’instructions
SQL
50
Exemple d’un Trigger
CREATE TRIGGER BeerTrigAFTER INSERT ON SellsREFERENCING NEW ROW AS NewTupleFOR EACH ROWWHEN (NewTuple.beer NOT IN
(SELECT name FROM Beers))INSERT INTO Beers(name)
VALUES(NewTuple.beer);
L’événement
la condition
L’action
