一种大规模RDF数据关联路径发现方法

摘要

本发明公开了一种大规模RDF数据关联路径发现方法。本方法为：1)抽取RDF数据库中的RDF关联数据并以、、形式缓存；2)对主语和宾语分别分配一id，生成主语id、url和宾语id、url存入到点文档中；将主语id宾语id谓语url存储到边文档中；3)将点文档内容存到nodes表中构建出点弹性分布式数据集实例，将边文档内容储到edges表中构建出边弹性分布式数据集实例；然后进行实例化，得到分布式图形数据集合；4)计算该集合中数据的所属子图，生成若干没有关联的最大连通子图；将同一子图中的点集合两两组合并计算每一组合中两点之间的关联路径。本发明能更快速完整的发现关联路径。

说明书

技术领域

本发明涉及一种基于SPARKGRAPHX的大规模RDF数据关联路径发现方法，属于计算 机软件技术领域。

背景技术

语义网是人工智能和Web技术相结合的产物，语义网的内容表达是基于XML(eXtensible MarkupLangauge)语言和资源描述框架(RDF)来实现的。XML允许使用者以层次结构自定义 标记来标注数据，并将其作为标注放置在网页中，以便计算机程序处理网页内容。XML的内 容包括XML声明、定义语言语法的DTD(DocumentTypeDeclaration)、描述标记的详细说明 及文档本身等。RDF是Web上用于数据交换的标准模型，继承了Web的连接结构，使用统 一资源标识符(URI)描述网络上的节点以及节点间的联系，即三元组模型。使用这个简单的 模型，允许结构化和半结构化的数据在不同的应用程序间共享。

目前广泛用来检索RDF信息以及数据之间的关联路径都是通过拼接有限的SPARQL语 句来完成数据关联路径的搜索，但目前的SPARQL只支持RDF数据基本模式的匹配查询， 不支持对RDF数据节点间或者单节点周围可能存在的联系路径的查询，不能充分挖掘RDF 数据节点间关联的特性，因此很难直接发挥RDF数据模型区别于其它数据模型的优势，而实 际应用中不仅需要使用SPARQL对RDF数据进行基本模式匹配的查询，很多时候挖掘RDF 数据节点间的联系也十分重要。目前也有一些发明和软件是在做RDF数据关联路径发现，例 如RELFINDER可以发现RDF数据之间的关联和关联路径，但是它的运行原理和机制是限制 了数据发现的路径长度和数据之间连接的方向，列举了三种场景下给出每一种场景下的 SPARQL语句拼接，这种方式在一定程度上确实能够发现RDF数据的关联路径，但是诸多的 限制也会造成数据关联路径发现不完全的现象，而且RELFINDER在很大程度上它要求底层 必须为RDF数据库且该数据库支持SPARQL标准，对底层数据库的耦合性也较高。另外 RELFINDER要求发现关联数据必须在同一台RDF数据库当中，只有这样才能够发现数据之 间的关联路径，但是现实情况往往是数据量大且数据节点多，一个RDF数据库无法存储所有 的数据，此时RELFINDER就解决不了这样的数据的关联路径发现问题。

发明内容

针对现有技术中存在的技术问题，本发明的目的在于提供一种基于SPARKGRAPHX的 大规模RDF数据关联路径发现方法，该方法运用了现有的一些大数据处理平台尤其是图形数 据并行化处理框架，通过自主研发的一套关联数据处理和分析机制，实现了基于spark的RDF 数据关联路径的发现。从总体说来，该发明主要包含RDF关联数据抽取模块、关联数据组织 模块、关联数据的存储和管理模块、关联数据构图模块、最大连通子图计算模块、关联数据 路径搜索模块、关联数据源的指定和关联路径可视化展示模块。

本发明的技术方案为：

一种基于SPARKGRAPHX的大规模RDF数据关联路径发现方法，其步骤为：

1)RDF关联数据抽取模块：该模块读取关于多个RDF数据库地址信息、用户名、密码、 数据库名称的配置信息，启动SPARQL构建语句模块，通过该模块作用是调用系统内置的 sparql查询语句，查询关联数据，即主语、谓语、宾语均为url的资源，然后连接RDF数据 库，抽取数据库当中的RDF关联数据，并且将多台RDF数据库查询出来的关联数据三元组 以<主语><谓语><宾语>的形式缓存在内存中，超出发明给予的缓存上限1G，启动连接 HDFS模块，启动HDFS写入模块将数据写入到HDFS当中，存储的文件名称为rdf_relations.n3 由分布式文件系统存储RDF关联数据信息。

2)关联数据组织模块：RDF数据都是URL形式，而GRAPHX接收的数据id为long类 型且数据与数据之间的关系都通过这个id进行描述，而RDF数据与数据之间的关系都通过 URL描述。因此本发明对RDF的主语和宾语内容进行了重编码。因此本模块的功能是从HDFS 当中读取主语和宾语的信息并且给主语和宾语内容重新分配id，首先是通过hive这个数据仓 储工具，将之前注入到hdfs文件系统中rdf_relations.n3数据调用系统编制好的hive脚本，读 取出来rdf_relations.n3文件当中的主语url、谓语url和宾语url，然后首先对主语url和宾语 url进行编码，分别对主语和宾语的url都分配一个long整型的id号,最终生成主语id1主语 url和宾语id2宾语url这样的内容，将这个内容存入到node.txt文件中。然后再生成id1id2谓 语url这样的内容，将这个内容存储到edge.txt文件中。根据上述的关联关系模块的功能，发 明首先利用了hive的client创建了一个结构为id–url(例如1http://baidu.com,2 http://google.com.cn)RDF_relationship表格结构，这个表格结构存储在了hive的metasore模 块当中，然后调用了系统内置的装载数据的脚本，将rdf_relations.n3内容装载到了 RDF_relationship表中，首先调用系统内置脚本读取表中的主语内容和宾语内容，然后将这个 主语url和宾语url进行编码，在读取这个主语和宾语对应的谓语，最后形成两种结构的内容， 一个是id主语url，id宾语url；另一个是主语id宾语id谓语url，再将第一种结构的内容 存储到点文档node.txt当中，再将第二种结构的内容存储到edge.txt边文档中。最后再把这两 个文档存储到hdfs当中。

3)关联数据的存储和管理模块：该模块的主要功能有两个，一个是建立点表格(nodes) 和边表格(edges)且将这个文档结构存储在hivemetastore中，第二个就是调用数据载入脚本 将HDFS中的node.txt和edge.txt文档中的内容存储到edges表和nodes表中。那么具体的做 法是首先系统启动内置点表格创建脚本createtablenodesvalues(idlong,urlString)和边表格创 建脚本createtableedgesvalues(idlong,idlong,urlString)构建边表格和点表格结构，然后调用 loaddataintotable这样的批次载入数据的方式将node.txt和edge.txt文档中的内容注入到上述 表格中。最后hive会将创建的边表格结构和点表格结构存储到metastore中。接收点文档和边 文档，启动HDFS数据写入模块，然后将点文档和边文档存储到HDFS文件系统当中。并且 构建hive表结构，并将表结构存储在hive的metadata元信息存储库中。

4)关联数据构图模块：包括了hive查询模块、vertexRDD构建模块、EdgeRDD构建模 块、graph构建模块。hive查询模块构建查询语句，将HDFS文件系统中存储的node.txt和 edge.txt的内容查询出来。具体的来说，首先我们查询的是nodes表，运用hql基本的语法规 则构建了一个点查询语句，selectid，urlfromnodes，我们此时查询后得到的结果为id和url， 为下一步利用这个查询出来的结果构建vertexRDD做铺垫，同理我们用类似的语句可以查询 出来edge表中的内容，为下一步构建EdgeRDD做铺垫。vertexRDD构建模块负责将点文档 内容通过spark接口构建出点弹性分布式数据集实例，具体的做法是首先从nodes表中实际上 查询出来的结果是关于id和url的一个集合，那么我们可以创建一个Array，这个Array数组 里面存储的是node实例，node实例包含两个属性，这两个属性是整数类型身份号longid和 字符串类型统一资源定位符Stringurl(因为此处是从nodes表中读取的内容，因此这里的url 指的是主语或者宾语的url而不是谓语的url)，最后通过SparkContext序列化接口接收这个包 含着点集合的Array数组，这样就创建了一个vertexRDD。EdgeRDD构建模块将边文档内容 通过spark接口构建出边弹性分布式数据集实例，它的创建过程与vertexRDD类似，首先是 从edge表实际上查询出来的结果是关于ididurl的一个集合，那么我们可以创建一个Array， 这个Array数组里面存储的是edge实例，edge实例包含三个属性，这三个属性是longid1， longid2，Stringurl，最后通过SparkContext序列化接口接收这个包含着边集合的Array数组， 这样就创建了一个EdgeRDD。最后我们利用了spark接口将上述的两个创建的vertexRDD和 EdgeRDD实例注入到spark接口中来实例化一个graph实例，而这个graph实例就是一个分布 式图形数据集合。

5)最大连通子图计算模块：计算的目的是弄清一个图有几个连通部分及每个连通部分有 多少顶点。这样可以将一个大图分割为多个小图，并去掉零碎的连通部分，从而可以在多个 小子图上进行后面的关联数据路径搜索计算。本次发明运用PREGEL计算框架计算分布式图 形数据集合中数据的所属子图，通过该模块将生成若干个没有关联的最大连通子图，计算完 成后将结果记录下来，打开HDFS写文件流，然后将计算完成的内容存放到 ConnectedComponents.txt文件当中，存储的时候以graphxno[id1,id2,id3…,idn]的方式进行存 储。数据存储结束后，接下来我们调用最大连通子图表格结构生成脚本，生成createtable ConnectedComponentsvalues(intnumber,Array<int>connectedIds),然后将 ConnectedComponents.txt内容存到这个数据表里面，最后我们将ConnectedComponents表格 结构存储在hivemetastore当中。

6)关联数据路径搜索模块：该模块读取最大连通子图计算模块计算后的存储在HDFS当 中的数据，并且通过该数据进行构图，将同一子图中的点集合两两组合，对于每一个组合计 算这组合的两个点(例如a和b)之间的关联路径，a一个点为起点，然后找出以a出发的边， 组成一个路径集合PATH(1)，对PATH(1)中的每一条路径path：取path的端点x，找出从端 点x出发的所有边EDGE(x)，遍历EDGE(x)，对其中每一条边edge：如果edge不在path 中，则将path+edge放入PATH(2)中，如果edge已经存在在path当中，那么就不重复存储。 结束后，再以PATH(2)为路径集合再次遍历，以此类推遍历一遍PATH(n)的集合，最终我 们在得到的所有path(n)集合中查询每一条结果，判断这条结果中是否有端点b，如果有的话， 那么找到这条结果中从第一次出现的端点a和最后一次出现的端点b的片段并且将结果截取 出来，那么我们处理完所有的path(n)集合就得到从a到b的所有关联路径集合。然后我们把 这个关联路径集合记录下来。细分起来该模块分为hive查询模块、关联路径算法模块、关联 路径记录模块。

7)关联数据源的指定和关联路径可视化展示模块：最后本发明提供了一个用户输入和查 看的界面。这里面包括了数据源地址的输入、数据源校验模块、数据源最大连通图展示模块、 关联路径展示模块。首先用户可以在界面当中输入选取的数据源地址，然后系统会根据这个 数据源地址进行校验，发现数据源地址是否正确且是否能够访问，如果上述通过了，那么系 统会完成上述的1-5步的过程，然后展示出来这些数据源哪些数据源是连通的他们连通的子 图是什么样子的，然后用户可以在连通图上点击两个点，系统会完成第6步的工作，从而计 算得出结果，将结果转换成json格式的文档，然后利用ajax技术传给前台，前台接收到后台 的json数据并运用d3.js的技术完成关联路径的展示。

本发明从技术思路上是首先明确数据源，然后判定数据源在系统中是否已经存在，如果 存在则直接显示出来这些数据源的连通子图，然后我们可以选择任意连通子图上的两个点， 就可以得到这两个点具体的连接路径是什么。如果是新的数据源就完成上述的步骤之后就可 以发现数据之间的关联和关联路径。如果有新的数据源加入，那么这个过程需要对新的数据 源走完1-3流程，然后新老数据都走步骤4-7即可。

与现有技术相比，本发明的积极效果为：

1)该方案以HDFS为存储介质，并且利用hive进行查询，从数据存储方面来说它突破了 传统的RDF存储方式，提高了RDF数据存储的扩展能力，也突破了许多原生态的RDF数据 库在存储容量上的限制，解决了海量RDF数据的存储问题。

2)该方法与RDF原生态数据库解耦且不依靠SPARQL查询语句标准。

3)该发明以SPARKGRAPHX并行图形处理框架为基础，通过PREGEL计算模型将连通 路径查找算法、最大连通子图算法都做了并行化处理，能够解决大规模RDF数据关联发现的 问题，这相较于之前的传统的依赖于构建有限的SPARQL之间的关联路径的方式相比，传统 的数据关联路径发现都是通过拼接SPARQL语句，这种方式是通过内置设定几种情况，然后 拼接SPARQL语句来完成。而本次发明不会假定任何数据关联路线，也就是说只要数据之间 有关联路径就可以通过该方法获取而不是只能发现一些既定路线和方向的数据之间的路径和 关系，突破了SPARQL的限制，能够更加快速更加完整的发现数据之间关联路径。

附图说明

图1基于spark的RDF数据关联路径发现方法总体设计图；

图2最大连通子图

(a)最大连通子图示例一，(b)最大连通子图示例二。

具体的实施方式

一种基于SPARKGRAPHX的大规模RDF数据关联路径发现方法，如图1所示，其具体 的步骤是：

1)RDF关联数据抽取。本部分是发明的数据准备阶段，数据处理人员可以在系统当中 配置和管理多个RDF数据源地址，然后发明首先会检查系统内部是否有该地址，如果有则询 问是否需要重新载入该地址，如果确定需要重新载入，那么系统会首先读取RDF数据库地址 信息、用户名、密码、数据库名称的配置信息，然后进入到该RDF资源库当中，然后启动 SPARQL构建语句模块构建系统内置的RDF关联数据抽取语句并且加入过滤条件FILTER isIRI(？o)，从而构建好抽取关联数据的SPARQL语句，然后调用jena引擎，执行sparql语句， 获取RDF关联数据，并且将RDF关联数据以<主语><谓语><宾语>形式(即主语url、谓 语url、宾语url)缓存在内存当中，当内存超过一个G时，启动数据写入模块，开启HDFS 写入接口，指定文件名为RDF.n3，然后将内存中的数据注入到hdfs当中，最后清空内存继续 载入新的关联数据，直到指定的数据源关联数据获取完毕，关闭数据源链接，释放hdfs资源。

2)关联数据id分配，这是一个RDF数据ETL的过程，将RDF数据转变成能够进入graphx 内置的数据结构的过程。发明在完成数据源的获取之后首先打开hdfs接口然后打开hdfs读模 式获取RDF.n3文件，然后以行为粒度，将一行的数据以空格的方式进行拆分，拆分的结果即 为主谓宾的结构，然后拿到主语和宾语数据，分别启动一个id分配模块新分配一个id，然后 将id和url对应关系记录在点文档中。紧接着将之前拆分出来的主谓宾结构的数据修改成为 {主语id，宾语id，谓语}这样结构的数据并且把该数据记录在边文档当中。完成之后我们启 动hdfs接入接口，将点文档id_url和边文档edge_url存储在hdfs当中，数据成功载入到hdfs 后系统释放资源。

3)关联数据的存储和管理，在hdfs存储完成后系统启动系统内置的hive构建脚本，脚 本可以将id_url和edge_url文档的结构存放到hive配置的metastore进行数据库表结构的存储， 以方便后续在关联数据构图过程中数据的查询模块进行数据查询和获取工作。

4)关联数据构图过程依据上述的关联数据id分配和数据存储，读取点文档，并且调用 SPARKGRAPHX数据接收入口构建GRAPHX的点RDD，最终形成了一系列具有 VertexRDD<LONG,STRING>结构的点弹性分布式数据集实例。另外读取边文档并且将数据注 入到EdgeRDD<LONG,LONG,STRING>结构的边弹性分布式数据集实例中。从而步骤2和4 共同完成了RDF数据ETL到spark的过程。

5)最大连通子图计算该计算是后面数据关联路径搜索计算的一个基础性工作，原因是 数据关联路径计算必须要将所有的数据节点都放入计算集群当中，无法进行数据切割，因为 并不知道哪些数据点是没有连通性的，所以整个集群上如果要进行数据的切割，那么相当于 所有节点的一个复制。所以我们为了减小计算的复杂性，所以在计算数据关联路径之前优先 计算数据的最大连通图，此时计算的目的是弄清一个图有几个连通部分及每个连通部分有多 少顶点。这样可以将一个大图分割为多个小图，并去掉零碎的连通部分，从而可以在多个小 子图上进行更加精细的操作。这些子图的特点是最大程度的保证了在图中所有的点都是具有 关联的且都有路径可以连接而子图与子图之间没有任何关联路径。因此这样我们就可以判断 加载进来的所有的点，他们之间的所属子图，也就是说具体计算出来哪些点在一个子图当中， 哪些点不在这个子图当中。该模块在最大连通子图算法的基础上，运用了sparkgraphx的pregel 计算框架，实现了算法并行化，这样在处理大规模的rdf数据时，我们能够快速计算出最大 连通图，从而进行每一个连通图的关联路径。具体做法是首先接收了关联数据构图过程之后 的图形结构数据，然后调用了SPARKGRAPHX图形处理框架的映射操作，根据原图的一些 特性得到新图，原图结构是不变的，属于可以供SPARKGRAPHX内部优化的等价结构图，然 后启动PREGEL计算框架并且将之前构建的图注入到PREGEL计算框架中，并且配置 activeDirection＝EdgeDirection.Either即告知PREGEL框架该图为双向图。然后PREGEL启动 主导节点和工作节点，主导节点负责分配图处理任务，工作节点负责计算。然后工作节点负 责顺序执行用户定义的超步操作，对于每一个超步操作我们都由用户定义的function来执行。 在每个超步步骤中，各个节点执行相同的用户定义函数来处理数据，更新自身的状态乃至更 改整个图的拓扑结构。PREGEL完成上述的启动后发明首先定义了一个图的起始点，然后以 该起始点作为起点获得与该点连通的所有的点，然后通过sendmessage方式将之前计算好的 信息发送给所有的点，再聚合这个结果，聚合消息要求产生消息队列的最小集合，然后第一 个超步计算完成，第一个超步将计算的结果传给第二个超步，第二个超步从第一个超步当中 获得消息队列并且取出节点，计算与该节点相连接的所有节点，然后把这个计算的结果发送 给所有的点，再聚合这个结果得到一个消息队列的最小集合。其他的同理，直到图中所有的 点遍历完全从而就产生了最大连通子图。上述过程可能过于抽象，我们举一个简单的例子如 图2所示，那首先获取下图数据并且序列化Array((1L,"1"),(2L,"2"),(3L,"3"),(4L,"4"),(5L, "5"),(6L,"6"),(7L,"7"),(7L,"7"),(8L,"8"),(9L,"9"))构成vertexRDD这样的数据结构，然后序列 化Array(Edge(1L,2L,"朋友"),Edge(2L,3L,"朋友"),Edge(3L,5L,"朋友"),Edge(1L,4L,"朋友 "),Edge(4L,6L,"朋友"),Edge(3L,6L,"朋友"),Edge(7L,8L,"朋友"),Edge(8L,9L,"朋友"))生成 EdgeRDD边数据结构，然后构建一个由vertexRDD和EdgeRDDPREGEL组成的图实例graph， 接着创建一个PREGEL实例并且把graph实例注入到PREGEL当中且指明图的结构是双向结 构(这是因为GRAPHX是基于有向图的计算框架，所以要计算无向图时实际上是构建的双向 图，这样GRAPHX就能够进行无向图计算了)，然后PREGEL启动主导和工作节点，每一个 工作节点启动一个超步，这个超步选取一个点作为起始点，例如选择1作为起始点，然后计 算与1关联的点，发现是2和4，这时候组成一个计算点集合[1,2,4]，也组成了计算边集合[{1,2, 朋友},{1,4,朋友}]将这个点集合和边集合信息发送到其他的超步当中，每一个超步都会先做一 个集合的merge操作，建立最小的集合，此时计算点集合[1,2,4]是最小的集合。同样的计算过 程2这个节点会得到[1,2,3]这个集合，然后merge之后我们会将前面的[1,2,4]和这次计算的 [1,2,3]进行合并，这样我们得到的最小计算点集合是[1,2,3,4]和最小的计算边集合[{1,2,朋 友},{1,4,朋友},{2,3,朋友}]，其他点也是同样的道理，最后我们就可以得到计算点集合 ARRAY([1,2,3,4,5,6],[7,8,9])和计算边集合ARRAY([{1,2,朋友},{1,4,朋友},{2,3,朋友},{4,6,朋 友},{3,5,朋友}],[{7,8,朋友},{8,9,朋友}]。需要强调和说明的是每一个点的计算没有先后顺序， 每一个点相当于形成了一个超步，那么这些超步计算的时候都是并行执行的，所以很大程度 上提升了计算的速度和计算能力。最后生成了整个若干个独立的连通子图，并且我们将这些 连通子图的id存入到HDFS当中文件结构为NO,[ID1，ID2，ID3…]，然后我们首先打开HDFS 文件写入流将内容写入到ConnectedComponentsVertex.txt.文件中，然后我们将[ID1，ID2，ID3…] 里面的id取出来，两两组合查询edges边文档，得到id与id之间的关系，即ID1ID2url这样 的内容，然后把这个内容记录下来形成ConnectedComponentsEdges.txt调用系统内置的脚本， 构建表格ConnectedComponentsVertex.结构和ConnectedComponentsEdges结构，再调用hive 数据载入命令将ConnectedComponentsVertex.txt.文件的内容载入到 ConnectedComponentsVertex表格当中，将ConnectedComponentsEdges.txt文件内容载入到 ConnectedComponentsEdges表格当中。

6)关联数据路径搜索读取最大连通子图文件，获取连通子图id，依次构建NO下的所 有的id号构成的最大连通子图，并且将子图数据重新加载到GRAPHX当中，此时我们可以 在这个最大连通子图上计算数据的关联路径。本发明算法基本的设计思想是首先获取该连通 图中所有的id节点的编号列表，也就是VertexRDD的节点列表，然后抽取列表中的第一个a 和第二个b构成数据关联路径的起始节点和终止节点，然后从点a出发，并且在VertexRDD 和EdgeRDD构成的图中找出以a出发的边，组成一个路径集合PATH(1)，对PATH(1)中的 每一条路径path：取path的端点x，找出从端点x出发的所有边EDGE(x)，遍历EDGE(x)， 对其中每一条边edge：如果edge不在path中，则将path+edge放入PATH(2)中，如果edge 以及存在在path当中，那么就不重复存储。结束后，再以PATH(2)为路径集合再次遍历，以 此类推，直到path(n)的端点没有任何的边从它出发为止。遍历一遍PATH(n)的集合，把端点 b提取出来，即可以得到a到b的所有关联路径。整个算法是基于GRAPHX的PREGEL模型 进行开发的，使得该算法能够并行化，从而能够大规模分布式并行运算关联数据路径搜索的 问题。本发明的关联数据路径搜索算法，我们可以得到任意两点a和b的关联路径，本算法 的输出是a,b,[path1,path2,path3,path4…,pathn]。如果这两个点之间确实没有关联路径，那么 算法输出的结果为a，b，[]。本发明将此结果记录为relations.txt文件中。本发明首先连接hive 数据库并且连接ConnectedComponentsVertex表格，然后调用发明内置的HQL语句selectno, idsfromConnectedComponentsVertex，获得HDFS存储的关于最大连通子图计算发现的每一个 最大子图，取no＝1，然后序列化ids，序列化ids生成一号最大连通子图的点集合vertexRDD， 然后同理连接HIVE调用发明内置的HQL语句，selectno,edgesfrom ConnectedComponentsedgeswhere{no＝1}序列化edges生成一号最大连通子图的点集合 edgeRDD，然后用vertexRDDedgeRDD构图GRAPHX。然后本发明PREGEL图形计算框架 的思想，然后启动PREGEL计算框架并且将之前构建的图注入到PREGEL计算框架中，并且 配置activeDirection＝EdgeDirection.Either，然后PREGEL启动主导和工作节点，主导负责分 配图处理任务，工作负责计算。然后工作节点负责顺序执行用户定义的超步操作，对于每一 个超步操作我们都由用户定义的function来执行。本次发明的function具体做法是首先指定 一个点作为起始点，然后计算与这个点相关的点并且记录下来id1-id2，将这个结果进行 sendmessage到所有的点中，然后mergemessage是除去计算当中的重复信息，然后再启动下 一个超步超步，这个超步永远都取出上一个超步计算结果的最后一个点，例如上一个超步计 算出来并且分发到各个节点的结果是id1-id2-id3-id4那么这个超步计算所取出的点就是id4， 首先判断这个头尾两个点是否为同一个点，如果是那么就让这个点的计算变为非活跃点，说 明它已经找完一个闭合路径，该点已经找完相关路径了。如果不是相同的点那么计算与id4 关联的点并且记录下来，然后sendmessage到所有的活跃点中，然后mergemessage是除去计 算当中的重复信息，直到所有的点都变成非活跃点程序结束，程序最终获得的是id1在子图 no1的所有连通路径集合t1，然后我们取出子图no1中的所有的点，然后两两组合例如 (IDA,IDB)，在t1的结果集中搜索每一个结果是否包含IDA和IDB，如果有那么我们就把t1 当中相关记录的结果截取以结构IDA,IDB,{[PATH1],[PATH2]…[PATHN]}组织，并且把内容记 录到文件findrelationships当中。

7)关联数据路径结果存储由于本发明在设计之初就希望该发明是一个离线系统，那么 也就意味着真正业务查询时查找两个或者多个关联数据之间的关联路径时，这时候我们是已 经通过上述的步骤1-6都已经完成了计算，然后将步骤六的计算结果存储在HDFS当中，由 HIVE进行统一的查询。那么也就意味着需要将关联数据的搜索路径进行存储和管理。这里涉 及到了数据库连接模块、数据打包模块、数据存储模块。

8)关联数据源的指定和关联路径可视化展示最后本发明提供了一个用户输入和查看的 界面。这里面包括了数据源地址的输入、数据源校验模块、数据源最大连通图展示模块、关 联路径展示模块。用户可以指定RDF数据库的地址和具体的数据集的名称、发明首先会检查 这个数据源是否已经存在，若存在则查询该数据源的最大连通子图，然后利用d3.js和AJAX 技术将结果渲染在页面上，用户可以点击任意两个节点，发明会截取用户点击的id信息，然 后查询关联数据路径结果存储表pathes，启动HIVE连接接口，然后调用发明内置的关联路 径查询模块，该模块是基于HIVEHQL查询语言封装好的HQL查询语句接口，该模块接收 两个参数，就是之前用户点击后系统截取的id1和id2，然后将id1和id2注入到hql查询语句 模块内置的查询语句当中成为查询过滤条件，然后findrelationships表中，id1和id2对应的关 联数据路径，然后将id1，id2和relationpathes内容组合成一个JSON结构的文档，再启动rest 服务接口，将这个JSON结构的内容返回给d3.js，d3.js接收到后台数据之后，通过d3的svg 技术和力导图技术，从而构建数据关联路径的界面展示。

实施案例分析

案例分析首先我们以生物学的基因数据、蛋白数据、go数据为例且由于数据量很大无法 在此一一展开数据的形式和内容因此只是从中抽取了几个三元组来讲解。首先系统会有一个 配置入口，配置数据源的地址datasource、用户名、密码、数据源名称，然后系统会检查数据 源的地址是否已经存在在系统当中，如果没有存在那么系统会自动的去获取其中的rdf数据 资源。这个获取的过程是，首先系统通过jena接口把数据源的地址、用户名、密码、数据源 的名称信息统统都注入到连接数据库接口上，然后数据库连接成功之后我们调用了sparql查 询模块构建了查询语句抽取RDF关联数据，然后开启hdfs文件写入流入口，将内存中读取 的RDF关联数据写入到hdfs当中。当完成该数据源所有的关联数据抽取完毕之后，我们开 启关联数据id分配模块，此时需要一些数据内容作为支撑，那么本次案例分析在讲解时抽取 了极小数量的rdf关联数据来讲解下面的问题。

<http://gcm.wfcc.info/protein/C5501_GLOVI><http://www.w3.org/1999/02/22-rdf-syntax-ns#type>

<http://gcm.wfcc.info/type/protein>

<http://gcm.wfcc.info/protein/C5501_GLOVI><http://gcm.wdcm.org/gcm/xGO>

<http://gcm.wfcc.info/go/GO:0005886>

<http://gcm.wfcc.info/protein/C550_BACSU><http://www.w3.org/1999/02/22-rdf-syntax-ns#type>

<http://gcm.wfcc.info/type/protein>

<http://gcm.wfcc.info/protein/C550_BACSU><http://gcm.wdcm.org/gcm/relation>

<http://gcm.wfcc.info/gene/1058105>

<http://gcm.wfcc.info/gene/1058105><http://gcm.wdcm.org/gcm/belongTo>

<http://gcm.wfcc.info/genome/NC_004526>

<http://gcm.wfcc.info/gene/1058105><http://gcm.wdcm.org/gcm/protein>

<http://gcm.wfcc.info/protein/C5501_GLOVI>

<http://gcm.wfcc.info/gene/1064112><http://www.w3.org/1999/02/22-rdf-syntax-ns#type><

http://gcm.wfcc.info/type/gene>

首先系统会启动hive，然后执行系统内置的hive查询程序，这个查询程序获得存储在hdfs 当中的rdf数据，并且将结果返给系统，系统首先截取每一个rdf的主语和宾语内容并且将主 语和宾语内容去重，然后构建id。以上面内容为例，我们最终可以生成如下的点文档

1<http://gcm.wfcc.info/protein/C5501_GLOVI>

2<http://gcm.wfcc.info/type/protein>

3<http://gcm.wfcc.info/go/GO:0005886>

4<http://gcm.wfcc.info/protein/C550_BACSU>

5<http://gcm.wfcc.info/gene/1058105>

6<http://gcm.wfcc.info/genome/NC_004526>

7<http://gcm.wfcc.info/gene/1064112>

8<http://gcm.wfcc.info/type/gene>

然后在生成如下的边文档

1,2,<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>

1,3,<http://gcm.wdcm.org/gcm/xGO>

4,2,<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>

4,5,<http://gcm.wdcm.org/gcm/relation>

5,6,<http://gcm.wdcm.org/gcm/belongTo>

5,1,<http://gcm.wdcm.org/gcm/protein>

7,8,<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>

然后将点文档和边文档存储在hdfs当中。系统会调用hive接口，读取hdfs的点文档信息 和边文档的内容，然后通过该内容利用graphx的接口构建两种graphx内置的数据结构， vertexRDD和edgeRDD,然后用这两个RDD构成一个graph图形结构并利用pregel计算框架 将graph注入其中开始了计算最大连通图，然后PREGEL启动主导和工作节点，然后工作节 点负责顺序执行用户定义的超步操作，每个超步都计算与该点连通的点和路径并且将计算的 结果传送到所有的点上，所有的点都进行合并并且求接收到的所有消息的集合最小值，这样 就可以求出最大连通图了，那么就以上述例子来说。对于节点1，pregel的超步计算了与1关 联的所有点和路径，那么得到的结果是[1,3,2],然后把计算的结果都发送到了所有的节点上， 对于节点2，他接收到了节点1计算出来的集合并且它也会计算出来与它相关的所有点是[1,4], 这时候他会将自己计算的结果和1传给它的结果进行整合，求出最小集合也就是把重复出现 的点去掉，这时候结果是[1,3,2,4]同理节点5计算的结果是[1,4]，那么此时将结果进行合并， 我们发现[1,3,2,4]和[1,4]的最小完整集合就是[1,3,2,4]，节点3计算出来的结果是[1]将结果进 行合并还是[1,3,2,4]同样的道理计算节点4和节点6最终可以得到新的最小完整集合 [1,3,2,4,5,6],然后节点7的计算出来发现与节点7连接的是节点8此时构建出来 {[1,3,2,4,5,6],[7,8]}从而计算出来两个最大连通子图且这两个最大连通子图均互不相交。然后 将这个结果{[1,3,2,4,5,6],[7,8]}存储在HDFS文件系统当中，这个文件的名称为component。 然后启动hive接入接口，利用查询构建模块构建hive的查询语句，查询得到最大连通图 {[1,3,2,4,5,6],[7,8]}，此时我们发现1,3,2,4,5,6这几个点是连通的，然后构两个hive查询语句 一个查询语句查询edge_url边文档，查询是条件为id1in[1,3,2,4,5,6]或者id2in[1,3,2,4,5,6] 的数据，另外一个查询语句查询点文档id_url，查询语句要求idin[1,3,2,4,5,6]，从而将连个 查询语句查询出来的结果重新构建graph图形结构，然后利用我们的在每一个点上计算跟他 连通的所有点，然后将这个记录发送到图中所有的点上，每个点接收了这个信息之后就将内 容进行合并，最终确定所有的关联路径。那么我们以上述的例子介绍这个过程，系统启动pregel 框架，并且设定最大步长为5，然后启动主导和工作，启动第一个超步，然后计算每一个点 上与他关联的路径，再将结果传输给所有的节点，然后merge操作中会判断头尾是否已经闭 合或者是出现了重复路径如果是的话，那么就将该节点设置为不活跃状态，不再针对该节点 的下一个计算超步，从而直到所有的计算节点的活跃状态为不活跃，那么计算结束。举例子， 例如计算节点1，首先计算与它连接的点，得到{[1,3][1,2][1,5]}计算结束，并且将计算结果传 输给所有的点，他们接收这个结果，等待第二个超步计算,第二步超算计算的是与3、2、5连 接的点，那么3和2和5这个节点已经记录着之前计算出来的{[1,3][1,2][1,5]}这个信息，然 后开启了计算得到的结果是{[3,1]}{[2,4],[2,1]},{[5,1],[5,4],[5,6]}此时再将第二步的超算结 果跟第一步计算完成的结果进行合并，得到{[1,3,1],[1,2,4],[1,2,1],[1,5,1],[1,5,6],[1,5,4]},那么我 们发现1,3,1和1,2,1和1,5,1这三个结构都是一个闭环结果了，所以我们将节点1设置为非活 跃状态，那么下一个超步计算的时候不会计算1这个节点的相连通的点和路径了，然后我们 又把得到的结果[1,3][1,2][1,2,4],[1,5,6],[1,5,4]传输给所有的节点，启动下一个超步，这时候下 一个超步是由之前那个超步启动的，他明确的知道该从第4个节点为活跃节点，那么就从第 4个节点和第6个节点出发，于是他计算与第4和节点6个节点相关的所有点和路径得到的 结果是[1,2,4,5],[1,2,4,2],[1,5,6,5],[1,5,4,2],[1,5,4,5]然后我们将结果传送给所有的节点，再进行 结果合并，得到的结果是 {[1,3],[1,2],[1,2,4],[1,5,6],[1,5,4],[1,2,4,5],[1,2,4,2],[1,5,6,5],[1,5,4,2],[1,5,4,5]}，这个时候没有任 何标识表名是闭环结果或者是路径重复出现，有效并且启动下一个超步，这时两个分别从5 和2出发，那么再重复上述过程得到的结果是{[1,3],[1,2],[1,2,4],[1,5,6],[1,5,4] [1,2,4,5],[1,2,4,2],[1,2,4,5,6],[1,2,4,5,1],[1,2,4,2,4],[1,2,4,2,1]},此时我们发现[1,2,4,5,1], [1,2,4,2,4],[1,2,4,2,1]这三个结果中有两个出现了闭环，有一个出现了重复路径，那么节点1 和4都设置为不活跃状态。由于我们设定最大步长为5所以我们得到的结果为：[1,3], [1,2],[1,5],[1,2,4],[1,5,6],[1,5,4],[1,2,4,5],[1,2,4,2],[1,5,6,5],[1,5,4,2],[1,5,4,5],[1,2,4,5,6], [1,2,4,5,4],[1,2,4,2,5],[1,5,6,5,4],[1,5,4,2,4],[1,5,4,5,6]，这样以1为开头的数据路径已经计算好 了，其他的点也同理得到了计算。最后我们取出结果集中每一份结果，然后取该结果的头和 尾构建result文件，文件的内容格式是：1,3,[1,3]；1,2,[1,2]；1,5,[1,5]；1,4,[1,2,4]；…1,6,[1,5,4,5,6], 从而将结果文件result存放到hdfs当中。然后当界面提出请求需要查询两个点id1和id2的关 联关系的时候，我们只需要打开hive接口，载入result表，然后查询这两个点的对应路径， 例如1和5这两个点的对应路径是[1,5],[1,2,4,5],[1,5,6,5],[1,5,4,5],[1,2,4,2,5]，得到该路径之 后，后台需要将结果保存下来，然后让hive连接点文档，查询这些点的id对应的url是什么， 最终构成的是id对应的url的连接路径，以[1,5]为例，我们查询数据库点文档，然后查看得 到1这个点对应的url和5这个点对应的url最后组成 [<http://gcm.wfcc.info/protein/C5501_GLOVI>,<http://gcm.wfcc.info/gene/1058105>],其他的雷 同接着把结果重新组织成jsonformat，最后将结果传给前台，前台d3.js收到后台发送给他的 结果，然后就将结果展示出来。