Spatial Databases: With Application to GIS
(The Morgan)
Philippe Rigaux
Michel Scholl
Agnes Voisard
Morgan Kaufmann Publishers
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) 3
1.1.1 Basic Description and Main Features 3
1.1.2 Modeling Applications 6
1.1.3 Physical Data Management 8
1.2 Vocabulary in Geospatial Database Applications 9
1.2.1 Theme 9
1.2.2 Geographic Objects 9
1.3 Geospatial Data Manipulation 11
1.3.1 Simple Operations on Themes 12
1.3.2 Further Theme Operations 18
1.3.3 Other Typical GIS Operations 20
1.4 DBMS Support for Geospatial Data 21
1.4.1 Use of a Relational DBMS 22
1.4.2 Loosely Coupled Approach 24
1.4.3 Integrated Approach Based on DBMS Extensibility 25
1.5 Requirements for a Spatial DBMS 25
1.6 Bibliographic Notes 26
2 REPRESENTATION OF SPATIAL OBJECTS 29
2.1 Geographic Space Modeling 31
2.1.1 Entity-Based Models 31
2.1.2 Field-Based Models 34
2.2 Representation Modes 35
2.2.1 Tessellation 35
2.2.2 Vector Mode 38
2.2.3 Half-Plane Representation 42
2.3 Representing the Geometry of a Collection of Objects 46
2.3.1 Spaghetti Model 47
2.3.2 Network Model 47
2.3.3 Topological Model 49
2.4 Spatial Data Formats and Exchange Standards 51
2.4.1 Overview of Current Spatial Data Formats 52
2.4.2 The TIGER/Line Data Format 54
2.4.3 Recent Standardization Initiatives 61
2.5 Bibliographic Notes 64
3 LOGICAL MODELS AND
QUERY LANGUAGES 69
3.1 Reference Schemas 71
3.1.1 Administrative Units (Schema 1) 71
3.1.2 Highway Network Among Cities (Schema 2) 72
3.1.3 Land Use (Schema 3) 72
3.2 Reference Queries 73
3.3 Spatial Abstract Data Types 75
3.3.1 Extending Data Models with Spatial ADTs 75
3.3.2 Designing Spatial ADTs 80
3.3.3 Exploring Relationships Between Spatial Objects:
Topological Predicates 85
3.4 Relational Models Extended with ADT 88
3.4.1 Representation of the Reference Schemas 89
3.4.2 Reference Queries 92
3.5 Object-Oriented Models 100
3.5.1 A Brief Overview of Object-Oriented DBMS 100
3.5.2 Representation of Reference Schemas 101
3.5.3 Spatial Classes 104
3.5.4 Reference Queries 106
3.6 Bibliographic Notes 108
4 THE CONSTRAINT DATA MODEL 113
4.1 Spatial Data Modeling with Constraints 114
4.1.1 Point Sets as Infinite Relations 115
4.1.2 Finitely Representing Infinite Relations 117
4.1.3 Evaluating Queries on Infinite Instances 120
4.1.4 Summary of the Constraint Data Model 122
4.2 The Linear Constraint Data Model 123
4.2.1 Data Representation 124
4.2.2 Query Languages: First-Order Queries 125
4.2.3 Query Languages: Algebraic Queries 128
4.3 Modeling Entity-Based Data 134
4.3.1 Nested Relations 134
4.3.2 Queries 136
4.4 Modeling Field-Based Data and Moving Objects 139
4.4.1 Elevation Data 140
4.4.2 Moving Objects 141
4.4.3 Queries on Field-Based Data and Moving Points 143
4.5 Bibliographic Notes 145
5 COMPUTATIONAL GEOMETRY 149
5.1 An Introduction to Computational Geometry 150
5.2 Background 150
5.2.1 Basic Concepts of Algorithms 151
5.2.2 Algorithm Analysis 152
5.2.3 Optimality 153
5.2.4 Data Structures 155
5.3 Useful Algorithmic Strategies 157
5.3.1 Incremental Algorithms: The Convex-Hull Example 157
5.3.2 Divide-and-Conquer Strategy: The Half-Plane Intersection
Example 161
5.3.3 Sweep-Line Method: The Rectangle Intersection
Example 164
5.4 Polygon Partitioning 167
5.4.1 Trapezoidalization of a Simple Polygon 168
5.4.2 Triangulation of Simple Polygons 170
5.4.3 Convex Partitioning 173
5.5 Algorithms for Spatial Databases 175
5.5.1 Area Size of a Polygon and Related Operations 176
5.5.2 Point in Polygon 177
5.5.3 Polyline Intersections 179
5.5.4 Polygon Intersections 186
5.5.5 Windowing and Clipping 192
5.6 Bibliographic Notes 197
5.6.1 General Sources 197
5.6.2 Sources on Algorithms 198
6 SPATIAL ACCESS METHODS 201
6.1 Issues in SAM Design 204
6.1.1 What Is Expected of a SAM? 205
6.1.2 Illustration with a B+Tree 206
6.1.3 Space-Driven Versus Data-Driven SAMs 207
6.2 Space-Driven Structures 208
6.2.1 The Grid File 209
6.2.2 The Linear Quadtree 219
6.2.3 The z-Ordering Tree 227
6.2.4 Remarks on Linear SAM 237
6.3 Data-Driven Structures: The R-Tree 237
6.3.1 The Original R-Tree 238
6.3.2 The R∗Tree 252
6.3.3 R-Tree Packing 255
6.3.4 The R+Tree 257
6.3.5 Cost Models 259
6.4 Bibliographic Notes 261
7 QUERY PROCESSING 267
7.1 An Introduction to Query Processing 269
7.2 Two Optimal I/O Algorithms 271
7.2.1 External Sort/Merge 271
7.2.2 Distribution Sweeping (Rectangle Intersection) 274
7.3 Spatial Join 279
7.3.1 z-Ordering Spatial Join 280
7.3.2 Joining Two R-Trees 284
7.3.3 Spatial Hash Join 288
7.4 Complex Queries 292
7.4.1 Query Execution Plans 292
7.4.2 Spatial Joins with Refinement Step 296
7.4.3 Multiway Joins 300
7.5 Bibliographic Notes 303
8 COMMERCIAL SYSTEMS 311
8.1 An Introduction to Commercial Systems 312
8.1.1 How to Read This Chapter 312
8.1.2 Interacting with a GIS or with a Spatial DBMS 315
8.2 ArcInfo 317
8.2.1 Functionalities of ArcInfo 317
8.2.2 Spatial and Topological Information in ArcInfo 319
8.2.3 Representation of Sample Schemas 328
8.2.4 Querying with ArcInfo 332
8.3 ArcView GIS 341
8.3.1 ArcView Spatial Model 342
8.3.2 Querying with ArcView 343
8.4 Smallworld 347
8.4.1 Smallworld Spatial Data Model 347
8.4.2 Querying with Smallworld Object Browser 348
8.4.3 Discussion 351
8.5 Oracle Extension for Handling Spatial Data 352
8.5.1 Introduction to Oracle Spatial 352
8.5.2 Spatial Data Model 353
8.5.3 Spatial Operations 355
8.5.4 Spatial Indexing and Query Processing 357
8.6 PostgreSQL 360
8.6.1 Geometric Types and Operators 361
8.6.2 Creating the Database 363
8.6.3 Expressing Queries 364
8.7 Bibliographic Notes 368
BIBLIOGRAPHY 373
INDEX 395
ABOUT THE AUTHORS 409
للقراءة والتحميل اضغط هنا
ليست هناك تعليقات:
إرسال تعليق