Research Of Spatial Join And Query Optimization In Spatial Databases

Spatial database is a new database technology,promoted by kinds of development and applications of geographical information systems.The performance problem of spatial database limits its application and development seriously.Among spatial operations,spatial join is one of the most useful.Spatial join is the most complex and time-consuming operation in spatial database system.Its efficiency determines the performance of the whole spatial database system to a great extent.Although there are many spatial join algorithms,cost estimation and query optimization of spatial join operation need further study.Based on analyzing some spatial-temporal database query methods,this thesis proposed a new raster approximation suitable to performing spatial joins as a filter in the second step of the Multi-Step Query Processor,involving these three common data types(polygon,polyline and point) and the classes of different spatial joins involving them.We proposed a raster signature named—Three-Color Raster Signature(3CRS).The 3CRS is based on 4CRS.3CRS is a compact and approximated raster representation of objects upon a grid of cells that uses few colors.Each color represents an intersection type between the object and the cell.Actually,3CRS is a 4CRS where the Weak and Strong cell types are replaced by an Inconclusive type.The Weak 4CRS cell type represents that the polygon has an intersection equal or less than 50%with the cell,and the Strong type represents an intersection greater than50%and less than 100%.The 3CRS Inconclusive cell type replaces these two types,and it represents that there is a portion of the object within the cell,which does not overlap the whole cell. This characteristic allows 3CRS to represent polylines and points in the same way it represents polygons.The 3CRS signature has the main advantage of faster generation time and that it can be used to represent polygons,polylines and points(without any specific characteristic).We analyzed the type of the cells of the 3CRS,provided an algorithm to generate 3CRS and gave an algorithm for change of scale.In the end,this thesis gave an algorithm for spatial joins query optimization which is based on the 3CRS.Besides,we analyzed the algorithm and the results demonstrated the effectiveness of the approach.