DB　第10章　同時実行制御

単語カード

設定全面表示

• アプリケーションにおけるひとまとまりの処理を表すデータベース操作の集まり

  トランザクション
• トランザクション同士の競合や各種障害の発生が起因する問題が生じないようにトランザクションの実行を行うこと

  トランザクション処理
• transaction processing のもう一つの呼び方

  トランザクション管理
• 原始性、整合性、隔離性、耐久性の性質をまとめた特性

  ACID特性
• アクティブ、コミット処理中、コミット済み、アボート処理、アボート済みの総称

  トランザクションの状態
• アボートされるトランザクションがアクティブな状態の間に何らかのデータ更新を行っていた場合には、それらすべてを取り消したデータベースをトランザクション開始前の状態に戻さなくてはならない

  ロールバック
• いったんコミット済みとなったトランサクションは、その処理内容にかかわらず取り消すことはできない。したがって、誤った値でデータを更新してしまったような場合には、その値を正しい値に書き換える別のトランザクションを実行する必要があるトランザクションのこと

  補償トランザクション
• 例）データの更新の喪失や整合性のないデータの読み出し これらの不整合は、ACID特性の隔離性の要求に反するような順序で基本操作を実行したことに起因する。このような不整合が生じないように制御すること

  同時実行制御
• 不整合が発生しないための一つの基準は、トランザクションＴ₁,...,Tnを並行処理した時の実行結果が、それらを何らかの順序で逐次処理した時の実行結果と一致すること

  直列可能性
• 直列可能性に関して、より厳密な議論を行うための概念

  スケジュール
• 対象トランザクション群を何らかの順序で逐次処理する場合のスケジュール

  直列スケジュール
• 直列スケジュール以外のスケジュール

  非直列スケジュール
• スケジュールのうち直列スケジュールと「等価」なもの

  直列可能スケジュール
• 競合等価もしくはビュー等価であるかどうか

  等価性
• 競合する基本操作の実行順序が同じである

  競合等価
• 各readが同じ値を読み最終的なデータベースの状態が等しいこと

  ビュー等価
• スケジュールがある直列スケジュールと競合等価なとき

  競合直列可能
• ① Sに参加する各トランザクションTiに対してノードN（Tj）を作成する。 ② Ri(A)(Wi(A))がWj(A)(Rj(A))に先行するとき、有向エッジN(Ti)→N(Tj)を引く ③ Wi(A)がWj(A)に先行するとき、有向エッジN(Ti)→N(Tj)をひくの手順で作成できるもの

  先行グラフ
• スケジュールＳにおいて、「Ri(A)で読まれるA値がWj(Ａ)によって書かれた値であり、TiがコミットするときにはCjがCiに先行する」という条件が常に満たされるとき

  回復可能
• あるトランサクションのアボートに伴いほかのトランザクションのアボートが引き起こされること

  連鎖的アボート
• スケジュールＳにおいて、「Ri(A)またはWi(A)よりもWj(A)が先行するときには、CjまたはAjがそのままRi(A)またはWi(A)に先行する」という条件が常に満たされるとき

  厳格
• 共有ロック

  Ｓロック
• 専有ロック

  Ｘロック
• 実際のDBMSにおける同時実行制御では、何らかの機構と規約を用いて並行処理における問題の解決を行う。このような機構として最も一般的なもの

  ロック
• すでにかけている共有ロックを専有ロックに変更する操作

  ロックのアップグレード
• すでにかけている専有ロックを共有ロックに変更する操作

  ロックのダウングレード
• ロックをかける操作と解く操作に関する規約

  ロッキングプロトコル
• 実行中のトランサクションがロック操作を成功するまで待ち状態となってしまう状態のこと

  デッドロック
• 競合直列可能性を保証するロッキングプロトコル.各トランザクション中のロック操作がロックをかける操作だけからなる成長相（growing phase）とロックを解く操作だけからなる縮退相（shrinking phase）の二つの部分に分離されなければならないという規約

  二層ロッキングプロトコル　2PL
• 各トランザクション中のロック操作がロックをかける操作だけ

  成長相
• ロックを解く操作だけ

  縮退相
• 二層ロッキングプロトコルにおいて、「縮退相における最初のロックを解く操作はトランザクションのコミットまたはアボート操作の後である」という条件と付け足したもの

  厳格な二層ロッキングプロトコル
• データベース中の項目を木構造に構成。複数の項目をアクセスするトランザクションは木のルートからリーフに向かってデータをアクセスする

  木ロッキングプロトコル
• ある項目Ａの下位の句重くＡ‘をアクセスする際、Ａの下位の項目を共有あるいは専有の目的でアクセスしていることを知らせるためのロック

  インテンションロック
• デッドロックは起こり得るものとして、起きた場合にそれを検出し解消するというアプローチ

  デッドロックの検出
• デッドロックを発見した場合サイクルを構成するトランザクションのいずれかを犠牲者としてアボートすることでデッドロックを解消する

  待ちグラフ
• Lもし、その時点で一つもロックをかけられない項目がある場合はいずれの項目へのロックを行わず、しばらく待った後の見に再度ロック操作を試みる。この規約と二層ロッキングプロトコルを組み合わせたもの

  保守的2層ロッキングプロトコル　保守的2P
• TS(Ti)<TS(Tj)のときTiはTjがAのロックを解くまで待つ 　TS(Ti)>TS(Tj)のときTiはアボートする

  wait-die方式
• TS(Ti)<TS(Tj)のときTjをアボートさせる 　TS(Ti)>TS(Tj)のときTiはTjがAのロックを解くまで待つ

  wound-wait方式
• 各トランザクションに発生順に一意的な時刻印を与え、その時刻印の順にトランザクションを逐次実行する場合と等価なスケジュールが生じるように制御を行う方法

  時刻印順方式
• Read, write操作の規約に従って行う基本的な方法

  基本時刻印順方式
• 基本時刻印順方式で生じる連鎖的アボートなどの問題を防ぐための厳格な方法

  厳格な時刻印順方式
• TS(Ti)>=RTS(A)かつTS(Ti)<WTS(A)のときTiはwriteの時機を逸してしまっているが、そのことによるデータベースおよび他のトランザクションへの影響はないので、Tiはこのwrite要求を無視して処理を続行する。という規約

  トマスの書き込み規則
• 他のトランザクションとの競合はないものとして実行し、終了時に競合の有無を確認する制御方法

  楽観的同時実行制御
• 版を利用した同時実行制御の方法

  多版同時実行制御

広告

コメント