空间数据库中连接运算的处理与优化

空间数据库的性能问题严重制约了它的应用与发展 .由于空间连接运算是空间数据库中最复杂、最耗时的基本操作 ,因此其处理效率在很大程度上决定了空间数据库的整体性能 .尽管目前已经有许多空间连接算法 ,但空间连接运算的代价估计和查询优化仍然有待进一步研究 .众所周知 ,大部分空间连接算法都是基于 R树索引实现的 ,如果参与空间连接运算的关系上没有索引或只有部分索引 ,那么就需要使用特殊的算法来处理 .另外 ,各种算法的代价评估模型需要一个相对统一的计算方法 ,实践证明 ,根据空间数据库的实际情况 ,使用 I/ O代价来估计算法的复杂性较为合理 .在此基础上 ,针对复杂的空间查询中可能出现多个关系参与空间连接运算的情况 ,故还需要合理地应用动态编程算法来找出代价最优的连接顺序 ,以便最终形成一个通用的算法框架 .通过对该算法框架的复杂性分析可以看出 ,在此基础上实现的空间数据库查询优化系统将具有较高的时空效率 ,并且能够处理非常复杂的空间查询

Processing and Optimization of Join Operation in Spatial Database

The performance problem of spatial database limits its application and development seriously. 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 already, cost estimation and query optimization of spatial join operation need further study. Most spatial join algorithms are implemented based on R tree index, but if the corresponding relations have no indices, or only have partly indices, special algorithms should be used to handle the situation. Cost estimation models of each algorithm need a relatively uniform calculation method. Considering the characteristic of spatial database, it's reasonable to use I/O cost to estimate the complexity of each algorithm. Based on the above approaches, and because complex spatial queries may include multiple relations for spatial join, dynamic programming algorithm should be used to choose the proper join order which has minimum cost. It becomes a universal algorithm framework. Through the complexity analysis of the algorithm framework, the spatial database query optimization system implemented base on this approach will have better spatial and temporal efficiency, and can handle very complex spatial queries.