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

# 目的

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

<img width="655" alt="スクリーンショット 2020-08-01 8.48.37.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/591c58b2-dbca-8a81-a41f-2df5c022e36c.png">

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

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

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

<img width="503" alt="スクリーンショット 2020-08-01 8.38.58.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/0e82affc-26bb-e2e0-8e2c-6793c94bd57e.png">


# 経路列挙(Path Enumeration)

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

```sql
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)
);
```

```sql
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, '私も行きたい');
```

<img width="574" alt="スクリーンショット 2020-08-01 8.47.45.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/dccfa279-f7c0-16c9-1483-22057d522977.png">

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

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

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

<img width="926" alt="スクリーンショット 2020-08-01 8.57.01.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/64fc39d5-d40c-65bc-d993-ab88a17bfe54.png">

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

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

<img width="909" alt="スクリーンショット 2020-08-01 9.03.08.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/51ead6a3-28c9-5180-1c27-9d67afce5c94.png">

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

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

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

<img width="1209" alt="スクリーンショット 2020-08-01 9.07.40.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/2dc4ab20-8560-715e-2544-f63106351d82.png">

### コメント7の子に挿入

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

<img width="956" alt="スクリーンショット 2020-08-01 9.14.32.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/845bec71-1372-1cc1-18eb-a957922fb912.png">

<img width="610" alt="スクリーンショット 2020-08-01 9.15.09.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/e31d3f17-53a9-4991-2e9f-6481c75da275.png">

```sql
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を返す。

<img width="1429" alt="スクリーンショット 2020-08-01 9.23.08.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/20dc7a5c-1892-efb0-c3af-617cfa5faab7.png">

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

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

<img width="963" alt="スクリーンショット 2020-08-01 9.23.39.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/b683ad46-329d-5309-c236-c947fc902791.png">


# 入れ子集合(Nested Set)

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

<img width="736" alt="スクリーンショット 2020-08-01 9.36.45.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/896b7224-7d70-1624-668b-169bf270e1e2.png">


```sql
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)
);
```

```sql
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,'私も行きたい');
```

<img width="660" alt="スクリーンショット 2020-08-01 9.35.01.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/c9fd99ec-3a06-b69c-0c5a-037e464612e2.png">


### コメント4の子孫を取得

```sql
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``が含まれるノードを検索する。

<img width="611" alt="スクリーンショット 2020-08-01 9.52.54.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/8ca5613e-4127-dcf8-5914-f6f1723dcfdc.png">

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

```sql
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``の間に含むノードを検索する。

<img width="658" alt="スクリーンショット 2020-08-01 9.59.57.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/6042ad11-1b37-4442-0c48-721272326acd.png">

### コメント6の親を取得

```sql
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;
```

<img width="545" alt="スクリーンショット 2020-08-01 10.05.18.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/e636776f-fe2d-8580-2d0d-aba4f2ed3a6f.png">


#閉包テーブル(Closuer Table)

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

<img width="761" alt="スクリーンショット 2020-08-01 10.27.24.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/fb430c07-4b72-305f-5059-376f2cc2cb57.png">


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

```sql 
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)
);
```

```sql
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);
```

<img width="517" alt="スクリーンショット 2020-08-01 10.23.26.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/d8fb1740-78ca-8e69-27b6-3be96f8c024a.png">

<img width="504" alt="スクリーンショット 2020-08-01 10.29.49.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/6f5a06a0-f4dd-81bc-1258-5b8c6a23b945.png">

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

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

<img width="429" alt="スクリーンショット 2020-08-01 10.31.25.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/bc3d8b45-f0ae-5a78-3587-f63c72e3be66.png">

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

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

<img width="483" alt="スクリーンショット 2020-08-01 10.33.36.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/cccdca6d-a3ff-9597-377d-fcb87dc1142c.png">

### コメント5の子を挿入

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

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

<img width="509" alt="スクリーンショット 2020-08-01 10.41.30.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402245/1b00d7a7-c52d-4b08-db68-bebadafcaaff.png">