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

摘要

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

目录

声明

第一章 绪论

1.1 研究背景和意义

1.2 国内外研究现状

1.3 本文主要贡献

1.4 本文组织结构

第二章 相关理论研究

2.1 标签图相关理论

2.2 索引构建及相关理论

2.3 RDF数据管理相关理论

2.4 本章小结

第三章 基于S-树的RDF数据索引

3.1 基本理论和方法的扩充

3.2 VS-树存在的缺陷

3.3 基于S-树的索引（ST-Index）结构

3.4 建立在ST-index基础上的查询

3.5 ST-index的维护

3.6 实验分析

3.7 本章小结

第四章 基于S-树的RDF数据索引（ST-index）改进方案

4.1 ST-index和现有的索引面临的共同问题

4.2 AST-index索引结构和图数据存储

4.3 AST-index的查询算法优化

4.4 AST-index节点的合并

4.5 实验分析

4.6 本章小结

第五章 总结与展望

5.1 本文工作总结

5.2 研究展望

致谢

参考文献

作者在学期间取得的学术成果