Breadth First/Depth First Searches & Reporting | CREATE RECURSIVE VIEW | Vantage - 17.10 - Breadth First and Depth First Searches - Advanced SQL Engine - Teradata Database

Teradata Vantage™ - SQL Data Definition Language Detailed Topics

Product
Advanced SQL Engine
Teradata Database
Release Number
17.10
Release Date
July 2021
Content Type
Programming Reference
Publication ID
B035-1184-171K
Language
English (United States)

Hierarchical trees can be traversed either breadth first or depth first. These searches are abbreviated as indicated by the following table.

Abbreviation Definition
BFS Breadth first search

See Breadth First Reporting.

DFS Depth first search

See Depth First Reporting.

In a BFS, each immediate child of a node is visited before any of its grandchildren.

In a DFS, all descendants of each immediate node in the graph are visited before visiting other immediate children of that node.

Consider the following graph of a parts hierarchy.


Parts hierarchy comprising 12 nodes

If this graph is searched breadth first, its nodes are visited in the following order.

      p1   p2   p3   p4   p5   p6   p7   p8   p9   p10   p11   p12

In contrast, if the graph is searched depth first, its nodes are visited in the following order.

      p1   p2   p5   p6   p7   p3   p8   p9   p4   p10   p11   p12

The real effect of specifying a BFS versus a DFS is the ordering of the result set. As a result, it is simple to simulate a BFS or a DFS by simple ordering of the output.