Geo-spatial Information

Volume 7, Issue 3

Science (Quarterly)

September 2004

Article ID: 1009-5020(2004)03-174-179

Document code: A

Network Analysis Modeling Towards GIS Based on Object-Relation Database YUE Peng

WANG Yandong

GONG Jianya

HUANG Xianfeng

This paper compares the differences between the mathematical model in graph theory and GIS

ABSTRACT

network analysis model. Thus it claims that the GIS network analysis model needs to solve. Then this paper introduces the spatial data management methods in object-relation database for GIS and discusses its effects on the network analysis model. Finally it puts forward the GIS network analysis model based on the object-relation database. The structure of the model is introduced in detail and research is done to the internal and external memory data structure of the model. The results show that it performs well in practice. network analysis;GIS;object-relation database

KEYWORDS

P208

CLC N U M B E R

spatial data model and spatial data structure. And

Introduction

the research in data model and data structure plays a kernel role in GI8 Ez~. Presently, the widely used ob-

W i t h the wide application of GIS in fields of city t r a n s p o r t a t i o n ,

ject-relation database in GIS is built on the object-re-

pipeline n e t w o r k , electrici-

lation model. It does not store the topological rela-

t y , t e l e c o m m u n i c a t i o n , m o r e e n h a n c e m e n t s need

tion of spatial objects, thus the previous network

to be added to the current GIS spatial analysis,

analysis model needs to be extended.

especially n e t w o r k analysis.

T h e basic data in

T o meet the various demands of special fields,

these fields have one c o m m o n feature: they are

people tend to combine the theoretical models

net data constructed by points and lines.

To

defined in m a t h s with the practical problems.

fully describe these net data and relationship be-

A f t e r using G I S as a tool for m a n a g e m e n t and

tween t h e m , m o r e powerful and flexible n e t w o r k

p r e s e n t a t i o n of spatial data,

analysis functions

routing

arouses the interest of researchers: the p r o b l e m

analysis, resource allocation, connection analy-

of designing a flexible n e t w o r k analysis model as

sis, flow analysis, are required EI~.

a middle layer between the mathematical model

Many

and practical application which can be easily cus-

w o r k about the efficiency of n e t w o r k analysis al-

tomized, modularized and a p l a t f o r m easy for en-

gorithms,

hanced development.

such path

have

as the

done

including

theoretical

shortest

scholars

in G I S ,

much

another problem

classical a l g o r i t h m

searching--Dijkstra.

of

However,

Focusing on the problems that GIS network

the i m p l e m e n t a t i o n of theoretic a l g o r i t h m s al-

analysis model needs to solve, this paper pres-

w a y s depen~[s on certain kind of data organiza-

ents an extended n e t w o r k analysis model based

tion.

on the object-relation database. And a n e t w o r k

The organization of spatial data consists of

Received on September 8, Z003. Funded by the National 973 Project (NO. G2000077904) and the National 863 Project (No. 2002AA131030). YUE Peng, Ph. D candidate, State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, 129 Luoyu Road, Wuhan, 430079, China. E-mail: yuepeng79(~hotmail, corn

YUE Peng, et al./Network Analysis Modeling Towards GIS Based on ...

175

application test is done to d e m o n s t r a t e how this

great touch with the data structure of graph. It is

model w o r k s well.

well known that there are always differences existing between theoretic models and realistic models. So

1

Problems that GIS network anal-

the differences between the network analysis model

ysis model needs to solve

in GIS and mathematical model in the graph theory need to be known firstly, and these are exactly what

In the graph theory, network is abstracted to the

the network analysis model primarily aims to solve

graph Ea?. Thus the data structure of network is in Table 1

(Table 1).

DifferenCes of mathematical model and GIS network analysis model

Model

Difference

Mathematic model in graph theory

Data

moderate volume, symmetric distributed

GIS network analysis model large volume, asymmetric distributed

Spatial position of arc and node

unmeaningful

meaningful

Weight of are Weight of node Weight of turn Dynamic segmentation Topological relation

monotone nonexistent nonexistent nonexistent simple

multiple existent existent existent complex

Below is the detailed explanation to T a b l e 1.

G I S , one arc always c o r r e s p o n d s to one record of

1) Data. U s u a l l y the spatial data is large-scale

a t t r i b u t e data.

However,

in the road informa-

and a s y m m e t r i c a l l y distributed. T h e model m u s t

tion m a n a g e m e n t field, the arc m a y c o r r e s p o n d

be carefully designed to m e e t the demands for

to several a t t r i b u t e s while each a t t r i b u t e records

both efficiency and m e m o r y in n e t w o r k analysis.

the p r o p e r t y of sub-arc of that arc. T o describe

2) Spatial position of arc and node: T h e origi-

the sub-arc of an arc, a linear reference f r a m e is

nal data that G I S manages is geographic spatial

introduced and a specific field in the a t t r i b u t e da-

data, so the arc and node derived f r o m the origi-

ta is used to record sub-arc position in this refer-

nal data can not deviate f r o m the geographic

ence frame. T h e s e sub-arcs are not digitized sep-

meaning of the spatial data and can m a p the fea-

a r a t e l y , so t h e y are not the conventional arcs.

tures of the real world.

We usually call sub-arcs dynamic s e g m e n t s , and

3) Weight of arc: Differing from the monotone

this kind of record is n a m e d as dynamic s e g m e n -

weight of the graph theory, the weight of arc in net-

tation.

work analysis model is affected by several factors de-

analysis model, too.

pending on the practical problems.

For example,

7)

T h u s it m u s t be considered in n e t w o r k

Topological relation:

Points m a k e up of

both the length of route and the velocity of car must

arc, and arcs are linked by point. Such kind of

be included when considering the cost of car travel.

topological relation is stored in GIS.

The GIS

At this time, functions are often used to represent

software m u s t

costs

the weight value of arc in network.

maintaining these topological relations.

4) Weight of node: T h e nodes in n e t w o r k m a y also influence the flow of resources in network. 5) Weight of turn:

T h e turn is defined as a

way that some kind of resource flows t h r o u g h a node from one arc to another.

afford the

additional

of

T h i s is

also a research division of dynamic G I S that h o w the designed model can keep the real-time update of topological relation w h e n editing the g e o m e t ric and a t t r i b u t e data.

In a realistic

w o r l d , the different turns in a road crossing cor-

2

Object-relation database

respond different costs E43. 6)

Dynamic

segmentation:

In

conventional

Relation database is a kind of perfect database

176

Geo-spatial Information Science (Quarterly)

both in theory and practice. However, it is not

The structure of this model is shown in Fig. 1.

efficient when directly using relation database management system (RDBMS) in GIS without any additional improvement made by GIS software such as spatial index. Presently object-oriented model is the best model to describe and manage the spatial data. It can afford not only the management of changeable length record but also the inheritance and congregation of information. It also permits the customized object defiFig. 1

nition, object structure and object operation.

Structure of network analysis model

Yet there are still many theoretical and technological problems unresolved in the object orien-

vided into two layers: geometric network layer

ted database system. Now

many

database

As illustrated in Fig. 1, the whole model is di-

management

system

(DBMS) software companies make extensions to their current RDBMS and present the object-relation database which can directly store and manage the nonstructural spatial data (i. e. point, line, polygon etc. ). This kind of database supports the object-oriented data model. Thus we can query the nonstructural spatial data in its application user interface. Because the extensions are made by database software companies, the efficiency of management to changeable length record is higher than the older one which make use of binary block. Now it is widely used. However, it still can not resolve the problem of object-embedding, so the topological relation can not be described fully. The spatial data structure still can not be customized. These problems limit the further use of it Es3. Furthermore, data of different attribute types or geometric types are stored as different types of feature classes in object-relation data-

and topological network layer. The geometric network layer stores the original geographic network data in forms of feature classes. The management, query, editting and display of spatial data, i. e. presentation, are implemented basd on this layer. The object-relation database does not store the topological relation of spatial data, so each geometric network layer corresponds one topological network layer for network analysis. In topological network layer there are no layers of feature classes existing in geometric network layer. It abstracts the feature classes of the same geometric type into a uniform element collection in network, but maintains the topological relation of elements. The analyses of the whole network (namely the implementation of network analysis algorithms) are conducted in this topological layer.

The topological relation can be

stored either in database or in file. The detailed illustration is shown in Fig. 2.

3. 1

Geometric network

layer

base, yet it needs to integrate them into one environment when doing network analysis. In view of these demands, additional processions are necessary for network analysis.

The geographic spatial data are represented as line feature classes, point feature classes and some attribute tables (such as turn attribute table) in this layer. Each feature class is assigned a unique global feature class ID in an object-rela-

3

Extended network analysis model

tion database. In every feature class each point

based on object-relation database

or line feature with independent attributes has a unique object ID (OID). As shown in Fig. 2, the

To solve the previous problems, this paper presents an extended network analysis model.

road's feature class ID is 1. The two features in it have the OID g l , gz, respectively. The geom-

YUE Peng, et al./Network Analysis Modeling Towards GIS Based on ..-

Topological network layer

Geometric network layer Roads (feature class ID=I)

!oeom,w,mI Railways (feature class ID=2) OlD Geometry Time ... FI

. . . . . .

[

. . . . . . . . .

C3

.

174

. . . . . . . . . . . .

.

.

.

/ @

1

r I

gt

"'"

g~ g:

g2 rl

"'" ""

..~ ~

Fig. 2

From To arc arc EID EID Turn E1D Arc3 Arc 1 Turn 1 Arc 1 Arc 2 Turn2 Arc 2 Arc 3 Turn3 Arc weight table Arc EID I Time value Arc 1 "" ...... Node weight table Node EID I Time value I Node 1 ] ... ......

I

C4

Turn attribute table From arc Toarc lD OID OID Time 2 3

OID c~ c2 c3 e4

c3

l

.

Turn table

SublD Node EID 0 Node 1 0 Node 2 0 Node 3 0 Node 4

Arc table Feature OID SublD A.rcEID class ID 1 g~ 0 Arc 1 1 g2 0 Arc 2 2 rl 0 Arc 3 Topologicalrelation table 1 Turn weight table Node Topological Topological Topological Topological relation table 2 relation relation relation EID Arc IED Node EID :Node EID Node 1 Node 2, Arcl Node 1 Node2 Node 2 Node 1, Arcl Node 3, Arc2 Node 4, Arc3 Arc I Arc2 N o d e 2 Node3 Node 3 Node 2, Arc2 Arc3 N o d e 2 Node4 Node 4~ Node 2, Arc3

/ rl / 1

. . . . . .

C2

.

Node table Feature class ID 3 3 3 3

gt

Cities (feature class ID=3) OlD Geometry Time "" C1

177

Detailed presentation of network analysis model

e t r y field stores the spatial g e o m e t r i c data. T h e

relation to the original

o t h e r fields r e p r e s e n t a set of a t t r i b u t e values.

lished.

spatial

data

is e s t a b -

T h e t u r n a t t r i b u t e table r e c o r d s t h o s e t u r n s w i t h

A r c t a b l e : All line f e a t u r e classes of g e o m e t r i c

a t t r i b u t e values t h a t m i g h t affect the r e s u l t s of

n e t w o r k layer are s o r t e d as the e l e m e n t set of

n e t w o r k analysis.

T h e arc table.

E a c h f e a t u r e of f e a t u r e classes is

mapped

here

with

(EID).

T h e A r c E I D in the arc table also re-

3.2

Topological network layer

a

unique

arc

element

ID

T o p o l o g i c a l n e t w o r k layer derives f r o m geo-

cords the c o r r e s p o n d i n g f e a t u r e class ID and o b -

metric n e t w o r k layer a c c o r d i n g to the topological

ject ID. T h e S u b I D in the arc table can be used

features of the g e o g r a p h i c spatial

to identify t h e s u b - p a r t of one line feature.

data.

It is

m a i n l y c o m p o s e d of t h r e e p a r t s : net e l e m e n t ta-

T u r n t a b l e : Since the line f e a t u r e O I D in the

ble, topological relation table, w e i g h t table.

turn attribute

3.2.1

A r c E I D in t h e topological n e t w o r k l a y e r ,

Net e l e m e n t table

T h e e l e m e n t s of the w h o l e n e t w o r k are divided

table will be c o n v e r t e d into t h e the

t u r n can be r e p r e s e n t e d b y f r o m A r c E I D and to A r c EID.

into three t y p e s in this l a y e r : arc, n o d e , turn. N o d e table: All point f e a t u r e classes of geometric n e t w o r k layer are s o r t e d as the e l e m e n t

3.2.2

T o p o l o g i c a l r e l a t i o n table

T o p o l o g i c a l relation table can be r e g a r d e d as

set of N o d e table. E a c h f e a t u r e of f e a t u r e classes

the r e p r e s e n t a t i o n

of the

is m a p p e d w i t h a unique node e l e m e n t ID ( E I D ) .

s t r u c t u r e of n o d e - a r c in n e t w o r k a n a l y s i s b e l o w ,

Since the node E I D in the n o d e table r e c o r d s the

t h o u g h it is i l l u s t r a t e d as f o r m s of t a b l e in d a t a -

c o r r e s p o n d i n g f e a t u r e class ID and object I D , the

base.

typedef struct tagNodeInfo(Node structure) {

long

F e a t u r e C l a s s I D ; / / r e l a t e d point F e a t u r e Class ID

long

FeaOID

; / / related point F e a t u r e O I D

long

SubID

; / / r e s e r v e d use for s u b - p a r t

void*

pEdgeList

; / / r e l a t e d edges

_variant_t

Weight

; / / w e i g h t value

byte

bEnabled

; //whether

} NodeInfo; t y p e d e f s t r u c t tag E d g e I n f o ( E d g e S t r u c t u r e )

used in n e t w o r k a n a l y s i s or not

widely

used

united

178 Geo-spatial Information Science (Quarterly)

{

long

FeatureClassID ~ / / r e l a t e d line Feature Class ID

long

FeaOID

; / / related line Feature OID

long

SubID

; / / r e s e r v e d use for sub-arc

long

From_ID

/ / F r o m Node EID

long

To_ID

/ / T o Node EID

long

bReverse

/ / w h e t h e r same as the flow direction or not

_variant_t

WeightF

/ / W e i g h t value from From_ID to T o _ I D

_variant_t

WeightT

/ / W e i g h t value from T o _ I D to From_ID

byte

bEnabled

/ / w h e t h e r used in network analysis or not

} Edgelnfo ; T h e characteristics about the structure are described as follows.

field of the feature classes in the geometric network. T h e n users can get each net e l e m e n t ' s

1) Instead of storing the geometric and attrib-

weight value by taking it from the mapped field.

ute values, the structure builds relations with

Finally the weight table according to each weight

spatial data through feature class ID and object

ID is established to store net e l e m e n t s ' weight

ID, thus greatly decreases the m e m o r y cost.

values (weight tables in Fig. 2).

2) It can integrate spatial data from different feature classes into one analysis environment and build a uniform network element description. 3) T h e type of weight values is variable.

3.3

Relationship between geometric network layer and topological network layer

4) It provides support for full consideration of

In the geometric network layer, spatial data of

node weight value and bidirectional arc weight

different geometric types are stored in different

value.

feature classes. As shown in Fig. 2, there is a

3.2.3

road feature class and a railway feature class in

W e i g h t table

T h e weight in network analysis model directly

one network. Conventional n e t w o r k analysis is

affects the analysis results. T h e attribute values

carried out in only one line feature class. This

in the geometric n e t w o r k layer mainly contribute

can not reflect the practical demands. People al-

to dynamic segmentation and the attainment of

ways need to take into account many factors in a

weight values. T h e r e is a set of global weight ID

network such as roads,

in

when doing network analysis. So this model can

the

topological

Weightname Net Time Net~Length

network

layer

WeightID 1 2

(Fig. 3).

Weighttype double double

Table name

integrate different types of spatial data and do the network analysis in a uniform topological network layer. Users only need to consider the algorithms in

Weight definitionin network

1

Roads

Field name time

1

Railroads

time

1 1 2 2

Cities Turn Attributetable Roads Railroads

time time ... ...

Weight ID

railways and bridges

Mapping of weightto table fields

the topological network layer.

After finishing

the analyses, the results of this layer can be reflected into the geometric network layer for visualization and reports. Of course, the alteration of spatial data in the geometric network layer must correspond to the change of table records in the topological network layer in order to keep the consistency of topology.

Fig. 3

Network weight

Each weight ID represents one type of weight that user defines~, and it will be mapped to one

Taking into account the complexity of real world problems, the model can afford various kinds of applications, and the results of analysis will be more reasonable.

YUE Peng, et al./Network Analysis Modeling Towards GIS Based on

.'- 179

author implements the c o m m o n n e t w o r k {unc-

4

Experimental system and results Based on the theoretical studies, an experimen-

tions like route analysis, resource allocation and connection analysis successively.

Results show

that it performs well in practice.

As s h o w n in

tal system for this model is conducted on busi-

Fig. 4, that is the result of service areas func-

ness GIS software GeoStar using the technique

tion. T h e data are roads data in Beijing(1 123

of COM. The full-considered model needs more

n o d e s , 1 811 a r c s ( b i d i r e c t i o n a l ) ) .

complicated implementation and then the effi-

ration of PC is: C P U f r e q u e n c y ( 4 0 0 M H z ) , H D

ciency of it is always negatively affected. But it

(10G), Memory(256M).

can still get satisfactory results when m e m o r y

tion is less than one second when computing the

optimization

service a r e a s ( i n 170 unit) of 26 gas stations if

techniques

and

reasonable

data

structure are adopted. Based on this model, the

Fig. 4

T h e configu-

T h e time of calcula-

the time cost of results display is not considered.

An example of network analysis

tern. Beijing: Science Press,270-271 (in Chinese) REFERENCES

5 Gong J Y (2001) Concepts and development of spatial database management system. Journal o f Surveying

1 Gong J Y (2001) The basis of GIS. Beijing: Science

Science ,26(3) :4-9 (in Chinese)

Press. 246-247 (in Chinese) 2

van Oosterom P (1990) Reactive data structures for

6

3

7 Zhan F (1997) Three fastest shortest path algorithms on real road networks. Journal o f Geographic Infor-

Yue Y (1999) The implement and application of net-

mation and Decision Analysis, 1(1)

work analysis model in GIS: [Ph. D dissertation]. Wuhan: Wuhan Technical University of Surveying and Mapping. (in Chinese) l

Wan J Y (2001) The theory of spatial information sys-

Envi-

ronmental Systems Research Institute,Inc.

geographic information systems: [Ph. D dissertation']. Leiden:Leiden University.

ESRI (2001) Technical documents-networks.

8

Goodchild M F (1991) Spatial analysis using GIS. Seminar Workbook (2nd Edition) ,NCGIA.