JPH02217940A - データベース・アクセス・システム - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明は、多数のブロックから成るデータベースにアク
セスするためのシステムに関する。」１記ブロックの各
々は複数のデータ・ファイル及び各ブロック中に記憶さ
れたファイルのアクセス・キーを有するディレクトリを
含み、また上記データ・ベースは各ブロック中のアクセ
ス・キーが所定の関係を有するようにデータ・ファイル
のソート順序を生じさせるための手段を有する。

Ｂ、従来技術 大規模なシステムにおいて、記憶装置中の項目があるキ
ーに関して探索されなければならない場合、もし順次的
な探索を行わなければならないならば、それは非実用的
で且つ能率は低いであろう。

実際、所望の項目を見つけるために、平均的には、全項
目の半分を読み取らなければならない。これには、比較
的多数のディスク読み取り操作が関係する。過去におい
て、この多数回のディスク読み取り界作をＳ（少させる
試みが行われてきた。

上述の型のシステムは例えばカナダ国特許第９６４．３
７３号に記載されている。この従来技術のシステムにお
いて、１回のシーク及び１回の読み取り操作を行う事に
より、所定のファイル名のディスク・マスク・ファイル
からデータ・ファイルが読み取られるように、適当なフ
ァイル構成が提供されている。データ・ファイルの位置
を特定し読み取るプロセスは、ファイル名をハツシュ・
コーディングしてブロック・アドレスを生成し、そのブ
ロック・アドレスを有するディスク領域に読み取りヘッ
ドを移動し、そしてデータ・ファイルを読み出すために
ディレクトリ及びブロックの残りを読み取るステップを
伴う。ディレクトリ読み取りの間、データ・ファイル名
は、それらがディスクから読み取られる時に、所望のデ
ータ・ファイルの名前と実時間的に比較される。名前の
一致が生すると、ブロック中のデータ・ファイルのアド
レス及び同じブロック中の次のファイルのアドレスが読
み取られ記憶される。ディスクが回転する時、丁度読み
取られた所望のデータ・ファイルのアドレスが活性のデ
ィスク・アドレスと定常的に比較される。一致が生じる
時、ファイルの位置が見出されており、それが読み出さ
れる。読み取りは、次のファイルの開始アドレスで終了
する。

もしファイル名のハツシュ・コーディングにより示され
たブロックのディレクトリ中にファイル名が見出されな
い場合、ファイルはそこには存在しない。

特定のデータ・ファイルに夕・１するアクセス時間は、
もし上記の従来技術のシステムが使われたならばかなり
減少するが、その代わりに、他の欠点が導入される。即
ち、全てのファイル名のハツシュ・コーディングを用い
なければならない点である。このハツシュ・コーディン
グにより、特定のファイルが記憶されているブロックの
アドレスが検索できる。しかし、ハツシュ・コーディン
グのために、この従来技術の方法は、少なくともファイ
ル名の構造及びレイアウトを変更する事なく、既存のシ
ステムに適用する事はできない。

Ｃ１発明が解決しようとする課題 本発明の目的は、探索データの構造又はレイアウトに変
更を行う事なく、任意め°データベース探索機構に適用
可能で、且つディスク読み取り操作の回数従ってファイ
ル・アクセス時間のかなりの減少を生じるデータベース
・アクセス・システムを提供する事である。

Ｄ、Ａ’！題を解決するための手段 本発明によれば、この明細書の冒頭で述べた型のシステ
ムは、データベースがアクセスされる前に全てのブロッ
クのディレクトリが所定の順序で一度読み取られ、それ
により各ディレクトリ中のアクセス・キーの範囲が決定
され、その後に各アクセス動作の間に最初に、決定され
たアクセス・キー範囲に基づき、要求されたデ〜り・フ
ァイルの探索キーが存在するかもしれないこれらディレ
クトリがソート・アウトされ、その後ソート・アウトさ
れたディレクトリに対応するブロックのみが、要求され
たデータ・ファイルを探索される。

最初に各ブロックに関するアクセス・キーの範囲を確立
する事によって、その後の探索動作の間に、要求された
データ・ファイルの探索キーにアクセス・キーの範囲が
一致しない全てのブロックを探索から除去することが可
能である。従って、読み取り操作の回数をかなり減少さ
せることができる。アクセス・データの特別なコーディ
ングは不必要であり、従って本発明は原理的には任意の
既存のデータベース・アクセス・システムに適用が可能
である。

各ディレクトリの中のアクセス・キーの範囲は、各ディ
レクトリ中の最高及び最低のアクセス・キーにより定義
される事が好ましい。このようにして各ディレクトリ中
のアクセス・キーの範囲を定義する事により、探索キー
は、２つの項目即ち前述のディレクトリの最高及び最低
のアクセス・キーと比較するだけで、探索キーが上記最
高及び最低の探索キーに囲まれる範囲内に存在しうるか
又は否かを見出す事ができる。「最高」及び「最低」と
いう用語は、データ・ファイルがソートされる方式に関
係している事は明らかであろう。

好ましくは、検索されたアクセス・キー範囲の集合は、
別個の読み取り操作なしにそれらのアクセス・キー範囲
がデータベース・アクセス・システムに直接アクセス可
能であるような方式で記憶される。従って、特定のデー
タ・ファイルに関する探索において不必要な遅延が避け
られる。

Ｅ、実施例 第１図はディスク・メモリ上の多数の物理ブロック１〜
７を示している。その各々は、多数のデータ・ファイル
及びディレクトリを含み、ディレクトリ中には関連ブロ
ック中のデータ・ファイルの各々に関するアクセス・キ
ーが結合されている。

例えば、ブロック１に記憶されているデータ・ファイル
はファイル１．１、ファイル１．２、ファイル１．Ｎで
あり、ブイレフ１へり・セクション中の対応するキーは
キー１．１、キー１．２、キー１゜Ｎである。

本発明によれば、最初に、種々のディレクトリが全て一
度所定の順序で読み取られ〈例えばブロック１から始ま
ってブロック７まで、しかし、この順序は任意である）
、各ディレクトリ毎に（例えば英数字の順で）最高及び
最低のアクセス・キーが、全てのキーを読み取る小によ
って決定される。従って、各ブロック毎に可能なキーの
範囲が見出される。

第２図において、各キーが符号語、パスワード等の英数
字のストリングにより表されていると仮定して、ソート
されたキーが示されている。これらのパスワードは、第
２図中に例として示されている。

ディレクトリは第２図の左側に示されている。

第２図の中央に矢印で図示されているように、各ディレ
クトリの最高及び最低の探索キーが検索され、第２図の
右側に示されているように別個のアクセス・キー高／低
表に記憶される。この高／低表は、その後の探索手続き
において、特定の探索キーがあるディレクトリに存在す
るか否かを見出すために使用される。

探索キー：　ＢＲＯＯＤ、ＡＡＰＡＬＦＡ、ＭＵＩＴ、
ＺＥＢＲＡ、ＴＥＡＣＵＰ及びＺＱＱＸＸＸを有する６
つの異なったレコードを探索したいものと仮定する。最
初の探索キーＢＲＯＯＤから出発して、この探索キーを
高／低表と比較すると、探索キーＢＲＯＯＤはディレク
トリ１及び７に存在する可能性がある。この探索キーは
他の全てのディレクトリ中には確かに存在しない。第２
の探索キーＡ　Ａ　Ｐ　Ａ　！、、、　Ｆ　Ａはデイレ
クトリフ中にのみ存在する可能性がある。第３のキーＭ
ＵＩＴはディレクトリ２．５及び７中に存在する可能性
がある。第４のキーＺＥＢＲＡはディレクトリ３及び４
中に存在する可能性かある。探索キーＴＥＡＣＵＰはど
のディレクトリ中にも存在しないが、最後の探索キーＺ
ＱＱＸＸＸはディレクトリ４中にのみ存在する可能性が
ある。まとめると、大工 ｆｆ１＝Ｆ二　　　　　　　存在しうるブロックＢＲＯ
ＯＤ　　　　　　　　　１及び７Ａ、　Ａ　Ｐ　Ａ　Ｌ
　Ｆ　Ａ、　　　　　　　７ＭｔＪＩＴ　　　　　　　
　　　　２．５及び７ＺＥＢＲＡ　　　　　　　　　　
３及び４ＴＥＡＣＵＰ　　　　　　　　　なし ＺＱＱＸＸＸ　　　　　　　　４ 種々の探索キーの位置を求めるために最大で９回のディ
スク読み取りが必要である。しかしながら、明らかに、
探索キーの一つを見出すためのディスク読み取りの平均
回数は実際は最大値の５０％であり、言い換えると、こ
れらすべての探索キーを見出すのに必要なディスク読み
取りの平均回数は９／２＝４．５である。別個の記憶域
に高／低表を構成するのに必要な最初の７回のディスク
読み取りを一緒にすると、これら６個の探索キーを見出
すのに必要なディスク読み取りの回数は９の５０％に７
を足したもの即ち１１．５である。

高、／１表を用いなければ６個の探索キーの各々につき
、７つのディレクトリの各々を別個にアクセスしなけれ
ばならない。これは最大で６×７＝４２回のディスク読
み取りが必要な事を意味し、ディスク読み取りの平均回
数は４２の５０％で２１である。

従って、本発明を用いると、ディスク読み取りの回数が
大幅に減少する。

高／低表の構成に必要な初期のディスク読み取りの数の
彰害は、その後の探索動作の数が増加すると共に減少す
る。

ファイルを種々のブロック中に記憶する前にファイルが
より良くソートされていれば、ディスク操作の数が大幅
に減少する事は、明らかであろう。

全てのファイルがアクセス・キーの英数７順にソートさ
れ、その後連続した記憶ブロック中にこの順番で記憶さ
れていると仮定すると、特定の探索キーに対応するファ
イルを見つけ出すのに１回だけのディスク読み取り操作
しか必要でない。全てのファイルが完全に芙数字順にソ
ートされていると、どのアクセス・キー範囲も他のアク
セス・キー範囲と重なりを示さない、、Ｎい換えると、
各探索キー毎に、この特定の探索キーがアクセス・キー
として存在しうるただ一つのアクセス・キーの範囲が存
在する。

しかしながら、不幸な事に、いかなる活動状態のデータ
ベースにおいても探索動作のみならず更新動作が実行さ
れる。言い換えると、データがデータベースに付加され
又はデータベースから削除され、その結果ファイルの英
数字順序は乱され、データベースが長く使われるほど、
英数字順序は消失する。従って、少なくともある程度の
順序が存在し、本発明の適用によりかなりの利益が生じ
る事を保証するように定期的な間隔で全てのファイルの
ソート動作を行う事が望ましい。

実験目的のために、大規模計算機システムのユーザーに
ついての記述が記憶されたデータベースに本件発明が適
用された。このデータベースにより、各ユーザーはその
記述中に指定された計算機システムの部分にのみアクセ
スする事ができる。

ユーザー・データベースはディスク記憶媒体上の複数の
データのブロックより成っている。ディスク記憶装置上
の各ブロックは４にのサイズを有し、１６９人までのユ
ーザーの記述を収容できるスペースを提供している。も
し従来技術の探索技術が使用されるならば、ユーザーに
関する情報が必要になる度に、ブロックが一つづつ読み
取られ関連のユーザーに関するブロックが見付かるまで
走査されなければならない。これは、もし非常に多くの
ユーザーが同時にシステムにログオンしようとすると重
大な結果を引き起こすであろう。これは、システムが再
始動した後によくある状況である。

この時、応答時間は、ディレクトリに関する長いＩ１０
キューにより、最初の半時間程度の間極めて長くなるで
あろう。約１７００人の登録されたユーザーをカバーす
るデータベースの場合、従来技術の探索方法と本発明に
よる探索方法との比較結果は下記の通りである。

従来技術の探索方法： 延ム取ユ皿敗　　秋対町ｒす側 平均　　　　　　５２　　　　　２ Ｒ悪時　　　　１０５　　　　　６ 本発明の探索方法： 読み取り回数　　経過時間（秒） 平均　　　　　　１．２　　　　　　０．４最悪時　　
　　３０．９ 上述のシステムにおけるユーザーの数が５００００Å以
上に拡大されたならば、本発明による探索機構は、毎秒
当たり約３００回のディレクトリに対する読み取りを回
避する。

Ｆ１発明の効果 本発明によれば、探索データの構造又はレイアウトに変
更を行う事なく、任意のデータベース探索機構に適用可
能で、且つディスク読み取り操作の回数従ってファイル
・アクセス時間のかなりの減少を生じるデータベース・
アクセス・システムが提供される。

【図面の簡単な説明】

第１図はディスク・メモリ上の多数の物理ブロックを示
す図、 第２図は記憶ブロックのソートされたディレクトリ及び
対応する高／低アクセス・キー表を示す図である。 出願人　インターナショナル・ビジネス・マシーンズ・
コーポレーション

Claims (2)

【特許請求の範囲】
1. （１）複数のブロックから成り上記ブロックの各々は複
   数のデータ・ファイル及び各ブロック中に記憶されたフ
   ァイルのアクセス・キーを有するディレクトリを含むデ
   ータベースにアクセスするためのシステムであって、 上記データベースがアクセスされる前に上記ブロック全
   てのディレクトリを読み取り各ディレクトリ中のアクセ
   ス・キーの範囲を決定する手段と、その後の各アクセス
   動作の間に、上記決定されたディレクトリのアクセス・
   キーの範囲に基づき、要求されたデータ・ファイルの探
   索キーが存在しうるディレクトリを判別し、該判別され
   たディレクトリに対応するブロックに関してのみ、要求
   されたデータ・ファイルを探索する データベース・アクセス・システム。
2. （２）上記ディレクトリのアクセス・キーの範囲が、該
   ディレクトリに含まれるアクセス・キーの最大値及び最
   小値により定義され、上記判別が上記探索キーと上記最
   大値及び最小値との比較により行われる特許請求の範囲
   第１項に記載の データベース・アクセス・システム。