このエントリから、FFモデルの核心的な設計部分を紹介します。内容は、Fertile Forest Model のオフィシャルサイトから許可を得て転載したものです。
モデルデザイン
Fettile Forest モデルでは、全く新しい発想で階層構造カラムが設計されています。
階層構造のマトリックス化
以下のツリー構造データを元にして図説します。
[A]
|
+---+---+
| |
[B] [C]
| |
+-+-+ +-+-+
| | | |
[D] [E] [F] [G]
|
+-+-+
| |
[H] [I]
- ツリー全体を以下のように変形します。
[A]
|
+-------+
| |
[B] [C]
| |
+---+ +-+-+
| | | |
[D] [E] [F] [G]
|
+---+
| |
[H] [I]
- ノードがタテにひとつだけになるよう、更に変形します。
[A]--+-----------+
| |
[B]--+---+ [C]--+---+
| | | |
[D] [E] [F] [G]--+---+
| |
[H] [I]
- 全体をグリッド平面に見立てて、ノードのある位置のXY軸に附番します。
0 | [A]--+-----------+
| | |
1 | [B]--+---+ [C]--+---+
| | | | |
2 | [D] [E] [F] [G]--+---+
| | |
3 | [H] [I]
--+-------------------------------------
| 0 1 2 3 4 5 6 7 8
この図で、各ノードはユニークなXY座標を持ちます。このXY座標によりノードの階層構造位置を特定するのが、FFモデルの骨子です。
階層構造カラムの定義
附番されたXY座標は、次のように定義されます。
- X軸
- QUEUE (序列)
- Y軸
- DEPTH (深度)
FFモデルのテーブルは、複数のツリーを格納できます。その場合、2番目以降の根ノードの QUEUE は、以前のツリーのノード数に応じて決まります。
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テーブルに追加します。
id|name|ff_queue|ff_depth
:--:+:----:+------------:+------------:
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
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 は、テーブル内の全ノードについてユニークでなければなりません。ただし、ff_queue に UNIQUE KEY は指定できません。理由は、後述するノードの移動の際にそれがエラーを生じさせるからです。
上記の CREATE TABLE 文には、index が貼られていません。RDB テーブルに貼る index については、ノード検索の項目で説明します。
QUEUEは、全ノードに一定の規則で振られたシリアルナンバーと考えられます。このことから、FFモデルは「直列化ツリーモデル（Serialized Tree Model）」とも呼ばれます。