Banco de Dados Móvel
traduzidos / ampliados / adaptados de:
Vijay Kumar
Computer Sc. Telecommunications
University of Missouri-Kansas City
5100 Rockhill Road
Kansas City, MO 64110, USA
[email protected]
Índice



Introdução: O Problema
Parte I: Comunicação com Redes
sem Fio
Parte II: Sistemas de Gerência de
Banco de Dados Móvel
O Problema


Trata-se da gerência de dados em um sistema
em que processadores e o banco de dados, ou
partes dele, movem-se através de um espaço
geográfico
Deseja-se permitir que usuários de telefones
celulares tenham acesso a dados persistentes,
de qualquer lugar

Esforço conjunto de pesquisadores de
comunicação sem fio e BD para a gênese de uma
nova área de pesquisa




Mobile Database Systems (MDS)
Pervasive Computing
Nomad Computing
Anywhere Anytime Computing
O Problema

Deve-se chamar a atenção para a
imaturidade da pesquisa

Modelos de transação para BD móvel
 Mecanismos de controle de concorrência
 Protocolos de recuperação de falhas


Dados dependentes de localização
Entretanto, há claras indicações de que,
em um futuro próximo, os resultados
estarão disponíveis nos produtos
comerciais

Tecnologia de BD móvel consolidada 
pletora de aplicações
Comunicação com Redes Sem Fio





Espaço de Informação Totalmente
Conectado
Rádio-Frequência e Banda
Comunicação Celular
Arquitetura de Sistema de
Comunicação Celular
Soluções para a Comunicação
Celular
Espaço de Informação
Totalmente Conectado
Espaço de Informação
Totalmente Conectado
 Cada nó do espaço de informação tem alguma
capacidade de comunicação
 Alguns nós podem processar informação
 Alguns nós podem se comunicar através de sinal
de voz
 Alguns nós podem fazer ambas as coisas
Espaço de Informação
Totalmente Conectado
 Criação e Manutenção
Integrando SGBDs legados, e sistemas celulares
com / sem fio
PCS: Personal Communication System
Transmissões analógica e digital
América do Norte
GSM: Global System for Mobile
Communication
Transmissão digital
Europa
Rádio-Frequência e Banda
 Comunicações sem fio utilizam ondas
eletromagnéticas


Banda: uma faixa de RFs – unidade: M(G)Hz –
utilizável para uma tarefa particular



O comprimento da onda é determinado pela rádiofrequência (RF)
Transmissão de dados ou voz
Mais alguma coisa
Faixas típicas: 800 MHz – 3 GHz



Refletidas facilmente por objetos fixos (p.e., edifícios) ou
móveis (p.e., carros), etc.
O sinal de absorção é forte
Reuso de RF
Rádio-Frequência e Banda
Item
Mobile
Phones
Europe (MHz)
NMT: 453-457, 463-467
GSM: 890-915, 935-960,
1710-1785, 1805-1880
Cordless CT1+: 885-887, 930-932
Phones
CT2: 864-868
DECT: 1880-1900
US (MHz)
Japan (MHz)
AMPS, TDMA, CDMA
824-849, 869-894
GSM, TDMA, CDMA
PDC: 810-826
940-956,
1429-1465,
1850-1910, 1930-1990
1477-1513.
PACS
1850-1910,1930-1990;
PHS
1895-1918;
PACS-UB: 1910-1930
JCT: 254-380
NMT:
Nordic Mobile Telephone
PDC:
Pacific Digital Cellular
PACS:
Personal Access Communications System
PHS:
Personal Handyphone System
PACS-UB: PACS Unlicensed Band
JCT:
Japanese Cordless Telephone
(Taken from Mobile Communications by Jochen Schiller)
Rádio-Frequência e Banda
 Não há RF que possa transportar dado ou voz a
longa distância sem sérios problemas de
enfraquecimento do sinal
 Solução

Divisão da área de cobertura em células (móveis)


Intensidade do sinal aproximadamente constante
Reuso de RF através das células móveis
Comunicação Celular
Células móveis
Metropolitan area
Metropolitan area
BS
Base Station
Coverage area in one cell
BS
BS
Coverage area in three cells
Large cells.
Low density
Small cells.
High density
Smaller cells.
Higher density
Comunicação Celular
Frequency reuse
A
2
7
3
7
4
6
1
6
5
A
2
2
3
1
4
5
D7
3
1
6
A
A
A
4
5
A
A
D
 3N
R
D = distance between cells using the same frequency
R = cell radius
N = reuse pattern (the cluster size, which is 7).
Thus, for a 7-cell group with cell radius R = 3 miles, the frequency reuse
distance D is 13.74 miles.
Arquitetura de Sistema de
Comunicação Celular
PCS
Mobile
Host
Mobile
Host
Wireless radio cell
Fixed
Host
Base
Station
Fixed
Host
Mobile
Host
Fixed Network
Base
Station
Mobile
Host
Wireless radio cell
Mbps to Gbps
Fixed
Host
Wireless LAN cell
Base
Station
Fixed
Host
Arquitetura de Sistema de
Comunicação Celular
 Dois conjuntos distintos de entidades
 Mobile Host (MH) – também chamados de
clientes móveis
 Fixed Host (FH)
 Alguns FHs são estações de base (Mobile
Support Stations)
 Cada MH se comunica com uma estação de base
via um canal sem fio
 Célula – área coberta por uma estação de base
 Tipicamente, o servidor de banco de dados (BD)
reside em um FH via uma interface com fio

Confundiremos BD com FH
Arquitetura de Sistema de
Comunicação Celular
 Especificades dos ambientes de computação
móvel

Largura de banda assimétrica

FH tem mais capacidade de comunicação do que MH
 Freqüentes desconexões

MHs não podem se manter conectados à rede todo o
tempo
 Limitações de energia

MHs usam baterias, basicamente
 Economia de energia é um imperativo
Arquitetura de Sistema de
Comunicação Celular
BS
MH
MH
Arquitetura de Sistema de
Comunicação Celular
 MH transmite a 825.030 MHz e BS transmite
a 870.030 MHz
 O canal de separação é 45 MHz
 Cada canal de voz tem uma banda de 30
kHz
 Conectividade MH – FH

Conectividade contínua

O MH é continuamente conectado ao FH
– Exemplo: meu laptop (MH) e o servidor Anjinho
Arquitetura de Sistema de
Comunicação Celular
 Modo


Desconectado
O MH voluntariamente se desconecta do FH e
continua a processar localmente. Em um
tempo fixado, ele se conecta de novo
Conectividade intermitente

Como o desconectado, mas a desconexão
pode partir do FH, e não há fixação de tempo
para a conexão
Estes modos de conexão têm pesada influência na
gerência de transações móveis
Arquitetura de Sistema de
Comunicação Celular
Mais detalhes:
PSTN
AC
HLR
VLR
MSC (MTSO)
MSC (MTSO)
EIR
MS
BS
MS
Wireless component
PSTN: Public Switched Network.
MSC: Mobile Switching Center. Also called MTSO
(Mobile Telephone Switching Office).
BS:
Base Station.
MS:
Mobile Station. Also called MU (Mobile Unit)
or Mobile Host (MH).
HLR: Home Location Register.
VLR: Visitor Location Register.
EIR:
Equipment Identify Register.
AC:
Access Chanel.
Arquitetura de Sistema de
Comunicação Celular
MSC
PSTN
Soluções para a Comunicação
Celular

Como manter uma comunicação contínua entre
duas células em presença de mobilidade?
Solução: Handoff

Como localizar MH em uma célula?
Solução: Gerência de Localização

Como gerenciar uma comunicação contínua
entre duas células em presença de mobilidade?
Solução: Roaming
Soluções para a Comunicação
Celular
Handoff
Um processo que garante a continuidade da transmissão
quando um usuário quebra a conexão com uma BS e
estabelece uma conexão com outra BS
MSC
MSC
New BS
Old BS
Old BS
MSC
MSC
Old BS
New BS
New BS
Old BS
New BS
Soluções para a Comunicação
Celular
Handoff
Para manter a conversação, o procedimento Handoff
deve ser completado enquanto o MH (o ônibus) estiver na
região de superposição das células
Cell overlap region
G
Old BS
New BS
Soluções para a Comunicação
Celular
Gerência de Localização
HLR: Home Location Register
Um HLR armazena o perfil do usuário e sua
localização geográfica – célula corrente
VLR: Visitor Location Register
O VLR de uma célula armazena o perfil do
usuário e a localização corrente do usuário
que vai visitar a célula
S-LS: Source Location Server
D-LS: Destination Location Server
Soluções para a Comunicação
Celular
5
R-ID
LS Address
1
2
D-LS
HLR
4
9
8
6
VLR
3
S-LS
R-ID
Base Station
100
200
D-BS
7
D-LS
10
2
Dest. BS
Source BS
1
Chamador
Chamado
Soluções para a Comunicação
Celular
MH1 se comunica com MH2
Cell 1
Cell 2
MU1
MU2
Soluções para a Comunicação
Celular
Algoritmo de Localização
P1. O chamador disca um número. Para encontrar a
localização do chamado (destino), o chamador
consulta a S-BS (1)
P2. A S-BS envia a consulta ao S-LS (2)
P3. S-LS primeiro procura o VLR (3). Se o chamado
é um visitante da S-LS, a conexão é feita
P4. Se VLR falha, então a consulta é enviada ao
HLR (4)
P5. HLR encontra a localização de D-LS (5)
Soluções para a Comunicação
Celular
P6. A procura agora passa para o D-LS (6)
P7. D-LS encontra o endereço de D-BS (7)
P8. O endereço da D-BS é enviado ao HLR (8)
P9. HLR envia o endereço da D-BS ao S-LS (9)
P10. O endereço da D-BS é enviado à S-BS (10)
Soluções para a Comunicação
Celular
Roaming (verbo Roam: vagar, perambular)
Assegura as políticas (ou restrições) administrativas
e técnicas
Soluções para a Comunicação
Celular
Roaming
Políticas Administrativas

Faturamento

Acordo de subscrição

Perfil do usuário

Outras políticas
Soluções para a Comunicação
Celular
Roaming
Restrições Técnicas

Incompatibilidade de largura de banda. Por
exemplo, a banda de 900 MHz não é disponível
em várias partes do mundo. Isto pode impedir
o uso de certos equipamentos

Padrões de comunicação entre provedores de
serviço

Restrições de MH

Outras
Sistemas de Gerência de Banco
de Dados Móvel

Sistemas de Computação Móvel

Sistemas de Banco de Dados Móvel

Sistemas de Gerência da Banco de
Dados Móvel

Arquitetura

Gerência de Dados

Gerência de Transação

Recuperação

Conclusões
Sistemas de Computação Móvel
 Computação móvel é associada com
mobilidade de usuários, hardware, dados e
software em aplicações de computador
 Classe especializada de sistemas de
computação distribuída em que alguns nós
podem mover-se dentro de um espaço físico
ou lógico, (des)conectando-se de maneira ad
hoc
Sistemas de Banco de Dados
Móvel
O que é um sistema de banco de dados móvel
(MDS: Mobile Database Systems)?
Um sistema de computação móvel com as seguintes
propriedades estruturais e funcionais

Sistema distribuído com conectividade intermitente
 MHs e FHs

Um MH é um SGBD à part entière

Completa mobilidade espacial

Construído sobre plataformas PCS/GSM

Capacidade de comunicação com / sem fio
Sistemas de Banco de Dados
Móvel
Objetivos
Construir um sistema de processamento de informação
verdadeiramente ubíquo, mesmo com as restrições
inerentes às arquiteturas sem fio
Sistemas de Gerência de Banco
de Dados Móvel
Mobile Database Systems
 Oracle Lite
 IBM DB/2 Everyplace
 Sybase Anywhere
 Versões MS Access e MS SQL Server
para plataformas móveis
 MS
Windows CE
Sistemas de Gerência de Banco de
Dados Móvel
Aplicações

Companhias de seguro

Serviços emergenciais (polícia, assistência médica,
etc.)

Controle de tráfego

Serviço de taxi

E-commerce

Etc.
Arquitetura
Application-transparent Adaptation
Applications
Mobile
File
Server
DBMS
APIs
DBMS Proxy
Mobile SGBD APIs
Mobile Host
Adaptado de: J. Jing, A. Helal e A. Elmagarmid
Fixed Network
Arquitetura
Application-transparent Adaptation
Web Server
(or Proxy Server)
Web Browser
HTTP
(TCP/IP)
Web Client
Side Intercept (CSI)
Mobile Host
TCP/IP Connection
Web Client
Side Intercept (CSI)
Fixed Network
http://www.dsc.ufcg.edu.br/~sampaio/cursos/2007.1/BancoDeDados/TopicosDaDisciplina/5-BDMoveis/LeituraAdicional/MobileEnvironments.pdf
Gerência de Dados

Objetivos

Categorização de Dados

Caching de Dados

Difusão de Dados

Processamento de Consultas
Objetivos
 Como melhorar a disponibilidade de dados
para as consultas dos usuários, em presença
de bandas de RF limitadas e de mobilidade?
 Possibilidades

Caching de dados



Cashing semânticos: o conteúdo é decidido por
resultados de consultas passadas
Difusão de dados (data broadcast) em canais sem
fio
Suporte a consultas dependentes de localização
Categorização de Dados
 Dados dependentes de localização (Location-
Dependent Data (LDD)): classe de dados
com valores estreitamente ligados a uma
localização geográfica específica.


Exs: CEP, Código DDI, Aeroporto
Contra-exemplos: Nome de rua, Número de
identidade (Location-Independent Data (LID))
 Processamento de dados convencional: LID
Categorização de Dados
 Consulta Dependente de Localização (Location-
Dependent Query (LDQ)): LDD leva a LDQ: depende
da origem da consulta, ou o processamento da
consulta depende da mobilidade



Exemplo: Qual a distância (daqui) para o aeroporto João
Suassuna?
Qual é o valor do CEP (onde estou)?
Qual é o valor do DDI (onde estou)?
 Em consultas LDQ, a posição do LDD concernente e
da origem da consulta devem ser conhecidas

Existem provedores de serviço que oferecem facilidades de
descoberta de localização
Categorização de Dados
 Location-Aware Query: não depende da
origem da consulta, ou o
processamento da consulta não
depende da mobilidade
 Exemplo:
Qual a distância entre Rio de
Janeiro e São Paulo?
Categorização de Dados
 Distribuição
de Dados Dependente de
Localização

Um hotel tem filiais em todo o Brasil. Os
serviços em cada filial são idênticos, mas os
valores dependem da localização
Categorização de Dados
 Dados
em uma região não podem ser
replicados em outra região, como é
comum em BDs distribuídos tradicionais
Célula
Alto Branco
Prata
Categorização de Dados
 Exemplo:
Quais restaurantes se situam
próximo de onde estou?
Se estiver no Alto Branco, a resposta é uma
 Se estiver na Prata, a resposta é outra
 Note que, em nenhum momento, é exigido do
usuário que indique seu bairro

Categorização de Dados
LDD: Hierarquia de Localização
Em uma dada região, a localização dos dados
pode ser definida hierarquicamente
City data
County 1 data
Subdivision 1 data
County 2 data
Subdivision data
County n data
Subdivision m data
Caching de Dados
 Clientes móveis (MHs) têm acesso a
servidores de BD fixo (FH), via um canal sem
fio
 Caching de dados são importantes para
melhorar a disponibilidade dos dados e o
desempenho das consultas


Limitada largura de banda dos canais sem fio
Instabilidade das redes sem fio
 Caches convencionais requerem estabilidade
da rede e bandas largas
Caching de Dados
 Uma nova abordagem de caching
 A estratégia
de substituição de dados é
baseada em padrões de acesso, em vez
dos esquemas o menos recentemente
usado ou o mais recentemente usado
Difusão de Dados
 O Princípio
 Um
conjunto de dados frequentemente
usados é disponibilidado por difusão
contínua de FHs, em alguma RF fixa
 MHs sintonizam a frequência e baixam os
dados para os seus caches locais
Difusão de Dados
 Como um MH acessa um BD fixo?
 A abordagem mais aceita é
broadcasting, ou push-based
 Mas a abordagem sob demanda, pullbased, cresce de interesse
 Abordagem híbrida

Conseqüência lógica das duas outras
abordagens
Difusão de Dados
 Flat Broadcasting
Dados do FH são repetidamente difundidos
através de um canal de difusão (broadcast
channel)
 O canal torna-se um ‘disco’ (file on the air)


O disco pode ser indexado
MHs podem recuperar seus dados do ‘disco’
 O tempo médio de espera por um ítem é
constante

Difusão de Dados
D
C
B
E
A
server
B
C
D
A
E
Difusão de Dados
 Pull-Based Broadcasting
 Somente
dados solicitados aparecerão
como ‘dados no ar’
Difusão de Dados
 Abordagem Híbrida
 Mistura
tanto push como pull
 Usuários enviam pedidos se os dados não
se encontram nos ‘discos’
Difusão de Dados
 Independentemente da Abordagem
 Clientes
podem economizar bateria se
conectando somente quando dados que
lhes interessam são difundidos
 Um catálogo de dados é difundido m vezes
toda vez que há uma difusão de dados
Difusão de Dados
 Difusão
de dados em diferentes
freqüências, segundo suas relevâncias
 Hierarquia de memória multi-nível
 Dados quentes são difundidos mais
frequentemente que dados frios
 Dados com freqüência de acesso similar
são agrupados dentro dos ‘discos’
Processamento de Consulta
Modelo de Dados: Padrão Relacional, SQL
Esquema de Dados: a diferença, agora, é que,
para uma dada classe, pode haver valores
dependentes de localização
O MDS deve oferecer a função location binding ou
location mapping
Processamento de Consulta
Situação: Uma pessoa viajando de carro deseja
saber seu progresso e continuamente se faz a
mesma pergunta.
Cada vez,
a resposta é
diferente porém correta
Requisitos: Contínua monitoração da latitude e
da longitude do local de origem da consulta. GPS
pode fazer isso
Gerência de Transação
 Transações Clássicas ACID
 Workflow
 Um Modelo de Transação Móvel
 Execução de Transação Móvel, Segundo o
Modelo
 Controle de Concorrência
Transação Clássica ACID
 Atomicidade
 Tudo ou nada
 Consistência
 Uma transação é uma transição entre dois estados
consistentes do BD, por hipótese
 Isolação

Toda transação vê os dados como se ela fosse
processada sozinha
 Durabilidade

Se uma transação é validada, seus efeitos devem
ser refletidos no BD
Transação Clássica ACID
 As propriedades ACID garantem
 A validação de uma transação em sua totalidade,
ou
 Tudo de passa como se a transação nunca tivesse
existido
 Nada melhor para garantir a consistência do
BD
 Mas só são aceitáveis se a duração da
transação for curta
Workflow
 Propriedades ACID são muito rígidas para
MDS

Transações interativas, ou de duração longa

Workflow
– Várias partes, ou fragmentos, com ordem parcial
 Necessidade de flexibilizar


Validação de partes da transação, ou validação parcial
As partes não validades são como se nunca tivessem
existido
Workflow
Exemplo de Workflow
Reserva de Hotel
Reserva de Restaurante
Reserva de Teatro
Se não puder reservar um teatro, eu posso me
contentar com o hotel e o restaurante
Só hotel, ou só restaurante, não serve
Um Modelo de Transação Móvel
 Cenário de Execução
 Um usuário lança uma transação (workflow) de seu MH
 Os resultados finais voltam para o MH
 A transação do usuáro não precisa ser completamente
executada no seu MH

Fragmentada e distribuída entre FHs e outros MHs
– Execução distribuída de uma transação móvel
 Exemplo: workflow de viagem
 Passagens no MH que lançou a transação
 Hotéis em um FH
 Restaurantes em outro FH
 Teatros em outro MH
Um Modelo de Transação Móvel
Uma transação móvel pode ser definida como
T é uma tripla <F, L, FLM>, em que
F = {e1, e2, …, en} é um conjunto de fragmentos da
transação,
L = {l1, l2, …, ln} é um conjunto de localizações, e
FLM = {flm1, flm2, …, flmn} é um conjunto de
funções de mapeamento de fragmento para
localização, isto é, j, flmi (ei) = li
Um Modelo de Transação Móvel
Uma execução do fragmento ei é uma ordem parcial eij =
{j, j} em que

j = OSj  {Nj} em que OSj = kOjk, Ojk {read, write},
e Nj  {Abort, Commit}

Para quaisquer Ojk e Ojl com Ojk = R(x) e Ojl = W(x)
para um objeto x, então ou Ojk j Ojl ou Ojl j Ojk
Um Modelo de Transação Móvel
 Hipóteses do Modelo
 Transação de longa duração

Pode ser dividida em sub-transações, com ordem parcial
– Workflow

Sub-transações podem ser executadas em
diferentes MHs e FHs
 Uma operação merge em um FH reúne os efeitos
das sub-transações
 Validações parciais, no nível de sub-transação
são aceitáveis

Critérios de validação explicitamente definidos
Execução de Transação Móvel
DBS1
DBS2
T2(e4, e 5)
MU1
MU3
T1(e1, e 2, e 3)
MU2
DBS4
DBS3
Execução de Transação Móvel
 Cópias primárias: FHs
 Cópias secundárias (cached) mantidas
em MHs
 A tolerância a falhas incorpora o
‘desaparecimento’ de MHs
Controle de Concorrência
Objetivo:
Garantir a propriedade de Isolação (I) das
transações móveis
Controle de Concorrência
 Um MH lê e atualiza dados de seu cache
local, baixados de um FH

O que fazer para garantir a consistência do FH, se
os dados locais são atualizados durante uma
desconexão – problema de consistência de dados
--?
 Vários critérios para consistência baseiam-se
na seriação das atualizações do BD
 Controle
de concorrência para assegurar a
propriedade de isolação das
(sub)transações dos clientes móveis
Controle de Concorrência
Métodos convencionais de
execuções concorrentes


seriação
de
Métodos Pessimistas

Bloqueio em duas fases (Two-phase
locking)

Timestamping
Métodos otimistas
Controle de Concorrência
Problemas

Sobrecarga de mensagens (com / sem fio)

Lidar eficientemente com desconexões é
muito difícil

Em caso de bloqueio, a gerência
bloqueios distribuídos é muito complexa
de
Controle de Concorrência
Um requisito importante para MDS: um número
mínimo de mensagens trocadas, especialmente
mensagens sem fio
Métodos otimistas
Deixa a consistência para depois, na
esperança de que tudo dê certo
Se não der certo?!
Transações de compensação
Validação de Transações Móveis
Os clássicos 2-phase commit (2PC) e 3-phase
commit (3PC) não são adequados
Muitas mensagens trocadas durante o
processo de validação de transação
distribuída
Um esquema que use poucas mensagens,
especialmente em meio sem fio, é sumamente
necessário
Conclusões
Redes sem fio estão se tornando uma plataforma de
comunicação muito usada. Elas oferecem um modo
mais barato de se conectar e, em alguns casos, elas
são a única forma de tornar ubíqua a computação
Entretanto, muitos problemas complexos devem ser
resolvidos, para que os MDS possam ser
efetivamente úteis
Esta visão geral discutiu alguns desses problemas,
e identificou algumas possíveis abordagens