Bancos de Dados Espaciais
Mestrado em Engenharia de Computação:
área de concentração Geomática
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
1
Bibliografia...
• Robert Laurini and Derek Thompson. Fundamentals of Spatial
Information Systems. Academic Press Inc, 1992.
• Martien Molenaar. An Introduction to the Theory of Spatial
Object Modelling for GIS. Taylor and Francis Ltd., 1998.
• Oracle Documentation Library. Oracle8i interMedia, Spatial,
Time Series, and Visual Information Retrieval Options, Release
8.1.6.
• Graeme F. Bonham Carter. Geographic Information Systems for
Geoscientists: Modelling with GIS. Pergamon Press. 1994.
• Peter a Burrough and Rachael A, McDonnell. Principals of
Geographical Information Systems. Oxford University Press,
1998.
• Elmasri R., Navathe, S.B. Fundamentals of Database Systems,
Redwood City: Benjamin/Cummings, 1994.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
2
Bibliografia
• Papers diversos
• Internet hyperlinks
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
3
Escopo...
 Geomática
– Sistemas de Informação Espaciais (SIE)
– Usos dos SIE
•
•
•
•
•
•
•
•
•
UERJ - Março 2001
Cadastro (IPTU, ITR, etc.)
Marketing
Meio Ambiente
Agricultura
Empresas de Infra-Estrutura (Energia Elétrica, Gás, Telefonia,
Petróleo, etc,)
Planejamento Urbano
Transporte
Arqueologia
Computer Aided Design...
© Oscar Luiz Monteiro de Farias
4
Escopo...
 Tipos de Problemas Espaciais
 O que se encontra em uma localização particular?
 Aonde se encontra um dado objeto ?
 Realizar medidas de objetos em um dado espaço
 Identificar relações espaciais
 Encontrar uma área que satisfaça determinados requisitos
 Inferir a forma de objetos não diretamente observáveis
 Modelos espaciais preditivos
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
5
Escopo...
 Categorias de problemas espaciais
 Movimentos ou fluxos (migração populacional, massas de ar, etc.)
 Networks (rodovias, ferrovias, distribuição de água, telefonia, etc.)
 Nodos (intersecção de linhas férreas)
 Hierarquias e ordenamento de áreas em termos de funções
econômicas
 Campos ou superfícies (ex. área de circulação de jornais e revistas,
de alcance de determinados artefatos bélicos, etc.)
 Difusão de doenças, idéias ou inovações
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
6
Escopo...
 Alguns Problemas Locacionais:
 localização de entidades pontuais (centro comerciais, hospitais, etc.)
 Alocação de recursos de um ponto a outro (ex. de campos de
petróleo para refinarias...)
 Roteamento (dados dois pontos em uma rede, um inicial e outro
final, encontrar um trajeto entre eles)
 Descoberta de trajetórias entre dois pontos (no sentido de evitar
obstáculos, p.ex.)
 Encontrar áreas que atendam a determinadas especificações
 Layout (urbanismo)
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
7
Sistemas de Informação Espaciais
Banco de Dados
Espaciais (BDE)
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
8
Níveis de Modelagem de Dados
Disciplinas Aplicativas
Modelagem Espacial
Teoria da
Geo-Informação
Modelagem Conceitual
Modelagem Lógica
Modelagem Física
Ciência da Computação
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
9
Representação de Objetos...
Intensão X Extensão
• Extensão - todos os dados pertencentes ao objeto são
armazenados
• Intensão - i) armazenamento de alguns elementos de dados
privilegiados do objeto;
ii) especificação de uma regra para gerar todos os possíveis
elementos do objeto;
iii) Definição de uma regra para testar se um elemento é
membro do objeto.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
10
Representação de Objetos...
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
11
Spatial Queries...
• Uma Consulta Espacial está relacionada aos atributos
geométricos dos objetos espaciais.
• Tipos de spatial queries:
–
–
–
–
point query
window query
nearest neighbor
spatial join
• Window query: o conjunto resposta consiste de todos os
objetos cujos componentes geométricos superpõem-se a
uma dada janela retangular.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
12
Spatial Queries...
• Spatial Join: É definido sobre duas ou mais relações.
Computa um subconjunto do produto cartesiano. Combina
objetos espaciais destas relações, de acordo com seus
atributos geométricos, i.e., estes atributos devem satisfazer
um predicado espacial.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
13
Spatial Queries...
• A operação relacional  - join de duas relações A e B nas
colunas i e i, denotada por AiJ
B, combina aquelas
tuplas em que a i-ésima coluna de A e a j-ésima coluna de
B satisfazem predicado .
• Um join AiJ
B é chamado um spatial join, se a i-ésima
coluna de A e a j-ésima coluna de B são atributos espaciais
e se  é um apredicado espacial.
• Um spatial join computa um subconjunto do produto
cartesiano das relações A e B.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
14
Bancos de Dados Espaciais (BDEs)
São sistemas de banco de dados não convencionais
•
•
•
•
•
•
Tipos de dados espaciais
Operações/Consultas espaciais
Métodos de acesso espaciais
Estruturas de dados espaciais
Aquisição de dados espaciais
Apresentação de dados espaciais
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
15
Tecnologias de BDs candidatas
• Relacional
• Relacional Estendido
• Objeto-Relacional
• Orientado a Objetos
• Semânticos
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
16
Algumas Tecnologias Envolvidas
• Bancos de Dados
• Computação Gráfica (geometria computacional,
processamento de imagens, interface homem/máquina,
CAD, etc.)
• Geoprocessamento, geodésia, sensoriamento remoto,
fotogrametria, topografia
• Matemática aplicada e matemática computacional
• Engenharia de Software
• Inteligência Artificial (Redes Neurais, Algoritmos
Genéticos)
• Otimização e Pesquisa Operacional
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
17
Modelos Conceituais para SIGs
Modelos OO
• GMOD [Pires 1997]
• Geo-OMT [Borges, 1997]
• GeoOOA [Kösters, 1997]
• MADS [Parent, 1998]
• GeoOMT [Abrantes, 1998]
• Perceptory [Bédard, 1999]
• UML-GeoFrame [Lisboa, 1999]
Modelos ER
• Modul-R (Bédard, 1999]
• GISER (Shekhar, 1997]
• Geo-ER (Hadzilacos, 1997]
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
18
A superfície da terra pode ser vista como um continuum espaço temporal,
aonde diversos processos ocorrem.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
19
Classes de Processos
• Processos de Campo (field process) - a intensidade
das forças que interagem é função da posição e o
padrão resultante pode ser expresso em termos de
valores de campo dependentes da posição (visão
de campo).
• Processos caracterizados pela interação espacial de
objetos. O padrão resultante pode ser expresso em
termos da distribuição espacial e do estado destes
objetos (visão de objetos).
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
20
Visão de Campo
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
21
Visão de Objetos
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
22
Campos, Objetos e Geometria...
• Sistemas de geo-informação são utilizados para armazenar e
processar dados referentes à superfície da terra. Estes dados
contêm informação temática e espacial
• Para uma grande parte de aplicações os aspectos temáticos
de uma descrição geográfica (terrain) são os mais
importantes.
• O processamento de dados e as consultas serão organizadas
e formuladas basicamente a partir de uma perspectiva
temática.
• A estrutura e formulação dos aspectos geométricos serão
secundárias, i.e., dependerão da formulação temática do
problema
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
23
Campos, Objetos e Geometria
• A escolha de como a geometria deve ser representada em um
SIG depende portanto dos dados temáticos e do seu uso.
• Visão de campo (field approach)
Posição
Valores dos atributos
raster
• Visão de objetos
Dado temático
vector
Identificador do objeto
Dado geométrico
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
24
Aspectos da Informação Geométrica
• Posição e Orientação: devem ser expressos relativamente a
um sistema de coordenadas ou sitema de referência
espacial.
– Posição - par de coordenadas
– Orientação - ângulo relativo a um dos eixos do sistema de
coordenadas
• Forma e Tamanho: podem ser expressas sem referência a
um sistema de coordenadas. Estes aspectos métricos
podem ser derivados dos comprimentos dos lados das
figuras e dos ângulos entre estes lados. Esta informação é
invariante relativamente à transformação de coordenadas.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
25
Aspectos da Informação Geométrica
• As relações topológicas entre objetos podem ser descritas
sem referência à sua posição, orientação, forma e tamanho.
São relações do tipo: inclusão (pertence), intersecção,
adjacência, etc.
• As relações topológicas são invariantes sob todas as
transformações contínuas do sistema de coordenadas.
• São também invariantes relativamente a deformações
contínuas.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
26
Relações Topológicas
Invariantes sob:
Y
Y
Y
X
X
Y
X
X
Inclusão
Y
Y
Y
X
X
Intersecção
UERJ - Março 2001
Translação
Rotação
Y
X
X
Mudança
de Escala
© Oscar Luiz Monteiro de Farias
Deformação
27
Campos e Rasters
• Veja Capítulo II do Molenaar
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
28
A Geometria dos Objetos Espaciais...
• Na visão de objetos, o link entre os dados temáticos e os
dados geométricos é feita através do identificador de
objetos (slide 24).
• A definição dos objetos se dá primariamente a partir de
uma perspectiva temática.
• Objetos com a mesma estrutura de atributos formam uma
classe de objetos temáticos.
• Em geral a representação geométrica será especificada por
classe de objetos.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
29
Tipos de Objetos Geométricos
Dado Temático
Objeto ponto
Dado Temático
Objeto linha
Dado Temático
Objeto área
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
30
A Geometria dos Objetos Espaciais...
• Quando a informação geométrica é necessária, várias decisões devem
ser tomadas, relativamente a como a geometria dos objetos deve ser
representada.
 Para cada classe temática de objetos deve-se decidir se os objetos serão
representados por objetos tipo ponto, linha ou área.
 para objetos ponto somente a posição é armazenada
 para objetos linha a posição e a forma são armazenadas;
comprimento (length) é a única medida fornecida.
 Para objetos área a posição e a forma sãoarmazenadas e o
comprimento do perímetro e a área do objeto são as únicas medidas
fornecidas.
 Esta escolha depende do papel dos objetos na descrição da geografia e
na análise, ao invés da forma real dos objetos. Depende também de
aspectos temáticos e da escala observada.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
31
A Geometria dos Objetos Espaciais...
 Deve-se decidir sobre a acurácia necessária na descrição
geométrica dos objetos geográficos (terrain objects).
Esta decisão diz respeito tanto à acurácia posicional,
quanto à acurácia e precisão na descrição da forma e dos
detalhes geométricos.
 Deve-se escolher a estrutura geométrica para a descrição:
 raster
 vetorial
Deve-se decidir se as relações topológicas entre os objetos
serão representadas explicitamente no modelo de dados ou
não.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
32
Estruturas Geométricas
Dados Temáticos
Objeto
Geometria vetorial
UERJ - Março 2001
Geometria raster
© Oscar Luiz Monteiro de Farias
33
Geometria Raster...
• A geometria raster é mais adequada para a representação de objetos tipo
área.
• Cada célula do látice possui um label que indica a que objeto ela pertence.
• Células na fronteira entre dois objetos:
– pode-se atribuir um label indicando que a célula está na fronteira de dois
objetos;
– pode-se atribuir um label à célula, associando-a ao objeto que possui
maior overlap com a mesma.
• Rasters não são adequados para representar objetos do tipo ponto e do tipo
linhas.
• A topologia do raster ajuda a encontrar a estrutura geométrica dos objetos
(testa os labels das células vizinhas).
• Objetos são identificados como conjuntos contígüos de células com o
mesmo label.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
34
Geometria Raster...
Estrutura Topológica
Situação em raster
Objetos
Área
A
A
A
B
B
B
A
A
A
B
B
B
A
A
A
B
B
B
A
A
A
B
B
B
A
A
A
B
B
B
B
B
B
C
B
B
B
B
B
C
B
B
B
B
B
C
C
B
Objetos
Linha
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
35
Geometria Raster...
• Existem dois modos para associar-se a informação sobre os
objetos às células da representação raster:
 Cada célula possuir um label indicando a que objeto ela pertence.
 Cada objeto apontar para o conjunto de células que o representa.
Isto pode ser feito através, p.ex., de uma lista encadeada.
• Para os objetos representados no formato raster, a
descrição geométrica do objeto é dada pelas próprias
células do raster.
• A resolução do raster determina a precisão com que a
geometria do objeto será representada.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
36
A Estrutura Vetorial...
• Representa as características lineares da geometria de
objetos geográficos.
• A estrutura topológica de um mapa vetorial pode ser
analisada pelas ferramentas da Teoria dos Grafos.
• Os elementos geométricos da estrutura espacial de um
mapa vetorial devem ser interpretados como componentes
de um grafo.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
37
A Estrutura Vetorial...
Nodo
Ponto
Vértice
Arco
Aresta (edge)
Segment Polyline
Chain
Polygon Face Area Segment
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
38
Convenções utilizadas
•
•
•
•
Nodo: ponto em um grafo.
Aresta (edge): uma linha conectando dois nodos.
Polyline: uma cadeia (chain) de arestas (edges).
Segmento de um grafo (graph segment, g-segment,
segment): é uma polyline que não contém nodos, aonde
mais de duas arestas (edges) se encontram. Esta restrição
não se aplica aos nodos iniciais e finais de um segmento.
• Polygono (polygon): Uma combinação de polylines que em
conjunto formam um loop.
• Um polígono limita um segmento de área (area segment).
• Face (face): segmento de área não interceptado por um
polígono.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
39
Tipos de objetos geográficos (terrain)
• Pontos
– não possuem dimensão espacial
– possuem apenas uma posição (coordenadas)
– são representados por nodos
• Linhas
– possuem uma dimensão espacial
– possuem um comprimento e uma forma
– são representadas por polylines
• Áreas
– possuem duas dimensões espaciais
– representadas por polígonos
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
40
Estruturas Alternativas na Rep. Vetorial
A
B
C
D
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
41
Estruturas Alternativas na Rep. Vetorial
• A - Situação geográfica representada de diferentes maneiras nas figs.
B, C e D.
• B - Representa a geometria corretamente mas não é possível associar
(link) os objetos aos elementos geométricos de forma não ambígua.
• C - é possível associar-se os objetos aos elementos geométricos de
forma não ambígua. É possível se derivar informações sobre a posição,
a forma e o tamanho dos objetos individuais a partir desta estrutura.
Todavia, é difícil analisar as relações topológicas existentes entre os
objetos, porque elas não são representadas explicitamente nesta
estrutura. Devem ser computadas a partir dos polígonos e cadeias
representativas dos objetos
• D - Possibilita uma associação não ambígua entre os objetos e os
elementos geométricos. Permite analisar as relações topológicas entre
os objetos.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
42
Dados Vetoriais x Situação Geográfica
• Para objetos geográficos três conjuntos de dados devem ser armazenados
em um SIG:
 Identificadores de objetos (nomes, códigos ou nos)
 Dados temáticos
 Dados geométricos
• Para um determinado objeto estes dados estão conectados através do seu
identificador.
• Necessidade: Formular um modelo conceitual para explicar como os
dados geométricos e os dados dos objetos podem ser associados (linked).
Este modelo nos ajudará a entender como consultas sobre os objetos
geográficos (terrain objects) e suas relações topológicas mútuas podem
ser manipuladas em uma estrutura vetorial.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
43
Modelo Conceitual - Convenções...
• Convenção I: Todos os pontos que são utilizados para
descrever a geometria de uma situação geográfica serão
tratados como nodos.
• Convenção II: Todos os elementos linha que são utilizados
para descrever a geometria de uma situação geográfica
serão tratados como arestas direcionadas e serão
consideradas como segmentos de reta.
• Se a geometria de um mapa vetorial é estruturada em
termo de polylines ou segmentos (slide 38) então a
Convenção II pode ser substituída pela Convenção II-ª
• Convenção II-A: O nodo inicial de um segmento deve ser
diferente do nodo final.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
44
Modelo Conceitual - Convenções...
• Convenção III: Para cada par de nodos existe no máximo
uma aresta que os conecta diretamente, mas, além desta
aresta, podem existir diversos segmentos conectando-os.
• Convenção IV: Arestas não devem se interceptar. Se duas
arestas se interceptarem, então elas devem ser substituídas
por quatro arestas encontrando-se em um nodo.
O nodo inicial ou final de uma aresta “a” não pode estar
em uma outra aresta “b”. Se isto ocorrer a outra aresta
deve ser particionada em duas, de forma que a primeira
aresta e as duas novas arestas encontrem-se em um ponto.
(o grafo representativo da geometria deve satisfazer a
fórmula de Euler)
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
45
Modelo Conceitual - Convenções...
Não mais que uma aresta
entre um par de nodos
Arestas não devem se
interceptar
Uma aresta não deve
terminar em outra
Incorreto
Correto
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
46
Modelo Conceitual - Convenções...
• Segmentos de grafos freqüentemente exercem o papel de
arestas . Assim eles devem satisfazer a Convenção IV-A.
• Convenção IV-A: Segmentos não devem se interceptar. Se
dois segmentos se interceptarem, então devem ser
substituídos por quatro segmentos encontrando-se em um
nodo. O nodo inicial ou o nodo final de um segmento não
pode estar em um outro segmento. Se isto ocorrer o outro
segmento deve ser particionado em dois, de forma que o
primeiro segmento e os dois novos segmentos encontremse em um nodo.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
47
Relações entre Arestas e Objetos...
Relação entre aresta e objeto linha
Polyline representa o objeto linha
k
k
i
i
k
Aresta parte da objeto linha
i Aresta parte da polyline
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
48
Relações entre Arestas e Objetos
Relação entre aresta e objetos áreas
Objeto área A
esquerda
A
q
q
p
p
B
direita
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
Objeto área B
49
Modelo Conceitual - Convenções...
Informações geométricas fornecidas para os três tipos de objetos:
• Objeto ponto: a localização (coordenadas). Será representado por
um nodo.
• Objeto linha: a localização, a forma e o comprimento. Será
representado por uma polyline. Os nodos contêem a informação da
posição e a informação sobre a forma pode ser derivada dos
ângulos entra as arestas e o seu comprimento.
• Objeto área: a geometria de um objeto área é dada pela sua
fronteira. Objetos área cobrem a área de interesse totalmente e
não se superpõem. Formam uma partição geométrica da área.
Representados por polígonos, consistindo de arestas, as quais
sempre possuirão um objeto área à direita e outro à esquerda.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
50
Modelo Conceitual - Convenções...
• Nodos desempenham dois papéis diferentes no modelo:
– Representam objetos do tipo ponto.
– Agem como nodos inicial e final das arestas. Neste papel
são de grande importância para a definição da geometria
de uma estrutura vetorial correspondente a uma dada
situação geográfica.
• Arestas também desempenham dois tipos de papel:
– São parte de um objeto linha.
– São parte da fronteira entre dois objetos do tipo área.
• Objetos linha que interceptam um objeto área terão este
objeto área, tanto do seu lado direito como do lado esquerdo.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
51
Modelo Conceitual - Convenções...
• Uma aresta pode ser parte, no máximo, de um objeto
linha.
• Arestas possuem apenas um objeto área do seu lado direito
e um do lado esquerdo.
• Objetos ponto não podem coincidir.
• SVVM (Single Valued Vector Map) - Bases de Dados
Espaciais que satisfazem os requisitos acima.
• Estas restrições podem ser sumarisadas nas Convenções
V-A e V-B.
• São importantes porque implicam em aspectos semânticos
das Bases de Dados Espaciais.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
52
Modelo Conceitual - Convenções...
• Convenção V-A: Um nodo pode representar no máximo um
objeto do tipo ponto.
• Convenção V-B: Uma aresta (segmento) pode ser parte, no
máximo, de um objeto linha e tem apenas um objeto área
do seu lado esquerdo e exatamente um objeto área do seu
lado direito.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
53
Ex.: Um Modelo de Dados Conceitual...
• Dois tipos de elementos geométricos: nodos e arestas.
• Três tipos de objetos geográficos: objetos do tipo ponto,
tipo linha e tipo área.
• Informação posicional será associada aos nodos na forma
de dois atributos: as coordenadas X e Y.
• Informação temática também será associada aos objetos
na forma de uma lista de atributos.
• Neste exemplo a única informação temática fornecida será
um atributo especificando a classe temática à qual ele
pertence.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
54
Ex.: Um Modelo de Dados Conceitual...
Para as classes de objetos duas restrições adicionais são
aplicáveis:
• Convenção VI: Todos os objetos pertencem a uma classe e
cada objeto pertence exatamente a uma classe. Relativamente
aos objetos mapeados as classes são exaustivas e disjuntas.
As classes formam uma partição temática do conjunto
completo dos objetos.
• Convenção VII: Cada classe de objeto contém objetos de um
tipo geométrico. Uma classe contém ou objetos pontos, ou
objetos linha ou objetos área. Estes três tipos de objetos
geométricos formam uma partição do conjunto completo das
classes de objetos temáticos
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
55
Ex.: Um Modelo de Dados Conceitual...
As relações entre os cinco tipos de entidades e os dados
temáticos e geométricos especificados para o modelo
podem ser resumidos a:
 Um nodo possui um par de coordenadas (X,Y) para
informação posicional.
 Uma aresta possui um nodo inicial e um nodo final.
 Uma aresta pode ser parte de, no máximo, um objeto
linha.
 Uma aresta tem exatamente um objeto área de seu lado
direito e exatamente um objeto área do seu lado esquerdo.
 Cada objeto pertence a exatamente uma classe temática.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
56
Ex.: Um Modelo de Dados Conceitual...
Acrescentamos:
 Um objeto do tipo ponto, representado por um nodo que
não está relacionado a uma aresta, está localizado dentro
de um objeto do tipo área.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
57
Estrutura Vetorial de um Terreno
6
5
5
1
Object Number
3
2
Node Number
6
4
1
3
7
2
4
8
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
58
Um Modelo Lógico
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
59
Queries e a Estrutura Vetorial...
Exemplos de queries que podem ser aplicadas a um banco
de dados organizado na estrutura vetorial:
 Que tipo de objeto é o objeto de no 7?
 É um objeto do tipo ponto que pertence à classe “mill”.
 Selecione o objeto tipo ponto com (id = 7), forneça a
classe (no caso de haver objetos tipo linha ou tipo área
com id =7).
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
60
Queries e a Estrutura Vetorial...
A query referente à posição de um objeto pode ser
interpretada de dois modos:topológico e posicional.
 Aonde o objeto n0 7 está localizado?
No sentido topológico pode ser interpretada como:
 a Selecione o objeto tipo ponto com (id = 7), forneça aid.
Interpretada em termos posicionais, pode ser subdividida em
duas partes:
 .1 Selecione o objeto tipo ponto com (id = 7), atribua o
valor p = nid;
 .2 Selecione o nodo com (id = p), forneça as coordenadas
X e Y;
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
61
Queries e a Estrutura Vetorial...
Queries sobre classes temáticas do tipo linha ou área podem
ser manipuladas de modo similar à query .
 Aonde o objeto tipo área n0 3 está localizado?
(A resposta será fornecida para um objeto área sem buracos)
i) A localização do objeto é especificada por sua fronteira, a
qual é geometricamente descrita pelas suas arestas.
ii)
Encontramo-las na tabela “edge”, procurando por arestas
que tenham os atributos “le=3” ou “ri=3”, mas não ambos
simultaneamente.
iii) Estabelece-se uma seqüência de arestas tomando-se
uma das arestas selecionadas e encontrando-se os valores
dos atributos ”b” e “e”.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
62
Queries e a Estrutura Vetorial...
Estes são os nos dos nodos inicial e final de cada aresta.
iv) O valor de “e” é mantido em memória e então a lista de
arestas selecionadas é pesquisada para a próxima aresta
que tenha seu no de nodo sob “b” ou “e”.Estes novos nos
de nodo são mantidos em memória e pesquisa-se para a
próxima aresta.
v) Este procedimento é repetido até que o nodo final de uma
aresta na lista seja igual ao nodo inicial da primeira
aresta.
A seqüência de nodos de fronteira podem ser derivados a
partir desta seqüência de arestas, e as coordenadas destes
nodos fornecem a localização do objeto.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
63
Queries e a Estrutura Vetorial...
A consulta “aonde o objeto tipo área n0 3 está
localizado?” deve ser transformada em:
 .1 Selecione arestas com ((le eq 3) xor (ri eq 3)), grave
estas arestas em uma tabela “T”;
Recuperamos assim, as arestas que formam a fronteira do
objeto, armazenando-as temporariamente em “T”. Então
os nodos de fronteira são ordenados e suas coordenadas
são armazenadas em outra tabela “P”.
 .2 Selecione a aresta da primeira linha de “T”. Atribua os
valores “B=b” e “E=e”;
 .3 Selecione nodo com (id eq E), grave nodo em “P”;
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
64
Queries e a Estrutura Vetorial
 .4.1 Selecione aresta com (b eq E), atribua valor E=e;
 .4.2 O mesmo que ..3;
 .4.3 Selecione aresta com (e eq E), atribua valor E=b;
 .4.4 O mesmo que ..3;
 .4.5 Se (E eq B) então pare, senão retorne para  .4.1
Em cada iteração do loop o sistema encontra na tabela
“T” através do passo  .4.1 uma aresta com b=E ou,
através do passo  .4.3 uma aresta com E=e. Quando o
processo termina em  .4.5 a tabela “P” contém os nodos
de fronteira ordenados de modo a especificar a geometria.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
65
Queries sobre a Topologia dos Objetos...
• As relações topológicas entre objetos linha e objetos área
podem ser encontrados de preferência na tabela “edge”.
 Que áreas margeiam uma cidade?
 Na tabela de objetos tipo área procura-se pelo “id” do
objeto cuja “class=city” (id=3);
 Na tabela “edge”, uma lista com as arestas da fronteira da
cidade são obtidas, de acordo com a query .
 Se uma aresta nesta lista possui o valor 3, então o valor do
atributo ri é o id do objeto adjacente e vice-versa.
 Os objetos adjacentes têm os ids 1, 2 e 4.
 As classes temáticas destes objetos podem ser encontradas
na tabela de objetos área (2 agricultural, 1 forest).
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
66
Queries sobre a Topologia dos Objetos...
• Query  deveria ser respondida da forma:
 .1 Selecione o objeto área com (class eq city), atribua o
valor s=id;
 .2 Selecione as arestas com ((ri eq s) and (le ne s)), grave
“le” em LIST;
 .3 Selecione as arestas com ((le eq s) and (ri ne s)), grave
“ri” em LIST;
 .4 Atualize LIST, de forma que cada no de objeto apareça no
máximo uma vez;
 .5 Para cada no em LIST:
Selecione o objeto área com (id eq no); grave sua classe
em LIST2;
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
67
Queries sobre a Topologia dos Objetos...
• Que áreas são conectadas pela rodovia (road)?
® A rodovia passa pelas fronteira entre a área agrícola de no
1 e pela área de floresta e continua atravessando a cidade.
• A resposta anterior contém dois tipos de relações
topológicas: adjacência e interseção.
• Estas relações topológicas podem ser formuladas em duas
diferentes consultas:
 Na fronteira de que objetos área a rodovia se extende?
 Que objetos a rodovia atravessa (intercepta) ?
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
68
Queries sobre a Topologia dos Objetos...
• Query  pode ser respondida selecionando-se na tabela
“edge” aquelas arestas que pertencem à rodovia e que
possuem do seu lado direito e do seu lado esquerdo
diferentes objetos.
 .1 Selecione o objeto linha com (class eq road), atribua o
valor s=id;
 .2 Selecione as arestas com ((lo eq s) and (le ne ri)), grave
“le” e “ri” em LIST;
 .3 O mesmo que ..4;
 O mesmo que ..5.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
69
Queries sobre a Topologia dos Objetos
• Query  pode ser respondida assim:
 .1 O mesmo que ..1;
 .2 Selecione as arestas com ((lo eq s) and (le eq ri)), grave
“le” em LIST;
 .3 O mesmo que ..4;
 .4 O mesmo que ..5.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
70
Relações entre Objetos Espaciais
Relações área-área
adjacência
inclusão
Relações linha-linha
toque
ramificação
cruzamento
interseção
Relações área-linha
Linha na fronteira
de uma área
Relações ponto-linha
UERJ - Março 2001
Relações área-ponto
© Oscar Luiz Monteiro de Farias
71