Facilitando a Tomada de Decisão em um
Ambiente Móvel
ASSUNTO
Mohamed A. Sharaf
Panos K. Chrysanthis
Felipe Menezes Cardoso
COPIN – UFCG
Banco de Dados – 2007.1
Objetivo
• Apresentar um novo algoritmo de
gerência de difusão de dados para
tomada de decisão.
2
2
Sumário
•Visão Geral de SAD e Data Warehouse
•Visão Multidimensional e Ferramentas OLAP
•Esquema Estrela
•Search Lattice
•Data Cube Operator
•Modelo OLAP Wireless Proposto
•Algoritmo Proposto (STOBS)
•Avaliação de Desempenho do STOBS
•Conclusões
3
3
SAD – Sistema de Apoio a Decisão
• Apoiar os gerentes e diretores das
organizações nos seus processos de
tomada de decisão.
• Processar complexas consultas
gerenciais
• Manipulação de grande quantidade de
informação.
4
4
Data Warehouse
Warehouse – Armazém ou Depósito
Data Warehouse (DW) – Depósito de Dado
Fonte: Colaço, 2004
5
5
Data Warehouse
“Conjunto de dados, não volátil, orientado por
temas, integrado, que varia com o passar do
tempo e que serve de suporte para o processo de
tomada de decisões da gerência.”
(W. H. INMON,1996)
6
6
CUBO de Dados
Representação Multidimensional Conceitual
Fatos (Vendas)
•Proporciona diferentes visões aos gerentes, facilitando o
entendimento e a visualização de problemas típicos de
suporte à decisão.
•Mais intuitiva para o processamento analítico da informação
7
7
CUBO de Dados
• Um cubo possui grande quantidade de
células (fatos ou medidas do negócio)
• Tempo: 10 anos, granularidade dia = 3650 linhas
• Cliente: 1000 clientes
• Produtos: 3000
• 3650*1000*5 = 18.250.000 células
• Ou seja, 18.250.000 vendas para o gerente
analisar.
• Exige-se uma ferramenta para analisar essas
informações
8
8
Ferramentas OLAP
Sistema de Apoio à Decisão
• Processamento Analítico da Informação
• Grande volume de dados
• Alto nível de agregação ou sumarização
• Utiliza visualização multidimensional dos
dados
• Dimensão = Critério de Agregação
•
•
•
•
Vendas
Vendas
Vendas
Vendas
por
por
por
por
mês
fornecedor
produto
cliente
9
9
Operações OLAP
• Uma ferramenta OLAP deve implementar
algumas funções, entre elas:
• Drill Down
• Roll UP
• Série temporal (ex: vendas mês a mês)
• Deve-se conhecer o passado para prever o
futuro.
10
10
Esquema Estrela para DW
• Simular um cubo de dados através de
um esquema relacional especial.
• Consiste de:
• Tabela de Fatos (A estrela)
• Tabela dominante
• Tabelas de Dimensão (Os planetas)
• Tabelas auxiliares
• Qualificam os fatos
11
11
Esquema Estrela
Dimensão Fornecedor
12
12
Hierarquia de uma Dimensão
PRODUTO
PAPEL
Antalis
IMPRESSORA
Lexmark
HP
MONITOR
Sansung
LG
NOTEBOOK
Toshiba
Acer
HP
13
13
Operações OLAP
Demonstração
14
14
Ambiente OLAP Móvel
DW Fixo
Wireless
FH
DW Móvel
(Cache)
MH
Gerente Móvel
15
15
Dispositivos Móveis
• Características Peculiares
• Assimetria da Conexão
• Desconexões Freqüentes
• Intencional
• Não Intencional
• Limitação da Fonte de Energia
• Quanto menos transmissão, mais economia
de bateria.
16
16
DW para um Ambiente Móvel
• Unir estas duas tecnologias é
desafiante.
• Questões de desempenho
• Questões de armazenamento
• Diversas pesquisas estão sendo
desenvolvidas nesta área – Mobile
DW.
17
17
Tabela de Fatos
• Consultas OLAP tipicamente são na forma
de dados sumarizados em vários níveis de
detalhe.
• Vendas de um produto em determinado ano, mês,
dia;
• Vendas por fornecedor;
• Total de vendas da empresa;
• etc.
• Pode-se materializar as consultas para
aumentar o desempenho.
• Visões Materializadas
18
18
Visões Materializadas
• Visão é uma relação derivada de uma ou
mais relações base, que são computadas
sempre que uma referência a ela é feita.
• Visão Materializada
• Visão que é armazenada na base de dados
em vez de ser computada
• Aumenta o desempenho de consultas com grande
quantidade de dados
19
19
Search Lattice
Atributos do Group-By
VM
CFP
Relação de Dependência
(Dependency Derivation)
VM
CF
CP
FP
VM
C
F
P
_
VM
VM
• Grafo direcionado que
representa o espaço de
visões materializadas
com suas derivações.
• Cada vértice representa
uma combinação de
atributos do Group-By.
20
20
Data Cube Operator
• Pode-se gerar todas as possíveis visões
materializadas de uma consulta OLAP
através do Data Cube Operator.
• Data Cube Operator
• Proposto pelo pessoal da Microsoft e IBM
• União de todos os possíveis operadores
Group-By aplicados aos atributos da tabela
de fatos.
• 2^n VMs, n são as dimensões da estrela.
21
21
Data Cube Operator
Demonstração
22
22
Modelo OLAP Wireless
1. O gerente requisita VMs.
2
2. O Servidor difunda as VMs
no canal Broadcast.
Servidor
DW
3. O gerente baixa as VMs
requisitadas.
1
3
O Gerente Móvel
23
23
Modelo OLAP Wireless
Bucket Descritor
T(C,P)
Bucket Descritor
T(C,P)
Header
Broadcast
T(C,P,F)
T(C,P,F)
T(C,P,F)
Identificador: 110
Qtd. de Linhas: 1000
Qtd. De Pacotes da Tabela: 2
Valor do Otimizador Alfa: 2
Header
•Especifica se o Bucket em questão é um descritor ou é
um dado.
•Contém o Offset para o próximo pacote descritor e do
pacote descritor corrente.
Bucket
Header
24
24
Modelo OLAP Wireless
Bucket Descritor
Id: 001
L: 800
...
Bucket Descritor
T(F)
T(F)
Id: 110
L: 100
...
T(C,P)
T(C,P)
T(C,P)
Broadcast
O cliente solicita a Tabela T(C,P) utilizando codificação de bit (110).
Cliente vai para o canal de Download. (Active Mode)
O cliente encontra um pacote descritor (001) e o classifica como:
•
Exact Match
•
No Match
•
Subsuming Match
Bucket
Se for compatível com a solicitação então
Continua no Active Mode e baixa a tabela
Senão
Vai para Doze Mode e acorda no próximo pacote descritor
Header
25
25
Algoritmo STOBS-α
• STOBS - Summary Table On-Demand
Broadcast Scheduler
• Algoritmo de Gerenciamento de Difusão
26
26
Algoritmo STOBS-α
Dois componentes básicos:
• Normalizador
• Otimizador-α
• Data Cube Search Lattice.
• Relação de dependência (Dependency
Derivation).
27
27
Algoritmo STOBS-α - Normalizador
O servidor mantém uma fila com todas as
requisições à tabelas dos clientes.
• Para cada requisição ele armazena:
• R – Número de requisições feitas à
tabela Tx.
• W – Tempo da primeira requisição Qx, feita
à tabela Tx.
• S – Tamanho da tabela Tx.
28
28
Algoritmo STOBS-α - Normalizador
• Cada vez que o servidor for difundir
uma tabela ele realiza o seguinte cálculo
para cada tabela da fila:
• (Rx * W) / S
• A tabela de maior valor será escolhida para
o broadcast
29
29
Algoritmo STOBS-α - Otimizador
• Após a seleção da tabela (VM) que será
difundida, o servidor utiliza o
otimizador-α para limpar a fila de
requisições.
• Otimizador-α
• Baseado no parâmetro α, elimina da fila de
requisições as solicitações de VMs que
podem ser derivadas e estão até α níveis
abaixo no grafo de Lattice.
30
30
Algoritmo STOBS-α
• Utiliza a fórmula:
• |X| - |Y| <= α
• Onde |X| é a quantidade de atributos da
visão materializadas x que será difundida
(Broadcasted) e |Y| a quantidade de
atributos da visão materializada y que está
na fila de requisições.
31
31
Funcionamento - STOBS-α
Para α = 2
Imaginemos uma solicitação Q para a
tabela T(d1,d2,d3,d4)
Esta tabela pode derivar tabelas mais
abstratas tais como:
T(d1), T(d2), T(d3), T(d4),
T(d1,d2) , T(d1,d3),
T(d1,d2,d3) e T(d1,d2,d4).
Entretanto, como α = 2, apenas as
requisições as tabelas
T(d1,d2) , T(d1,d3),
T(d1,d2,d3) e T(d1,d2,d4) serão
satisfeitas pela solicitação Q.
Data Cube Search Lattice
As tabelas T(d1), T(d2), T(d3), T(d4)
permanecerão na fila.
32
32
Avaliação de Desempenho
• Foram medidos:
• Tempo de Espera: Tempo gasto pelo cliente para
esperar por um pacote descritor no canal de
Download. Doze Mode
• Tempo de Tune: Tempo gasto pelo cliente para ler um
pacote descritor ou baixar um stream de dados.
Active Mode.
• Tempo de Processamento: Tempo gasto para converter
o stream baixado em uma tabela sumarizada.
• Tempo de Acesso:
• Tespera + Ttune + Tprocessamento
• Consumo de Energia:
• Tactive + Tdoze + Tprocessamento
33
33
Resultado de Desempenho
34
34
Resultado de Desempenho
35
35
Resultado de Desempenho
36
36
Resultado de Desempenho
37
37
Considerações Finais
• É desafiante um ambiente de suporte
à decisão com dispositivos móveis.
• O uso de visões materializadas é uma
estratégia interessante em um
ambiente OLAP Móvel
• O algoritmo STOBS mostrou-se
bastante flexível e de alto
desempenho.
38
38
Referências Bibliográficas
SHARAF, Mohamed; CHRYSANTHIS, Panos. Facilitanting
Mobile Decision Making. WMC’02, September 28, 2002.
COLAÇO JR., Methanias. Projetando Sistemas de Apoio à
Decisão baseado em Data Warehouse. Aracaju: Axcel,
2004.197 p.
GRAY, Jym; CHAUDHURI, Surajit; BOSWORTH, Adam;
LAYMAN, Andrew; REICHART, Don; VENKATRAO Murali;
PELLOW, Frank; PIRAHESH, Hamid.Data Cube: A Relational
Aggregation Operator Generalizing Group-By, Cross-Tab,
and Sub-Totals. 1996.
39
39
Dúvidas?
40
40