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ção
Introdução

Proliferação de dispositivos móveis
 PDAs,
Celulares, Smart Cards;
Processamento Móvel da Informação;
 Acesso contínuo à informação,
independente do local físico;

 Informações
negócios;
pessoais, financeiras, médicas,
Introdução

Tecnologia móvel nas empresas
 Vendas,
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óveis
Problemática
Problemática


Dispositivos Móveis => Limitações de
Hardware/Software
RAM
Cards – Alguns KB (4Kb – 128Kb)
 PDAs e Celulares – Alguns MB
 Smart

Memória estável
Cards – (128Kb – 1MB)
 PDAs e Celulares – (1MB – 512MB)
 Smart
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
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 problemas
 Sincronização
 Usabilidade
 Dentre
outros...
Desafios
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

Armazenamento
Armazenamento

Armazenamento Seqüencial
 Simplicidade
 Tuplas armazenadas

em seqüência;
Problemas
Consumo de espaço – valores de atributos
duplicados
 2. Ineficiente – Ausência de índices => busca
seqüencial
 1.

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
Valores
Relação R
v1
v2
v3
v4
Relação S
Armazenamento

Armazenamento por domínio
 Compactaçã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?
Armazenamento

Combinação Seqüencial + Domínio
 Valores
únicos => seqüencial;
 Valores < tamanho da palavra => seqüencial;
 Valores > tamanho da palavra => domínio
(simplifica gestão de memória)
Problema: estruturas de índices
Armazenamento

Armazenamento em anel
 Redução
de estruturas de índices;
 Formação de anel: valor => atributos => valor
 Semelhança com armazenamento por
domínio;
Armazenamento

Estrutura de índice em anel – Select Index
R.a
Indice em R.a
Valores
Relação R
v1
v2
v3
v4
Select Index
...
Where R.a=“v1”
Requisito de espaço para o índice: 1 apontador/valor
Armazenamento

Armazenamento em anel
 Overhead
de projeção – percorrer anel
Armazenamento

Estrutura de índice em Anel – Join Index
R.b
S.a
Relação S
Join Index
...
Where R.b=S.a
Relação R
Requisito de espaço para o índice: 1 apontador/valor
Armazenamento

Estrutura de índice em Anel
 Junções
efetuadas em Chaves
(freqüentemente)
 Chaves => armazenamento seqüencial;
Processamento de consulta
Processamento de Consulta

Problemas e Restrições
O
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ções
 Os
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 operadores
 Expressõ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óteses
 H1:
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
R2)
estrutura de dados: DataFlow (R1 e
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.