FoRWaRD のバックアップ(No.3)

RDBの行をベクトル化し、逐次的投入にも対応した仕組み。
以下の論文で提案。

対象データベースの定義

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

問題定義

静的DB埋め込み (Static database embedding)
スキーマ\( \sigma \)を持つデータベース\( D \)に対し、
埋め込み関数\( \gamma:D \to \mathbb{R}^k \)を作る。
ただし、ハイパーパラメータ\( k>0 \)
動的DB埋め込み (Dynamic database embedding)
\( \gamma \)を新たな事実\( f \notin D \)に拡張する。
\( \gamma^\prime:D \cup \{f\} \to \mathbb{R}^k \)
ただし、元の値は変更しない。
つまり、\( f^\prime \in D \)に対し\( \gamma^\prime(f^\prime)=\gamma(f^\prime) \)

DB上のランダムウォークの手法

外部キー制約を用いてリレーション間をたどる。
\( R_k[\mathbf{A}^k] \subseteq R_{k+1}[\mathbf{B}^{k+1}] \)または\( R_{k+1}[\mathbf{B}^{k+1}] \subseteq R_k[\mathbf{A}^k] \ \)といった外部キー制約があるとき、\( R_k[\mathbf{A}^k] - R_{k+1}[\mathbf{B}^{k+1}] \)とたどれる。

このとき、距離\( \ell \)のランダムウォークの経路\( s \)は、下にようになる。
\( 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}] \)