隣接リスト(再帰クエリ)以外で階層構造を実現する方法は
1.経路列挙
2.入れ子集合
3.閉包テーブル
があります。

隣接リストを含む、それぞれの方法は一長一短ありますが
今回は、『階層構造のシンプルかつエレガントな格納方法。
最も用途が幅広く、(中略)計算が楽』になる
「閉包テーブル」について言及したいと思います。

「閉包テーブル」は隣接リストのように直接の親子関係だけでなく
ツリー全体のパスを格納する方法です。

例えば、以下のような階層構造があるとします。
(先頭の数字はIDです)

1:野菜┬2:根菜類
    │ ├4:ダイコン
    │ └5:にんじん
    │
    └3:果菜類
      └6:トマト

カテゴリテーブルの他に、自分自身を含む全ての先祖/子孫関係の
組み合わせを格納したテーブルを用意します。

カテゴリテーブル
----------------
ID | 名前   
----------------
1 | 野菜   
2 | 根菜類  
3 | 果菜類  
4 | ダイコン 
5 | にんじん 
6 | トマト  
----------------

ツリーテーブル
-------------------
先祖 | 子孫 | 階層 
-------------------
1  | 1  | 0
1  | 2  | 1
1  | 3  | 1
1  | 4  | 2
1  | 5  | 2
1  | 6  | 2
2  | 2  | 0
2  | 4  | 1
2  | 5  | 1
3  | 3  | 0
3  | 6  | 1
4  | 4  | 0
5  | 5  | 0
6  | 6  | 0
-------------------

ツリーテーブルの「階層」は階層の「深さ」になります。
自分自身は「0」、子は「1」、孫は「2」といった具合です。

ツリーテーブルのような「閉包テーブル」を使用することで
クエリは簡潔なものになります。

■例1.ダイコンの「先祖」を取得する

SELECT 先祖
 FROM  ツリーテーブル
WHERE  子孫 = 4
ORDER BY 階層 DESC;
-------------------
1(野菜)
2(根菜類)
4(ダイコン)

■例2.根菜類の「子孫」を取得する

SELECT 子孫
 FROM  ツリーテーブル
WHERE  先祖 = 2
ORDER BY 階層;
-------------------
2(根菜類)
4(ダイコン)
5(にんじん)

■例3.ダイコンの下に練馬大根を追加

INSERT INTO ツリーテーブル
SELECT 先祖, 7, 階層
 FROM ツリーテーブル
WHERE 子孫 = 4
UNION
SELECT 7,7,3;

結果
-------------------
先祖 | 子孫 | 階層 
-------------------
1  | 1  | 0
1  | 2  | 1
1  | 3  | 1
1  | 4  | 2
1  | 5  | 2
1  | 6  | 2
2  | 2  | 0
2  | 4  | 1
2  | 5  | 1
3  | 3  | 0
3  | 6  | 1
4  | 4  | 0
5  | 5  | 0
6  | 6  | 0
1  | 7  | 0
2  | 7  | 1
4  | 7  | 2
7  | 7  | 3
-------------------

1:野菜┬2:根菜類
    │ ├4:ダイコン
    │ │   └7:練馬大根
    │ └5:にんじん
    │
    └3:果菜類
      └6:トマト

■例4.トマトを削除

DELETE FROM ツリーテーブル WHERE 子孫 = 6;

結果
-------------------
先祖 | 子孫 | 階層 
-------------------
1  | 1  | 0
1  | 2  | 1
1  | 3  | 1
1  | 4  | 2
1  | 5  | 2
2  | 2  | 0
2  | 4  | 1
2  | 5  | 1
3  | 3  | 0
4  | 4  | 0
5  | 5  | 0
1  | 7  | 0
2  | 7  | 1
4  | 7  | 2
7  | 7  | 3
-------------------

1:野菜┬2:根菜類
    │ ├4:ダイコン
    │ │   └7:練馬大根
    │ └5:にんじん
    │
    └3:果菜類

■例5.ダイコンとそのサブツリーを削除

DELETE FROM ツリーテーブル WHERE 子孫 IN (SELECT 子孫 FROM ツリーテーブル WHERE 先祖 = 4);

結果
-------------------
先祖 | 子孫 | 階層 
-------------------
1  | 1  | 0
1  | 2  | 1
1  | 3  | 1
1  | 5  | 2
2  | 2  | 0
2  | 5  | 1
3  | 3  | 0
5  | 5  | 0
-------------------

1:野菜┬2:根菜類
    │ └5:にんじん
    │
    └3:果菜類


閉包テーブルは、パスを別のテーブルに格納することで
柔軟にノードの関連付けを行うようにする設計方法です。
何階層目かを表す「階層」の計算は少し厄介かもしれません。
「例3」の「追加」のように「7:練馬大根」が何階層目になるかを
クエリだけで取得するのは難しいからです。

そのためか、本書では「階層」についての言及は「閉包テーブル」の節の
最後のほうにしかなく、「階層」を含んだクエリの例はありません。
ですが、「階層」がなくては階層構造のデータとしては片手落ちのような気がします。

最初に述べたように、階層構造のテーブル設計は
どのような方法を取るにしろ、一長一短あります。
要件に応じて都度、最適なものを選択していくようにすべきでしょう。

野菜┬根菜類
  │ ├ダイコン
  │ └にんじん
  └果菜類
    └トマト

このような階層構造をデータとして持つ場合
もっとも一般的な方法は親となるデータのIDを持つことと思われます。

カテゴリテーブル
------------------------
ID  | 名前   | 親ID
------------------------
101 | 野菜   | 0  
102 | 根菜類  | 101
103 | 果菜類  | 101
104 | ダイコン | 102
105 | にんじん | 102
106 | トマト  | 103
------------------------

これは「隣接リスト」と呼ばれるやり方で、SQLアンチパターンでは
「アンチパターン」の一つとしています。

その理由として
「1.すべての子孫を取得するには、階層の深さを固定化する必要がある」

階層構造はその性質上、深さに制限がない場合が多いため
階層の深さにかかわらず子孫を取得する必要があります。
ですが、隣接リストでは自身の親IDしか持っていないため
下記のようなクエリでしか、遠い親や子の情報を取得できません。

SELECT c1.名前, c2.名前, c3.名前
 FROM  カテゴリテーブル c1  -- 1階層目
 LEFT OUTER JOIN カテゴリテーブル c2  -- 2階層目
   ON c2.親ID = c1.ID 
 LEFT OUTER JOIN カテゴリテーブル c3  -- 3階層目
   ON c3.親ID = c2.ID 

これはJOINの数を固定しなくてはならないことを表しています。
階層が深くなれば、SQLも修正する必要があります。

野菜┬根菜類
  │ ├ダイコン
  │ │ └練馬大根
  │ └にんじん
  └果菜類
    └トマト

------------------------
ID  | 名前   | 親ID
------------------------
101 | 野菜   | 0  
102 | 根菜類  | 101
103 | 果菜類  | 101
104 | ダイコン | 102
105 | にんじん | 102
106 | トマト  | 103
107 | 練馬大根 | 104
------------------------

SELECT c1.名前, c2.名前, c3.名前, c4.名前
 FROM  カテゴリテーブル c1  -- 1階層目
 LEFT OUTER JOIN カテゴリテーブル c2  -- 2階層目
   ON c2.親ID = c1.ID 
 LEFT OUTER JOIN カテゴリテーブル c3  -- 3階層目
   ON c3.親ID = c2.ID 
 LEFT OUTER JOIN カテゴリテーブル c4  -- 4階層目
   ON c4.親ID = c3.ID 


「2.メンテナンスが面倒」
挿入はかなり楽です。
INSERT INTO カテゴリテーブル VALUES (108,亀戸大根,104);

また、ノード間の移動も簡単に行えます。
UPDATE カテゴリテーブル SET 親ID = 103 WHERE ID = 105; -- にんじんを果菜類に移動

しかし、ノードの削除は少々手間です。
例えば「根菜類」を削除したい場合

SELECT ID FROM カテゴリテーブル WHERE 親ID = 102; -- 104,105が返る
SELECT ID FROM カテゴリテーブル WHERE 親ID = 104; -- 107が返る
SELECT ID FROM カテゴリテーブル WHERE 親ID = 105; -- 105を親に持つデータなし
SELECT ID FROM カテゴリテーブル WHERE 親ID = 107; -- 107を親に持つデータなし
DELETE FROM カテゴリテーブル WHERE ID IN (102,104,105,107);

というように「果菜類」の子孫を検索する必要があります。
親IDに外部キー定義で[ON DELETE CASCADE]を指定すれば
102を削除時に、自動的に子孫も削除されますが、ノードの昇格には対応できません。

例.「果菜類」を削除して、その子どもを第2階層に昇格。
SELECT 親ID FROM カテゴリテーブル WHERE ID = 103; -- 101が返る
SELECT ID FROM カテゴリテーブル WHERE 親ID = 103; -- 106が返る
UPDATE カテゴリテーブル SET 親ID = 101 WHERE ID = 106;
DELETE FROM カテゴリテーブル WHERE ID IN (103);

ノード同士の関係を表すものが直近の親しかないため
何度もSELECT文を発行する必要があるわけです。

ただ隣接リストが必ずしも悪いわけではなく、本書では以下のような場合には
「アンチパターン」を用いてもよいとしています。
『アプリケーションで求められているタスクに適している限りは有効です。
隣接リストの長所は直近の親と子を簡単に取得できることです。また、
列の挿入も容易です。階層構造を持つデータに対して必要な操作がこれのみで
ある場合、隣接リストは効果的に機能します。』

また、階層構造をサポートするSQL拡張機能を備えているデータベース製品を
使用している場合もOKとしています。
例えば、再帰クエリをサポートしている「SQL Sever2005」や「Oracle」などです。

ただ、個人的な感想を述べさせてもらうなら、これについては少々疑問に思います。
WITH句を使用した再帰クエリは使用したことがないので何とも言えませんが
ORACLEの「CONNECT BY PRIOR」を使用した再帰クエリは、処理が遅く
最終的に別の方法に置き換えたという経験があるからです。

それでは隣接リスト以外に階層構造を実現するには、どのような方法があるのか。
長くなったので、次回へ続きます。

SQLアンチパターン [大型本]
では、カンマ区切りなどのフォーマットのリストを
一つの列に格納するのは避けるべきとしています。

例えば、『担当者マスタ』と『問合せ受付テーブル』が存在し、
その関係が当初、1:Nとして設計されていました。
1件の「問い合わせ」を1人の担当者が受け持つという想定です。
ところが、複数の担当者が1件の「問い合わせ」を担当したいという
要望が出てきました。その対応として、『問合せ受付テーブル』の
「担当者ID」列サイズを大きく拡張し、そこに複数の担当者IDを
カンマ区切りで格納するわけです。

担当者マスタ
------------------
ID  | 名前
------------------
101 | 富山A子
102 | 福岡B美
103 | 大阪C男
------------------

問合せ受付テーブル(他の列は省略)
------------------
KEY  | 担当者ID
------------------
key1 | 101,103
key2 | 102
key3 | 103,101,102
------------------

これを避けるべき理由として、以下を上げています。
1.『問合せ受付テーブル』を担当者IDで検索する場合、等価検索できない。
2.検索時にインデックスが使われない。
3.「名前」を取得したくとも、担当者マスタと結合できない。
4.etc

避けるべき理由として、異論はありません。

個人的に付け加えるなら、以下のようなケースもアンチパターンとしたいところです。

問合せ受付テーブル
----------------------------------------------
KEY  | 担当者ID_1  | 担当者ID_2  | 担当者ID_3
----------------------------------------------
key1 | 101            | 103           |
key2 | 102            |                 |
key3 | 103            | 101           | 102
----------------------------------------------

これでは、登録できる担当者数に制限ができます。
また、「名前」を取得するために、ID列数分、担当者マスタを結合する必要があります。

SELECT KEY, B.名前, C.名前, D.名前
FROM  
 問合せ受付テーブル A
    LEFT OUTER JOIN 担当者マスタ B ON A.担当者ID_1 = B.ID
    LEFT OUTER JOIN 担当者マスタ C ON A.担当者ID_2 = C.ID
    LEFT OUTER JOIN 担当者マスタ D ON A.担当者ID_3 = D.ID

結合するテーブル数が多くなれば、それだけコストがかかりパフォーマンスが落ちます。

解決策は、『担当者マスタ』と『問合せ受付テーブル』の
N:Nの関係性を表す交差テーブルを持つことです。

問合せ受付担当者テーブル
------------------
KEY  | 担当者ID
------------------
key1 | 101
key1 | 103
key2 | 102
key3 | 103
key3 | 101
key3 | 102
------------------

これならば、担当者IDで検索する場合、等価検索できますし
インデックスの効果も期待できます。
登録できる担当者数の制限もありません。

ただ、『問合せ受付テーブル』の情報と一緒に
「名前」を取得しようとする場合は注意が必要です。
単純に三つのテーブルを結合すると、

--------------------------------
KEY  | 担当者ID    | 担当者名
--------------------------------
key1 | 101         | 富山A子
key1 | 103         | 大阪C男
key2 | 102         | 福岡B美
key3 | 103         | 大阪C男
key3 | 101         | 富山A子
key3 | 102         | 福岡B美
--------------------------------

となります。
一覧画面で問合せ受付テーブルを表示し、そこに「担当者名」も表示しようとする仕様では
担当者が増えるたびにレコード件数が増えて表示されてしまう不具合が出てしまいます。

...今となっては懐かしい思い出です(汗)。

結局、一覧画面表示用に『問合せ受付テーブル』に「担当者名」を
カンマ区切りで持つようにしました。

問合せ受付テーブル
------------------------------------
KEY  | 担当者名
------------------------------------
key1 | 富山A子,大阪C男
key2 | 福岡B美
key3 | 大阪C男,富山A子,福岡B美
------------------------------------

「担当者」の登録、更新、削除があるたびに「担当者名」を更新します。

本書では、『カンマ区切りフォーマットのデータが必要で、かつリスト内の
各要素への個別アクセスが不要な』場合にアンチパターンを用いてもよいとしています。

表示用と割り切れば、このようなデータの持ち方も「あり」と考えます。

↑このページのトップヘ