optimisation

M1 Miage
U.N.S.
P. Crescenzo - I. Mirbel
Ann´ee universitaire 2014/2015
TP 4
Fonctionnement d’un SGBD
L’optimisation
I. R´
evisions sur le langage alg´
ebrique
EXERCICE 1 :
Soit le sch´ema relationnel suivant :
EMP(Matr, NomE, Poste, DatEmb, Sup, Salaire, Commission, NumDept)
DEPT(NumDept, NomDept, Lieu)
PROJET(CodeP, NomP)
PARTICIPATION(Matr, CodeP, Fonction)
– Donnez la suite d’op´erations ´el´ementaires de l’alg`ebre relationnelle pour obtenir les donn´ees
qui correspondent aux listes suivantes :
1.
2.
3.
4.
5.
Matricules et noms des employ´es qui ont ´et´e embauch´es avant le 1er janvier 1995.
Noms des employ´es qui ont le poste de secr´etaire.
Noms des employ´es avec le nom du d´epartement dans lequel ils travaillent.
Noms des employ´es qui travaillent dans le d´epartement FINANCES.
Num´eros des d´epartements qui ont des ing´enieurs.
II. Application du cours
EXERCICE 1 :
Soit le sch´ema relationnel suivant :
Etudiant(Id-Etud, Nom-Etud, Adr-Etud, Res)
UFR(Id-UFR, Nom-UFR, Adr-UFR)
Cours(Id-Cours, No-UFR, Libell´e, Resp)
Inscr(No-Cours, No-Etud, Note)
– On souhaite r´epondre `
a la requˆete suivante : Donner le nom et le r´esultat des ´etudiants ayant
obtenu la note de 15 en anglais. Donner l’arbre correspondant `a cette requˆete puis trouver
deux arbres optimaux.
– Donner l’arbre optimal correspondant `a la requˆete suivante :
Q1= (π[Nom-UFR, Adr-UFR] (σ [Id-UFR = No-UFR] (σ[Resp=’Dupont’] (Cours ×
UFR))))
– Donner l’arbre optimal correspondant `a la requˆete suivante et dans lequel les premi`eres tables
jointes sont celles sur lesquelles sont effectu´ees les s´elections.
Q2 = Select Nom-UFR, Libell´
e, Id-Cours
From UFR, Cours, Inscr, Etudiant
Where (Nom-Etud = ’Smith’) and (Cours.Id-Cours = Inscr.No-Cours) and
(UFR.Id-UFR = Cours.No-UFR) and (Etudiant.Id-Etud = Inscr.No-Etud)
EXERCICE 2 :
Soient les profils correspondant `a 4 relations W, X, Y et Z.
W(a,b)
CARD(W)=100
VAL(W,a)=20
VAL(W,b)=60
X(b,c)
CARD(X)=200
VAL(X,b)=50
VAL(X,c)=100
Y(c,d)
CARD(Y)=300
VAL(Y,c)=50
VAL(Y,d)=50
Z(d,e)
CARD(Z)=400
VAL(Z,d)=40
VAL(Z,e)=100
Donner une estimation de la taille des relations r´esultats des expressions suivantes. Dans le cas
o`
u le nombre de valeurs distinctes d’un attribut de jointure est diff´erent dans les deux tables jointes,
on doit consid´erer le maximum de ces deux nombres pour estimer la taille de la table r´esultat de
la jointure.
–
–
–
–
σa=10 (W)
X ./ Y
(πc (Y)) ./ X
W ./ X ./ Y ./ Z
EXERCICE 3 :
On consid`ere une base de donn´ees constitu´ee des relations suivantes :
Production(NoPdt, Type, Modele, Qt´eStock, Machine)
DetailCmde(NoCmde, NoPdt)
Cmde(NoCmde, Client, MontantCmde)
Comm(NoCmde, Vendeur, MontantComm)
On consid`ere les profils suivants:
CARD(Production) = 200 000
CARD(DetailCmde) = 50 000
CARD(Cmde) = 10 000
CARD(Comm) = 5 000
SIZE(NoPdt) = 10
SIZE(Type) = 1
SIZE(Modele) = 10
SIZE(Qt´e) = 10
SIZE(Machine) = 10
SIZE(NoCmde) = 5
SIZE(Client) = 30
SIZE(MontantCmde) = 10
SIZE(MontantComm) = 10
SIZE(Vendeur) = 20
SIZE(DetailCmde) = 15
SIZE(Comm) = 35
VAL(Production, NoPdt) = 200 000
VAL(Production, Type) = 4
VAL(Production, Modele) = 400
VAL(Production, Qt´e) = 100
VAL(Production, Machine) = 50
VAL(Cmde, NoCmde) = 10 000
VAL(Cmde, Client) = 400
VAL(Cmde, MontantCmde) = 5000
VAL(Comm, NoCmde) = 10 000
VAL(Comm, MontantComm) = 7500
VAL(Comm, Vendeur) = 25
VAL(DetailCmde, NoCmde) = 10 000
VAL(DetailCmde, NoPdt) = 50 000
SIZE(Production) = 41
SIZE(Cmde) = 45
D´ecrire l’optimisation alg´ebrique et le calcul des profils sur les r´esultats interm´ediaires pour les
requˆetes suivantes, qui n´ecessitent d’ˆetre ´ecrites en SQL puis traduites en langage alg´ebrique.
– Donner la quantit´e disponible du produit dont l’Id est R2778.
– Donner les machines n´ecessaires `
a la production des produits achet´es par monsieur Dupont.
Pour la seconde requˆete qui n´ecessite des jointures entre plusieurs tables, donner l’ordre de
jointure qui vous semble le plus indiqu´e `a la vue de la taille des tables. Donner ´egalement l’arbre
de d´ecision permettant de choisir parmi les techniques de jointure.
EXERCICE 4 :
On consid`ere une base de donn´ees constitu´ee des relations suivantes :
INSTRUMENT(IDI, NomI)
ARTISTE(IDA, NomA, PrenomA, DNaiss, Natio)
ALBUM(IDD, TitreA, Aparution, Label)
CONTRIBUTION(IDD, IDA, IDI)
La table INSTRUMENT rassemble les informations concernant les diff´erents instruments de musique : un identifiant (IDI) et un nom (NomI). La table ARTISTE contient les informations concernant les artistes : un identifiant (IDA), un nom (NomA), un pr´enom (PrenomA), une date de
naissance (Dnaiss) et une nationalit´e (Natio). La table ALBUM rassemble les informations concernant les albums : un identifiant (IDD), un titre (TitreA), l’ann´ee de parution (AParution) et le
label ayant ´edit´e le disque (Label). Enfin, la table CONTRIBUTION contient les informations
concernant la participation d’un artiste (IDA) `a un album (IDD). Elle indique plus pr´ecis´ement
le(s) instrument(s) jou´e(s) par l’artiste (IDI) sur l’album.
On consid`ere les profils suivants:
CARD(INSTRUMENT)=15
CARD(CONTRIBUTION)=280
VAL(IDI,INSTRUMENT)=15
VAL(IDA, ARTISTE)=60
VAL(Prenom, ARTISTE)=40
VAL(Natio, ARTISTE)=20
VAL(TitreA, ALBUM)=100
VAL(Label, ALBUM)=3
VAL(IDA, CONTRIBUTION)=60
CARD(ALBUM)=100
CARD(ARTISTE)= 60
VAL(NomI, INSTRUMENT)=15
VAL(NomA, ARTISTE)=55
VAL(DNaiss, ARTISTE)=60
VAL(IDD, ALBUM)=100
VAL(AParution, ALBUM)=10
VAL(IDD, CONTRIBUTION)=100
VAL(IDI, CONTRIBUTION)=15
On consid`ere la requˆete suivante : on cherche les artistes ayant particip´e `a un ou plusieurs
albums ´edit´es chez le label Blue note (Label=’Blue Note’) en 2010 (AParution=’2010’) en tant que
percussionniste (NomI=’Percussion’). Donner pour chaque artiste : son nom, son pr´enom et le titre
de l’album.
– Combien d’arbres sont g´en´er´es `
a l’issue de la phase d’optimisation logique?
– Donner l’arbre optimal dont l’ordre de jointure est l’inverse de l’ordre dans lequel les tables ont
´et´e d´ecrites dans l’´enonc´e. Par exemple, si les tables INSTRUMENT et CONTRIBUTION
sont n´ecessaires `
a la r´esolution de cette requˆete, la table CONTRIBUTION devra ˆetre la
premi`ere `
a apparaˆıtre dans une jointure et INSTRUMENT la derni`ere.
– Donner une estimation du nombre de tuples de la table r´esultat de la requˆete, r´esultat obtenu
en exploitant l’arbre optimal trouv´e en r´eponse `a la question 2. Justifiez votre r´eponse. Faites
figurer les calculs et r´esultats interm´ediaires directement sur l’arbre trouv´e en r´eponse `a la
question 2.

Download Report