一种基于实体图社团结构的RDF关键词查询方法

摘要

本发明公开了一种基于实体图社团结构的RDF关键词查询方法，包括以下步骤：1)构建RDF资源实体，并且构建RDF资源实体间关系，从而实现RDF实体图的构建；2)对RDF实体图进行层次社团发现，得到RDF实体图的社团结构树，并基于实体图社团结构树构建实体图社团结构索引；3)使用实体关键词倒排索引实现关键词查询到RDF资源实体的映射；对不同关键词对应的实体进行组合，并通过RDF资源实体与关键词的相关度对RDF资源实体组合进行筛选，得到候选RDF资源实体组合集合；对于RDF资源实体组合集合中的每一个RDF资源实体组合，根据社团结构索引，构建组合中实体之间的关系，并作为查询结果添加到结果集中；依据查询结果紧凑度，对结果集进行排序，返回给用户。

说明书

技术领域

本发明涉及一种RDF关键词查询方法，具体涉及一种基于实体图社 团结构的RDF关键词查询方法。

背景技术

随着语义网的不断发展，RDF(Resource Description Framework，是 一种用于描述网络上的信息和资源的标记语言，为语义网提供了描述资 源的统一标准)作为语义网中信息和知识的载体其规模急剧增长，普通 用户对于RDF数据查询需求也不断增加。传统的基于结构化查询语言的 RDF数据查询，要求用户掌握RDF数据模式和查询语言语法规则，难 以在普通用户中推广。因此，面对大规模的RDF数据，借鉴传统信息检 索技术，提供高效的关键词查询可以帮助普通用户方便地检索RDF数据 资源。但现有的技术均没有涉及RDF关键词查询方法。

发明内容

本发明的目的在于克服上述现有技术的缺点，提供了一种基于实体 图社团结构的RDF关键词查询方法，该方法可以实现RDF关键词的查询。

为达到上述目的，本发明所述的基于实体图社团结构的RDF关键词 查询方法包括以下步骤：

1)判断RDF三元组集合T的谓词类别，并根据谓词类别的判断结果 将谓词分为属性关系及实体关系，再遍历所有的RDF三元组集合T，得 各RDF三元组集合T对应的RDF资源实体，然后通过构建各RDF资源实 体间的关系得RDF实体图，同时构建各RDF资源实体的虚拟文档；

2)通过基于Fast Unfold算法的层次社团发现算法对RDF实体图进 行社团发现，得到RDF实体图的社团结构树，然后基于实体图的社团结 构树构建实体图社团结构索引；

3)解析用户查询的信息，得关键词集合Q＝{k₁，k₂，...，k_i，...，k_m}，其中， k_i为关键词集合Q中的第i个关键词，m为关键词的总个数，使用实体 关键词倒排索引实现关键词到RDF资源实体的映射，得到各关键词对应 的RDF资源实体集合，再对各关键词对应的RDF资源实体集合中的RDF 资源实体进行组合，并通过RDF资源实体与关键词的相关度对RDF资源 实体组合进行筛选，得到候选RDF资源实体组合集合，然后对于候选RDF 资源实体组合集合中的每一个RDF资源实体组合根据社团结构索引构建 候选RDF资源实体组合集合中各RDF资源实体之间的关系，并将候选RDF 资源实体组合集合中各RDF资源实体之间的关系作为查询结果添加到查 询结果集中，然后依据查询结果的紧凑度对查询结果集中查询结果进行 排序，并将排序结果返回给用户。

所述RDF三元组集合T中的RDF三元组为

(subject，predicate，object)   (1)

其中，subject∈U∪B，predicate∈U，object∈U∪B∪L，U、B及L分别 为URI reference集合、空节点集合及文字描述节点集合；

所述RDF资源实体为：

(uri_subject，A_subject)   (2)

其中，uri_subject为用于唯一标识RDF资源实体的URI，S_object为RDF三 元组集合T中包含的object集合，S_subject为RDF三元组集合T中包含的 subject集合，将RDF资源实体集合记作Entity(T)， RDF实体图记作G^l(V^l，E^l)，其中，V^l为RDF资源实体对应的节点集合，E^l为RDF实体图中边的集合，且满足E^l＝{(u^l，v^l)|(u^l，p，v^l)∈T，u^l，v^l∈V^l，p∈U_p}， U_p为RDF三元组集合T中包含的谓词集合。

步骤1)中通过构建各RDF资源实体间的关系得RDF实体图的具体 操作如下：

1)通过Jena将RDF格式文档集转换为三元组格式，得RDF三元组 集合T，同时记录RDF资源实体编号id；

2)判断RDF三元组集合的谓词类别，根据谓词类别的判断结果将谓 词分为属性关系及实体关系，遍历所有RDF三元组集合T，根据各RDF 三元组集合T的谓词类别将各RDF三元组合集合T的谓词添加到属性关 系集合AR或实体关系集合ER中；

3)遍历RDF三元组集合T，对于各RDF三元组集合T中的每一个RDF 三元组(subject，predicate，object)，当RDF资源实体集合Entity(T)中不包含 subject时，则id加1，并将映射关系(subject，id)添加到RDF资源实体集合 Entity(T)中，当predicate∈ER，则将RDF资源实体关系(subject，object)以及 predicate添加到RDF资源实体关系集合ERSet(T)中，其中对于第一个RDF 资源实体集合Entity(T)，id等于0；

4)遍历各RDF资源实体集合Entity(T)，将各RDF资源实体编号及URI 按序输出到Pajek格式文档P中，然后，遍历RDF资源实体关系集合 ERSet(T)，将各RDF资源实体间的关系输出到文档P中，得到RDF实体图。

步骤1)中构建各RDF资源实体的虚拟文档的具体操作如下：

1)对各RDF资源实体集合Entity(T)中的每一个subject创建对应的 RDF资源实体(uri_subject，A_subject)；

2)遍历所有的RDF三元组集合T，当predicate∈AR且则将object添加到subject对应RDF资源实体(uri_subject，A_subject)的关联属性集合 A_subject中；

3)提取各RDF资源实体(uri_subject，A_subject)中的文本属性，然后根据各 RDF资源实体(uri_subject，A_subject)中的文本属性生成实体虚拟文档集合 VDoc(T)，则RDF资源实体(uri_subject，A_subject)对应的虚拟文档VDoc(entity)为：

VDoc(entity)＝label(uri_entity)+literal(attris_entity)   (3)

其中，label(uri_entity)为uri_entity中包含的反映实体主题的标签， literal(attris_entity)为RDF资源实体(uri_subject，A_subject)中包含的文字描述属性的集 合。

步骤2)中通过基于Fast Unfold算法的层次社团发现算法对RDF 实体图进行社团发现的具体操作为：

1)将RDF实体图转换为无向图，并将转换后的RDF实体图作为社团 结构树C-Tree的根社团节点加入到待分析社团节点队列CCNQ中，社团 结构树C-Tree的根社团节点为：

CNode(V_C，Children，Parent)   (4)

其中，V_C为社团节点包含的RDF资源实体集合Entity(T)，Children为 社团节点的子社团节点集合，Parent为社团节点的父社团节点；

2)从待分析社团节点队列CCNQ中取出队首节点CH，使用Fast  Unfold算法对队首节点CH对应的RDF实体图或子图进行社团划分，当 得到的社团划分结果对应的模块度值均大于或等于时，则创建各社团 对应的社团节点，然后将社团节点作为队首节点CH的子社团节点加入待 分析社团节点队列CCNQ中；

3)对待分析社团节点队列CCNQ中的所有节点进行步骤(2)的操作， 直到待分析社团节点队列CCNQ为空，得到领域知识地图对应的社团结 构树C-Tree，完成对RDF实体图的社团发现，其中

C-Tree(CNodeSet，croot，n)   (5)

其中，CNodeSet为社团结构树的社团节点集合，croot为社团结构树 的根社团节点，n为社团节点数。

步骤2)中基于实体图社团结构树构建实体图社团结构索引的具体 操作为：

1)将社团结构树C-Tree的根节点croot加入到社团节点队列CQ，设 H为社团节点队列CQ的队首社团，CEMap(c)为社团结构树C-Tree中社团 c到RDF资源实体集合的映射，CSMap(c)为社团结构树C-Tree中社团c与 社团规模的映射，ECMap(entity)为RDF资源实体到其所属社团的映射；

2)从社团节点队列CQ中取出队首社团H，计算队首社团H的节点 个数，然后队首社团H的节点个数添加到CSMap(c)中，遍历队首社团H 的所有RDF资源实体，并在ECMap(entity)中添加RDF资源实体entity到 所属社团H的映射，同时将RDF资源实体(uri_subject，A_subject)添加到社团 CEMap(H)对应的映射中，将社团结构树C-Tree中队首社团H包含的子 社团节点加入到社团节点队列CQ中；

3)重复步骤2)直至社团节点队列CQ为空为止；

4)遍历CEMap(c)、CSMap(c)及ECMap(entity)，分别得到实体索引、 社团规模及实体到社团索引三类索引信息。

步骤3)对各关键词对应的RDF资源实体集合中的RDF资源实体进 行组合的具体操作为：

1)使用Lucene查询关键词k_i对应的RDF资源实体，得到关键词k_i对 应的RDF资源实体集合L_i，并然后将所述RDF资源实体集合L_i添加到关 键实体列表list(L_i)中；

2)将关键实体列表list(L_i)中不同RDF资源实体集合中的RDF资源实 体进行组合，到关键节点组合{(n₁，n₂，...，n_i，...，n_m)|n_i∈L_i}，然后根据关键节 点组合{(n₁，n₂，...，n_i，...，n_m)|n_i∈L_i}得所有关键实体组合的集合KNCSet，对于 KNCSet中的关键节点组合根据查询关键词的相关度进行排序，选取前k 个相关度最大的关键词加入到目标关键节点组合集合中。

本发明具有以下有益效果：

本发明所述的基于实体图社团结构的RDF关键词查询方法在查询过 程中，先遍历RDF三元组合集合，构建RDF资源实体，并构建各RDF资 源实体之间的关系，从而得到RDF实体图，然后根据RDF实体图得到RDF 实体图的社团结构树，并给予RDF实体图的社团结构树构建实体图社团 结构索引，再使用实体关键词倒排索引实现关键词查询到RDF资源实体 的映射，并对不同关键词对应的实体进行组合，然后通过RDF资源实体 与关键词的相关度对RDF资源实体组合进行筛选，得到候选RDF资源 实体组合集合，最后对于RDF资源实体组合集合中的每一个RDF资源 实体组合根据社团结构索引构建组合中实体之间的关系，并组合中实体 之间的关系作为查询结果添加到结果集中，然后依据查询结果的紧凑度 对结果集进行排序，并将排序的结果返回给用户，从而实现RDF关键词 的查询，同时查询的简单，易于操作，并且效率高。

附图说明

图1为本发明RDF实体图构建流程图；

图2为本发明RDF虚拟文档构建流程图；

图3为本发明RDF实体图社团发现流程图；

图4为本发明RDF社团结构索引构建流程图；

图5为图4所示构建的社团结构索引的基于HBase的表模式；

图6为本发明基于社团结构的关键词查询流程图。

具体实施方式

下面结合附图对本发明做进一步详细描述：

本发明所述的基于实体图社团结构的RDF关键词查询方法包括以下 步骤：

1)判断RDF三元组集合T的谓词类别，并根据谓词类别的判断结果 将谓词分为属性关系及实体关系，再遍历所有的RDF三元组集合T，得 各RDF三元组集合T对应的RDF资源实体，然后通过构建各RDF资源实 体间的关系得RDF实体图，同时构建各RDF资源实体的虚拟文档；

2)通过基于Fast Unfold算法的层次社团发现算法对RDF实体图进 行社团发现，得到RDF实体图的社团结构树，然后基于实体图的社团结 构树构建实体图社团结构索引；

3)解析用户查询的信息，得关键词集合Q＝{k₁，k₂，...，k_i，...，k_m}，其中， k_i为关键词集合Q中的第i个关键词，m为关键词的总个数，使用实体 关键词倒排索引实现关键词到RDF资源实体的映射，得到各关键词对应 的RDF资源实体集合，再对各关键词对应的RDF资源实体集合中的RDF 资源实体进行组合，并通过RDF资源实体与关键词的相关度对RDF资源 实体组合进行筛选，得到候选RDF资源实体组合集合，然后对于候选RDF 资源实体组合集合中的每一个RDF资源实体组合根据社团结构索引构建 候选RDF资源实体组合集合中各RDF资源实体之间的关系，并将候选RDF 资源实体组合集合中各RDF资源实体之间的关系作为查询结果添加到查 询结果集中，然后依据查询结果的紧凑度对查询结果集中查询结果进行 排序，并将排序结果返回给用户。

所述RDF三元组集合T中的RDF三元组为

(subject，predicate，object)   (1)

其中，subjecr∈U∪B，predicate∈U，object∈U∪B∪L，U、B及L分别 为URI reference集合、空节点集合及文字描述节点集合；

所述RDF资源实体为：

(uri_subject，A_subject)   (2)

其中，uri_subject为用于唯一标识RDF资源实体的URI，S_object为RDF三 元组集合T中包含的object集合，S_subject为RDF三元组集合T中包含的 subject集合，将RDF资源实体集合记作Entity(T)， RDF实体图记作G^l(V^l，E^l)，其中，V^l为RDF资源实体对应的节点集合，E^l为RDF实体图中边的集合，且满足E^l＝{(u^l，v^l)|(u^l，p，v^l)∈T，u^l，v^l∈V^l，p∈U_p}， U_p为RDF三元组集合T中包含的谓词集合。

参考图1，步骤1)中通过构建各RDF资源实体间的关系得RDF实体 图的具体操作如下：

1)通过Jena将RDF格式文档集转换为三元组格式，得RDF三元组 集合T，同时记录RDF资源实体编号id；

2)判断RDF三元组集合的谓词类别，根据谓词类别的判断结果将谓 词分为属性关系及实体关系，遍历所有RDF三元组集合T，根据各RDF 三元组集合T的谓词类别将各RDF三元组合集合T的谓词添加到属性关 系集合AR或实体关系集合ER中；

3)遍历RDF三元组集合T，对于各RDF三元组集合T中的每一个RDF 三元组(subject，predicate，object)，当RDF资源实体集合Entity(T)中不包含 subject时，则id加1，并将映射关系(subject，id)添加到RDF资源实体集合 Entity(T)中，当predicate∈ER，则将RDF资源实体关系(subject，object)以及 predicate添加到RDF资源实体关系集合ERSet(T)中，其中对于第一个RDF 资源实体集合Entity(T)，id等于0；

4)遍历各RDF资源实体集合Entity(T)，将各RDF资源实体编号及URI 按序输出到Pajek格式文档P中，然后，遍历RDF资源实体关系集合 ERSet(T)，将各RDF资源实体间的关系输出到文档P中，得到RDF实体图。

参考图2，步骤1)中构建各RDF资源实体的虚拟文档的具体操作 如下：

1)对各RDF资源实体集合Entity(T)中的每一个subject创建对应的 RDF资源实体(uri_subject，A_subject)；

2)遍历所有的RDF三元组集合T，当predicate∈AR且则将object添加到subject对应RDF资源实体(uri_subject，A_subject)的关联属性集合 A_subject中；

3)提取各RDF资源实体(uri_subject，A_subject)中的文本属性，然后根据各 RDF资源实体(uri_subject，A_subject)中的文本属性生成实体虚拟文档集合 VDoc(T)，则RDF资源实体(uri_subject，A_subject)对应的虚拟文档VDoc(entity)为：

VDoc(entity)＝label(uri_entity)+literal(attris_entity)   (3)

其中，label(uri_entity)为uri_entity中包含的反映实体主题的标签， literal(attris_entity)为RDF资源实体(uri_subject，A_subject)中包含的文字描述属性的集 合。

参考图3，步骤2)中通过基于Fast Unfold算法的层次社团发现算 法对RDF实体图进行社团发现的具体操作为：

1)将RDF实体图转换为无向图，并将转换后的RDF实体图作为社团 结构树C-Tree的根社团节点加入到待分析社团节点队列CCNQ中，社团 结构树C-Tree的根社团节点为：

CNode(V_C，Children，Parent)   (4)

其中，V_C为社团节点包含的RDF资源实体集合Entity(T)，Children为 社团节点的子社团节点集合，Parent为社团节点的父社团节点；

2)从待分析社团节点队列CCNQ中取出队首节点CH，使用Fast  Unfold算法对队首节点CH对应的RDF实体图或子图进行社团划分，当 得到的社团划分结果对应的模块度值均大于或等于时，则创建各社团 对应的社团节点，然后将社团节点作为队首节点CH的子社团节点加入待 分析社团节点队列CCNQ中；

3)对待分析社团节点队列CCNQ中的所有节点进行步骤2)的操作， 直到CCNQ队列为空，得到领域知识地图对应的社团结构树C-Tree，完 成对RDF实体图的社团发现，其中

C-Tree(CNodeSet，croot，n)   (5)

其中，CNodeSet为社团结构树的社团节点集合，croot为社团结构树 的根社团节点，n为社团节点数。

参考图4及图5，步骤2)中基于实体图社团结构树构建实体图社团 结构索引的具体操作为：

1)将社团结构树C-Tree的根节点croot加入到社团节点队列CQ，设 H为社团节点队列CQ的队首社团，CEMap(c)为社团结构树C-Tree中社团 c到RDF资源实体集合的映射，CSMap(c)为社团结构树C-Tree中社团c与 社团规模的映射，ECMap(entity)为RDF资源实体到其所属社团的映射；

2)从社团节点队列CQ中取出队首社团H，计算队首社团H的节点 个数，然后队首社团H的节点个数添加到CSMap(c)中，遍历队首社团H 的所有RDF资源实体，并在ECMap(entity)中添加RDF资源实体entity到 所属社团H的映射，同时将RDF资源实体(uri_subject，A_subject)添加到社团 CEMap(H)对应的映射中，将社团结构树C-Tree中队首社团H包含的子 社团节点加入到社团节点队列CQ中；

3)重复步骤2)直至社团节点队列CQ为空为止；

4)遍历CEMap(c)、CSMap(c)及ECMap(entity)，分别得到实体索引、 社团规模及实体到社团索引三类索引信息。

步骤3)对各关键词对应的RDF资源实体集合中的实体进行组合的 具体操作为：

1)使用Lucene查询关键词k_i对应的RDF实体，得到关键词k_i对应 的实体集合L_i，并然后将所述实体集合L_i添加到关键实体列表list(L_i)中；

2)将关键实体列表list(L_i)中不同实体集合中的实体进行组合，到关 键节点组合{(n₁，n₂，...，n_i，...，n_m)|n_i∈L_i}，然后根据关键节点组合 {(n₁，n₂，...，n_i，...，n_m)|n_i∈L_i}得所有关键实体组合的集合KNCSet，对于 KNCSet中的关键节点组合根据查询关键词的相关度进行排序，选取前k 个相关度最大的关键词加入到目标关键节点组合集合中。

参考图6，步骤3)对各关键词对应的RDF资源实体集合中的RDF 资源实体进行组合的具体操作为：

1)使用Lucene查询关键词k_i对应的RDF资源实体，得到关键词k_i对 应的RDF资源实体集合L_i，并然后将所述RDF资源实体集合L_i添加到关 键实体列表list(L_i)中；

2)将关键实体列表list(L_i)中不同RDF资源实体集合中的RDF资源实 体进行组合，到关键节点组合{(n₁，n₂，...，n_i，...，n_m)|n_i∈L_i}，然后根据关键节 点组合{(n₁，n₂，...，n_i，...，n_m)|n_i∈L_i}得所有关键实体组合的集合KNCSet，对于 KNCSet中的关键节点组合根据查询关键词的相关度进行排序，选取前k 个相关度最大的关键词加入到目标关键节点组合集合中。

其中，定关键节点集合K＝{l₁，l₂，...，l_m}，D＝{K₁，K₂，....，K_s}为K的一个非 空子集集合，c_i表示K_i中关键节点的共属社团，且满足 则成D是集合K的一个覆盖，D中的子集 合个数s称为覆盖层次。

给定的关键节点集合K＝{l₁，l₂，...，l_m}，K的t-层覆盖D_t＝{K₁，K₂，....，K_t}中 的任一关键节点子集合K_i，不存在l_j∈K可以添加K_i到中，构成新的t- 层覆盖D′_t，则称D_t为t-层最大覆盖。

依据查询结果子图的结构紧凑性对ST中的查询结果进行排序，并将 排序后的结果返回。查询结果结构紧凑性定义如下：

$\mathrm{score}\left(g^r\right)=1/\underset{n_i,n_j\in K\left(g^r\right)}{\Sigma }\mathrm{dist}(n_i,n_j)---\left(6\right)$

其中，g^r表示查询得到的一个结果子图；K(g^r)表示g^r包括的关键 节点集合；dist(n_i，n_j)表示g^r中任意两个关键节点n_i和n_j的路径长度。