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 1 
 
Questão 1: Arquitetura 
 
 
 
a) Defina independência lógica e física de dados. 
 
 
 
 
 
b) Defina o modelo de processos baseado em pool de processos. Quais as 
vantagens deste modelo? 
 
 
 
 
 
c) Quais as vantagens e desvantagens do modelo de processamento paralelo de 
memória compartilhada? 
 
 
 
 
Questão 2: Armazenamento 
 
a) Defina o modelo I/O de computação e contraste o mesmo com o modelo de 
computação baseado em memória RAM. 
 
 
 
 
 
 
 
 
b) Assuma um disco com apenas 20 cilindros e que o tempo de busca em uma 
unidade de tempo ( ) qualquer é equivalente a quantidade de cilindros 
percorridos. Ex.: um movimento do cilindro até o cilindro gasta 
unidades de tempo. Além disso, vamos assumir que a latência de rotação e o 
tempo de transferência consomem conjuntamente 4 ‘s e que a cabeça 
encontra-se posicionada sobre o segundo cilindro. 
 
Cinlindro Requisitado Tempo de chegada da requisição 
2 0 
7 0 
6 8 
32 10 
18 10 
8 20 
 
Considere a tabela acima com os tempos de chegadas de seis requisições. 
Apresente o tempo de completude de cada requisição usando o algoritmo do 
elevador para escalonamento de acessos ao disco. 
 
 
 
 
c) Considere um esquema RAID 4 com três discos de dados e um disco 
redundante. Por simplicidade assuma que cada disco contém apenas um bloco e 
que cada bloco armazena apenas 1 byte. 
 
i. Dado o conteúdo dos três discos abaixo apresente o conteúdo do disco 
redundante. 
 
Disco 1: 00110010 
Disco 2: 11101100 
Disco 3: 00101010 
 
 
ii. Apresente o novo conteúdo do disco redundante quando o conteúdo do 
disco Disco 2 é modificado para 10101111. 
 
Questão 3 – Representação de Dados 
 
a) Rearrange os offsets do registro abaixo para evitar operações de realinhamento 
de posições de memória em arquiteturas de 64 bits. 
 
 
 
 
 
 
b) Explique a operação de swizzling de ponteiros. 
 
c) Apresente uma estratégia para acomodamento de campos de tamanho fixo e 
variável em um registro (de tamanho variável). Justifique esta estratégia. 
 
 
Questão 4 – Gerenciamento de Buffer 
 
a) Explique por que uma mesma string de referência lógica pode resultar em 
diferentes strings de referência física. 
 
b) Considere a string de referência lógica de uma transação abaixo, segmentada 
(conceitualmente) em nas janelas de tempo de tamanho . 
 
 
 
1. Qual é o tamanho do working-set médio de ? 
 
 
2. Em quais janelas de tempo a transação apresenta maior localidade? 
 
 
c) Considere a disposição de quadros de páginas de buffer abaixo. O algoritmo de 
substibuição de página empregado pelo gerenciador de buffer é o CLOCK. Na 
figura, a notação denota que a página possui flag , onde está em . 
Apresente as sequência de (cinco) “vítimas” gerada pelos seguintes eventos: 
 
i. Páginas C, E, e H são referenciadas. 
ii. CLOCK seleciona uma página para substituição. 
iii. Página A, C, D são referenciadas. 
iv. CLOCK seleciona uma página para substituição. 
v. CLOCK seleciona uma página para substituição. 
vi. Página D, G, H são referenciadas. 
vii. CLOCK seleciona uma página para substituição. 
viii. CLOCK seleciona uma página para substituição. 
 
 
 
 
 
 
Questão 5 – Índices/Árvores B 
 
a) Compare os seguintes tipos de índices: 
a. Índices densos vs. índices esparsos 
b. Índices primários vs. índices secundários 
c. Índices secundários simples vs. índices compostos 
 
b) Explique como é realizado o processamento de consultas usando um nível 
adicional de indireção em índices secundários. 
 
 
c) Apresente uma configuração de índices para responder as consultas abaixo: 
 
 
a. SELECT 
 FROM Alunos a 
 WHERE EXISTS (SELECT * 
 FROM Iniciacao_Cientifica ic 
 WHERE a.matr = ic.matr) 
 
b. SELECT dno, count(*) 
FROM Alunos 
GROUP BY dno 
 
c. SELECT * 
 FROM Alunos 
 WHERE aniversario BETWEEN ‘01.01.82‘ AND ‘01.01.92‘ 
 and cidade = ‘Lavras ‘ 
 
 
 
 
d) O comando CREATE INDEX em SQL para criação de indices normalmente 
suporte a opção INCLUDE. Este opção permite especificar atributos adicionais 
para serem armazenados no arquivo de índice embora estes não façam parte da 
chave de busca. Qual seria a utilidade desta opção? 
 
e) Considere um arquivo sequencial de registros e uma árvore de ordem 
30 definida sobre este arquivo. No pior caso, qual é a quantida máxima de IO 
realizada por uma operação de busca? 
 
f) Descreva as alternativas para layout de nós-folha em uma árvore B+ 
 
 
 
Questão 6 – Índices baseados em Hashing 
 
 
a) Faça uma comparação entre: 
 
1. Índices baseados em árvores e indices baseados em hashing; 
 
 
 
2. Tabelas hash estáticas e tabelas hash dinâmicas; 
 
 
 
3. Hashing estendível e hashing linear. 
 
b) Considere a tabela hash abaixo baseada em hashing estendível. Temos , 
 ; para todos blocos, temos . Cada bloco de dados possui espaço para 
dois registros. Apresente a tabela hash resultante após a inserção dos registros 
com hash da chave igual a: 1000, 1011 e 1001. (Note que registros duplicados 
são permitidos). 
 
 
 
 
 
c) Considere a tabela hash abaixo baseada em hashing linear. Os valores para k, i, 
n e r são também apresentados. Cada bloco de dados possui espaço para dois 
registros e ocupação média dos blocos deve ser 85%; portanto, . 
Apresente a tabela hash resultante após a inserção dos registros com hash da 
chave igual a: 1111, 0100 e 0111.