空間查詢(xún)處理(數(shù)據(jù)庫(kù))

時(shí)間：2022-10-31 18:30:01 | 來(lái)源：信息時(shí)代

時(shí)間：2022-10-31 18:30:01 來(lái)源：信息時(shí)代

    空間查詢(xún)處理 : 對(duì)數(shù)據(jù)庫(kù)中大量的空間對(duì)象進(jìn)行高效檢索的過(guò)程?？臻g數(shù)據(jù)庫(kù)的查詢(xún)處理與關(guān)系數(shù)據(jù)庫(kù)之間的主要區(qū)別是: ①空間數(shù)據(jù)庫(kù)沒(méi)有固定的算子集合可以充當(dāng)查詢(xún)計(jì)算的基本構(gòu)件;②空間數(shù)據(jù)庫(kù)要處理大量的復(fù)雜對(duì)象,這些對(duì)象具有空間范圍,而且不能自然地排序成一維數(shù)組;③檢測(cè)空間謂詞需要用到計(jì)算代價(jià)高昂的算法,所以不能再假定I/O代價(jià)遠(yuǎn)超CPU代價(jià)。
1.空間查詢(xún)操作的步驟
空間查詢(xún)操作通常采用過(guò)濾精煉算法以高效地處理空間查詢(xún)中所包含復(fù)雜數(shù)據(jù)類(lèi)型。該算法的處理步驟為:
(1)過(guò)濾步驟: 空間對(duì)象表示為相對(duì)簡(jiǎn)單的近似(approximations),比如最小外接矩形,其結(jié)果是真實(shí)結(jié)果集的超集,也稱(chēng)為候選集。空間謂詞也可以被替換成一個(gè)近似以簡(jiǎn)化查詢(xún)優(yōu)化器。有些空間算子,例如inside(在內(nèi)部),north-of(在北部),buffer(緩沖區(qū)分析)可以近似成相應(yīng)最小外接矩形之間的交疊關(guān)系。這樣的轉(zhuǎn)換能夠保證最終結(jié)果中的元組不會(huì)在過(guò)濾步驟中被排除掉。
(2)精煉步驟: 檢查候選集中每個(gè)元素的精確幾何信息和精確的空間謂詞。這通常需要使用計(jì)算密集型的算法。這一步驟有時(shí)可以在空間數(shù)據(jù)庫(kù)以外的某個(gè)應(yīng)用程序(如GIS)中進(jìn)行,該應(yīng)用程序會(huì)用到空間數(shù)據(jù)庫(kù)在過(guò)濾步驟產(chǎn)生的候選集。
2. 空間查詢(xún)操作的類(lèi)型
空間查詢(xún)主要包括以下四種類(lèi)型的操作:
(1)更新操作:標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)操作(修改、創(chuàng)建等)。
(2)空間選擇操作: 又分為點(diǎn)和范圍兩種。①點(diǎn)查詢(xún): 給定一個(gè)查詢(xún)點(diǎn)P,找出所有包含它的空間對(duì)象O: PQ(p)={O|p∈O.G≠0},其中O.G為對(duì)象O的幾何信息。②范圍或區(qū)域查詢(xún): 給定一個(gè)查詢(xún)多邊形P,找出所有與之相交的空間對(duì)象O:PQ(p)={O|O.G∩P.G≠0}。當(dāng)查詢(xún)多邊形是一個(gè)矩形時(shí),稱(chēng)這個(gè)查詢(xún)?yōu)榫匦未翱诓樵?xún)。這些查詢(xún)有時(shí)也稱(chēng)作范圍查詢(xún)。
(3)空間連接操作: 空間連接是更為重要的算子之一,類(lèi)似于關(guān)系數(shù)據(jù)庫(kù)中的連接算子。當(dāng)兩個(gè)表R和S基于一個(gè)空間謂詞θ連接時(shí),則該連接被稱(chēng)為空間連接。R⋈θS={(O,O’)|O∈R,O′∈S,θ(O.G,O′.G)}空間連接的一個(gè)變形是地圖疊加(map overlay),它也是GIS中的一個(gè)重要算子。這個(gè)操作組合了兩個(gè)空間對(duì)象集合以形成一個(gè)新的集合。這些新對(duì)象的集合的“邊界”由疊加操作所指定的非空間屬性來(lái)決定。
(4)空間聚集操作: 通常是最近鄰居搜索問(wèn)題的變體。給定一個(gè)對(duì)象O′,找出所有距離O′最近的對(duì)象O:NNQ(O′)={O|∀O″:dist(d.G,O.G)≤dist(O′.G,O″.G)}。
3. 空間操作采取的策略
除了更新操作是數(shù)據(jù)庫(kù)的標(biāo)準(zhǔn)操作之外,上述其他空間操作都需要針對(duì)于空間數(shù)據(jù)和組織結(jié)構(gòu)的不同而采取不同的策略:
(1)空間選擇操作: 針對(duì)包含待查關(guān)系的文件的不同組織,空間選擇有以下三個(gè)方法: ①數(shù)據(jù)未排序且沒(méi)有索引: 采用窮舉法(brute force)掃描整個(gè)文件并檢查每一條記錄是否滿(mǎn)足謂詞。根據(jù)關(guān)系的大小,兩步(過(guò)濾加精煉)處理可能對(duì)計(jì)算相交謂詞非常有用。這個(gè)處理與沒(méi)有過(guò)濾而處理整個(gè)對(duì)象相比,代價(jià)是非常低的,掃描的代價(jià)為O(n)。對(duì)于點(diǎn)查詢(xún),過(guò)濾步驟包括檢驗(yàn)一個(gè)點(diǎn)在矩形中的操作。②數(shù)據(jù)建立了空間索引: 使用空間索引(如R-樹(shù))可以避免掃描整個(gè)文件從而減少系統(tǒng)代價(jià)。采用搜索樹(shù)的點(diǎn)查詢(xún)通?？梢栽贠(log n)時(shí)間內(nèi)完成處理。使用索引樹(shù)時(shí)查詢(xún)的代價(jià)依賴(lài)于許多因素,包括數(shù)據(jù)矩形的分布、查詢(xún)窗口的大小、樹(shù)的高度以及用于構(gòu)造索引樹(shù)結(jié)點(diǎn)的組裝算法等。采用R-樹(shù)的一個(gè)缺點(diǎn)是不同分支的最小外接矩形允許交疊,這就可能導(dǎo)致沿著索引樹(shù)的不同分支進(jìn)行搜索。R-樹(shù)的一個(gè)變體R⁺-樹(shù)就避免了內(nèi)部結(jié)點(diǎn)的交疊,R⁺-樹(shù)的主要問(wèn)題是數(shù)據(jù)矩形可能在多個(gè)內(nèi)部結(jié)點(diǎn)上存在復(fù)本,這會(huì)導(dǎo)致搜索時(shí)間和結(jié)點(diǎn)溢出的增加。③空間填充曲線(xiàn)散列: 空間填充曲線(xiàn)通常的例子就是z曲線(xiàn)和Hilbert曲線(xiàn),但它們都不具備如下屬性: 即所有在多維空間中“位置鄰近”的記錄在映射后的范圍空間中仍保持鄰近。一旦數(shù)據(jù)按空間填充曲線(xiàn)“排序”,B樹(shù)索引就可以用于排序后的記錄以加快搜索速度。點(diǎn)查詢(xún)的代價(jià)為O(log_B(n)),其中B為分塊因子。范圍查詢(xún)的代價(jià)大約為

(2)空間連接操作: 進(jìn)行空間連接需要采用一些特別的方法來(lái)避免執(zhí)行笛卡兒積。如果只關(guān)注過(guò)濾-精煉兩步策略中的過(guò)濾步驟。這樣空間交疊操作簡(jiǎn)化為求矩形與矩形的交,與從二級(jí)存儲(chǔ)器檢索頁(yè)面的I/O代價(jià)相比而言,這個(gè)代價(jià)是很小的?？臻g連接操作的處理方法根據(jù)數(shù)據(jù)上的索引情況可以有以下幾種: ①?zèng)]有索引的嵌套循環(huán): 枚舉兩個(gè)關(guān)系所有可能的元組對(duì),并用overlap函數(shù)檢查。②有索引的嵌套循環(huán): 如果其中一個(gè)關(guān)系建有索引,那么可以將有索引的關(guān)系作為內(nèi)層循環(huán)以利用其優(yōu)點(diǎn),這樣就不需要在每次循環(huán)中完全掃描整個(gè)內(nèi)層關(guān)系。使用內(nèi)層關(guān)系上的索引來(lái)檢索能與存儲(chǔ)在主存中的外層關(guān)系的元組相匹配的候選元組,可以取代范圍查詢(xún)。③樹(shù)匹配: 如果兩個(gè)關(guān)系都有空間索引(例如R-樹(shù)),那么就可以使用樹(shù)匹配策略。樹(shù)結(jié)點(diǎn)包含形如(ref,rect)的記錄,其中ref為指向子結(jié)點(diǎn)的指針。rect為子結(jié)點(diǎn)記錄的最小外接矩形或是空間對(duì)象的最小外接矩形,這取決于該結(jié)點(diǎn)是否為葉結(jié)點(diǎn)。二級(jí)存儲(chǔ)器中對(duì)應(yīng)非葉結(jié)點(diǎn)的頁(yè)稱(chēng)為目錄頁(yè),對(duì)應(yīng)實(shí)際數(shù)據(jù)的頁(yè)稱(chēng)為數(shù)據(jù)頁(yè)。該算法基于這樣一條規(guī)律: 非葉結(jié)點(diǎn)的矩形能夠容納所有子結(jié)點(diǎn)中的矩形的MBR。因此,如果兩個(gè)目錄頁(yè)中的記錄Erl和Er2不交,那么必然其后子樹(shù)中的所有數(shù)據(jù)矩形也不交。如果目錄頁(yè)中的記錄相交,那么子樹(shù)的數(shù)據(jù)矩形則有可能會(huì)相交。④基于分塊的空間融合連接: 給定兩個(gè)關(guān)系F和R,過(guò)濾步驟描述如下: 對(duì)F和R中的每個(gè)元組構(gòu)造key-pointer元組,包含元組的唯一OID和空間屬性的最小外接矩形,稱(chēng)新關(guān)系為F_kp和R_kp。如果關(guān)系F_kp和R_kp都可以裝入主存,那么連接關(guān)系可以用平面掃描算法處理。如果關(guān)系太大而不能全部裝入主存,則將兩個(gè)關(guān)系都分成P塊。F_1kp,…,F_Pkp和R_1kp,…,R_Pkp。分塊必須滿(mǎn)足兩個(gè)約束: 對(duì)每一個(gè)F_ikp,R_kp中與之交疊的元素位于R_ikp;F_ikp和R_ikp都位于主存。
還有一些其他的空間連接策略,例如外部平面掃描或基于連接索引的方法。
(3)空間聚集操作: 最近鄰居查詢(xún)可以通過(guò)兩遍檢索解決這個(gè)問(wèn)題。第一遍檢索包含查詢(xún)對(duì)象QO的數(shù)據(jù)頁(yè)D,以確定D中任意對(duì)象到QO的最小距離d。第二遍通過(guò)一個(gè)范圍查詢(xún)檢索與QO的距離在d之內(nèi)的對(duì)象以確定最近鄰居。這個(gè)方法重用了空間選擇的算法,例如點(diǎn)查詢(xún)和范圍查詢(xún)。
一遍處理最近鄰居查詢(xún)的搜索算法與上述方法不同,它從R-樹(shù)的根結(jié)點(diǎn)開(kāi)始遍歷整棵樹(shù)。例如,廣度優(yōu)先遍歷將訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)中所有內(nèi)部結(jié)點(diǎn)的子結(jié)點(diǎn)的最小外接矩形,并利用規(guī)則進(jìn)行剪枝。保留下來(lái)的子結(jié)點(diǎn)將在下一輪迭代中被展開(kāi)。最后一遍將根據(jù)樹(shù)的層次順序?qū)κＯ碌淖钚⊥饨泳匦芜M(jìn)行剪枝,獲得一組葉結(jié)點(diǎn)(數(shù)據(jù)庫(kù)對(duì)象級(jí))。該算法需要計(jì)算每個(gè)葉結(jié)點(diǎn)到查詢(xún)點(diǎn)P的距離以決定最近鄰居。也可以選擇深度優(yōu)先或其他R-樹(shù)遍歷方式。這個(gè)算法可以擴(kuò)展為找到K個(gè)最近鄰居,只需要稍稍修改剪枝規(guī)則就可以保留K個(gè)最好的候選。最后,剪枝規(guī)則同樣適用于基于矩形的索引方法,比如柵格文件,四叉樹(shù)等等。