本文關(guān)鍵詞：關(guān)系數(shù)據(jù)庫中圖查詢優(yōu)化方法的研究，，由筆耕文化傳播整理發(fā)布。

【摘要】：圖這種數(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)系數(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ò)展,增加了一個(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ò)展的圖查詢語言,給出了幾個(gè)解決具體的圖應(yīng)用的例子。我們討論了圖查詢中幾種常見的優(yōu)化算法,并詳細(xì)介紹了這些優(yōu)化技術(shù)在GraphView中具體的實(shí)現(xiàn)細(xì)節(jié)。最后,我們通過一系列詳盡的實(shí)驗(yàn)在不同的數(shù)據(jù)集上對(duì)GraphView系統(tǒng)作了測(cè)試和評(píng)估。我們將其與標(biāo)準(zhǔn)的SQL數(shù)據(jù)庫和圖數(shù)據(jù)庫作了性能比對(duì),實(shí)現(xiàn)結(jié)果表明,本文介紹的GraphView系統(tǒng)和基于其實(shí)現(xiàn)圖查詢算法在性能上具有明顯的優(yōu)勢(shì)。
【關(guān)鍵詞】：關(guān)系數(shù)據(jù)庫 圖查詢 優(yōu)化算法
【學(xué)位授予單位】：上海交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP311.13
【目錄】：

• 摘要3-5
• ABSTRACT5-10
• 第一章 緒論10-16
• 1.1 用關(guān)系數(shù)據(jù)庫處理圖數(shù)據(jù)10-11
• 1.2 針對(duì)圖數(shù)據(jù)的查詢語言11
• 1.3 針對(duì)圖數(shù)據(jù)查詢的優(yōu)化技術(shù)11-12
• 1.4 國(guó)內(nèi)外研究現(xiàn)狀12-14
• 1.4.1 NoSQL數(shù)據(jù)庫12-13
• 1.4.2 圖數(shù)據(jù)庫13
• 1.4.3 圖數(shù)據(jù)的查詢與優(yōu)化13-14
• 1.5 本章小結(jié)14-16
• 第二章 圖數(shù)據(jù)在關(guān)系數(shù)據(jù)庫中的表示16-24
• 2.1 GraphView概覽16-17
• 2.2 節(jié)點(diǎn)表的設(shè)計(jì)17-19
• 2.3 關(guān)系數(shù)據(jù)庫中的圖遍歷19-22
• 2.4 本章小結(jié)22-24
• 第三章 基于SQL的圖查詢語言設(shè)計(jì)24-36
• 3.1 擴(kuò)展的SQL語言24-26
• 3.2 圖查詢的翻譯26-33
• 3.2.1 邊的反轉(zhuǎn)27-28
• 3.2.2 圖模式的分解28-29
• 3.2.3 代價(jià)模型29-32
• 3.2.4 翻譯算法32-33
• 3.3 本章小結(jié)33-36
• 第四章 用關(guān)系數(shù)據(jù)庫處理圖查詢36-48
• 4.1 PageRank36-38
• 4.1.1 問題描述36-37
• 4.1.2 迭代的計(jì)算過程37-38
• 4.2 整體同步并行模型38-42
• 4.3 圖查詢中的優(yōu)化42-45
• 4.4 異步計(jì)算模型45-46
• 4.5 本章小結(jié)46-48
• 第五章 實(shí)驗(yàn)48-56
• 5.1 實(shí)驗(yàn)環(huán)境48-49
• 5.2 GraphView vs. SQL49-52
• 5.3 GraphView vs. Neo4j52-53
• 5.4 GraphView vs. GraphLab53-54
• 5.5 本章小結(jié)54-56
• 第六章 結(jié)束語56-58
• 參考文獻(xiàn)58-62
• 致謝62-64
• 攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文目錄64-66

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫 前10條

1 趙曉英;;關(guān)系數(shù)據(jù)庫中固定數(shù)據(jù)、半固定數(shù)據(jù)、變動(dòng)數(shù)據(jù)的處理[J];晉中學(xué)院學(xué)報(bào);2005年06期

2 羅幼平;;關(guān)系數(shù)據(jù)庫中的多表聯(lián)接查詢[J];電腦知識(shí)與技術(shù);2006年05期

3 陳莉瑩;董文;;“教、學(xué)、做一體化”在“關(guān)系數(shù)據(jù)庫”課程中的應(yīng)用[J];學(xué)習(xí)月刊;2010年15期

4 蔡曉兵;;模糊關(guān)系數(shù)據(jù)庫和關(guān)系數(shù)據(jù)庫中的模糊信息[J];貴州工學(xué)院學(xué)報(bào);1990年01期

5 陳楚s

本文編號(hào)：265431