SQL - `TRAVERSE`

Retrieves connected records crossing relationships. This works with both the Document and Graph API’s, meaning that you can traverse relationships between say invoices and customers on a graph, without the need to model the domain using the Graph API.

In many cases, you may find it more efficient to use SELECT, which can result in shorter and faster queries. For more information, see TRAVERSE versus SELECT below.

Syntax

TRAVERSE <projection> [, <projection>]*   (a field, or a function such as out(), in() or both())
         FROM <target>
         [MAXDEPTH <number>]
         [WHILE <condition>]
         [LIMIT <max-records>]
         [STRATEGY DEPTH_FIRST|BREADTH_FIRST]

<fields> Defines the fields you want to traverse.
<target> Defines the target you want to traverse. This can be a type, one or more buckets, a single Record ID, set of Record ID’s, or a sub-query.
MAXDEPTH Defines the maximum depth of the traversal. 0 indicates that you only want to traverse the root node. Negative values are invalid. The result is every record reachable within that many hops of a root, whichever strategy is used.
WHILE Defines the condition for continuing the traversal while it is true. It is evaluated on every record before it is traversed, the roots included: a root that does not satisfy it is neither returned nor traversed. MAXDEPTH and WHILE can be used together.
LIMIT Defines the maximum number of results the command can return.
STRATEGY Defines strategy for traversing the graph. It also decides what $depth and $path mean on a graph where a record can be reached by more than one path, see Traversal Strategies.

TRAVERSE has no WHERE clause. To filter the traversed records, wrap the TRAVERSE in a SELECT, as in the examples below.

There is a difference between MAXDEPTH N and WHILE $depth <= N: the MAXDEPTH will evaluate exactly N levels, while the WHILE will evaluate N+1 levels and will discard the N+1th, so the MAXDEPTH in general has better performance. Both return the same records.

Examples

In a social network-like domain, a user profile is connected to friend through links. The following examples consider common operations on a user with the record ID #10:1234.

Traverse the outgoing edges of the root record (* is not accepted after TRAVERSE; use out(), in() or both()):

ArcadeDB> TRAVERSE out() FROM #10:1234

Specify fields and depth up to the third level, using the BREADTH_FIRST strategy:

ArcadeDB> TRAVERSE out("Friend") FROM #10:1234 MAXDEPTH 3
            STRATEGY BREADTH_FIRST

Execute the same command, this time filtering for a minimum depth to exclude the first target vertex:

ArcadeDB> SELECT FROM (TRAVERSE out("Friend") FROM #10:1234 MAXDEPTH 3)
            WHERE $depth >= 1

Bound the depth with MAXDEPTH or WHILE in the inner TRAVERSE rather than with $depth in the outer SELECT. It is much more efficient, because the traversal stops there instead of walking the whole graph. It is also correct with both strategies, while an outer WHERE $depth <= N returns every record within N hops only with STRATEGY BREADTH_FIRST: with the default DEPTH_FIRST, a record first reached through a longer path carries that longer $depth and is filtered out, see Traversal Strategies. Filtering out only the root, as above, is safe with both: the roots are the only records at depth 0.

Combine traversal with SELECT command to filter the result-set. Repeat the above example, filtering for users in Rome:

ArcadeDB> SELECT FROM (TRAVERSE out("Friend") FROM #10:1234 MAXDEPTH 3)
            WHERE city = 'Rome'

Extract movies of actors that have worked, at least once, in any movie produced by J.J. Abrams:

ArcadeDB> SELECT FROM (TRAVERSE out("Actors"), out("Movies") FROM (SELECT FROM
            Movie WHERE producer = "J.J. Abrams") MAXDEPTH 3) WHERE
            @type = 'Movie'

Display the current path in the traversal:

ArcadeDB> SELECT $path FROM ( TRAVERSE out() FROM V MAXDEPTH 10 )

Supported Variables

Fields

Defines the fields that you want to traverse. If set to *, then it traverses all fields. This can prove costly to performance and resource usage, so it is recommended that you optimize the command to only traverse the pertinent fields.

In addition to his, you can specify the fields at a type-level. Inheritance is supported. By specifying Person.city and the type Customer extends person, you also traverse fields in Customer.

Field names are case-sensitive, types not.

Target

Targets for traversal can be:

<type> Defines the type that you want to traverse.
BUCKET:<bucket> Defines the bucket you want to traverse.
<record-id> Individual root Record ID that you want to traverse.
[<record-id>,<record-id>,…] Set of Record ID’s that you want to traverse. This is useful when navigating graphs starting from the same root nodes.

Context Variables

In addition to the above, you can use the following context variables in traversals:

$parent Gives the parent context, if any. You may find this useful when traversing from a sub-query.
$current Gives the current record in the iteration. To get the upper-level record in nested queries, you can use $parent.$current.
$depth Gives the number of hops from the root to the current record, along $path. The root is at depth 0.
$path Gives the path the traversal followed to reach the current record, as the list of its Record IDs from the root to the record itself (for instance [#8:0, #8:1, #8:3]). It always has $depth + 1 elements. You can also display it through SELECT:

ArcadeDB> SELECT $path, $depth FROM (TRAVERSE out() FROM #10:1234)

$stack Gives the same Record IDs as $path, in reverse order: the current record first, the root last.

With STRATEGY BREADTH_FIRST, $depth is the shortest distance from the root. With the default DEPTH_FIRST it can be longer, see Traversal Strategies.

Use Cases

TRAVERSE versus SELECT

When you already know traversal information, such as relationship names and depth-level, consider using SELECT instead of TRAVERSE as it is faster in some cases.

For example, this query traverses the follow relationship from the Twitter account #10:1234, getting the accounts at the second level of friendship, that is the accounts it does not follow directly but that the accounts it follows do:

ArcadeDB> SELECT FROM (TRAVERSE out('follow') FROM #10:1234 MAXDEPTH 2
          STRATEGY BREADTH_FIRST) WHERE $depth = 2

STRATEGY BREADTH_FIRST is what makes $depth = 2 mean "two hops away and not closer", see Traversal Strategies. Note that the traversal starts from one account: each record is returned once per TRAVERSE, so starting from every account (FROM TwitterAccounts) makes them all roots, an account is typically returned at depth 0, and $depth = 2 finds next to nothing.

If you only need the accounts reachable in exactly two hops, you can express it with a SELECT, in a way that is also shorter and faster:

ArcadeDB> SELECT expand(out('follow').out('follow')) FROM #10:1234

The two are not the same query: the SELECT also returns an account the root follows directly when it is followed by another account the root follows, and returns an account once for every path that reaches it.

TRAVERSE with the Graph Model and API

While you can use the TRAVERSE command with any domain model, it provides the greatest utility with the Graph Model.

This model is based on the concepts of the Vertex (or Node) and the Edge (or Arc, Connection, Link, etc.) If you want to traverse in a direction, you have to use the type name when declaring the traversing fields. The supported directions are:

Vertex to outgoing edges Using outE() or outE('EdgeTypeName'). That is, going out from a vertex and into the outgoing edges.
Vertex to incoming edges Using inE() or inE('EdgeTypeName'). That is, going from a vertex and into the incoming edges.
Vertex to all edges Using bothE() or bothE('EdgeTypeName'). That is, going from a vertex and into all the connected edges.
Edge to Vertex (end point) Using inV() . That is, going out from an edge and into a vertex.
Edge to Vertex (starting point) Using outV() . That is, going back from an edge and into a vertex.
Edge to Vertex (both sizes) Using bothV() . That is, going from an edge and into connected vertices.
Vertex to Vertex (outgoing edges) Using out() or out('EdgeTypeName'). This is the same as outE().inV()
Vertex to Vertex (incoming edges) Using in() or in('EdgeTypeName'). This is the same as inE().outV()
Vertex to Vertex (all directions) Using both() or both('EdgeTypeName').

For instance, traversing outgoing edges on the record #10:3434:

ArcadeDB> TRAVERSE out() FROM #10:3434

In a domain for emails, to find all messages sent on January 1, 2012 from the user Luca, assuming that they are stored in the vertex type User and that the messages are contained in the vertex type Message. Sent messages are stored as out connections on the edge type SentMessage:

ArcadeDB> SELECT FROM (TRAVERSE outE(), inV() FROM (SELECT FROM User WHERE
          name = 'Luca') WHILE $depth &lt;= 2 AND (@type = 'User' OR
          @type = 'Message' OR (@type = 'SentMessage' AND
          sentOn = '01/01/2012'))) WHERE @type = 'Message'

The WHILE condition accepts User too because it is also evaluated on the root: without it, the traversal would stop before leaving the user.

Traversal Strategies

When ArcadeDB traverses a graph it can use one of two available approaches, either explore every branch to its leaf before backtracking (depth-first), or visiting each child before progressing down the next level (breadth-first), see:

By default, the depth-first strategy is used.

A TRAVERSE returns each record at most once, even when several roots or several paths reach it. Without a LIMIT, both strategies return the same records, and MAXDEPTH N (or WHILE $depth <= N) returns every record within N hops with either of them. What differs is the order of the results and, on a graph where a record can be reached by paths of different lengths, the $depth and $path a record is returned with:

Strategy Order of the results $depth and $path of a record

Strategy	Order of the results	`$depth` and `$path` of a record
`DEPTH_FIRST` (default)	A branch is explored to its end before the next one	The path the walk took. It can be longer than the shortest one
`BREADTH_FIRST`	All the records at depth N before any record at depth N+1	A shortest path. `$depth` is the distance from the root

DEPTH_FIRST (default)

A branch is explored to its end before the next one

The path the walk took. It can be longer than the shortest one

BREADTH_FIRST

All the records at depth N before any record at depth N+1

A shortest path. $depth is the distance from the root

For example, if A reaches X through A → B → X and also through A → C → D → E → X, a depth-first traversal that explores the C branch first returns X with $depth 4 and the longer path, while a breadth-first one always returns it with $depth 2. On a tree, where every record has only one path from the root, the two strategies return the same $depth and $path.

When the meaning of $depth matters, as when you filter or group the results by it in an outer SELECT (WHERE $depth = 2, "the friends of my friends"), use STRATEGY BREADTH_FIRST. With the default DEPTH_FIRST, SELECT FROM (TRAVERSE …) WHERE $depth <= 2 can miss records that are within 2 hops, because they were first reached through a longer path. To only bound the traversal, MAXDEPTH and WHILE are correct with both strategies.

SQL - TRAVERSE

Traversal Strategies

SQL - `TRAVERSE`