2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@KAZAMAI_NaruTo(NaruTo KAZAMAI)

SQL Server 2017 のGraph拡張を試してみた

2
Last updated at Posted at 2017-12-05

SQL Server 2017 には 「Graph 拡張」というのができている。

Graph Data Processing with SQL Server 2017 and Azure SQL Database

みたところこの記事(2017年4月)の時点では

  • node
  • edge

といった、特定のフィールドを予め持ったテーブルを作成できるだけというレベルだが。
今後の拡張には期待・・・だが、これ以上の機能があるとのは今のところ聞いていない。

SQL Server 2017 CTP のときに CodeIQ のとある問題で試してみた。
が、これは公開できない(まだ公開中の問題だし) ので別に問題を作って試してみることにする。

n × m で区切られた領域があり、それぞれには 0 から9までの「高さ」がある。
上下左右のみ移動可能で、
高さが同じならば 4分、高さが 1増えるならば7分、高さが1 減るならば 3分で移動できる。
左上から右下まで最短何分でいけるか。
ただし、たどり着く少なくとも経路は一つあるものとする。

なんかどっかで見かけた問題に似ていないこともないがこれで試してみよう。

まず、テーブルを作成する。

IF object_id('dbo.SAMPLE_N') IS NOT NULL BEGIN
    DROP TABLE dbo.SAMPLE_N
END

CREATE TABLE dbo.SAMPLE_N(
    X INT
    , Y INT
    , H INT
    , TT INT
    , constraint PK_SAMPLE_N PRIMARY KEY(
        $node_id)
    ) AS NODE

CREATE UNIQUE INDEX IDX_SAMPLE_N__XY ON SAMPLE_N(X,Y);

IF object_id('dbo.SAMPLE_E') IS NOT NULL BEGIN
    DROP TABLE dbo.SAMPLE_E
END

CREATE TABLE SAMPLE_E(
        W INT NOT NULL
            , constraint PK_SAMPLE_E PRIMARY KEY(
                $edge_id
            )
    ) AS EDGE

CREATE INDEX IDX_SAMPLE_E__F ON SAMPLE_E($from_id);

node のテーブルは

CREATE TABLE table_n (<テーブル定義>) as node

の形式で「as node」を付ける。すると自動的には「$node_id」の列名でアクセスできる列ができる。(ただし、実際の列名はローカル一時テーブルのテーブル名のときのように $node_id ではない。が、今後「$node_id列」と呼ぶ。)
この 「$node_id列」、特にキーとかにはなっていないので今回はこの「$node_id列」を主キーとする。
その他、各ノードは座標(X,Y) と高さ H、そして後で設定する所要時間(Travel Time) TT の列を持ち、座標には　Unique index を付けた。

edge のテーブルは

CREATE TABLE table_n (<テーブル定義>) as edge

の形式で「as edge」を付ける。すると自動的には「$edge_id」「$from_id」「$to_id」の列名でアクセスできる列ができる。(同じく、実際の列名は違うが「$edge_id列」「$from_id列」「$to_id列」と呼ぶ。)
主キーは 「$edge_id列」とし、「$from_id列」にも index を作成する。
Edge にはその経路を通る場合の重み(Weight) W の列を付けた。

テーブルはできたので次は最短距離を求める問題を作成する。

DECLARE @FIELD_W int = 10;
DECLARE @FIELD_H int = 5;

DECLARE @ix int = 0
DECLARE @iy int = 0
DECLARE @h int = 5
SET @iy = 0

SELECT RAND(5)
TRUNCATE TABLE SAMPLE_E
TRUNCATE TABLE SAMPLE_N

WHILE @iy < @FIELD_H BEGIN
    SET @ix = 0
    WHILE @ix < @FIELD_W BEGIN
        SELECT
            @h = 
                CASE
                        WHEN v < 0.4 AND @h >0
                            THEN @h - 1
                        WHEN v > 0.6 AND @h < 9
                            THEN @h + 1
                        ELSE @h
                    END
            FROM
                (VALUES(RAND())) AS R(v);
        INSERT INTO SAMPLE_N(X,Y,h)
            SELECT
                IIF(@iy % 2 = 0,@ix,@FIELD_W - @ix -1),@iy,
                @h;
        SET @ix += 1
    END
    SET @iy += 1
END

UPDATE SAMPLE_N
    SET TT = 0
    WHERE
        X = 0 AND Y = 0;

SELECT
    Y
    , STRING_AGG(CAST(h AS NVARCHAR(1)),'') WITHIN GROUP (ORDER BY X) AS MAP
FROM
    SAMPLE_N
GROUP BY
    Y
ORDER BY Y

高さ @FIELD_H, 幅 @FIELD_W とする。 左上を (0,0) 、右下を (@FIELD_W - 1, @FIELD_H - 1)として 「SELECT RAND(5)」で乱数系列を初期化。(同じ MAP を繰り返し作成するため。シード値を変えれば別のマップを作れ、コメントアウトすれば作るたびに変わる。) 乱数で高さを上げ下げしつつ 1行目は左から右、2行目は右から左、・・・と高さを設定する。 CTE では 100までしか再帰できないので T-SQL の While でループを回した。 出発点の (0.0) には所要時間 0 を設定。 最後に できた MAP を表示する。 STRING_AGG は SQL Server 2017 から追加された関数で、他の Database で言うところの GROUP_CONCAT() である。

これでできる MAP は次のようになる。

Y MAP
0 5567654343
1 6543223444
2 7899988789
3 5456567899
4 5455567787

さて、問題を解くにあたり、まず Edge を設定する。

TRUNCATE TABLE SAMPLE_E;

INSERT INTO SAMPLE_E
    SELECT
        NF.$node_id
        , NT.$node_id
        , CASE
                WHEN NF.H > NT.H THEN 3
                WHEN NF.H < NT.H THEN 7
                ELSE 4
            END AS W
    FROM
        SAMPLE_N NF
        , SAMPLE_N NT
    WHERE
        ABS(NF.H - NT.H) <= 1
        AND (
            (NF.X = NT.X AND ABS(NF.Y - NT.Y) = 1)
            OR (NF.Y = NT.Y AND ABS(NF.X - NT.X) = 1))

テーブルをクリア後、node テーブルを cross join し、

  • 高さの差が 1以下
  • （X が同じで Y の差が 1) または(Y が同じで X の差が 1)

の組み合わせに対して

  • 登りなら 7
  • 下りなら 3
  • それ以外は 4

の重みを設定して edgeテーブルに登録する。

で実際に解く。

DECLARE @UPDATED int =  1

WHILE @UPDATED > 0 BEGIN
    UPDATE NT
            SET NT.TT = NF.TT + E.W
        FROM
            SAMPLE_N NF
            , SAMPLE_E E
            , SAMPLE_N NT
        WHERE
            match (NF-(E)->NT)
            AND (NF.TT IS NOT NULL)
            AND ((NT.TT IS NULL)
                OR (NT.TT > NF.TT + E.W))
    SET @UPDATED = @@ROWCOUNT
    --SELECT @UPDATED
END

パワープレイ(爆)。
「edge の先の所要時間が設定されていないか、より短く成るなら所要時間を更新する」
というのを更新が無くなるまで繰り返す。
この「match」構文が graph database 専用らしい。

で結果表示。

SELECT 
        TT
    FROM
        SAMPLE_N N
        INNER JOIN (
            SELECT MAX(X) X,MAX(Y) Y FROM SAMPLE_N) M
        ON M.X = N.X AND M.Y = N.Y

SELECT
        Y
        , STRING_AGG(CAST(h AS NVARCHAR(1)),'-') WITHIN GROUP (ORDER BY X) AS MAP
        , STRING_AGG(CAST(tt AS NVARCHAR(4)),'-') WITHIN GROUP (ORDER BY X) AS TravelTime
    FROM
        SAMPLE_N
    GROUP BY
        Y
    ORDER BY Y

この問題の場合は所要時間 64分、
MAP の各地点までの所要時間は次のとおり

Y MAP TravelTime
0 5-5-6-7-6-5-4-3-4-3 0-4-11-18-21-24-27-30-37-40
1 6-5-4-3-2-2-3-4-4-4 7-8-11-14-17-21-28-35-39-43
2 7-8-9-9-9-8-8-7-8-9 14-21-28-32-36-39-43-46-53-60
3 5-4-5-6-5-6-7-8-9-9 72-65-62-59-52-49-46-53-60-64
4 5-4-5-5-5-6-7-7-8-7 74-67-64-60-56-53-50-54-61-64

とりあえず、特別な機能はわからないがやってみたということで。

ここからの転載です。

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?