PicoDBMS: Scaling down Database
Techniques for the Smartcard
Christophe Bobineau, Luc Bouganin, Philippe
Pucheral, Pratick Valduriez
Ana Karina de Oliveira Rocha
1
Roteiro
• Motivação
• Problemática
• Desafios
• Armazenamento
• Custo de Armazenamento
• Processamento de Consultas
• Comentários Finais
• Referências Bibliográficas
2
Motivação
• Proliferação de dispositivos portáteis.
− Celulares
− PDAs
− Cartões inteligentes (Smart cards)
• Acesso de serviços independente da sua
localização física.
− Aplicações nas áreas de telefonia celular,
bancárias, de transportes, de saúde, de
identificação pessoal e de finanças.
3
Motivação
• Os cartões inteligentes são modernos e
seguros.
• Número cada vez maior de aplicações utilizam
cartões inteligentes.
• Os cartões inteligentes fornecem grande
mobilidade devido ao seu tamanho reduzido.
4
Motivação
• Vantagens dos cartões inteligentes:
− São bastante flexíveis.
− São recarregáveis.
− São multioperacionais.
• Quanto a forma de comunicação os cartões
inteligentes podem ser de dois tipos:
− Cartões com contato
− Cartões sem contato
5
Problemática
• Os Cartões inteligentes possuem
limitações computacionais.
− Possuem uma CPU.
− Memória RAM (4KB – 128 KB).
− Memória ROM – 96 KB.
− Memória EEPROM (128 KB – 1MB).
• Tempo de leitura rápido (60-100 ns)
• Tempo de escrita lento (10 ms/palavra)
6
Problemática
• Os cartões inteligentes possuem as maiores
restrições de recursos computacionais.
• As técnicas de banco de dados tradicionais
não podem ser diretamente aplicadas em
ambientes com recursos computacionais
limitados.
• Como baixar a escala das técnicas tradicionais
de banco de dados?
7
Problemática
• Técnicas tradicionais
− Armazenamento:
• Possuem várias estruturas de índices
• Possuem valores repetidos
− Consumo de memória
8
Problemática
• Técnicas tradicionais
− Processamento de Consultas
• Alto consumo de memória
• Armazenamento de resultados intermediários
• Materialização
• Estruturas temporárias guardadas na memória
− Ex: índices
9
Desafios
• Diminuir o espaço ocupado pelas
estruturas de dados (índices, tuplas,
etc.)
• Diminuir uso da memória RAM
• Diminuir as operações de escrita
• Aproveitar eficiência de operações de
leituras
10
Armazenamento
• Armazenamento Seqüencial (FS)
− Simplicidade
− As tuplas são 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.
11
Armazenamento
• Armazenamento por domínio (DS)
− Ausência de valores duplicados
− Uso de apontadores em atributos
Valores
v1
v2
v3
Relação R
v4
Relação S
12
Armazenamento
• Armazenamento em anel (RS)
− Redução das estruturas de índices
− Formação de anel: valor -> atributos ->
valor
− Semelhança com armazenamento por
domínio
13
Armazenamento
• Estrutura de índice em anel – Select
Index
Relação R
R.a
Indice em R.a
Valores
v1
v2
Select Index
...
Where R.a=“v1”
v3
v4
14
Armazenamento
• Estrutura de índice em Anel – Join Index
Relação R
R.b
S.a
Relação S
Join Index
...
Where R.b=S.a
15
Custo de Armazenamento
• Se os atributos não precisam ser
indexados a escolha deve ser feita entre
o FS e o DS. Caso contrário,
• A escolha deve ser feita entre por RS e
FS com índices tradicionais.
16
Custo de Armazenamento
• A Figura abaixo compara FS com DS
17
Custo de Armazenamento
• A Figura abaixo compara FS com RS
18
Processamento de Consultas
• Modelos tradicionais consomem muita
memória principal armazenando estrutura de
dados temporários e resultados intermediários.
• Quando a memória principal não é suficiente
eles recorrem a materialização para evitar
overflow de memória.
19
Processamento de Consultas
• Algoritmos tradicionais não podem ser usados
no PicoDBMS:
− 1. Lentidão da escrita na memória.
− 2. Não se pode estimar previamente o tamanho de
uma área específica de RAM a ser utilizada.
− 3. No estado da arte os algoritmos são bastante
sofisticados.
• No PicoDBMS - Código simples, compacto e
seguro.
20
Processamento de Consultas
• Para resolver estes problemas o
PicoDBMS propõe técnicas de consulta
que não utilizam nenhuma área de RAM,
nem escrevem na memória estável.
− 1. Consultas Básicas - Seleção, projeção e
junção
− 2. Consultas Complexas - Agregação,
ordenação e remoção
21
Processamento de Consultas
• No modelo tradicional o processo de
Consultas é feito em 2 passos:
− 1. O “otimizador” gera planos de otimização
de execução de consultas (QEP).
− 2 O QEP é executado para uma consulta
que implementa um modelo de execução e
usa bibliotecas de operadores relacionais.
22
Processamento de Consultas
• O “otimizador” pode usar diferentes
formas de QEP:
− 1. Árvore de profundidade à esquerda.
− 2. Árvore de profundidade à direita.
23
Processamento de Consultas
• Árvore de profundidade à esquerda
− Os operadores são executados seqüencialmente e cada
resultado intermediário é materializado.
24
Processamento de Consultas
• Árvore de profundidade à direita
− Os operadores são executados em pipeline evitando que
resultados intermediários sejam materializados.
25
Processamento de Consultas
• Problema: Eles requerem materialização em
memória para todas as relações da esquerda.
26
Processamento de Consultas
Básicas
• O PicoDBMS propõe usar somente pipeline em
todos os operadores. Ex: árvore de extrema
profundidade à direita.
27
Processamento de Consultas
Complexas
• Problema: Pipeline não é compatível com os
operadores de seleção e remoção de duplicatas, pois
classicamente os seus resultados intermediários são
materializados.
28
Processamento de Consultas
Complexas
• O picoDBMS explora duas propriedades:
•
•
1. Agregação e remoção de duplicatas podem ser
feitos em pipeline se: As tuplas de entrada já
estiverem agrupadas por valores distintos.
2. Operadores pipeline preservam a ordem desde
que eles consumam ou produzam tuplas na sua ordem
de chegada.
29
Processamento de Consultas
Complexas
• Existe um problema na solução proposta pelo
PicoDBMS:
− Para construir uma Árvore de extrema profundidade à direita
o processador de consultas do PicoDBMS viola uma heurística
para a otimização de consultas relacionais.
• PicoDBMS possui um processamento de consultas
dispendioso, manipulando uma maior quantidade de
dados e consumindo muito tempo no processamento
dos dados.
30
Considerações Finais
• Existência do Sql Java Machine - pequeno e
completo SGBD, menor que 8KB que fornece as
linguagens de definição de dados (DDL) e de
manipulação de dados (DML).
31
Referências
•
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.
• Pré-Calculo de Junções para Processamento Consultas em
Ambientes com Recursos Computacionais Limitados. Tathianne
Moreira Paulino. Orientador: Dr. Angelo Brayner. Dissertação de
Mestrado – UFC, 2004.
32