時空索引管理(數(shù)據(jù)庫)

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

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

    時空索引管理 : 時空數(shù)據(jù)庫管理系統(tǒng)的一個重要功能,目的是使時空數(shù)據(jù)庫管理系統(tǒng)能對大量的時空數(shù)據(jù)進(jìn)行快速的查詢和處理。傳統(tǒng)的關(guān)系數(shù)據(jù)庫管理系統(tǒng)的索引機(jī)制主要支持對數(shù)值型、字符串等數(shù)據(jù)的索引與快速存取,已不能滿足時空數(shù)據(jù)庫的查詢需求。
時空數(shù)據(jù)庫管理系統(tǒng)需要管理大量的帶有長期時間信息的空間數(shù)據(jù),為了對這些數(shù)據(jù)進(jìn)行有效存取,對時空索引機(jī)制的研究顯得尤為重要。但空間、時間索引技術(shù)的研究成果并不能直接應(yīng)用于時空數(shù)據(jù),因為空間索引可以支持對點、任意形狀的區(qū)域及光柵數(shù)據(jù)進(jìn)行查詢操作,但沒有考慮到時空應(yīng)用中的時間特性; 而針對時間信息的存取方法只對有效時間和事務(wù)時間進(jìn)行索引,沒有考慮到時空對象的空間屬性。
1. 時空索引方法
時空索引的索引結(jié)構(gòu)直接與查詢類型和時空對象本身有關(guān),在空間索引方法和時態(tài)索引方法的基礎(chǔ)上,已經(jīng)提出了一些時空索引方法,主要如下:
(1)時間維作為一個空間維度:將時間看成是時空對象另一維度的空間信息,則可直接使用傳統(tǒng)的空間索引方法(如R-樹、四叉樹)處理d+1維的空間信息(d是參考空間的維度)。3DR-樹將二維參考空間中的最小邊界矩形(MBR)轉(zhuǎn)換成三維空間的最小邊界矩形(MBR的高度對應(yīng)于對象的生命期),以表示位置及范圍均不隨時間發(fā)生變化的時空對象,并使用R-樹索引結(jié)構(gòu)存儲時空數(shù)據(jù)。圖1給出了時空對象實例及其對應(yīng)的3DR-樹。

圖1 用R-樹結(jié)構(gòu)存儲三維的MBRs

3DR-樹實現(xiàn)較容易,可有效地支持時間片查詢,缺點是沒有考慮到時間維的特有屬性。對生命期長或位置變化大的對象,該方法會導(dǎo)致3DR-樹中結(jié)點MBRs的大量重疊,降低查詢效率。
(2)綜合考慮時空對象的時間與空間信息: 以MR-樹和RT-樹為代表的索引方法是將時間和空間信息一起存儲到R-樹結(jié)點中,無論是葉結(jié)點還是非葉結(jié)點中的實體,都以<S,T,P>格式存儲,其中S表示空間信息(MBRs),T是時間信息(時間間隔),P為指向子樹或具體對象的指針。這里T=(t_i,t_j),i≤j,t_j表示當(dāng)前時間戳,t_j+1是下一個時間戳(t_j≤t_j+1)。如果時空對象在時間戳t_j到t_j+1期間空間位置不變,則實體的空間信息S保持不變,而時間信息由T更新為T′(T′=(t_i,t_j+1));一旦時空對象的空間位置發(fā)生變化,原實體保持不變,產(chǎn)生新的實體<S′,T,P′>,插入到索引樹中,其中S′是對象新的空間位置,T=(t_j+1,t_j+1)。該結(jié)構(gòu)較適用于對象移動較少的時空數(shù)據(jù)庫。
(3)基于部分持久和重疊技術(shù)的方法:部分持久結(jié)構(gòu)(partially persistent structure)將二維空間存取方法(如R-樹、四叉樹或k-d-樹結(jié)構(gòu))轉(zhuǎn)換為部分持久的結(jié)構(gòu),它在“邏輯”上存儲過去的時空狀態(tài)S(t),并只對當(dāng)前時空狀態(tài)數(shù)據(jù)更新。對時空狀態(tài)S(t)的歷史查詢,可直接對時空狀態(tài)在時間戳t的部分持久結(jié)構(gòu)操作(可看成是對暫態(tài)R-樹的操作)。該方法避免了3DR-樹中長生命期對象引起的結(jié)點MBRs重疊問題,可有效地支持時間戳和時間間隔查詢。重疊(overlapping)技術(shù)是用二維空間索引為每個時間戳建立一棵對應(yīng)的暫態(tài)樹(如暫態(tài)R-樹),并假設(shè)相鄰時間戳的暫態(tài)樹區(qū)別不大,存在許多共同路徑(路徑上結(jié)點內(nèi)空間對象沒有隨時間變化)。為了節(jié)省磁盤空間,相鄰時間戳的暫態(tài)樹間可共享這些路徑,而那些包含空間對象變化的結(jié)點及路徑可更新后復(fù)制到后續(xù)暫態(tài)樹中。圖2(a)、(b)分別對應(yīng)時間戳t₀和t₁的暫態(tài)R-樹,如果在時間戳t₁結(jié)點3數(shù)據(jù)更新(假設(shè)是結(jié)點3中一個空間對象被刪除),則時間戳t₁的暫態(tài)R-樹與t₀時的區(qū)別僅是創(chuàng)建了新的結(jié)點3a和到達(dá)結(jié)點3a的新路徑,其余結(jié)點和路徑均與t₀時相同,可共享,兩棵暫態(tài)R-樹有重疊部分,見圖2(c)。
(4)移動點過去軌跡的方法:對連續(xù)移動點過去軌跡的索引一般可轉(zhuǎn)化為離散情況下的索引問題。例如,在平面上作直線運(yùn)動的點對象,其運(yùn)動軌跡可看成是若干線段的集合。對象的移動變化意味著在原來軌跡的末端插入新的線段。如果將每條線段都當(dāng)作是一個空間對象(如點或區(qū)域?qū)ο?處理,則連續(xù)點的移動變化相當(dāng)于在數(shù)據(jù)庫中插入和刪除線段對象,可對離散情況下的時空索引進(jìn)行擴(kuò)展,如STR-樹、TB-樹。

圖2 暫態(tài)R-樹及重疊樹

(5)支持移動點未來位置查詢的方法:連續(xù)情況下移動點的運(yùn)動軌跡可用時間函數(shù)(如p_i(t))表示,根據(jù)p_i(t)及已知的某一時間戳移動點的位置來預(yù)測其未來位置。
創(chuàng)建索引的一種簡單方法是假設(shè)點對象在d-維(d=1,2,3)空間移動,這些點未來的移動軌跡可當(dāng)作d+1-維空間的線對象進(jìn)行索引。例如可將一維空間中點的移動軌跡看成是(x,t)空間中的線,可使用PMR-四叉樹(PMR-quadtree)作為索引結(jié)構(gòu)。具體方法是將時間維劃分為若干個相等的時間間隔ΔT,對每個ΔT重建新的PMR-樹索引,并允許在ΔT內(nèi)插入、刪除和更新操作。這種索引結(jié)構(gòu)的缺點是在樹中存在冗余數(shù)據(jù)(如一條線段通常會存儲在幾個結(jié)點中),且需要大量的存儲空間和頻繁的數(shù)據(jù)更新。
另一種方法是在二元空間(dual space)中建立索引,其主要思想源于幾何算法中的二元轉(zhuǎn)換: 將初始空間(primal space)中的線(移動點的軌跡)轉(zhuǎn)換為二元空間中的點,如圖3所示。在二元空間中,基于k-d-樹的存取方法優(yōu)于R-樹。
2. 時空索引分類
時空索引可作如下分類:
(1)按處理的數(shù)據(jù)類型分類:主要的時空數(shù)據(jù)類型為移動點和移動區(qū)域。有些索引只處理點數(shù)據(jù)或移動點的軌跡,支持軌跡查詢; 處理區(qū)域數(shù)據(jù)的索引方法既能處理點數(shù)據(jù)又能處理非點數(shù)據(jù),因為點對象可看成是大小為零的區(qū)域?qū)ο?如3DR-樹、RT-樹、HR-樹、PPR-樹及MV3R-樹等。

(a) 初始空間中移動點的軌跡

(b) 轉(zhuǎn)換后的二次元空間(Hough-X轉(zhuǎn)換)

圖3 二元空間轉(zhuǎn)換

(2)按數(shù)據(jù)加載的方式分類: 在時空數(shù)據(jù)庫中,對過去時間戳的空間數(shù)據(jù)插入或更新均是無意義的(無論是靜態(tài)載入還是動態(tài)插入)。因此,時空索引可分為靜態(tài)、按時間順序(chronological)和動態(tài)的三種類型。靜態(tài)類型和按時間順序類型均不允許對過去時間戳的數(shù)據(jù)插入或更新,前者是以批處理方式載入數(shù)據(jù)(如3DR-樹),后者按時間戳的遞增順序動態(tài)插入數(shù)據(jù)(RT-樹、HR-樹、PPR-樹等); 動態(tài)類型允許動態(tài)插入數(shù)據(jù),且可對過去時間戳的數(shù)據(jù)插入或更新。
(3)按數(shù)據(jù)集的更新情況分類:時空索引可按數(shù)據(jù)集的更新情況分為增長的、變化的和完全動態(tài)的三類。增長類型是指對象靜止不動,而時間是動態(tài)遞增的;變化類型是時間為靜態(tài)的,而對象是移動的; 支持時間動態(tài)變化情況下的移動對象稱為完全動態(tài)類型(full-dynamic),目前研究的索引結(jié)構(gòu)大多是支持時間動態(tài)變化的。
(4)按時空對象的近似表示分類:部分索引結(jié)構(gòu)(如3DR-樹)采用R-樹中用MBR表示空間對象的方法來表示時空對象。由于時空對象獨有的移動特性,這種表示方法會導(dǎo)致大量的無效空間和MBR的重疊,并不能很好地支持時空查詢,對此提出了一些時空對象近似表示方法。
(5)按是否支持特定的時空查詢分類:時空索引除了要支持選擇、連接和最近鄰居查詢外,還應(yīng)支持時間查詢和復(fù)雜的時空查詢,如時間片查詢、軌跡查詢以及歷史查詢等。RT-樹索引結(jié)構(gòu)僅支持基本的時空查詢,HR-樹、PPR-樹支持對時間戳的查詢,3DR-樹和MV3R-樹可同時支持時間戳、時間間隔的查詢; STR-樹、TB-樹以及TPR-樹可支持對移動點的軌跡查詢。
(6)按支持的時間維度分類:時空數(shù)據(jù)庫應(yīng)至少包含一維時間信息,時空索引可分為支持有效時間、事務(wù)時間和雙時間的索引機(jī)制。
(7)按離散/連續(xù)的情況分類: 目前大多數(shù)的索引結(jié)構(gòu)均是基于離散情況(如3DR-樹、HR-樹、RT-樹以及PPR-樹等),可以查詢時空對象過去及當(dāng)前的狀態(tài)。對連續(xù)時空變化情況下,可根據(jù)時空對象位置或范圍隨時間變化的函數(shù)來建立索引,不僅可以查詢時空對象過去和當(dāng)前的位置和范圍,還可根據(jù)時空對象當(dāng)前的信息推測出它在將來某個時間戳的行為。