SQLite Forum

Breadth-first graph traversal
Login
I've learned it from a [book about database concepts](https://www.mitp.de/IT-WEB/Datenbanken/Datenbanken-Konzepte-und-Sprachen-oxid.html) (chapter 11.5.2):

> Traversing order
>
> The SQL standard provides an optional traversing clause, which determines the order in which the the nodes of the graph are visited. This is possible via the clause
>
> `SEARCH BREADTH FIRST BY column SET pseudo-column`
>
> the width search is possible, through which first all directly connected  nodes (in
> in our example the places that can be reached directly from the starting point)
> then the nodes are output over two edges (places marked with
> (which can be reached with a single change), then the nodes over three edges
> etc.
>
> On the other hand, by specifying the clause
> 
> `SEARCH DEPTH FIRST BY column SET pseudo-column`
>
> forced a depth search. At first a path is searched until the end
> before the next path is visited.
>
> In both cases, column specifies the attribute to be used for navigation -
> so it must be an attribute from the condition of the recursive compound
> be. The clause generates a pseudo column in the query result,
> in the non-recursive part of the request by an ORDER BY clause
> can be evaluated.
> 
> (Translated with www.DeepL.com/Translator (free version))

So, to me it looked as if it were part of SQL standard. Appearently, it's supported in Oracle and IBM DB2. The latter contains the following [example](https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_73/sqlp/rbafyrecursivequeries.htm):

```sql
WITH destinations (departure, arrival, connections, cost) AS 
    (SELECT f.departure, f.arrival, 0, price
            FROM flights f 
            WHERE f.departure = 'Chicago' 
     UNION ALL 
     SELECT r.departure, b.arrival, r.connections + 1,
                r.cost + b.price 
            FROM destinations r, flights b 
            WHERE r.arrival = b.departure) 
    SEARCH BREADTH FIRST BY arrival SET ordcol 
SELECT * 
  FROM destinations 
  ORDER BY ordcol```