MySQL でツリー構造 by 閉包テーブルモデル

備忘録。

SQL アンチパターンに載っていた木構造RDB で表現するためのモデルの1つ、閉包テーブルモデルの MySQL による実装について。

今回は以下の制約をかける。

  • 簡略のため、各ノードは id のみを持つ
  • ノードの削除はサポートしない
  • ノードの追加は葉のみ

以下の5つのインタフェースを実装することを考える。

  • ノードを追加する addNode(id, parentId)
  • 子孫ノードを全て返す getDescendantsOf(id)
  • 先祖ノードを全て返す getAncestorsOf(id)
  • 直接の子ノードを全て返す getChildrenOf(id)
  • 直接の親ノードを返す getParentOf(id)

スキーマは以下のようになる:

CREATE TABLE tree (
  id INTEGER NOT NULL PRIMARY KEY
);

CREATE TABLE tree_path (
  ancestor INTEGER NOT NULL,
  descendant INTEGER NOT NULL,
  PRIMARY KEY(ancestor, descendant),
  FOREIGN KEY(ancestor) REFERENCES tree (id),
  FOREIGN KEY(descendant) REFERENCES tree (id)
);

addNode(idm parentId)

INSERT INTO tree (id) VALUES (#{id});

INSERT INTO tree_path (ancestor, descendant)
  SELECT other.ancestor, #{id} FROM tree_path AS other
    WHERE other.descendant = #{parentId}
  UNION ALL
  SELECT #{id}, #{id};

tree テーブルに加えて、tree_path テーブルに挿入する必要がある。

getDescendantsOf(id)

SELECT descendant FROM tree_path
  WHERE ancestor = #{id} AND descendant != #{id};

見ての通り。

getAncestorsOf(id)

SELECT ancestor FROM tree_path
  WHERE descendant = #{id} AND ancestor != #{id};

こちらも見ての通り。

getParentOf(id)

SELECT ancestor FROM tree_path
  WHERE descendant IN (
    SELECT ancestor FROM tree_path
      WHERE descendant = #{id} AND ancestor != #{id}
  )
  GROUP BY ancestor ORDER BY COUNT(*) LIMIT 1;

サブクエリは getAncestorsOf と同じ。あるノードの先祖の ID の中で、親ノード側として登録されているパスが一番少ないのが、直接の親ノードになる。