面向web规模rdf数据查询算法的研究与实现

《面向web规模rdf数据查询算法的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文面向web规模RDF数据查询算法的研究与实现作者姓名：叶向东指导教师：袁野副教授东北大学信息科学与工程学院申请学位级别：硕士学科类别：工学学科专业名称：计算机应用技术论文提交日期：2014年6月论文答辩日期：2014年6月学位授予日期：2014年7月答辩委员会主席：赵海教授评阅人：张大波教授吴刚副教授东北大学2014年6月万方数据AThesisinComputerApplicationTechnologyResearchandImplementationoftheQueryProcessingAlgo

2、rithmsforWeb-·scaleRDFDataByXiangDongYeSupervisor：AssociateProfessorYeYuanNortheasternUniversityJune2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：计向东日期：2口，中、／、／o学位论文

3、版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构遴交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口学位论文作者签名签字日期：：计钢纸加7住反fO丙荤D／万方数据查i垦盘鲎塑圭茎焦逾圭堂垩Web规模RDF数据查询算法的研究与实现摘要目前因特网发展出现瓶颈的原因之一是由于没有赋予网络上的全部资源足够的语义信息。最主要的原因在于，现

4、在的网络主要是基于超链接实现的，网络只是知道如何显示资源，却不清楚资源的实际含义。而RDF(ResourceDescriptionFramework)正是由W3C提出的语义网的标准描述框架。随着信息提取技术的发展和语义网的不断进步，网络中涌现出大量的RDF数据，如何存储、管理以及检索如此庞大的RDF数据已经成为了一项棘手却亟待解决的问题。SPARQL查询是W3C提出的对RDF进行查询的标准查询语言。目前RDF查询算法面临的主要问题是：(1)不支持带有通配符的SPAJR．QL查询。(2)不能支持实时在线更新。(3)可扩展性差。本文基于

5、以上三个问题，提出了基于索引的查询算法以及分布式环境的查询算法。针对以上问题，首先在第三章基于索引的查询算法中做了如下工作：(1)采取基于图的模型来存储RDF数据。具体地讲，本文通过基于索引的邻接表存储RDF数据。(2)本文在原始RDF图的基础上，对每个实体和类顶点增加一个标记信息。随之，提出了一种新的索引结构VS*-tree。它可以对上述带有数字标记信息的RDF图进行快速索引，且维护代价较低，易于更新。(3)针对带有数字标记信息的数据图，本节提出了一种新的剪枝规则，这种剪枝规则可以完美的嵌入到本文提出的查询算法中，并且同时适用于普

6、通SPARQL查询和带有通配符的SPARQL查询。其次，本文充分考虑了RDF数据本身的特点，在第四章分布式环境的算法中(1)提出了一种扩展性强的RDF数据系统，该系统可以通过Hadoop框架可以直接利用任何现有集中式算法。(2)提出的数据分割技术和存储技术可以显著的降低查询过程中的数据通信量。(3)给出了一种可以自动将查询分解成可并行执行片段的算法，使得大量独立执行片段可以在不进行通信的前提下，在数据存储节点独立获得查询子结果，进一步提高了算法的可扩展性。在本文的最后，通过大量实验验证了本文算法的有效性及高效性。关键词：语义网，RD

7、F数据，SPARQL，分布式万方数据万方数据ResearchandImplementationoftheQueryProcessingAlgorithmsforWeb—scaleRDFDataAbstractNowadays，theraresemanticinformationofthenetworkresourcesisoneofthemainlimitationsoftheInteractdevelopment．AstheorganizationoftheInternetisbasedonhyperlinks，itonlykno

8、wshowtodisplaytheresourcesratherthanrecognizetheimplicationoftheresources。TheRDF(ResourceDescriptionFramework)，propos