关系数据库中图查询优化方法的研究

发布时间：2017-03-24 10:05

  本文关键词：关系数据库中图查询优化方法的研究，，由笔耕文化传播整理发布。

【摘要】：图这种数据结构具有强大的表达能力,通常被用对于现实生活中的各种对象及其之间的关系进行描述和建模,在计算机学科的各个领域都有着广泛的应用。传统的关系数据库用“表”这种结构来存储数据和关系,在对图数据的表达上存在着一些缺陷。本文对关系数据库和图数据的特征分别作了分析,指出了用关系数据库在处理图数据过程中存在的各种困难,并提出了一种解决方案,用于高效地在关系数据库中对图型数据做查询。本文首先介绍了GraphView,它是一种基于关系数据库的中间层系统。它提供了一套完整的接口,用户可以利用它给出自己的图数据定义。GraphView根据用户的定义,将图数据导入到关系数据库中,这个过程对用户是完全透明的。GraphView采用了一种特殊的节点表来表示图中的节点信息,图中所有的边都以二进制串的形式存储到了节点表里。本文详细介绍了这种表示方式的实现机制,并重点分析了该方法在存储局部性上的性能优势。随后,为了更好地表达图查询,我们对标准的SQL语句作了扩展,增加了一个新的MATCH子句对图模式进行描述。我们详细介绍了这种扩展语言的语法,并给出了一系列具体的例子。这种查询语言将被GraphView翻译为标准的SQL语句在关系数据库里运行,我们给出了具体的翻译算法。在翻译过程中,我们重点讨论了可能的优化方法,并设计了一个代价模型来对不同的翻译方案进行评估,最后我们设计了一个启发式的搜索算法,它可以在较短的时间内找到一个近似最优的翻译方法。我们利用本文介绍的GraphView系统和扩展的图查询语言,给出了几个解决具体的图应用的例子。我们讨论了图查询中几种常见的优化算法,并详细介绍了这些优化技术在GraphView中具体的实现细节。最后,我们通过一系列详尽的实验在不同的数据集上对GraphView系统作了测试和评估。我们将其与标准的SQL数据库和图数据库作了性能比对,实现结果表明,本文介绍的GraphView系统和基于其实现图查询算法在性能上具有明显的优势。
【关键词】：关系数据库 图查询 优化算法
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP311.13
【目录】：

• 摘要3-5
• ABSTRACT5-10
• 第一章 绪论10-16
• 1.1 用关系数据库处理图数据10-11
• 1.2 针对图数据的查询语言11
• 1.3 针对图数据查询的优化技术11-12
• 1.4 国内外研究现状12-14
• 1.4.1 NoSQL数据库12-13
• 1.4.2 图数据库13
• 1.4.3 图数据的查询与优化13-14
• 1.5 本章小结14-16
• 第二章 图数据在关系数据库中的表示16-24
• 2.1 GraphView概览16-17
• 2.2 节点表的设计17-19
• 2.3 关系数据库中的图遍历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
• 第四章 用关系数据库处理图查询36-48
• 4.1 PageRank36-38
• 4.1.1 问题描述36-37
• 4.1.2 迭代的计算过程37-38
• 4.2 整体同步并行模型38-42
• 4.3 图查询中的优化42-45
• 4.4 异步计算模型45-46
• 4.5 本章小结46-48
• 第五章 实验48-56
• 5.1 实验环境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
• 攻读学位期间发表的学术论文目录64-66

【相似文献】

中国期刊全文数据库 前10条

1 赵晓英;;关系数据库中固定数据、半固定数据、变动数据的处理[J];晋中学院学报;2005年06期

2 罗幼平;;关系数据库中的多表联接查询[J];电脑知识与技术;2006年05期

3 陈莉莹;董文;;“教、学、做一体化”在“关系数据库”课程中的应用[J];学习月刊;2010年15期

4 蔡晓兵;;模糊关系数据库和关系数据库中的模糊信息[J];贵州工学院学报;1990年01期

5 陈楚s

本文编号：265431