Aulas práticas - Ficha 7

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:

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.
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?

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:

tabela $T_1$ ocupando $n=100$ blocos em disco e com tamanho de $4$ bytes para um valor da chave primária;
tabela $T_2$ ocupando $n=10000$ blocos em disco e com tamanho de $12$ bytes para um valor da chave primária.

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

quantos blocos são necessários para armazenar os índices;
quantos acessos a blocos de disco são no máximo necessários para localizar registos da tabela usando o índice;
quantos acessos em comparação seriam no máximo necessários sem o índice.

3. Índices sobre chaves secundárias

Considere uma tabela contendo $N = 25000$ 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.

4. Índices multi-nível

Considere agora que definimos um índice de segundo nível sobre os índice de primeiro nível do exercício anterior.

Quantos blocos em disco seriam adicionalmente necessários e qual seria a melhoria de desempenho no acesso a disco? Faria sentido um índice de terceiro nível?