受限空間連接查詢及代價分析

楊澤雪，郝忠孝

（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.

(編輯 張 紅)