閉包テーブル(Closure Table)をナイーブツリー(Naive Trees)に変換してみる

やったこと

前回記事「閉包テーブル(Closure Table)で子ノードを取得してみる 」でやったルートノードからの距離を取得する方法を応用し、閉包テーブルのデータ構造(祖先ノード、子孫ノード)をナイーブツリーのデータ構造（自身のノードと自身の親ノード）に変換してみた。

前提条件

前回と同様に閉包テーブルに対して以下の条件を設定

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

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

解説につかうツリー構造のイメージ

特定のノードと子孫ノードの距離を算出する（のおさらい）

解説につかうツリー構造でルートノードをBとしたとき
Bとの関係性は以下のSQLを実行することで距離の情報が得られる。

テーブルとカラム

• 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

上記のSQLによって得られる結果は、B自身の距離を1とした以下のような情報が得られる。

子孫ノード(descendent)	距離(depth)
B	1
D	2
E	2
F	3
G	3

親子関係を抽出する方法

特定のノードと子孫ノードの距離を算出する方法は、ルートノード自身(B)を含めたルートノードを祖先に持つ子孫ノード（DEFG）が祖先になるデータ(図でいうとDEFGに向かって伸びている矢印)の数を集約している。
よって集約元のデータの中には親子関係を表す情報が含まれているのでこちらを抽出すればよい。

親子関係にあるということは２つのノードが

• 祖先ノード、子孫ノードの関係にある
• 祖先ノードと子孫ノードの距離が１である

という条件を満たす必要があるので距離を集約元の情報（緑矢印）に集約後の距離情報を与えてやると祖先ノードと子孫ノードの距離関係を知ることができる。
この距離情報を

• ルートノードと子孫ノードの距離 = ルートノードと祖先ノードの距離 + 1

となるように条件指定することで親子関係にあるノードの情報を抽出できる。
これらをSQLにまとめると以下のような感じになる。

-- ① 集約前のデータ（ルートノードに対する子孫ノードの子孫関係）
WITH temp1 AS ( 
  SELECT t0.ancestor
        ,t0.descendent 
    FROM tree t0
    WHERE
      EXISTS ( 
        SELECT 1 
          FROM tree t1 
         WHERE t1.ancestor   = 'B(対象のノード)' 
           AND t1.descendent = t0.ancestor
      )
)
-- ② 集約後のデータ(ルートノードの子孫ノードの距離情報)
, temp2 AS ( 
  SELECT descendent
        ,count(*) as depth
    FROM temp1 
   GROUP BY descendent
)
-- ①の祖先、子孫ノードに②の距離情報を結合し
--「子孫ノードの距離 = 祖先ノードの距離 ＋１」
-- となっているデータを抽出する
SELECT a1.descendent as child
      ,a1.ancestor   as parent
  FROM temp1 a1
  JOIN temp2 a2
    ON a1.ancestor = a2.descendent
  JOIN temp2 a3
    ON a1.descendent = a3.descendent
 WHERE a3.depth = a2.depth + 1

実行結果としては以下のような感じになる。

子ノード(child)	親ノード(parent)
B	D
B	E
D	F
D	G

図では緑矢印の矢印の元と先の位置の差が1になるもの(青矢印)を抽出している。