To Find Nodes (Kinships)
I am going to express query finding kinship 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 Sibling Nodes
On Sun, 18 Oct 2015 14:30:00 +0000UTC, I discovered an once query to find sibling nodes of any node. The considering procedure is as:
- [X] means base node.
- The node in conditions as follows is as Qh (Queue head).
- Has QUEUE lesser than [X].
- Has DEPTH lesser than [X].
- Has greatest QUEUE in above conditions.
- The node in conditions as follows is as Qt (Queue tail).
- Has QUEUE greater than [X].
- Has DEPTH lesser than [X].
- Has least QUEUE in above conditions.
- Sibling nodes meet conditions as follow:
- The node has QUEUE between Qh and Qt.
(Qh < QUEUE < Qt) - Has same DEPTH of [X].
- The node has QUEUE between Qh and Qt.
I am going to create a query to find for sibling nodes of [F]. Fq means QUEUE of [F], and Fd means DEPTH of [F]. The subquery to find Qh and Qt of [F] as follow.
QhSBQ (subquery to find Qh):
SELECT MAX(ff_queue)
FROM ff_table
WHERE ff_depth < Fd
AND ff_queue < Fq
QtSBQ (subquery to find Qt):
SELECT MIN(ff_queue)
FROM ff_table
WHERE ff_depth < Fd
AND ff_queue > Fq
The constitution of main query that includes two subqueries is as:
SELECT * FROM ff_table
WHERE ff_depth = Fd
AND ff_queue > (QhSBQ)
AND ff_queue < (QtSBQ)
;
In summary, we got the query to find sibling nodes as follow.
SELECT * FROM ff_table
WHERE ff_depth = Fd
AND ff_queue > (
SELECT MAX(ff_queue) FROM ff_table
WHERE ff_depth < Fd AND ff_queue < Fq
)
AND ff_queue < (
SELECT MIN(ff_queue) FROM ff_table
WHERE ff_depth < Fd AND ff_queue > Fq
)
;
This query contains a bug that causes a runtime error, as well as the query to retrieve the descendant node. Because of, when can not find Qh or Qt, the subquery result is NULL.
To avoid the bug by using the COALESCE() as:
SELECT * FROM ff_table
WHERE ff_depth = Fd
AND ff_queue >=
COALESCE(
(
SELECT MAX(ff_queue) + 1 FROM ff_table
WHERE ff_depth < Fd
AND ff_queue < Fq
),
0
)
AND ff_queue <=
COALESCE(
(
SELECT MIN(ff_queue) - 1 FROM ff_table
WHERE ff_depth < Fd
AND ff_queue > Fq
),
0x7fffffff
)
;
To Find Any Kind of Kinship Nodes.
On Sun, 18 Oct 2015 14:30:00 +0000UTC, I have just discovered an single query for finding any kinship nodes, by applying query to find sibling nodes.
Consider the generalization to find kinship nodes on the basis of the search of the brother node.
We can define sibling node as:
Replace "parent node" to "the node which has one upper depth" the parent node.
In addition, replace "child node" to "node which has one downer depth".
Now, preparation of generalization is over.
In the figure below, all cousin nodes of [D] is ([D], [E], [F], [G]).
DEPTH|
0 | [A]--+-----------+
| | |
1 | [B]--+---+ [C]--+---+
| | | | |
2 | [D] [E] [F] [G]--+---+
| | |
3 | [H] [I]
-----+-------------------------------------------
| 0 1 2 3 4 5 6 7 8 QUEUE
When to express the cousin nodes of [D] by using the definition of sibling node, the expression is as follows.
The "one" has changed to the "two" in the definition of cousin nodes of [D].
The relatives other than one own direct line of ancestors and descendants is said "collateral". Below is a list of collateral level.
| Collateral | Level |
|---|---|
| Sibling | 1 |
| Cousin | 2 |
| Second Cousin | 3 |
| Third Cousin | 4 |
| ... | ... |
Replace the changed word between the definition of sibling nodes and cousin node, to N.
When rewritten definition of the query to find sibling nodes for generalization, it is as follows. [X] means base node, Xq means QUEUE of [X], Xd means DEPTH of [X] and NN means "n".
SELECT * FROM ff_table
WHERE ff_depth = Xd
AND ff_queue >=
COALESCE(
(
SELECT MAX(ff_queue) + 1 FROM ff_table
WHERE ff_depth <= Xd - NN
AND ff_queue < Xq
),
0
)
AND ff_queue <=
COALESCE(
(
SELECT MIN(ff_queue) - 1 FROM ff_table
WHERE ff_depth <= Xd - NN
AND ff_queue > Xq
),
0x7fffffff
)
;
We can find collateral nodes of the same depth as the base node by using query above. However, we can not get right result in the following cases.
The above query get extra nodes from over the root node of target node on next tree.
We can avoid the bug easily by adding "AND Xd < NN" into WHERE clause of the query. However, we know the condition before creating the query. Therefore, it would be reasonable to use "if statement" for branching in actual library of FF model.
Perfect Generalization to find kinship nodes
I am going to expand the generalization further, for finding piblings (uncles and aunts) and niblings (nephews and nieces).
Rewrite the definition as follows. It is changed the upper and lower depth to "Nup" and "Ndown".
Nup and Ndown will change by relatives.
| Diff. | Direct | Collateral | |||
|---|---|---|---|---|---|
| -4 | Great-Great-Grand Parents | ||||
| -3 | Great-Grand Parents | Great-Grand Pibling | |||
| -2 | Grand Parent | Grand Pibling | first cousin twice removed | ||
| -1 | Parent | Pibling | first cousin once removed | second cousin once removed | |
| 0 | Self | Sibling | Cousin | Second Cousin | Third Cousin |
| 1 | Child | Nibling | first Cousin Once Removed | Second Cousin Once Removed | Third Cousin Once Removed |
| 2 | Grand Child | Grand Nibling | first Cousin Twice Removed | Second Cousin Twice Removed | Third Cousin Twice Removed |
| 3 | Great-Grand Child | Great-Grand Nibling | first Cousin Thrice Removed | Second Cousin Thrice Removed | Third Cousin Thrice Removed |
| 4 | Great-Great-Grand Child | Great-Great-Grand Nibling | first Cousin 4 times Removed | Second Cousin 4 times Removed | Third Cousin 4 times Removed |
| 4 | Great-Great-Great-Grand Child | Great-Great-Great-Grand Nibling | first Cousin 5 times Removed | Second Cousin 5 times Removed | Third Cousin 5 times Removed |
When to check relation between self and nibling. Firstly to move to parent node (-1), and then to move to grandchild node (+2). To move up and down means Nup and Ndown.
| Collateral | Nup | Ndown |
|---|---|---|
| Sibling | 1 | 1 |
| Cousin | 2 | 2 |
| Second Cousin | 3 | 3 |
| Thiird Cousin | 4 | 4 |
| Pibling | 2 | 1 |
| Grand Pibling | 3 | 1 |
| Great-Grand Pibling | 4 | 1 |
| Nibling | 1 | 2 |
| first Cousin Once Removed | 2 | 3 |
| ... | ... | ... |
I am going to generalize query to find kinship nodes by using Nup and Ndown.
SELECT * FROM ff_table
WHERE ff_depth = Xd - Nup + Ndown
AND ff_queue >=
COALESCE(
(
SELECT MAX(ff_queue) + 1 FROM ff_table
WHERE ff_depth <= Xd - Nup
AND ff_queue < Xq
),
0
)
AND ff_queue <=
COALESCE(
(
SELECT MIN(ff_queue) - 1 FROM ff_table
WHERE ff_depth <= Xd - Nup
AND ff_queue > Xq
),
0x7fffffff
)
;
I named the query above "The Formula Query" of Fertile Forest Model.
FF model can find any relatives nodes! This is the result of FF Model, I found.
When I found the formula query, I got exhilarating feeling as same as a per billion of evolving special theory of relativity into the general theory of relativity.
Collateral Level
We got generalizing query to find any kinship nodes. However, the generalizing query was not considered about "collateral discrete level". When to use the query for finding cousin nodes, the results includes sibling node of base node. Therefore, we can not say that cousin() method has correctly represent name.
When getting data from the hierarchical data, the same level nodes are treated on the same level. Therefore, even though the sibling node is mixed on the results to find cousin nodes, we can insist "It is specification".
However, when others ask us "can you identify the cousin nodes and sibling nodes?", answer is "yes", if we have a spirit of software engineer. To solve this problem, we consider the following method.
As a result, we can use "processing with the exception of sibling nodes from the search results cousin nodes".
Because it takes time to explain the details, I implemented in my libraries. Please check on the following versions.