すぴすらのろぐ

読んだもののメモとかポエムとか

トランザクションの単位とhidden restrictions

このポストは、papa本読書会第1回目で読んだ範囲における、トランザクションの単位とトランザクション間のhidden restrictionsについてのまとめです。 議論としては2回目の内容も含んでいます。話題としては2回目の内容を含んでいます。ポストの内容は個人的なもので読書会の総意ではありません。

具体的には、こだわっているトランザクション間の依存関係の話です。

papa本は以下の本です。

トランザクションとは

papa本 p.5より:

A transaction is a sequence of database steps resulting from the execution of a program.

。ここでトランザクションのsyntacticな(?)定義をしていて、それはつまりプログラムから生成される具体的なdatabase stepの列である(database stepとは例えばentityに対するreadやwrite stepのこと)。

トランザクションとは

papa本 p.5より:

A transaction is a unit of consistency, a grouping together of several database steps, the combined execution of which is known to preserve the integrity constraints

。ここでトランザクションのsemanticな(?)定義をしていて、それはつまりconsistencyの単位である。 ここでのconsistencyとはintegrity constraintsの説明に出てくるconsistentのことで*1、つまりトランザクションとは、integrity constraintsを維持するdatabase stepsの列といえる。

トランザクション間のhidden restrictions

papa本p.5より:

A consequence is that there can be no "hidden restrictions" on inter-transaction behavior.

トランザクションがconsistencyの単位だという定義を受けて、トランザクション間のhidden restrictionsはないと結論付けている。

トランザクションX1とX2がある。 これらは一見、consistent stateを維持するとみなされている。 これらのトランザクション間には、X1→X2の順序でスケジューリングしてほしいというhidden restrictionsが存在する。

この場合、この本ではX1とX2はまとめて1つのトランザクションにすべきといっている:

For example, if correctness requires that steps from two "transactions" are executed in some predefined order, then these two "transactions" are in fact a single transaction.

解釈

これは以下のような解釈に基づいていると思われる。

  • トランザクション間にhidden restrictionsがあるということは、そうでない順序でスケジューリングされたら問題があるということだ。
  • それはつまり、そうでない順序で生成される結果がconsistent stateではないということだ。
  • その結果、X1、およびX2はそれぞれ単体ではトランザクションとはみなされない(integrity constraintsを維持しないから)。
  • よってここでのトランザクションはX1とX2を合成したものになる。

これをconsistency(integrity constraints)原理主義と呼ぼう。

consistency原理主義の何が問題か

上記の何を問題だと思うかというと、上記の例のトランザクションX1とX2によって生成される局所的なconsistent stateをアプリケーション(プログラマ)が定義できたとしても、原理主義が期待するX1、X2間の順序を含むconsistent stateをアプリケーション(プログラマ)が定義できないと思うからだ。

X1、X2の順序を含めた定義をするためには、(local)トランザクションの発行順序に影響のあるすべての要素を定式化する必要があり、それは結果的に世界のすべてを記述することになってしまうはずだ(と思う)。

また逆に、もし世界のすべてを記述できるとしたら、あり得る(local)トランザクションの発行順序はただ1つに決まってしまい、その場合、すべての(local)トランザクションを1つに合成したただ一つのトランザクションになってしまうことになるのではないか。

落としどころ

世界をシミュレートできない/決定的でない/予知できないという立場に基づくと、アプリケーションで定義可能な範囲をconsistent stateとみなすしかないと思われる。 その結果、やはりhidden restrictionsは生じてしまう。

前のポストでは、「トランザクション理論は、アプリケーションとデータベースが、consistencyとserializabilityの維持の役割を完全に分離したモデル」とか書いたが、アプリケーションは世界の記述をあきらめざるを得ない。そのためスケジューラは、アプリケーションがあきらめた分をhidden restrictionsの保証という形で守る必要がある。

トランザクション間のhidden restrictionsの定義

ここでトランザクション間のhidden restrictionsを、アプリケーションによって事前に定義された(期待される)、トランザクション間の半順序関係と定義することにする。

トランザクション集合を {T}としたとき、トランザクション間のhidden restrictionsを半順序関係{ R(x,y) \in T \times T, x,y \in T }とする。

スケジューラが出力する順序関係Sも同様に、{ S(x,y) \in T \times T, x,y \in T })とする。

スケジューラが全順序関係を出力する場合、{ R \subset S }となる必要がある。これがスケジューラに課される追加の仕事だ。


*1:consistency自体の用語の定義はないが、ここでいきなり分散処理の文脈のconsistencyは出てこないと思う(発行年的にも)