论文导读 | 图上视图的研究

图谱学苑 2023-01-07

694

在关系型数据库中，视图是一项常见的技术。它常用于加速查询（对查询进行抽取，获取公共内容，进行物化，从而加速查询），进行数据分析（用户对自己感兴趣的内容构建视图）以及数据权限访问等。近年也有一些在图数据库上进行的视图研究。本次报告将介绍几篇关于图上视图的工作，希望对大家有所帮助。

这篇工作关注于使用视图加速子图匹配问题，它所使用的子图匹配定义是图模拟（graph simulation），这是一种相较于宽松的子图匹配定义。简单来说，在图模拟匹配语义下，查询图中的节点 u 匹配数据图中的节点 v，当且仅当 1）u 和 v 的标签相同；2）u 的任何后继都能够被 v 的某个后继所匹配。

这篇工作的整体思路是：给定一系列预设的视图，判断图模拟查询能否被这些视图所加速。

接下来，我们给出视图的描述，视图的内容是由模式图和模式图所匹配的结果所组成的，如下图（b）中所展现的。

有了视图的定义，我们需要判断一个查询是否能够使用预设的视图集合进行加速，或者说查询的结果是否包含于视图集合之中。这个是容易判断的，我们只需要使用视图的模式对查询进行匹配。然后判断该查询是否能够被这些视图模式所覆盖，如下图的例子，其中蓝色边框、箭头和红色边框、箭头标识出了视图如何覆盖查询的。有了覆盖关系，查询的查找范围也缩小了，查询图的每条边的候选集就是覆盖它的视图的模式中的边所匹配的结果。例如：PMàDBA1 这条边被 e1 覆盖，那么他的匹配候选集就是

。在此候选集的基础上在进行图模拟构建，从而回答了查询。

如果一个查询能够被预设的视图所回答，我们称它被这些视图所包含。有时，回答一个查询并不需要所有的视图，如下图所示，Qs 只需要之中的某几个视图即可被覆盖。因此，文章提出了极小覆盖的优化，即删除视图集合中所使用的视图，直到再删除一个视图会导致视图集合无法包含查询。除此之外，文章还提出了最小覆盖，即选取数量最少的视图，使得查询能够被覆盖，这个问题是 NP-hard 的，并且是 APX-hard 的，因此文章提出了一个 log-近似的思路来解决该问题。

当查询不被预设的视图集合所覆盖时，文章提出了最大包含重写的方式。依然考虑使用视图去覆盖查询，因为查询不会被预设的视图集合所覆盖，所有存在一些边无法被任何一个视图所覆盖，删掉这些边，剩下的内容就是最大包含重写的查询了。最大包含重写的查询可以用于作为查询的近似回答。

在实验中，作者比较了使用视图和不使用视图的效率。如下图所示：其中Match是不使用视图加速，

是使用极小覆盖的覆盖方法进行视图加速，而

是使用最小覆盖的覆盖方法进行视图加速。可以看出视图能够起到加速的效果。

第二篇相关工作是发表在 SIGMOD‘21 上的一篇工作。这篇工作构建一个系统Graphsurge，用来对静态图进行视图和快照分析。Graphsurge提供了两个用户接口，一个用来进行视图选取，另外一个用于在选取的视图上进行分析。这两个接口构建了一个工作流：用户先进行视图的选取，对于自己感兴趣的内容就选取出来作为视图。接着，对这些视图进行统一的算法分析。由于，视图是最开始确定的，因此对视图进行分析时，Graphsurge可以共享一些计算。

下图是该系统的架构，绿色的方框是前文所提到的两个用户接口，其中视图选取的接口是使用文章所定义的 Graph View Definition Language 进行描述。而算法分析的接口是提供的 Rust 语言接口。

Graphsurge 会把用户输入的视图以差分的形式存储下来，例如：视图集合为

，Graphsurge会存储为

的形式。

Graphsurge 是基于一个带时间戳的并行计算系统TD（timely dataflow）构建的。这个系统支持处理流数据，但同时支持BSP，这得益于它的时间戳设置。每个数据都会有个整型向量，表示时间戳。TD 提供了一些基于时间戳的数据并行计算操作，例如：map, reduce或者iterate等。Graphsurge 存储视图集合就是直接基于 TD 的。DD（differential dataflow）则是基于 TD 构建的系统，和 TD 相比，DD 的每个数据也有时间戳，但是它要求数据要以差分的形式存储，例如：考虑操作op，At 是 t 时刻 op 的输入流，Bt 是 t 时刻 op 的输出流，那么 DD 就要以 δAt 和 δBt 的形式存储这两个数据流。并且 δBt 也是由 δAt 计算得到的。考虑下面 bellman-ford 计算流程图，它有三个数据流 E,D,M，在右图中就以差分的形式存储和计算的。

前文提到 Graphsurge 会以差分的形式存储视图集合。例如下图定义的视图集合，先会以EBM（Edge Boolean Matrix）的形式存储，即存储视图边的 bitmap，接着 Graphsurge 会进行前后差分获得 EDS (Edge Difference Stream)。我们可以发现视图集合中的视图顺序不同时，EDS 的大小也不同。由此，很自然的引出问题：如何排列使得 EDS 尽量小。

作者定义该问题为 Collection Ordering Problem(COP) ，并且证明了 COP 是 NP-hard 的问题，但是提出了一个 3-近似的算法解决了 COP。

最后，作者发现有时候前后两个视图差距过大，重新计算的效率或许比在前一个视图的计算结果基础上增量的计算效率更高。因此，Graphsurge 采用了一种自适应的方式判断当前应该重新计算还是对增量进行计算。简单来说，我们只需要对每次增量计算的大小和重新计算的大小，以及他们所消耗的时间进行统计、线性拟合，获得估计值，就能够比较这两种方法，从而进行决策了。

实验部分，作者在 view 之间比较相似的情况和 view 之间区别比较大的情况上做了实验。下图，上面一排是view 比较相似的情况，下面一排是区别比较大的情况，可以看到view比较相似时，Graphsurge 有非常大的提升，而在区别比较大情况的情况下，Graphsurge 的效率也没有下降。

这篇文章是 ICDE‘20 的工作，它背景是：微软的数据湖非常庞大，为了维护这个数据湖里的数据，他们把这些数据组织成了依赖图（provenance graph），这个依赖图的节点表示：工作（job），任务（tasks）, 文件以及用户等。自然我们需要在依赖图上执行很多业务，例如：标签传递，设置某个文件的权限，那么依赖它的文件也会受到影响。作者提出，他们发现这些业务经常是相似的，如果把他们公共部分抽取出来，进行物化，那么就会节约大量时间。因此，他们设计 Kaskade 这个系统。

这个系统的框架如下图所示：

该系统可以导入 query workload 进行分析，进行视图抽取和视图选择，选择有价值的视图进行物化。接下来，当有 query 传入系统时，Kaskade 会对 query 进行重写，重写成能够利用上视图的形式，然后用视图对该查询进行优化。

Kaskade 的查询使用的是 Cypher 和 SQL 相结合的语言，使用 Cypher 来描述图结构，SQL 来进行数据分析，如下所示：

而Kaskade 的视图是使用 Prolog 语言编写的，Prolog语言是一种基于推理的语言。简单来说，它的使用方法是，给定一些事实和推理规则作为已知条件。之后，我们进行询问时，Prolog的推导引擎就会通过搜索的方式判断该询问能否被已知的事实和推理规则推导出来。下图展示了这一过程。

Kaskade 的查询重写就是利用了Prolog的推导功能，它先将查询转化为事实，然后根据视图的推导规则，判断查询能否被重写成视图的形式。

Kaskade 的视图可以分成两个大类：Connectors 和 Summarizers ，分别用于存储特定的路径（例如：k-hop路径）和被筛选的子图（例如：删去指定label的节点剩下的导出子图）。

Kaskade 的 workload analyzer 会将抽取出 query workload 能够推导出的视图，接着对每个视图进行评估，从而决定哪些视图值得物化。对于一个视图带来的代价，它是正比于视图的大小的，Kaskade 提供了一种估计方式来解决视图大小的估计。对于一个视图带来的好处，这个通过计算每个询问在该视图中进行查询和在原图中进行查询的效率之比，就可以量化该视图带来的好处。最后，有了代价和收益，对物化视图的选取就转变为了一个 0-1背包问题了，进行求解即可。

总结

图数据库相较于关系型数据库，结构更加复杂，构建于上的视图语义也更加丰富。对于不同的图数据库任务（例如：子图同构，RPQ查询等），我们都有可能抽取出基于该任务语义的视图模式，进而加快计算。除了加快图数据库查询计算，使用视图对数据安全保护也是值得研究的方向，这方面目前也有些相关工作。

欢迎关注北京大学王选计算机研究所数据管理实验室微信公众号“图谱学苑“
实验室官网：https://mod.wict.pku.edu.cn/
微信社区群：请回复“社区”获取

实验室开源产品图数据库gStore：
gStore官网：http://www.gstore.cn/
GitHub：https://github.com/pkumod/gStore
Gitee：https://gitee.com/PKUMOD/gStore

时间戳数据库视图

文章转载自图谱学苑，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

论文导读 | 图上视图的研究

评论