基于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.
【基于Hadoop的RDF數據存儲策略的理論分析論文】相關文章：