papa本第13回参加メモ
- p40の4行目Supposeからp40のVariableまで(ほとんど進んでない)
- 後日議論なしで一言一句読み直すそうです。
Theory of Database Concurrency Control
- 作者: Christos Papadimitriou
- 出版社/メーカー: Computer Science Pr
- 発売日: 1986/07/01
- メディア: ハードカバー
- この商品を含むブログを見る
議論:VariableとFan-outの説明でif A then Bの順の説明の順序が食い違ってるのはなぜか
- Variable
- B:graph
- A:assignment
- Fan-out
- A:assignment
- B:graph
- Variableの文章は、"このようなグラフがあれば、このようなassingmentになっているはずである。"という文章になっている
Fan-outの文章は、"このようなassingmentであればこのようなグラフになっているはずである"という文章になっている。
Variable.
If the directed graph D includes the arc(bi,ci), we take this to mean that xi is true; otherwise (if, that is,(ci,ai)is in D),xi is taken to be false
- Fan-out
If xi is true--That is (bi,ci) is in D
- なぜこの順序を揃えていないのか。
- 同値なので順序はどうでも良い。
- if、ではなく,iffなら納得するのか
- 納得する
- DはNPの判定問題に置けるcertificateに当たる。
- assingmentでarcを選んだ後のP(F)
- 説明が下手なだけなのでは？それを持って正しくないとは言えない。
Dとs
- 任意のpolygraphからscheduleが作成できる。
- そしてpolygraphが
上記任意のPolygraphなのか？制約付きではないのか？という議論が発生した。
choiesの存在しないグラフは？
- choiseが空集合のpolygraphがacyclicなのは自明。
おさらい:polygraphの定義(p35,p36)
P=(V,A,C), where V is a finite set of vertices,
A⊂V * V is a set of arcs, and
C⊂V * V * V is a set of chosices. If(u,v,w)∈C,then the three vertices are necessarily distinct, and in fact (w,u)∈A.
今日の板書
