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

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

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

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

【學(xué)位級(jí)別】：碩士

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



本文編號(hào)：3471221