Modelos e Tipos de Dados para
Banco de Dados Móveis
Equipe:
Aderval, Eudes, Ivanildo, Mozart, Pablo
Roteiro








Motivação
Conceitos
MOST
Modelo proposto por Bei Yi
Modelo para Rede de estradas
Tipos de Dados de BD Móveis
Conclusão
Referências
Motivação



Surgimento de Aplicações Móveis (Uso militar)
Interesse na possibilidade de capturar dados relativos
aos movimentos, cuja velocidade implicará em
aumento da taxa de transferência.
Exemplos: Fenômenos relacionados ao movimento
Motivação




Bancos de dados Espaço-Temporais são pouco
eficazes
Paradigmas de modelagem existentes são pouco
adequados
Linguagens de consultas existentes não possuem
operadores que exploram as novas possibilidades dos
objetos móveis
O modelo consiste em agrupar versão dos objetos
móveis em cada intervalo de tempo, formando assim a
sua trajetória
Conceitos

Objeto espaço-temporal: Atributos espaciais,
temporais e descritivos

Exemplos: Fazenda(Nome, Localização,
tempo);

Desafios: Complexidade em capturar,
armazenar e gerenciar grandezas envolvendo
Espaço e Tempo
Conceitos


Modelagem dependente da natureza dos objetos
Classificação: Forma de variação do espaço em
função do tempo
–
–
–
Continua: Modelagem de atributos através de um gráfico de
variação continua
Registro de Eventos: Variação de espaço em intervalos
discretos. Dados válidos apenas durante este intervalo
Mudança de Estado: Semelhante ao anterior, mas mantendo
a localização, mesmo fora dos intervalos do evento, até o
próximo evento ocorra
Conceitos

Objeto Móvel – qualquer objeto, pontual ou
com extensão, que muda sua posição
geográfica continuamente conforme o passar
do tempo.

Especialização de objeto espaço-temporal.

Ex : Táxi, Cardume de golfinhos.
Conceitos


Banco de Dados Móveis: Especialização de bases de
dados espaço-temporais
Problemas:
–
–
–
O número de registros cresceria muito se cada posição
exigisse o armazenamento um registro novo
A complexidade algorítmica dos operadores é muito maior
pois precisa considerar a continuidade do movimento.
Pode haver intervalo de tempo sem informação amostrada.
Isso pode apresentar ”lacunas”de informações, o que exige
técnicas de reconstituição da continuidade, usando técnicas
de aproximação como interpolação.
Modelo MOST
Modelo MOST



Moving Object Spatial Temporal.
Objeto Espacial - Coordenadas x, y, z
BD com atributos dinâmicos.
–
–
–
updatetime
value
function
Modelo MOST


Representação de estados do futuro.
DataBase History
–
–
Past Database History
Future Database History
Tipos de MOST Query

Consultas sobre o DataBase History:
Instantâneas

Contínuas

Persistentes

Instântaneas


Consulta avaliada em um tempo infinito
iniciando em um tempo t.
Presente
–

Ex : “Quais os supermercados que estão num raio
de 10 km da minha posição ?”
Futuro
–
Ex : “ Quais supermercados eu poderei chegar em
5 min.?”
Contínuas



Consulta contínua em t, é uma seqüência de
consultas instantâneas, uma para cada ponto
t’ >t.
Update explícito
Ex : “Quais supermercados vendem pão e
estão em um raio de 10 km?”
Persistentes


Seqüência de consultas instantâneas. Porém
estas consultas tem um mesmo tempo t inicial.
Persistentes x Contínuos
Modelo MOST

Vantagens:
–
–

Maioria dos casos o movimento permanece
uniforme.
Consultas sobre o futuro próximo.
Desvantagem:
–
–
Não Descreve a trajetória completa dos objetos
móveis.
Baseado em objetos pontuais.
Modelo proposto por
Claudia Medeiros
e
Bei Yi
Considerações do modelo

Tipos de objetos a serem modelados de
acordo com o comportamento temporal:
–
–
–

Estático
Temporal discreto
Temporal continuo
Atributos a serem consultados:
–
–
–
Descritivo ou convencional
Temporal
Espacial
Considerações do Modelo

Tipos de representação da trajetória:
–
–
–
Ponto
Linha
Polígono
Considerações do modelo


O que se consulta em um banco de dados de
objetos móveis?
Que dados de objetos móveis devem ser
guardados?
O que se consulta?

Consultas tradicionais em banco de dados
espaço-temporais:
–
–
No tempo t1 qual a localização do carro A?
Quando o carro A estava na coordenada (x1,y1)?
O que se consulta?
Existem outras necessidades de consulta:
 Relacionamentos entre um objeto móvel e um
estático.
–

Quando o carro A estava fora da área central
(demarcada pelo polígono X)?
Relacionamento entre dois objetos moveis.
–
No tempo t1, o carro A estava ao lado do carro B?
O que se consulta?
Existem outras necessidades de consulta:
 Estimativas sobre futuro.
–
–
Quando o carro A entrará na região central?
Qual o local provável de interseção das trajetórias
dos carros A e B?
Quais os dados armazenados?


Precisa-se armazenar a trajetória do objeto.
Trajetória é o registro do movimento,
mostrando a evolução da posição do objeto
indexado pelo tempo.
Quais os dados armazenados?

Por que armazenar os dados indexando pelo
tempo?
–

Dado um tempo, só existe um estado de
relacionamento espacial entre os objetos.
Qual o intervalo de tempo a se considerar?
Como tratar movimentos não uniformes?
–
Uma solução é dividir o percurso em intervalos
pequenos o suficiente para garantir movimento
uniforme nele.
Modelo proposto


Modelo orientado a objetos voltado a dados
vetoriais (geo-objetos).
Os objetos se relacionam, possuindo cada um
o seu estado (atributo) e comportamento
(métodos)
Modelo proposto
Modelo Proposto

Vantagens
–

Classes para representar os objetos e outras para
representar as trajetórias.
Desvantagens
–
–
O modelo não possui proposta de linguagem de
consulta.
Dificuldade de implementação devido ao alto grau
de abstração.
Modelo proposto para rede de
estrada – Serviço de Táxi
Serviço de táxi


Há uma grande variedade de aplicações que
manipulam objetos que se movimentam ao
passar do tempo. Porém, essas aplicações
geralmente são desprovidas de suporte a
banco de dados.
É um desafio projetar um modelo de banco de
dados para ser integrado a esses tipos de
aplicações.
Serviço de Táxi


Esses modelos precisam permitir o
armazenamento desses objetos como
entidades estruturadas e também permitir
consultas baseadas em sua estrutura espaçotemporal.
Apresentaremos um exemplo concreto de um
modelo para uma aplicação comercial que
utiliza objetos móveis.
Serviço de Taxi


Imagine um serviço de táxis que precisa saber
continuamente a localização de seus táxis e precisa
estar sempre otimizando o seu serviço.
Consultas possíveis:
–
–
–
–
Qual o táxi mais próximo a um dado endereço?
Quais táxis estarão ao menos a 5 km do endereço do cliente
nos´próximos 10 minutos.
As trajetórias de dois táxis A e B se cruzaram nas últimas 2h?
Assumindo que se sabe antecipadamente as trajetórias, dois
táxis A e B estarão a menos de 2 km em algum momento, nos
próximos 30 min?
Serviço de Táxi


A co-existência de atributos espaciais e
temporais nesse sistema tornam o
processamento de consultas um desafio.
O modelo proposto para suportar esse tipo de
problema vai ser descrito a seguir e foi
construído através da extensão das
tecnologias de banco de dados existentes.
Serviço de Táxi - Modelo


A informação inicial é a representação da rota
entre dois pontos da cidade. Cada ponto é
representado por uma coordenada (x,y) e a
rota entre dois pontos é uma polilinha que é
representada como uma seqüência de
coordenadas: (x1,y1), (x2,y2),...,(xn,yn).
Dessa forma, o mapa da cidade é
representado como um grafo não direcionado.
Serviço de Táxi - Modelo

Trajetória:
–
–
–
É a combinação da rota do objeto com o tempo que
esse objeto se encontrará em cada ponto da rota.
Essa rota é especificada pelo endereço ou ponto
inicial (x1,y1), o endereço ou ponto final (xn,yn) e o
tempo inicial t.
Uma rotina externa deve calcular o custo (caminho
ou tempo) mínimo entre esses dois pontos.
Serviço de Táxi - Modelo


A Trajetória T(o) de um objeto o, é especificado por
uma relação, cujas tuplas são denotados por [i, (x,y), ti,
b], onde (x,y) é o i-ésimo ponto intermediário na rota
L(o) do objeto o e o estará lá no tempo ti. Como uma
trajetória T(o) pode representar mais de uma viagem,
pode-se adicionar um atributo b, que diz se esse ponto
é um início de uma nova viagem ou não.
CREATE TYPE trajetoria AS OBJECT (sequence#
integer, x integer, y integer, ti real, b boolean)
Serviço de Táxi - Modelo
Serviço de Táxi - Modelo


CREATE TYPE objeto_movel AS OBJECT
(object_id integer, T trajetoria, cor integer, peso
integer, motorista pessoa_id)
É necessário, também, uma função que
retorne a distância percorrida entre dois pontos
quaisquer da trajetória e outra que retorne o
tempo entre eles. Essas duas funções
pertencem ao tipo objeto_movel.
Serviço de Táxi - Modelo
SELECT LOC(id, t) | WHEN_AT(id, location-L) |
<other attributes of T or moving objects relation>
FROM T
WHERE id WITHIN (DISTANCE s | TRAVELTIME t) FROM R
[(ALONG EXISTING PATH) | (ALONG SHORTEST PATH) ]
[(ALWAYS BETWEEN) | (SOMETIMES BETWEEN) starttime AND
endtime]
Serviço de Táxi - Modelo




LOC(id,t)
WHENAT(id, location-L)
WITHIN (DISTANCE s | TRAVELTIME t) FROM R –
retorna true se o objeto precisa alcançar R em no mínimo s
ou t.
Quantificadores para refinar WHITIN:
–
–
ALONG EXISTING PATH and ALONG SHORTEST PATH
ALWAYS BETWEEN and SOMETIMES BETWEEN starttime
AND endtime
Tipos de Dados de BD Móveis
Data Reduction


Técnica para otimizar o acesso / armazenamento /
processamento / transmissão de dados em
dispositivos móveis
Estratégias:
–
–
–
–
–
–
Abstração
Projeção
Seleção
Ordenamento
Substituição de dados / Tipos
Técnicas híbridas
Substituição de Tipos


Quanto mais complexo o tipo, mais recursos
ele vai demandar para acesso /
processamento / armazenamento /
transmissão
Quanto maior a diversidades de tipos, maiores
e mais complexas terão que ser as APIs
(espaço e processamento suficientes?)
SQL Server x SQL CE
binary
Binary (<=510), Image (>510) *
char
Nchar (<=255), ntext (>255) *
Varchar
Nvarchar (<=255), ntext (>255) *
SmallDateTime
DateTime **
SmallMoney
Money **
VarBinary
VarBinary (<=510), Image (>510) *
* Podem acontecer falhas na sincronização por causa de tamanho de campo
** Podem acontecer falhas na sincronização por causa de precisão
Oracle 9i x Oracle 9i Lite
1B
2B
4B
FLOAT
DATE
TIME
DOUBLE
LONGVARBINARY
VAR
CHAR
INTEGER
X
X
X
X
X
-
-
-
VARCHAR2
-
-
-
-
-
-
-
X
VARCHAR
-
-
-
-
-
-
-
X
CHAR
-
-
-
-
-
-
-
X
SMALLINT
X
X
X
X
X
-
-
-
FLOAT
X
X
X
X
X
-
-
-
DOUBLE
PRECISION
X
X
X
X
X
-
-
-
NUMBER
X
X
X
X
X
-
-
-
DATE
-
-
-
-
-
X
-
-
LONG RAW
-
-
-
-
-
-
X
-
BLOB
-
-
-
-
-
-
X
-
Conclusão



Os modelos para banco de dados móveis
estão sendo cada vez mais necessário.
Os desafios são grandes.
Existe grandes dificuldades em se encontrar
modelos bem detalhados.
Referências


A.P.Sistla, O.Wolfson , S.Chamberlain and
S.Dao. Modeling and querying moving objects.
In Proc. IEEE Intl. Conf. On Data Engeneering,
pages 422–432, Birminghan, UK, 1997.
Yi, B. and Medeiros, C.Bauzer. Um modelo de
Dados para Objetos Móveis. In IV Simpósio
Brasleiro de GeoInformática, pages 33-40,
2002.
Referências


AVazirgiannis, M. and Wolfson, O. A
Spatiotemporal Model and Language for Moving
Objects on Road Networks.
Wolfsony, O. Chamberlainx, S. Xuz, B. Jiang L.
Moving Objects Databases: Issues and
Solutions
Referências

Small Database Answers for Small Mobile Resources
–

Data Reduction an Adaptation Technique for Mobile Environments
–

http://www.oracle.com/technology/tech/wireless/papers/q402/Oracle_Lite_wp11-02.pdf
Oracle 9i Lite Developers Guide for Windows CE
–

http://citeseer.ist.psu.edu/120366.html
Oracle 9i Lite: A technical White Paper
–

http://citeseer.ist.psu.edu/lubinski00small.html
http://download-east.oracle.com/docs/html/A95913_01/toc.htm
SQL CE Supported DataTypes and Mappings
–
http://msdn.microsoft.com/library/default.asp?url=/library/enus/sqlce/htm/_lce_accessing_data.asp