Universidade Federal de São Carlos
Centro de Ciências Exatas e de Tecnologia
Departamento de Computação
Artigo: Implementando o
cubo de dados eficientemente
Venky Harinarayan
Anand Rajaraman
Jeffrey D. U1lman
Walter Coelho Pereira de Magalhães Junior
PPGCC/DC
Agosto / 2009
Organização desta apresentação
 Introdução
 Framework lattice
 Modelo de custo de consultas utilizado neste artigo
 Otimizando o cubo de dados lattice
 Hipercubo lattice
 Conclusões e trabalhos futuros
2/36
Introdução
Breve revisão de conceitos básicos
1) Modelos multidimensionais e conceitos associados
 Observam as relações inerentes aos dados para gerar matrizes multidimensionais:
 Bidimensionais (planilhas)
 Tridimensionais (cubo de dados)
 Acima de três dimensões (hipercubo)
Cada célula no cubo de dados contém dados de cada dimensão e consiste em uma medida (agregação) de
interesse. Os valores de muitas destas células são dependentes dos valores de outras células.
Os dados podem ser consultados diretamente em qualquer combinação de dimensões, evitando consultas
complexas no banco de dados
O desempenho de consultas em matrizes multidimensionais pode ser muito superior comparativamente ao
modelo relacional
Em um cubo de dados a mudança de uma hierarquia dimensional para outra é realizada por meio de uma
técnica de rotação (pivotamento)... Mostrar exemplo
3/36
Introdução
 Modelos multidimensionais proporcionam visões hierárquicas conhecidas como
apresentações:
 “roll-up”: agregação, sumarização, maior granularidade, move-se para cima na
hierarquia, agrupa em unidades maiores ao longo de uma hierarquia...
Exemplo: sumarização de dados mensais por trimestre ou por ano
 “drill-down”: desagregação, granularidade mais fina, move-se para baixo na hierarquia..
Exemplo: desagrupar vendas nacionais em regionais ou por unidade produtiva
 Um modelo de armazenamento multidimensional envolve dois tipos de tabelas:
 de dimensão, consistindo de uma tupla de atributos da dimensão
 de fatos, uma tupla para cada fato identificado por ponteiros para as tabelas de dimensão
 Esquemas multidimensionais comuns são:
Estrela, única tabela de fatos e única tabela para cada dimensão
 Snowflake, possui tabelas de dimensão normalizadas

“Constelação de fatos, conjunto de tabelas de fatos compartilhando tabelas de dimensão...”
4/36
Introdução
 Modelagem multidimensional: os sistemas de banco de dados tradicionais utilizam a normalização
no formato de dados visando garantir consistência aos dados e uma minimização do espaço de
armazenamento necessário. Entretanto, algumas transações e consultas em bases de dados
normalizadas podem tornar-se lentas devido às operações de junção entre tabelas. Um Data
Warehouse utiliza dados em formato de-normalizados. Isto aumenta o desempenho das consultas
e, adicionalmente, o processo de consulta torna-se mais intuitivo para os usuários comuns.
2) Sistemas de apoio à decisão (DSS) e Banco de dados para apoio à decisão – Data Warehouse:
 Aplicações de suporte à decisão envolvem consultas complexas em banco de dados muito grandes e
fazem forte uso de agregação de dados - Uma vez que o tempo de resposta deve ser pequeno, a
otimização de consultas é crítica...
Uma técnica comum e poderosa para otimização de consultas é “materializar algumas ou todas estas
células (visões)” ao invés de computá-las, cada vez, a partir de dados brutos
As visões materializadas consistem na principal opção para aprimorar o desempenho em um DW,
entretanto:
 otimizadores e técnicas de avaliação de consultas podem ser aprimoradas para lidar melhor com
agregações
 podemos usar diferentes estratégias de indexação, tais como índices de bitmap e índices de junção
 outras opções
Uma visão materializada é uma consulta cujo resultado já foi computado e está armazenado na base de dados...
As consultas que puderem utilizar as visões já armazenadas, podem ser executadas de forma muito mais rápida.
Conforme a complexidade e o volumes de dados, podem ser reduzidas de horas ou dias para segundos ou minutos.
5/36
Introdução
Outra questão importante é que ao materializarmos uma consulta (mesmo que relativamente
infrequente) podemos ser capazes de responder a outras rapidamente...
3) Este artigo:
 Investiga a questão de qual célula (visão) materializar, quando for muito caro materializar
todas as visões.
 Um framework lattice (entrelaçado) é usado para expressar as dependências entre as visões e
juntamente com algorítimos, permitem escolher um bom conjunto de consultas a serem
materializadas e indicar a ordem em que devem ser materializadas.
TPC-D: Banco de dados de apoio à decisão - Data warehouse
 Existem três dimensões nas quais estamos interessados: peça, fornecedor e consumidor.
 A medida de interesse é o total de vendas.
 Em cada célula (p,s,c) neste cubo de dados 3-D armazenamos as vendas de peças “p” que foram
compradas do fornecedor “s” e vendidas ao consumidor “c”.
“Embora uma dimensão possa ter muitos atributos, usa-se os termos dimensões e atributos de
forma alternada nesta seção”
6/36
Introdução
Suponha que os usuários estão interessados nas vendas consolidadas...
Qual é o total de vendas de uma peça “p” para um consumidor “c”
Sugere-se acrescentar um valor adicional “ALL” para o domínio de cada dimensão:
Qual o total de vendas da peça “p” para o consumidor “c” para “todos” os fornecedores
A consulta será respondida observando o valor da célula (p, ALL, c), que será computada como a soma dos
valores das células de (p, s1, c),...,(p, sn, c), onde “n” representa o número de fornecedores
Quanto mais células nós materializamos, melhor será o desempenho das consultas. Contudo, para grandes
cubos, nós podemos ser capazes de materializar somente uma pequena fração de células devido ao espaço e
outras restrições. Por isto é muito importante escolhermos as células corretas para materializar...
Qualquer célula que tenha o valor “ALL” como um dos componentes em seu endereço é uma “célula
dependente”, cujo valor é computável a partir de outras células no cubo de dados. Se uma célula não possui
“ALL” como componente, seu valor não pode ser computado por outras células e nós precisaremos consultar
os dados brutos para computar seu valor.
O número de células contendo “ALL” como um de seus componentes é normalmente uma grande parte do
total de células no cubo de dados... No TPC-D 70% das células do cubo de dados são dependentes...
7/36
Introdução
 Alternativas de implementação do cubo de dados:

Materialização completa do cubo de dados
Melhor tempo de reposta
 Alternativa não factível para grandes cubos de dados - espaço de armazenamento
 Espaço consumido causa impacto na indexação


Nenhuma materialização

 Problemas com tempo de resposta: “precisamos ir até os dados brutos e computar cada célula...”
 Nenhum espaço extra é solicitado, além do exigido para os dados brutos
Materializar somente parte do cubo de dados
 Aproveitar o conceito de células dependentes no cubo de dados, sabendo que os valores de muitas
células são computáveis a partir de outras
“Esta dependência é similar a uma planilha onde o valor das células pode ser calculado em função de outras...”
 A questão de onde armazenar o cubo de dados materializado, facilita o processamento de
dados multidimensionais - OLAP
 Sistema relacional: escalável, suporta DW muito grandes, técnicas para melhorar desempenho
 Banco de dados multidimensional proprietário (MDDB)+API’s para OLAP: melhor desempenho
“Implementação comum: dados brutos em sistema relacional e o cubo em MDDB...”
8/36
Introdução
 Este artigo assume que:
 O cubo de dados está implementado em tabelas resumo em um sistema relacional
 Os conjuntos de células do cubo de dados estão associados a diferentes tabelas e agrupados segundo a
posição do operador “ALL” em seus endereços
Assim, todas as células que batem com o endereço ( _, ALL, _) estão colocadas no mesmo conjunto...
 Cada um deste conjuntos de células correspondem a diferentes consultas SQL...
A saída da consulta
“SELECT Part, Customer, SUM(SP) AS Sales FROM R GROUP BY Part, Customer”
é o conjunto de células no formato (_, ALL, _)
Observações:
 Em geral, atributos com valores “ALL” no conjunto de células não aparecem na cláusula GROUP BY
 Os atributos de agrupamento diferenciam as consultas SQL que formam os conjuntos de dados
 Decidir qual conjunto de células materializar é equivalente a decidir qual consulta (visão)
materializar
 O custo de resposta a uma consulta é proporcional ao número de linhas examinadas
 As visões não possuem índices...
9/36
Introdução
Exemplo:
O banco de dados TPC-D possui três dimensões (atributos): peça, fornecedor, consumidor
A medida de interesse são as vendas
Oferece oito possibilidades de agrupamento dos atributos ...
formam oito consultas (visões) organizados em forma entrelaçada (lattice)
“Repare que basta mencionar os atributos na cláusula GROUP BY...”
Visões candidatas a materialização:
1.
2.
3.
4.
5.
6.
7.
8.
part, supplier, customer (6 Milhões de linhas)
part, customer (6M)
part, supplier (0.8M)
supplier, customer (6M)
part (0.2 M)
supplier (0. 01 M)
customer (0.1 M)
none (1) – nenhum atributo na cláusula GROUP-BY
10/36
Introdução
Trabalhando com as visões: exemplo de possíveis consultas solicitadas pelos usuários...
 Total das vendas agrupadas por peça
Temos uma visão materializada agrupada somente por (peça) - visão 5:
 Processamento: basta varrer a visão inteira e mostrar a resposta
 Custo de resposta da consulta: custo de processar 0,2 milhões de linhas (tamanho da view)
Temos uma visão materializada agrupada por (peça,consumidor) – visão 2:
 Processamento: para cada peça precisamos somar suas vendas por todos os consumidores
 Custo de resposta da consulta: processar 6 milhões de linhas
 Vendas de uma única peça
A análise acima se aplica, exceto pelo fato de que no processamento da visão 5 poderíamos
varrer a visão inteira ou metade na média
Questões interessantes:
 Quantas visões devemos materializar para obtermos uma performance razoável ?
 Quais visões devemos materializar para minimizar o custo médio de consulta ? (Existe espaço)
O framework lattice e os algorítimos, vistos mais a frente, ajudam a responder estas questões e
fornecem resultados próximos ao ótimo...
11/36
Introdução
Buscando a eficiência no processo de materialização:
Na materialização de todo o cubo de dados do TPC-D as visões materializadas ocupariam mais de
19 milhões de linhas...
Procurando ser mais eficiente, podemos escolher adequadamente quais partes do cubo de dados
materializar, aproveitando a “dependência das células (consultas, visões) e colher benefícios dramáticos:

Necessitamos materializar a visão agrupada (peça,fornecedor,consumidor) – visão 1 –
“evitando consultar os dados brutos, uma vez que ela não pode ser construída a partir de outra”

Não existe nenhuma vantagem em materializar a visão (peça,consumidor) – visão 2 “toda consulta direcionada à esta visão pode ser respondida por meio da visão 1, a qual também
apresenta um custo de resposta na ordem de 6 milhões de linhas”

Pela mesma razão, não existe vantagem em materializar a visão (fornecedor,consumidor)
– visão 4
Conclusão:
“... podemos obter quase o mesmo custo médio de consulta materializando um cubo de dados com
apenas 7 milhões de linhas, representando um ganho de mais de 60% em termos de espaço
consumido e no custo para criar o cubo de dados”
12/36
Framework Lattice
 Consiste em uma notação utilizada para descrever quando uma consulta ao cubo de dados
pode ser respondida usando o resultado de outra...
A notação de uma visão ou consulta apresenta seus atributos de agrupamento entre
parênteses, por exemplo: (peça, fornecedor, consumidor)
Q1
Q2 :: A consulta Q1 pode ser respondida usando os resultados da consulta Q2
Q1 é dependente de Q2
Exemplo: (peça,consumidor)
(peça,fornecedor,consumidor)
(peça,fornecedor)
(peça,fornecedor,consumidor)
Q1
Q2 :: A consulta Q1 não é comparável com a consulta Q2
Exemplo: (peça)
(consumidor)
 Notação Lattice: (L,
) : L = conjunto de elementos (visões ou consultas) do lattice
:
= relação de dependência
Para os elementos (visões) “a” e “b” do lattice dizemos que “b” é progenitora (mãe) de “a”
se e somente se a b
13/36
Framework Lattice
 Hierarquias
Na maioria das aplicações do mundo real as dimensões de um cubo de dados possuem
vários atributos e estão organizadas em hierarquias destes atributos
“...organizar a dimensão tempo na hierarquia dia, mês, ano”
Possibilitam as operações abaixo:
TOTAL DE VENDAS
“roll-up”
: Vendas por dia, vendas por mês, vendas por ano
Dia Mês Ano
“drill-down”
: Vendas por ano, vendas por mês, vendas por dia
Lembrando:
 Introduzem o conceito de “dependência de consultas” que devemos considerar quando
formos materializar as consultas...
 Drill-down é o processo de visualização de dados progressivamente até um nível mais
detalhado, roll-up é o oposto
14/36
Framework Lattice
 Com hierarquias a dependência lattice (L, ) é mais complexa que o hipercubo lattice...
Usando a hierarquia com atributos da dimensão tempo Ano, Mês, Dia podemos agrupar as
consultas em três possibilidades, conforme a granularidade, em (Ano), (Mês), (Dia) e assim
temos que (Ano) (Mês) (Dia)
“...se temos o total de vendas agrupado por mês, podemos usar os resultados para
computar o total de vendas por ano”
Em uma hierarquia Ano, Mês, Semana, Dia observe que (semana) (mês)
(semana) (ano). Portanto, se agruparmos por semana não poderemos,
a partir deste agrupamento, determinar o agrupamento por mês ou ano,
e vice-versa, uma vez que nem mês nem ano podem ser divididos de uma
maneira uniforme em semanas
Composição lattice para múltiplas dimensões hierárquicas
Estamos confrontados com dois tipos de “dependência de consultas”:
 Dependência de consulta devido a interação entre diferentes dimensões
 Dependência de consulta em uma mesma dimensão devido a hierarquia de atributos
15/36
Framework Lattice
Para cada dimensão podemos criar visões agrupando por um membro da hierarquia ou nenhum...
então cada visão pode ser representada por uma n-tupla (a1, a2, ..., an) onde cada elemento
é um ponto nesta hierarquia da n-ézima dimensão
Este lattice é denominado “produto direto do lattice dimensional”:
(a1, a2,...,an) (b1,b2,..,bn), se e somente se, ai bi, para todo i.
Exemplo:
• As dimensões “peça” e “consumidor” estão organizadas em hierarquias...
• No lattice dimensional os atributos de cada dimensão podem ser agrupados, formando as consultas:
• na dimensão “consumidor”: individualmente (i), por nação(n) ou nenhum (none)
• na dimensão “peça”: tamanho (s), tipo (t) ou nenhum (none) , observando que (s) (t)
“Quando o valor da dimensão é “none” não especificamos a dimensão na consulta: (s,none) => (s)”
16/36
Framework Lattice
 Framework lattice combinando duas dimensões hierárquicas
Vantagens do framework lattice:
1) Trata-se de um framework limpo para raciocinarmos com hierarquias dimensionais, uma vez que
o produto direto lattice nem sempre é um hipercubo quando as hierarquias não são simples
2) Podemos modelar melhor as consultas comuns solicitadas pelos usuários
3) A abordagem lattice nos ajuda a determinar em que ordem materializar as visões…
 Ao usarmos as visões que já tenham sido materializadas para materializar outras visões, podemos
reduzir o acesso aos dados brutos e reduzir o tempo total de materialização
 Uma simples ordenação descendente no operador
nos informa a ordem requerida para
materialização
17/36
O modelo de custo
Modelo de custo linear adotado
“O tempo para responder a uma consulta é considerado igual ao espaço ocupado pela visão a partir da
qual a consulta é respondida...”
Em um lattice (L, ) de visões para responder a uma consulta Q escolhemos visão materializada
QA progenitora de Q.
Para responder Q necessitamos processar a tabela correspondente a QA...
Este artigo adota o modelo de custo mais simples:
O custo para responder Q é o “número de linhas” presentes na tabela QA usada para construir
Q, ou seja, o custo de Q está em função do tamanho da tabela QA
Existem outros fatores não considerados que influenciam no custo da consulta, por exemplo:
 cluster de visões materializadas sobre algum atributo
 índices
Modelos de custo mais complicados são certamente possíveis, mas o modelo de custo adotado é
mais simples e realista, habilitando-nos a projetar e analisar algoritmos poderosos...
A análise dos algoritmos detalhados mais a frente, reflete a performance sobre outros modelos de
custo, tanto quanto, sobre o modelo de custo adotado...
18/36
O modelo de custo
Exame de um experimento do modelo de custo linear adotado
Em uma validação experimental deste modelo de custo solicitamos o total de vendas para um único fornecedor
usando visões de diferentes granulações...
Encontramos um relacionamento quase linear entre o tamanho e o tempo de execução da consulta, expresso pela
fórmula :
T= M * S + C
 T = tempo de execução da consulta
 M = razão (taxa) entre o tempo da consulta e o tamanho da visão (T/S), após contabilizar o custo fixo
 S = tamanho da visão
 C = custo fixo (overhead para executar a consulta em uma visão de tamanho desprezível)
Fonte
Tamanho
Tempo
Taxa
A partir da célula
1
2.07
-
A partir da visão s
10.000
2.38
.000031
A partir da visão ps
0.8 M
20.77
.000023
A partir da visão psc
6M
226.26
.000037
Note que a taxa é quase sempre a mesma para diferentes visões....
19/36
O modelo de custo
Determinando os tamanhos das visões
Os algorítmos usados neste artigo requerem o conhecimento do número de linhas presente em cada visão
Existem muitas maneiras de estimar os tamanhos das visões sem materializar todas as visões...
• Uma abordagem comumente usada é executar o algorítmo sobre um pequeno mas estatisticamente
representativo subconjunto de dados brutos.
Neste caso, nós podemos obter o tamanho das visões, na verdade, materializando as visões.
Usamos este subconjunto de dados brutos para determinar quais visões nós queremos materializar.
Podemos usar métodos de amostragem e análise para calcular o tamanho das diferentes visões se nós
somente materializarmos o maior elemento no lattice (a visão agrupada pelo maior atributo em cada
dimensão).
Em uma visão, se sabemos que os atributos de agrupamento são estatisticamente independentes, podemos
estimar o tamanho da visão, analiticamente, em relação ao tamanho da maior visão no lattice.
De outra forma, nós podemos amostrar a maior visão ou dado bruto para estimar o tamanho de outras
visões.
O tamanho de uma visão é o número de valores distintos dos atributos que ela agrupa...
Existem muitas técnicas de amostragem conhecidas que podemos usar para determinar o número de
valores distintos dos atributos em uma relação
20/36
Otimizando o cubo de dados lattice
Nosso mais importante objetivo é desenvolver técnicas para otimização de tempo e espaço quando
implementamos um lattice de visões
Iniciaremos com um simples problema de otimização:
 Minimizar o tempo médio necessário para avaliar o conjunto de consultas que são idênticas às visões
 Estamos restritos a materialização de um número fixo de visões não importando o espaço que ocupem
Algorítmo ganancioso
“...selecionamos uma sequência de visões sendo cada uma a melhor escolha dado o que aconteceu
antes. Esta abordagem é sempre relativamente próxima à ótima, e em alguns casos produz a melhor
seleção possível de visões a materializar...”
Supondo:
 existe um cubo de dados lattice com um custo de espaço (número de linhas) associado a cada visão
 C(v) = custo da visão v
 o conjunto de visões que materializaremos deve sempre incluir a visão superior (topo), porque não
existe qualquer outra visão que possa ser utilizada para responder a uma consulta correspondente a
esta visão...
 existe um limite k para o número de visões, adicionalmente a visão superior que podemos selecionar
 após selecionar o conjunto S de visões, o benefício da visão v relativa a S , denotado por B(v,S), é
definido por:
1) Para cada w
v definir a quantidade Bw por:
a) u é a visão de menor custo em S e w
u
b) se C(v) < C(u), então Bw = C(v) – C(u), senão Bw = 0
21/36
Otimizando o cubo de dados lattice
2)
Ou seja, nós computamos o benefício da visão “v” considerando como ela pode aprimorar o custo de
execução das visões “w” que podem ser respondidas a partir dela, incluindo também a si mesma
Para cada visão “w” que “v” cobre, nós comparamos o custo de execução de “w” usando “v” X o custo
de execução de “w” usando qualquer visão em S oferecida como a maneira mais barata de executar
“w”
Se “v” contribui para que o custo de “v” seja menor que da sua concorrente, então a diferença
representa parte do benefício de selecionar “v” como uma visão materializada
O benefício total B(v, S) é a soma dos benefícios de executar todas as visões “w” a partir de “v”,
desde que o benefício seja positivo
Definimos o algorítmo ganancioso para selecionar um conjunto de k visões para materializar
S = {top view};
for i=l to k do begin
select that view v not in S such that B(v, S) is maximized;
S = S union {v};
end;
resulting S is the greedy selection;
22/36
Otimizando o cubo de dados lattice
Exemplo:
O lattice ao lado possui oito visões (a ... h) com seus custos de espaço
 A visão superior (a), com custo 100, precisa ser escolhida
 Gostaríamos de escolher mais três visões para materializar
Para executar o algorítmo ganancioso neste lattice precisamos fazer três
escolhas sucessivas de visões para materializar...
A coluna “Choice 1” informa os benefícios de escolha além de “a”
 No cálculo do benefício assumimos que cada visão é avaliada
usando “a” e portanto terá um custo de 100
 Se primeiramente pegarmos a visão “b” para materializar
reduziremos seu custo por 50 e para cada visão abaixo dela (d,e,g,h) ... O benefício será de 50 x 5 = 250
 Se pegarmos “e” primeiro, então ela e as visões (g,h) abaixo dela terão seus custos reduzidos em 70,
ou seja, de 100 para 30. Assim o benefício será de 70 x 3 = 210
 Então, elegemos a visão “b” neste primeiro round, como
uma das visões a serem materializadas
 Precisamos recalcular os benefícios de cada visão “v”
dado que a visão será criada ou a partir de “b” a um custo
de 50 se “b” estiver acima de “v” , ou a partir de “a” a um
custo de 100 se “b” não estiver acima de “v”
23/36
Otimizando o cubo de dados lattice
Os benefícios agora são mostrados na coluna “Choice 2”
 O benefício da visão “c” é agora 50: 25 para si mesmo e f. Escolher “c” não melhora o custo de e, g ou h
em 25 para estas visões
 Escolher f gera um benefício de 60 para si mesma, de 100 para 40. Para “h” ela gera um benefício de 10,
de 50 para 40, uma vez que a escolha de “b” já melhorou o custo associado com “h” em 50
 A vencedora é “f” com um benefício de 70
Nossa terceira escolha está resumida na coluna “Choise 3”
 A vencedora do terceiro round é “d” com um benefício de 60 para si mesma e para “g”
A seleção gananciosa são as visões “b”, “f” e “d” que juntamente com “a” reduzem o custo total para executar
todas as visões de 800 (caso somente “a” fosse materializada) para 420. Atualmente, este é o custo ótimo
24/36
Otimizando o cubo de dados lattice
Exemplo: O lattice ilustrado abaixo é tão ruim quanto um lattice pode ser para o caso k = 2
“Um exemplo onde a ganância faz mal…”
O algorítmo ganancioso inicia com somente a visão top “a”.
Primeiramente pega “c” cujo benefício é 4141. “c” e as 40 visões abaixo dela são melhoradas de 200 para 99,
quando usamos “c” no lugar de “a” para respondê-las
Para nossa segunda escolha, podemos pegar ou “b” ou “d”. Ambos possuem o benefício de 2100. Em “b”
observamos que ela melhora a si mesmo e os 20 nós na extremidade esquerda por 100 cada
Assim, com k = 2 o algorítmo produz uma solução com um benefício de 6241
25/36
Otimizando o cubo de dados lattice
Contudo, a escolha ótima é pegar “b” e “d”, uma vez que juntas estas duas visões melhoram em 100 a si
mesmas e as outras 80 visões nas quatro cadeias
Desta forma, a solução ótima apresenta um benefício superior de 8200
A razão greedy / ótima é 6241 / 8200 = ¾
“Em verdade, tornando o custo de “c” próximo a 100 e fazendo as quatro cadeias terem um número
grande de visões, podemos encontrar exemplos para k = 2 com razão próxima a 3/4, mas não pior”
Um experimento com o algorítmo ganancioso
Executamos o algorítmo no lattice combinando 2 dimensões hierárquicas (mostrado anteriormente)
usando o banco de dados TPC-D
A ordem resultante das visões a partir da primeira (top – obrigatória)
para a última, é vista ao lado
As unidades Benefícios, Tempo e Espaço estão em número de linhas
O tempo médio da consulta é o tempo total dividido pelo número de
linhas das 12 visões
O exemplo a seguir mostra porque é importante materializar algumas
visões e porque materializar todas as visões não é boa escolha…
26/36
Otimizando o cubo de dados lattice
Para as primeiras visões que selecionamos com mínima adição de espaço, o tempo de consulta é reduzido
substancialmente. Contudo, após a quinta visão, não melhoramos o tempo total de consulta substancialmente,
mesmo usando grandes quantidades de espaço
É claro quando parar de pegar visões...Para as cinco primeiras obtemos quase o tempo total mínimo possível
enquanto o espaço total usado é pouco maior que o espaço obrigatório usado apenas para a visão “top”
Tempo total
Espaço consumido
Número de visões
27/36
Otimizando o cubo de dados lattice
Um desempenho garantido para o algorítmo ganancioso
O algorítmo ganancioso nunca executa “muito mal” qualquer que seja o lattice...
possui ao menos 63% do benefício de um algorítmo ótimo
Notação
m = número de visões em um lattice
suponha não existir nenhuma visão selecionada além da “top” (a qual é obrigatória), então
o tempo T para responder cada consulta é exatamente o número de linhas da visão “top”
V = {v1,v2,..,vk} conjunto de visões ordenadas escolhidas pelo algorítmo além da visão “top”
Tv = tempo médio para responder a uma consulta
T - Tv = benefício do conjunto de visões V: redução no tempo médio para responder a uma consulta
“...minimizar o tempo médio para responder a uma consulta equivale a maximizar o benefício
de um conjunto de visões...”
v1,v2,...,vk = “k” visões selecionadas em ordem pelo algorítmo ganancioso
ai = benefício alcançado pela seleção de vi pertencente ao conjunto V + top e onde i = 1,2,...,k
W = {w1,w2,..,wk} conjunto ótimo de visões: fornecem o benefício total máximo
bi = benefício alcançado pela seleção de wi pertencente ao conjunto W (ordenado) + top e onde i = 1,2,..,k
e
28/36
Otimizando o cubo de dados lattice
Bgreedy = T - Tv = A / m benefício do conjunto V escolhido pelo algorítmo
Bopt = T - Tw = B / m
benefício do conjunto W ótimo escolhido
para k = 2 obtivemos A / B ≥ 3 / 4 .... O algorítmo ganancioso é ao menos 3/4 do ótimo
mostramos um lattice que aproximou em 3/4 a razão entre o benefício dos algorítimos greedy e ótimo
Em outro artigo mostramos que podemos construir um lattice tal que
k
como k ->  ,
aproxima de 1/e, assim 1 – 1/e = (e – 1) / e = 0.63
ou seja, para qualquer lattice o algorítmo ganancioso não dará benefício inferior a 63% do algorítmo
ótimo. O exemplo “onde a ganância faz mal” mostra que esta razão não pode ser melhorada
Os resultados estão sumarizados no seguinte teorema:
“Para qualquer lattice onde
Bgreedy seja o benefício de k visões escolhidas pelo algorítmo ganancioso
Bopt
seja o benefício de um conjunto ótimo de k visões
então
e existem lattices onde
é próximo a
“
29/36
Otimizando o cubo de dados lattice
Situações onde o algorítmo ganancioso é ótimo e não necessitamos buscar outras soluções...


se a1 é muito maior que os outros a’s então o algorítmo ganancioso é próximo a ótimo
se todos os a’s são iguais então o algorítmo ganancioso é ótimo
Extensões ao modelo básico
Existem ao menos duas situações onde o modelo falha ao refletir a realidade...
 As visões em um lattice não são sucetíveis de terem a mesma probabilidade de serem solicitadas em
uma consulta... Em vista disto, devemos ser capazes associar uma probabilidade à cada visão
representando a frequência na qual é solicitada
Ao computarmos os benefícios, pesamos cada visão por sua probabilidade... O algorítmo terá os
mesmos limites de desempenho: ao menos 63%...

Em vez de solicitar um número fixo de visões a materializar, nós poderíamos alocar uma quantidade
fixa espaço para as visões (além da visão “top” que sempre deve ser materializada)
Se não temos restrições ao número de visões selecionadas , mas sim ao espaço ocupado por elas,
necessitamos considerar o benefício de cada visão por unidade de espaço utilizado na sua materialização...
O algorítmo ganancioso terá uma complicação adicional, mas existe um teorema que afirma: “se ignoramos
casos limite o desempenho garantido do algorítmo ganancioso é o mesmo dos casos simples...”
Teorema: “Seja Bgreedy o benefício e S o espaço ocupado por um conjunto de visões escolhidas pelo algorítmo
ganancioso e Bopt o benefício de um conjunto ótimo de visões que ocupa não mais que S unidades de espaço,
então
“
30/36
O hipercubo lattice
A classe mais importante de lattices são os hipercubos, nos quais as visões são vértices de um cubo
n-dimensional, para qualquer “n”
 Existem “n” atributos onde um agrupamento pode acontecer...
Vimos um exemplo de hipercubo com n=3 para o banco de dados TPC-D
 A visão “top” agrupa todos estes “n” atributos
 Podemos visualizar as visões organizadas por “ranks” onde o i-ézimo rank a partir do fundo são todas
as visões agrupadas em “i” atributos. Existem
visões no rank “i”
Caso: tamanho de domínio igual
Podemos aplicar o algorítmo ganancioso no hipercubo procurando:
 um número fixo de visões para materializar ou
 uma quantidade fixa de espaço para alocar para as visões
Examinaremos em maiores detalhes as opções para seleção de visões para materialização...
Assumimos ser improvável, na prática, que todos os atributos tenham o mesmo tamanho de domínio (r)
 Consequentemente, podemos estimar facilmente o tamanho de qualquer visão...
 Veremos à frente que a visão atual selecionada para materialização irá variar, mas as técnicas básicas
não mudarão para acomodar esta situação
Quando cada tamanho de domínio é “r” e os dados no cubo de dados estão distribuídos aleatoriamente,
então existe uma maneira simples de estimar o tamanho das visões
 Suponha que somente “m” células da visão topo de um lattice aparecem nos dados brutos
 Se agruparmos em “i” atributos então o número de células no cubo resultante será “ri”
31/36
O hipercubo lattice
Se ri ≥ m então cada célula conterá no máximo um ponto de dados e “m” destas células não estarão vazias
então, “m” será o tamanho de qualquer visão para a qual ri ≥ m
Se ri < m então quase todas as “ri” células terão ao menos um ponto de dados
Uma vez que podemos condensar todos os pontos de dados de uma célula em um valor agregado , o custo de
espaço de uma visão com ri < m será de aproximadamente “ri”
O gráfico mostra como o tamanho de uma visão cresce em função do número de atributos agrupados...
O tamanho das visões cresce exponencialmente até atingir o tamanho dos dados brutos no rank
o qual é o precipício no gráfico, e então pára de crescer
Este padrão quase bate com o do banco de dados TPC-D: a visão “top” e as visões com 2 atributos
agrupados possuem o mesmo “tamanho máximo”, exceto que a visão “ps” tem linhas a menos (0,8M)
32/36
O hipercubo lattice
A solução tempo e espaço ótima
Uma questão natural a ser investigada: qual é o tempo médio para uma consulta quando o espaço é mínimo ?
O espaço é minimizado quando materializamos somente a visão “top”... então, cada consulta leva um
tempo “m” para ser executada e o custo de tempo total para todas as 2n consultas é m 2n
Em um outro extremo nós podemos minimizar o tempo materializando cada consulta
Entretanto, não ganharíamos muito materializando qualquer visão acima do “precipício” no gráfico...
então, devemos evitar materializar aquelas visões...
A solução tempo ótimo depende do rank
maximizado
,onde o precipício ocorre, e o rank “j” onde
seja
O quadro abaixo resume o tempo e espaço para os três pontos estudados
Estratégias de tempo ótimas para o hipercubo
33/36
O hipercubo lattice
Extensão para variações no tamanho do domínio
Suponha agora que os domínios de cada atributo não tenham valores de “r” igualmente prováveis...
O modelo deve então assumir que para cada dimensão valores são igualmente prováveis mas o número de
valores varia, com ri valores na i-ézima dimensão para i = 1, 2,...,n
Agora o precipício não ocorre em um particular rank mas encontra-se distribuído entre os ranks
Entretanto, o comportamento fundamental sugerido no gráfico anterior, permanece inalterado
34/36
Conclusões e trabalhos futuros
Conclusões
 Neste artigo investigamos o problema de decidir qual conjunto de células (visões) devemos materializar
em um cubo de dados, visando minimizar o tempo de resposta às consultas
 A materialização de visões é uma estratégia essencial para otimização de consultas em sistemas de apoio
à decisão, e a correta seleção de visões a materializar é ponto crítico para o sucesso desta estratégia

Usando o banco de dados TPC-D, mostramos porque é importante materializar alguma parte do cubo de
dados, mas não todo o cubo
 A segunda contribuição é um framework lattice que modela análises multidimensionais muito bem
 O algorítmo ganancioso trabalha neste lattice e seleciona corretamente as visões a materializar, sujeitas a
várias restrições... “outros autores mostraram que nenhum algorítmo polinomial pode executar melhor”

Finalmente, observamos o caso mais comum de um hipercubo lattice e investigamos a negociação de
tempo e espaço em detalhes

As visões, em algum sentido, formam uma memória hierárquica com diferentes tempos de acesso. Nas
hierarquias de memória convencionais os dados são comumente associados a diferentes memórias de
armazenamento (tais como cache ou memória principal) dinamicamente baseadas em padrões de acesso
em tempo de execução
Trabalhos futuros
 Estamos atualmente investigando estratégias de materialização similares para o cubo de dados
35/36
36
Walter Coelho Pereira de Magalhães Junior
[email protected]
PPGCC/DC - UFSCar
2009
36/36