大规模rdf图数据的正则路径查询研究

《大规模rdf图数据的正则路径查询研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、天津大学硕士学位论文大规模RDF图数据的正则路径查询研究TheResearchofRegularPathQueryonLarge-ScaleRDFGraph学科专业：软件工程研究生：姜龙翔指导教师：石红天津大学软件学院二零一三年十一月独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得天津大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了

2、谢意。学位论文作者签名：签字日期：年月日我是爱天大的！！学位论文版权使用授权书本学位论文作者完全了解天津大学有关保留、使用学位论文的规定。特授权天津大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。（保密的学位论文在解密后适用本授权说明）学位论文作者签名：导师签名：签字日期：年月日签字日期：年月日摘要正则路径查询(RegularPathqueries,RPQ)是图数据管理中一种最基本的查询。随着链接运动(Linke

3、dOpenData,LOD)的开展，越来越多的RDF数据发布到Web上，形成了一个庞大的图。如此大规模的图数据对正则路径查询的性能提出了严峻的挑战。针对上述问题，设计了一种具有线性空间复杂度的分布式路径索引方案(Double-layerBi-directionalIndex，DBI)，用于大规模RDF图数据上高效的路径查询，并分别提供了基于Bigtable模型和分布式B+树模型的实现方案。在索引结构基础上，提出了一系列新的分布式路径查询算法TraPath，包括基于深度优先遍历的子路径查询算法TBS、基于出/入度节点集的路径划分算法

4、和调度算法等，用以支持快速正则路径查询，并提供了基于Bigdata分布式计算框架的并行实现。通过定义允许有重复节点的“非简单路径”和限制结果集数目的“非计数结果路径”的语义，将路径查询问题时间复杂度降低到可接受的多项式(polynomialtime)级别。此外，对基于维基百科发布的真实世界的RDF数据集DBpedia，进行了大量的图数据结构统计与性能评估。综上所述，本文提出的分布式正则路径查询解决方案，基于高效的专用路径索引，给出了新的查询算法系列。通过大量的性能评估和对比实验表明，本文提出的解决方案在为用户提供大规模RDF图数据

5、上正则路径查询方面，具备显著的性能优势。关键词：正则路径查询，分布式，路径索引，大数据，RDF，NoSQLABSTRACTRegularpathqueries,orRPQs,arebasicqueryingmechanismsongraphsthatplayanincreasinglyimportantroleoverthepastdecade.Inrecentyears,largeamountsofRDFdataarepublishedontheWebsincethedevelopmentofLinkedData.Suchala

6、rge-scaleofdatahasposedseriouschallengestotheefficiencyofRPQs.Inviewoftheaboveproblems,wedeviseaDouble-LayerBi-Directionalindexstructurethathasalinearspacecomplexityforefficientpathqueriesonlarge-scaleRDFgraphdata.ImplementationsbasedonBigtablemodelandthedistributedB+

7、treemodelareprovidedinthispaper.Onthebasisoftheindexstructure,weproposedanovelalgorithmsfamily,namedTraPath,includingtraversalsub-pathsearchalgorithmbasedonDFS,pathportioningalgorithmbasedontheindegree/outdegreenodesandschedulingalgorithmstosupportfastregularpathqueri

8、es.Also,parallelimplementationsbasedonBigdatadistributedcomputationframeworkareprovided.BydefiningtheNoSimplePathsandNoCount