このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

データベース・テーブルの変更を圏論的に見るならば

【注意】2022年3月より、MathJaxまたは「はてなブログ」の仕様変更またはバグにより、MathJax/XyJaxを使った数式・図が表示できなくなりました。そのため、一部の数式・図は表示できなくなっています(ソースコードが見えます)。新しいタブまたはウィンドウに、この記事のURLを貼り付けて開くと見えることがあります(ダメなときもあります)。もし、表示できていれば、この注意書きは無視してください。

\newcommand{\mrm}[1]{\mathrm{#1}} 
\newcommand{\lis}[1]{ \boldsymbol{#1} }
\newcommand{\In}{\text{ in } }
データベース・テーブルのある時点での状態は集合として捉えることができます。しかし、状態の変更である“削除・更新・挿入”を写像としてモデル化するのはうまくいかないようです。写像(集合圏の射)に拘らずに、別な見方をしたほうが良さそうです。

この記事では、変わり者/はぐれ者達に登場してもらって別な見方を提供します。

内容:

テーブルスキーマとテーブル状態

以下、関係データベースを単にデータベースと言います。データベースのテーブルを作るには、事前にテーブルスキーマが必要です。テーブルスキーマは、カラムの名前と型の集まりです。例えば次のような。

カラムの名前 生年月日 体重
カラムの型 文字列型 文字列型 日付型 整数型

ここでは、カラムの名前の代わりにカラムの(順番の)番号を使います。もちろん、名前に比べて意味が分かりにくくなり、実用上は困りますが、理論的には問題ありません。

カラムの番号 1 2 3 4
カラムの型 文字列型 文字列型 日付型 整数型

ある時点におけるテーブルの状態はタプルの集合です。タプルは ("坂東", "トン吉", 1999-08-28, 69) のようなデータです。

A_1, A_2, \cdots, A_n をn個の集合とします。テーブルスキーマ〈table schema〉は、集合のタプル  \lis{A} = (A_1, A_2, \cdots, A_n) として定義します。

テーブルスキーマ  \lis{A} = (A_1, A_2, \cdots, A_n) に対して、すべての成分を直積した集合を、

\quad \prod(\lis{A}) := 
\prod( (A_1, A_2, \cdots, A_n) ) := A_1 \times A_2\times, \cdots\times An

と書くことにします。より具体的に書けば:

  • \prod( (A, B, C) ) = A\times B\times C
  • \prod( (A, B) ) = A\times B
  • \prod( (A) ) = A
  • \prod( () ) = {\bf 1} = \{()\}

テーブルスキーマ  \lis{A} に対して、\prod(\lis{A})タプル空間〈tuple space〉と呼ぶことにします*1。空なテーブルスキーマ () のタプル空間 \prod( ()) は空集合ではなくて、空タプルだけからなる単元集合〈singleton set〉\{()\} であることに注意してください。テーブルスキーマとしてのタプルと、データとしてのタプルを混同しないように。

テーブル状態〈table state〉とは、タプル空間 \prod(\lis{A}) の部分集合のことです。次の3つの文は同じ意味です。

  1. S は、テーブルスキーマ \lis{A} のテーブル状態である。
  2. S \subseteq \prod(\lis{A})
  3. S \in \mrm{Pow}(\prod(\lis{A}))

\mrm{Pow}(X) は、集合 X のベキ集合〈powerset〉を意味します。

テーブル状態の変更

データに対する典型的操作は、その頭文字をとってCRUD〈クラッド〉というアクロニムで呼ばれます。

  • Create : 新しくデータを作り出すこと
  • Read : データを読み出すこと
  • Update : 既存のデータを変化させること
  • Delete : 既存のデータを削除すること

Readはデータを変更しないので、変更する操作はCUDです。データベース・テーブルへの変更の場合は、Delete, Update, Insert という言葉がよく使われます。略称しないで、そのまま Delete, Update, Insert〈削除・更新・挿入〉と記すことにします。

「タプルの更新〈update〉は、タプルを削除〈delete〉してから新規データを挿入〈insert〉しても同じだ」という意見があります。僕は腑に落ちないです。例えば、坂東トン吉さんの体重が、69kgから74kgに増えたとき、タプル ("坂東", "トン吉", 1999-08-28, 69) を削除してから、新規に ("坂東", "トン吉", 1999-08-28, 74) を挿入するのは「なんか違うでしょ!?」と思うわけです。

現実に起きたことは、同一人物としてのアイデンティティは保ちながら体重だけ増えたということです。なんかのサークルから退会して、太って再入会したという事象とは違います。

アイデンティティの話になると、キーとかIDとかが登場します。しかし、そういう追加のメカニズムを入れると話が複雑になり嬉しくありません。キーだのIDだのを(少なくとも表立っては)持ち出さない定式化が欲しいのです。

単射スパン

2つの集合に対して単射スパンというものを定義します。一般的には、モノ射のファイバー積〈fibred product〉を持つ圏ならモノ射スパンを定義できますが、ここでは集合圏をベースとした話に限定します。単射スパンが、データベース・テーブルの変更をモデル化するために使えます。

集合圏のスパン〈span〉とは、次の図式で表現される2つの写像の組み合わせです。

\xymatrix{
{}  & {X}\ar[ld] \ar[rd] & {} \\
{A}  & {}  & {B}
}\\
\text{in }{\bf Set}

スパンの各部を次のように呼びます。

  • 集合 X をスパンの〈head〉(またはボディ〈body〉)
  • 写像 X \to A をスパンの左脚〈left leg〉
  • 写像 X \to B をスパンの右脚〈right leg〉
  • 集合 A をスパンの左足〈left foot〉
  • 集合 B をスパンの右足〈right foot〉

「脚」と「足」の区別を付けるには、「脚」を「きゃく」と読むといいでしょう。

スパンを一種の射とみなして、次のように書きます。

\quad x = (X, x_l, x_r): A \to B

ここで、

  • x_l : X \to A は左脚
  • x_r : X \to B は右脚

頭が X であって、左足 A から右足 B へのスパンの集合は次の集合と同じです。

\quad {\bf Set}(X, A)\times {\bf Set}(X, B)

これらの集合を、X をすべての集合に渡って動かして寄せ集めると次のような(大きな)集合ができます。

 \mrm{SPAN}(A, B) := \bigcup_{X\in |{\bf Set}|}( {\bf Set}(X, A)\times {\bf Set}(X, B) )

このままでは扱いにくいので、2つのスパン x, y:A \to B のあいだの同値関係  x \sim y を定義します。 x \sim y とは、次の図式を可換にする同型写像 u:X \to Y が存在することです。

\xymatrix{
{}  & {X}\ar[ld]_{x_l} \ar[rd]^{x_r} \ar[dd]^{u}_{\cong}& {} \\
{A}  & {}  & {B}\\
{}  & {Y}\ar[lu]^{y_l}\ar[ru]_{y_r} & {}
}\\
\text{commutative in }{\bf Set}

\mrm{SPAN}(A, B) 上の関係 \sim が実際同値関係になるのはすぐ分かるので、商集合をとります。

\quad \mrm{Span}(A, B) := \mrm{SPAN}(A, B)/\sim

これでもまだ小さい集合になることが保証できませんが、以下の条件を付けると小さな集合になります。

  • スパンの左脚も右脚も単射写像〈injective map〉である。

この条件を付けたスパンを単射スパン〈injective span〉と呼び、改めて次の定義をします。

 \quad \mrm{InjSpan}(A, B) := \mrm{INJSPAN}(A, B)/\sim

\mrm{INJSPAN}(A, B) はすべての単射スパンの集合です。

\mrm{InjSpan}(A, B) が小さい集合になることは、次のような埋め込み写像が在ることから分かります。

\quad \mrm{InjSpan}(A, B) \to \bigcup_{X\in \mrm{Pow}(A)} {\bf Set}(X, B)

埋め込み写像の構成は練習問題です。

単射スパンの圏

以下では、A から B への単射スパンと言えば \mrm{InjSpan}(A, B) の要素を表すとします。\mrm{InjSpan}(A, B) の要素は同値類なので、適当な代表元 x = (X, x_l, x_r) \in \mrm{INJSPAN}(A, B) を取って議論します。つまり、行きがかり上、単射スパンが同値類の代表元を意味することもあります。

単射スパンを射とする圏を構成したいのですが、それには、x = (X, x_l,x_r):A \to B y = (Y, y_l, y_r): B \to C の結合〈composition〉を定義する必要があります。結合は次の図式のように定義します。

\xymatrix{
{} & {} & {Z}\ar[dl]_{\pi^1} \ar[dr]^{\pi^2} & {} & {}\\
{} & {X}\ar[dl]_{x_l} \ar[dr]^{x_r} & {} & {Y}\ar[dl]_{y_l}\ar[dr]^{y_r} & {}\\
{A} & {} & {B} & {} & {C}
}\\
\text{commutative in }{\bf Set}

上記図式で、ひし形の部分がファイバー積になってますが、ここは具体的に定義できます。


\quad Z := \{(i, j)\in X\times Y\mid x_r(i) = y_l(j) \}

図式内の \pi^1, \pi^2 は直積の第一射影/第二射影です。新しく作られたスパン z = (Z, z_l, z_r):A \to C は次のように定義します。

  • 左脚:  z_l := \pi^1; x_l
  • 右脚:  z_r := \pi^2; y_r

x, y が単射スパンのとき、この定義で作られた z も単射スパンになります(確認してみてください)。

単射スパン x:A \to B と単射スパン y:B \to C結合〈composition〉は、今定義した単射スパン z :A \to C だとして、 z = x;y = y\circ x と書きます。

単射スパン x, y の代表元のとり方により、構成される  z = x;y は変わりますが、同値類としては一意なので、結合は well-defined です。

恒等単射スパン〈identity injective span〉は、左右の脚がどちらも恒等写像であるスパンとして定義します。

細部まで確認するのはけっこう面倒ですが、今定義した結合と恒等により、すべての集合の類〈クラス〉を対象類として、単射スパンを射とする圏が構成できます。この圏を {\bf InjSpan} と書きます。

\quad {\bf InjSpan}(A, B) = \mrm{InjSpan}(A, B)

ですが、太字で書くと圏のホムセットであることが強調されます。

単射スパンと削除・更新・挿入

\lis{A} = (A_1, \cdots, A_n) をテーブルスキーマとして、S, T\subseteq \prod(\lis{A}) を2つのテーブル状態とします。テーブル状態が S から T に変更されることを、単射スパンを使って記述します。

\quad x = (X, x_l, x_r):S \to T \In {\bf InjSpan}

なぜ単射スパンがテーブル状態の変更〈削除・更新・挿入〉の記述になっているのでしょうか?

単射スパンの頭〈head〉の要素 i\in X が一時的なIDの役割を果たしています。変更前の x_l(i)\in S と変更後の x_r(i)\in T は、同一物が変化した before/after を表していると解釈します。

では、一時的なIDを振られなかった要素〈タプル〉達はどう解釈すべきでしょうか?

  • 左足 S から、左脚の像集合 x_l(X) \subseteq S を取り除いた差集合 S \setminus x_l(X) に属する要素〈タプル〉達は、削除されたとみなす。
  • 右足 T から、右脚の像集合 x_r(X) \subseteq T を取り除いた差集合 S \setminus x_r(X) に属する要素〈タプル〉達は、挿入されたとみなす。

以上のように解釈すれば、単射スパン x = (X, x_l, x_r):S \to T は、状態 S から状態 T への変更〈削除・更新・挿入〉を過不足なく表現していると言っていいでしょう。

テーブル状態と状態変更の圏

テーブルスキーマ \lis{A} = (A_1, \cdots, A_n) に対して、このスキーマに基づくテーブル状態を対象として、テーブル状態の変更〈削除・更新・挿入〉を射とする圏を定義しておきましょう。この圏は {\bf TableState}[\lis{A}] とします。

  • 対象集合: |{\bf TableState}[\lis{A}]| := \mrm{Pow}(\prod(\lis{A}))
  • ホムセット:{\bf TableState}[\lis{A}](S, T) := {\bf InjSpan}(S, T)

結合と恒等は、単射スパンの圏のそれを流用します。

例えば、何もないカラッポのテーブル状態から、データ(タプル達)が増えたり減ったり変わったりして時間的に推移する様は、次のような射のチェーンで表現できます。

\quad
\emptyset = S_0 \overset{x^1}{\to} S_1 \overset{x^2}{\to} S_2 \overset{x^3}{\to} \cdots\\
\:\\
\quad \text{in }{\bf TableState}[\lis{A}]

ひとつ前の記事「実用圏論: 2-圏、居住関係、プロファイリング」において:

ときに、未定義部分がある関数、値が一意に決まらない関数もどき、関手とは呼べない対応、自然性を満たさない変換のような、出来そこないや無法者が登場します。それらも排除しないで利用していきましょう。

と述べました。テーブル状態の変更も、“まっとうな写像”ではうまく記述できないので、ちょっと風変わりな単射スパンを利用しました。関数、関手、自然変換のような“まっとうな奴ら”だけでは太刀打ちできない現象もけっこうあります。

*1:「タプル空間〈tuple sppace〉」という言葉は、分散コンピューティングのモデルの意味で使われることがあります。ここでは、単純素朴に、すべてのタプルからなる集合の意味です。