Aulas práticas - Ficha 12 (com resolução dada)

Bases de Dados (CC2005), Dep. Ciência de Computadores, FCUP

Eduardo R. B. Marques, DCC/FCUP

Objectivos: Exercícios sobre organização física de dados.

Referências: Organização física dos dados ("slides" das aulas teóricas)

Sumário de noções básicas

Assumiremos nesta aula armazenamento de registos em ficheiro tal que o tamanho de cada registo é fixo com tamanho \(R\) e com tamanho igual ou inferior a \(B\) a dimensão de um bloco de disco em bytes.

Notação Significado
\(B\) tamanho de um bloco em disco em bytes
\(N\) nº de registos em um ficheiro
\(R\) tamanho de um registo em bytes
\(bfr = \lfloor\: B \:/ \:R \: \rfloor\) "blocking factor": nº de registos por bloco
\(n = \lceil\: N \:/\: bfr \:\rceil \) nº de blocos em disco ocupados pelo ficheiro

Em todos os exercícios assuma \(B=4096\) bytes (tamanho de um bloco em disco).

Tabela de valores logarítmicos

\(x \in\: ]2^{k-1},2^k]\) \(k = \lceil {\rm log}_2(x) \rceil\)
\(]1,2]\) \(1\)
\(]2,4]\) \(2\)
\(]4,8]\) \(3\)
\(]8,16]\) \(4\)
\(]16,32]\) \(5\)
\(]32,64]\) \(6\)
\(]64,128]\) \(7\)
\(]128,256]\) \(8\)
\(]256,512]\) \(9\)
\(]512,1024]\) \(10\)
\(]1024,2048]\) \(11\)
\(]2048,4096]\) \(12\)
\(]4096,8192]\) \(13\)
\(]8192,16384]\) \(14\)

1. Ficheiros de tabelas

Considere o armazenamento de duas tabelas \(T_1\) e \(T_2\) com a seguinte caracterização:

\[T_1: \quad N = 10,000 \quad R = 32 \]

\[T_2: \quad N = 100,000 \quad R = 130 \]

Para cada um dos casos:

  1. Calcule o "blocking factor" \(bfr\), nº de bytes não usados por bloco \(B - bfr \times R\), e nº de blocos \(n\) necessários a guardar os dados da tabela em disco.

  2. Suponha que os ficheiros de \(T_1\) e \(T_2\) estão ordenados pelos valores dos atributos que constituem a chave primária de cada tabela. Quantos acessos a blocos de disco no máximo precisamos de aceder para localizar um registo a partir de um valor da chave primária nos dois casos? E no caso de a pesquisa ser baseada no valor de um outro atributo?

Resolução

Caracterização:

\( B = 4096 \)

\(T_1: \quad N = 10,000 \quad R = 32 \)

\(T_2: \quad N = 100,000 \quad R = 130 \)

1.1

\(T_1: \quad bfr = \lfloor 4096/32 \rfloor = 128 \quad B - bfr * R = 0 \quad n = \lceil 10000 \:/\: 128 \rceil = 79 \)

\(T_2: \quad bfr = \lfloor 4096/130\rfloor = 31 \quad B - bfr * R = 66 \quad n = \lceil 100000 \:/\: 31 \rceil = 3226 \)

1.2

Para \(T_1\): \( \lceil log_2(79) \rceil = 7\) pela chave primária, por outro atributo \(n = 79\).

Para \(T_2\): \( \lceil log_2(3226) \rceil = 12\) pela chave primária, por outro atributo \(n = 3226\).

2. Índices primários

Considere a construção de índices primários para tabelas cujos ficheiros são ordenados pelos atributos de chave primária nos seguintes dois casos:

Assumindo também que referências para blocos em disco têm um tamanho de \(8\) bytes, calcule em cada caso:

Resolução:

3. Índices sobre chaves secundárias

Considere uma tabela contendo \(N = 25,000\) registos armazenados em \(n = 400\) blocos de disco.

Repita a análise do exercício anterior, mas para um índice sobre uma chave secundária com tamanho de \(8\) bytes e considerando de novo que referências para blocos em disco ocupam \(8\) bytes.

Resolução

Temos

\( N_I = N = 25000 \quad R_I = 8 + 8 = 16 \quad bfr_I = \lfloor 4096 / 16\rfloor = 256 \quad n_I = \lceil 25000 / 256 \rceil = 98 \)

portanto precisamos de \(8=\lceil log_2(98)\rceil +1\) acessos a disco no máximo vs. \(n=400\) numa pesquisa linear usando a chave secundária.

4. Índices multi-nível

Considere uma tabela \(T\) ocupando \(n=256,000\) blocos em disco e com tamanho de \(8\) bytes para um valor da chave primária.

Assuma que apontadores para blocos em disco tomam \(8\) bytes e considere um índice primário de 1º nível, e ainda um de 2º nível sobre este. Quantos blocos em disco seriam adicionalmente necessários em cada nível e qual seria a melhoria de desempenho no acesso a disco usando o índice multi-nível resultante?

Resolução

Sem índice

Acesso:

\( \lceil log_2(256,000) \rceil = 18 \)

Nível 1

\( N_I^1 = n = 256,000 \quad R_I^1 = 8 + 8 = 16 \quad bfr_I^1 = \lfloor 4096 / 16\rfloor = 256 \quad n_I^1 = \lceil 256,000 / 256 \rceil = 1,000 \)

1,000 blocos em disco

Acesso:

\( \lceil log_2(1,000) \rceil + 1 = 11 \)

Nível 2

\( N_{I}^2 = n_I^1 = 1,000 \quad R_I^2 = R_I^1 = 16 \quad bfr_I^2 = bfr_I^1 = 256 \quad n_I^2 = \lceil 1,000 / 256 \rceil = 4 \)

4 blocos em disco

Acesso:

\( log_2(4) + 2 = 4 \)