半結(jié)構(gòu)化索引(數(shù)據(jù)庫(kù))

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

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

    半結(jié)構(gòu)化索引 : 對(duì)主要是XML數(shù)據(jù)的半結(jié)構(gòu)化數(shù)據(jù)所建立的索引。結(jié)構(gòu)匯總(structural summary)類(lèi)索引,以XML-樹(shù)結(jié)構(gòu)中結(jié)點(diǎn)的路徑信息為基礎(chǔ),采取某種化簡(jiǎn)方式,使得化簡(jiǎn)后的樹(shù)結(jié)構(gòu)只維護(hù)不同的路徑信息,而不會(huì)存在具有相同路徑的兩個(gè)結(jié)點(diǎn)。該類(lèi)索引仍然采取標(biāo)簽有向圖的結(jié)構(gòu)。當(dāng)基于結(jié)構(gòu)匯總進(jìn)行XML查詢(xún)處理時(shí),避免了對(duì)XML中標(biāo)簽路徑相同的結(jié)點(diǎn)需要重新遍歷所有相同路徑的缺陷。
T-索引(T-index): 即模板索引(template index),它是一個(gè)通用的用于半結(jié)構(gòu)化數(shù)據(jù)的索引結(jié)構(gòu)。T-索引具有以下特點(diǎn): ①允許在空間與通用性之間進(jìn)行權(quán)衡。②索引構(gòu)建效率比較高。③索引本身占用空間不是很大。④具有很好的推廣性。
T-索引的關(guān)鍵思想在于,將數(shù)據(jù)庫(kù)對(duì)象按等價(jià)類(lèi)(equivalence class)進(jìn)行分組,每個(gè)類(lèi)包含與路徑模板(path template)定義相同的路徑。由于計(jì)算完全的等價(jià)關(guān)系代價(jià)很高,因此T-索引只考慮計(jì)算效率較高的半雙擬(bisimulation)或雙擬(simulation)關(guān)系,為便于描述,本索引中所提到的等價(jià)關(guān)系均指這種半雙擬或雙擬等價(jià)關(guān)系。
如果存在一個(gè)半雙擬關(guān)系～,即v～u,則兩個(gè)結(jié)點(diǎn)v和u是半相似(bisimilar)的,寫(xiě)為v≈_bu。同樣的,如果存在兩個(gè)雙擬關(guān)系≤,即v≤u和u≤v,則兩個(gè)結(jié)點(diǎn)v和u是相似(similar)的,寫(xiě)為v≈_su。實(shí)際上,有一個(gè)簡(jiǎn)單的判斷相互半相似的推論。如果兩個(gè)結(jié)點(diǎn)是相互半相似的,則進(jìn)入它們的輸入邊(in-coming path)是相同的。
基于上述這種等價(jià)關(guān)系,利用非確定性自動(dòng)機(jī)(non-deterministic automaton)可以構(gòu)建一個(gè)T-索引,自動(dòng)機(jī)中的狀態(tài)代表等價(jià)類(lèi),狀態(tài)遷移對(duì)應(yīng)于類(lèi)中對(duì)象間的邊。在T-索引中,半結(jié)構(gòu)化數(shù)據(jù)被建模成一個(gè)邊帶有標(biāo)記的圖(labeled graph),圖中結(jié)點(diǎn)對(duì)應(yīng)數(shù)據(jù)庫(kù)中的對(duì)象,邊對(duì)應(yīng)對(duì)象的屬性。標(biāo)記圖用DB=(V,E,R)形式化表示,其中V表示圖的頂點(diǎn),是有限的頂點(diǎn)集合; E表示圖中相鄰結(jié)點(diǎn)之間的邊,是帶標(biāo)記的邊集合;R是根結(jié)點(diǎn)集合,從R中某個(gè)根結(jié)點(diǎn)r_i出發(fā)可達(dá)V中以r_i為根的所有相關(guān)頂點(diǎn)。
一個(gè)路徑模板t具有T₁x₁T₂x₂…T_nx_n表達(dá)形式,其中每個(gè)T或者是一個(gè)正則路徑表達(dá)式(regular path expression),或者是P和F二個(gè)占位符之一。P可用正則路徑表達(dá)式來(lái)替換,F可用公式替換。一個(gè)查詢(xún)由一條查詢(xún)路徑和一組變量集合構(gòu)成,其表示形式為“select x_i1,x_i2,…,x_ik from P₁x₁P₂x₂…P_nx_n”,查詢(xún)路徑就是對(duì)路徑模板的實(shí)例化。比如,一個(gè)真實(shí)的查詢(xún)具有形式“select x from(*.Restaurant) x(Menu.*.Dinner.*.Lasagna) y” ,其中(*.Restaurant)和(Menu.*.Dinner.*.Lasagna)就是路徑模板實(shí)例。如果令t=Px₁Px₂…Px_k,那么t₁＝Px就是1-索引,t₂＝^*x₁Px₂就是2-索引。
實(shí)際上,有一個(gè)簡(jiǎn)單的判斷1-索引和2-索引的推論。1-索引就是從根結(jié)點(diǎn)root進(jìn)入某個(gè)結(jié)點(diǎn)v的所有路徑均相同。2-索引就是一對(duì)結(jié)點(diǎn)(對(duì)應(yīng)一條標(biāo)記路徑的起始點(diǎn)和終止點(diǎn))具有相同的標(biāo)記路徑。圖1和圖2給出了1-索引和2-索引。在圖1中,(a)為數(shù)據(jù)圖;(b)為該數(shù)據(jù)圖對(duì)應(yīng)的1-索引;(c)為數(shù)據(jù)圖對(duì)應(yīng)的強(qiáng)數(shù)據(jù)向?qū)?data guide)。

圖1 1-索引

圖2 2-索引

A(K)索引(A(K)index):由于1-索引和DataGuide要對(duì)XML數(shù)據(jù)圖中的所有路徑進(jìn)行編碼,包括長(zhǎng)的和復(fù)雜的路徑,因此,即使當(dāng)兩個(gè)結(jié)點(diǎn)局部相似時(shí),它們也必須被存儲(chǔ)成不同的實(shí)例。針對(duì)該問(wèn)題,一種利用局部相似性(local similarity)來(lái)構(gòu)建索引的機(jī)制被提出,這就是A(K)索引。A(K)索引的基本思想是: 該索引放棄了索引的絕對(duì)準(zhǔn)確性,而是將在一起的相似數(shù)據(jù)進(jìn)行分組,以便一次更新操作對(duì)索引占據(jù)空間大小和索引最大范圍所產(chǎn)生的影響可以通過(guò)一個(gè)參數(shù)k來(lái)控制。
A(K)索引是一種近似的結(jié)構(gòu)匯總(approximate structural summary)索引,是基于k-相互半相似性(k-bisimilarity)來(lái)構(gòu)建的,它具有這樣的性質(zhì): 如果兩個(gè)結(jié)點(diǎn)u和v是k-相互半相似的,則進(jìn)入它們的長(zhǎng)為k的標(biāo)記路徑集合是相同的。k-相互半相似性≈^k的遞歸定義如下:
(1)對(duì)于任意兩個(gè)結(jié)點(diǎn)u和v,如果u和v具有相同的標(biāo)記,則u≈⁰v。
(2)對(duì)于u的每個(gè)父結(jié)點(diǎn)u′,都存在一個(gè)v的父結(jié)點(diǎn)v′,使得u≈^k-1v,則u≈^kv。
k-相互半相似性定義了圖中結(jié)點(diǎn)的等價(jià)關(guān)系。通過(guò)為每個(gè)等價(jià)類(lèi)建立一個(gè)索引結(jié)點(diǎn),并將數(shù)據(jù)結(jié)點(diǎn)與索引結(jié)點(diǎn)相關(guān)聯(lián),然后將索引結(jié)點(diǎn)用邊連接起來(lái),這樣就形成了一個(gè)索引圖。A(K)索引的創(chuàng)建過(guò)程是一個(gè)逐漸細(xì)化的過(guò)程:k階索引的建立是在(k-1)階索引的基礎(chǔ)上實(shí)現(xiàn)的,隨著k的增加,通過(guò)分裂某一指定的等價(jià)類(lèi),會(huì)進(jìn)一步細(xì)化由原等價(jià)關(guān)系所引入的部分,直至到達(dá)最大的雙相似性,即獲得了1-索引為止。
圖3解釋了A(k)索引的整個(gè)構(gòu)建過(guò)程。首先給出了一個(gè)數(shù)據(jù)圖G,以及基于0-半相似性、1-半相似性和2-半相似性的A(0)索引、A(1)索引以及A(2)索引。在當(dāng)前情況下,2-半相似性索引就是基于最大半相似性的1-索引。

圖3 一系列A(K)索引

從圖中可以看出,A(0)索引就是將結(jié)點(diǎn)標(biāo)記相同的結(jié)點(diǎn)實(shí)例合并在一起的索引,如G中標(biāo)記為D的結(jié)點(diǎn)實(shí)例{4,5}在A(0)索引中被合并成一個(gè)D結(jié)點(diǎn),同樣的還有具有兩個(gè)實(shí)例{6,7}的E結(jié)點(diǎn)。A(1)索引是將到G中任意一個(gè)結(jié)點(diǎn)的長(zhǎng)度為1的輸入邊相同的結(jié)點(diǎn)合并到一起的索引,如G中結(jié)點(diǎn)標(biāo)記為E的兩個(gè)實(shí)例結(jié)點(diǎn){6,7},由于它們具有相同的長(zhǎng)度為1的輸入邊,因此在A(1)索引中它們被合并成一個(gè)E結(jié)點(diǎn)。類(lèi)似地,A(2)索引就是將到G中任意一個(gè)結(jié)點(diǎn)的長(zhǎng)度為2的輸入邊相同的結(jié)點(diǎn)合并到一起的索引,由于G中所有長(zhǎng)為2的輸入邊均不相同,因此,A(2)索引中沒(méi)有合并結(jié)點(diǎn)的存在。同時(shí),在該例中,由于A(2)索引具有最大的半相似性,因此A(2)索引與1-索引相同。