papa本第9回参加メモ

• 前回7回
• 8回は休止
• 今回9回

p34「Proof」からp38「proof」まで読んだ。次回は「Theorem2.4」から

メインの内容としてpolygraphとVSRのNP完全の証明を読んだ。

雑なノートです。人が読めるように整理していないので読まないでどうぞ。

Theory of Database Concurrency Control

full interpretation

定義

legal

We say that s is legal for I and X if for each transaction A of s and each predicate P in SA the following holds:Transaction A corresponds to a path of Sa which , for each predicate P of Sa, takes the left branch at P if xxxxxx, and the right branch otherwise where the vis are the read steps which precedeP in A, and p is the interpretation of P. (p33)

PI

permutationを並べる写像？

Let Pi :{A,A2,...,An} ⇨ {A1,A2,...,An} be a permutation of the transaction in s,

Theorem2.3の証明

• よくわからん
• Not Theorem2.3の状態でFSR出ない状態が作れる⇨待遇を示している？
• Full interpretationの定義が貧相では？
  • １階の述語にしか対応していない　

VSRのComplexity

• m!n²のnは何か？
  • step数？
  • freeschemaの高さ？
  • interpretationの数？
  • viewの数
• FSRのNP完全
• NP完全：なぜ難しいか説明できないから難しい。
  • NP完全:効率的なアルゴリズムが存在しない、という意味ではない。

• Polygraph:poly=複数の(ギリシャ語),graph=グラフ

• p36AとB真部分集合なのか？

  • choiseが一つもなければ真部分集合
  • ここでは特に重要ではない。

• step graphではなくtransactionのグラフ

• Lemma2.2はacyclicではなく、total orderになる。

• write skewは循環
• 順序(order theory)からの拡張にacyclicを使いたくない。
  • orderの概念とgraphの概念を混ぜるな危険。

• order theoryにはtotal orderはもう言わない。partial orderのliner extensionという話で同等の概念を扱う

  • 出来上がったtotal orderはどうでもいい。
    • total orderを作るための理論の研究が盛ん。

• トポロジカルソート可能=Serializableはやや強引。