経路列挙モデル

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


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


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

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