#gStore-weekly | SPARQL 执行过程中高级查询函数的求值（下）

SPARQL 执行过程中高级查询函数的求值（下）

1.1 上期回顾

在上篇中，我们介绍了 GeneralEvaluation::getFinalResult 函数中与高级查询函数相关的逻辑，其在查询的 WHERE 语句执行完成后从结果中提取出高级查询函数的各参数；对于每组有效的参数，调用 PathQueryHandler 类中对应的成员函数，得到高级查询函数的执行结果。

本篇中，我们将介绍 PathQueryHandler 类（Query/PathQueryHandler.[h|cpp]）的基本功能，及其中重要的成员变量和成员函数。

1.2 PathQueryHandler 类

1.2.1 基本功能

PathQueryHandler 类是 gStore 中高级查询函数的执行入口，负责将当前装载数据库的全量 RDF 图数据以压缩稀疏行（Compressed Sparse Row, CSR）的形式读入到内存中（目的是在执行高级分析型查询的过程中剔除大量 I/O 带来的开销；目前假设图数据能够全量读入内存，暂未处理图数据占用空间大于内存限制的情形），并在其上通过调用成员函数来执行相应类型的高级查询。

1.2.2 重要的成员变量：csr

PathQueryHandler 类的成员变量 csr 即是上述用于在内存中存储全量图数据的 CSR 结构，其为 CSR 类（Database/CSR.h）指针。一般而言，一个 CSR 结构由 id2vid 、offset_list 、adjacency_list 三部分构成，如下图所示：

其中 id2vid 表示从下标到结点 ID 的映射（如下标 0 对应的结点 ID 为 1）；adjacency_list 连续依次给出 id2vid 中各结点的出邻接列表；offset_list 则给出 adjacency_list 中各结点邻接列表起始的偏移量（例如 offset_list[0] == 0 且 offset_list[1] == 3 ，表示下标 0 对应的结点的邻接列表以 adjacency_list[0] 起始，以 adjacency_list[3 - 1] 为止；offset_list[1] == offset_list[2] == 3 ，表示下标 1 对应的结点没有出邻居）。

CSR 类对象在此基础上添加了 vid2id （std::map 类型），为 id2vid 的逆映射，能对某些操作以空间换时间。此外，由于 RDF 图中有多种谓词（可看作边标签），一些高级查询函数中又对允许出现的谓词有限制，因此上述四个构成部分均为 std::vector 或 std::map 类指针，实质上对每个谓词会存储一个其诱导子图（induced subgraph，即将原图中的对应谓词边及其所关联的结点抽取出来得到的子图）对应的 CSR ；以谓词 ID 为下标即可将对应的 CSR 取出。

PathQueryHandler 类中的 CSR 类指针实际上指向含有两个元素的 CSR 数组，分别表示出、入邻接列表。

PathQueryHandler 类中提供了一系列基于 CSR 类访问图的基本操作，如获取总结点或总边数、获取结点邻居列表等，足以满足高级查询（即较复杂的图算法）对图的访问需求。在与高级查询函数对应的PathQueryHandler 类成员函数中均调用了这些基本操作。未来即将介绍的自定义算子函数中，用户也可调用这些基本操作来实现自己的图算法。

1.2.3 与高级查询函数对应的成员函数：以 shortestPath 为例

PathQueryHandler::shortestPath 为最短路径查询函数。其参数包括：

• int uid ：起始结点 u 的 ID ；
• int vid ：目标结点 v 的 ID ；
• bool directed ：表示是否仅返回有向路径（若为 false ，则表示可返回无向或有向路径，无向路径即为将图中所有边视作双向后得到的任意路径）；
• const vector &pred_set ：路径中边上允许出现的谓词 ID 集合。

与上篇对照可以发现，这些参数与高级查询函数的 SPARQL 扩展语法中的参数是一一对应的。

以下我们以此函数为例，呈现一个典型的高级查询函数的实现方式。

由于考虑不带权最短路径（边权统一视为 1），因此 shortestPath 实现为双向宽度优先搜索（Bidirectional Breadth-First Search, BiBFS）。其中关键的数据结构为：

• q_u, q_v ：分别从结点 u 、v 出发的前向、后向（即与原图中边的方向相反）BFS 的队列；
• dis_u, dis_v ：分别从结点 u 、v 出发分别通过前向、后向 BFS 找到的到某结点的最短路径长度；
• meet_node ：从结点 u 、v 出发的前向、后向 BFS 相遇的结点（若 u 到 v 可达）；
• flag ：布尔值，表示 meet_node 的值是否有效（若为假，则尚未找到从 u 到 v 的路径（即尚未找到相遇结点），或 u 到 v 不可达）。

函数的主体为以下 while 循环：

while (flag == 0 && (!q_u.empty() || !q_v.empty()))
{
	queue new_q_u;
	while (!q_u.empty() && flag == 0) { ... }
	q_u = new_q_u;
	
	queue new_q_v;
	while (!q_v.empty() && flag == 0) { ... }
	q_v = new_q_v;
}
1
2
3
4
5
6
7
8
9
10

可见最外层 while 循环的条件为：尚未找到从 u 到 v 的路径（flag == 0），且 BFS 队列 q_u 和 q_v 中至少有一者不为空；内层还有两个 while 循环，分别表示从 u 出发的一轮前向 BFS 和从 v 出发的一轮后向 BFS 。接下来我们详细分析从 u 出发的一轮前向 BFS 的代码：

while (!q_u.empty() && flag == 0)
{
  int temp_u = q_u.front();

  q_u.pop();
  for (int i = 0; i < num_of_pred; ++i)
  {
    int x = pred_set[i];
    int num = getOutSize(temp_u, x);
    for (int j = 0; j < num; ++j)
    {
      int t = getOutVertID(temp_u, x, j); // get the node

      if (dis_v.find(t) != dis_v.end())
      {
        flag = 1;
        meet_node = t;
        dis_u[t] = dis_u[temp_u] + 1;
        break;
      } // get the meet node

      if (dis_u.find(t) != dis_u.end())
        continue; // has visited before

      new_q_u.push(t);
      dis_u[t] = dis_u[temp_u] + 1;
    }
    if (flag)
      break;
    if (directed)
      continue;

    num = getInSize(temp_u, x);
    for (int j = 0; j < num; ++j)
    {
      int t = getInVertID(temp_u, x, j); // get the node

      if (dis_v.find(t) != dis_v.end())
      {
        flag = 1;
        meet_node = t;
        dis_u[t] = dis_u[temp_u] + 1;
        break;
      } // get the meet node

      if (dis_u.find(t) != dis_u.end())
        continue; // has visited before

      new_q_u.push(t);
      dis_u[t] = dis_u[temp_u] + 1;
    }
    if (flag)
      break;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

上述代码首先取出队列 q_u 的队首元素，即是准备进行拓展的当前结点。下面的 for 循环对当前结点以每种谓词为标签的边进行拓展（若 directed == true ，则仅拓展出边；注意 for 循环中的 if (directed) continue;。若 directed == false ，则出、入边均拓展）。以拓展出边为例，通过调用 getOutSize 函数获取当前结点以当前谓词为标签的出边数；对每条这样的出边，通过调用 getOutVertID 函数获取对应的出邻居。若获取到的出邻居在 dis_u 中已有值，说明此出邻居已被前向 BFS 访问过，则跳过；若此出邻居在 dis_v 中已有值，说明此出邻居已被后向 BFS 访问过，其为前、后向 BFS 相遇的结点（也就说明从 u 到 v 的最短路径已找到），则相应设置 flag 、meet_node 和 dis_u 值，跳出循环；否则，设置出邻居的 dis_u 值，并将其放入备用队列 new_q_u 中，等待下一轮拓展。

完成主体 for 循环后，shortestPath 函数中还有一段逻辑用于由 meet_node 复原从 u 到 v 的最短路径，此处不再详述。

1.3 小结

本篇介绍了 SPARQL 执行过程中实际进行高级查询函数求值的 PathQueryHandler 类，的基本功能，其中重要的成员变量 csr ，及以 PathQueryHandler::shortestPath 为例的、与高级查询函数一一对应的成员函数，建议在阅读的同时结合源码 Database/CSR.h 、 Query/PathQueryHandler.[h|cpp] ，会更容易理解。接下来我们拟分析 SPARQL 执行过程中自定义算子函数的处理机制。