SQL Server 2019 Graph Database で実装された到達可能性を試した

# 初めに

SQL Server の Graph Database は SQL Server 2016 から実装されている。
・・・が正直言ってSQL Server 2017 までは RDB と特に差が見受けられない状態だった。
[SQL Server 2017 のGraph拡張を試してみた](https://qiita.com/KAZAMAI_NaruTo/items/e4bcd74ec35befdeeea0)

ところが、2019年10月に行われた [JSSUG](https://sqlserver.connpass.com/) の [SQL Server 勉強会](https://sqlserver.connpass.com/event/142199/)に於いて
[Graph Database のセッション](https://blog.jssug.jp/archives/374)があり、そこで到達可能性について実装されたことを知った。

早速この機能を試す。


# 第13回 JSSUG 「T-SQLでプログラムを作ろう」問題２ 
2018年12月の [JSSUG](https://sqlserver.connpass.com/) の [第13回 SQL Server 勉強会](https://sqlserver.connpass.com/event/111132/)に於いて「T-SQLでプログラムを作ろう」というセッションが催され、出された3問の問題に対して SQL を皆で作るというのが行われた。

その問題2 は次のようなものだった。

***

> ■仕様説明
> ・JSSUG_DEV データベースに、RELATIONテーブル(関係テーブル) があります。
> ■求めること
> ・RELATIONテーブルの ColAカラム列の値とColBカラム列のお互いの関係を探し、グルーピングを行い、グループIDは 1 から付番し、ColA 及び ColB の値を昇順で並び替えます。
> ■コーディング規則
> ・T-SQL で行うこと。他のCLR や言語を使ってはいけません。
> ・ユーザーファンクション、ストアドプロシージャの実装可能の数は制限はありません。
> ・変数名、一時テーブルを使う場合は、読めやすく書きましょう。
> ・なるべくループやカーソル処理を避けましょう。
> ■サンプルデータ

| ColA | ColB |
|:-:|:-:|
| A  | B |
| B  | C |
| D  | E |

> の場合、

| GroupID | ColValue |
|:-:|:-:|
| 1 | A |
| 1 | B |
| 1 | C |
| 2 | D |
| 2 | E |

> ■ 問題の JSSUG_DEV データベースの RELATION テーブルの中身

| ColA | ColB |
|:-:|:-:|
| A | A |
| A | B |
| B | C |
| B | D |
| E | F |
| G | H |
| G | F |
| J | D |
| K | C |
	

***

この問題に対して、 [第14回 SQL Server 勉強会](https://sqlserver.connpass.com/event/113907/) で[柳さんが解説](https://www.slideshare.net/ssuser79c1e3/lt-second)をしており、また僕も改めて[解いて](https://qiita.com/KAZAMAI_NaruTo/items/19d37d70cd53eda8c1c8)いる

しかし、この問題、まさに[グラフ](https://ja.wikipedia.org/wiki/グラフ理論) の到達可能性の問題である。
そこでこの問題を SQL Server 2019 の Graph Database の到達可能性を試す題材とする。

# 試してみる

次の手順で試す。
1. 問題用のテーブルを作成する
2. サンプル用・問題用・テスト用のデータを用意する
3. 解答用の Graph DB のテーブルを作成する
4. 問題用のテーブルのデータから Graph DB用のデータを作成する
5. 結果を出力するクエリを作る。


## 問題用のテーブルを作成する

とりあえず、問題用のテーブル

```2018Q2_01_01_CreateTable.sql
CREATE TABLE RELATION(
	ColA NVARCHAR(1)
	, ColB NVARCHAR(1));
```

## サンプル用・問題用・テスト用のデータを用意する
### サンプル用

サンプル用のデータ。TRUNCATE文を加えてデータを入れ替えられるようにしている。

```2018Q2_02_01_Sample1.sql
TRUNCATE TABLE RELATION;
INSERT INTO RELATION
	VALUES('A','B'),('B','C'),('D','E');
SELECT * FROM RELATION;
```
### 問題用
```2018Q2_02_02_Sample2.sql
TRUNCATE TABLE RELATION;
INSERT INTO RELATION
	VALUES
		('A','A'),('A','B'),('B','C')
		, ('B','D'),('E','F'),('G','H')
		, ('G','F'),('J','D'),('K','C')
;
SELECT * FROM RELATION;
```
###テスト用

到達までの PATH が長いものを含む場合を用意する。

```2018Q2_02_03_Sample3.sql
TRUNCATE TABLE RELATION;
INSERT INTO RELATION
	VALUES
		('A','B'),('B','C'),('C','D')
		, ('D','E'),('E','F'),('F','G')
		, ('G','H'),('H','I'),('I','J')
;
SELECT * FROM RELATION;
```

## 解答用の Graph DB のテーブルを作成する

Node には カラムの名前の属性が付く。Edge には追加の属性がないので明示的な列定義はない。
Edge のテーブルの CONNECTION 制約は SQL Server 2019 からの機能でグラフの対象の node を指定するものである。


```2018Q2_01_02_CreateGraphTable.sql
CREATE TABLE Q2N(
	ColValue NVARCHAR(1)
	) AS NODE
;
CREATE TABLE Q2E(
	CONSTRAINT CN_Q2E_NODE CONNECTION (Q2N TO Q2N)
	) AS EDGE
;
```

## 問題用のテーブルのデータから Graph DB用のデータを作成する

まず、RELATIONテーブルの ColA, ColB の両方から Node を抽出し、Q2Nテーブルに登録する。

その後、RELATIONテーブルと Q2N テーブルを結び付けて Q2E に登録する。
問題の RELATION は無向グラフなので ColA から ColB、ColB から ColA の双方向を登録する。
また、到達可能性を扱ううえで便利なので各Nodeから 自分自身への Path も登録する。
Q2E に登録した結果を確認する際に、Q2N と結び付けて ColValue を出している。

```2018Q2_03_01_PrepareGraphData.sql
TRUNCATE TABLE Q2E;
DELETE FROM Q2N;

INSERT INTO Q2N(ColValue)
SELECT
		ColA
	FROM
		RELATION
UNION
SELECT
		ColB
	FROM
		RELATION
;

INSERT INTO Q2E(
	$from_id
	, $to_id)
SELECT
		$node_id
		, $node_id
	FROM
		Q2N
UNION
SELECT
		NS.$node_id
		, ND.$node_id
	FROM
		Q2N NS
		INNER JOIN RELATION
		ON NS.ColValue = RELATION.ColA
		INNER JOIN Q2N ND
		ON ND.ColValue = RELATION.ColB
UNION
SELECT
		NS.$node_id
		, ND.$node_id
	FROM
		Q2N NS
		INNER JOIN RELATION
		ON NS.ColValue = RELATION.ColB
		INNER JOIN Q2N ND
		ON ND.ColValue = RELATION.ColA

;


SELECT * FROM Q2N;
SELECT
	NS.ColValue AS ColS
	, ND.ColValue AS ColD
	, Q2E.*
FROM
	Q2E
	INNER JOIN Q2N NS
	ON Q2E.$from_id = NS.$node_id
	INNER JOIN Q2N ND
	ON Q2E.$to_id = ND.$node_id
```

## 結果を出力するクエリを作る。

お膳立てができたので結果を求める。
クエリの結果は問題用データ(2018Q2_02_02_Sample2.sql) の場合のものとする。

RELATION

| ColA | ColB |
|:-:|:-:|
| A | A |
| A | B |
| B | C |
| B | D |
| E | F |
| G | H |
| G | F |
| J | D |
| K | C |

Q2N

| ColValue |
|:-:|
| A |
| B |
| C |
| D |
| E |
| F |
| G |
| J |
| K |

### 各Node から到達可能な Node

いきなり到達可能性を使う。

```
SELECT
			NS.ColValue
			, LAST_VALUE(ND.ColValue) WITHIN GROUP (GRAPH PATH) ColD
		FROM
			Q2N NS
			, Q2N FOR PATH ND
			, Q2E FOR PATH
		WHERE
			match(SHORTEST_PATH(NS(-(Q2E)->ND)+))
```
```
match(SHORTEST_PATH(NS(-(Q2E)->ND)+))
```
の条件により、開始点を NS として到達可能な Node とその Node へ最初に到達したときの Path を取得する条件となる。

```
(-(Q2E)->ND)+
```
の最後 の `+` が一般的な正規表現での `+` と同じ、「一つ以上の任意の長さ」を表すことになる。
この ()+ での書式は SHORTEST_PATH 関数の中でのみ利用できる。
そして ()+ の中に出現する Edgeテーブル、Nodeテーブルは FROM句で `FOR PATH` を付ける必要があり、そして FOR PATH をつけると`()+` あるは `(){1, n}` といった SHORTEST_PATH の中でのみ利用可能となる。
`FOR PATH` をつけたテーブルにエイリアスを設定する場合は FOR PATH の後に書く。

### 到達可能な Node のグループ分け

各Node からの到達点を挙げられるようになったので到達可能な点で辞書順序的に"最小"のものを取ることで到達可能な Node のグループ分けができる。

```
SELECT
	MIN(ColD) AS Grp
	, ColValue
FROM
	(
		SELECT
			NS.ColValue
			, LAST_VALUE(ND.ColValue) WITHIN GROUP (GRAPH PATH) ColD
		FROM
			Q2N NS
			, Q2N FOR PATH ND
			, Q2E FOR PATH
		WHERE
			match(SHORTEST_PATH(NS(-(Q2E)->ND)+))) P
GROUP BY
	ColValue
ORDER BY
	GRP
```

結果

| Grp | ColValue |
|:-:|:-:|
| A | A |
| A | B |
| A | C |
| A | D |
| A | J |
| A | K |
| E | E |
| E | F |
| E | G |
| E | H |

### 結果取得

グループ分けに辞書的順序で番号をつければ結果が得られる。
番号付けには DENSE_RANK() を用いる。

```2018Q2_03_02_GetGroup.sql
SELECT
	DENSE_RANK() OVER (ORDER BY MIN(ColD)) AS GroupID
	, ColValue
FROM
	(
		SELECT
			NS.ColValue
			, LAST_VALUE(ND.ColValue) WITHIN GROUP (GRAPH PATH) ColD
		FROM
			Q2N NS
			, Q2N FOR PATH ND
			, Q2E FOR PATH
		WHERE
			match(SHORTEST_PATH(NS(-(Q2E)->ND)+))) P
GROUP BY
	ColValue
ORDER BY
	GroupID
```
結果(解答)

| GroupID | ColValue |
|:-:|:-:|
| 1 | A |
| 1 | B |
| 1 | C |
| 1 | D |
| 1 | J |
| 1 | K |
| 2 | E |
| 2 | F |
| 2 | G |
| 2 | H |

#　終わりに
SHORTEST_PATH 関数は現時点では重み付きグラフでの最短経路には対応していないので、機能的には到達可能性用の関数と解釈したほうが適切である。ただ、この到達可能性の機能はSQL的に「サブシステムに投げて結果をウィンドウ関数の仕組みで取得する」形になっているので将来的には重み付きグラフの最短距離や最短経路にも対応するかもしれない。