木構造のデータベースでの処理

木構造は良く使われるデータ構造ですね。オブジェクト指向プログラミング言語の場合は各ノードに親ノードのポインターを加えたらコードを書きやすいですが、データベースの場合は全てのノードを出力させるクエリが長くなったり、離れた先祖ノードをすぐ計算できなかったりしますので、木構造の処理は難しくなります。

そうして、今回紹介したいのはデータベースでも扱いやすい入れ子集合モデルです。

そのモデルは子ノードが親ノードの部分集合になります。わかりやすくなるように、具体的な例を挙げます。例えば、オンラインショップの商品はカテゴリーが木構造で現れることが多いです。下記のようなカテゴリーを考えてみましょう。

入れ子集合モデルしたら、下記のように構造になります。

部分集合をはっきりと区別できるように左から右へ集合の境域に番号をつけましょう。

終わったらモデル化出来上がりました。

そのうような構造をデータベースに保存しやすいです。MySQLでコードの例を挙げます。

CREATE TABLE `CategoryTree` (
  `CategoryID` int(11) NOT NULL AUTO_INCREMENT,
  `CategoryName` varchar(128) CHARACTER SET utf8 NOT NULL,
  `CategoryLeft` int(11) NOT NULL,
  `CategoryRight` int(11) NOT NULL,
  PRIMARY KEY (`CategoryID`)
) ENGINE=InnoDB AUTO_INCREMENT=62 DEFAULT CHARSET=latin1;

以上のようなカテゴリーがあれば、入っているデータはこうなります。

　
SELECT CategoryName, CategoryLeft,CategoryRight
FROM CategoryTree
ORDER BY CategoryLeft

木構造のデータが綺麗に出力できるように、深さを表すこういうクエリを書いておいて実行してみましょう。

SELECT node.CategoryName, (COUNT(parent.CategoryName) - 1) AS depth
FROM CategoryTree AS node,
     CategoryTree AS parent
WHERE node.CategoryLeft BETWEEN parent.CategoryLeft AND parent.CategoryRight
GROUP BY node.CategoryName, node.CategoryLeft
ORDER BY node.CategoryLeft;

データ収集のリクエストは手間がかからないですが、新しいノードの追加と要らないノードの削除は他のノードに影響を与えるため改めて計算する必要がありますので、APIとしてプロシージャを作った方が良いと思います。

CREATE DEFINER=`root`@`localhost` PROCEDURE `addCategory`(IN _parent VARCHAR(128) CHARSET utf8, IN _name VARCHAR(128) CHARSET utf8)
BEGIN

SELECT CategoryRight INTO @PrnRight 
FROM CategoryTree
WHERE CategoryName = _parent;

UPDATE CategoryTree 
SET CategoryRight = CategoryRight + 2 
WHERE CategoryRight >= @PrnRight;
UPDATE CategoryTree 
SET CategoryLeft = CategoryLeft + 2 
WHERE CategoryLeft > @PrnRight;

INSERT INTO CategoryTree(CategoryName, CategoryLeft, CategoryRight) 
VALUES(_name,  @PrnRight ,  @PrnRight+ 1);

END

CREATE DEFINER=`root`@`localhost` PROCEDURE `deleteCategory`(IN _name VARCHAR(128) CHARSET utf8)
BEGIN

SELECT  CategoryLeft,  CategoryRight INTO @Lft, @Rgt 
FROM CategoryTree
WHERE CategoryName = _name;

UPDATE CategoryTree 
SET CategoryRight = CategoryRight - 1 
WHERE CategoryRight >= @Lft;
UPDATE CategoryTree 
SET CategoryLeft = CategoryLeft - 1 
WHERE CategoryLeft >= @Lft;

UPDATE CategoryTree 
SET CategoryLeft = CategoryLeft - 1 
WHERE CategoryLeft >= @Rgt;
UPDATE CategoryTree 
SET CategoryRight = CategoryRight - 1 
WHERE CategoryRight >= @Rgt;

DELETE FROM CategoryTree WHERE CategoryName = _name;

END

私は実際に入れ子集合モデルを使ったことがありますし、結構便利だと思いますので、皆さんにシェアしたいです。