Research On Spatial Query Optimization

Spatial databases have widely used in the fields of geography information (GIS),CAD/CAM, remote sensing. Spatial objects are stored in spatial database, which aredescribed by spatial data and attribute data together. Spatial data is a term used todescribe data that pertains to the space occupied by objects in the database. Andattribute data is the one used to describe data about the name of the object, etc.Because of the high volume of the spatial data and the complexity of spatial query,spatial query optimization has become the key to applications of spatial database and ahot point in the research of spatial database.This dissertation focuses on optimizing query of spatial data. The research work inthis dissertation is part work of the Tenth National Five-Year Plan of Ministry Scienceand Technology (No. 2002BA107B). The main contents of this Dissertation are asfollows:Firstly, after presenting spatial data and its characteristics, the relative conceptionabout spatial query and spatial query optimization are introduced, and the related studyfields are confirmed.Secondly, we study on three main techniques of spatial query optimization.Techniques of spatial indexes, the estimation of I/O cost of accessing spatial objectbased on spatial indexes and the estimation of the size of query result based onhistogram are given in detail respectively. The cost model based on Euler Histogram isthe focal point of the dissertation.Further, to the boundary problem of Euler Histogram, we propose Closed_EulerHistogram. Based on MBRs and SCPs approximations, the correctness of it statisticalmethod has been proved. And we discuss how to estimate the size of query result withClosed_Euler Histogram.Finally, based on the research work above, we discuss the efficiency and feasibilityof the integration of Closed_Euler Histogram and practical query optimizer through anemulation experiment.The works in this dissertation enrich and expand the theories for spatial queryoptimization based on cost models, and expand the research range and content of costmodel based on histograms. These researches provide a feasible path for improvingefficiency of queries in spatial database.