Lista de Exercícios 1 - respostas

Prévia do material em texto

Lista de Exercícios 1 
 
Arquitetura 
a)Defina independência lógica e física de dados. 
Independência lógica: capacidade de alterar a descrição lógica dos dados (esquema) sem 
interferir com usuários e programas de aplicação (problema em sua maior parte em aberto) 
Independência de dados. 
Independência física: capacidade de alterar a representação física dos dados em meios de 
armazenamento e as técnicas usadas para acessar estes dados sem interferir com usuários e 
programas de aplicação 
 
b) Descreva a arquitetura de SGBDs baseada em 5 camadas, destacando a interação entre 
camadas adjacentes. 
 
c) Quais as vantagens e desvantagens do modelo de processamento paralelo de memória 
compartilhada? 
Vantagens: 
Custo reduzido de administração. 
 
Desvantagens: 
Se falhar um todos param. 
Preço elevado. 
 
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. 
Modelo RAM 
• Assume dados na memória principal 
• Tempo uniforme para acesso a itens de dados 
 
Implementação de SGBDs: dados não “cabem” na memória principal: Modelo I/O 
• Acessos à memória secundária (disco) devem ser considerados 
 
b) Descreva e compare os conceitos de localidade espacial e temporal. 
• Localidade temporal: objetos acessados recentemente são mantidos no buffer 
• Localidade espacial: objetos próximos ao objeto requisitado são mantidos no buffer 
 
c) Discuta as três técnicas vistas em sala para acelerar o acesso a discos magnéticos. 
Uso de Múltiplos Discos 
Usando múltiplos discos com cabeças independentes, é possível, aproximadamente, 
reduzir o tempo de acesso original para / , onde é o número de discos. 
Quando um arquivo armazenado em múltiplos blocos é lido, blocos podem ser acessados 
paralelamente de discos e, com isso, aumentando a taxa de transferência. 
Quando um único bloco é lido, a taxa de transferência é a mesma que a de 1 disco; mesmo 
assim, os − 1 discos restantes estão livres para servirem outras requisições e, com isso, pode-
se obter melhor balanceamento de carga. 
 
Prefetching 
Em certas aplicações, é possível prever a ordem na qual os blocos serão requisitados do disco 
Neste caso, é possível carregar antecipadamente blocos em buffers na memória principal, 
antes que a requisição para acessar estes blocos seja feita pela aplicação 
Vantagens: Melhor exploração de padrões de acesso sequencial 
Desvantagens: Requer buffers extra na memória e nenhum ganho é obtido quando o acesso é 
inerentemente randômico. 
 
“Kill It with Iron” 
Problemas de desempenho causados por acessos randômicos podem ser mitigados através do 
armazenamento de porções do banco de dados em meios de armazenamento mais rápidos. 
 
d) Explique o conceito de RAID 4, destacando a sua principal motivação. Então, 
discuta a desvantagem do RAID 4 que provê a motivação para o RAID 5. 
RAID Nível 4 
RAID 1 é uma maneira efetiva para aumentar significativamente o tempo médio para perda 
de dados. Entretanto, o espelhamento requer um disco redundante para cada disco de dados 
RAID nível 4 requer apenas um disco redundante para uma quantidade qualquer de discos de 
dados. 
 
O cálculo usado para determinar os bits de paridade é soma módulo-2. Usando soma módulo-
2 é possível calcular não apenas o conteúdo do disco redundante, mas também o conteúdo de 
qualquer disco através dos dados dos demais discos. Cálculo usado para recuperação de falhas 
em qq disco. 
 
Em RAID nível 4, toda modificação em blocos dos discos de dados requer uma modificação 
no disco redundante. 
Como resultado, o número médio de escritas disco redundante será aproximadamente vezes 
o número de escritas em um único disco. 
Possível gargalo. 
 
RAID nível 5 explora o fato de que a operação de soma modulo-2 pode ser usada para 
recuperar qualquer disco, de dados ou o disco redundante. 
Cada disco pode desempenhar o papel de disco redundante. 
 
Gerenciamento de Buffer 
a)Descreva a interface FIX e UNFIX e as ações realizadas pela camada C2 para implementar 
estes serviços. 
Método FIX: possui uma página como parâmetro, opcionalmente com um flag sinalizando 
intenção de atualização na página. 
• é localizada, armazenada em um quadro de página, e “fixada“ no buffer para evitar que a 
mesma seja removida do buffer enquanto estiver sendo usada 
• O endereço de memória de é passado para o invocador 
(em C3) do método FIX 
• O invocador pode usar e modificar os elementos de dados 
contidos em 
 
Método UNFIX: Após o término das operações em , o método UNFIX é invocado para deixar 
 disponível para seleção pelo algoritimo de substituição de páginas (mais adiante). 
 
b) Descreva as estratégias de substibuição de páginas LRU e FIFO. 
LRU (Least Recently Used) 
Substitui a página que foi referenciada pela última vez há mais tempo 
Intuição: páginas que não tem sido usada por um bom tempo possuem menos probabilidade 
de serem acessadas novamente. 
O gerenciador de buffer precisa manter uma tabela indicando a última vez que cada página foi 
acessada. 
 
FIFO (First-In-First-Out) 
Seleciona a página que foi carregada do disco para a memória há mais tempo. 
O gerenciador precisa apenas saber o momento que o bloco do disco foi escrito no buffer. 
Como a estratégia FIFO desconsidera referências, páginas altamente referenciadas e que 
estejam no buffer há mais tempo podem ser selecionadas como vítima. Ex.: o nó raiz de uma 
árvore B. 
FIFO é apropriado para padrões de acesso sequencial. Ex.: scan de uma tabela. 
 
c) Discuta a relação entre referências físicas e lógicas de páginas. 
Referências de Página 
Referências de páginas podem ser lógicas ou físicas 
Referências lógicas: realizada por operações em C3 invocando serviços em C2 
 
Referências físicas: realizada por operações em C2 invocando serviços em C1 
• Ocorre quando a página requisitada na referência lógica não se encontra em memória e seu 
conteúdo precisa ser buscado no bloco correspodente. 
• Resulta em acesso ao disco a não ser que os serviços do sistema de arquivos do SO estejam 
sendo usados por C1 e os dados do bloco correspondente se encontrem no cachê. 
• O último caso resulta em uma situação de Double buffering, onde dados estão duplicados no 
buffer do SGBD e no cache do sistema de arquivos, como discutido anteriormente. 
 
d) Apresente as motivações para os chamados SGBD baseados em memória principal e a 
principal diferença com SGBDs tradicionais em relação à estratégia de otimização. 
SGBDs especializados para dados em memória principal podem ser ordens de magnitude mais 
rápidos do SGBDs tradicionais, mesmo quando existe memória suficiente para armazenar todo 
o banco de dados. 
 
Representação de Dados 
a)Explique a operação de swizzling de ponteiros. 
Ponteiros do SGBD não podem ser usados diretamente: é necessário substituir o identificador 
da página pelo endereço de memória do quadro de página correspondente. 
▪ Esta operação é denominada swizzling de ponteiros: conversão de um ponteiro no espaço de 
endereçamento do SGBD em um ponteiro válido no espaço de endereçamento do SO. 
▪ Operação realizadas pela camada C2 (gerenciador de buffer); pode requer acesso à camada 
C1 se a página apontada não estiver em memória. 
 
b) 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. 
 
c) Explique porque a presença de blocos de overflow pode resultar na divergência 
entre ordenação física e lógica de dados. 
Um bloco de overflow será armazenado em posição distante ao bloco original 
▪ Como resultado, podemos ter perda de desempenho em operações acessando sequência 
ordenada de registros 
• Cada acesso a um bloco de overflow pode resultar em um acesso randômico ao disco 
 
d) Descreva as principais características da estratégia de armazenamento orientado a 
colunas. 
Uma estratégia popular é o armazenamento orientado a colunas, onde os valores de cada 
coluna (ou atributos) são armazenados de maneira contíguaem páginas do disco. 
 
▪ Compressão: armazenamento orientado a colunas permite maior eficiência em compressão 
de dados que armazenamento orientado a registros. 
• Permite maior economia em largura de banda de discos 
• Motivação: tempo transmissão de dados comprimidos pelo barramento + descompressão 
posterior < transmissão de dados não comprimidos. 
▪ Paralelismo: quando os dados já estão em memória principal, armazenamento orientado a 
colunas permite explorar o paralelismo presente em processadores modernos baseados em 
arquitetura SIMD (single instruction multiple data). 
▪ Ordenação: múltiplas cópias de uma coluna podem ser armazenadas em diferentes ordens 
para acelerar processamento de consultas. 
 
 
 
Índices/Árvores B 
a) Compare os seguintes tipos de índices, incluindo aspectos do processamento de 
consultas na discussão: 
a.Índices densos vs. índices esparsos 
Índices densos: índices que possuem uma entrada no arquivo de índices para cada registro 
do arquivo de dados. 
 
Índices esparsos: índices que possuem uma entrada no arquivo de índices para cada bloco do 
arquivo de dados. 
 
b. Índices primários vs. índices secundários 
Índices primários: índices cuja chave de busca define a ordem do arquivo sequencial. 
• Índices agrupados (clustering indexes): definição alternativa para índices agrupados. 
 
Índices secundários: índices cuja chave de busca define uma ordem diferente da ordem do 
arquivo sequencial. 
• Índices não agrupados (nonclustering indexes): definição alternativa para índices secundários 
 
c. Índices secundários simples vs. índices compostos 
Índices simples: índices definidos sobre apenas um campo do arquivo indexado 
Índices compostos: índices definidos sobre mais de um campo do arquivo indexado 
 
B) 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 = ‘Goiânia‘ 
 
C) Apresente uma situação na qual o SGBD pode optar por não usar um índice elegível para 
executar uma consulta. 
Se o índice for secundário e for preciso acessar mais que 25%, ele fará logo uma busca no 
arquivo de página, uma varredura completa. 
 
A) O comando CREATE INDEX em SQL para criação de índices 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? 
 
B) Considere um arquivo sequencial de 107 registros e uma árvore B de ordem 30 definida 
sobre este arquivo. No pior caso, qual é a quantidade máxima de IO realizada por uma 
operação de busca? 
 
C) Descreva as alternativas para layout de nós-folha em uma árvore B+.