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，還是要根據具體場景及需求來選擇。