RESPOSTAS
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.
• Primário: poderia, pois o arquivo está ordenado pelo campo codAluno;
além disso, codAluno é chave primária, e geralmente chaves primárias são
indexadas por índices primários;
• Secundário: não poderia, pois o arquivo precisaria estar ordenado por
outra coluna que não a coluna a ser indexada (codAluno);
• Clustering: não poderia, pois o arquivo precisaria estar ordenado por uma
coluna não chave.
Esparso ou denso: ambos seriam possíveis, embora geralmente utilizem-se
índices esparsos para índices primários. É mais rápido localizar um registro se
tivermos um índice denso do que um índice esparso. Entretanto, os índices
esparsos têm vantagem sobre os densos por exigirem menos espaço e menos
sobrecarga de manutenção para inserções e exclusões.
ii. Qual seria o arquivo de índices correspondente a este campo, considerando um índice
primário esparso com 10 entradas?
valorChave
1
101
201
301
401
501
601
701
801
901
ponteiro
2.
1
101
201
301
401
501
601
701
801
901
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, e 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?
Bloco 1
Bloco
1
valorChave
ponteiro
1
...
...
...
...
2
Bloco 11
3
Bloco 21
4
Bloco 31
5
...
6
7
8
9
10
Bloco 91
Operações/acessos:
1. faça uma busca linear ou binária no arquivo de
índices, buscando pelo valor 214. Como é esparso, o
valor 214 pode não ser encontrado (de fato, não o é,
supondo uma distribuição uniforme nas entradas do
arquivo de índices), então procure o índice menor que
mais se aproxima de 214 (no caso, o 201).
2. acesse o bloco apontado pela entrada 201 (no caso, o
bloco 21)
3. faça uma busca linear ou binária entre o bloco 21
(apontado pela entrada 201) e o bloco 30 (bloco
anterior ao apontado pela entrada 301), procurando
pelo registro correspondente ao código 214
Bloco 2
11 ...
12
13
14
15
16
17
18
19
20
...
...
...
Uma forma tbém utilizada na implementação de índices
primárias esparsos é criar uma entrada no arquivo de
índices para cada valor de codAluno que encabeça um
bloco. Ex: bloco 1 começa com 1, então cria uma entrada
no arquivo de índices com o valor 1; bloco 2 começa com
11, então cria uma entrada no arquivo de índice com o
valor 11; e assim sucessivamente.
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.
• Primário: poderia, pois o arquivo está ordenado pelo campo cidade; no entanto,
índices primários são geralmente criados em colunas chave primária.
• Secundário: não poderia, pois o arquivo precisaria estar ordenado por outra coluna
que não a coluna a ser indexada (cidade);
• Clustering: poderia, pois o arquivo precisa estar ordenado por uma coluna não
chave, e cidade é uma coluna não chave.
Esparso ou denso: ambos seriam possíveis, embora geralmente utilizem-se índices
esparsos para índices clustering. É mais rápido localizar um registro se tivermos um
índice denso do que um índice esparso. Entretanto, os índices esparsos têm vantagem
sobre os densos por exigirem menos espaço e menos sobrecarga de manutenção para
inserções e exclusões.
ii. Qual seria o arquivo de índices correspondente a este campo, considerando um índice
esparso com 10 entradas?
valorChave
Alvorada
Canoas
Gravataí
Guaiba
Novo Hamburgo
Porto Alegre
São Leopoldo
Sapucaia
Triunfo
Viamão
ponteiro
iii. Qual seria o arquivo de índices correspondente a este campo, considerando um índice
denso? Quantas entradas existiriam no arquivo de índices?
valorChave
ponteiro
Alvorada
....
Canoas
....
.....
Gravataí
....
....
Guaiba
.....
Novo Hamburgo
Porto Alegre
São Leopoldo
....
Sapucaia
Triunfo
....
Viamão
Teria tantas entradas quanto fosse o número de cidades distintas
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)
valorChave
Alvorada
Canoas
Gravataí
Guaiba
Novo Hamburgo
Porto Alegre
São Leopoldo
Sapucaia
Triunfo
Viamão
ponteiro
Bloco 1
Alvorada
Alvorada
Alvorada
Alvorada
Alvorada
Bloco 2
Alvorada
...
...
...
...
Canoas
Canoas
Gravataí
Gravataí
Operações/acessos:
1. faça uma busca linear ou binária no arquivo de índices, buscando pelo valor Porto Alegre. Como é
esparso, o valor Porto Alegre pode não ser encontrado; se este for o caso, então procure o índice
anterior que mais se aproxima de Porto Alegre.
2. acesse o bloco apontado pela entrada Porto Alegre ou pela entrada que mais se aproxima de Porto
Alegre
3. faça uma busca linear ou binária no bloco (s), procurando pelo primeiro registro (primeira ocorrência
do registro) desejado. Retorne todos os registros a partir do primeiro encontrado que ainda satisfazem o
critério de seleção (busca linear)
2.
valorChave
Alvorada
Canoas
Gravataí
Guaiba
Novo Hamburgo
Porto Alegre
São Leopoldo
Sapucaia
Triunfo
Viamão
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)
ponteiro
Bloco 1
Alvorada
Alvorada
Alvorada
Alvorada
Alvorada
...
...
Bloco 2
Canoas
Canoas
Canoas
Bloco 3
Gravataí
Operações/acessos:
Gravataí
1. faça uma busca linear ou binária no arquivo de índices, buscando
pelo valor Porto Alegre. Como é esparso, o valor Porto Alegre pode
não ser encontrado; se este for o caso, então procure o índice anterior
que mais se aproxima de Porto Alegre.
2. acesse o bloco apontado pela entrada Porto Alegre ou pela entrada que mais se aproxima de Porto
Alegre
3. se o primeiro registro já satisfaz a consulta (entrada do arquivo de índices é Porto Alegre)
a. Então:
i. Retorne todos os registros a partir do primeiro que ainda satisfazem o critério e
seleção (busca linear)
b. Senão:
i. faça uma busca linear ou binária no bloco (s), procurando pelo primeiro registro
(primeira ocorrência do registro) desejado. Retorne todos os registros a partir do
primeiro encontrado que ainda satisfazem o critério de seleção (busca linear)
...
...
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?
(OP1): σ codAluno=10 (ALUNO)
Linear (S1); ou
Pesquisa binária (S2)
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?
(OP3): σ cidade=’POA’ (ALUNO)
Linear (S1)
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?
(OP1): σ codAluno=10 (ALUNO)
Linear (S1); ou
Pesquisa binária (S2); ou
Pesquisa indexada utilizando o índice primário (S3)
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?
(OP3): σ cidade=’POA’ (ALUNO)
Linear (S1); ou
Pesquisa indexada utilizando o índice cluster para recuperar múltiplos registros
(S5)
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?
(OP2): σ codCurso>5 (ALUNO)
Linear (S1); ou
Pesquisa indexada utilizando o índice cluster para recuperar múltiplos registros
(S5)
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?
(OP4): σ codAluno>=5 AND renda>2000 AND cidade=‘Gravatai’ (ALUNO)
Linear (S1); ou
Seleção conjuntiva utilizando o índice individual da coluna codAluno (S7); ou
Seleção conjuntiva utilizando o índice individual da coluna cidade (S7); ou
Seleção conjuntiva por meio da interseção de registros (S9)
5.
Algoritmos de junção.
Considere a seguinte relação Curso:
codCurso
1
descricao
Ciência da computação
reprDiscente
1
dataCriacao
..
coordenador
...
2
3
4
5
6
7
8
9
10
11
12
...
50
Sistemas de Informação
Medicina
Odontologia
Biologia
Contábeis
Economia
Direito
Engenharia Civil
Engenharia Elétrica
Desenho Industrial
Fisioterapia
3
99
4
1000
5
7
88
8
67
9
34
Vando
23
...
...
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.
Para cada tupla tR em R faca
Para cada tupla tS em S faca
Teste o par (tR,tS) para ver se satisfazem a condição de junção
Se satisfizerem
Adicione tR,tS ao resultado
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.
Como existe um índice na segunda tabela S, então o algoritmo funciona da seguinte
forma:
– recupere cada registro t em R (um por vez)
• Use a estrutura de acesso para recuperar os registros em S que
satisfaçam a condição de junção
Teste de mesa:
Para o registro t em R, acesse o registro em S que satisfaz a condição de junção, usando
o índice para acessar curso.codCurso:
t1R:
1
1
Ana
POA
Recupera o registro em S, usando o índice:
Ciência da computação
1
1300.50
1
..
...
t2R:
2
1
Paulo
Gravataí
Recupera o registro em S, usando o índice:
Ciência da computação
1
2641.56
1
..
...
t3R:
3
2
José
POA
Recupera o registro em S, usando o índice:
Sistemas de Informação
3
1300.50
2
...
...
t4R:
4
4
Maria
Canoas
Recupera o registro em S, usando o índice:
Odontologia
4
4
2300.54
E assim sucessivamente, até que todos os registros de R tenham sido recuperados.
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.
codAluno
1
2
3
4
6
10
1000
5
7
11
12
8
9
...
codCurso
1
2
3
4
5
6
7
8
9
10
11
12
...
50
Varrer ambos arquivos simultaneamente
– Fazendo a correspondência dos registros que possuem os mesmos valores
para os atributos de junção
Tabela aluno ordenada pelo atributo de junção:
nome
cidade
Ana
POA
Paulo
Gravataí
José
POA
Maria
Canoas
Mariana
POA
Carlos
Viamão
Vando
POA
Marcos
Canoas
Juliana
Canoas
Pedro
Gravataí
Sérgio
POA
Eduardo
POA
Ronaldo
Viamão
codCurso
1
1
2
4
4
4
5
6
7
7
7
9
11
Tabela curso ordenada pelo atributo de junção:
descricao
reprDiscente
Ciência da computação
1
Sistemas de Informação
3
Medicina
99
Odontologia
4
Biologia
1000
Contábeis
5
Economia
7
Direito
88
Engenharia Civil
8
Engenharia Elétrica
67
Desenho Industrial
9
Fisioterapia
34
Vando
dataCriacao
..
...
renda
1300.50
2641.56
1300.50
2300.54
3300.88
2360.28
1500.52
2300.57
2300.98
2370.88
1360.98
4305.38
3137.38
coordenador
...
...
23
Teste de mesa:
Pegar o primeiro registro de aluno (R): codCurso=1
Pegar o primeiro registro de curso (S): codCurso=1
Casou (são iguais), então manda pro resultado
Pegar o segundo registro de aluno (R): codCurso=1
Pega o primeiro registro de curso (S): codCurso=1
Casou (são iguais), então manda pro resultado
Pegar o terceiro registro de aluno (R): codCurso=2
Como o terceiro registro de R (codCurso=2) não casa mais com o primeiro registro de
S (codCurso=1), anda uma posição em S e pega o segundo registro de S
Casou (são iguais), então manda pro resultado
Pegar o quarto registro de aluno (R): codCurso=4
Como o quarto registro de R (codCurso=4) não casa mais com o segundo registro de S
(codCurso=2), anda uma posição em S e pega o terceiro registro de S
Como o quarto registro de R (codCurso=4) não casa com o terceiro registro de S
(codCurso=3), anda uma posição em S e pega o quarto registro de S
Casou (são iguais), então manda pro resultado
E assim sucessivamente.....
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?
Como a lista de atributos projetados inclui a chave primária da tabela, basta projetar os dois atributos
pedidos, enviando-os pro resultado
custo = varredura de R; custo=Br
custo = bR (gera bRes blocos de resultado)
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?
Seleção:
Pode ser linear (S1)
Pode ser uma busca indexada (S5: Utilização de um índice cluster para recuperar múltiplos registros)
Projeção:
Como a lista de atributos projetados não inclui a chave primária da tabela, temos que projetar o atributo
solicitado e eliminar eventuais duplicatas.
custo = (1) varredura de R + (2) eliminação de duplicatas
custo de (1) = bR (gera bRes blocos de resultado)
custo de (2) = custo de eliminar as duplicatas (classificar o resultado pelos atributos da projeção e eliminar
tuplas idênticas consecutivas)
Logo: pode ser seleção linear com projeção eliminando duplicatas, ou seleção indexada (usando o índice
cluster para recuperar múltiplos registros) com projeção eliminando duplicatas.
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).
Junção:
J1. Junção de laço aninhado (nested loop) - força bruta. Sempre é possível
J2. Junção de laço único (single loop): como existe uma estrutura de acesso para para curso.codCurso, pode-se
usar este algoritmo:
– Se existir um índice para um dos dois atributos de junção (curso.codCurso)
– recupere cada registro t em aluno (um por vez)
Use a estrutura de acesso para recuperar os registros em curso que satisfaçam a
condição de junção
J3: junção ordenação-fusão (sort-merge). Como aluno está ordenado por codAluno e curso está ordenado por
codcurso, não é possível usar o algoritmo J3 (junção ordenação-fusão - sort-merge), pois este algoritmo exige
que os registros das duas tabelas estejam ordenados pelos valores dos atributos da junção.
Seleção:
Pode ser linear (S1)
Pode ser uma busca indexada (S6. Utilização de um índice secundário em uma comparação de igualdaderecuperar múltiplos registros se o campo de indexação não for chave)
Projeção:
Como a lista de atributos projetados não inclui a chave primária da tabela, temos que projetar os atributos
solicitados e eliminar eventuais duplicatas.
Os algoritmos possíveis incluem a combinação das diversas opções:
1. Junção de laço aninhado com seleção linear e projeção com eliminação de duplicatas
2. Junção de laço aninhado com seleção indexada (S6) e projeção com eliminação de duplicatas
3. Junção de laço único com seleção linear e projeção com eliminação de duplicatas
4. Junção de laço único com seleção indexada (S6) e projeção com eliminação de duplicatas