Spatial Databases

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