トランザクションの参照透過性&副作用およびHerbrand Semanticsについて

トランザクションの参照透過性と副作用

前回のポストでは、関数の参照透過性と副作用について書きました。

本ポストでは、（データベースにおける）トランザクションの参照透過性を以下のように定義する。

• トランザクションのすべての作用が、トランザクションがデータベースからreadした情報だけに依存するとき、そのトランザクションには参照透過性があると定義する。
• トランザクションの作用とは、データベースのdata itemへのwriteである。
• つまりトランザクションがデータベースへwriteする内容が、そのトランザクションがデータベースからreadした情報だけに依存して決まるとき、そのトランザクションには参照透過性がある。

また本ポストでは、（データベースにおける）トランザクションの副作用を以下のように定義する。

• トランザクションの実行によって影響を及ぼす範囲が、データベースのdata itemだけに閉じているとき、そのトランザクションには副作用がないと定義する。

この定義によると、トランザクションとデータベースの間の界面がトランザクションの主たる界面（副ではないという意味で）となる。

Herbrand Semanticsとは

Herbrand Semanticsとは、トランザクションが何を引き起こすか、トランザクションのその意味をモデル化する方法である。

TIS（Weikum本）のDefinition 3.3では、ステップについてのHerbrand Semanticsが次のように定義されている。

DEFINITION 3.3 Herbrand Semantics of Steps

Let s be a schedule. The Herbrand semantics H_s of steps r_i(x), w_i(x) ∈ op(s) is recursively defined as follows:

1. H_s(r_i(x)) := H_s(w_j(x)), where w_j(x), j ≠ i, is the last write operation on x in s before r_i(x).
2. H_s(w_i(x)) := f_ix(H_s(r_i(y₁)),..., H_s(r_i(y_m))), where the r_i(y_j), 1 ≤ j ≤ m, represent all read operations of t_i that occur in s before w_i(x), and where f_ix is an uninterpreted m-ary function symbol.

Weikum, Gerhard; Vossen, Gottfried. Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems) （ページ74). Elsevier Science. Kindle 版.

これは以下のように解釈できる。

• トランザクションt_iがdata item xにwriteする値は、そのトランザクションt_iが（そのwrite step以前に）readしたすべてのdata itemの値と、そのトランザクションt_iのそのwrite step固有の関数f_ix のみに依存して決まるとする考え方。

Definition 3.3に続く文章では、スケジュール内の全てのトランザクションに先行する（各data itemの初期値をwriteだけする）特別なトランザクションt₀によって書かれたという考え方を取り入れている。これによりf_ixを展開していくと、各data itemの値は最終的には、関数f_ixの組み合わせだけに還元できる。

Herbrand Senanticsにつては以下も参考になります。

• Serializablitiyとは？ １. Final State Serializabilityについて
• エルブラン・セマンティクス(Herbrand Semantics)理解メモ

Herbrand Senanticsと参照透過性

TISのDefinition 3.3 Herbrand Senantics of Steps を見る限り、この定義におけるトランザクションには参照透過性がある。言い換えると、参照透過性があるトランザクションを一見、前提にしているように見える。

Herbrand Senanticsにおける副入力の解釈

例えば銀行口座間の送金トランザクションを考えると、２つの口座番号と送金金額はプログラム上はパラメタライズされており、外部から与えられた情報をもとにして初めて実体化される。

この外部からの入力は、参照透過性の観点における副入力に他ならないのではないかという疑問が湧く。 しかしこれは以下のように解釈できる。

• トランザクションは（トランザクションの識別性は）、そのロジックとパラメタを組み合わせたものである。パラメタが異なる（例: 口座番号や金額が異なる）トランザクションは別のトランザクションである。

このように考えると、すべての副入力はトランザクションのロジックと区別がつかなくなり、トランザクションに副入力は存在しないことになる。

トランザクションの副作用

トランザクションの作用はdata itemへのwriteであり、それ以外は副作用と見なすと定義した。

データベース管理システムで実行されるトランザクションは応答を返す。 応答が観測されるなら、これは副作用になり得る。

トランザクションの実行モデル

トランザクションが実行されるモデルとして以下の３つを考える。

1. すべてのトランザクションが投入され終わらない限り、いずれのトランザクションの応答も返ってこないモデル。
   • すべてのトランザクションが投入されてから初めて、実行がスケジューリングされるモデルと見なせる
2. １つのトランザクションがまとめて一度だけシステムに渡され、一度だけ応答を返すモデル。
   • One-shotモデル？
3. １つのトランザクションにつき複数回のやり取りを許すモデル。
   • SQLのステートメントごとに要求と応答を繰り返すような対話型モデル

これらのうち１つ目のモデルでは、あるトランザクションの応答を別のトランザクションが参照することがないため、副作用はないものと見なせる。

一方残りの２つのモデルでは、他のトランザクションの応答を観測しうるので、このモデルにはトランザクションの副作用が存在し得る。

異なるトランザクションの間に外部の依存関係があった場合

あるトランザクションXの（完了）応答が、別トランザクションYの振る舞いに影響を与えている場合を考える。

例えば、ある送金トランザクションXの実行結果によって、別の送金トランザクションYの金額や送金差先が変更されるような状況である。

このときXの応答は別のトランザクションの振る舞いに影響を与えている（観測された）ので、これは明らかに副作用である。 （一方、先の議論で、トランザクションの参照透過性を脅かす副入力は存在しないことになっている。）

このようなトランザクション間の外部の依存関係はトランザクションマネージャには捕捉されないので、トランザクションマネージャは、Y→Xというような順序付けを行う可能性がある。

これは外部の依存関係を知る者にとっては明らかに誤りだが、トランザクションマネージャは何らかのserial scheduleとequivalentだと判断したはずである。

Herbrand Semanticsにおける副入力の扱いを踏まえると、以下のような状況である。

• まずトランザクションXのテンプレートX<T>とトランザクションYのテンプレートY<S>があった。
• （X<T>から実体化された）トランザクションX<A>の応答をもとに、テンプレートY<S>のパラメタSがBと決定された。
• トランザクションY<B>が実行された。
• 実際の依存関係はX<T>→Y<S>であったが、トランザクションマネージャはY<S>→X<T>と順序付けた。

もし実際の順序がY<S>→X<T>であったなら、パラメタSはBにはなりえなかった。つまりこの順序の場合、Y<B'>→X<A>である。一方、実際はX<A>→Y<B>である。

まとめると以下のような状況になる。

trans() ＼ 順序	X→Y	Y→X
{X<A>,Y<B>}	①あり得る	②あり得ない
{X<A>,Y<B'>}	③あり得ない	④あり得る

トランザクションマネージャは②を選択したが、①と比較すれば順序付けが誤っていたと見えるし、④と比較するとequivalentだと思ったスケジュールのトランザクション集合が実は異なっていたと見える。

外部の依存関係を許すか

上記のような外部の依存関係を許さないシステムが多かったのではないかと想像します。

一方で、DBMSがUDFに対して参照透過性や副作用が無いことを要求するのとおなじように、アプリケーション/トランザクションにそれを要求できるかというと難しいと思われる。

なぜなら、通常UDFが触れている世界とDBMSの世界ではDBMSの扱う範囲の方が広く、だからDBMSはUDFに「必要なものはすべて私が与えるからそれ以外の界面でやりとりするな」という主張に納得できる部分もあるが、DBMSの世界よりアプリケーションが触れる世界の方が大きいから、DBMSがアプリケーションに「必要なものはすべて与える」という主張は滑稽に見える。

しかしこれも、データベースの性質によっては言えるかもしれない。 例えば以下のご本尊系データベースの場合。

データベースには二種類ある。ひとつは実世界の状態の複製であるところのデータベースで、もうひとつはデータベース自体が本体、マスタ、オリジナル、ご本尊であるところのデータベースだ。

— デヴすぴスラ (@dev_supisula) 2019年2月14日

トランザクションの単位

上記のような依存関係があるなら、別のトランザクションにするのではなく、１つのトランザクションにすべきだ、という主張が考えられる。

しかし一般にトランザクションの単位とはなにか、というとそれは永続化のatomicity、および分離のatomicityの単位と認識されているのではないか。依存関係のスコープを表す手段としてのトランザクション、という考え方は一般的ではないのではないか。

この問題の回避

外部の依存関係は実時間の流れる方向にしか発生しないはずだ。

だから、one-shotモデルの場合は既存のプロコトルに以下の制約を付け加えればよい。

ｰ Tx < Ty | cx < by の場合。ここでcxはトランザクションTxの完了応答時刻で、byはトランザクションTyの到着時刻

この制約は、トランザクションに（分散処理の文脈における）consistencyを導入することに対応するはずだ。

再びHerbrand Senantics

TISのp.73のIdea of Herbrand Senanticsは次のように書かれている。

1. a step wi(x) ∈ s writes a new value that potentially depends on the Idea of Herbrand semantics values of all data items that ti has read from the database or from other transactions in active(s) ∪ commit(s) prior to wi(x).

強調部分を読むと、副入力を想定しているようにも見える。しかしこれがdefinition 3.3になると、データベースとの入出力だけに限定されているように読める。

その他

トランザクションの副作用を考えたとき、対話型モデルではステートメント毎の応答が他のトランザクションに影響を（isolationを無視して）及ぼしうる。

またone-shotモデルでも、abort応答が他のトランザクションの振舞いに影響を与えるかもしれない。

これらはどう扱えばよいのか…。