SQLでツリー（木構造）を実装する その３

昨晩は24時からWebサーバ切り替え作業があって、切り替え後動作確認と多少の修正。 今日は9:30から客先リリース。無事完了してキモチが少し楽になりました。

さて、SQLのツリーですが、ツリーの内容確認ができるようになったので、ツリーの操作方法を見ていきましょう。

ノードの追加

まず追加です。 参照サイトの3-3．リーフを追加するを参考にしました。 まずUPDATEを実行して追加する場所に１ノード分の隙間を用意し、その後ノードをINSERTします。 以下のようなストアドファンクションになりました。

CREATE OR REPLACE FUNCTION section_add(integer, text)
  RETURNS void AS
$BODY$
DECLARE
  -- 親部署ID
  parent_section_id ALIAS FOR $1;
  -- 新規登録する部署名
  new_section_name ALIAS FOR $2;
  parent_section_rgt integer;
BEGIN
  -- 親部署のrgtを取得
  SELECT rgt
  INTO parent_section_rgt
  FROM section
  WHERE section_id = parent_section_id;

  -- 親部署が見つからない場合は処理中断
  IF NOT FOUND THEN
    RAISE EXCEPTION 'no such section: %', parent_section_id;
    RETURN;
  END IF;

  -- 新規部署の挿入前に場所を確保
  UPDATE section
  SET
    lft = CASE
      WHEN parent_section_rgt < lft THEN lft + 2
      ELSE lft
    END,
    rgt = CASE
      WHEN parent_section_rgt <= rgt THEN rgt + 2
      ELSE rgt
    END,
    update_time = now()
  WHERE parent_section_rgt <= rgt;

  -- 更新に失敗した場合は処理中断
  IF NOT FOUND THEN
    RAISE EXCEPTION 'update failed';
    RETURN;
  END IF;

  -- 新しい部署を挿入
  INSERT INTO section(section_name, lft, rgt)
  VALUES(new_section_name, parent_section_rgt, parent_section_rgt + 1);

  -- 挿入に失敗した場合は処理中断ｎ
  IF NOT FOUND THEN
    RAISE EXCEPTION 'insert failed';
    RETURN;
  END IF;

  RETURN;
END;
$BODY$
  LANGUAGE 'plpgsql' VOLATILE;

パラメータは親部署のIDと、新規登録する部署名です。以下のように呼び出します。

SELECT section_add(1, '部署名');

親部署は必ず必要になるので、一からツリーを作成する場合は最低でもルートノードが必要になります。 ルートノードはlft=1, rgt=2で事前にINSERTしておきましょう。 処理に失敗した場合は例外が発生し、ファンクション内でトランザクションがロールバックされます。

ノードの削除

追加の次は削除です。 参照サイトの3-2．単一ノードの削除を参考にしました。 単純に指定したノードの情報を消すだけなので、例えばulを削除するとその下にあったliはbodyに含まれることになり、 ulの下をまとめて消すような動作はしません。 まとめて消したい場合は3-1．部分木の削除を参照してください。 （ウェブ画面のほうでリーフでないノードは削除が実行できないようにしたので、単一の処理しか実装していません。） ストアドファンクションは以下のようになりました。

CREATE OR REPLACE FUNCTION section_delete(integer)
  RETURNS void AS
$BODY$
DECLARE
BEGIN
  -- 削除
  -- この部署の下層に部署が存在する場合は、下層の部署が２世代上に直接属すようになる
  DELETE FROM section
  WHERE section_id = $1;

  -- 削除されたかチェック
  IF NOT FOUND THEN
    RAISE EXCEPTION 'no such section: %', $1;
    RETURN;
  END IF;

  -- 欠番を埋める
  PERFORM section_pack();

  RETURN;
END;
$BODY$
  LANGUAGE 'plpgsql' VOLATILE;

以下のように実行します。

SELECT section_delete(5);

「欠番を埋める」という処理が入っていますが、これはノードの削除によって生じたlftとrgtの値の隙間を埋める処理です。 ルートノードから順にノードをどんどん登録していくと、lftとrgtを並べた値は1から始まる連番になり、あいだが空かないはずなのです。 ノードの表示や追加では欠番を埋めなくても処理に影響はありませんが、 欠番があるとlftとrgtの差が1であるノードはリーフノード（子孫がいればlftとrgtの間に最低2以上の差があるはずですよね？）という簡単なリーフノード確認が行えなくなり、不便なことがあるので埋めておきましょう。

欠番を埋める

参照サイトの3-6．添え字の欠番を埋めるを参考にしました。 欠番を埋めるには２ステップ必要です。 まずビューの作成。

CREATE VIEW v_section_lr AS
SELECT section.lft AS seq FROM section
UNION ALL 
SELECT section.rgt AS seq FROM section;

lftとrgtの値を取り出して１つの列に入れただけの簡単なビューです。 欠番がなければこのビューのseq列は1から始まる連番になっているはずですが、 欠番がある場合は連番になっていません。

連番ビューが準備できたらsection_packを定義します。

CREATE OR REPLACE FUNCTION section_pack()
  RETURNS void AS
$BODY$DECLARE
BEGIN
  -- 欠番を埋める
  UPDATE section
  SET
    lft = (
      SELECT count(*)
      FROM v_section_lr
      WHERE seq <= lft
    ),
    rgt = (
      SELECT count(*)
      FROM v_section_lr
      WHERE seq <= rgt
    ),
    update_time = now();

  IF FOUND THEN
    RETURN;
  ELSE
    RAISE EXCEPTION 'section_pack failed';
  END IF;
END;
$BODY$
  LANGUAGE 'plpgsql' VOLATILE;

実行後は掃除をしたような気持ちよさ。 不要なバグを避けるためにも入れておきましょう。

追加・削除ときたので、次は並べ替えです。