JPH09507109A

JPH09507109A - コンピュータデータベースに関するトランザクションの処理を促進させるための装置

Info

Publication number: JPH09507109A
Application number: JP7513213A
Authority: JP
Inventors: リンエムヒューエイ
Original assignee: パラコムコーポレイション
Priority date: 1993-11-02
Filing date: 1994-10-04
Publication date: 1997-07-15
Also published as: EP0727067A4; CN1139489A; BR9407962A; EP0727067A1; US5544357A; AU7965794A; WO1995012846A1

Abstract

(57)【要約】コンピュータデータベース（１１０）を管理するためのハドウエアアクセラレータ（１２０）は、レコードアドレス値に対するレコードキー値のマップを記憶するキーメモリ（１２４）と、所定のキー値についてキーメモリ（１２４）を探索し、関連したレコードアドレス値を中央処理装置（１０２）へと与える探索プロセッサ（１２２）と、中央処理装置（１０２）に対して探索プロセッサ（１２２）およびキーメモリ（１２４）をインターフェイスするバスインターフェイス（１３０）とを備える。中央処理装置（１０２）に関して実行するデータベース管理ソフトウエア（１１６）は、バスインターフェイス（１３０）を介して探索プロセッサ（１２２）へ要求を発することにより、キー値からレコードアドレス値へのマッピングを要求する。アクセラレータ（１２０）は、また、キーメモリ（１２４）においてエントリを追加したり削除したりする動作も行なう。アクセラレータ（１２４）は、エントリの探索値が単一でないようなメモリを探索するのに特に有用な変形バイナリ探索を使用する。この変形バイナリ探索は、所定の値に整合するメモリにおける最初のエントリを見つけ出す。バイナリ探索を繰り返す毎に、探索されたエントリと所定の値との比較によって発生されるＣＡＲＲＹは、その探索の次の繰り返しにおいて算出されるプローブアドレスを変更するために使用される。この探索は、所定の値が見つけ出されたときに終了するのでなく、始端および終端アドレスが所定のエントリと整合する最初のエントリに収れんするまで続けられる。

Description

【発明の詳細な説明】コンピュータデータベースに関するトランザクションの処理を促進させるための装置発明の背景本発明は、コンピュータデータベースに関するトランザクションの処理を促進させるための装置および方法に関する。コンピュータデータベースは、データレコードの収集体である。各データレコードは、そのレコードのための“名称”として役立つ１つまたはそれ以上の論理的キーを有している。典型的には、あるアプリケーションプログラムがそのデータベースにおけるあるレコードに対してアクセス要求をするとき、そのアプリケーションプログラムは、データベース管理プログラムへある論理的キー値を与える。すると、そのデータベース管理プログラムは、ディスクまたはメモリに保持されたインデックスからの情報に問い合わせて、その論理的キー値をレコードアドレス値へとマッピングする。このレコードアドレス値は、その論理的キー値に関連したデータ記録が見だされるはずであるディスクの場所を特定している。こうして、データベースインデックスは、書物の索引と非常によく似た機能を果たすものである。読者がある論理的キー値（興味のある題目）を与えると、その索引が、その情報が見だされるはずであるレコードアドレス値（頁番号）を与える。データベースは、多重キーを有しうる。典型的には、１つのキーは、レコードへの明白ですばやいアクセスを与える“一次キー”として選定されており、“二次キー”は、単一レコードへのよりゆっくりとしているか、より特定的でないアクセスを与える。例えば、従業員データベースは、その一次キーとして従業員番号を使用し、二次キーとして従業員の名前および所属部の番号を使用することができる。キーインデックスは、それがディスク上に存在するとき、データベースの永久的な部分である。キーインデックスは、（書物の目次がその本文と共通の綴じ込みとなっているのと同様に）データレコード自体と同じファイルに記憶されてもよいし、（何巻もからなる百科事典の索引／概観巻のように）別のファイルに記憶されていてもよい。既知のデータベース管理システムは、２つの論理的レイヤーに分けられている。すなわち、データベースマネージャーと称される上部レイヤーは、ユーザインターフェイス（例えば、データベース質問言語）を与え、データベースエンジンと称される下部レイヤーは、データベースの構造、すなわち、実際にデータベースファイルに記憶された物理的データと論理的キーとの間の関係を維持する。発明の概要第１の観点においては、本発明は、コンピュータデータベースを管理するためのハードウエアアクセラレータを提供する。このアクセラレータは、レコードキー値をレコードアドレス値に関連付けるマップを記憶するためのキーメモリと、該キーメモリを所定の値について検索し且つ関連したレコードアドレス値を中央処理装置へ与えるための探索プロセッサと、前記探索プロセッサおよびキーメモリを前記中央処理装置に対してインターフェイスするためのバスインターフェイスと、該バスインターフェイスを介して要求を前記探索プロセッサへと発することにより、レコードキー値からレコードアドレス値へのマッピングの要求を前記中央処理装置において実行させるためのデータベース管理ソフトウエアとを含む。本発明の好ましい実施例においては、次のような諸特徴が含まれる。キーメモリマップは、例えば、単一でない二次キーの場合には、単一キー値から多重レコードアドレスへのマッピングを含みうる。探索プロセッサは、所定のキー値と整合するキーメモリの最初のエントリを与えるバイナリ探索構造でもってキーメモリを探索するための構造を含みうる。データベース管理ソフトウエアは、レコードアドレスへのマッピングを行なうために探索プロセッサへキー値を与える前に、論理的キー値からエンコードされたキー値へのマッピングを行なうための構造を有する。中央処理装置は、キーメモリを割り当てるための構造を含む。ホストコンピュータのディスクメモリに記憶されたインデックスファイルは、そのキーメモリの内容のイメージを記憶しうる。中央処理装置がキーメモリに対して読み出しを行ったり書き込みを行ったりすることができるメモリポートを設けることができる。探索プロセッサは、中央処理装置へ、所定のキー値に対応するキーメモリのエントリのインデックスを与えることができ、また、そのときは、データベース管理ソフトウエアは、そのインデックスに対応するエットリをキーメモリから読み出すことができる。データベースアクセラレータは、キーメモリへエントリを加えたり、および／または、キーメモリからエントリを削除したりするための構造を含みうる。第２の観点においては、本発明は、エントリの探索値が単一でないメモリを探索するのに特に有用な変形バイナリサーチを特徴とする。この変形バイナリ探索は、所定の値に整合する最初のエントリをメモリ内に見つけ出す。通常のバイナリ探索におけるように、それらエントリは、分類された順序にてメモリに記憶されている。始端アドレスと終端アドレスとの平均であるプローブアドレスが形成され、対応するエントリが探索される。探索エントリと所定の値との比較に依存して、始端アドレスまたは終端アドレスが、そのプローブアドレスと等しく設定される。変形バイナリ探索では、探索エントリと所定の値との比較により発生されたＣＡＲＲＹを用いて、その探索の次の繰り返しにおいて算出されるプローブアドレスを変更する。所定の値が見つけ出されたときに終了する代わりに、この探索は、始端アドレスと終端アドレスとが所定の値に整合する最初のエントリに収れんするまで、続けられる。本発明の種々ある効果として、次のようなものが挙げられる。データベースアクセラレータを使用しているデータベースマネージャーは、アクセラレータを持たないものと比較して、はるかに速く動作する。何故ならば、論理的キー値のレコードアドレス値へのマッピングが、インデックス情報のディスクコピーへのアクセスなしに行われうるからである。本発明は、データベースソフトウエアベンダーに対するコピー防止機能を与える。すなわち、データベース管理ソフトウエアの不正なコピーは、データベースアクセラレータボード無しでは使用できない。従来のソフトウエアデータベースエンジンでは、探索のためには速くアクセスできるようにするが、レコードの追加または削除についてはゆっくりとしたアクセスしかできないようにする（階層的組織において典型的である）か、または、レコードの追加または削除については速くアクセスすることができるようにするが、ゆっくりとした探索しかできないようにする（関係形式データベースにおいて典型的である）か、のどちらかにせざるを得なかった。これに対して、本発明によれば、それらのどちらのソフトウエアデータベースエンジンよりも、はるかに速く探索機能も更新機能も行え、また、構造設計もより簡単とされる。本発明のその他の効果および特徴については、次の添付図面に関連してなされる好ましい実施例の説明から明らかとなろう。図面の簡単な説明第１図は、データベースアクセラレータを有したコンピュータを示すブロック図である。第２図は、データベースのディスクレコードおよびキーメモリを有するデータベースアクセラレータを示す図である。第３図は、データベースアクセラレータのブロック図である。第４図は、データベースアクセラレータの動作のフローチャートを示す図である。好ましい実施例の説明第１図を参照するに、パーソナルコンピュータ１００は、中央処理装置（ＣＰＵ）１０２と、ランダムアクセスメモリ（ＲＡＭ）１０４と、ディスクまたはその他の大型記憶装置１０６とを有しており、これらのすべては、システムバス１０８を介して通信するようにされている。ディスク１０６は、データベースを構成するデータファイル１１０およびインデックスファイル１１２を保持しており、ＣＰＵ１０２は、ＲＡＭ１０４に記憶されたデータベース管理ソフトウエア１１４およびアプリケーションソフトウエア１１６を実行させる。データベースアクセラレータ１２０もまた、バス１０８を介して通信し、コントロールロジック１２２およびキーメモリ１２４を有している。後述する始動段階中において、論理的キー値をレコードアドレス値へとマッピングするためのインデックス情報は、高速アクセスのためにインデックスファイル１１２からキーメモリ１２４へとロードされる。一般的動作においては、アプリケーションソフトウエア１１６は、データベースマネージャー１１４からの動作を要求する。もし、その要求が、ＳＥＡＲＣＨ、ＡＤＤＩＴＩＯＮまたはＤＥＬＥＴＩＯＮのうちの一つであるならば、そのときには、データベースマネージャー１１４は、その要求をシステムバス１０８を介してバスインターフェイス１３０を通してデータベースアクセラレータ１２０へと通過させ、データベースインデックスファイル１１２へアクセスする段階をバイパスする。探索動作を、データベースアクセラレータ１２０によって行われる代表的な動作として考え（ＳＥＡＲＣＨ、ＡＤＤＩＴＩＯＮおよびＤＥＬＥＴＩＯＮについては、後で、第４図を参照して、より詳細に説明する）、データベースマネージャー１１４は、ある論理的キー値をデータベースアクセラレータ１２０へ与え、且つ、その論理的キーを探索するためのコマンドを与える。データベースアクセラレータ１２０内において、コントロールロジック１２２（状態マシンでありうる）は、そのアクセラレータのキーメモリ１２４におけるその要求された動作を指示する。もし、その論理値がキーメモリ１２４において見出されるならば、コントロールロジック１２２は、その論理的キー値に関連したレコードアドレス値をデータベースマネージャー１１４へ与える。その時、そのデータベースマネージャー１１４は、データベースファイル１１０における適当なデータベースレコードにアクセスできる。第２図を参照するに、データベースアクセラレータのキーメモリ１２４は、２つのコラム、すなわち、エンコードされた論理的キー値のための左側コラム２０２と、関連するレコードアドレス値のための右側コラム２０４とを有しているかのように、組織されている。第２図において、インデックス１１２を有したデータベース１１０は、各々が一次キーおよび二次キーを有した５つのデータレコードを有するようなものとして例示されている。始動段階中において、これらの一次および二次のエンコードされた論理的キー値は、それらの関連したレコードアドレスと共に、それらのキー値にしたがった分類された順番にて、キーメモリ１２４にロードされている。一般的な動作中において、コントロールロジック１２２は、エンコードされた論理的キー値２１１−２１５または２２１−２２５について左側コラム２０２の探索を指示する。そのエンコードされた論理的キー値が見つけ出されるときには、その右側コラムにおける対応するエントリが、そのレコード２５１−２５５のためのレコードアドレス値２３１−２３５または２４１ −２４５である。こうして、キーメモリ１２４は、インデックスファイル１１２における情報に関するキャッシュとして作用する。第３図を参照するに、データベースアクセラレータ１２０は、バスインターフェイス１３０を有する。このバスインターフェイス１３０の設計は、ホストコンピュータのバスプロトコル、例えば、種々な型のパーソナルコンピュータにおいて見出されるＡＴ、ＩＳＡ、ＥＩＳＡ、Microchannel、またはMacIntoshバスアーキテクチャによって、主として決定されている。第３図のロジックは、任意の都合のよい技法、例えば、カスタムＶＬＳＩ、ゲートアレイ、フィールドプログラマブルゲートアレイ、プログラマブルロジックアレイ（ＰＡＬｓ）、ビットスライスプロセッサ、またはマイクロプロセッサにて実施されうる。キーメモリ１２０は、データベース１１０の所望のキーを保持するようなサイズとされており、典型的には、２５６ｋＢである。データベースアクセラレータ１２０は、ホストプロセッサ１０２のメモリスペースへマッピングされている多数のコントロールレジスタおよびデータを有する。ホストプロセッサ１０２は、典型的には、例えば、探索するための値、探索するためのキーメモリの領域の低限界および高限界、コマンド値（例えば、ＳＥＡＲＣＨ）およびＧＯコマンド等の値をレジスタへと書き込むことにより、データベースアクセラレータからのサービスを要求する。データベースアクセラレータ１２０がその要求をサービスするとき、ホストプロセッサ１０２は、その他の機能を行なうか、または、データベースアクセラレータの状態レジスタに関するスピンウエイトを実行するか、によってその動作が完了するまで待つことができる。このような段階については、後で、より詳細に説明する。キーメモリ１２４は、ホストによって読み出されたり、書き込まれたりされうる。キーメモリにアクセスするために、ホスト１０２は、メモリＬＯＡＤまたはＵＮＬＯＡＤコマンドをコントロールバッファ３０１へ書き込む。それに応答して、アドレスマルチプレクサは、アドレスバッファ３０９のアドレス値をキーメモリ１２４へと通す。コントロールバッファ３０１がＬＯＡＤへセットされるとき、メモリデータバッファ３０３へ書き込まれている、どのデータ値もアドレスバッファ３０９に指定されたアドレスで、キーメモリ１２４へ書き込まれる。同様に、コントロールバッファ３０１がＵＮＬＯＡＤへセットされるとき、アドレスバッファ３０９によってアドレスされるセル値が、ホストが読み出すためにメモリデータバッファ３０３へコピーされる。キーメモリ１２４は典型的には非常に大きいので、コントロールバッファ３０１は、ウインドウをキーメモリ１２４に亘って移動させる高アドレスビットを記憶し、低いアドレスビットは、アドレスバッファ３０９に記憶される。次に、始動段階についてより詳細に説明するに、始動段階は、次のようにして進められる。キーメモリ１２４には、エンコードされた論理的キー／レコードアドレス値対がロードされる。そのエンコードされた論理的キー値は、キーメモリ１２４の一方のコラム２０２に、１６ビットのエンコードされたキー値として記憶され、ホストプロセッサ１２０は、任意の都合のよい方法、例えば、ＣＲＣ（円形冗長検査）の如き既知のハッシュ関数による方法によって、各任意長の論理的キー値を１６ビットのエンコードされたキー値へとマッピングする。こうして、いくつかの論理的キー値は、同一のエンコードされたキー値へとマッピングされ得て、異なるレコードアドレスを有し得る。第２図におけるレコードアドレス値コラムは、データベースファイル１１０内のレコード番号を表す１６ビットの整数として第２のコラム２０４に記憶される。キーメモリ１２４にロードするため、ホストデータベースソフトウエア１１４は、データベース１１０、１１２から、レコードの番号のカウントおよびそのデータベースレコードのためのレコードアドレス値を得て、どのエンコードされた論理的キーおよびレコードアドレスがキーメモリ１２４に記憶されるかを選択する。例えば、インデックスファイル１１２は、そのエンコードされた論理的キーおよびレコードアドレスを、厳密に、キーメモリ１２４に使用されるフォーマットにて記憶しうる。その場合において、単に、インデックスファイル１１２からのインデックスをキーメモリ１２４へとコピーするだけで、キーメモリ１２４にロードすることが可能である。または、ホストデータベース１１４は、データベースファイル１１０のレコードを読み出し、論理的キーを抽出し、それらを、１６ビットのエンコードされたキーへとマッピングし、そのエンコードされたキー／レコードアドレス対を前述したようなＬＯＡＤコマンドを使用してキーメモリ１２４に記憶することもできる。ホストデータベースソフトウエア１１４は、キーメモリ１２４を管理し、例えば、多重論理的キーの間にキーメモリ１２４を配分する。例えば、もし、キーメモリ１２４が４０９６個のエントリを有し、データベースファイル１１０が３つのキー（典型的には、１つの一次キーと２つの二次キー）を有する場合には、ホストデータベースソフトウエア１１４は、その一次キーをエントリ０から１３６５に記憶させ、二次キーをエントリ１３６６から２７３０に記憶させ、三次キーをエントリ２７３１から４０９５に記憶させるように決定することができる。ホストデータベースソフトウエア１１４は、各ＳＥＡＲＣＨ、ＡＤＤＩＴＩＯＮ、またはＤＥＬＥＴＩＯＮ要求に対して正しい限界を指定することができるように、各論理的キーに配分されたキーメモリの領域を維持する。キーメモリ１２４におけるエントリは、データベースアクセラレータ１２０の探索回路によって実施される探索戦略によって必要とされるように管理される。例えば、もし、データベースアクセラレータ１２０がバイナリ探索を使用している場合には、キーメモリにおけるエントリは、１つの論理的キーに割り当てられた領域内にギャップがないようにして分類された順序にて記憶されなければならない。第４図は、キーメモリ１２４が配分されロードされた後のデータベースアクセラレータ１２０の動作を示している。ステップ４０２において、ホストプロセッサ１０２は、アクセラレータのデータレジスタのうちのいくつかにコマンドおよびデータ値を書き込む。これらデータレジスタの使用は、後述するような各動作について特定されている。比較ステップ４０８は、種々なコマンドの間でＳＥＡＲＣＨ、ＤＥＬＥＴＩＯＮおよびＡＤＤＩＴＩＯＮ動作を区別する。これら動作の各々については、後述する。第３図および第４図を参照するに、ＳＥＡＲＣＨコマンドは、エンコードされたキー値に対応するキーメモリの選択された領域における最初のキー値をつきとめるためにバイナリ探索を使用しており、したがって、キーメモリ１２４のエントリは、エンコードされたキー値２０２によって昇り順序にて分類されて記憶される。ステップ４０２において、ホストプロセッサ１０２は、始端アドレスレジスタＳＡＲ３１６および終端アドレスレジスタＥＡＲ３１４において探索を行なうための間隔を定めるキーメモリ１２４のエントリ番号を記憶する。探索すべきエンコードされたキー値は、データバッファ３１０に記憶されている。ＳＥＡＲＣＨコマンドを指定する値は、コントロールバッファ３０１に記憶されている。これらのデータがステップ４０２および４０４において各レジスタに記憶されたとき、ホスト１０２は、ステップ４０４においてＧＯ信号をゴー／結果バッファ３０７へ書き込む。ステップ４０６において、データベースアクセラレータ１２０は、ホストプロセッサ１０２によって読み出されるように、コントロールバッファ３０１の値をＢＵＳＹへセットするように応答する。ステップ４０８において、コントロールロジック３０２は、実行すべきコマンドがどれかを決定し、その適当なコマンドを実行するようにデータベースアクセラレータ１２０のロジックを制御する。ＳＥＡＲＣＨ手順は、ステップ４１０で始まる。比較器３１８からのＣＡＲＲＹ信号は、コントロールロジック３０２によって１へセットされる。この探索の後のステップにおいて、このＣＡＲＲＹ信号は、比較器３２０によって自動的に発生され、もし、ある選択されたエンコードされたキー値がキーメモリ１２４に何回も現れる場合には、その探索を最初にヒットするところで終了させる代わりに、これらの多重エントリのうちの次に続く最初のエントリのところで終了させるように、バイナリ探索のための通常のルールを変更するのに使用される。ＦＯＵＮＤ信号も、ステップ４１０にて０へセットされる。このＦＯＵＮＤ信号は、キーメモリ１２４におけるいずれかのエントリがそのエンコードされた論理的キー値と整合しているかを指示し、したがって、その探索が成功したかを指示する。ステップ４１２において、加算器３１７は、ＳＡＲ３１６、ＥＡＲ３１４の内容とＣＡＲＲＹとを加算し、シフトレジスタ３２０にて２で除算し、このバイナリ探索のこのステップにて探索すべきキーメモリ１２４におけるアドレスである値Ｍ１を形成する。ステップ４１４において、ＦＩＮＩＳＨＥＤフラッグは、比較器３１９を介してＳＡＲ３１６の現在値と比較されるＭ１の値を記録し、これが、このバイナリ探索の最後のプローブであることを指示する。先にステップ４２６を見ると、もし、ＦＩＮＩＳＨＥＤフラッグがステップ４１４にてセットされた場合には、エントリＭ１でのこのプローブは、そのバイナリ探索の最終プローブであり、この探索は、この繰り返しにて終了することができる。ステップ４１６において、Ｍ１は、キーメモリ１２４にアドレスするために、アドレスマルチプレクサ３０８を介して多重化される。キーメモリ１２４のエントリＭ１でのエンコードされたキー／レコードアドレス値は、暫定バッファ３１１にロードされる。ステップ４１８において、データバッファ３１０からの探索キー値は、比較器３２０によって探索されエンコードされたキー値３１１と比較される。コントロールロジック３０２は、比較器３２０の結果を使用して、その探索されエンコードされたキー値がその探索キー値より小さいか、等しいか、大きいかを決定する。ステップ４２２において、もし、その探索キー値と探索されエンコードされたキー値とが等しい場合には、比較器３２０からのＣＡＲＲＹがクリアされる（ＣＡＲＲＹ：＝０）。コントロールロジック３０２は、ＦＯＵＮＤフラッグをセットし（ＦＯＵＮＤ：＝１）、ＥＡＲ３１４の内容をＭ１の値と置き換える。ステップ４２０において、もし、暫定バッファ３１１（探索されたキー値を保持している）がデータバッファ３１０（探索キー値を保持している）より小さい場合には、値Ｍ１は、アドレスＭＵＸ３０８からＳＡＲ３１６へとラッチされ、ＣＡＲＲＹがセットされる（１へ）。さもなければ、ステップ４２４において、探索されたキー値３１１は、探索キー値３１０より大きく、アドレスＭ１は、アドレスＭＵＸ３０８からＥＡＲ３１４へとラッチされ、ＣＡＲＲＹがクリアされる。ここで注目すべき点は、このバイナリ探索は、探索キー値がキーメモリ１２４からのエンコードされたキー値と整合したときに停止するのでなく、このバイナリ探索は、キーメモリ１２４におけるエントリがデータバッファ３１０に記憶された探索キー値と最初に整合してこの探索のための低限界ＳＡＲ３１６および高限界ＥＡＲ３１４が終わるまでは、続けられるということである。ステップ４２６において、このバイナリ探索がＳＡＲの内容のうちの一つ内にて終わったときに（すなわち、ＥＡＲ３１４の内容（値Ｍ１に等しい）、もし、そのようなエントリが指定された元のＳＡＲ値とＥＡＲ値との間に存在する場合には、エンコードされたキー値に整合するキーメモリ１２４における最初のエントリをＭ１は指している。もし、ＦＯＵＮＤフラッグがステップ４２２においてセットされた場合には、少なくとも１つの整合エントリがあることが分かる。したがって、ステップ４２６での比較の結果が肯定（Ｙｅｓ）となり、ステップ４２８へと進められる。ステップ４２８では、その値Ｍ１がゴー／結果バッファ３０７へと書き込まれ、ＦＯＵＮＤ状態値がコントロールバッファ３０１へと書き込まれる。比較の結果が否定（Ｎｏ）であると、そのバイナリ探索が続けられなければならないことが指示され、ＥＡＲとＳＡＲとの間の差が半分で終わったことを指示している。このデータベースアクセラレータの探索動作は、ステップ４３０で完了する。もし、ホストプロセッサ１０２がビジーであって、コントロールバッファ３０１を待っている場合には、それは実行を継続することができる。ホストプロセッサ１０２は、ゴー／結果バッファ３０７からＭ１値を読み出し、次いで、読み出すべきキーメモリ１２４におけるエントリを特定する。もし、このエントリのエンコードされたキーが探索されたエンコードされたキーと整合する場合には、このエントリの低１６ビットが、データベースファイル１１０から読み出すべきレコードを特定する。ホストプロセッサ１０２は、典型的には、データベースファイル１１０から指示されたレコードを読み出す。同一のエンコードされたキー値を有する多数のレコードがあるので（特に、論理的キー自体が単一でないことがありうる二次キーの場合において）、典型的には、探索されたエンコードされたキー値を有するレコードのすべてを調べることが必要である。探索手順４１０から４３０により、探索されたエンコードされたキー値と整合するキーメモリの最初のエントリのみが与えられ、ホストプロセッサ１０２は、典型的には、キーメモリ１２４から読み出されるエンコードされたキー値が探索されたエンコードされたキーと最早整合しなくなるまで、キーメモリ１２４から相続くエントリを読み出し且つデータベースファイル１１０からレコードを読み出すために前述したＵＮＬＯＡＤコマンドを使用する。ＤＥＬＥＴＩＯＮおよびＡＤＤＩＴＩＯＮ動作は、フローチャートのステップ４４０から４５２に例示されている。エンコードされたキーのアレイおよびレコードアドレス値対は、密に維持されねばならないので（特定の論理的キーに対して専用されるキーメモリスペースにどのような孔があってもならない）、ＡＤＤＩＴＩＯＮは、挿入されたキー値よりも高いアレイの部分を、１つのキーメモリ位置だけ上に移動させるように作動する。ホストプロセッサ１０２は、その新しいエンコードされたキーおよびレコードアドレス対を選択された位置へ書き込む。ステップ４５０から４５４のＤＥＬＥＴＩＯＮは、キーメモリの上方部分を１つのエントリだけ下にコピーするように作動する。ホストデータベースソフトウエア１１４は、正しいＥＡＲ値がキーメモリ１２４に関する次の動作を適切に境界付けるために使用されうるように、その終端値を更新する。ＡＤＤＩＴＩＯＮ（ＤＥＬＥＴＩＯＮ）コマンドを実行するために、ステップ４０２から４０４において、ホストプロセッサ１０２は、挿入（削除される）メモリ位置に対するキーメモリエントリ番号をＵＣＲ３０６へ書き込み、最後の正当エントリ番号をＥＡＲ３１４へ書き込み、ＡＤＤＩＴＩＯＮ（ＤＥＬＥＴＩＯＮ）コマンド値をコントロールバッファ３０１へ書き込み、ＧＯ信号をゴーバッファ３０７へ書き込む。ステップ４０６において、コントロールロジック３０２は、コントロールバッファ３０１の値を、ＢＵＳＹにセットし、また、そのデータ移動が完了するときに、ＦＯＵＮＤまたはＮＯＴＢＵＳＹにセットする。ステップ４４０から４４２（４５０から４５２）において、ＡＤＤＩＴＩＯＮ（ＤＥＬＥＴＩＯＮ）コマンドは、ＵＣＲ３０６にて特定されたエントリより上方のすべてのエントリを１つのエントリ分だけ上方（下方）に移動させる。ＡＤＤＩＴＩＯＮコマンドがデータベースアクセラレータによって完了されるとき、キーメモリにおける１つのエントリが複写され、新しいエントリが、前述したＬＯＡＤコマンドを使用してそれら複写のうちの最初のものの上に書き込まれる。ＡＤＤＩＴＩＯＮ（ＤＥＬＥＴＩＯＮ）コマンドは、ステップ４４６（４５４）にて完了する。キーマップ１２４は、例えば、ＤＥＬＥＴＩＯＮおよびＡＤＤＩＴＩＯＮコマンドの後で、データベースファイル１１０と矛盾のないように維持される。伝統的なソフトウエアデータベースエンジンに使用される技術のあるものは、有用なものとして利用でき、また、いくつかの技術は、劇的に簡単化されうる。ホストコンピュータ１０２において作動するデータベースマネージャー１１４は、データベースファイルに書き込むすべてのトランザクションを記録するトランザクションのログファイルを維持する。トランザクションのログファイルは、クラッシュ回復を助けるために維持される。インデックス探索、挿入および削除はインデックスファイル１１２におけるディスク速度の代わりに、キーメモリ１２４におけるＲＡＭ速度で起きるので、階層的データベースマネージャーから許容しうる性能を得るのに普通に使用されるコンプレックスインデックスファイル１１２（およびインデックスファイルを操作するためのコンプレックスデータベースエンジンソフトウエア）は不必要である。キーメモリの１２４個のエンコードされたキー／レコードアドレス対の単なるイメージであるインデックスファイルで充分であり、これは、頻繁には更新されず、例えば、ユーザがその日の終わりとするときに更新されうる。もし、コンピュータがインデックスファイル１１２をデータベースファイル１１０と一致するように更新せずにクラッシュする場合には、インデックスファイル１１２は、データベースファイル１１０におけるレコードから再生されうる。ユーザが普通にエクシットするとき、ホストは、そのアクセスウインドウを使用してキーメモリ１２４からエントリを読み出し、キーメモリ１２４のイメージをインデックスファイル１１２へ記憶させて、インデクッスファイル１１２をデータベースファイル１１０と一致させるようにする。ユーザが次にデータベースへログするとき、キーメモリ１２４は、インデックスファイル１１２から直接的にロードされうる。ホストデータベースソフトウエア１１４がデータベースアクセラレータ１２０へコマンドを発するとき、ホストプロセッサ１０２は、データベースアクセラレータを待つスピンウエイトに入り、コントロールバッファ３０１に“動作完了” 状態コードをセットする。データベースアクセラレータは、例えば、１６個のプローブを使用する２５６Ｋメモリにおける６４Ｋエントリの探索を、ホストプロセッサのためのスピンループの２または３回の繰り返しである、１６ＭＨｚデータベースアクセラレータクロックについて９３７ｎｓにて完了するに充分に速い。その他の実施例においては、キーメモリを種々異なった形に組織することができる。例えば、大きなデータベースの場合には、エンコードされたキーおよびレコードアドレスに対して３２ビット（またはより大きい）表現を使用することが望ましい。長さレジスタは、エンコードされたキー値の長さを特定し、または、タイプレジスタは、論理的キーの照合シーケンスを特定する。レコードアドレスは、任意の都合のよい表現、例えば、データレコードを見出すべきディスクボリューム、シリンダ、ヘッドおよびレコードを記憶する表現にて記憶されうる。キーメモリは、任意の都合のよい探索技術、例えば、Ｂトリー、ハッシュテーブル、フィボナッチ探索または補間探索を使用するように組織されうる。キーメモリ組織は、探索に関する挿入および削除の相対的頻度によって選択される。その他の実施例は、次の請求の範囲内に入るものである。

───────────────────────────────────────────────────── フロントページの続き (81)指定国ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ，ＤＫ，ＥＳ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，ＬＵ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ，ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＫＥ，ＭＷ，ＳＤ，ＳＺ)，ＡＭ，ＡＴ，ＡＵ，ＢＢ，ＢＧ，ＢＲ，ＢＹ，ＣＡ，ＣＨ，ＣＮ，ＣＺ，ＤＥ，ＤＫ，ＥＥ，ＥＳ，ＦＩ，ＧＢ，ＧＥ，ＨＵ，ＪＰ，ＫＥ，ＫＧ，ＫＰ，ＫＲ，ＫＺ，ＬＫ，ＬＴ，ＬＵ，ＬＶ，ＭＤ，ＭＧ，ＭＮ，ＭＷ，ＮＬ，ＮＯ，ＮＺ，ＰＬ，ＰＴ，ＲＯ，ＲＵ，ＳＤ，ＳＥ，ＳＩ，ＳＫ，ＴＪ，ＴＴ，ＵＡ，ＵＺ，ＶＮ【要約の続き】モリにおける最初のエントリを見つけ出す。バイナリ探索を繰り返す毎に、探索されたエントリと所定の値との比較によって発生されるＣＡＲＲＹは、その探索の次の繰り返しにおいて算出されるプローブアドレスを変更するために使用される。この探索は、所定の値が見つけ出されたときに終了するのでなく、始端および終端アドレスが所定のエントリと整合する最初のエントリに収れんするまで続けられる。

Claims

【特許請求の範囲】１．ホストコンピュータと関連して記憶されたデータベースを管理するための装置であって、前記データベースは、各々がレコードアドレス値および少なくとも１つの論理的キー値によって識別される複数のレコードを有しており、前記ホストコンピュータは、中央処理装置を有しているような装置において、前記データベースのレコードのキー値の前記レコードのレコードアドレス値へのマップを記憶するためのキーメモリと、前記中央処理装置からの要求に応答して所定のキー値について前記キーメモリを探索し、それに関連したレコードアドレス値を前記中央処理装置へと与えるための探索プロセッサと、前記探索プロセッサおよびキーメモリを前記中央処理装置に対してインターフェイスするためのバスインターフェイスと、前記中央処理装置にて実行するためのデータベース管理ソフトウエアとを備えており、前記ソフトウエアは、前記バスインターフェイスを通して通信される要求を前記探索プロセッサへ発することにより、前記所定のキー値から前記レコードアドレス値へのマッピングを要求するように構成されていることを特徴とする装置。２．単一のキー値を前記キーメモリマップにおける多重レコードアドレス値へとマッピングするためのマッピング手段をさらに備える請求項１記載の装置。３．前記探索プロセッサは、前記所定のキー値と整合する前記キーメモリの最初のエントリを与えるバイナリ探索手段でもって前記キーメモリを探索するための手段を備える請求項１記載の装置。４．前記バイナリ手段は、 (a) 前記キー値を、前記キーメモリのインデックスされたエントリにおいて分類された順序で記憶するための手段と、 (b) 探索すべき間を示す前記キーメモリのエントリ番号に対応する始端アドレスおよび終端アドレスを与えるための手段と、 (c) 探索される探索値を与えるための手段と、 (d) Ｆａｌｓｅの初期ＦＯＵＮＤ値および初期ＣＡＲＲＹ値を与えるための手段と、 (e) 前記始端アドレス、終端アドレスおよびＣＡＲＲＹを加算し、その和を２で除算することによりプローブアドレスを形成するための手段と、 (f) 前記プローブアドレスによってインデックスされた前記キーメモリエントリのキー値を読み出すための手段と、 (g) 前記探索値を前記読み出されたキー値と比較し、その比較にしたがって前記ＣＡＲＲＹ値を０または１へセットするための手段と、 (h) 前記読み出されたキー値が前記探索される値より小さい場合に、前記始端アドレスを前記プローブアドレスにセットするための手段と、 (i) 前記読み出されたキー値が前記探索される値に等しい場合に、ＦＯＵＮＤをＴｒｕｅにセットし、前記終端アドレスを前記プローブアドレスにセットするための手段と、 (j) 前記読み出されたキー値が前記探索される値より大きい場合に、前記終端アドレスを前記プローブアドレスへセットするための手段と、 (k) 探索インデックスが始端アドレスに等しくなるまで、前記手段(e)から(j) を繰り返すための手段、とを備える請求項３記載の装置。５．前記データベース管理ソフトウエアは、前記マッピングのために前記エンコードされたキー値を前記探索プロセッサへ与える前に、論理的キー値からエンコードされたキー値へのエンコーディングを行なうための手段を備える請求項１記載の装置。６．前記データベース管理ソフトウエアは、前記探索プロセッサが前記探索を行っている間スピンウエイトを行なうための手段を備える請求項１記載の装置。７．前記中央処理装置は、前記キーメモリを割り当てるための手段を備える請求項１記載の装置。８．前記ホストコンピュータのディスクメモリに記憶されるインデックスファイルを更に備え、該インデックスファイルは、前記キーメモリの内容のイメージを記憶する請求項１記載の装置。９．前記中央処理装置が前記キーメモリの読み出しおよび書き込みを行えるようにするメモリポートを更に備える請求項１記載の装置。 10．前記探索プロセッサは、前記所定のキー値に対応する前記キーメモリのエントリのインデックスを前記中央処理装置へと与え、前記データベース管理ソフトウエアは、さらに、前記インデックスに対応する前記キーメモリからエントリを読み出すための手段を備える請求項１記載の装置。 11．コンピュータ関連メモリに記憶されたデータベースのレコードを探し出すための方法であって、前記データベースは、各々がレコードアドレスおよび少なくとも１つの論理的キー値によって識別される複数のレコードを有しているような方法において、データベースアクセラレータ周辺装置のキーメモリに、前記レコードのキー値からレコードアドレス値へのマップインデックスを記憶させ、前記周辺装置へ前記データベースのレコードのキー値を与え、前記与えられたキー値に関連したレコードアドレス値を決定するために前記周辺装置に関して前記マップインデックスの探索を、前記周辺装置のプロセッサによって行い、前記決定されたレコードアドレス値と関連した前記データベースのレコードを参照する、ことを特徴とする方法。 12．新しいレコードを前記データベースへ加え、新しいキー値および新しいレコードアドレスを前記周辺装置に記憶させる段階を更に含み、前記新しいキー値は、前記新しいレコードに関連しており、前記新しいレコードアドレス値は、前記新しいレコードの前記データベースにおける位置を指示している請求項１１記載の方法。 13．前記データベースからあるレコードを削除し、前記周辺装置から前記削除されたレコードに関連したキー値および前記削除されたレコードのレコードアドレス値を削除する段階を更に含む請求項１１記載の方法。 14．前記探索のために前記探索プロセッサへ前記キー値を与える前に、論理的キー値をエンコードされたキー値へとエンコーディングする段階を更に含む請求項１１記載の方法。 15．前記中央処理装置へ、前記所定のキー値に対応する前記キーメモリのエントリのインデックスをコピーし、前記中央処理装置により前記エントリインデックスに対応するエントリを前記キーメモリから読み出す段階を更に含む請求項１１記載の方法。 16．各々が探索値を有するエントリのメモリを探索する方法において、 (a) 前記エントリを、前記探索値にしたがって分類された順序にて前記メモリに記憶させ、 (b) 探索すべき間を示す前記メモリのエントリ番号に対応する始端アドレスおよび終端アドレスを与え、 (c) 探索される探索値を与え、 (d) 初期ＣＡＲＲＹ値を与え、 (e) 前記始端アドレス、終端アドレスおよびＣＡＲＲＹを加算し、その和を２で除算することによりプローブアドレスを形成し、 (f) 前記プローブアドレスによってインデックスされたメモリエントリを読み出し、 (g) 前記探索値を前記読み出されたエントリと比較し、その比較にしたがって前記ＣＡＲＲＹ値を０または１にセットし、 (h) 前記読み出されたエントリの探索値が前記探索される値よりも小さい場合に、前記始端アドレスを前記プローブアドレスへセットし、 (i) 前記読み出されたエントリの探索値が前記探索される値に等しい場合に、前記終端アドレスを前記プローブアドレスにセットし、 (j) 前記読み出されたエントリの探索値が前記探索される値よりも大きい場合に、前記終端アドレスを前記プローブアドレスにセットし、 (k) 前記プローブアドレスが前記始端アドレスに等しくなるまで、前記段階(e )から(j)を繰り返す、ことを特徴とする方法。