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

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

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

参照用 記事

トランザクションの代数、ちょっとだけ

デジタルなモノイド」というエントリーのコメントでチラリと触れてますが、モノイドをストレージに対する操作(の集合)だと考えると、原子性(Atomicity)は次のように定式化できます。

Mをストレージ操作(のつもり)のモノイドとしましょう。Mの部分集合Aをアルファベットとする自由モノイドFreeMonoid(A)を作って、適当な合同関係(モノイド構造を保存する同値関係)〜 で割り算して N := FreeMonoid(A)/〜 とします。Nは、Mから作った新しいモノイドです。もとのモノイドMが状態空間Sに作用している(加群になっている)とき、Nを係数域とする加群を合理的に作る処方が原始性の話です。

任意の集合Xから、自由モノイドを作る操作 X|→FreeMonoid(X) は、リストモナドList(X)とほぼ同じです。リストモナドのモナド乗法である平坦化 flattenX:List(List(X))→List(X) が自由モノイドのモノイド演算を与えます(「アイレンベルク/ムーア圏 その2:リストモナドのとき」を参照)。このリストモナドに、commit/cancelの概念を入れると、原始性を記述するモナドが出来ます。そこから後は通常のモナドの議論が通用します。

次に分離性(Isolation)ですが、一番厳しい分離性であるSERIALIZABLE条件は、モノイド圏の交替律(interchange law)そのものです。トランザクションの実行主体であるプロセスとかスレッドを2つ考えて、それぞれが行う操作をf, gとしましょう。fとgが同時に実行されることをタプルを用いて [f, g] と表現します。何も行わないことはidとします。

交替律は:

  • [f, g] = [f, id];[id, g] = [id, g];[f, id]

と書けます。これは、fとgの同時実行([f, g])が順次実行([f, id];[id, g] または [id, g];[f, id])と変わらないことを表現しています。ほんとに同時に実行しても、適当にインターリーブしてもかまわないということです。別言すれば、メモリ空間やストレージ領域が分離していれば、パラレル、コンカレント、タイムシェアリング、なんだって結果は同じよ、ってこと。

分離性のREPEATABLE READという条件は、余代数や余加群の余結合律(coassociative law)ですね。状態空間をSとして、観測値の集合をV、観測(エクリー)を q:S→S×V、Vのコピー操作を Δ:V→V×V とすると:

  • q;(idS×Δ) = q;(q×idV)

これは、加群スカラー乗法(モノイドの状態空間への作用)に関する結合律の双対です。この等式が言っていることは、クエリーしてコピー(2つの同じ値)を作っても、2回クエリーしても同じだということ。つまり、READのREPEATが可能で、同じ値であることを保証します。


交替律や余結合律はポピュラーな計算法則なので、それが成立していると何がうれしいか? 成立しないとどう困るか? 困ったときの回避策などの知見が蓄積されています。ストレージ操作にそういう知見が活かせないだろうか、活かせればいいな、と思っています。