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