# 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] Great-grandparent node of [H]
``` 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 ) ;``` ``` 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 ) ;```