Efficient Query Processing in Geographic Information SystemsThis monograph describes methods for extending relational database systems for geographic applications. The ways in which a relational database system is supplemented with unconventional spatial indexing structures, additional spatial subsystems and query processors are described in great detail. The work presents an extensive survey of existing spatial indexing techniques and a taxonomy of the extensions to the multidimensional indexing structures. An extensive experimental analysis of spatial indexes is presented. The work covers the following areas: - the design of geographic information systems (GIS) - extended query languages for GIS - spatial indexing mechanisms - query processing strategies. The author presents his own skd-trees and extended query optimization strategies. The survey of spatial indexing structures for non-zero sized objects provides a framework for workers in the field of spatial information systems to evaluate spatial access methods. The consideration of query optimization will assist understanding of the role of that topic in GIS. |
Contents
Introduction | 1 |
12 Motivation | 2 |
13 Indexing Structures | 4 |
14 Query Optimization | 5 |
15 Thesis Synopsis | 6 |
Related Work and GEOQL | 9 |
212 On the Design of a GIS | 10 |
213 Existing Systems | 11 |
351 Page Structure | 97 |
352 Paging Strategy | 98 |
36 Static Tree Construction | 100 |
37 Data Storage Structure | 105 |
38 Spatial Primitive Operations | 107 |
39 Set Operations | 111 |
310 Summary | 115 |
Performance Analysis and Case Studies | 116 |
22 Query Languages | 14 |
222 QBE Extensions | 16 |
223 SQL Extensions | 17 |
224 GEOQL An Augmented SQL | 18 |
23 The Need for Efficient Spatial Indexing Mechanisms | 22 |
24 Point Structures | 23 |
2422 Region QuadTrees | 25 |
243 The kdTrees | 28 |
25 Access Structures for Extended Spatial Objects | 32 |
252 Search Types | 33 |
254 Corner Stitching | 34 |
255 Cell Methods based on Dynamic Hashing | 35 |
2552 The EXCELL Method | 41 |
2553 PLOPHashing | 42 |
257 Locational Keys | 44 |
258 Matsuyamas kdTree | 47 |
259 The4DTree | 49 |
2511 The R+Tree | 52 |
2512 The Cell Tree | 57 |
26 Optimizations | 60 |
262 Definitions | 62 |
263 Optimization Strategies | 63 |
2631 Query Transformation | 64 |
26312 Simplification | 65 |
2632 Query Evaluations | 71 |
2633 Optimization in System R | 73 |
2634 Optimization in INGRES Query Decomposition | 74 |
265 Extensible DBMS and Resident Memory Systems Current Trends | 75 |
266 Optimization in GIS | 77 |
267 Summary | 78 |
The Spatial kdTree | 80 |
32 Searching | 86 |
33 Insertion | 88 |
34 Deletion | 90 |
35 Directory Paging | 96 |
412 Parameters | 117 |
42 A Variant of the skdTree | 118 |
43 Evaluation with Nonuniform Data | 121 |
431 The Skew Factor | 122 |
433 Empirical Results | 123 |
44 Further Comparisons | 129 |
441 Object Mapping Structures | 130 |
442 Object Duplication Structures | 132 |
45 Summary | 135 |
Query Optimization | 136 |
52 Extending Techniques | 137 |
522 Extended Optimization | 138 |
53 Classification of GEOQL Queries | 139 |
54 An Introduction to the Extended Optimization | 141 |
541 Grouping of Predicates | 142 |
5421 The Not Operator | 143 |
55 Optimization Strategy | 144 |
552 Logical Transformation | 145 |
553 Decomposition | 148 |
554 Subquery Sequencing | 153 |
5542 SQP Formulation | 159 |
5543 Cost Estimation | 163 |
56 Conclusions | 164 |
Implementation and Experiments | 166 |
63 The GEOQL Database | 168 |
64 The Experimental System | 169 |
65 Discussion | 176 |
652 Limitations | 177 |
Conclusions | 178 |
| 181 | |
GEOQL Grammar | 196 |
Query Optimization Algorithms | 202 |
Sample Database | 207 |
Other editions - View all
Efficient Query Processing in Geographic Information Systems Beng Chin Ooi No preview available - 2014 |
Common terms and phrases
ACM SIGMOD International algorithm aspatial data attribute bounding rectangle cell tree centroid Comp containment search conventional cost covering rectangles data base data objects data pages data structures database systems DBMS decomposition deletion efficient entries executed Figure geo_obj Geographic Information Systems GEOQL query grid file hi_br IEEE implementation indexing structures insertion interface language internal node intersection search join leaf node lo_br LOSON Management of Data method node.disc non-zero sized objects object duplication optimization strategy parse tree partial result partitioned PLOP-Hashing predicate tree Proc proposed quad-tree query language query optimization query processing query region R-tree railway relational algebra relational database representation retrieval search space SELECT semantic SIGMOD International Conf skd-tree spatial and aspatial spatial data spatial indexing spatial objects spatial operators spatial predicates split SQL backend storage stored strategy tree subquery sequence subspace subtree techniques temporary relation tuple unnested value_expr
Popular passages
Page ii - System Science, National University of Singapore, Heng Mui Keng Terrace, Kent Ridge, Singapore 0511 S.