閉包テーブル(Closure Table)で子ノードを取得してみる

やったこと

RDBでツリー構造を表現する手法の１つである閉包テーブルで
特定のノードに隣接する子ノードの一覧を取得する方法を模索してみた。

前提条件

以下の前提条件を設定

• 親ノードは１つまでとする
  ※閉包テーブルのデータ構造は、複数の親ノードを持つこともできるみたいだが今回なし

上記前提がないと問い合わせ結果が正しく得られない

ツリー構造のイメージ

特定のノードと子孫ノードの距離を算出する

特定のノードを基準としたとき、関連する子孫のノードが特定のノードと
どのぐらいの位置関係にあるかを算出する。

登録するデータ
閉包テーブルでは子孫、祖先という形で対象ノードの関係性をすべて登録しておく
矢印の向かう元が子孫ノード、矢印の向かう先が祖先ノードを指す

テーブルとカラム

• tree・・・閉包テーブル
• descendent ・・・子孫ノード
• ancestor・・・祖先ノード

SELECT t0.descendent
      ,count(*) as depth
  FROM tree t0 
  WHERE EXISTS ( 
      SELECT 1 
        FROM tree t1 
       WHERE t1.ancestor   = 'B(対象ノード)'
	     AND t1.descendent = t0.ancestor
    )
 GROUP BY descendent

1. 祖先ノードが対象ノード(B)のデータを取得する
   ノードBに向かって矢印が伸びているもの
   

2. 1.で該当したデータの子孫ノードを祖先ノードとするデータを取得する
   BDEFGに向かって矢印が伸びているもの
   

3. 2.で該当したデータを子孫ノードでデータ数を集計する
   子孫ノードから出ている緑の矢印を数える
   親ノードが1つである前提があることで、対象ノードまでの距離とすることができる。
   

特定のノードの子ノードを取得する

特定のノードからの距離の算出が上記でできるので距離が2のものを取得する
距離を変えることで孫を取得できるが親が複数あるときにどの親の孫であるかはわからない

SELECT t0.descendent
      ,count(*) as depth
  FROM tree t0 
  WHERE EXISTS ( 
      SELECT 1 
        FROM tree t1 
       WHERE t1.ancestor   = 'B(対象ノード)'
	     AND t1.descendent = t0.ancestor
    )
 GROUP BY descendent
HAVING depth = 2