Exercícios
Estruturas de indexação e algoritmos de processamento de consultas
Considere a seguinte relação Aluno:
codAluno
1
2
3
4
5
6
7
8
9
10
11
12
...
1000
nome
Ana
Paulo
José
Maria
Marcos
Mariana
Juliana
Eduardo
Ronaldo
Carlos
Pedro
Sérgio
cidade
POA
Gravataí
POA
Canoas
Canoas
POA
Canoas
POA
Viamão
Viamão
Gravataí
POA
codCurso
1
1
2
4
6
4
7
9
11
4
7
7
renda
1300.50
2641.56
1300.50
2300.54
2300.57
3300.88
2300.98
4305.38
3137.38
2360.28
2370.88
1360.98
Vando
POA
5
1500.52
Estruturas básicas de indexação. Considere as situações:
1. Supondo que o arquivo físico de dados está ordenado pelo campo chave codAluno.
i. Dos tipos de índices vistos até o momento, qual tipo poderia ser criado para este campo (primário,
secundário, clustering)? Esparso ou denso? Justifique.
ii. Qual seria o arquivo de índices correspondente a este campo, considerando um índice primário esparso
com 10 entradas?
2.
Supondo que um bloco armazene 10 tuplas do arquivo de dados da relação Alunos.
i. Quais acessos/operações de acessos seriam feitos para selecionar a tupla do aluno de código 214,
supondo um índice esparso primário na coluna codAluno, com 10 entradas no arquivo de índices,
supondo que o arquivo de índices aponta para o primeiro registro do bloco? Uma vez localizado o
bloco, como poderia ser feita a busca do registro dentro do bloco?
3.
Supondo que o arquivo físico de dados está ordenado pelo campo cidade.
i. Dos tipos de índices vistos até o momento, qual tipo poderia ser criado para este campo (primário,
secundário, clustering)? Esparso ou denso? Justifique.
ii. Qual seria o arquivo de índices correspondente a este campo, considerando um índice esparso com 10
entradas?
iii. Qual seria o arquivo de índices correspondente a este campo, considerando um índice denso? Quantas
entradas existiriam no arquivo de índices?
iv. Supondo que um bloco armazene 5 tuplas do arquivo de dados da relação Alunos. Considere que existe
um índice clustering esparso na coluna cidade.
1. Quais acessos/operações de acesso seriam feitos para selecionar as tuplas dos alunos que
moram em POA, supondo que o arquivo de índices aponta para o primeiro registro do bloco
que contém a informação pesquisada? (considere que o grupo de registros que compartilham
diferentes valores de clustering podem estar no mesmo bloco – ver slide 13)
2. Quais acessos/operações de acesso seriam feitos para selecionar as tuplas dos alunos que
moram em POA, supondo que o arquivo de índices aponta para o primeiro registro do bloco
que contém a informação pesquisada? (considere que o grupo de registros que compartilham o
mesmo valor de clustering podem estar em blocos separados – ver slide 14)
4. Algoritmos de seleção. Considere as seguintes operações:
(OP1): σ codAluno=10 (ALUNO)
(OP2): σ codCurso>5 (ALUNO)
(OP3): σ cidade=’POA’ (ALUNO)
(OP4): σ codAluno>=5 AND renda>2000 AND cidade=‘Gravatai’ (ALUNO)
(OP5): σ codAluno>10 (ALUNO)
Suponha as seguintes situações:
i. Não existe índice em nenhum campo no arquivo de dados e o arquivo físico de dados está ordenado
pelo campo codAluno.
1. Qual algoritmo de seleção você utilizaria para executar a OP1?
ii. Não existe índice em nenhum campo no arquivo de dados e o arquivo físico de dados está ordenado
pelo campo codAluno.
1. Qual algoritmo de seleção você utilizaria para executar a OP3?
iii. O arquivo físico de dados está ordenado pelo campo chave codAluno; existe um índice primário
esparso na coluna codAluno, com 10 entradas no arquivo de índices.
1. Quais algoritmos você poderia utilizar para executar a OP1?
iv. O arquivo físico de dados está ordenado pelo campo cidade; existe um índice cluster denso na coluna
cidade.
1. Quais algoritmos você poderia utilizar para executar a OP3?
v. O arquivo físico de dados está ordenado pelo campo codCurso; existe um índice clustering esparso na
coluna codCurso.
1. Quais algoritmos você poderia utilizar para executar a OP2?
vi. O arquivo físico de dados está ordenado pelo campo codAluno; existe um índice primário esparso na
coluna codAluno; existe um índice secundário na coluna cidade;
1. Quais algoritmos você poderia utilizar para executar a OP4?
5.
Algoritmos de junção.
Considere a seguinte relação Curso:
codCurso
1
2
3
4
5
6
7
8
9
10
11
12
...
50
descricao
Ciência da computação
Sistemas de Informação
Medicina
Odontologia
Biologia
Contábeis
Economia
Direito
Engenharia Civil
Engenharia Elétrica
Desenho Industrial
Fisioterapia
reprDiscente
1
3
99
4
1000
5
7
88
8
67
9
34
Vando
23
dataCriacao
..
...
coordenador
...
...
Considere as seguintes operações:
(OP6): ALUNO
(OP7): CURSO
Aluno.codCurso=Curso.codCurso CURSO
curso.ReprDiscente=aluno.CodAluno ALUNO
i. Monte o código do algoritmo para a operação OP6, usando laço aninhado.
ii. Suponha que existe um índice na coluna Curso.codCurso. Para executar a operação 6, rabisque o teste
de mesa usando o algoritmo laço único.
iii. Supondo que os arquivos físicos de dados das relações aluno e curso estão ordenados pelos atributos de
junção. Para executar a operação 6, rabisque o teste de mesa usando o algoritmo ordenação-fusão.
6. Algoritmos de projeção. Considere as seguintes operações:
(OP8): π codAluno, nomeAluno (ALUNO)
(OP9): π nomeAluno(σcidade = ‘POA’ (ALUNO))
i. Quais os possíveis algoritmos para executar a operação OP8?
ii. Suponha que existe um índice clustering na coluna cidade e o arquivo de dados está fisicamente
ordenado pelo campo cidade. Quais os possíveis algoritmos para executar a operação OP9?
7.
Considere a seguinte operação:
(OP10): π nomeAluno, descricao (σcidade = ‘POA’ (ALUNO
aluno.codCurso=Curso.codCurso CURSO))
Suponha que existe um índice primário na coluna Aluno.codAluno e o arquivo de alunos esteja ordenado fisicamente pelo campo
codAluno. Suponha que existe um índice secundário na coluna cidade. Suponha que exista um índice primário na coluna
Curso.CodCurso e o arquivo de cursos esteja ordenado fisicamente pelo campo codCurso. Quais as possíveis combinações de
algoritmos podem ser utilizadas para responder a consulta OP10? (Dica: veja os possíveis algoritmos que podem ser utilizados
para executar cada uma das operações individualmente e depois verifique as combinações possíveis).