ぱと隊長日誌

ブログ運用もエンジニアとしての生き方も模索中

MCSR の conflict が r-w (read-write) だけなのはなぜなのか？

データベース

はじめに

MCSR (Multiversion Conflict Serializability) を知るには以下の本及び記事を読むのが最も理解に近づきます。

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

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

TX本 5.3.3 Multiversion Conflict Serializability

multi-versionの基礎 - 急がば回れ、選ぶなら近道

Multi-version Conflict Serializability - 急がば回れ、選ぶなら近道

MCSR - nikezono

ただ、これらの本・記事を読んでもなお、r-w が依存関係になる、つまり可換性 (commutativity) がない、という点はなかなか理解し難いです。そこで、本エントリではこの点に絞って解説を行います。

先に挙げた本及び記事は読んでいる前提とします。

step の交換による MCSR の判定

DEFINITION 5.10 Multiversion Reducibility
A (totally ordered) multiversion history m is multiversion reducible if it can be transformed into a serial monoversion history by a finite sequence of transformation steps, each of which exchanges the order of two adjacent steps, (i.e., steps p,q with p < q such that o < p or q < o for all other steps o) but without reversing the ordering of a multiversion conflict (i.e., rw) pair.

DEFINITION 5.11 Multiversion Conflict Serializability
A multiversion history m is multiversion conflict serializable if there is a serial monoversion history for the same set of transactions in which all pairs of operations in multiversion conflict occur in the same order as in m. Let MCSR denote the class of all multiversion conflict-serializable histories.

From what we have discussed above, the following theorems can be derived.

THEOREM 5.5
A multiversion history is multiversion reducible iff it is multiversion conflict serializable.

引用：TX本 5.3.3 Multiversion Conflict Serializability

オリジナルの multiversion history を隣り合う step の交換で serial monoversion history に変換できるのであれば、それは MCSR であるとしています。ただし、multiversion conflict pair である r-w は交換できません。

r-w がなぜ交換不可なのか、他の操作はなぜ交換可能なのかを確認していきます。

reads-from

TX本において MCSR の章 (5.3.3) の前までは history と同時に reads-from (RF, view) も与えられている (given) ことを前提としていました。

つまり、
w1(x1)c1r2(x1)r3(y0)w3(x3)w2(y2)c2c3
のような history で r2(x1) は w1(x1) の write した version を読んでいるし、それが変わることはない、という前提が置かれていました。

ですが、RF は後で自由に決めて良いと考えることもできます。

TX本の5章では以下の仮定を置いています。

An important assumption we will make in this chapter is that versioning is transparent to the outside world. In other words, users or applications will not be aware of the fact that data items can appear in multiple versions.
引用：TX本 5.1 Goal and Overview

ユーザ視点で version が見えない（指定できない）ということはスケジューラに version を決める裁量があるということです。

つまり、history における RF の定式化には以下の2つがあります。
(1) RF が一つ与えられている（かつ変わらない）
(2) RF は後で自由に決めて良い

具体的な例で確認します。
w1(x)w2(x)r3(x)
このスケジュールを multiversion (MV) で考えた時、
w1(x1)w2(x2)r3(x2)
と RF を決めたとします。
(1) の方式では r3(x2) を後から r3(x1) にすることを認めません。
(2) の方式では r3(x2) を r3(x1) としても構いません。
※ MV なので r3(x) は x1, x2 のいずれも read することができます。

TX本の MVSR では (1) を前提としています。これに対し、MCSR では (2) を前提としています。このことは明記されておらず、混乱を招くポイントとなっています。

なお、現実に (2) の方式を採用するのは困難に思えます。RF を後で決められるということは r(x) の段階で read する version を確定しないということです。ですが、r(x) が実行できたということは何らかの version を read したはずであり、それを後から変えるというのは現実的に実現困難と思われます。

equivalence

MV における equivalence とは View Equivalence のことです。

DEFINITION 5.5 View Equivalence
Let m and m' be two multiversion schedules such that trans(m') = trans(m). m and m' are view equivalent, abbreviated m ≈v m', if RF(m) = RF(m').
引用：TX本 5.3.1 Multiversion View Serializability

commutativity

commutativity（可換性）とは隣り合う命令ペアを交換したとしても、交換前後でスケジュール／ヒストリーが equivalent である操作のことです。先に引用した DEFINITION 5.5 より、RF を崩さなければ equivalent であるとわかります。

命令ペアを交換しても RF を維持できるか見ていきます。
なお、確認の対象は異なる transaction (TX) が同じ item に対する操作についてです。同じ TX 間で操作の交換はできませんし、異なる TX かつ異なる item に対する操作であれば常に交換可能です。

w-w (write-write)

以下のスケジュールを考えます。
wi(xi)wj(xj)rk(xj)

wi-wj を交換すると以下のスケジュールが得られます。
wj(xj)wi(xi)rk(xj)
MV ですので rk(xj) は実行可能です（1つ前のバージョンを読んでいるに過ぎない）。

よって、w-w は交換可能と分かります。

w-r (write-read)

以下のスケジュールを考えます。
wi(xi)wj(xj)rk(xj)

wj-rk を交換すると以下のスケジュールが得られます。
wi(xi)rk(xj)wj(xj)
wj(xj) が write する前に rk(xj) が read してしまいました。これではまずいので rk(x) がread する version を変更します。
wi(xi)rk(xi)wj(xj)
このスケジュールであれば成立します。

ですが、rk の read する version が xj → xi になってしまいました。これは RF を崩したことにならないのでしょうか？

実は問題ありません。

前提として、ユーザ視点では version が見えていないことを思い出してください。つまり、ユーザからは以下のスケジュールが見えていたはずです。
wi(x)wj(x)rk(x)
これにスケジューラが勝手に version を割り振ったにすぎません。それが冒頭のスケジュールである
wi(xi)wj(xj)rk(xj)
ということです。

つまり、スケジューラは rk(x) に別の version を割り振ることも可能ということです。なので、以下のスケジュールも可能です。
wi(xi)wj(xj)rk(xi)
このスケジュールで wj-rk を交換したのが以下のスケジュールです。
wi(xi)rk(xi)wj(xj)
これは先ほどの交換結果と同じになりました。

つまり、w-r の交換は可能と分かります。

繰り返しになりますが、このような version の再割り当てを現実で実現するのは困難でしょう。ですが、理論上は可能ということです。

r-w (read-write)

以下のスケジュールを考えます。
wi(xi)rj(xi)wk(xk)

rj-wk を交換すると以下のスケジュールが得られます。
wi(xi)wk(xk)rj(xi)

一見問題ないように見えますが、交換したことでもう一つのスケジュールの可能性が生まれました。それが以下のスケジュールです。
wi(xi)wk(xk)rj(xk)
rj(xi) が rj(xk) になっています。wk(xk) が先行しているので read することは可能です。

実はこの「もう一つのスケジュール」こそが問題なのです。

rj(xk) はオリジナルのスケジュールでは不可能です（wk(xk) の前に read しているため）。つまり、交換したがためにオリジナルにはない可能性が広がってしまいました。これでは RF が同じではなく、equivalent とは言えません。

MV なのだから rj-wk を交換しても rj(xi) のままでよいと考えるかもしれません。ですが、MCSRは「オリジナルの multiversion history を隣り合う step の交換で serial monoversion history に変換できる」ものでなければいけません。交換したスケジュールを monoversion で考えれば rj(xk) となります。つまり、交換後のスケジュールを monoversion で考えた時、equivalent でないとわかります。

これが r-w を交換できない (multiversion conflict pair) 理由となります。

ただし、他の交換操作と組み合わせれば r-w も交換できるケースがあります。
※以降、太字は次の step で交換する操作を示しています。
wi(xi)rj(xi)wk(xk)
wi(xi)wk(xk)rj(xi)
wk(xk)wi(xi)rj(xi)
このような交換を行えば monoversion でも equivalent になります。
私はこれが MCSR と MVSR の範囲の違いとして現れていると考えています。この後の実例でも確認します。

MCSR 判定の実例

TX本 Figure 5.2 より2例用いて MCSR の判定を行います。

(1)

MCSR である（つまり MVSR でもある）s4を例に考えます。

s4 = r1(x)w1(x)r2(x)r2(y)w2(y)r1(y)w1(y)c1c2

初期値とバージョンの割り当てを行います。その後、変換操作を行います。
w0(x0)w0(y0)r1(x0)w1(x1)r2(x0)r2(y0)w2(y2)r1(y2)w1(y1)
w0(x0)w0(y0)r1(x0)r2(x0)w1(x1)r2(y0)w2(y2)r1(y2)w1(y1)
w0(x0)w0(y0)r2(x0)r1(x0)w1(x1)r2(y0)w2(y2)r1(y2)w1(y1)
w0(x0)w0(y0)r2(x0)r1(x0)r2(y0)w1(x1)w2(y2)r1(y2)w1(y1)
w0(x0)w0(y0)r2(x0)r2(y0)r1(x0)w1(x1)w2(y2)r1(y2)w1(y1)
w0(x0)w0(y0)r2(x0)r2(y0)r1(x0)w2(y2)w1(x1)r1(y2)w1(y1)
w0(x0)w0(y0)r2(x0)r2(y0)w2(y2)r1(x0)w1(x1)r1(y2)w1(y1)

最終的に serial monoversion history (T2 → T1) を得ることができましたので、s4 は MCSR であるとわかります。

(2)

MCSR ではないが MVSR な s2 を例に考えます。

s2 = w1(x)c1r2(x)r3(y)w3(x)w2(y)c2c3

s2 は以下の通り MVSR であると判明しています（※TX本に記述あり）。
w1(x1)c1r2(x1)r3(y0)w3(x3)w2(y2)c2c3
これを参考に T3 → T1 → T2 な serial monoversion history へ変換を目指します。

w0(x0)w0(y0)w1(x1)r2(x1)r3(y0)w3(x3)w2(y2)
w0(x0)w0(y0)w1(x1)r3(y0)r2(x1)w3(x3)w2(y2)
w0(x0)w0(y0)r3(y0)w1(x1)r2(x1)w3(x3)w2(y2)
r2(x1)w3(x3) を交換したいのですが、r-w なので交換できません。よって、MCSR ではありません。今回は交換できたとして先に進めます。
w0(x0)w0(y0)r3(y0)w1(x1)w3(x3)r2(x1)w2(y2)
w0(x0)w0(y0)r3(y0)w3(x3)w1(x1)r2(x1)w2(y2)
w1(x1)w3(x3) を交換したことで、monoversion でみても正しいスケジュールとなりました。

このように、r-w の交換をしても最終的には RF の崩れない（そして MVSR になる）ケースがあるとわかりました。

新しいアイコンのお知らせ

小ネタ 道標 コミュニケーション

アイコンについて

Twitter アイコン（ぱと (@pato_taityo) | Twitter）を変更しました。

【変更前】
f:id:pato_taityo:20190202150100p:plain:w200
※元画像を紛失したので Twitter プロフィールより切り貼りしてます…。

【変更後】
f:id:pato_taityo:20190202150129j:plain:w200

アイコンはなつよさん（なつよ@インフラ女子の日常連載中 (@infragirl755) | Twitter）に描いていただきました。


ありがとうございました！

今後はこのアイコンを Twitter 以外でも利用していきます。

この機会に今回お願いした経緯等についてまとめておこうと思います。アイコンやイラストをイラストレーターに依頼したいと思っている方のちょっとした参考（良きにつけ悪しきにつけその一例として）になれば幸いです。

きっかけ

これまで利用していたアイコンはフリー素材から切り出したものでした。長く利用し、愛着があります。また、アイコンで覚えていただいている方もいらっしゃいました。ただ、いかんせんフリー素材ということもあり、自分を表現できるアイコンがほしいと常々考えていました。

そんな中、Twitter でアイコンをイラストレーターの方に描いていただいたよ！という方をお見掛けし、そんな方法もあるということを知りました。そこで、いつか気に入った画風かつ依頼を受けていただける方と出会えれば、ぜひ依頼したいと考えました。

…そんなことを考えて早数年。Twitter の TL でこんな tweet を見かけました。

ということはアイコンを依頼できるかもしれない。これは長年待っていたチャンスなのではないか…！とはやる気持ちを抑えつつ、なつよさんの scrapbox（INFRAGIRL NATSUYO WORK）にあるイラスト依頼方法や過去の作品例を確認したり、安易な気持ちで依頼しようとしていないかと自問自答をし、そのうえで Twitter にてお声がけさせていただきました。

なつよさんにお願いしたのは画風の好みはもちろんのこと、tweet から伝わる雰囲気、高専出身かつエンジニアという同じバックグラウンドを持つ者同士としての親近感なども決め手でした。

発注～納品までの流れ

今回は以下のような流れで進みました。

  • Twitter でお声がけする。
  • TL で用途や納期の確認など。
  • DM で詳細の打ち合わせ。
  • 下書きの確認。
    • 今回は事前にお願いしていたので見せていただくことができました。
  • 完成！

代金と納期

なつよさんの scrapbox のイラスト依頼受付に以下の記載があります（現時点での情報です）。

  • 修行中の身のため、アイコン作成の代金は特にいただきません
    • 気に入ったら Amazon の wishlist をぽちっと！
  • 納期は1～2週間

scrapbox でなつよさんの意向を把握していたので、事前に代金の話はあえてしないつもりでいたのですが、なつよさんから話題を切り出していただいたので、そのタイミングでこちらの思いも伝えさせていただきました。
代金については元よりお支払いする考えでいました。技術や時間を費やしていただくわけですから、その対価はお支払いしたいと考えていました。
ただ、なつよさんの意向も踏まえ、フリーで活躍されている方が受注する際の価格を参考にしつつ、金額設定が高くなりすぎないように…というところで選びました。

納期についてはかなり時間がかかるかもということでしたが、数年探したことを思えば時間がかかろうが構わないと考え、OKと回答させていただきました。

また、なつよさんには自分のペースで楽しんで描いていただきたい、と思っていました。そこで私の中で決めたことが2つあります。

  1. 御礼の前払いをしないことにしました。励みになればうれしいと思いつつ、完成時期へのプレッシャーになってほしくないとの思いから止めました。
  2. 完成時期について触れないように注意を払いました。待つと決めて一度伝えたからには、聞かれない限りこちらからは「いつでも大丈夫です」という言葉すら出さないようにしました。「いつでも」という言葉自体がプレッシャーになることを避けたかったからです。

イラストのインプット

scrapbox の記事から引用します。

  • 依頼者様からの画像（これをモチーフにします）
  • 私が抱く依頼者様のイメージ（bioや、どのようなジャンルでツイートされている方かなどを参考にします）

これらのやり取りは DM で行いました。

今回の依頼で私が特に気を付けていたのは以下の点でした。

  • ビジネスではなく、ご厚意で描いていただいていることを忘れない。
    • 修正依頼は原則としてしない。後から修正出来ない前提で考える。
  • お互いが満足できるものに仕上げたい。
    • 最終的なイラストのイメージをお互いに共有する。

なつよさんとは面識がないため、お互いのことをよく知りません。この状況下でも先に挙げた点を実現するため、なるべく多くのリソースを提供することにしました。

まず、簡単な自己紹介をしました。私の tweet は私の一面（技術やマネジメントなど）に限られるため、そこに現れない面も含めお伝えしました。

自分の写真の説明ではどんなところを周囲からよく褒められるか（例：笑顔）を伝えました。自分に自信がない私ですから、自分の良さを伝えることはものすごく恥ずかしいことでしたが、ここはえいやっと乗り越えました。

愛犬の写真の説明では愛犬との思い出をお伝えしました。

イラストに対する希望は詳細にお伝えし、そのうえで最終決定はお任せしました。例えば、過去の作品の中で私が特に気に入ったものをお伝えしたり、こだわりのある箇所については色指定をさせていただいたりもしました。

あと、過去の tweet なども参考にしました。


当初は似顔絵をリクエストしていたのですが、これを見て愛犬をモチーフすることを優先に方針転換しました。この2つを上手くフュージョンしてくださった結果が冒頭のイラストとなります。私も愛犬の雰囲気もとてもよく出ています。

振り返れば、どうでもいいような情報まで伝えすぎたな…迷惑だったんじゃなかろうか…と深く反省しているわけですが、それでも情報が足りないよりはよかったかなと思っています。不要なことは捨て置いてもらえればいいやと。

ふりかえり

お願いしたいと思える方に出会えるまで、とても時間がかかりました。でも、そんな方にお会いでき、また依頼できたことは本当にありがたいことだと思っています。時間をかけてよかったし、出会えてよかった。


この tweet を見た時は本当にうれしかったです。一緒に作品を作り上げたような気持ちになりました。私の貢献があったとしても1%程度でしょうが…それでも！

最後に、きっかけとなった tweet を再掲します。


私も自分の得意なこと・出来ることで活躍できるよう、これからも精進していきます！

トランザクション理論における polygraph と History の VSR 判定

データベース

目的

トランザクション理論における polygraph とは何かを説明し、それを利用して History の VSR (View Serializability) 判定に利用できることを示します。

略語

本エントリ内では以下の略語を使います。

  • TX本：Transactional Information Systems

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

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

  • Papa論文：The Serializability of Concurrent Database Updates

https://www.cs.purdue.edu/homes/bb/cs542-11Spr/SCDU-Papa-79.pdf

  • Papa本：Theory of Database Concurrency Control

Theory of Database Concurrency Control

Theory of Database Concurrency Control

  • Ullman本

http://infolab.stanford.edu/~ullman/dscb/vs-old.pdf
Database Systems: The Complete Book の "Materials from First Edition Deleted in Second" がPDFとして公開されています。

  • MVCC勉強会：Transactional Information Systems 5章 MVCC勉強会　第三回

Transactional Information Systems 5章 MVCC勉強会 第三回 - connpass

polygraph の定義

TX本から polygraph の定義を引用します。

A polygraph is a triple P = (V, E, C), where (V, E) is a directed graph and C ⊆ V × V × V is a set of choices such that (u, v, w) ∈ C implies u ≠ v, u ≠ w, v ≠ w, and (w, u) ∈ E.
引用：TX本 3.7.2 章

V = Vertex, 頂点
E = Edge, 枝・辺
C = Choices, ※直訳すれば選択肢

polygraph とは以下の定義ということです。

  • 異なる V の u, v, w があるとする。
  • (w, u) が E となる directed graph （有向グラフ）になる。
  • (u, v, w) で C を作る。

f:id:pato_taityo:20181223223416p:plain

TX本 Figure 3.6 で E は直線辺として表現されています。また、C を作るための (u, v), (v, w) は破線辺で表現されています。結果として直線辺1つと破線辺2つで C が作られます。
※「直線辺」「破線辺」は本エントリで独自に定義した用語です。

f:id:pato_taityo:20181223230354p:plain
引用：TX本 3.7.2 章

実は Figure 3.6 とほぼ同じ図がPapa論文 (FIG 2(a)) やPapa本 (Figure 2.4. (a)) でも登場しています。というより、発表年度から並べると、Papa論文(1979) ＜ Papa本(1986) ＜ TX本(2001) の順序であり、TX本の Figure 3.6 はPapa論文／Papa本のコピーといえます。

ここで注意すべき点として、Figure 3.6 には複数の u, v, w が存在しますが、同じ名前でもそれぞれ関係ないということです。各 V は独立しています。
これはPapa論文やPapa本を見るとわかります。Papa論文では各 V に対して v1 - v7 まで割り当てています。Papa本では名前さえついていません。このことから、各 V が独立しているとわかります。
u, v, w は先に引用した polygraph の定義と対応させるために名付けたものと思われます。

Figure 3.6 に対し、私は3つの疑問点を持っています。これらはまだ解消できていません。
説明に用いるため、Figure 3.6 の各 V に対して v1 - v7 を割り当てます。
f:id:pato_taityo:20181223231902p:plain

なお、本エントリの公開後に各疑問に対して デヴすぴスラ (@dev_supisula) さんがコメントしてくださいました。コメントを各疑問に追記させて頂きました。

【疑問1】

(v6, v4) の直線辺は何を意味しているのか？これはMVCC勉強会でも話題に挙がりました。
実はPapa論文に (v6, v4) の直線辺はありません。これが登場するのはPapa本からです。ですが、Papa本にもこれに関する説明はありませんでした。
MVCC勉強会では著者 (Christos H. Papadimitriou) の気まぐれなのではないか？という意見も出ていました。

デヴすぴスラさんのコメントです。

疑問1について：(v6,v4)という実線辺があってもそれを破線辺とするchoiceが無いわけではないよ、という事のために追加されたのでは。

https://twitter.com/dev_supisula/status/1077771808105852928

確かにその可能性がありそうです。
また、この例のように実線辺と破線辺が重なった場合、polygraph を history に適用するならば、(v5, v6, v4) の C は (v6, v4) で決まります。後程説明しますが、C の破線辺はどちらか一方を選択すればよいからです。

【疑問2】

TX本では C が4つあるとしています。これは (v1, v3, v2), (v5, v3, v4), (v5, v6, v4), (v5, v7, v4) のことと思われます。
ですが、C は他にも存在しうるように見えます。例えば (v1, v3, v4) です。なぜこれがカウントされていないかはわかりませんでした。

デヴすぴスラさんのコメントです。

疑問2：私も疑問でしたが後に出てくるヒストリから得られるpolygraphでも、reads-fromの実線辺とその他全ての頂点とのchoiceを考えているわけではなく（実線辺に対応するitemへの）writeを含むトランザクションしか考えていない。だから全ての頂点がchoiceになる訳じゃないよ、と示したかったのでは。

https://twitter.com/dev_supisula/status/1077772404036784128

『全ての頂点がchoiceになる訳じゃない』とコメントいただいた通りで、実線辺に対して C が必ず存在するわけではないことを示唆しているように思われます。特に (v4, v1) はその意図を感じました。
(v4, v1) の C を構成しうる (v1, v3), (v3, v4) は既に (v1, v3, v2), (v5, v3, v4) の C に含まれています。つまり、(v1, v3, v2), (v5, v3, v4) の破線辺が選択されれば (v1, v3, v4) の C は破線辺の選択の余地が無いことになります。後程説明する通り、C の破線辺はいずれかのみ選択されるためです。

【疑問3】

(v7, v6) が (v, v) となっています。
先に述べたように各 v は独立しているとはいえ、polygraph の定義と対応させるために名付けたとしたのであれば違和感があります。直線辺であることを踏まえると、(w, u) であるのが適切にも思えるのですが…？

デヴすぴスラさんのコメントです。

疑問3：(v7, v6) を実線辺とするchoiceをここでは考えていないからでは。

https://twitter.com/dev_supisula/status/1077772844224806912

疑問2と同様と考えています。

polygraph と directed graph の関係

polygraph と directed graph は compatible か否かを判定できます。TX本、Papa本共に compatible の定義を説明していますが、Papa本のほうが分かりやすいため、Papa本から引用します。

Suppose that P = (V, A, C) is a polygraph, and let D = (V, B) be a directed graph with the same set of nodes. We say that D is compatible with P if A ⊂ B, and for each choice (u, v, w) ∈ C either (u, v) ∈ A or (v, w) ∈ A. Polygraph P is called acyclic if there is an acyclic directed graph D that is compatible with P.
引用：Papa本 2.5 章

polygraph (P) と directed graph (D) が compatible であるかの判定は以下の通り行います。

  • P と D の Vertex が同じであること
  • P の Edge が D の Edge に全て含まれていること
    • P の破線辺（P では Edge として扱わない）が D では Edge になったりする
    • TX本では直線辺を "normal" edges、破線辺を additional edges と指している
  • 各 choice (u, v, w) の (u, v) もしくは (v, w) が D では Edge になること

Now a polygraph P is called acyclic if there exists a directed acyclic graph (DAG) G that is compatible with P.
引用：TX本 3.7.2 章

polygraph と compatible な directed acyclic graph (DAG) が存在すれば、その polygraph は acyclic と呼ぶとしています。

polygraph と compatible な graph は複数存在しうること、またそのうちの一つでも acyclic なら polygraph はacyclic と呼ばれることに注意してください。
TX本 Figure 3.7 はこれを表しています。いずれも Figure 3.6 の polygraph と compatible な graph ですが、左は cyclic、右は acyclic です。acyclic な graph があるので、この polygraph は acyclic といえます。

f:id:pato_taityo:20181223232239p:plain
引用：TX本 3.7.2 章

polygraph の単語の意味を調べると「うそ発見器」等と出てきますが、"poly-" は「多くの」等の意味を持つ連結詞（ランダムハウス英和大辞典　第2版）と理解したほうがよさそうです。polygraph と compatible な graph が複数存在しうることを "poly-" と表現していると思われます。

polygraph の History への適用

polygraph を transaction (TX) history に適用するためのルールを説明します。

Schedule と History の違いは以下の記事を参照ください。
History - nikezono

Our next goal is to associate a polygraph with a given history. To this end, we will assume for the remainder of this subsection that our history under consideration contains committed transactions only, and is equipped with initializing transaction t0 and final transaction t∞. Let s be a history such that trans(s) = T ∪ {t0, t∞}. The Polygraph P(s) = (V, E, C) associated with s is defined as follows:

1. V = trans(s)
2. E = {(t0, t) | t ∈ T} ∪ {(t, t∞) | t ∈ T} ∪ {(t, t') | t' reads some data item from t}
3. C = {(t', t'', t) | (t, t') ∈ E ∧ t' reads x from t ∧ some w(x) from t'' appears somewhere in s}

引用：TX本 3.7.2 章

V, E, C はそれぞれ以下のように割り当てられます。

  • V : history s 内のTX（t0 及び t∞ 含む）
  • E : 以下に該当する V 間に直線辺を引く
    • 1. t0 → 各 TX (t)
      • 初期状態 (t0) は全ての TX より前にあることを示している。
    • 2. 各 TX (t) → t∞
      • 最終状態 (t∞) は全ての TX の後にあることを示している。
    • 3. item x に値を書いた TX (t) → その値を読んだ TX (t')
  • C : choice は以下の V 間で作る
    • 1. item x に値を書いた TX (t) → その値を読んだ TX (t')
      • これが直線辺に相当する。
    • 2. item x から値を読んだ TX (t') → x に値を書き込んだ他のTX (t'')
    • 3. item x に値を書き込んだ他のTX (t'') → x に値を書き込んだ TX (t)
      • 2.3.が破線辺に相当する。

polygraph を用いた VSR 判定

polygraph を利用して history が VSR であるか否かを判定できます。

「item x に値を書いた TX (t) → その値を読んだ TX (t')」とは Reads-From (RF) の関係を表しています。

TX本 THEOREM 3.2 より 2つのスケジュールが View Equivalence であるということは RF も同じということです。今は polygraph を利用して VSR であるか否かを判定したいのですから、既存の RF の関係を壊してはならないとわかります。

同じ item の write - read の間に別の write が入ると、RF の関係が変わってしまいます。既存の RF の関係を壊さずに新しい write を挿入するには以下のいずれかを選ぶ必要があります。

  • write - read の前に write を挿入する (write - write - read)
  • write - read の後に write を挿入する (write - read - write)

これが polygraph の Choices として現れます。

f:id:pato_taityo:20181223223747p:plain

t1 が書いた値を t3 が読んでいます。この RF 関係が直線辺であらわされています。

同じ item に対し t2 が書き込んだとすると、RF 関係を崩さないためには以下のいずれかを選びます。

  • t1 の前に t2 が書き込む
  • t3 の後に t2 が書き込む

これが破線辺で示されています。

TX本では以下の history s が与えられています。
s = w0(x) w0(y) c0 r1(x) w2(y) w1(y) c1 r3(y) c3 w2(x) c2 r∞(x) r∞(y) c∞

これを polygraph であらわしたものが Figure 3.8 となります。

f:id:pato_taityo:20181223232331p:plain
引用：TX本 3.7.2 章

次に polygraph を compatible な directed graph に変換していきます。

polygraph から directed graph に変換する際に、Choices はいずれかの破線辺のみが Edge となります。なぜなら、両方存在するということは Graph が循環するということであり、トポロジカルソートできない、つまり TX の順序が決まらないということになるからです。

また、Choices に t0 もしくは t∞ を含む場合は以下の特別ルールが適用されます。Ullman本から説明箇所を引用し、次に解説を行います。

Suppose Tj is the source of a read ri(x), and Tk is another writer of X. It is not allowed for Tk to intervene between Tj and Ti, so it must appear either before Tj or after Ti.

（中略）

(a) If Tj is T0, then it is not possible for Tk to appear before Tj, so we use an arc Ti → Tk in place of the arc pair.

(b) If Ti is Tf, then Tk cannot follow Ti, so we user an arc Tk → Tj in place of the arc pair.

引用：Ullman本

(a) Choices に t0 を含む場合

f:id:pato_taityo:20181223225356p:plain

t0 を含まない Edge が選択されます。上図の場合、(t1, t2) が選択されます。
t0 は初期状態であり、ある history 内のトランザクションが t0 より前に存在しえないからです。

(b) Choices に t∞ を含む場合

f:id:pato_taityo:20181223225412p:plain

t∞ を含まない Edge が選択されます。上図の場合、(t2, t1) が選択されます。
t∞ は最終状態であり、ある history 内のトランザクションが t∞ より後に存在しえないからです。

これを踏まえて Figure 3.8 の polygraph から compatible な directed graph に変換した結果が下図となります。

f:id:pato_taityo:20181223225425p:plain

循環が存在し、VSR ではないと判定できました。

次にTX本の Figure 3.13 で VSR と示された history s4 を同じ手法で判定します。
初期状態 w0(x) w0(y) c0、最終状態 r∞(x) r∞(y) c∞ を追加します。

s4 = w0(x) w0(y) c0 w1(x) w2(x) w2(y) c2 w1(y) c1 w3(x) w3(y) c3 r∞(x) r∞(y) c∞

s4 に対応する polygraph を示します。

f:id:pato_taityo:20181224064932p:plain

(t3, t∞) の横に "x, y" と記載があるのは x, y の RF 関係による直線辺であることを示しています。よって、x もしくは y に write する TX はこの直線辺に対して Choices を検討することになります。これが破線辺で示されています。

なお、どの item に対する RF 関係なのかを直線辺に併記するアイディアは Ullman本 Figure 19.1, 19.4 から得ました。

この polygraph を compatible な directed graph に変換した結果が下図となります。

f:id:pato_taityo:20181224064948p:plain

循環がないため、VSR と判断できます。

どのような serial history と等価になるかは directed graph をトポロジカルソートすることで得られます。ここではトポロジカルソートに Linux の tsort コマンドを利用します。

# tsort << EOF
> t0 t1
> t0 t2
> t0 t3
> t1 t3
> t2 t3
> t1 tf
> t2 tf
> t3 tf
> EOF
t0
t2
t1
t3
tf

t0 → t2 → t1 → t3 → t∞ の serial history と等価であることが分かりました。

更新情報

2019/01/03

以下の置換を行いました。
P論文 ⇒ Papa論文
P本 ⇒ Papa本

Ullman本を「略語」セクションに移動しました。これに伴い一部説明を書き替えました。

Ullman本から特別ルールに関する記述箇所を引用しました。

デヴすぴスラさんからの本エントリに対するコメントとそれに対する私の意見を追記させていただきました。

E の初期状態及び最終状態からの直線辺について補足を追記しました。

2019/08/17

「polygraph の定義」セクションの【疑問2】に追記しました。