JPH0740239B2 - データページにアクセスする方法 - Google Patents

Description

【発明の詳細な説明】 A.産業上の利用分野 本発明はコンピュータによるデータ処理システムに関
し、より詳細には、セグメント化された記憶装置に記憶
されたデータの削除、ロック及び読取りに関するもので
ある。

B.従来技術 コンピュータによるデータ管理システムは、データの操
作及び処理には拘束の中央演算処理装置を使用し、デー
タの永続的記憶にははるかに遅い物理的記憶装置を使用
している。物理的に記憶されたデータを処理する必要が
あるときは、データを記憶装置からバッファに転送し、
バッファで読み取り、更新し、または他の処理を行なう
ことができる。処理の後でバッファ内のページの内容が
更新された場合、そのページが再び物理的記憶装置に複
写され、前に記憶されていたデータと置き換わる。バッ
ファは中央演算処理装置（CPU）の主メモリ等の高速の
電子的記憶装置（実記憶装置）または高速の物理的記憶
装置（ページング装置）のいずれかに存在することがで
きる。

物理的記憶装置からバッファへのデータ・ページの転
送、すなわち、「バッファ・ページング」と呼ばれる処
理は、ページが順次（先行する記憶ページの直後に）ア
クセスされたか、それともランダムにアクセスされたか
に応じて、約２または20ミリ秒を要する。恐らくは100,
000データ・ページにわたって分散された数100万のデー
タ・レコードを有する通常の大きなデータベースでは、
全データをランダムに読み取るにはバッファ・ページン
グのみで半時間以上を要する。バッファ内にページング
する必要のあるデータ・ページ数が少しでも減少する
と、データベースの能力が直接かつ大幅に向上すること
になる。したがって、不必要なデータ・ページ読取り要
求をなくすことにより、バッファ・ページングを最小限
に抑えることが望ましい。

データベースが複数のユーザまたはプログラムによって
同時にアクセスまたは更新できるようにするため、「ペ
ージ・レベル・ロッキング」と呼ばれる技術がデータベ
ース管理システムで使用されている。ページ・レベル・
ロッキングを使用すると、ユーザまたはプログラムによ
ってアクセスまたは更新される各ページが、「ロック」
されて、他のユーザまたはプログラムによる同時アクセ
スまたは更新ができなくなる。ロックは、多大なCPU時
間を使用する、費用のかかる動作であり、システムの処
理能力及び応答時間を大きく低下させる可能性がある。
したがって、複数ユーザによる有効使用のために必要な
同時動作制御を犠牲にすることなく、ロックを最小限に
することが望ましい。

W.チュー（Chu等）の論文、「密結合システム用の故障
許容ロッキング（Fault Tolerant Locking for Tightly
Coupled Systems）」、分散ソフトウェア及びデータベ
ース・システムの信頼性に関する第５回シンポジウムの
報告要旨集（Proceedings of the 5th Symposium on Re
liability in Distributed Software and Database Sys
tem）、IEEEコンピューティング・ソサイエティ・プレ
ス、（IEEE Computing Society Press）1986年、pp.49
−55は、レコード群の状況を含むロック・ワードがその
群に付加されるという、故障許容ロッキング・プロトコ
ルを開示している。プロセッサは、この群にアクセスす
る前に状態テーブルを調べる。記録される状態は、空
き、ロック、更新開始または故障である。

データベース管理システムはログ・レコードを使って、
失敗したトランザクションまたは動作を取り消すことが
できる。この機能は危険を伴う。なぜならば、トランザ
クションまたは動作がその完了の途中で失敗した場合、
あるデータは変更されているが別のデータは前の状態に
留まっているからである。故障時点までに書かれたログ
・レコードを使って、テーブルをその元の状態に復元、
すなわち、ロールバックし、トラザクションまたは動作
を再び開始することができる。一度トランザクションま
たは動作が完了し、データに対するその変更を永続的な
ものにできるようになると、トランザクションまたは動
作は「コミット」される。そのコミットの後では、トラ
ンザクションまたは動作は取り消すことができない。

１つの重要な種類のデータベース管理システムは、リレ
ーショナル・データベース管理システムである。リレー
ショナル・データベース管理システムでは、データは、
それぞれが特定の列数及び可変数の順序付けられない行
または「レコード」から成る、１つまたは複数のテーブ
ルまたは「リレーション」中に存在することが認められ
る。リレーショナル・データベース管理システムの利点
は、それらのデータが、記憶装置の特定の編成または記
憶位置の代わりに、その内容を参照することによって、
アクセスできることである。

C.発明が解決しようとする問題点 過去においては、リレーショナル・データベース・テー
ブル等の大きなデータ実体の内容全体の削除、すなわ
ち、大量削除または無条件削除とも呼ばれる処理は、大
きなデータ実体では多大な時間を要した。というのは、
大量削除処理は、データ実体のレコード（行）を１つ１
つ削除し、すべての削除レコードについてログ・レコー
ドを書かねばならないからである。

本発明の１つの目的は、読み取られるページ数を減少さ
せ、かつページ・ロッキングを減少させることにより、
データベース管理システムにおけるバッファ・ジング量
を最少にすることである。

本発明のもう１つの目的は、リレーショナル・データベ
ース・テーブルの大量削除に必要な時間を減少させるこ
とである。

D.問題点を解決するための手段 上記及びその他の目的は、各データ・ページが単一デー
タ実体のためのデータのみを含み、各ページの状況はそ
のページとは別に記憶されている、物理的記憶空間のペ
ージを読み取る方法及びそのページにデータを挿入する
方法によって達成される。どちらの方法でも、あるデー
タ実体に属するデータのすべてを削除する間に、記憶空
間がロックされる。またどちらの方法でも、データ実体
のすべてのデータが削除されたため古くなったデータの
みを含むページは、データを含まないページと同じ扱い
を受ける。

ページを読み取るための方法では、少なくとも幾つかの
最新データを含むページがロックされ、かつ読み取られ
る。データ実体のすべてのデータよりも少ないデータが
削除されたため古くなったデータをみの含むページはロ
ックされ、ロックが得られた後、最新データを含む場合
にだけそれらのページが読み取られる。データを含まな
いか、またはデータ実体のすべてのデータが削除された
ため古くなったデータのみを含むページは、ロッムも読
取りもされない。

ページにデータを挿入するための方法では、現データを
含むページ、及びデータ実体のすべてのデータよりも少
ないデータが削除されたため古くなったデータのみを含
むページは、ロックされ、読み取られてから、そこにデ
ータが挿入される。データを含まないか、または、デー
タ実体のすべてのデータが削除されたため古くなったデ
ータのみを含むページは、初めに読取りを行なわず、そ
のページにデータが直接挿入される。

本発明のその他の特徴及び利点は、添付の図面に関して
行なわれるその好ましい実施例に関する以下の詳細な説
明から明らかになるはずである。

E.実施例 Ｅ−１ セグメント化されたテーブル空間 リレーショナル・データベース・テーブルの内容（行）
は、通常物理的記憶装置の「テーブル空間」に記憶され
る。テーブル空間を形成するため、物理的記憶装置の１
つまたは複数の区域が互いに論理的に連結されて、単一
の線形アドレス指定範囲（すなわち、０から64ギガバイ
ト）を形成する。テーブル空間は一定の大きさのページ
に分割（フォーマット化）され、テーブル空間内のすべ
てのページが相対ページ番号によって一意的に識別され
る。各テーブル空間は、バッファ・サイズがテーブル空
間のページ・サイズと等しくなっている、バッファ・グ
ループまたはバッファ・プールと関連付けられている。

セグメント化されたテーブル空間は、その内部データ編
成及び空間管理の方式によって区別される特定の種類の
テーブル空間である。セグメント化されたテーブル空間
は、通常、ヘッダ・ページ、空間マップ・ページ及びデ
ータ・ページを含む。データ・ページは実際のデータを
記憶し、一方、ヘッダ・ページ及び空間マップ・ページ
は、そのデータ・ページに迅速にアクセスするための枠
組を提供する。

データ・ページは、相対セグメント番号によって一意的
に識別されるセグメントにまとめられる。各セグメント
は大きさが等しく、テーブル空間での基本的記憶単位を
構成する。特定のセグメントにおけるすべてのデータ・
ページは、そのセグメントのテーブルのみのためのデー
タを含む。テーブルが追加の記憶域を必要とするとき
は、さらにセグメントがテーブルに割り当てられる。

セグメントはそれ自体グループ化され、各セグメント・
グループの前に、空間マップ・ページがくる。空間マッ
プ・ページは、空間マップ・ページの各セグメントごと
にセグメント制御ブロックと呼ばれる項目を含む。各テ
ーブルのためのセグメント制御ブロックは、ポインタに
よって互いに連鎖される。ヘッダ・ページは、空間マッ
プ・ページがセグメントを識別するのと同様にして空間
マップ・ページを識別し、セグメント化されたテーブル
空間内に階層記憶構造を作成する。

第１図は、本発明の方法が特に有用である、代表的なセ
グメント化されたテーブル空間10を示す。テーブル空間
は同じ大きさの多数のページから構成される。テーブル
空間10の最初のページは、テーブル空間ヘッダ12であ
り、そのうちテーブル空間全体用のものが１つある。テ
ーブル空間ヘッダ12はテーブル空間識別子、及びテーブ
ル空間全体に関連するその他の情報を含む。テーブル空
間の残りの部分は、それぞれいくつかのセグメント16を
従えた空間マップ・ページ14から成る。各セグメント16
はいくつかのデータ・ページ18から成る。データ・ペー
ジ18のみがテーブルの行からのデータを含む。空間マッ
プ・ページ及びヘッダ・ページは、個々のデータ・ペー
ジ上に記憶されたデータに対するアクセスを容易にする
階層編成をもたらす。

空間マップ・ページ14及びそれに続くセグメント16a、1
6b、...、を第２図に示す。空間マップ・ページ14は、
セグメント制御ブロックのリスト20と、次の空間マップ
・ページを指すポインタ22を含む。空間マップ・ページ
14に続くセグメント16a、16b、...、は幾つかのデータ
・ページ18を含み、各データ・ページはテーブルの数行
分のデータを記憶する。テーブル空間10はセグメント化
されているので、特定のセグメント16内のすべてのデー
タ・ページ18は同じテーブル用の行を含む。隣接するセ
グメント16は、同じテーブルまたは異なるテーブル用の
データを含む可能性がある。各セグメント16は、対応す
るセグメント制御ブロック20を有する。

通常のセグメント制御ブロック20を第３図に示す。各セ
グメント制御ブロック20は、テーブル識別子24、セグメ
ント状況標識25、いくつかのデータ・ページ状況標識2
6、及び同じテーブル用の次のセグメント制御ブロック
を指すポインタ28を含む。これらのポインタ28は、第２
図に示すように、同じテーブルに属するセグメント制御
ブロック20の連鎖を作成する。特定のセグメント16用の
セグメント制御ブロック20は、そのセグメント内の各デ
ータ・ページ18の状況の標識26を記憶する。この状況標
識の５つの異なる値（26a−26e）は次の通りである。

（１）満杯（26a）−データ・ページが最新データで完
全に満たされている。

（２）一部満杯（26b）−データ・ページの一部分が最
新データで満たされている。

（３）未フォーマット（26c）−データ・ベースがフォ
ーマットされておらず、データを含まない。

（４）大量削除（mass delete）（26d）−データ・ペー
ジが、テーブルの無条件削除または大量削除の結果、古
くったデータのみを含む。

（５）条件削除（qualified delete）（26e）−データ
・ページが、テーブル中のすべてのデータよりも少ない
データが削除される条件削除の結果、廃用化したデータ
のみを含む。

データベース・テーブルのすべての行の大量削除するた
めの好ましい方法について次に説明する。

Ｅ−２ セグメント化されたテーブル空間での大量削除 第１図及び第２図に示すようなセグメント化されたテー
ブル空間で、テーブル全体の大量削除を効率的に行なう
ための新しい方法が発見された。この新しい大量削除動
作は、テーブルのデータ・ページ18をアクセス、ロック
またはログしない。その代わりに、この大量削除動作
は、対象テーブルのセグメント制御ブロック20のみを走
査し、それらのセグメント状況標識25を「空き」（割振
り解除）とマークする。後でデータ挿入を可能にするた
め、テーブルの最初のセグメント16は割振り解除されな
い。大量削除を取り消しできるようにするため、割振り
解除された空間マップ・ページ14についてロギングが行
なわれる。

セグメント制御ブロックのページ状況標識26は、それら
のページが大量削除動作の一部として削除されたことを
示すため、「大量削除」にセットされる。これらのデー
タ・ページを含むセグメント16が再割り振りされる場
合、ページ状況標識26は、データベース管理システムに
対してそれを識別するために変更されない。こうする必
要があるのは、大量削除されたデータ・ページ18に新し
いデータが挿入される前に特別な処置が取られなければ
ならないためである。「大量削除」ページ状況標識26
は、データ・ページが論理的に空であることを示す。し
たがって、大量削除されたページは活動データまたは最
新データを含まず、大量削除動作中に消去されなかった
古くなったデータのみを含む。古くなったデータの消去
を回避することにより、それらのデータ・ページについ
てページ・アクセス及びログ・レコードが不要となるの
で、大量削除動作に必要な時間が非常に大幅に減少す
る。

表１に、本発明の大量削除動作の疑似コードによる実施
態様を示す。

大量削除されるテーブル上で他のトラザクションまたは
動作が実行されないことが不可欠である。表１の行101
は、テーブルを排他モードでロックして、他のユーザま
たはプログラムがそのテーブル中のデータにアクセスで
きないようにすることにより、このことを保証する。同
時に、行102で、コミットされていない（まだ永続的で
ない）空きセグメントが、大量削除動作を含めてどのユ
ーザまたはアプリケーション・プログラムによっても再
使用されないように、「大量削除」型のロックが獲得さ
れる。したがって、この大量削除ロックは排他モードで
獲得され、大量削除動作が永続的になり、コミットされ
たときにのみ解除される。

大量削除動作は次に、テーブルのセグメント制御ブロッ
ク連鎖をたどることにより、テーブルの各セグメントに
アクセスする。テーブルの各セグメント16に必要な空間
マップ・ページ14が、アクセスされる。テーブルの最初
のセグメント16は、後続セグメントとはわずかに異なる
方式で処理される（行105−107）。どちらの場合にも、
セグメントのセグメント制御ブロック20の前後のイメー
ジを記録するためにログ・レコードが書かれる。セグメ
ントが連鎖上の最初のセグメントでない場合（行108−1
11）、セグメント制御ブロックは大量削除された空きセ
グメントとしてマークされるが、セグメントのテーブル
識別子24は変更されないまま残される。０でないセグメ
ント・テーブル識別子24は、そのセグメントに前に関連
づけられていたテーブルに関しコミットされない大量削
除が進行中の間、セグメントを再割振りすることができ
ないことを示す。各セグメントに対する最終ステップ
（テーブル１の行107及び111）は、セグメントの全テー
タ・ページを、それらのページが他のテーブルに割り振
られるとき使用できるように、大量削除されたものとし
てマークする。行103と112の間のDOループは、セグメン
ト制御ブロック20の連鎖をたどることにより、テーブル
のすべてのセグメントについて繰り返される。最後のセ
グメントが処理された後、大量削除動作は完了し、コミ
ットされることが可能になる。

後続のデータ挿入のためにテーブルが保持されないドロ
ップ・テーブル動作は、他のデータがテーブルに挿入さ
れないのでテーブルに対して最初に割り振られたセグメ
ントも割振り解除されることを除いて、大量削除と同様
に動作する。

Ｅ−３ 空ページのロック及び読取りの最小化 本発明の主目的は、物理的または論理的に空のデータ・
ページ18のロック及び読取りを最小限にすることであ
る。「物理的に」空のページは、２進０のみを含み、デ
ータをまったく含まない。幾分似ているが、「論理的
に」空のページは、有効データを含まないが、２進０に
リセットされていない。論理的に空のページは、大量削
除（すなわち、テーブル内の全データの無条件削除）ま
たは、テーブルのすべてのデータよりも少ないデータの
条件によって引き起こされる可能性がある。したがっ
て、物理的に空のページはデータを含まず、論理的に空
のページは古くなったデータのみを含み、その他のすべ
てのページは最新（すなわち、活動または有効）データ
を部分的または完全に含む。

この目的を達成するため、各データ・ページの状況をペ
ージ18自体とは別に記憶しなければならず、したがって
ページが空の場合は、それを読み取る必要はない。この
指示は、ページ状況標識26としてセグメント制御ブロッ
ク20に記憶される。上述の５種類の状況指示の１つが各
データ・ページ18ごとに記憶されなければならない。各
状況指示は、データ・ページの１つの状態に対応する。

最初の状況指示「満杯」は、ページ18にそれ以上データ
を追加することができないときにセットされる。読取り
動作中、これらのページはまずロックされ、次に読み取
られる。「満杯」ページは挿入動作中は無視される。

第２の状況指示「一部満杯」は、ページが少なくともい
くつかの最新データまたは有効データを含むときにセッ
トされる。読取り動作中、これらのページは「満杯」ペ
ージ同様、まずロックされ、次に通常通り読み取られ
る。可変長の行（すなわち、少なくとも１つの可変長列
を含むテーブルの行）では、データ・ページ上に残され
た空き空間量を一層正確に示すために、この第２の状況
指示をさらに複数の設定に細分することができ、それに
よって一層多くの行をデータ・ページに詰め込むことに
より、物理的記憶装置の利用度が向上する。

第３の状況指示「未フォーマット」は、物理的に空のペ
ージ、すなわち、内容が２進０のみであることが保証さ
れているページ18に対してセットされる。空間マップ・
ページ14が最初にフォーマットされたとき、その空間マ
ップによってカバーされるすべてのデータ・ページ18
は、それらのページが使用可能になる前にこの状態にセ
ットされる。「未フォーマット」ページはデータを含ま
ないので、読取り動作中、ロックも読取りも行なわれな
い。同様に、これらのページにデータが挿入されると
き、考慮すべき既存データはないので、それらのページ
は最初に読み取られない。しかし、要求されたページは
ログ記録され、２進０にリセットされた空のバッファが
そのページに割り当てられ、データを含まないデータ・
ページとしてフォーマットされる。

第４の状況指示「大量削除」は、大量削除（またはドロ
ップ・テーブル）動作のためにページ18が論理的に空に
なったときにセットされる。この状態は、ページが２進
０にリセットされていなくてもページの内容が無視でき
ることを示す。この状況指示を有するページは有効デー
タを含まない。表１について上述したように、大量削除
動作で、テーブルのセグメント制御ブロック20のページ
状況標識26が第４の状況指示「大量削除」に変更され
る。読取り動作中「大量削除」ページは、最新データを
含まないので、ロックも読取りも行なわれない。大量削
除が実行されている間、別のユーザまたはアプリケーシ
ョンがそのテーブルに対して読取り動作を開始できない
ように、大量削除動作によってテーブルに対する排他的
ロックが保持されるので、同時的大量削除がコミットさ
れず、取り消されるという危険はない。挿入動作中、
「大量削除」ページは（「未フォーマット」ページと同
様に）、古くなったデータのみ含むので、最初に読み取
られない。しかし、ページにデータが挿入される前に、
空のバッファが割り当てられ、ページがフォーマットさ
れる。このフォーマット処理で、ページはまず２進０に
リセットされ、次にページがデータを含まないことを示
すために、ページ・ペッダ及びページ・トレーラがセッ
トされる。

第５の状況指示「条件削除」は、条件削除の結果、ペー
ジ18が論理的に空になったときにセットされる。この種
の削除ステートメントの次には、通常、テーブルのレコ
ードの一部のみを削除させる条件が付加される。読取り
動作中、「条件削除」ページは、その論理的に空の状態
が、コミットされていない削除によって引き起こされた
のではないことを確認するため、まず検査される。この
検査は、ページに対するロックを要求し、待ち、最終的
に獲得することによって行なわれる。ロックが獲得され
た後、ページが依然として論理的に空であり、古くなっ
たデータのみを含む場合は、読取り動作はそのページを
飛び越す。「条件削除」ページにデータが挿入されると
きは、ページが読み取られる。

Ｅ−４ セグメント化されたテーブル空間でのリレーシ
ョナル走査 表２に、本発明の好ましい実施例によるリレーション走
査またはテーブル走査と呼ばれる一種の読取り動作の疑
似コードによる実施態様を示す。テーブル走査でテーブ
ルのデータのいくつかのページが順次読み取られる。

表２の疑似コードに示したリレーションの走査は、基本
的に、テーブルのセグメント16にわたる外側DOループ、
各セグメントのデータ・ページ18にわたる内側DOルー
プ、及び内側DOループ内で、空間マップ・ページ14のセ
グメント制御ブロック20のその状況標識26内の値に従っ
てデータ・ページを処理するための、行205、208及び22
8の３つのCASEステートメントを有するSELECT構造から
構成される。

行201と243の間の外側DOループは、空間マップ・ページ
14を通じてテーブルのセグメント制御ブロック20連鎖を
たどることにより、テーブルの各セグメント16を処理す
る。テーブルのセグメント16用のセグメント制御ブロッ
ク20を有する各空間マップ・ページ14が、行202でアク
セスされる。

行203と242の間の内側DOループは、セグメント化された
テーブル空間では、各セグメントがテーブル等の特定の
データ実体のためのデータのみを含むことが必要なの
で、現セグメント16内のすべてのデータ・ページ18を処
理する。この内側DOループは、セグメント制御ブロック
20のデータ・ページ状況標識26のリストを通して読み、
SELECT構造を使って、標識の値に従って、各標識の対応
するデータ・ページ18を処理する。

行204と241の間のSELECT構造は、データ・ページ状況標
識26の異なる値を処理するための、行205、208及び228
の３つのCASEステートメントを含む。行205の最初のCAS
Eステートメントにより、テーブル走査動作は、「未フ
ォーマット」という状況標識26値を有する物理的に空の
ページ、及び大量削除のため論理的に空になり、したが
って「大量削除」の標識値を有するデータ・ページを飛
び越す。これら２種類のデータ・ページ18は有効または
現データを含まないので、無視できる。したがって、行
206及び207では何も行なわれない。すなわち、ページは
ロックまたは読取りを行なわない。

行208の第２のCASEステートメントは、限定削除のため
に論理的に空になっているデータ・ページ18を処理す
る。テーブル走査動作でテーブル全体にわたるテーブル
・レーブル・ロックを獲得した場合、他のユーザまたは
アプリケーションは同時にそのテーブルを走査すること
ができない。したがって、行210−212で、「条件削除」
ページは、古くなったデータのみを含み、それらの内容
は同時にユーザまたはアプリケーションによって変更で
きないので、無視される。この場合も、不必要なロック
及び読取りアクセスが回避される。テーブル走査がテー
ブル・レベル・ロックを有せず、その代わりにページ・
レベル・ロッキングが活動状態にある場合は、行213−2
27が実行されて、そのページに関する共用ロックが要求
され（行215）、さらに、ロックが得られたとき、その
ページが少なくともいくつかの最新データを含む場合は
（行216）、そのページがアクセスされ読み取られる
（行217−223）。ロックが得られたとき、ページが依然
として論理的に空であり、古くなったデータのみを含む
場合は（行224）、そのページは無視しても安全であ
り、何も実行されず、やはり不必要なロックが回避さ
れ、論理的に空のデータ・ページが読み取られる。

行228の第３のCASEステートメントは、少なくともいく
つかの最新データを含むページ18を識別する、「一部満
杯」または「満杯」というデータ・ページ状況標識26の
値を取る。テーブル走査動作がテーブルに対するテーブ
ル・レベル・ロックを獲得しなかった場合（行230−23
2）、そのページは共用モードでロックされる（行233−
234）。次に、そのページがすでにバッファ内にない場
合、データ・ページがアクセスされ、読み取られる。

SELECT構造は行241で終了し、次のデータ・ページ18に
ついて内側DOループ（行203−242）が繰り返される。現
セグメント16の最後のデータ・ページが内側DOループを
介して処理されると、テーブル全体が走査されるまで、
そのテーブルの次のセグメント16について外側DOループ
（行201−243）が繰り返される。

Ｅ−５ セグメント化されたテーブル空間への挿入 表３に、本発明によるセグメント化されたテーブル空間
16中のデータ・ページ18にデータを挿入するための方法
の疑似コードによる実施態様を示す。

表３に示した挿入動作の疑似コードによる実施態様は、
２つの主要部分を有する。すなわち、新しいデータの挿
入が可能なデータ・ページ18を探し出すための２つのネ
ストされたDOループの組（行301−321）と、データをロ
ックし、フォーマットし、読み取り、記録し、ページに
挿入し、さらに、空間マップ・ページ14上のセグメント
制御ブロック20内のページの状況標識26を更新するため
の後続の一連のモジュール（行322−329、330−352、35
3−356及び357−368）である。

行301と321の間のネストされたDOループは、新しいデー
タの挿入が可能な最初の使用可能なデータ・ページ18を
探し出す。行301と321の間の外側ループは、テーブル空
間の空間マップ・ページ14に沿ってテーブルのセグメン
ト制御ブロック20連鎖をたどることにより、テーブルの
セグメント16をループする。行303と320の間の内側DOテ
ーブルは、非満杯データ・ページ18が見つかるまで、セ
グメント制御ブロック20のデータ・ページ状況標識26の
リストを読む。「満杯」以外の状況標識26が見つかると
（行304）、DOループを出て、ロック、フォーマット、
読取り等のための一連のモジュールが開始される。セグ
メント16内のすべてのデータ・ページ18が満杯と示され
た場合は（行317）、内側DOループを出て、非満杯デー
タ・ページ18が見つかるまで、次のセグメント16につい
て外側ループを繰り返す。非満杯ページが見つからない
場合は、新しいセグメントがテーブルに割り振られる
（行322−329）。

一旦、データ・ページ18がロックされると、必要に応じ
て行332−343で再フォーマットされるか、または344−3
51で読み取られる。取られる処置はページの状況標識26
の値によって決まる。「未フォーマット」及び「大量削
除」標識26を有するページ18は最初に読み取られずに再
フォーマットされ、「一部満杯」または「条件削除」標
識を有するページは再フォーマットせずに読み取られな
ければならない。行331と352の間のSELECT構造は、それ
ぞれ「未フォーマット」、「大量削除」及び「一部満
杯」、または「条件削除」状況標識を処理する３つのCA
SEステートメントを含む。

ページが「未フォーマット」の場合は、データが挿入さ
れる前に読み取る必要はない。したがって、そのページ
に空のバッファ（２進０にセットされた）が割り当てら
れ（行334）、ログ標識REDOONLYをもつフォーマット・
ログ・レコードが書込まれ（行335）、次に、その空の
バッファがデータを含まないページとしてフォーマット
される（行336）、このときバッファは新しいデータを
挿入され、記録され、物理的記憶域に書込まれる準備が
できている。

大量削除の結果、古くなったデータのみを含む「大量削
除」ページは行338−343で処理される。未フォーマット
・ページと同様、大量削除されたページは読まれない。
その代わり、２進０にセットされた空のバッファがその
ページに割り当てられ、フォーマット・ログ・レコード
が書込まれる（行340−341）。大量削除されたページが
再フォーマットされるときに書かれるフォーマット・ロ
グ・レコードは、REDO ONLYログ標識及びNONZERO PHY
SICAL PAGEログ標識を含む。NONZERO PHYSICAL PAGE
ログ標識は、後で「データの保全性」の項で説明するよ
うに、整合性のない記憶データがあるかどうか検査する
ためにシステム再始動中に使用される。フォーマット・
ログ・レコードが書込まれた後は、このとき空のバッフ
ァは、データを含まないページのためのヘッダ及びフッ
タでフォーマットされ（行342）、そのページは行353−
364のロギング及び挿入モジュールを適用する準備がで
きている。

新しいデータが挿入されるページ18が「一部満杯」また
は「条件削除」（条件削除で古くなったデータのみを含
むページになるため論理的に空）である場合は、ページ
18は再フォーマットされてはならないが、その代わり
に、その既存の内容の「前のイメージ」が記録されるこ
とが可能なように、アクセスされ、読み取られなければ
ならない。行344のCASEステートメントが、行345−351
でアクセスされて読み取られ、次いで行353−364のロギ
ング及び挿入モジュールで処理されるページを識別す
る。

データ・ページ18が必要に応じて再フォーマットまたは
読み取られると、行353−364のロギング及び挿入モジュ
ールは、ページの前後のイメージのログ・レコードを書
込み、新しいデータをページに挿入する。行355での挿
入には、ページ18の新しい内容を物理的記憶域に書き込
むことを含む。

挿入動作の最後のステップは、空間マップ・ページ14の
そのセグメント制御ブロック20におけるデータ・ページ
の状況標識26を更新することである（行357−364）。新
しい挿入でページが満杯になり、そのページにそれ以上
データを受け入れることができなくなった場合（行35
8）、ページの状況標識26は「満杯」にセットされる
（行359）。そうでない場合は、ページの状況標識26が
「一部満杯」にセットされる（行360−361）。行362で
空間マップ・ページの前後のイメージのログ・レコード
が書込まれ、変更されたデータ・ページ状況標識26を含
むセグメント制御ブロック20が空間マップ・ページ14上
で更新される（行363）。この更新は、更新された空間
マップ・ページ14を物理的記憶域に転送することを含
む。

Ｅ−６ セグメント化されたテーブル空間でのデータの
保全性 データベース管理システムは、ユーザまたはアプリケー
ションが矛盾したデータにアクセスすることを防止しな
ければならない。このデータの保全性の必要性は、有用
なデータベース管理システムにとって欠くことのできな
い要件である。ページがバッファから物理的記憶域に転
送されている間にシステムが破壊し、物理的に記憶され
たページの最初の部分が更新されたデータを含み、ペー
ジの最後の部分が古くなったデータを含んだままである
場合、データ・ページ18は矛盾したデータを含む可能性
がある。

この状態を検出するための好ましい方法は、２つの保全
性検査ビット、すなわち、ページの始めの１ビットと終
わりの１ビットを保持することである。整合性のあるデ
ータを含むページでは、これらの２ビットは同じ値を有
する（すなわち、共にオンか、または共にオフにな
る）。保全性ビットが異なる場合は、ページのデータは
矛盾したものとして扱われる。ページが物理的記憶域に
転送されるたびに、保全性ビットが反転される（オフか
らオンに、またはオンからオフに変更される）。ページ
が部分的にのみ転送された場合は、２つの保全性ビット
が一致しなくなる。

前述のように、入出力読取り（すなわち、ページ・アク
セス及び読取り）は、大量削除によって生じた論理的に
空のページが挿入動作に使用されるときは、実行されな
い。入出力読取りが実行されないので、物理的に記憶さ
れたページに関する保全性ビットの値は不明である。こ
のため、新たに挿入されたデータを含む再使用されたペ
ージが部分的にのみ物理的記憶域に転送された場合、ペ
ージの始めの新しい保全性ビットが、物理的に記憶され
たページの終わりの古い置き換えられていない保全性ビ
ットと一致するかも知れないので、矛盾した状態が検出
できない可能性が残る。

この検出不能な矛盾したデータの可能性を回避するた
め、大量削除されたページが再フォーマットされるとき
に書込まれるページ・フォーマット・ログ・レコード
に、NONZERO PHYSICAL PAGEログ標識が含まれる（表
３の行329）。NONZERO PHYSICAL PAGEログ標識は、シ
ステム再始動中にフォーマット・ログ・レコードを再び
適用して、物理的に記憶されたページの内容を２進０で
置き換えなければならないことを示す。先行書込みログ
ギングを使用するデータベース管理システムは通常、ペ
ージが更新されるとき、ページ・ヘッダ及びログ・レコ
ードの両方にタイムスタンプ値を入れる。フォーマット
・ログ・レコードにNONZERO PHYSICAL PAGEログ標識
がなければ、たとえページが実際には部分的にのみ転送
された場合でも、物理的に記憶されたページのタイムス
タンプがログ・レコードのタイムスタンプと一致するの
で、再始動中にシステムは、前に大量削除され、このと
き更新されたページが首尾よく物理的記憶域に転送され
たものと見なすはずである。NONZERO PHYSICAL PAGE
ログ標識を用いる場合、システムはまずページを２進０
にセットし、次にそれを新たに挿入されたデータでリセ
ットする。セグメント化されたテーブル空間10における
データの保全性を保証するこの方法は、先行書込みロギ
ングの使用に基づいており、データベース管理システム
は、更新されたページを物理的記憶域に転送する前に、
更新されたログ・レコードを書くことを強制される。

データの保全性を保証するためのこの方法の疑似コード
による実施態様を表４に示す。

表４に示したデータの保全性を保証する方法は、２つの
独立したモジュール、すなわち、ページからデータを読
み取る前に保全性ビットを検査するためのモジュール
と、新しいデータがページに書き込まれるときに保全性
ビットをセットするためのもう１つのモジュールから成
る。行401−409の第１のモジュールは、ページ18が読み
取られるようとするとき、ページ18の保全性ビットを検
査する（行401）。ページの始めと終わりの保全性ビッ
トが同じ値を含まない場合は（行403）、ページは損傷
を受けたものとしてマークされる（行404）。損傷を受
けたページは、ログ・レコードを使ってページを回復す
ることにより、その最後の整合性のある状態に戻される
（行405）。ページの保全性ビットが一致する場合は、
何も行なわれず（行406−408）、ページはただちに正常
に読み取られることが可能である。

データ保全性を保証する方法の第２のモジュール（行41
0−412）は、ページがバッファから物理的記憶域に転送
されようとするとき、保全性ビットをリセットする（行
410）。そのような転送の前に、保全性ビットが反転さ
れる。ビットが現在オンである場合は、オフに変更（反
転）され、現在オフである場合は、オンに反転される
（行401）。

セグメント化されたテーブル空間10におけるデータの保
全性を保証するための上記の方法を用いると、データ・
ページのロッう及び読取りを最小限にするための本発明
の方法を使って、読取り及び挿入動作中に必要なページ
・アクセス回数を減少させ、それによってデータベース
管理システムの処理能力をある程度向上させることがで
きる。

例示のために特定の実施例及び実施態様について説明し
たが、本発明の精神及び範囲から逸脱することなく種々
の変更を加えることができることを理解されたい。たと
えば、ページの不必要なロック及び読取りを回避できる
ようにデータ・ページの状況をページとは別に記憶する
という本発明の基本的要件を満たしている限り、異なる
編成のセグメント化されたテーブル空間に本発明を適用
することができる。さらに、本発明はリレーションナル
・データベース管理システムに限定されたものではな
く、他の種類のコンピュータによるデータ処理システム
にも有効に適用することができる。

F.発明の効果 本発明を用いればデータベース・システム等における操
作を高速化することができる。

【図面の簡単な説明】

第１図は、本発明の好ましい実施例の方法に必要なセグ
メント化されたテーブル空間を示す。 第２図は第１図のセグメント化されたテーブル空間とそ
れに関連する空間マップ・ページを示す。 第３図は第２図の空間マップ・ページのセグメント制御
ブロックのフォーマットを示す。

───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 昭62−85355（ＪＰ，Ａ)

Claims (1)

【特許請求の範囲】
1. 【請求項１】少なくとも一つのデータ記憶装置を含むコ
   ンピュータ化データベース管理システムにより管理され
   る、複数のデータページからなる物理的記憶空間にある
   前記データページにアクセスする方法であって、 （ａ）単一のデータ実体のためのデータを前記データ記
   憶装置により任意のデータページに記憶する段階と、 （ｂ）前記データページの状態表示子を各ページ毎に前
   記データ記憶装置により記憶する段階と、 （ｃ）選択されたデータページの状態を前記状態表示子
   に基づいて決定する段階と、 （ｄ）前記選択されたデータページに記憶されたデータ
   実体のデータが全部削除されたために前記選択されたデ
   ータページはデータを含んでいないか古くなったデータ
   しか含んでいないことを前記選択されたデータページの
   前記状態表示子が示す場合、前記選択されたデータペー
   ジへのアクセスをスキップする段階と、 （ｅ）前記選択されたデータページに記憶されたデータ
   実体のデータの一部が削除されたために前記選択された
   データページはデータを含んでいないか古くなったデー
   タしか含んでいないことを前記選択されたデータページ
   の前記状態表示子が示す場合、前記選択されたデータペ
   ージをロックし、前記選択されたデータページにその後
   最新データが取入れられたときにはじめて前記選択され
   たデータページを読出す段階と、 （ｆ）前記データ実体のデータ全部の削除中、前記デー
   タ実体のデータページをロックする段階と、 よりなるデータページにアクセスする方法。