ぱと隊長日誌

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

トランザクション理論における 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】に追記しました。