1. 基础知识

RDF图：RDF图是由三元组（subject, predicate, object）组成的有向图，subject通过predicate指向object，如图1-1所示为一个RDF图。通常用三元组的数量表示RDF图的大小。

图1-1 RDF图

RDF压缩图：基于RDF图的关键字查询先将图进行压缩为图G=(V, E)。其中节点V包括RDF图中的实体、姓名（标签）、类型信息，边E为RDF中实体之间的关系。图1-1所示RDF压缩图如图1-2所示。

图1-2 压缩图

下文中出现的图均为压缩图。

2. 问题定义

给定一个图G=(V, E)、一个查询Q={w₁, w₂,w₃,···w_m}，w_i为查询关键字。则称集合{r, v₁, v₂,v₃, ···, v_m}为候选结果，其中v_i (0≤i≤m)通过结点r构成一个连通图，其中结点v_i (0≤i≤m)包含了关键字w _i。另g为任意的一个候选，且g的得分s(g)为r到v_i (0≤i≤m)的最短路径之和，取得最小值的候选即为查询结果。

如图2-1所示，图中共有7个结点，v_i为结点标签(名字)，旁边的w_i表示其包含的关键字。给定查询Q1={w₁, w₂,w₃, w₄}，则g = {r=v4, v1, v2, v6, v7}与g` = {r=v3, v1, v2, v6, v7}等均为查询Q1的候选，且有s(g) = 8，s(g`) = 6。易得图中不存在比g`更小的得分，则g`即为查询结果。

图2-1 查询Q1 = {w₁,w₂, w₃, w₄}

3. 分析与求解

3.1 现有方法（Backward）

思想：从包含关键字的节点出发，当第一次相遇到某个节点时，则该节点作为查询结果。流程图如图3-1所示。

显然上述终止条件不能求出正确结果。因此需要将终止条件修改为：

(1) 求出相遇节点

(2) 判断当前节点与其它结点为根的子图得分，若当前节点小，则终止；反之继续寻找下一个相遇节点（具体过程查看ppt动画：http://download.csdn.net/detail/woniu317/7504623）。修正后方法称之为Baseline，流程图如图3-2所示。

图3-1 Backward流程图

图3-2 Baseline流程图

3.2 分析

上述方法无论采用什么样的终止条件都是先找到包含关键字的节点然后一点点进行扩展，直到找到相交节点（这里的相交指满足修正后的条件）则终止。如图3-3所示，查询Q₂= {1, 2}。

图3-3 Backward示意图

显然该图中关键字1的个数大于2的个数，假设图中每个圆中均包含10000个结点，则查找到结果共要10000*5=50000次计算。而有效的计算为10000*2=20000次，因此有效的计算只占0.4，即 60%的计算都是无用的。

基于上述分析我们可以选择一次走多步（将多个节点当做一个节点来处理）来减少无效操作。例将100个结点当做一个块来处理，则共需要计算100*5+2*10000=20500，即扩展走100次左下角两个圆相遇，则只需在这两个小圆里再一个个结点处理。此时，有效操作占0.98。处理的过程示意图如图3-4所示。

图3-4 基于分块思想的关键字查询示意图

剖析：该方法需要1. 划分子图；2. 估计到子图的最小最大距离。至此可以得出按照分块的思想来处理图的流程如图3-5所示。

图3-5 分块求解关键字查询流程图

3.3 分块

按照节点类型（type）进行划分。换分步骤如下：

(1) 将节点按照类型进行分类；

(2) 按照类别一次访问每个结点，并以该节点为根求得α hop邻居，构成一块。（注意块与块之间只允许存在相交节点，而不存在相交边，即一条边只出现在一个快中）

图1-2所示的RDF图划分1-hop块如图3-6所示。

图3-6 1-hop块

此种规则划分的结果示意图如图3-7所示。

图3-7 块之间关系示意图

3.4 块中关系记录

由定义以及3.2的分析可知我们只需关注块内节点之间的最短路径，因此最好是能够将每块内节点之间的关系记录下来，但全部记录索引空间太大，因此需要充分挖掘块与块之间的关系。

3.4.1 同形态

如图3-8所示，其中图A中的每一个节点均可在B中找到对应结点，且对应的定点之间边也相同，则称A为B的同形态。

图3-8 同形态

A图的性质可通过B图来获取，因此A图无需建立最短路径索引，只需指引到B中相应位置即可。

3.4.2 核(core)

如图3-9所示，(1) 图C是图D的同形态，(2) D是C的同形态，(3) C是满足前两条中最小的图，则称C是D的核。易得，只需记录C即可得到D的性质。

图3-9 核

因此分块与记录块性质过程如图3-10所示。

图3-10 分块记录流程图

3.5 覆盖树

不难得出3-9中求核与判断同形态关系均属于子图同构问题，即NP-hard。可通过求解覆盖树来较少该问题的求解难度。

如图3-11所示，左边为一个块，将除根节点外的所有节点分为入度个节点，比如T₄拆封成3个节点。

图3-11 覆盖树

因此只需存储覆盖树的核即可。3-10中的流程图中c=core(p_i)变为c = core(CT(p_i))。

3.6 最短路径估计

3.6.1 块内估计

如图3-12A所示，其中任意两点R, P之间最短路径可由三角不等式限定，即d(R, P) ≤ d(S, R) + d(S, P)，d(R, P) ≥ |d(S, R) – d(S, P)|。易得图3-12中A为B的同形态，则在A中存在的边均可在B中找到对应的边，因此有d(R, P) ≥ d(f(R)=B.R, f(P)=B.P)。即A中最短路径界可以通过B计算。

图3-12 块内最短路径估计

但值得注意的是summary中存储的为覆盖树，即不存在块的同形态。因此定义了join操作。（具体过程参看ppt：http://download.csdn.net/detail/woniu317/7504623）

3.6.2 块间估计

如图3-13所示，通过v₅结点到达左边的块，从v₉结点到达右边的块。设到达左边块的上下界分别为d_lower与d_upper，则易得到达右边块的上下界分别为d_lower+lower(v₅,v₉)与d_upper+upper(v₅,v₉)。

图3-13

3.7 查询

查询过程见3.2，即现在块级别求解相遇节点得出结果子图，进一步在该子图上求解查询结果。

参考文献：

1. ScalableKeyword Search on Large RDF Data