Exercício com Gabarito
Defina no máximo 10 índices para as tabelas abaixo (tipo, atributos, justificativa). Considere
as estatísticas e principais consultas apresentadas a seguir. O contexto é de alimentação
servida em voos em todo o mundo.
Tabelas:
(R) Refeição (cod-ref, nome-ref, cia-aérea, culinária)
(T) Tem (cod-ref, cod-ing, quantidade)
(I) Ingrediente (cod-ing, nome-ing, perecível, unidade)
(P) Preparo (cod-ref, etapa, descrição, duração)
Estatísticas:
10.000 refeições, 2.000 ingredientes, 222 companhias aéreas
Em média uma refeição tem 9 ingredientes e 6 etapas de preparo
R.culinária = Brasileira (1%), Internacional (73%), Chinesa (21%), Vegetariana (5%)
I.perecível = Não (20%), Sim (80%)
Cardinalidade (R.nome-ref) ≈ Cardinalidade (R.cod-ref)
Cardinalidade (I.nome-ing) ≈ Cardinalidade (I.cod-ing)
Principais Consultas:
1. SELECT nome-ref FROM R WHERE cia-aérea = “Mistral” AND cor-ref IN (SELECT cod-ref
FROM T WHERE cod-ing IN (SELECT cod-ing FROM I WHERE perecível = “Não”))
2. SELECT cod-ref, nome-ref, cia-aérea FROM R WHERE cod-ref NOT IN (SELECT cod-ref
from P)
3. SELECT cod-ing, nome-ing FROM I, R, T, P WHERE I.cod-ing = T.cod-ing AND T.cod-ref
= R.cod-ref AND R.cod-ref = P.cod-ref AND cia-aérea = “Minuano” AND culinária =
“Vegetariana” AND perecível = “Sim” AND unidade = “gramas” AND quantidade > 200
AND duração > 10
4. SELECT nome-ref FROM R, P WHERE R.cod-ref = P.cod-ref AND descrição LIKE
‘%fritar%’
p.1
A decisão de usar índices, e eventual escolha do tipo de índice, para cada atributo de uma tabela,
deve levar em consideração (1) a sua utilização e (2) a sua cardinalidade na tabela, que podem ser
observadas nas estatísticas fornecidas.
Uma heurística é que chaves primárias precisam de índices e chaves secundárias também, para
otimizar a junção entre tabelas. Outra é que valores normalmente não são indexados, a não ser que
sejam codificados (ex: faixas de salários, A = 100 a 1.000, etc).
Nos exercícios, testes e provas eu sempre apresentarei, junto com as tabelas, um conjunto de
“principais consultas”. Elas serviram de referência para o projeto de índices. Na prática, a
recomendação é que se busque identificar as transações típicas que utilizam o conjunto de tabelas
alvo do projeto de índices.
Os 3 tipos de índices que apresentei em sala têm vantagens e limitações, que descrevo brevemente
a seguir:
•
Árvore B+ é o “coringa” dos índices, mas nem sempre a melhor escolha. Pode ser usado
para comparações (busca) por igualdade, diferença, maior, menor. Pode ter algumas chaves
repetidas. Não é tão rápido/eficiente quanto o Hashing quando a busca é apenas por
igualdade (o Hashing faz mais contas e menos acessos a disco que a Árvore B+ para
descobrir o endereço físico de uma tupla). Não é tão eficiente quanto o Bitmap no caso do
atributo possuir baixa cardinalidade em comparação com a cardinalidade da tabela
(ex:atributos cores de produtos, 5 cores distintas, 10.000 produtos).
•
Hashing só serve para buscas por igualdade e com atributos com cardinalidade próxima à
cardinalidade da tabela. Um bom exemplo são as chaves primárias e candidatas. Quanto
mais a cardinalidade do atributo for próxima a da tabela, menos colisões haverá no
processamento destes atributos. É melhor que a árvore B+ quando pode ser aplicado (veja
acima).
•
Bitmap ideal para buscas que comparam com “E”, “OU” ou “NÃO” (operadores lógicos)
vários atributos com índices bitmap, pois eles podem ser “logicamente” combinados, mas
também funciona de forma eficiente para buscar por igualdade. Não é adequado caso a
cardinalidade do atributo seja próxima à cardinalidade da tabela (os bitmaps teriam quase
todos os seus bits zerados e uns poucos bits ligados, muito espaço ocupado, baixa
eficiência). É melhor que a árvore B+ quando pode ser aplicado (veja acima).
p.2
Tipo
Atributos
Justificativa
1
Hashing ou
Árvore B+
R.cod-ref
É chave primária, há apenas comparações por igualdade
2
Bitmap
R.cia-aérea
Apenas busca por igualdade (consultas 1 e 3), baixa
cardinalidade relativa (222 em 10.000 refeições)
3
Bitmap
R.culinária
Apenas busca por igualdade (consulta 3), baixíssima
cardinalidade relativa (4 em 10.000 refeições)
4
Árvore B+
T.cod-ref
Comparações por igualdade para junção porém há valores
repetidos na tabela T
5
Árvore B+
T.cod-ing
Comparações por igualdade para junção porém há valores
repetidos na tabela T
6
Hashing ou
Árvore B+
I.cod-ing
É chave primária, há apenas comparações por igualdade
7
Bitmap ou
nada
I.perecível
A cardinalidade relativa é muito baixa (2 em 2000) mas no
caso do valor = “Sim” (consulta 3) é provável que o índice
não seja útil (baixa seletividade, 80%).
8
Bitmap
I.unidade
Não há estatísticas apresentadas, mas pode-se inferir que as
unidades de ingredientes tenham baixa cardinalidade relativa
na tabela I
9
Hashing ou
Árvore B+
P.cod-ref
É chave primária, há apenas comparações por igualdade
10
Obs: não há necessidade de índices para T.quantidade e
O.duração (heurística: não indexar valores) e P.descrição (a
busca é por LIKE com %X% e pode-se inferir que
Cardinalidade (P.descrição) ≈ Cardinalidade (P)
p.3