Yabu.log

ITなどの雑記

Transactionのinterpretation(herbrand semantics)について

herbrand semanticsのメモです。主にFSRを理解するための準備です。このエントリはChristos Papadimitrioupapa:Theory of Database Concurrency Control(通称papa本)の5~9ページのまとめです。

データベースの世界にはherbrand semanticsというConflictやSerializabilityを考える時に使う便利な道具があります。いつからherbrand semanticsと呼ばれるようになったのかはわかりませんが、papa本ではinterpretationという名前で扱われています。 近年ではトランザクションの教科書にもherbrand semanticsと書かれていることもありますので、本エントリではpapa本からの引用以外はこちらの名前を使います。

weikum本寄りの解説はぱとさんがあげているので、今回はpapa本寄りのメモを書きたいと思います。

taityo-diary.hatenablog.jp

Theory of Database Concurrency Control

Theory of Database Concurrency Control

transactionとreadとwrite

まずはトランザクションの定義から。トランザクションは任意のentityに対するreadとwriteの有限集合。

Difinition 1.1 A transaction A is a finite sequence fo steps A = a_1,a_2...a_n. The steps are assumed to be distinct symbols, and two differencttransactions cannot have steps in common. With each step a_j of A we associate an action ACTION(a_j) ∈ {W,R}, and an entity ENTITY(a_j) ∈ E.

read:対象entityの現在の値をプログラム中の変数へ割当てることを意味する。

If some step a_j reads entity x. This means that a particular program variable t_j in the underlying program is assigned the current value of x in the database: t_j := x.

write:対象entityに対するプログラムで計算した値の割り当てを意味する。

If ACTION(a_j) = W and ENTITY(a_j) = x , then the step write x. By this we mean that x is assigned a value computed by the program, which is potentially a function of all previously read(by the same program) values of entities: x := fj(t_i1,ti_2,...t_ik),where the ip's are all indices smaller than j for which ACTION(a_ip) = R

なおこのwriteで書く値の計算はwrite step以前のすべてのreadを引数にとる関数fとして定義することができる。この関数の厳密な定義がherbrand semanticsになる。

interpretation

条件分岐や繰り返しなどの制御構文を含むアプリ(プログラム)から発行されたdatabaseに対するread/writeのdatabase stepの意味をdatabase側から解釈する。プログラムが発行したdatabase stepのまとまりはtransactionになる。transactionは制御構文を持たないので、アプリとは別の解釈が必要となる。

A transaction, as defined above, is a purely syntactic object, subject to different interpretations. Intuitively, specifying an interpretation of a transaction means fixing a particular application program from which the transaction has originated, disregarding of course any control structure the program may have.

トランザクションの実行はある状態からある状態への写像と解釈する。

An interpretation of A(注:このAは任意のtransactionを指している) is a pair I = (D,F), where D = {D_x,D_y,...} is a set of domains, onefor each entity in E; each domain is a set of values for the corresponding entity. F = {f_a:a is a step of A and Action(a)=W} is a set of functions, one for each write step of A. For each such step a, f_a is a mapping

f_a: \prod_{x \in B(a)} D_x \to D_{ENTITY(a)}

  • writeのオペレーションはそれまでに読んだ値のドメインの直積からwrite対象のentityのドメインへの写像になる。
  • B(a)はa以前に読んだ全てのentityの集合。

B(a_j) = {x \in E : {\bf For \, some }\, i  \le j \, ACTION(a_i) = {\bf R \, and \, }ENTITY(a_i) = x}

具体例として1トランザクション前提(1並列)で以下の送金プログラムで説明されている。

program transfer(amt:integer);
    entities x,y: integer;
    variables temp1,temp2:integer;
    begin
    temp1 := x;
    if temp1 ≧ amt then
        begin
        x := tmp1 -amt; 
        temp2 := y;
        y := temp2 + amt
        end
    end.

ローカル変数へのentity代入をread,entityへの値の書き込みをwriteのデータベースステップと考えると上記のプログラムは以下のschedule(Action)を作る。

A = R(x)W(x)R(y)W(y)

この時、各database stepのherbrand semanticsは以下のようになる。

t1:=x
x:=f2(t1)
t3:=y
y:=f4(t1,t3)

f4の関数の内容はf4(t1,t3)=t3+50で、t1は一切使わないが、このt1はherbrand semanticsでは必要とする。 どのパラメータが実際に使われているかという情報はアプリ(DBMSを読み書きするプログラム)の完全な情報がないと分からない。そしてconncurency controlを考える時にアプリのコード全体が把握できるケースは極めて稀*1であるため、writeの前に発行されたreadは全てwriteを表す関数の引数として扱う。

Situations such as this of Example 1.2, in which we have complete information about the program and the value of their parameters, are rare in concurrency control

同じentityへの各database stepは1回まで

オペレーションごとにherbrand semanticsを考えることができそうだが、correctなスケジュールなら1つのentityへの複数回のread,writeは冗長なので、herbrand semanticsを考えるときは同じトランザクション内では

  • read/writeは1つのentityに対して1回まで
  • writeしたentityの値をreadしない

という前提を置く

It is quite natural-and, it turns out, simplifying-to make the following assumptions about the structure of the transactions.

(a)In a transaction an entity is read at most once, and is written at most once.

(b)In a transaction, no entity is read after it is written.

後述しますが、本来ならあるトランザクションの何番目のステップのfというような表記になるところを上記の前提を置くことで 、あるトランザクションのあるentityに対する操作(f)、またはあるトランザクションの何番目の操作(f)というシンタックスで表現できる。ちなみに、weikum本では前者のシンタックスを採用し、papa本では後者を採用している。*2

Hs(wi(x)) := fix(Hs(ri(y1)),...,Hs(ri(ym))), where the ri(yj), 1 ≤ j ≤ m, represent all read operations of ti that occur in s before wi(x)

weikum本より引用。f_{ix}のiをトランザクションの添え字、xをentityとするシンタックスにしている

Interpretationとshcedule

If s is a schedule involving the transactions A_1,...,A_k, then an interpretation I of s is a k-tuple of interpretations I_j = (D,F_j), all with the same choice D of domains for the entities.

scheduleにinterpretationを適応すると、schedule中の任意のdatabase stepをa_s(I,X)で表現することができる。

Suppose that s is a schedule, I an interpretation, and X an initial state, that is a value for each entity. We say that every database step a of s computes a value a_s(I,X).

また、スケジュールの実行結果、つまり最終状態をs(I,X)という特別なシンタックスで表現する

The final state resulting from the execution of s, denoted s(I,X)

まとめ

  • 各entityがとりうる値(domain)の集合をDとしている
  • writeの関数fのすべての集合をFとしている。
  • 上記二つのペアをinterpretation(herbrand semantics)としている。
    • interpretationと初期値Xを使うことでtransaction中の任意のstepを関数で表現できる

*1:ストアドは例外

*2:上記のプログラムのread/writeへのherbrand semanticsの適当を見ると、最初のwriteは2回目のオペレーションなのでf2となっている