ボンジュール・マドモアゼル

本サイトの情報は自己責任にてご利用下さい。

[用語] 参照透過性と冪等(べき等)性

 
※ 2012-11-16 書き直しました。

等価ではない。
冪等性は関数の特質であり、参照透過性は言語の特質。

Wikipedia 参照透過性

冪等は副作用が有り得る。

次はRFCによる冪等性の定義。
9.1.2 Idempotent Methods

Methods can also have the property of "idempotence" in that (aside from error or expiration issues) the side-effects of N > 0 identical requests is the same as for a single request.
RFC2616 Hypertext Transfer Protocol -- HTTP/1.1 9.1.2 Idempotent Methods

和訳
http://suika.fam.cx/~wakaba/wiki/sw/n/%E5%86%AA%E7%AD%89


数学では冪等写像は f(f(x)) = f(x) と定義される。
当然ながら、副作用がないからといって冪等写像というわけではない。

任意の数値 x について
abs(x) == abs(abs(x)) == abs(abs(abs(x)))
が成り立つ。

階乗 factrial は冪等写像ではない。

factrial(x) ≠ factrial(factrial(x))  ( x > 2 の場合)

[ゲーム] リス缶とは

 
スポーングレネード、リスポーングレネードのこと。
KILLZONE 2 の公式サイトの戦術兵の説明では、「スポーングレネード」と表記されている。
"+respawn grenade" KILLZONE でググっても検索結果は少ない。

[トランザクション処理 概念と技法] トランザクション処理 概念と技法 [正誤表ほか]

 
以下、

トランザクション処理〈上〉— 概念と技法 —
トランザクション処理〈下〉— 概念と技法 —

の正誤表と学習ノート。どちらも 1版1刷。
ページ数は上下巻の通し番号。

p.66
まず、C≈0.01×S が仮定されているから、S≈100×C である。これを実質的なキャッシュアクセス時間の式に適用すると

H × C + (1 - H) × S
≈H × C + (1 - H) × 100 × C
= (100 - 99 × H) × C

50%のヒット率は実質的なメモリをキャッシュの50倍遅いものにし、

(100 - 99 × 0.5 ) × C = 50.5 × C ≈ 50 × C

90%のヒット率は実質的なメモリをキャッシュの11倍遅いものにする。
(100 - 99 × 0.9 ) × C = 10.9 × C ≈ 11 × C

もし99%のヒット率ならば、実質的なメモリはキャッシュの半分の速さになる。(半分の速さ ≡ 2倍遅くなる)
(100 - 99 × 0.99) × C = 1.99 × C ≈ 2 × C

実質的なメモリの速度をキャッシュの10%増し以下にするには、ヒット率は99.8%にならねばならない。
(100 - 99 × H) × C ≤ 1.1 × C
100 - 99 × H ≤ 1.1
-99 × H ≤ -98.9
H ≥ 98.9 ÷ 99 ≈ 0.99898989898989

p.67
5分間ルール
[説明] この 5分間ルールの説明には怪しいところがある。詳細はhttp://monado.dtiblog.com/blog-entry-136.html を参照。

p.198
Further, not only must the input state of the transaction be consistent, it must remain consistent for the duration of the transaction.
更に、トランザクションの入力状態が一貫性を持つだけでなく、トランザクション期間中も一貫し続けなければならない。

[説明] 明らかに次の記述と矛盾する。「トランザクションは、一貫した状態のシステムから出発して、一時的にはシステムを矛盾した状態にするにしても、一貫した状態を新たに作り出してから終了する。(p.456 7.2分離性の導入)」
原文の "for the duration of the transaction" だが "after the duration of the transaction" の間違いではないか。その後もよくわからない説明が続く。ここは読み流せ。

p.386
typedef struct Processes * PCBP;
typedef struct Processes * PCB;

説明: p.609 では、Process と単数形になっている

p.387
struct Sessions
{
SECBP tran_next_ses;
}
説明: tran_next_ses が、P.610 には存在する。

p.471
(誤) (あるトランザクションT"が存在して T <<<H T" かつ ‹T,o,T'› ∈ DEP(H))が成り立つときである。

(正) (あるトランザクションT"が存在して T <<<H T" かつ ‹T",o,T'› ∈ DEP(H))が成り立つときである。



p.473
A particular history, H, such that <<< = <<<H , implies a total order of the transactions extending the partial order <<<.
ここで、<<< = <<<Hを満たす特定の履歴Hは、半順序<<<を拡大して得られる全順序である。
説明: 意味がわからない。仮に直列な履歴だったとしても全順序とは限らない。

p.478
2行目
(誤) Hの中の両者の間には ‹T, UNLOCK, a› が ‹T, XLOCK, a› よりも先に存在せねばならない。

(正) Hの中の両者の間には ‹T, UNLOCK, o› が ‹T, XLOCK, o› よりも先に存在せねばならない。


(誤) トランザクションT=‹‹T',ai,ai›|i=1,...,n›
(正) トランザクションT=‹‹T,ai,ai›|i=1,...,n›

P.493
[誤訳]
To lock a subtree rooted at a certain node (e.g., a file at Ripa) without locking any of the other files at Ripa (or any of the files at other nodes), a transaction must prevent a shared or exclusive lock from being set on the root node and on the Ripa site node.

(誤) あるノードを根とする部分木(例:Ripaにあるファイル)をロックしつつ、Ripaにあるそれ以外のファイル(および他のすべてのファイル節点)をロックしないようにするには、トランザクションはRipaのサイト節点にも、木構造全体の根である節点にも、共有および排他ロックを行なうようにしなければならない。

(正) あるノードを根とする部分木(例:Ripaにあるファイル)をロックしつつ、Ripaにあるそれ以外のファイル(および他のすべてのファイル節点)をロックしないようにするには、トランザクションはRipaのサイト節点と木構造全体の根である節点で、共有および排他ロックを防がなければならない。

p.496
[誤訳]
If, as is typical, several fine-granularity locks are set under a coarse lock (say, five record locks within a file), then the cost of the two coarse locks is amortized across five locks, and the per-lock cost is closer to 250 than it is to 600 instructions.

(誤) 典型的な例ではあるが、複数の細粒度のロックに代えて1つの粒度ロックで設定されるなら(5つのレコードロックが1つのファイルにあるとしよう)、2つの粗粒度のロックのコストは、5つのロックで分担され、ロックあたりのコストは600命令ではなくて、250命令に近づく。

(正) 典型的な例ではあるが、複数の細粒度のロックが1つの粒度ロックの下で設定されるなら(5つのレコードロックが1つのファイルにあるとしよう)、2つの粗粒度のロックのコストは、5つのロックで等分され、ロックあたりのコストは600命令ではなくて、250命令に近づく。

説明:粒度の高い方から2つの対象をロックするとロック/解放のコストは、400命令であり、これを5等分した80命令を、ファイルひとつあたり粒度のコスト200命令に足すと 280命令となる。

p.499
In previous-key locking, the transaction requests a lock on the key valu, of W to lock key range [W,X). The dual of this is next-key locking which uses the half-open interval (W,X] to lock anything after W up to X.

(誤) 後方キーロッキングでは、キー範囲 [W,X) をロックするために、キー値 W へのロックを要求する。これと双対になるのが、半開区間 [W,X) を用いてWより後ろでX以前の全てをロックする。

(正) 後方キーロッキングでは、キー範囲 [W,X) をロックするために、キー値 W へのロックを要求する。これと双対になるのが、半開区間 (W,X] を用いてWより後ろでX以前の全てをロックする。

p.500
REPLACE. REPLACEing a new record in a key range splits the key range in two. REPLACEing X into [W,Y) creates two key ranges [W,X), and [X,Y).

(誤) 挿入 あるキー範囲に新しいレコードを挿入すると、キー範囲は2つに分割される。X を [W,Y) に挿入すると、2つのキー範囲 [W,Y) と [X,Y) が生成される。

(正) 挿入 あるキー範囲に新しいレコードを挿入すると、キー範囲は2つに分割される。X を [W,Y) に挿入すると、2つのキー範囲 [W,X) と [X,Y) が生成される。

p.502
When reading the blondes, the key range [blonde, brunette) is acquired on the hair_color index in shared mode.
(誤) 金髪(blonde)の人物を読み出す時には、hair_index上のキー範囲 [blonde, brunette) を共有モードで取得する。

(正) 金髪(blonde)の人物を読み出す時には、hair_color上のキー範囲 [blonde, brunette) を共有モードで取得する。

When REPLACEing the first brown-haired person into, or deleting last brown-haired person from, the hair_color index, exclusive locks on the two key ranges [blonde.brown) and [brown,brunette) would be acquired.

(誤) hair_colorインデックス上で茶色い髪の人(brown)を初めて挿入するか、または、茶色い髪をした人を最後に削除するときには、2つの範囲 [blonde,brunette)[blonde,brunette) に関する排他ロックを要求するだろう。

(正) hair_colorインデックス上で茶色い髪の人(brown)を初めて挿入するか、または、茶色い髪をした人を最後に削除するときには、2つの範囲 [blonde,brown)[brown,brunette) に関する排他ロックを要求するだろう。

p.505
(誤) bが根であって LOCKST(b) = X であるか、bが根ではなく、bの節点スライスが存在して、そのスライスに含まれる個々の節点において、IMPLICITLOCKST(bi) = X が成り立つならば、IMPLICITLOCKST(b) = X である。

(正) bが根であって LOCKST(b) = X であるか、bが根ではなく、b のすべての根に関して、bの節点スライスが存在して、そのスライスに含まれる個々の節点において、LOCKST(bi) = X が成り立つならば、IMPLICITLOCKST(b) = X である。


p.506
粒度ロック定理に対する反例
図7.10を例にする。以下のふたつのロック要求は、明示的ロックグラフは両立するが、暗黙ロックグラフは両立しない。

ロック要求1
LOCK "IN DATABASE"   IN SHARED MODE

LOCK NODE="RIPA" IN SHARED MODE
LOCK FILE="PHONE" IN SHARED MODE

ロック要求2
LOCK "IN DATABASE"   IN UPDATE MODE

LOCK NODE="RIPA" IN UPDATE MODE
LOCK FILE="PHONE" IN UPDATE MODE
LOCK NAME="GIOVANNA" IN EXCLUSIVE MODE


説明: 粒度ロック定理の証明のおかしいのは、スライス Z と路 Q が交差するとしたとき sq の全ての先祖 c に関してL(c) ∈ {IX, SIX, U, X} となるべきところ、L(c) ∈ {IX, SIX, X} としているところであって、L'(d) = S かつ L(d) = U のケースを考えていないことである。


p.507
The transaction cannot release the shared lock and then get the exclusive lock, because that would violate two-phase locking.

(誤) トランザクションは、共有ロックを解放することなしには排他ロックを取得することができない。なぜなら、2相ロッキングに反してしまうからである。

(正) トランザクションは、共有ロックを解放して排他ロックを取得することができない。なぜなら、2相ロッキングに反してしまうからである。

p.516
Thus, each lock exists at a single site (object), and locks are not distributed data structures. In contrast, the transaction wait list of Figure 7.16 will be distributed.
従って、個々のロックは全て必ず1つのサイトにのみ存在していて、個々のロックは分散したデータ構造にはなっていない。対照的に、図7.16のトランザクション待機リストは分散され得る。
[解釈]
ロック・リストは、その資源のあるサイト内でリストが丸ごと保持され、リストのデータ構造が分割され分散することはない。しかし、トランザクション待機リストは、リストの要素が各ノードに散らばり分散する。

p.516
(誤) 経路圧縮法(path pushing)
(正) 経路転送(path pushing)

p.520
7.12.1 フィールドコール
フィールドコール(Field call, FLD call)は、以下の流れで実行される。

トランザクションの開始
    共有モードロックの取得
        述語テスト
        REDO ログの書込み
    共有モードロックの解放

    ....

(コミット時)
    排他モードロックの取得
        述語テスト
        変更
    排他モードロックの解放
トランザクションの終了

フィールドコールは、トランザクション期間を通してロックを保持するのではなく、最初の述語テストとコミット時のみ資源をロックする。
最初の述語テストからコミット時まではリソースのロックが解放されるので、並列処理性が向上する。

#トランザクションの期間がそもそも短い場合は、並列処理性に関して、フィールドコールはあまり意味がない?
#逆にトランザクションの期間が長ければ、コミット時の述語テストが失敗する確率が高くなるから、やはり問題。その対処のひとつがエスクロー機構。

欠点として、トランザクションは更新した後、更新した結果を読み出すことができないと言われるが、最初の述語テスト完了とコミットまでの間で、随時、他のトランザクションによって資源が変更される可能性があるからである。結局、コミット時まで値が確定していないので、通番の問題などには適用できない。

As first implemented, they had some minor drawbacks. First, if the transaction read a quantity it had updated, the transaction did not see the effects of the update.

p.523
7.12.2 エスクロー・ロッキングと各種のフィールドコール改善手法

閉区間 [m, n] を追加して、レコードの値が m と n の間にあることを示している。
説明: m は現在のデータベースの値を示し、n は、未コミットの変更をそれに反映した結果を示す。先を読めば分かることだが、必ずしも m ≤ n ではない。[1000, 850] などの区間表記がある。

そのレコードに対して、処理が完了していないフィールドコールがなければ、m をその時の値として、この区間は [m,m] になる。+x という変更を伴うフィールドコールが発行されると、システムは [m, m+x] という値を保持する。この値 [m, m+x]に対する後続の述語を評価する時には、この述語は値 m と m+x の双方に対して検査される。トランザクションがコミットまたはアボートすると、この値は [m+x, m+x] または [m, m] になる。

説明: 本文のこの説明では、m を処理前のデータベースの値と仮定している。その為、図7.18のような複数のトランザクションの並列実行については説明が付かない。
並列処理での区間の更新の意味規則は下表のとおり。なお、この表では、m を処理前のデータベースの値、a, b を区間の現在の境界値、x をフィールドコールで加算される値を示す。
事象更新式
初期状態:[m, m]
フィールドコール:[a, b+x]
コミット:[a+x, b]
アボート:[a, b-x]


# エスクロー範囲に対する更新がホットスポットになることはないのか。

p.525
図7.18
説明: 当座の数量(Quantity On Hand) の列は、通常のフィールドコールの処理結果の状態遷移を示し、エスクローの列は、エスクロー方式の処理結果を示す。トランザクションの列 T1, T2, T3 に対して、それぞれ別々の処理結果を示している。

p.557
図8.3 は次のような状況で発生する。
プロセス 1プロセス 2
block *bad_get_black(void) {

block* new;
block* old = free;
do {
if (old ==null) panic();
new = old->next;
/* この時点で free は node1, new は node2 */
block* node1 = bad_get_black();

block* node2 = bad_get_black();

give_block(node1);
/* この時点で free は node1 */
    } while(!CS(&free, &old, &new);

/* free == old == node1 なので CS は成功する */
return(old);
};


p.563
図8.7 ロックの履歴
(誤)(正) 履歴 A の左から2番目のモードは、IS ではなく IX である。

p.572
/* 何も変更しない場合はここまでである。                                                     */

if(lock -> queue == request && request -> queue == NULL) /* これが唯一のリクエストなら、 */
{ if (prev == NULL) lock_hash[bucket].chain = lock -> chain; /*ロックを解放し、 */
(誤)else prevreq -> queue = lock ->queue; /* チェインから取り除き、 */
(正)else prev -> queue = lock ->queue; /* チェインから取り除き、 */
p.574
(誤) lock_reply unlock_class(lock_class class, Boolean all_le, RMID rmid); /*                   */

(正) lock_reply unlock_class(lock_class class, Boolean all_le, RMID rmid) /* */

....

if (request->class == class || /* 期間が一致するか、クラスが低くかつ */
(誤) (request->class-> class && all_le)) /* all_leオプションが選ばれていて、しかも */
(正) (request->class < class && all_le)) /* all_leオプションが選ばれていて、しかも */


p.574
To support notify locks, the lock header is modified with a boolean flag that says, "There is a notify lock in the granted group."
(誤) 通知ロックをサポートするために、ロックのヘッダを論理型のフラグに変更して、「許可グループの中に通知ロックが存在すること」を示す。
(正) 通知ロックをサポートするために、ロックのヘッダは、「許可グループの中に通知ロックが存在すること」を示す論理型のフラグにて変更される。

p.574
When this boolean flag is true, successful unlock operations and conflicting lock operations search the granted group for such notify requests and wake up the corresponding process to notify it that the object may have changed.

あるロックの状態が変更されたことを知りたがっているクライアントがあるとしよう。このフラグが真である時、アンロック操作が成功するか、あるいは、ロック操作が競合すれば、許可グループから通知リクエストを探して対応するプロセスを起動し、オブジェクトが変更された可能性があることを通知する。

[説明] ロックの競合の通知は、粗粒度のロックを細粒度のロックに切り替えるデエスカレーションを実現するのに使われる。「16.5.4.3 VMS ロックマネージャ」を参照。なお、当節の説明で"告知ロック"とあるが通知ロックのことだろう。

# 許可されたロック、および、ロック操作の競合が知りたいクライアントとして、デッドロック検出器はどうか。

p.594
1つ後のレコードの LSN は、ボディ長、ヘッダサイズ、データページのオーバヘッドから計算できるので必要ない。

説明:少し後を読めば分かることだが、LSN の内容は以下のとおり位置情報を含む。
typedef struct {    long file;  /* number of log file in log directory                  */

long rba; /* relative byte address of (first byte) record in file */
} LSN ; /* Definition of Log Sequence Numbers (LSN) */
LSN NullLSN ={0,0}; /* null LSN is used to end pointer chains. */


p.607
(誤) LSN  log_REPLACE(char* buffer, long n)    /* buffer[0..n]のデータを用いてログレコードを      */

/* 追加する。*/

(正) LSN log_REPLACE(char* buffer, long n) /* buffer[0..n-1]のデータを用いてログレコードを */
/* 追加する。*/
p.614
そして、リソースマネージャは、アンカLSNと下限水位LSNをトランザクションマネージャに登録する。

[説明] リソースマネージャのチェックポイントLSN(アンカLSN)と下限水位LSN の登録にあたって、トランザクションマネージャからリソースマネージャの Checkpoint(LSN *low_water)コールバックが呼び出さる。リソースマネージャは、引数 low_water が指すメモリに下限水位LSNを設定し、戻り値としてチェックポイントレコードの LSN を返す。
LSN Checkpoint(LSN *low_water); /* TMがチェックポイントを採取する場合、                 */

/* チェックポイントLSNを返し、下限水位LSNを設定する。 */
トランザクションマネージャのチェックポイント処理では、以下のようにリソースマネージャのチェックポイントLSNと下限水位LSNを取得し、保存している。
void Checkpoint(void)

...
rm->checkpoint = rmid.Checkpoint(&rm->low_water_lsn);
...
TM_anchor.RM_list中の各rmに対して
RMCB をtm_checkpoint にコピー;
RMのアンカLSN(チェックポイントLSN)と下限水位LSN について
アンカLSN(チェックポイントLSN)は、RMのチェックポイントログレコードのLSNである。RMのチェックポイントログレコードは、その時点でのリソースマネージャの実行コンテキストを保存しており、通常のリソースの更新履歴ではない。下限水位LSN が指すログレコードは、通常のリソースの更新履歴であり、下限水位LSNは、REDO処理の起点となる。上述のとおり、どちらの LSN もトランザクション・チェックポイント・レコードに保存される。リスタート時には、トランザクションマネージャは、リソースマネージャのチェックポイントLSNTM_Startupの引数としてリソースマネージャに渡すが、RM下限水位LSNは、リソースマネージャの REDO()コールバックの起点として使用し、直接、リソースマネージャには渡さない。

log_write_anchor と log_read_anchorについて
この二つのインタフェースは、ログマネージャがトランザクションマネージャに対して提供するインタフェースである。トランザクションマネージャは、自身のトランザクション・チェックポイント・レコードの LSN をリスタート時に復旧できるよう log_write_anchor を呼び出しログアンカに保存する。

p.636
(誤) トランザクションマネージャは、ログマネージャやロックマネージャと共に、リソースマネージャ処理やコンピュータ処理にACID属性を与えるメカニズム提供している。

(正) トランザクションマネージャは、ログマネージャやロックマネージャと共に、リソースマネージャ処理やコンピュータ処理にACID属性を与えるメカニズム提供している。

p.654
論理ロギングが持つ基本的問題は2つある。

部分動作と動作一貫性の違い
このふたつの問題は、障害発生時に以下のような違いがある。
部分動作の問題はプログラムでトランザクションがアボートされるようなオンラインの障害を扱う。完了したステップの状態は完了したものとして残っている。
動作一貫性問題では、システム障害などの揮発性メモリがリセットされるリスタートのケースを扱う。したがって、完了したステップの状態が壊れうる。揮発性メモリの内容は、動作一貫性チェックポイントによって永続メモリに移すことになる。

p.654
10.3.5.1 シャドウ
[説明]
シャドウページについては、「13.5.1.3 シャドウページ・アルゴリズム」にてより詳しく扱われる。ただし、用語の使い方が若干異なっている。本節ではページの配置情報をディレクトリと表しているが、参照先ではページアロケーションテーブルと表現が変わっている。なお、本書では、ディレクトリという語は、メタデータやアロケーション・テーブルなどを指し、「目録」という広い意味で使われている。

p.656
ロギング形式まとめ
ロギング形式ログの内容
値ロギング、物理ロギング更新場所と更新前後の値
操作ロギング、論理ロギング更新操作
物理論理ロギング更新場所と更新操作
操作ロギングでは、各操作が原子的であることを仮定している。
物理論理ロギングでは、各操作は複数のステップで構成され、それぞれのステップは原子的であると仮定されており、そのステップ単位でログが取られる。

p.664
VVlsn    Volatile Version LSN

VLlsn Volatile Log LSN
DLlsn Durable Log LSN
PVlsn Persistent Version LSN


p.665
(誤) 図10.14 でいうと、DLlsn VVlsn であることを保証しなければならない。
(正) 図10.14 でいうと、DLlsn VVlsn であることを保証しなければならない。

p.666
(誤) いったんチェックポイントが完了すると、永続メモリのページコピーが現在値となる。つまり、VVlsn PVlsn となる。

(正) いったんチェックポイントが完了すると、永続メモリのページコピーが現在値となる。つまり、VVlsn = PVlsn となる。

VVlsn < PVlsn となるのは、障害発生時のみである。

p.669

(誤) rec_size = log_read_lsn(lsn, header, 0, log_rec, big);
(正) log_read_lsn(lsn, header, 0, log_rec, rec_size);

const int rec_size (p.660) だから代入できないし。

p.670

(誤) rec_size = log_read_lsn(lsn, header, 0, log_rec, big);
(正) log_read_lsn(lsn, header, 0, log_rec, rec_size);

p.678
すべてがYesを投じると、コミット処理はトランザクションがコミット済みであることを示すレコードをログへ書き込む。

説明:

トランザクションには、以下の6つの状態がある(付録インタフェース宣言より)。
enum tran_status {ACTIVE, PREPARED, ABORTING, COMMITTING, ABORTED, COMMITTED};

分散トランザクションの場合、ノード毎に状態が存在する。トランザクションの状態遷移をまとめると、下表のとおりになる。
ノードがルートの場合、そのノードにおけるトランザクションの状態
状態契機TMログ書き出し
ACTIVE動作中Begin_Work() が呼び出された時。
PREPAREDプリペア済み全ての参加者が Yes を投票。コミットレコード
COMMITTINGコミット中コミットレコードを永続化した時。
COMMITTEDコミット済み全ての参加者からコミットアクノリッジを受付けた時。コミット完了レコード
ABORTINGアボート中そのノードのTM.Abort() の呼び出しを受けた時。アボートレコード
ABORTEDアボート済み各参加者の UNDO 処理完了後。Begin_Work() に対する UNDO ログ
アボート完了レコード

ノードがルートでない場合、そのノードにおけるトランザクションの状態
状態契機TMログ書き出し
ACTIVE動作中通信マネージャから Join_Work() が呼び出された時。
PREPAREDプリペア済みそのノードのTMが管理する全ての参加者が Yes を投票。プリペアレコード
COMMITTINGコミット中そのノードが TM.Commit() の呼び出しを受けた時。
COMMITTEDコミット済みそのノードのTMが管理する参加者の全ての参加者からコミットアクノリッジを受付けた時。?
ABORTINGアボート中そのノードが TM.Abort() の呼び出しを受けた時。?
ABORTEDアボート済みそのノードのTMが管理する参加者の全ての UNDO 処理完了後。?

p.708
The log manager maintains the LSN fields, and the lock manager maintains the trans->lock_list.
(誤) ログマネージャはこれらLSNの関連フィールドを管理すると共に、trans->lock_list を管理する。
(正) ログマネージャはこれらLSNの関連フィールドを管理し、ロックマネージャは、trans->lock_list を管理する。

p.708
TRID Begin_Work(context* it, Boolean soft)

(誤) TM_savepointaaave; /*書き込むセーブポイントレコード */
(正) TM_savepoint save; /*書き込むセーブポイントレコード */
p.708
TRID Begin_Work(context* it, Boolean soft)

(誤) trans->save_pt_lsn = log(REPLACE(save, sizeof(save)); /* トランザクションログレコードを書き込 */
(正) trans->save_pt_lsn = log_REPLACE(save, sizeof(save)); /* トランザクションログレコードを書き込 */
p.720
if(vote){                                                       /* このセーブポイントに関してすべての投票が Yes の場合  */

trans->max_lsn = header.tran_prev_lsn; /* 一つ前のセーブポイントレコードにセーブポイントを設定 */
trans->save_pt_lsn = log_REPLACE(save,sizeof(save)); /* 新しいセーブポイント(クローン)を書いて、 */
} /* このセーブポイントを確立 */
説明: 少々、分かりにくいが、trans->max_lsn = header.tran_prev_lsn; がミソ。
log_REPLACE() は、内部で log_transaction() を呼んでいることに注意。
LSN log_REPLACE(char* buffer, long n)            // p.607

{ ...
hearder->tran_prev_lsn = log_transaction(lsn);
...
}

LSN log_transaction(LSN new_lsn) // p.607
{ ...
prev = trans->max_lsn;
...
return prev;
}


p.720
チェックポイントとセーブポイントのまとめ
以下、トランザクションマネージャ、リソースマネージャをそれぞれ TM, RM と略記。

チェックポイントはシステムに関する回復ポイントである。
TMRMがそれぞれのチェックポイントログレコードを作成する。
TMのチェックポイントログレコードは、ノード単位のログであり、すべてのRMCBTACBを保存する。最新のTMチェックポイントログレコードのLSNはログアンカに保存される。TMチェックポイントログレコードは、各RMチェックポイントへのアンカとなっており、各RMチェックポイントログレコードのLSNを保存している。RMチェックポイントログレコードは、RM自身で作成するログレコードであり、そのRMの実行コンテキストを保存する。もし、そのRMの状態が REDO/UNDO ステップのみで再構成できるのであれば、そのRMに対するRMチェックポイントログレコードは不要である。

セーブポイントは、トランザクションに関する回復ポイントである。
TMとトランザクションに関わるRMがそれぞれのセーブポイントログレコードを作成する。TMのセーブポイントログレコードは、各RMのセーブポイントへのアンカとなっており、各RMのセーブポイントログレコードのLSNを保存している。
RMのセーブポイントログレコードは、そのRMが管理するトランザクションコンテキストを保存する。これらは読み出しカーソルの位置情報など REDO/UNDO ステップで再構成できない情報である。もし、トランザクションに関わるそのRMの状態が REDO/UNDO ステップのみで再構成できるのであれば、そのRMに関わるセーブポイントログレコードは不要である。

p.732
First, it invokes the resource manager's rm_restart(checkpoint_lsn), passing the most recent checkpoint LSN of that resource manager (RMCB.checkpoint_lsn).
(誤) まず、トランザクションマネージャはリソースマネージャのTM_Startup(checkpoint_lsn)を呼び出し、当該リソースマネージャの最新チェックポイントのLSN(TMCB.checkpoint_lsn)を渡す。

(正) まず、トランザクションマネージャはリソースマネージャのTM_Startup(checkpoint_lsn)を呼び出し、当該リソースマネージャの最新チェックポイントのLSN(RMCB.checkpoint_lsn)を渡す。

p.832
typdef struct

{...
(誤) Uint frame_index; /*ページが現在格納されているバッファプールのインデックス*/
(正) int frame_index; /*ページが現在格納されているバッファプールのインデックス*/
} BUFFER_CB, *BUFFER_CBP;

説明: p.837 の locate_page() のコードにnext_bcb->frame_index = -1;という箇所がある。


p.838
(誤) Int getframe();
(正) int getframe()

p.840
次に、LRUチェインをたどって到達したときにあった pageid が現在の制御ブロックに依然として含まれているかどうかを調べる。この検査は、バッファマネージャの別のインスタンスが同じことを並行して行っているかも知れないということから必要となるものである。もしもそちらの get_frame の起動が少し早ければ、次に見たときには制御ブロックが変わっている。

[疑問] get_frame の中で sem_get(&LRU_sem, LOCK_X); によって LRU_sem の排他セマフォを獲得しているだから別の get_frame プロセスとは競合しないはずである。ところで、ループの最後に next_younger: next_bcb = next_bcb->prev_in_LRU; とあるが、これは LRU_sem のセマフォを獲得しておけば、別プロセスによってページが置換されてたとしても next_bcb->prev_in_LRUは旧値が参照できるということなのだろうか。

p.841+5
(誤) get_frame()は、初めに LRU_sem共有セマフォを獲得し、それから、
(正) get_frame()は、初めに LRU_sem排他セマフォを獲得し、それから、

p.858
However, each read operation moves the page to the top of the LRU chain,
しかし、個々の読み込みオペレーションはページをLRUチェインの先頭に移動する。

[説明] LRUチェインのページの移動は以下のようになると考えられる。なお、図13.15を見て分かるとおりLRUチェインの両端は、lru_pagemru_page で管理される。
update_LRU(BUFFER_CBP bcb)

{
sem_get(&LRU_sem, LOCK_X);

if (mru_page != bcb) {

/* 現在のLRUチェインから排除 */
if(bcb->next_in_LRU != NULL)
bcb->next_in_LRU->prev_in_LRU = bcb->prev_in_LRU;

if(bcb->prev_in_LRU != NULL)
bcb->prev_in_LRU->next_in_LRU = bcb->next_in_LRU;

if(lru_page == bcb)
lru_page = bcb->prev_in_LRU;
if(lru_page == NULL)
lru_page = bcb;

/* LRUチェインの先頭へ追加 */
bcb->next_in_LRU = mru_page;
bcb->prev_in_LRU = NULL;

if(mru_page != NULL)
mru_page->prev_in_LRU = bcb;
mru_page = bcb;
}
sem_give(&LRU_sem);

}

p.898
(誤) F はページの大きさ S(通常、2のべき乗の整数)とエントリの大きさ E で決まる。
(正) e はページの大きさ S(通常、2のべき乗の整数)とエントリの大きさ E で決まる。

[説明] e = ⌊ S ÷ E

p.915
(誤) 一般的にって、長いタプルを扱う機構は
(正) 一般的にって、長いタプルを扱う機構は

p.918
新しい属性が追加されるとカタログ構造を変更する。relation_cat中のno_of_attributesを1つ増やし、その値をattribute_cat中のF7のインデックスとする。

[補足] no_of_attributes は属性が削除されてもデクリメントしない。属性削除は論理削除として扱われる。属性削除の実装については演習問題6を参照。

p.918
(誤) タプルがアクセスされ、指定された属性の attribute_cat 中のインデックスがタプルのプレフィクス中の no_of_field の値より大きい場合には、その属性値として NULL を返す。

(正) タプルがアクセスされ、指定された属性の attribute_cat 中のインデックスがタプルのプレフィクス中の no_of_fields の値より大きい場合には、その属性値として NULL を返す。

p.920
(誤) 簡単化したコード例では、CREATE TABLE 文で宣言される属性の順番が直接catalog_cat配列のインデックスになっているため、フィールド値はこの順番で格納しなければいけない。

(正) 簡単化したコード例では、CREATE TABLE 文で宣言される属性の順番が直接attribute_cat配列のインデックスになっているため、フィールド値はこの順番で格納しなければいけない。

p.921-6
2つ目の手法では、任意の2つの可変長フィールドの距離は全て事前にコンパイルするが、可変長フィールドの長さは実行時に加算する。

[説明] 0個以上の固定長フィールドを挟む 2つの可変長フィールドの距離については、それらの固定長フィールドの長さの合計を距離としてコンパイル時に確定できるが、任意の2つの可変長フィールドの距離をコンパイル時に確定できるわけではない。2つの可変長フィールドA,Bの間に他の可変長フィールドCが含まれる場合、AとBの距離は事前に確定できない。

p.925-1
(誤) i < k である全ての i について Fi < Ciであり、かつ、Fk < Ck であるような

(正) i < k である全ての i について Fi = Ciであり、かつ、Fk < Ck であるような

p.926
文献「Blasgen、Casey、and Eswaran[1977]」の方式の適用例


F1 = "a"
F2 = "b"
F3 = "cccc"

C1 = "aaaaaaa"
C2 = "b"
C3 = "c"


とする。
s = 5 のとき、連結イメージは下表のとおり。
F1'∥F2'∥F3'a000004b000004cccc001
C1'∥C2'∥C3'aaaaaFFaa00003b000004c000004


p.928

(誤) LONG属性は2バイト長のフィールドを持つにすぎない。

(正) LONG属性は2バイトの長さフィールドを持つにすぎない。

[説明] p.918に「(1)長さフィールドはどの実装においても、固定長なので自分自身の長さは含まない。多くの「旧式な」データベースでは長さは1バイトだが、2バイトのLONG FIELDを持つデータベースもいくつかある。」という記述あり。

p.948

(誤) その属性をスキャンキーとして指定したスキャンでは、readops操作がそのままnext_key操作になる。

(正) その属性をスキャンキーとして指定したスキャンでは、readpos操作がそのままnext_key操作になる。

p.950
     Uint           timeout = 1000;

BUFFER_ACC_CBP pacb_data, pacb_dir;
PAGEID curr_poi, new_poi, directory_page;
PAGEPTR data_p, dir_p;
Uint tuple_length;
TUPLEID tupleid
lock_name ThisTID;
LSN LogPosition;
TRID NewTRID, OldTRID;
(誤) bufferfix(directory_page, ex_sem, &pacb_dir);
(正) bufferfix(directory_page, LOCK_X, &pacb_dir);
(誤) bufferfix(curr_poi, lock_x, &pacb_data);
(正) bufferfix(curr_poi, LOCK_X, &pacb_data);
data_p = pacb_data->pageaddr;
if(data_p->freespace < tuple_length + 4)
{ bufferunfix(pacb_data);
dir_p = padb_dir->pageaddr;
new_poi = dir_p->relation_cat->empty_page_anchor;
if(new_poi == NULL) panic();
OldTRID = MyTrid();
Leave_Transaction();
NewTRID = Begin_Work();
curr_poi = new_poi;
(誤) bufferfix(curr_poi, ex_sem, &pacb_data);
(正) bufferfix(curr_poi, LOCK_X, &pacb_data);
data_p = pacb_data->pageaddr;
(誤) newpoi, dir_p->relation_cat->empty_page_anchor - data_p->next;
(正) newpoi= dir_p->relation_cat->empty_page_anchor - data_p->next;

['advance-EOF', directory_page, curr_poi, new_poi]というログレコードを準備;
LogPosition = log_REPLACE(log_record, length);
dir_p->safe_up_to = LogPosition;
Commit_Work(NULL, TRUE);
Resume_Transaction(OldTRID);
};
bufferunfix(pacb_dir);
data_p->no_entries = data_p->no_entries + 1;
data_p->offset_in_page[-(data_p->no_entries)] = PAGESIZE - (data_p->freespace);

タプルの物理表現をコピー;
タプル識別子をtupleidに設定;
data_p->freespace = data_p->freespace - tuple_length - 4;
['REPLACE', curr_poi, TID, tuple data] というログレコードを準備;
LogPosition = log_REPLACE(log_record, length);
data_p->safe_up_to = LogPosition;
ロック名をタプルIDとMyRMID()から作成しThisTIDに設定;
switch(lock(ThisTID, LOCK_X, LOCK_LONG, timeout))
{ case LOCK_ON :
bufferunfix(pacb_data);
return(ThisTID);
case LOCK_TIMEOUT :
再実行等の必要な処理を行う;
何度もタイムアウトする場合はpanic();
case LOCK_DEADLOCK :
panic();};

p.952
(誤) if(new_cursor.in_page == NULLTID)

(正) if(new_cursor.in_page == NULL)
[説明] NULLTID との比較は明らかに間違い。readposコードの下から7行目のファイルの末尾との比較に合わせ修正。
(誤) { new_cursor.pageno = 1;
(正) { new_cursor.in_page = 1;
(誤) RC = bufferfix(new_cursor.in_page, sh_sem, &pacb);
(正) RC = bufferfix(new_cursor.in_page, LOCK_S, &pacb);
data_p = pacb->pageaddr;
new_cursor.dir_index = 0; /* 最初のタプルのインデクスは-1 */
↑ [説明] インデックス 0 はファイルの始端、あるいは終端を示す。
offset_in_page[0]は不正な参照となることに注意。
最初のタプルのインデックスは-1となる。

}
...
(誤) RC = bufferfix(new_cursor.in_page, sh_sem, &pacb);
(正) RC = bufferfix(new_cursor.in_page, LOCK_S, &pacb);

p.987
(誤)

(正)


p.990
n を n = ⌊V/B⌋ とする。Bを使う代わりに、B'を次の式にもとづいて決める。B'=次に大きい素数(⌈V/n⌉)。
このようにする理由を見てみるため、D << B であるDについて、V=B+Dとあると仮定する。ハッシュ関数が優秀で属性の値が一様に分布するならば、各挿入においてB個のページすべてが、同じ確立でタプルを受け取る。ただし例外として、D個のページは2倍の確率で受け取るので、それだけ早くオーバーフローする恐れがある。

[説明] 以下では、D を V を B で割った余り、n を n = ⌊V/B⌋ とする。
V個の異なる値をそれぞれ1回づつ挿入することを考える。V が B で割り切れる場合、B個のページは、n(=V/B)個のタプルを受け取る。
割り切れない場合、ハッシュ関数の性質より、余りのD個の値も一様にページに割り当てられると考えられるため、(B-D)個のページが n 個のタプルを受け取り、D個のページが n+1 個を受け取る。
これを敷衍して考えるとV個の異なる値をそれぞれ m 回づつ挿入するとき、V が B で割り切れる場合、B個のページは、mn個のタプルを受け取る。割り切れない場合、V個の値が割り振られるページは固定なので、(B-D)個のページが mn 個のタプルを受け取り、D個のページが mn+m 個を受け取る。これは、Vの値が一様な確率で挿入されるとき、タプルを受け取る確率が一様でなくなることを意味する。したがって、衝突率も一様でなくなる(nが1のときは、(B-D)個のページが 1個、D個のページが 2個を受け取り、受け取る確率は2倍となる)。

n = ⌊V/B⌋ は商を示すので、V = nB + D である。そこで、B' = V/n = B + D/n ととれば、V = nB' となる。
しかし、実際には、B'は、次に大きい素数(⌈V/n⌉)としているので、上の議論は、再び繰り返されることになる。
結局、D=0 にできない場合もあり、Dを最小になるようにB'を修正するしかなくなる。

p.998

ノードには、葉ノード(leaf node)とインデクスノード(index node)の2種類のノードがある。

すべての内部ノードはこの型のルーティング情報だけを持つ。

[説明]
内部ノード(internal node、inner node)とは子ノードを持つノードのことを言う。すなわち葉ノード以外のノードを意味する。
B木の場合、内部ノードはインデクスノードであり、インデクスノードは内部ノードである。以降の議論では、インデクスノードを内部ノードと表現することもある。

p.998
上の宣言した構造には、先頭にK0が付加されている。
[説明] index_node_structure[]の最初の要素が
index_node_structure[0].K == K0
index_node_structure[0].PAGEID == P0

であるということ。

K1未満のすべてのキー値はP0が指す部分木にあるという定義に従えば、この項がどうしても必要というわけではない。しかし、こうしておくとノード内部のデータ構造が単純になるので、B木のほとんどの実装でこの項目を用意している。

ポインタだけのあとに<キー値、ポインタ>の対が続くのではなく、すべてを<キー値、ポインタ>対にした方が規則的だからである。
[説明]
P0, (K1, P1), ...,(KF, PF) とするのではなく、

(K0, P0), (K1, P1),...,(KF, PF) と管理した方が楽という話。

p.1007
あるいは、属性値は一意ではないが、属性値とタプル識別子を合わせたものは一意であり、それを主キーと同じようにB木に送り込むことができる。9

[説明] この場合、一致問い合わせ(equality query)は、範囲問い合わせ(range query)によって実現される。「一意的なエントリしか存在しないように<属性値,タプル識別子>というエントリ構造を採用したので、完全一致問い合わせも実質上、一意的なインデクスに対する範囲問い合わせになる。キー値=cを満たすすべてのタプルを取り出すことは、区間(<c, -∞>,<c, +∞>)を探索することを意味する。ここで、±∞はタプルの識別子の最大値、最小値を表す。(1018頁)」
struct {

char* value;
TUPLEID tupleid;
} range_start, range_end;

renge_start.value = range_end.value = searchkey;
range_start.tupleid = MIN_TUPLEID;
range_end.tupleid = MAX_TUPLEID;

range_search(range_start, range_end, &buf, sizeof(buf));


p.1007
9この見方をすると、B木の葉ノードのデータ部分が空になる。B木のユーザの観点から見たデータは、B木のマネージャに対しては一意的な値を得るためにキーの一部として定義されるからである。
[説明] 「B木のユーザの観点から見たデータ」とはタプル識別子のこと。通常、データとして扱われるタプル識別子が既にキー値に含まれる為、B木マネージャがデータとして扱うものがない。

p.1010
平均してタプルはポインタよりも x倍大きいので、

[説明] したがって、ページ内に保持できるポインタのエントリ数はタプルのエントリ数の x倍となる。タプルのエントリ数を C* とすれば、ポインタのエントリ数は、x × C* となる。

p.1028
(誤) { outcome = bufferfix(nextint, sh_sem, &right_leg); /* バッファ内にページを確保しセマフォをセット */
(正) { outcome = bufferfix(nextint, LOCK_S, &right_leg); /* バッファ内にページを確保しセマフォをセット */

(誤) outcome = bufferfix(nextint, sh_sem, &right_leg); /* 読み出し用に共有セマフォを得る */
(正) outcome = bufferfix(nextint, LOCK_S, &right_leg); /* 読み出し用に共有セマフォを得る */

(誤) outcome = bufferfix(nextint, ex_sem, &right_leg); /* 更新用排他セマフォ */
(正) outcome = bufferfix(nextint, LOCK_X, &right_leg); /* 更新用排他セマフォ */

p.1033
(誤) searchpath[tree.height].lsn_seen = leafadd.pageaddr->safe_up_to;
(正) searchpath[tree.height].lsn_seen = curr_leaf->pageaddr->safe_up_to;

(誤) { outcome = bufferfix(searchpath[i].hereiwas, ex_sem, &modnode[i]);
(正) { outcome = bufferfix(searchpath[i].hereiwas, LOCK_X, &modnode[i]);

(誤) outcome = emptyfix(newnode, ex_sem, &newnodecbp); /* 排他セマフォ付きで新ページをバッファに固定 */
(正) outcome = emptyfix(newnode, LOCK_X, &newnodecbp); /* 排他セマフォ付きで新ページをバッファに固定 */

p.1108

STDL is not a persistent programming language; variables are not durable: if the STDL process fails, the terminal context is lost.

STDL は永続プログラミング言語ではない。なぜなら、変数は持続的でないからである。STDLプロセスが故障した場合、端末コンテクストは失われてしまう。

[説明] STDLが永続プログラミング言語か否かについて、本文と用語集の記述が矛盾する。

Structured Task Definition Language (STDL).
The persistent programming language used by DEC'S ACMS transaction manager to define global transaction flow.

DECのACMSトランザクションマネージャで使用される永続プログラミング言語。グローバルトランザクションの処理を記述する。

[Oracle] ORA-48146: ADRの初期化中にディレクトリに対する読取り権限、書込み権限または実行権限がありませんでした

 
Oracle Windows版
SQL> startup

ORA-48146: missing read, write, or exec permission on directory during ADR initialization [c:\app\oracle\diag\rdbms\orcl\orcl\trace] [0]
ORA-48188: user missing read, write, or exec permission on specified directory
OSD-00005: additional error information
O/S-Error: (OS 12) アクセス コードが無効です。

対処
コマンド・プロンプトにおいて、ATTRIBコマンドを実行する。
C:\> ATTRIB -R C:\app\oracle\diag\rdbms\orcl\orcl\trace
ATTRIB コマンドによって、traceディレクトリの読み取り専用を解除する。

参考
ちなみに、フォルダの読み取り専用属性は、ATTRIB コマンドでないと変更できない。
フォルダーの読み取り専用属性を変更するには、どうしたらよいですか?

[未分類] Windows 7 サービス管理コンソールの列幅を保存する方法

 
サービス管理コンソールの項目の列幅やウィンドウの表示状態を保存する方法.
  1. 次のいずれかの方法で、サービス管理コンソールを作成者モードで開く。

    • サービスを右クリックし、作成者(A) を選択する。
      サービス管理コンソールをコンテキストメニューより作成者モードで開く

    • ファイル名を指定して実行 にて services.msc /a を入力する。

  2. ウィンドウを好みの表示状態にする。

  3. メニューより ファイル(F)→名前を付けて保存(A)... を選択し、保存する。

  4. 次回以降の作業では、保存したmscファイルを開く。その際、mscファイルを作成者モードで開けば、表示状態を保存できるようになる。
Windows Vista 以降、C:\Windows\System32\services.msc は、WRP (Windows Resource Protection) によって保護されています。したがって、変更は、TrustedInstaller 権限に対してのみ許可されており、管理者権限では上書き保存ができません。
次のページ