Tópicos Avançados de Base de Dados
Carlos Rodrigues
Nuno Loureiro
070316102
070316088
1
Improved Histograms for
Selectivity Estimation of Range Predicates
Autores
FCUP / DCC
Viswanath Poosala
Yannis E. Ioannidis
Peter J. Has
Eugene J.Shekita
2012
Índice
2
 Introdução
 Definição de Histogramas
 Regra de Partição
 Regras de Histogramas
 Abordagens Anteriores a Histogramas
 Histogramas Anteriores
 Novas abordagens a Histogramas
 Novos Histogramas
 Técnicas Computacionais
 Conclusões
Introdução
3
 Vários Histogramas propostos no passado
 Vários módulos de um sistema de BD, necessitam de
estimativas para o tamanho do resultado da consulta
 Estudos anteriores estimam que erros numa consulta
podem aumentar exponencialmente com o número
de conjuntos
Definição de Histogramas
4
 Os Histogramas aproximam a frequência da
distribuição de um atributo


agrupando os seus valores em “baldes” (subconjuntos)
aproximando os verdadeiros valores do atributo e a sua
frequência na BD
 Praticamente não ocorre nenhum gasto em tempo de
execução.
 Nem sempre são eficientes ou práticos
Definição de Histogramas
5
 Um Histograma sobre um atributo X é construído
através de:

Partição da distribuição dos dados T em β, subconjuntos

disjuntos chamados Baldes.
Aproximação das frequências e valores em cada Balde com algo em
comum entre si.
 Baldes são calculados de acordo com a regra da
Partição que procura uma aproximação a T
Regra de Partição
6
 Juntar a T uma terceira coluna que é derivada das
duas primeiras, com T como objecto de ordenação
 Especificar uma subclasse restrita de todos os
Histogramas possíveis numa distribuição T
 Juntar uma quarta coluna derivada das duas
primeiras
 Determinar a única partição de T em β baldes, tal
que o Histograma pertença à subclasse restrita e
satisfaça uma restrição especificada na quarta
coluna
Regras de Histogramas
7
 Classe de partição:
 É a classe restrita de histogramas, considerada pela regra da
partição.
 Restrição de partição:
 É a Restrição matemática, sendo aquela que identifica
unicamente o histograma dentro da sua classe de partição
 Parâmetro de Ordenação e Parâmetro de Origem:
 Os parâmetros derivados de T e colocados na terceira e quarta
coluna.
Regras de Histogramas
8
 Aproximação de valores dentro de um subconjunto:
 A hipótese que determina os valores próximos dentro de um
subconjunto do histograma.
 Aproximação das frequências dentro de um
subconjunto:

A hipótese que determina a frequência aproximada de cada
valor dentro de um subconjunto do histograma.
 Estas duas regras determinam a informação que
necessita estar armazenada em cada balde.
Abordagens anteriores a Histogramas
9
 Classe de partição:


Os Histogramas clássicos não têm restrição no número de elementos
de T que podem ser atribuídos ao Balde.
Histogramas “End-Biased” obrigam que todos os baldes contenham
apenas um elemento de T
 Restrição de partição:

Para a classe em série são considerados 3 tipos de histogramas,
definidos para várias fontes de parâmetros:
Equi-sum: Usa β Baldes, a soma da fonte de valores em cada
subconjunto é igual a 1/β vezes a soma de todas as fontes de valores
no histograma
 V-Optimal: É um histograma com variância ponderada, a fonte de
valores é minimizada.
 Spline-based: O máximo absoluto que difere entre a fonte de valor e a
média da fonte de valores no seu Balde é minimizado.

Abordagens anteriores a Histogramas
10
 Aproximação de valores atribuídos e frequências:


Todos os histogramas fazem a frequência uniforme supondo e
aproximando todas as frequências num Balde pelas suas médias.
Todos os histogramas necessitam de armazenar a frequência média
para cada Balde
Histogramas anteriores
11
 Trivial Histogram:
 Tem apenas um único Balde.
 Equivalentes à popular hipótese de distribuição uniforme
 Equi-Sum(V,S) alias Equi-width:
 Histograma contíguo aos intervalos dos atributos nos
Baldes.
 Soma das propagações em cada balde
 Equi-sum(V,F) alias Equi-depth:
 Como o histograma acima porém tem a soma das
frequências em cada Balde em vez da soma da propagação.
Histogramas anteriores
12
 Spline-Based(V,C):
 Inspiram outros histogramas para melhoramentos em
análise numérica para aproximar curvas.
 V-Optimal(F,F):
 Histogramas contíguos ao conjunto de frequências em
Baldes de forma a minimizar a variância sobre a frequência
aproximada.
 V-Optimal-End-Biased(F,F):
 Algumas das maiores frequências e algumas das mais
pequenas são colocadas em Baldes individuais enquanto as
frequências médias são agrupados num único Balde.
Novas abordagens a Histogramas
13
 Classe de Partição:
 Histogramas tendenciosos têm pelo menos um Balde
singleton e possivelmente vários “não-singleton”.
 Restrições de Partição:
 Duas novas restrições
Maxdiff: Balde limitado entre duas fontes de parâmetros de valores
adjacentes.
 Compressed: Os n maiores valores de origem são guardados
separadamente em n Baldes singleton, o resto é particionado em
histogramas equi-sum.

Novas abordagens a Histogramas
14
 Parâmetros de Ordenação e Parâmetros de origem:
 Introduziu-se a área como uma possível escolha na
classificação e fonte de parâmetros.
 Aproximação de valores atribuídos dentro de um
Balde:

Introduziu-se a hipótese de propagação uniforme em que
para cada atributo dentro de um Balde, assume-se que a
propagação é igual à média do Balde.
Novos Histogramas
15
 V-Optimal(V,F), V-Optimal(V,A), V-Optimal(A,A) e V-
Optimal(V,C):


V-Optimal(V,F) e V-Optimal(V,A) minimizam a variância em
frequências e nas áreas respectivamente.
O V-Optimal(A,A) minimiza a variância da aproximação global da
área.
 V-Optimal-End-Biased(A,A) :
 Idêntico ao (F,F) excepto que este usa a área como parâmetros de
ordenação e origem.
 Maxdiff(V,F), Maxdiff(V,A):
 Tentam alcançar o seu objectivo inserindo limite nos Baldes entre os
valores de origem adjacentes.
 Compressed(V,F) e Compressed(V,A):
 Os atributos com a maior frequência são colocados num Balde
singleton e depois os valores restantes são distribuídos por múltiplos
Baldes.
Técnicas Computacionais
16
 A construção de Histogramas necessita de:
 Cálculo dos quantis para Histogramas equi-depth


Necessário calcular o limite de Baldes
Cálculo das frequências e das frequências acumuladas de cada
atributo

Necessário um contador para cada atributo distinto

Cálculo do número de atributos distintos que se encontram
num dado intervalo

Cálculo da propagação de cada atributo
Conclusões
17
 Inovações:
 Restrições de Partição são mais precisas que as tradicionais.

Uso do número de valores distintos num Balde para aproximar
de forma mais precisa a distribuição dos valores e frequências
no Balde.

Adaptação a algoritmos aleatórios para uma construção
eficiente de Histogramas em série.

Uso de um reservatório de amostras e técnicas de estimações
estatísticas para construir eficientemente Histogramas usando
uma única verificação dos dados.