(57)【要約】  データベースに対するデータ更新の効率的かつ高速な実行を可能にするデータベースシステムを提供する。データベースシステムは、クエリに基づいたデータ処理をデータベースに対して実行するデータ処理部を備える。データベースは、実体データそのものを一意に表す固定長のデータ識別子が格納されている識別子テーブルと変換テーブルとを含む。変換テーブルは、実体データの記憶領域の位置を示す位置データとデータ識別子との間の対応関係を表すものである。この変換テーブルはメタデータ領域Ｆｉｄｘを有し、このメタデータ領域Ｆｉｄｘには、識別子テーブルにおいてデータ識別子が格納されているタプルを一意に表すタプル識別子が格納されている。
2010084754.tif 000002
【特許請求の範囲】
【請求項１】
複数の実体データを含むデータベースを有するデータ記憶部と、
クエリを受信し、当該受信されたクエリに基づいたデータ処理を前記データベースに対して実行するデータ処理部と、
を備え、
前記データベースは、
行方向に定義された少なくとも１つのタプルと列方向に定義された少なくとも１つの属性フィールドとで定まる領域に前記実体データそのものを一意に表す固定長のデータ識別子が格納されている識別子テーブルと、
前記複数の実体データそれぞれの記憶領域の位置を示す位置データと前記複数のデータ識別子との間の対応関係を表す変換テーブルと、
を含み、
前記変換テーブルは、前記識別子テーブルにおいて前記各データ識別子が格納されている当該タプルを一意に表すタプル識別子が格納されるメタデータ領域を有する、データベースシステム。
【請求項２】
請求項１記載のデータベースシステムであって、前記識別子テーブルに割り当てられた記憶領域と前記実体データに割り当てられた記憶領域とが互いに異なる、データベースシステム。
【請求項３】
請求項１または２記載のデータベースシステムであって、前記データ識別子の値は、前記実体データの入力に対して固定長のビット列を出力するハッシュ関数の出力値である、データベースシステム。
【請求項４】
請求項１から３のうちのいずれか１項に記載のデータベースシステムであって、前記メタデータ領域のサイズは固定長である、データベースシステム。
【請求項５】
請求項４に記載のデータベースシステムであって、前記変換テーブルは、前記各データ識別子に対して、前記タプル識別子のデータ量が前記メタデータ領域の固定長サイズを超えたか否かを示すフラグ情報が格納されるフラグ領域を有する、データベースシステム。
【請求項６】
請求項４または５に記載のデータベースシステムであって、
前記データベースは、前記タプル識別子のデータ量が前記固定長サイズを超えるときに当該タプル識別子の全部または一部が格納されるオーバフロー領域を更に有し、
前記データ処理部は、前記タプル識別子のデータ量が前記固定長サイズを超えるときに、当該タプル識別子の全部または一部を前記オーバフロー領域に格納する、データベースシステム。
【請求項７】
請求項６に記載のデータベースシステムであって、前記データ処理部は、前記オーバフロー領域に前記タプル識別子を格納するとき、当該タプル識別子の記憶領域の位置を示す位置データを前記メタデータ領域に格納する、データベースシステム。
【請求項８】
請求項７に記載のデータベースシステムであって、前記タプル識別子の記憶領域の位置を示す位置データは、前記タプル識別子の記憶領域の絶対的位置を指定するアドレスである、データベースシステム。
【請求項９】
請求項７に記載のデータベースシステムであって、前記タプル識別子の記録領域の位置を示す位置データは、前記タプル識別子の記憶領域の相対的位置を指定するオフセットである、データベースシステム。
【請求項１０】
請求項１から９のうちのいずれか１項に記載のデータベースシステムであって、前記複数の実体データは可変長データを含む、データベースシステム。
【請求項１１】
請求項１から１０のうちのいずれか１項に記載のデータベースシステムであって、
前記識別子テーブルは複数存在し、
前記データベースは、前記複数の識別子テーブル内のデータ識別子をそれぞれ一意に表す参照識別子の集合を有する参照テーブルを更に含み、
前記データ処理部は、前記参照テーブルおよび前記識別子テーブルを用いて前記データ処理を実行する、データベースシステム。
【請求項１２】
請求項１から１１のうちのいずれか１項に記載のデータベースシステムであって、
前記クエリは、問い合わせ言語で記述されており、
前記データ処理部は、前記クエリを解析し、その解析結果に基づいたトランザクションを前記データ処理として前記データベースに対して実行する、データベースシステム。
【請求項１３】
複数の実体データを含むデータベース構造であって、
行方向に定義された少なくとも１つのタプルと列方向に定義された少なくとも１つの属性フィールドとで定まる領域に前記実体データそのものを一意に表す固定長のデータ識別子が格納されている識別子テーブルと、
前記複数の実体データそれぞれの記憶領域の位置を示す位置データと前記複数のデータ識別子との間の対応関係を表す変換テーブルと、
を含み、
前記変換テーブルは、前記識別子テーブルにおいて前記各データ識別子が格納されている当該タプルを一意に表すタプル識別子が格納されるメタデータ領域を有する、データベース構造。
【請求項１４】
請求項１３記載のデータベース構造であって、前記識別子テーブルに割り当てられた記憶領域と前記実体データに割り当てられた記憶領域とが互いに異なる、データベース構造。
【請求項１５】
請求項１３または１４に記載のデータベース構造であって、前記メタデータ領域のサイズは固定長である、データベース構造。
【請求項１６】
請求項１５に記載のデータベース構造であって、前記変換テーブルは、前記各データ識別子に対して、前記タプル識別子のデータ量が前記メタデータ領域の固定長サイズを超えたか否かを示すフラグ情報が格納されるフラグ領域を有する、データベース構造。
【請求項１７】
請求項１５または１６に記載のデータベース構造であって、前記タプル識別子のデータ量が前記固定長サイズを超えるときに当該タプル識別子の全部または一部が格納されるオーバフロー領域を更に有するデータベース構造。
【請求項１８】
（ａ）複数の実体データを含むデータベースについてクエリを受信するステップと、
（ｂ）前記データベースに対して、当該受信されたクエリに基づいたデータ処理を実行するステップと、
を備え、
前記データベースは、
行方向に定義された少なくとも１つのタプルと列方向に定義された少なくとも１つの属性フィールドとで定まる領域に前記実体データそのものを一意に表す固定長のデータ識別子が格納されている識別子テーブルと、
前記複数の実体データそれぞれの記憶領域の位置を示す位置データと前記複数のデータ識別子との間の対応関係を表す変換テーブルと、
を含み、
前記変換テーブルは、前記識別子テーブルにおいて前記各データ識別子が格納されている当該タプルを一意に表すタプル識別子が格納されるメタデータ領域を有する、データベース管理方法。
【請求項１９】
請求項１８記載のデータベース管理方法であって、前記識別子テーブルに割り当てられた記憶領域と前記実体データに割り当てられた記憶領域とが互いに異なる、データベース管理方法。
【請求項２０】
請求項１８または１９に記載のデータベース管理方法であって、前記メタデータ領域のサイズは固定長である、データベース管理方法。
【請求項２１】
請求項２０に記載のデータベース管理方法であって、前記変換テーブルは、前記各データ識別子に対して、前記タプル識別子のデータ量が前記メタデータ領域の固定長サイズを超えたか否かを示すフラグ情報が格納されるフラグ領域を有する、データベース管理方法。
【請求項２２】
請求項２０または２１に記載のデータベース管理方法であって、
前記データベースは、前記タプル識別子のデータ量が前記固定長サイズを超えるときに当該タプル識別子の全部または一部が格納されるオーバフロー領域を有し、
前記ステップ（ｂ）は、前記タプル識別子のデータ量が前記固定長サイズを超えるときに、当該タプル識別子の全部または一部を前記オーバフロー領域に格納するステップを含む、データベース管理方法。
【請求項２３】
請求項２２に記載のデータベース管理方法であって、前記ステップ（ｂ）は、前記オーバフロー領域に前記タプル識別子が格納されるとき、当該タプル識別子の記憶領域の位置を示す位置データを前記メタデータ領域に格納するステップを含む、データベース管理方法。
【請求項２４】
コンピュータによって読み取り可能な記録媒体であって、
複数の実体データを含むデータベースについてクエリを受信する処理と、
前記データベースに対して当該受信されたクエリに基づいて実行されるデータ処理と、
を含むデータベース管理処理を前記コンピュータに実行させるコンピュータプログラムを格納し、
前記データベースは、
行方向に定義された少なくとも１つのタプルと列方向に定義された少なくとも１つの属性フィールドとで定まる領域に前記実体データそのものを一意に表す固定長のデータ識別子が格納されている識別子テーブルと、
前記複数の実体データそれぞれの記憶領域の位置を示す位置データと前記複数のデータ識別子との間の対応関係を表す変換テーブルと、
を含み、
前記変換テーブルは、前記識別子テーブルにおいて前記各データ識別子が格納されている当該タプルを一意に表すタプル識別子が格納されるメタデータ領域を有することを特徴とする記憶媒体。
【請求項２５】
請求項２４記載の記憶媒体であって、前記識別子テーブルに割り当てられた記憶領域と前記実体データに割り当てられた記憶領域とが互いに異なることを特徴とする記憶媒体。
【請求項２６】
請求項２４または２５に記載の記憶媒体であって、前記メタデータ領域のサイズは固定長であることを特徴とする記憶媒体。
【請求項２７】
請求項２６に記載の記憶媒体であって、前記変換テーブルは、前記各データ識別子に対して、前記タプル識別子のデータ量が前記メタデータ領域の固定長サイズを超えたか否かを示すフラグ情報が格納されるフラグ領域を有することを特徴とする記憶媒体。
【請求項２８】
請求項２６または２７に記載の記憶媒体であって、
前記データベースは、前記タプル識別子のデータ量が前記固定長サイズを超えるときに当該タプル識別子の全部または一部が格納されるオーバフロー領域を有し、
前記データ処理は、前記タプル識別子のデータ量が前記固定長サイズを超えるときに、当該タプル識別子の全部または一部を前記オーバフロー領域に格納する処理を含むことを特徴とする記憶媒体。
【請求項２９】
請求項２８に記載の記憶媒体であって、前記データ処理は、前記オーバフロー領域に前記タプル識別子が格納されるとき、当該タプル識別子の記憶領域の位置を示す位置データを前記メタデータ領域に格納する処理を含むことを特徴とする記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベース構造並びにデータベースに対するデータ処理を実行する技術に関する。
【背景技術】
【０００２】
ＲＤＢＭＳ（Relational DataBase Management System：リレーショナル・データベース管理システム）は、１９７０年にＥ・Ｆ・コッド（Edgar Frank Codd）により提唱された関係モデル（リレーショナルモデル）理論に基づいたシステムであり、現在広く使用されている。ＲＤＢ（Relational DataBase）は、複数のテーブル（すなわち、リレーション）の集合体であり、各テーブルは、少なくとも１つの行（タプル）と列（属性フィールド）とを有する。ＲＤＢＭＳに関する先行技術文献としては、たとえば、特許文献１（特開２００５−２０８７５７号公報）が挙げられる。【０００３】
しかしながら、一般にＲＤＢＭＳでは、データ処理量が巨大になり処理負荷が増大したときに、トランザクションの処理速度の低下が目立つようになる。この原因の１つとして、ＲＤＢを構成するテーブルを行単位で検索する際に、このテーブルの各行のデータ長が可変長である場合には、当該各行のデータ長が固定長である場合と比べて、データの読み出し位置の計算時間がかかることが挙げられる。【０００４】
また、ＲＤＢＭＳは、行ごとに一意のキー（key）を用いて行単位でデータを管理するため、行単位での大規模処理を高速かつ効率的に実行できるが、列単位での大規模処理を効率的に実行することが難しいという問題がある。たとえば、ＲＤＢＭＳは、列単位でデータ処理を実行する際、クエリが要求する列に対応する複数行のデータを読み出す必要があり、これが処理速度の低下を招くという問題がある。更に、ＲＤＢＭＳは、行単位でデータをメモリ内の連続的な記憶領域に書き込むことができるため、行単位でデータに高速にアクセスすることができる。しかしながら、ＲＤＢＭＳが、列単位での検索処理、比較演算あるいは集計演算などに関するトランザクションを実行する際には、非連続な複数のメモリ領域に格納されたデータにアクセスする現象が頻繁に生じ、これにより処理速度が低下する場合がある。【０００５】
一方、大規模な検索や集計を効率的に実行するデータベースシステムとして、データウェアハウス（ＤＷＨ：Data WareHouse）と称するシステムが使用されている。しかしながら、ＤＷＨは、基幹系業務システムとは独立して構築され、原則としてデータ更新（新規データの追加、既存データの変更または既存データの削除）を行わないシステムである。それ故、ＤＷＨは、データ更新を効率的に実行し得るデータベース構造を有していない。【０００６】
そこで、従来のＲＤＢＭＳやＤＷＨに関する前述の問題を解消することを目的として、たとえば、特許文献２（特開２０００−３３９３９０号公報）および特許文献３（国際公開第００／１０１０３号パンフレット）に開示されたシステムが提案されている。特許文献２および特許文献３のデータベースシステムは、論理的な表形式のデータを、たとえば、性別、年齢、身長および体重のそれぞれの項目に対応する複数の情報ブロックに変換することで得られるデータベース構造を利用する。各情報ブロックは、値管理テーブル（値リスト）と、この値管理テーブルへのポインタ配列とを含む。ここで、値管理テーブルへのポインタ配列とは、表形式のデータの或る列の項目値番号（すなわち値管理テーブルへのポインタ）が当該表形式のデータの所定の順番（レコード番号順）に格納された配列である。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００５−２０８７５７号公報
【特許文献２】特開２０００−３３９３９０号公報
【特許文献３】国際公開第００／１０１０３号パンフレット
【発明の概要】
【０００８】
しかしながら、特許文献２および特許文献３のデータベース構造では、データ更新（たとえば、レコードの更新、挿入または削除）の高速化のために、値管理テーブル内の項目値番号が所定の順番で配列されることが要求される。このため、データ更新の際に新たな項目値番号が値管理テーブルに挿入されると、他の既存の項目値番号を再配列する必要がある。この再配列後の項目値番号と整合するように、値管理テーブルへのポインタ配列も更新しなければならない。したがって、特許文献２および特許文献３のデータベース構造では、データ更新を効率的かつ高速に実行することができない。特に、データ更新が頻繁に行われる場合には、処理負荷が極めて大きくなり、処理速度が著しく低下するという問題がある。
【０００９】
上記に鑑みて本発明の目的は、データベースに対するデータ更新の効率的かつ高速な実行を可能にするとともに検索や集計の処理速度の向上をも実現し得るデータベースシステム、データベース管理方法、データベース構造および記憶媒体を提供することである。
【００１０】
本発明によれば、複数の実体データを含むデータベースを有するデータ記憶部と、クエリを受信し、当該受信されたクエリに基づいたデータ処理を前記データベースに対して実行するデータ処理部と、を備えたデータベースシステムが提供される。このデータベースシステムでは、前記データベースは、行方向に定義された少なくとも１つのタプルと列方向に定義された少なくとも１つの属性フィールドとで定まる領域に前記実体データそのものを一意に表す固定長のデータ識別子が格納されている識別子テーブルと、前記複数の実体データそれぞれの記憶領域の位置を示す位置データと前記複数のデータ識別子との間の対応関係を表す変換テーブルと、を含み、前記変換テーブルは、前記識別子テーブルにおいて前記各データ識別子が格納されている当該タプルを一意に表すタプル識別子が格納されるメタデータ領域を有する。
【００１１】
本発明によれば、複数の実体データを含むデータベース構造が提供される。このデータベース構造は、行方向に定義された少なくとも１つのタプルと列方向に定義された少なくとも１つの属性フィールドとで定まる領域に前記実体データそのものを一意に表す固定長のデータ識別子が格納されている識別子テーブルと、前記複数の実体データそれぞれの記憶領域の位置を示す位置データと前記複数のデータ識別子との間の対応関係を表す変換テーブルと、を含み、前記変換テーブルは、前記識別子テーブルにおいて前記各データ識別子が格納されている当該タプルを一意に表すタプル識別子が格納されるメタデータ領域を有する。
【００１２】
本発明によれば、（ａ）複数の実体データを含むデータベースについてクエリを受信するステップと、（ｂ）前記データベースに対して、当該受信されたクエリに基づいたデータ処理を実行するステップと、を備えたデータベース管理方法が提供される。このデータベース管理方法では、前記データベースは、行方向に定義された少なくとも１つのタプルと列方向に定義された少なくとも１つの属性フィールドとで定まる領域に前記実体データそのものを一意に表す固定長のデータ識別子が格納されている識別子テーブルと、前記複数の実体データそれぞれの記憶領域の位置を示す位置データと前記複数のデータ識別子との間の対応関係を表す変換テーブルと、を含み、前記変換テーブルは、前記識別子テーブルにおいて前記各データ識別子が格納されている当該タプルを一意に表すタプル識別子が格納されるメタデータ領域を有する。
【００１３】
本発明によれば、コンピュータによって読み取り可能な記録媒体であって、複数の実体データを含むデータベースについてクエリを受信する処理と、前記データベースに対して当該受信されたクエリに基づいて実行されるデータ処理と、を含むデータベース管理処理を前記コンピュータに実行させるコンピュータプログラムを格納している記憶媒体が提供される。前記データベースは、行方向に定義された少なくとも１つのタプルと列方向に定義された少なくとも１つの属性フィールドとで定まる領域に前記実体データそのものを一意に表す固定長のデータ識別子が格納されている識別子テーブルと、前記複数の実体データそれぞれの記憶領域の位置を示す位置データと前記複数のデータ識別子との間の対応関係を表す変換テーブルと、を含んでいる。さらに、前記変換テーブルは、前記識別子テーブルにおいて前記各データ識別子が格納されている当該タプルを一意に表すタプル識別子が格納されるメタデータ領域を有している。
【００１４】
本発明によれば、データベースに対する更新を効率的かつ高速に実行することができ、検索や集計などの処理をも高速に実行することができる。
【図面の簡単な説明】
【００１５】
上述した目的、およびその他の目的、特徴および利点は、以下に述べる好適な実施の形態、およびそれに付随する以下の図面によってさらに明らかになる。【００１６】
【図１】本発明に係る一実施形態のデータベースシステムの概略構成を示す機能ブロック図である。
【図２】データベースシステムのトランザクション処理部の処理手順を概略的に示すフローチャートである。
【図３】本発明の第１の実施形態に係るデータベースの論理構造の一例を示す概略図である。
【図４】実テーブルの一例を模式的に示す図である。
【図５】（Ａ）〜（Ｃ）は、データベースの論理データ構造を示す図である。
【図６】（Ａ）および（Ｂ）は、第１の実施形態に係るデータベースのうちの変換テーブルの第１変形例を概略的に示す図である。
【図７】（Ａ）および（Ｂ）は、第１の実施形態に係るデータベースのうちの変換テーブルの第２変形例を概略的に示す図である。
【図８】（Ａ）および（Ｂ）は、第１の実施形態に係るデータベースのうちの変換テーブルの第３変形例を概略的に示す図である。
【図９】（Ａ）および（Ｂ）は、第１の実施形態に係るデータベースのうちの変換テーブルの第４変形例を概略的に示す図である。
【図１０】本発明の第２の実施形態に係るデータベースの論理構造を示す概略図である。
【図１１】第２の実施形態のデータベースを構成する参照テーブルと中間識別子テーブルとを示す図である。
【図１２】第２の実施形態の変形例に係る参照テーブルと中間識別子テーブルとを示す図である。
【図１３】第２の実施形態の他の変形例に係る参照テーブルと中間識別子テーブルとを示す図である。
【発明を実施するための形態】
【００１７】
以下、本発明に係る実施の形態について図面を参照しつつ説明する。
【００１８】
（データベースシステム１０の基本構成）
図１は、本発明に係る一実施形態のデータベースシステム１０の概略構成を示す機能ブロック図である。このデータベースシステム１０は、トランザクション処理部２０、チェックポイント処理部３０、デフラグ処理部３１、トランザクションサーバ３２および記憶装置４０を有する。記憶装置４０には、データベース４１とログファイル４２とが格納されている。トランザクション処理部２０は、クエリ受信部２１、解析部２２、トランザクション実行部２３および応答処理部２４を含む。
【００１９】
ネットワークＮＷには、データベースシステム１０と、複数のクライアント端末５０１，５０２とが接続されている。ネットワークＮＷとしては、たとえば、一般的に使用されている小規模ネットワーク（たとえば、有線または無線ＬＡＮ）が挙げられるが、特に限定されるものではない。ネットワークＮＷがインターネットなどの大規模ネットワークであってもよい。
【００２０】
クライアント端末５０１，５０２は、それぞれ、データベース４１についてＳＱＬ（Structured Query Language）やＸＱｕｅｒｙ（XML Query Language：ＸＭＬ問い合わせ言語）などの問い合わせ言語（データベース言語）で記述されたクエリをデータベースシステム１０に宛てて送信する機能を有する。
【００２１】
データベースシステム１０のハードウェア構成は、汎用的な構成であればよく、たとえば、ＣＰＵ（Central Processing Unit）などのプロセッサ、主メモリ、キャッシュメモリ、信号伝達用バス、タイマ回路、入力装置（たとえば、キーボードやポインティングデバイス）および出力装置（たとえば、ディスプレイやプリンタ）などのハードウェア資源によって構成され得るが、特に限定されるものではない。
【００２２】
データベースシステム１０の構成の全部または一部は、ハードウェアで実現されてもよいし、あるいは、プロセッサに処理を実行させるコンピュータプログラム（またはプログラムコード）で実現されてもよい。データベースシステム１０の構成要素２１〜２４，３０，３１，３２の機能がコンピュータプログラムで実現される場合、プロセッサは、不揮発性メモリなどの記録媒体からそのコンピュータプログラムを読み出し実行する。また、データベースシステム１０の構成要素２１〜２４，３０，３１，３２，４０は、単一の装置に組み込まれてもよいし、あるいは、互いに連携動作する複数の装置に分散して組み込まれてもよい。
【００２３】
図２は、データベースシステム１０のトランザクション処理部２０の処理手順を概略的に示すフローチャートである。トランザクション処理部２０では、クエリ受信部２１がクライアント端末５０１，５０２から到来したクエリを受信し（ステップＳ１１）、当該受信されたクエリを解析部２２に与える。解析部２２は、クエリの解析（構文解析や最適化処理など）を実行し、その解析結果をトランザクション実行部２３に与える（ステップＳ１２）。トランザクション実行部２３は、当該解析結果に基づいたトランザクションをデータベース４１に対して実行する（ステップＳ１３）。ここで、トランザクションとは、データベース４１の検索や更新などの処理を含む１つの作業単位を意味し、原子性（ATOMICITY）、一貫性（CONSISTENCY）、隔離性（ISOLATION）および持続性（DURABILITY）というＡＣＩＤ特性を満たす処理である。トランザクション処理が正常に終了したとき（ステップＳ１４のＹＥＳ）、トランザクションはコミットされる（ステップＳ１５）。
【００２４】
トランザクション実行部２３は、トランザクションのログ情報（履歴情報）をログファイル４２として記憶装置４０に記録する。これと並行して、トランザクション実行部２３は、トランザクションのログのメタデータ（各トランザクションの開始または終了などの情報）をトランザクションサーバ３２に記録する。
【００２５】
チェックポイント処理部３０は、トランザクションサーバ３２に記録されたメタデータとログファイル４２とに基づいて定期的にチェックポイントを設定する。トランザクションやシステムに関する障害が発生してトランザクションが正常に終了しなかったとき（図２のステップＳ１４のＮＯ）、トランザクション実行部２３は、ロールフォワードを実行する（ステップＳ１６）。すなわち、チェックポイント処理部３０は、ログファイル４２を参照して、直前に設定されたチェックポイントの時点から障害発生時点までの期間Ｔｅｒｒのログ情報を確認し、この期間Ｔｅｒｒ中にコミットされていないトランザクションに関するログ情報をログファイル４２から削除する。次に、期間Ｔｅｒｒ中にコミットされたトランザクションが存在する場合、トランザクション実行部２３は、ログファイル４２に基づいて当該トランザクションの実行結果をデータベース４１に反映させる。その後、トランザクション実行部２３は、データベース４１を、コミットされていないトランザクションの処理開始前の状態に戻す、すなわち、ロールバックする（ステップＳ１７）。
【００２６】
そして、応答処理部２４は、トランザクション実行部２３からトランザクションの実行結果を受け取り、その実行結果をクライアント端末５０１，５０２に送信する（ステップＳ１８）。
【００２７】
データベース４１は、後述するように、可変長データを含む実体データ群と、実体データそのものを一意に表す固定長のデータ識別子が格納されている識別子テーブルとを含む。識別子テーブルに割り当てられている記憶領域とは異なる記憶領域が実体データ群に割り当てられており、識別子テーブルと実体データ群とは互いに完全に分離されている。
【００２８】
トランザクション実行部２３は、クエリの要求に応じて、実体データ群を検索せずに、識別子テーブル内の固定長のデータ識別子を検索する。トランザクション実行部２３は、この検索結果を用いて、データベース４１に対して更新などのトランザクションを実行する。
【００２９】
データベース４１の更新が繰り返し実行されると、記憶装置４０内のデータの記録や削除が繰り返し実行されるので、記憶装置４０内の連続的な記憶領域に記録されていたデータ群が断片化（フラグメンテーション化）し、これによりキャッシュヒット率が低下して処理速度が低下してしまう。デフラグ処理部３１は、データ群の断片化を解消する機能を有する。すなわち、デフラグ処理部３１は、複数のデータ識別子が記憶装置４０内の不連続な記憶領域に分散して記憶されているとき、これらデータ識別子を記憶装置４０から読み出し、識別子テーブル用の連続的な記憶領域に書き込む機能を有している。たとえば、データ識別子ＶＲ１１，ＶＲ１２，ＶＲ１３，...，ＶＲ１９が互いに離れた記憶領域に記憶されているとき、デフラグ処理部３１は、これらデータ識別子ＶＲ１１，ＶＲ１２，ＶＲ１３，...，ＶＲ１９を連続した記憶領域に書き込むことができる。
【００３０】
次に、本発明の種々の実施形態に係るデータベース４１の構造について説明する。
【００３１】
（第１の実施形態）
図３は、本発明の第１の実施形態に係るデータベース４１の論理構造の一例を示す概略図である。図３に示されるように、このデータベース構造は、記憶装置４０内の記憶領域ＤＡ０に格納されている実体データ群と、記憶装置４０において記憶領域ＤＡ０とは異なる記憶領域に格納されている参照テーブル（識別子テーブル）ＲＴ０とを有する。
【００３２】
参照テーブルＲＴ０は、行方向に定義された５つのタプルと、列方向に定義された５つの属性フィールドＴＩＤ，Ｖａｌ１，Ｖａｌ２，Ｖａｌ３，Ｖａｌ４とを有している。第１の実施形態では、説明の便宜上、参照テーブルＲＴ０のタプルの数は５つであるが、これに限定されず、タプルの数を、たとえば、数十〜数百万に設定することができる。属性フィールドの数も５つに限定されるものではない。
【００３３】
参照テーブルＲＴ０の５つのタプルには、それぞれ、一意のタプル識別子（ＴＩＤ）Ｒ１，Ｒ２，Ｒ３，Ｒ４，Ｒ５が割り当てられている。これらタプルと属性フィールドＶａｌ１，Ｖａｌ２，Ｖａｌ３，Ｖａｌ４とで定まる領域（タプルと属性フィールドＶａｌ１，Ｖａｌ２，Ｖａｌ３，Ｖａｌ４とが交差する領域）にそれぞれ固定長のデータ識別子ＶＲ１１，ＶＲ１２，...，ＶＲ４３が格納されている。すなわち、属性フィールドＶａｌ１は、タプル識別子Ｒ１，Ｒ２，Ｒ３，Ｒ４，Ｒ５に対応する領域にそれぞれデータ識別子ＶＲ１１，ＶＲ１２，ＶＲ１３，ＶＲ１４，ＶＲ１５を含み、属性フィールドＶａｌ２は、タプル識別子Ｒ１，Ｒ２，Ｒ３，Ｒ４，Ｒ５に対応する領域にそれぞれデータ識別子ＶＲ２１，ＶＲ２２，ＶＲ２３，ＶＲ２３，ＶＲ２４を含み、属性フィールドＶａｌ３は、タプル識別子Ｒ１，Ｒ２，Ｒ３，Ｒ４，Ｒ５に対応する領域にそれぞれデータ識別子ＶＲ３１，ＶＲ３２，ＶＲ３３，ＶＲ３４，ＶＲ３５を含み、属性フィールドＶａｌ４は、タプル識別子Ｒ１，Ｒ２，Ｒ３，Ｒ４，Ｒ５に対応する領域にそれぞれデータ識別子ＶＲ４１，ＶＲ４１，ＶＲ４１，ＶＲ４２，ＶＲ４３を含む。
【００３４】
データ識別子ＶＲ１１〜ＶＲ４３の値は、ハッシュ関数を用いて算出することができる。ここで、ハッシュ関数は、可変長ビット列の入力に対して固定長のビット列を出力する論理演算子である。実体データの入力に対するハッシュ関数の出力値（ハッシュ値）をそれぞれデータ識別子ＶＲ１１〜ＶＲ４３の値とすることができる。データ識別子の一意性を確保する観点からは、ハッシュ関数の対衝突性（異なる２つの入力値から同一のハッシュ値が生成されることが困難という性質）は、データベース４１の規模に応じて十分に高いことが望ましい。トランザクション実行部２３は、検索文字列をハッシュ値に変換し、このハッシュ値と一致する値を持つデータ識別子を参照テーブルＲＴ０から探し出し、探し出されたデータ識別子に対応する実体データを記憶領域ＤＡ０から探し出すことができる。このとき、トランザクション実行部２３は、可変長データを含まない固定長データ群のみからなる参照テーブルＲＴ０を検索するので、文字列を高速に探し出すことができる。
【００３５】
上記データ識別子ＶＲ１１〜ＶＲ４３は、記憶領域ＤＡ０内の実体データをそれぞれ実質的に一意に表す値を有する。このため、トランザクション実行部２３は、データ識別子ＶＲ１１〜ＶＲ４３を検索し、その検索結果に基づいてこれらデータ識別子ＶＲ１１〜ＶＲ４３に対応する可変長の実体データにアクセスすることが可能である。なお、本明細書において「実質的に一意」とは、データベース４１に対するデータ処理上の一意性を満たしていることを意味する。
【００３６】
属性フィールドＶａｌ１、Ｖａｌ２、Ｖａｌ３，Ｖａｌ４の名称（属性名）としては、たとえば、「店名」、「地域」、「売上」、「年月」を設定できる。図３に示すデータベース構造は、図４に例示されるような実体データの集合（実テーブル）ＳＴに基づいて生成することができる。図４の実テーブルＳＴは、「店名」、「地域」、「売上」、「年月」という４つの属性フィールドを有する５行４列のテーブルである。この実テーブルＳＴの「Ａ店」、「Ｂ店」、「九州」などの実体データをハッシュ化（実体データの値をハッシュ値に変換）し、実体データを記憶領域ＤＡ０に格納することで、図３に示した固定長のデータ識別子ＶＲ１１，ＶＲ１２，...，ＶＲ４３を生成することができる。なお、本実施形態のデータベースを既存の実テーブルに基づいて生成することができるが、これに限らず、実テーブルを生成せずに入力データから、直接、本実施形態の図３のデータベース構造を生成してもよい。
【００３７】
図５（Ａ）〜図５（Ｃ）は、データベース４１を構成する論理データ構造を示す図である。図５（Ａ）に示されるデータ構造は、先頭部分にヘッダ領域を有し、末尾部分にアロケーション管理テーブルを有している。また、ヘッダ領域とアロケーション管理テーブルとの間に実体データ群が格納される領域が設けられている。
【００３８】
図５（Ｂ）は、ヘッダ領域に含まれる変換テーブルの一例を示す概略図である。この変換テーブルは、データ識別子ＶＲ１１〜ＶＲ４３と、これらデータ識別子ＶＲ１１〜ＶＲ４３それぞれに対応する実体データＤ１１〜Ｄ４３の記憶領域との間の対応関係を規定するテーブルである。この変換テーブルにおいては、図５（Ｂ）に示されるように、データ識別子ＶＲ１１〜ＶＲ４３が格納される領域Ｆｉｄと、これらデータ識別子ＶＲ１１〜ＶＲ４３それぞれに対応する実体データＤ１１〜Ｄ４３の記憶領域の位置を示す位置データＡ１１〜Ａ４３が格納される領域Ｆａとが設けられている。更に、位置データＡＩ１１〜ＡＩ４３が格納される領域Ｆａｉが設けられている。位置データＡＩ１１〜ＡＩ４３は、識別子テーブルＲＴ０においてデータ識別子ＶＲ１１〜ＶＲ４３が格納されているタプルを一意に表すタプル識別子の記憶領域の位置を示すデータである。図５（Ｃ）は、データ識別子ＶＲ１１に対応するタプル識別子Ｒ２，Ｒ１００，...，０が格納されているメタデータ領域Ｆｉｄｘを示す図である。メタデータ領域Ｆｉｄｘは、記憶領域ＤＡ０とは異なる記憶領域に割り当てられている。
【００３９】
ここで、位置データＡＩ１１〜ＡＩ４３は、タプル識別子の当該記憶領域の絶対的位置を指定するアドレス、もしくは、所定アドレスを基準として当該記憶領域の相対的位置（実効アドレス）を指定するオフセットであればよい。あるいは、当該記憶領域に割り当てられたアドレスを指すポインタを位置データＡＩ１１〜ＡＩ４３として使用することもできる。
【００４０】
図５（Ｂ）の変換テーブルでは、同一値を有するデータ識別子の重複が排除されている（すなわち、変換テーブル内にある任意の２つのデータ識別子の値は必ず異なる）ので、この変換テーブルを使用することにより、同一値を有する実体データを重複させずに記憶領域ＤＡ０に記憶させることができる。言い換えれば、データベース４１を構成する実体データ群を圧縮して記憶領域ＤＡ０に記憶させることができるので、記憶領域ＤＡ０の効率的な利用が可能となる。後述する第１〜第４変形例の変換テーブルについても同様である。
【００４１】
メタデータ領域Ｆｉｄｘに格納されたタプル識別子は、識別子テーブルＲＴ０に対するインデックス情報として利用される。トランザクション実行部２３は、図５（Ａ）のヘッダ領域を参照することによりデータ識別子に対応する実体データにアクセスできるだけでなく、メタデータ領域Ｆｉｄｘを参照することにより、実体データに関連付けられたタプル識別子の全てを取得することができる。言い換えれば、データ識別子から、識別子テーブルＲＴ０において当該データ識別子が格納されているタプルの集合を特定することが可能である。たとえば、図３に示されるように、データ識別子ＶＲ４１が格納されているタプルには、複数のタプル識別子Ｒ１〜Ｒ３が割り当てられている。図５（Ｂ）の変換テーブルを使用することで、データ識別子ＶＲ４１からタプル識別子Ｒ１〜Ｒ３を一括して特定することが可能である。
【００４２】
本実施形態のデータベースシステム１０が奏する効果は以下の通りである。
【００４３】
実体データＤ１１〜Ｄ４３の記憶領域ＤＡ０と、これら実体データＤ１１〜Ｄ４３をそれぞれ一意に表すデータ識別子ＶＲ１１〜ＶＲ４３の記憶領域とは互いに完全に分離されているので、データベース４１の更新処理の高効率化、検索や集計の処理速度の向上、並びに移植性の向上を実現することができる。
【００４４】
具体的には、データベース４１が更新、追加または削除されるとき、更新処理を効率的に行うことができる。たとえば、記憶領域ＤＡ０内の可変長の実体データＤ４１の値を別の値に更新する場合、この更新に合わせて、図３の識別子テーブルＲＴ０内および図５（Ｂ）の変換テーブル内の全てのデータ識別子ＶＲ４１の値を新たな値に更新すればよい。また、新たなタプルを識別子テーブルＲＴ０に追加する場合であって、この新たなタプルに既存のデータ識別子（たとえば、データ識別子ＶＲ１１〜ＶＲ１４）しか格納されない場合は、図５（Ｂ）の変換テーブルを更新する必要はない。さらに、識別子テーブルＲＴ０からタプルの一部（たとえば、タプル識別子Ｒ１のタプル）を削除する場合に、必ずしも、図５（Ｂ）の変換テーブルを更新する必要はない。このように実体データの更新、追加または削除に伴い、データベース４１は必要最小限に更新されるので、データベース４１に対する更新が頻繁に行われる場合でも、かかる更新を効率的かつ高速に実行することが可能である。
【００４５】
また、本実施形態のデータベースシステム１０は、図５（Ａ）〜図５（Ｃ）に示したデータ構造を使用して、データ識別子に関連付けられているタプル識別子の集合（メタデータ領域Ｆｉｄｘに格納されているタプル識別子の集合）を一括して取得することができるので、識別子テーブルＲＴ０において共通のデータ識別子を格納するタプル集合に高速にアクセスすることができる。よって、検索や集計やタプルの更新などの処理速度の向上が可能である。
【００４６】
実体データＤ１１〜Ｄ４３の記憶領域ＤＡ０とデータ識別子ＶＲ１１〜ＶＲ４３の記憶領域とは互いに完全に分離されているので、参照テーブルＲＴ０と実体データ群とを分散配置することが容易である。たとえば、ＬＡＮなどのコンピュータネットワークを介して接続された２つのコンピュータシステムにそれぞれ参照テーブルＲＴ０と実体データ群とを分散配置することができる。
【００４７】
さらに、実体データＤ１１〜Ｄ４３の記憶領域ＤＡ０とデータ識別子ＶＲ１１〜ＶＲ４３の記憶領域とは互いに完全に分離されているので、データベース構造のハードウェア構成への依存性は低く、データベース構造を他のシステムへ容易に移植することができる。
【００４８】
（第１の実施形態の第１変形例）
図６（Ａ）は、記憶領域ＤＡ０の模式図であり、図６（Ｂ）は、第１の実施形態に係るデータベース４１のうち記憶領域ＤＡ０内の変換テーブルの第１変形例を概略的に示す図である。
【００４９】
図６（Ｂ）の変換テーブルには、図５（Ｂ）の変換テーブルと同様に、データ識別子ＶＲ１１〜ＶＲ４３が格納される領域Ｆｉｄと、位置データＡ１１〜Ａ４３が格納される領域Ｆａとが設けられている。位置データＡ１１〜Ａ４３は、データ識別子ＶＲ１１〜ＶＲ４３それぞれに対応する実体データＤ１１〜Ｄ４３の記憶領域を示すデータである。
【００５０】
図６（Ｂ）の変換テーブルには、更に、データ識別子ＶＲ１１〜ＶＲ４３の各々に対して、データ識別子ＶＲ１１〜ＶＲ４３にそれぞれ対応するタプル識別子の集合が格納されるメタデータ領域Ｆｉｄｘと、各領域Ｆｉｄｘに格納されているデータの個数（フラグ情報）が格納されているフラグ領域Ｆｎとが設けられている。
【００５１】
第１変形例では、各メタデータ領域Ｆｉｄｘは固定長であり、各メタデータ領域Ｆｉｄｘには、最大２５６個のタプル識別子を格納することができる。或るデータ識別子に関連付けられたタプル識別子の個数が最大個数（２５６個）を超えた場合、言い換えれば、当該データ識別子に関連付けられたタプル識別子の全体のデータ量がそのメタデータ領域Ｆｉｄｘの固定長サイズを超えた場合には、当該メタデータ領域Ｆｉｄｘには、５００個以上のタプル識別子が格納されている記憶領域（オーバフロー領域）の位置を示す位置データが格納される。たとえば、図６（Ｂ）の変換テーブルでは、データ識別子ＶＲ１４に対応するメタデータ領域Ｆｉｄｘには、タプル識別子が格納されているオーバフロー領域の位置を示す位置データＡＩ１４が格納される。位置データＡＩ１４としては、タプル識別子の当該記憶領域の絶対的位置を指定するアドレス、当該記憶領域の相対的位置（実効アドレス）を指定するオフセット、あるいは、当該記憶領域に割り当てられたアドレスを指すポインタを使用すればよい。
【００５２】
図６（Ｂ）に示す変換テーブルを使用することで、各データ識別子に関連付けられたタプル識別子の個数に関係なく、領域Ｆｉｄ、領域Ｆａ、フラグ領域Ｆｎおよびメタデータ領域Ｆｉｄｘの全体の長さを固定長にすることができるので、所定個数以下のタプル識別子を高速に参照することができる。これにより、図３の識別子テーブルＲＴ０において共通のデータ識別子を格納するタプル集合へのアクセス速度の向上が可能となる。
【００５３】
なお、本実施形態では、或るデータ識別子に関連付けられたタプル識別子の個数が最大個数（２５６個）を超えた場合、当該タプル識別子の全てがオーバフロー領域に格納されるが、これに限定されるものではない。かかる場合に当該タプル識別子の一部をオーバフロー領域に格納してもよく、残るタプル識別子をメタデータ領域Ｆｉｄｘに格納してもよい。
【００５４】
また、データ識別子に関連付けられたタプル識別子の個数が最大個数（２５６個）を超えた場合に、フラグ領域Ｆｎには、その個数を表す多ビット値の代わりに、タプル識別子の個数が最大個数を超えたことを示す１ビット値がフラグ情報として格納されてもよい。
【００５５】
（第１の実施形態の第２変形例）
図７（Ａ）は、記憶領域ＤＡ０の模式図であり、図７（Ｂ）は、第１の実施形態に係るデータベース４１のうち記憶領域ＤＡ０内の変換テーブルの第２変形例を概略的に示す図である。
【００５６】
図７（Ｂ）の変換テーブルには、図５（Ｂ）の変換テーブルと同様に、データ識別子ＶＲ１１〜ＶＲ４３が格納される領域Ｆｉｄと、これらデータ識別子ＶＲ１１〜ＶＲ４３それぞれに対応する実体データＤ１１〜Ｄ４３の記憶領域の位置を示す位置データＡ１１〜Ａ４３が格納される領域Ｆａとが設けられている。
【００５７】
図７（Ｂ）の変換テーブルには、更に、データ識別子ＶＲ１１〜ＶＲ４３にそれぞれ対応するタプル識別子の集合が格納される固定長のメタデータ領域Ｆｉｄｘと、フラグ領域Ｆｐとが設けられている。フラグ領域Ｆｐには、各メタデータ領域Ｆｉｄｘに格納されているデータの個数がメタデータ領域Ｆｉｄｘの固定長サイズを超えたか否かを示す値（フラグ情報）が格納されている。
【００５８】
第２変形例では、各メタデータ領域Ｆｉｄｘには、たとえば、最大２５６個のタプル識別子を格納することができる。或るデータ識別子に関連付けられたタプル識別子の個数が最大個数（２５６個）以下の場合、フラグ領域ＦｐにはＮＵＬＬ値が格納される。また、メタデータ領域Ｆｉｄｘに最大個数（２５６個）未満のｍ個のタプル識別子が格納される場合、このメタデータ領域Ｆｉｄｘには、これらｍ個のタプル識別子と、（２５６−ｍ）個の特殊値（たとえば、ゼロの値）とが格納される。たとえば、図７（Ｂ）の変換テーブルを参照すると、データ識別子ＶＲ１３に対応するメタデータ領域Ｆｉｄｘには、３個のタプル識別子Ｒ３，Ｒ１５，Ｒ２５が格納されるとともに、２５３（＝２５６−３）個のゼロ値（＝０）が格納されている。
【００５９】
一方、データ識別子に関連付けられたタプル識別子の個数が最大個数（２５６個）を超えた場合、言い換えれば、当該データ識別子に関連付けられたタプル識別子の全体のデータ量がそのメタデータ領域Ｆｉｄｘの固定長サイズを超えた場合には、フラグ領域Ｆｐには、タプル識別子が格納されている記憶領域（オーバフロー領域）の位置を示す位置データが格納される。たとえば、図７（Ｂ）の変換テーブルでは、データ識別子ＶＲ１４に対応するフラグ領域Ｆｐには、タプル識別子が格納されているオーバフロー領域の位置を示す位置データＡＩ１４が格納されている。また、このデータ識別子ＶＲ１４に対応するメタデータ領域Ｆｉｄｘには、２５６個のゼロ値（＝０）が格納されている。位置データＡＩ１４としては、タプル識別子の当該記憶領域の絶対的位置を指定するアドレス、当該記憶領域の相対的位置（実効アドレス）を指定するオフセット、あるいは、当該記憶領域に割り当てられたアドレスを指すポインタを使用すればよい。
【００６０】
図７（Ｂ）に示す変換テーブルを使用することで、各データ識別子に関連付けられたタプル識別子の個数に関係なく、領域Ｆｉｄ、領域Ｆａ、フラグ領域Ｆｐおよびメタデータ領域Ｆｉｄｘの全体の長さを固定長にすることができるので、所定個数以下のタプル識別子を高速に参照することができる。これにより、図３の識別子テーブルＲＴ０において共通のデータ識別子を格納するタプル集合へのアクセス速度の向上が可能となる。
【００６１】
（第１の実施形態の第３変形例）
図８（Ａ）は、記憶領域ＤＡ０の模式図であり、図８（Ｂ）は、第１の実施形態に係るデータベース４１のうち記憶領域ＤＡ０内の変換テーブルの第３変形例を概略的に示す図である。
【００６２】
図８（Ｂ）の変換テーブルには、図５（Ｂ）の変換テーブルと同様に、データ識別子ＶＲ１１〜ＶＲ４３が格納される領域Ｆｉｄと、これらデータ識別子ＶＲ１１〜ＶＲ４３それぞれに対応する実体データＤ１１〜Ｄ４３の記憶領域の位置を示す位置データＡ１１〜Ａ４３が格納される領域Ｆａとが設けられている。更に、データ識別子ＶＲ１１〜ＶＲ４３にそれぞれ対応するタプル識別子の集合が格納される固定長のメタデータ領域Ｆｉｄｘが設けられている。
【００６３】
第３変形例では、各メタデータ領域Ｆｉｄｘには、たとえば、最大２５６個のタプル識別子を格納することができる。データ識別子に関連付けられたタプル識別子の個数が最大個数（２５６個）を超えた場合、言い換えれば、当該データ識別子に関連付けられたタプル識別子の全体のデータ量がそのメタデータ領域Ｆｉｄｘの固定長サイズを超えた場合には、当該メタデータ領域Ｆｉｄｘには、特殊値（たとえば「−１」の値）と、タプル識別子が格納されている記憶領域（オーバフロー領域）の位置を示す位置データとが格納される。
【００６４】
たとえば、図８（Ｂ）の変換テーブルでは、データ識別子ＶＲ１４に対応するメタデータ領域Ｆｉｄｘには、「−１」の値と、オーバフロー領域の位置を示す位置データＡＩ１４とが格納されている。位置データＡＩ１４としては、タプル識別子の当該記憶領域の絶対的位置を指定するアドレス、当該記憶領域の相対的位置（実効アドレス）を指定するオフセット、あるいは、当該記憶領域に割り当てられたアドレスを指すポインタを使用すればよい。
【００６５】
図８（Ｂ）に示す変換テーブルを使用することで、各データ識別子に関連付けられたタプル識別子の個数に関係なく、領域Ｆｉｄ、領域Ｆａおよびメタデータ領域Ｆｉｄｘの全体の長さを固定長にすることができるので、所定個数未満のタプル識別子を高速に参照することができる。これにより、図３の識別子テーブルＲＴ０において共通のデータ識別子を格納するタプル集合へのアクセス速度の向上が可能となる。また、第２変形例の図７のデータ構造と比べると、第３変形例のデータ構造は、フラグ領域Ｆｐを持たないので、シンプルな構造を実現することが可能である。
【００６６】
データ識別子に関連付けられたタプル識別子の個数が最大個数（２５６個）を超えた場合に、当該メタデータ領域Ｆｉｄｘに「−１」の値と位置データの両方を格納する代わりに、「−１」の値を格納してもよい。この場合、当該データ識別子に対応するように予め設けられたオーバフロー領域に当該タプル識別子を格納すればよい。
【００６７】
（第１の実施形態の第４変形例）
図９（Ａ）および図９（Ｂ）は、第１の実施形態の第４変形例の論理データ構造を概略的に示す図である。第４変形例では、記憶領域ＤＡ０には、上記第１〜第３変形例のような変換テーブルは設けられていない。図９（Ａ）に示されるように、本変形例では、記憶領域ＤＡ０には、参照テーブルＲＴ０のデータ識別子ＶＲ１１〜ＶＲ４３にそれぞれ対応するデータブロックＤＢ１１〜ＤＢ４３が格納されている。各データブロックは、データ識別子とこれに対応する実体データ値とを含むとともに、インデックス情報としてのタプル識別子の集合を含む。
【００６８】
図９（Ｂ）は、データブロックＤＢ２２のデータ構造を概略的に示す図である。図９（Ｂ）に示されているように、データブロックＤＢ２２は、データ識別子ＶＲ２２が格納される領域Ｆｉｄと、実体データＤ２２が格納される可変長領域Ｆｄと、データ識別子ＶＲ２２に関連付けされているタプル識別子群Ｉ２２が格納される可変長領域（メタデータ領域）Ｆｘｉｄとを有する。また、データブロックＤＢ２２において、領域Ｆｄｓは、実体データＤ２２の長さＤＬ２２が格納される領域であり、領域Ｆｉｘｓは、メタデータ領域Ｆｘｉｄの長さＩＬ２２が格納される領域である。
【００６９】
本変形例によれば、トランザクション実行部２３は、データブロックＤＢ１１〜ＤＢ４３の各々の末尾部分のメタデータ領域Ｆｘｉｄ内を参照して、実体データ（データ識別子）に関連付けられているタプル識別子を参照することができる。したがって、本実施形態のデータベースシステム１０は、データ識別子に関連付けられているタプル識別子の集合を一括して取得することができるので、識別子テーブルＲＴ０において共通のデータ識別子を格納するタプル集合に高速にアクセスすることができる。よって、検索や集計やタプルの更新などの処理速度の向上が可能である。
【００７０】
（第２の実施形態）
図１０は、本発明の第２の実施形態に係るデータベース４１を示す概略図である。図１０に示されるように、このデータベース構造は、記憶装置４０の記憶領域ＤＡ３に格納された実体データ群と、記憶領域ＤＡ３とは別の記憶領域に格納された参照テーブルＲＴ１および第１〜第３の中間識別子テーブルＩＴ４１，ＩＴ４２，ＩＴ４３とを有する。
【００７１】
図１１（Ａ）は、参照テーブルＲＴ１の概略構成を示す図である。参照テーブルＲＴ１は、行方向に定義された複数のタプルと、列方向に定義された４つの属性フィールドＴＩＤ，Ｃｏｌ１Ｒｅｆ，Ｃｏｌ２Ｒｅｆ，Ｃｏｌ３Ｒｅｆとを有している。参照テーブルＲＴ１のタプルの数については、たとえば、これを数十〜数百万に設定することができる。属性フィールドの数も４つに限定されるものではない。
【００７２】
参照テーブルＲＴ１のタプルには、それぞれ、一意のタプル識別子（ＴＩＤ）Ｒ１，Ｒ２，Ｒ３，Ｒ４，...が割り当てられている。これらタプルと属性フィールドＣｏｌ１Ｒｅｆ，Ｃｏｌ２Ｒｅｆ，Ｃｏｌ３Ｒｅｆとで定まる領域（タプルと属性フィールドＣｏｌ１Ｒｅｆ，Ｃｏｌ２Ｒｅｆ，Ｃｏｌ３Ｒｅｆとが交差する領域）にそれぞれ固定長の参照識別子ＣＲＶ１１，ＣＲＶ１２，...，ＣＲＶ３１，...が格納されている。参照識別子ＣＲＶ１１〜ＣＲＶ３１の値は、上記第１の実施形態のデータ識別子の場合と同様のハッシュ関数を用いて算出することができる。すなわち、データ識別子ＶＲ１１〜ＶＲ３１の入力に対するハッシュ関数の出力値をそれぞれ参照識別子ＣＲＶ１１〜ＣＲＶ３１の値とすればよい。
【００７３】
図１１（Ｂ）〜図１１（Ｄ）は、第１〜第３の中間識別子テーブルＩＴ４１，ＩＴ４２，ＩＴ４３の構造を概略的に示す図である。第１の中間識別子テーブルＩＴ４１は、行方向に定義された複数のタプルと、列方向に定義された４つの属性フィールドＣｏｌ１，Ｖａｌ，ｎｕｍ，Ｉｎｄｅｘとを有する。属性フィールドＣｏｌ１は、固定長の参照識別子ＣＲＶ１１，ＣＲＶ１２，...を含み、属性フィールドＶａｌは、タプルにそれぞれ対応する領域にそれぞれ固定長のデータ識別子ＶＲ１１，ＶＲ１２，...を含む。属性フィールドＩｎｄｅｘは、タプルにそれぞれ対応する領域に、インデックス情報としてのタプル識別子を含み、属性フィールドｎｕｍは、属性フィールドＩｎｄｅｘ内に含まれるタプル識別子の個数を含む。
【００７４】
第２の中間識別子テーブルＩＴ４２は、行方向に定義された複数のタプルと、列方向に定義された４つの属性フィールドＣｏｌ２，Ｖａｌ，ｎｕｍ，Ｉｎｄｅｘとを有する。属性フィールドＣｏｌ２は、固定長の参照識別子ＣＲＶ２１，ＣＲＶ２２，...を含み、属性フィールドＶａｌは、タプルにそれぞれ対応する領域にそれぞれ固定長のデータ識別子ＶＲ２１，ＶＲ２２，...を含む。属性フィールドＩｎｄｅｘは、タプルにそれぞれ対応する領域に、インデックス情報としてのタプル識別子を含み、属性フィールドｎｕｍは、属性フィールドＩｎｄｅｘ内に含まれるタプル識別子の個数を含む。
【００７５】
そして、第３の中間識別子テーブルＩＴ４３は、行方向に定義された複数のタプルと、列方向に定義された４つの属性フィールドＣｏｌ３，Ｖａｌ，ｎｕｍ，Ｉｎｄｅｘとを有する。属性フィールドＣｏｌ３は、固定長の参照識別子ＣＲＶ３１，ＣＲＶ３２，...を含み、属性フィールドＶａｌは、タプルにそれぞれ対応する領域にそれぞれ固定長のデータ識別子ＶＲ３１，ＶＲ３２，...を含む。属性フィールドＩｎｄｅｘは、タプルにそれぞれ対応する領域に、インデックス情報としてのタプル識別子を含み、属性フィールドｎｕｍは、属性フィールドＩｎｄｅｘ内に含まれるタプル識別子の個数を含む。
【００７６】
第１〜第３の中間識別子テーブルＩＴ４１，ＩＴ４２，ＩＴ４３の各々は、互いに重複した値を持つ参照識別子を排除しているので、冗長性を排除したデータ構造を有する。また、第１〜第３の中間識別子テーブルＩＴ４１〜ＩＴ４３においては、それぞれ、上記第２の実施形態の図６（Ｂ）の変換テーブルの領域Ｆｎとメタデータ領域Ｆｉｄｘとに相当する属性フィールドｎｕｍ，Ｉｎｄｅｘを有している。
【００７７】
トランザクション実行部２３は、参照識別子ＣＲＶ１１〜ＣＲＶ３３およびデータ識別子ＶＲ１１〜ＶＲ３３を検索し、この検索結果を用いて可変長の実体データにアクセスすることができる。記憶領域ＤＡ３は、上記第１の実施形態あるいはその変形例の変換テーブルと同様の変換テーブルを有しているので、トランザクション実行部２３は、当該検索結果に基づいて実体データにアクセスすることができる。
【００７８】
また、本実施形態では、第１〜第３の中間識別子テーブルＩＴ４１〜ＩＴ４３の属性フィールドｎｕｍ，Ｉｎｄｅｘを使用することにより、参照識別子ＣＲＶ１１〜ＣＲＶ３３の各々に関連付けられているタプル識別子の集合を一括して取得することができるので、参照テーブルＲＴ１において共通の参照識別子を格納するタプル集合に高速にアクセスすることができる。よって、検索や集計やタプルの更新などの処理速度の向上が可能である。
【００７９】
（第２の実施形態の変形例）
図１２（Ａ）〜図１２（Ｄ）は、第２の実施形態の変形例の論理データ構造を概略的に示す図である。図１２（Ａ）は、図１１（Ａ）と同じ参照テーブルＲＴ１の概略構成を示す図である。また、図１２（Ｂ）〜図１２（Ｄ）は、この変形例の中間識別子テーブルＩＴ４１，ＩＴ４２，ＩＴ４３のデータ構造を概略的に示す図である。本変形例の第１〜第３の中間識別子テーブルＩＴ４１〜ＩＴ４３においては、それぞれ、上記第１の実施形態の第２変形例に係る変換テーブル（図７（Ｂ））の領域Ｆｐとメタデータ領域Ｆｉｄｘとに相当する属性フィールドＯｖｅｒ，Ｉｎｄｅｘを有している。
【００８０】
また、図１３（Ａ）〜図１３（Ｄ）は、第２の実施形態の他の変形例の論理データ構造を概略的に示す図である。図１３（Ａ）は、図１１（Ａ）と同じ参照テーブルＲＴ１の概略構成を示す図である。また、図１３（Ｂ）〜図１３（Ｄ）は、当該他の変形例の中間識別子テーブルＩＴ４１，ＩＴ４２，ＩＴ４３のデータ構造を概略的に示す図である。本変形例の第１〜第３の中間識別子テーブルＩＴ４１〜ＩＴ４３においては、それぞれ、上記第１の実施形態の第３変形例に係る変換テーブル（図８（Ｂ））のメタデータ領域Ｆｉｄｘに相当する属性フィールドＩｎｄｅｘを有している。
【００８１】
したがって、これら変形例においても、参照識別子ＣＲＶ１１〜ＣＲＶ３３の各々に関連付けられているタプル識別子の集合を一括して取得することができるので、参照テーブルＲＴ１において共通の参照識別子を格納するタプル集合に高速にアクセスすることができる。したがって、検索や集計やタプルの更新などの処理速度の向上が可能である。
【００８２】
以上、図面を参照して本発明の実施形態について述べたが、これらは本発明の例示であり、上記以外の様々な構成を採用することもできる。たとえば、上記実施形態は、データベース４１に対してトランザクションを実行するために適した処理を実行するが、これに限定されるものではない。上述の通り、トランザクションは、ＡＣＩＤ特性を満たす処理であるが、本発明に係るデータベース構造は、これらＡＣＩＤ特性のうちのいずれかの特性を満たさないデータ処理にも適用することが可能である。
【００８３】
上記実施形態では、クエリ受信部２１は問い合わせ言語で記述されたクエリを受信し、解析部２２はそのクエリを解析するが、これに限定されるものではない。たとえば、クエリが、問い合わせ言語（データベース言語）で記述されておらず、単に、データベース用のＡＰＩ（Application Programming Interface）関数を呼び出すための値を含むものであってもよい。
【００８４】
この出願は、日本国特許庁に出願された特願２００９−１４１４２号（出願日：２００９年１月２６日）を基礎とする優先権を主張するものであり、その開示の全ては、本明細書の一部として援用（incorporation herein by reference）される。
【図１】
2010084754.tif 000003
【図２】
2010084754.tif 000004
【図３】
2010084754.tif 000005
【図４】
2010084754.tif 000006
【図５】
2010084754.tif 000007
【図６】
2010084754.tif 000008
【図７】
2010084754.tif 000009
【図８】
2010084754.tif 000010
【図９】
2010084754.tif 000011
【図１０】
2010084754.tif 000012
【図１１】
2010084754.tif 000013
【図１２】
2010084754.tif 000014
【図１３】
2010084754.tif 000015
【手続補正書】
【提出日】平成23年7月20日(2011.7.20)
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
上記に鑑みて本発明の目的は、データベースに対するデータ更新の効率的かつ高速な実行を可能にするとともに検索や集計の処理速度の向上をも実現し得るデータベースシステム、データベース管理方法、及びデータベース構造を提供することである。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
本発明によれば、複数の実体データを含むデータベースについてクエリを受信する処理と、前記データベースに対して当該受信されたクエリに基づいて実行されるデータ処理と、を含むデータベース管理処理をコンピュータに実行させるコンピュータプログラム及びこのコンピュータプログラムを格納する、当該コンピュータによって読み取り可能な記録媒体が提供される。前記データベースは、行方向に定義された少なくとも１つのタプルと列方向に定義された少なくとも１つの属性フィールドとで定まる領域に前記実体データそのものを一意に表す固定長のデータ識別子が格納されている識別子テーブルと、前記複数の実体データそれぞれの記憶領域の位置を示す位置データと前記複数のデータ識別子との間の対応関係を表す変換テーブルと、を含んでいる。さらに、前記変換テーブルは、前記識別子テーブルにおいて前記各データ識別子が格納されている当該タプルを一意に表すタプル識別子が格納されるメタデータ領域を有している。
【手続補正４】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の実体データを含むデータベースを有するデータ記憶部と、
クエリを受信し、当該受信されたクエリに基づいたデータ処理を前記データベースに対して実行するデータ処理部と、
を備え、
前記データベースは、
行方向に定義された少なくとも１つのタプルと列方向に定義された少なくとも１つの属性フィールドとで定まる領域に前記実体データそのものを一意に表す固定長のデータ識別子が格納されている識別子テーブルと、
前記複数の実体データそれぞれの記憶領域の位置を示す位置データと前記複数のデータ識別子との間の対応関係を表す変換テーブルと、
を含み、
前記変換テーブルは、前記識別子テーブルにおいて前記各データ識別子が格納されている当該タプルを一意に表すタプル識別子が格納されるメタデータ領域を有する、データベースシステム。
【請求項２】
請求項１記載のデータベースシステムであって、前記識別子テーブルに割り当てられた記憶領域と前記実体データに割り当てられた記憶領域とが互いに異なる、データベースシステム。
【請求項３】
請求項１または２記載のデータベースシステムであって、前記データ識別子の値は、前記実体データの入力に対して固定長のビット列を出力するハッシュ関数の出力値である、データベースシステム。
【請求項４】
請求項１から３のうちのいずれか１項に記載のデータベースシステムであって、前記メタデータ領域のサイズは固定長である、データベースシステム。
【請求項５】
請求項４に記載のデータベースシステムであって、前記変換テーブルは、前記各データ識別子に対して、前記タプル識別子のデータ量が前記メタデータ領域の固定長サイズを超えたか否かを示すフラグ情報が格納されるフラグ領域を有する、データベースシステム。
【請求項６】
請求項４または５に記載のデータベースシステムであって、
前記データベースは、前記タプル識別子のデータ量が前記固定長サイズを超えるときに当該タプル識別子の全部または一部が格納されるオーバフロー領域を更に有し、
前記データ処理部は、前記タプル識別子のデータ量が前記固定長サイズを超えるときに、当該タプル識別子の全部または一部を前記オーバフロー領域に格納する、データベースシステム。
【請求項７】
請求項６に記載のデータベースシステムであって、前記データ処理部は、前記オーバフロー領域に前記タプル識別子を格納するとき、当該タプル識別子の記憶領域の位置を示す位置データを前記メタデータ領域に格納する、データベースシステム。
【請求項８】
請求項７に記載のデータベースシステムであって、前記タプル識別子の記憶領域の位置を示す位置データは、前記タプル識別子の記憶領域の絶対的位置を指定するアドレスである、データベースシステム。
【請求項９】
請求項７に記載のデータベースシステムであって、前記タプル識別子の記録領域の位置を示す位置データは、前記タプル識別子の記憶領域の相対的位置を指定するオフセットである、データベースシステム。
【請求項１０】
請求項１から９のうちのいずれか１項に記載のデータベースシステムであって、前記複数の実体データは可変長データを含む、データベースシステム。
【請求項１１】
請求項１から１０のうちのいずれか１項に記載のデータベースシステムであって、
前記識別子テーブルは複数存在し、
前記データベースは、前記複数の識別子テーブル内のデータ識別子をそれぞれ一意に表す参照識別子の集合を有する参照テーブルを更に含み、
前記データ処理部は、前記参照テーブルおよび前記識別子テーブルを用いて前記データ処理を実行する、データベースシステム。
【請求項１２】
請求項１から１１のうちのいずれか１項に記載のデータベースシステムであって、
前記クエリは、問い合わせ言語で記述されており、
前記データ処理部は、前記クエリを解析し、その解析結果に基づいたトランザクションを前記データ処理として前記データベースに対して実行する、データベースシステム。
【請求項１３】
複数の実体データを含むデータベース構造であって、
行方向に定義された少なくとも１つのタプルと列方向に定義された少なくとも１つの属性フィールドとで定まる領域に前記実体データそのものを一意に表す固定長のデータ識別子が格納されている識別子テーブルと、
前記複数の実体データそれぞれの記憶領域の位置を示す位置データと前記複数のデータ識別子との間の対応関係を表す変換テーブルと、
を含み、
前記変換テーブルは、前記識別子テーブルにおいて前記各データ識別子が格納されている当該タプルを一意に表すタプル識別子が格納されるメタデータ領域を有する、データベース構造。
【請求項１４】
請求項１３記載のデータベース構造であって、前記識別子テーブルに割り当てられた記憶領域と前記実体データに割り当てられた記憶領域とが互いに異なる、データベース構造。
【請求項１５】
請求項１３または１４に記載のデータベース構造であって、前記メタデータ領域のサイズは固定長である、データベース構造。
【請求項１６】
請求項１５に記載のデータベース構造であって、前記変換テーブルは、前記各データ識別子に対して、前記タプル識別子のデータ量が前記メタデータ領域の固定長サイズを超えたか否かを示すフラグ情報が格納されるフラグ領域を有する、データベース構造。
【請求項１７】
請求項１５または１６に記載のデータベース構造であって、前記タプル識別子のデータ量が前記固定長サイズを超えるときに当該タプル識別子の全部または一部が格納されるオーバフロー領域を更に有するデータベース構造。
【請求項１８】
（ａ）複数の実体データを含むデータベースについてクエリを受信するステップと、
（ｂ）前記データベースに対して、当該受信されたクエリに基づいたデータ処理を実行するステップと、
を備え、
前記データベースは、
行方向に定義された少なくとも１つのタプルと列方向に定義された少なくとも１つの属性フィールドとで定まる領域に前記実体データそのものを一意に表す固定長のデータ識別子が格納されている識別子テーブルと、
前記複数の実体データそれぞれの記憶領域の位置を示す位置データと前記複数のデータ識別子との間の対応関係を表す変換テーブルと、
を含み、
前記変換テーブルは、前記識別子テーブルにおいて前記各データ識別子が格納されている当該タプルを一意に表すタプル識別子が格納されるメタデータ領域を有する、データベース管理方法。
【請求項１９】
請求項１８記載のデータベース管理方法であって、前記識別子テーブルに割り当てられた記憶領域と前記実体データに割り当てられた記憶領域とが互いに異なる、データベース管理方法。
【請求項２０】
請求項１８または１９に記載のデータベース管理方法であって、前記メタデータ領域のサイズは固定長である、データベース管理方法。
【請求項２１】
請求項２０に記載のデータベース管理方法であって、前記変換テーブルは、前記各データ識別子に対して、前記タプル識別子のデータ量が前記メタデータ領域の固定長サイズを超えたか否かを示すフラグ情報が格納されるフラグ領域を有する、データベース管理方法。
【請求項２２】
請求項２０または２１に記載のデータベース管理方法であって、
前記データベースは、前記タプル識別子のデータ量が前記固定長サイズを超えるときに当該タプル識別子の全部または一部が格納されるオーバフロー領域を有し、
前記ステップ（ｂ）は、前記タプル識別子のデータ量が前記固定長サイズを超えるときに、当該タプル識別子の全部または一部を前記オーバフロー領域に格納するステップを含む、データベース管理方法。
【請求項２３】
請求項２２に記載のデータベース管理方法であって、前記ステップ（ｂ）は、前記オーバフロー領域に前記タプル識別子が格納されるとき、当該タプル識別子の記憶領域の位置を示す位置データを前記メタデータ領域に格納するステップを含む、データベース管理方法。
【請求項２４】
複数の実体データを含むデータベースについてクエリを受信する処理と、
前記データベースに対して当該受信されたクエリに基づいて実行されるデータ処理と、
を含むデータベース管理処理をコンピュータに実行させるコンピュータプログラムであって、
前記データベースは、
行方向に定義された少なくとも１つのタプルと列方向に定義された少なくとも１つの属性フィールドとで定まる領域に前記実体データそのものを一意に表す固定長のデータ識別子が格納されている識別子テーブルと、
前記複数の実体データそれぞれの記憶領域の位置を示す位置データと前記複数のデータ識別子との間の対応関係を表す変換テーブルと、
を含み、
前記変換テーブルは、前記識別子テーブルにおいて前記各データ識別子が格納されている当該タプルを一意に表すタプル識別子が格納されるメタデータ領域を有することを特徴とするコンピュータプログラム。
【請求項２５】
請求項２４記載のコンピュータプログラムであって、前記識別子テーブルに割り当てられた記憶領域と前記実体データに割り当てられた記憶領域とが互いに異なることを特徴とするコンピュータプログラム。
【請求項２６】
請求項２４または２５に記載のコンピュータプログラムであって、前記メタデータ領域のサイズは固定長であることを特徴とするコンピュータプログラム。
【請求項２７】
請求項２６に記載のコンピュータプログラムであって、前記変換テーブルは、前記各データ識別子に対して、前記タプル識別子のデータ量が前記メタデータ領域の固定長サイズを超えたか否かを示すフラグ情報が格納されるフラグ領域を有することを特徴とするコンピュータプログラム。
【請求項２８】
請求項２６または２７に記載のコンピュータプログラムであって、
前記データベースは、前記タプル識別子のデータ量が前記固定長サイズを超えるときに当該タプル識別子の全部または一部が格納されるオーバフロー領域を有し、
前記データ処理は、前記タプル識別子のデータ量が前記固定長サイズを超えるときに、当該タプル識別子の全部または一部を前記オーバフロー領域に格納する処理を含むことを特徴とするコンピュータプログラム。
【請求項２９】
請求項２８に記載のコンピュータプログラムであって、前記データ処理は、前記オーバフロー領域に前記タプル識別子が格納されるとき、当該タプル識別子の記憶領域の位置を示す位置データを前記メタデータ領域に格納する処理を含むことを特徴とするコンピュータプログラム。
【国際調査報告】
2010084754.tif 000016
2010084754.tif 000017