Algoritmos para
Seleção com Condições Gerais
AULA 17
Profa. Sandra de Amo
GBC053 – BCC
2012-2
Condições Gerais de Seleção
SELECT *
FROM R
WHERE (R.A op ‘a’ OR R.A op ‘a1)
AND
(R.B op ‘b’ OR R.B op ‘b1’)
op: =, < , > , ≤ , ≥
Tamanho de R = M páginas
Número de tuplas por página = Pr
Condição de seleção em FNC
(A11 op a11 OR ... OR An1 op an1) AND
(A12 op a12 OR ... OR An2 op an2) AND ....
AND (A1k op a1k OR ... OR Ank op ank)
 Exemplo:
(day < 8/9/2002 OR R.name = ‘Joe’) AND
(R.id = 5 OR R.name = ‘Joe’)

Caso 1: sem OR

Solução 1 : um só índice



Criar índice para atributo que aparece na
condição de seleção, com maior “seletividade”
utilizar este índice para obter os registros
satisfazendo a condição da chave do índice
A medida que se recupera as tuplas satisfazendo
esta condição elimina-se as tuplas que não
satisfazem alguma das outras condições.
Caso 1: sem OR

Solução 2: diversos índices





Utiliza-se diversos indices, sobre alguns atributos
aparecendo na condição de seleção.
Para cada condição Ai = ai recupera-se as páginas do
arquivo de indice satisfazendo esta condição.
Ordena-se as entradas de cada índice pelo page-id
Faz-se a intersecção das entradas com os mesmos pageids
Recupera-se as tuplas contidas nas páginas indicadas
pelos page-ids e elimina-se aquelas que não satisfazem as
outras condições da seleção (para as quais não foram
considerados indices).
Registros do Indice 1 satisfazendo a condição de seleção : Chave > 1, ordenados pelo page_id
2, (1,3)
15, (8,3)
7, (1,7)
18, (8,7)
Páginas de dados apontadas: 1, 2, 7, 8, 9, 17
3, (1,15)
10, (9,15)
6, (2,10)
4, (7,10)
17, (9,11)
5, (17,10)
Registros do Indice 2 satisfazendo a condição de seleção : Chave ≥ 4, ordenados pelo page_id
4, (1,3)
7, (8,3)
4, (1,7)
12, (11,7)
7, (4,15)
5, (15,15)
6, (5,10)
8, (7,10)
10, (16,11)
9, (17,9)
Páginas de dados apontadas: 1, 4, 5, 7, 8, 11,15,16,17
Páginas que podem conter registros de dados satisfazendo
às duas condições simultaneamente: 1, 7, 8, 17
Só estas páginas de dados serão carregadas no buffer !!
Exemplo

Condição:





Usando B+tree em day recupera-se o conjunto das entradas
E1 com day < 8/9/2002
Usando um indice Hash em R.id recupera-se o conjunto de
entradas E2 com R.id = 5
Ordena-se cada conjunto de entradas pelo page-ids
Considera-se a intersecção das entradas pelos rids


day < 8/9/2002 AND R.id = 5 AND S.age > 35
<a1,p1,s1> ε E1 e <a2, p1, s7> ε E2 então <a1,p1,s1> e <a2, p1,
s7> entram na intersecção
Recupera-se as tuplas do banco de dadas, através das entradas
contidas na intersecção.
Caso 2 : com OR

A = a1 OR B = b1



(A = a1 OR B = b1) AND C = c1



Indice em A, não há indice em B
Melhor solução : scan (o indice em A não ajuda nada)
Indice em A, não há indice em B, indice em C
Melhor solução: utilizar o indice em C
A = a1 OR B = b1


Indice em A, indice em B
Melhor solução:




recupera-se as entradas no arquivo de indice para A = a1 :
recupera-se as entradas no arquivo de indice para B = b1 :
Faz-se a união destes dois conjuntos de entradas
Ordena-se este conjunto pelo page-id
Registros do Indice 1 satisfazendo a condição de seleção : Chave > 1, ordenados pelo page_id
2, (1,3)
15, (8,3)
7, (1,7)
18, (8,7)
Páginas de dados apontadas: 1, 2, 7, 8, 9, 17
3, (1,15)
10, (9,15)
6, (2,10)
4, (7,10)
17, (9,11)
5, (17,10)
Registros do Indice 2 satisfazendo a condição de seleção : Chave ≥ 4, ordenados pelo page_id
4, (1,3)
7, (8,3)
4, (1,7)
12, (11,7)
7, (4,15)
5, (15,15)
6, (5,10)
8, (7,10)
10, (16,11)
9, (17,9)
Páginas de dados apontadas: 1, 4, 5, 7, 8, 11,15,16,17
Páginas que podem conter registros de dados satisfazendo
uma das duas condições: 1,2,4,5,7,8,9,11,15,16,17
Só estas páginas de dados serão carregadas no buffer !!