データベーススペシャリスト 試験情報＆徹底解説

皆さま、秋季の試験お疲れさまでした。
私は午後1，2とも回答欄を埋めきれなかったので、来年頑張ろうと思います。

さて、表記についてご意見いただければと思います。
MVCCについての私の知識は、増永本第3版 P.315-316の説明がすべてなのですが、
そこからすると、表記設問の解答は  イ  のような気がします。

増永本●MVCCアルゴリズム の項目に沿って説明すると、
（前提）トランザクションP（P）の実行中にトランザクションQ（Q）が開始している。
        なので、トランザクションのタイムスタンプ（TS）は、TS(P)<TS(Q)になる。
1. TS(P)はTS(Q)以下、かつ、他に更新の記載がないので、
    値が5の資源Xは、Qより若いトランザクションが更新した最新の版になる。
    なので、Qは資源Xの値として5を読む
2.(ii)Pは資源Xの版（値は５）を発行できている ※回答に影響しない。

以上から、MVCCの場合、Qが資源Xの値として5を読むことになる。4を読むことはない、と思うのですが、どうなのでしょうか。
また、増永本以外にも、詳しくMVCCを理解するのにいい参考書などありますでしょうか。

そもそもダーティリードは理解していますか？
Qが参照するとき、まだPの変更はコミットされていません
まだ他のトランザクションがコミットしていない値を読み込まないように多版を作成するのがMVCC（多版型同時実行制御）です

> まだ他のトランザクションがコミットしていない値を読み込まないように多版を作成するのがMVCC（多版型同時実行制御）です

増永本ではそう説明されていないのです。
MVCCは、(ロックを用いずに）トランザクションを同時実行しても実質的に直列可能性のあるスケジュールを実行したことにする。

そのため、各トランザクションに時刻印を付け、
データ項目にも更新時に時刻印と、どのトランザクションが更新したかの記録を残し、
データを読む際には、自身かそれより若いトランザクションが更新した中で、最大の時刻印の版の値を読む、
というアルゴリズムを使う、と説明されています。

増永本第3版 P317 図11.21を見ていただきたいのですが、トランザクションT2が、時刻t3の時点で初版のx0ではなく、コミット前のT1が発行したx1の版の値を読んでいるよう図示されています。

MVCCではコミットされていない値を全く読まない、と説明されている参考書が別にあるということでしょうか。

増永本はわかりませんが、wikiにも「書き込みの直前の状態を処理結果として返す」と記載があります
問題文の隔離性水準もREAD COMMITEDになっていますので、コミットされていない値が読み込まれることはありません
そもそもMVCCとはまだコミットされていない値が読み込まれないように更新前と更新後の版を作成するから多版同時実行制御というのであり、常に更新後の値を返していたら多版の意味がなくなってしまいます

以下、wikiのMultiVersion Concurrency Controlについての記載
>MVCCは、書き込み処理（トランザクション）が行われている最中に他のユーザによる読み取りアクセスがあった場合、書き込みの直前の状態（スナップショット）を処理結果として返す。つまり、書き込み中も読み取りができ、読み取り中でも書き込みができる。

恐らくですが、増永本のいう「更新」とはUPDATE文を実行したタイミングではなく、コミットして変更が反映されたときのことをいうのではないでしょうか？

回答ありがとうございます。

気を悪くしないで頂きたいのですが。英語版のwikiをClomeの翻訳で読んだところ、
MVCCではコミット前の値を読む、単純に書きこみ直前の状態を読む、という記載はありませんでした。
  （  英語wikiの、Multiversion_concurrency_control  ）
記事内の「実装」項（Implementation）の一部を転記します。

MVCC は、タイムスタンプ(TS)と増分トランザクション IDを使用して、トランザクションの一貫性を実現します。
(略）
オブジェクトPの各バージョンには、読み取りタイムスタンプ(RTS)と書き込みタイムスタンプ(WTS)の両方があり、
特定のトランザクションTiは、トランザクションの読み取りタイムスタンプRTS(Ti)に先行するオブジェクトの最新バージョンを読み取ることができます。
(略）
すべてのオブジェクト (P) にはタイムスタンプ (TS) がありますが、トランザクション Ti がオブジェクトに書き込む場合、…
(略：書き込みが中断される条件の説明）
それ以外の場合、Ti はオブジェクト P の新しいバージョンを作成し、新しいバージョンの読み取り/書き込みタイムスタンプ TS をトランザクション TS ← TS(Ti) のタイムスタンプに設定します。

以上となります。
増永本にはRTSの記載がありませんが、英語wikiでも、データ項目の最新版のTSは書き込み時に更新され、トランザクションは自身のRTSより前のTSを持つデータ項目のうち最新版を読む、となっています。

また、英語版wikiには議論のノートがあり、ノートのない日本語版wikiより信頼性が高いと考えます。
増永先生の経歴と本自身の評判から、増永本の信頼性は高いと考えます。

>増永本はわかりませんが
増永本の解釈・信頼性vs回答例の信頼性、についての質問なので、増永本に目を通してから、もしくは増永本に沿って説明した内容を理解してから回答いただきたかったです。
>問題文の隔離性水準もREAD COMMITEDになっていますので
こちらは2PLに対しての補足だと理解できます。
>まだコミットされていない値が読み込まれないように更新前と更新後の版を作成するから多版同時実行制御というのであり
信頼度の高い英語wiki、増永本の説明では、トランザクション実行中にデータ項目の新版が作成されるのがMVCCです。
>常に更新後の値を返していたら
信頼度の高い英語wiki、増永本では、自身よりRTSが新しいデータ項目の値は読みません。
>増永本のいう「更新」とはUPDATE文を実行したタイミングではなく、コミットして変更が反映されたときのことをいうのではないでしょうか？
UPDATEを実行したタイミングです。増永本をご確認ください。

黒猫さんには真っ先に回答いただき、大変ありがたいと思っております。
日本語wikiもあいまいに書かれているので、黒猫さん以外にも同じように理解している方は多いのではと思います。
また、私も英語wikiの記載を確認するいい機会になりました。
黒猫さん、ありがとうございました。

ただ、試験で問われるのは、現実に適用・提案されている理論やアルゴリズムを正しく理解できているか？であって、
この方が望ましいという理論・アルゴリズムを推測する能力ではないと思います。

このスレッドを立てたのは、問14の解答がイとなる根拠はどこで確認できるか、それが確認できる参考書などあれば教えてほしい、
または私の増永本の理解が間違っていれば教えてほしかったからです。

確かな根拠を持ってイを選んだ方がいましたら、この点、ご教示いただければと思います。

お力になれず、残念です
英語wikiにもそれらしい記載はあったので、ちゃんと目を通してみてください
それほど難しい問題ではないので、理解できるといいですね

かなり難しい問題に踏み込んでおられて、正しく回答するにはDBを専門に学んだ院卒レベルの知識が要求される気がして自信がありませんが
増永本に書かれているMVCC(MVTO)アルゴリズムは
（コミットされていないx1をT2が読んでいるように)ダーティリードを許す実装になっています。
おそらく元の論文はどのトランザクションもロールバックされずにコミットされる前提になっていると思われます(Commited Projection)。

ロールバックがありうる現実のMVCCシステムでは、
上記の方法ではREAD COMMITEDは実現できないので
これを実現するためにSNAPSHOT ISOLATIONという方式が使用されます。
自トランザクションが開始した時点ですでにコミットされているデータのみ取得するというやつです。

SIがデファクトなので同一視してしまいがちですがMVCCとSIは別物で、
専門家はしっかりと区別しているので、
アルゴリズムの説明はSIベースで書いていないのでしょう。

なお、今回は問題文にREAD COMMITEDの指定が入った時点で、
MVCC実装のうちSNAPSHOT ISOLATIONが暗黙的に示唆されています。

[参考]
1)増永教授のDB特論⑧「MVCC」(@SRA OSS Tech Blog)
   SI, SSIに関する記述周辺
2)Making Snapshot Isolation Serializable再考 (@okachimachiorz はてなブログ)
   "前提1 MVCCとSIとではSIのほうが制限的である"周辺
3)MVTO(multi-version timestamp ordering) (@okachimachiorz はてなブログ)
   "最新のversionとは何か？" 周辺
4)急がば回れ、選ぶなら近道 TX記事 読解メモ (@ぱと隊長日誌)

横から失礼いたします。
ご解説ありがとうございます。
自分も本番で間違えて(イ)にしていたため、ご解説、大変参考になりました。
お三方と違い、難しい文献を調べていませんが、この問題で正解を得る方法は以下のように理解致しました。

問題文で「隔離性水準はREAD COMITTEDとする」と指定されているため、この問題では2PL、MVCCどちらの場合も、指定された隔離性水準を満たす必要がある。
トランPが更新した資源Xの値5は、トランPがコミット完了するまで、トランQが読めないようにする必要がある。

隔離性水準の観点で、選択肢のトランQの挙動を確認する。
(イ)(ウ)は、MVCCの場合に「Pのコミット完了を待機することなく、Xの値5を得る」とあり、隔離性水準を満たせない。NG。
(エ)は、2PLの場合に「Pのコミット完了を待機することなく、Xの値5を得る」とあり、隔離性水準を満たせずない。NG。
この段階で、正解は(ア)に絞られる。

2PLはそもそも、トランPがコミット完了するまで、トランQは資源Xのロック解放待ちとなり、資源Xを参照できない。
選択肢について、2PLの場合のトランQの挙動を比較する。
(ウ)(エ)は、2PLの場合に「Pのコミット完了を待機することなくXの値を得る」とあり、資源Xのロックが効いていない。NG。

MVCCの場合、トランPがコミット完了するまで、トランQは、トランQ開始時点のスナップショットを見て、Xの値を得る。
スナップショットに格納される資源Xの値は、トランQ開始時点でコミット済の4となる。
各選択肢について、MVCCの場合のトランQの挙動を比較する。
(イ)(ウ)は、MVCCの場合に「Pのコミット完了を待機することなく、Xの値5を得る」とあり、トランPのコミット完了前にトランQが得る資源Xの値が、スナップショットと異なる。NG。

トランPが資源Xの値を更新してからコミット完了する前に、トランQが資源Xを参照しようとすると、以下の挙動になる。
2PL：トランPがコミット完了するまで、資源Xを参照できない。トランPのコミットが完了すると、資源Xの更新後の値5を得る。
MVCC：トランPがコミット完了するまで、トランQ開始時のスナップショットから資源Xの更新前の値4を得る。トランPのコミットが完了すると、資源Xの更新後の値5を得る。

よって(ア)が正しい。失礼いたしました。

簡潔な回答ありがとうございます。腑に落ちました。
参考として紹介されたサイトを少し読ませていただきました。
「MVCC」がMVTOから派生した手法全般を指すこと、スナップショット隔離性なんて手法があることを初めて知りました。

問題文中にREAD COMMITEDを指定しているので、ダーティーリードを起こさない方のMVCCを想定して答えなさい、という出題の意図だと理解しました。
大変助かりました。ありがとうございます。

問題の解き方については、私もちょーさんと同じ理解をしました。
文末のMVCCの動作については、トランQは、トランPがコミットが完了しても、更新後の5を読まないのではと思います。
weizenさんが紹介された、増永教授のページでは「トランザクションは、開始された論理時刻の時点で有効なコミット済みデータからなるスナップショットから常にデータを読み取る」と説明されていますし、トランQの後半で更新後の値を読んでしまうと、アンリピータブルリードになってしまいます。
ちょーさんの意図とは違う読み方をしていたらすみません。

隔離性水準とMVCCアルゴリズムに直接の関係はありません。
read committedなら更新後の値を読むし、snapshot isolationなら読みません。
問14ではread committedなのでコミット後は5です。

すみません、自信がないので確認させてください。
「問14ではread committedなのでコミット後は5です」
という文章の意味ですが、MVCC(SI)で制御されている場合、トランQの実行中にトランPがコミットしたら、それ以降はトランQは自身の実行前のスナップショットでなく、Pがコミットして確定させた値を読む、という意味でしょうか。
そうとした場合、「反復不可能な読み」を許容するMVCCがある、という理解で正しいでしょうか。

MVCCならdirty readを許容するはずだ、MVCCならnon-repeatable readは発生しないはずだ、MVCCならsnapshot isolationのはずだ
これらは全てあなたの勝手な思い込みでありMVCCアルゴリズム一般に適用できる話ではありません。
snapshot isolationは関係ありません。問題文にread committedと指定されている事が全てです。
MVCC(read committed)だからdirty readは発生せずnon-repeatable readは起こり得ます。

増永教授のDB特論⑧「MVCC」(@SRA OSS Tech Blog) 3.1 SI の提案にPostgreSQLでの実装例が出ていますしリレーショナルデータベース入門第3版のp.321には隔離性水準とMVCCの関係が記述されています。
権威として名前を出すだけではなく、中身を読んでください。

紹介ありがとうございます。大変助かります。読んでみます。