空间数据库中连接查询方法的研究

摘要

空间数据库技术是当前数据库领域中的研究热点，在国内外的许多不同领域都得到了应用。由于空间数据库中的数据无序、庞大，以及空间对象与空间查询的高度复杂性，使得查询效率成为衡量空间数据库性能的重要指标，并且实际应用也对空间数据库的查询性能提出了迫切要求。
　　 空间连接操作是空间数据库中的一种基本操作，同时它也是最耗时、最复杂的操作之一。在众多的空间连接方法之中，当两个数据集均建立R-树索引时，基于R-树的连接算法性能最佳。R-树空间连接算法根据遍历策略的不同有两种经典的算法，深度优先的R-树空间连接算法(Depth-First R-tree Join，DFRJ)和广度优先的R-树空间连接算法(Breadth-First R-tree Join，BFRJ)。后来出现的基于广度优先搜索的层内分组扫描策略的R-树空间连接算法(Breadth-First Group-based Sweeping，BFGS)就是基于BFRJ算法提出来的。BFRJ和BFGS算法都是效率很高的算法，但是这些算法对中间连接索引(Intermediate Join Index，IJI)进行排序时，并没有将中间连接索引的二元组的两个数据项进行充分考虑，没有考虑到空间相接近的对象它们重叠的对象也可能是相同的，这样就不能充分利用缓冲区中的数据。针对这样的问题，使用一种空间填充曲线(Adaptive Row Major Order，ARMO)对中间连接索引进行了排序。
　　 首先，本文对基于R-树的空间连接算法进行研究，从广度优先策略的R-树空间连接算法的原理、特点和流程出发，分析中间连接索引优化排序对算法的重要性及对算法性能的影响。其次，本文基于BFRJ算法提出了一种对中间连接索引优化排序的空间连接算法(Optimal Breadth-First R-tree Join，OBFRJ)。该算法使用广度优先顺序对两棵R-树进行同步遍历，对生成的中间连接索引采用一种空间填充曲线进行排序，使得在下一层的连接时出现页错误的次数减少。最后，论文把OBFRJ算法同其它基于R-树的空间连接算法进行理论分析和比较，同时在开源的对象-关系数据库PostgreSQL8.3上实现了OBFRJ算法并且进行了相关的实验测试，通过实验表明，特别是在缓冲区较大时，改进的算法在CUP代价和I/O代价上都要小于BFGS算法，能够更好的满足查询的需求。