發(fā)布時間：2017-03-24 10:05

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

【摘要】：圖這種數(shù)據(jù)結構具有強大的表達能力,通常被用對于現(xiàn)實生活中的各種對象及其之間的關系進行描述和建模,在計算機學科的各個領域都有著廣泛的應用。傳統(tǒng)的關系數(shù)據(jù)庫用“表”這種結構來存儲數(shù)據(jù)和關系,在對圖數(shù)據(jù)的表達上存在著一些缺陷。本文對關系數(shù)據(jù)庫和圖數(shù)據(jù)的特征分別作了分析,指出了用關系數(shù)據(jù)庫在處理圖數(shù)據(jù)過程中存在的各種困難,并提出了一種解決方案,用于高效地在關系數(shù)據(jù)庫中對圖型數(shù)據(jù)做查詢。本文首先介紹了GraphView,它是一種基于關系數(shù)據(jù)庫的中間層系統(tǒng)。它提供了一套完整的接口,用戶可以利用它給出自己的圖數(shù)據(jù)定義。GraphView根據(jù)用戶的定義,將圖數(shù)據(jù)導入到關系數(shù)據(jù)庫中,這個過程對用戶是完全透明的。GraphView采用了一種特殊的節(jié)點表來表示圖中的節(jié)點信息,圖中所有的邊都以二進制串的形式存儲到了節(jié)點表里。本文詳細介紹了這種表示方式的實現(xiàn)機制,并重點分析了該方法在存儲局部性上的性能優(yōu)勢。隨后,為了更好地表達圖查詢,我們對標準的SQL語句作了擴展,增加了一個新的MATCH子句對圖模式進行描述。我們詳細介紹了這種擴展語言的語法,并給出了一系列具體的例子。這種查詢語言將被GraphView翻譯為標準的SQL語句在關系數(shù)據(jù)庫里運行,我們給出了具體的翻譯算法。在翻譯過程中,我們重點討論了可能的優(yōu)化方法,并設計了一個代價模型來對不同的翻譯方案進行評估,最后我們設計了一個啟發(fā)式的搜索算法,它可以在較短的時間內找到一個近似最優(yōu)的翻譯方法。我們利用本文介紹的GraphView系統(tǒng)和擴展的圖查詢語言,給出了幾個解決具體的圖應用的例子。我們討論了圖查詢中幾種常見的優(yōu)化算法,并詳細介紹了這些優(yōu)化技術在GraphView中具體的實現(xiàn)細節(jié)。最后,我們通過一系列詳盡的實驗在不同的數(shù)據(jù)集上對GraphView系統(tǒng)作了測試和評估。我們將其與標準的SQL數(shù)據(jù)庫和圖數(shù)據(jù)庫作了性能比對,實現(xiàn)結果表明,本文介紹的GraphView系統(tǒng)和基于其實現(xiàn)圖查詢算法在性能上具有明顯的優(yōu)勢。
【關鍵詞】：關系數(shù)據(jù)庫 圖查詢 優(yōu)化算法
【學位授予單位】：上海交通大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TP311.13
【目錄】：

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

【相似文獻】

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

1 趙曉英;;關系數(shù)據(jù)庫中固定數(shù)據(jù)、半固定數(shù)據(jù)、變動數(shù)據(jù)的處理[J];晉中學院學報;2005年06期

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

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

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

5 陳楚s

本文編號：265431