再帰クエリで木構造のデータを取得する


はじめに

フォルダ機能を作る際にSQLserverで再帰クエリを書いたので、メモとして残しておきたいと思います。

再帰関数

関数の中で自分自身を呼び出すものを再帰関数といいます。
無駄に多用するとコードが見づらくなりますが、何重になるかわからない時などループでやりづらい場合に再帰関数を使うと簡単に書けたりします。

function funcA(n){
    if(n == 0){
        return 0;
    }else{
        return n + funcA(n-1);
    } 
}

木構造のデータ

以下のような構造のデータを木構造と言います。

以下のように各ノードが親のノードを持つだけのデータ構造を隣接リストモデルといいます。

parentid id
0 1
1 2
1 3
2 4
2 5

他には経路列挙モデル、入れ子モデル、閉包テーブルモデルなどがあります。
隣接リストモデルはシンプルですが、RDBMSが再帰クエリに対応していない場合は子孫ノードを取得しづらいなどの問題があり、アンチパターンとなります。
SQLserverは再帰クエリに対応しているので大丈夫です。

WITH句を使って再帰クエリを書く

1.id:2よりも上の階層の情報を取得する場合

→取得できるid 1、2

WITH r AS (
--起点となるselect文
SELECT
*
FROM
tbl1
WHERE
tbl1.id = 

UNION ALL

--再帰
SELECT
*
FROM
tbl2 AS r
WHERE
tbl2.id = r.parentid
)

SELECT
*
FROM
r
2.id:2よりも下の階層の情報を取得する場合

→取得できるid 2、4、5

WITH r AS (
--起点となるselect文
SELECT
*
FROM
tbl1
WHERE
tbl1.id = 

UNION ALL

--再帰
SELECT
*
FROM
tbl2 AS r
WHERE
--ここのidとparentidが逆になる
tbl2.parentid = r.id
)

SELECT
*
FROM
r

おわりに

SQLアンチパターンという本があり、その中の2章 Naive Trees(素朴な木)をまとめてあるこちらの記事が設計の時に参考になりました。
自分も読んでみたいと思います。