基于Hadoop的RDF数据存储策略的理论分析论文

基于Hadoop的RDF数据存储策略的理论分析论文

　　【 摘 要 】 随着信息爆炸时代的到来和语义网的快速发展，海量RDF数据存储已成为普遍关注的问题。分布式云计算技术为海量RDF的存储和查询提供了了新的、更高效的解决方案，而基于Hadoop平台的RDF数据存储研究成为了研究焦点。本文对Hadoop在海量RDF数据存储中应用的关键问题进行分析，介绍了现有的基于Hadoop平台的RDF存储系统并将它们进行综合分析，最后对未来发展方向进行了展望。

　　【 关键词 】 语义网；RDF；存储系统；查询；Hadoop

　　【 Abstract 】 With the arrival of the era of information explosion and the rapid development of the semantic web， the storage for large-scale RDF data has become an issue of common concern. A distributed cloud computing technology， which is more efficient， provides a new solution for large-scale RDF's storage and query and the research on storing RDF data based on Hadoop platform has become the focus of research. This paper carries on the analysis to the key issues of the application of the Hadoop in the massive RDF data storage and introduces the existing RDF Storage System based on Hadoop platform and summarize them . Finally this paper proposes the future development direction.

　　【 Keywords 】 semantic web； RDF； storage system； query； hadoop

　　1 引言

　　语义网（Semantic Web）的核心思想是通过给万维网上的文档（如： HTML）添加能够被计算机所理解的语义（Meta data），促使互联网成为一个通用的信息交换媒介。资源描述框架（Resource Description Framework，RDF）是 W3C 提出的资源描述标准语言，具有一定的信息表达和交换能力，还能一定程度上描述语义信息。语义网的快速发展与应用带给RDF数据的剧增，海量RDF数据的存储、检索成为了难题。

　　传统的关系数据库面对海量RDF处理显得力不从心，而分布式云计算技术在处理海量数据方面有着得天独厚的优势，而Hadoop凭借其对分布式计算的实现以及开源性，吸引了很多研究者和研究机构进行海量RDF数据存储研究，并提出了各自的解决方案，比如上海交通大学提出的HadoopRDF，Hyunsk Choi等人提出的SPIDER，Nikolaos Papailiou等人提出的H2RDF等。本文分析了用Hadoop相关技术解决RDF数据存储时考虑的关键问题，然后对当前的存储策略进行对比分析和综述。

　　2 RDF数据存储的三个关键问题

　　（1）存储容器的选择。RDF三元组最简单的存储就是保留RDF三元组（S，P，O）的形态，直接存放在文件系统（如HDFS、RDF-3x）上，这样做的好处是不用对三元组结构做额外处理，存储速度快，缺点是检索不方便，需要建立大量索引。另一种就是用数据库HBase来存放，HBase是一种Key-value键值对的存储模式，这样存储的好处是可以有效利用MapReduce算法进行高效检索，但是缺点是存储的时候需要改变三元组的结构，而且如何拆分三元组进行存储才更有利于高效检索和重组也是一个值得探究的问题。

　　（2）数据库的选择与划分。在使用HBase表进行存储的时候，可以将三元组（S，P，O）中的一个元素（S或P或O）或者元素组合分开存储在key和value中，充分利用HBase行键RowKey的默认字典索引方便检索，不过往往要通过建立冗余表来实现对不同元素的索引来方便检索。另一种方案就是按照类和属性进行划分，将同一类或同一属性的RDF数据集中存储。但是如何建表才能使表的数目、数据冗余度、检索效率之间找到平衡有待研究。

　　（3）索引策略的设计。索引的建立是为了查询时的高效，利用HDFS上的三元组存储需要建立HDFS的一级或者多级索引，如果表的数目太多，索引文件很难维护。利用HBase进行存储可以利用HBase的RowKey索引，但是查询往往是RDF基本图或者更为复杂的查询模式，这样就涉及不同查询变量和表间连接，为了配合查询，往往需要将（S，P，O）中不同的元素和元素组合作为RowKey来建立不同索引。如何建立简单、有效索引才能将RDF基本图的`查询化繁为简还值得讨论。

　　3 RDF存储策略

　　3.1 HDFS&MapReduce策略

　　这种存储模式将海量RDF数据直接以三元组的形式保存在HDFS文件中，并且可以利用Jena等推理工具或者算法对数据进行划分，通过Hash函数分开存储在不同节点，并利用指针或者hash索引将具有相同查询特性的数据存放在磁盘上的连续区域来提高查询效率。

　　文献[12]将RDF数据按照谓语及宾语的类型划分成多个类并分别存储在HDFS中的多个小文件中，利用贪心算法生成多个MapReduce作业迭代处理SPARQL查询的连接操作，并优先处理出现次数最多的变量所在的子句。文献[13]根据主语所属类划分RDF数据并将划分后的RDF数据所在文件存储在HDFS，一个MapReduce作业处理一条Triple Pattern查询，所有Triple Pattern查询都顺序执行。文献[14]将RDF数据按照N-Triple文件的形式存储，查询时采用多个MapReduce作业查询RDF三元组数据并迭代处理SPARQL查询的连接操作，提出了贪婪选择以及多路选择两种连接选择策略。

　　3.2 HBase&MapReduce策略

　　基于HBase的RDF存储模式主要利用HBase的RowKey的默认索引并通过建立冗余表（拥有不同RowKey）来建立不同索引，方法是将需要索引的主语（S）、谓语（P）、宾语（O）（后边我们用S、P、O简称）中的一个或多个组合放在RowKey中，充分利用HBase表RowKey的默认索引，这样我们就可以用不同组合来建立不同索引表，用空间来换时间。

　　文献[15]用SP_O、P_SO、O_SP、PS_O、SO_P、PO_S六张表来存放RDF数据，其中SP_O代表以（主语，谓语）为RowKey、宾语为列名，以此类推，查询时提出一种以选择度为标准的贪心的MapReduce多路连接。文献[6]用SP_O、PO_S、OS_P三张表来存储RDF数据，查询时用Jena解析SPARQL，然后利用连接算法确定查询模式是集中式还是分布式连接，如果是分布式则用MapReduce处理，如图1所示。文献[16]用Ts、Tp、To三张表来存储RDF三元组，Ts表中S为RowKey、P|O为Value，Tp表中P为RowKey、S|O为Value，To表中O为RowKey、S|P为Value，并使用HBase API实现三个SPARQL查询算法，分别是三元组与Triple Pattern的匹配算法、Triple Patte rn的匹配算法以及SPARQL BGP的匹配算法。

　　3.3 Hadoop&自定义算法策略

　　由于RDF数据查询模式中几乎是SPARQL BGP 基本图模式查询，而MapReduce算法适用于批处理而在图匹配上并不是原生算法，而且启动MapReduce的时间对于整个查询的响应都会有影响，所以结合HBase的存储可以设计查询效率更高的算法。

　　文献[17]将RDF数据存放在Hadoop文件系统中，采用一种基于BSP的查询策略，利用图匹配算法替代了原有的MapReduce算法，算法分为匹配和迭代两个阶段，先匹配出要查询的单个三元组模式，然后通过迭代使部分解逐步逼近完全解，借此来优化查询性能。

　　3.4 自定义存储&MapReduce策略

　　这种存储模式为了避免大量索引以及对RDF三元组结构的破坏，利用第三方RDF存储系统来提高存储与检索效率，代表性的有HadoopRDF。

　　HadoopRDF采用利用一种图分区算法来划分RDF数据集，将RDF数据存储到集群中的RDF-3x数据库中，每个RDF-3x都存储了数据集中S、P、O三者及其组合的统计信息来进行查询定位。集群的每个节点上都部署了Sesame RDF管理系统实例，实例提供了查询RDF数据的接口。Sesame成熟的存储管理系统加上Hadoop集群的高可靠性和容错机制，还有MapReduce来实现并行处理SPARQL 查询，HadoopRDF借此来提供高效的RDF查询。

　　4 综合分析

　　现有的基于Hadoop相关技术的RDF存储与查询策略的研究主要集中在RDF数据模型设计和查询优化两个方面。存储系统方面除了采用Hadoop自身的文件系统HDFS以及数据库HBase存储外，还有新的文件系统和数据库被采用，而存储系统的优化主要是针对RDF数据存储系统（文件系统或者数据库系统）索引的优化，然而建立何种索引、用什么数据结构来实现索引才能既不浪费空间又能提供高效检索，仍待广大研究者深入讨论。查询优化主要是用MapReduce分布式算法进行多路连接，用选择算法来优化查询连接顺序，用图模式来开发更适合SPARQL BGP基本图模式的查询，但是还没有一种统一的高效的查询策略。

　　5 结束语

　　本文对基于Hadoop平台相关技术的RDF存储研究现状以及关键问题进行讨论，并介绍和分析了现有的基于Hadoop的存储与查询策略，未来还有很多方面值得探究，主要有：（1）寻找更适合RDF三元组的存储结构，既能最大程度上保留源数据结构，又能尽可能少地减少数据冗余，方便快速查询；（2）现有查询策略大多集中在连接优化、选择度优化、并行查询优化上，缺乏一种与存储结构无缝配合的查询策略，广大研究者可以将存储结构和查询算法深入结合，提出一个完整的海量RDF存储与查询策略。

　　参考文献

　　[1] Mary Burke， （2009），"The semantic web and the digital library"， Aslib Proceedings，Vol.61 Iss 3 pp. 316 - 322.

　　[2] Klyne G， Carroll J J，McBride B. Resource description framework （RDF）： Concepts and abstract syntax[J]. W3C recommendation， 2004， 10.

　　[3] Apache. Hadoop[EB/OL]. http：//hadoop.apache.org/.

　　[4] J.H.Du， H.F.Wang， Y.Ni， and Y.Yu. HadoopRDF： AScalable Semantic Data Analytical Endine，ICIC 2012.633-641.

　　[5] Choi H， Son J，Cho Y H， et al. SPIDER： a system for scalable， parallel/distributed evaluation of large-scale RDF data[C]. Proceedings of the 18th ACM conference on Information and knowledge management. ACM， 2009： 2087-2088.