论文注解《Query Languages for Graph Databases》graph数据库查询语法（III）

本文主要是介绍论文注解《Query Languages for Graph Databases》graph数据库查询语法（III），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

聚合

聚合运算，例如： $count, sum, min, max$
$Figure\ 3...$
$Figure\ 4...$
在 $GraphLog$ 中，聚合项可以是可区分的边或节点的标签，一个简单的 $count$ 查询如 $Figure\ 3$ 所示：对于每个作者 $x$ ，计算其获 $y$ 奖的次数。 $a n s (x, c o u n t (y)) \leftarrow (x, h a s W o n, y)$ $ans(x,count(y)) \leftarrow (x,hasWon, y)$
找出每个点对间的最短路径需要计算出沿路径各段的最小距离，再汇总（基本也就是Floyd算法），如 $Figure\ 4$ 所示。查询中的变量 $d$ 是聚集变量， $sum$ 是汇总功能， $min$ 用于聚合汇总的距离。当汇总和聚合的操作是闭半环时，查询时间复杂度是 $PTIME$ 。查询 $Q$ 可悲转化为以下 $Datalog$ 程序：
$len(x, x, x, 0) ← dist(x, y, l)$
$len(x, x, x, 0) ← dist(y, x, l)$
$len(x, z, y, d) ← sp(x, z, s), dist(z, y, l), d = s + l$
$sp(x, y, min(d)) ← len(x, z, y, d)$
谓词 $len(x, z, y, d)$ 说明有一条长度为 $d=s+l$ 的路径从 $x$ 经过 $z$ 到 $y$ ， $x$ 到 $z$ 的最短路径为 $s$ ， $z$ 到 $y$ 的最短路径为 $l$ 。

近似匹配和排名

设一条正则路径查询 $Q$ 如公式 $(3)$ ，运用正则表达式 $r$ 。近似匹配可通过把编辑操作应用到 $L(r)$ 来实现。可能的编辑操作包括符号的插入、删除、置换、移项、倒置。
令 $x,y \in \Sigma$ ，从 $x$ 到 $y$ 的编辑操作被模型化为一个基于 $\Sigma^*$ 的二元关系 $\mapsto$ ，以至于 $x \mapsto y$ 当且仅当存在 $u,v \in \Sigma^* , a,b \in \Sigma , a \neq b$ 。例如：
$x = uav, y = ubv (置换)$
$x = uav, y = uv (删除)$
$x = uv, y = ubv (插入)$
令 ${^k_{\mapsto}}$ 代表执行 $k$ 次 $\mapsto$ 操作。 $d_e(x,y)$ 代表 $x\ {^k_{\mapsto}}\ y$ 所需最小的 $k$ 。
每个操作的开销可能都不一样。通常来说，对于不同实例，相同操作的开销也不一定相同。
假定近似值由加权正则转换器的方法指定，这种转换器能用一个基于三元组 $(a,k,b)$ 的正则表达式来表示（ $a$ 能被 $b$ 以 $k$ 开销替换）。加权转换器 $T=(S_T, Σ, σ_T, S_{0_T} , F_T)$ ：有穷状态集合 $S_T$ 、输入/输出字符集 $\Sigma$ 、初始状态集合 $S_{0_T}$ 、终止状态集合 $F_T$ 、转换关系 $\sigma_T \subseteq S_T \times \Sigma \subseteq \Bbb{N} \times \Sigma \times S_T$ 。转换 $(s, a, k, b, t)$ 表示当转换器处于状态 $s$ 读入符号 $a$ ，输出符号 $b$ 消耗 $k$ 并转到状态 $t$ 。
从查询 $Q$ 的正则表达式 $r$ 中构造一个 $NFA$ $M_r$ 并将 $G$ 也作为一个 $NFA$ 。得到乘积自动机 $M_r \times T \times G$ 。 $(a, b, k) \in ans_T(Q,G)$ 当且仅当从初始状态 $(\_,\_,a)$ 到终止状态 $(\_,\_,b)$ 的最短路径开销为 $k$ 。在一种更简单的设定里，近似值由编辑操作引起，所有开销均为 $1$ ，且转换器 $T$ 只有一个状态 $s$ 实现从 $s$ 到 $s$ 的标签 $ε$ ：
$(a, 1, ε), a \in Σ (删除)$
$(ε, 1, a), a \in Σ (插入)$
$(a, 1, b), a, b \in Σ,a \neq b (置换)$

表达能力和计算复杂性

我们将查询语句分类为：联合查询（ $CQ$ ）、正则路径查询( $RPQ$ )、联合路径查询( $CRPQ$ )、扩展联合路径查询( $ECRPQ$ ）。设 $FQ$ 为一阶逻辑，可得到 $C Q \subseteq F O$ $CQ \subseteq FO$ $R P Q \subset C R P Q \subset E C R P Q$ $RPQ \subset CRPQ \subset ECRPQ$
具有传递闭包（用 $FO + TC$ 来表示）的一阶逻辑语言，用形如公式 $TC=(\lambda \bar x, \bar y \cdot \phi(\bar x, \bar y))$ 扩展了一阶逻辑： $\bar x$ 和 $\bar y$ 是 $k$ 元组， $\phi(\bar x, \bar y)$ 为 $FO+TC$ 中的公式且决定了 $k$ 元组的二元关系。 $TC=(\lambda \bar x, \bar y \cdot \phi(\bar x, \bar y))$ 决定了 $\phi$ 的传递闭包。
在一个线性 $Datalog$ 程序中，每一条规则都最多只有一个递归子目标。在一个分层 $Datalog$ 程序中，否定谓词的使用是有层次的。

总结

总的来说这是篇概述性的论文，主要铺述了各类graph数据库的查询语言，主要着重于几个功能性的层面。尽管很多语言的特性和概念已经成为学术研究的主题，但对于graph查询语言来说工作则着力于建立一个完整且一致的框架。近似查询和图的转换也值得更多研究。

个人感悟

graph数据库可以说是传统关系型数据库的一个特化版本，即更专注于一元|二元关系的表达。 $RDF$ 的形式为主语 $\rightarrow$ 谓词 $\rightarrow$ 宾语，相较于 $schema$ 化的graph数据库灵活性更强，但是在线计算的能力必然更弱。当图中的节点数多到必须分布式存储时，针对子图分割和最短路径的传统算法就完全没有什么卵用，因此必须涉及到概率性的层面。很多语言在功能和架构完善后都会引入正则表达式，正则语法应当是对原有功能的汇总表示。