MariaDB講座 / 再帰CTEで階層を検索し、循環を防ぐ
再帰CTEは開始行から関連をたどり、次の行を繰り返し作る共通表式です。階層を安全に読むには開始条件、停止条件、十分なパス幅、循環への対応と最終ソートが必要です。
再帰が必要な構造か判断する
通常のCTEは中間名、再帰CTEはその定義自身を参照します。anchorが初期行、recursive memberが直前の結果から次を作り、ここではUNION ALLで組み合わせます。可変深度の分類や組織で有効ですが、固定二階層ならJOINが単純な場合もあります。
親から子を探す索引と業務上の深さ上限も必要です。深さ制限で切れた結果を、全階層が取れた証拠とはしません。
六分類の完全な例を作る
appops_labを作成できる管理者または実習アカウントで接続します。既存category_treeがあれば先に定義と行を確認し、無条件に再作成しません。
CREATE DATABASE IF NOT EXISTS appops_lab
CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci;
USE appops_lab;
CREATE TABLE category_tree (
category_id INT NOT NULL PRIMARY KEY,
parent_id INT NULL,
category_name VARCHAR(40) NOT NULL,
INDEX ix_parent (parent_id),
CONSTRAINT fk_category_parent FOREIGN KEY (parent_id)
REFERENCES category_tree(category_id)
) ENGINE=InnoDB;
INSERT INTO category_tree VALUES
(1, NULL, 'Catalog'), (2, 1, 'Books'), (3, 1, 'Tools'),
(4, 2, 'SQL'), (5, 2, 'Python'), (6, 3, 'Editors');
Catalogの下にBooksとTools、Booksの下にSQLとPython、Toolsの下にEditorsがあります。名称は実データの英語サンプルです。図の説明は日本語で示します。外部キーは親の存在を確認しますが、循環のない木を保証しません。
深さと経路を記録して検索する
全体を実行します。
WITH RECURSIVE tree AS (
SELECT category_id, parent_id, category_name, 0 AS depth,
CAST(CONCAT('/', category_id, '/') AS CHAR(1000)) AS visited,
CAST(category_name AS CHAR(1000)) AS name_path
FROM category_tree WHERE category_id = 1
UNION ALL
SELECT c.category_id, c.parent_id, c.category_name, t.depth + 1,
CONCAT(t.visited, c.category_id, '/'),
CONCAT(t.name_path, ' > ', c.category_name)
FROM category_tree c JOIN tree t ON c.parent_id = t.category_id
WHERE t.depth < 8
AND LOCATE(CONCAT('/', c.category_id, '/'), t.visited) = 0
)
SELECT category_id, parent_id, depth, name_path
FROM tree ORDER BY depth, category_id;
ID1は深さ0、2・3は1、4・5・6は2です。visitedは/で整数IDを囲み、1が11の一部へ誤一致しないようにします。anchorのCHAR(1000)が後続の長い連結パスの型幅を確保します。短い初期値から狭い型が決まると後の経路があふれ得ます。
この幅は短名・整数ID・最大深度8という例の条件です。現実の長さに応じて再計算します。表示順を保証するのは最後のORDER BYで、再帰評価順や文字列パスの辞書順と整数順を同一視しません。
上限と開始点を一つずつ変える
t.depth < 8だけを< 1へ変えると、開始と直下のID1・2・3です。比較後8へ戻します。開始をcategory_id = 2に変えると2・4・5で、Booksが深さ0になります。これも元に戻します。
max_recursive_iterationsは別の計算回数上限で、業務上の停止条件や親構造の検証を代替しません。深すぎる場合は実構造を調べてから上限を選びます。
循環を作り、同じ接続で取り消す
次の後で完全な再帰SQLをもう一度実行します。
START TRANSACTION; UPDATE category_tree SET parent_id = 4 WHERE category_id = 1;
1→2→4→1という循環でも、ID1から明示開始したこの問い合わせは訪問済みを除いて六行で終わります。すぐ元へ戻します。
ROLLBACK; SELECT category_id, parent_id FROM category_tree WHERE category_id = 1;
ID1の親がNULLへ戻るか確認します。parent_id IS NULLを開始にすると、根が失われた循環成分を丸ごと見逃すことがあります。探索中の再訪防止は、全DBに循環がない証明ではありません。MariaDBのCYCLE ... RESTRICTも選択肢ですが、この例は経路検査を見せています。
階層全体の条件を別々に検査する
開始根、欠けた親、自分自身の親、循環、到達不能な成分を別条件として確認します。深さとパス幅をそろえ、子検索の索引とEXPLAIN、件数を照合します。不要と確認した実習表だけにDROP TABLE appops_lab.category_tree;を使い、業務表へ読み替えません。構造削除は普通のROLLBACKでは戻せません。
