「データベース:: テーブル構造とデータベース構造」において：
関係データベースは、テーブルのあいだの参照（外部キー）メカニズムを持っています。システムが組み込みで持っているメカニズムを、数理モデルに取り込まないわけにはいかないので、参照はデータベース構造の一部になります。
というわけで、この記事では、データベース内のテーブルのあいだの参照について定式化します。
一連のデータベースに関する記事のハブ記事（リンク集がある記事）は「データベース:: テーブルのキーって何なのよ？」です。その他の記事はハブ記事からたどれます。$`\newcommand{\n}[1]{\mathsf{#1}}
\newcommand{\bs}[1]{\boldsymbol{#1}}
\newcommand{\mrm}[1]{\mathrm{#1}}
\newcommand{\hyp}{\text{－} }
\newcommand{\Iff}{\Leftrightarrow }
\newcommand{\Imp}{ \Rightarrow }
\newcommand{\id}{ \mathrm{id} }
\newcommand{\For}{\text{For } }
`$
内容：
シリーズ・ハブ記事：
前提のおさらい
ドメイン〈ASPDT | Application Specific Primitive Data-Type〉の集合 $`\mathscr{D}`$ は前もって決まっているとします。$`\mathscr{D}`$ は集合の有限集合なので、$`D\ \in \mathscr{D}`$ と書いたら $`D`$ は集合〈基本データ型〉です。データベース分野では、基本データ型を「ドメイン」と呼びます。ドメイン〈基本データ型 | ASPDT〉を、システム組み込みドメインとユーザー定義ドメインに分けることもありますが、ここでは区別なしに扱います。
データベースはテーブルの集まりです。とあるデータベースに所属するテーブルの名前または番号の集合を $`I`$ とします。無限個のテーブルは実現できないので $`I`$ は有限集合です。$`i\in I`$ ごとにテーブル構造が定まるので、それを次のように書きます。
$`\quad \bs{t}_i = (C_i, S_i, \Gamma_i)`$
この書き方の意味は「データベース:: テーブル構造とデータベース構造」を見てください。
テーブル構造 $`\bs{t}_i`$ のテーブルスキーマは $`(C_i, S_i)`$ ですが、この書き方は冗長なので、スキーマを単に $`S_i`$ と書いても同じことです。（以下の $`\mrm{dom}`$ は写像の域のこと。）
$`\quad S_i : C_i \to \mathscr{D}\\
\text{i.e.}\\
\quad C_i = \mrm{dom}(S_i)
`$
テーブル構造、特にテーブルクラス $`\Gamma_i`$ から、テーブルの超キー〈superkey〉の集合と候補キー〈candidate key〉の集合は決まるので、それらを次のように書きます。
$`\quad \mrm{SKey}(\bs{t}_i)\\
\quad \mrm{CKey}(\bs{t}_i)
`$
主キーは原則的に使いません。実用上は主キーは重要ですが、候補キーの集合から主キーをひとつ選ぶ根拠がないからです。
「カラム」の用法
$`i \in I`$ で識別されるテーブル構造のカラム名の集合は $`C_i`$ です。カラム名の集合 $`C_i`$ の部分集合を $`X, Y`$ などで表してきましたが、以下、$`C_i`$ の部分集合を「カラム〈column〉」と呼びます。
データベースに限らず、多義曖昧語／同義語の錯綜がコミュニケーションや学習の障害となります。なので、多義曖昧語は使いたくはないのですが、$`C_i`$ の部分集合は頻出するので、短い名前「カラム」で呼びます。念のため、同義語・類義語を列挙しておきます。
- カラム名： 集合 $`C_i`$ の要素
- カラム関数： カラム名 $`c\in C_i`$ に対して決まる関数〈写像〉 $`\pi_c : \mrm{Tuple}(S_i) \to S_i(c)`$ 。
- カラム： 集合 $`C_i`$ の部分集合。正確に言いたいときは複合カラム名〈multicolumn name〉
テーブルの超キーや候補キーは、今定義した意味でのカラム〈複合カラム名〉になります。単一のカラム名 $`c \in C_i`$ と単元部分集合であるカラム〈複合カラム名〉 $`\{c\} \subseteq C_i`$ を区別しなくてはならない場面はあまりないので、単一のカラム名 $`c`$ と、単元集合である複合カラム名 $`\{c\}`$ をイチイチ区別しない方針とします。
カラム〈複合カラム名（単一カラム名を含む）〉 $`X \subseteq C_i`$ に対して、その射影関数が決まります。
$`\quad \pi_X : \mrm{Tuple}(S_i) \to \mrm{Tuple}(S_i|_X)`$
すぐ上で出てきた記号は「データベース:: テーブルのキーって何なのよ？」で説明しています。「データベース:: テーブル構造とデータベース構造」では、簡潔な略記を導入しています。
$`\quad \pi_X : \widehat{S_i} \to \widehat{S_i}[X]`$
$`X = \{c\}`$ の射影関数は、カラム名 $`c`$ のカラム関数と同一視してかまいません。
$`\quad \pi_{\{c\}} : \widehat{S_i} \to \widehat{S_i}[\{c\}] \cong S_i(c)`$
参照カラム
今まで、カラム〈複合カラム名（単一カラム名を含む）〉には、データ型としてドメインまたは幾つかのドメインの直積が割り当てられていました。カラムに特別な意味〈セマンティクス〉は与えていません。
ここでは、あるテーブルの特定のカラム $`X \subseteq C_i`$ が、他のテーブルまたは自テーブルのタプルを参照する状況を考えます。参照に使われるカラム〈複合カラム名〉を参照カラム〈reference column〉または外部キー〈foreign key〉と呼びます。
カラム $`X \subseteq C_i`$ が参照カラムであることを指定するには、次の追加情報が必要です。
- 参照先のテーブル構造の名前 $`j \in I`$
- 参照先のテーブル構造の超キーのひとつ $`Y \in \mrm{SKey}(\bs{t}_j)`$
- 集合としての $`X`$ と $`Y`$ のあいだの全単射写像〈双射写像〉 $`r:X \to Y`$
念のため $`i, X`$ も含めておけば、次の5つ組が参照カラムの仕様となります。（以下の $`\mrm{BijMap}(\hyp, \hyp)`$ は全単射写像〈双射写像〉の集合を表します。）
$`\quad (i, X, j, Y, r)\\
\text{where}\\
\quad i \in I\\
\quad X \subseteq C_i\\
\quad j \in I\\
\quad Y \in \mrm{SKey}(\bs{t}_j)\\
\quad r \in \mrm{BijMap}(X, Y)
`$
参照カラムの5つ組仕様のことも、参照カラム、あるいは単に参照と呼びます。
参照カラムを許すと、テーブルスキーマは単にドメインの割り当て $`S_i:C_i \to \mathscr{D}`$ だけでは済まなくなり、参照カラム〈外部キー〉の仕様の集合（空かも知れないが）を追加する必要があります。
参照を持つデータベースの妥当性
テーブルやデータベースが望ましく正しい状態であることを、妥当である〈valid〉とか整合している〈consitent | 一貫している〉といいます。データベースの議論では、妥当性／整合性の記述とチェックをどうするか？ に多くの時間が費やされます。
個々のテーブルの整合性は、テーブル構造 $`(C_i, S_i, \Gamma_i)`$ が持つテーブルクラス $`\Gamma_i`$ で記述されます。データベースを構成するすべてのテーブルの状態が、個別に妥当だったとしても、データベース全体として妥当だとは限りません。テーブル単独で見ても判断できない妥当性〈整合性 | 一貫性〉があります。
参照を持つデータベースでは、複数のテーブルが関与する妥当性が現れます。参照の妥当性です。以下の状況で考えましょう。
- テーブル $`i`$ が、参照カラム $`(i, X, j, Y, r)`$ を持つ。
参照があると、個別に妥当なテーブルインスタンス〈テーブル状態〉のペア $`(T_i, T_j)`$ が妥当とは限りません。
まず、テーブル $`\bs{t}_i`$ のスキーマ $`S_i`$ と、テーブル $`\bs{t}_j`$ のスキーマ $`S_j`$ のあいだに次の関係が要求されます。（'$`;`$' は、写像の図式順結合記号。）
$`\quad S_i|_X = r ; S_j \;: X \to \mathscr{D}`$
ここでの縦棒（'$`|`$'）は写像の域の制限のことです。
もっと詳細に書けば：
$`\quad \forall c\in X.(\, S_i(c) = S_j(r(c)) \;\in \mathscr{D} \,)`$
これが成立していれば、タプルの集合のあいだに全単射が作れます。つまり、次のような集合の同型が在ります。
$`\quad \mrm{Tuple}(S_i|_X) \cong \mrm{Tuple}(S_j|_Y)`$
簡潔に書けば：
$`\quad \widehat{S_i}[X] \cong \widehat{S_j}[Y]`$
この同型を与える写像を $`r^*`$ とすると、次のように $`r^*`$ を具体的に書けます。
$`\quad r^* : \widehat{S_j}[Y] \to \widehat{S_i}[X]\\
\quad r^* := \lambda\, t\in \widehat{S_j}[Y].\, r; t
`$
写像 $`r^*`$ の方向を逆にしたのは、$`r^*`$ の定義が簡単になるからです。タプルを写像とみなしていることがこの定義のミソです。
$`\quad t \in \widehat{S_j}[Y] \Iff t \in \prod_{c \in Y} S_j(c)\\
\quad \prod_{c \in Y} S_j(c) \subseteq \mrm{Map}(Y, \sum_{c\in Y} S_j(c))
`$
$`r`$ が可逆なので、$`r^*`$ の逆写像も作れます。
$`\quad (r^*)^{-1} = (r^{-1})^* \;: \widehat{S_i}[X] \to \widehat{S_j}[Y]`$
$`(r^*)^{-1}`$ はちょっと鬱陶しいので、$`\widehat{r}`$ と略記します（ハット使いすぎかも知れない）。
$`\quad \widehat{r} = (r^{-1})^* \;: \widehat{S_i}[X] \to \widehat{S_j}[Y]`$
$`\widehat{r}`$ を使って、テーブルインスタンス $`T_i \in \Gamma_i`$ から $`T_j \in \Gamma_j`$ への写像も構成できます。次のような写像を組み合わせて、点線疑問符の写像を作ります（ただし、後述の条件が必要）。
$`\xymatrix{
T_i \ar@{^{(}->}[d] \ar@{..>}[r]^{?}
& T_j \ar@{^{(}->}[d]
\\
\widehat{S_i} \ar[d]_{\pi_X}
& \widehat{S_j} \ar[d]_{\pi_Y}
\\
\widehat{S_j}[X] \ar[r]^{ \widehat{r} }
& \widehat{S_j}[Y]
}`$
参照に関する妥当性〈整合性 | 一貫性〉の制約条件をより具体的に書き下すのは次節以降にします。
超キー／候補キー再論
データベースのテーブル構造 $`(C_i, S_i, \Gamma_i)`$ のカラム〈複合カラム名〉 $`X \subseteq C_i`$ が超キー〈superkey〉であることは次のように書けるのでした（「データベース:: テーブルのキーって何なのよ？」参照）。
$`\quad \forall T \in \Gamma_i. \forall t,t'\in T.\,
\pi_X(t) = \pi_X(t) \Imp t = t'
`$
この条件は次のように書き換えられます。
$`\quad \forall T \in \Gamma_i.(\, \pi_X|_T \text{ は単射} \,)
`$
注意すべきは； 射影 $`\pi_X`$ が単射と言っているのではなくて、射影の制限 $`\pi_X|_T`$ が単射だと言っていることです。
単射であることは、部分集合 $`\pi_X(T)`$ （テーブルインスタンス $`T`$ の射影による像）上で定義された逆写像が存在することです。その部分的な逆写像を $`\kappa_T`$ としましょう。部分的な逆写像は、一意的に存在するので、単射である条件は次のように書けます。
$`\quad \forall T \in \Gamma_i.\\
\qquad \exists! \kappa_T \in \mrm{Map}(\pi_X(T), T).\, \kappa_T ; (\pi_X|_T) = \id_{\pi_X(T)} \land (\pi_X|_T) ; \kappa_T = \id_T
`$
'$`\exists!`$' は「一意的に存在する」の意味ですが、一意性は後から証明できる事なので、単に '$`\exists`$' でもかまいません。
この条件から定義される $`(\kappa_T)_{T\in \Gamma_i}`$ は、$`\bs{t}_i`$ の妥当なテーブルインスタンス達でインデックス付けられた写像の族〈ファミリー〉です。明示的に述べられる事はあまりないようですが、これらの写像達は、張り合わせて拡張することにより、単一の部分写像 $`\kappa_X`$ に出来ると仮定します。
$`\quad \kappa_X : \widehat{S_i}[X] \supseteq\!\to \widehat{S_i}`$
$`\kappa_X`$ は次の性質を持ちます。以下の $`\id`$ は、$`\id`$ を制限した部分写像のことです（面倒なのでオーバロード）。
$`\quad \kappa_X ; \pi_X = \id_{\widehat{S_i}[X]} \;: \widehat{S_i}[X] \supseteq\!\to \widehat{S_i}[X]\\
\:\\
\quad \forall T \in \Gamma_i.\\
\qquad (\kappa_X|_{\pi_X(T)}) ; (\pi_X|_T) = \id_{\pi_X(T)} \land (\pi_X|_T) ; (\kappa_X|_{\pi_X(T)}) = \id_T
`$
$`\kappa_X`$ を、超キー $`X`$ のキーセクション関数〈key section function〉と呼ぶことにします。射影に対する「セクション」はよく使われる言葉です。結局、カラム $`X`$ が超キーであることは、射影 $`\pi_X`$ に対するキーセクション関数 $`\kappa_X`$ を持つことだ、と言えます。
射影 $`\pi_X`$ とキーセクション $`\kappa_X`$ は互いに逆とは限りませんが、妥当なテーブルインスタンス $`T \in \Gamma_i`$ に制限すれば互いに逆 $`T \leftrightarrow \pi_X(T)`$ となります。
候補キーは超キーの特別なものなので、もちろんキーセクション関数を持ちます。
参照制約条件
前々節の最後の図式に、超キーのキーセクション関数を描き足すと次のようになります。キーセクション関数 $`\kappa_Y`$ は実際は部分写像です。
$`\xymatrix{
T_i \ar@{^{(}->}[d] \ar@{..>}[r]^{?}
& T_j \ar@{^{(}->}[d]
\\
\widehat{S_i} \ar[d]_{\pi_X}
& \widehat{S_j} \ar[d]_{\pi_Y}
\\
\widehat{S_j}[X] \ar[r]^{ \widehat{r} }
& \widehat{S_j}[Y] \ar@/_1.2pc/[u]_{\kappa_Y}
}`$
左上から右下にいたる写像のパスを結合〈compose〉してひとつにまとめると次のようになります。
$`\xymatrix@C+1.5pc{
T_i \ar[ddr]_{ (\pi_X ; \widehat{r} )|_{T_i} } \ar@{..>}[r]^{?}
& T_j \ar@{^{(}->}[d]
\\
{}
& \widehat{S_j} \ar[d]_{\pi_Y}
\\
{}
& \widehat{S_j}[Y] \ar@/_1.2pc/[u]_{\kappa_Y}
}`$
このままでは、右の縦方向を下から上に昇ることはできません。次の形になればOKです。
$`\xymatrix@C+1.5pc{
T_i \ar[ddr]_{(\pi_X ; \widehat{r} )|_{T_i} } \ar@{..>}[r]^{?}
& T_j \ar[dd]_{\pi_Y|_{T_j}}
\\
{}
& {}
\\
{}
& \pi_Y(T_j) \ar@/_1.2pc/[uu]_{\kappa_Y|_{\pi_Y(T_j)}}
}`$
この状況では、疑問符点線部分は、次のような写像になります。
$`\quad (\pi_X ; \widehat{r} )|_{T_i} ; (\kappa_Y|_{\pi_Y(T_j)} )
\;: T_i \to T_j
`$
写像の域を制限する縦棒が煩雑なので省略してしまえば：
$`\quad \pi_X ; \widehat{r} ; \kappa_Y
\;: T_i \to T_j
`$
この写像が定義可能な条件は：
$`\quad (\pi_X ; \widehat{r})(T_i) \subseteq \pi_Y(T_j)`$
同じことをタプルを使って書けば：
$`\quad \forall t \in T_i. \exists t' \in T_j .\,
\widehat{r}(\pi_X(t)) = \pi_Y(t')
`$
この条件は、ペア $`(T_i, T_j)`$ に対する条件です。つまり、勝手なペア $`(T_i, T_j) \in \Gamma_i\times \Gamma_j`$ だと参照がうまくいかないかも知れないので、参照がうまくいくようなペアを選び出す条件になっています。したがって、参照がうまくいくペアの集合は次のように書けます。
$`\quad \{ (T_i, T_j) \in \Gamma_i\times \Gamma_j \mid
(\pi_X ; \widehat{r})(T_i) \subseteq \pi_Y(T_j)
\}`$
参照 $`(i, X, j, Y, r)`$ に関して妥当なテーブルインスタンスのペアは、上記条件を満たす必要があります。この条件が、参照カラム $`(i, X, j, Y, r)`$ に対する参照制約条件〈reference constraint {condition}?〉／外部キー制約条件〈foreign key constraint {condition}?〉です。
参照関数
参照の5つ組 $`(i, X, j, Y, r)`$ を $`r`$ で代表させることにします。つまり、次のような記号の乱用を使います。
$`\quad r = (i, X, j, Y, r)`$
実際は、これは乱用ではなくて単なる冗長表現として合理化できますが、今は気にしないことにします。
先に、参照 $`r = (i, X, j, Y, r)`$ から関数〈写像〉 $`\widehat{r}`$ を作りました。その定義は：
$`\quad \widehat{r} := (r^*)^{-1} = (r^{-1})^* \;: \widehat{S_i}[X] \to \widehat{S_j}[Y]`$
参照 $`r`$ から関数 $`\widehat{r}`$ は一意に決まるので、$`r \mapsto \widehat{r}`$ は（域と余域を適切に決めれば）写像です。
$`\widehat{r}`$ を $`\rho_r`$ とも書いて、参照関数〈reference function〉と呼ぶことにします。ギリシャ文字小文字を使ったのは、次のように記法を揃えたかったからです。
- カラム $`X`$ の射影関数 $`\pi_X`$ （projection の'p'に対応するギリシャ文字が $`\pi`$）
- 超キー $`Y`$ のキーセクション関数 $`\kappa_Y`$ （key の'k'に対応するギリシャ文字が $`\kappa`$）
- 参照 $`r`$ の参照関数 $`\rho_r`$ （reference の'r'に対応するギリシャ文字が $`\rho`$）
カラム、超キー（候補キーを含む）、参照でインデックス付けられた関数の族達 $`\pi_X, \kappa_Y, \rho_r`$ は、データベース構造を記述する際に重要な役割りを演じます。
射影関数／キーセクション関数／参照関数の準備が出来たので、これらを使ってデータベーススキーマの形式的な定義を与えることが出来ます。それはまた次の機会に。
