初めに
SQL Server の Graph Database は SQL Server 2016 から実装されている。
・・・が正直言ってSQL Server 2017 までは RDB と特に差が見受けられない状態だった。
SQL Server 2017 のGraph拡張を試してみた
ところが、2019年10月に行われた JSSUG の SQL Server 勉強会に於いて
Graph Database のセッションがあり、そこで到達可能性について実装されたことを知った。
早速この機能を試す。
第13回 JSSUG 「T-SQLでプログラムを作ろう」問題２
2018年12月の JSSUG の 第13回 SQL Server 勉強会に於いて「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 勉強会 で柳さんが解説をしており、また僕も改めて解いている
しかし、この問題、まさにグラフ の到達可能性の問題である。
そこでこの問題を SQL Server 2019 の Graph Database の到達可能性を試す題材とする。
試してみる
次の手順で試す。
1. 問題用のテーブルを作成する
2. サンプル用・問題用・テスト用のデータを用意する
3. 解答用の Graph DB のテーブルを作成する
4. 問題用のテーブルのデータから Graph DB用のデータを作成する
5. 結果を出力するクエリを作る。
問題用のテーブルを作成する
とりあえず、問題用のテーブル
CREATE TABLE RELATION(
ColA NVARCHAR(1)
, ColB NVARCHAR(1));
サンプル用・問題用・テスト用のデータを用意する
サンプル用
サンプル用のデータ。TRUNCATE文を加えてデータを入れ替えられるようにしている。
TRUNCATE TABLE RELATION;
INSERT INTO RELATION
VALUES('A','B'),('B','C'),('D','E');
SELECT * FROM RELATION;
問題用
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 が長いものを含む場合を用意する。
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 を指定するものである。
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 を出している。
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() を用いる。
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的に「サブシステムに投げて結果をウィンドウ関数の仕組みで取得する」形になっているので将来的には重み付きグラフの最短距離や最短経路にも対応するかもしれない。