空間網(wǎng)絡數(shù)據(jù)庫(數(shù)據(jù)庫)

時間：2022-10-31 16:30:01 | 來源：信息時代

時間：2022-10-31 16:30:01 來源：信息時代

    空間網(wǎng)絡數(shù)據(jù)庫 : 能夠支持基于連通性的空間實體的高效存儲和查詢的一類空間數(shù)據(jù)庫。應用于運輸規(guī)劃、空中交通管制、管網(wǎng)設(shè)施、電話網(wǎng)絡、河道運輸、灌渠管理等領(lǐng)域。在空間網(wǎng)絡數(shù)據(jù)庫中,起根本作用的是基于連通性的關(guān)系。
1. 空間網(wǎng)絡數(shù)據(jù)的圖操作
空間網(wǎng)絡數(shù)據(jù)通常被建模為圖,其結(jié)點是嵌在空間上的點。路徑估算和最短路徑計算操作的高效實現(xiàn)通常是基于結(jié)點之間的連通性,而不是歐幾里得距離。圖可以用關(guān)系數(shù)據(jù)庫中的結(jié)點表和邊表來表示。鄰接矩陣(adjacency-matrix)和鄰接表(adjacency-list)可以用于圖的實現(xiàn)。
在鄰接矩陣中,行和列表示圖的頂點,矩陣中元素的取值為1或0,即對應的兩個頂點之間有邊則為1,否則為0。如果是無向圖,那么矩陣是對稱的。鄰接矩陣結(jié)構(gòu)對于回答邊的查詢是很有效的,例如,邊(u,v)是否在圖G中。
鄰接表是一個指針數(shù)組,數(shù)組的每個元素對應圖中的一個頂點,而指針則指向該頂點的一個直接后繼頂點表。鄰接表結(jié)構(gòu)對于涉及枚舉圖的頂點查詢是高效的,例如,找出v的所有鄰近頂點。
基于關(guān)系代數(shù)的查詢語言(如SQL)對許多圖操作(如最短路徑問題)無能為力,因為這些圖操作要用到傳遞閉包操作。傳遞閉包的處理可以采用廣度優(yōu)先搜索或者深度優(yōu)先搜索策略,而計算部分的傳遞閉包更多的是用Dijkstra算法。最短路徑計算還有特別的策略(A*算法,層次算法)。
2. 空間網(wǎng)絡查詢
空間網(wǎng)絡上常用的查詢可以分為三類: 單遍掃描查詢、連接查詢和網(wǎng)絡分析查詢。單遍掃描查詢包括點和范圍查詢,例如,點查詢、邊查詢、前驅(qū)查詢、后繼查詢以及路徑估算操作。連接查詢是多個空間網(wǎng)絡的圖形疊加。網(wǎng)絡分析查詢是一組基于傳遞閉包的查詢,它們包括最短路徑、連接性確定、最短旅行路線、定位和布局等。其中最短路徑問題和圖遍歷問題的算法,用于處理大多數(shù)網(wǎng)絡分析查詢,同樣也用于處理單遍掃描查詢和連接查詢。
路徑查詢處理是空間網(wǎng)絡應用中的一個重要部分,本質(zhì)上可以歸結(jié)為提供基于相關(guān)應用準則的路徑選擇。最基本的路徑查詢是確定網(wǎng)絡中兩個點A和B之間的最短路徑,“最短”可以是距離、旅行時間或者其他用戶指定的約束。
路徑計算可以分為三類:
(1)單對:給定一個圖G=(V,E)和N中的頂點u與v,找出u與v之間的最優(yōu)路徑。
(2)單源: 給定一個源結(jié)點u,找出G中從u到所有可達(reachable)結(jié)點的最優(yōu)路徑。這也是所謂的部分傳遞閉包(partial transitive closure)問題。
(3)所有對: 在G中找出N的所有結(jié)點對u和v之間的最優(yōu)路徑。這是有關(guān)傳遞閉包的問題。
對于空間網(wǎng)絡,只有點和范圍查詢的I/O度量方法是不夠的,因為網(wǎng)絡中的關(guān)系是基于連接性而不是基于鄰近性的。就網(wǎng)絡操作的I/O代價而言,一種簡單并且直觀的度量方法與非分離邊的數(shù)目有關(guān)。如果一條邊的兩個端點位于同一個磁盤頁中,那么它是非分離的,否則就是分離的。
連接性剩余率(connectivity residue ratio,CRR):CRR=非分離邊總數(shù)/總邊數(shù)。連接性剩余率是一種數(shù)據(jù)結(jié)構(gòu)無關(guān)的度量,其最大化的存儲和訪問方法可以提高圖操作的I/O效率。已經(jīng)有專用的連接性聚簇的空間網(wǎng)絡存取方法,它采用最小分割的圖分區(qū)算法來聚集結(jié)點記錄,以使連接性剩余率最大化。此外,還可以采用輔助的二級索引來支持點查詢、邊查詢、前驅(qū)查詢和后繼查詢操作。選擇二級索引可以針對應用作調(diào)整,有些采用了帶Z序的B⁺-樹。為了適于應用,還可以創(chuàng)建其他存取方法(如R-樹和grid文件)作為二級索引。