發(fā)布時間：2021-11-02 03:11

　　圖結(jié)構數(shù)據(jù)有助于數(shù)據(jù)的相關性挖掘,近年來使用圖結(jié)構來表示大型數(shù)據(jù)變得越來越流行,其中資源描述框架（RDF）系統(tǒng)逐漸被廣泛使用在公共知識庫和網(wǎng)頁內(nèi)容的存儲上,并給用戶提供使用SPARQL語言進行查詢的服務。大量的RDF圖查詢系統(tǒng)被研究界和工業(yè)界提出來,這些RDF系統(tǒng)致力于提供給用戶在大型RDF數(shù)據(jù)集中進行高并發(fā)度和低延遲的查詢服務。查詢優(yōu)化器作為查詢系統(tǒng)必不可少的組成部分成為提升查詢整體性能的關鍵,新軟件和硬件優(yōu)化方法的出現(xiàn)給查詢優(yōu)化器的設計和實現(xiàn)提出了新的挑戰(zhàn)。查詢優(yōu)化器由三部分組成:基數(shù)估計模塊、開銷模型模塊和遍歷算法模塊。這三部分共同協(xié)作對外提供查詢優(yōu)化服務,每一部分都對查詢優(yōu)化的效果和性能都有著至關重要的影響。本文通過數(shù)據(jù)測試和分析發(fā)現(xiàn)傳統(tǒng)的基于三元組連接的查詢優(yōu)化器存在許多問題:在基數(shù)估計方面,采用基于兩元謂詞關系的方法進行基數(shù)估計,并用兩元謂詞選擇率的乘積來代替多元謂詞間的依賴,該基數(shù)估計方法也無法適用于新型的基于圖探索的系統(tǒng);在開銷模型方面,由于新型查詢系統(tǒng)Wukong^[1]的出現(xiàn),查詢語義的不同導致成熟的開銷模型無法直接移植和復用。針對這些問題,本文... 

【文章來源】：上海交通大學上海市 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：99 頁

【學位級別】：碩士

【文章目錄】：
摘要
abstract
第一章 緒論
    1.1 研究背景
    1.2 研究現(xiàn)狀
    1.3 主要研究內(nèi)容
    1.4 論文組織結(jié)構
第二章 相關技術背景
    2.1 RDF與 SPARQL
    2.2 SPARQL查詢執(zhí)行方式
    2.3 查詢優(yōu)化器
        2.3.1 基本組成
        2.3.2 查詢優(yōu)化過程
    2.4 本章小結(jié)
第三章 基于三元組連接的查詢優(yōu)化器的分析與評測
    3.1 基于三元存儲的統(tǒng)計方法
    3.2 基數(shù)估計
    3.3 開銷模型
    3.4 查詢優(yōu)化時間
    3.5 本章小結(jié)
第四章 基于全歷史圖探索的查詢優(yōu)化器的設計與實現(xiàn)
    4.1 系統(tǒng)架構
    4.2 統(tǒng)計數(shù)據(jù)
        4.2.1 基于謂詞關系的統(tǒng)計數(shù)據(jù)
        4.2.2 統(tǒng)計數(shù)據(jù)收集過程
    4.3 基于全歷史記錄的基數(shù)估計
        4.3.1 基本的基數(shù)估計方法
        4.3.2 多元謂詞關系的處理
        4.3.3 常量剪枝估計
    4.4 開銷模型
    4.5 計劃空間遍歷算法
        4.5.1 深度優(yōu)先遍歷
        4.5.2 動態(tài)規(guī)劃算法
        4.5.3 索引的影響
        4.5.4 算法對比
        4.5.5 空集查詢優(yōu)化
    4.6 本章小結(jié)
第五章 基于類型的查詢優(yōu)化方法
    5.1 基于全歷史圖探索的查詢優(yōu)化器存在的問題分析
        5.1.1 基于謂詞關系的基數(shù)估計準確性分析
        5.1.2 開銷模型合理性分析
        5.1.3 查詢優(yōu)化時間分析
        5.1.4 存在問題總結(jié)
    5.2 觀察和假設
    5.3 統(tǒng)計數(shù)據(jù)
        5.3.1 基于類型的統(tǒng)計數(shù)據(jù)
        5.3.2 統(tǒng)計數(shù)據(jù)收集方法
    5.4 基于類型的基數(shù)估計
    5.5 無類型和多類型
    5.6 細粒度的開銷模型
    5.7 有區(qū)分的查詢優(yōu)化算法
        5.7.1 基于規(guī)則的查詢優(yōu)化
        5.7.2 大小型查詢的區(qū)分
    5.8 本章小結(jié)
第六章 實驗和評測
    6.1 測試環(huán)境
    6.2 測試方法
    6.3 基數(shù)估計準確性
    6.4 開銷模型準確性
    6.5 查詢優(yōu)化時間
    6.6 總體性能
    6.7 本章小結(jié)
第七章 總結(jié)與展望
    7.1 全文總結(jié)
    7.2 工作展望
參考文獻
致謝
攻讀學位期間發(fā)表的學術論文



本文編號：3471221