@contribute 2018-08-20T09:32:16.000000Z 字数 13917 阅读 4381

图计算理论、实现及应用

tinkerpop

宋子豪
z@a-z.ai

曹志富
cao.zhifu@gmail.com

技术报告
2016年3月

摘要

为什么会有所谓“大数据问题”？因为大多数程序可以计算“数据”但不是“大数据”。为什么不是所有的程序都能计算“大数据”？这属于经典计算体系内的工程进度问题，还是说，经典计算体系对程序的定义有问题？经典计算机实现的是可编程计算机。随着程序和数据变得越来越庞大和复杂，在“可编程”概念下的计算机理论对新问题缺乏指导意义。图灵发明计算机理论、冯・诺伊曼发明经典计算机是因为他们遇到了当时的“大数据”问题。今天，我们需要重新思考和更新这套理论。本文讨论图计算（Graph Computing）理论的意义，分析实现方案和应用价值。我们的结论是图计算理论提供一个适用于今天数据规模的通用计算架构，图计算的实现可从根本上改善“大数据”应用难的问题。

版权所有
北京太观科技有限公司

1. 引言

在实践中，一些极具竞争力的大数据技术开始展露图（graph）的特点：我们发现数据的排列组合用顶点（vertex）和边（edge）来表达更好，程序本身的排列组合也一样。从更宏观的角度看，这种转变可能来源于知识本身就是事物间的关系。随着图计算的一些模式和方法不断出现，图计算概念也逐渐清晰，现在已经变成了一个新的计算体系。

在具备图灵完备性的前提下，计算机是让数据按照程序演化的机器，以冯・诺伊曼结构为代表；遍历机是让图按照遍历（traversal）方案演化的机器，以 Rodriguez 提出的 GTM（Gremlin Traversal Machine）为代表[1]。

物理计算机	遍历机
指令集	步骤库（step library）
程序	遍历（traversal）
程序计数器	遍历子（traverser）
内存	图

这种概念上的变化不是凭空出现的，而是在人们解决大数据问题当中形成的一种趋势。

1.1 背景

在数据库方面，NoSQL 数据库已经开始慢慢取代 SQL 数据库，或者同时存在于应用中。NoSQL 的数据结构主要以键值和文档型（树型）为主。近年来出现了一些图型数据库，比如 Neo4J，OrientDB，InfiniteGraph，Sparksee 等等。这反映了应用层面需要更丰富和直观的数据表现方式。

在计算框架上，我们有了 Hama，Giraph，GraphLab，GraphX 等面向图型数据的计算工具。

1.2 现状

现有图型数据库的优点：

适用于以点为中心的局部遍历
适合高并发
面向图的语言

缺点：

不能全局遍历和分析
数据库特征不适合更广义的计算

现有图计算框架的优点：

适用于全局分析
并行计算
充分利用顺序读取

缺点：

不支持并发
延迟高

所有网络服务都存在数学意义上的图模型，但大家没有一个通用图计算系统。这意味大家在搭建应用模型时都需要搭建或者使用一个不完整的图结构，这是大量的重造车轮。云计算需要一套对大数据通用的虚拟计算架构，就跟物理计算机需要像 x86、ARM 这样的通用物理计算架构一样。

2. 理论

我们先简要介绍 Gremlin 遍历机（GTM）结构及其语言。

2.1 基本结构

GTM 由三部分组成：图 $G$ ，遍历 $\Psi$ 和遍历子 $T$ ，分别对应数据，指令和读写头。

$G$ 由带有属性的顶点和边组成：

$G = (V, E, \lambda) \\ E \subseteq (V \times V) \\ \lambda: ((V \cup E) \times \Sigma^{\ast}) \rightarrow (U \setminus (V \cup E))$

其中， $V$ 为顶点集合； $E$ 为带方向的二元制边集合， $\lambda$ 将图中对象与字符串标签的配对映射到一个除了顶点和边以外的任意属性集 $U$ 。

一个遍历 $\Psi$ 是一个由步骤（steps）组成的树状函数。步骤可以是线性的 $f \circ g \circ h$ ，也可以是嵌套的 $(f \circ g) \circ h$ 。

每个步骤 $f \in \Psi$ 将一组在 $A$ 对象上的遍历子映射到新的位置 $B$ ：

$f: A^{\ast} \rightarrow B^{\ast}$

在这里，带有 Kleene 星号的 $A^{\ast}$ 表示可能有多个遍历子在同一个 $A$ 的元素上。但是，每一个被映射的遍历子都是唯一的。

遍历子集合 $T$ 将图中的对象和遍历中的步骤关联起来，其定义为一个六元组：

$T \subseteq (U \times \Psi \times (\mathcal{P}(\Sigma^{\ast}) \times U)^{\ast} \times \mathbb{N}^{+} \times U \times \mathbb{N}^{+}).$

所以，遍历子需要六个函数分别对应以上六个部分。

$\mu: T \rightarrow U$ 将一个遍历子 $t \in T$ 映射到图中的位置，比方说 $v \in V, V \subset U$ ，该位置可能是顶点和边，也可能是相关的属性。
$\psi: T \rightarrow \Psi$ 将 $t$ 映射到 $\Psi$ 的一个步骤上。
$\Delta: T \rightarrow (\mathcal{P}(\Sigma^{\ast}) \times U)^{\ast}$ 记录 $t$ 的路径（path），一个由字符串和对象以及他们的子集组成的序列；
$\beta: T \rightarrow \mathbb{N}^{+}$ 记录 $t$ 的块数（bulk）：跟这个遍历子相同的遍历子的数量。
$\varsigma: T \rightarrow U$ 给 $t$ 提供一个口袋（sack）来装本地变量。
$\iota: T \rightarrow \mathbb{N}^{+}$ 记录 $t$ 的循环数（loop counter），它经过的循环序列数量。

当机器在工作时，一组遍历子根据遍历方案在图上移动。

2.2 机器语言

Gremlin 的基本语言由大约30个步骤组成，类似于物理计算机的指令集。其目的是让人能直观地定义遍历，遍历机接到请求后，就让遍历子去执行遍历。

要支持 Gremlin 语言，母语言需要有复合函数和函数类（函数可以作为对象）。这样的话，我们可定义一个流畅的语法。在面向对象编程语言中， $a \circ b \circ c$ 可写作 a().b().c()；带遍历嵌套的 $a(b \circ c) \circ d$ 可写作 a(b().c()).d()。

Gremlin 步骤可分为以下五大类。

$\mathbf{map}: A^{\ast} \rightarrow B^{\ast}$ ，其中 $|\text{map}(T)| = |T|$ 。这类函数将遍历子们 $T$ 从位置 $A$ 映射到 $B$ 时不会改变 $T$ 的数量。
$\mathbf{flatMap}: A^{\ast} \rightarrow B^{\ast}$ ，输出遍历子的数量可能跟之前不一样。
$\mathbf{filter}: A^{\ast} \rightarrow A^{\ast}$ ，其中 $\text{filter}(T) \subseteq T$ 。来的遍历子们有的能过去，有的过不去。
$\mathbf{sideEffect}: A^{\ast} \rightarrow_{x} A^{\ast}$ ，其中 $\text{sideEffect}(T) = T$ 。虽然是遍历子上的恒等函数，中间可能有 $U$ 中其他的数据结构发生变化。
$\mathbf{branch}: A^{\ast} \rightarrow^{b} B^{\ast}$ ，其中 $b: T \rightarrow \mathcal{P}(\Psi)$ 。这类函数将每一个进来的遍历子送上一个或者多个新的遍历。

`map`	`flatMap`	`filter`	`sideEffect`	`branch`
`LabelStep`	`VertexStep`	`AndStep`	`AggregateStep`	`BranchStep`
`IdStep`	`EdgeStep`	`CoinStep`	`IdentityStep`	`ChooseStep`
`PathStep`	`CoalesceStep`	`CyclicPathStep`	`InjectStep`	`LocalStep`
`SackStep`	...	`DedupStep`	`GroupStep`	`RepeatStep`
`SelectStep`		`DropStep`	`GroupCountStep`	`UnionStep`
`MatchStep`		`FilterStep`	`StoreStep`	...
`ConstantStep`		`HasStep`	`SubgraphStep`
...		`IsStep`	`TreeStep`
		`NotStep`	...
		`OrStep`
		`RangeStep`
		...

TinkerPop3 提供了一个开源的步骤库规范。目前有五十多个步骤供参考。详细的步骤说明和范例在 Apache TinkerPop 官网（中文翻译）。

2.3 通用计算

通用计算有很多种形式，能力也不一样。我们概括 GTM 的几种基本形式和高级形式。

2.3.1 图灵完备性

图灵机是最基本的可以做通用计算的自动机。我们可以把 GTM 简化为图灵机：假设遍历机的图是线状的，遍历子当图灵机的读写头，遍历子的口袋作为图灵机状态，一部分步骤库作为指令表。

2.3.2 UGM

进步一思考，遍历 $\Psi$ 和遍历子 $T$ 本身也可以编码在 $G$ 里面。我们可以定义一个 GTM 用它的 $G, \Psi, T$ 去仿真另一个 GTM。这是与 Universal Turing Machine 类似的 Universal Gremlin Machine（UGM），它的 $G$ 包含了被编码的 GTM（ $G$ -Encoded Machines)。

2.3.3. 并行 GTM

如果一个遍历 $\Psi$ 中的遍历子集合 $T$ 可以采用序列式、并行式或者分布式计算，那么在 UGM 里，因为 $T$ 和 $\Psi$ 都被编码在了 $G$ 里面，我们可以让多个 $T$ 在各自的 $\Psi$ 下面运行。遍历子的口袋里可装 $\Psi$ 的 ID 号，在运行时能识别 $\Psi$ 就行了。我们可以把并行 GTM 看成多线程 UGM。当然多个 UGM 也可以在另一个 $G$ 里并行。

2.3.4. 进化 GTM

如果 $\Psi$ 和 $T$ 都被编码在了同一个 $G$ 里面， $\Psi$ 的输入对象可能不只是 $G \setminus (\Psi \cup U)$ ，它完全可能读取和修改它自己的结构。而且，一个遍历子也可能修改它归属的 $\Psi$ 。理论上来说，这个机器可以分析自己和修改自己。当然，这样的理论不少见，其可行性取决于机器构造和实现方式。在后面的应用部分，我们会谈到 GTM 给人工智能的一些前沿概念提供了一种更好的架构。

2.3.5. 起始 GTM

取一个多元关系的，带有任意属性的有向图 $\text{MADG}$ （multi-relational, attributed digraph）。我们找一个单射函数将 $\text{MADG}$ 映射到一个多元关系的，无属性的有向图 $\text{MDG}$ ，其中关系是固定的，但所有属性的键变成了边的标签，属性的值变成了顶点的标签。我们再找一个单射函数将带标签的 $\text{MDG}$ 映射到一个无标签的有向图 $\text{DG}$ 。这类似于图论里的上色问题。最后，我们找另一个单射函数将边的方向性转化成无方向性的拓扑特征 $\text{UG}$ [2]。

$\text{MADG} \mapsto \text{MDG} \mapsto \text{DG} \mapsto \text{UG}$

$\text{UG}$ 就是一个起始 GTM。在没有任何标签、字符串或数字属性情况下，所有的计算状态都可以由高维空间中的点和线演化而来。这可以用来模拟一定的生物、化学或物理过程。

3. 实现

图计算实现的主要瓶颈在于承载图结构的数据库能否支持低延迟高吞吐 I/O 并保证数据的完整性。有了图结构，剩下的问题就是针对该结构做计算框架的优化，遍历子的实现。

3.1. 图结构

关系型数据库在60年代末就已经出现了。至今仍是主流的数据管理工具。关系型数据库里是一堆表格。行代表对象，列代表属性。我们会在多个表格上构建业务模型，然后用 JOIN 来统一不同表格上的数据。在关系型数据库里，保持不同表格间指向的一致性很重要。

相反，图型数据库的数据都在一个图结构里，而不是不同的表格里。具体地讲，图型数据库的基本特征是无索引相邻（index-free adjacency）。这里每个对象都直接指向相邻对象，没有不同表格间的 JOIN。这提供了一个很大的优势：相邻对象的查询只需要恒定时间。光是这一点就让遍历成为了一种效率极高的计算模式。但是，就跟关系型数据库一样，这里面难点在于当数据增加时，如何对图进行切片（sharding）并同时保持关系的一致性和遍历效率。将图结构用支持大数据的 NoSQL 数据库实现帮我们解决了这个问题。

3.1.1. 基础数据模型

图结构由一下几个基本元素构成：

Graph：维护点、边集合，还包括一系列连接数据库的功能
Element：维护一系列的属性集合以及元素类型标签
- Vertex
- Edge
Property：属性键值对
- VertexProperty：点多值属性集合，边或者其他元素并不支持

点与边之间的关系，通过邻接表结构来进行实现。

Titan 是一个基于 Gremlin 的分布式、支持 ACID 图型数据库。其架构如图：

在 Titan 中，针对遍历做了特定的优化：

利用存储后端引擎，如 Cassandra、HBase 等实现内部倒排索引
利用索引系统，实现外部索引，用于支持多种方式（如：分词、GEO、时间范围等等）的遍历与过滤。

类似与其他图数据库，Titan 同样利用邻接表来存储图形结构，同时为了优化遍历查询，进行了冗余存储。

点存储模型：

以点的唯一 ID，作为存储 ROW KEY，属性与边进行排序存储。属性与边作为一个单独的存储列来存储
边存储模型：

以边标签与边方向作为列前缀，与邻接点 ID，边 ID 作为列名，签名键与属性值作为存储值
属性存储模型：

3.1.1.2 全局索引

全局索引是一种贯穿整个图形的索引结构，可以利用点或者边的属性，来高效的进行全局检索，考虑如下面两个查询：

g.V().has('name', 'hercules')
g.E().has('reason', textContains('loves'))

3.1.1.3 顶点中心索引

顶点中心索引是构建在每个点上的本地索引。顶点中心索引利用这种本地索引结构，加速在那些需要遍历的边上的遍历速度。

以顶点为中心的检索，能够快速的实现从点开始的图遍历。以顶点为中心的索引对顶点有其特殊的意义。与图索引计算相反，这种计算对图来说全局的。以顶点为中心的计算方式的目的是根据顶点附加的边、标签及属性来排序或检索其边。如果利用这种计算来查询一个顶点，将可能会达到(O(1) 或O(log n))的遍历速度，避免导致边查询的计算强度线性增加为（O(n)）。

h = g.V().has('name', 'hercules').next()
g.V(h).outE('battled').has('time', inside(10, 20)).inV()

3.1.2. 数据类型扩展

Gremlin 拥有良好的扩展性。图结构、步骤、遍历子及遍历策略都可以进行相应的扩展，以支持更多的数据类型和需求。

3.1.2.1 时间序列

时间序列对性能有两个基本要求：

高吞吐、低延迟的写入
低延迟的读取最新状态数据

利用图型数据库存储时间序列数据有一下两个优势：
1. 整个物联网的数据作为一个统一的视图，将传感器数据与其实体之间进行直接关联，如图所示：示意图
2. Gremlin 语言能够方便的对时间序列数据进行查询遍历

采取图型数据库进行时间序列存储解决方案时，需要解决几个问题或者说需要达到以下两个目标：
1. 模型简单，易于查询
2. 尽可能的减少点的遍历查询

实现方案

通常对于时间序列数据，一般由专门的时间序列数据库（比如：influxdb），或者 NoSQL 数据库（比如：Cassandra）来存储。我们可以将前文提到的基础数据模型与相应的数据后端进行整合。

具体的实现方案如下：
1. 将物联设备（实体）作为一个点 Device
2. 采取按照某一固定时间段（eg：天、周、月）作为分块，本分块作为一个点 Chunk
3. 在点 Device 与 Chunk 之间，通过边进行关联，其属性为块的起始时间
4. 实体数据作为一个点 data，与点 Chunk 之间通过，边进行关联，边上设置属性为具体的时间，其中本属性是一个排序属性

结合上述方案，通过 Gremlin 查询语言，即可做到时间序列数据的查询与存储，以下是示例代码：

查询某一时间段内的传感数据

chunk.outE().has(“tstamp”, between(1442162072000, 1442162073000))

查询最新的传感数据

chunk.outE().has(“tstamp”, lte(System.currentTimeMillis()).  order().by(“tstamp”, decr).limit(1)

插入传感数据

chunk.addEdge(“data”, chunk, “tstamp”, 1442162072000, “value”, 500.123)

3.1.2.2 文件

针对文件这种非结构化数据，可以通过实现一个新的步骤以及适配底层分布式存储系统，即可实现文件的读取、写入、解析、分析，与具体的业务实体进行关联。

实现方案

在图中展示了一个文件的存储模型：

具体业务实体比如文件的拥有者、读取者，作为图中的一个点，每个文件同样作为图中的一个点。其中文件点包括该文件的元数据信息。
业务实体与点之间通过有向边进行关联，不同的业务实体与文件之间的边用不同的标签标示，如：创建者用 created，被分享用 shared。
边上建立一些需索引的属性，比如：createdAt，fileType。这样可以轻松按照时间、文件类型进行排序、分组检索。
实现新的 Gremlin Step：ReadStep、WriteStep。在ReadStep与WriteStep中远程分布式文件存储系统如HDFS、ClusterFS进行关联通信。

3.2. 遍历策略

遍历策略是指将遍历片段（traversal-pattern）重写来实现某种期望的效果，但不改变其结果的手段。GTM 支持一些可能性，根据其目的大致可分五类。在遍历执行前，这些策略类别会依次执行。每个策略类中子策略也有次序，有的子策略可能需要其他类别中子策略先执行。

跟步骤库一样，这些策略是需要不断补充和完善的。

3.2.1. 修饰

单纯语法上的修饰。

ConjunctionStrategy：将中缀的逻辑算子转化为前缀的。

a.and().b           # and(a,b)
a.or().b            # or(a,b)
a.or().b.and().c    # or(a,and(b,c))
a.and().b.or().c    # or(and(a,b),c)

3.2.2. 优化

对于遍历写法本身的优化。

IncidentToAdjacentStrategy：如果一个遍历接触了一个顶点的边但却无需分析那些边的内容，它可以直接跳到相邻顶点。

# a.outE().inV().b
a.out().b
# a.bothE().otherV().b
a.both().b

AdjacentToIncidentStrategy：上一例的“反例”。

# a.in().count().b
a.inE().count().b
# a.where(out()).b
a.where(outE()).b
# a.and(in(),out()).b
a.and(inE(),outE()).b

IndentityRemovalStrategy：去掉 indentity() 步骤。如果有 as() 控制幅度，并入前一步。

# a.identity().b
a.b

FilterRankingStrategy：因为 filter() 可能会让结果集缩小，如果有一系列 filter() ，将它们重新排序让省力的步骤先执行。这样会使费力的步骤尽可能处理更小的集合。请注意 order() 也被当作 filter()。

# a.and(c,d).has().b
a.has().and(c,d).b
# a.order().dedup().b
a.dedup().order().b

MatchPredicateStrategy：如果 match() 后面跟着 where()，将 where() 折叠到 match() 里作为一个新的分支片段。这样，where() 后面的片段就用上了 match() 的 XMatchAlgorithm 优化器。

# a.match(c,d).where(e).b
a.match(c,d,e)

RangeByIsCountStrategy：如果一个遍历只需要知道一个集合的大小是否为某个特定值，限制计数至 1 加上该特定值。

# a.count().is(0)
a.limit(1).count().is(0)

3.2.3. 供应商优化

GTM 提供的只是顶层接口规范，底层实现由各类供应商完成。供应商优化是指对于底层遍历子和图结构的优化。

XGraphStepStrategy：对于顶点和边的查询，图系统供应商通常会提供索引服务。我们可以把多个 has() 步骤折叠到一个供应商特定的 V() 步骤里，把查询时间从 $O(|V \cup E|)$ 降到 $O(\log(|V \cup E|)$ 。

# V.has().has().b
V[has,has].b

3.2.4. 完结

在遍历结束前完成一些工作。

ProfileStrategy：用 profile() 测量遍历的性能表现。

# a.b.profile()
a.profile().b.profile()

3.2.5. 校验

确保遍历是合格的。

ComputerVerificationStrategy：有些遍历片段在特定计算模式（比方说分布式）下是不被支持的。随着底层计算模式的进步，这些限制会被逐渐清除。

# a.order.b
error
# a.local(out().out()).b
error

3.3. 遍历子

3.3.1 序列式

OLTP（Online Transactional Processing）指联机事务处理。在图型系统中特指：查询、交互一组有限的数据，拥有毫秒或者秒级的响应。

图型系统的 OLTP 具有以下特点：

高并发低延迟
局部遍历

实现与范例

OLTP

从上图中可以看出，在 Gremlin OLTP 中，遍历是顺由点与点之间的边，逐步遍历。OLTP 采用了深度优先遍历算法。因此，在 OLTP 中 Gremlin 的遍历步骤是与后端存储数据库直接进行通信。

示例：

g = graph.traversal(standard())
g.V(4).bothE('knows','created','blah').otherV()

在上面示例中，采用步骤 VertexStep 来实现。上面例子的执行步骤

查找 V(4) 的 knows, created, blah 三种边标签的所有边
合并符合条件的边所关联的顶点并排除 V(4)

3.3.2 分布式

OLAP（Online Analytical Processing）指联机分析处理。在图形系统中指，全图将被分析处理，意味着每个点与边都将被迭代（一次或多次）分析计算。与 OLTP 相比，OLAP 的响应时间将会是分钟或者小时级别。

图形系统的 OLAP 具有以下特点：

高度并行处理
全局遍历

实现与范例

OLAP

在 Gremlin OLAP 中，利用广度优先遍历算法，所有的点均提供一个遍历子 VertexProgram。这些遍历子通过一种 BSP 计算模型将消息进行传递。

在 OLAP 的实现中，遍历步骤通过分布式计算引擎如 Giraph、Spark 与后端存储引擎对接。以存储引擎 Cassandra、分析引擎 Spark 为例，其工作流程为：

Gremlin 先把遍历编译成 Spark 任务，提交给 Spark 集群。
Spark 利用与 Cassandra 专用的连接器并行读取数据，转化为 SparkRDD 格式。
Spark 完成运算，将结果写入 Cassandra。

Spark

示例：

g = graph.traversal(computer(SparkGraphComputer))
g.V().both().hasLabel('person').values('age').groupCount().next()

3.4. 供应商

目前已发布的支持 TinkerPop 的产品有 Allegro，Arango，Blazegraph，InfiniteGraph，OrientDB，Sparksee，Stardog，Titan。这些产品基本可以做 OLTP，但对 OLAP 的支持十分有限。顶层接口有计算功能，但却很难在生产环境中对大数据使用。

准备发布的有 DSE Graph 和 Bluemix Graph，分别由 Datastax 和 IBM 开发。Datastax 是 Cassandra 的主要贡献者，在大数据领域比较权威。IBM 希望将 Bluemix Graph 和 Watson 结合，为企业提供一个智能的数据中心。除了这些美国公司，中国的太观科技也在开发 Metagraph，更加注重与应用场景的对接。这三个产品旨在提高图计算中的大数据处理性能，让图计算可以做通用计算。

4. 应用

图对任何数据的表现力和遍历子灵活的运作方式。

4.1. 特性分析

对于一个产品团队不同角色的分析

4.1.1. 对于架构师

全面的数据模型：捕捉所有场景的复杂性
灵活和敏捷：更短的产品周期
一致的开发模式：一个简约通用的虚拟环境和语言将批量计算和实时交易请求融为一体
降低系统复杂性：一个端对端优化的开发平台，降低成本和风险

4.1.2. 对于开发者

直观的模型：更好地思考和管理代码
流畅的语言：采用数据流编程编程思想

# 用三种图查询语言找 hercules 的舅舅
# Gremlin
g.V().has('name','hercules')
 .out('father').out('brother')
 .value('name')
# Cypher
MATCH
(n)-[r:FATHER]-(m),
(m)-[s:BROTHER]-(o),
WHERE
n.name = 'hercules'
RETURN
o.name
# SPARQL
SELECT ?name
{
  ?h g:name 'hercules' .
  ?h g:father ?m .
  ?m g:brother ?o .
  ?o g:name ?name
}

丰富的表达：声明式和过程式融为一体。跟 SQL 相比，Gremlin 在写法上优势明显。

# 在 SQL 中，你需要通过 stored procedures 注入过程式计算
# 例子来自于：https://msdn.microsoft.com/en-us/library/ms191320.aspx
IF OBJECT_ID (N'dbo.ufnGetInventoryStock', N'FN') IS NOT NULL
    DROP FUNCTION ufnGetInventoryStock;
GO
CREATE FUNCTION dbo.ufnGetInventoryStock(@ProductID int)
RETURNS int 
AS 
-- Returns the stock level for the product.
BEGIN
    DECLARE @ret int;
    SELECT @ret = SUM(p.Quantity) 
    FROM Production.ProductInventory p 
    WHERE p.ProductID = @ProductID 
        AND p.LocationID = '6';
     IF (@ret IS NULL) 
        SET @ret = 0;
    RETURN @ret;
END;
GO
# Gremlin 是基于母语言（比如 Java，Groovy）的 DSL。它自带过程式结构，还有其母语言的其他特性。
g.V().until(has('name','ripple')).
    repeat(out()).path().by('name')
# Gremlin 让你能在声明式和过程式间语句间平滑切换。
g.V.match(
        as('a').out('knows').as('b'),
        as('b').out('created').has('name','lop'))
    .select('b').out('created')
    .match(
        as('x').in('created').as('y'),
        as('y').out('knows').as('z'))
    .select('z').values('name')
    .flatMap{charactersOf(it)}.groupCount()

查看更多 SQL 和 Gremlin 的对比

开源标准：Apache TinkerPop 已发展为图计算的顶层接口标准。TinkerPop 社区还提供了主流查询语言向 Gremlin 的转化器。

4.1.3. 对于分析师和数据科学家

统一的数据结构：数据不再处于割裂状态
更快地投入生产：保持与开发团队一致的环境、数据模型和语言，让算法和洞见更快地产品化

4.2. 应用方向

4.2.1 空间几何

欧拉发明图论是为了给我们对空间的认识提供一套微积分以外的体系。他在解决柯尼斯堡七桥问题的过程中建立了一套新的数学体系，专门用于空间中节点关系的运算。

图论中的算法可以直接应用在地理信息系统（GIS）和建筑信息模型（BIM）上。这些算法都基于广度优先搜索（BFS）和深度优先搜索（DFS）。在实践中，这两个基本遍历步骤的实现决定了图算法的效率，很大程度上影响 GIS 和 BIM 的用户体验和稳定性。尤其在 BIM 中，信息维度从 GIS 的二维或三维，扩展到四维以上，节点数量和关系复杂性呈指数化增长，对于高效遍历的需求迫切。

RDBMS 对于点和点关系的处理效率一向是软肋。每层关系都需要靠索引和 JOIN 来实现。而图计算系统的基本数据模型实现了无索引相邻（index-free adjacency）。针对特定的分布式存储系统，我们可以做图分区（graph partition）优化，从根本上让存在关系的点与点之间更“近”。在这个基础上，遍历步骤和遍历子的实现给任何遍历提供了“最大公约数”。图计算系统在提高性能的同时缩短了开发周期和降低了技术风险。这些优势对于 BIM 的实现有支撑作用。

4.2.2. 数据聚合和充实

对于不同数据源和模型的整合和运用是当今的热点问题。像智慧城市、智慧地球这样的应用需要大量不同的数据聚合和相互充实。物联网上的设备借助 BIM 才能跟应用场景发生精确的关联。BIM 中设备的综合感应可以让人和真实环境发生更丰富的交互体验。这就需要海量多媒体文件存储、分析和关联。

我们需要一个数据结构兼容所有的业务模型、计算和分析方式。图计算提供了更宽广的通用计算平台。TinkerPop 的底层和顶层都具有很强的扩展性。底层的图、步骤库和遍历子可以适配不同特性的数据后端来满足不同场景和类型的数据需求。简洁、通用的顶层接口可以支撑广阔而复杂的应用场景。而且所有的数据都用图表达，给复杂的关系最自然的体现。这让工程师、设计师和分析师更好地思考和创新。

4.2.3. 人工智能

以神经网络为基础的深度学习已经将图像识别和语音识别这样的基础智能做得比较好了。机器可以识别图像和语音中的个体还有一些简单的关系。而要进入更高层的智能则需要理论和工程上的突破。

深度学习很擅长学习底层特征（features）。通过不同方式产生的特征集可以通过图计算融入更高层的模型中。这类似于人的底层智能和高层思维由不同的脑组织负责，但都要通过连接体（connectome）协调才能正常运作。目前，深度学习与贝叶斯网络[3]（Bayesian Networks）、神经图灵机[4]（Neural Turing Machine）和迁移学习[5]（Transfer Learning）的结合是几个热门的领域。数据与程序的关联，程序与程序关联是研发人工智能过程中的一大阻力点。

架构上，深度学习需要一个 GPU 集群训练模型，用单独的计算框架（Caffe、Theano 等）。训练后的神经网络可以在单节点上运行。高层模型的训练和运行都可以在单节点运行。我们提供一个深度学习环境和一个基于 numpy/scipy 的环境就能满足大部分需求。有了运行环境，我们再用图来组织程序、模型和数据，并通过实时的消息分发和订阅让他们协同工作。

4.2.4. 超大型仿真

如果我们的顶点代表运行环境可支持的程序，边代表他们之间的数据流，那么我们可以构建超大型的生物、物理、社会科学和游戏仿真。目前的仿真模型支持的个体类型和数量十分有限。图计算可以让上百万个程序间可以相互感知、影响和演化。

4. 总结

从理论上来说，遍历更具普适性，将传统的序列式，并行和分布式计算融为一体。 GTM 和云计算的关系就像 ARM 和集成电路的关系。供应商提供了不同层次的实现，目前可以满足事务性（transactional）需求。在通用大数据计算上存在一些挑战，但在短期内可以用软件和硬件手段克服。

[1] M. Rodriguez, The Gremlin Graph Traversal Machine and Language, Proceedings of the ACM Database Programming Languages Conference, 2015 ↩
[2] M. Rodriguez, Mapping Semantic Networks to Undirected Networks, International Journal of Applied Mathematics and Computer Sciences, 2009 ↩
[3] J.M. Hernández-Lobato, R.P. Adams, Probabilistic Backpropagation for Scalable Learning of Bayesian Neural Networks, arxiv preprint, 2015 ↩
[4] W. Zaremba, I. Sutskever, Reinforcement Learning Neural Turing Machines, arxiv preprint, 2015 ↩
[5] J. Lu, J., et al, Transfer learning using computational intelligence: a survey. Knowledge-Based Systems, 2015 ↩