To Find Nodes (Descendants)
I am going to express query finding subtree 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 Descendant nodes
I explain the concept of a query to find descendant nodes of the node [B].
DEPTH|
|
0 | [A]---+--------------+
| [ ] | |
1 | [ ] [B]---+----+ [C]---+----+
| [ ] [ ] | | [ ] | |
2 | [ ] [ ] [D] [E] [ ] [F] [G]---+----+
| [ ] [ ] [ ] [ ] [ ] [ ] [ ] | |
3 | [ ] [ ] [ ] [ ] [ ] [ ] [ ] [H] [I]
| [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
-----+----------------------------------------------------
| 0 1 2 3 4 5 6 7 8 QUEUE
The above figure has been depicted as a bar graph. Please consider a bar of each node as building. Can not see buildings behind building that has same or more height. For example, can not see [F] from the [B].
When ceate query to find descendant nodes of node [B], consider as follows.
- On the right side of [B], look for the building of more than the height of the [B].
- The nodes between "found node" and [B] are descendant nodes.
The building that can be seen from [B] is the [C]. Thus, descendant nodes of [B] are between [B] and [C]. These are [C] [D] and [E].
Consider the actual query to find descendant nodes. Target to find descendant nodes is [B]. Query to find with conditions same or less depth from [B] on right side of [B] has next WHERE clause.
WHERE ff_queue > 1 AND ff_depth <= 1
Can determine the scope of the descendant nodes by "QUEUE of node on the far left" in that condition.
SELECT MIN(ff_queue)
FROM ff_tables
WHERE ff_queue > 1 AND ff_depth <= 1
;
When the query in above is defined as SBQ, the query to find descendant nodes of [B] is as follows.
SELECT *
FROM ff_tables
WHERE ff_queue > 1
AND ff_queue < (SBQ)
;
To summarize the above, we get the query to find the descendant nodes of [B].
SELECT *
FROM ff_tables
WHERE ff_queue > 1
AND ff_queue <
(
SELECT MIN(ff_queue)
FROM ff_tables
WHERE ff_queue > 1 AND ff_depth <= 1
)
;
The value of MIN(ff_queue) obtained in the subquery is four. Thus, the query to find the descendant nodes of [B] is equivalent as:
SELECT *
FROM ff_tables
WHERE ff_queue > 1
AND ff_queue < 4
;
The basic structure of the query to find the descendants node is in above. However, a bug remains in the query for actual using. Because there are some cases that subquery returns NULL. For example, when find descendant nodes of node [G], there is no building which has same or more height of [G] on right side of [G]. Since the subquery result is NULL, the entire query will result in an error.
To avoid this error, rewrite the query as follows. This new query gives us compensation results without having to be aware of the QUEUE position.
SELECT *
FROM ff_tables
WHERE ff_queue > 1
AND ff_queue <=
COALESCE(
(SELECT MIN(ff_queue) - 1
FROM ff_tables
WHERE ff_queue > 1 AND ff_depth <= 1
),
0x7fffffff
)
;
To Find Subtree
Subtree is a set of nodes that include base node and descendant nodes of base node. To create query to find subtree is so easy. It is a little bit change from query of descendant nodes.
SELECT *
FROM ff_tables
WHERE ff_queue >= 1
AND ff_queue <=
COALESCE(
(SELECT MIN(ff_queue) - 1
FROM ff_tables
WHERE ff_queue > 1 AND ff_depth <= 1
),
0x7fffffff
)
;
To Find Child Nodes
To create query to find child nodes is easy. It is to add one condition into WHERE clause in query to descendant nodes. "1 + 1" of the added condition means "(DEPTH of [B]) + 1".
SELECT *
FROM ff_tables
WHERE ff_queue > 1
AND ff_queue <=
COALESCE(
(SELECT MIN(ff_queue) - 1
FROM ff_tables
WHERE ff_queue > 1 AND ff_depth <= 1
),
0x7fffffff
)
AND ff_depth = 1 + 1
;
To Find Grandchild Nodes
It is easy as same as query to find child nodes. You Know that "1 + 2" means "(DEPTH of [B]) + 2".
SELECT *
FROM ff_tables
WHERE ff_queue > 1
AND ff_queue <=
COALESCE(
(SELECT MIN(ff_queue) - 1
FROM ff_tables
WHERE ff_queue > 1 AND ff_depth <= 1
),
0x7fffffff
)
AND ff_depth = 1 + 2
;
To Find Great-grandchild nodes And Great-great-grandchild nodes
Can generalize the query to find descendant nodes as same as ancestor nodes. When QUEUE of the base node is QQ and the DEPTH is DD, the query to find the descendent nodes of down to n-generations is generalized as follows. In case of great-grandchild: n = 3, In case of great-great-grandchild: n = 4. It is so neat.
SELECT *
FROM ff_tables
WHERE ff_queue > QQ
AND ff_queue <=
COALESCE(
(SELECT MIN(ff_queue) - 1
FROM ff_tables
WHERE ff_queue > QQ AND ff_depth <= DD
),
0x7fffffff
)
AND ff_depth = DD + n
;
To find descendant nodes by range specification
When add a condition into the WHERE clause of a query to find all descendant nodes, can create the query to find an descendant nodes of the range that specify. The query to find descendant nodes of [B] down to n-generations is as follows.
SELECT *
FROM ff_tables
WHERE ff_queue > 1
AND ff_depth >= 1 + n
AND ff_queue <=
COALESCE(
(SELECT MIN(ff_queue) - 1
FROM ff_tables
WHERE ff_queue > 1 AND ff_depth <= 1
),
0x7fffffff
)
;
Even if the tree data has several hundred depths, the query to find the descendant nodes is so simple. Because it only specifies the depth difference between the descendant node numerically.