The Cusp of Helix

Fertile Forest Model

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:

  1. [X] means base node.
  2. 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.
  3. 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.
  4. Sibling nodes meet conditions as follow:
    • The node has QUEUE between Qh and Qt.
      (Qh < QUEUE < Qt)
    • Has same DEPTH of [X].

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:

Set of child nodes having parent node of the target node.

Replace "parent node" to "the node which has one upper depth" the parent node.

Set of child nodes having "the node which has one upper depth" of the target node.

In addition, replace "child node" to "node which has one downer depth".

Set of "node which has one downer depth" having "the node which has one upper depth" of the target node.

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.

Set of "node which has two downer depth" having "the node which has two upper depth" of [D].

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.

CollateralLevel
Sibling1
Cousin2
Second Cousin3
Third Cousin4
......

Replace the changed word between the definition of sibling nodes and cousin node, to N.

Set of "node which has N downer depth" having "the node which has N upper depth" of target node.

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.

DEPTH of Base Node < Collateral Level

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".

Set of "node which has Ndown downer depth" having "the node which has Nup upper depth" of target node.

Nup and Ndown will change by relatives.

Diff.DirectCollateral
-4Great-Great-Grand Parents
-3Great-Grand ParentsGreat-Grand Pibling
-2Grand ParentGrand Piblingfirst cousin twice removed
-1ParentPiblingfirst cousin once removedsecond cousin once removed
0SelfSiblingCousinSecond CousinThird Cousin
1ChildNiblingfirst Cousin Once RemovedSecond Cousin Once RemovedThird Cousin Once Removed
2Grand ChildGrand Niblingfirst Cousin Twice RemovedSecond Cousin Twice RemovedThird Cousin Twice Removed
3Great-Grand ChildGreat-Grand Niblingfirst Cousin Thrice RemovedSecond Cousin Thrice RemovedThird Cousin Thrice Removed
4Great-Great-Grand ChildGreat-Great-Grand Niblingfirst Cousin
4 times Removed
Second Cousin
4 times Removed
Third Cousin
4 times Removed
4Great-Great-Great-Grand ChildGreat-Great-Great-Grand Niblingfirst 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.

CollateralNupNdown
Sibling11
Cousin22
Second Cousin33
Thiird Cousin44
Pibling21
Grand Pibling31
Great-Grand Pibling41
Nibling12
first Cousin Once Removed23
.........

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.

In the library of the FF model, it includes a "discrete degree column of collateral" into the query to find kinship nodes.

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.