08解説：SQLでエレガントにベクトル内積計算
CodeIQの設問「SQLでエレガントにベクトル内積計算」の解説を行います。
問題文
問１
下記のような要素4の縦ベクトルが２つあります。
U V [1 [1 3 2 5 3 7] 4]例えば、ベクトルUはリレーショナルデータベースの表として以下のように表現されます。
Uも同様に表現されます。row_id val_nr 1 1 2 3 3 5 4 7２つのベクトルUとVの内積はどのようにSQLクエリーで表現できるかを考え、内積U・Vを表すSQLクエリーをselect文で答えてください。
UとVの内積はUとVの表の結合として表せます。ただし、JOIN文は使いません。
内積の計算は以下の図式になります。
U.row_id=V.row_id=1の要素同士をかけて、次のU.row_id=V.row_id=2の要素同士をかけたものを順次足していくと行くという操作になります。U.row_id [1 3 5 7] [1 V.row_id 2 3 4] = 1×1 + 3×2 + 5×3 + 7×4SQLでの表の結合は表内のすべての要素の組み合わせを試して、結果を出力するので、何らかの条件統制が必要となります。
要素mの表と要素nの表の結合を行うとm×n個の要素が結果として出てしまいます。答えのSQLは以下のような形式になります。
select sum( ... ) from U, V where ... = ... ;計算結果は50となります。
答えのSQLを書き加えたvector.txtを送ってください。
問２ ステップ問題
以下のような行列Wがあります。
W = [[1 2 3 4] [5 6 7 8] [9 10 11 12]]この行列は表で以下のように表現できます。
row_id col_id val_nr 1 1 1 1 2 2 1 3 3 1 4 4 2 1 5 2 2 6 2 3 7 2 4 8 3 1 9 3 2 10 3 3 11 3 4 12この行列Wと前問のVの積を計算してください。その計算を実現するSQLを考えてください。
W V [[1 2 3 4] [1 [5 6 7 8] 2 [9 10 11 12]] 3 4]答えは各row_id毎の結果を求めてください。
計算結果は以下のような表になります。row_id sum 1 30 2 70 3 110Wの行列要素は(W.row_id, W.col_id)のように行と列に分かれてしまっているので、
何らかの条件統制が必要となります。
答えのrow_id=1の場合について考えてみましょう。
W.row_id=1という条件で絞れば、以下のようにベクトルの内積となります。W.col_id= 1 2 3 4 W.row_id=1 [1 2 3 4] [1 V.row_id=1 2 2 3 3 4] 4row_id=1の計算結果はW.col_idとV.row_idが一致する各W, Vの要素のかけたものの和となっています。計算結果のrow_idとW.row_idは同じものです。
各row_idについて計算結果が欲しいので、W.row_idでグルーピングすれば、各row_idについて計算することができます。解答のSQL文は以下の形式になります。
select W.row_id, sum( ... ) from W, V where ... = ... group by ... ;解答方法
計算結果の数値は必要ありません。データは確認用に使ってください。
添付ファイルはこちらからダウンロードしてください。vector.txtはpostgreSQLのスクリプトになっていますので、下記のように実行してください。
$ psql yourdb < vector.txt前半部分は表作成とデータのロードとなっています。
MySQLやOracle等他のデータベースをお使いの場合は適宜修正して、データを読み込んでください。発展問題
この問題ができた方は、次のレベルの問題がありますので、挑戦してみてください。
「SQLで行列積の計算???」
https://codeiq.jp/ace/kawagashira_nobuyuki/q379
解説
問1
答えは以下の通り。
select sum(U.val_nr * V.val_nr)
from U, V
where U.row_id = V.row_id;
Uの各要素をU(i)（iはrow_id）、Vの各要素をV(i)（iはrow_id）とすると、UとVのベクトル積は以下の式になる。要素数はnとする。
U・V = U(1) V(1) + U(2) V(2) + U(3) V(3) + … + U(n) V(n)
つまり、Uの各要素とVの各要素の和の形になっているので、求めるものはsum(U.val_nr * V.val_nr)となる。
ここで、ベクトル積の各項の添字iはrow_idで、UとVのrow_idが常に同じだから、U.row_id = V.row_idという制約条件をつける必要があります。
もし、ここで制約条件を付けないと、UとVの全要素の組み合わせが集計されてしまい、以下のような計算結果となってしまいます。
U(1) V(1) + U(1) V(2) + U(1) V(3) + … + U(1) V(n) +
U(2) V(1) + U(2) V(2) + U(2) V(3) + … + U(2) V(n) +
U(3) V(1) + U(3) V(2) + U(3) V(3) + … + U(3) V(n) +
...
U(n) V(1) + U(n) V(2) + U(n) V(3) + … + U(n) V(n)
問２ ステップ問題
答えは以下の通り。
select W.row_id, sum(W.val_nr * V.val_nr)
from W, V
where W.col_id = V.row_id
group by W.row_id;
計算結果の表をZとすると、計算結果の要素はZ(1), Z(2), Z(3),...,Z(m)となります。
mは計算結果の要素数で、W.row_idの列数です。
問題文にも書きましたが、計算結果Zの要素 row_id=k は、W(row_id=k)とVのベクトル積になるので、Z(row_id=k)についてSQL文を作成します。
Z(row_id=k) = W(k,1) V(1) + W(k,2) V(2) + W(k,3) V(3) + … + W(k,n) V(n)
計算の値はベクトル積なので、問１と同様に、sum(W.val_nr * V.val_n)となります。計算結果の要素番号、つまりrow_idを表示する必要があるので、W.row_idを要素番号としてselectの項目に付け足します。
Z(row_id=k)の和の各項はWのcol_idとVのrow_idが同じとなっているので、W.col_id = V.row_idという制約条件を付け加えます。
更に、row_id毎に掲載結果を集計する必要があるので、group by W.row_idというグループ句を付け加えます。
答えのSQLはシンプルですが、論理は結構複雑ですね。正しいSQL文が出来ましたでしょうか。
この問題ができた方は、行列積の計算にも挑戦してみてください。
「SQLで行列積の計算???」
