トランザクションの Strictness と Rigorousness の定義を再確認する

はじめに

トランザクションの Recoverability を理解するうえで Strictness (ST) と Rigorousness (RG) を避けては通ることができません。ただ、日本語の資料が少ないうえに用語の定義が若干あいまいなケースも見受けられました。そこで、本エントリでは資料をまとめつつ、定義を再確認します。

参考資料

本エントリで参照する資料と本エントリ内での略記をまとめます。

(1) TX本

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)

言わずと知れたトランザクション技術に関する原典ともいうべき本。以降に紹介する資料もこの本を参考にしていると思われます。

(2) Rosati資料
http://www.dis.uniroma1.it/~rosati/gd/1-concurrency.pdf
Rosati教授の講義用資料のようです。
今回の内容は資料の "2.5 Recoverability of transactions" にまとめられています。

(3) kumagi資料
S2PLと永続化
@kumagi さんがトランザクション技術について解説した「一人トランザクション技術 Advent Calendar 2016」のうち、今回のテーマに関する記事です。

(4) 星野資料

トランザクションの並行実行制御 rev.2 from Takashi Hoshino

星野 喬 さんが筑波大学 集中講義で利用したスライドとのことです。

Strictness (ST) とは

まず、TX本(P393)から確認します。

DEFINITION 11.7 Strictness
A schedule s is strict if the following holds for all transaction t_i ∈ trans(s) and for all p_i(x) ∈ op(t_i), p ∈ {r,w}: if w_j(x) <_s p_i(x), i ≠ j, then a_j <_s p_i(x) ∨ c_j <_s p_i(x).
Let ST denote the class of all strict schedules.

In words, a schedule is strict if no data item is read or overwritten until the transaction that wrote it last has ended (either by commit or by abort).

Rosati資料(P105)では式を使わずに説明しています。

We say that a schedule S is strict if every transaction reads only values written by transactions that have already committed, and writes only on transactions that have already committed

kumagi資料での説明を引用します。

Strictとは「あるトランザクションによる、ある値への書き込みが他のトランザクションの読み込み・書き込みより先なら、他のトランザクションの読み書きは最初のトランザクションのコミットかアボートより後になる」というルールである。

星野資料(P20)での説明を引用します。

Tx1 が write している data item を read/write しようとする Tx2 は Tx1 が commit/abort するまでそれを待つ必要がある

いずれの説明も同じといえます。

Rigorousness (RG) とは

今回取り上げた日本語の資料は Rigorousness の説明に補足すべき点があります。順に確認していきます。

まず、TX本(P394)から確認します。

DEFINITION 11.8 Rigorousness
A schedule s is rigorous if it is strict and additionally satisfies the following condition: for all transactions t_i, t_j ∈ trans(s), if r_j(x) <_s w_i(x), i ≠ j, then a_j <_s w_i(x) ∨ c_j <_s w_i(x).
Let RG denote the class of all rigorous schedules.

In words, a schedule is rigorous if it is strict and no object x is overwritten until all transactions that read x last are finished.

Rosati資料(P107)を確認します。Strictness も含めた定義となっています。

We say that a schedule S is rigorous if for each pair of conflicting actions ai (belonging to transaction Ti) and bj (belonging to transaction Tj) appearing in S, the commit command ci of Ti appears in S between ai and bj.

kumagi資料での説明を引用します。

RigorousとはStrictの条件を守った上で「あるトランザクションによる、ある値への読み込みが他のトランザクションの読み込みより先なら、他のトランザクションの読み込みは最初のトランザクションのコミットかアボートより後になる」というルールである。

この説明には誤記があり、「他のトランザクションの読み込み」ではなく「他のトランザクションの書き込み」です。

正しく書き換えると以下の説明となります。
『RigorousとはStrictの条件を守った上で「あるトランザクションによる、ある値への読み込みが他のトランザクションの書き込みより先なら、他のトランザクションの書き込みは最初のトランザクションのコミットかアボートより後になる」というルールである。』

星野資料(P23)での説明を引用します。

Tx1 が read/write している data item を read/write しようとする Tx2 は Tx1 が commit/abort するまでそれを待つ必要がある

この説明には若干ミスリードな個所があり、Tx1 / Tx2 共に read のみであれば commit/abort 済みであるかは問題となりません。星野資料(P15)の「Conflict（競合）」の説明より、同じ data item に対する r-r は競合しないからです。

まとめ

Strictness / Rigorousness の定義は既に確認した通りです。今回の用語に限らず、改めてTX本を見直すことで発見があるかもしれません。

Strictness は w-r / w-w 競合を、Rigorousness は r-w 競合も対象としています。r-r は競合しません。