学位论文 > 优秀研究生学位论文题录展示

大规模图数据库上的模式匹配

作　者: 解春欣
导　师: 汪卫
学　校: 复旦大学
专　业: 计算机软件与理论
关键词: 图数据库模式匹配查询优化
分类号: TP311.13
类　型: 硕士论文
年　份: 2010年
下　载: 153次
引　用: 0次
阅　读: 论文下载

内容摘要

数据管理问题几乎存在于一切人类活动领域中,如何利用计算机来管理大量的数据,几乎对于各个领域的工作者来说都是很重要的。关系型数据库已经在很多领域取得了巨大的成功,但是,已经有越来越多的复杂数据超出了传统的关系型数据库的能力范围,图就是这些复杂数据中的一种,它具有十分强大的表达能力,可以很好地表达像社会网络、XML文档、生物化学分子、蛋白质作用网络等客观世界事物的语义。因此,图数据的管理和查询吸引了越来越多的研究者的目光。图数据库上的模式匹配问题,要求给出指定查询结构在图数据库中的所有出现位置。这一问题是图数据库领域的关键问题之一,也是潜在应用最大的问题之一。一些研究者和程序开发者已经在这方面提出了很多的解决方案。但是,大部分的已有工作,要么是针对“小图”数据库的,也就是假设可以把数据库中一部分的数据图完全装载进内存里来,模式匹配算法可以完全在内存里进行。要么就是主要关注一些比较基本的查询,而对于复杂的模式查询,主要是通过关系数据库中的连接操作来实现的。本文则是主要关注和讨论如何在大规模的、基于磁盘的图数据库上高效地进行模式匹配查询。本文的主要研究成果如下：(1)提出了一种大规模图数据库的系统设计方案并对其主要部分进行了实现。(2)提出了一种全新的、在基于磁盘的大图上进行模式匹配的算法。在本文中,模式匹配问题被转化为了多个临时表的连接问题。针对“广度优先”和“深度优先”策略各自的缺陷,本文提出了一种“满前进-空后退”的连接策略,可以在不把数量庞大的中间结果写入到磁盘的情况下,完成整个模式匹配的过程。对于基于磁盘的图数据库上的模式匹配所特有的一些问题,比如,一些临时数据的访问和存储方法、cache策略等问题,本文也进行了一些深入的讨论。(3)针对所述的模式匹配算法框架,本文提出了几种优化措施。本文讨论了不同的连接顺序对于查询执行效率的影响,提出了不同连接顺序的执行代价应该用什么样的标准来衡量。针对执行代价的衡量标准,本文提出了一种有效的优化连接顺序的方法。另外,本文还讨论了算法的平行化执行以及一些需要在线下进行的优化措施。在一个真实数据集上的实验表明,本文的算法和优化策略都是很有效的。

全文目录

目录  3-5
摘要  5-6
ABSTRACT  6-8
第一章图数据库模型与模式匹配问题  8-13
  1.1 引言  8-9
  1.2 基本概念  9-11
  1.3 相关工作  11-13
第二章系统的整体结构与数据的底层存储方法  13-22
  2.1 系统的整体结构  13-14
  2.2 图的基本访问接口  14-15
    2.2.1 数据访问  14
    2.2.2 数据修改  14-15
  2.3 存储层的关系数据库实现  15-22
    2.3.1 图拓扑结构的存储  15-16
    2.3.2 属性的存储  16
    2.3.3 属性值的存储  16-17
    2.3.4 数据存储层操作的SQL实现  17-22
第三章模式匹配算法  22-40
  3.1 基于边扩展的映射寻找方法  22-26
  3.2 模式匹配与边投影表的连接  26-28
  3.3 "满前进-空后退"策略  28-34
    3.3.1 广度优先搜索vs深度优先搜索  28-30
    3.3.2 "满前进-空后退"策略  30-34
  3.4 边投影表的访问方法  34-40
    3.4.1 边投影表的集中存储和访问  34-38
    3.4.2 边投影表的分段索引和访问  38-40
第四章模式匹配算法的优化  40-51
  4.1 连接顺序的选择  40-45
    4.1.1 连接顺序与连接的效率  40-42
    4.1.2 选择一个较好的连接顺序  42-43
    4.1.3 两张边投影表连接结果大小的估算方法  43-45
  4.2 边投影的优化  45-46
  4.3 分布式处理  46-47
  4.4 一些其他的优化措施  47-51
    4.4.1 属性值表的预连接  48-49
    4.4.2 顶点id重排  49-51
第五章实验结果及分析  51-56
  5.1 实验环境和数据集  51
  5.2 实验结果和分析  51-56
第六章结论与展望  56-58
参考文献  58-60
研究生期间的主要工作  60-61
致谢  61-62

大规模图数据库上的模式匹配

内容摘要

全文目录

相似论文