OrientDB图遍历SQL之TRAVERSE

• 2019 年 10 月 27 日
• 筆記

本文介绍的TRAVERSE语法是基于OrientDB3.0.x版本，所有的SQL在OrientDB3.0.4社区版本自带的数据库demodb下试验，数据模型请参考demodb。

1.简介

TRAVERSE主要用于对图进行遍历。基于深度搜索算法或者广度搜索算法对图进行有限制的盲目搜索。它返回一个符合遍历条件的子图。

2.TRAVERSE语法格式介绍

根据官方文档，TRAVERSE的语法格式如下：

TRAVERSE <[class.]field>|*|any()|all()           [FROM <target>]           [             MAXDEPTH <number>             |             WHILE <condition>           ]           [LIMIT <max-records>]           [STRATEGY <strategy>]

下面我们对主要的语法点作下简要的介绍。

• 必须以TRAVERSE关键字开头，大小写不敏感。
• <[class.]field>|*|any()|all()

1.any() 和all() 在orientdb2.x支持该函数，在orientdb3.x试验下来，已不支持该函数。

2.根据官方文档TRAVERSE可以跟<field>字段。如下SQL，我们尝试执行如下两个SQL:

TRAVERSE Bio FROM (SELECT * FROM Profiles WHERE Id = 1)  TRAVERSE Hello FROM (SELECT * FROM Profiles WHERE Id = 1)  TRAVERSE out_HasFriend FROM (SELECT * FROM Profiles WHERE Id = 1)

分析：上图中Bio是Profiles的普通字段，而Hello不是Profiles的字段，out_HasFriend是系统自动为Profiles创建的边的record。TRAVERSE是基于relationship来遍历的，普通字段不会触发遍历，而对于边的遍历也仅仅遍历到边这一层而已。上图中展示一条记录也是Id为1的根记录，在TRAVERSE的查询结果中查询目标对象总会被查询出来，而且深度为0。

3.TRAVERSE后可跟9个函数：out()|in()|both()|outV()|inV()|bothV()|outE()|inE()|bothE()

• <target> 遍历的目标对象。可以是一个class、cluster、record id(s)、子查询。
• <number> 定义最大的遍历深度，0表示遍历根结点，不允许设置为负数。
• <condition> 定义遍历的结束条件。经常和变量$depth一起使用，后续会有例子说明。
• <max-records> 定义该命令可以返回结果的最大数量。
• <strategy> 定义遍历的策略。可选值有 DEPTH_FIRST(深度优先搜索)、 BREATH_FIRST（广度优先搜索）。默认为 DEPTH_FIRST。后续会有例子说明。

注意：where关键字不能用于该SQL。

3.TRAVERSE的使用

3.1.在browse控制台中使用

TRAVERSE * FROM (SELECT * FROM Profiles WHERE Id = 1)

3.2.在graph控制台中使用

TRAVERSE * FROM (SELECT * FROM Profiles WHERE Id = 1)

3.3.使用API

Maven依赖如下：

<dependency>      <groupId>com.orientechnologies</groupId>      <artifactId>OrientDB-graphdb</artifactId>      <version>3.0.4</version>  </dependency>  <dependency>      <groupId>com.orientechnologies</groupId>      <artifactId>OrientDB-core</artifactId>      <version>3.0.4</version>  </dependency>  <dependency>      <groupId>com.orientechnologies</groupId>      <artifactId>OrientDB-client</artifactId>      <version>3.0.4</version>  </dependency>

测试代码如下：

public class TraverseTest {      public static void main(String[] args) {              // 用户名和密码，请根据配置修改              OrientGraphFactory factory = new OrientGraphFactory("remote:localhost/demodb", "root", "root");              OrientGraphNoTx graphNoTx = factory.getNoTx();              // 执行TRAVERSE语句              Iterable<Element> iterable = graphNoTx.command(                      new OCommandSQL(                              "TRAVERSE * FROM (SELECT * FROM Profiles where Id = 1) LIMIT 10"                      )).execute();              Iterator<Element> it = iterable.iterator();              // 遍历TRAVERSE返回的结果集              while (it.hasNext()) {                  Element ele = it.next();                  System.out.println("@class=>" + ele.getProperty("@class") + ",rid=>" + ele.getId());              }              graphNoTx.shutdown();              factory.close();      }  }

4.SELECT、MATCH和TRAVERSE比较

4.1.使用优先级

在一般情况下按如下顺序选择使用：SELECT>MATCH>TRAVERSE。

一般SELECT性能最好，TRAVERSE最差。因为TRAVERSE是基于深度优先搜索或者广度优先搜索的盲目搜索算法，它返回是一个子图。

4.2.查询环

对于有些场景下可能会涉及到环的模型，如下图的环的模型。

根据此模型通过如下SQL在图库构造模型数据：

INSRET INTO V SET name = 'P0'  INSRET INTO V SET name = 'P1'  INSRET INTO V SET name = 'P2'  CREATE EDGEE FROM (SELECT FROM V where name = 'P0') TO (SELECT FROM V where name = 'P1')  CREATE EDGEE FROM (SELECT FROM V where name = 'P0') TO (SELECT FROM V where name = 'P2')  CREATE EDGEE FROM (SELECT FROM V where name = 'P1') TO (SELECT FROM V where name = 'P0')  CREATE EDGEE FROM (SELECT FROM V where name = 'P1') TO (SELECT FROM V where name = 'P2')

通过如下SQL，查看图中的模型数据。

SELECT FROM V WHERE name = 'P0'

然后我们分别执行如下SQL，观察查询结果：

SELECT expand(out().out()) FROM V WHERE name = 'P0'

MATCH      {class:v,WHERE:(name = 'P0')}-->{as:p2,maxDepth:2,depthAlias:da}  RETURN da,p2.name ORDER BY da ASC

SELECT $depth,$path,* FROM (TRAVERSE OUT() FROM (SELECT FROM V WHERE name = 'P0'))

分析：根据上述执行结果:

• SELECT的返回结果为：P0和P2。
• MATCH的一度返回结果结果为：P1和P2，二度返回结果为：P0和P2
• TRAVERSE的一度返回结果为P1和P2，二度返回结果为空。

第一个out()的返回结果即一度返回结果是P1和P2，这个是没有问题的。但对于第二个out()，SELECT和MATCH的二度返回结果P0是查询到环了，而P1是因为一度和二度是同一个点。而TRAVERSE却不存在这种问题。所以在有些场景下我们可以基于这三者的特性来综合使用。

4.3.使用场景

SELECT一般适用于类似RDBMS的查询需求，同时也可以使用此来查询特定路径的查询需求。

SELECT COUNT(*) FROM V  SELECT out().out() FROM Profiles WHERE Id = 1

MATCH一般适用基本确定的多条路径的查询。

MATCH      {as:customer,class:Customers,where:(Phone = '+1400844724')}.out('HasVisited'),      {as:customer}.out('HasStayed'),      {as:customer}.out('HasEaten')  RETURN DISTINCT customer   

TRAVERSE一般适用于不确定路径的查询遍历。

TRAVERSE * FROM V MAXDEPTH 4

但有些场景下可能需要要组合使用。所以具体还要基于使用场景使用，有些场景就是使用MATCH合适，有些场景下可能就是使用TRAVERSE合适。

5.TRAVERSE实战

5.1.编写注意事项

为了尽可能减少在遍历过程的查询范围，提高遍历性能，在写TRAVERSE语句时注意如下事项：

• 尽量缩小查询目标的范围。
• 尽量指定边的方向和名称。
• 尽量设置查询深度MAXDEPTH的大小。
• 尽量设置LIMIT的大小。

5.2.查询目标

FROM后的对象，我们暂时称之为查询目标。根据语法介绍部分，查询目标可以是一个class、cluster、record id(s)、子查询。

TRAVERSE * FROM Profiles  TRAVERSE * FROM cluster:profiles  TRAVERSE * FROM #41:0  TRAVERSE * FROM [#41:0,#41:1]  TRAVERSE * FROM (SELECT FROM Profiles WHERE Id = 1)

5.3.上下文变量的使用

TRAVERSE支持如下变量$current、$path和$depth，这几个变量都要和SELECT一起使用。

• $current 遍历的当前结点。也就是遍历路径上的最后一个node。
• $path 遍历的路径node集合。包括每条遍历路径上所有点或边或者点边的集合，这是一个很有用的变量，通过它可知道两个点之间的所有路径及路径上经过的点和边。
• $depth 遍历路径的深度。$depth也可与WHILE一起使用。

SELECT $path,$current,$depth,@class FROM (TRAVERSE * FROM V)

注意：TRAVERSE *时，遍历的结果包括点和边，遍历的深度是包括边的。

5.4.MAXDPTH的使用

MAXDEPTH用于设置TRAVERSE的遍历深度。"MAXDEPTH N"和"WHILE $depth <=N"，具有同样的查询结果。但区别是WHILE会评估到N+1度，然后舍弃N+1度的数据，所以平时在使用时建议使用MAXDEPTH。

TRAVERSE * FROM (SELECT FROM Profiles WHERE Id = 1) MAXDEPTH 2 LIMIT 10

TRAVERSE * FROM (SELECT FROM Profiles WHERE Id = 1) WHILE $depth <= 2 LIMIT 10

5.5.遍历策略的使用

TRAVERSE支持两种遍历策略:

• DEPTH_FIRST，基于深度优先搜索算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。如下图基于深度搜索算法的遍历顺序。

• BREADTH_FIRST，基于深度优先搜索算法。沿着树的宽度遍历树的节点，如果发现目标，则演算终止。如下图基于广度搜索算法的遍历顺序。

我们来验证下图两种遍历策略。先执行如下SQL，构造模型数据（基于深度优先搜索算法的选择分支和插入顺序有关，所以如下SQL在创建边时对顺序有所关注，方便后续验证问题）：

INSERT INTO V(name) VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),(12)  CREATE EDGE FROM (SELECT FROM V WHERE name = 1) TO (SELECT FROM V WHERE name = 8)  CREATE EDGE FROM (SELECT FROM V WHERE name = 1) TO (SELECT FROM V WHERE name = 7)  CREATE EDGE FROM (SELECT FROM V WHERE name = 1) TO (SELECT FROM V WHERE name = 2)  CREATE EDGE FROM (SELECT FROM V WHERE name = 8) TO (SELECT FROM V WHERE name = 12)  CREATE EDGE FROM (SELECT FROM V WHERE name = 8) TO (SELECT FROM V WHERE name = 9)  CREATE EDGE FROM (SELECT FROM V WHERE name = 2) TO (SELECT FROM V WHERE name = 6)  CREATE EDGE FROM (SELECT FROM V WHERE name = 2) TO (SELECT FROM V WHERE name = 3)  CREATE EDGE FROM (SELECT FROM V WHERE name = 9) TO (SELECT FROM V WHERE name = 11)  CREATE EDGE FROM (SELECT FROM V WHERE name = 9) TO (SELECT FROM V WHERE name = 10)  CREATE EDGE FROM (SELECT FROM V WHERE name = 3) TO (SELECT FROM V WHERE name = 5)  CREATE EDGE FROM (SELECT FROM V WHERE name = 3) TO (SELECT FROM V WHERE name = 4)

在OrientDB中的图展示如下：

SELECT FROM V WHERE name = 1

可通过如下SQL来验证，通过调整LIMIT的大小来观察两种遍历策略的情况。

TRAVERSE out() FROM (SELECT FROM V WHERE name = 1) LIMIT 1 STRATEGY DEPTH_FIRST  TRAVERSE out() FROM (SELECT FROM V WHERE name = 1) LIMIT 2 STRATEGY DEPTH_FIRST                                                           .                                                           .                                                           .  TRAVERSE out() FROM (SELECT FROM V WHERE name = 1) LIMIT 12 STRATEGY DEPTH_FIRST

TRAVERSE out() FROM (SELECT FROM V WHERE name = 1) LIMIT 1 STRATEGY BREADTH_FIRST  TRAVERSE out() FROM (SELECT FROM V WHERE name = 1) LIMIT 2 STRATEGY BREADTH_FIRST                                                           .                                                           .                                                           .  TRAVERSE out() FROM (SELECT FROM V WHERE name = 1) LIMIT 12 STRATEGY BREADTH_FIRST

限于篇幅，请自行验证。

5.6.基于使用场景的选择

场景：查询Id=1的Profiles的二度朋友。

根据4.1.使用优先级我们分别按SELECT、MATCH和TRAVERSE的实现如下：

SELECT:

SELECT out('HasFriend').out('HasFriend') FROM Profiles WHERE Id = 1

MATCH:

MATCH      {class:Profiles,WHERE:(Id = 1)}-HasFriend->{}-HasFriend->{as:friend}  RETURN friend LIMIT 100

TRAVERSE:

SELECT * FROM (TRAVERSE out('HasFriend') FROM (SELECT * FROM Profiles WHERE Id = 1) MAXDEPTH 2) WHERE $depth = 2

分析：根据上述结果SELECT的返回结果数量为45，MATCH的返回结果数量也是45，且通过对比SELECT和MATCH的返回结果是一致的。但是TRAVERSE的返回结果却是空。那么究竟哪个是正确的呢？

我们先看下这Id=1的二度及以内的朋友关系子图。

MATCH      {class:Profiles,WHERE:(Id = 1)}-HasFriend->{}-HasFriend->{as:friend}  RETURN $pathElements LIMIT 100

通过这个子图，我们知道所有二度的朋友同时也是一度的朋友，是4.2.查询环所描述的情形的一种。此种场景下如果有明确的需求要求二度朋友不能是一度朋友，那么只有TRAVERSE的结果是满足需求的。

但如果需求要求二度朋友也可以是一度朋友，那么就要使用SELECT或者MATCH了。但根据上图，即使二度朋友也可以是一度朋友，那么二度朋友的数量应该是9(Id=2的Profiles不是二度朋友)，而不是45才对。问题出在哪儿了？因为多个一度朋友可能有同一个二度朋友，所以二度朋友存在重复了，可借助set()函数或者distinct关键字去重，去重SQL如下。

SELECT set(out('HasFriend').out('HasFriend')) FROM Profiles WHERE Id = 1

MATCH      {class:Profiles,WHERE:(Id = 1)}-HasFriend->{}-HasFriend->{as:friend}  RETURN distinct friend LIMIT 100

MATCH      {class:Profiles,WHERE:(Id = 1)}-HasFriend->{}-HasFriend->{as:friend}  RETURN set(friend) LIMIT 100

至此SELECT和MATCH好像已经完美的解决问题了，对于此模型是没有问题，因为它不存在4.2.查询环提到的P0-P1且P1->P0的情况，即一度朋友可能是Id=1的Profiles本身，二度朋友也可能是一度朋友本身或者是Id=1的Profiles本身。假如存在这种问题，怎么办？这种场景下SELECT已经很难实现，我们直接放弃，我们需要修改MATCH。如下SQL:

MATCH      {as:p0,class:Profiles,WHERE:(Id = 1)}-HasFriend->{as:friend1,WHERE:($currentMatch != $matched.p0)}-HasFriend->{as:friend2,WHERE:($currentMatch != $matched.p0 AND $currentMatch != $matched.friend1)}  RETURN set(friend2) LIMIT 100

总结：最终应该使用哪种SQL，还是要根据具体场景及需求来选择。