経路列挙モデル（検索編）：MySQLで階層化データを使う

(0)

(0)

(0)

(0)Total: 0

おしながき

ツリー構造よりルート（ツリー構造で最上位のノード）を取得する
ツリー構造よりリーフノード（子供がいないノード）を取得する
ノードの深さを測る
ツリー構造の深さを測る
ノードをインデントにより階層表示
親ノードから見た場合の子ノードを取得する
親ノード配下の子ノードの数
子から見た場合の親
ツリー構造より一部分を取得する
ノード間のパスを取得する
関連記事

ツリー構造よりルート（ツリー構造で最上位のノード）を取得する

pathより区切り文字を消し、node_idと同じノードを取得することにより実現します。
SELECT * FROM node WHERE node_id = REPLACE(path, '.', '');

+---------+-------+------+
| node_id | name  | path |
+---------+-------+------+
|       1 | Apple | .1.  |
+---------+-------+------+

ツリー構造よりリーフノード（子供がいないノード）を取得する

pathに「path + １字以上の任意文字」が該当しないノードを取得することにより実現します。
SELECT * FROM node AS parent WHERE NOT EXISTS (SELECT * FROM node AS child WHERE child.path LIKE CONCAT(parent.path,'_%'));

+---------+------------------------+-----------+
| node_id | name                   | path      |
+---------+------------------------+-----------+
|       4 | タワー型               | .1.2.3.4. |
|       5 | 一体型                 | .1.2.3.5. |
|       6 | ラップトップPC         | .1.2.6.   |
|       7 | ハンドヘルドPC         | .1.2.7.   |
|       8 | デジタル音楽プレーヤー | .1.8.     |
|       9 | 携帯電話               | .1.9.     |
|      10 | ソフトウェア           | .1.10.    |
+---------+------------------------+-----------+

ノードの深さを測る

ツリー構造よりそれぞれのノードの深さを測ります。
ノードが何階層目にいるかを取得するためです。
SELECT *, LENGTH(path) - LENGTH(REPLACE(path,'.','')) -2 AS depth FROM node ORDER BY path;

+---------+------------------------+-----------+-------+
| node_id | name                   | path      | depth |
+---------+------------------------+-----------+-------+
|       1 | Apple                  | .1.       |     0 |
|       2 | コンピューター         | .1.2.     |     1 |
|       3 | デスクトップPC         | .1.2.3.   |     1 |
|       4 | タワー型               | .1.2.3.4. |     2 |
|       5 | 一体型                 | .1.2.3.5. |     3 |
|       6 | ラップトップPC         | .1.2.6.   |     3 |
|       7 | ハンドヘルドPC         | .1.2.7.   |     2 |
|       8 | デジタル音楽プレーヤー | .1.8.     |     2 |
|       9 | 携帯電話               | .1.9.     |     1 |
|      10 | ソフトウェア           | .1.10.    |     1 |
+---------+------------------------+-----------+-------+

ツリー構造の深さを測る

SELECT MAX(LENGTH(path) - LENGTH(REPLACE(path,'.','')) -1) AS depth FROM node;

+-------+
| depth |
+-------+
|     4 |
+-------+

ノードをインデントにより階層表示

ノードの深さを測るの深さの値に応じてnameをインデント表示を行います。
pathに含まれる前後を除く区切り文字「.」の数分をインデントしてnameと連結し取得することにより実現します。
SELECT node_id,CONCAT(REPEAT("\t",LENGTH(path) - LENGTH(REPLACE(path,'.',''))-2),name) as name,path FROM node ORDER BY path;

+---------+----------------------------+-----------+
| node_id | name                       | path      |
+---------+----------------------------+-----------+
|       1 | Apple                      | .1.       |
|      10 |     ソフトウェア           | .1.10.    |
|       2 |     コンピューター         | .1.2.     |
|       3 |         デスクトップPC     | .1.2.3.   |
|       4 |             タワー型       | .1.2.3.4. |
|       5 |             一体型         | .1.2.3.5. |
|       6 |         ラップトップPC     | .1.2.6.   |
|       7 |         ハンドヘルドPC     | .1.2.7.   |
|       8 |     デジタル音楽プレーヤー | .1.8.     |
|       9 |     携帯電話               | .1.9.     |
+---------+----------------------------+-----------+

親ノードから見た場合の子ノードを取得する

子ノードのパスが含まれる、最大のパスを持つ親ノードを取得することにより実現します。
なお、子ノードが存在しないノードにはNULLが表示されます。
SELECT parent.node_id AS parent, parent.name parent_name, child.node_id AS child, child.name AS child_name FROM node AS parent LEFT JOIN node AS child ON parent.path = (SELECT MAX(path) FROM node WHERE child.path LIKE CONCAT(path,'_%'));

+--------+------------------------+-------+------------------------+
| parent | parent_name            | child | child_name             |
+--------+------------------------+-------+------------------------+
|      1 | Apple                  |     2 | コンピューター         |
|      1 | Apple                  |     8 | デジタル音楽プレーヤー |
|      1 | Apple                  |     9 | 携帯電話               |
|      1 | Apple                  |    10 | ソフトウェア           |
|      2 | コンピューター         |     3 | デスクトップPC         |
|      2 | コンピューター         |     6 | ラップトップPC         |
|      2 | コンピューター         |     7 | ハンドヘルドPC         |
|      3 | デスクトップPC         |     4 | タワー型               |
|      3 | デスクトップPC         |     5 | 一体型                 |
|      4 | タワー型               | NULL  |  NULL                  |
|      5 | 一体型                 | NULL  |  NULL                  |
|      6 | ラップトップPC         | NULL  |  NULL                  |
|      7 | ハンドヘルドPC         | NULL  |  NULL                  |
|      8 | デジタル音楽プレーヤー | NULL  |  NULL                  |
|      9 | 携帯電話               | NULL  |  NULL                  |
|     10 | ソフトウェア           | NULL  |  NULL                  |
+--------+------------------------+-------+------------------------+

親ノード配下の子ノードの数

前述の「親ノードから見た場合の子ノードを取得する」より親ノードをグループとして行数を取得することにより実現します。
SELECT parent.node_id AS parent, parent.name AS parent_name, COUNT(child.node_id) AS child_count FROM node AS parent LEFT JOIN node AS child ON parent.path = (SELECT MAX(path) FROM node WHERE child.path LIKE CONCAT(path,'_%')) GROUP BY parent.node_id;

+--------+------------------------+-------------+
| parent | parent_name            | child_count |
+--------+------------------------+-------------+
|      1 | Apple                  |           4 |
|      2 | コンピューター         |           3 |
|      3 | デスクトップPC         |           2 |
|      4 | タワー型               |           0 |
|      5 | 一体型                 |           0 |
|      6 | ラップトップPC         |           0 |
|      7 | ハンドヘルドPC         |           0 |
|      8 | デジタル音楽プレーヤー |           0 |
|      9 | 携帯電話               |           0 |
|     10 | ソフトウェア           |           0 |
+--------+------------------------+-------------+

子から見た場合の親

前述の「親ノードから見た場合の子ノードを取得する」のLEFT JOIN 部分を親と子を逆にし取得することにより実現します。
SELECT child.node_id AS child, child.name AS child_name, parent.node_id AS parent, parent.name parent_name FROM node AS child LEFT JOIN node AS parent ON parent.path = (SELECT MAX(path) FROM node WHERE child.path LIKE CONCAT(path,'_%'));

+-------+------------------------+--------+----------------+
| child | child_name             | parent | parent_name    |
+-------+------------------------+--------+----------------+
|     1 | Apple                  | NULL   | NULL           |
|     2 | コンピューター         |      1 | Apple          |
|     3 | デスクトップPC         |      2 | コンピューター |
|     4 | タワー型               |      3 | デスクトップPC |
|     5 | 一体型                 |      3 | デスクトップPC |
|     6 | ラップトップPC         |      2 | コンピューター |
|     7 | ハンドヘルドPC         |      2 | コンピューター |
|     8 | デジタル音楽プレーヤー |      1 | Apple          |
|     9 | 携帯電話               |      1 | Apple          |
|    10 | ソフトウェア           |      1 | Apple          |
+-------+------------------------+--------+----------------+

ツリー構造より一部分を取得する

同一のテーブルを対象に行う結合「自己結合（self join）」によって取得することができます。
親ノードのパスが該当するパスを持つ子ノード、かつ親ノードの名前が「デスクトップPC」に該当するレコードを取得することにより実現します。
SELECT child.* FROM node AS parent, node AS child WHERE child.path LIKE CONCAT(parent.path,'%') AND parent.name = 'デスクトップPC' ORDER BY child.path;

+---------+----------------+-----------+
| node_id | name           | path      |
+---------+----------------+-----------+
|       3 | デスクトップPC | .1.2.3.   |
|       4 | タワー型       | .1.2.3.4. |
|       5 | 一体型         | .1.2.3.5. |
+---------+----------------+-----------+

もし、自分「デスクトップPC」を含める必要がないのなら、以下のように「’%'」の代わりに「’_%’」を使えば取得できます。
SELECT child.* FROM node AS parent, node AS child WHERE child.path LIKE CONCAT(parent.path,'_%') AND parent.name = 'デスクトップPC' ORDER BY child.path;

+---------+----------+-----------+
| node_id | name     | path      |
+---------+----------+-----------+
|       4 | タワー型 | .1.2.3.4. |
|       5 | 一体型   | .1.2.3.5. |
+---------+----------+-----------+

ノード間のパスを取得する

開始ノード「:start_node」をルートとした終了ノード「:end_node」までの部分木を取得します。
※部分木とはツリー構造の一部であり、それ自身も完全なツリー構造となっている部分をいう。
SELECT parent.* FROM node AS parent, node AS child WHERE parent.path >= (SELECT path FROM node WHERE node_id = :start_node) AND child.node_id = :end_node AND child.path LIKE CONCAT(parent.path,'%') ORDER BY parent.path;

例：開始ノード「1:Apple」、終了ノード「7:ハンドヘルドPC」を取得する
SELECT parent.* FROM node AS parent, node AS child WHERE parent.path >= (SELECT path FROM node WHERE node_id = 1) AND child.node_id = 7 AND child.path LIKE CONCAT(parent.path,'%') ORDER BY parent.path;

+---------+----------------+---------+
| node_id | name           | path    |
+---------+----------------+---------+
|       1 | Apple          | .1.     |
|       2 | コンピューター | .1.2.   |
|       7 | ハンドヘルドPC | .1.2.7. |
+---------+----------------+---------+

関連記事