weikum TIS読書メモ2:scheduleのpartial/total order,givenでないscheduleのsyntax等

1H
読んだ範囲p69~71｡
note:※historyはscheduleの内､terminate operationを含んでいるものであるから､書中でhistory and scheduleと書いてあるところは本ブログでは特に断り無くscheduleのみの表記とする｡
(partial order)historyの性質
- a:含まれるトランザクションの全てのoperationを含む
- b:各トランザクションはabort or commitのどちらかを持つ
- c:transactionのorderを保持する
- d:termination step は必ず各トランザクション最終に持つ
- e:conflictの条件
  - 詳細:異なるトランザクション内で同じdataに対するreadがあり､かつどちらかのtransactionがwriteを含む時
total ordered history s'について考える｡半順序scheduleの条件b,dに加えて､
- s'∈shuffle(T)であること
  - 補足:T={t1,...tn}の直積を shuffle(T)で表す
  - shuffle(T)は各t中のaction(read write commit abort)の全orderの集合のこと
s=tp(1)...tp(n)である時そのscheduleはSerialである
- p {1,...n}は各トランザクション内の順序を保持している
- まぁoperationがtransactionごとにinterleaveせずに並んでいるといういつものアレだと思います
total order scheduleの例
- T={t1,t2,t3}
  - t1=r1(x)w1(x)r1(y)
  - t2=r2(z)w2(x)w2(z)
  - t3=r3(x)r3(y)w3(z)
- s1 = r1(x)r2(z)r3(x)w2(x)w1(x)r3(y)r1(y)w1(y)w2(z)w3(z) ∈ shuffle(T)である
- s2 = s1c1c2a3 は history である
- s3 = r1(x)r2(z)r3(x) は schedule である
- s4 = t1c1t3a3t2c2は serial である
scheduleがgivenでない時を考える(non deterministic?)
- trans(s) := {ti | s contai steps from ti}
  - trans(s)はsで起こった全てのtrasactionの集合
- commit(s) := {ti ∈ trans(s) | ci ∈ s}
  - commitされたs中のtransactionの集合を表す
- abort(s) := {ti ∈ trans(s) |ai ∈s}
  - abortされたs中のtransactionの集合を表す
- active(s) := trans(s) - (commit(s) ∪ abort(s))
  - commitもabortもまだされていないs中のtransactionの集合を表す
- 具体例
  - s2 = r1(x)r2(z)r3(x)w2(x)w1(x)r3(y)r1(y)w1(y)w2(z)w3(z)c1c2a3の場合
    - trans(s2) = {t1,t2,t3}
    - commit(s2) = {t1,t2}
    - abort(s2) = {t3}
    - active(s2) = Φ
  - 当たり前だが､history sの場合は常にこうなる
    - trans(s) = commit(s) ∪ abort(s)
    - active(s) = Φ