暂无图片
暂无图片
暂无图片
暂无图片
暂无图片
首页 / OrientDB图遍历SQL之TRAVERSE

OrientDB图遍历SQL之TRAVERSE

图数据库 2021-04-26
1048

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

1.简介

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

2.TRAVERSE语法格式介绍

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

  1. TRAVERSE <[class.]field>|*|any()|all()
  2.          [FROM <target>]
  3.          [
  4.            MAXDEPTH <number>
  5.            |
  6.            WHILE <condition> 
  7.          ]
  8.          [LIMIT <max-records>]
  9.          [STRATEGY <strategy>]

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

  • 必须以TRAVERSE关键字开头，大小写不敏感。

  • <[class.]field>|*|any()|all()

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

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

  1.   TRAVERSE Bio FROM (SELECT * FROM Profiles WHERE Id = 1)
  2.   TRAVERSE Hello FROM (SELECT * FROM Profiles WHERE Id = 1)
  3.   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()

函数示例查询目标遍历结果方向
out()TRAVERSE out() FROM V LIMIT 8点点左指向右

TRAVERSE out('EdgeClass') FROM V LIMIT 8点点左指向右
in()TRAVERSE in() FROM V LIMIT 8点点右指向左

TRAVERSE in('EdgeClass') FROM V LIMIT 8点点右指向左
both()TRAVERSE both() FROM V LIMIT 8点点任意

TRAVERSE both('EdgeClass') FROM V LIMIT 8点点任意
outE()TRAVERSE outE() FROM V LIMIT 8点边左指向右

TRAVERSE outE('EdgeClass') FROM V LIMIT 8点边左指向右
inE()TRAVERSE inE() FROM V LIMIT 8点边右指向左

TRAVERSE inE('EdgeClass') FROM V LIMIT 8点边右指向左
bothE()TRAVERSE bothE() FROM V LIMIT 8点边任意

TRAVERSE bothE('EdgeClass') FROM V LIMIT 8点边任意
outV()TRAVERSE outV() FROM E LIMIT 8边点左指向右

TRAVERSE outV('EdgeClass') FROM E LIMIT 8边点左指向右
inV()TRAVERSE inV() FROM E LIMIT 8边点右指向左

TRAVERSE outV('EdgeClass') FROM E LIMIT 8边点右指向左
bothV()TRAVERSE V() FROM E LIMIT 8边点任意

TRAVERSE V('EdgeClass') FROM E LIMIT 8边点任意
*TRAVERSE * FROM V LIMIT 8点点和边任意

TRAVERSE * FROM E LIMIT 8边点和边任意

  • <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控制台中使用

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

3.2.在graph控制台中使用

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

3.3.使用API

Maven依赖如下：

  1. <dependency>
  2.     <groupId>com.orientechnologies</groupId>
  3.     <artifactId>OrientDB-graphdb</artifactId>
  4.     <version>3.0.4</version>
  5. </dependency>
  6. <dependency>
  7.     <groupId>com.orientechnologies</groupId>
  8.     <artifactId>OrientDB-core</artifactId>
  9.     <version>3.0.4</version>
  10. </dependency>
  11. <dependency>
  12.     <groupId>com.orientechnologies</groupId>
  13.     <artifactId>OrientDB-client</artifactId>
  14.     <version>3.0.4</version>
  15. </dependency>

测试代码如下：

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

4.SELECT、MATCH和TRAVERSE比较

4.1.使用优先级

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

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

4.2.查询环

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

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

  1. INSRET INTO V SET name = 'P0'
  2. INSRET INTO V SET name = 'P1'
  3. INSRET INTO V SET name = 'P2'
  4. CREATE EDGEE FROM (SELECT FROM V where name = 'P0') TO (SELECT FROM V where name = 'P1')
  5. CREATE EDGEE FROM (SELECT FROM V where name = 'P0') TO (SELECT FROM V where name = 'P2')
  6. CREATE EDGEE FROM (SELECT FROM V where name = 'P1') TO (SELECT FROM V where name = 'P0')
  7. CREATE EDGEE FROM (SELECT FROM V where name = 'P1') TO (SELECT FROM V where name = 'P2')

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

  1. SELECT FROM V WHERE name = 'P0'

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

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

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

  1. 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的查询需求，同时也可以使用此来查询特定路径的查询需求。

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

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

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

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

  1. TRAVERSE * FROM V MAXDEPTH 4

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

5.TRAVERSE实战

5.1.编写注意事项

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

  • 尽量缩小查询目标的范围。

  • 尽量指定边的方向和名称。

  • 尽量设置查询深度MAXDEPTH的大小。

  • 尽量设置LIMIT的大小。

5.2.查询目标

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

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

5.3.上下文变量的使用

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

  • $current 遍历的当前结点。也就是遍历路径上的最后一个node。

  • $path 遍历的路径node集合。包括每条遍历路径上所有点或边或者点边的集合，这是一个很有用的变量，通过它可知道两个点之间的所有路径及路径上经过的点和边。

  • $depth 遍历路径的深度。$depth也可与WHILE一起使用。

  1. 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。

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

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

5.5.遍历策略的使用

TRAVERSE支持两种遍历策略:

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

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

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


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

在OrientDB中的图展示如下：

  1. SELECT FROM V WHERE name = 1

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

  1. TRAVERSE out() FROM (SELECT FROM V WHERE name = 1) LIMIT 1 STRATEGY DEPTH_FIRST
  2. TRAVERSE out() FROM (SELECT FROM V WHERE name = 1) LIMIT 2 STRATEGY DEPTH_FIRST
  3.                                                          .
  4.                                                          .
  5.                                                          .
  6. TRAVERSE out() FROM (SELECT FROM V WHERE name = 1) LIMIT 12 STRATEGY DEPTH_FIRST
  1. TRAVERSE out() FROM (SELECT FROM V WHERE name = 1) LIMIT 1 STRATEGY BREADTH_FIRST
  2. TRAVERSE out() FROM (SELECT FROM V WHERE name = 1) LIMIT 2 STRATEGY BREADTH_FIRST
  3.                                                          .
  4.                                                          .
  5.                                                          .
  6. 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:

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

MATCH:

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

TRAVERSE:

  1. 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的二度及以内的朋友关系子图。

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

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

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

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

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

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

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

  1. MATCH
  2.     {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)}
  3. RETURN set(friend2) LIMIT 100

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

温馨提示：如果在微信PC端浏览，请使用系统浏览器，效果最佳



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

评论