0
1

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)

第13回 JSSUG 「みんなでプログラムを作ろう」問題２ の解答例(NaruTo版)

0
Posted at

初めに

2018年12月22日(土) に JSSUG 第13回勉強会で催されたハッカソンで出された3問のうちの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

NaruTo の解答例を書いておきます。
ここでは6通りの解を挙げているが、「なるべくループやカーソル処理を避けましょう」の条件に合致しているのは
JSSUG13_Q2_A04.sql と JSSUG13_Q2_A05.sql のみです。

逐次置き換えで解く

RELATION に含まれる値とそのグループを格納するためのテーブル変数 @V を用意する。
@v にはグループの初期値として値自信を格納する・

このテーブル変数に対し、各リレーションの二つの文字が属するグループを取得し、その二つのグループの文字の大きい方のグループをすべて文字の小さい方のグループに置き換えるというのを逐次行うことで解を得る。

JSSUG13_Q2_A01.sql
DECLARE @V TABLE 
    (ColVal CHAR(1) NOT NULL,
     GroupVal CHAR(1) NOT NULL
    );
INSERT INTO @v
		SELECT
			ColA, ColA
		FROM
			RELATION
		UNION
		SELECT
			ColB, ColB
		FROM
			RELATION VB

DECLARE cur CURSOR LOCAL STATIC
FOR
	SELECT
		ColA, ColB
	FROM
		RELATION
	WHERE
		ColA < ColB
	UNION
	SELECT
		ColB, ColA
	FROM
		RELATION
	WHERE
		ColB < ColA

;
DECLARE @l CHAR(1), @h CHAR(1)

OPEN cur
FETCH NEXT FROM cur INTO @l, @h

WHILE @@FETCH_STATUS = 0
BEGIN
	UPDATE @V
		SET GroupVal = (SELECT GroupVal FROM @V WHERE ColVal = @l)
	WHERE
		GroupVal = (SELECT GroupVal FROM @V WHERE ColVal = @h)

	FETCH NEXT FROM cur INTO @l, @h
END
CLOSE cur
DEALLOCATE cur

SELECT
	DENSE_RANK() OVER (ORDER BY GroupVal) GroupID
	, ColVal
FROM @V
ORDER BY
	ColVal

カーソルを使ってグループを逐次置き換える代わりに、全体の置き換えを置き換えがなくなるまで繰り返すことでも解を求められる。

JSSUG13_Q2_A02.sql
DECLARE @V TABLE 
    (ColVal CHAR(1) NOT NULL,
     GroupVal CHAR(1) NOT NULL
    );
INSERT INTO @v
		SELECT
			ColA, ColA
		FROM
			RELATION
		UNION
		SELECT
			ColB, ColB
		FROM
			RELATION VB
;
DECLARE @UPDATED INT = 1;

WHILE @UPDATED > 0
BEGIN
	WITH GMB(GroupA, GroupB) AS (
		SELECT
				vA.GroupVal AS GroupA
				, vB.GroupVal AS GroupB
			FROM
				@v vA
				INNER JOIN RELATION
				ON vA.ColVal = RELATION.ColA
				INNER JOIN @v vB
				ON vB.ColVal = RELATION.ColB)
		, GM (GroupL, GroupH) AS (
			SELECT
				MIN(GroupL) AS GroupL
				, GroupH
			FROM
				(
					SELECT
							GroupA AS GroupL
							, GroupB AS GroupH
						FROM
							GMB
						WHERE
							GroupA < GroupB
					UNION ALL
					SELECT
							GroupB AS GroupL
							, GroupA AS GroupH
						FROM
							GMB
						WHERE
							GroupB < GroupA) GMBR
			GROUP BY
				GroupH)
		UPDATE v
			SET
				GroupVal = GroupL
			FROM
				@v v
				INNER JOIN GM
				ON GroupVal = GroupH
;
	SET @UPDATED = @@ROWCOUNT
END

SELECT
	DENSE_RANK() OVER (ORDER BY GroupVal) GroupID
	, ColVal
FROM @V
ORDER BY
	ColVal

しかし、コーディング規則の「なるべくループやカーソル処理を避けましょう。」があるためあまり良くない。

有向グラフを用いて解く

有向グラフを用いて問題を解くには次のようにする。

  1. 頂点(Vertex) と辺(Edge) を求めて V×E の有向グラフを作成する。
  2. 各頂点から到達可能な頂点をすべて求める。
  3. 到達可能な頂点の中の最小値の Dense_Rank を求めることで各頂点の GroupID を求める。

　　RELATION から 頂点(Vertex)は次のようにして求める。

SELECT
        ColA as node
    FROM
        RELATION
UNION
SELECT
        COlB
    FROM
        RELATION

　　RELATION から 辺(Edge)は次のようにして求める。

SELECT
        ColA as fn
        , ColB as tn
    FROM
        RELATION
    WHERE
        ColA <> COlB
UNION
SELECT
        ColB as fn
        , ColA as tn
    FROM
        RELATION
    WHERE
        ColA <> COlB

各 RELATION に対し、”ColA から ColB” と "ColB から ColA" のそれぞれを登録する。
ただし、ColA と ColB が同じものは排除している。

　　各頂点の到達可能な頂点のリストを保持するテーブルを RA(fn, tn) とすると
各頂点の GroupID は次で求められる。（RA: ReachAble, fn: from node, tn: to node)

SELECT
        DENSE_RANK() OVER (ORDER BY MIN(tn)) AS GroupID
        , fn AS ColValue
    FROM
        RA
    GROUP BY
        fn
    ORDER BY
        fn
;

で求める結果を得られる。

したがって与えれえた問題は 有効グラフ V×E で 各頂点から到達可能な頂点のリストを作成する到達可能性の問題に帰着される。

繰り返しを利用した求め方

到達可能な頂点の組を繋げていき、新しい頂点の組み合わせが出なくなるまで繰り返すことですべての到達可能な頂点を挙げる、

JSSUG13_Q2_A03.sql
IF object_id('RA') IS NOT NULL
	DROP TABLE RA;
DECLARE @UPDATED int
;
WITH V(node) AS (
		SELECT node
		FROM
			(
				SELECT
						ColA as node
					FROM
						RELATION
				UNION
				SELECT
						COlB
					FROM
						RELATION) VX
		)
	,E(fn, tn) AS (
		SELECT
				ColA as fn
				, ColB as tn
			FROM
				RELATION
			WHERE
				ColA <> COlB
		UNION
		SELECT
				ColB as fn
				, ColA as tn
			FROM
				RELATION
			WHERE
				ColA <> COlB)
SELECT fn, tn 
		INTO RA
	FROM
		(
			SELECT
					node AS fn, node AS tn
				FROM
					V
				UNION
				SELECT
					fn, tn FROM E) RAI;

SET @UPDATED = @@ROWCOUNT
--PRINT @UPDATED

WHILE @UPDATED > 0
BEGIN
	INSERT INTO RA(fn, tn)
	SELECT
			RA1.fn, RA2.tn
		FROM
			RA AS RA1
			INNER JOIN RA RA2
			ON RA1.tn = RA2.fn
		WHERE
			NOT EXISTS (SELECT * FROM RA WHERE RA.fn = RA1.fn AND RA.tn =  RA2.tn)
	SET @UPDATED = @@ROWCOUNT
	--PRINT @UPDATED
END

--SELECT * FROM RA;

SELECT
        DENSE_RANK() OVER (ORDER BY MIN(tn)) AS GroupID
        , fn AS ColValue
    FROM
        RA
    GROUP BY
        fn
    ORDER BY
        fn
;

まぁ、こんな感じで特に難しいところはない。
しかし、問題文には「なるべくループやカーソル処理を避けましょう。」とあるのだった。

再帰CTE を利用した求め方

ループの代わりに再帰CTE を使えばできるかと思い、やってみた。
・・・が、これが苦労した。

再帰CTE では再帰部で
・再帰するテーブルは1度しか出現をゆるされない
・GROUP BY、集合関数は使えない
・外部結合も使えない。
等々、様々な制限がある。

したがって、繰り返しで使用したような自己結合も使えず、
辺(Edge) を継ぎ足していくにしても終了条件を設定するのが難しい。

そのため、次のような手法を用いた。

・距離を導入し、自分自身へは 0、辺を経由するごとに 1大きくなるようにする。
・到達可能なすべての頂点に到達することが保証される距離までの範囲で辺を継ぎ足す。
・到達可能な頂点が多重に挙げられる冗長性を許容する。(ただし、可能な範囲で冗長性を抑える)

「到達可能なすべての頂点に到達することが保証される距離」を満たすものとして
もっとも簡便なものは

{頂点の数} - 1

である。但し、可能ならばこの値はできるだけ小さくしたい。

ここで次のような性質が成立する。

”E で A を始点、B を終点とする辺が存在するなら B を始点、A を終点とする辺が存在する”なら
ある頂点 A を始点とする終点の数が 2以上の n の場合、すべての到達可能な頂点は

{頂点の数} - 1 - (n - 2) 以下

で到達可能である。特に n の最大値 max(n) が 2以上の場合、

{頂点の数} - 1 - (max(n) - 2)、つまり {頂点の数} - max(n) + 1 以下

で到達可能である。
また、 max(n) <= 1 の場合、自分自身以外に到達可能な頂点が 1個以下になるため、
すべての到達可能な頂点に距離1以下で到達可能である。

これを求める SQL は V(node) を頂点、E(fn,tn) を辺とした場合に次のようになる。

JSSUG13_Q2_A04.sql
SELECT
            iif(max(ntn) < 2, 1
	            , (SELECT COUNT(*) as n FROM V) - max(ntn) + 1)  as n
        FROM
            (
                SELECT count(*) AS ntn
                        FROM E
                        GROUP BY
                            fn) mntn

これを利用し、次のような SQL で問題を解く

WITH V AS (
		SELECT ColA as node FROM RELATION
		UNION
		SELECT ColB FROM RELATION)
	, E AS (
		SELECT ColA as fn, ColB as tn FROM RELATION
			WHERE ColA <> ColB
		UNION
		SELECT ColB, ColA FROM RELATION
			WHERE ColA <> ColB)
	, MAXD AS (
		SELECT
			iif(max(ntn) < 2, 1
				, (SELECT COUNT(*) as n FROM V) - max(ntn) + 1)  as n
		FROM
			(
				SELECT count(*) AS ntn
						FROM E
						GROUP BY
							fn) mntn)
	, RA AS (
		(
			(SELECT node as fn, node as tn , 0 as d FROM V)
			UNION
			(SELECT fn, tn , 1 as d FROM E)
		)
		UNION ALL (
			SELECT
				RA.fn, E.tn, d + 1 AS d
			FROM
				RA
				INNER JOIN E
				ON RA.tn = E.fn
					AND RA.fn <> E.tn
			WHERE
				d > 0
				AND d + 1 <= (SELECT n FROM MAXD)
		)
	)
SELECT
		DENSE_RANK() OVER (ORDER BY min(tn)) AS GroupID
		, fn AS ColValue
	FROM RA
	GROUP BY
		fn
	ORDER BY
		fn

RA と E との JOIN の条件に AND RA.fn <> E.tn を加えることで些細ながら冗長性を抑えている。

通過点マップを利用して解く

有向グラフの再帰CTE が距離で抑えないといけないと無限に再帰を繰り返して再帰回数の上限に達するが、これは一度通った経路に再度戻るためである。
そこで途中の通過点の情報を保持させる方法を検討した。
通過点の情報を持つ「通過点マップ」は次のようにして作る。
各頂点に 2のべき乗になる nodeid を付ける。

SELECT POWER(2,ROW_NUMBER() OVER (ORDER BY node) - 1) AS nodeid, node
		FROM
			(
				SELECT ColA as node FROM RELATION
				UNION
				SELECT ColB FROM RELATION)VBASE

通過点した点は nodeid の論理和(OR) で表現する。

こうした場合、論理積(AND) が 0 より大きい二つの通過点マップに含まれるすべての頂点は互いに到達可能になるから
その二つの通過点マップの論理和(OR) を新しい通過点マップにできる。
・・・その場合、辺はいらず、通過点マップだけで済むやん。
そして到達可能なすべての頂点を含む通過点マップができるとそれ以上は増えなくなる。

先の nodeid を含む頂点のテーブルを V(nodeid,node) とすると
RELATION を通過点マップに変換するには次のようにする。

SELECT DISTINCT TV.nodeid | FV.nodeid as m
		FROM
			RELATION
				INNER JOIN V TV
				ON RELATION.ColB = TV.node
				INNER JOIN V FV
				ON RELATION.ColA = FV.node)

これらを元に問題を解くSQL を作ると次のようになる。

JSSUG13_Q2_A05.sql
WITH V AS (
        SELECT POWER(2,ROW_NUMBER() OVER (ORDER BY node) - 1) AS nodeid, node
        FROM
            (
                SELECT ColA as node FROM RELATION
                UNION
                SELECT ColB FROM RELATION)VBASE)
    , BM AS (
        SELECT DISTINCT TV.nodeid | FV.nodeid as m
        FROM
            RELATION
                INNER JOIN V TV
                ON RELATION.ColB = TV.node
                INNER JOIN V FV
                ON RELATION.ColA = FV.node)
    , M AS (
        SELECT m FROM BM
        UNION ALL
        SELECT
            M.m | BM.m
        FROM
            M
            INNER JOIN BM
            ON (M.m & BM.m) > 0
                AND (M.m | BM.m) > M.m)
    , GBASE AS (
        SELECT
            node, MAX(m) AS m
        FROM
            (SELECT DISTINCT m FROM M) M
            INNER JOIN V
            ON M & V.nodeid > 0
        GROUP BY
            node)
SELECT
        GroupID, node AS ColValue
    FROM
        GBASE
        INNER JOIN (
            SELECT
                    DENSE_RANK() OVER (ORDER BY MIN(node)) AS GroupID, m
                FROM
                    GBASE
                GROUP BY
                        m) G
        ON GBASE.m = G.m
    ORDER BY
        node
;
  • V が頂点のテーブル
  • BM がRELATION から作った通過点マップ
  • M が 再帰CTE で BM をそれ以上広がらなくなるまで結合した通過点マップ
  • GBASE が M から頂点毎にその頂点を含む最大の通過点map をとりだしたもの

である。

なお、M で多量の冗長な列を生成するため、処理に結構時間がかかる。
RELATION を始点ごとに論理和を取ってマップにするなどすれば効率化を図ることができる。

なお、繰り返しを用いるならば 通過点マップ用のテーブル自体を事項結合し、また他に包含される通過点マップを都度除外することができる。

JSSUG13_Q2_A06.sql
DECLARE @v TABLE 
    (nodeid int NOT NULL,
     node CHAR(1) NOT NULL
    );

INSERT INTO @v
		SELECT POWER(2,ROW_NUMBER() OVER (ORDER BY node) - 1) AS nodeid, node
		FROM
			(
				SELECT ColA as node FROM RELATION
				UNION
				SELECT ColB FROM RELATION)VBASE

DECLARE @m TABLE
	(m int NOT NULL PRIMARY KEY)
;

INSERT INTO @m
	SELECT DISTINCT TV.nodeid | FV.nodeid as m
		FROM
			RELATION
				INNER JOIN @v TV
				ON RELATION.ColB = TV.node
				INNER JOIN @v FV
				ON RELATION.ColA = FV.node
;

DECLARE @updated int = 1

WHILE @updated > 0
BEGIN
	INSERT INTO @m
	SELECT DISTINCT
			M1.m | M2.m
		FROM
			@m M1
			INNER JOIN @m M2
			ON (M1.m & M2.m) >0
				AND M1.m > M2.m
				AND (M1.m | M2.m) > M1.m
		WHERE
			NOT EXISTS (
				SELECT m FROM @m WHERE (m | M1.m | M2.m) = m)
	SET @updated = @@ROWCOUNT

	DELETE FROM M
		FROM @m M
		WHERE
			EXISTS (
				SELECT m FROM @m M2 WHERE M2.m > M.m AND (M2.m | M.m) = M2.m)
END

SELECT
		GroupID, node AS ColValue
	FROM
		@v V
		INNER JOIN (
			SELECT
					DENSE_RANK() OVER (ORDER BY MIN(node)) AS GroupID, m
				FROM
					@m
					INNER JOIN @v
					ON (m & nodeid) > 0
				GROUP BY
						m) G
		ON V.nodeid & G.m > 0
	ORDER BY
		node
0
1
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
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?