Upload
internet
View
104
Download
0
Embed Size (px)
Citation preview
SGBD Para Dispositivos Limitados*
Camilo Porto
Bruno Alexandre
Roteiro
Introdução Problemática Desafios Armazenamento Processamento de consultas Conclusões Referências bibliográficas
IntroduçãoIntrodução
Introdução
Proliferação de dispositivos móveisPDAs, Celulares, Smart Cards;
Processamento Móvel da Informação; Acesso contínuo à informação,
independente do local físico; Informações pessoais, financeiras, médicas,
negócios;
Introdução
Tecnologia móvel nas empresasVendas, trabalho de campo, saúde
Necessidade de computação em todo lugar (Pervasive Computing)
Aumento da complexidade/volume das informações
Introdução
Eficiência no armazenamento da informação;
Eficiência na recuperação da informação; Segurança;
SGBD para dispositivos móveisSGBD para dispositivos móveis
ProblemáticaProblemática
Problemática
Dispositivos Móveis => Limitações de Hardware/Software
RAM Smart Cards – Alguns KB (4Kb – 128Kb) PDAs e Celulares – Alguns MB
Memória estável Smart Cards – (128Kb – 1MB) PDAs e Celulares – (1MB – 512MB)
Problemática
Baixa performance na escrita em memória estável;
Eficiência na leitura; Autonomia de energia;
Problemática
SGBD => Software complexo Técnicas convencionais => Inviabilidade
Como baixar escala das técnicas Como baixar escala das técnicas convencionais?convencionais?
Foco: Armazenamento & Processamento de Consulta
Problemática
Técnicas Convencionais:Armazenamento
Várias estruturas de índices => Consumo de memória
Valores repetidos => Consumo de memória Uso de cache (diminuir I/O) => Consumo de RAM
Problemática
Técnicas Convencionais:Processamento de Consulta
Alto consumo de memória Armazenamento de resultados intermediários Materialização Estruturas temporárias em memória (índices,
ordenação, etc.)
Problemática
Outros problemasSincronizaçãoUsabilidadeDentre outros...
DesafiosDesafios
Desafios
Diminuir espaço ocupado por estruturas de dados (índices, tuplas, etc.)
Diminuir uso de memória RAM Diminuir operações de escrita (lento) Aproveitar eficiência de operações de
leituras
ArmazenamentoArmazenamento
Armazenamento
Armazenamento Seqüencial Simplicidade Tuplas armazenadas em seqüência;
Problemas 1. Consumo de espaço – valores de atributos
duplicados 2. Ineficiente – Ausência de índices => busca
seqüencial Adição de índices resolve o 2º problema ao
mesmo tempo que agrava o 1º...
Armazenamento
Armazenamento por domínio Ausência de valores duplicados Uso de apontadores em atributos
v1
v2
v3
v4Relação R Relação S
Valores
Armazenamento
Armazenamento por domínioCompactação de dados (ausência de valores
duplicados)Facilidade de gestão de memória (tuplas com
tamanhos fixos)
Armazenamento
Armazenamento por domínio Desvantagens
Overhead nas operações insert/delete/update;
Valores únicos (chaves, por exemplo)Valores menor que tamanho da palavra de
memória
Solução?Solução?
Armazenamento
Combinação Seqüencial + DomínioValores únicos => seqüencial;Valores < tamanho da palavra => seqüencial;Valores > tamanho da palavra => domínio
(simplifica gestão de memória)
Problema: estruturas de índicesProblema: estruturas de índices
Armazenamento
Armazenamento em anelRedução de estruturas de índices;Formação de anel: valor => atributos => valorSemelhança com armazenamento por
domínio;
Armazenamento
Estrutura de índice em anel – Select Index
v1
v2
v3
v4Relação R
Valores
R.a
Indice em R.a
Requisito de espaço para o índice: 1 apontador/valor
Select Index...Where R.a=“v1”
Armazenamento
Armazenamento em anelOverhead de projeção – percorrer anel
Armazenamento
Estrutura de índice em Anel – Join Index
Relação R
Relação S
R.b
S.a
Requisito de espaço para o índice: 1 apontador/valor
Join Index...Where R.b=S.a
Armazenamento
Estrutura de índice em AnelJunções efetuadas em Chaves
(freqüentemente)Chaves => armazenamento seqüencial;
Processamento de consultaProcessamento de consulta
Processamento de Consulta
Problemas e RestriçõesO estado da arte em Q.P. não pode ser usado
em SGBDs móveis;Não se pode estimar quantidade de memória
que será utilizada;Devido a restrição de escrita e tempo de vida
da memória utilizada, condena-se uso de write e materialization.
Processamento de Consulta
SoluçõesOs SGBDs existentes (Sybase Everywehere,
Oracle lite, DB2 EveryPlace), não resolvem o problema da restrição de Memória principal;
Framework (operadores) para Query evaluators voltado para dispositivos com restrições de RAM.
Processamento de Consulta
Framework operadoresExpressões utilizadas: Execution without
RAM, RAM Lower Bound model (RLB)Armazenamento interfere na execução de
planos de consulta (uso de índice ou não); Algoritmos dos operadores devem seguir
alguns princípios;
Proc. de Consulta (sem índice)
HipótesesH1: Arquivos de dados on-board são
sequenciais (baixo desempenho);H2: Consultas não aninhadas;H3: Dispositivos autônomos;H5: Armazenamento em memória eletrônica
tipo EEPROM.
Proc. de Consulta (sem índice)
Regras de design R1: Proibido uso de E.D. de tamanho variável; R2: Nunca Armazene informação que pode ser
recomputada (no materialization); Unicidade Completude Operador possui três primitivas: open, close e next.
Proc. de Consulta (sem índice)
Algoritmos Compartilham estrutura de dados: DataFlow (R1 e
R2)
Proc. de Consulta (sem índice)
Algoritmos (select)
Proc. de Consulta (sem índice)
Algoritmos (GBY.open)
Proc. de Consulta (sem índice)
Algoritmos (GBY.next)
Proc. de Consulta (sem índice)
Algoritmos (GBY) Tipos: CompMin, CompMax e IterMin Otimização: Diminuir avaliação de tuplas irrelevantes
através da utilização de filtros.
Proc. de Consulta (sem índice)
Algoritmos (GRY - filtros) Definição: Relevant tuples, required tuples e
Irrelevant tuples; Quanto mais o algoritmo que evitar required tuples e
irrelevant tuples, melhor será.
Proc. de Consulta (sem índice)
Avaliação de desempenho Esquema: R, S, T e U
Proc. de Consulta (sem índice)
Avaliação de desempenho
SGBD Para Dispositivos Limitados
Referências Memory Requirements for Query Execution in Highly
Constrained Devices. Anciaux N., Bougamin L. andPucheral P.Int. Conf. on Very Large Data Bases (VLDB), 2003.
PicoDBMS: Scaling down Database Techniques for the Smartcard. Christophe Bobineau, Luc Bouganim, Philippe Pucheral and Patrick Valduriez.Proceedings of the 26th International Conference on Very Large Databases, Cairo, Egypt, 2000.
IBM DB2 Everyplace, Version 8.1.Interactive Management Software Inc.