私は SQL の専門家ではありませんが、どなたか助けていただければ幸いです。
以下のように、再帰的な CTE を使用して値を取得します。
子 1 --> 親 1
親 1 --> 親 2
親 2 --> NULL
データの作成がうまくいかなかった場合、以下のようになります。これにより、CTE が無限再帰ループに陥り、最大再帰エラーが発生する可能性があります。データが膨大なため、この不良データを手動で確認することはできません。見分ける方法があれば教えてください。
子 1 --> 親 1
親 1 --> 子 1
また
子 1 --> 親 1
親 1 --> 親 2
親 2 --> 子 1
Postgres では、訪問したすべてのノードを配列に収集することで、これを簡単に防ぐことができます。
設定：
create table hierarchy (id integer, parent_id integer);
insert into hierarchy
values
(1, null), -- root element
(2, 1), -- first child
(3, 1), -- second child
(4, 3),
(5, 4),
(3, 5); -- endless loop
再帰クエリ:
with recursive tree as (
select id,
parent_id,
array[id] as all_parents
from hierarchy
where parent_id is null
union all
select c.id,
c.parent_id,
p.all_parents||c.id
from hierarchy c
join tree p
on c.parent_id = p.id
and c.id <> ALL (p.all_parents) -- this is the trick to exclude the endless loops
)
select *
from tree;
複数のツリーに対して同時にこれを行うには、ルート ノードの ID を子に引き継ぐ必要があります。
with recursive tree as (
select id,
parent_id,
array[id] as all_parents,
id as root_id
from hierarchy
where parent_id is null
union all
select c.id,
c.parent_id,
p.all_parents||c.id,
p.root_id
from hierarchy c
join tree p
on c.parent_id = p.id
and c.id <> ALL (p.all_parents) -- this is the trick to exclude the endless loops
and c.root_id = p.root_id
)
select *
from tree;
Postgres 14 では、サイクルを検出する (標準に準拠した)CYCLEオプションが導入されました。
with recursive tree as (
select id,
parent_id
from hierarchy
where parent_id is null
union all
select c.id,
c.parent_id
from hierarchy c
join tree p
on c.parent_id = p.id
)
cycle id -- track cycles for this column
set is_cycle -- adds a boolean column is_cycle
using path -- adds a column that contains all parents for the id
select *
from tree
where not is_cycle
隣接リスト (親子関係) でサイクルを検出する別の方法を次に示します。この場合、ノードは子列に一意の制約を適用できる親を 1 つだけ持つことができます (id下の表を参照)。これは、再帰クエリを介して隣接リストのクロージャ テーブルを計算することで機能します。レベル 0 ですべてのノードを独自の祖先としてクロージャ テーブルに追加することから開始し、隣接リストを反復してクロージャ テーブルを展開します。新しいレコードの子と祖先が元のレベル 0 (ゼロ) 以外のレベルで同じである場合、サイクルが検出されます。
-- For PostgreSQL and MySQL 8 use the Recursive key word in the CTE code:
-- with RECURSIVE cte(ancestor, child, lev, cycle) as (
with cte(ancestor, child, lev, cycle) as (
select id, id, 0, 0 from Table1
union all
select cte.ancestor
, Table1.id
, case when cte.ancestor = Table1.id then 0 else cte.lev + 1 end
, case when cte.ancestor = Table1.id then cte.lev + 1 else 0 end
from Table1
join cte
on cte.child = Table1.PARENT_ID
where cte.cycle = 0
) -- In oracle uncomment the next line
-- cycle child set isCycle to 'Y' default 'N'
select distinct
ancestor
, child
, lev
, max(cycle) over (partition by ancestor) cycle
from cte
Table1 に次の隣接リストがあるとします。
| parent_id | id |
|-----------|----|
| (null) | 1 |
| (null) | 2 |
| 1 | 3 |
| 3 | 4 |
| 1 | 5 |
| 2 | 6 |
| 6 | 7 |
| 7 | 8 |
| 9 | 10 |
| 10 | 11 |
| 11 | 9 |
SQL サーバー (および指示に従って変更された場合は Oracle、PostgreSQL、および MySQL 8) で機能する上記のクエリは、ノード 9、10、および 11 が長さ 3 のサイクルに参加していることを正しく検出します。
さまざまな DB でこれを示す SQL(/DB) Fiddles を以下に示します。