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 1 Exercício 1 Considere um disco com tamanho de setor igaul a 512 bytes, 2000 trilhas por superfície, 50 setores por trilha, cinco pratos de lado duplo e tempo de busca médio de 10mseg. 1. Qual a capacidade de uma trilha em bytes ? 2. Qual a capacidade de cada superficie ? 3. Qual a capacidade do disco ? 4. Quantos cilindros tem o disco ? 5. Dê exemplos de tamanhos válidos de bloco. 256 é um tamanho válido ? 2048 ? 51200 ? 6. Se os pratos do disco rotacionarem a 5400rpm, qual a latência rotacional máxima ? 7. Se uma trilha de dados puder ser transferida por rotação, qual a taxa de transferência (bytes por segundo) ? Exercício 2 Considere novamente as especificações do exercicio anterior. Suponha que o tamanho do bloco é de 1024 bytes. Suponha que um arquivo contendo 100.000 registros de 100 bytes cada deva ser armazenado neste disco e que nenhum registro possa ser espalhado por diferentes blocos. 1. Quantos registros cabem em um bloco ? 2. Quantos blocos são necessários para armazenar o arquivo inteiro ? Se o arquivo estiver organizado sequencialmente em disco, quantas superfícies serão necessárias ? 3. Quantos registros de 100 bytes cada podem ser armazenados neste disco ? 4. Se as páginas forem armazenadas sequencialmente em disco, com a página 1 no bloco 1 da trilha 1, qual página será armazenada no bloco 1 da trilha 1 da próxima superficie de disco ? 5. Quanto tempo é necessário para ler um arquivo de 100.000 registros de 100 bytes cada sequencialmente ? 6. Como sua resposta ao item anterior mudaria caso o disco fosse capaz de ler/gravar de todos os cabeçotes em paralelo (e os dados estivessem organizados de modo ótimo ?) 7. Quanto tempo é necessário para ler um arquivo de 100.000 registros de 100 bytes cada sequencialmente ? Para ler um registro, o bloco contendo o registro tem de ser trazido do disco para o buffer pool. Suponha que a solicitação do bloco incorra no tempo de busca e latência rotacional médios. Exercício 3: Sobre política de substituição de páginas nos frames do buffer pool a) Suponha que o buffer pool tem espaço para 10 páginas. Suponha um arquivo de 10 páginas armazenado no disco, cada página contendo 100.000 registros. Supondo que o arquivo é organizado sequencialmente em disco, quantas vezes cada página será carregada no buffer para uma operação de scan no arquivo, usando a politica de substituição LRU, MRU ou random ? b) Mesma pergunta do item a) supondo que o arquivo contém 11 páginas organizadas de forma sequencial. c) Mesma pergunta do item a) supondo que o arquivo contém 11 páginas organizadas da seguinte maneira no disco: Página 1: contém os registros de identificador N tal que N mod 11 = 1 Página 2: contém os registros de identificador N tal que N mod 11 = 2 ... Página 10: contém os registros de identificador N tal que N mod 11 = 10 Página 11: contém os registros de identificador N tal que N mod 11 = 0 Suponha que cada bloco no disco armazena no máximo 9091 registros. Exercício 4: Considere a situação do exercício 1(c). Responda às seguintes perguntas: a. Encontre uma fórmula que dado o número K da página e a posição P na página, é possivel calcular o identificador N do registro que está na posição P da página K. Exemplo, se K = 1 e P = 3 então N = 23. b. Qual o último registro do bloco 1 ? Qual o último registro do bloco 10 ? E do bloco 11 ? Exercício 5a Considere um arquivo A com 8 páginas, 5 cheias e 3 com espaço livre (1ª página com 8 bytes livre, 2ª página com 10 bytes livres e 3ª página com 12 bytes livres). Suponha que o gerenciador de buffer utilize duas listas duplamente encadeadas para fazer o gerenciamento das páginas do arquivo e que o diretório de arquivos no disco tenha os seguintes dados: Arquivo Header Page A 1000 Descreva passo a passo a operação de inserção de um registro de 10 bytes neste arquivo. Exercício 5b Considere a mesma situação do exercicio anterior, só que desta vez o gerenciador de buffer utiliza um Diretório de Páginas para fazer o gerenciamento das páginas do arquivo. Suponha que o diretório de páginas contenha os seguintes dados: EndPágina 2000 3000 4500 6000 7500 8000 8500 9000 Espaço livre (em bytes) 0 8 0 10 0 12 0 0 Descreva passo a passo a operação de inserção de um registro de 10 bytes neste arquivo. Exercício 6 Considere um arquivo A contendo registros de tamanho VARIÁVEL, cujo gerenciamento dos registros nas páginas é feito através de um diretório de slots. Isto é, cada página armazena, além dos registros de dados, um array (diretório de slots) contendo informações sobre como localizar um registro nesta página, dado o rid deste registro (quando não se tem o rid do registro que se procura, a única maneira de encontrar um registro é fazer uma varredura (scan) da página). Lembre-­‐se que o rid do registro é um par (n,i), onde n = número da página (bloco) onde se encontra o registro e i = número do slot onde se encontra o registro. Suponhamos que o diretório de slots da página 5 é dado abaixo: (-­‐1,_) (702,334) (201,500) (0,200) 1035 4 Slot 2 Número Slot 4 Slot 3 Slot 1 Endereço do inicio total de do espaço slots até o livre momento Pede-­‐se: a) Descreva os passos para a inserção de um novo registro de tamanho 130. Como fica o diretório de slots após esta inserção ? b) Descreva os passos para a inserção de mais um novo registro, de tamanho 180. Como fica o diretório de slots após esta segunda inserção ? c) Descreva os passos para a remoção do registro de rid (5,2) sobre a situação anterior à operação feita no item a. Como fica o diretório de slots após esta remoção ? Exercício 7: Considere o arquivo de dados R(A,B,C,D) A a8 a6 a2 a4 a1 a5 a7 a3 a)
b)
c)
d)
e)
f)
g)
B b4 b3 b2 b1 b1 b2 b4 b3 C c2 c2 c1 c1 c1 c1 c2 c1 D d3 d3 d1 d2 d1 d2 d3 d2 Construa um índice agrupado e denso com chave no atributo C Construa um índice agrupado não-­‐denso com chave no atributo B Construa um índice hash e denso com chave no atributo C e diga se é agrupado. Construa um índice composto, com chave {B,C}. Este índice é denso ? Descreva os detalhes da operação de busca pelo registro (a5,b2,c1,d2) no arquivo R usando o indice do item (a). Descreva os detalhes da operação de busca pelo registro (a5,b2,c1,d2) no arquivo R usando o indice do item (c). Descreva os detalhes da operação de busca pelo registro (a5,b2,c1,d2) no arquivo R usando o indice do item (d). Exercício 8: Considere um arquivo de dados R(A,B,C,D) com 1000 páginas, 100.000 registros de dados por página, tempo de leitura/gravação de uma página de 25msec, tempo de processamento de um registro no buffer de 10 microseg (1 microseg = 1 milionésimo de segundo = 10-­‐6 seg). Suponha que o arquivo esteja organizado de forma sequencial (heap file). O atributo B é a única chave de R. Dê uma estimativa do custo de cada uma das seguintes consultas : d)
e)
f)
g)
h)
i)
j)
Select * From R Select * From R where R.A = a Select * From R where R.A > a Insert into R values (a, b,c,d) Delete from R where R.A = a Delete from R where R.A > a Select * From R where R.B = b Exercício 9 : Considere um arquivo de dados R(A,B,C,D) com 1000 páginas, 100.000 registros de dados por página, tempo de leitura/gravação de uma página de 25msec, tempo de processamento de um registro no buffer de 10 microseg (1 microseg = 1 milionésimo de segundo = 10-­‐6 seg). O atributo B é a única chave de R. Suponha que o arquivo seja ordenado pela chave B. Dê uma estimativa do custo de cada uma das seguintes consultas :
a)
b)
c)
d)
e)
f)
g)
h)
Select * From R
Select * From R where R.B = b
Select * From R where R.B > b
Select * From R where R.A = a
Insert into R values (a,b,c,d)
Delete from R where R.B = b
Delete from R where R.B > b
Select * From R where R.A = a
Resumo: CUSTOS
(SUPONDO SEMPRE QUE A RELAÇÃO ESTÁ ORDENADA PELO ATRIBUTO A)
SCAN = B(D+RC)
Seleção A = a (A é chave candidata da relação) =
(log2B)(D+C) + C (log2R)
Seleção A = a (A não é chave candidata da relação) =
(log2B)(D+C) + C (log2R) + custo médio de ler o resto =
(log2B)(D+C) + C (log2R) + RC/2
Seleção A > a = (log2B)(D+C) + C (log2R) + custo médio de ler o resto =
(log2B)(D+C) + C (log2R) + B/2(D+RC)
Inserção: Sel + Custo médio de atualizar a página onde foi inserido o registro = Sel +
(D+RC/2) = (log2B)(D+C) + C (log2R) + (D+RC/2)
Deleção: Sel + (custo médio de atualizar as páginas onde foram feitas as remoções de
registros)
Atenção : Tanto o custo da operação Sel na deleção quanto o cursto da atualização das
páginas onde foram feitas remoções dependem de como é feita a seleção no comando
DELETE.
Exemplos:
1) Delete FROM R where B = b
(B é chave candidata e R está ordenada por B)
Neste caso o custo da operação Sel é (log2B)(D+C) + C (log2R)
Custo total da operação de remoção =
(log2B)(D+C) + C (log2R) + D + RC/2
2) Delete FROM R where A = a
(A não é chave candidata e R está ordenada por A)
Neste caso o custo da operação Sel é (log2B)(D+C) + C (log2R) + RC/2
Custo total da operação de remoção =
(log2B)(D+C) + C (log2R) + RC/2 + D + RC/2
Observação: Para fins de estimativa de custos, estamos supondo que todos os registros
com A = a cabem em uma página
Exercício 10: Considere um arquivo de dados R(A,B,C,D) com 1000 páginas, 100.000 registros de dados por página, tempo de leitura/gravação de uma página de 25msec, tempo de processamento de um registro no buffer de 10 microseg (1 microseg = 1 milionésimo de segundo = 10-­‐6 seg). Suponha que o arquivo esteja organizado de forma Hash, usando a função h(x) = x mod 5, sendo a chave de busca o atributo A. O atributo A também é chave candidata da relação (a única). O tempo H de cálculo da função h é muito pequeno e pode ser desprezado. Dê uma estimativa do custo de cada uma das seguintes consultas : s) Select * From R t) Select * From R where R.A = a. u) Select * From R where R.A > a. v) Insert into R values (a,b,c,d) w) Delete from R where R.A = a x) Delete from R where R.A > a y) Select * From R where R.B = b. Scan Sel = Sel=nchave Sel <> Insert Delete chave 1,25B(D+RC) H+D+RC 1,25B(D+RC) 1,25B(D+RC) H+2D+RC Sel+D+RC Exercício 11: Considere um arquivo de dados R(A,B,C,D) com 5000 páginas, 100.000 registros de dados por página. O arquivo está ordenado pelo atributo A, que é chave candidata de R. Queremos calcular o custo em termos de operações de I/O de uma operação de busca no arquivo: SELECT * FROM R WHERE R.A = a 1) Quantas operações de I/O são feitas para se encontrar o registro com A = a ? 2) Decide-­‐se construir um indice agrupado com chave A. Suponha que um registro do arquivo de índice ocupar 10% do espaço de um registro completo do arquivo de dados. Pergunta-­‐se: Quantas operações de I/O são feitas para se encontrar o registro com A = a ? 3) Decide-­‐se agora otimizar a estrutura do índice, usando o método ISAM. Os nós internos têm capacidade para 3 registros (incluindo os ponteiros). Além disto decide-­‐se deixar 20% de espaço livre em cada folha. Pergunta-­‐se: a) Quantas folhas tem a estrutura de árvore do índice ? b) Quantos níveis ? c) Quantas operações de I/O são feitas para se encontrar o registro com A = a no arquivo de dados, utilizando-­‐se o indice com a estrutura ISAM ? d) Suponha que o tempo máximo tolerável de operações de I/O é de 100.000. Qual o número mínimo de inserções de registros de dados para que o indice comece a apresentar problemas de performance ? e) Qual o número máximo de inserções de registros de dados que esta estrutura suporta antes de começar a ser totalmente inviável ?