閉包表による木構造

SQL木構造を扱う方法の一つ、 閉包表を SQLite3 をターゲットとして試してみます。 閉包表 (Closure Table Tree Encoding) は、 ノードの主キーと、 そのノードを根とする部分木中の主キーの集合を関連付けます。 この関連付けを逆写像で眺めると、 経路列挙をカラムに文字列で格納するのではなく、 別の多対多の表に切り出したものになります。 そのため、 入れ子集合、 経路列挙の 2 つの視点から木構造を利用できるようになっています。 閉包表の名称でこの手法の利用例が説明されだしたのは 2010 年ぐらいからです。

参考

The simplest(?) way to do tree-based queries in SQL (dirtSimple.org)

Moving Subtrees in Closure Table Hierarchies - Percona Database Performance Blog

SQLで木と階層構造のデータを扱う(2)―― 経路列挙モデル

入れ子集合と経路の 2 面性を扱える閉包表ですけど、 今回は主に経路列挙の視点から木を扱ってみます。 閉包表で経路を列挙するときは、 葉から根へ向けて、 言い換えると子孫から祖先へ向けるやりかたが主流になっています。 閉包表には、 着目しているノードの主キー descendant に対して、 そのノードから根までの経路の途中のノードの主キー ancestor を列挙します。 閉包表は入れ子集合でもあるので、 経路の順番を閉包表に記入しなくてもその都度計算可能ですけど、 それならば最初から経路の順番を depth に書き込む方が賢いやりかただと納得できます。 もっとも、 その代償で、 削除と挿入時に depth をメンテナンスするやりかたを考えるはめになります。 この文書の目的の一つは depth の素朴なメンテナンスのやりかたの備忘録を残しておくことでもあります。

CREATE TABLE IF NOT EXISTS entries (
    id INTEGER NOT NULL UNIQUE PRIMARY KEY
   ,body TEXT NOT NULL
);

CREATE TABLE IF NOT EXISTS closure (
    descendant INTEGER NOT NULL REFERENCES entries (id)
   ,ancestor INTEGER NOT NULL REFERENCES entries (id)
   ,depth INTEGER NOT NULL CHECK (depth >= 0)
   ,PRIMARY KEY (descendant ASC, ancestor ASC)
);

主キーによる経路列挙と同じで、 経路には根の主キーとノードの主キーまでを列挙します。 depth は葉をゼロ、 根を深さになるように逆順に付けておくのが通例になっています。 逆順なのは、 ある主キーの直下にある子の主キーをリストアップするとき depth が 1 の行で探せば良いためです。

BEGIN TRANSACTION;

-- 主キーが 1 のエントリを経路 /1/ で作ります
INSERT INTO entries (id, body) VALUES (1, 'A');
INSERT INTO closure (descendant, ancestor, depth) VALUES (1, 1, 0);
-- 主キーが 2 のエントリを経路 /1/2/ で作ります
INSERT INTO entries (id, body) VALUES (2, 'B');
INSERT INTO closure (descendant, ancestor, depth) VALUES (2, 1, 1);
INSERT INTO closure (descendant, ancestor, depth) VALUES (2, 2, 0);
-- 主キーが 3 のエントリを経路 /1/3/ で作ります
INSERT INTO entries (id, body) VALUES (3, 'C');
INSERT INTO closure (descendant, ancestor, depth) VALUES (3, 1, 1);
INSERT INTO closure (descendant, ancestor, depth) VALUES (3, 3, 0);
-- 主キーが 4 のエントリを経路 /1/3/4/ で作ります
INSERT INTO entries (id, body) VALUES (4, 'D');
INSERT INTO closure (descendant, ancestor, depth) VALUES (4, 1, 2);
INSERT INTO closure (descendant, ancestor, depth) VALUES (4, 3, 1);
INSERT INTO closure (descendant, ancestor, depth) VALUES (4, 4, 0);
-- 主キーが 5 のエントリを経路 /1/3/5/ で作ります
INSERT INTO entries (id, body) VALUES (5, 'E');
INSERT INTO closure (descendant, ancestor, depth) VALUES (5, 1, 2);
INSERT INTO closure (descendant, ancestor, depth) VALUES (5, 3, 1);
INSERT INTO closure (descendant, ancestor, depth) VALUES (5, 5, 0);
-- 主キーが 6 のエントリを経路 /1/3/6/ で作ります
INSERT INTO entries (id, body) VALUES (6, 'F');
INSERT INTO closure (descendant, ancestor, depth) VALUES (6, 1, 2);
INSERT INTO closure (descendant, ancestor, depth) VALUES (6, 3, 1);
INSERT INTO closure (descendant, ancestor, depth) VALUES (6, 6, 0);
-- 主キーが 7 のエントリを経路 /1/3/4/7/ で作ります
INSERT INTO entries (id, body) VALUES (7, 'G');
INSERT INTO closure (descendant, ancestor, depth) VALUES (7, 1, 3);
INSERT INTO closure (descendant, ancestor, depth) VALUES (7, 3, 2);
INSERT INTO closure (descendant, ancestor, depth) VALUES (7, 4, 1);
INSERT INTO closure (descendant, ancestor, depth) VALUES (7, 7, 0);

COMMIT;

ルートを見つけるには、 主キーを 1 に決め打ちしていると楽ですが、 必ずしもそうでないときは経路の先頭にしか現れないことを利用します。

SELECT *
  FROM entries
  WHERE 1 == (SELECT COUNT(*) FROM closure WHERE descendant = id);

-- => 1|A

葉を探すときは、 経路の末尾にしか現れないことを利用します。

SELECT * 
  FROM entries
  WHERE 1 == (SELECT COUNT(*) FROM closure WHERE ancestor = id);

-- => 2|B
--    5|E
--    6|F
--    7|G

descendant でグループを作ることで、 ノードの深さと経路を列挙することができます。 SQLite3 の方言 GROUP_CONCAT 集計関数は、 本稿執筆時点の最新版 3.19.3 でも ancestor の順番を depth を使って並べ替えることができないので、 これまた SQLite3 の方言である FROM SELECT 句を使って depth の降順で並べ替えてからグループ化をおこないます。 GROUP_CONCAT 集計関数に相当する方言に、 Oracle は LIST_AGG、 MySQL は group_concat、 PostgreSQL は string_agg をそれぞれ持っています。 SQLite3 以外では、 ORDER BY を関数の引数に修飾可能で、 下のような FROM にサブクエリを指定する非標準記述は不要です。

SELECT id, body
      ,MAX(depth) AS lev
      ,GROUP_CONCAT(ancestor) AS path
    FROM (SELECT id, body, descendant, ancestor, depth
            FROM entries JOIN closure ON descendant = id
            ORDER BY depth DESC)
    GROUP BY descendant
    ORDER BY path;

-- => 1|A|0|1
--    2|B|1|1,2
--    3|C|1|1,3
--    4|D|2|1,3,4
--    7|G|3|1,3,4,7
--    5|E|2|1,3,5
--    6|F|2|1,3,6

ノードの深さと quote zeroblob ハック を使ってインデント表現もできなくはありません。 制限として、 path を文字列順に並べているので、 桁数の異なる id が混在しているときは、 インデント表示が崩れることがあります。

--      quote(zeroblob(1))         => X'00'
-- trim(quote(zeroblob(1)), 'X''') => 00
SELECT replace(trim(quote(zeroblob(lev)), 'X'''), '00', '  ') || body
    FROM (SELECT id, body
          ,MAX(depth) AS lev
          ,GROUP_CONCAT(ancestor) AS path
        FROM (SELECT id, body, descendant, ancestor, depth
                FROM entries JOIN closure ON descendant = id
                ORDER BY depth DESC)
        GROUP BY descendant
        ORDER BY path);

-- => A
--      B
--      C
--        D
--          G
--        E
--        F

直属の親から見た子を取得するには、 depth が 1 になっている閉包表の行を利用します。 子供がない親では、 子のカラムには NULL が返ります。

SELECT P.id, P.body, C.id, C.body
    FROM entries AS P LEFT OUTER JOIN entries AS C
        ON P.id == (SELECT ancestor
                        FROM closure
                        WHERE descendant = C.id AND depth = 1);

-- => 1|A|2|B
--    1|A|3|C
--    2|B||
--    3|C|4|D
--    3|C|5|E
--    3|C|6|F
--    4|D|7|G
--    5|E||
--    6|F||
--    7|G||

直属の子から見た親を取得するには、 外部結合をひっくり返します。 根の親は NULL になります。

SELECT C.id, C.body, P.id, P.body
    FROM entries AS C LEFT OUTER JOIN entries AS P
        ON P.id == (SELECT ancestor
                        FROM closure
                        WHERE descendant = C.id AND depth = 1);

-- => 1|A||
--    2|B|1|A
--    3|C|1|A
--    4|D|3|C
--    5|E|3|C
--    6|F|3|C
--    7|G|4|D

部分木のノードを列挙するには、 閉包表は部分木そのものでもあるので、 表示の仕方に細工をするだけです。

SELECT R.id, R.body, C.id, C.body
    FROM entries AS R JOIN entries AS C JOIN closure
        ON ancestor = R.id AND descendant = C.id
    WHERE R.id != C.id
    ORDER BY R.id;

-- => 1|A|2|B
--    1|A|3|C
--    1|A|4|D
--    1|A|5|E
--    1|A|6|F
--    1|A|7|G
--    3|C|4|D
--    3|C|5|E
--    3|C|6|F
--    3|C|7|G
--    4|D|7|G

葉を削除するときは、 閉包の descendant が主キーに一致する行を削除します。

BEGIN TRANSACTION;

-- 葉 5|E|2|1,3,5 を削除します。
DELETE FROM closure WHERE descendant = 5;
DELETE FROM entries WHERE id = 5;

-- => 1|A|0|1
--    2|B|1|1,2
--    3|C|1|1,3
--    4|D|2|1,3,4
--    7|G|3|1,3,4,7
--    6|F|2|1,3,6

--COMMIT;
ROLLBACK;

閉包表は部分木を表しているので、 部分木を葉までごっそりと削除するのは簡単です。 例えば、 4 を削除すると 7 も一緒に削除します。 結果は経路列挙表示にしています。

BEGIN TRANSACTION;

-- ノード 4|D|2|1,3,4 と
--     葉 7|G|3|1,3,4,7 を同時に削除します。

DELETE FROM entries
    WHERE id IN (SELECT descendant FROM closure WHERE ancestor = 4);

DELETE FROM closure
    WHERE descendant IN (SELECT descendant FROM closure WHERE ancestor = 4);

-- => 1|A|0|1
--    2|B|1|1,2
--    3|C|1|1,3
--    5|E|2|1,3,5
--    6|F|2|1,3,6

--COMMIT;
ROLLBACK;

木の途中のノードを削除して中抜きするとき、 経路情報の depth を更新するのに一手間かかります。 更新さえしてしまえば、 閉包表からの削除は単純作業です。 例えば、 祖父母を親代わりにするには、 根から祖父母のノードまでの経路の depth をすべて 1 減じます。 なお、 下の UPDATE 文が MySQL でエラーになるときは、 「3 つの closure 表の自己結合」を使うことで動かすことができます。

BEGIN TRANSACTION;

-- ノード 3|C|1|1,3 を中抜きします。
-- closure VALUES (3, 1, 1) => delete
-- closure VALUES (3, 3, 0) => delete
--
-- closure VALUES (4, 1, 2) => closure VALUES (4, 1, 1) depth を 1 減じます。
-- closure VALUES (4, 3, 1) => delete
-- closure VALUES (4, 4, 0) 変更なし
--
-- closure VALUES (7, 1, 3) => closure VALUES (7, 1, 2) depth を 1 減じます。
-- closure VALUES (7, 3, 2) => delete
-- closure VALUES (7, 4, 1) 変更なし
-- closure VALUES (7, 7, 0) 変更なし
-- 等

UPDATE closure
    SET depth = depth - 1
    WHERE descendant IN (SELECT descendant FROM closure WHERE ancestor = 3)
      AND ancestor NOT IN (SELECT descendant FROM closure WHERE ancestor = 3);

DELETE FROM closure
    WHERE descendant = 3 OR ancestor = 3;

DELETE FROM entries
    WHERE id = 3;

-- => 1|A|0|1
--    2|B|1|1,2
--    4|D|1|1,4
--    7|G|2|1,4,7
--    5|E|1|1,5
--    6|F|1|1,6

--COMMIT;
ROLLBACK;

親 3 を削除して、 代理で子供の一人 4 が親代わりになるときは、 4 の部分木を一段上へ移動します。 移動したら 3 を削除し、 ancestor が 3 のまま残っている閉包表の行を 4 へ書き直します。

BEGIN TRANSACTION;

-- 部分木 4|D|2|1,3,4 を 4|D|1|1,4 に移動します。
-- closure VALUES (4, 1, 2) => delete => insert => closure VALUES (4, 1, 1)
-- closure VALUES (4, 3, 1) => delete
-- closure VALUES (4, 4, 0) 変更なし
--
-- closure VALUES (7, 1, 3) => delete => insert => closure VALUES (7, 1, 2)
-- closure VALUES (7, 3, 2) => delete
-- closure VALUES (7, 4, 1) 変更なし
-- closure VALUES (7, 7, 0) 変更なし
DELETE FROM closure
    WHERE descendant IN (SELECT descendant FROM closure WHERE ancestor = 4)
      AND ancestor NOT IN (SELECT descendant FROM closure WHERE ancestor = 4);

INSERT INTO closure
    SELECT D.descendant, A.ancestor, A.depth + D.depth + 1
        FROM closure AS A JOIN closure AS D
        WHERE A.descendant = (SELECT ancestor FROM closure WHERE descendant = 3 AND depth = 1)
          AND D.ancestor = 4;

-- 3|C|1|1,3 を削除します。
DELETE FROM closure
    WHERE descendant = 3;

-- 5|E|2|1,3,5 を 5|E|2|1,4,5 へ
-- 6|F|2|1,3,6 を 6|F|2|1,4,6 へ書き直します。
UPDATE closure
    SET ancestor = 4
    WHERE ancestor = 3;

-- => 1|A|0|1
--    2|B|1|1,2
--    4|D|1|1,4
--    5|E|2|1,4,5
--    6|F|2|1,4,6
--    7|G|2|1,4,7

--COMMIT;
ROLLBACK;

葉を追加するとき、 閉包表の親から根までの ancestor を受け継いで、 depth に 1 を加えた行を追加します。 さらに葉自身の行を閉包表へ追加します。

BEGIN TRANSACTION;

-- 2|B|1|1,2 の直下に葉 8|H|2|1,2,8 を追加します。
INSERT INTO entries VALUES (8, 'H');
INSERT INTO closure
    SELECT 8, ancestor, depth + 1 FROM closure WHERE descendant = 2
    UNION ALL
    SELECT 8, 8, 0;

-- => 1|A|0|1
--    2|B|1|1,2
--    8|H|2|1,2,8
--    3|C|1|1,3
--    4|D|2|1,3,4
--    7|G|3|1,3,4,7
--    5|E|2|1,3,5
--    6|F|2|1,3,6

--COMMIT;
ROLLBACK;

経路の途中にノードを追加するときは、 まず葉として追加します。 例えばノード 4 とノード 6 の直上にノード 8 を挿入するときは、 4 の直上の親に葉 8 を追加します。 その後のやりかたはいくつか考えられますが、 ここでは使いまわしが効く方法を採用し、 ノード 4 の部分木をノード 8 の下へ移動することにします。 続いて、 ノード 6 の部分木もノード 8 の下へ移動します。 ノード 4 の部分木を移動するには、 ノード 4 を ancestor に含むすべての経路に対して、 経路の先頭からノード 4 の直前までを削除してから、 ノード 8 の直下に根までの経路を作り直します。

BEGIN TRANSACTION;

-- 4|E|2|1,3,4 と 6|F|2|1,3,6 の上に 8|H を追加します。
INSERT INTO entries VALUES (8, 'H');
INSERT INTO closure
    SELECT 8, ancestor, depth + 1
        FROM closure
        WHERE descendant = (SELECT ancestor FROM closure WHERE descendant = 4 AND depth = 1)
    UNION ALL
    SELECT 8, 8, 0;

-- 4|E|2|1,3,4 をノード 3 の直下から、 ノード 8 の直下へ移動して 4|E|3|1,3,8,4| に作り直します。
-- そのとき同時に 7|G|3|1,3,4,7 もノード 8 の下へ移動させて 7|G|4|1,3,8,4,7 にします。
DELETE FROM closure
    WHERE descendant IN (SELECT descendant FROM closure WHERE ancestor = 4)
      AND ancestor NOT IN (SELECT descendant FROM closure WHERE ancestor = 4);

INSERT INTO closure
    SELECT D.descendant, A.ancestor, A.depth + D.depth + 1
        FROM closure AS A JOIN closure AS D
        WHERE A.descendant = 8
          AND D.ancestor = 4;

-- 6|E|2|1,3,6 をノード 3 の直下から、 ノード 8 の直下へ移動して 6|E|3|1,3,8,6| に作り直します。
DELETE FROM closure
    WHERE descendant IN (SELECT descendant FROM closure WHERE ancestor = 6)
      AND ancestor NOT IN (SELECT descendant FROM closure WHERE ancestor = 6);

INSERT INTO closure
    SELECT D.descendant, A.ancestor, A.depth + D.depth + 1
        FROM closure AS A JOIN closure AS D
        WHERE A.descendant = 8
          AND D.ancestor = 6;

-- => 1|A|0|1
--    2|B|1|1,2
--    3|C|1|1,3
--    5|E|3|1,3,5
--    8|H|2|1,3,8
--    4|D|2|1,3,8,4
--    7|G|3|1,3,8,4,7
--    6|F|3|1,3,8,6

--COMMIT;
ROLLBACK;