Efficient query processing in geographic information systems (Q1188802)

Standard relational database management systems (RDBMS) are not well- suited for handling spatial data. Two primary approaches for dealing with spatial data can be found in the field of geographic information systems (GIS): the design of new systems with a special purpose language, extended data types and a special graphical processor or the extension of existing RDBMS to accommodate management of spatial data. Beng Chin Ooi's book belongs to the second approach. He uses a conventional DBMS, which provides efficient storage and retrieval of a spatial data and a spatial processor, which handles the spatial components of the queries. GIS, as a growing field, gives rise to many subfields. These include data models and data structures, new indexing mechanisms, query languages and optimization techniques, user interfaces, spatial cognition, spatial reasoning and analysis. The author's focus on such a small subfield is legitimite as the work is based upon his doctoral dissertation. The reader is introduced to various spatial indexing mechanisms and several query optimization issues. In the first chapter the author summarizes the book's most essential topics. The chapter can be viewed as a lengthy abstract of the text. Chapter 2 gives a broad insight into the state-of- the art technology relevant to the work. Approximately one third of the book is devoted to the review of implemented systems, query languages, data and access structures. The point and region quad-tree, the \(kd\)- tree, the 4-\(D\)-tree and the \(R\)-tree are also explained here. These structures are suitable for aspatial point objects as well as for nonzero spatial objects. The chapter concludes with an overview of the variety of optimization strategies. In Chapter 3 the author presents his developed data structure, the spatial \(kd\)-tree \((skd\)-tree), based on the \(kd\)- tree. One can find algorithms for inserting, updating and searching, whereby intersection search and containment search are directly supported. To substantiate the claim that the \(skd\)-tree is an efficient structure, a performance analysis is undertaken in chapter 4. Experimental results from the \(skd\)-tree are compared with both the \(R\)- tree and the \(kd\)-tree using the object mapping technique \((4d\)-tree) on the one hand and the object duplication technique \((mkd\)-tree) on the other hand. A simulation study with 9 sets of skewed and uniform data, 4 indexing structures and 5 page sizes form the basis of 180 experiments in both cases. The author comes to the conclusion that in general the \(skd\)- tree is a more efficient data structure for supporting both containment and intersection searches compared to the \(R\)-tree, the \(kd\)-tree and the \(mkd\)-tree, respectively. Chapter 5 takes up the issue of query optimization introduced in previous chapters. The major contribution here is the presentation of a global optimization strategy for the extended SQL query language, GEOSQL. From the point of view of system architecture, the following modules are necessary: logical transformation, decomposition, plans formulation, selection, and execution. The extension to standard RDBMS is minor: the SQL parser can parse a larger set of predicates than SQL predicates and the extended optimizer is based upon existing optimizers. A feasibility study in chapter 6 presents and discusses the implemented system with a small spatial database and one spatial query together with the optimization strategy. The author himself concedes that more studies are required. Chapter 7 provides a summary of the book. The text concludes with an extensive bibliography and three appendices containing the GEOQL Grammar, the query optimization algorithms and the sample database. Ooi's text belongs to the new and growing field of GIS, whose date of birth can be traced to the First Symposium on the Design and Implementation of Large Spatial Databases (SSD '89) in Santa Barbara, California. For the reader interested in a cohensive presentation of the topic efficient query processing and its implications, this text will surely be to his or her gain. It may serve as an introductory text as well as providing one possible solution to the problem of efficient spatial query processing in extending the standard query language SQL. The text could have been improved by better structuring the contents and by avoiding the frequent repetitions made in the introductions and summaries of the chapters.