Bacharelado em Ciência da Computação – UFU
Disciplina GBC053 – Gerência de Banco de Dados
Profa. Sandra de Amo
Lista dos exercícios feitos em sala de aula – Preparação Prova 3
Exercicio 1. Seja R(A,B,C) relação com 1000 páginas, e um buffer com 41 páginas.
Considere a seguinte consulta:
SELECT R.A, Sum(B)
FROM R
GROUP BY R.A
Pede-se:
a) Estime o custo de I/O desta consulta utilizando a técnica de hash para fazer o
agrupamento. Descreva como é realizado o algoritmo do Group By.
b) Estime o custo de I/O desta consulta utilizando a técnica de ordenação para
fazer o agrupamento. Descreva como é realizado o algoritmo do Group By.
c) Analise os custos comparativos dos dois algoritmos utilizados. O algoritmo
hash é sempre o melhor ?
Exercicio 2. Considere os esquemas relacionais:
Estudante(ENUM, ENOME, Curso, Idade, Periodo)
Aula(DId;DiaSemana,Sala, Horario)
Disciplina(DId,Dnome,PId)
Prof(PId, PNome, Dept)
Matriculado(ENUM,DNome)
Considere a seguinte consulta SQL sobre este banco de dados:
Para cada valor de idade que aparece na tabela Estudante, encontre o período que aparece mais
frequentemente. (Por exemplo, se existe mais alunos com 20 anos cursando o 3o periodo do que
cursando os demais periodos, então o par (20,3) deve ser retornado.)
Um usuário entra o seguinte comando SQL para esta consulta:
SELECT DISTINCT E.Idade, E.Periodo
FROM ESTUDANTE E
GROUP BY E.Idade, E.Periodo
HAVING E.Periodo IN
(SELECT E1.Periodo
FROM ESTUDANTE E1
WHERE E1.Idade = E.Idade
GROUP BY E1.Periodo
HAVING COUNT(*) >= ALL (SELECT COUNT(*)
FROM ESTUDANTE E2
WHERE E1.Idade = E2.Idade
GROUP BY E2.Periodo))
Pede-se:
a) Determinar a sequência de blocos simples SQL produzidos pelo parser do SQL para
este comando SQL entrado pelo usuário.
b) Estime o tamanho da resposta fornecida por cada bloco. Para isto, suponha que a
tabela Estudante tem 1000 páginas, e que não existe nenhum indice no atributo
idade.
Exercicio 3 Diga se é verdadeira ou falsa as equivalências abaixo: em caso de ser
verdadeira, prove. Em caso de ser falsa, dê contra-exemplo ou alguma justificativa
referente ao esquema relacional da expressão:
a) ΠA (R – S) = (ΠA R – ΠAS), onde R(A,B), S(A,B)
b) σA = a( R – S) = (σA = a R - σA = a S), onde R(A,B), S(A,B)
c)
σA = a ( R – S) = (R - σA = a S), onde R(A,B), S(A,B)
d) σA = a ( R – S) = (σA = a R - S), onde R(A,B), S(A,B)
e) σA = a ( R Join S) = (σA = a R Join σA = a S), onde R(A,B), S(A,C), junção é feita pelo
atributo A
f) σA = a ( R Join S) = (σA = a R Join σA = a S), onde R(A,B,C), S(A,C,D), junção é feita
pelo atributo C
g) σA = a ( R Join S) = (σA = a R Join S), onde R(A,B,C), S(A,C,D), junção é feita pelo
atributo C
h) ΠABC (R Join S) = (ΠAB R Join ΠAC S), onde R(ABD), S(ACE), atributo de junção =A
i) ΠBC (R Join S) = (ΠB R Join ΠC S), onde R(ABD), S(ACE), atributo de junção =A
j) ΠBC (R Join S) = ΠBC (ΠAB R Join ΠAC S), onde R(ABD), S(ACE), atributo de junção =A
Exercicio 4 Suponha as seguintes informações armazenadas sobre as tabelas R(A,B,C) e S(A,D,E) no
catálogo:
NTuples (R) = 100000
NPages(R) = 1000
Ntuples(S) = 50.000
Npages(S) = 500
Suponha que existam dois índices já criados na tabela R: I e H. O índice I é do tipo B-Tree, com chave A e
o índice H é hash sobre o atributo B. As seguintes estatísticas estão armazenadas no momento no
catálogo referentes a estes índices:
NKeys(I) = 20
Nkeys (H) = 10
INPages(I) = 200
INPages (H) = 50
IHeight(I) = 4
ILow(I) = 10
IHigh(I) = 250
Calcule o tamanho das respostas das seguintes consultas:
a) SELECT *
FROM R
WHERE R.A = 10
b) SELECT *
FROM R
WHERE R.A = 10 AND R.B = 30
c) SELECT *
FROM R
WHERE R.A = 10 OR R.B = 30
d) SELECT *
FROM R,S
WHERE R.A = S.A AND R.C = 10
e) SELECT *
FROM R,S
WHERE R.A = S.A OR R.C = 10
e) SELECT S.D, S.E
FROM R , S
WHERE R.A = S.A AND R.C = 10
Exercicio 5. Suponha uma relação R(A,B,C) com 100 tuplas, sendo que o valor do
atributo A varia de 1 a 98. As tabelas abaixo descrevem para cada valor do atributo A
(coluna à esquerda) o número de tuplas de R possuindo este valor do atributo A
(coluna à direita).
Vlr
N.Tup
Vlr
N.Tup
1
3
58
2
4
10 60
7
6
4
63
3
10
3
65
4
22
8
76
3
31
9
78
7
35
2
80
2
43
5
84
4
47
7
93
3
53
8
98
6
Pede-se:
1. Descrever uma distribuição uniforme para estes dados.
2. Fazer um histograma por largura .
3. Estimar o número de tuplas com valores > 30, supondo uma distribuição
uniforme
4. Estimar o número de tuplas com valores > 30, supondo uma distribuição de
acordo com o histograma por largura.
Exercício 6. Considere os mesmos dados do exercício anterior.
Pede-se:
1. Fazer um histograma por profundidade .
2. Estimar o número de tuplas com valores > 30, supondo uma distribuição de
acordo com o histograma por largura.
3. Qual a melhor estimativa ?
Exercicio 7. Considere os mesmos dados do exercicios anterior.
1. Suponha que o SGBD mantenha um histograma comprimido, mantendo um
contador para os valores mais frequentes que são 4 e 31, e utilizando um
histograma em largura para os demais valores. Fazer o histograma em
profundidade, neste caso.
2. Estimar o número de tuplas com valores > 30, supondo os contadores para os
valores 4 e 31 e o historgrama por profundidade feito no item anterior.
3. Compare o resultado com as estimativas dos exercicios anteriores e diga qual
seria a melhor estimativa a seu ver.
Cálculo de Custos de Planos de
Execução
Exercício – AULA 27 –
26/03/2013
Bacharelado em Ciência da Computação – UFU
Disciplina GBC053 – Gerência de Banco de Dados
Profa. Sandra de Amo
Exercício1 :
Calcule o custo deste plano
Π sname
On-the-fly
R : 1000 páginas
σ bid=100 and rating > 5
S : 500 páginas
R: 100 tuplas por página
S: 80 tuplas por página
Simple Nested Loops página a página
sid=sid
Reservas
(scan)
Sailors
(scan)
Tabela externa
“Empurrando” seleções para baixo na
árvore de execução
Exercicio 2:
Calcule o custo deste plano
Π sname
Número de valores para bid = 100
sid=sid Sorte-Merge Join
Numero de páginas no buffer = 5
σ
σ rating > 5
Reservas
(scan)
Scan, write to Temp2
Sailors
(scan)
Tabela externa
Tabela interna
“Empurrando” projeções para baixo na
árvore de execução
Π sname
Rating varia de 1 a 10
Uniformemente distribuídos
Número de páginas no buffer = 5
Scan, write to Temp1
Rating varia de 1 a 10
Uniformemente distribuidos
sid=sid Block Nested Looping Join
sid=sid Block Nested Looping Join
Π sid,sname
σ bid=100
σ rating > 5
Tabela externa
σ
σ rating > 5
bid=100
Reservas
(scan)
Scan, write to Temp2
Sailors
(scan)
Tabela externa
Tabela interna
Nem sempre “empurrar seleções
abaixo do join é vantajoso”
Π sname
On-the-fly
Número de valores para bid = 100
Π sid
Reservas
(scan)
Scan, write to Temp1
Exercício 5 :
Calcule o custo deste plano
On-the-fly
Número de valores para bid = 100
On-the-fly
On-the-fly
Numero de páginas no buffer = 5
bid=100
Exercicio 4 :
Calcule o custo deste plano
Π sname
Número de valores para bid = 100
Rating varia de 1 a 10
Uniformemente distribuidos
Scan, write to Temp1
Tabela interna
“Empurrando” seleções para baixo na
árvore de execução
Exercicio 3 :
Calcule o custo deste plano
On-the-fly
On-the-fly
Rating varia de 1 a 10
Uniformemente distribuídos
Número de páginas no buffer = 5
σ rating > 5
On-the-fly
sid=sid
Scan, write to Temp2
Sailors
(scan)
On-the-fly
σbid=100
(tem índice hash em bid, Reservas
agrupado e estático)
Tabela externa
On-the-fly
Index Nested Loops com pipeline
Sailors (tem índice hash em sid, não
necessariamente agrupado)
Tabela interna
Tabela interna
1
Nem sempre execuções em pipeline são
mais vantajosas que as materializadas
Exercício 6 :
Calcule o custo deste plano
•Número de valores para bid = 100
•Rating varia de 1 a 10
uniformemente distribuídos
• Número de páginas no buffer = 5
• Todos os marinheiros fizeram reservas
de barcos.
• Reservas distribuidas uniformemente
entre os marinheiros.
• Todos os barcos foram reservados um
mesmo número de vezes
Scan, write to Temp
ordena por sid
Π sname
On-the-fly
σ rating > 5
sid=sid
σbid=100
(tem índice hash em bid, Reservas
agrupado e estático)
Tabela externa
On-the-fly
Index Nested Loops
Seleção por atributo chave “empurrada” abaixo
do Join é muito vantajosa.
Exercício 7 :
Calcule o custo deste plano
•Número de valores para bid = 100
•Rating varia de 1 a 10
uniformemente distribuídos
• Número de páginas no buffer = 5
• Todos os marinheiros fizeram reservas
de barcos.
• Reservas distribuidas uniformemente
entre os marinheiros.
• (bid,day) é chave de Reservas
On-the-fly
Sailors (tem índice hash em sid)
Tabela interna
Π sname
On-the-fly
σ rating > 5
sid=sid
On-the-fly
Index Nested Loops com pipeline
σday = 09/09/82
Sailors (tem índice hash em sid)
On-the-fly
σ
(tem índice hash em bid,
agrupado e estático)
Reservas
bid=100
Tabela externa
Tabela interna
Compare com o custo do plano
do exercicio 1.
2
Exercicio 15 . Suponha relações R(A,B,C) com 5000 páginas de 200 tuplas cada,
S(A,D) com 2000 páginas de 100 tuplas cada.
•
•
•
•
A é chave de S
S tem indice hash em D, e indice hash em A
R tem índice B-Tree em B
O sistema mantém um histograma em profundidade para os valores do
atributo B de R. Os valores de B variam de 1 a 10.
o Faixa [1-2] = 198000 tuplas
o Faixa [3-5] = 202.000 tuplas
o Faixa [6-7] = 200.000 tuplas
o Faixa [8] = 200.000 tuplas
o Faixa [9-10] = 200.000 tuplas
•
O sistema não mantém histogramas para os valores dos atributos da relação S
Pede-se:
1. Propor um plano de execução que julgue otimal para a seguinte consulta SQL, e
calcule seu custo I/O. Justifique por que você acha que este plano é otimal
SELECT R.C
FROM R, S
WHERE R.B > 7 AND S.D = d AND S.A = R.A
2. Na aula de revisão de 06/04/2013 foram propostos pelos alunos dois planos
de execução (plano A e plano B), descritos nas figuras abaixo. Qual destes
planos é o melhor ? Responda à questão, calculando os custos de I/O de cada
um dos planos.
3. Responda às questões propostas no quadro do PLANO A.
A Typical Query Optimizer
153
SELECT S.sname, P.pname
FROM
Suppliers S, Parts P, Supply Y
WHERE S.sid = Y.sid AND Y.pid = P.pid AND
S.city = ‘Madison’ AND P.price ≤ 1,000
1. What information about these relations does the query optimizer need to select a
good query execution plan for the given query?
2. How many different join orders, assuming that cross-products are disallowed, does
a System R style query optimizer consider when deciding how to process the given
query? List each of these join orders.
3. What indexes might be of help in processing this query? Explain briefly.
4. How does adding DISTINCT to the SELECT clause affect the plans produced?
5. How does adding ORDER BY sname to the query affect the plans produced?
6. How does adding GROUP BY sname to the query affect the plans produced?
Answer 15.8 Answer omitted.
Exercise 15.9 Consider the following scenario:
Emp(eid: integer, sal: integer, age: real, did: integer)
Dept(did: integer, projid: integer, budget: real, status: char(10))
Proj(projid: integer, code: integer, report: varchar)
Assume that each Emp record is 20 bytes long, each Dept record is 40 bytes long, and
each Proj record is 2000 bytes long on average. There are 20,000 tuples in Emp, 5000
tuples in Dept (note that did is not a key), and 1000 tuples in Proj. Each department,
identified by did, has 10 projects on average. The file system supports 4000 byte pages,
and 12 buffer pages are available. All following questions are based on this information.
You can assume uniform distribution of values. State any additional assumptions. The
cost metric to use is the number of page I/Os. Ignore the cost of writing out the final
result.
1. Consider the following two queries: “Find all employees with age = 30” and
“Find all projects with code = 20.” Assume that the number of qualifying tuples
is the same in each case. If you are building indexes on the selected attributes to
speed up these queries, for which query is a clustered index (in comparison to an
unclustered index) more important?
2. Consider the following query: “Find all employees with age > 30.” Assume that
there is an unclustered index on age. Let the number of qualifying tuples be N .
For what values of N is a sequential scan cheaper than using the index?
154
Chapter 15
3. Consider the following query:
SELECT *
FROM
Emp E, Dept D
WHERE E.did=D.did
(a) Suppose that there is a clustered hash index on did on Emp. List all the
plans that are considered and identify the plan with the lowest estimated
cost.
(b) Assume that both relations are sorted on the join column. List all the plans
that are considered and show the plan with the lowest estimated cost.
(c) Suppose that there is a clustered B+ tree index on did on Emp and Dept is
sorted on did. List all the plans that are considered and identify the plan
with the lowest estimated cost.
4. Consider the following query:
SELECT
FROM
WHERE
GROUP BY
D.did, COUNT(*)
Dept D, Proj P
D.projid=P.projid
D.did
(a) Suppose that no indexes are available. Show the plan with the lowest estimated cost.
(b) If there is a hash index on P.projid what is the plan with lowest estimated
cost?
(c) If there is a hash index on D.projid what is the plan with lowest estimated
cost?
(d) If there is a hash index on D.projid and P.projid what is the plan with lowest
estimated cost?
(e) Suppose that there is a clustered B+ tree index on D.did and a hash index
on P.projid. Show the plan with the lowest estimated cost.
(f) Suppose that there is a clustered B+ tree index on D.did, a hash index
on D.projid, and a hash index on P.projid. Show the plan with the lowest
estimated cost.
(g) Suppose that there is a clustered B+ tree index on D.did, D.projid and a
hash index on P.projid. Show the plan with the lowest estimated cost.
(h) Suppose that there is a clustered B+ tree index on D.projid, D.did and a
hash index on P.projid. Show the plan with the lowest estimated cost.
5. Consider the following query:
A Typical Query Optimizer
SELECT
FROM
WHERE
GROUP BY
155
D.did, COUNT(*)
Dept D, Proj P
D.projid=P.projid AND D.budget>99000
D.did
Assume that department budgets are uniformly distributed in the range 0 to
100,000.
(a) Show the plan with lowest estimated cost if no indexes are available.
(b) If there is a hash index on P.projid show the plan with lowest estimated cost.
(c) If there is a hash index on D.budget show the plan with lowest estimated
cost.
(d) If there is a hash index on D.projid and D.budget show the plan with lowest
estimated cost.
(e) Suppose that there is a clustered B+ tree index on D.did,D.budget and a
hash index on P.projid. Show the plan with the lowest estimated cost.
(f) Suppose there is a clustered B+ tree index on D.did, a hash index on D.budget,
and a hash index on P.projid. Show the plan with the lowest estimated cost.
(g) Suppose there is a clustered B+ tree index on D.did, D.budget, D.projid
and a hash index on P.projid. Show the plan with the lowest estimated cost.
(h) Suppose there is a clustered B+ tree index on D.did, D.projid, D.budget
and a hash index on P.projid. Show the plan with the lowest estimated cost.
6. Consider the following query:
SELECT E.eid, D.did, P.projid
FROM
Emp E, Dept D, Proj P
WHERE E.sal=50,000 AND D.budget>20,000
E.did=D.did AND D.projid=P.projid
Assume that employee salaries are uniformly distributed in the range 10,009 to
110,008 and that project budgets are uniformly distributed in the range 10,000 to
30,000. There is a clustered index on sal for Emp, a clustered index on did for
Dept, and a clustered index on projid for Proj.
(a) List all the one-relation, two-relation, and three-relation subplans considered
in optimizing this query.
(b) Show the plan with the lowest estimated cost for this query.
(c) If the index on Proj were unclustered, would the cost of the preceding plan
change substantially? What if the index on Emp or on Dept were unclustered?