基于修改空間的圖形數(shù)據(jù)庫Top-K查詢研究.pdf

1、近年來,計(jì)算機(jī)應(yīng)用正以各種方式越來越快地滲透到各個(gè)領(lǐng)域之中。其中以數(shù)據(jù)庫,尤其是關(guān)系數(shù)據(jù)庫的應(yīng)用最為廣泛。關(guān)系數(shù)據(jù)庫以集合代數(shù)為基礎(chǔ),利用關(guān)系模型來建立問題和領(lǐng)域結(jié)構(gòu)模型。然而這種建模方式有一定的局限性,難以直接且深入的描述現(xiàn)實(shí)世界對(duì)象間復(fù)雜聯(lián)系。圖形是一種描述性很強(qiáng)的數(shù)據(jù)結(jié)構(gòu)。通過加以標(biāo)記的頂點(diǎn)和邊,圖形既可以深入描述一組實(shí)體間的關(guān)系,也可以直觀地描述這些關(guān)系間的屬性。在復(fù)雜結(jié)構(gòu)數(shù)據(jù)建模方面,如化合物分子結(jié)構(gòu),蛋白質(zhì)基因結(jié)構(gòu),電路結(jié)構(gòu)

2、,Web和XML文檔等,圖形起著很重要的作用,圖形數(shù)據(jù)庫也由此得到廣泛的關(guān)注及應(yīng)用。 隨著圖形數(shù)據(jù)庫越來越大,對(duì)于快速有效圖形查詢搜索系統(tǒng)的需要也越來越迫切?，F(xiàn)有的圖形搜索方法是將數(shù)據(jù)庫中的頻繁結(jié)構(gòu)碎片作為索引項(xiàng),根據(jù)各個(gè)圖形所包含的結(jié)構(gòu)碎片邊的特性做高維索引,查詢時(shí)把圖形進(jìn)行分解,在索引中查找包含所有碎片的圖形。但是圖形頻繁結(jié)構(gòu)碎片需由圖形數(shù)據(jù)庫的挖掘獲得,頻繁結(jié)構(gòu)邊數(shù)的不同使得每個(gè)索引項(xiàng)的維數(shù)也不確定,而且查詢圖形難以實(shí)現(xiàn)最

3、優(yōu)分解。 GString技術(shù)是目前圖形表示的最新方法,該方法給出了三種基本結(jié)構(gòu)及語法規(guī)則來描述基本子圖,進(jìn)而通過基本子圖的組合表示圖形。本文以此為基礎(chǔ),構(gòu)建了一個(gè)圖形修改空間,通過不同的權(quán)值分配,把每個(gè)基本子圖頂點(diǎn),分支和邊的修改作為其在圖形修改空間中各方向的位移。在此修改空間基礎(chǔ)上,本文為屬于相同類型的基本子圖建立三維R-tree索引,并對(duì)R-tree索引的相關(guān)算法進(jìn)行修改,以滿足對(duì)圖形修改的特定需要。圖形修改空間的實(shí)例和模擬