COVID-19 Update: We are currently shipping orders daily. However, due to transit disruptions in some geographies, deliveries may be delayed. To provide all customers with timely access to content, we are offering 50% off Science and Technology Print & eBook bundle options. Terms & conditions.
Spatial Databases - 1st Edition - ISBN: 9781558605886, 9780080517469

Spatial Databases

1st Edition

With Application to GIS

Authors: Philippe Rigaux Michel Scholl Agnès Voisard
Hardcover ISBN: 9781558605886
eBook ISBN: 9780080517469
Imprint: Morgan Kaufmann
Published Date: 18th May 2001
Page Count: 410
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.

Table of Contents


by Victor Vianu, University of California, San Diego




1.1 Database Management Systems (DBMSs)

1.1.1 Basic Description and Main Features

1.1.2 Modeling Applications

1.1.3 Physical Data Management

1.2 Vocabulary in Geospatial Database Applications

1.2.1 Theme

1.2.2 Geographic Objects

1.3 Geospatial Data Manipulation

1.3.1 Simple Operations on Themes

1.3.2 Further Theme Operations

1.3.3 Other Typical GIS Operations

1.4 DBMS Support for Geospatial Data

1.4.1 Use of a Relational DBMS

1.4.2 Loosely Coupled Approach

1.4.3 Integrated Approach Based on DBMS Extensibility

1.5 Requirements for a Spatial DBMS

1.6 Bibliographic Notes


2.1 Geographic Space Modeling

2.1.1 Entity-Based Models

2.1.2 Field-Based Models

2.2 Representation Modes

2.2.1 Tessellation

2.2.2 Vector Mode

2.2.3 Half-Plane Representation

2.3 Representing the Geometry of a Collection of Objects

2.3.1 Spaghetti Model

2.3.2 Network Model

2.3.3 Topological Model

2.4 Spatial Data Formats and Exchange Standards

2.4.1 Overview of Current Spatial Data Formats

2.4.2 The TIGER/Line Data Format

2.4.3 Recent Standardization Initiatives

2.5 Bibliographic Notes


3.1 Reference Schemas

3.1.1 Administrative Units (Schema 1)

3.1.2 Highway Network Among Cities (Schema 2)

3.1.3 Land Use (Schema 3)

3.2 Reference Queries

3.3 Spatial Abstract Data Types

3.3.1 Extending Data Models with Spatial ADTs

3.3.2 Designing Spatial ADTs

3.3.3 Exploring Relationships Between Spatial Objects: Topological Predicates

3.4 Relational Models Extended with ADT

3.4.1 Representation of the Reference Schemas

3.4.2 Reference Queries

3.5 Object-Oriented Models

3.5.1 A Brief Overview of Object-Oriented DBMS

3.5.2 Representation of Reference Schemas

3.5.3 Spatial Classes

3.5.4 Reference Queries

3.6 Bibliographic Notes


4.1 Spatial Data Modeling with Constraints

4.1.1 Point Sets as Infinite Relations

4.1.2 Finitely Representing Infinite Relations

4.1.3 Evaluating Queries on Infinite Instances

4.1.4 Summary of the Constraint Data Model

4.2 The Linear Constraint Data Model

4.2.1 Data Representation

4.2.2 Query Languages: First-Order Queries

4.2.3 Query Languages: Algebraic Queries

4.3 Modeling Entity-Based Data

4.3.1 Nested Relations

4.3.2 Queries

4.4 Modeling Field-Based Data and Moving Objects

4.4.1 Elevation Data

4.4.2 Moving Objects

4.4.3 Queries on Field-Based Data and Moving Points

4.5 Bibliographic Notes


5.1 An Introduction to Computational Geometry

5.2 Background

5.2.1 Basic Concepts of Algorithms

5.2.2 Algorithm Analysis

5.2.3 Optimality

5.2.4 Data Structures

5.3 Useful Algorithmic Strategies

5.3.1 Incremental Algorithms: The Convex-Hull Example

5.3.2 Divide-and-Conquer Strategy: The Half-Plane Intersection Example

5.3.3 Sweep-Line Method: The Rectangle Intersection Example

5.4 Polygon Partitioning

5.4.1 Trapezoidalization of a Simple Polygon

5.4.2 Triangulation of Simple Polygons

5.4.3 Convex Partitioning

5.5 Algorithms for Spatial Databases

5.5.1 Area Size of a Polygon and Related Operations

5.5.2 Point in Polygon

5.5.3 Polyline Intersections

5.5.4 Polygon Intersections

5.5.5 Windowing and Clipping

5.6 Bibliographic Notes

5.6.1 General Sources

5.6.2 Sources on Algorithms


6.1 Issues in SAM Design

6.1.1 What Is Expected of a SAM?

6.1.2 Illustration with a B+Tree

6.1.3 Space-Driven Versus Data-Driven SAMs

6.2 Space-Driven Structures

6.2.1 The Grid File

6.2.2 The Linear Quadtree

6.2.3 The z-Ordering Tree

6.2.4 Remarks on Linear SAM

6.3 Data-Driven Structures: The R-Tree

6.3.1 The Original R-Tree

6.3.2 The R Tree

6.3.3 R-Tree Packing

6.3.4 The R+Tree

6.3.5 Cost Models

6.4 Bibliographic Notes


7.1 An Introduction to Query Processing

7.2 Two Optimal I/O Algorithms

7.2.1 External Sort/Merge

7.2.2 Distribution Sweeping (Rectangle Intersection)

7.3 Spatial Join

7.3.1 z-Ordering Spatial Join

7.3.2 Joining Two R-Trees

7.3.3 Spatial Hash Join

7.4 Complex Queries

7.4.1 Query Execution Plans

7.4.2 Spatial Joins with Refinement Step

7.4.3 Multiway Joins

7.5 Bibliographic Notes


8.1 An Introduction to Commercial Systems

8.1.1 How to Read This Chapter

8.1.2 Interacting with a GIS or with a Spatial DBMS

8.2 ArcInfo

8.2.1 Functionalities of ArcInfo

8.2.2 Spatial and Topological Information in ArcInfo

8.2.3 Representation of Sample Schemas

8.2.4 Querying with ArcInfo

8.3 ArcView GIS

8.3.1 ArcView Spatial Model

8.3.2 Querying with ArcView

8.4 Smallworld

8.4.1 Smallworld Spatial Data Model

8.4.2 Querying with Smallworld Object Browser

8.4.3 Discussion

8.5 Oracle Extension for Handling Spatial Data

8.5.1 Introduction to Oracle Spatial

8.5.2 Spatial Data Model

8.5.3 Spatial Operations

8.5.4 Spatial Indexing and Query Processing

8.6 PostgreSQL

8.6.1 Geometric Types and Operators

8.6.2 Creating the Database

8.6.3 Expressing Queries

8.7 Bibliographic Notes





Spatial Databases is the first unified, in-depth treatment of special techniques for dealing with spatial data, particularly in the field of geographic information systems (GIS). This book surveys various techniques, such as spatial data models, algorithms, and indexing methods, developed to address specific features of spatial data that are not adequately handled by mainstream DBMS technology.

The book also reviews commercial solutions to geographic data handling: ArcInfo, ArcView, and Smallworld GISs; and two extensions to the relational model, PostgreSQL and Oracle Spatial. The authors examine these underlying GIS technologies, assess their strengths and weaknesses, and consider specific uses for which each product is best suited.

Key Features

  • Examines the strengths of various query languages and approaches to query processing.
  • Explains the use of computational geometry in spatial databases GISs, providing necessary background and an in-depth look at key algorithms.
  • Covers spatial access methods, including the R-tree and several space-driven structures, and is filled with dozens of helpful illustrations.


Computer science and GIS professionals.


No. of pages:
© Morgan Kaufmann 2002
18th May 2001
Morgan Kaufmann
Hardcover ISBN:
eBook ISBN:


@qu:"Spatial Databases covers all of the major themes of the field -- representation, query languages, computational geometry, spatial indexing -- using geographic information systems as the principal application domain and motivation. It is an excellent introduction for computer science professionals interested in exploring GIS, and an excellent resource for GIS professionals interested in learning more about the computer science foundations of the field." @source:—Michael F. Goodchild, National Center for Geographic Information and Analysis, and University of California, Santa Barbara @qu:"Spatial Databases is a well-written, comprehensive treatment of a multi-disciplinary field, spanning computational geometry, database modeling, object-orientation, and query processing. The book presents both advanced research and commercial systems in a clear and accessible manner. This book is essential for understanding the current state of the art. Well done!" @source:—Professor Dennis Shasha, New York University

Ratings and Reviews

About the Authors

Philippe Rigaux

Philippe Rigaux is Assistant Professor of Computer Science at CNAM (Conservatoire National des Arts et Métiers), where his work focuses on spatial applications for database systems.

Affiliations and Expertise

CNAM (Conservatoire National des Arts et Métiers), Paris

Michel Scholl

Michel Scholl is a Professor of Computer Science at CNAM and a Senior Researcher at INRIA (French Institut National de Recherche en Informatique et en Automatique). His recent work has focused on spatial databases and digital libraries.

Affiliations and Expertise

CNAM (Conservatoire National des Arts et Métiers) amd INRIA (French Institut National de Recherche en Informatique et en Automatique), Paris

Agnès Voisard

Agnès Voisard is Assistant Professor of Computer Science at the Free University of Berlin and a System Architect at Kivera, Inc. Her research interests include data models for geographic and environmental information systems, interoperability in information systems, and navigation systems.

Affiliations and Expertise

Fraunhofer ISST (Institut für Software- und Systemtechnik)and Free University Berlin, Germany