すぴすらのろぐ

読んだもののメモとかポエムとか

3-CNF SATからpolygraphのacyclicity判定問題への帰着

このポストは、papa本で証明されている「スケジュールsが与えられとき、それがview serializableであることのテストはNP完全である」の証明の一部を構成する、3-CNF SAT問題からpolygraphのacyclicity判定問題への帰着についてのメモです。

papa本は以下の本のことです。

Theory of Database Concurrency Control

Theory of Database Concurrency Control

証明の流れ

  1. スケジュールsがview serializableである iff polygraph P(s)が非巡回である (Theorem 2.4)
  2. polygraphが非巡回であることのテストはNP完全である(Theorem 2.5)
    1. 3-CNF Fが充足可能 iff polygraph P(F)が非巡回である(本ポストの内容)
    2. 3-CNF Fからpolygraph P(F)が多項式時間で構築できる
  3. polygraph Pが与えられたとき、「Pが非巡回である iff スケジュールsがview serializableである」ようなスケジュールsをPから構築できる(Lemma 2.4)
続きを読む

トランザクションの単位とhidden restrictions

このポストは、papa本読書会第1回目で読んだ範囲における、トランザクションの単位とトランザクション間のhidden restrictionsについてのまとめです。 議論としては2回目の内容も含んでいます。話題としては2回目の内容を含んでいます。ポストの内容は個人的なもので読書会の総意ではありません。

具体的には、こだわっているトランザクション間の依存関係の話です。

papa本は以下の本です。

Theory of Database Concurrency Control

Theory of Database Concurrency Control

トランザクションとは

papa本 p.5より:

A transaction is a sequence of database steps resulting from the execution of a program.

。ここでトランザクションのsyntacticな(?)定義をしていて、それはつまりプログラムから生成される具体的なdatabase stepの列である(database stepとは例えばentityに対するreadやwrite stepのこと)。

トランザクションとは

papa本 p.5より:

A transaction is a unit of consistency, a grouping together of several database steps, the combined execution of which is known to preserve the integrity constraints

。ここでトランザクションのsemanticな(?)定義をしていて、それはつまりconsistencyの単位である。 ここでのconsistencyとはintegrity constraintsの説明に出てくるconsistentのことで*1、つまりトランザクションとは、integrity constraintsを維持するdatabase stepsの列といえる。

トランザクション間のhidden restrictions

papa本p.5より:

A consequence is that there can be no "hidden restrictions" on inter-transaction behavior.

トランザクションがconsistencyの単位だという定義を受けて、トランザクション間のhidden restrictionsはないと結論付けている。

トランザクションX1とX2がある。 これらは一見、consistent stateを維持するとみなされている。 これらのトランザクション間には、X1→X2の順序でスケジューリングしてほしいというhidden restrictionsが存在する。

この場合、この本ではX1とX2はまとめて1つのトランザクションにすべきといっている:

For example, if correctness requires that steps from two "transactions" are executed in some predefined order, then these two "transactions" are in fact a single transaction.

解釈

これは以下のような解釈に基づいていると思われる。

  • トランザクション間にhidden restrictionsがあるということは、そうでない順序でスケジューリングされたら問題があるということだ。
  • それはつまり、そうでない順序で生成される結果がconsistent stateではないということだ。
  • その結果、X1、およびX2はそれぞれ単体ではトランザクションとはみなされない(integrity constraintsを維持しないから)。
  • よってここでのトランザクションはX1とX2を合成したものになる。

これをconsistency(integrity constraints)原理主義と呼ぼう。

consistency原理主義の何が問題か

上記の何を問題だと思うかというと、上記の例のトランザクションX1とX2によって生成される局所的なconsistent stateをアプリケーション(プログラマ)が定義できたとしても、原理主義が期待するX1、X2間の順序を含むconsistent stateをアプリケーション(プログラマ)が定義できないと思うからだ。

X1、X2の順序を含めた定義をするためには、(local)トランザクションの発行順序に影響のあるすべての要素を定式化する必要があり、それは結果的に世界のすべてを記述することになってしまうはずだ(と思う)。

また逆に、もし世界のすべてを記述できるとしたら、あり得る(local)トランザクションの発行順序はただ1つに決まってしまい、その場合、すべての(local)トランザクションを1つに合成したただ一つのトランザクションになってしまうことになるのではないか。

落としどころ

世界をシミュレートできない/決定的でない/予知できないという立場に基づくと、アプリケーションで定義可能な範囲をconsistent stateとみなすしかないと思われる。 その結果、やはりhidden restrictionsは生じてしまう。

前のポストでは、「トランザクション理論は、アプリケーションとデータベースが、consistencyとserializabilityの維持の役割を完全に分離したモデル」とか書いたが、アプリケーションは世界の記述をあきらめざるを得ない。そのためスケジューラは、アプリケーションがあきらめた分をhidden restrictionsの保証という形で守る必要がある。

トランザクション間のhidden restrictionsの定義

ここでトランザクション間のhidden restrictionsを、アプリケーションによって事前に定義された(期待される)、トランザクション間の半順序関係と定義することにする。

トランザクション集合を {T}としたとき、トランザクション間のhidden restrictionsを半順序関係{ R(x,y) \in T \times T, x,y \in T }とする。

スケジューラが出力する順序関係Sも同様に、{ S(x,y) \in T \times T, x,y \in T })とする。

スケジューラが全順序関係を出力する場合、{ R \subset S }となる必要がある。これがスケジューラに課される追加の仕事だ。


*1:consistency自体の用語の定義はないが、ここでいきなり分散処理の文脈のconsistencyは出てこないと思う(発行年的にも)

serializableとconsistent state

このポストはpapa本読書会第1回目で読んだ部分のうちのconsistent stateについてのメモです。p.8くらいまでの範囲です。

このポストではpapa本は以下の本のことです。

Theory of Database Concurrency Control

Theory of Database Concurrency Control

大学の図書館においてあったりします。研究目的なら大学等に所属していなくても図書館を利用できることが多いです。

Model

database

databaseは、entityの集合*1

entityの取る値は変化していくので、変数という理解でよいと思う。 構文上は、変数の値を見ている場合と識別子として見ている場合に特に区別がなかったので文脈で判断する。

不可分とか互いに疎とかの条件が付いている。

domain

entityごとに定義された、entityの取りうる値の集合*2

基本的には、DBのカラムのデータ型の取りうる範囲という認識でよいと思うが、アプリケーションに応じてさらに範囲が制限されたもの(ユーザ定義型)を指している可能性もある。

しかし後述のように、上記の違いはDBにとっては重要でない。

database state

すべてのentityのdomainの直積。

databaseの観点での取りうる状態の集合。

integrity constraints

database stateの部分集合。

アプリケーションとして正しい状態の集合。

状態がこの部分集合に含まれるとき、 consistent という。

transaction

トランザクションの実行が完了すれば、(かつ実行前の状態がconsistentであれば)、完了後の状態もconsistentである(ようにアプリケーションが責任をもってトランザクションを発行する必要がある)。

serializable と consistent state

このモデルでは、データベースの状態がconsistentであるかどうかの責任はすべてアプリケーションプログラムにある。

DBMS側は、与えられたトランザクションのconcurrency controlについては責任を持つが、何が正しい状態かについての知識は持っていない。

つまり、DBMSが常にserializableなスケジューリングを行うことと、アプリケーションプログラムが常にconsistentな状態からconsistentな状態へ遷移するようなトランザクションだけを発行することの両輪によって、データベース状態の正しさを維持していくという、完全に役割を分担した(美しい)モデルである。

この世界では、DBMSはデータベース状態に対する任意の制約を保証する機能を提供する必要はない。

つまり制約、例えば一意性制約や外部参照制約、を保証する機能をDBMSが提供しなくても、(スケジュールがserializableなら)アプリケーションプログラムはそれを自分で保証することができる。

DBMSが制約を提供する理由

しかし今の巷のDBMSは制約を保証する機能を持っているが、これは以下の理由ではないかと想像する。

  1. serializable分離レベルを提供していない、もしくは実用的でない
  2. アプリケーションプログラムで制約を保証することが可能だが、DBMSで行ったほうが実行効率が良い
  3. 一般的な制約(一意性等)を保証するためのロジックが共通になる結果、アプリケーションプログラムの共通機能がDBMS側にストアされるようになった

serializable分離レベルが実用的で当たり前の世界になった場合

上記の理由が正しければ、serializableが当たり前になったとしても、すべての制約の責任をアプリケーションが持つ世界には戻らなさそう。 (一度DBMSが面倒見てくれた仕事をアプリケーションは引き受けないのではないか)

所感

私は情報系DBをやっていたので、serializableの実現が厳しいならもう少し分離レベルを緩くすればいい、くらいの認識でしたが、アプリケーションとDBMSのきれいな役割分離を見て、serializableは良いものだなという思いがインクリメントされました。

制約については、正しい状態を保つことをもっとDBMSががんばったほうが良いのではと思っていたことがありましたが、そもそも理論上はすべてアプリケーションの責任だった(DBMSはアプリケーションロジックをすべて理解できないという位置に立っていた)ということで、がんばらなくてよいのだなと納得しました。

*1:countable set

*2:enumerable set

トランザクションとXのきもち

(このポストはトランザクションとは関係ありません)

トランザクションをTXと略すことがある。

これはtransactionを、同じ発音で読めるtranxtion(またはtranxaction)と書いたときの音節ごとの先頭文字をとってきたものである。

一方、トランザクションをXと略すことがある*1

これはtransactionをxactionと書いた時の先頭文字をとってきたものである。

ここでxはtrans-という接頭辞に対応していることになる。

同様の省略のされ方は他にもあり、例えば

  • 今流行りのDXはDigital Transformationの略(Transformation → Xformation)
  • 昔のPCのキーボードにあったxferキーは、おそらくtransferの略
  • C言語の標準ライブラリ関数のstrxfrmは、おそらくstring transformの略(transform → xform → xfrm)

なぜtrans-接頭辞をxと書くのかについて昔疑問に思ったときは、それを説明するサイトを見つけられなかった。

trans-という接頭辞の意味は、weblioによると、

「越えて」「横切って」の意、「貫いて」「通って」「完全に」の意、「他の側へ」「別の状態へ」の意、「超越して」、「…の向こう側の」の意

とのことだったので、当時は、彼我の位置を入れ替えるときの軌跡がXを描くからだ、と解釈した。 以下の図のイメージ。

f:id:dev_supisula:20190512010730p:plain

いまぐぐってみたところ、英語学習者向けのQAサイト?でHow did “trans-” become “x-”?という投稿を見つけた。

最初の回答に、「xはcrossのgraphical representation」とあるので、もっと単純に境界を超える、越境のイメージのようだ。

f:id:dev_supisula:20190512011312p:plain




おしまい

*1:PostgreSQLのXIDとか

NP完全性のメモ(1)

0. まとめ

0.1 P, NP, NP完全

計算複雑度のクラスP (complexity class P)とは、多項式時間で解ける問題の集合である。

計算複雑度のクラスNP (complexity class NP)とは、多項式時間で検証可能な問題の集合である。 問題を解くより検証の方が簡単なので、 P \subset NP まはた P = NP のどちらかである(が多くの研究者は  P \ne NP だと信じている)。

問題が以下の全てを満たすならば、NP完全 (NP-complete)であるという。

  1. その問題がNPに属する。かつ、
  2. NPに属するすべての問題に対し、多項式時間でその問題に帰着可能である場合。

NPに属する問題の中で、最も難しい問題からなる集合(NPの部分集合) がNP完全な問題である。

NP完全な問題はNPに属する他のどの問題よりも同じかより難しいので、もしもNP完全な問題の一つについて多項式時間で解ける(クラスPに属する)ことが証明できれば、NPに属するすべての問題が多項式時間で解ける ( P=NPである) ことが証明されるという強力なものである(だからこそ、 P \ne NP であると信じられている)。

0.2 NP完全性の証明

すでにNP完全であることが証明された問題があるので、それを利用して以下の2つを確かめることにより行う。

  1. 問題がNPに属することを証明する。
  2. NP完全であることが証明されている問題から(from)、対象の問題へ(to)多項式時間で帰着可能であることを証明する。

一つ目は対象の問題の難しさの上限を確認するもの(少なくとも検証は多項式時間でできる)、二つ目は対象の問題の難しさの下限を確認するもの(少なくともNP完全な問題よりは同じか難しい)である。


1. はじめに

NP完全性についての理解が怪しかったので、学生時代の教科書を(年末年始休暇に)引っ張り出して読み直しました。 以下の本「アルゴリズムイントロダクション 第3巻 精選トピックス」の第36章がNP完全性の章です。

アルゴリズムイントロダクション 第3巻 精選トピックス

上記の本は分冊版(全3巻)ですが、現在は原著第3版の翻訳(統合版)が出ており、こちらの第34章が該当の内容のようです(未確認)。

アルゴリズムイントロダクション 第3版 総合版:世界標準MIT教科書

以降は主に本の説明の流れに沿って用語の定義などをまとめています。見出しのタイトルは私がつけたものです。 元の第36章の各節のタイトルは以下です。

  1. 多項式時間
  2. 多項式時間の検証
  3. NP完全性と帰着
  4. NP完全性の証明
  5. NP完全問題

2. 準備

2.1 多項式時間を特別視する理由

多項式時間で解ける問題は、手に負える問題だとされている。これについて以下の3つの理由が記載されている。

  1.  n^{100} のような高い次数の多項式のオーダを必要とする実用的なアルゴリズムがほとんどない。
  2.  ある計算モデルにおいて多項式時間で解ける問題は、他の計算モデルでも多項式時間で解ける。
  3. 多項式が、加法、乗法、複合(composition)について閉じている(よい性質である)。

2.2 問題とは(問題の定義)

2.2.1 抽象的な問題 (abstract problem)

  • 抽象的な問題 Q とは、問題の事例 (instance) の集合 I と問題の (solution) の集合 S の間の2項関係のこと。
  • ある問題の事例が複数の解を持つこともありうる。

2.2.2 決定問題 (decision problem)

  • yesとnoの答えを持っている問題。
  • 解の集合 S \{0,1\} である問題で、ある問題の事例が解のどちらか一方にしか2項関係を持たない。
  • ある問題の事例の解がただ一つなので、決定問題は問題事例の集合 I から解集合  \{0,1\}写像する関数とみなせる。
  • 以降のNP完全性の議論では決定問題のみを扱う。

2.2.3 決定問題について考えることは有用なのか

  • 多くの問題は決定問題ではなく、むしろ 最適化問題 (optimization problem) である。
  • 典型的な焼き直し方は、最適化問題に限界値を導入し、例えば「ある値を最小化する(最適化)問題」を「最小値がk以下である解が存在するか、という(決定)問題」にするというものである。
  • 決定問題に焼き直したとしても、もし元の最適化問題が速く解けるなら関連する決定問題も速く解けるし、決定問題が手に負えないのであれば元の最適化問題も同様に手に負えないことが言える。
  • (よって決定問題を考えることも有用である、という主張)

2.2.4 問題の符号化 (encoding)

  • プログラムが理解できるように、抽象的な問題を表現する必要がある。
  • 抽象的対象物の集合 S符号化 とは、Sから2進文字列への写像 e である。
    • 2進文字列とは、0と1の2種類の文字だけから構成される長さ0以上の文字列。
    • 以降では、長さ0以上の2進文字列は  \{0,1\}^* のように表現しています。
    • 符号は2進文字列でなくても良いが、2つ以上のシンボルによる符号化の必要がある。
      • 1進文字列だと計算の難しさが変わってくるとのこと(1進についての説明は省略)。
  • 問題の符号化にはいくつかの(いくつもの)バリエーションが考えられるが、どれを利用するかは問題が多項式時間で解けるかどうかには影響を与えない。
    • これには条件があり、符号化自体が多項式時間で計算可能である必要がある。
    • 標準的な符号化が自明でなく、符号化によって違いが生じるような問題も起こりうるので注意する必要があるとのこと。
    • 任意の入力 x に対して出力 f(x)を作り出す多項式時間のアルゴリズム A が存在するとき、関数は 多項式時間で計算可能 (polynomial-time computable) という。
    • 問題事例のある集合 I の任意の問題事例 i に対して、 f_{12}(e_{1}(i)) = e_{2}(i) かつ f_{21} (e_{2}(i)) = e_{1}(i) であるような多項式時間で計算可能な2つの関数が存在するとき、2つの符号化 e_1 e_2多項式的に関連している(polynomial-related) という。
    • 2進文字列の符号化と3進文字列の符号化は多項式的に関連しているので、どちらの符号化を利用しても問題が多項式時間で解けるかどうかには影響を与えない。

2.2.5 具体的な問題 (concrete problem)

  • 問題事例の集合が2進文字列の集合であるような問題を 具体的な問題 と呼ぶ。
  • 以降の議論では、具体的な問題だけを扱う。
    • 抽象的な問題事例に対応付かない2進表現がありうるが、それらは(簡単のため)解の0に写像されると仮定している。

2.3 多項式時間

  • 長さ  n=\lvert i\rvert を持つ問題事例 i に対し、アルゴリズムがその解を高々 O(T(n))時間内で作り出すことができるならばそのアルゴリズムは具体的な問題を O(T(n))時間で 解く (solve) という。
    •  T(n)nについての何らかの関数
  • 具体的な問題に対して、ある定数 k があり O(n^{k})で解くアルゴリズムが存在するならば、その問題は 多項式時間で解ける (polynomial-time solvable) という。
  • 計算複雑度のクラス P (complexity class P)を、多項式時間で解ける具体的な決定問題の集合と定義する。

2.4 形式的言語への対応

  • 決定問題は形式的言語として表現することができる

2.4.1 形式的言語の簡単なまとめ

  • アルファベット (alphabet)  \Sigmaはシンボルの有限集合である。
  •  \Sigma上の 言語 (language) は  \Sigma に属するシンボルからなる任意の文字列の集合である。
  • 空文字列 (empty string) を  \epsilon で表す。
  • 空言語 (empty languate) を  \phi で表す。
  •  \Sigma上のすべての文字列からなる言語は \Sigma^*で表される。
    • 例えば \Sigma = \{0,1\} なら、 \Sigma^{*} = \{ \epsilon, 0, 1, 00, 01, 10, 11, 000, ... \} である。
      • 通常、言語というときは  \Sigma^{*}のようなすべての組み合わせ指しているのではなくその一部だけ( \Sigma^{*}の部分集合)を指す。

2.4.2 決定問題と形式的言語

  • 決定問題 Q を形式的言語L に対応付けることができる。
  •  L = \{  x \in Σ^* : Q(x) = 1 \} 、つまり解が1となる問題事例の集合を言語Lとする。

2.4.3 形式的言語と計算複雑度のクラス

  • 入力文字列  x \in \{0, 1\}^* に対して問題を解くアルゴリズムA A(x) = 1を出力するとき、アルゴリズムAはその文字列 x受理する(accept)という。
  • アルゴリズムAによって受理される(accepted)言語とは、 L = \{ x \in \{0, 1\}^* : A(x) = 1 \} 、つまりアルゴリズムAによって受理される文字列の集合である。
    • これにより決定問題Qとそれを解くアルゴリズムAの関係を表現できた、とのこと。
  • ある言語がアルゴリズムによって受理されるとしても、その言語に含まれない文字列を却下するとは限らない。
    • 言語に含まれない文字列を与えると無限ループに陥る可能性等。
  • もし任意の(2進)文字列があるアルゴリズムによって受理されるか却下されるかのどちらかであれば、言語Lはそのアルゴリズムによって決定される(decided)という。
  • 長さ nの言語 L上の文字列 x \in Lに対し、アルゴリズム x O(n^{k}) 時間で受理するとき、言語 Lアルゴリズム Aによって多項式時間で受理される(accepted in polynomial time)という。
  • 同様に、アルゴリズム x O(n^{k}) 時間で正しく決定するとき、言語 Lアルゴリズム Aによって多項式時間で決定される(decided in polynomial time)という。
    • いずれも kは定数。
  • 以上を踏まえて計算複雑度のクラスPを(別の)定義すると、 P = \{ L \subseteq \{0, 1\}^* : Lを多項式時間で決定するようなアルゴリズムが存在する \}
    • 計算複雑度のクラス(complexity class)とは、与えられた文字列xが言語Lに属するかどうかを決定するアルゴリズム計算複雑度の測度(complexity measure)によって、属することが決定されるような言語の集合のこと、らしい。
  • さらに、Pは多項式時間によって受理される言語クラスということもできる。
    • 多項式時間で受理できるならば、多項式時間で決定できることが証明できる(証明は省略)。

3. 検証と NP

3.1 検証アルゴリズム

  • 多項式時間で決定するアルゴリズムは知られていないが、検証が簡単な問題がある。
  • 検証アルゴリズム(verification algorithm)とは、通常の入力の文字列 xである引数と、証明書(certificate)と呼ばれる二つ目の2進文字列 yを引数にとるアルゴリズム Aのことである。。
  • もし A(x,y) = 1であるような証明書 yが存在するなら、アルゴリズム Aは文字列 x検証する(verify)という。
  • 証明書が存在する文字列 xによって構成される言語を、検証アルゴリズム  Aによって検証される言語(the language verified)という。
    • 検証アルゴリズム Aによって検証される言語 Lにおいて、入力文字列 x \notin Lに対して A(x,y) = 1となるような証明書 yがあってはならない。
      • 定義より、この入力文字列は Lに含まれているはず。

3.2 計算複雑度のクラスNP

  • 計算複雑度のクラスNP(complexity class NP)は、多項式時間アルゴリズムAによって検証される言語のクラスである。
    • 条件として、証明書yの大きさが入力xの大きさの多項式サイズである必要がある。
  • このときアルゴリズムAは言語L多項式時間で(in polynoial time)検証する(verify)という。
  •  L\in Pならば L\in NPである。
  •  P=NPかどうかは知られていない。
    • であるが、ほとんどの研究者は P \ne NPと信じているとのこと。

3.3 計算複雑度のクラスco-NP

  • 計算複雑度のクラスco-NP(complexity class co-NP)は、 \overline{L} \in NPであるような言語Lの集合である。
    •  \overline{L}Lの補集合で、 \overline{L} = \Sigma^{*} - Lである。
      • つまり言語Lで受理されない入力文字列の集合。
  • NPが補集合に関して閉じているかどうかがまだわかってない。
    • 言い換えると、 L\in NP \overline{L} \in NPを意味するかどうか。

トランザクションの参照透過性&副作用およびHerbrand Semanticsについて

トランザクションの参照透過性と副作用

前回のポストでは、関数の参照透過性と副作用について書きました。

本ポストでは、(データベースにおける)トランザクションの参照透過性を以下のように定義する。

また本ポストでは、(データベースにおける)トランザクションの副作用を以下のように定義する。

この定義によると、トランザクションとデータベースの間の界面がトランザクションの主たる界面(副ではないという意味で)となる。

Herbrand Semanticsとは

Herbrand Semanticsとは、トランザクションが何を引き起こすか、トランザクションのその意味をモデル化する方法である。

TIS(Weikum本)のDefinition 3.3では、ステップについてのHerbrand Semanticsが次のように定義されている。

DEFINITION 3.3 Herbrand Semantics of Steps

Let s be a schedule. The Herbrand semantics Hs of steps ri(x), wi(x) ∈ op(s) is recursively defined as follows:

  1. Hs(ri(x)) := Hs(wj(x)), where wj(x), j ≠ i, is the last write operation on x in s before ri(x).
  2. Hs(wi(x)) := fix(Hs(ri(y1)),..., Hs(ri(ym))), where the ri(yj), 1 ≤ j ≤ m, represent all read operations of ti that occur in s before wi(x), and where fix is an uninterpreted m-ary function symbol.

Weikum, Gerhard; Vossen, Gottfried. Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems) (ページ74). Elsevier Science. Kindle 版.

これは以下のように解釈できる。

Definition 3.3に続く文章では、スケジュール内の全てのトランザクションに先行する(各data itemの初期値をwriteだけする)特別なトランザクションt0によって書かれたという考え方を取り入れている。これによりfixを展開していくと、各data itemの値は最終的には、関数fixの組み合わせだけに還元できる。

Herbrand Senanticsにつては以下も参考になります。

Herbrand Senanticsと参照透過性

TISのDefinition 3.3 Herbrand Senantics of Steps を見る限り、この定義におけるトランザクションには参照透過性がある。言い換えると、参照透過性があるトランザクションを一見、前提にしているように見える。

Herbrand Senanticsにおける副入力の解釈

例えば銀行口座間の送金トランザクションを考えると、2つの口座番号と送金金額はプログラム上はパラメタライズされており、外部から与えられた情報をもとにして初めて実体化される。

この外部からの入力は、参照透過性の観点における副入力に他ならないのではないかという疑問が湧く。 しかしこれは以下のように解釈できる。

このように考えると、すべての副入力はトランザクションのロジックと区別がつかなくなり、トランザクションに副入力は存在しないことになる。

トランザクションの副作用

トランザクションの作用はdata itemへのwriteであり、それ以外は副作用と見なすと定義した。

データベース管理システムで実行されるトランザクションは応答を返す。 応答が観測されるなら、これは副作用になり得る。

トランザクションの実行モデル

トランザクションが実行されるモデルとして以下の3つを考える。

  1. すべてのトランザクションが投入され終わらない限り、いずれのトランザクションの応答も返ってこないモデル。
    • すべてのトランザクションが投入されてから初めて、実行がスケジューリングされるモデルと見なせる
  2. 1つのトランザクションがまとめて一度だけシステムに渡され、一度だけ応答を返すモデル。
    • One-shotモデル?
  3. 1つのトランザクションにつき複数回のやり取りを許すモデル。

これらのうち1つ目のモデルでは、あるトランザクションの応答を別のトランザクションが参照することがないため、副作用はないものと見なせる。

一方残りの2つのモデルでは、他のトランザクションの応答を観測しうるので、このモデルにはトランザクションの副作用が存在し得る。

異なるトランザクションの間に外部の依存関係があった場合

あるトランザクションXの(完了)応答が、別トランザクションYの振る舞いに影響を与えている場合を考える。

例えば、ある送金トランザクションXの実行結果によって、別の送金トランザクションYの金額や送金差先が変更されるような状況である。

このときXの応答は別のトランザクションの振る舞いに影響を与えている(観測された)ので、これは明らかに副作用である。 (一方、先の議論で、トランザクションの参照透過性を脅かす副入力は存在しないことになっている。)

このようなトランザクション間の外部の依存関係はトランザクションマネージャには捕捉されないので、トランザクションマネージャは、Y→Xというような順序付けを行う可能性がある。

これは外部の依存関係を知る者にとっては明らかに誤りだが、トランザクションマネージャは何らかのserial scheduleとequivalentだと判断したはずである。

Herbrand Semanticsにおける副入力の扱いを踏まえると、以下のような状況である。

もし実際の順序がY<S>X<T>であったなら、パラメタSBにはなりえなかった。つまりこの順序の場合、Y<B'>X<A>である。一方、実際はX<A>Y<B>である。

まとめると以下のような状況になる。

trans() \ 順序 X→Y Y→X
{X<A>,Y<B>} ①あり得る ②あり得ない
{X<A>,Y<B'>} ③あり得ない ④あり得る

トランザクションマネージャは②を選択したが、①と比較すれば順序付けが誤っていたと見えるし、④と比較するとequivalentだと思ったスケジュールのトランザクション集合が実は異なっていたと見える。

外部の依存関係を許すか

上記のような外部の依存関係を許さないシステムが多かったのではないかと想像します。

一方で、DBMSがUDFに対して参照透過性や副作用が無いことを要求するのとおなじように、アプリケーション/トランザクションにそれを要求できるかというと難しいと思われる。

なぜなら、通常UDFが触れている世界とDBMSの世界ではDBMSの扱う範囲の方が広く、だからDBMSはUDFに「必要なものはすべて私が与えるからそれ以外の界面でやりとりするな」という主張に納得できる部分もあるが、DBMSの世界よりアプリケーションが触れる世界の方が大きいから、DBMSがアプリケーションに「必要なものはすべて与える」という主張は滑稽に見える。

しかしこれも、データベースの性質によっては言えるかもしれない。 例えば以下のご本尊系データベースの場合。

トランザクションの単位

上記のような依存関係があるなら、別のトランザクションにするのではなく、1つのトランザクションにすべきだ、という主張が考えられる。

しかし一般にトランザクションの単位とはなにか、というとそれは永続化のatomicity、および分離のatomicityの単位と認識されているのではないか。依存関係のスコープを表す手段としてのトランザクション、という考え方は一般的ではないのではないか。

この問題の回避

外部の依存関係は実時間の流れる方向にしか発生しないはずだ。

だから、one-shotモデルの場合は既存のプロコトルに以下の制約を付け加えればよい。

ー Tx < Ty | cx < by の場合。ここでcxはトランザクションTxの完了応答時刻で、byはトランザクションTyの到着時刻

この制約は、トランザクションに(分散処理の文脈における)consistencyを導入することに対応するはずだ。

再びHerbrand Senantics

TISのp.73のIdea of Herbrand Senanticsは次のように書かれている。

  1. a step wi(x) ∈ s writes a new value that potentially depends on the Idea of Herbrand semantics values of all data items that ti has read from the database or from other transactions in active(s) ∪ commit(s) prior to wi(x).

強調部分を読むと、副入力を想定しているようにも見える。しかしこれがdefinition 3.3になると、データベースとの入出力だけに限定されているように読める。

その他

トランザクションの副作用を考えたとき、対話型モデルではステートメント毎の応答が他のトランザクションに影響を(isolationを無視して)及ぼしうる。

またone-shotモデルでも、abort応答が他のトランザクションの振舞いに影響を与えるかもしれない。

これらはどう扱えばよいのか…。

 関数の参照透過性と副作用についてのメモ

概要

プログラミング言語やUDF機能を提供するシステムにおいて関数が持っていると嬉しい性質として以下の2つがある。

  • 関数の返す値は、関数の引数に与えた値だけに依存して決まる(参照透過性がある)。
  • 関数は、値を返す以外の作用(副作用)を行わない(副作用がない)。

上記の2つの性質を持つ関数は、関数の処理系のコンパイラオプティマイザによって最適化することができる。 例えば、

  • 関数の引数が定数の場合、その関数の値(計算結果)をコンパイル時に決定できるので、実行コードにおける関数の呼び出しをなくすことができる。
  • 同じ関数に同じ引数を与えている箇所があれば、2回目以降の関数の呼び出しをなくし、1回目の関数の計算結果に置き換えることができる。

関数に参照透過性がない場合

同じ関数に同じ引数を与えたとしても同じ結果を返すとは限らないため、コンパイラオプティマイザはその結果を事前計算orキャッシュすることができない。

参照透過性がない関数とは例えば、システム時刻を返す関数であったり、乱数によって振舞いを変えたり、通信やIO等の外部からの入力を利用したりするものである。

関数に副作用がある場合

副作用がある関数とは、例えば関数の実装の中でログに出力するような関数である。

そのため最適化によって関数呼び出しが削除されてしまうと、残るべきログが残らないという事態が起こる。

参照透過性と副作用のイメージ

関数の引数(INPUT)と、関数の計算結果(OUTPUT)による界面(インターフェイス)を通常と考えると、それ以外の界面からの入力があると参照透過性を脅かし、それ以外の界面への出力があると副作用となりうる。

参照透過性と副作用の関係

両者は独立して存在しうる。

参照透過性があるが副作用を持つ関数も存在するし、副作用はないが参照透過性がない関数もありうる。

参照透過性と副作用は本当に独立か?

副作用がない関数がありうると書いたが、実際には何を副作用とみなすかは程度問題である。

ログ出力は典型的な副作用であるが、ログが最適化で省略されても問題ないのであれば、その副作用は無視できる。

また世の中にはサイドチャネル攻撃というものが存在するので、ふつうに考えて副作用がないような関数も、同じコアで同時実行される別のスレッドのスケジューリングやCPUの電力消費や電波の輻射等の形で外部に影響を与えるため、これを副作用とみなすこともできる。

その意味で副作用とは、その副作用を観測するものの存在ぬきでは語れない。

参照透過性のない関数は、そのような副作用を観測するものの一つである。