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

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

概述

这篇paper主要介绍了历史上的graph数据库查询语法的发展和用途，并从查询处理的表达能力和计算复杂性做出评估

简介

对于一个graph数据库 $G$ 最简单的形式为 $(V,E)$ ，其中 $V$ 是有限点集， $E$ 是连接点对的有限边集（有向|无向）。在大多数的应用场景中点和边往往以某种形式被打上标签（例如属性-值），且用字符 $\sum$ 表示打标签的过程，即 $E \subseteq V \times \sum \times V$ 。有些应用环境则需要更精巧的graph化的数据结构，例如用于对超文本建模的超图，它的节点就可以由图构成。除此之外，在一些graph数据模型中，每个graph均需要对应特定的架构（ $schema$ ）。
$Figure\ 1...$
paper中用一张图来表示阐释这种模式，举个查询的例子：找出同时获得 $Booker$ 和 $Nobel$ 奖的作者——一种简单的联合查询 $CQ$ ，可利用以下语法来表示该次查询 $a n s (x) \leftarrow (x, h a s W o n, N o b e l), (x, h a s W o n, B o o k e r) . . . . . . (1)$ $ans(x) \leftarrow (x, hasWon, Nobel), (x, hasWon, Booker)......(1)$ 其中 $x$ 代表节点， $hasWon，Nobel，Booker$ 代表常量。这种语法类似于 $Datalog$ ，但是查询主体中的元素不包含谓词。实际上这些元素更像是三元组（ $triple$ $patterns$ 被用于 $SPARQL$ ）或 $W3C$ 查询语言（ $RDF$ ）
为了在graph中找出点对 $（x,y）$ 表示存在一条从 $x$ 到 $y$ 的路径 $P = e_{a},e_{b},e_{c},...$ 且序列 $label_{a},label_{b},label_{c},...$ 符合某种模式。一种做法是用正则表达式指定该模式，这种查询被称作 $RPQ$ 。例如 $(x, (c i t i z e n O f | ((b o r n I n | l i v e s I n) \cdot l o c a t e d I n *)), y)$ $(x, (citizenOf | ((bornIn | livesIn) · locatedIn∗)), y)$ $CQ$ 和 $RPQ$ 可以组合成一种新的形式 $CRPQ$ ，例如 $a n s (x, y) \leftarrow (x, h a s W o n, N o b e l), (x, h a s W o n, B o o k e r) (x, (c i t i z e n O f | ((b o r n I n | l i v e s I n) \cdot l o c a t e d I n *)), y) . . . . . . (2)$ $ans(x, y)← (x, hasWon, Nobel), (x, hasWon, Booker)(x, (citizenOf | ((bornIn | livesIn) · locatedIn∗)), y)......(2)$ 在 $GraphLog$ 中的表示形式如下
$Figure\ 2...$
图中较粗的边被称作 $distinguished\ edge$ ，代表出现在结果中的边，需要与查询头部相对应
当需要表示路径之间的关系时， $CRPQ$ 就显得不够强大，因此需要一种新的查询语法 $ECRPQ$ 。例如 $(x, y) \leftarrow (C o e t z e e, π, y), (x, π, y), Σ * (π)$ $(x, y) ← (Coetzee, π, y), (x, π, y), Σ^{∗}(π)$ 找出实体 $x$ 和 $y$ ，两者间路径上标签的序列等同于 $Coetzee$ 和 $y$ 之间。 $π$ 代表可行的路径， $Σ^{∗}$ 代表标签的序列。

查询语言功能

子图匹配

子图查询是被最广泛支持的一种图查询模式。以 $CQ$ 为例，设可用点集为 $(x,y,z,...)$ ，则查询语句的形式可以是 $a n s (z 1, . . ., z n) \leftarrow ⋀ 1 \leq i \leq m (x i, a i, y i)$ $ans(z1, . . . , zn) ←\bigwedge_{1≤i≤m} (x_i, a_i, y_i)$ 设 $\bar x = (x_1,x_2,...x_m)$ ， $\bar y=(y_1,y_2,...y_m)$ ， $\bar z=(z_1,z_2,...z_n)$ ，需要指定 $\bar x$ ， $\bar y$ 到 $G=V,E)$ 点集的映射关系 $\sigma$ ： $(G,\sigma)\vDash Q$ ，使 $(σ(x_i), a_i, σ(y_i)) ∈ E$ 。在某些应用领域，数据库本身就是由graph的集合组成，其查询结果需要返回匹配的子集。
尽管 $CQ$ 在某种意义上是最简单的graph查询模式，但是研究难点在于找到一种有效的方式去评估其在大规模graph查询中的表现。因为针对 $CQ$ 计算 $QEP$ 的复杂度等同于子图同构问题(NP问题)。因此，业内正在研究基于graph模拟的graph模式匹配。

发现路径所连的节点

设 $G=(V,E)$ ， $v_0、v_1 \in V$ ， $v_0、v_1$ 之间存在一条路径 $\rho = v_0 a_0 v_1 a_1 v_2 a_2...v_{m-1} a_{m-1} v_m$ ，路径上标签的序列为 $\lambda(\rho) = a_0...a_{m−1} ∈ Σ^{*}$

正则路径查询（ $RPQ$ ）

计算和决定节点间的可达性这种查询机制存在于绝大部分graph查询语言中。 $RPQ$ 通常返回与一条路径相连的所有符合正则表达式的点对集合。其形式为 $a n s (x, y) \leftarrow (x, r, y) . . . . . . (3)$ $ans(x, y) ← (x, r, y)......(3)$ $x$ 和 $y$ 为可用的节点， $r$ 为正则表达式（用 $|$ 表示析取， $·$ 表示，并保留简写 $r^+ \Rightarrow (r · r^∗)、r? \Rightarrow (r|\epsilon)、Σ \Rightarrow (a_1|... |a_n)、a^- \Rightarrow$ 任何标记为 $a$ 的反向边）。
正则路径查询的难点在于针对给出的查询Q和点对 (x,y) ，如何判断 (x,y)∈Q(G)? 有一种算法如下：
1. 构造一个非确定性的有穷自动机( $NFA$ ) $M_r$ （初始状态 $s_0$ 终止状态 $s_1$ ）来接收 $L(r)$
2. 将 $G$ 视作一个拥有初始状态 $x$ 终止状态 $y$ 的 $NFA$
3. 构建自动机的乘积 $M_r×G$
4. 判断在 $M_r×G$ 是否存在从 $(s_0, x)$ 到 $(s_f, y)$ 的路径
算法中的每个步骤是PTIME的复杂度，因此正则路径查询问题的总体复杂度是 $\sum PTIME$
或者，我们可以按照 $Datalog$ 的规则把 $Q$ 转化为一组集合，例如正则表达式 $citizenOf | ((bornIn | livesIn) · locatedIn∗)$ 可转化为
$ans(x, y) ← citizenOf(x, y)$
$ans(x, y) ← assoc(x, y)$
$ans(x, y) ← assoc(x, z),partOf(z, y)$
$assoc(x, y) ← bornIn(x, y)$
$assoc(x, y) ← livesIn(x, y)$
$partOf(x, x) ← locatedIn(x, x)$
$partOf(x, y) ← locatedIn(x, z), partOf(z, y)$
有时我们可能仅仅想在 $G$ 中找出的匹配正则表达式 $r$ 的简单路径（当一条路径 $ρ$ 中没有重复的节点时则将其定义为简单路径）。所以正则简单路径问题可以被阐明为：给定 $G$ 、点对 $(x,y)$ 和正则表达式 $r$ ，判断是否存在一条从 $x$ 到 $y$ 且匹配 $r$ 的简单路径。然而，这个问题居然tm的是个 $NP$ 问题，即使对于固定的正则表达式。