Transactional Information Systems続き(chap 3.3)
3.3 Syntax of Histories and Schedules
この節ではschedulerがオンラインで正しいスケジューリングをどう判断するかを議論するにあたって、スケジュールの記法を明確にする。
P65下から9行目, Here we try to respect ... のrespectが訳せない。
まず、トランザクションは必ずtermination operation
で終了するものとする。
- c: commit, トランザクションは他のトランザクションに邪魔されることなく終了し、トランザクションの結果は他のトランザクションに見える状態になっている
- a: abort, トランザクションの影響がdatabaseに一切ない状態になっている。
- abortにはrecovery処理が必要だがこれはpart3以降で扱う
次にhistories
とschedule
を次のように区別する
- histories
- schedule
- 部分的もしくはすべてのスケジュールが明らかになっているもの
- historiesのprefixに相当する部分で、
termination operation
など、オペレーションのすべてが明らかになっていないもの
DEFINITION 3.1
正直このままなので、コピペ。
history
は
- (a) すべてのトランザクションのすべてのオペレーションを含んでいる
- (b) 個別にtermination operation
を持っている必要がある
- (c) トランザクション内ですべての順序を保持している
- (d) それぞれのトランザクションの最後にtermination operation
を持っている必要がある
- (e) 同じデータへの操作は順序付けられている? 原文 -> (orders conflicting operations)
(a)と(b)を満たすとき、historyはcomplete scheduleと呼ばれる
DEFINITION 3.2
これもそのまま
あるステップp
がstepq
の前にあるときp < q
とかく。
特にschedule s(transaction t)のコンテキストにおいてそう書きたいときはp <_s q(p <_t q)
とかく。
また、半順序(partial order)のprefix(約不明)は"reachability chain"の最後の部分を削除することで得られる。 より正確に言うと、
(以下の分が画像に続く) if s =
となる。
次のような3つのトランザクションがあるとき、
全順序(total order)と半順序(partial order)を図示すると以下のようになる。
この図において、(a)がtotal order,(b)がpartial orderである。
(このあと例による説明が続く) サンプル3.5のprefixがわからん。
また、以下のようにscheduleを表記する。
p70より