RDBで経路列挙モデルを用いて木構造を扱う

こんにちは、株式会社CINC開発本部です。

再帰的な関連を持ったデータをリレーショナルデータベースで扱う機会があったので紹介したいと思います。

そもそもMySQLをはじめとしたリレーショナルデータベースは、列と行で構成されるテーブルの構造体であり、木構造のような再帰的構造を表現することが苦手とされています。 ただ現在では、リレーショナルデータベースで階層構造を扱うにあたり、いくつかの解法が存在します。

• 隣接リストモデル
• 入れ子集合モデル
• 経路列挙型モデル

今回私は、経路列挙モデルを取り上げることにします。

経路列挙モデル

経路列挙モデルとは、対象ノードの先祖までの経路を属性として格納することで、木構造を表現するモデルです。 下記のディレクトリ構造を例に見ていきます。

経路列挙モデルでは、上記の構造を下記のように表現することができます。

directory	path
top	/top/
marketing	/top/marketing/
socal	/top/social/
programming	/top/technology/programming/
database	/top/technology/database/
server	/top/technology/server/
php	/top/technology/programming/php/
python	/top/technology/programming/python/
go	/top/technology/programming/go/
7.0	/top/technology/programming/7.0/

または、各ノードのパス文字列を数値に置き換えることで経路（path）を表現してもいいでしょう。

directory	path
top	/1/
marketing	/1/1/
technology	/1/2/
socal	/1/3/
programming	/1/2/1/
database	/1/2/2/
server	/1/2/3/
php	/1/2/1/1/
python	/1/2/1/2/
go	/1/2/1/3/
7.0	/1/2/1/1/1/

このモデルが優れているのは、各ノードまでの絶対パスをそれぞれのレコードに持つことで可能にするその経路探索のパフォーマンスです。 例えば、「programming」の先祖を取得するには、下記のクエリで可能です。

SELECT *
FROM directories
WHERE '/top/technology/programming/' LIKE CONCAT(path, '%');

このクエリは/top/%、/top/technology/%、/top/technology/programming/%の各パターンとマッチします。 また、「programming」の子孫はWHERE句の条件式を逆順にすることで取得ができます。

SELECT *
FROM directories
WHERE path LIKE CONCAT('/top/technology/programming/', '%');

/top/technology/programming/の子孫をパス文字列の前方一致で検索をかけます。 各ノードは自身の包含関係のためテーブル上に置いて常に一意になるためインデックを使用しての検索も可能になります。 その際、pathカラムはパス文字列の文字列長にカラムのサイズが左右されるため、上記で提示した数値パスに置き換えることも検討に入れても良いかもしれません。

また各ノードの深さは、パスの文字列長からパスを削除したパス文字列を減算して、両端の/（スラッシュ）分削除することで取得できます。

SELECT
  directory,
  LENGTH(path) - LENGTH(REPLACE(path, '/', '')) - 1
FROM directories;

新しいノードの追加には、多少複雑ですが、正規表現を使用することで可能になります。 「machinelearning」というディレクトリを、「programming」、「database」、「server」の3階層目に追加します。 3階層目に一意なディレクトリがいくつ存在するか、をカウントすることがこの処理において重要です。 まず正規表現で3階層目に存在するディレクトリを抽出します。 抽出したレコードから更にSUBSTRING_INDEX()関数で/の後ろから2番目、つまり3階層目のディレクトリを抽出し、GROUP BYで重複を弾いたカラム数をカウントしている。 クエリは下記の様になります。

SELECT 
  SUBSTRING_INDEX(path, '/', -2) AS path_str
FROM directories
WHERE 
  path REGEXP '^/[a-z0-9]+/[a-z0-9]+/[a-z0-9]+/$'
GROUP BY path_str;

出力の結果が、3階層目に存在する既存のディレクトリ数になるので、2階層目までのパスと+1してあげた値を連結したあものが新規ノードの数値パスになります。

経路列挙モデルを用いてデータ構造を設計することで、任意の数（正確にはカラムで指定したデータ型の許容バイト数まで）の包含関係を単純なクエリで取得することが可能であることを紹介してきました。

ただ、経路列挙モデルも万能ではありません。各レコードに自身までの経路をすべて保持しているため、更新や削除の処理が複雑化してしまうという欠点もあります。 そうしたデメリットも把握した上で、今回のディレクトリ構造のように、頻繁な更新のない階層構造データをRDBで扱う場合には一つの選択肢になるかと思います。