JPH0467660B2 - - Google Patents

Description

【発明の詳細な説明】 技術分野 本発明はチエイン探索方法に関し、特に電子計
算機システムにおいて補助記憶装置に格納された
チエイン構造をもつフアイル内のレコード順序性
を認識するためのチエイン探索方式に関する。

従来技術 磁気デイスクなど補助記憶装置に記録されるレ
コードの順序性を表現する方式として、始点レコ
ードから論理的に番目のレコード内に＋１番
目のレコードアドレスをポインタとして記録する
方式がある。以下、この記録方式によつて記録さ
れたレコードの格納されている補助記憶装置内の
領域をチエインフアイル、１つの始点レコードか
らポインタによつて連結されているレコードの集
まりをチエインと夫々呼ぶ。

各レコードが始点レコードから何番目のレコー
ドであるかを認識するための従来方式としては、
何らかの手段によつて始点レコードを補助記憶装
置から主記憶装置に読込んだ後、各レコードに記
録されたポインタから次のレコードのアドレスを
得て、該レコードの属するページを直アクセス手
段により主記憶装置に読込む操作を繰返して、終
点レコードまでたどる方式がある。

ここにページとは補助記憶装置と主記憶装置と
の間の物理入出力単位であり、以下補助記憶装置
と主記憶装置との間でページを入出力するための
操作をページIOと呼ぶ。

第２図は４個のページからなるチエインフアイ
ルの例であり、チエインフアイル内には１個のチ
エインを構成する７個のレコードが格納されてい
る。aiは各レコードのアドレスを示し、ａ４は始
点レコード、ａ５は終点レコード、その他はすべ
て中間レコードである。

従来方式においては、ある始点レコードに対応
するチエイン全体が１つのページ内に閉じて格納
されている場合は、主記憶に読込んだページ内を
探索できるため、１個のページIOで終点レコー
ドまでたどることができる。

しかし、この第２図のようにチエインが複数個
のページに跨つて記録されている場合は、読込ん
だページをすべて記憶しない限り、各レコード毎
にページIOを必要とする。第２図においては始
点レコードはチエインフアイル内で１個のみであ
るが、チエインフアイル内に多数の始点レコード
とそれらレコードから始まるチエインが存在し、
各チエインがページに跨つているような場合は、
すべてのチエインをたどるためにはフアイル当り
のレコード件数に等しい回数のページIOが必要
である。

さらに、第３図に示すように、順序性を規定す
るポインタが複数種類あるときは、フアイル当り
のレコード件数とレコード当りのポインタ数の積
に相当するページIOが必要になる場合がある。

発明の目的 本発明は以上述べてきた従来技術の問題点を解
決すべくなされたものであり、その目的とすると
ころは、ページIOの削減を図つたチエイン探索
方法を提供することである。

発明の構成 本発明によれば、チエインフアイル内の各レコ
ードの順序性を認識するチエイン探索方法であつ
て、前記チエインフアイルのページをチエインフ
アイルの先頭から順次主記憶内に読込む第１のス
テツプと、チエインフアイル内の各レコードにつ
いて、そのレコードの格納アドレスと前記レコー
ド内のポインタとの組から、（Ａ，Ｂ，Ｃ，Ｎ）
の４つのフイールド（Ａ及びＣは始点、終点、中
間の各レコードに応じてそのアドレス及びポイン
タを記録するフイールド、Ｂは始点、終点、中間
の各レコードに応じて０，１または２を記録する
フイールド、Ｎはレコードの順序を示すフイール
ド）からなるフイールドレコードを生成して分類
用作業フアイルに格納する第２のステツプと、前
記分類用作業フアイルの前記フイールドレコード
について前記フイールドをキーとして昇順に並べ
換えを行う第３のステツプと、この並べ換え後の
分類用作業フアイルの互いに隣接するフイールド
レコードの各々に関して所定の規則に従つて互い
に突合せ処理を行いその突合せが一定の関係にあ
るフイールドレコードを結果フアイルに格納し、
それ以外のフイールドレコードの突合せ結果を突
合せ用作業フアイルに格納する第４のステツプ
と、前記第４のステツプの終了に応答して前記突
合せ用作業フアイルの内容を前記分類用作業フア
イルへ複写して前記第３のステツプから前記第４
のステツプを繰返し行う第４のステツプとを含
み、前記突合せ用作業フアイルにフイールドレコ
ードが一件も出力されなくなつたときの前記結果
フアイルのフイールドレコードの前記Ｎフイール
ドにより、チエインフアイル内の任意のレコード
がチエインフアイル内の最初のレコードから幾つ
チエインをたどれば到達できるかを示す情報を得
るようにしたことを特徴とするチエイン探索方法
が得られる。

実施例 以下、本発明の実施例を図面を用いて説明す
る。

本発明の実施例のブロツク図を第１図に示す。
第１図において、補助記憶装置１１〜４１は必ず
しも異なる装置である必要はなく、チエインフア
イル１１、結果フアイル２１、突合せ用作業フア
イル３１、分類用作業フアイル４１の全部または
これらの任意の組合せを同一の補助記憶装置に配
置してもよいが、第１図ではこれらフアイルは全
て異なる補助記憶装置に配置されているものとし
て示している。

制御手段５は順アクセス手段１を用いてチエイ
ンフアイルを読み順序性を認識するために必要な
レコードを順アクセス手段４を用いて分類用作業
フアイル４１に出力し、その後分類手段６と順ア
クセス手段３、順アクセス手段４を繰返し用いて
分類用作業フアイル４１と突合せ用作業フアイル
３１との間でレコードを複数回移し変えながら、
順序性の決定したレコードを順アクセス手段２を
用いて結果フアイル２１へ出力する。

本発明の前提となるチエインフアイル１１の条
件を第２図によつて説明する。

(1) aiはレコードアドレスを示し、各レコードを
チエインフアイル１１内で一意に識別するもの
であれば、その表現形式は任意である。ただ
し、ページを読込んだときにai値が判別できる
ことが必要である。

(2) レコードの第１フイールドはポインタを示
し、第２フイールドはレコードがチエインの始
点であるか（第２図では“Ｓ”）、終点であるか
（第２図では“Ｅ”）、中間であるか（第２図で
は空白）を示すフラグである。ポインタおよび
フラグの位置、フラグの値は該レコード自身ま
たは外部からの指示により判別できる限り任意
である。

分類用作業フアイル４１、突合せ用作業フアイ
ル３１及び結果フアイル２１には、夫々４個のフ
イールドで構成される新たなフイールドレコード
（Ａ，Ｂ，Ｃ，Ｎ）が格納される。第１及び第３
フイールドＡ，Ｃには、始点、終点、中間の各レ
コードに応じてそのアドレスやポインタが記録さ
れ、第２フイールドＢには、同じく始点、終点、
中間の各レコードに応じて０，１または２の各値
が記録され、第４フイールドＮにはレコードの順
序性を示す整数値が記録されるもので、具体的に
は以下のとおりである。

(1) Ｂ＝０かつＮ＝０ならば、チエインフアイル
内のレコードはチエインフアイル内のレコード
Ａからチエインをたどつて２のＧ乗番目（2^Gで
あり、ここにＧは整数値レジスタの値であつて
後述する突合せ用作業フアイル３１へ突合せ処
理結果を何回繰返し格納したかの回数を表わ
す）に当ることを示す。

(2) Ｂ＝０かつＮ≠０ならば、チエインフアイル
内のレコードＡは始点レコードからチエインを
たどつてＮ番目にあたることを示す。

(3) Ｂ＝１かつＮ＝０ならば、チエインフアイル
内のレコードＡはレコードＮからチエインをた
どつて２のＧ乗番目にあたることを示す。

(4) Ｂ＝２のときはチエインフアイル内のレコー
ドＡは終点レコードであることを示し、この場
合はＣ＝０，Ｎ＝０である。

以下の説明では、分類用作業フアイル４１、突
合せ用作業フアイル３１及び結果フアイル２１の
各フイールドレコードの内容を上述した（Ａ，
Ｂ，Ｃ，Ｎ）の形式で示し、例えば、第４図Ａの
最初のレコードは（a6，０，a1，０）で表わさ
れる。

本発明は第３図のように順序性を規定するポイ
ンタが複数種類ある場合、またフアイル内に複数
の始点レコードがある場合にも容易に応用できる
ので、第２図のチエインフアイル１１について、
第１図にもとづき手順の詳細を説明する。

(1) 訟御手段５は順序アクセス手段１を用いてチ
エインフアイル１１の先頭からページを順次的
に主記憶装置に読込み、チエインフアイル１１
のすべてのレコードにつき、以下の（１−１），
（１−２），（１−３）のいずれかの操作を行う。

(1‐1) レコードaiが始点レコードならば、
［ai，０，ai，０］なるフイールドレコード
を生成して結果フアイルに出力し［aiのポイ
ンタ、０，ai，１］なるフイールドレコード
を生成して分類用作業フアイル４１に出力す
る。

(1‐2) レコードaiが終点レコードならば、
［ai，２，０，０］なるフイールドレコード
を生成して分類用作業フアイル４１に出力す
る。

(1‐3) レコードaiが中間レコードならば、［ai
のポインタ、０，ai，０］なるフイールドレ
コードと、［ai，１，aiのポインタ、０］な
るフイールドレコードを生成し、分類用作業
フアイル４１に出力する。

チエインフアイル１１内のレコードが全て始点
レコードであれば処理を終了し、そうでなければ
レジスタＧの値を０にして分類手段６に制御を渡
し、(2)へ行く。

(2) 分類手段６は分類用主記憶装置７を使用しつ
つ、分類用作業フアイル４１のレコードをその
第１フイールド、第２フイールド、第３フイー
ルドをキーとして昇順に並び換えて、制御手段
５に制御を返す。

(3) 制御手段５は分類用作業フアイル４１の先頭
からレコードを読込み前後のレコードを比較し
ながら（31）〜（36）のいずれかの処理を分類
用作業フアイル４１の終端に達するまで繰り返
す。（31）〜（36）において、Ap，Bp，Cp，
Npは分類用作業フアイル４１の先頭からｐ番
目のレコードの第１、第２、第３、第４フイー
ルドの値を示す。

（31） Ap＝Ap＋１，Bp＋１＝１，Np＝０な
らば、［Cp＋１，０，Cp，０］及び［Cp，１，
Cp＋１，０］なるフイールドレコードを突合
せ用作業フアイル３１に出力し、ｐ＝ｐ＋２と
する。すなわち、チエインフアイル内のレコー
ドApがチエインフアイル内のレコードCpから
２のＧ乗番目にあたり、チエインフアイル内の
レコードCp＋１がAp（＝Ap＋１）から２のＧ
乗番目にあたるため、Cp＋１がCpから２のＧ
＋１乗番目にあたり、チエインの先頭から何番
目にあたるかは未確定であることを示す情報を
次のＧ＋１回目の処理のために保存する。

（32） Ap＝Ap＋１，Bp＋１，Np≠０であれ
ば、［Ap，０，Cp，Np］及び［Cp＋１，０，
Cp，Np＋２のＧ乗］なるフイールドレコード
を突合せ用作業フアイル３１に出力し、ｐ＝ｐ
＋２とする。すなわち、Apは始点フイールド
からチエインをたどつてNp番目であり、かつ
Cp＋１はApから２のＧ乗番目にあたり、Cp＋
１はCpからNp＋２のＧ乗番目にあたるため、
Apは始点レコードCpからNp番目であり、Cp
＋１はCpからNp＋２のＧ乗番目にあたること
を示す情報を次のＧ＋１回目の処理のために保
存する。

（33） Ap＝Ap＋１，Bp＋１＝２，Np＝０な
らば、ｐ＋１番目のレコードを突合せ用作業フ
アイル３１に出力し、ｐ＝ｐ＋２とする。

（34） Ap＝Ap＋１，Bp＋１＝２，Np≠０な
らば、ｐ番目のレコードを突合せ用作業フアイ
ル３１に出力し、ｐ＝ｐ＋２とする。

（35） Ap≠Ap＋１，Bp＝Bp＋１＝０，Np＝
０ならば、ｐ＝ｐ＋１とする。

（36） Ap≠Ap＋１，Bp＝Bp＋１＝０，Np≠
０ならばｐ番目のレコードを結果フアイル２１
に出力し、ｐ＝ｐ＋１とする。

制御手段５は分類用作業フアイル４１の終端に
達すると、下記の操作を行う。

（37） 最終レコードの第４フイールドが０のと
きは（38）へ行き、０でなければ最終レコード
を結果フアイル２１へ出力して（38）へ行く。

（38） 前記繰返し処理中に突合せフアイル３１
へ１件もレコードが出力されなければ処理を終
了し、そうでなければ(4)へ行く。

(4) 制御手段５はレジスタＧに１を加算し、突合
せ用作業フアイル３１の内容を分類用フアイル
４１に複写して分類手段６に制御を渡し、(2)へ
行く。

以上のように、分類処理を繰返す過程におい
て、結果フアイル２１には、［自アドレス、０、
始点レコードアドレス、始点レコードからの相対
番号］なる形式のレコードが蓄積され、チエイン
フアイル１１内の全てのレコードの順序性が認識
できる。

第４図を用いて手順の詳細を補足説明する。第
２図のチエインフアイル１１を入力して前記手順
(1)を実行すると、分類用作業フアイル４１の内容
は第４図Ａのようになり、結果フアイル２１には
第４図のＣで示すレコードが出力される。

手順(2)により第４図Ａを分類すると分類用作業
フアイル４１は第４図Ｂで示す状態になる。Ｇ＝
０のとき、手順(3)を実行すると第４図Ｄで示す突
合せ用作業フアイル３１が作成され、手順(4)でＧ
＝１として手順(2)により分類すると分類用作業フ
アイル４１は第４図Ｅで示す状態になる。

Ｇ＝１のとき、手順(3)を実行すると第４図Ｆで
示す突合せ用作業フアイル３１が作成され、手順
(4)でＧ＝２として手順(2)による分類すると分類用
作業フアイル４１は第４図Ｇで示す状態になる。

Ｇ＝２のとき、手順(3)を実行すると第４図Ｈで
示す突合せ用作業フアイル３１が作成され、第４
図Ｊで示すレコードが結果フアイル２１に追加さ
れ、手順(4)でＧ＝３として手順(2)により分類する
と分類用作業フアイル４１は第４図Ｉで示す状態
になる。

Ｇ＝３のとき、手順(3)を実行すると第４図Ｋで
示すレコードが結果フアイル２１に追加される
が、突合せ用作業フアイル３１にはレコードが出
力されないので、処理を終了する。

前記のように手順を繰返すことにより、結果フ
アイル２１へは第４図Ｃ、第４図Ｊ及び第４図Ｋ
で示すレコードが蓄積される。よつて、この結果
フアイルの内容により各レコードの順序性が認識
可能となる。

以上要約すれば、順アクセス手段１を用いてチ
エインフアイル１１内のページをすべて読込み、
各レコードの順序性を認識するために必要なレコ
ードからなる作業フアイルを作成し、これ等をレ
コードに対して［log₂N］⁺＋１回の分類処理を繰
返すことにより、チエインフアイル内のすべての
チエインについて、各レコードのチエイン内での
順序性を認識するようにしているのである。

ここに、Ｎはチエインフアイルに含まれている
すべてのチエインについて、チエインを構成する
レコードから１引いた値の最大値をとつた値であ
り、［ ］⁺は小数点以下を切下げた整数値を示す
ものとする。

このように、チエインフアイル当りのページ数
に等しいページIO回数と作業フアイルに対する
ページIO回数との和でもつて、チエインフアイ
ル内のすべてのチエインの順序性が認識できるこ
とになり、［log₂N］⁺＋１回の分類操作の過程で
作業フアイルのレコード数は急激に減少する。

また、作業フアイルのページ当りのレコード数
を補助記憶装置の特性が許す限り最大化して作業
フアイルのページIOを削減できること、分類用
主記憶容量を大きくして分類作業フアイルのペー
ジIOを削減できるなど最適化が容易であるとい
う利点を有する。特に、ページに跨がるチエイン
の多いチエインフアイルに対しては、従来方式に
比し全体のページIOを削減できることになるの
である。

発明の効果 以上述べたように、本発明はチエインフアイル
に大量のレコードが格納されているとき、すべて
のレコードのチエイン内での順序性を一度に認識
する場合に効果がある。特に、チエインフアイル
内に異なる順序性を規定するポインタが何種類も
存在する場合に効果が著しい。

本発明はデータ間の論理的な関係をチエインで
表現してするデータベースの再編成処理やチエイ
ンの連結状態を検査する場合に応用できる。

【図面の簡単な説明】

第１図は本発明の実施例のブロツク図、第２図
及び第３図はチエインフアイルの例を示す図、第
４図Ａ〜Ｋは第２図のチエインフアイルについて
本発明を適用して順序性を認識する過程を示す図
である。 主要部分の符号の説明、１…順アクセス手段
１、２…順アクセス手段２、３…順アクセス手段
３、４…順アクセス手段４、５…制御手段、６…
分類手段、７…分類用主記憶、１１…チエインフ
アイル、２１…結果フアイル、３１…突合せ用作
業フアイル、４１…分類用作業フアイル。

Claims (1)

【特許請求の範囲】
1. １ チエインフアイル内の各レコードの順序性を
   認識するチエイン探索方法であつて、前記チエイ
   ンフアイルのページをチエインフアイルの先頭か
   ら順次主記憶内に読込む第１のステツプと、チエ
   インフアイル内の各レコードについて、そのレコ
   ードの格納アドレスと前記レコード内のポインタ
   との組から、（Ａ，Ｂ，Ｃ，Ｎ）の４つのフイー
   ルド（Ａ及びＣは始点、終点、中間の各レコード
   に応じてそのアドレス及びポインタを記録するフ
   イールド、Ｂは始点、終点、中間の各レコードに
   応じて０，１または２を記録するフイールド、Ｎ
   はレコードの順序を示すフイールド）からなるフ
   イールドレコードを生成して分類用作業フアイル
   に格納する第２のステツプと、前記分類用作業フ
   アイルの前記フイールドレコードについて前記各
   フイールドをキーとして昇順に並べ換えを行う第
   ３のステツプと、この並べ換え後の分類用作業フ
   アイルの互いに隣接するフイールドレコードの
   各々に関して所定の規則に従つて互いに突合せ処
   理を行いその突合せ結果が一定の関係にあるフイ
   ールドレコードを結果フアイルに格納し、それ以
   外のフイールドレコードの突合せ結果を突合せ用
   作業フアイルに格納する第４のステツプと、前記
   第４のステツプの終了に応答して前記突合せ用作
   業フアイルの内容を前記分類用作業フアイルへ複
   写して前記第３のステツプから前記第４のステツ
   プを繰返し行う第５のステツプとを含み、前記突
   合せ用作業フアイルにフイールドレコードが一件
   も出力されなくなつたときの前記結果フアイルの
   フイールドレコードの前記Ｎフイールドにより、
   チエインフアイル内の任意のレコードがチエイン
   フアイル内の最初のレコードから幾つチエインを
   たどれば到達できるかを示す情報を得るようにし
   たことを特徴とするチエイン探索方法。