欢迎访问一起赢论文辅导网
机械论文
当前位置:首页 > 机械论文
基于矩阵分解的大规模RDF数据存储与查询系统
来源:一起赢论文网     日期:2017-06-26     浏览数:3178     【 字体:

 40卷 计算机学报 Vol.402017论文在线出版号No.60 CHINESEJOURNALOFCOMPUTERS OnlinePublishingNo.60———————————————本课题得到国家自然科学基金专项基金项目“面向大数据的媒体内容分析与关联语义挖掘研究”(项目号:61223003),国家自然科学基金“基于大众参与的语义Web实体链接方法研究”(项目号:61370019)和江苏省科技支撑计划项目“大数据分析计算统一编程框架与软件平台”(项目号BE2014131)的资助. 顾荣,男,1988年生,在读博士,中国计算机学会(CCF)学生会员(E200032327G)主要研究领域为大数据并行处理和云计算技术等,E-mail: gurongwalker@gmail.com. 仇红剑,男,1990年生,硕士研究生,主要研究领域为大数据并行处理与云计算技术,E-mail:qiuhongjian_nju@hotmail.com. 杨文家,男,1991年生,硕士研究生,主要研究领域为大数据并行处理与云计算技术,E-mail: yangwen_jia@163.com.胡伟,男,1982年出生,副教授,中国计算机学会(CCF)会员(会员号31410M),主要研究领域为语义网、本体、数据集成,E-mail:whu@nju.edu.cn.袁春风,女,1963年生,教授,计算机学会(CCF)会员,主要研究领域为体系结构与并行计算,多媒体文档处理、Web信息检索与挖掘等,Email:cfyuan@nju.edu.cn.黄宜华(通信作者),男,1962年生,教授,计算机学会(CCF)会员(14302S),主要研究领域为大数据并行处理与云计算技术、体系结构与并行计算,E-mail:yhuang@nju.edu.cn.Goldfish:基于矩阵分解的大规模RDF数据存储与查询系统顾荣,仇红剑,杨文家,胡伟,袁春风,黄宜华(南京大学计算机软件新技术国家重点实验室,南京210093)(江苏省软件新技术与产业化协同创新中心,南京210093)摘要 随着互联网应用的迅猛发展和语义网技术研究的深入开展,语义数据呈现出爆炸性增长的趋势。一方面,对于语义数据实现高效存储和查询是语义网应用的重要基础,越来越多的语义应用可以依赖于此以提供更好的服务;另一方面,语义数据的爆炸性增长,对大数据环境下的语义数据的存储与查询技术提出了新的挑战。传统的基于关系型数据库的语义数据与查询系统已难以满足大规模语义数据的存储与查询需求。本文针对大规模RDF数据的存储与查询问题,以OpenRDFSesame框架为基础,采用分布式分层式存储架构,提出并实现了属性表存储结构来进行语义数据的存储。在此基础上,针对布尔矩阵分解算法在对大规模语义数据构造属性表较慢的问题,基于Spark分布式计算框架提出并实现了并行化频繁项集挖掘算法求解大规模矩阵分解,以加速属性表的构造过程。并且,在查询层增加了基于哈希转换等查询优化。最后,基于本文所提出的索引结构和优化方法设计实现了原型系统Goldfish,并在大规模合成和真实数据集上进行了实验对比。结果表明,Goldfish原型系统比Rainbow系统查询性能平均提升约6倍,比Jena-HBase查询性能平均提升约500倍,比基于MapReduceRDF查询系统SHARD性能平均提升约1200倍。关键词 大规模RDF存储;矩阵分解;分层式存储;大数据;语义网中图法分类号TP311论文引用格式:顾荣,仇红剑,杨文家,胡伟,袁春风,黄宜华,Goldfish:基于矩阵分解的大规模RDF数据存储与查询系统,2017,Vol.40,在线出版号No.60GuRongQiuJian-Hong,YangJia-Wen,Hu,Wei,YuanChun-Feng,HuangYi-Hua,Goldfish:ALargeScaleSemanticDataStoreandQuerySystemBasedonBooleanMatrixFactorization,2017,Vol.40,OnlinePublishingNo.60Goldfish:ALargeScaleSemanticDataStoreandQuerySystemBasedonBooleanMatrixFactorizationRongGu,HongjianQiu,WenjiaYang,WeiHu,ChunfengYuan,YihuaHuang(NationalKeyLaboratoryforNovelSoftwareTechnology,NanjingUniversity,Nanjing210093)(CollaborativeInnovationCenterofNovelSoftwareTechnologyandIndustrialization,Nanjing210093)网络出版时间:2017-05-19 12:00:20网络出版地址:http://kns.cnki.net/kcms/detail/11.1826.TP.20170519.1200.004.html2 计算机学报 2017Abstract WiththerapiddevelopmentoftheInternetapplicationsandthesemanticwebtechnology, theamountofthesemanticdataisexploding. Ononehand, it issignificant tostoreandquerysemanticdataefficiently, asmanyapplicationscanprovidebetterservicesbasedonthis.Ontheotherhand,therapidincreaseofthesemanticdatabringsnewchallengesonefficient storingandqueryingsemanticdatainbigdataera. Thetraditionalwaysforsemanticdatamanagement istostoreandquerythedatainrelationaldatabasemanagement systems. Asthedataincreases, thetraditional wayscanhardlyhandlebigdata. Toaddressthisproblem, thispaperproposedadistributedhierarchical storagearchitecturetostoreandquerylarge-scalesemanticdatabasedontheOpenRDFSesameframework.TheRDFstoragemechanismisoptimizedbyadoptingtheattributetabletoreplacetheRDFtriple store. Considering the big semantic data, a parallel frequent itemset mining algorithmwith Sparkframeworkis proposedtogenerate the indexof the attribute table. Moreover, a layer of optimizedhashconversionisproposedtoavoidwastingtimeinfrequent hashtablesearchduringquerystage. Toevaluatetheefficiencyoftheproposedapproachinthispaper,weimplementaprototypesystemcalledGoldfish,andconductacomparisonuselarge-scalesyntheticdatasetandrealdataset. Experiment resultsshowthatGoldfishisaround8timesfasterthanRainbow,500timesfasterthanJena-HBaseand1200timesfasterthantheMapReducebasedRDFqueryingsystemSHARD.Keywords largescaleRDFstore;matrixfactorization;hierarchicalstorage;bigdata;semanticweb1引言据20087Google给出的数据显示,Web上存在1TB不同的URIIDC统计显示全球数据总量2011年已有1.8ZB,并预测到2020年全球数据总量将超过35ZB,总体增长近20[1]。这些Web网页承载着大规模的数据,网页之间也存在着各种超链接。Berners-Lee1998年提出了语义网[2]的概念,其目的为了使计算机可以从语义的角度迅速准确理解和处理大规模网页。通过对Web增加语义支持,使机器能够根据语义进行判断,实现高效的数据共享和人机智能协同。语义数据通常采用RDF1(ResourceDescriptionFramework)来表达,在形式上是一种高度稀疏的图数据。语义数据的爆炸性增长对语义数据的存储与查询技术进一步提出了新的挑战。截至20123月,LODLinkedOpenData)项目2所收集的RDF数据集已经超过325亿条RDF三元组。传统的基于关系型数据库的语义数据在处理语义数据的数据量和存储扩展性上存在的一定的缺陷,难以满足迅猛增长的数据带来的需求。与此同时,大数据技术在全球的学术界和工业界领域迅猛发展,为实现大规模语义数据高效存储与查询提供了技术支持。目前出现了很多典型的分布式数据库和大数据处1. http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/2. http://linkeddata.org/理平台,例如广为使用的分布式的、面向列的非关系型数据库HBase。此外,Redis是一种基于内存的、可进行数据持久化的高性能key-value存储数据库。本文设计实现了一套大规模RDF数据存储和查询系统,在存储层采用层次化结构,以HBase作为持久存储层存储全局RDF数据,分布式Redis存储经常被查询的热数据。本文的主要贡献可以归纳为以下三个方面:1)针对RDF数据三元组表存储所表现出的查询效率和存储空间利用率低、可扩展性不佳等问题,本文设计了大规模属性表存储语义数据,强关联的属性会存储到一张表中,从而减少查询过程中的join操作。进一步地,针对大规模数据集下构建属性表采用的ASSO算法存在求解速度较慢等问题,本文设计了基于Spark分布式框架的并行化频繁项集挖掘算法对其进行求解,以加速在大规模数据集下属性表的构造。2)提出以HBase作为持久化存储层,Redis作为分布式内存层的层次化语义数据存储架构,并进一步采用了基于哈希转换的查询优化。本文采用分层式存储架构对语义数据进行分层存储,查询效率进一步提升。并针对分层式RDF数据存储与查询系统在查询过程中出现的频繁查找哈希表的现象,提出增加哈希转换层。通过增加哈希转化层,仅在SPARQL查询的始末进行哈希转换,避免了频繁查找哈希表的开销。3)基于以上优化方案的基础上,进一步设计论文在线出版号No.60顾荣等:Goldfish:基于矩阵分解的大规模RDF数据存储与查询系统 3并实现了大规模RDF数据存储与查询原型系统Goldfish,并进行了相关的实验对比和可扩展性分析。与现有系统相比,Goldfish的优势体现在以下两点:1) 存储空间的高利用率和弹性高效的存储扩展性。基于属性表存储结构优化,可以极大地提高存储空间的利用率,同时系统的存储容量可以随着集群节点的增加而呈现出近线性扩展。2) 高效的查询速度。采用基于属性表的分层式存储架构对语义数据进行存储、哈希转换的查询优化等措施提升查询的性能。本文按照如下方式组织:第一部分简介本文相关的研究背景和现状,并阐明本文的主要内容;第二部分介绍相关的背景知识;第三部分简要阐述了系统的整体框架;第四部分重点阐述基于属性表的大规模RDF数据存储优化。第五部分主要介绍基于哈希转换的查询优化。第六部分介绍了原型系统。第七部分对本文提出的Goldfish系统性能进行了实验分析。第八部分讨论了相关工作。最后,在第九部分我们对本篇论文的进行了总结,并指出下一步需要展开的工作。2背景知识2.1资源描述框架RDF和查询语言SPARQLRDFW3C提出的一种表达WWW资源信息的标准。一个RDF陈述(Statement)包括资源(主体)、属性(谓词)和属性值(客体)。主体通常是指具体资源的URI引用(URIReference),谓词指与资源描述有关的特征或关系,客体是指属性的值。这种三元组表达了信息资源间的对应关系。具体地,三元组的主体和客体间存在谓词表达的关系。Web上的元数据进行可以通过RDF的标准进行语义编码、传递和重用。如图1所示,一个RDF模型结构由一组RDF三元组组成。其为一个有向标记图,其中主体或客体用节点表示,节点的内容可以为URI引用、字面量等,有向边从主体指向客体,为谓词的URI引用标记。RDF数据是本文第三节提出的系统底层存储的数据,其中第4节中RDF数据作为原数据来构建属性表,另外RDF数据也是7.3节中对比系统底层存储的数据。图1RDF模型结构在2004年,RDF数据访问工作组提出了针对RDF数据进行查询的语言SPARQLSPARQL查询语句通常包括查询子句和WHERE子句。SPARQL查询子句与SQL中的查询子句SELECT子句类似,用于指定出现在查询结果集的变量;而WHERE子句则通过基本图模式来同RDF数据匹配。SPARQL语法支持四种类型的语义查询,分别为SELECTCONSTRUCTDESCRIBEASK。经过几年的发展,SPARQL已经成为W3C的推荐标准。SPARQL语言与关系数据库中的SQL语言类似,这方便了用户对于SPARQL语言的使用。本文第三节提出的系统在查询层采用的OpenRDFSesame框架中使用SPARQL作为RDF查询语言,7.3节中的对比系统也使用SPARQL作为RDF查询语言。2.2分布式系统Spark介绍ApacheSpark是由UCBerkeleyAMP实验室于2009年发布的分布式内存计算框架,它是BerkeleyDataAnalysisStackBDAS)中的核心项目。RDD[3]ResilientDistributedDataset)是Spark[4]中的核心数据结构。它本质上是一种可以基于内存的弹性分布式数据集,允许用户将数据加载至内存后重复地使用,这样的设计适合计算密集型的机器学习算法和交互式查询算法。基于内存计算特点,与HadoopMapReduce相比,Spark在迭代计算和交互式应用上的性能快10-100倍。SparkHadoop类似,采用主从式结构,由MasterWorker两部分组成。Driver程序是执行应用逻辑的入口点,Driver启动后会连接SparkMaster节点,将对RDD的转换(transformation)和操作发送到各个Worker节点。Worker是运行在工作节点上的守护进程Executor,存储着数据分块,并享有集群内存,当RDD操作指令发送到各个节点上的Executor时,这些Executor对对应的数据分片进行本地化操作生成新的数据分片,并将生成的RDD返回或写入存储系统,具体见图2所示。数据的划分传输以及执行过程中的容错都不需要应用程序员关心。本文4.2节使用分布式内存计算框架Spark来并行化求解大规模属性表的构造问题。4 计算机学报 2017年图2Spark作业执行过程2.3属性表构建方法有研究者[5]根据Pauli提出的布尔矩阵分解ASSO算法[6],在单机关系型数据库中以串行化的方式构造属性表。其构造属性表的流程是首先将RDF语义数据表示成布尔矩阵的形式,然后通过布尔矩阵分解算法ASSO进行矩阵分解,并且引入最短描述距离MDL[7]MinimumDescriptionLength)来评估矩阵分解的结果, 最后通过分解后的子矩阵得出语义数据之间的相似度来构造属性表。通过布尔矩阵分解ASSO算法分析数据矩阵列与列之间的相关性是一种精度上有效的手段,其实质是借鉴关联挖掘的思想,将强关联的属性放到同一张表中,弱相关的属性放到不同的表中,因此也可以通过频繁项集挖掘算法来得到RDF数据属性间的分布来构建属性表。用1 2{, ,..., }mI i i i = 表示RDF数据中所有属性的集合,T=(tid,X)表示一个事务,其中tid表示RDF的主体,X表示该主体在RDF数据集中出现的属性集合,XI的子集,用D表示包含很多事务的一个集合。属性子集Y的支持度计数为D中包含Y的事务个数,定义为式(1):sup(Y)=|{tid|Y X,(tid,X) D}| Í Í (1)相应地,属性子集Y的支持度则为sup(Y)/N,其中ND中的事务个数。若属性子集Y中属性间是强关联的则其支持度必须大于事先设定的最小支持度阈值。存在这样一个事实:如果一个属性集合是强关联的,则其所有非空子集也是强关联的。基于该事实,首先在D中找出所有支持度大于设定的最小支持度阈值的频繁1-项集,之后基于频繁(k-1)-项集来生成频繁k-项集,其中k-项集表示为含有k个属性的集合。上述频繁项集挖掘算法中,所有RDF数据按照主体划分,每行表示一个事务T。若属性A和属性B是强关联的,则对应每一个事务T,若属性A出现,则属性B也极有可能出现。这里频繁项集挖掘算法的目标是找出属性间的关联,将强关联的属性放到同一张属性表中,属性AB之间的关联度则通过s来衡量,其中s定义为式(2):[ ] { } |                ,  1, |/ i i A Bi N N s= Î 若第行包含和 (2)其中,N表示总共的RDF数据行数,s介于01之间。若s大于实现设定的最小支持度阈值,则可以认为属性AB是强关联的。由此可见,频繁项集挖掘算法可以用来构建属性表。3系统框架本文提出的分布式分层RDF数据查询系统Goldfish的系统总体结构如图3所示。系统主要分为查询层与存储层两个部分。查询层基于OpenRDFSesame框架,主要包括查询解析器(QueryParser)、查询优化器(QueryOptimizer)和查询执行器(QueryEvaluator),其主要功能是对查询语句进行解析和优化,并将其转化为对应的查询模型(QueryModel)。存储架构以HBase为持久化存储层,Redis为分布式内存层构成分布式层次化存储。持久存储层使用HBase存储大规模语义数据,提供持久存储服务。HBase能够保证数据存储的可靠性,当存储的语义数据规模增大或者动态增加节点时,HBase能自动完成负载均衡操作。分布式内存层使用Redis存储常用的SP**PO查询模式,保证查询的高效性。这样通过持久化存储层来存储属性表做容错,分布式内存层存放热数据,使得更多的查询发生在分布式内存层,而不是持久化存储层。同时由于采用属性表存储结构,将强关联的属性放在一张表中,使得一般不会进行连接操作。如图3所示,一个SPARQL查询首先会传入查询解析器进行查询语句的解析。经过查询解析器之后,查询语句被构造成查询解析树。接下来,查询优化器会对得到的查询解析树进行优化,调整查询语句之间的连接顺序,构造查询优化树。然后,查询执行器会对查询优化树进行对应的查询。查询执行器会在底层的数据存储层进行查找,并将查询的对应结果进行输出。论文在线出版号No.60顾荣等:Goldfish:基于矩阵分解的大规模RDF数据存储与查询系统 54基于属性表的RDF数据存储优化4.1基于布尔矩阵分解的RDF数据存储布局属性表的目标是减少查询过程中涉及到的自连接操作、提高存储空间的利用效率以及提升系统的可扩展性。基于RDF数据稀疏图的特性,本文采用了一种基于布尔矩阵分解的RDF数据存储布局。通过下面的简单例子来阐述如何通过布尔矩阵分解ASSO算法在RDF数据中构造属性表的过程。下面是一系列的RDF数据,每一行代表一条RDF数据,以主语-属性-宾语的顺序排列。图3Goldfish系统的总体架构(查询层基于Sesame框架,存储层基于分层式存储架构)author1rdf:hasNameAliceauthor1rdf:hasPubpub1pub1rdf:hasTypeJournalpub1rdf:year2004author2rdf:hasNameBobauthor2rdf:hasPubpub2pub2rdf:hasTypeArticlepub2rdf:hasTitleWhySPARQL?pub2rdf:year2004author3rdf:hasPubpub3pub3rdf:hasTypeJournalpub3rdf:year2008author3rdf:hasNameCindy1)根据RDF数据构建成布尔矩阵将上面例子中的RDF数据按照矩阵表的方式构建布尔矩阵,即以RDF数据中全部的主体作为行,以RDF数据中全部的属性作为列,行列的交叉单元表示对应三元组的RDF数据是否存在,1表示数据集中存在以该主语和属性组合的三元组,反之,0表示不存在。比如,author1存在hasName的属性,故author1hasName行列交叉处的值在布尔矩阵中为1。上述RDF数据集对应如下的数据矩阵(此处将该矩阵记为C)。1 1 1 0 0 02 1 1 0 0 03 1 1 0 0 01 0 0 1 1 02 0 0 1 1 13 0 0 1 1 0hasName hasPub hasType hasYear hasTitleauthorauthorauthorpubpubpubé ùê úê úê úê úê úê úê úë û可以看到上面的布尔矩阵包含着很多的列,同时矩阵非常稀疏,这也就是RDF数据稀疏性与多样性的体现。为了能够有效地对RDF数据进行存储与查询,必须将矩阵C进行规则化,即:减少列名集合的大小和减少矩阵的稀疏性;否则,会浪费大量的存储空间,同时降低查询处理的效率。(2)布尔矩阵分解对由上面例子中构造的布尔矩阵C利用ASSO算法进行布尔矩阵分解。利用布尔矩阵分解后,原RDF数据布尔矩阵将分解成以下的两个子矩阵SB,见式(3:C S B = ´ (3)因此,示例中的布尔矩阵可以按照频繁项集挖掘的方式求得属性列之间的关系,将强关联的属性列放在一张表中,弱相关的属性放在不同的表中。其中,矩阵C经过分解之后,会得到两个子矩阵S和子矩阵B6 计算机学报 20171 0 01 0 01 0 00 1 00 1 10 1 0Sé ùê úê úê ú=ê úê úê úê úë û,1 1 0 0 00 0 1 1 00 0 0 0 1Bé ùê ú=ê úê úë û通过布尔矩阵分解ASSO算法,可以得到如上面矩阵S和矩阵B的两个子矩阵。根据矩阵B构造属性表,矩阵B每一行代表一个属性表,每行为1的列集合即是一个属性表中要存储的属性列名集合,可以放在同一张属性表中,如下所示。矩阵的行数代表了属性表的个数,构造得到的属性表可以在非关系型数据库中作为一个独立的表存储。1 1 1 0 0 02 0 0 1 1 03 0 0 0 0 1hasName hasPub hasType hasYear hasTitleTableTableTableé ùê úê úê úë û(3)基于属性表存储结构存储RDF数据通过对RDF数据以属性表的方式进行存储,将属性强关联的RDF数据放在同一张表中,属性弱相关的属性放在不同的表中,既可以兼顾查询效率,又减少了RDF数据冗余的存储。因此,通过矩阵分解ASSO算法后得到的属性表如表1所示。最后对RDF数据,按照上面步骤构造的属性表,将数据插入到对应属性的属性表中。表1ASSO算法构造的属性表(a) 子表1Subject hasName hasPubauthor1 Alice pub1author2 Bob pub2author3 Cindy pub3(b) 子表2Subject hasType hasYearpub1 Journal 2004pub2 Article 2004pub3 Journal 2008(c)剩余表Subject hasTitlepub2 WhySPARQL?4.2基于YAFIM算法的属性间关联规则生成由2.3节和4.1节中的例子可知,布尔矩阵分解构造属性表的实质是将强关联的属性放到一张表中,弱相关的属性放到不同的表中,该算法在单机上面对大规模RDF数据构造属性表的串行处理方式比较低效,可以使用易于并行化的频繁项集挖掘算法对其进行大规模求解。本节采用基于Spark分布式计算框架的并行化频繁项集挖掘算法YAFIM[8],以加速构造大规模RDF数据属性表。在YAFIM中关联度阈值s设定为与具体实验数据集相关的经验值。实验中,若s值设定过高则会存在很多属性是弱相关的,造成属性表的数量增多;若s值设定过低,就会造成每个属性间都是强关联的。本文中我们采用的是调试得出的0.6~0.8的经验值,频繁项集挖掘算法的并行化求解速度很快。另外,由于我们引入了剩余表来存储与其他RDF数据的属性关联性较弱的语义数据,因此无论s值得设定,总可以保证整个系统的正确性。本节依然沿用4.1节中用到的例子,利用Spark框架并行化来处理,包括RDF数据格式转换、利用YAFIM构造属性表结构并在基础上存储RDF数据。(1RDF数据格式转换利用分布式内存计算框架Spark来并行化处理RDF数据格式转换,整个过程如图4所示,其中每个圆角矩形表示RDD的一个分区。首先Spark从分布式文件系统HDFSRDF数据加载至RDD,利用RDD算子,将所有的RDF数据按照主体重新划分:RDD中的每条记录中第一列为不同的主体,第二列为对应主体在RDF数据集中出现的属性,把同一主体的属性放在同一条RDD记录中。上面的RDF数据经过处理之后RDD中每条记录的格式就变为如表2所示的形式。图4RDF数据格式转换过程表2RDF数据格式转换表Subject Property论文在线出版号No.60顾荣等:Goldfish:基于矩阵分解的大规模RDF数据存储与查询系统 7author1 rdf:hasNamerdf:hasPubauthor2 rdf:hasNamerdf:hasPubauthor3 rdf:hasNamerdf:hasPubpub1 rdf:hasTyperdf:yearpub2 rdf:hasTyperdf:hasTitlerdf:yearpub3 rdf:hasTyperdf:year接下来,对上面格式的语义数据进行数值化处理。假定用数值1-5分别代表hasNamehasPubhasTypehasYearhasTitle这五个属性,上面格式的RDF数据就会以数值形式表示为以下内容。其中行号1-6分别表示不同的主体author1pub3。如表3所示,数值化表即事务数据集,每行表示一个事务,每个事务第一列为主体的编码,第二列为该主体在RDF数据集中出现的属性编码。表3数值化表Subject Property1 122 123 124 345 3456 342)利用频繁项集挖掘算法构造属性表结构基于Spark框架,本文实现了并行频繁项集挖掘算法,并且利用该算法处理大规模RDF数据,得到RDF数据在属性表中的分布。图5并行化频繁项集挖掘算法构造属性表流程示例图5YAFIM并行化流程示例,首先Spark从分布式文件系统HDFS读入上一步生成的RDF数据数值化表,利用RDD算子1操作生成频繁1-项集,然后主节点将频繁1-项集取回本地,生成候选2-项集并将其广播到每个从节点,接下来经过一系列RDD算子操作生成频繁2-项集,如此反复利用上一步生成的频繁项集便可求得最大频繁项集。YAFIM算法主要包括两个阶段:生成频繁1-项集,利用频繁k-项集迭代生成频繁(k+1)-项集。1)第一个阶段:从分布式文件系统HDFS上获取RDF数据的数值化表,加载到分布式内存RDD中。图6YAFIM算法第一阶段的Lineage图如图6所示,原始事务数据集由操作flatMap操作(由workers执行)去读取事务数据集(RDF数据的数值化表),并且将所有的事务数据转化为SparkRDD。接下来每一个事务(transactions)中1. http://spark.apache.org/docs/latest/programming-guide.html#rdd-operations8 计算机学报 2017年执行flatMap操作,从中得到所有的items项集。执行完flapMap操作后,执行map操作,将所有项集items转化为<Item, 1>key/value形式。最后,reduceByKey函数统计每个项集items的支持度,并对支持度小于最小支持度s的项集进行剪枝。所有超过最小支持度s的项集将会生成频繁1-项集。2)第二阶段:不断迭代以使用k-频繁项集生成(k+1)-频繁项集。如图7所示,首先,读取k-频繁项集kL并且以<itemset,count>的形式将其存储为SparkRDD。然后从k-频繁项集中得到候选(k+1-项集1 kC+。为了加速从候选项集中查找(k+1)-频繁项集的过程,将候选(k+1-项集1 kC+存放在哈希树中。接下来,通过flatMap操作从原始事务库RDD中去获得每个候选项集的支持度。进一步,对每个频繁项集使用map函数来输出<itemset,1>key/value对的形式。最后,通过reduceByKey操作来收集所有的候选项集的支持度,并且对支持度大于最小阈值s的频繁项集以<itemset,count>key/value对的形式进行输出作为(k+1)-频繁项集。图7YAFIM算法第二阶段的Lineage图在上面的例子中,通过YAFIM算法,可以发现属性hasNamehasPub具有相关性,其关联度大于给定的最小支持度阈值,并且属性hasTypehasTitle具有相关性。因此,将属性hasNamehasPub放在一张属性表中;将属性hasTypehasYear放在一张属性表中;剩下的属性hasTitle与其他属性的关联度小于给定的最小阈值,将其单独放在剩余表(left-overtable)中。表4为示例的属性表结构。表4示例属性表结构(a) 子表1Subject hasName hasPub(b) 子表2Subject hasType hasYear(c) 剩余表Subject hasTitle3)利用属性表存储结构进行RDF数据存储通过上一步骤在RDF数据中生成的属性表分布,在存储层创建对应的属性表,并将RDF数据转换存储到对应的属性表中。在上面的例子中,插入RDF数据后的属性表如表5所示。表5YAFIM构造的属性表(a) 子表1Subject hasName hasPubauthor1 Alice pub1author2 Bob pub2author3 Cindy pub3(b) 子表2Subject hasType hasYearpub1 Journal 2004pub2 Article 2004pub3 Journal 2008(c)剩余表Subject hasTitlepub2 WhySPARQL?通过以上过程,在分层式RDF数据查询系统中利用属性表存储结构存储RDF数据。在利用属性表存储结构实现分层式RDF数据查询系统存储层的过程中,这里通过剩余表(left-overtable)存储与其他RDF数据的属性关联性较弱的语义数据。所以,当新的RDF数据插入到分层式RDF数据存储查询系统时,如果新插入的RDF数据具有新的属性值,会直接存放到剩余表中;否则,便插入到对应的属性表中。并且,随着新RDF数据的插入,会定期更新属性表。论文在线出版号No.60顾荣等:Goldfish:基于矩阵分解的大规模RDF数据存储与查询系统 95基于哈希转换的查询优化SPARQL查询引擎是RDF数据查询系统的重要组成部分,如图8所示,SPARQL查询引擎主要包括查询解析器、查询优化器和查询执行器三个部分。当SPARQL查询引擎获取用户提交的查询请求后,首先查询解析器会对查询语句执行语法和语义解析操作,并生成查询模型,提交给查询优化器。然后查询优化器根据输入的查询模型,其会在编译过程中生成许多查询结果等价的方案模型,并计算每个模型具体的查询代价,选取性能最优的查询模型提交给查询执行器。最后查询执行器根据优化后的查询模型,生成查询策略并执行查询操作。图8SPARQL查询引擎主要模块本节首先对查询过程中的时间消耗进行详细地测试与分析,以定位需要重点优化的模块。图9展示了具有代表性的LUBM-1语义数据集的14条测试查询语句的执行过程中各个阶段的时间占比。如图9所示,横轴代表不同的测试查询语句,纵轴代表每条查询语句在查询解析器、查询优化器和查询执行器上的时间消耗比例,其中“查询解析器”、“查询优化器”和“查询执行器”代表查询层的三个部分。图9LUBM-1规模的查询时间耗时过程分析从图9可以看出在查询执行器的时间消耗比例平均是最高的,查询执行器则是根据优化后的查询模型,在数据库中执行查询策略。进一步分析可知,查询执行器的时间开销可以分为两个部分:查询存储层数据的时间和查找哈希表的时间。如图10所示为Query1中查询执行器的时间分析,坐标横轴代表查询返回的RDF结果集的规模,坐标纵轴代表查询执行时间。“查找数据库”代表查询执行器在存储层数据库查找结果消耗的时间,“查找哈希表”代表将RDF数据和其对应的哈希值转换的时间开销。从图10可以发现,随着RDF查询结果集规模的增长,在底层数据库查找的时间增加平缓,但是进行哈希转换的时间近线性增长。这表明了查询执行器的时间主要消耗在频繁查找哈希表的操作上。由于SPARQL查询引擎只能识别RDF数据,而在系统存储层存储的是RDF数据的哈希值,存储层与查询层的异构性导致Goldfish系统在查询过程中需要频繁查询哈希表。因此,查询返回的RDF数据结果集的数量越大,查询所消耗的时间越多,查询执行器中查找哈希表在RDF数据查找的总时间中所占的权重越大。因此,下面的工作主要集中在如何减小查询执行器中的查找哈希表开销。图10查询执行器查询过程分析针对频繁查找哈希表所带来的开销,本节提出在查询执行层增加哈希转换部分的方案,将SPARQL查询在查询执行层直接转换成哈希值在存储层的数据库中进行查找。基于此,优化的具体的思路是:当查询语句经过查询解析器和查询优化器之后,在向底层存储的RDF数据查询结果之前,增加一层查询转换层,查询执行器直接以哈希值的形式在底层的RDF数据中进行查找,在最后返回查询结果时,只需对返回查询的结果查找哈希表即可,这样就避免了查询时频繁查找哈希表带来的开销。通过在底层采用属性表存储结构,在查询层增加哈希转换优化后,可以良好地支持单表范围查询、包含Union操作的查询以及多个表的join查询10 计算机学报 2017年等。图11表示了优化后的查询层。通过在查询引擎层增加哈希语义转换,使得查询语句在查询引擎层就转换为哈希值进行RDF数据的查找,减少了哈希语义转换的开销。本文性能评估部分的第7.2.3节也验证了查询层哈希转换优化后效果。图11增加哈希转换的查询层6原型系统实现本章我们简要介绍Goldfish原型系统的实现。本系统查询层基于OpenRDFSesame框架,RDF管理模块和RDF输入输出模块沿用了Sesame框架提供的处理方式。RDF查询模块、SAIL层等模块则重新设计,并确保重新设计后的模块符合Sesame框架制定的接口规范。系统的体系结构如图12所示。图12SAIL模块针对基于属性表存储结构的存储层需要重新设计,Repository模块根据基于查询层哈希转换的优化重新设计。其余的模块则依然沿用分层式RDF数据查询系统的模块。图12原型系统内部模块图为了使Goldfish系统的用户体验更好,便于用户交互,原型系统采用前端+后台处理的方式。前端采用Tomcat服务器Web服务,后台采用优化后的分布式分层RDF数据查询系统,并采用基于HBase+Redis+Sesame的环境开发和部署,通过Sesame框架提供的统一接口。图13服务交互请求处理图图13给出了Goldfish系统的前端设计框架。系统的前端采用JSP页面来展示查询界面和搜索结果,Web服务部署在Tomcat之上。如图13所示,JSP页面通过查询接口调用后台优化后的分层式RDF数据存储查询系统,并获得查询结果,最后返回给用户页面。7实验结果与分析7.1实验数据及平台实验数据集选用了人工合成数据集和真实数据集。其中人工合成数据集采用的是当前公认的面向大规模语义数据应用环境的知识库系统测试基准LUBMLehighUniversityBenchmark[9]大学语义数据;真实语义数据集采用的是WordNet3.1[10]DBLPComputer Science Bibliography(DataBasesystemsandLogicProgramming)LUBM测试Benchmark提供了14条不同的查询语句2,分别代表了不同的查询情况(如单个表的查询、包含Union操作的查询、多个表的join查询等),我们在1. http://dblp.uni-trier.de/2. http://swat.cse.lehigh.edu/projects/lubm/queries-sparql.txt论文在线出版号No.60顾荣等:Goldfish:基于矩阵分解的大规模RDF数据存储与查询系统 11WordNetDBLP上生成了10条不同的查询语句,同样覆盖了所有常见的查询类型。实验平台环境中每个节点的配置了24GB的内存,82.4GHzIntelQuadXen处理器,这些节点通过一个1Gbps带宽的网络连接。软件方面安装好了RedHatEnterpriseLinuxServer6.0的操作系统以及Hadoop1.0.3Spark1.4.0。本文利用拟合工具在实验中生成了4组不同规模的LUBM测试数据集:LUBM-1LUBM-10LUBM-100LUBM-1000,分别包括130,0001,300,00013,300,000133,000,000条三元组,以测试在不同规模的语义数据下RDF数据查询系统的性能。DBLP是德国特里尔大学开发的一个计算机类英文文献集成数据库系统,其以作者为核心并按照年代列出作者的科研成果。DBLP中数据按照语义来组织,本文采用的DBLP数据集共含有42million条三元组。WordNet是普林斯顿大学研究人员设计开发的基于语义组织的大型英文词汇数据库,本文采用的WordNet3.1共含有8.9million条三元组。7.2优化性能分析7.2.1 属性表构建本节在实验环境所述的12个节点的集群上分别对4组数据(LUBM-1LUBM-10LUBM-100LUBM-1000)来构建基于属性表的RDF数据存储,以评估该方法的速度、扩展性、总体存储空间消耗等性能指标。属性表构造时间的实验结果见图14,其中坐标横轴代表四个数据集,坐标纵轴为构建属性表消耗的总时间。这里的构建属性表消耗的总时间包括前期的预处理(格式转换、编码等)、利用并行化频繁项目集挖掘生成属性表结构以及原始表转成属性表存储三部分构成。图14数据规模变化时构建属性表的总时间图14中,可以看到在不同规模的数据下,构建属性表的总耗时增加的倍数与数据规模增加的倍数基本成正比,例如LUBM-1000相对于LUBM-100数据规模增加的倍数为10LUBM-1000相对于LUBM-100构建属性表所耗总时间增加的倍数为8.38。存储空间消耗方面,我们对比评估了RDF语义数据的存储结构有四种主流形式:三元组存储结构、垂直划分存储结构、水平存储结构和本文采用的属性表存储结构。在表6中我们具体分析了这四种存储划分方案在不同规模数据集上的存储开销(整体数据都是持久化存储在底层基于磁盘的HBase),可以看出采用本文的属性表存储结构的总体数据开销相当于原始数据的3倍左右。这是由于属性表的结构避免了很多稀疏化导致的额外开销。因此,本文采用的属性表的索引结构的空间开销较低,可以很容易地将热点数据存储到分布式内存中,并将整体数据持久化存储在底层基于磁盘的HBase上。表6四种存储划分方案的存储空间占用对比比例数据集 原数据集 属性表 三元组 垂直划分 水平划分LUBM-1 8 15.2 31 21 32LUBM-10 102 374.85 696 416 612LUBM-100 1,126.4 3,686.4 6993 4506 6634LUBM-1000 11,264 35,053.5 63612 45082 51878另外,对于流式插入的数据,相同数据分布规律的数据集对属性表结构的影响不大,例如属性1和属性2LUBM-1是频繁相关的,在其他的数据集中也是频繁相关的。因此,对于同一数据集只需构造一次属性表结构,当新的RDF语义数据流式插入到分层式RDF存储系统时,若新插入的数据具有新的新的属性值,会直接放到剩余表(left-overtable)中,否则会插入到其对应的属性表当中,并且随着新RDF数据的插入,系统会定期更新属性表。最后,为了评估基于YAFIM算法在计算节点增加时的性能扩展性,这里分别采用LUBM-100LUBM-1000 两个数据集、以及真实数据集WordNet3.1DBLP在节点数为24681012上的生成关联规则的时间,每个节点上Spark进程使用的内存大小为12GB(ExecutorMemory)。图15中,坐标横轴为节点数目,坐标纵轴为使用12 计算机学报 2017YAFIM算法来生成关联规则的时间。由图15可见,节点数为2时由于计算资源的有限,所以耗费时间较长,随着节点数目的增加,可用的计算资源不断增加,但同时节点间的网络开销带来的时间消耗也开始逐渐增加,时间变化曲线趋于平缓。总体上,关联规则的生成时间随着节点数目不断增多,在生成数据集和真实数据集上都呈现出近线性的扩展性。图15YAFIM算法构建属性表的节点可扩展性7.2.2 存储层优化本节采用6组数据(LUBM-1LUBM-10LUBM-100LUBM-1000WordNet3.1DBLP)评估基于属性表存储结构的分层式RDF数据系统的查询性能,一共做了3次测试,最后取平均查询时间。此外,本节还使用循环三元组存储结构(SPO,OPS,PSO)进行对比实验。循环三元组存储结构是一种广为使用的以SPOPOSOSP循环索引来应对给定不同SPO组合查询的表结构。在LUBM所提供的14条测试查询语句、WordNet3.1DBLP生成的10条查询语句中,本节选取部分具有代表性的查询,实验结果如图16到图21所示。其中,坐标横轴代表了选取的标准测试查询语句,纵轴代表查询所消耗的时间,“循环三元组存储结构”表示循环三元组存储结构作为分层式RDF数据查询系统的存储层查询所需的时间,而“属性表存储结构”表示以属性表存储结构作为分层式RDF数据查询系统的存储层查询所需的时间。图16LUBM-10.13M条三元组)查询性能对比图17LUBM-101.3M条三元组)查询性能对比图18LUBM-10013.3M条三元组)查询性能对比图19LUBM-1000133M条三元组)查询性能对比论文在线出版号No.60顾荣等:Goldfish:基于矩阵分解的大规模RDF数据存储与查询系统 1320WordNet3.1(8.9M条三元组)查询性能对比图21DBLP(42M条三元组)查询性能对比由图16到图21的实验结果可见,与循环三元组索引结构作为分层式RDF数据查询系统的存储层存储方式相比,利用属性表存储结构的存储方式在查询时间上更快。并且,从实验中可以发现不同的查询语句,利用属性表存储结构提高RDF数据查询的效果也不一样,这和RDF数据在属性表中的分布有关。如果查询语句中的几条子句要查询的属性都在一张属性表中,利用属性表存储结构作为存储层的RDF数据查询系统的查询速度就快得多;反之,如果子句中需要查询的属性都在不同的属性表中,这就需要表间连接,查询效果就会不理想。7.2.3 查询层优化进一步地,为了验证本文所提出的查询层优化的效果,本节采用6组数据(LUBM-1LUBM-10LUBM-100LUBM-1000WordNet3.1DBLP)分别做了3趟测试,最后取平均运行时间,实验结果如图22到图27所示。其中,横轴代表的是不同的标准测试查询语句,纵轴代表的查询所需要执行的时间。“查询层哈希转换优化”代表的是在分层式RDF数据查询系统的查询层增加哈希转换优化后的系统,“查询层未优化”代表的是查询层未优化的分层式RDF数据查询系统。这里选取了部分具有代表性的查询语句,如图所示。图22LUBM-10.13M条三元组)的查询时间对比图23LUBM-101.3M条三元组)查询时间对比图24LUBM-10013.3M条三元组)查询时间对比14 计算机学报 2017年图25LUBM-1000133M条三元组)查询时间对比图26WordNet3.1(8.9M条三元组)查询时间对比图27DBLP(42M条三元组) 查询时间对比由实验结果可见,与查询层未增加查询转换优化的分层式RDF数据查询系统相比,通过增加哈希转换层优化后的RDF数据查询系统比原系统查询时间平均快1-7倍。从图中可以看到,在LUBM-1规模的RDF数据集下,优化效果最快的Query6的查询速度提高了9倍,返回结果数7790条;优化效果最慢的Query2的查询速度提高了0.5倍,返回查询结果数0条。在LUBM-10规模的RDF数据集下,优化效果最快的Query6的查询速度提高了9倍,返回结果数99566条;优化效果最慢的Query2的查询速度提高了0.5倍,返回查询结果数0条。在LUBM-100规模的RDF数据集下,优化效果最快的Query6的查询速度提高了9倍,返回查询结果1048532条;优化效果最慢的Query2的查询速度提高了1倍,返回查询结果数0条。在LUBM-1000规模的RDF数据集下,优化效果最快的Query13的查询速度提高了19倍,返回结果数6078条;优化效果最慢的Query4的查询速度提高了1.3倍,返回结果数34条。WordNet 3.1数据集中,优化效果最快的Query6的查询速度提高了10倍,返回结果数7532条;优化效果最慢的Query2的查询速度提高了2倍,返回结果数8条。DBLP数据集中,优化效果最快的Query9的查询速度提高了28倍,返回结果数1230条;优化效果最慢的Query4的查询速度提高了3倍,返回结果数30条。因此,在RDF数据查询任务中,查询的数据集规模越大、返回的查询结果数越多,本文提出的查询层的哈希转换优化的效果越明显。7.2.4 系统扩展性为了评估随着RDF数据规模的增长,对比以属性表存储结构的RDF数据查询系统和以循环三元组存储结构的RDF数据查询系统在查询时间上的变化情况,同时也对比查询层优化后的分层式RDF数据查询系统和未优化的原系统在查询时间的变化情况。这里选用数据规模不同的四组LUBM数据集进行测试,每个规模级别下分别作3趟测试,最后取平均运行时间7.2.4.1 索引结构扩展性实验结果见图28到图31,图中纵坐标为查询时间,横坐标为LUBM数据集规模。“属性表存储结构”表示以属性表存储结构作为存储层的RDF数据查询系统,“循环三元组存储结构”表示以循环三元组存储结构作为存储层的RDF数据查询系统。在这里,选取的具有典型代表的Query3Query4Query7Query14进行分析。从图中可以发现,随着RDF数据测试数据集规模的增长,用属性表存储结构的RDF数据查询系统随着RDF测试数据集的增大,查询速度均优于循环三元组存储结构。论文在线出版号No.60顾荣等:Goldfish:基于矩阵分解的大规模RDF数据存储与查询系统 1528数据规模变化时Query3可扩展性对比图29数据规模变化时Query4可扩展性对比图30数据规模变化时Query7可扩展性对比图31数据规模变化时Query14可扩展性对比7.2.4.2 哈希优化扩展性实验结果见图32到图35。图中纵坐标为查询执行时间,横坐标为RDF数据的规模。“查询层哈希转换优化”代表的是在分层式RDF数据查询系统的查询层增加哈希转换优化后的系统,“查询层未优化”代表的是查询层未优化的分层式RDF数据查询原系统。由图中可见,随着RDF数据规模的增长,查询层增加哈希转换优化后的系统比原系统查询时间快1倍到7倍。在图中,随着RDF数据测试数据集规模的增长,对Query2查询语句,查询层优化后的系统的查询时间比原系统的查询时间快1倍左右;对Query6查询语句,查询时间快9倍左右;对Query9查询语句,查询时间快1倍左右;对Query13查询语句,在LUBM-1LUBM-100规模的RDF数据集上,查询时间快2倍左右,在LUBM-1000时,性能提升19倍。图32数据规模变化时Query2查询时间对比图33数据规模变化时Query6查询时间对比16 计算机学报 2017年图34数据规模变化时Query9查询时间对比图35数据规模变化时Query13查询时间对比在查询语句Query2Query6Query9Query13中,查询层哈希转换优化后的分层式RDF数据查询系统的查询时间随着RDF数据规模的增长均低于未优化的分层式RDF数据查询系统的查询执行时间,并且查询返回的RDF数据结果越多,查询层进行哈希转换优化的效果越明显。7.3系统对比分析为了评估采用了上述所有优化后的Goldfish系统的查询性能,本节采用已有的查询性能较好的语义数据查询系统Jena-HBaseSHARDRainbow与之进行对比。Jena-HBaseSHARDRainbow系统都是基于类似平台(Hadoop/HBase)的分布式大规模RDF数据的查询系统。我们在数据集LUBM-10WordNet3.1中选取了部分查询语句,对每条查询在Jena-HBaseSHARDRainbowGoldfish系统分别做了3趟测试,最后取平均运行时间,实验结果如图36到图37所示。(1LUBM-10下的四种系统对比图36四种系统对LUBM-101.3M条三元组)的查询时间对比从图36可以看出,在LUBM-10规模的RDF数据集下,Goldfish系统的查询时间均快于Jena-HBaseSHRADRainbow这三种系统的查询时间。其中Goldfish系统对比Jena-HBase系统,优化效果最快的Query3的查询速度提高了1000倍,返回结果数6条;优化效果最慢的Query5的查询速度提高了11倍,返回查询结果数678条。Goldfish系统对比SHARD系统,优化效果最快的Query12的查询速度提高了2700倍,返回结果数15条;优化效果最慢的Query8的查询速度提高了28倍,返回查询结果数7790条。Goldfish系统对比Rainbow系统,优化效果最快的Query1的查询速度提高了11倍,返回结果数129466条;优化效果最慢的Query11的查询速度提高了3倍,返回查询结果数5条。(2WordNet3.1下的四种系统对比图37四种系统在WordNet3.18.9M条三元组)下的查询时间对比从图37可以看出,在真实语义数据集WordNet3.1下,Goldfish系统的查询时间均快于Jena-HBaseSHRADRainbow这三种系统的查询时间。其中Goldfish系统对比Jena-HBase系统,优化效果最快的Query1的查询速度提高了348倍,返回结果数4论文在线出版号No.60顾荣等:Goldfish:基于矩阵分解的大规模RDF数据存储与查询系统 17条;优化效果最慢的Query10的查询速度提高了1.3倍,返回结果数12条。Goldfish系统对比SHARD系统,优化效果最快的Query1的查询速度提高了2642倍,返回结果数10条;优化效果最慢的Query8的查询速度提高了7.5倍,返回结果数7648条。Goldfish系统对比Rainbow系统,优化效果最快的Query6的查询速度提高10.9倍,返回结果数7832条;优化效果最慢的Query9的查询速度提高2.8倍,返回结果数30条。因此,在大规模RDF数据查询任务中,Goldfish系统比SHARDJena-HBaseRainbow系统具有更好的性能。8相关工作在过去,研究人员开发了诸如Jena[11]Sesame[12]RDF-3X[13]RDF数据存储和查询系统。这类系统通常使用传统的关系型数据库作为底层存储,并通过一定的组织方式将语义数据存储在其中。然后将SPARQL语义查询转换成传统的SQL语句进行数据查询[14]。这样做好处是单机范围内技术发展较为完善且系统稳定度高。Erling[15]等人基于OpenLinkVirtuoso1实现了RDF三元组结构的存储。袁平鹏等人通过采用增量压缩、变长整数编码、基于数据块划分的存储等措施设计实现了TripleBit[16]Craig等人[17]HBase中实现了基于水平存储RDF索引结构,并对比基于MySQL集群环境的RDF索引结构的性能。基于HBase的方案在大多数的查询情况下均优与基于MySQL集群的方案。但是在基于HBase的方案中存在两种格式的水平表,这样不仅造成冗余而且水平划分方案无法避免空值问题。然而,现在随着RDF数据的爆炸性增长,基于传统单机数据库的RDF系统在处理语义的数据量和扩展性上存在一定的缺陷,使其无法满足大规模语义数据的应用场景。传统的关系型数据库模型和RDF语义模型在设计和优化目标上并不完全一致,这往往会导致基于关系数据库的RDF数据系统在存储和查询语义数据时会有较大开销。Khadilkar等人利用Jena提供的接口,开发出了Jena-HBase[18]系统,使其能够适应大规模RDFhttps://en.wikipedia.org/wiki/Virtuoso_Universal_Server数据处理的需求。该系统使用HBase管理语义数据,解决了大规模RDF数据的存储问题。但是,Jena-HBase未根据HBase非关系型数据库的特性对查询引擎层未作出优化;并且,由于所有的RDF数据被存储在磁盘中,因而性能表现一般。为了保证语义数据存储服务的可靠性以及查询服务的高效性,顾荣等人研究提出了分层式RDF数据存储查询系统Rainbow[19]。分层式RDF数据存储查询系统Rainbow分为两层:持久存储层和分布式内存存储层。持久存储层通过HBase存储全局RDF数据,保证数据的高可靠性。分布式内存存储层通过Redis存储经常被查询的热数据,将热数据存储在分布式内存中,以提供更高效的数据查询服务。Rohloff等人基于Hadoop设计了SHARD[20]系统,其将RDF数据存储在HDFS中以支持大规模语义数据的存储。并且,为了提高大规模语义数据查询处理的效率,所有的查询处理全部转化为MapReduce任务来执行,能够很好地保证系统的容错性和可扩展性,但是I/O开销过大。另外,其他一些研究者利用图划分优化技术来进行RDF图模式的匹配。例如,Huang[21]等人他们的图划分存储在RDF图上达到了高查询性能。这种方法在RDF图是静态的,机器数是预先固定的情况下表现很好,但是当新批次的数据和机器加入时,为了更好的负载平衡整个RDF图就需要重新划分和分配。Shao等人[22]基于MPI[23]构建RDF图存储系统TrinityTrinity的存储是完全基于分布式内存中的。Gurajada等人基于异步MPI设计了TriAD[24], 其通过分布式的RDF图划分索引结构对join查询进行预先剪枝,之后利用多线程进行异步的join操作,使其达到了非常高的查询性能。Wu等人基于Hadoop设计SemStore[25],利用K-means构建一种特殊的子图进行图划分,并提出分区敏感查询分解算法和两阶段的动态优化技术来减少分布式join查询开销。Chen等人基于Spark设计了SparkRDF[26],其将RDF依据关系和类别划分为多个子图,利用Spark内存计算的特性减小I/O开销,来达到较高的查询效率。Hammoud等人设计了DREAM[27],将数据共享到每个节点,把查询转换为多个子图并映射到一个独立的节点,通过节点间的通信来获取最终的查询结果,以此来避免大量的网络数据传输而带来的开销。Galárraga等人[28]则通过分析历史查询日志,动态地对数据进行分配来提高查询效率。18 计算机学报 20179总结与展望随着语义网技术的不断发展与进步,语义网被广泛应用在医疗、地理信息等多个领域。大数据时代的来临,给语义网的研究带来了新的机遇和挑战。特别是大规模RDF语义数据的存储与查询是目前研究的热点。针对大规模RDF数据的存储与查询问题,本文的主要贡献为:以OpenRDFSesame框架为基础,设计实现了以HBase作为持久存储层、Redis存储热点数据的分层式RDF数据存储查询系统Goldfish,并针对三元组表存储结构所表现出的查询效率和存储空间利用率低、可扩展性不佳的问题,在存储层以属性表作为RDF数据存储结构,替代了常用的循环三元组表存储结构;属性表可以通过布尔矩阵分解算法(ASSO)生成,但是该算法在大规模数据集下出现了构造缓慢等问题。根据布尔矩阵分解算法的特性,本文通过频繁项集挖掘算法对其进行求解,并采用了基于Spark的框架并行化频繁项集挖掘算法,以加速在大规模数据集下属性表的构造。在查询层增加哈希转换层,避免了频繁查询哈希表带来的查询性能的降低。实验表明,Goldfish整体性能比Rainbow系统平均提升6倍左右,比Jena-HBase平均提升500倍左右,比SHARD系统平均提升1200倍左右。下一步工作,我们将会针对以下两点进一步研究和改进:(1)对跨多张属性表进行查询时的查询效率降低的问题。(2)基于数据切分的并行化查询。基于大规模RDF数据的数据切割并行化查询一直是RDF数据查询的难点。RDF数据是一种图数据,具有图结构的特殊性;而现有的分布式框架,如MapReduce,是基于数据切分的并行化框架。如何利用现有的分布式计算框架,将RDF数据查询与之相结合,实现并行化查询,涉及到RDF数据的图切割的问题,需要进一步地研究。参考文献[1] GantzJ, Reinsel D. ExtractingValuefromChaos. Framingham, USA:IDCsDigitalUniverseStudy:IDC-1142,2011.[2] Berners-Lee T, Hendler J, Lassila O. The SemanticWeb. ScientificAmerican,2001,284(5):2837.[3] ZahariaM,etal.Resilientdistributeddatasets:Afault-tolerantabstractionforin-memoryclustercomputing//Proceedingsofthe9thUSENIXconferenceonNetworkedSystemsDesignandImplementation.USENIXAssociation,USA,2012:2-2.[4] Zaharia M, et al. Spark: cluster computing with workingsets//Proceedings of the 2ndUSENIXconference onHot topics incloudcomputing.USENIXAssociation,USA,2010:10-10.[5] ChuanLei Ni, HuWei, Gu Rong, et al. Based on Booleanmatrixdecomposition of RDFdata storage layout and query optimizationmethod//Proceedings of the 31th National Database Conference ofChina.TaiYuan,China,2014. (inChinese)(倪传蕾, 胡伟等人. 基于布尔矩阵分解的RDF数据存储布局及查询优化方法. 31届中国数据库学术会议. 太原, 中国,2014.)[6] MiettinenP,MielikainenT,GionisA,etal.Thediscretebasisproblem.IEEETransactionsonKnowledgeandDataEngineering,2008,20(10):1348-1362.[7] ChandolaV,KumarV.Summarizationcompressingdataintoaninformativerepresentation.KnowledgeandInformationSystems,2007,12(3):355-378.[8] HongjianQiu, RongGu, ChunfengYuan, Yihua Huang. YAFIM: AParallel Frequent Itemset MiningAlgorithmwithSpark//Proceedingsofthe28thInternational Parallel &DistributedProcessingSymposiumWorkshops(ParLearning).Phoenix,USA2014:1664-1671.[9] GuoY, PanZ, HeflinJ. LUBM: Abenchmarkfor OWLknowledgebase systems. WebSemantics: Science, Services andAgents ontheWorldWideWeb,2005,3(2):158182.[10]MillerGA. WordNet: alexical databaseforEnglish. CommunicationsoftheACM,1995,38(11):39-41.[11]McBrideB.Jena:Asemanticwebtoolkit.IEEEInternetcomputing,2002,6(6):5559.[12]BroekstraJ,KampmanA,VanHarmelenF.Sesame:AGenericArchitectureforStoringandQueryingRDFandRDFSchema.//Proceedingsofthe1stInternationalSemanticWebConference,Sardinia,Italy,2002:5468.[13]NeumannT,WeikumG.TheRDF-3XengineforscalablemanagementofRDFdata.TheInternationalJournalonVeryLargeDataBase,2010,19(1):91-113.[14]SakrS,Al-NaymatG.RelationalprocessingofRDFqueries:asurvey.ACMSIGMODRecord,2010,38(4):23-28.[15]ErlingO,MikhailovI.RDFSupportintheVirtuosoDBMS//ProceedingsoftheNetworkedKnowledge-NetworkedMedia.NewYork,USA,2007:59-68[16]PingpengYuan,PuLiu,etal.TripleBit:AFastandCompactSystemforLargeScaleRDFData.TheVeryLargeDataBaseEndowment,2013,4(7):517-528.[17]FrankeC,MorinS,ChebotkoA,etal.DistributedsemanticwebdatamanagementinHBaseandMySQLcluster//Proceedingsofthe2011IEEE4thInternationalConferenceonCloudComputing.Washington,论文在线出版号No.60顾荣等:Goldfish:基于矩阵分解的大规模RDF数据存储与查询系统 19USA,2011:105-112.[18]KhadilkarV,KantarciogluM,ThuraisinghamB.Jena-HBase:ADistributed,ScalableandEffcientRDFTripleStore//Proceedingsofthe2012thInternationalSemanticWebConference(Posters&Demos).Aachen,Germany,2012:85-88.[19]RongGu,WeiHu,andYihuaHuang.Rainbow:ADistributedandHierarchicalRDFTripleStorewithDynamicScalability//Proceedingsofthe2014IEEEInternationalConferenceonBigData.Washington,USA,2014:561-566.[20]RohloffK,SchantzRE.High-performance,massivelyscalabledistributedsystemsusingtheMapReducesoftwareframework:theSHARDtriple-store//ProceedingsoftheProgrammingSupportInnovationsforEmergingDistributedApplications.NewYork,USA2010:4.[21]HuangJ,AbadiD.J.Scalablesparqlqueryingoflargerdfgraphs.TheVeryLargeDataBaseEndowment,2011,4(11):11231134.[22]BinShao,HaixunWang,YataoLi.Trinity:Adistributedgraphengineonamemorycloud//Proceedingsofthe2013ACMSIGMODInternationalConferenceonManagementofData.NewYork,USA,2011:505-516.[23]TheMPIForum.MPI:AMessagePassingInterface//Proceedingsofthe1993ACM/IEEEconferenceonSupercomputing.NewYork,USA,1993:878-883.[24]GurajadaS,SeufertS,MiliarakiI,etal.TriAD:adistributedshared-nothingRDFenginebasedonasynchronousmessagepassing//ProceedingsoftheACMSIGMODConferenceonManagementofData.NewYork,USA.2014:289-300.[25]BuwenWu,YongluanZhou,PingpengYuan,etal.SemStore:ASemantic-PreservingDistributedRDFTripleStore//Proceedingsofthe23rdACMInternationalConferenceonConferenceonInformationandKnowledgeManagement.NewYork,USA.2014:509-518.[26]XiChen,HuajunChen,NingyuZhang,etal.SparkRDF:ElasticDiscretedRDFGraphProcessingEngineWithDistributedMemory//Proceedingsofthe2014InternationalConferenceonPosters&DemonstrationsTrack.RivadelGarda,Italy.2014:261-264.[27]HammoudM,etal.DREAM:DistributedRDFEnginewithAdaptiveQueryPlannerandMinimalCommunication.TheVeryLargeDataBaseEndowment,2015,8(6):654-665.[28] GalárragaL,HoseK,SchenkelR.Partout:adistributedengineforefficientRDFprocessing//Proceedingsofthe23rdInternationalWorldWideWeb.Seoul,Korea.2014:267-268.GuRong, bornin1988.PhDcandidate.Hisresearch interests include Big Dataprocessing, largescalemachinelearninganddistributedsystems.QiuHongJian, bornin1990, Master. Hisresearchinterestsincludesemanticwebandbigdataparallelprocessing.YangWenjia,bornin1991,Master.Hisresearchinterestsincludebigdataparallelprocessingandcloudcomputing.HuWei, bornin1982, associateProfessor .Hismainresearchinterestsincludeontologyengineeringanddatafusion.Yuan Chunfeng, born in 1963, Professor. Her researchinterests include computer system architecture, big dataprocessingandwebinformationextractionandintegrationHuangYiHua, bornin1962, Professor. Hisresearchinterestsinclude big data parallel processing and cloud computing,computerarchitectureandparallelcomputing.BackgroundIntheBigDataera, withtherapiddevelopment of theInternet applications and the semantic web technology, thesemantic data is exploding. Many applications can providebetter services basedonthelarge amount of semantic data.Thus,itissignificanttostoreandqueryoverthelargesemanticdata. However, therapidincreaseof thesemanticdatabringsnewchallengesonefficient storingandqueryingsemanticdatainthebigdataenvironment. Thetraditionalwaysforsemanticdatamanagement is tostoreandquerythedatainrelationaldatabasemanagement systems. Withthedataincreases, thesetraditional ways can hardly handle big data. Recently,researchers tryto adopt the cutting-edge distributedsystemsuch as MapReduce and HBase to handling large scalesemantic data. However, they put forward fewindexingstrategies, andsystemslikeSHARDinherit theinefficiencyofHadoopMapReduce.To address these problems, this paper proposed adistributedhierarchical storagearchitecturetostoreandquerylarge-scale semantic data based on the OpenRDF Sesameframework, calledGoldfish. The RDFstorage andindexingmechanismis the triple store optimized by adopting theattribute table to replace the rawRDF tables. To handlegenerating the attribute table structure of the large scale20 计算机学报 2017semantic data, a parallel frequent itemset miningalgorithmwithSparkframeworkisadopt toprocessthelargescaledata.Inaddition, anoptimizedhashconversionlayerisproposedtoreducetimecostinfrequenthashtablesearchduringthead-hocquerystage.Goldfish takes advantage of the cluster resource andperformsgoodscalability. Theexperimental resultsshowthatGoldfishis around8times faster thanRainbow, 500timesfaster than Jena-HBase and 1200 times faster than theMapReducebasedRDFqueryingsystemSHARD.This work is supported by China National ScienceFoundationSpecial ResearchGrant (NO.61223003) ChinaNational Science FoundationGrant (NO.61370019) and theKey technologies Research and Development programofJiangSu(NO.BE2014131).

[返回]
上一篇:复杂装备精密产品多项式混沌扩展稳健优化设计
下一篇:知识系统中全粒度粗糙集及概念漂移的研究