Transcript
Page 1: 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)

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)

Page 2: 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

Page 3: 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)

3

Exemple

Drinkers(name, addr, beersLiked, manf, favBeer).

DF évidentes :1. name -> addr2. name -> favBeer3. beersLiked -> manf

Page 4: 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)

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

Page 5: 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)

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é

Page 6: 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)

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 …

Page 7: 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)

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

Page 8: 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)

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 +.

Page 9: 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)

9

Y+new Y+

X A

Page 10: 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)

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 !

Page 11: 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)

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é

Page 12: 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)

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.

Page 13: 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)

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

Page 14: 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)

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 ?

Page 15: 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)

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)

Page 16: 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)

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

Page 17: 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)

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

Page 18: 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)

18

Exemple

Beers(name, manf, manfAddr) DF: name->manf, manf->manfAddr Clé : {name}. name->manf respecte la règle BCNF,

mais pas manf->manfAddr

Page 19: 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)

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é.

Page 20: 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)

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.

Page 21: 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)

21

Principe de décomposition

R-X + X X +-X

R2

R1

R

Page 22: 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)

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)

Page 23: 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)

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.

Page 24: 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)

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)

Page 25: 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)

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.

Page 26: 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)

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

Page 27: 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)

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

Page 28: 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)

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”

Page 29: 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)

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.

Page 30: 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)

30

Exemple

CREATE TABLE Beers (

nameCHAR(20) PRIMARY KEY,

manfCHAR(20) );

CREATE TABLE Sells (

bar CHAR(20),

beerCHAR(20) REFERENCES Beers(name),

price REAL );

Page 31: 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)

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));

Page 32: 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)

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 »)

Page 33: 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)

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

Page 34: 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)

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

Page 35: 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)

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’.

Page 36: 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)

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

Page 37: 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)

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

Page 38: 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)

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 );

Page 39: 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)

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).

Page 40: 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)

40

Exemple

CREATE TABLE Sells (

bar CHAR(20),

beer CHAR(20) CHECK ( beer IN

(SELECT name FROM Beers)),

price REAL CHECK ( price <= 5.00 )

);

Page 41: 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)

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))

Page 42: 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)

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

Page 43: 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)

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));

Page 44: 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)

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

Page 45: 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)

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

Page 46: 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)

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)

);

Page 47: 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)

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

Page 48: 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)

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

Page 49: 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)

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

Page 50: 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)

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


Recommended