Exercícios de Banco de Dados II

Prévia do material em texto

Universidade Federal de Lavras 
Departamento de Ciência da Computação 
1
o
 semestre de 2013 
 
 
GCC119 – Banco de Dados II 
Professor Responsável: Leonardo Andrade Ribeiro 
 
 
Lista de Exercícios 2 
 
Considere relações agrupadas em todos exercícios abaixo, exceto quando afirmado 
explicitamente o contrário. 
 
Exercício 1: Considere o pseudocódigo para o iterador (modelo ONC) do operador de 
projeção onde é a lista de atributos a serem projetados e R a relação de 
entrada 
 
//Seja Proj o iterador para a operação de Projeção e Scan é o iterador de 
de entrada associado com Proj (poderia ser quaquer iterador) 
 
Proj.Open(): 
Scan.Open() 
 
Proj.Next(): 
 ; Se , retorne 
 ; //construa uma nova tupla à partir de 
Remova de r os valores associados com os atributos tal que 
Retorne 
 
Proj. Close(): 
Scan.Close() 
 
Baseando-se no exemplo de Proj, apresente implementações em alto-nivel para 
iteradores dos seguintes algoritmos: 
 
a) Seleção onde é a condição da seleção e R a relação de entrada 
 
 
 
b) Equi-Join onde Y são os atributos da junção e R e S as 
relações de entrada 
 
 
 
Exercício 2: Um Semijoin é uma variante da operação junção onde dada duas 
relações R(X,Y) e S(Y,Z), a operação Semijoin(R,S) irá retornar todas as tuplas de 
R para as quais existe pelo menos um tupla de S com o mesmo valor para Y. 
Apresente um algoritmo de Um-Passo para implementar o Semijoin. 
 
 
 
 
 
Exercício 3: Considere uma relação R com B=1000 e assuma M=10. Qual é a 
quantidade de IO necessária para ordenar R usando o TPMMS e escrevendo a 
saída no disco nos seguintes casos: 
 
a) Apenas um buffer é associado com cada run na etapa de Combinação 
b) Quando dois buffers são associados com cada run na etapa de Combinação 
 
 
 
 
 
 
 
 
Exercício 4: Considere duas relação e ; seja e e 
 . Qual é a quantidade de IO realizada pelo Nested-Loop Join para realizar 
a junção entre e ? 
 
 
 
 
 
 
 
 
Exercício 5: Apresente um algoritmo em alto-nível baseado em ordenamento para 
implementar a operação de Uniao 
 
 
 
 
 
 
 
 
Exercício 6: A algoritmo Sort-Merge Join, versão 2, e o Hash-Join possuem o 
mesmo custo em termos de quantidade de IO realizada. Entretanto, existem 
situações onde é mais vantajoso usar um algoritmo do que o outro. Apresente um 
exemplo para cada caso: o Sort-Merge Join é preferível ao Hash-Join, o Hash-Join 
é preferível ao Sort-Merge Join 
 
 
 
 
 
 
 
Exercício 7: Vimos duas estratégias para realização de junções baseadas em 
índices quando apenas existe um índice (uma árvore B) definido sobre apenas uma 
relação (relação interna): 
 
Estratégia 1: realize um scan sobre a relação externa e para tupla retornada faça 
uma consulta ao índice 
Estratégia 2: Execute um IndexScan sobre a relação interna e realize um Sort-
Merge Join 
 
Apresente situações para estes dois casos: Estratégia 1 é preferível à Estratégia 2; 
Estratégia 2 é preferível à Estratégia 1 
 
 
 
 
 
 
 
Exercício 8: Considere duas relações e e as respectivas estatísticas 
 e . Seja . Apresente a quantidade de IO realizada 
pelas duas versões do Sort-Merge Join sobre e . Desconsidere problemas 
relacionados a multiplicidade de valores nos atributos da junção (e.g., os atributos 
da junção são chaves) 
 
 
 
 
 
Exercício 9: Considere as relações , , e e a seguinte 
expressão lógica: . Apresente uma expressão lógica 
equivalente que possa conduzir a um plano físico onde a quantidade de dados 
processados pelas junções seja reduzida. 
 
 
Exercício 10: Considere as ) e as respectivas estatísticas 
 , , . Qual o tamanho do resultado 
junção de e ? 
 
 
 
 
 
 
Exercício 11: Considere as relações ) e as respectivas estatísticas 
 , . Considere os dois histogramas equi-width 
compatíveis abaixo, para R.Y e S.Y, respectivamente. Os parâmetros dos 
histograms são e e o intervalo total dos valores é [ ]. Qual 
o tamanho do resultado da junção entre R e S? 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Exercício 12: Considere duas relações e e e ; 
considere . Apresente o custo da junção de e usando o algoritmo 
Hybrid Hash-Join. Qual a quantidade buckets de usada? 
 
Intervalos R.Y S.Y 
0-99 40 10 
100-199 60 0 
200-299 500 0 
300-399 100 0 
400-499 0 90 
500-599 50 20 
600-699 50 10 
700-799 0 300 
800-899 200 0 
900-999 0 70 
Exercício 13: Considere as estatísticas abaixo e presente as etapas do algoritmo 
baseado em programa dinâmica para encontrar a melhor ordenação para as junções 
de R, S, T e U. 
 
 
𝑹 𝒂 𝒃 𝑺 𝒃 𝒄 𝑻 𝒄 𝒅 𝑼 𝒅 𝒂 
𝑉 𝑅 𝑎 𝑉 𝑈 𝑎 
𝑉 𝑅 𝑏 𝑉 𝑆 𝑏 
 𝑉 𝑆 𝑐 2 𝑉 𝑇 𝑐 
 𝑉 𝑇 𝑑 𝑉 𝑈 𝑑