大规模RDF图数据的正则路径查询分析

《大规模RDF图数据的正则路径查询分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、-------第一章绪论据集bioinformatics[9]等。截至2012年9月，LinkedData已经包含了295个数据集，316亿条三元组以及5.04亿个RDF链接，我们已经进入了大数据[10]时代。如此大规模的语义数据为传统的数据存储带来了新的挑战。传统数据库以表的形式维护数据，并要求数据的强一致性，在数据查询过程中涉及大量的表之间的连接操作。这种特性，用来管理图数据，尤其是类似LinkedData中发布的大规模图数据会存在性能瓶颈。首先，当数据规模无限增大，例如，图的节点和边数目增大到一定量，则关系数据库表维护代价尤其是表之间做连接操作代价过高。其次，维护如此大规模数据的强

2、一致性会产生很多关于性能方面的问题，例如事务管理代价等。此外，表结构不易于扩展，并不适用于现今较为广泛应用的是水平扩展(scale-out)形式的集群服务器。NoSQL[37](NotOnlySQL)是不同于传统关系型数据库和数据管理系统的新一类存储库，其主要特点包括：可扩展性强，通常为分布式形态；NoSQL存储库不需要SQL作为其查询语言；数据存储不需要固定的表格式，而且尽量避免使用连接操作。此外，尽管牺牲了传统关系型数据库的强一致性，不提供ACID支持，但由此换来了集群环境高可用性和高扩展性等优势。因此，采用NoSQL来管理大规模图数据，尤其是LinkedData上发布的大规模RDF

3、图数据具有十分显著的性能优势。目前，NoSQL已经具有十分广泛的应用。例如，亚马逊的基于磁盘的键值存储库Dynamo[22]、Google的面向列的存储库Bigtable[1]等，在大规模图数据管理，尤其是具备小世界模型社交网络等类型的超大规模稀疏图数据管理方面体现出十分强大的性能优势。1.2主要内容和研究目标本课题主要的研究内容为构建一套合理的索引结构，设计一套高效的查询处理算法，通过与底层存储库交互，来支持正则表达式路径查询。课题将针对RDF图数据模型的特殊性，考虑大数据环境下RDF图数据下高效查询效率需求，以分布式路径索引和分布式路径查询算法的定义、设计和实现为主线，开展研究工作。

4、具体研究内容包括：1)分布式路径索引构建按照以空间换取时间的原则，建立RDF图数据的索引结构，用以支持高效的路径查询的设计与实现方案。研究如何结合RDF图数据结构特性设计一种或多种RDF路径索引，以期利用局部路径的索引信息快速回答全局路径查询问题。路径索引是一种图结构索引，其设计需要在查询覆盖率和存储空间开销之间寻求权衡。路径索引数据结构的精巧设计还需要以真实RDF图数据的结构特征为前4-----------第一章绪论提。通过维基百科、生物信息和社会网络等领域RDF图数据集的综合分析，归纳出RDF图的一般特征，作为设计路径索引的重要依据。2)分布式路径查询处理算法研究如何利用路径索引的支

5、持设计出一种高效率的RDF路径查询处理算法。该算法应满足Web规模RDF图数据量的要求。研究如何利用近似方法放松对查询结果的限制，在不要求查询结果全面性或准确性的前提下，进一步降低路径查询处理的计算复杂度。并利用分布式计算的性能优势对查询进行优化。本课题的研究目标为：1)以空间换时间原则，充分利用RDF图结构特性，设计高效的RDF图数据上分布式路径索引，使其空间复杂度和RDF图大小呈线性关系。2)设计高效的分布式路径查询算法，利用分布式集群的计算性能，加快查询效率，使其与单机环境路径查询方案有较显著的性能提升。1.2论文组织结构全文共分六章。第一章阐述课题背景及意义，以及主要内容和研究目

6、标。第二章介绍目前正则路径查询研究现状，主要从分布式RDF索引和图数据管理相关工作两个方面进行阐述。第三章给出分布式路径索引模型的设计与实现方案，包括索引模型的形式化定义、分布式路径索引模型的构建、路径索引基于Bigtable模型的实现和基于分布式B+树的实现方案。第四章提出了分布式路径查询解决方案的设计与实现，包括分布式路径查询语法和语义的定义、路径查询算法和基于Bigdata的路径查询算法的分布式实现。第五章给出分布式路径查询解决方案的评价，主要从数据预处理、数据装载性能和路径查询性能三个方面阐述。第六章对全文进行总结并指出目前工作的不足以及对未来工作的展望。5-----------

7、第二章相关研究综述第二章相关研究综述本章主要对分布式正则路径查询相关研究工作进行阐述，2.1节主要描述RDF索引相关研究，包括基于传统关系型数据库构建索引和基于NoSQL构建索引的相关工作。2.2节阐述图数据管理相关研究，主要包括SPARQL相关研究和正则路径查询相关研究。1.2RDF索引相关研究RDF索引的相关研究可以大致分为两个个方向：将RDF图数据模型映射到传统关系型数据库数据表中，并构建独立的RDF索引；基于NoSQL构建索