Fertile Forest Model (4/n) To Find Nodes (Ancestors)

To Find Nodes (Ancestors)

I am going to express query finding ancestor nodes by the following tree structure data. [A], [B], ... indicated in figure means nodes.

DEPTH|
   0 | [A]--+-----------+
     |      |           |
   1 |     [B]--+---+  [C]--+---+
     |          |   |       |   |
   2 |         [D] [E]     [F] [G]--+---+
     |                              |   |
   3 |                             [H] [I]
-----+-------------------------------------------
     |  0   1   2   3   4   5   6   7   8   QUEUE

To Find Ancestor Nodes

Consider a query to find the ancestor node of [F]. Those satisfying the following conditions will be the ancestor node of [F].

1. Has the above DEPTH than [F]. (ff_depth < 2)
2. Nodes to the left than [F]. (ff_queue < 5)
3. The node at the far right for each DEPTH.
   (MAX(ff_queue), GROUP BY ff_depth)

Conditions of "Has the above DEPTH than [F]" and "Nodes to the left than [F]" are specified as the WHERE clause such as the following.

WHERE ff_queue < 5 AND ff_depth < 2

Procedure to find "Node at the far right for each depth" as:

1. Group by ff_depth, and select maximum number of ff_queue.
2. Get the node with the ff_queue that matches the maximum number of ff_queue.

To summarize the above, it is as:

SELECT *
  FROM ff_tables
  WHERE ff_queue IN
    (SELECT MAX(ff_queue)
      FROM ff_tables
      WHERE ff_queue < 5 AND ff_depth < 2
      GROUP BY ff_depth
    )
;

To Find Parent Node

To create a query to find parent node is so easy. It is a little bit to modify WHERE clause in the finding query of ancestor node.

SELECT *
  FROM ff_tables
  WHERE ff_queue IN
    (SELECT MAX(ff_queue)
      FROM ff_tables
      WHERE ff_queue < 5 AND ff_depth = (2 - 1)
      GROUP BY ff_depth
    )
;

ff_depth < 2 has changed ff_depth = (2 - 1) in the subquery. (2 - 1) means that (DEPTH of [F] - 1).

To Find Root Node

To create query to find root node of base node is like the parent node. By just slightly modified search query ancestor node.

SELECT *
  FROM ff_tables
  WHERE ff_queue IN
    (SELECT MAX(ff_queue)
      FROM ff_tables
      WHERE ff_queue < 5 AND ff_depth = 0
      GROUP BY ff_depth
    )
;

To Find Grandparent Node

In example of the parent node and root node, the query was created by simply changing a little bit from query of ancestor nodes. The query to retrieve a grandparent node and great-grandparents nodes can be created by the same idea.

Grandparent node of [F]

SELECT *
  FROM ff_tables
  WHERE ff_queue IN
    (SELECT MAX(ff_queue)
      FROM ff_tables
      WHERE ff_queue < 5
        AND ff_depth = 2 - 2
      GROUP BY ff_depth
    )
;

Great-grandparent node of [H]

SELECT *
  FROM ff_tables
  WHERE ff_queue IN
  (SELECT MAX(ff_queue)
    FROM ff_tables
    WHERE ff_queue < 7
      AND ff_depth = 3 - 3
    GROUP BY ff_depth
  )
;

To Generalize The Query To Find Ancestor Node Before N-Generations

When base node has QUEUE = QQ, DEPTH = DD, can generalize the query to find ancestor nodes before n-generations as:

SELECT *
  FROM ff_tables
  WHERE ff_queue IN
    (SELECT MAX(ff_queue)
      FROM ff_tables
      WHERE ff_queue < QQ AND ff_depth = DD - n
      GROUP BY ff_depth
    )
;

To Find Ancestor Nodes By Range Specification

When add a condition into the WHERE clause of a query to find all ancestor nodes, can create the query to find an ancestor nodes of the range that specify.

Query to find the ancestor nodes of [H] up to 2 generations.

SELECT *
  FROM ff_tables
  WHERE ff_queue IN
    (SELECT MAX(ff_queue)
      FROM ff_tables
      WHERE ff_queue < 7 AND ff_depth < 3
        AND ff_depth >= 3 - 2
      GROUP BY ff_depth
    )
;