Spatial Databases

With Application to GIS


  • Philippe Rigaux, CNAM (Conservatoire National des Arts et Métiers), Paris
  • Michel Scholl, CNAM (Conservatoire National des Arts et Métiers) amd INRIA (French Institut National de Recherche en Informatique et en Automatique), Paris
  • Agnès Voisard, Fraunhofer ISST (Institut für Software- und Systemtechnik)and Free University Berlin, Germany

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.

View full description


Computer science and GIS professionals.


Book information

  • Published: May 2001
  • ISBN: 978-1-55860-588-6


"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."
—Michael F. Goodchild, National Center for Geographic Information and Analysis, and University of California, Santa Barbara

"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!"
—Professor Dennis Shasha, New York University

Table of Contents

FOREWORDby Victor Vianu, University of California, San DiegoLIST OF FIGURESPREFACE1 AN INTRODUCTION TO SPATIAL DATABASES1.1 Database Management Systems (DBMSs)1.1.1 Basic Description and Main Features1.1.2 Modeling Applications1.1.3 Physical Data Management1.2 Vocabulary in Geospatial Database Applications1.2.1 Theme1.2.2 Geographic Objects1.3 Geospatial Data Manipulation1.3.1 Simple Operations on Themes1.3.2 Further Theme Operations1.3.3 Other Typical GIS Operations1.4 DBMS Support for Geospatial Data1.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 Notes2 REPRESENTATION OF SPATIAL OBJECTS2.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 Model2.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 Notes3 LOGICAL MODELS AND QUERY LANGUAGES3.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 ADTs3.3.2 Designing Spatial ADTs3.3.3 Exploring Relationships Between Spatial Objects: Topological Predicates3.4 Relational Models Extended with ADT 3.4.1 Representation of the Reference Schemas3.4.2 Reference Queries3.5 Object-Oriented Models 3.5.1 A Brief Overview of Object-Oriented DBMS3.5.2 Representation of Reference Schemas 3.5.3 Spatial Classes 3.5.4 Reference Queries3.6 Bibliographic Notes4 THE CONSTRAINT DATA MODEL4.1 Spatial Data Modeling with Constraints4.1.1 Point Sets as Infinite Relations4.1.2 Finitely Representing Infinite Relations 4.1.3 Evaluating Queries on Infinite Instances 4.1.4 Summary of the Constraint Data Model4.2 The Linear Constraint Data Model 4.2.1 Data Representation4.2.2 Query Languages: First-Order Queries 4.2.3 Query Languages: Algebraic Queries4.3 Modeling Entity-Based Data 4.3.1 Nested Relations4.3.2 Queries4.4 Modeling Field-Based Data and Moving Objects 4.4.1 Elevation Data4.4.2 Moving Objects 4.4.3 Queries on Field-Based Data and Moving Points4.5 Bibliographic Notes5 COMPUTATIONAL GEOMETRY5.1 An Introduction to Computational Geometry 5.2 Background 5.2.1 Basic Concepts of Algorithms5.2.2 Algorithm Analysis 5.2.3 Optimality 5.2.4 Data Structures5.3 Useful Algorithmic Strategies 5.3.1 Incremental Algorithms: The Convex-Hull Example5.3.2 Divide-and-Conquer Strategy: The Half-Plane Intersection Example 5.3.3 Sweep-Line Method: The Rectangle Intersection Example5.4 Polygon Partitioning 5.4.1 Trapezoidalization of a Simple Polygon5.4.2 Triangulation of Simple Polygons 5.4.3 Convex Partitioning5.5 Algorithms for Spatial Databases 5.5.1 Area Size of a Polygon and Related Operations5.5.2 Point in Polygon 5.5.3 Polyline Intersections 5.5.4 Polygon Intersections 5.5.5 Windowing and Clipping5.6 Bibliographic Notes 5.6.1 General Sources 5.6.2 Sources on Algorithms6 SPATIAL ACCESS METHODS6.1 Issues in SAM Design6.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-Tree6.3.2 The RTree 6.3.3 R-Tree Packing 6.3.4 The R+Tree 6.3.5 Cost Models6.4 Bibliographic Notes7 QUERY PROCESSING7.1 An Introduction to Query Processing7.2 Two Optimal I/O Algorithms 7.2.1 External Sort/Merge7.2.2 Distribution Sweeping (Rectangle Intersection)7.3 Spatial Join 7.3.1 z-Ordering Spatial Join7.3.2 Joining Two R-Trees 7.3.3 Spatial Hash Join7.4 Complex Queries 7.4.1 Query Execution Plans7.4.2 Spatial Joins with Refinement Step 7.4.3 Multiway Joins7.5 Bibliographic Notes8 COMMERCIAL SYSTEMS8.1 An Introduction to Commercial Systems8.1.1 How to Read This Chapter8.1.2 Interacting with a GIS or with a Spatial DBMS8.2 ArcInfo8.2.1 Functionalities of ArcInfo8.2.2 Spatial and Topological Information in ArcInfo8.2.3 Representation of Sample Schemas 8.2.4 Querying with ArcInfo8.3 ArcView GIS 8.3.1 ArcView Spatial Model8.3.2 Querying with ArcView8.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 Model8.5.3 Spatial Operations8.5.4 Spatial Indexing and Query Processing8.6 PostgreSQL 8.6.1 Geometric Types and Operators8.6.2 Creating the Database8.6.3 Expressing Queries8.7 Bibliographic NotesBIBLIOGRAPHYINDEXABOUT THE AUTHORS