分布式图查询系统优化器的设计与实现

发布时间：2021-11-02 03:11

　　图结构数据有助于数据的相关性挖掘,近年来使用图结构来表示大型数据变得越来越流行,其中资源描述框架（RDF）系统逐渐被广泛使用在公共知识库和网页内容的存储上,并给用户提供使用SPARQL语言进行查询的服务。大量的RDF图查询系统被研究界和工业界提出来,这些RDF系统致力于提供给用户在大型RDF数据集中进行高并发度和低延迟的查询服务。查询优化器作为查询系统必不可少的组成部分成为提升查询整体性能的关键,新软件和硬件优化方法的出现给查询优化器的设计和实现提出了新的挑战。查询优化器由三部分组成:基数估计模块、开销模型模块和遍历算法模块。这三部分共同协作对外提供查询优化服务,每一部分都对查询优化的效果和性能都有着至关重要的影响。本文通过数据测试和分析发现传统的基于三元组连接的查询优化器存在许多问题:在基数估计方面,采用基于两元谓词关系的方法进行基数估计,并用两元谓词选择率的乘积来代替多元谓词间的依赖,该基数估计方法也无法适用于新型的基于图探索的系统;在开销模型方面,由于新型查询系统Wukong^[1]的出现,查询语义的不同导致成熟的开销模型无法直接移植和复用。针对这些问题,本文... 

【文章来源】：上海交通大学上海市 211工程院校 985工程院校 教育部直属院校

【文章页数】：99 页

【学位级别】：硕士

【文章目录】：
摘要
abstract
第一章 绪论
    1.1 研究背景
    1.2 研究现状
    1.3 主要研究内容
    1.4 论文组织结构
第二章 相关技术背景
    2.1 RDF与 SPARQL
    2.2 SPARQL查询执行方式
    2.3 查询优化器
        2.3.1 基本组成
        2.3.2 查询优化过程
    2.4 本章小结
第三章 基于三元组连接的查询优化器的分析与评测
    3.1 基于三元存储的统计方法
    3.2 基数估计
    3.3 开销模型
    3.4 查询优化时间
    3.5 本章小结
第四章 基于全历史图探索的查询优化器的设计与实现
    4.1 系统架构
    4.2 统计数据
        4.2.1 基于谓词关系的统计数据
        4.2.2 统计数据收集过程
    4.3 基于全历史记录的基数估计
        4.3.1 基本的基数估计方法
        4.3.2 多元谓词关系的处理
        4.3.3 常量剪枝估计
    4.4 开销模型
    4.5 计划空间遍历算法
        4.5.1 深度优先遍历
        4.5.2 动态规划算法
        4.5.3 索引的影响
        4.5.4 算法对比
        4.5.5 空集查询优化
    4.6 本章小结
第五章 基于类型的查询优化方法
    5.1 基于全历史图探索的查询优化器存在的问题分析
        5.1.1 基于谓词关系的基数估计准确性分析
        5.1.2 开销模型合理性分析
        5.1.3 查询优化时间分析
        5.1.4 存在问题总结
    5.2 观察和假设
    5.3 统计数据
        5.3.1 基于类型的统计数据
        5.3.2 统计数据收集方法
    5.4 基于类型的基数估计
    5.5 无类型和多类型
    5.6 细粒度的开销模型
    5.7 有区分的查询优化算法
        5.7.1 基于规则的查询优化
        5.7.2 大小型查询的区分
    5.8 本章小结
第六章 实验和评测
    6.1 测试环境
    6.2 测试方法
    6.3 基数估计准确性
    6.4 开销模型准确性
    6.5 查询优化时间
    6.6 总体性能
    6.7 本章小结
第七章 总结与展望
    7.1 全文总结
    7.2 工作展望
参考文献
致谢
攻读学位期间发表的学术论文



本文编号：3471221