Model Design
FF model is designed by new idea.
Matrix of hierarchical structure
I am going to explain the FF-Model visually by tree data as:
[A]
|
+---+---+
| |
[B] [C]
| |
+-+-+ +-+-+
| | | |
[D] [E] [F] [G]
|
+-+-+
| |
[H] [I]
(1) Modifies form of entire tree as:
[A]
|
+-------+
| |
[B] [C]
| |
+---+ +---+
| | | |
[D] [E] [F] [G]
|
+---+
| |
[H] [I]
(2) Further modifies for each node as only one in vertical positions.
[A]--+-----------+
| |
[B]--+---+ [C]--+---+
| | | |
[D] [E] [F] [G]--+---+
| |
[H] [I]
Give numbers of XY axis position for each node in likening to the grid plain.
0 | [A]--+-----------+
| | |
1 | [B]--+---+ [C]--+---+
| | | | |
2 | [D] [E] [F] [G]--+---+
| | |
3 | [H] [I]
--+-------------------------------------
| 0 1 2 3 4 5 6 7 8
Each node has a unique XY coordinates in this figure. To be able to identify the hierarchical data position of the node by the XY coordinates. This is the gist of FF model.
I defined the XY coordinates as follows.
- X-axis
- QUEUE
- Y-axis
- DEPTH
A table of FF-Model can have some trees. When in the case, QUEUE of 2nd (or more) root nodes are depending on size of trees before.
DEPTH|
0 | [A]--+-----------+ [J]--+---------------+
| | | | |
1 | [B]--+---+ [C]--+---+ [K]--+ [L]--+
| | | | | | |
2 | [D] [E] [F] [G]--+---+ [M]--+---+ [N]
| | | | |
3 | [H] [I] [O] [P]
--+----------------------------------------------------------------------
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 QUEUE
RDB Table Design
Add two columns for containing QUEUE and DEPTH into RDB table as tree-storing column.
| id | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| name | A | B | C | D | E | F | G | H | I |
| ff_queue | 0 | 1 | 4 | 2 | 3 | 5 | 6 | 7 | 8 |
| ff_depth | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 |
CREATE TABLE `ff_tables` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(225) DEFAULT NULL,
`ff_queue` int(11) NOT NULL,
`ff_depth` int(11) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;
INSERT INTO `ff_tables`
(`id`, `name`, `ff_queue`, `ff_depth`)
VALUES
(1, 'A', 0, 0), (2, 'B', 1, 1), (3, 'C', 4, 1),
(4, 'D', 2, 2), (5, 'E', 3, 2), (6, 'F', 5, 2),
(7, 'G', 6, 2), (8, 'H', 7, 3), (9, 'I', 8, 3)
;
ff_queue must be UNIQUE for all nodes in a table. But can not use UNIQUE KEY for ff_queue, because it makes error when to graft nodes.
QUEUE is likened as a serial number by certain rules to all nodes. From this fact, FF model is also referred to as a "Serialized Tree Model".
Index to be applied to a table.
All basic queries can be referred to index to find nodes in FF-Model. Grant the index in tables as:
CREATE TABLE `ff_tables` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`ff_depth` int(11) NOT NULL,
`ff_queue` int(11) NOT NULL,
PRIMARY KEY (`id`),
KEY `ff_queue_index` (`ff_queue`),
KEY `ff_depth_index` (`ff_depth`,`ff_queue`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;
ff_queue_index is used in the search in general. It is the most important index of the FF model.
ff_depth_index is a composite index. When to find descendant nodes, subquery finds the end of node in subtree. At that time, the index is used for the search speed.
To reproduce the tree structure data from stored data
A model has two roles for storing hierarchical data in RDB. (First chapter first section)
- To store the hierarchical data in RDB table.
- To write the query to find the relevant nodes (such as "sub-tree", "parent node", "children nodes", "ancestor nodes" and "descendant nodes") efficiently for any nodes.
I verify the steps to reproduce a tree structure from data stored in RDB table of the FF model.
(1) To map all nodes saved in RDB table onto the grid plain by QUEUE and DEPTH columns.
DEPTH|
|
0 | [A]
|
1 | [B] [C]
|
2 | [D] [E] [F] [G]
|
3 | [H] [I]
-----+-------------------------------------------
| 0 1 2 3 4 5 6 7 8 QUEUE
(2) When take to the left on "upper one depth" from each node, "first found node" is parent node.
DEPTH|
|
0 | [A]--+-----------+
| | |
1 | [B]--+---+ [C]--+---+
| | | | |
2 | [D] [E] [F] [G]--+---+
| | |
3 | [H] [I]
-----+-------------------------------------------
| 0 1 2 3 4 5 6 7 8 QUEUE
(3) By modifying the above figure, you get the figure below.
[A]
|
+---+---+
| |
[B] [C]
| |
+-+-+ +-+-+
| | | |
[D] [E] [F] [G]
|
+-+-+
| |
[H] [I]
We have just seen that FF model clears the condition of second role of model to store hierarchical data in RDB (To store the hierarchical data in RDB table).
In the next section "To Find Nodes", I will verify the second item of model condition (To write the query to find the relevant nodes efficiently for any nodes).