受限空间连接查询及代价分析

杨泽雪，郝忠孝

（1.哈尔滨理工大学计算机科学与技术学院，150080 哈尔滨;2.黑龙江工程学院计算机科学与技术系，150050 哈尔滨;3.哈尔滨工业大学计算机科学与技术学院，150001 哈尔滨）

受限空间连接查询及代价分析

杨泽雪1，2，郝忠孝1，3

（1.哈尔滨理工大学计算机科学与技术学院，150080 哈尔滨;2.黑龙江工程学院计算机科学与技术系，150050 哈尔滨;3.哈尔滨工业大学计算机科学与技术学院，150001 哈尔滨）

针对已有的空间连接查询算法无法解决限定范围内的空间连接查询问题，提出了受限的空间连接查询，在给定查询范围内找到满足某种空间谓词的空间对象，给出直接解决方法和基于R－树的受限空间连接查询算法.基于QR树的优良特性，提出一种基于QR树的受限空间连接查询算法，该算法既避免了四叉树的较大存储代价，又克服了R树的节点重复的弊端，使得受限空间连接查询可以在多棵较小的R树上进行，较好地解决了空间连接查询开销较大的问题.对所提出的算法进行代价分析，实验证明算法具有较高效率.

空间连接查询;QR树;空间数据库;R树;受限空间连接查询

近年来空间连接查询成为空间数据库中的热点问题.给定两个空间数据集，空间连接查询找到两个数据集中所有满足某个空间谓词的对象.空间谓词包括交叠、相交、方向和距离等，本文主要研究相交的情况.例如:找到与某条河流相交的所有城市.按照两个空间数据集是否有索引，可以将空间连接查询分为3种情况:两个数据集都有索引［1－7］;一个数据集有索引［8－9］;两个数据集都没有索引.

对于受限的空间连接查询，没有找到文献.考虑到若对于两个数据集的空间连接只考虑某个限定的空间而不是整个空间，提出了受限的空间连接查询.例如:找到某个国家与河流相交的城市.而已有的算法都不能直接用于某个限定的空间，根据已有的空间连接方法和范围查询方法，给出受限空间连接的直接解决方法，并给出基于R－树的受限空间连接算法.针对基于R－树的空间连接方法和四叉树的空间连接方法的局限性，提出了基于QR树的受限空间连接方法.

1 QR 树［10］

图1是二维空间QR树的一个例子.在该例中，QR树由一棵深度为2的四叉树和5棵R树组成.整个空间被划分为2级共5个子空间:S0，S1，S2，S3，S4(S0=S1∪ S2∪ S3∪ S4)，Rt0，Rt1，Rt2，Rt3，Rt4这5棵R树分别与之相关联.

图1 二维空间QR－树

2 基于R－树的受限空间连接查询

2.1 受限空间连接查询的直接解决方法

给定两个数据集和一个查询范围，受限的空间连接(CSJ)查询是指找到与给定查询范围相交的且满足某空间谓词的数据对象的集合.

受限的空间连接查询是空间连接查询和空间范围查询的结合.虽然已有很多方法解决了空间连接查询和范围查询，但已有的方法并不能直接实现受限的空间连接查询.对于受限的空间连接查询，直接的解决方法就是顺序执行两个算法，按照两个算法的执行顺序分为两种方法，一种是先进行范围查询，然后再进行连接查询，此方法表示为FRLJ.另一种方法是先进行连接查询，然后在进行范围查询，此方法表示为FJLR.

假设两个数据集都由R－树索引，对应R－树索引分别为A和B，给定受限空间为W.利用基于R－树的空间连接算法和基于R－树的空间范围查询算法［11］，实现FRLJ的过程如下:

1)对A、B在W上分别执行范围查询算法，获取A中与W相交的结果集R1和B中与W相交的结果集R2;

2)对R1和R2执行基于R－树的空间连接算法，得到最终结果.

实现FJLR的过程如下:

1)对A、B执行基于R树的空间连接算法，获取两个数据集中相交的对象对的集合R;

2)对R执行范围查询算法，判断R中每一对对象对应MBR是否与W相交，若相交，输出结果，否则继续其他结果的判断.

分析两种方法发现，如果受限范围较小，FRLJ的效果较好，因为执行范围查询可以剪掉许多不会成为结果的节点，但随着受限范围的增大，FRLJ的优势逐渐减小;而对于FJLR来说，首先执行连接查询，对于两个数据集的数量都不是很大时，效果较好，但随着数据量的增大，连接代价变得很昂贵，因此效率不高.

2.2 基于R树的受限空间连接查询算法

基于上述分析，将范围查询和空间连接查询结合在一起，提出基于R－树的受限空间连接算法RCSJ.该算法的基本思想是:对两棵R树进行同步遍历，在遍历过程中，设定节点是否与限定范围W相交作为条件，按照节点的类型可分为两个节点都为叶节点、一个为叶节点另一个为中间节点和两个都为中间节点3种情况分别进行处理.

3 基于QR－树的受限空间连接查询

利用QR树将四叉树和R－树相结合的良好特性，提出一种基于QR树的受限空间连接算法，在连接查询的过程中判断节点是否与限定空间相交，通过一次的树遍历可得到查询结果.算法的基本思想是:利用四叉树将空间进行划分，然后在每个子空间按照数据进行划分构成R－树，利用R－树实现受限空间连接.因此按照空间划分和数据划分两个方面实现受限空间连接.给定两个数据集和对应的两棵QR树，首先将两棵QR树的四叉树节点进行匹配，然后将匹配的节点对所对应的R－树的MBR以及受限空间进行相交判断，如果相交，则调用对应的R－树进行连接.

3.1 节点匹配算法

考虑到QR树的构成，将节点分配到包含该节点的子空间中的最小者，则上一层子空间节点可能与下一层子空间的节点相交.所以要进行不同层空间的节点匹配.算法如下.

3.2 连接算法

算法思想如下.

1)从两棵QR树的根开始，对两棵QR树进行同步遍历.

2)对于每一对节点，对与节点相关联的子空间和受限空间进行相交判断，如果相交，则调用相应的R－树进行连接，否则对该节点及其子节点的判断结束.

3)针对两个节点的类型，分成3种情况，对每种情况分别进行处理.

算法 2QRCSJ(NA，NB，W)

输入:两棵 QR 树 A、B 的节点 NA，NB，限定空间W;

输出:相交的数据对组成的结果集CRL.

4 代价分析

4.1 基于R树的受限空间连接查询代价分析

因为进行受限空间连接要计算每一层节点与W相交且彼此相交的数据个数，因此要计算每一层R－树节点与W相交的概率，为此有

所以总的连接代价为

4.2 基于QR树的受限空间连接查询代价分析

设两棵QR树分别为 ＜A，RA＞＜B，RB＞，其对应数据个数分别为MA，MB，树的高度分别为hA，hB，设hA≤hB，两棵QR树划分子空间的个数分别为nA，nB，则对应R － 树个数也为nA，nB，其中

假设数据均匀分布，每棵R－树对应的数据个数为MA/nA，MB/nB，设两棵R － 树RAu，RBv的高度分别为hRAu和hRBv，设hRAu≥hRBv，由上述分析可知，两棵R－树进行空间连接代价为

式中:NRAu，j为 RAu 在第 j层的结点数;sRAu，j，t为 RAu在第j层的结点的平均范围.

对于QR－树的受限空间连接代价，主要计算进行R－树连接的次数，按照两个QR－树节点是否同层，分别考虑:

综合以上两种情况，基于QR－树的受限连接查询总代价为

4.3 两种查询代价比较

要比较QRCSJ和RCSJ的查询代价，通过计算比值ratio=CQR(A，B)/CR(A，B)的值来衡量，如果ratio＜1，说明QRCSJ要比RCSJ好.

因此CQR(A，B)明显小于CR(A，B).

5 结果

实验是在 PentiumⅣ2.8 GHz CPU，1 GB内存，Windows XP平台上用Visual C++6.0实现的，磁盘页大小为1 024 Bytes.测试数据是由Spa－tial Data Generator(http://www.rtreeportal.org)产生的标准分布的数据，数据尺寸为12、13 K.对数据进行实验，图2对受限范围的大小对各个算法的影响进行了实验.图2中，x坐标轴表示受限范围的占整个数据空间的百分比，FRLJ、FJLR、RCSJ和QRCSJ表示上述的4种受限空间连接算法，其中QR－树的高度为3.由图2可知，基于QR树的受限空间连接查询明显优于其他几个算法.随着查询范围的增大，FRLJ的查询时间逐渐增加，这是因为随着查询范围的增大，先做范围查询的优势越来越小，当查询范围变为整个数据区域的时候，FRLJ的效率是很低的.FJLR的查询时间逐渐变少，这是因为随着查询范围的增大，由连接查询得到的中间结果可能成为最终结果的可能性逐渐增大.

图2 算法执行时间比较

6 结论

1)提出受限的空间连接查询，给出直接的解决方法和基于R－树的受限空间连接算法.基于QR树的优良特性，给出了基于QR树的受限空间连接算法.

2)通过代价分析得到基于QR树的受限空间连接算法与基于R树的算法代价比值小于1，证明所提算法优于其他的方法.

［1］BRINKHOFF T，KRIEGEL H P，SEEGER B.Efficient processing of spatial joins using R－trees［C］//Proceedings of the ACM SIGMOD International Conference on Management of Data.Washington，DC:ACM，1993:237－246.

［2］HUANG Yunwu，JING Ning，RUNDENSTEINER E A.Spatial joins using R－trees:breadth－first traversal with global optimizations［C］//Proceedings of the 23rd International Conference on Very Large Data Bases.San Francisco， CA:Morgan Kaufmann PublishersInc，1997:396－405.

［3］BRINKHOFF T，KRIEGEL H P，SEEGER B.Parallel processing of spatial joins using R－trees［C］//Proceedings of the 12th International Conference on Data Engineering.New Orleans:IEEE，1996:258－265.

［4］CHEN Hue－ling，CHANG Ye－in.Spatial joins based on NA－trees［J］.Journal Information Processing Letters，2009，109(13):713－718.

［5］HOEL E G，SAMET H.Benchmarking spatial join operations with spatial output［C］//Proceedings of the 21th International Conference on Very Large Data Bases.San Francisco:Morgan Kaufmann Publishers Inc，1995:606－618.

［6］LIMA A A B，ESPERANCA C，MATTOSO M.A parallel spatial join framework using PMR－quadtrees［C］//Proceedings of the 11th International Workshop on Database and Expert Systems Applications.Los Alamitos:IEEE，2000:889－893.

［7］郝忠孝.时空数据库－查询与推理［M］.北京:科学出版社，2010:220－230.

［8］GURRET C，RIGAUX P.The sort/sweep algorithm:a new method for R－tree based spatial joins［C］//Proceedings of the 12th International Conference on Statistical and Scientific Database Management.Washington，DC:IEEE Computer Society，2000:153－165.

［9］JACOX E H，SAMET H.Spatial join techniques［J］.ACM Transactions on Database Systems，2007，32(1):1－44.

［10］FU Yuchen，HU Zhiyong，WEI Guo，et al.QR－tree:a hybrid spatial index structure［C］//Proceedings of International Conference on Machine Learning and Cybernetics.Xi－an:Institute of Electrical and Electronics Engineers Inc，2003:459－463.

［11］GUTTMAN A.R－trees:a dynamic index structure for spatial searching［J］.ACM SIGMOD，1984，14(2):47－57.

［12］THEODORIDIS Y，STEFANAKIS E，SELLIS T.Efficient cost models for spatial queries using R－trees［J］.IEEE TKDE，2000，12(1):19－32.

Constrained spatial join queries and cost analysis

YANG Ze－xue1，2，HAO Zhong－xiao1，3

(1.College of Computer Science and Technology，Harbin University of Science and Technology，150080 Harbin，China;2.Dept.of Computer Science and Technology，Heilongjiang Institute of Technology，150050 Harbin，China;3.College of Computer Science and Technology，Harbin Institute of Technology，150001 Harbin，China)

Aimed at the problem that the existed spatial join algorithms can not solve the spatial join query within the constrained range，the constrained spatial join query is proposed which finds all the pairs of objects satisfying some spatial predicate within the given range.The directed solving methods and algorithms based on R－tree are given.Based on good property of QR－tree，a constrained spatial join algorithm is proposed which avoids larger storage cost of quadtree and overcomes the drawbacks of R－tree node overlapping.Thus the algorithm implements the constrained spatial join query on many small R－tree and the problem of expensive spatial join overhead is solved.The cost analysis for the proposed algorithms is given.Experiments show the algorithm has high efficiency.

spatial join query;QR－tree;spatial database;R－tree;constrained spatial join query

TP311.13

A

0367－6234(2012)11－118－05

2011－08－22.

国家自然科学基金资助项目(60673136);黑龙江省自然科学基金资助项目(F201134).

杨泽雪(1978—)，女，博士，讲师;

郝忠孝(1940—)，男，教授，博士生导师.

杨泽雪，yzx1978@126.com.

(编辑 张 红)