【SQLアンチパターン2章】経路列挙・入れ子集合・閉包テーブル

目的

再帰的な関連を持つデータ(スレッドのコメント欄など)の階層構造を格納し、クエリを実行する。

↓全てに共通するAccountsテーブル

create table Accounts (
account_id serial primary key, 
name varchar(10) not null
);

insert into Accounts 
values (1,'佐藤'),(2,'鈴木'),(3,'高橋'), (4,'田中'), (5,'伊藤');

経路列挙(Path Enumeration)

先祖の系譜を表す文字列を各ノードの属性として格納する。

create table Comments1 (
comment_id serial primary key, 
path varchar(1000), 
author bigint unsigned not null, 
comment text not null, 
foreign key (author) references Accounts(account_id)
);

insert into Comments1 
values (1, '1/', 1, '明日暇な人いる？'),(2, '1/2/', 2, '忙しいわ'), (3, '1/2/3/', 1, 'わかった'),(4, '1/4/', 3, '暇だよー'),(5, '1/4/5/', 4, '俺も'),(6, '1/4/6/', 1, '遊びに行こう'),(7, '1/4/6/7/', 5, '私も行きたい');

コメント7とその先祖を取得

select * 
from Comments1 as c 
where '1/4/6/7/' like concat(c.path, '%');

1/4/6/%、1/4/%、1/%のパターンとマッチする。

コメント4とその子孫を取得

select * 
from Comments1 as c 
where c.path like concat('1/4/', '%');

コメント4とその子孫の発言者別のコメント数、　コメント1とその子孫の発言者別のコメント数を取得

select c.author, count(*) 
from Comments1 as c 
where c.path like concat('1/4/', '%') 
group by c.author;

select c.author, count(*) 
from Comments1 as c 
where c.path like concat('1/', '%') 
group by c.author;

コメント7の子に挿入

insert into Comments1 (author, comment) 
values (1, 'よし、一緒に行こう');

update Comments1 
set path = concat((select x.path from (select path from Comments1 where comment_id = 7) as x), last_insert_id(), '/') 
where comment_id = last_insert_id();

last_insert_id()は、現在のセッションでの行挿入によって生成された最新のIDを返す。

ちなみに、以下のSQL文でpathの一部を取得している。

select x.path 
from (select path from Comments1 where comment_id = 7) as x;

入れ子集合(Nested Set)

直近の親ではなく、子孫の集合に関する情報を各ノードに格納する。

create table Comments2 (
comment_id serial primary key, 
nsleft integer not null, 
nsright integer not null, 
author bigint unsigned not null, 
comment text not null, 
foreign key (author) references Accounts(account_id)
);

insert into Comments2 
values (1,1,14,1, '明日暇な人いる？'),(2,2,5,2,'忙しいわ'),(3,3,4,1,'わかった'),(4,6,13,3,'暇だよー'),(5,7,8,4,'俺も'),(6,9,12,1,'遊びに行こう'),(7,10,11,5,'私も行きたい');

コメント4の子孫を取得

select c2.* 
from Comments2 as c1 
inner join Comments2 as c2 
on c2.nsleft between c1.nsleft and c1.nsright 
where c1.comment_id = 4;

コメント4のノードのnsleftとnsrightの間にnsleftが含まれるノードを検索する。

コメント6とその先祖を取得

select c2.* 
from Comments2 as c1 
inner join Comments2 as c2 
on c1.nsleft between c2.nsleft and c2.nsright 
where c1.comment_id = 6;

コメント6のノードのnsleftを、nsleftとnsrightの間に含むノードを検索する。

コメント6の親を取得

select parent.* 
from Comments2 as c 
inner join Comments2 as parent 
on parent.nsleft < c.nsleft and c.nsleft < parent.nsright 
left outer join Comments2 as in_between 
on in_between.nsleft < c.nsleft and c.nsleft < in_between.nsright 
and parent.nsleft < in_between.nsleft and in_between.nsleft < parent.nsright 
where c.comment_id = 6 
and in_between.comment_id is null;

閉包テーブル(Closuer Table)

直近の親子関係だけではなく、ツリー全体のパスを格納する。

create table Comments3 (
comment_id serial primary key, 
author bigint unsigned not null, 
comment text not null, 
foreign key (author) references Accounts(account_id)
);

create table TreePaths (
ancestor bigint unsigned not null, 
descendant bigint unsigned not null, 
primary key (ancestor, descendant), 
foreign key (ancestor) references Comments3(comment_id), 
foreign key (descendant) references Comments3(comment_id)
);

insert into TreePaths 
values (1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(2,2),(2,3),(3,3),(4,4),(4,5),(4,6),(4,7),(5,5),(6,6),(6,7),(7,7);

コメント4とその子孫を取得

select c.* 
from Comments3 as c 
inner join TreePaths as t on c.comment_id = t.descendant 
where t.ancestor = 4;

コメント6とその先祖を取得

select c.* 
from Comments3 as c 
inner join TreePaths as t on comment_id = t.ancestor 
where t.descendant = 6;

コメント5の子を挿入

insert into Comments3 values(8,1,いいね);

insert into TreePaths 
select t.ancestor, 8 
from TreePaths as t 
where t.descendant = 5 
union all 
select 8, 8;