FoRWaRD のバックアップ差分(No.4)

  • 追加された行はこの色です。
  • 削除された行はこの色です。
RDBの行をベクトル化し、逐次的投入にも対応した仕組み。
以下の論文で提案。
-[[Dynamic Database Embeddings with FoRWaRD&BR;11 Mar 2021  ·  Jan Toenshoff, Neta Friedman, Martin Grohe, Benny Kimelfeld:https://cs.paperswithcode.com/paper/dynamic-database-embeddings-with-forward]]

#CONTENTS

**対象データベースの定義 [#q02d78ff]
|&mathjax{D};|データベース|
|&mathjax{\sigma};|データベーススキーマ（定義全体）|
|&mathjax{R,S};|個々のリレーション名|
|&mathjax{R(A_1 \dots A_k)};|リレーションスキーマの集合|
|&mathjax{A_i};|&mathjax{\sigma};の要素名 (attribute name)|
|&mathjax{\mathbf{A},\mathbf{B},\mathbf{C}};|要素名の集合|
|~|&mathjax{\mathbf{B}=B_1 \dots B_\ell};|
|&mathjax{R.A};|&mathjax{\sigma};の要素(attribute)|
|&mathjax{\mathrm{dom}(R.A)};|&mathjax{R.A};の値域(domain)|
|&mathjax{\mathrm{key}(R)};|&mathjax{R};のキー|
|~|&mathjax{\mathrm{key}(R) \subseteq R(A_1 \dots A_k)};|
|~|空集合であることが可能|
----
:外部キー制約|&mathjax{R[\mathbf{B}] \subseteq S[\mathbf{C}]};
&mathjax{\mathrm{key}(S)  = S[\mathbf{C}]};
----
|&mathjax{f=R(a_1 \dots a_k)};|行（事実の集合）|
|~|&mathjax{a_i \in \mathrm{dom}(R.A_i)};|
|~|空値 (null value) の場合、&mathjax{\bot};|
|~|&mathjax{R};-fact, &mathjax{\sigma};-factともいう|
|&mathjax{R(D)};|&mathjax{f \in R(D)};|
|&mathjax{f[A_i]};|&mathjax{a_i};の値|
|&mathjax{f[\mathbf{B}]};|&mathjax{f[\mathbf{B}]=f[B_1],\dots,f[B_\ell]};|

**問題定義 [#f01f83f1]
:静的DB埋め込み (Static database embedding)|スキーマ&mathjax{\sigma};を持つデータベース&mathjax{D};に対し、
埋め込み関数&mathjax{\gamma:D \to \mathbb{R}^k};を作る。
ただし、ハイパーパラメータ&mathjax{k>0};

:動的DB埋め込み (Dynamic database embedding)|&mathjax{\gamma};を新たな事実&mathjax{f \notin D};に拡張する。
&mathjax{\gamma^\prime:D \cup \{f\} \to \mathbb{R}^k};
ただし、元の値は変更しない。
つまり、&mathjax{f^\prime \in D};に対し&mathjax{\gamma^\prime(f^\prime)=\gamma(f^\prime)};

**DB上のランダムウォークの手法 [#c0143c10]
~外部キー制約を用いてリレーション間をたどる。
&mathjax{R_k[\mathbf{A}^k] \subseteq R_{k+1}[\mathbf{B}^{k+1}]};または&mathjax{ R_{k+1}[\mathbf{B}^{k+1}] \subseteq R_k[\mathbf{A}^k] \};といった外部キー制約があるとき、&mathjax{R_k[\mathbf{A}^k] - R_{k+1}[\mathbf{B}^{k+1}]};とたどれる。

このとき、距離&mathjax{\ell};のランダムウォークの経路&mathjax{s};は、下にようになる。
このとき、距離&mathjax{\ell};のランダムウォークは、下にような経路&mathjax{s};になる。
&mathjax{R_0[\mathbf{A}^0] - R_{1}[\mathbf{B}^{1}],R_1[\mathbf{A}^1] - R_{2}[\mathbf{B}^{2}],\dots,R_{\ell-1}[\mathbf{A}^{\ell-1}] - R_{\ell}[\mathbf{B}^{\ell}]};

このとき、walkは、
&mathjax{f_0, \dots ,f_\ell};
ただし、
&mathjax{f_{k-1}(\mathbf{A}^{k-1})=f_k(\mathbf{B}^{k})};

ただし、距離0の場合は、&mathjax{f_0};

&mathjax{\mathcal{W}(f,s)};：事実&mathjax{f};から始まるウォークスキーマ&mathjax{s};のいてのウォークの集合
&mathjax{d_{f,s}};：個々のウォークの最終到達地
&mathjax{\mathrm{Pr}(d_{f,s}=g)};：&mathrm{g\inR^k(D)};で終わる確率
&mathjax{d_{f,s}[A]};：要素&mathjax{A};を持つランダムウォークの到達地

リレーション&mathjax{R};の事実&mathjax{f_0}で始まるウォークスキーマ&mathjax{s};においては、&mathjax{s};によって特定される外部キーに添って幅優先探索を行うことで、&mathjax{d_{f,s}};の分布が計算できる。