テーブル構成方法、データアクセス方法、コンピュータプログラム、テーブル構成装置及びデータ処理装置
【課題】複数のプログラムが同時にアクセスできる共通エリアテーブルへのアクセスする際に、高速処理を可能とする。
【解決手段】共通エリア１１−１〜１１−８に個別テーブル群１５−１〜１５−８を展開する。ＲＦＵ領域１２に共通エリア１１−１〜１１−８に展開された個別テーブル群１５−１〜１５−８の情報が記録されるＲＦＵテーブルを展開し、ＨＳＴ領域１３に個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されるＨＳＴテーブルを展開し、ＴＡＴ領域１４に個別テーブルの展開テーブルＩＤ、各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニムオフセットとが記録されるＴＡＴテーブルを展開する。個別テーブル群１５−１〜１５−８をアクセスする際に、ＨＳＴ領域１３のＨＳＴテーブルと、ＴＡＴ領域１４のＴＡＴテーブルとを用いる。
【解決手段】共通エリア１１−１〜１１−８に個別テーブル群１５−１〜１５−８を展開する。ＲＦＵ領域１２に共通エリア１１−１〜１１−８に展開された個別テーブル群１５−１〜１５−８の情報が記録されるＲＦＵテーブルを展開し、ＨＳＴ領域１３に個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されるＨＳＴテーブルを展開し、ＴＡＴ領域１４に個別テーブルの展開テーブルＩＤ、各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニムオフセットとが記録されるＴＡＴテーブルを展開する。個別テーブル群１５−１〜１５−８をアクセスする際に、ＨＳＴ領域１３のＨＳＴテーブルと、ＴＡＴ領域１４のＴＡＴテーブルとを用いる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数プログラムが同時にアクセス可能である汎用共通エリアに対して、高速アクセスが可能なテーブル構成方法、データアクセス方法、コンピュータプログラム、テーブル構成装置及びデータ処理装置に関する。
【背景技術】
【０００２】
コンピュータのハードウェアの性能向上が目覚ましく発展したことから、従来に比べテーブル配置やアクセス方式を意識しない設計であっても、少数のテーブル展開であれば、問題なく動作するようになってきている。しかしながら、一方で、コンピュータがあらゆる分野で活用され、大規模で多くのデータ量を所定の時間で処理するために、参照系のテーブルを複数枚の大きな共通エリアに展開することが行われている（例えば特許文献１）。この場合、その共通エリアテーブルへのアクセスが処理速度の低下のボトルネックとなる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平０９−１４６８１６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、これまで提案されているデータ処理方法では、展開するテーブル数に比例してアクセスが遅くなる、あるいは２枚目以降の汎用共通エリアに展開された場合にアクセスが遅くなる、テーブル配置が後のテーブルのアクセスがより遅くなる等の課題がある。
【０００５】
上述の課題を鑑み、本発明は、複数のプログラムが同時にアクセスできる共通エリアテーブルへのアクセスする際に、高速処理が可能なテーブル構成方法、データアクセス方法、コンピュータプログラム、テーブル構成装置及びデータ処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の一態様は、テーブル構成方法であって、共通エリアに個別テーブル群を展開するステップと、前記共通エリアに展開された個別テーブルの情報が記録されるリソーステーブルを展開するステップと、前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されるハッシングテーブルを展開するステップと、前記個別テーブルの展開テーブルＩＤ、前記個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報が記録されるアドレステーブルを展開するステップとを含むことを特徴とする。
【０００７】
本発明の一態様は、共通エリアに展開された個別テーブル群と、前記共通エリアに展開された個別テーブルの情報が記録されたリソーステーブルと、前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されたハッシングテーブルと、前記個別テーブルの展開テーブルＩＤ、前記各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報とが記録されたアドレステーブルとを含むデータ処理装置のデータアクセス方法であって、前記ハッシングテーブルと前記アドレステーブルとを用いて前記個別テーブル群をアクセスするステップを含むことを特徴とする。
【０００８】
本発明の一態様は、共通エリアに個別テーブル群を展開するステップと、前記共通エリアに展開された個別テーブルの情報が記録されるリソーステーブルを展開するステップと、前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されるハッシングテーブルを展開するステップと、前記個別テーブルの展開テーブルＩＤ、前記個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報が記録されるアドレステーブルを展開するステップと、をコンピュータに実行させるためのコンピュータプログラムである。
【０００９】
本発明の一態様は、共通エリアに展開された個別テーブル群と、前記共通エリアに展開された個別テーブルの情報が記録されたリソーステーブルと、前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されたハッシングテーブルと、前記個別テーブルの展開テーブルＩＤ、前記各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報とが記録されたアドレステーブルとを含むデータ処理装置に対し、前記ハッシングテーブルと前記アドレステーブルとを用いて前記個別テーブル群をアクセスするステップを実行させるためのコンピュータプログラムである。
【００１０】
本発明の一態様は、テーブル構成装置であって、共通エリアに個別テーブル群を展開する第一展開部と、前記共通エリアに展開された個別テーブルの情報が記録されるリソーステーブルを展開する第二展開部と、前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されるハッシングテーブルを展開する第三展開部と、前記個別テーブルの展開テーブルＩＤ、前記個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報が記録されるアドレステーブルを展開する第四展開部とを備えることを特徴とする。
【００１１】
本発明の一態様は、データ処理装置であって、複数のプログラムが同時にアクセス可能な共通エリアに展開された個別テーブル群と、前記共通エリアに展開された個別テーブルの情報が記録されたリソーステーブルと、前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されたハッシングテーブルと、前記個別テーブルの展開テーブルＩＤ、前記各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報とが記録されたアドレステーブルと、前記ハッシングテーブルと前記アドレステーブルとを用いて、前記個別テーブル群をアクセスするデータ処理部と、を備えることを特徴とする。
【発明の効果】
【００１２】
本発明によれば、各共通エリアに設けられた個別テーブル群をアクセスするのに、ハッシュ値が用いられ、同一のハッシュ値にマッピングされるテーブルＩＤをシノニム関係として処理している。このため、個別テーブル群へのアクセス処理時間を短縮することができる。
【図面の簡単な説明】
【００１３】
【図１】データ処理装置の構成を示すブロック図である。
【図２】ＲＦＵ領域１２に設けられるテーブルの具体例を示すものである。
【図３】ＨＳＴ領域１３に設けられるテーブルの具体例を示すものである。
【図４】ＴＡＴ領域１４に設けられるテーブルの具体例を示すものである。
【図５】展開テーブルにアクセスする際の処理をフローチャートで示したものである。
【発明を実施するための形態】
【００１４】
図１は、データ処理装置（テーブル構成装置）の構成を示すブロック図である。データ処理装置は、バスを介して互いに接続されたデータ処理部１と、記憶部２と、入力部３と、表示部４と、通信部５とを用いて構成される。データ処理部１は、ＣＰＵ（Central Processing Unit）やキャッシュ等の半導体記憶装置を用いて構成される。データ処理部１は、ＣＰＵが所定のプログラムを実行することによってデータ処理部１としての機能を実現する。記憶部２は、磁気ハードディスク装置や半導体記憶装置などの記憶装置を用いて構成される。入力部３には、キーボードやマウス等の入力装置が接続される。表示部４には、ＬＣＤ（Liquid Crystal Display）等の画像表示装置が接続される。なお、データ処理部１の機能の全て又は一部は、ＡＳＩＣ（Application Specific Integrated Circuit）やＰＬＤ（Programmable Logic Device）等のハードウェアを用いて実現されても良い。データ処理装置は、後述する各テーブルを生成する際には、テーブル構成装置として動作し、生成された各テーブルを用いてアクセスを行う際にはデータ処理装置として動作する。
【００１５】
記憶部２の記憶領域には、共通エリア群１０が設けられる。共通エリア群１０は、複数の共通エリアからなる。各共通エリアは、複数のプログラムが同時にアクセスできる記憶領域である。共通エリア群１０には、例えば８つの共通エリア１１−１〜１１−８が設けられる。共通エリア１１−１〜１１−８には、個別テーブル群１５−１〜１５−８が設けられる。
【００１６】
共通エリア１１−１の先頭には、ＲＦＵ（Resource Future Used）領域１２、ＨＳＴ（HaShing Table）領域１３、ＴＡＴ（Table Address Table）領域１４が設けられる。ＲＦＵ領域１２、ＨＳＴ領域１３、ＴＡＴ領域１４は、いずれもデータ処理部１の処理によって記憶部２に設けられる。
【００１７】
ＲＦＵ領域１２にはＲＦＵテーブルが記憶される。ＲＦＵテーブルには、データレコードとして、各共通エリア１１−１〜１１−８に展開された個別テーブル群１５−１〜１５−８のアドレス値、各共通エリア１１−１〜１１−８の空き領域のバイト数とが記録される。
【００１８】
ＨＳＴ領域１３にはＨＳＴテーブルが記憶される。ＨＳＴテーブルには、データレコードとして、個別テーブルのテーブルＩＤのハッシュ値と、各ハッシュ値に対応するＴＡＴテーブルへのエントリとなるアドレスとが記録される。ここで、ハッシュ値は、テーブルＩＤを文字列から数値に変換し、例えば母数１２８で除算し、その剰余から求められる。このように、文字列を数値に変換し、母数１２８で除算した剰余からハッシュ値を求めているため、その数は、「０」〜「１２７」となる。ＨＳＴテーブルには、「１」〜「１２８」の１２８個のレコードが設けられる。ＨＳＴテーブルの「１」〜「１２８」の各レコードには、ハッシュ値の「０」〜「１２７」に対応している。
【００１９】
ＴＡＴ領域１４にはＴＡＴテーブルが記憶される。ＴＡＴテーブルには、データレコードとして、個別テーブルの展開テーブルＩＤと、各個別テーブル群へのエントリとなる展開開始アドレスと、シノニムオフセットとが記録される。ここで、シノニムオフセットは、シノニム関係のテーブルＩＤがある場合に利用される。すなわち、前述したように、本実施形態では、テーブルＩＤの文字列を数値に変換し、母数１２８で除算した剰余からハッシュ値を求めている。この場合、ハッシュ値は「１」〜「１２８」となる。このため、異なるテーブルＩＤの文字列に対して同一のハッシュ値がマッピングされる可能性がある。ここでは、このように、同一のハッシュ値がマッピングされる場合を、シノニム関係としている。シノニムオフセットには、シノニム関係になるテーブルＩＤのデータレコードの位置を示すオフセットが記録される。
【００２０】
図２〜図４は、ＲＦＵ領域１２、ＨＳＴ領域１３、ＴＡＴ領域１４に設けられる各テーブルの具体例を示すものである。ＲＦＵ領域１２に記憶されるＲＦＵテーブル、ＨＳＴ領域１３に記憶されるＨＳＴテーブル、ＴＡＴ領域１４に記憶されるＴＡＴテーブルは、それぞれデータ処理部１の処理によって記録される。
【００２１】
ＲＦＵ領域１２は、共通エリア１１−１の先頭から例えば９６バイト分の領域として、データ処理部１によって確保される。ＲＦＵ領域１２のＲＦＵテーブルには、図２に示すように、テーブルＩＤ（１６バイト）と、テーブルサイズ（４バイト）と、テーブルレコード数（４バイト）と、データレコードサイズ（４バイト）と、データレコード「１」〜データレコード「８」（各８バイト）が設けられる。テーブルＩＤは、このＲＦＵテーブルを識別するためのものである。テーブルサイズは、このＲＦＵテーブルのテーブルサイズで、例えば９６バイトである。テーブルレコード数は、共通エリアの数を表しており、共通エリア１１−１〜１１−８が８個の場合には「８」である。データレコードサイズは、ＲＦＵテーブルの各データレコードのサイズである。データレコード「１」〜データレコード「８」には、各共通エリア１１−１〜１１−８に展開された個別テーブル群１５−１〜１５−８のアドレス値と、各共通エリア１１−１〜１１−８の空き領域のバイト数とが記録される。
【００２２】
ＨＳＴ領域１３は、共通エリア１１−１の先頭からＲＦＵテーブルに続いて例えば５４０バイト分の領域として、データ処理部１によって確保される。ＨＳＴ領域１３のＨＳＴテーブルには、図３に示すように、テーブルＩＤ（１６バイト）と、テーブルサイズ（４バイト）と、テーブルレコード数（４バイト）と、データレコードサイズ（４バイト）と、データレコード「１」〜データレコード「１２８」（各４バイト）とが設けられる。テーブルＩＤは、このＨＳＴテーブルを識別するためのものである。テーブルサイズは、このＨＳＴテーブルのテーブルサイズで、例えば５４０バイトである。テーブルレコード数は、このＨＳＴテーブルのレコード数である。このレコード数は、ハッシュ値の数に対応する。ここでは、データ処理部１は、テーブルＩＤの文字列を数値に変換し、母数１２８で除算した剰余からハッシュ値を求めている。そのため、テーブルレコード数は「１２８」となる。データレコードサイズは、ＨＳＴテーブルの各データレコードのサイズである。データレコード「１」〜データレコード「１２８」には、各ハッシュ値「０」〜「１２７」に対応して、ＴＡＴテーブルへのエントリとなるアドレスが記録される。なお、ハッシュ値「０」がデータレコード「１」に対応し、ハッシュ値「１２７」がデータレコード「１２８」に対応する。
【００２３】
ＴＡＴ領域１４は、共通エリア１１−１の先頭からＨＳＴテーブルに続いて例えば３１０４バイト分の領域として、データ処理部１によって確保される。ＴＡＴ領域１４のＴＡＴテーブルには、図４に示すように、テーブルＩＤ（１６バイト）と、テーブルサイズ（４バイト）と、テーブルレコード数（４バイト）と、有効レコード数（４バイト）と、データレコードサイズ（４バイト）と、データレコード「１」〜データレコード「１２８」（各２４バイト）とが設けられる。テーブルＩＤは、このＴＡＴテーブルを識別するためのものである。テーブルサイズは、このＴＡＴテーブルのテーブルサイズで、例えば３１０４バイトである。テーブルレコード数は、このＴＡＴテーブルのレコード数である。有効レコード数は、ＴＡＴテーブルに記録した有効レコード数である。データレコード「１」〜データレコード「１２８」には、各共通エリア１１−１〜１１−８に展開した個別テーブルの展開テーブルＩＤと、展開開始アドレスと、シノニムオフセットとが記録される。
【００２４】
以上のように、データ処理部１の処理によって、記憶部２にＲＦＵ領域１２、ＨＳＴ領域１３、ＴＡＴ領域１４が設けられ、それぞれの領域にテーブルが生成される。具体的には、ＲＦＵ領域１２への展開処理、ＨＳＴ領域１３への展開処理、ＴＡＴ領域１４への展開処理、テーブルＡへの展開処理、テーブルＢへの展開処理をデータ処理部１が順次実行することによって、テーブルが生成される。次に、上記の各テーブルを用いてデータにアクセスするための処理について説明する。本実施形態において、共通エリア１１−１〜１１−８の個別テーブル群をアクセスする際には、以下のような処理が行われる。
【００２５】
図１において、例えば入力部３から検索キーがテーブルＩＤとして入力されると、データ処理部１は、テーブルＩＤを文字列から数値に変換する。そして、データ処理部１は、母数１２８の剰余からハッシュ値を計算し、図３に示したＨＳＴ領域１３のＨＳＴテーブルにアクセスする。前述したように、各ハッシュ値「０」〜「１２７」は、ＨＳＴテーブルのデータレコード「１」〜データレコード「１２８」に対応している。そして、このＨＳＴテーブルのデータレコード「１」〜「１２８」には、図３に示すように、ＴＡＴテーブルへのエントリとなるアドレスが記録される。よって、データ処理部１は、検索キーとして入力されたテーブルＩＤのハッシュ値を計算し、このハッシュ値を基にＨＳＴテーブルにアクセスすることによって、ＴＡＴテーブルへのエントリとなるアドレス値を取得する。
【００２６】
データ処理部１は、ＴＡＴテーブルのアドレス値を取得すると、このアドレス値に基づいて、ＴＡＴテーブルにアクセスする。図４に示したように、ＴＡＴテーブルのデータレコード「１」〜「１２８」には、個別テーブルの展開テーブルＩＤと、展開開始アドレスと、シノニムオフセットとが記録されている。データ処理部１は、ＴＡＴテーブルにアクセスしたら、検索キーとして入力されたテーブルＩＤと、展開テーブルＩＤとが一致するかどうかを判定する。つまり、ＨＳＴテーブルからＴＡＴテーブルにアクセスする際に、シノニム関係にあるテーブルＩＤは、同一のデータレコードにアクセスされる。検索キーとして入力されたテーブルＩＤがそのＴＡＴテーブルのデータレコードそのものであれば、入力されたテーブルＩＤと展開テーブルＩＤとは一致する。一方で、シノニム関係のテーブルＩＤの場合には、入力されたテーブルＩＤと展開テーブルＩＤとは一致しない。
【００２７】
入力されたテーブルＩＤと展開テーブルＩＤとが一致する場合には、データ処理部１は、このＴＡＴテーブルのデータレコードから展開開始アドレスを取得する。そして、データ処理部１は、この展開開始アドレスをエントリとして、個別テーブル群１５−１〜１５−８にアクセスする。
【００２８】
入力されたテーブルＩＤと展開テーブルＩＤとが一致しない場合には、データ処理部１は、シノニムオフセットで示されるデータレコードに移動する。そして、データ処理部１は、移動したデータレコードで、再び、入力されたテーブルＩＤと、展開テーブルＩＤとが一致するかどうかを判定する。入力されたテーブルＩＤと展開テーブルＩＤとが一致する場合には、データ処理部１は、この移動したデータレコードから展開開始アドレスを取得する。そして、データ処理部１は、この展開開始アドレスをエントリとして、個別テーブル群１５−１〜１５−８にアクセスする。
【００２９】
このように、本実施形態では、各共通エリア１１−１〜１１−８の個別テーブル群１５−１〜１５−８にアクセスする際に、ハッシュ値が用いられる。そして、同一のハッシュ値にマッピングされるテーブルＩＤが、シノニム関係として処理される。これにより、個別テーブルのレコード数が多くなっても、高速アクセスが実現できる。
【００３０】
次に、共通エリア１１−１に個別テーブル群Ａ、共通エリア１１−２に個別テーブル群Ｂの２つのテーブルデータを展開する処理について具体的に説明する。図１において、先ず、データ処理部１は、８枚の共通エリア（ここでは各６４ＫＢと仮定し、管理テーブルが十分格納できるサイズの共通エリアとする）を確保し、先頭アドレスを取得する。次に、データ処理部１は、ＲＦＵ領域１２を共通エリア１１−１の先頭アドレスより９６バイト確保し、初期値を設定する。データ処理部１は、データレコード「１」には、共通エリア１１−１の先頭アドレスより９６バイト分加えたアドレスを設定する。また、データ処理部１は、データレコード「２」〜「８」には、それぞれ共通エリア１１−２〜１１−８の先頭アドレスを設定する。
【００３１】
次に、データ処理部１は、ＨＳＴ領域１３を共通エリア１１−１のＲＦＵテーブルに続き５４０バイト確保し、全てのレコードにＮＵＬＬ値を設定する。なお、データレコード「１」はハッシュ計算結果の剰余が「０」の場合、データレコード「１２８」はハッシュ計算結果の剰余が「１２７」の場合に使用される。
【００３２】
次に、データ処理部１は、ＴＡＴ領域１４を共通エリア１１−１のＨＳＴテーブルに続き３１０４バイト確保し、全てのレコードのテーブルＩＤ、アドレス、シノニムオフセットにＮＵＬＬ値を設定する。
【００３３】
次に、データ処理部１は、個別テーブル群Ａのテーブルサイズを事前の算出し、ＲＦＵテーブルの（１レコード目）から順番に空き領域サイズと比較し、格納できる共通エリアを決定する。今回は共通エリア１１−１に格納可能であったこととする。
【００３４】
次に、データ処理部１は、個別テーブル群Ａを共通エリア１１−１の空き領域の先頭（１レコード目のアドレス値）から展開する。そして、データ処理部１は、 ＲＦＵテーブルの１レコード目のアドレス値から個別テーブル群Ａのテーブルサイズを加え、かつ１レコード目の空き領域サイズから個別テーブル群Ａのテーブルサイズを減じて値を更新する。
【００３５】
次に、データ処理部１は、個別テーブル群ＡのテーブルＩＤを文字列から数値に変換し、母数１２８でハッシュ計算を行い、剰余を求める。ここで、剰余の値が１２６であったとする。剰余が１２６の場合には、データ処理部１は、ＨＳＴテーブルの１２７レコード目にＴＡＴテーブルの有効レコード数（現在０）の１加算したレコードのアドレスを設定する。なお、１件目で記していないが、ＨＳＴテーブルの１２７レコード目設定時にシノニムレコード有無チェックとして、１２７レコード目のアドレスがＮＵＬＬ値であることを確認する。なお、今回は１件目でＮＵＬＬ値であったとする。
【００３６】
次に、データ処理部１は、ＴＡＴテーブルの１レコード目の個別テーブル群ＩＤにテーブルＩＤを、展開開始アドレス値に個別テーブル群Ａの展開された先頭アドレスを設定する。
次に、データ処理部１は、個別テーブル群Ｂのテーブルサイズを事前の算出し、ＲＦＵテーブルの１レコード目から順番に空き領域サイズと比較し、格納できる共通エリアを決定する。今回は共通エリア１１−１に格納できず、共通エリア１１−２に格納可能であったこととする。この場合、個別テーブル群Ｂを共通エリア１１−２の空き領域の先頭から展開する。そして、データ処理部１は、ＲＦＵの２レコード目のアドレス値から個別テーブル群Ｂのテーブルサイズを加え、かつ２レコード目の空き領域サイズから個別テーブル群Ｂのテーブルサイズを減じて値を更新する。
【００３７】
次に、データ処理部１は、個別テーブル群ＢのテーブルＩＤを文字列から数値に変換し、母数１２８でハッシュ計算を行い、剰余を求める。この剰余の値が前回と同じ１２６であったとする。すなわち、前回のテーブルＩＤとシノニム関係であったとする。この場合、ＨＳＴテーブルの１２７レコード目のアドレスが非ＮＵＬＬ値（ＴＡＴテーブルの１レコード目のアドレスが格納）であることから、既にハッシュ結果の値において既存テーブルとの間でシノニムの関係があるとが検知される。なお、このとき、ＨＳＴテーブルは変更しない。
【００３８】
次に、データ処理部１は、ＨＳＴテーブルの１２７レコード目のアドレスが示すＴＡＴテーブルの１レコード目のシノニムオフセットにＴＡＴテーブルの有効レコード数（現在１）の１加算したレコードのアドレスを設定する。
以上のように展開された個別テーブル群Ａ、個別テーブル群Ｂの２つのテーブルへアクセスする場合には、以下のような処理が行われる。
【００３９】
個別テーブル群Ａにアクセスする際には、データ処理部１は、個別テーブル群ＡのテーブルＩＤを文字列から数値に変換し、母数１２８でハッシュ計算を行い、剰余を求める。ここで、余剰の結果は１２６であるとする。余剰の結果が１２６である場合には、データ処理部１は、ＨＳＴテーブルのデータレコード１２７にアクセスし、アドレス値を確認する。そして、ＨＳＴテーブルに設定されたアドレス値をエントリとして、ＴＡＴテーブルのデータレコードをアクセスする。ここでは、ＴＡＴテーブルのデータレコード「１」にアクセスしたとする。
【００４０】
次に、データ処理部１は、個別テーブル群ＡのテーブルＩＤとＴＡＴテーブルのデータレコード「１」の個別テーブル群ＩＤを比較する。ここで、個別テーブル群ＡのテーブルＩＤとＴＡＴテーブルのデータレコード「１」の個別テーブル群ＩＤとの比較結果が一致した場合には、ＴＡＴテーブルから展開開始アドレス値を取得し、個別テーブル群Ａにアクセスする。
【００４１】
個別テーブル群Ｂにアクセスする際には、データ処理部１は、個別テーブル群ＢのテーブルＩＤを文字列から数値に変換し、母数１２８でハッシュ計算を行い、剰余を求める。ここで、余剰の結果は１２６であるとする。余剰の結果が１２６であることから、ＨＳＴテーブルのデータレコード１２７にアクセスし、アドレス値を確認し、ＨＳＴテーブルに設定されたアドレス値をエントリとして、ＴＡＴテーブルのデータレコード「１」にアクセスする。そして、データ処理部１は、個別テーブル群ＢのテーブルＩＤとＴＡＴテーブルのデータレコード「１」の個別テーブル群ＩＤを比較する。前述したように、このテーブルＩＤはシノニムの関係にあるので、個別テーブル群ＢのテーブルＩＤとＴＡＴテーブルのデータレコード「１」の個別テーブル群ＩＤとは一致しない。
【００４２】
ここで、比較結果が不一致である場合には、データ処理部１は、ＴＡＴテーブルのシノニムオフセットを確認する。シノニムオフセットの内容からデータレコード「２」へ移動し、個別テーブル群ＢのテーブルＩＤとＴＡＴテーブルのデータレコード「２」の個別テーブル群ＩＤを比較する。ここで、比較結果が一致した場合には、データ処理部１は、データレコード「２」の展開開始アドレス値を取得し、個別テーブル群Ｂにアクセスする。
【００４３】
図５は、展開テーブルにアクセスする際の処理をフローチャートで示したものである。図５において、テーブルＩＤが入力されると（ステップＳ１）、データ処理部１は、テーブルＩＤを文字列から数値に変換し（ステップＳ２）、母数１２８の剰余からハッシュ値を計算する（ステップＳ３）。そして、データ処理部１は、このハッシュ値に対応するＨＳＴ領域１３のＨＳＴテーブルにアクセスし、図３に示したＨＳＴテーブルのデータレコードに基づいて、ＴＡＴテーブルのアドレス値を取得する（ステップＳ４）。そして、データ処理部１は、このアドレス値をエントリとして、ＴＡＴテーブルのデータレコードをアクセスし、図４に示したＴＡＴテーブルのデータレコードから、展開テーブルＩＤを取得する（ステップＳ５）。そして、データ処理部１は、入力されたテーブルＩＤと、展開テーブルＩＤとが一致するかどうかを判定する（ステップＳ６）。
【００４４】
ステップＳ６で、入力されたテーブルＩＤと展開テーブルＩＤとが一致する場合には、このＴＡＴテーブルのデータレコードから展開開始アドレスを取得し（ステップＳ７）、個別テーブル群にアクセスする（ステップＳ８）。
【００４５】
ステップＳ６で、入力されたテーブルＩＤと展開テーブルＩＤとが一致していない場合には、データ処理部１は、ＴＡＴテーブルからシノニムオフセットを取得し（ステップＳ９）、シノニムオフセットに従って、データレコードを移動し（ステップＳ１０）、ステップＳ６にリターンする。そして、データ処理部１は、再びステップＳ６で、移動したデータレコードで、入力されたテーブルＩＤと展開テーブルＩＤとが一致するかどうかを判定し、入力されたテーブルＩＤと展開テーブルＩＤとが一致する場合には、ＴＡＴテーブルから展開開始アドレスを取得し（ステップＳ７）、個別テーブル群にアクセスする（ステップＳ８）。
【００４６】
以上説明したように、本実施形態では、ＲＦＵ領域１２に共通エリア１１−１〜１１−８に展開された個別テーブル群１５−１〜１５−８の情報が記録されたＲＦＵテーブルが展開され、ＨＳＴ領域１３に個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されたＨＳＴテーブルが展開され、ＴＡＴ領域１４に個別テーブルの展開テーブルＩＤ、各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニムオフセットとが記録されるＴＡＴテーブルが展開される。そして、各共通エリア１１−１〜１１−８の個別テーブル群をアクセスするのに、ＨＳＴテーブルとＴＡＴテーブルとが用いられる。本実施形態では、ＴＡＴテーブルに、個別テーブルの展開テーブルＩＤ、各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニムオフセットとが記録されるので、同一のハッシュ値にマッピングされるテーブルＩＤをシノニム関係として処理することができ、個別テーブルのレコード数が増加しても、高速処理が可能となる。
【００４７】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００４８】
１…データ処理部， ２…記憶部， １０…共通エリア群， １１−１〜１１−８…共通エリア， １２…ＲＦＵ領域， １３…ＨＳＴ領域， １４…ＴＡＴ領域， １５…個別テーブル群
【技術分野】
【０００１】
本発明は、複数プログラムが同時にアクセス可能である汎用共通エリアに対して、高速アクセスが可能なテーブル構成方法、データアクセス方法、コンピュータプログラム、テーブル構成装置及びデータ処理装置に関する。
【背景技術】
【０００２】
コンピュータのハードウェアの性能向上が目覚ましく発展したことから、従来に比べテーブル配置やアクセス方式を意識しない設計であっても、少数のテーブル展開であれば、問題なく動作するようになってきている。しかしながら、一方で、コンピュータがあらゆる分野で活用され、大規模で多くのデータ量を所定の時間で処理するために、参照系のテーブルを複数枚の大きな共通エリアに展開することが行われている（例えば特許文献１）。この場合、その共通エリアテーブルへのアクセスが処理速度の低下のボトルネックとなる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平０９−１４６８１６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、これまで提案されているデータ処理方法では、展開するテーブル数に比例してアクセスが遅くなる、あるいは２枚目以降の汎用共通エリアに展開された場合にアクセスが遅くなる、テーブル配置が後のテーブルのアクセスがより遅くなる等の課題がある。
【０００５】
上述の課題を鑑み、本発明は、複数のプログラムが同時にアクセスできる共通エリアテーブルへのアクセスする際に、高速処理が可能なテーブル構成方法、データアクセス方法、コンピュータプログラム、テーブル構成装置及びデータ処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の一態様は、テーブル構成方法であって、共通エリアに個別テーブル群を展開するステップと、前記共通エリアに展開された個別テーブルの情報が記録されるリソーステーブルを展開するステップと、前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されるハッシングテーブルを展開するステップと、前記個別テーブルの展開テーブルＩＤ、前記個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報が記録されるアドレステーブルを展開するステップとを含むことを特徴とする。
【０００７】
本発明の一態様は、共通エリアに展開された個別テーブル群と、前記共通エリアに展開された個別テーブルの情報が記録されたリソーステーブルと、前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されたハッシングテーブルと、前記個別テーブルの展開テーブルＩＤ、前記各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報とが記録されたアドレステーブルとを含むデータ処理装置のデータアクセス方法であって、前記ハッシングテーブルと前記アドレステーブルとを用いて前記個別テーブル群をアクセスするステップを含むことを特徴とする。
【０００８】
本発明の一態様は、共通エリアに個別テーブル群を展開するステップと、前記共通エリアに展開された個別テーブルの情報が記録されるリソーステーブルを展開するステップと、前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されるハッシングテーブルを展開するステップと、前記個別テーブルの展開テーブルＩＤ、前記個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報が記録されるアドレステーブルを展開するステップと、をコンピュータに実行させるためのコンピュータプログラムである。
【０００９】
本発明の一態様は、共通エリアに展開された個別テーブル群と、前記共通エリアに展開された個別テーブルの情報が記録されたリソーステーブルと、前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されたハッシングテーブルと、前記個別テーブルの展開テーブルＩＤ、前記各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報とが記録されたアドレステーブルとを含むデータ処理装置に対し、前記ハッシングテーブルと前記アドレステーブルとを用いて前記個別テーブル群をアクセスするステップを実行させるためのコンピュータプログラムである。
【００１０】
本発明の一態様は、テーブル構成装置であって、共通エリアに個別テーブル群を展開する第一展開部と、前記共通エリアに展開された個別テーブルの情報が記録されるリソーステーブルを展開する第二展開部と、前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されるハッシングテーブルを展開する第三展開部と、前記個別テーブルの展開テーブルＩＤ、前記個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報が記録されるアドレステーブルを展開する第四展開部とを備えることを特徴とする。
【００１１】
本発明の一態様は、データ処理装置であって、複数のプログラムが同時にアクセス可能な共通エリアに展開された個別テーブル群と、前記共通エリアに展開された個別テーブルの情報が記録されたリソーステーブルと、前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されたハッシングテーブルと、前記個別テーブルの展開テーブルＩＤ、前記各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報とが記録されたアドレステーブルと、前記ハッシングテーブルと前記アドレステーブルとを用いて、前記個別テーブル群をアクセスするデータ処理部と、を備えることを特徴とする。
【発明の効果】
【００１２】
本発明によれば、各共通エリアに設けられた個別テーブル群をアクセスするのに、ハッシュ値が用いられ、同一のハッシュ値にマッピングされるテーブルＩＤをシノニム関係として処理している。このため、個別テーブル群へのアクセス処理時間を短縮することができる。
【図面の簡単な説明】
【００１３】
【図１】データ処理装置の構成を示すブロック図である。
【図２】ＲＦＵ領域１２に設けられるテーブルの具体例を示すものである。
【図３】ＨＳＴ領域１３に設けられるテーブルの具体例を示すものである。
【図４】ＴＡＴ領域１４に設けられるテーブルの具体例を示すものである。
【図５】展開テーブルにアクセスする際の処理をフローチャートで示したものである。
【発明を実施するための形態】
【００１４】
図１は、データ処理装置（テーブル構成装置）の構成を示すブロック図である。データ処理装置は、バスを介して互いに接続されたデータ処理部１と、記憶部２と、入力部３と、表示部４と、通信部５とを用いて構成される。データ処理部１は、ＣＰＵ（Central Processing Unit）やキャッシュ等の半導体記憶装置を用いて構成される。データ処理部１は、ＣＰＵが所定のプログラムを実行することによってデータ処理部１としての機能を実現する。記憶部２は、磁気ハードディスク装置や半導体記憶装置などの記憶装置を用いて構成される。入力部３には、キーボードやマウス等の入力装置が接続される。表示部４には、ＬＣＤ（Liquid Crystal Display）等の画像表示装置が接続される。なお、データ処理部１の機能の全て又は一部は、ＡＳＩＣ（Application Specific Integrated Circuit）やＰＬＤ（Programmable Logic Device）等のハードウェアを用いて実現されても良い。データ処理装置は、後述する各テーブルを生成する際には、テーブル構成装置として動作し、生成された各テーブルを用いてアクセスを行う際にはデータ処理装置として動作する。
【００１５】
記憶部２の記憶領域には、共通エリア群１０が設けられる。共通エリア群１０は、複数の共通エリアからなる。各共通エリアは、複数のプログラムが同時にアクセスできる記憶領域である。共通エリア群１０には、例えば８つの共通エリア１１−１〜１１−８が設けられる。共通エリア１１−１〜１１−８には、個別テーブル群１５−１〜１５−８が設けられる。
【００１６】
共通エリア１１−１の先頭には、ＲＦＵ（Resource Future Used）領域１２、ＨＳＴ（HaShing Table）領域１３、ＴＡＴ（Table Address Table）領域１４が設けられる。ＲＦＵ領域１２、ＨＳＴ領域１３、ＴＡＴ領域１４は、いずれもデータ処理部１の処理によって記憶部２に設けられる。
【００１７】
ＲＦＵ領域１２にはＲＦＵテーブルが記憶される。ＲＦＵテーブルには、データレコードとして、各共通エリア１１−１〜１１−８に展開された個別テーブル群１５−１〜１５−８のアドレス値、各共通エリア１１−１〜１１−８の空き領域のバイト数とが記録される。
【００１８】
ＨＳＴ領域１３にはＨＳＴテーブルが記憶される。ＨＳＴテーブルには、データレコードとして、個別テーブルのテーブルＩＤのハッシュ値と、各ハッシュ値に対応するＴＡＴテーブルへのエントリとなるアドレスとが記録される。ここで、ハッシュ値は、テーブルＩＤを文字列から数値に変換し、例えば母数１２８で除算し、その剰余から求められる。このように、文字列を数値に変換し、母数１２８で除算した剰余からハッシュ値を求めているため、その数は、「０」〜「１２７」となる。ＨＳＴテーブルには、「１」〜「１２８」の１２８個のレコードが設けられる。ＨＳＴテーブルの「１」〜「１２８」の各レコードには、ハッシュ値の「０」〜「１２７」に対応している。
【００１９】
ＴＡＴ領域１４にはＴＡＴテーブルが記憶される。ＴＡＴテーブルには、データレコードとして、個別テーブルの展開テーブルＩＤと、各個別テーブル群へのエントリとなる展開開始アドレスと、シノニムオフセットとが記録される。ここで、シノニムオフセットは、シノニム関係のテーブルＩＤがある場合に利用される。すなわち、前述したように、本実施形態では、テーブルＩＤの文字列を数値に変換し、母数１２８で除算した剰余からハッシュ値を求めている。この場合、ハッシュ値は「１」〜「１２８」となる。このため、異なるテーブルＩＤの文字列に対して同一のハッシュ値がマッピングされる可能性がある。ここでは、このように、同一のハッシュ値がマッピングされる場合を、シノニム関係としている。シノニムオフセットには、シノニム関係になるテーブルＩＤのデータレコードの位置を示すオフセットが記録される。
【００２０】
図２〜図４は、ＲＦＵ領域１２、ＨＳＴ領域１３、ＴＡＴ領域１４に設けられる各テーブルの具体例を示すものである。ＲＦＵ領域１２に記憶されるＲＦＵテーブル、ＨＳＴ領域１３に記憶されるＨＳＴテーブル、ＴＡＴ領域１４に記憶されるＴＡＴテーブルは、それぞれデータ処理部１の処理によって記録される。
【００２１】
ＲＦＵ領域１２は、共通エリア１１−１の先頭から例えば９６バイト分の領域として、データ処理部１によって確保される。ＲＦＵ領域１２のＲＦＵテーブルには、図２に示すように、テーブルＩＤ（１６バイト）と、テーブルサイズ（４バイト）と、テーブルレコード数（４バイト）と、データレコードサイズ（４バイト）と、データレコード「１」〜データレコード「８」（各８バイト）が設けられる。テーブルＩＤは、このＲＦＵテーブルを識別するためのものである。テーブルサイズは、このＲＦＵテーブルのテーブルサイズで、例えば９６バイトである。テーブルレコード数は、共通エリアの数を表しており、共通エリア１１−１〜１１−８が８個の場合には「８」である。データレコードサイズは、ＲＦＵテーブルの各データレコードのサイズである。データレコード「１」〜データレコード「８」には、各共通エリア１１−１〜１１−８に展開された個別テーブル群１５−１〜１５−８のアドレス値と、各共通エリア１１−１〜１１−８の空き領域のバイト数とが記録される。
【００２２】
ＨＳＴ領域１３は、共通エリア１１−１の先頭からＲＦＵテーブルに続いて例えば５４０バイト分の領域として、データ処理部１によって確保される。ＨＳＴ領域１３のＨＳＴテーブルには、図３に示すように、テーブルＩＤ（１６バイト）と、テーブルサイズ（４バイト）と、テーブルレコード数（４バイト）と、データレコードサイズ（４バイト）と、データレコード「１」〜データレコード「１２８」（各４バイト）とが設けられる。テーブルＩＤは、このＨＳＴテーブルを識別するためのものである。テーブルサイズは、このＨＳＴテーブルのテーブルサイズで、例えば５４０バイトである。テーブルレコード数は、このＨＳＴテーブルのレコード数である。このレコード数は、ハッシュ値の数に対応する。ここでは、データ処理部１は、テーブルＩＤの文字列を数値に変換し、母数１２８で除算した剰余からハッシュ値を求めている。そのため、テーブルレコード数は「１２８」となる。データレコードサイズは、ＨＳＴテーブルの各データレコードのサイズである。データレコード「１」〜データレコード「１２８」には、各ハッシュ値「０」〜「１２７」に対応して、ＴＡＴテーブルへのエントリとなるアドレスが記録される。なお、ハッシュ値「０」がデータレコード「１」に対応し、ハッシュ値「１２７」がデータレコード「１２８」に対応する。
【００２３】
ＴＡＴ領域１４は、共通エリア１１−１の先頭からＨＳＴテーブルに続いて例えば３１０４バイト分の領域として、データ処理部１によって確保される。ＴＡＴ領域１４のＴＡＴテーブルには、図４に示すように、テーブルＩＤ（１６バイト）と、テーブルサイズ（４バイト）と、テーブルレコード数（４バイト）と、有効レコード数（４バイト）と、データレコードサイズ（４バイト）と、データレコード「１」〜データレコード「１２８」（各２４バイト）とが設けられる。テーブルＩＤは、このＴＡＴテーブルを識別するためのものである。テーブルサイズは、このＴＡＴテーブルのテーブルサイズで、例えば３１０４バイトである。テーブルレコード数は、このＴＡＴテーブルのレコード数である。有効レコード数は、ＴＡＴテーブルに記録した有効レコード数である。データレコード「１」〜データレコード「１２８」には、各共通エリア１１−１〜１１−８に展開した個別テーブルの展開テーブルＩＤと、展開開始アドレスと、シノニムオフセットとが記録される。
【００２４】
以上のように、データ処理部１の処理によって、記憶部２にＲＦＵ領域１２、ＨＳＴ領域１３、ＴＡＴ領域１４が設けられ、それぞれの領域にテーブルが生成される。具体的には、ＲＦＵ領域１２への展開処理、ＨＳＴ領域１３への展開処理、ＴＡＴ領域１４への展開処理、テーブルＡへの展開処理、テーブルＢへの展開処理をデータ処理部１が順次実行することによって、テーブルが生成される。次に、上記の各テーブルを用いてデータにアクセスするための処理について説明する。本実施形態において、共通エリア１１−１〜１１−８の個別テーブル群をアクセスする際には、以下のような処理が行われる。
【００２５】
図１において、例えば入力部３から検索キーがテーブルＩＤとして入力されると、データ処理部１は、テーブルＩＤを文字列から数値に変換する。そして、データ処理部１は、母数１２８の剰余からハッシュ値を計算し、図３に示したＨＳＴ領域１３のＨＳＴテーブルにアクセスする。前述したように、各ハッシュ値「０」〜「１２７」は、ＨＳＴテーブルのデータレコード「１」〜データレコード「１２８」に対応している。そして、このＨＳＴテーブルのデータレコード「１」〜「１２８」には、図３に示すように、ＴＡＴテーブルへのエントリとなるアドレスが記録される。よって、データ処理部１は、検索キーとして入力されたテーブルＩＤのハッシュ値を計算し、このハッシュ値を基にＨＳＴテーブルにアクセスすることによって、ＴＡＴテーブルへのエントリとなるアドレス値を取得する。
【００２６】
データ処理部１は、ＴＡＴテーブルのアドレス値を取得すると、このアドレス値に基づいて、ＴＡＴテーブルにアクセスする。図４に示したように、ＴＡＴテーブルのデータレコード「１」〜「１２８」には、個別テーブルの展開テーブルＩＤと、展開開始アドレスと、シノニムオフセットとが記録されている。データ処理部１は、ＴＡＴテーブルにアクセスしたら、検索キーとして入力されたテーブルＩＤと、展開テーブルＩＤとが一致するかどうかを判定する。つまり、ＨＳＴテーブルからＴＡＴテーブルにアクセスする際に、シノニム関係にあるテーブルＩＤは、同一のデータレコードにアクセスされる。検索キーとして入力されたテーブルＩＤがそのＴＡＴテーブルのデータレコードそのものであれば、入力されたテーブルＩＤと展開テーブルＩＤとは一致する。一方で、シノニム関係のテーブルＩＤの場合には、入力されたテーブルＩＤと展開テーブルＩＤとは一致しない。
【００２７】
入力されたテーブルＩＤと展開テーブルＩＤとが一致する場合には、データ処理部１は、このＴＡＴテーブルのデータレコードから展開開始アドレスを取得する。そして、データ処理部１は、この展開開始アドレスをエントリとして、個別テーブル群１５−１〜１５−８にアクセスする。
【００２８】
入力されたテーブルＩＤと展開テーブルＩＤとが一致しない場合には、データ処理部１は、シノニムオフセットで示されるデータレコードに移動する。そして、データ処理部１は、移動したデータレコードで、再び、入力されたテーブルＩＤと、展開テーブルＩＤとが一致するかどうかを判定する。入力されたテーブルＩＤと展開テーブルＩＤとが一致する場合には、データ処理部１は、この移動したデータレコードから展開開始アドレスを取得する。そして、データ処理部１は、この展開開始アドレスをエントリとして、個別テーブル群１５−１〜１５−８にアクセスする。
【００２９】
このように、本実施形態では、各共通エリア１１−１〜１１−８の個別テーブル群１５−１〜１５−８にアクセスする際に、ハッシュ値が用いられる。そして、同一のハッシュ値にマッピングされるテーブルＩＤが、シノニム関係として処理される。これにより、個別テーブルのレコード数が多くなっても、高速アクセスが実現できる。
【００３０】
次に、共通エリア１１−１に個別テーブル群Ａ、共通エリア１１−２に個別テーブル群Ｂの２つのテーブルデータを展開する処理について具体的に説明する。図１において、先ず、データ処理部１は、８枚の共通エリア（ここでは各６４ＫＢと仮定し、管理テーブルが十分格納できるサイズの共通エリアとする）を確保し、先頭アドレスを取得する。次に、データ処理部１は、ＲＦＵ領域１２を共通エリア１１−１の先頭アドレスより９６バイト確保し、初期値を設定する。データ処理部１は、データレコード「１」には、共通エリア１１−１の先頭アドレスより９６バイト分加えたアドレスを設定する。また、データ処理部１は、データレコード「２」〜「８」には、それぞれ共通エリア１１−２〜１１−８の先頭アドレスを設定する。
【００３１】
次に、データ処理部１は、ＨＳＴ領域１３を共通エリア１１−１のＲＦＵテーブルに続き５４０バイト確保し、全てのレコードにＮＵＬＬ値を設定する。なお、データレコード「１」はハッシュ計算結果の剰余が「０」の場合、データレコード「１２８」はハッシュ計算結果の剰余が「１２７」の場合に使用される。
【００３２】
次に、データ処理部１は、ＴＡＴ領域１４を共通エリア１１−１のＨＳＴテーブルに続き３１０４バイト確保し、全てのレコードのテーブルＩＤ、アドレス、シノニムオフセットにＮＵＬＬ値を設定する。
【００３３】
次に、データ処理部１は、個別テーブル群Ａのテーブルサイズを事前の算出し、ＲＦＵテーブルの（１レコード目）から順番に空き領域サイズと比較し、格納できる共通エリアを決定する。今回は共通エリア１１−１に格納可能であったこととする。
【００３４】
次に、データ処理部１は、個別テーブル群Ａを共通エリア１１−１の空き領域の先頭（１レコード目のアドレス値）から展開する。そして、データ処理部１は、 ＲＦＵテーブルの１レコード目のアドレス値から個別テーブル群Ａのテーブルサイズを加え、かつ１レコード目の空き領域サイズから個別テーブル群Ａのテーブルサイズを減じて値を更新する。
【００３５】
次に、データ処理部１は、個別テーブル群ＡのテーブルＩＤを文字列から数値に変換し、母数１２８でハッシュ計算を行い、剰余を求める。ここで、剰余の値が１２６であったとする。剰余が１２６の場合には、データ処理部１は、ＨＳＴテーブルの１２７レコード目にＴＡＴテーブルの有効レコード数（現在０）の１加算したレコードのアドレスを設定する。なお、１件目で記していないが、ＨＳＴテーブルの１２７レコード目設定時にシノニムレコード有無チェックとして、１２７レコード目のアドレスがＮＵＬＬ値であることを確認する。なお、今回は１件目でＮＵＬＬ値であったとする。
【００３６】
次に、データ処理部１は、ＴＡＴテーブルの１レコード目の個別テーブル群ＩＤにテーブルＩＤを、展開開始アドレス値に個別テーブル群Ａの展開された先頭アドレスを設定する。
次に、データ処理部１は、個別テーブル群Ｂのテーブルサイズを事前の算出し、ＲＦＵテーブルの１レコード目から順番に空き領域サイズと比較し、格納できる共通エリアを決定する。今回は共通エリア１１−１に格納できず、共通エリア１１−２に格納可能であったこととする。この場合、個別テーブル群Ｂを共通エリア１１−２の空き領域の先頭から展開する。そして、データ処理部１は、ＲＦＵの２レコード目のアドレス値から個別テーブル群Ｂのテーブルサイズを加え、かつ２レコード目の空き領域サイズから個別テーブル群Ｂのテーブルサイズを減じて値を更新する。
【００３７】
次に、データ処理部１は、個別テーブル群ＢのテーブルＩＤを文字列から数値に変換し、母数１２８でハッシュ計算を行い、剰余を求める。この剰余の値が前回と同じ１２６であったとする。すなわち、前回のテーブルＩＤとシノニム関係であったとする。この場合、ＨＳＴテーブルの１２７レコード目のアドレスが非ＮＵＬＬ値（ＴＡＴテーブルの１レコード目のアドレスが格納）であることから、既にハッシュ結果の値において既存テーブルとの間でシノニムの関係があるとが検知される。なお、このとき、ＨＳＴテーブルは変更しない。
【００３８】
次に、データ処理部１は、ＨＳＴテーブルの１２７レコード目のアドレスが示すＴＡＴテーブルの１レコード目のシノニムオフセットにＴＡＴテーブルの有効レコード数（現在１）の１加算したレコードのアドレスを設定する。
以上のように展開された個別テーブル群Ａ、個別テーブル群Ｂの２つのテーブルへアクセスする場合には、以下のような処理が行われる。
【００３９】
個別テーブル群Ａにアクセスする際には、データ処理部１は、個別テーブル群ＡのテーブルＩＤを文字列から数値に変換し、母数１２８でハッシュ計算を行い、剰余を求める。ここで、余剰の結果は１２６であるとする。余剰の結果が１２６である場合には、データ処理部１は、ＨＳＴテーブルのデータレコード１２７にアクセスし、アドレス値を確認する。そして、ＨＳＴテーブルに設定されたアドレス値をエントリとして、ＴＡＴテーブルのデータレコードをアクセスする。ここでは、ＴＡＴテーブルのデータレコード「１」にアクセスしたとする。
【００４０】
次に、データ処理部１は、個別テーブル群ＡのテーブルＩＤとＴＡＴテーブルのデータレコード「１」の個別テーブル群ＩＤを比較する。ここで、個別テーブル群ＡのテーブルＩＤとＴＡＴテーブルのデータレコード「１」の個別テーブル群ＩＤとの比較結果が一致した場合には、ＴＡＴテーブルから展開開始アドレス値を取得し、個別テーブル群Ａにアクセスする。
【００４１】
個別テーブル群Ｂにアクセスする際には、データ処理部１は、個別テーブル群ＢのテーブルＩＤを文字列から数値に変換し、母数１２８でハッシュ計算を行い、剰余を求める。ここで、余剰の結果は１２６であるとする。余剰の結果が１２６であることから、ＨＳＴテーブルのデータレコード１２７にアクセスし、アドレス値を確認し、ＨＳＴテーブルに設定されたアドレス値をエントリとして、ＴＡＴテーブルのデータレコード「１」にアクセスする。そして、データ処理部１は、個別テーブル群ＢのテーブルＩＤとＴＡＴテーブルのデータレコード「１」の個別テーブル群ＩＤを比較する。前述したように、このテーブルＩＤはシノニムの関係にあるので、個別テーブル群ＢのテーブルＩＤとＴＡＴテーブルのデータレコード「１」の個別テーブル群ＩＤとは一致しない。
【００４２】
ここで、比較結果が不一致である場合には、データ処理部１は、ＴＡＴテーブルのシノニムオフセットを確認する。シノニムオフセットの内容からデータレコード「２」へ移動し、個別テーブル群ＢのテーブルＩＤとＴＡＴテーブルのデータレコード「２」の個別テーブル群ＩＤを比較する。ここで、比較結果が一致した場合には、データ処理部１は、データレコード「２」の展開開始アドレス値を取得し、個別テーブル群Ｂにアクセスする。
【００４３】
図５は、展開テーブルにアクセスする際の処理をフローチャートで示したものである。図５において、テーブルＩＤが入力されると（ステップＳ１）、データ処理部１は、テーブルＩＤを文字列から数値に変換し（ステップＳ２）、母数１２８の剰余からハッシュ値を計算する（ステップＳ３）。そして、データ処理部１は、このハッシュ値に対応するＨＳＴ領域１３のＨＳＴテーブルにアクセスし、図３に示したＨＳＴテーブルのデータレコードに基づいて、ＴＡＴテーブルのアドレス値を取得する（ステップＳ４）。そして、データ処理部１は、このアドレス値をエントリとして、ＴＡＴテーブルのデータレコードをアクセスし、図４に示したＴＡＴテーブルのデータレコードから、展開テーブルＩＤを取得する（ステップＳ５）。そして、データ処理部１は、入力されたテーブルＩＤと、展開テーブルＩＤとが一致するかどうかを判定する（ステップＳ６）。
【００４４】
ステップＳ６で、入力されたテーブルＩＤと展開テーブルＩＤとが一致する場合には、このＴＡＴテーブルのデータレコードから展開開始アドレスを取得し（ステップＳ７）、個別テーブル群にアクセスする（ステップＳ８）。
【００４５】
ステップＳ６で、入力されたテーブルＩＤと展開テーブルＩＤとが一致していない場合には、データ処理部１は、ＴＡＴテーブルからシノニムオフセットを取得し（ステップＳ９）、シノニムオフセットに従って、データレコードを移動し（ステップＳ１０）、ステップＳ６にリターンする。そして、データ処理部１は、再びステップＳ６で、移動したデータレコードで、入力されたテーブルＩＤと展開テーブルＩＤとが一致するかどうかを判定し、入力されたテーブルＩＤと展開テーブルＩＤとが一致する場合には、ＴＡＴテーブルから展開開始アドレスを取得し（ステップＳ７）、個別テーブル群にアクセスする（ステップＳ８）。
【００４６】
以上説明したように、本実施形態では、ＲＦＵ領域１２に共通エリア１１−１〜１１−８に展開された個別テーブル群１５−１〜１５−８の情報が記録されたＲＦＵテーブルが展開され、ＨＳＴ領域１３に個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されたＨＳＴテーブルが展開され、ＴＡＴ領域１４に個別テーブルの展開テーブルＩＤ、各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニムオフセットとが記録されるＴＡＴテーブルが展開される。そして、各共通エリア１１−１〜１１−８の個別テーブル群をアクセスするのに、ＨＳＴテーブルとＴＡＴテーブルとが用いられる。本実施形態では、ＴＡＴテーブルに、個別テーブルの展開テーブルＩＤ、各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニムオフセットとが記録されるので、同一のハッシュ値にマッピングされるテーブルＩＤをシノニム関係として処理することができ、個別テーブルのレコード数が増加しても、高速処理が可能となる。
【００４７】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００４８】
１…データ処理部， ２…記憶部， １０…共通エリア群， １１−１〜１１−８…共通エリア， １２…ＲＦＵ領域， １３…ＨＳＴ領域， １４…ＴＡＴ領域， １５…個別テーブル群
【特許請求の範囲】
【請求項１】
共通エリアに個別テーブル群を展開するステップと、
前記共通エリアに展開された個別テーブルの情報が記録されるリソーステーブルを展開するステップと、
前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されるハッシングテーブルを展開するステップと、
前記個別テーブルの展開テーブルＩＤ、前記個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報が記録されるアドレステーブルを展開するステップと
を含むことを特徴とするテーブル構成方法。
【請求項２】
前記ハッシュ値は、前記テーブルＩＤの文字列を数値に変換し、所定数の母数で除算した剰余から求めることを特徴とする請求項１に記載のテーブル構成方法。
【請求項３】
前記シノニム情報は、ハッシュ値が同一となるテーブルＩＤのレコードの位置を示すオフセットであることを特徴とする請求項１又は２に記載のテーブル構成方法。
【請求項４】
共通エリアに展開された個別テーブル群と、
前記共通エリアに展開された個別テーブルの情報が記録されたリソーステーブルと、
前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されたハッシングテーブルと、
前記個別テーブルの展開テーブルＩＤ、前記各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報とが記録されたアドレステーブルと
を含むデータ処理装置のデータアクセス方法であって、
前記ハッシングテーブルと前記アドレステーブルとを用いて前記個別テーブル群をアクセスするステップを含む
ことを特徴とするデータアクセス方法。
【請求項５】
前記ハッシングテーブルと前記アドレステーブルとを用いて前記個別テーブル群をアクセスするステップは、
入力されたテーブルＩＤのハッシュ値を求め、前記ハッシュ値をエントリとして前記ハッシングテーブルのレコードをアクセスするステップと、
当該ハッシングテーブルのレコードから前記アドレステーブルへのエントリとなるレコードのアドレスを取得し、前記取得されたアドレスで前記アドレステーブルのレコードをアクセスするステップと、
前記入力されたテーブルＩＤと前記アドレステーブルのレコードから得られた展開テーブルＩＤが一致しているかどうかを判定するステップと、
前記入力されたテーブルＩＤと前記アドレステーブルのレコードから得られた展開テーブルＩＤが一致していたら、当該レコードの展開開始アドレスを取得して前記個別テーブル群をアクセスするステップと、
前記入力されたテーブルＩＤと前記アドレステーブルのレコードから得られた展開テーブルＩＤが一致していなければ、前記シノニム情報に従ってレコードに移動し、当該移動したレコードの展開開始アドレスを取得して前記個別テーブル群をアクセスするステップと
を含むことを特徴とする請求項４に記載のデータアクセス方法。
【請求項６】
共通エリアに個別テーブル群を展開するステップと、
前記共通エリアに展開された個別テーブルの情報が記録されるリソーステーブルを展開するステップと、
前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されるハッシングテーブルを展開するステップと、
前記個別テーブルの展開テーブルＩＤ、前記個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報が記録されるアドレステーブルを展開するステップと、
をコンピュータに実行させるためのコンピュータプログラム。
【請求項７】
共通エリアに展開された個別テーブル群と、
前記共通エリアに展開された個別テーブルの情報が記録されたリソーステーブルと、
前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されたハッシングテーブルと、
前記個別テーブルの展開テーブルＩＤ、前記各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報とが記録されたアドレステーブルと
を含むデータ処理装置に対し、
前記ハッシングテーブルと前記アドレステーブルとを用いて前記個別テーブル群をアクセスするステップを実行させるためのコンピュータプログラム。
【請求項８】
共通エリアに個別テーブル群を展開する第一展開部と、
前記共通エリアに展開された個別テーブルの情報が記録されるリソーステーブルを展開する第二展開部と、
前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されるハッシングテーブルを展開する第三展開部と、
前記個別テーブルの展開テーブルＩＤ、前記個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報が記録されるアドレステーブルを展開する第四展開部と
を備えることを特徴とするテーブル構成装置。
【請求項９】
複数のプログラムが同時にアクセス可能な共通エリアに展開された個別テーブル群と、
前記共通エリアに展開された個別テーブルの情報が記録されたリソーステーブルと、
前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されたハッシングテーブルと、
前記個別テーブルの展開テーブルＩＤ、前記各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報とが記録されたアドレステーブルと、
前記ハッシングテーブルと前記アドレステーブルとを用いて、前記個別テーブル群をアクセスするデータ処理部と、
を備えることを特徴とするデータ処理装置。
【請求項１】
共通エリアに個別テーブル群を展開するステップと、
前記共通エリアに展開された個別テーブルの情報が記録されるリソーステーブルを展開するステップと、
前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されるハッシングテーブルを展開するステップと、
前記個別テーブルの展開テーブルＩＤ、前記個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報が記録されるアドレステーブルを展開するステップと
を含むことを特徴とするテーブル構成方法。
【請求項２】
前記ハッシュ値は、前記テーブルＩＤの文字列を数値に変換し、所定数の母数で除算した剰余から求めることを特徴とする請求項１に記載のテーブル構成方法。
【請求項３】
前記シノニム情報は、ハッシュ値が同一となるテーブルＩＤのレコードの位置を示すオフセットであることを特徴とする請求項１又は２に記載のテーブル構成方法。
【請求項４】
共通エリアに展開された個別テーブル群と、
前記共通エリアに展開された個別テーブルの情報が記録されたリソーステーブルと、
前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されたハッシングテーブルと、
前記個別テーブルの展開テーブルＩＤ、前記各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報とが記録されたアドレステーブルと
を含むデータ処理装置のデータアクセス方法であって、
前記ハッシングテーブルと前記アドレステーブルとを用いて前記個別テーブル群をアクセスするステップを含む
ことを特徴とするデータアクセス方法。
【請求項５】
前記ハッシングテーブルと前記アドレステーブルとを用いて前記個別テーブル群をアクセスするステップは、
入力されたテーブルＩＤのハッシュ値を求め、前記ハッシュ値をエントリとして前記ハッシングテーブルのレコードをアクセスするステップと、
当該ハッシングテーブルのレコードから前記アドレステーブルへのエントリとなるレコードのアドレスを取得し、前記取得されたアドレスで前記アドレステーブルのレコードをアクセスするステップと、
前記入力されたテーブルＩＤと前記アドレステーブルのレコードから得られた展開テーブルＩＤが一致しているかどうかを判定するステップと、
前記入力されたテーブルＩＤと前記アドレステーブルのレコードから得られた展開テーブルＩＤが一致していたら、当該レコードの展開開始アドレスを取得して前記個別テーブル群をアクセスするステップと、
前記入力されたテーブルＩＤと前記アドレステーブルのレコードから得られた展開テーブルＩＤが一致していなければ、前記シノニム情報に従ってレコードに移動し、当該移動したレコードの展開開始アドレスを取得して前記個別テーブル群をアクセスするステップと
を含むことを特徴とする請求項４に記載のデータアクセス方法。
【請求項６】
共通エリアに個別テーブル群を展開するステップと、
前記共通エリアに展開された個別テーブルの情報が記録されるリソーステーブルを展開するステップと、
前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されるハッシングテーブルを展開するステップと、
前記個別テーブルの展開テーブルＩＤ、前記個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報が記録されるアドレステーブルを展開するステップと、
をコンピュータに実行させるためのコンピュータプログラム。
【請求項７】
共通エリアに展開された個別テーブル群と、
前記共通エリアに展開された個別テーブルの情報が記録されたリソーステーブルと、
前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されたハッシングテーブルと、
前記個別テーブルの展開テーブルＩＤ、前記各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報とが記録されたアドレステーブルと
を含むデータ処理装置に対し、
前記ハッシングテーブルと前記アドレステーブルとを用いて前記個別テーブル群をアクセスするステップを実行させるためのコンピュータプログラム。
【請求項８】
共通エリアに個別テーブル群を展開する第一展開部と、
前記共通エリアに展開された個別テーブルの情報が記録されるリソーステーブルを展開する第二展開部と、
前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されるハッシングテーブルを展開する第三展開部と、
前記個別テーブルの展開テーブルＩＤ、前記個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報が記録されるアドレステーブルを展開する第四展開部と
を備えることを特徴とするテーブル構成装置。
【請求項９】
複数のプログラムが同時にアクセス可能な共通エリアに展開された個別テーブル群と、
前記共通エリアに展開された個別テーブルの情報が記録されたリソーステーブルと、
前記個別テーブルのテーブルＩＤのハッシュ値に対応してアドレステーブルへのエントリとなるアドレスが記録されたハッシングテーブルと、
前記個別テーブルの展開テーブルＩＤ、前記各個別テーブル群へのエントリとなる展開開始アドレス、及びシノニム情報とが記録されたアドレステーブルと、
前記ハッシングテーブルと前記アドレステーブルとを用いて、前記個別テーブル群をアクセスするデータ処理部と、
を備えることを特徴とするデータ処理装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１１−２１５７６５（Ｐ２０１１−２１５７６５Ａ）
【公開日】平成２３年１０月２７日（２０１１．１０．２７）
【国際特許分類】
【出願番号】特願２０１０−８１８７８（Ｐ２０１０−８１８７８）
【出願日】平成２２年３月３１日（２０１０．３．３１）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【出願人】（０００２３２２２１）日本電気航空宇宙システム株式会社 (14)
【Ｆターム（参考）】
【公開日】平成２３年１０月２７日（２０１１．１０．２７）
【国際特許分類】
【出願日】平成２２年３月３１日（２０１０．３．３１）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【出願人】（０００２３２２２１）日本電気航空宇宙システム株式会社 (14)
【Ｆターム（参考）】
[ Back to top ]