経路列挙モデル - ぐるぐる～

RDBで親子関係を表すのに、たぶん隣接リストモデルがもっとも使われていると思う。
簡単に説明すると、子供に親へのポインタを持たせるようなものだ。

ただ、このモデルを採用すると、どうしてもきれいに問い合わせが書けなくなってしまう。
それを避けるために、冗長なカラムを追加するか、ストアドプロシージャやホスト言語側でコードを書くことになってしまう。
それでいい場合はいいんだけど、今回明らかに隣接リストモデルより、経路列挙モデルを採用した方がいい部分があったので、ちょっとまとめておく*1。

やりたいことは、だいたい以下の通り。

最大4つのサブコードがある*2
サブコードを順番に連結したもの*3が取得できる必要がある
それ以上サブコードが連結しないようなコード*4が取得できる必要がある
あるコード、またはサブコードの子要素すべてを取得できる必要がある
あるコード、またはサブコードの子要素すべてを削除できる必要がある
各コードの末端のサブコード*5が取得できる必要がある

これを実現したいときに、隣接リストモデルを使用するなら、こんな感じのテーブルになる。

code	parent
100
101
200	100
201	100
202	101
300	201
301	201
400	300

このテーブルを使うと、SQLはかなり冗長かつ非効率的なものとなる。
例えば、サブコードを順番に連結したものを取得するためのSQLはこんな感じになる*6。

WITH AllCodes AS (
-- 一階層
SELECT code FROM Codes WHERE parent IS NULL
UNION ALL
-- 二階層
SELECT
    A.code + coalesce(B.code, '')
FROM
    Codes A
      LEFT OUTER JOIN Codes B ON A.code = B.parent
WHERE
    A.parent IS NULL
UNION ALL
-- 三階層
SELECT
    A.code + coalesce(B.code, '') + coalesce(C.code, '')
FROM
    Codes A
      LEFT OUTER JOIN Codes B ON A.code = B.parent
      LEFT OUTER JOIN Codes C ON B.code = C.parent
WHERE
    A.parent IS NULL
UNION ALL
-- 四階層
SELECT
    A.code + coalesce(B.code, '') + coalesce(C.code, '') + coalesce(D.code, '')
FROM
    Codes A
      LEFT OUTER JOIN Codes B ON A.code = B.parent
      LEFT OUTER JOIN Codes C ON B.code = C.parent
      LEFT OUTER JOIN Codes D ON C.code = D.parent
WHERE
    A.parent IS NULL
)
SELECT DISTINCT code FROM AllCodes

子を持たないコードを取得するためには、

-- WITHは省略。これはもうビューを作るしかない
SELECT DISTINCT
    code
FROM
    AllCodes P
WHERE
    -- コードの末尾3文字を切り出し、parentと一致する行がなければ真
    NOT EXISTS(
      SELECT * FROM Codes C
      WHERE C.parent = substring(P.code, len(P.code) - 2, 3)
    )

とでもするのだろうか。

これらは、経路列挙モデルを使用するときれいに解決できる。
使用するテーブルは、こんな感じになる*7。

code	code_a	code_b	code_c	code_d
100	100
100200	100	200
100201	100	201
100201300	100	201	300
100201301	100	201	301
100201300400	100	201	300	400
101	101
101202	101	202

まず、コードの取得だが、すでにテーブル内に存在するので、

SELECT code FROM Codes

これだけでいい。

次に、子を持たないコードだが、

SELECT
    code
FROM
    Codes P
WHERE
    NOT EXISTS(
      SELECT * FROM Codes C
      WHERE C.code LIKE (P.code + '_%')
    )

の様にすればいい*8。
これは、自分のコードを含むほかのコードが存在しなければ末端要素である、という特徴を利用している。

あるコードの子要素すべてを取得、または削除するには、

SELECT
    C.code
FROM
    Codes P, Codes C
WHERE
    P.code = @target
      AND C.code LIKE (P.code + '%')

とすればいい。

ただし、経路列挙モデルが万能かというと、決してそんなことはない。
今回の例でも、各コードの末端のサブコードに対応する名前を取得するには、経路列挙モデルでは以下のように書く必要がある。

SELECT
    name
FROM
    Codes C
      INNER JOIN Names N
        ON N.code = CASE len(C.code) / 3
                      WHEN 1 THEN code_a
                      WHEN 2 THEN code_b
                      WHEN 3 THEN code_c
                      WHEN 4 THEN code_d
                    END

これが、隣接リストモデルだと、

SELECT
    name
FROM
    Codes C
      INNER JOIN Names N ON C.code = N.code

とするだけでいい。

経路列挙モデルについてもっと詳しく知りたければ、はるかに分かりやすい説明があるので、参考にするといいだろう。

*1:SQL Serverを使用

*2:サブコードは3桁の英数字

*3:これをコードという。最大12桁の英数字

*4:子を持たないコード

*5:実際はそのサブコードに対応する名前

*6:たぶんもっと効率いい方法もあるだろうけど、眠いからこれくらいしか思いつかない

*7:code_a〜code_dはcodeに含まれているので必須ではない

*8:ちなみにcodeをchar型にした場合、rtrim関数をC.codeとP.codeに適用する必要がある