FoRWaRD のバックアップ(No.4)
- バックアップ一覧
- 差分 を表示
- 現在との差分 を表示
- 現在との差分 - Visual を表示
- ソース を表示
- FoRWaRD へ行く。
- 1 (2021-05-23 (日) 10:48:40)
- 2 (2021-05-23 (日) 17:27:46)
- 3 (2021-05-26 (水) 08:21:08)
- 4 (2021-05-26 (水) 13:38:04)
RDBの行をベクトル化し、逐次的投入にも対応した仕組み。
以下の論文で提案。
CONTENTS
対象データベースの定義
\( 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 \) | |
\( R \)-fact, \( \sigma \)-factともいう | |
\( R(D) \) | \( f \in R(D) \) |
\( 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}] \)
このとき、walkは、
\( f_0, \dots ,f_\ell \)
ただし、
\( f_{k-1}(\mathbf{A}^{k-1})=f_k(\mathbf{B}^{k}) \)
ただし、距離0の場合は、\( f_0 \)
\( \mathcal{W}(f,s) \):事実\( f \)から始まるウォークスキーマ\( s \)のいてのウォークの集合
\( d_{f,s} \):個々のウォークの最終到達地
\( \mathrm{Pr}(d_{f,s}=g) \):&mathrm{g\inR^k(D)};で終わる確率
\( d_{f,s}[A] \):要素\( A \)を持つランダムウォークの到達地
リレーション\( R \)の事実\( f_0}で始まるウォークスキーマ\( s \)においては、\( s \)によって特定される外部キーに添って幅優先探索を行うことで、&mathjax{d_{f,s} \)の分布が計算できる。