空間數(shù)據(jù)的訪問(wèn)方法與查詢技術(shù)研究

摘要:二十一世紀(jì)是一個(gè)網(wǎng)絡(luò)的世紀(jì)，Internet技術(shù)正在以驚人的速度迅速膨脹發(fā)展，滲入人們工作和生活的方方面面，空間查詢技術(shù)、GIS系統(tǒng)與Web的有機(jī)結(jié)合，可以將地理信息應(yīng)用發(fā)布于互聯(lián)網(wǎng)上，為現(xiàn)有的信息服務(wù)行業(yè)注入了新鮮的血液，使得空間數(shù)據(jù)庫(kù)查詢應(yīng)用不再是專業(yè)人士的特殊工具，通過(guò)網(wǎng)絡(luò)，它將為越來(lái)越多的公眾服務(wù)，成為社會(huì)最基本的信息服務(wù)之一。

關(guān)鍵詞:空間數(shù)據(jù)庫(kù);查詢

中圖分類號(hào):TP311 文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2010)03-522-02

空間數(shù)據(jù)查詢技術(shù)在地理信息系統(tǒng)(GIS)和計(jì)算機(jī)輔助設(shè)計(jì)(CAD)領(lǐng)域中有著極其廣泛的應(yīng)用。人們不僅希望準(zhǔn)確檢索到數(shù)據(jù)，而且希望檢索的速度越快越好。當(dāng)前空間數(shù)據(jù)檢索的一個(gè)關(guān)鍵問(wèn)題是速度。提高速度的核心技術(shù)是空間索引。空間索引是由空間位置到空間對(duì)象的映射關(guān)系，為空間檢索提供一種合適的數(shù)據(jù)結(jié)構(gòu)，以提高檢索速度。

GIS數(shù)據(jù)中包含了大量的地理信息數(shù)據(jù)，如果不為這些數(shù)據(jù)創(chuàng)建索引，要從海量的GIS數(shù)據(jù)中檢索到目標(biāo)數(shù)據(jù)，這一過(guò)程可能會(huì)經(jīng)歷相當(dāng)長(zhǎng)的時(shí)間。如果為這些GIS數(shù)據(jù)創(chuàng)建合理的索引文件，在索引文件中檢索目標(biāo)數(shù)據(jù)，檢索速度會(huì)明顯得到提高。因此在空間數(shù)據(jù)產(chǎn)品中實(shí)現(xiàn)高效的索引算法是非常必要的。與此同時(shí)，隨著人們對(duì)地理數(shù)據(jù)表示和處理的需求越來(lái)越普遍，地理信息系統(tǒng)正迅速擴(kuò)展到各種應(yīng)用領(lǐng)域。傳統(tǒng)的GIS系統(tǒng)本身的功能和結(jié)構(gòu)也發(fā)生了巨大變化，開(kāi)始向Web擴(kuò)展。

1 空間數(shù)據(jù)庫(kù)查詢的主要特點(diǎn)

空間數(shù)據(jù)庫(kù)查詢是空間數(shù)據(jù)庫(kù)的一項(xiàng)重要操作，空間查詢技術(shù)是針對(duì)空間數(shù)據(jù)庫(kù)的特點(diǎn)發(fā)展起來(lái)的。由于空間數(shù)據(jù)量的龐大，以及空間對(duì)象、空間查詢的高度復(fù)雜性，使得空間數(shù)據(jù)庫(kù)的查詢效率成為衡量空間數(shù)據(jù)庫(kù)性能的重要指標(biāo)之一。

數(shù)據(jù)庫(kù)是為一定目的服務(wù)的，并以特定的數(shù)據(jù)格式存儲(chǔ)的相關(guān)聯(lián)的數(shù)據(jù)集合。它是數(shù)據(jù)管理的高級(jí)階段，是從文件管理系統(tǒng)發(fā)展而來(lái)的。空間數(shù)據(jù)庫(kù)是某一區(qū)域內(nèi)關(guān)于一定地理要素特征的數(shù)據(jù)集合，與一般關(guān)系數(shù)據(jù)庫(kù)相比，其主要特點(diǎn)有:

1)數(shù)據(jù)量特別大，要用數(shù)據(jù)來(lái)描述各種地理要素，尤其是要素的空間位置，其數(shù)據(jù)量往往很大。

2)不僅有地理要素的屬性數(shù)據(jù)與關(guān)系數(shù)據(jù)庫(kù)中數(shù)據(jù)性質(zhì)相似，還有大量描述地理要素空間分布位置的空間數(shù)據(jù)，并且這兩種數(shù)據(jù)之間具有不可分割的聯(lián)系。

3)數(shù)據(jù)應(yīng)用廣泛，如地理研究、環(huán)境保護(hù)、土地利用、生態(tài)環(huán)境、道路建設(shè)、資源開(kāi)發(fā)、市政管理等。

空間查詢是空間數(shù)據(jù)庫(kù)的一項(xiàng)重要操作。由于空間數(shù)據(jù)庫(kù)的特殊性，空間數(shù)據(jù)庫(kù)的查詢除兼有普通數(shù)據(jù)庫(kù)的查詢能力外，同時(shí)還應(yīng)具備空間數(shù)據(jù)的查詢能力。空間查詢大體上可分為點(diǎn)查詢、區(qū)域查詢、最近鄰查詢及空間連接查詢四類。

與一般關(guān)系數(shù)據(jù)庫(kù)相比，空間數(shù)據(jù)庫(kù)在查詢處理方面的主要特點(diǎn)至少有:1)目前僅僅在空間操作的類別上達(dá)成了一致，對(duì)每種具體空間查詢的設(shè)計(jì)與處理規(guī)則各不相同。2)空間數(shù)據(jù)庫(kù)要處理非常大量的復(fù)雜對(duì)象，這些對(duì)象具有空間范圍，而且不能自然地排序成數(shù)組，需要建立適合于空間數(shù)據(jù)的訪問(wèn)方法以提高查詢的效率。3)檢測(cè)空間謂詞的算法計(jì)算量極大，所以不能再假定I/O代價(jià)在CPU的處理代價(jià)中占主導(dǎo)地位，這就使得空間查詢處理與優(yōu)化過(guò)程設(shè)計(jì)比傳統(tǒng)數(shù)據(jù)庫(kù)更為復(fù)雜。

2 空間數(shù)據(jù)索引

空間數(shù)據(jù)訪問(wèn)方法由空間索引和定義在空間索引上的查詢操作組成，是空間查詢技術(shù)的基礎(chǔ)，空間查詢的性能好壞很大程度上取決于空間數(shù)據(jù)訪問(wèn)方法的效率。

2.1 網(wǎng)格索引

網(wǎng)格索引的基本思想是將研究區(qū)域縱橫分成若干個(gè)均等的小塊，每個(gè)小塊都作為一個(gè)桶，將落在該小塊內(nèi)的地物對(duì)象放入該小塊對(duì)應(yīng)的桶中。從精度考慮，小塊還可細(xì)分，直至不可再分為止。當(dāng)用戶進(jìn)行空間查詢時(shí)，首先計(jì)算出用戶查詢對(duì)象所在網(wǎng)格，然后再在該網(wǎng)格中快速查詢所選空間實(shí)體。其優(yōu)點(diǎn)主要有:桶數(shù)固定、結(jié)構(gòu)簡(jiǎn)單，每個(gè)表項(xiàng)都用于表示地物的空間位置及分布;查詢方式多樣，可以任意以一點(diǎn)或一條線或一個(gè)任意形狀的區(qū)域進(jìn)行檢索;檢索結(jié)果合理查詢精確，這是因?yàn)榫W(wǎng)格索引支持地物的特征信息存儲(chǔ);支持多精度等級(jí)，查詢并不要求太精確，如查詢某點(diǎn)附近的地物，網(wǎng)格索引的多級(jí)分塊策略正好適應(yīng)這種情況，對(duì)于一些非精確查詢，特征信息匹配計(jì)算無(wú)需進(jìn)行或只進(jìn)入第二級(jí)就行了，而不必再往下去。這樣就節(jié)省了更多的時(shí)間。然而網(wǎng)格文件本質(zhì)上會(huì)造成目錄非常松散，因而浪費(fèi)主存緩沖區(qū)和二級(jí)存儲(chǔ)。

2.2 R樹(shù)及其變種

R樹(shù)是GUTTMAN于1984年提出的最早支持?jǐn)U展對(duì)象存取方法之一，也是目前應(yīng)用最為廣泛的一種空間索引結(jié)構(gòu)。許多商用空間數(shù)據(jù)庫(kù)系統(tǒng)，如MapInfo SpatialWare和Oracle Spatial等均提供對(duì)R樹(shù)的支持，開(kāi)放源碼系統(tǒng)PostgreSQL也實(shí)現(xiàn)了R樹(shù)。近二十多年來(lái)，許多學(xué)者致力于R樹(shù)的研究，在R樹(shù)的基礎(chǔ)上衍生出了許多變種。比較典型的有R+樹(shù)、R*樹(shù)、壓縮R樹(shù)等。

R樹(shù)是一個(gè)高度平衡樹(shù)，它是B樹(shù)在k維上的自然擴(kuò)展，用空間對(duì)象的MBR來(lái)近似表達(dá)空間對(duì)象，根據(jù)地物的MBR建立R樹(shù)，可以直接對(duì)空間中占據(jù)一定范圍的空間對(duì)象進(jìn)行索引。R樹(shù)的每一個(gè)結(jié)點(diǎn)都對(duì)應(yīng)著磁盤頁(yè)D和區(qū)域I，如果結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則該結(jié)點(diǎn)的所有子結(jié)點(diǎn)的區(qū)域都在區(qū)域I的范圍之內(nèi)，而且存儲(chǔ)在磁盤頁(yè)D中。如果結(jié)點(diǎn)是葉結(jié)點(diǎn)，那么磁盤頁(yè)D中存儲(chǔ)的將是區(qū)域I范圍內(nèi)的一系列子區(qū)域，子區(qū)域緊緊圍繞空間對(duì)象，一般為空間對(duì)象的外接矩形。

R樹(shù)中每個(gè)結(jié)點(diǎn)所能擁有的子結(jié)點(diǎn)數(shù)目是有上下限的。下限保證索引對(duì)磁盤空間的有效利用，子結(jié)點(diǎn)的數(shù)目小于下限的結(jié)點(diǎn)將被刪除，該結(jié)點(diǎn)的子結(jié)點(diǎn)將被分配到其他的結(jié)點(diǎn)中;設(shè)立上限是因?yàn)槊恳粋€(gè)結(jié)點(diǎn)只對(duì)應(yīng)一個(gè)磁盤頁(yè)，如果某個(gè)結(jié)點(diǎn)要求的空間大于一個(gè)磁盤頁(yè)，那么該結(jié)點(diǎn)就要被劃分為兩個(gè)新的結(jié)點(diǎn)，原來(lái)結(jié)點(diǎn)的所有子結(jié)點(diǎn)將被分配到這兩個(gè)新的結(jié)點(diǎn)中。令M為一個(gè)結(jié)點(diǎn)中記錄數(shù)目的最大值，m≤M/2為一參數(shù)，說(shuō)明一個(gè)節(jié)點(diǎn)記錄的最小值，m可作為調(diào)節(jié)樹(shù)結(jié)構(gòu)的一個(gè)可變參數(shù)，R樹(shù)滿足如下幾項(xiàng)特點(diǎn):根節(jié)點(diǎn)若非葉子節(jié)點(diǎn)，則至少有兩個(gè)子節(jié)點(diǎn);每個(gè)非根葉節(jié)點(diǎn)和非葉節(jié)點(diǎn)包含的實(shí)體個(gè)數(shù)均介于m和M之間;所有葉子節(jié)點(diǎn)在同一層次。

R樹(shù)兄弟結(jié)點(diǎn)對(duì)應(yīng)的空間區(qū)域可以重疊，可以較容易地進(jìn)行插入和刪除操作。但正因?yàn)閰^(qū)域之間有重疊，空間索引可能要對(duì)多條路徑進(jìn)行搜索后才能得到最后的結(jié)果。當(dāng)查找與給定的查詢窗口相交的所有空間對(duì)象時(shí)，空間搜索算法是從根結(jié)點(diǎn)開(kāi)始，向下搜索相應(yīng)的子樹(shù)。算法遞歸遍歷所有約束矩形與查詢窗口相交的子樹(shù)，當(dāng)?shù)竭_(dá)葉結(jié)點(diǎn)時(shí)，邊界矩形中的元素被取出并測(cè)試其是否與查詢矩形相交，所有與查詢窗口相交的葉結(jié)點(diǎn)即為要查找的空間對(duì)象。R樹(shù)的查詢效率會(huì)因重疊區(qū)域的增大而大大減弱，在最壞情況下，其時(shí)間復(fù)雜度甚至?xí)蓪?duì)數(shù)搜索退化成線性搜索。正是這個(gè)原因促使了R+樹(shù)的產(chǎn)生。在R+樹(shù)中，兄弟結(jié)點(diǎn)對(duì)應(yīng)的空間區(qū)域沒(méi)有重疊，而沒(méi)有重疊的區(qū)域劃分可以使空間索引搜索的速度大大提高，克服了R樹(shù)中多路查詢的問(wèn)題，但同時(shí)它也存在著一些缺陷，如對(duì)某個(gè)最小約束矩形的劃分，可能會(huì)引起相關(guān)子樹(shù)上其他結(jié)點(diǎn)也需要重新劃分，向下分裂操作可能使得已經(jīng)劃分好了的結(jié)點(diǎn)被重新劃分，空間對(duì)象在R+樹(shù)的葉結(jié)點(diǎn)中被重復(fù)標(biāo)記，完成刪除運(yùn)算后，必須對(duì)R+樹(shù)進(jìn)行重建等，同時(shí)由于在插入和刪除空間對(duì)象時(shí)要保證兄弟結(jié)點(diǎn)對(duì)應(yīng)的空間區(qū)域不重疊，而使插入和刪除操作的效率降低。R*樹(shù)是最有效的R樹(shù)變種，它能對(duì)覆蓋區(qū)域、重疊面積和邊界周長(zhǎng)進(jìn)行啟發(fā)式地優(yōu)化，并通過(guò)重新插入節(jié)點(diǎn)重建R*樹(shù)以提高其性能，但重新插入這個(gè)過(guò)程相當(dāng)繁瑣，其實(shí)現(xiàn)過(guò)程太過(guò)漫長(zhǎng)。

壓縮R樹(shù)的空間數(shù)據(jù)集是預(yù)先己知的，通過(guò)預(yù)先對(duì)數(shù)據(jù)進(jìn)行合理有效的組織，可以保證其具有很高的空間利用率和良好的查詢效率，但由于其不能進(jìn)行動(dòng)態(tài)插入和刪除，因而其應(yīng)用受到了很大限制。

3 空間數(shù)據(jù)查詢技術(shù)

3.1 點(diǎn)查詢與區(qū)域查詢

點(diǎn)查詢(Point Query， PQ):給定一個(gè)查詢點(diǎn)P，找出所有包含它的空間對(duì)象O。使得PQ(p)={O|PεO.G≠?}，其中O.G為對(duì)象O的幾何信息。

范圍或區(qū)域查詢(Range or Regional query， RQ):給定一個(gè)查詢多邊形P，找出所有與之相交的空間對(duì)象O。當(dāng)查詢多邊形為矩形時(shí)，成為窗口查詢:

PQ(P)={O|O.G∩P.G≠?準(zhǔn)}

對(duì)這些查詢的處理與包含該查詢關(guān)系的文件的組織方式有關(guān)，根據(jù)參與查詢的空間數(shù)據(jù)集是否具有空間索引，其相應(yīng)的處理策略各不相同。

1) 數(shù)據(jù)集未排序且沒(méi)有空間索引在這種情況下，唯一的方法就是采用窮舉法掃描整個(gè)文件，并判定每一條記錄是否滿足查詢謂詞，利用過(guò)濾、精煉兩步處理來(lái)實(shí)現(xiàn)。如果空間對(duì)象用它的MBR來(lái)近似表示，則區(qū)域查詢的過(guò)濾步驟就對(duì)應(yīng)著檢驗(yàn)矩形與查詢矩形的交集。這個(gè)處理與沒(méi)有過(guò)濾就處理整個(gè)對(duì)象相比，其代價(jià)是非常低的。掃描的代價(jià)為O(n)，其中n是進(jìn)行區(qū)域查詢的關(guān)系中包含的頁(yè)面數(shù)。

2) 數(shù)據(jù)集具有空間索引在數(shù)據(jù)集具有空間索引的情況下，查詢可通過(guò)掃描索引文件過(guò)濾掉大部分不滿足查詢條件的空間對(duì)象，從而避免掃描整個(gè)數(shù)據(jù)文件，減少系統(tǒng)負(fù)載。通常使用的空間索引為R樹(shù)族。使用索引樹(shù)，點(diǎn)查詢通常可在O(logn)時(shí)間內(nèi)完成處理，區(qū)域查詢的代價(jià)則依賴于許多因素，包括數(shù)據(jù)矩形的分布、查詢窗口的大小、樹(shù)的高度及用于構(gòu)造索引樹(shù)結(jié)點(diǎn)的壓縮算法等等。采用R樹(shù)的缺點(diǎn)是不同分支的MBR可以交疊，這就可能導(dǎo)致沿著索引樹(shù)的不同分支進(jìn)行搜索。R樹(shù)的一個(gè)變體樹(shù)避免了內(nèi)部結(jié)點(diǎn)的交疊，R+樹(shù)的主要問(wèn)題是空間對(duì)象的外接矩形可能在多個(gè)內(nèi)部結(jié)點(diǎn)上存在重復(fù)，這會(huì)導(dǎo)致搜索時(shí)間增加和結(jié)點(diǎn)的頻繁溢出。

3.2 最近鄰查詢

最近鄰查詢?cè)谠S多應(yīng)用中都很常見(jiàn)。如電子商務(wù)網(wǎng)站接收到書(shū)籍訂單后該把訂單發(fā)送到最近的配送中心。典型的算法有兩遍算法和一遍算法:

1) 兩遍算法第一遍檢索包含查詢對(duì)象QO的數(shù)據(jù)頁(yè)D，以確定D中任意對(duì)象到QO的最小距離d;第二遍通過(guò)一個(gè)范圍查詢檢索與QO的距離在d內(nèi)的對(duì)象以確定最近鄰居。這個(gè)方法使用了用于范圍查詢和點(diǎn)查詢的算法。

2) 一遍處理算法該算法的最近鄰查詢需要用到與區(qū)域查詢和點(diǎn)查詢完全不同的算法。最早由ROSSOPOULOS提出，使用了一對(duì)距離度量，即搜索修剪條件和搜索算法。

3.3 空間連接查詢

空間連接查詢是空間數(shù)據(jù)庫(kù)系統(tǒng)一種重要的多路查詢，即從兩個(gè)數(shù)據(jù)集合中檢索出所有滿足某一空間謂詞，如交、包含等的空間對(duì)象。如給定兩個(gè)對(duì)象集A、B，其空間連接是從A中的對(duì)象到B中的對(duì)象應(yīng)用謂詞S的結(jié)果。謂詞S包括覆蓋、距離、方向、鄰接和包含等。

當(dāng)兩種空間關(guān)系連接在一起時(shí)，我們稱之為空間連接。空間關(guān)系是指空間對(duì)象之間具有空間特性的關(guān)系，主要包括拓?fù)洹㈨樞颉⒍攘咳箢愱P(guān)系。因此空間連接查詢又可分為拓?fù)溥B接查詢、順序(方位)連接查詢和度量(距離)連接查詢。與其它空間查詢一樣，空間連接查詢的實(shí)現(xiàn)過(guò)程通常分兩步進(jìn)行過(guò)濾和精煉。過(guò)濾即是借助空間索引與MBR，查找出滿足給定條件的空間對(duì)象候選集，建立空間連接索引。精煉則是用相應(yīng)的空間對(duì)象代替進(jìn)行具體的連接處理，檢索出滿足實(shí)際需求的空間對(duì)象，即從第二存儲(chǔ)區(qū)檢索候選集中每個(gè)對(duì)象的精確形狀信息，來(lái)測(cè)試其是否滿足查詢條件。

參考文獻(xiàn):

[1] 劉剛，鄧飛其，楊長(zhǎng)海.AJAX在WebGIS異步數(shù)據(jù)交互中的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009(1).

[2] 方元，趙冠偉，何觀生.基于Ajax和GeoServer的WebGIS設(shè)計(jì)[J].微計(jì)算機(jī)信息，2009(1).