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