Departamento
de
Engenharia
Informática
2009/2010
Administração
e
Optimização
de
BDs
2º
semestre
Mini‐Projecto
2
–
Entrega
a
16
de
Abril
de
2010
A
resolução
deve
ser
claramente
identificada
com
o
número
de
grupo
e
entregue
sob
a
forma
de
um
relatório
impresso,
seguindo
o
template
dado
na
página
da
cadeira.
A
entrega
electrónica
deve
incluir
o
código
Java
com
a
solução
das
perguntas
4
e
5.
1. Considere
que
numa
BD
relacional
existem
as
seguintes
três
relações:
Disciplinas (CodigoDisciplina, NomeDisciplina, NomeCampus, Creditos)
Professores (CodigoProfessor, Nome, CodigoDisciplina)
Campus (NomeCampus, Morada)
Em
cada
uma
das
relações
apresentadas,
as
chaves
primárias
são
os
atributos
CodigoDisciplina,
CodigoProfessor
e
NomeCampus,
respectivamente.
Considere
ainda
que
as
relações
têm
as
seguintes
propriedades:
• A
relação
Disciplinas
contém
120,000
tuplos.
• A
relação
Professores
contém
40,000
tuplos.
• A
relação
Campus
contém
80,000
tuplos.
• Na
relação
Disciplinas,
cada
página
pode
armazenar
um
máximo
de
60
tuplos.
• Na
relação
Professores,
cada
página
pode
armazenar
um
máximo
de
40
tuplos.
• Na
relação
Campus,
cada
página
pode
armazenar
um
máximo
de
80
tuplos.
a. Para
uma
junção
natural
entre
as
tabelas
Professores
e
Disciplinas,
estime
o
número
de
acessos
necessário
à
execução
no
pior
caso
de
cada
um
dos
seguintes
algoritmos
de
junção,
explicando
sempre
os
cálculos
necessários:
i. Merge
join,
assumindo
que
as
duas
relações
não
se
encontram
ordenadas.
ii. Hash
join,
assumindo
que
não
existem
colisões
na
função
de
hash.
iii. Block
nested‐loop
join,
com
a
relação
Disciplinas
como
a
inner
table.
b. Estime
o
tamanho
do
resultado
da
junção
natural
entre
as
três
relações
(Disciplinas
|x|
Professores
|x|
Campus)
e
apresente
uma
estratégia
eficiente
(i.e.
o
plano
de
execução
com
os
algoritmos)
para
o
seu
processamento.
Tenha
em
atenção
o
tamanho
das
relações
e
indique
o
custo
em
termos
de
operações
de
I/O.
Poderá
assumir
a
existência
de
índices
sobre
qualquer
uma
das
3
relações.
2. Considere
a
seguinte
interrogação
sobre
o
esquema
relacional
da
primeira
pergunta:
SELECT P.Nome, D.NomeDisciplina, C.NomeCampus
FROM
Professores P, Discilinas D, Campus C
WHERE D.CodigoDisciplina=P.CodigoDisciplina AND
D.NomeCampus=C.NomeCampus AND
C.NomeCampus=”Alameda” AND D.Creditos>30;
IST/DEI
Pág.
1
de
2
Administração
e
Optimização
de
Bases
de
Dados
Considere
um
optimizador
de
interrogações
semelhante
ao
apresentado
nas
aulas
teóricas.
Assuma
que
a
selectividade
do
predicado
NomeCampus=”Alameda” é
de
um
único
tuplo,
e
que
a
selectividade
do
predicado Creditos>30 corresponde
a
50%
da
relação
Disciplinas.
Com
a
informação
disponível,
e
assumindo
a
existência
de
índices
sempre
que
isso
seja
vantajoso,
indique
um
possível
plano
de
execução
eficiente
para
a
interrogação,
e
indique
os
algoritmos
escolhidos
a
cada
passo.
Justifique
a
sua
escolha
dos
algoritmos
com
os
cálculos
necessários.
3. Considere
as
seguinte
interrogações
sobre
o
esquema
relacional
da
primeira
pergunta:
a. π(CodigoProfessor,Nome)(σCodigoProfessor=10,000
(Professores))
b. σCodigoProfessor>30,000
∧
CodigoProfessor<30,100
(Professores)
c. σ¬(CodigoProfessor=20,000)
(Professores)
d. π(CodigoProfessor,Nome)(σCodigoEmpregado>30,000
(Professores))
e. σ¬(CodigoProfessor<10,000)(Professores)
f. σ¬(CodigoProfessor<40,000)(Professores)
Para
cada
uma
das
interrogações,
indique
qual
o
plano
de
execução
mais
eficiente,
justificando
a
resposta
com
os
cálculos
necessários.
Considere
que
o
atributo
CodigoProfessor
pode
tomar
valores
entre
1
e
40,000.
Considere
ainda
que
existe
um
índice
clustered
B+Tree
sobre
o
atributo
CodigoProfessor,
e
um
índice
non‐clustered
B+Tree
também
sobre
o
atributo
CodigoProfessor,
que
inclui
junto
com
a
chave
de
pesquisa
o
atributo
Nome.
Note
ainda
que,
nas
interrogações
que
envolvem
uma
negação,
o
optimizador
pode
substituir
as
expressões
por
outras
que
lhes
sejam
equivalentes.
4. Tomando
como
base
a
classe
JoinAlgorithmInterface.java,
implemente
o
algoritmo
merge
join.
Na
página
da
cadeira
encontra‐se
o
código
da
classe
abstracta
JoinAlgorithmInterface.java,
assim
como
uma
classe
NestedLoopJoin.java
que
exemplifica
a
sua
extensão
com
uma
implementação
do
algoritmo
nested
loop
join.
5. Tomando
como
base
a
classe
BPlusTree.java,
implemente
o
algoritmo
de
inserção
de
valores
da
estrutura
de
dados
B+Tree.
Na
página
da
cadeira
encontra‐se
o
esqueleto
da
classe
BPlusTree.java,
e
sob
esta
classe
abstracta
deverá
ser
implementado
o
método
insert.
Sugestão
de
implementação
:
Comece
por
encontrar
a
posição
onde
o
valor
deve
ser
inserido.
Verifique
se
a
inserção
envolve
o
split
do
nó
e,
em
caso
afirmativo,
verifique
se
o
mesmo
resulta
no
split
do
nó
antecessor.
Aconselha‐se
a
utilização
de
uma
estrutura
de
dados
que
armazene
a
informação
associada
ao
split.
IST/DEI
Pág.
2
de
2