CONTENTS
Foreword ix
By Victor Vianu, University of California, San Diego
List of Figures xvii
PREFACE xxiii
1 AN INTRODUCTION TO SPATIAL DATABASES 1
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 REPRESENTATION OF SPATIAL OBJECTS 29
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 LOGICAL MODELS AND QUERY LANGUAGES 69
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 THE CONSTRAINT DATA MODEL 113
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 COMPUTATIONAL GEOMETRY 149
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 SPATIAL ACCESS METHODS 201
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 QUERY PROCESSING 267
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 COMMERCIAL SYSTEMS 311
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
BIBLIOGRAPHY 373
INDEX 395
ABOUT THE AUTHORS 409