Qirava DMS docs

Graph: breadth-first traversal

Graph traversal uses TRAVERSE <edge_table> DEPTH <n> FROM <node_id>. The edge table holds rows with integer from and to node ids. The engine runs a breadth-first search from the start node up to depth n, building the set of reached node ids, and then keeps the main (FROM) rows whose _id is in that reached set. Adjacency is served by an equality index on the edge table's from column when one exists (O(degree) per hop); otherwise the engine builds an adjacency map in a single scan rather than rescanning the edges at every level. This page covers the syntax, the BFS, and how reached nodes filter the result.

TRAVERSE syntax and the edge model#

TRAVERSE <edge_table> DEPTH <n> FROM <start> is a SELECT clause. The edge table is a normal table whose rows carry integer from and to fields (directed edges). The start node id must be an integer (it can be a bound :param). The main FROM table's rows are matched by their _id against the reached node set.

text

SELECT * FROM people TRAVERSE knows DEPTH 2 FROM 1

Breadth-first frontier#

Starting from the start node, the engine expands level by level. At each of the n hops it visits every node in the current frontier, collects its out-neighbors (edges where from = node, yielding to), and adds newly-seen nodes to the next frontier and to the reached set. A visited set prevents revisiting. The loop stops early if a level produces no new nodes. The start node itself is visited but not added to reached, so only nodes you can actually walk to are kept.

  reached = {}
  frontier = [start];  visited = {start}
  repeat DEPTH times:
      next = []
      for node in frontier:
          for to in neighbors(node):        # edges where from == node
              if to not visited: visit; next += to; reached += to
      if next empty: break
      frontier = next

BFS over an edge table

Adjacency: from-index vs one-scan map#

If the edge table has a single-field equality index on from, each hop probes that index for the node's out-edges — O(degree) per node, no full scan. Without such an index the engine builds the full adjacency map (from → [to, ...]) once in a single pass over the edges, then walks it for every BFS level — avoiding a re-scan per level.

Reached-set filter on the main rows#

After BFS, the FROM table's candidate rows are retained only when their _id is in the reached set. Other clauses (WHERE, projection, etc.) compose with this.

Request

-- people get _id 1,2,3,4 (a,b,c,d); edges knows: 1->2, 2->3, 3->4
SELECT * FROM people TRAVERSE knows DEPTH 1 FROM 1
SELECT * FROM people TRAVERSE knows DEPTH 2 FROM 1

Response

// DEPTH 1 FROM 1 -> count 1 (node 2 only)
// DEPTH 2 FROM 1 -> count 2 (nodes 2 and 3; data includes name "c")