OrientDB图遍历SQL之TRAVERSE
OrientDB图遍历SQL之TRAVERSE
本文介绍的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()
函数 | 示例 | 查询目标 | 遍历结果 | 方向 |
|---|---|---|---|---|
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控制台中使用
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 = 1MATCH一般适用基本确定的多条路径的查询。
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_FIRSTTRAVERSE 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，还是要根据具体场景及需求来选择。