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
algorithm applications approach aspatial associated attribute bounding rectangle Chapter common Conf consider contain conventional cost covering data base data structures database database systems DBMS decomposition defined deletion described dimension duplication dynamic efficient entries evaluation example executed existing expression extended Figure geographic GEOQL given grid hence identifier implementation indexing structures insertion internal intersection involving join leaf node logical Management method objects operations optimization partial result partitioned performed possible predicate problem Proc processing produced proposed quad-tree query query language query optimization query processing R-tree railway record rectangles reduce region relation representation represented retrieval road root rules SELECT semantic sequence skd-tree space spatial spatial indexing spatial objects spatial predicates split storage stored strategy subqueries subspace subtree Table techniques transformation tree tuple
Popular passages
Page ii - System Science, National University of Singapore, Heng Mui Keng Terrace, Kent Ridge, Singapore 0511 S.
Bibliographic information
| Title | Efficient Query Processing in Geographic Information Systems Volume 471 of Lecture Notes in Computer Science, ISSN 0302-9743 |
| Author | Beng Chin Ooi |
| Edition | illustrated |
| Publisher | Springer Science & Business Media, 1990 |
| ISBN | 3540534741, 9783540534747 |
| Length | 208 pages |
| Subjects | › › Computers / Computer Science Computers / Data Science / Data Modeling & Design Computers / Database Administration & Management Computers / Information Technology Computers / Information Theory Computers / Programming / Algorithms Computers / System Administration / Storage & Retrieval Science / Earth Sciences / Geography Technology & Engineering / Remote Sensing & Geographic Information Systems |
| Export Citation | BiBTeX EndNote RefMan |