LoginSignup
3

More than 5 years have passed since last update.

Fertile Forest Model (3/n) モデルデザイン

Last updated at Posted at 2015-10-23

このエントリから、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)」とも呼ばれます。

リンク

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3