基于标签图理论的RDF数据索引构建及查询方法研究

作     者：朱元超 

作者单位：国防科学技术大学 

学位级别：硕士

导师姓名：黄宏斌

授予年度：2014年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：RDF数据 索引构建 子图匹配 

摘      要：由于具备很强的通用性,RDF语言在很多领域都获得了广泛的应用,用RDF描述的数据规模也在不断扩大。如果不设计优秀的索引方案,利用针对RDF数据的SPARQL查询语言对大规模数据进行查询的话效率将非常低下。RDF数据和SPARQL查询都具有一种图结构,所以基于图模型的RDF数据存储和查询成为一种直观、有效的方法,而查询过程则抽象为子图匹配过程。由于对大型图的子图匹配非常耗时,索引技术成为解决这个问题的关键。在现有的索引设计方案VS-tree[30]中,由于过量的匹配造成时间消耗。为解决这个问题,本文提出了一种新的查询算法,并且对索引的维护提供了方案,有效解决了这个问题。本文的主要工作体现在:(1)针对图数据原有的存储方案存储量大、遍历和查找困难的缺陷,本文提出两种存储方案,使得存储的数据量大幅减少,并且遍历和查找效率并不明显降低,在某些特殊情况下,如查询变量较多时效果更好。对原有的特征值距离度量方式和索引节点分裂方法不合理导致节点分裂操作频繁进行的情况,提出了一种新的特征值距离度量方式和索引节点分裂算法,能够有效减少节点分裂操作,降低索引构建时间。(2)对原有的查询算法重复查询次数较多的情况,设计了一种新的查询算法,能够消耗更少内存,减少查询次数,提高查询效率,并对这种现象的原因进行了剖析。对与原有的RDF索引维护技术没有提出节点合并的概念,过量的数据删除将破坏索引结构的问题,设计了一种节点合并方式,能够维持索引结构的平衡性,减少冗余的索引节点。