大規(guī)模圖數(shù)據(jù)庫上的模式匹配.pdf

1、數(shù)據(jù)管理問題幾乎存在于一切人類活動(dòng)領(lǐng)域中,如何利用計(jì)算機(jī)來管理大量的數(shù)據(jù),幾乎對于各個(gè)領(lǐng)域的工作者來說都是很重要的。關(guān)系型數(shù)據(jù)庫已經(jīng)在很多領(lǐng)域取得了巨大的成功,但是,已經(jīng)有越來越多的復(fù)雜數(shù)據(jù)超出了傳統(tǒng)的關(guān)系型數(shù)據(jù)庫的能力范圍,圖就是這些復(fù)雜數(shù)據(jù)中的一種,它具有十分強(qiáng)大的表達(dá)能力,可以很好地表達(dá)像社會網(wǎng)絡(luò)、XML文檔、生物化學(xué)分子、蛋白質(zhì)作用網(wǎng)絡(luò)等客觀世界事物的語義。因此,圖數(shù)據(jù)的管理和查詢吸引了越來越多的研究者的目光。
　　圖數(shù)據(jù)

2、庫上的模式匹配問題,要求給出指定查詢結(jié)構(gòu)在圖數(shù)據(jù)庫中的所有出現(xiàn)位置。這一問題是圖數(shù)據(jù)庫領(lǐng)域的關(guān)鍵問題之一,也是潛在應(yīng)用最大的問題之一。一些研究者和程序開發(fā)者已經(jīng)在這方面提出了很多的解決方案。但是,大部分的已有工作,要么是針對“小圖”數(shù)據(jù)庫的,也就是假設(shè)可以把數(shù)據(jù)庫中一部分的數(shù)據(jù)圖完全裝載進(jìn)內(nèi)存里來,模式匹配算法可以完全在內(nèi)存里進(jìn)行。要么就是主要關(guān)注一些比較基本的查詢,而對于復(fù)雜的模式查詢,主要是通過關(guān)系數(shù)據(jù)庫中的連接操作來實(shí)現(xiàn)的。本文則

3、是主要關(guān)注和討論如何在大規(guī)模的、基于磁盤的圖數(shù)據(jù)庫上高效地進(jìn)行模式匹配查詢。本文的主要研究成果如下:
　　(1)提出了一種大規(guī)模圖數(shù)據(jù)庫的系統(tǒng)設(shè)計(jì)方案并對其主要部分進(jìn)行了實(shí)現(xiàn)。
　　(2)提出了一種全新的、在基于磁盤的大圖上進(jìn)行模式匹配的算法。在本文中,模式匹配問題被轉(zhuǎn)化為了多個(gè)臨時(shí)表的連接問題。針對“廣度優(yōu)先”和“深度優(yōu)先”策略各自的缺陷,本文提出了一種“滿前進(jìn)-空后退”的連接策略,可以在不把數(shù)量龐大的中間結(jié)果寫入到磁盤的

4、情況下,完成整個(gè)模式匹配的過程。對于基于磁盤的圖數(shù)據(jù)庫上的模式匹配所特有的一些問題,比如,一些臨時(shí)數(shù)據(jù)的訪問和存儲方法、caChe策略等問題,本文也進(jìn)行了一些深入的討論。
　　(3)針對所述的模式匹配算法框架,本文提出了幾種優(yōu)化措施。本文討論了不同的連接順序?qū)τ诓樵儓?zhí)行效率的影響,提出了不同連接順序的執(zhí)行代價(jià)應(yīng)該用什么樣的標(biāo)準(zhǔn)來衡量。針對執(zhí)行代價(jià)的衡量標(biāo)準(zhǔn),本文提出了一種有效的優(yōu)化連接順序的方法。另外,本文還討論了算法的平行化執(zhí)行