|
|
The Benefits of Topology in the Database
By Steven Ramage and Peter Woodsford, Laser-Scan Ltd., Cambridge UK
Printer Friendly Version
 Laser-Scan from the world famous Cambridge Science Park in the UK has launched a
topological extension to Oracle9i, Radius Topology. Applications which manage, query or
analyse spatial data that is inherently topological - land parcels, urban zones, transportation
and utilities networks - can take advantage of Oracle’s database technology and security by
accessing server side processing functionality. Radius Topology implements ISO19107
topology within a mainstream relational database (RDBMS) environment. Integrity is
maintained at all times and analysis benefits from ‘switched on’ topological intelligence. All
with no call for specialist knowledge in a seamless IT environment. The article describes what
Radius Topology provides and the benefits it brings to key use cases.
What is topology?
The mathematician's answer is that topology describes the characteristics of a geometric
figure, which remain constant under continuous deformation of the co-ordinate space.
Imagine a rubber sheet with a jigsaw puzzle drawn out on its surface. As the sheet is
stretched, the shapes of the individual pieces become distorted; the original subject matter
may be hard to recognise. However, certain aspects of the jigsaw have not changed:
- it has the same number of pieces
- each piece retains the same set of nearest neighbours and in the same order
- the same set of drawn lines as before appears inside each piece (albeit distorted)
- drawn lines still join up where they cross the piece boundaries
Topology is the means to describe these relationships explicitly without resorting to costly
spatial comparisons each time we need to know them. So, for example, within the jigsaw, the
fact that two pieces are opposite each other is reflected in both pieces referring to the same
edge or shared line.
In practice, although rubber sheets do not figure prominently in the kind of phenomena and
businesses we seek to represent and manage using databases, the topological view is
fundamental to managing entities which are connected together (networks) and spaces which
are divided up or partitioned (planar topologies).
One-dimensional or network topology is built from node and edge primitives. Two-dimensional
or planar topology has face primitives in addition and can be regarded as network topology
with the constraint that edges do not cross, except at nodes. In both cases, the topological
model replaces expensive geometrical computations with simple combinatorial algorithms
(Ref. 1)
Topology in the database?
The combination of mathematical terminology (complexes, manifolds, partitions…), reams of
daunting Unified Modelling Language (UML) diagrams and the undoubted trials of accurately
managing all the special cases that abound in real life data, has conspired to give topology a
reputation for being extremely difficult and expensive. For some time the received wisdom
has been to make do without it and to compute it when required. This policy is defensible in
read-only applications, however it is weak if the application makes heavy use of queries that
can benefit from explicit topological operations (see below). It is second best, and indeed high
risk, in write applications. Topology is complicated, and although there is at last progress in
standardisation through to the engineering implementation level, there is still too much scope
for divergent implementations, undetected error and virus-like error propagation with costly
consequences. The arguments for server-side representation and validation are particularly
strong in the case of topology.
The inexorable progress of Moore's Law (Ref. 2), the benefits of migrating object-oriented
concepts and techniques to the RDBMS world and the maturity and greater understanding
that results from standardisation work have resulted in a situation where topology in the
database is achievable and deliverable. Laser-Scan's Radius Topology is the first realised
example and represents the next step in the migration of spatial data handling into
mainstream DBMS technology. This began in the second half of the 1980's with hybrid
systems, in which non-spatial attribute information was held in externally accessible
databases. Next, from the mid-90's onwards came the 'Spatial Cartridges' with spatial
(geometry) data also held in the RBDMS. Oracle Spatial has emerged as the pre-eminent
example. Now the scene is set for topological extensions to the mainstream DBMS.
Radius Topology from Laser-Scan
The first release of Radius Topology (June 2002) supports the Oracle Spatial type with
topology manifested in Oracle9i . Both network and planar topologies are dynamically
maintained in a transparent and open manner. Clients that use standard Oracle interfaces
become topologically enabled, without any change to the client code or user interface (see
Figure 1). For feature classes, which are defined to be topological, extra tables holding the
topological relationships are created and automatically maintained. When these tables are
activated, features in the enabled classes behave topologically. When a node is moved, all
the edges involved in the change are automatically modified. Similarly modifications to edges
are reflected in involved faces, and when new intersections arise, the relevant nodes are
automatically created.
Topologically enabled data can be freely mixed with inert (spaghetti) data. It can also be
partitioned into non-interacting manifolds. A very fine level of control on topological
interactions is provided (on a per feature class pair basis, with assignable priorities so that
trusted or surveyed data takes precedence and is preserved). The implementation follows
Topic 1 (Feature Geometry) of the Open GIS Consortium's Abstract Specification and the ISO
TC19107 Spatial Schema draft standard.
Figure 1. Topology in GeoMedia
Figure 1. Topology in MapInfo
Figure 1. Radius Topology allows all GIS packages to become 'topologically-enabled' (if they
can manage their data in an Oracle database). Changes to the database are checked and
processed by the Radius Topology Manager and reflected in all the client GIS packages.
Data courtesy of Ordnance Survey GB © Crown Copyright
When unstructured data is imported, it is structured on the fly. User-defined rules determine
the snapping processes; topological structures (and the associated relational tables) are
created automatically and cleaning and validation tools invoked. A fuller account of how
Radius Topology works, using only core Oracle9i data services, is to be found in the Laser-
Scan White Paper, “Laser-Scan and the Radius Topology Product: Advanced Spatial
Processing Environment for Oracle9i” (Ref. 3).
Radius Topology updates the topology model whenever a real-world geometry or topology
primitive is created, deleted or modified. This ensures that topology is always up to date and
synchronised with the real-world spatial data. The structure added to the data enables many
spatial queries to be answered more quickly by examining the topology. A spatial query
requires a spatial index to be traversed and a number of compute-intensive geometric
comparisons. Relationships such as overlap (share face) and co-linearity (share edge) are
held as references within the topology model. These may be traversed very quickly by table
joins to identify other features that use the same node, edge or face. Using topology can
improve performance by more than an order of magnitude, enabling the execution time for a
complex query to reduce from over a minute to just a few seconds.
The topology engine that is the core of Radius Topology is not new. It has been heavily used
for a decade and more in the Laser-Scan Gothic range of object-oriented geospatial
applications. It was used in the Fastrack data re-engineering programme by Ordnance
Survey, in which the OS MasterMapTM product was created. OS MasterMapTM provides
continuous national coverage of 400 million structured polygon objects. It was created in just
one year from 225,000 map sheets of spaghetti Land-Line® data, with less than 1% manual
editing and 60 million inconsistencies automatically corrected. Within Gothic the topology
engine is used to manage a full range of structured data models including the military
DIGEST VPF, the hydrographic IHO S57 and the transportation ISO204 GDF. It is
consequently both robust and flexible. Laser-Scan maintains code compatibility between the
Gothic and Radius Topology engines, and a rigorous common regression testing regime.
Figure 2 shows the role of the topology engine in the overall architecture.
Figure 2. Radius Topology in Oracle
Benefits
Once built, a topology model can be put to many uses. An application such as route finding is
inherently topological. The distinction made above between read and write applications is
important here. Provided the database can guarantee data integrity and can support update
(both by use of dynamic topology), specialist in-memory structures can be built to support
very rapid route evaluation and selection for huge numbers of users. The Back Office needs
dynamic topology maintenance in a database environment because it has to provide the
guarantee on which the route finding relies.
In other application domains the range of queries is much less predictable (and the frequency
lower). A large proportion of queries run significantly faster when topological operators are
available. Adjacency, co-linearity and containment relationships are examples where
geometric computation is expensive and slow, and use of topology results in significant
efficiency gains.
Managing people depends on counting and classifying them; this is done on an area basis.
Managing the boundaries of these areas is a prime application of topology, especially when
there are hierarchies of inter-related areas. A good example is administrative boundaries in
England and Wales, which follow the hierarchy….
Figure 3. Hierarchical bounded areas can all be described in terms of a single underlying
topology complex.
The classification, business and statistical data for such applications are ideally handled in an
RDBMS. The ability to manage the areas, so as to avoid gaps, overlaps and to control
change in the same database is a great advantage. This applies across census, post coding,
electoral, geodemographic and cadastral and land use applications. Dynamic server-side
topology ensures that all land is accounted for across all applications and that modifications,
even to nested shared geometries, need only be performed once. Coupled with a suitable
parcel referencing system or unique identifier regime, Radius Topology and Oracle Spatial
provide all the key requirements.
Topology is not unique to geospatial applications, many other applications for Radius
Topology are emerging but are not the subject of this paper.
Conclusions
Radius Topology marks a further stage in the progression of geospatial data management
from proprietary environments into mainstream DBMS. The addition of topology opens up
network and parcel management applications in Navigation and location based services
(LBS), utilities, cadastre and land management, as well as in mapping and charting. Since
these services are seamlessly integrated in the DBMS environment they can be deployed in
wider application business activities such as Customer Relationship Management (CRM) and
geodemographics.
All the usual benefits of a mainstream RDBMS (scalability, system and corporate robustness,
archiving, to name but a few) are sustained. In particular, Radius Topology uses standard
locking and versioning mechanisms, so that, for example, the Oracle History mechanism can
be used. Programming skills requirements are mainstream - SQL, Java and XML - and
neither the Database Administrator or application users have specialist demands placed upon
them.
Looking forward, Laser-Scan expects that its standards-based open architecture will deliver
further benefits of object-oriented geospatial technology as middleware components. Radius
Topology is the first of these and is being marketed through partners to bring the benefits of
GIS to the widest possible set of mainstream IT users.
References
1. Topology and ORDBMS technology, a White Paper by Paul Watson.
2. Moore’s Law originally stated that computing power would double every year (Gordon
Moore, 1965)
3. Laser-Scan and the Radius Topology Product - Marketing Perspective, a White Paper by
Steven Ramage, Paul Hardy and Paul Watson
http://www.laserscan.com/pdf/MarketingWhitePaper.pdf
Footnote
Laser-Scan launched Radius Topology at OracleWorld, Copenhagen, 24-27 June. For more
information visit the Radius Topology website http://www.radius.laser-scan.com/index.htm
Copyright © 2002 Laser-Scan
If you have news, announcements, or comments from the event, please be sure to tell us about it.
Send details to the Editor (editor@geocomm.com)
Search GeoCommunity for Related Stories
Search The Web (Google) for Related Stories
|
|
Sponsored by:
For information
regarding
advertising rates
Click Here!
|
