AJAX – Algoritmo de
Junção Adaptativo para
eXecução em ambientes
móveis
Monografia
Eriko Werbet
Unifor-CNPq
Motivação






Computação Móvel
Bancos de Dados + Mobilidade
Mobilidade + Restrições = Atraso
Técnicas Convencionais são Ineficientes
Processamento de Consultas Adaptativo
Definição de Operadores Adaptativos
Objetivos


Implementar um algoritmo de junção capaz
de executar operações de junção de forma
eficiente, num ambiente com suporte à
mobilidade.
Este algoritmo deve adaptar-se
dinamicamente às restrições do ambiente.
Mobilidade e Bancos de Dados





Ambiente de
Computação Móvel
Redes ad hoc
Mobilidade Física e
Lógica (Agentes)
Desafios
Soluções
Bancos de Dados Móveis



Autônomos
Heterogêneos
Distribuídos
A Arquitetura AMDB




Acesso a Bancos de
Dados Móveis
Comunidade de
Bancos de Dados
Móveis
Interoperabilidade
Agentes Móveis x
Estáticos
O Agente Executor




Acesso aos Membros da CBDM
Consultas
Coordenador do Protocolo 2PC
Operações de Junção
O Algoritmo AJAX

Adaptive Join Algorithm
for mobile
environments
eXecution





Simetria
Pipelining
Buckets Dinâmicos
Comparação
Progressiva
Prevenção de Estouro
de Memória
Simetria


Tratar as fontes de dados de maneira
independente, por meio de multithreading.
Evitar o bloqueio ou atraso na execução da
junção.
Buckets Dinâmicos




Comparação de buckets com o mesmo
“endereço” hash, em tabelas opostas.
Buckets com tamanho variável implicam em
mais flexibilidade, pois não precisamos tratar
bucket overflow.
Buckets podem acumular mais tuplas antes
de iniciar o probing.Melhor adaptação à
Comparação Progressiva.
Baixo overhead de manipulação.
Pipelining



Suprimento de tuplas para
operadores mais altos na
hierarquia da consulta.
Recebimento de tuplas de
operadores mais baixos.
Padrão recursivo implica
em pseudo-paralelismo na
execução da consulta, ou
seja, diminuição no tempo
de resposta.
Comparação Progressiva



Comparação cíclica dos
buckets.
Cada par de buckets é
comparado e somente o
conteúdo numa iteração “i”
é considerado.Tuplas
subseqüentes serão
comparadas numa iteração
“i + 1”.
Comparação e Hashing
contínuo das tuplas.
Last Probe Remembrance



Cada tupla do bucket
Alfa “lembra” a última
tupla do bucket Beta
(bucket oposto) que foi
comparada com ela.
Evita Duplicatas.
Evita Comparações
Desnecessárias.
Prevenção de Estouro de
Memória



A granularidade observada passa do nível de
bucket para o nível do sistema
computacional.
Monitoramento da memória do sistema.
Escolha de um ou vários pares de buckets
para descarregamento em disco.
Fases de Execução


Primeira Fase
Fase de execução
normal do AJAX



Segunda Fase
Executada quando
ocorre EOF ou quando
as fontes estão em
retardo.
O recebimento
continua, mas a
comparação passa a
usar buckets em disco.
AJAX em Pseudocódigo
1 thread de monitoramento EPSILON é iniciada em background;
2 thread de acesso à fonte de dados ALFA é iniciada; //simetria
3 se (operador depende de resultado parcial inferior) então
4
fonte BETA passa a ser o resultado parcial do operador inferior;
5 thread de acesso à fonte de dados BETA é iniciada;
6 iniciar geração da tabela hash para ambas as fontes; //dynamic bucket hashing
7 enquanto(não terminar o processamento) faça { //progressive probing
8 pegar próximo bucketAlfa;
9 localizar próximo bucketBeta pelo hashcode do bucketAlfa;
10 se (houver tuplas novas no bucketAlfa ou no bucketBeta) então {
11
se (a.UltimoProbe < b.Indice) então { //”a” é tupla de Alfa e “b” de Beta
12
adicionar o par (a, b) no resultado;
13
atualizar a.UltimoProbe; //last probe remembrance
14
se (existir operador superior na consulta) então
15
enviar tuplas parciais para o operador superior; //pipelining
16
}
17
se (EPSILON detectar a iminência de memory overflow) então { //overflow
18
escolher par de buckets que ocupa maior espaço de memória;
19
descarregar buckets escolhidos em disco;
20
}
21 se (as fontes atrasarem e houver buckets em disco) então { //segunda fase
22
comparar tuplas em disco [Alfa] com tuplas em disco [Beta];
23
comparar tuplas em disco [Alfa] com tuplas em memória [Beta];
24
comparar tuplas em memória [Alfa] com tuplas em disco [Beta];
25
comparar tuplas em memória [Alfa] com tuplas em memória [Beta];
26 }
27 }
28 }
Implementação do Protótipo




Linguagem Java
Threads simples
Função hash embutida etc
AMDB e Aglets
Estruturas de Dados




LinkedList
Tupla
Bucket
TabelaHash
Classes de Suporte




Ajax
FonteDados
Timer
TimerTask
Detalhes de Implementação





Desafios
Multithreading
Sincronização
Persistência
HashTable de Java




A Tabela Hash do AJAX
Encadeada
Buckets Dinâmicos
Deque (Deck)
Conclusão




AJAX garante:
Produção incremental de tuplas-resultado
Continuidade da execução da consulta
mesmo com fontes bloqueadas
Reação proativa em caso de estouro de
memória
Trabalhos Futuros




Testes comparativos
Aperfeiçoamento da Tabela Hash do AJAX
Definição de uma nova função hash
Pesquisa de estruturas de dados mais
adaptadas ao contexto do AJAX
Agradecimentos




CNPq
Angelo Brayner, Dr-Ing.
José de Aguiar, M.Sc.
A todos que tornaram este projeto possível!