關(guān)系數(shù)據(jù)庫中圖查詢優(yōu)化方法的研究.pdf

1、圖這種數(shù)據(jù)結(jié)構(gòu)具有強(qiáng)大的表達(dá)能力，通常被用對(duì)于現(xiàn)實(shí)生活中的各種對(duì)象及其之間的關(guān)系進(jìn)行描述和建模，在計(jì)算機(jī)學(xué)科的各個(gè)領(lǐng)域都有著廣泛的應(yīng)用。傳統(tǒng)的關(guān)系數(shù)據(jù)庫用“表”這種結(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)和關(guān)系，在對(duì)圖數(shù)據(jù)的表達(dá)上存在著一些缺陷。本文對(duì)關(guān)系數(shù)據(jù)庫和圖數(shù)據(jù)的特征分別作了分析，指出了用關(guān)系數(shù)據(jù)庫在處理圖數(shù)據(jù)過程中存在的各種困難，并提出了一種解決方案，用于高效地在關(guān)系數(shù)據(jù)庫中對(duì)圖型數(shù)據(jù)做查詢。
　　本文首先介紹了GraphView，它是一種基于關(guān)

2、系數(shù)據(jù)庫的中間層系統(tǒng)。它提供了一套完整的接口，用戶可以利用它給出自己的圖數(shù)據(jù)定義。GraphView根據(jù)用戶的定義，將圖數(shù)據(jù)導(dǎo)入到關(guān)系數(shù)據(jù)庫中，這個(gè)過程對(duì)用戶是完全透明的。GraphView采用了一種特殊的節(jié)點(diǎn)表來表示圖中的節(jié)點(diǎn)信息，圖中所有的邊都以二進(jìn)制串的形式存儲(chǔ)到了節(jié)點(diǎn)表里。本文詳細(xì)介紹了這種表示方式的實(shí)現(xiàn)機(jī)制，并重點(diǎn)分析了該方法在存儲(chǔ)局部性上的性能優(yōu)勢(shì)。
　　隨后，為了更好地表達(dá)圖查詢，我們對(duì)標(biāo)準(zhǔn)的SQL語句作了擴(kuò)展，增加

3、了一個(gè)新的MATCH子句對(duì)圖模式進(jìn)行描述。我們?cè)敿?xì)介紹了這種擴(kuò)展語言的語法，并給出了一系列具體的例子。這種查詢語言將被GraphView翻譯為標(biāo)準(zhǔn)的SQL語句在關(guān)系數(shù)據(jù)庫里運(yùn)行，我們給出了具體的翻譯算法。在翻譯過程中，我們重點(diǎn)討論了可能的優(yōu)化方法，并設(shè)計(jì)了一個(gè)代價(jià)模型來對(duì)不同的翻譯方案進(jìn)行評(píng)估，最后我們?cè)O(shè)計(jì)了一個(gè)啟發(fā)式的搜索算法，它可以在較短的時(shí)間內(nèi)找到一個(gè)近似最優(yōu)的翻譯方法。
　　我們利用本文介紹的GraphView系統(tǒng)和擴(kuò)展的