基于bsp的sparql基本图模式查询

《基于bsp的sparql基本图模式查询》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于BSP的SPARQL基本图模式查询SPARQLBGPQueryEngineBasedonBSP学科专业：计算机科学与技术研究生：李国鼎指导教师：张冰怡副教授天津大学计算机科学与技术学院二零一三年十一月1独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得天津大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名

2、：签字日期：年月日学位论文版权使用授权书本学位论文作者完全了解天津大学有关保留、使用学位论文的规定。特授权天津大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。（保密的学位论文在解密后适用本授权说明）学位论文作者签名：导师签名：签字日期：年月日签字日期：年月日2摘要随着语义网的不断发展以及开放链接运动深入展开，发布在互联网上的RDF数据不仅已达到百亿级三元组规模，而且呈现出几何增长的趋势。有效的管理和查询这些

3、RDF数据，正显得日益重要。传统的单机上针对RDF数据的SPARQL基本图模式查询算法，不能满足RDF数据日益增长的需求。而基于MapReduce分布式计算模型的SPARQL基本图模式查询方法，不能够充分发挥分布式计算的潜力，并行度有待提高。针对该问题，本文提出了一种基于BSP模型的SPARQL基本图模式算法。根据RDF数据是有向图数据的特性以及基本图模式的定义，把整个查询过程分成“匹配”和“迭代”两个阶段，先匹配出每个要查询的三元组模式，然后通过迭代让部分解逐步逼近完全解，最后得到查询结果。根据本文提出的基于BSP模型的S

4、PARQL基本图模式算法，设计并实现了一个SPARQL查询机原型。该SPARQL查询机原型的查询引擎部分采用BSP模型分布式计算框架——HAMA实现。在数据持久层，该SPARQL查询原型机中引入了基于Cassandra数据库存储RDF图数据，以满足RDF数据能够得到有效管理和快速加载的需要。此外，还设计了针对本文提出的基于BSP模型的SPARQL基本图模式算法的特有的缓存机制，提高查询速度。在实验部分，与前人提出的基于MapReduce模型的SPARQL基本图模式算法的查询时间对比实验。实验结果表明，本文提出的基于BSP模型

5、的SPARQL基本图模式算法查询效率得到提升。总的来说，本文提出的基于BSP模型的SPARQL基本图模式算法充分利用了BSP模型的消息机制，相对前人提出的基于MapReduce模型SPARQL基本图模式算法，在并行度上更优。从而可以为大规模RDF数据的快速SPARQL查询提供支持。关键词：语义网资源描述框架SPARQL查询基本图模式BSP模型HAMA框架3ABSTRACTWiththedevelopmentofSemanticWebandthemovementofLinkedOpenData,theRDFdatareleas

6、edontheInternethasalreadyreachedtenbillionstriplesscale,besides,italsopresentsthegeometricgrowthtrend.Howtoeffectivelymanagementandquerythesedata,ismoreandmoreimportantinnowadays.Traditionalmethodsbasedonstand-alonemachinetosolveSPARQLbasicgraphpatterncouldnotmeett

7、herequirementsofsuchhugedata.And,themethodbasedontheMapReducecomputationmodeltosolveSPARQLbasicgraphpatterncouldnotgivefullplaytodistributedcomputingpotential.Forthisproblem,wecomeupanalgorithmwithBSPmodeltosolveSPARQLbasicgraphpattern.AccordingtothegraphfeatherofR

8、DFdataandSPARQLbasicgraphpatterndefinition,wedividethewholeprocessintotwophases:“matchingphase”and“interactivephase”.Basedonthisalgorithm,wedesig