TOP > 国内特許検索 > データベース装置、データベースの管理方法、データベースのデータ構造、データベースの管理プログラムおよびそれを記録したコンピュータ読み取り可能な記録媒体 > 明細書

明細書 :データベース装置、データベースの管理方法、データベースのデータ構造、データベースの管理プログラムおよびそれを記録したコンピュータ読み取り可能な記録媒体

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5419069号 (P5419069)
登録日 平成25年11月29日(2013.11.29)
発行日 平成26年2月19日(2014.2.19)
発明の名称または考案の名称 データベース装置、データベースの管理方法、データベースのデータ構造、データベースの管理プログラムおよびそれを記録したコンピュータ読み取り可能な記録媒体
国際特許分類 G06F  12/00        (2006.01)
G06F  17/30        (2006.01)
FI G06F 12/00 512
G06F 17/30 180D
G06F 17/30 150Z
請求項の数または発明の数 12
全頁数 38
出願番号 特願2009-041176 (P2009-041176)
出願日 平成21年2月24日(2009.2.24)
審査請求日 平成23年10月14日(2011.10.14)
特許権者または実用新案権者 【識別番号】504145320
【氏名又は名称】国立大学法人福井大学
発明者または考案者 【氏名】都司 達夫
個別代理人の代理人 【識別番号】110000338、【弁理士】、【氏名又は名称】特許業務法人原謙三国際特許事務所
特許請求の範囲 【請求項1】
関係テーブルの各タップルに対応する拡張可能配列の要素の位置を示す位置情報をキー値として登録した要素位置データを格納したデータベース記憶部を具備するとともに、
関係テーブルには複数の属性が含まれ、当該関係テーブルに含まれるタップルは当該関係テーブルが有する上記属性のすべてを有し、
上記位置情報が、要素が属する拡張可能配列の区画の位置を示す区画位置情報と、区画内における要素の位置を示す、当該タップルの各属性の属性値に一意に対応した値を所定の属性順に並べた座標情報と、を含む情報であるデータベース装置において、
上記区画が拡張可能配列の部分配列であって、
上記データベース記憶部に、
関係テーブルの属性ごとに設けられ、属性の各属性値と拡張可能配列の添字との対応関係を規定する第1データと、
上記区画位置情報である、関係テーブルのタップルに対応する拡張可能配列の要素が属する部分配列の経歴値、および、上記座標情報である、当該タップルの各属性値に対応する上記拡張可能配列の各添字のビットパターンを所定の属性順に並べた座標パターン、の2項組表現をキー値として登録した、上記要素位置データである第2データと、
新たな属性値を持つタップルを挿入するとき、拡張可能配列に対して、上記属性値が属する属性の区画を追加する配列拡張において、各区画の追加が行われる時間的順序を表す上記経歴値を登録した属性毎経歴値テーブルと、
上記経歴値、各経歴値に対応する時間的順序で配列拡張した属性の次元、および、当該経歴値に対応する拡張部分配列の任意の要素について、属性毎に拡張可能配列における対応次元の添字の表現に要するビット数を要素とする境界ベクトルを登録した経歴値テーブルと、
拡張可能配列の添字毎にその添字に対応する属性値および該属性値を持つすべてのタップル数を登録した属性値テーブルと、を格納しており、
ある属性値を持つタップルを検索するとき、
上記属性値が属する属性の上記第1データを用いて、上記属性値を拡張可能配列の添字に変換し、当該次元の経歴値テーブルより経歴値を求めた後,
上記第2データを参照して、2項組表現されたキー値中の座標パターンに含まれる、上記属性の属性値に対応するビットパターンが、上記添字のビットパターンと一致するタップルを抽出するタップル検索手段をさらに具備することを特徴とするデータベース装置。
【請求項2】
関係テーブルの各タップルに対応する拡張可能配列の要素の位置を示す位置情報をキー値として登録した要素位置データを格納したデータベース記憶部を具備するとともに、
関係テーブルには複数の属性が含まれ、当該関係テーブルに含まれるタップルは当該関係テーブルが有する上記属性のすべてを有し、
上記位置情報が、要素が属する拡張可能配列の区画の位置を示す区画位置情報と、区画内における要素の位置を示す、当該タップルの各属性の属性値に一意に対応した値を所定の属性順に並べた座標情報と、を含む情報であるデータベース装置において、
上記区画が拡張可能配列の部分配列であって、
上記データベース記憶部に、
関係テーブルの属性ごとに設けられ、属性の各属性値と拡張可能配列の添字との対応関係を規定する第1データと、
上記区画位置情報である、関係テーブルのタップルに対応する拡張可能配列の要素が属する部分配列の経歴値、および、上記座標情報である、当該タップルの各属性値に対応する上記拡張可能配列の各添字のビットパターンを所定の属性順に並べた座標パターン、の2項組表現をキー値として登録した、上記要素位置データである第2データと、
新たな属性値を持つタップルを挿入するとき、拡張可能配列に対して、上記属性値が属する属性の区画を追加する配列拡張において、各区画の追加が行われる時間的順序を表す上記経歴値を登録した属性毎経歴値テーブルと、
上記経歴値、各経歴値に対応する時間的順序で配列拡張した属性の次元、および、当該経歴値に対応する拡張部分配列の任意の要素について、属性毎に拡張可能配列における対応次元の添字の表現に要するビット数を要素とする境界ベクトルを登録した経歴値テーブルと、
拡張可能配列の添字毎にその添字に対応する属性値および該属性値を持つすべてのタップル数を登録した属性値テーブルと、を格納しており、
新たな属性値を持つタップルを挿入するとき、
配列拡張が必要である場合には、上記属性値が属する属性の部分配列を追加するとともに、経歴値をインクリメントして当該属性の上記属性毎経歴値テーブルに登録する基本データ拡張処理を行い、
配列拡張が不必要である場合、および、配列拡張が必要である場合に上記基本データ拡張処理を行った後、上記属性値を上記属性値テーブルおよび上記第1データに登録するとともに、当該タップルの各属性値に対応する上記座標パターンを生成して、経歴値および座標パターンの2項組表現をキー値として上記第2データへ挿入するタップル挿入手段をさらに具備することを特徴とするデータベース装置。
【請求項3】
関係テーブルを用いたデータベース装置におけるデータベースの管理方法であって、
関係テーブルには複数の属性が含まれ、当該関係テーブルに含まれるタップルは当該関係テーブルが有する上記属性のすべてを有し、
上記データベース装置は、
データベース記憶部に、
関係テーブルの属性ごとに設けられ、属性の各属性値と拡張可能配列の添字との対応関係を規定する第1データと、
関係テーブルのタップルに対応する拡張可能配列の要素が属する部分配列の経歴値、および、当該タップルの各属性値に対応する上記拡張可能配列の各添字のビットパターンを所定の属性順に並べた座標パターン、の2項組表現をキー値として登録した第2データと、
新たな属性値を持つタップルを挿入するとき、拡張可能配列に対して、上記属性値が属する属性の区画を追加する配列拡張において、各区画の追加が行われる時間的順序を表す上記経歴値を登録した属性毎経歴値テーブルと、
上記経歴値、各経歴値に対応する時間的順序で配列拡張した属性の次元、および、当該経歴値に対応する拡張部分配列の任意の要素について、属性毎に拡張可能配列における対応次元の添字の表現に要するビット数を要素とする境界ベクトルを登録した経歴値テーブルと、
拡張可能配列の添字毎にその添字に対応する属性値および該属性値を持つすべてのタップル数を登録した属性値テーブルと、を格納しており、
ある属性値を持つタップルを検索するとき、
上記属性値が属する属性の上記第1データを用いて、上記属性値を拡張可能配列の添字に変換し、当該次元の経歴値テーブルより経歴値を求めた後、
上記第2データを参照して、2項組表現されたキー値中の座標パターンに含まれる、上記属性の属性値に対応するビットパターンが、上記添字のビットパターンと一致するタップルを抽出することを特徴とするデータベースの管理方法。
【請求項4】
関係テーブルを用いたデータベース装置におけるデータベースの管理方法であって、
関係テーブルには複数の属性が含まれ、当該関係テーブルに含まれるタップルは当該関係テーブルが有する上記属性のすべてを有し、
上記データベース装置は、
データベース記憶部に、
関係テーブルの属性ごとに設けられ、属性の各属性値と拡張可能配列の添字との対応関係を規定する第1データと、
関係テーブルのタップルに対応する拡張可能配列の要素が属する部分配列の経歴値、および、当該タップルの各属性値に対応する上記拡張可能配列の各添字のビットパターンを所定の属性順に並べた座標パターン、の2項組表現をキー値として登録した第2データと、
新たな属性値を持つタップルを挿入するとき、拡張可能配列に対して、上記属性値が属する属性の区画を追加する配列拡張において、各区画の追加が行われる時間的順序を表す上記経歴値を登録した属性毎経歴値テーブルと、
上記経歴値、各経歴値に対応する時間的順序で配列拡張した属性の次元、および、当該経歴値に対応する拡張部分配列の任意の要素について、属性毎に拡張可能配列における対応次元の添字の表現に要するビット数を要素とする境界ベクトルを登録した経歴値テーブルと、
拡張可能配列の添字毎にその添字に対応する属性値および該属性値を持つすべてのタップル数を登録した属性値テーブルと、を格納しており、
新たな属性値を持つタップルを挿入するとき、
配列拡張が必要である場合には、上記属性値が属する属性の部分配列を追加するとともに、経歴値をインクリメントして当該属性の上記属性毎経歴値テーブルに登録する基本データ拡張処理を行い、
配列拡張が不必要である場合、および、配列拡張が必要である場合に上記基本データ拡張処理を行った後、上記属性値を上記属性値テーブルおよび上記第1データに登録するとともに、当該タップルの各属性値に対応する上記座標パターンを生成して、経歴値および座標パターンの2項組表現をキー値として上記第2データへ挿入することを特徴とするデータベースの管理方法。
【請求項5】
請求項1または2に記載のデータベース装置に用いられる、関係テーブルを用いたデータベースのデータ構造であって、
上記第1データと、上記第2データと、上記属性毎経歴値テーブルと、上記経歴値テーブルと、上記属性値テーブルと、よりなることを特徴とするデータベースのデータ構造。
【請求項6】
関係テーブルの各タップルに対応する拡張可能配列の要素の位置を示す位置情報をキー値として登録した要素位置データを格納したデータベース記憶部を具備するとともに、
関係テーブルには複数の属性が含まれ、当該関係テーブルに含まれるタップルは当該関係テーブルが有する上記属性のすべてを有し、
上記位置情報が、要素が属する拡張可能配列の区画の位置を示す区画位置情報と、区画内における要素の位置を示す、当該タップルの各属性の属性値に一意に対応した値を所定の属性順に並べた座標情報と、を含む情報であるデータベース装置において、
上記拡張可能配列がチャンク化拡張可能配列であり、かつ、上記区画がチャンク化拡張可能配列のチャンクであって、
上記データベース記憶部に、
関係テーブルの属性ごとに設けられ、属性の各属性値とチャンク化拡張可能配列の添字との対応関係を規定する第1データと、
上記区画位置情報である、関係テーブルのタップルに対応するチャンク化拡張可能配列の要素が属するチャンクのチャンク番号、および、上記座標情報である、当該タップルの各属性値に対応する上記チャンク化拡張可能配列の当該チャンクにおける各添字のビットパターンを所定の属性順に並べたチャンク内座標パターン、の2項組表現をキー値として登録した、上記要素位置データである第2データと、
新たな属性値を持つタップルを挿入するとき、チャンク化拡張可能配列に対して、上記属性値が属する属性のチャンクを追加するチャンク配列拡張において、各チャンクを含むチャンク部分配列の追加が行われる時間的順序を表す経歴値を登録した属性毎経歴値テーブルと、
上記経歴値、各経歴値に対応する時間的順序でチャンク配列拡張した属性の次元、および、当該経歴値に対応する拡張チャンク部分配列中の任意のチャンクについて、チャンク化拡張可能配列における対応次元のチャンク毎に付される添字の表現に要するビット数を要素とする境界ベクトルを登録した経歴値テーブルと、
チャンク化拡張可能配列の添字毎にその添字に対応する属性値および該属性値を持つすべてのタップル数を登録した属性値テーブルと、を格納しており、
ある属性値を持つタップルを検索するとき、
上記属性値が属する属性の上記第1データを用いて、上記属性値をチャンク化拡張可能配列の当該次元の添字に変換し、当該次元の経歴値テーブルより経歴値を求めた後、
上記第2データを参照して、2項組表現されたキー値中のチャンク内座標パターンに含まれる、上記属性の属性値に対応するビットパターンが、上記添字のビットパターンと一致するタップルを抽出するタップル検索手段をさらに具備することを特徴とするデータベース装置。
【請求項7】
関係テーブルの各タップルに対応する拡張可能配列の要素の位置を示す位置情報をキー値として登録した要素位置データを格納したデータベース記憶部を具備するとともに、
関係テーブルには複数の属性が含まれ、当該関係テーブルに含まれるタップルは当該関係テーブルが有する上記属性のすべてを有し、
上記位置情報が、要素が属する拡張可能配列の区画の位置を示す区画位置情報と、区画内における要素の位置を示す、当該タップルの各属性の属性値に一意に対応した値を所定の属性順に並べた座標情報と、を含む情報であるデータベース装置において、
上記拡張可能配列がチャンク化拡張可能配列であり、かつ、上記区画がチャンク化拡張可能配列のチャンクであって、
上記データベース記憶部に、
関係テーブルの属性ごとに設けられ、属性の各属性値とチャンク化拡張可能配列の添字との対応関係を規定する第1データと、
上記区画位置情報である、関係テーブルのタップルに対応するチャンク化拡張可能配列の要素が属するチャンクのチャンク番号、および、上記座標情報である、当該タップルの各属性値に対応する上記チャンク化拡張可能配列の当該チャンクにおける各添字のビットパターンを所定の属性順に並べたチャンク内座標パターン、の2項組表現をキー値として登録した、上記要素位置データである第2データと、
新たな属性値を持つタップルを挿入するとき、チャンク化拡張可能配列に対して、上記属性値が属する属性のチャンクを追加するチャンク配列拡張において、各チャンクを含むチャンク部分配列の追加が行われる時間的順序を表す経歴値を登録した属性毎経歴値テーブルと、
上記経歴値、各経歴値に対応する時間的順序でチャンク配列拡張した属性の次元、および、当該経歴値に対応する拡張チャンク部分配列中の任意のチャンクについて、チャンク化拡張可能配列における対応次元のチャンク毎に付される添字の表現に要するビット数を要素とする境界ベクトルを登録した経歴値テーブルと、
チャンク化拡張可能配列の添字毎にその添字に対応する属性値および該属性値を持つすべてのタップル数を登録した属性値テーブルと、を格納しており、
新たな属性値を持つタップルを挿入するとき、
チャンク配列拡張が必要である場合には、上記属性値が属する属性のチャンク部分配列を追加するとともに、経歴値をインクリメントして当該属性の上記属性毎経歴値テーブルに登録する基本データ拡張処理を行い、
チャンク配列拡張が不必要である場合、および、チャンク配列拡張が必要である場合に上記基本データ拡張処理を行った後、上記属性値を上記属性値テーブルおよび上記第1データに登録するとともに、当該タップルの各属性値に対応する上記チャンク内座標パターンを生成して、チャンク番号およびチャンク座標パターンの2項組表現をキー値として上記第2データへ挿入するタップル挿入手段をさらに具備することを特徴とするデータベース装置。
【請求項8】
関係テーブルを用いたデータベース装置におけるデータベースの管理方法であって、
関係テーブルには複数の属性が含まれ、当該関係テーブルに含まれるタップルは当該関係テーブルが有する上記属性のすべてを有し、
上記データベース装置は、
データベース記憶部に、
関係テーブルの属性ごとに設けられ、属性の各属性値とチャンク化拡張可能配列の添字との対応関係を規定する第1データと、
関係テーブルのタップルに対応するチャンク化拡張可能配列の要素が属するチャンクのチャンク番号、および、当該タップルの各属性値に対応する上記チャンク化拡張可能配列の当該チャンクにおける各添字のビットパターンを所定の属性順に並べたチャンク内座標パターン、の2項組表現をキー値として登録した第2データと、
新たな属性値を持つタップルを挿入するとき、チャンク化拡張可能配列に対して、上記属性値が属する属性のチャンクを追加するチャンク配列拡張において、各チャンクを含むチャンク部分配列の追加が行われる時間的順序を表す経歴値を登録した属性毎経歴値テーブルと、
上記経歴値、各経歴値に対応する時間的順序でチャンク配列拡張した属性、および、当該経歴値に対応する拡張チャンク部分配列中の任意のチャンクについて、チャンク化拡張可能配列における対応次元のチャンク毎に付される添字の表現に要するビット数を要素とする境界ベクトルを登録した経歴値テーブルと、
チャンク化拡張可能配列の添字毎にその添字に対応する属性値および該属性値を持つすべてのタップル数を登録した属性値テーブルと、を格納しており、
ある属性値を持つタップルを検索するとき、
上記属性値が属する属性の上記第1データを用いて、上記属性値をチャンク化拡張可能配列の添字に変換し、
上記第2データを参照して、2項組表現されたキー値中のチャンク内座標パターンに含まれる、上記属性の属性値に対応するビットパターンが、上記添字のビットパターンと一致するタップルを抽出することを特徴とするデータベースの管理方法。
【請求項9】
関係テーブルを用いたデータベース装置におけるデータベースの管理方法であって、
関係テーブルには複数の属性が含まれ、当該関係テーブルに含まれるタップルは当該関係テーブルが有する上記属性のすべてを有し、
上記データベース装置は、
データベース記憶部に、
関係テーブルの属性ごとに設けられ、属性の各属性値とチャンク化拡張可能配列の添字との対応関係を規定する第1データと、
関係テーブルのタップルに対応するチャンク化拡張可能配列の要素が属するチャンクのチャンク番号、および、当該タップルの各属性値に対応する上記チャンク化拡張可能配列の当該チャンクにおける各添字のビットパターンを所定の属性順に並べたチャンク内座標パターン、の2項組表現をキー値として登録した第2データと、
新たな属性値を持つタップルを挿入するとき、チャンク化拡張可能配列に対して、上記属性値が属する属性のチャンクを追加するチャンク配列拡張において、各チャンクを含むチャンク部分配列の追加が行われる時間的順序を表す経歴値を登録した属性毎経歴値テーブルと、
上記経歴値、各経歴値に対応する時間的順序でチャンク配列拡張した属性の次元、および、当該経歴値に対応する拡張チャンク部分配列中の任意のチャンクについて、チャンク化拡張可能配列における対応次元のチャンク毎に付される添字の表現に要するビット数を要素とする境界ベクトルを登録した経歴値テーブルと、
チャンク化拡張可能配列の添字毎にその添字に対応する属性値および該属性値を持つすべてのタップル数を登録した属性値テーブルと、を格納しており、
新たな属性値を持つタップルを挿入するとき、
チャンク配列拡張が必要である場合には、上記属性値が属する属性のチャンク部分配列を追加するとともに、経歴値をインクリメントして当該属性の上記属性毎経歴値テーブルに登録する基本データ拡張処理を行い、
チャンク配列拡張が不必要である場合、および、チャンク配列拡張が必要である場合に上記基本データ拡張処理を行った後、上記属性値を上記属性値テーブルおよび上記第1データに登録するとともに、当該タップルの各属性値に対応する上記チャンク内座標パターンを生成して、チャンク番号およびチャンク座標パターンの2項組表現をキー値として上記第2データへ挿入することを特徴とするデータベースの管理方法。
【請求項10】
請求項6または7に記載のデータベース装置に用いられる、関係テーブルを用いたデータベースのデータ構造であって、
上記第1データと、上記第2データと、上記属性毎経歴値テーブルと、上記経歴値テーブルと、上記属性値テーブルと、よりなることを特徴とするデータベースのデータ構造。
【請求項11】
請求項1、2、6、7のいずれか1項に記載のデータベース装置を動作させるデータベース管理プログラムであって、コンピュータを上記の各手段として機能させるためのデータベース管理プログラム。
【請求項12】
請求項11に記載のデータベース管理プログラムを記録したコンピュータ読み取り可能な記録媒体。
発明の詳細な説明 【技術分野】
【0001】
本発明は、関係データベースを用いるデータベースに関するものであり、詳細には、データベース装置、データベースの管理方法、データベースのデータ構造、データベースの管理プログラムおよびそれを記録したコンピュータ読み取り可能な記録媒体に関するものである。
【背景技術】
【0002】
多次元データとは複数種類のデータの組(以下、タップルという)の集合であり、代表的な多次元データとして関係データベースにおける関係テーブルがあげられる。近年、情報処理分野の多様化と拡大に応じて、その重要性は急激に増大している。多次元データを計算機内部において記憶し、処理するための効率よい方式を提供することは、多次元情報処理を必要とする諸分野の発展に基本レベルで貢献し得ると考えられる。ここでは、計算機内部での記憶サイズおよび検索効率において、きわめて優れた、多次元データの処理方式を提案する。多次元データの例として、以降では、広く知られている関係データベーステーブルを取り上げて、説明する。
【0003】
関係データベースは、図8のような関係テーブルの集合であり、関係テーブルはその中のタップルの集合である。その検索は属性名や検索の条件を指定することにより、行われる。
【0004】
このような、関係テーブルは通常2次記憶上に置かれ、各タップルは入力された順に逐次、配置される。したがって、次のような欠点がある。
【0005】
(1)例えば、年齢が23のタップルを検索する場合、テーブル中のすべてのタップルをメモリ上にロードして年齢属性をチェックする必要がある。したがって、検索時間が大きくなる。
【0006】
(2)例えば、出身地が福井のタップルは数多く現れ、文字列「福井」を重複して多く格納する必要がある。したがって、ディスク使用量が大きくなる。
【0007】
このような欠点を回避するための方法として、多次元配列を使用することが考えられる。ここで、配列の各次元はテーブルの属性に対応し、配列の要素は対応するタップルを表す。
【0008】
図9は、配列による関係テーブルの表現の一例を示す説明図である。
【0009】
この時、年齢が23のタップル集合は「年齢」次元の値が23の平面上に空でない配列要素として、存在する。配列要素[*,*,23]の番地はアドレス関数により高速に求めることができる。したがって、(1)の欠点は回避される。また、各次元の値は値順にソートされて並べられ、1度しか現れないので、(2)の欠点も回避される。
【0010】
なお、拡張可能配列に関する先行技術文献としては、以下のものがある。
【先行技術文献】
【0011】

【非特許文献1】A.L.Rosenberg, “Allocating Storage for Extendible Arrays”, Journal of ACM, Vol. 21, pp.652-670, 1974.
【非特許文献2】E.J.Otoo, T.H.Merrett, “A Storage Scheme for Extendible Arrays, Computing”, Vol.31, pp.1-9, 1983.
【非特許文献3】都司達夫, 水野剛, 宝珍輝尚, 樋口健, “拡張可能配列の遅延割付け方式”, 電子情報通信学会論文誌 D-I, Vol.J86-D-I, No.5, pp.351-356, 2003.
【非特許文献4】T.Tsuji, A.Hara, K.Higuchi, “An extendible multidimensional array system for MOLAP”Proc. of ACM Applied Computing, pp.503-510, 2006.
【非特許文献5】Masakazu Kumakiri, Li Bei, T.Tsuji, K.Higuchi, “Flexibly resizable multidimensional arrays”, Proc. of the 22nd International Conference on Data Engineering Workshops, 2006.4.
【非特許文献6】熊切正和, Li Bei, 都司達夫, 樋口健, “挿入拡張・中抜き縮小可能な多次元配列”, 日本データベース学会Letters, Vol.5, No.1, pp.61-64, 2006.
【非特許文献7】Bei Li, T.Tsuji, K.Higuchi, “Sharing Flexibly Resizable Multidimensional Arrays in Client/Server Environment”, Proc. of IEEE Int'l Workshop of Databases for Next Generation Researchers, 2007.
【非特許文献8】E.J.Otoo, D.Rotem, “Efficient Storage Allocation of Large-Scale Extendible Multi-dimensional Scientific Datasets”, Proc. of SSDBM, 179-183, 2006.
【発明の概要】
【発明が解決しようとする課題】
【0012】
ここで、多次元配列によるテーブルの表現は高速にタップルを検索することができるが、次のような欠点(a)(b)がある。
【0013】
(a)各次元のサイズは固定である。固定であるから、アドレス関数が作成できる。したがって、新たな属性値を持つタップルの追加は不可能である。
【0014】
(b)各次元の値の組み合わせがすべて存在するような密なテーブルは稀であるので、配列内の有効要素は少ない(疎配列)。有効要素の割合は通常数%以下、場合によっては0.1%以下であることが多い。このような疎配列に対しても、アドレス関数によって配列要素にアクセスできるためには空の要素(存在しないタップル)についても記憶領域を確保する必要があり、ディスクスペースの多大な無駄になる。
【0015】
これらの欠点を回避するために、新しい仕組みに基づくテーブル実装方式を提案する。この実装方式を「経歴・パターン法」(History-Pattern implementation of Multidimensional Data:HPMD)と呼ぶ。HPMDは、以下に説明する拡張可能配列の考え方に基づいている。
【0016】
拡張可能配列(extendible array)は実行時に動的に任意の次元方向にそのサイズを拡張できる配列である。拡張可能配列では拡張部分のみが動的に割付けられ、拡張前の配列要素のデータは再配置することなくそのまま利用される。配列サイズがあらかじめ予測不能な場合や、必要サイズが実行環境の変化に応じて動的に変化し得るような種々のアプリケーション分野において使用することができる。拡張可能配列のモデルとしてE.J.Otoo等により提案されたインデックス配列モデル(非特許文献2)はインデックス配列用の記憶域を付加することにより高速に配列要素を参照することができ、例えばハッシュを使った他の方式(非特許文献1)より優れていることが示されている。本発明における着想のベースはこのインデックス配列モデルの考え方に基づいており、ここでは、このモデルについてその概略を述べる。
【0017】
ある次元方向の配列拡張はその次元を除くn-1次元の配列断面に相当するサイズの連続するメモリ領域(部分配列あるいはサブ配列という)を確保し、Aに追加することによって行われる。(非特許文献2)では、拡張時に確保される部分配列はメモリ領域の0番地から拡張の順に、順次、連続領域に割り付けられることを前提としている。通常行われるメモリの動的割付けにおいては、必ずしもメモリの連続領域を割り付けるとは限らない。このことをはじめ、現実の使用に即したいくつかの改良を施したモデルが(非特許文献3)で提案されている。以下では、(非特許文献3)のモデルについて述べる。
【0018】
n次元拡張可能配列Aは1つの経歴値カウンタと次元毎に3種類の補助テーブルを有している。これらの補助テーブルは経歴値テーブル、アドレステーブル、および係数テーブルと呼ばれる。経歴値テーブルは配列拡張の時間的順序を表す1次元配列であり、配列拡張が行われるたびに、固定配列のn-1次元の部分配列が動的に割り付けられ、アドレス番地テーブルにその先頭番地が記録される。また、現在の経歴値カウンタが1インクリメントされ、その値が経歴値テーブルに順次記録される。拡張可能配列および部分配列の各次元の添え字はいずれも0から始まり、次元は1から数えるものとし、配列の1要素のサイズは1とする。
【0019】
例えば、各次元のサイズが [s1,s2,s3,s4] の通常の固定サイズの4次元配列要素をメモリ上に次元1~4の順に優先して割り付ける場合、要素 <i,i2,i3,i4> のアドレスはよく知られているように、
s2s3s4i1+s3s4i2+s4i3+i4 (1)
なる i1,i2,i3,i4に関する1次関数を計算して得られる。
【0020】
これに対して、例えば現在のサイズが [s1,s2,s3,s4] の4次元拡張可能配列の場合には、次元2の方向に1つ拡張する時、サイズ [s2,s3,s4] の3次元部分配列Sが動的に確保される。アドレステーブルは各部分配列の先頭アドレスを保持する1次元配列である。要素 <i,i2,i3,i4> が格納されているアドレスはSの先頭番地に(1)式で計算されるオフセットを加えればよい。
【0021】
Aが3次元以上の拡張可能配列の場合には、部分配列内の要素のオフセットを計算する1次関数のn-2個の係数からなる係数ベクトルを部分配列毎に記録する係数テーブルを各次元について必要とする。例えば、上記部分配列Sの要素 <i,i2,i3> のオフセットは(1)式と同様、1次関数 s3s4i1+s4i2+i3となる。この時、(s3s4,s4) がSの係数ベクトルである。係数ベクトルの値は拡張時のAの各次元のサイズに依存しているので、拡張時に係数ベクトルを計算し、それを拡張次元の係数テーブルのスロットに書き込む。
【0022】
配列要素へのアクセスは次のように行われる。図10は、インデックス配列モデルの一例を示す説明図である。図10において、次元1方向および次元2方向の経歴値テーブルをそれぞれ H1,H2 とし、またアドレステーブルをそれぞれ A1.A2とする。例えば配列要素 <3,4> のアドレス計算は次のように行われる。 H1[3] < H2[4] であるから、要素 <3,4> を含む部分配列Sは経歴値 H2[4]=7 の時に割付けられ、その先頭アドレスは A2[4]=60 である。また、要素 [3,4] はSでは要素 <3> であるので、求めるアドレスは63となる。
【0023】
なお、(非特許文献4)~(非特許文献8)はいずれも、拡張可能配列の改良や機能強化について提案している。
【0024】
本発明は、上記の問題点に鑑みてなされたものであり、その目的は、新たな属性値を持つタップルの追加とタップルの高速検索が可能であり、かつ、ディスクスペースを効率良く使用することができる、テーブル実装方式を用いたデータベース装置、データベースの管理方法、データベースのデータ構造、データベースの管理プログラムおよびそれを記録したコンピュータ読み取り可能な記録媒体を実現することにある。
【課題を解決するための手段】
【0025】
上記の課題を解決するために、本発明に係るデータベース装置は、関係テーブルを用いたデータベース装置であって、関係テーブルの各タップルに対応する拡張可能配列の要素の位置を示す位置情報をキー値として登録した要素位置データを格納したデータベース記憶部を具備するとともに、上記位置情報が、要素が属する拡張可能配列の区画の位置を示す区画位置情報と、区画内における要素の位置を示す、当該タップルの各属性の属性値に一意に対応した値を所定の属性順に並べた座標情報と、を含む情報であることを特徴としている。
【0026】
ここで、本発明では、拡張可能配列の「区画」を様々に選択可能である。そして、上記要素位置データとして、区画に応じた要素位置データを登録する。
【0027】
例えば、(1)区画を拡張可能配列の部分配列とすれば、上記要素位置データとして、上記区画位置情報を、関係テーブルのタップルに対応する拡張可能配列の要素が属する部分配列の経歴値とし、上記座標情報を、当該タップルの各属性値に対応する拡張可能配列の各添字のビットパターンを所定の属性順に並べた座標パターンとした、2項組表現をキー値として登録した2項組データを利用できる。(2)また、区画をチャンク化拡張可能配列のチャンクとすれば、上記要素位置データとして、上記区画位置情報を、関係テーブルのタップルに対応するチャンク化拡張可能配列の要素が属するチャンクのチャンク番号とし、上記座標情報を、当該タップルの各属性値に対応するチャンク化拡張可能配列の当該チャンクにおける各添字のビットパターンを所定の属性順に並べたチャンク内座標パターンとした、2項組表現をキー値として登録した2項組データを利用できる。
【0028】
具体的には、要素が属する拡張可能配列の区画の位置を示す区画位置情報と、当該タップルの各属性の属性値に一意に対応した値を所定の属性順に並べた座標情報との2項組表現は、(1)の場合、<経歴値,座標パターン>であり、(2)の場合、<チャンク番号,チャンク内座標パターン>となる。なお、チャンク番号は、要素の添字<i1,i2,...,in>より、チャンク拡張可能配列の要素(チャンク)の位置決定機構により決定される。
【0029】
よって、上記データベース装置では、2項組データ(要素位置データ)を参照することにより、区画位置情報と座標情報との2項組表現に基づいて、拡張可能配列の要素の位置を特定することが可能となる。
【0030】
なお、拡張可能配列の全要素集合Eを互いに共通な要素を持たない部分集合の集合に類別(partition)したとき、その任意の部分集合Sを拡張可能配列の「区画」と定義する。そして、部分集合Sに対応する記憶表現の先頭要素の要素集合E内での位置を特定するために必要な情報を「区画位置情報」と定義する。これにより、「区画位置情報」および「座標情報」の両者により、拡張可能配列の任意の要素について、その位置が一意的に決定される。このような定義の下で、(1)では区画である部分集合Sを部分配列としており、(2)では区画である部分集合Sをチャンクとしている。さらに、(1)(2)では、「(これら2つの)2項組表現をキー値として登録した2項組データ」と記述しているが、必ずしも2項組として、キー値の記憶表現において位置的に連接している必要はない。(ただし、高速検索のためには、位置的に連接していることが望ましい。)すなわち、要素位置データには、キー値の記憶表現にこれら2つの情報(「区画位置情報」および「座標情報」)が含まれていればよい。そして、本発明に係るデータベース装置には、これらの2つの情報を使って要素に迅速にアクセスするための手段を具備していればよい。
【0031】
また、「所定の属性順」とは、関係テーブル毎に固定されていれば、任意に設定できる。たとえば、属性に付与された識別番号順であってもよい。
【0032】
(1)2項組データに、関係テーブルのタップルに対応する拡張可能配列の要素の経歴値と、当該タップルの各属性値に対応する拡張可能配列の各添字のビットパターンを所定の属性順に並べた座標パターンとの2項組表現をキー値として登録する場合のデータベースの構成と、タップルを検索、挿入する機能は以下のとおりである。
【0033】
本発明に係るデータベース装置は、上記区画が拡張可能配列の部分配列であって、上記データベース記憶部に、関係テーブルの属性ごとに設けられ、属性の各属性値から拡張可能配列の添字に変換するための第1データと、上記区画位置情報である、関係テーブルのタップルに対応する拡張可能配列の要素が属する部分配列の経歴値、および、上記座標情報である、当該タップルの各属性値に対応する上記拡張可能配列の各添字のビットパターンを所定の属性順に並べた座標パターン、の2項組表現をキー値として登録した、上記要素位置データである第2データと、属性毎の配列拡張の時間的順序を表す経歴値を登録した属性毎経歴値テーブルと、経歴値に対応する配列拡張した属性の次元、および、当該経歴値に対応する拡張部分配列の任意の要素について、属性毎に拡張可能配列における対応次元の添字の表現に要するビット数を要素とする境界ベクトルを登録した経歴値テーブルと、拡張可能配列の添字毎にその添字に対応する属性値および該属性値を持つすべてのタップル数を登録した属性値テーブルと、を格納したことを特徴としている。
【0034】
また、本発明に係るデータベース装置は、ある属性値を持つタップルを検索するとき、上記属性値が属する属性の上記第1データを用いて、上記属性値を拡張可能配列の当該次元の添字に変換し、当該次元の経歴値テーブルより経歴値を求めた後、上記第2データを参照して、2項組表現されたキー値中の座標パターンに含まれる、上記属性の属性値に対応するビットパターンが、上記添字のビットパターンと一致するタップルを抽出するタップル検索手段を具備することを特徴としている。
【0035】
また、本発明に係るデータベース装置は、新たな属性値を持つタップルを挿入するとき、配列拡張が必要である場合には、上記属性値が属する属性の部分配列を追加するとともに、経歴値をインクリメントして当該属性の上記属性毎経歴値テーブルに登録する基本データ拡張処理を行い、配列拡張が不必要である場合、および、配列拡張が必要である場合に上記基本データ拡張処理を行った後、上記属性値を上記属性値テーブルおよび上記第1データに登録するとともに、当該タップルの各属性値に対応する上記座標パターンを生成して、経歴値および座標パターンの2項組表現をキー値として上記第2データへ挿入するタップル挿入手段を具備することを特徴としている。
【0036】
そして、上記の構成により、本発明のデータベースは、関係テーブルを用いたデータベースのデータ構造であって、関係テーブルの属性ごとに設けられ、属性の各属性値から拡張可能配列の添字に変換するための第1データと、関係テーブルのタップルに対応する拡張可能配列の要素が属する部分配列の経歴値、および、当該タップルの各属性値に対応する上記拡張可能配列の各添字のビットパターンを所定の属性順に並べた座標パターン、の2項組表現をキー値として登録した第2データと、属性毎の配列拡張の時間的順序を表す経歴値を登録した属性毎経歴値テーブルと、経歴値に対応する配列拡張した属性の次元、および、当該経歴値に対応する拡張部分配列の任意の要素について、属性毎に拡張可能配列における対応次元の添字の表現に要するビット数を要素とする境界ベクトルを登録した経歴値テーブルと、拡張可能配列の添字毎にその添字に対応する属性値および該属性値を持つすべてのタップル数を登録した属性値テーブルと、よりなるデータ構造を有している。
【0037】
上記の構成によれば、関係データベースに新たな属性値を持つタップルの追加が可能であり、ディスクスペースを効率良く使用することが可能となる。
【0038】
(2)2項組データに、関係テーブルのタップルに対応するチャンク化拡張可能配列の要素が属するチャンクのチャンク番号と、当該タップルの各属性値に対応するチャンク化拡張可能配列の当該チャンクにおける各添字のビットパターンを所定の属性順に並べたチャンク内座標パターンとの2項組表現をキー値として登録する場合のデータベースの構成と、データを検索、挿入する機能は以下のとおりである。
【0039】
本発明に係るデータベース装置は、上記拡張可能配列がチャンク化拡張可能配列であり、かつ、上記区画がチャンク化拡張可能配列のチャンクであって、上記データベース記憶部に、関係テーブルの属性ごとに設けられ、属性の各属性値からチャンクを要素とするチャンク化拡張可能配列の添字に変換するための第1データと、上記区画位置情報である、関係テーブルのタップルに対応するチャンク化拡張可能配列の要素が属するチャンクのチャンク番号、および、上記座標情報である、当該タップルの各属性値に対応する上記チャンク化拡張可能配列の当該チャンクにおける各添字のビットパターンを所定の属性順に並べたチャンク内座標パターン、の2項組表現をキー値として登録した、上記要素位置データである第2データと、属性毎のチャンク配列拡張の時間的順序を表す経歴値を登録した属性毎経歴値テーブルと、経歴値に対応するチャンク配列拡張した属性の次元、および、当該経歴値に対応する拡張チャンク部分配列中の任意のチャンクについて、属性毎にチャンク拡張可能配列における対応次元の添字の表現に要するビット数を要素とする境界ベクトルを登録した経歴値テーブルと、チャンク化拡張可能配列の添字毎にその添字に対応する属性値および該属性値を持つすべてのタップル数を登録した属性値テーブルと、を格納したことを特徴としている。
【0040】
また、本発明に係るデータベース装置は、ある属性値を持つタップルを検索するとき、上記属性値が属する属性の上記第1データを用いて、上記属性値をチャンク化拡張可能配列の当該次元の添字に変換し、当該次元の経歴値テーブルより経歴値を求めた後、上記第2データを参照して、2項組表現されたキー値中のチャンク内座標パターンに含まれる、上記属性の属性値に対応するビットパターンが、上記添字のビットパターンと一致するタップルを抽出するタップル検索手段を具備することを特徴としている。
【0041】
また、本発明に係るデータベース装置は、新たな属性値を持つタップルを挿入するとき、チャンク配列拡張が必要である場合には、上記属性値が属する属性のチャンク部分配列を追加するとともに、経歴値をインクリメントして当該属性の上記属性毎経歴値テーブルに登録する基本データ拡張処理を行い、チャンク配列拡張が不必要である場合、および、チャンク配列拡張が必要である場合に上記基本データ拡張処理を行った後、上記属性値を上記属性値テーブルおよび上記第1データに登録するとともに、当該タップルの各属性値に対応する上記チャンク内座標パターンを生成して、チャンク番号およびチャンク内座標パターンの2項組表現をキー値として上記第2データへ挿入するタップル挿入手段を具備することを特徴としている。
【0042】
そして、上記の構成により、本発明のデータベースは、関係テーブルを用いたデータベースのデータ構造であって、関係テーブルの属性ごとに設けられ、属性の各属性値からチャンク化拡張可能配列の当該チャンクの添字に変換するための第1データと、関係テーブルのタップルに対応するチャンク化拡張可能配列の要素が属するチャンクのチャンク番号、および、当該タップルの各属性値に対応する上記チャンク化拡張可能配列の当該チャンクにおける各添字のビットパターンを所定の属性順に並べたチャンク内座標パターン、の2項組表現をキー値として登録した、上記要素位置データである第2データと、属性毎のチャンク配列拡張の時間的順序を表す経歴値を登録した属性毎経歴値テーブルと、経歴値に対応するチャンク配列拡張した属性の次元、および、当該経歴値に対応する拡張チャンク部分配列中の任意のチャンクについて、属性毎にチャンク拡張可能配列における対応次元の添字の表現に要するビット数を要素とする境界ベクトルを登録した経歴値テーブルと、チャンク化拡張可能配列の添字毎にその添字に対応する属性値および該属性値を持つすべてのタップル数を登録した属性値テーブルと、よりなるデータ構造を有している。
【0043】
上記の構成によれば、関係データベースに新たな属性値を持つタップルの追加が可能であり、ディスクスペースを効率良く使用することが可能となる。しかも、優れた検索速度が実現できる。
【0044】
なお、上記データベース装置は、コンピュータによって実現してもよく、この場合には、コンピュータを上記各手段として動作させることにより上記データベース装置をコンピュータにて実現させるデータベース管理プログラム、およびそれを記録したコンピュータ読み取り可能な記録媒体も、本発明の範疇に入る。
【発明の効果】
【0045】
以上のように、本発明に係るデータベース装置は、関係テーブルを用いたデータベース装置であって、関係テーブルの各タップルに対応する拡張可能配列の要素の位置を示す位置情報をキー値として登録した要素位置データを格納したデータベース記憶部を具備するとともに、上記位置情報が、要素が属する拡張可能配列の区画の位置を示す区画位置情報と、区画内における要素の位置を示す、当該タップルの各属性の属性値に一意に対応した値を所定の属性順に並べた座標情報と、を含む情報である構成である。
【0046】
それゆえ、関係データベースに新たな属性値を持つタップルの追加が可能であり、ディスクスペースを効率良く使用することが可能となるという効果を奏する。しかも、優れた検索速度を実現することが可能となるという効果を奏する。
【図面の簡単な説明】
【0047】
【図1】本発明の一実施の形態に係るデータベース装置の構成の概略を示す機能ブロック図である。
【図2】HPMDの基本データ構造を示す説明図である。
【図3】CVTのデータ部のデータ構造を示す説明図である。
【図4】タップルの挿入プログラムの本体int insert_rec()の流れを示すフローチャートである。
【図5】HPMDにおける属性値の検索範囲を示す説明図であり、(a)は経歴値5(次元1)の添字に対応する属性値の論理検索範囲を示し、(b)は経歴値3(次元2)の添字に対応する属性値の論理検索範囲を示す。
【図6】RDTを検索して、指定された次元iの属性値colvalを持つキーを出力するルーチンの流れを示すフローチャートである。
【図7】C-HPMDにおける論理拡張可能配列とチャンク番号との関係を示す説明図である。
【図8】従来の技術に係る関係テーブルの一例を示す説明図である。
【図9】従来の技術に係る配列による関係テーブルの表現の一例を示す説明図である。
【図10】従来の技術に係るインデックス配列モデルの一例を示す説明図である。
【発明を実施するための形態】
【0048】
本発明の一実施の形態について図1から図7に基づいて説明すれば、以下のとおりである。まず、本発明に係る関係テーブルの記憶、操作方式とその実現ソフトウェアについて説明する。

【0049】
1. HPMDの基本データ構造とその処理
HPMDでは〔発明が解決しようとする課題〕で述べた、多次元データの動的な追加・拡張に対して効率よく対処できる拡張可能配列の仕組みを、その基本部分において活かしている。n個の属性からなる多次元データTはn次元HPMDにより実装される。n次元HPMDは次のデータ構造からなる。

【0050】
(1)n個のCVTi(1≦i≦n)(attribute-subscript ConVersion Tree)とRDT(Real Data Tree)のn+1個のB+木。CVTiは次元iの属性値をキーとして、対応する拡張可能配列の添字を記録している。また、RDTのキーは以降で述べるエンコード方式による多次元データタップルのエンコード値が格納される。なお、CVTに必要な機能は、キー指定によるランダムアクセス機能とキーの値順による順次的アクセス機能であり、RDTに必要な機能は、キー指定によるランダムアクセス機能である。よって、CVTおよびRDTは、B+木に限らず、上記の機能をそれぞれ実現するキー編成のデータ構造であればよい。もちろん、B+木であれば、上記の機能をそれぞれ効率よく実現でき、HPMDの性能を高めることができる。

【0051】
(2)各次元毎に経歴値を格納するn個の経歴値テーブルHi(1≦i≦n)、および、経歴値を添字として、経歴値に対応する拡張次元と以降で述べる境界ベクトルを格納した経歴値テーブルH。以後、単に経歴値テーブルと言った場合、後者を指し、特に前者を指す場合には次元iの経歴値テーブルということとする。

【0052】
(3)各次元の添字ごとにその添字に対応する属性値およびその属性値を持つすべてのタップル数を記録する属性値テーブルCi(1≦i≦n)。

【0053】
図2は、HPMDの基本データ構造を示す説明図である。図2には表中の13個の2次元のタップル集合を上から順に挿入した場合の上記(1)(2)(3)のデータ構造を示す。n次元拡張可能配列Aの現在の各次元サイズを <s,s2,……,sn> として経歴値カウンタの値をhとする。sk-1(1≦k≦n)の表現に要するビット数を b(sk) として、次元kの包含サイズと呼ぶ。また、<b(s),b(s2),……,b(sn)> を経歴値hにおけるAの境界ベクトルと呼ぶ。

【0054】
経歴値カウンタの値がhの拡張可能配列Aのある次元kのサイズ skが1つ拡張して、 sk のビットパターンサイズが次元kの包含サイズを超えたときにAは次元kの方向に拡張される。拡張分の部分配列の各次元のサイズはAと同一であり、したがって、拡張後の配列の各次元サイズは <s,……,sk-1,2*sk,sk+1,……,sn> となる(図2)。現在の経歴値カウンタの値が1インクリメントされ、その値h+1が次元kの経歴値テーブルHkに格納される。また、この新たな経歴値h+1におけるAの境界ベクトルは V=<b(s),……,b(sk-1),b(sk)+1,b(sk+1),……,b(sn)> となり、経歴値h+1の下に、Vが拡張次元kとともに経歴値テーブルHに記録される。

【0055】
配列の要素位置を指定するn次元座標 i=<i,i2,……,in> は以下のように経歴値hと座標パターンpの対にエンコードされる。境界ベクトルVはこのエンコードに使用されるとともにエンコードされた対を元のn次元座標にデコードするのにも使用される。

【0056】
経歴値hはiの各次元座標のビットパターンサイズ <b(i),b(i2),……,b(in)> について、経歴値Hk(b(ik))(1≦k≦n)の最大値となる。また、座標パターンpは各次元の添え字のビットパターンを1 long長の上位から順に配置して得られる。このエンコード結果はRDTに格納される。逆に、エンコード結果対(経歴値h,座標パターンp)からの元のn次元座標 i=(i1,i2,……,in)へのデコードは、まず、経歴値テーブルHについて、H[h]より要素iが属する部分配列の次元kを求める。p中の各次元の座標値ik(1≦k≦n)をH[h]の境界ベクトルにより、分離する。

【0057】
(タップルのエンコード、デコードの例)
たとえば、タップル (s,e) の場合、CVT1(s)、CVT2(e) を検索してタップルの座標(5,4)を引き当てる。5=1012、4=1002であり、b(5)=3、b(4)=3であるから、H1[3]=6とH2[3]=4を比較して、H1[3]>H2[3]。したがって、(5,4) は経歴値6の部分配列に含まれる。H[6]の境界ベクトルは <3,3> であり、(5,4) のエンコードは (6,101.1002)=(6,44) となる。ここで、座標パターン 101.1002 の‘.’は各次元の座標値パターンの境界位置を表す。逆にこのエンコードより、経歴値6について、その部分配列の所属次元1と境界ベクトル <3,3> を引き当てる。これより、44=1011002 の上位3ビット分が1次元目の添字、下位3ビット分が2次元目の添字になることがわかる。したがって、(6, 101.1002) は (5,4) にデコードされる。C1(5)=s、C2(4)=e より、元のタップル(s,e)となる。

【0058】
配列の拡張に対して柔軟に効率よく対応できる、〔発明が解決しようとする課題〕で述べた拡張可能配列の仕組みは、各次元の包含サイズを固定することなく、固定サイズ(long長)の座標パターンの各次元のビットパターンサイズの境界を次元拡張の状況に応じて柔軟に設定していることに活かされているといえる。このような、柔軟性を確保した上で、上述のエンコード、デコードの過程では掛け算や割り算を一切使用しないでビットシフトとマスク演算のみのレジスタ命令のみで、エンコードとデコードが可能である。このことはタップルのアクセス速度および検索速度が従来の手法に比べて高速であることを意味しており、非常に注目される。

【0059】
上記拡張可能配列の係数ベクトルの記憶コストは非常に大きく、O(n2)であった。本方式の境界ベクトルはこの係数ベクトルに対応するがその記憶コストはO(n)となり、大幅に削減できる。また、経歴値テーブルサイズは各次元長を <s,s2,……,sn> とすると、拡張可能配列の方式では、s1+s2+……+sn であるのに対して、log2s1+log2s2+……+log2snとなる。以上より、経歴値テーブルの記憶コストはCVT、RDT、および属性値テーブルなどのHPMDの他の構成要素に比べて、ほとんど無視できる。属性値テーブルのタップル数は検索の最適化プランを立てるのに必要とされるデータである。CVTと属性値テーブルは多次元データの属性値を扱うために必要なデータ構造であり、拡張可能配列には対応するデータ構造は存在しない。また、RDTは多次元データソースに実際に登録されているタップルのみのエンコード値を登録しており、〔発明が解決しようとする課題〕の多次元配列の疎配列性の欠点(b)を解消している、また、多次元配列の欠点(a)は拡張可能配列の使用により、解消されている。ただし、多次元データソースに登録されていないタップルは除外しており、記憶域を占めないので以後、HPMDにおける拡張可能配列を論理拡張可能配列と呼ぶ。この論理拡張可能配列の各次元サイズを論理サイズといい、各次元の属性値の数(カーディナリティ)で定まる各次元サイズを実サイズという。図2の論理拡張可能配列の論理サイズは [7,7] であり、各次元のカーディナリティはそれぞれ 5,5 であり、実サイズは [5,5] である(図2の論理拡張可能配列中、点線の範囲)。

【0060】
1.1 基本データ構造の実装
ここでは、1ワード64ビットの64ビットマシンを使用するとして、整数値32ビット、長整数値64ビットとする。

【0061】
1.1.1 CVTのデータ部の実装
図3は、CVTのデータ部のデータ構造を示す説明図である。CVTのキー部は各属性の属性値であるがデータ部は対応次元の配列添字であり、符号なし整数とする。この添字の最上位ビットの位置 (0~31) を求めて、この位置でその次元の経歴値テーブルの経歴値を知る必要がある。最上位ビットの位置を求めるには、1ビット右シフト演算を繰り返しながらカウントすればよいが、これには多くの時間が必要になる。そこで、データ部の上位5ビットにこの位置をあらかじめ計算して、セットしておく。下位27ビットには添字を格納する。これにより、各次元、最大で 2^27=134,217,728 までの属性値の種類(カーディナリティ)が扱える。

【0062】
次元iのデータ部の値をdとすると経歴値テーブルHiについて、Hi[d>>27] で次元iの経歴値が求まり、d&0x07FFFFFF で添字の値が求まる。

【0063】
1.1.2 境界ベクトルの実装
n次元境界ベクトルに対して、

【0064】
【数1】
JP0005419069B2_000002t.gif

【0065】
として、構造体 struct v_mask の配列vを境界ベクトルの実装とする。

【0066】
struct v_mask [ ];
たとえば、<8,10,7,20,15,4> の6次元境界ベクトルの時、配列vは、

【0067】
【数2】
JP0005419069B2_000003t.gif

【0068】
となる。

【0069】
タップルエンコード後の座標パターンのサイズを long長(64) 以内とするためには、各境界ベクトルの包含サイズのビットパターンを上位次元のものから順に並べてできるビットパターンのサイズ、すなわち各次元の包含サイズの和、v[0].sz+v[1].sz+……+v[n-1].sz は、long長(64) 以下でなければならない。64ビットの時には最大10次元の232までの各次元のサイズが表現できる。論理拡張可能配列のすべての次元サイズが最大232までの拡張を仮定すると各 v[i].sz(0≦i≦n-1) は最大5であり、10次元までの論理拡張可能配列が表現可能である。232以下の最大次元サイズが存在するときには最大次元数は10を超えることができる。

【0070】
1.1.3 経歴値テーブルHの実装

【0071】
【数3】
JP0005419069B2_000004t.gif

【0072】
なお、次元iの経歴値テーブルHiの実装は経歴値の配列であり、unsigned char Hi[ ]。

【0073】
1.1.4 属性値テーブルCiの実装

【0074】
【数4】
JP0005419069B2_000005t.gif

【0075】
ここで、mkeyはHPMDにおいて許されている属性のデータ型である。

【0076】
【数5】
JP0005419069B2_000006t.gif

【0077】
1.2 タップルのエンコーディング
タップルを r=<c1,c2,……,cn> として、rを <経歴値hmax,座標パターンp> の対にエンコードする。各次元のデータ部 di=CVTi(ci) (1≦i≦n) に対して、hmax は Hi[di>>27] (1≦i≦n) の最大値。d[ ] を di&MASK_B の配列とすると、pを生成するマクロは、

【0078】
【数6】
JP0005419069B2_000007t.gif

【0079】
となる。

【0080】
1.3 タップルのデコーディング
<経歴値h,座標パターンp> の対にエンコードされたタップルから、次元iの添字を求める。

【0081】
【数7】
JP0005419069B2_000008t.gif

【0082】
1.4 タップルの挿入
現在の論理拡張可能配列の各次元サイズが配列 unsigned int c_size[ ] に保持されているものとする。

【0083】
タップルの挿入(HPMD)のプログラムの一例を示せば次の通りである。なお、〔数8〕の外部データ(グローバルデータ)が、〔数9〕で使われる。

【0084】
【数8】
JP0005419069B2_000009t.gif

【0085】
【数9】
JP0005419069B2_000010t.gif

【0086】
〔数9〕は、〔数1〕〔数2〕で表される境界ベクトルを作成するルーチンである。このルーチンを使った、タップルの挿入プログラム(〔数8〕)の本体int insert_rec()の流れを、図4に示す。

【0087】
1.5 検索
n次元のHPMDの論理拡張可能配列について、タップルの次元iのある属性値avが指定されたとき、CVTi(av) の添字をkとする。次元iの添字kに対する基部分配列とは配列要素 (0,0,…,0,k,0,…,0) を含む部分配列である。このとき、次の顕著な性質がある。

【0088】
[タップルの次元iの添字kが指定されたとき、その基部分配列の経歴値をhとする。次元iの添字がkであるタップルは基部分配列および、hより大きい経歴値の部分配列で次元がiでない部分配列にのみ存在する。]
この性質を図2の2次元HPMDについて、図5に図示する。図5は、HPMDにおける属性値の検索範囲を示す説明図であり、(a)は経歴値5(次元1)の添字に対応する属性値の論理検索範囲を示し、(b)は経歴値3(次元2)の添字に対応する属性値の論理検索範囲を示す。なお、点線は論理拡張可能配列の実サイズを表す。

【0089】
上記性質に基づいて、タップルのある属性について与えられた属性値を持つタップルを検索する手続きを示す。タップルの検索(HPMD)のプログラムの一例を示せば次の通りである。〔数10〕はRDTを検索して、指定された次元iの属性値colvalを持つキー(エンコードされたタップル)を出力するルーチンである。このルーチンの流れを、図6に示す。

【0090】
【数10】
JP0005419069B2_000011t.gif

【0091】
2. チャンク化HPMD(C-HPMD)
1.5節で説明したHPMDにおける検索では検索範囲が大きく、検索対象の部分配列中のタップルは全検索を行う必要がある。また、図6に見るように検索対象の属性の次元や属性値が所属する部分配列の経歴値によって、検索範囲が大きく異なる。ここでは、論理拡張可能配列のランダムアクセス機能を生かして、高速な検索を行うためにHPMDのチャンク化を提案する。チャンク化されたHPMDを以後、C-HPMD(Chunked HPMD)と呼ぶ。HPMDのチャンク化は高速検索に資すると同時に、タップルのアドレス空間を格段に拡げて、大規模な多次元データを収容することができる。

【0092】
チャンクとは1辺が2k のn次元超立方体であり、kをチャンクのランクという。論理拡張可能配列はチャンクを単位として拡張される。HPMDにおけるタップルのエンコードは <経歴値,座標パターン> の対であったのに対して、C-HPMDではタップルは <チャンク番号,チャンク内座標パターン> にエンコードされる。HPMDの各配列要素をチャンクに対応させると、RDTに付属するデータ構造としてCBMと呼ぶビットマップを保持する以外はC-HPMDはHPMDとほぼ同等のデータ構造である。また、HPMDに関する1節の説明はタップルのエンコーディング方式と検索方式以外はほぼそのまま適用できる。

【0093】
なお、C-HPMDでもHPMDと同様、CVTに必要な機能は、キー指定によるランダムアクセス機能とキーの値順による順次的アクセス機能であり、RDTに必要な機能は、キー指定によるランダムアクセス機能である。よって、CVTおよびRDTは、B+木に限らず、上記の機能をそれぞれ実現するキー編成のデータ構造であればよい。もちろん、B+木であれば、上記の機能をそれぞれ効率よく実現でき、C-HPMDの性能を高めることができる。

【0094】
図7に図2の配列要素をチャンクにそのまま置き換えたときのC-HPMDを示す。図7は、C-HPMDにおける論理拡張可能配列とチャンク番号との関係を示す説明図である。なお、論理拡張可能配列中の数字はチャンク番号を表す。

【0095】
2.1 タップルエンコーディング
各次元の属性値のタップルを <c,c2,……,cn> として、このタップルを <チャンク番号,チャンク内座標パターン> の対に変換する手順を以下に示す。

【0096】
(a) cj (j=1,…,n) を次元jのCVTjにより次元jの添字ijに変換
(b)タップル座標 <i,i2,……,in> からチャンク座標 dp=<p,p2,……,pn> への変換
pj = ij>> k (j=1,…,n) : ij をkビット右シフト
(c)タップルの経歴値hを求める
各次元の添字 ij = CVTj(cj) (1≦j≦n)に対して、
経歴値hは Hj[ij>>27] (1≦j≦n)の最大値
(d)経歴値hのチャンク部分配列の先頭チャンク番号を求める

【0097】
【数11】
JP0005419069B2_000012t.gif

【0098】
(e)チャンク座標dpからのチャンク番号の計算
・チャンク座標から所属チャンク部分配列の経歴値hを求める
・チャンク番号cnを求めるマクロget_chunkを計算

【0099】
【数12】
JP0005419069B2_000013t.gif

【0100】
〔例〕チャンク座標 (5,4) を含むチャンクのチャンク番号の計算

【0101】
【数13】
JP0005419069B2_000014t.gif

【0102】
(チャンク内マスクパターン)
ランクkのn次元チャンクの場合、マスクパターンを含むチャンク情報をグローバルに1つ定義する。

【0103】
【数14】
JP0005419069B2_000015t.gif

【0104】
(f)タップル座標 <i,i2,……,in> からチャンク内座標 dq=<q,q2,……,qn> への変換

【0105】
【数15】
JP0005419069B2_000016t.gif

【0106】
(g)タップル座標 d=<i,i2,……,in> からチャンク内座標パターンcpへの変換

【0107】
【数16】
JP0005419069B2_000017t.gif

【0108】
(h)タップルのエンコーディング
<cn,cp>
2.2 タップルへのデコーディング
<チャンク番号,チャンク内座標パターン> の対から元のタップルの座標への変換操作である。

【0109】
(チャンク座標への変換)
チャンク番号pより所属チャンク部分配列(基チャンク部分配列)の経歴値hを求める。これは、pのビットパターンサイズに相当する(図7)。hとpからチャンク座標 dp[ ] を求める。

【0110】
【数17】
JP0005419069B2_000018t.gif

【0111】
(チャンク内座標への変換)
チャンク内での座標パターンをqとしてチャンク内座標 dq[ ] を求める。

【0112】
【数18】
JP0005419069B2_000019t.gif

【0113】
(タップルへのデコーディング)
元のタップルの次元iの座標は(dp[i]<【0114】
〔例〕チャンクのランクを4として、図7における <チャンク番号44,チャンク内座標パターン55>のデコーディング。
44のビットパターンサイズは6。したがって、当該タップルを含むチャンク部分配列の経歴値hは6。その、h=5 の境界ベクトルは <2,3>。

【0115】
【数19】
JP0005419069B2_000020t.gif

【0116】
(経歴値hのチャンク部分配列の下限座標と上限座標)

【0117】
【数20】
JP0005419069B2_000021t.gif

【0118】
2.3 RDTの構成
タップルのエンコード結果 <チャンク番号,チャンク内座標パターン> の対はRDT(B+木)にキーとして登録される。C-HPMDが疎な場合、空のチャンクが多くを占めることを考慮して、検索のオーバヘッドを回避するために、1次元のビットマップCBMをRDTに付随させる。CBMはチャンク配列が拡張されるたびに拡張され、常に、チャンク総数のビット数を持つ。

【0119】
unsigned long cbm[ ];
先頭ビットを位置0として、チャンク番号の位置に、当該チャンクに、タップルが登録されていれば、1がセットされ、登録されていない(空)のときは0がセットされる。CBMは主メモリ上に置かれる。指定されたチャンク番号のチャンクを検索するときには、まず、CBMの当該ビットを調べて1の時にのみ実際にRDTを検索する。これにより、RDTを無駄に検索することを回避している。CBMの検索は、64ビットマシンの場合、次のマクロにより高速に行われる。

【0120】
【数21】
JP0005419069B2_000022t.gif

【0121】
2.4 C-HPMDの検索
「ある属性について、指定された属性値を持つタップルを検索する(スライス検索)」
属性の次元をiとして、属性値が所属するチャンク部分配列(基チャンク部分配列という)の経歴値をh0とする。当該タップルを含む可能性のあるチャンク(以下、候補チャンクという)の番号を順次計算により求めながら候補チャンク内を全検索することを繰り返す。

【0122】
基チャンク部分配列の候補チャンクを検索した後、h0より大きい経歴値のチャンク部分配列で所属次元がiでないものを順次検索する。タップルの検索(C-HPMD)のプログラムの一例を示せば次の通りである。なお、〔数22〕の外部データ(グローバルデータ)が、〔数23〕で使われる。

【0123】
【数22】
JP0005419069B2_000023t.gif

【0124】
【数23】
JP0005419069B2_000024t.gif

【0125】
〔数22〕に示すsearch_tuple()は、指定された次元iの属性値を有するタップルを検索する。具体的には、まず、CVTiについて、指定された属性値を検索する。図3のフォーマットに従って、次元iのチャンク座標p、およびチャンク内座標qを求める。また、次元iの経歴値テーブルHiを参照して、基チャンク部分配列の経歴値h0を求める。その後、経歴値h0のチャンク部分配列から始めて、次元i以外の次元の部分配列について、その経歴値h、および、i,p,qを引数として、search_subarray()を呼び出して、経歴値hのチャンク部分配列について、検索対象の候補となるチャンクを検索することを、hをインクリメントしながら繰り返す。

【0126】
そして、search_subarray()では、受け取った引数に基づいて、現在の拡張可能チャンク配列の実サイズ座標を取得して、実際に検索が必要な各次元の上現および下限を定める。その後、再帰的に、当該チャンクを検索して、検索結果のタップルを出力する〔数23〕の再帰ルーチンsearch_chunks()を呼び出す。

【0127】
さらに、〔数23〕のsearch_chunks()は、チャンク座標格納用配列wc、検索対象チャンク部分配列の経歴値h、チャンク座標p、チャンク内座標q、および再帰の深さlevを引数として受け取る。lev の初期値は0であり、再帰呼び出しのたびにlevはインクリメントされる。

【0128】
(S1)再帰の深さlevをチェックする。再帰の深さlevが次元数nに対して、n-1に達していないときは、(S4)へ。達したときには、次の(S2)へ。

【0129】
(S2)検索対象チャンク部分配列はチャンクの1次元配列となる。この1次元配列中のチャンクに対して、以下の(S3)を繰り返す。

【0130】
(S3)渡されたチャンク座標wcからチャンク番号を計算する。さらに、このチャンク番号のチャンク内にタップルが存在するかどうかを調べるために、ビットマップCBMをチェックする。存在する場合のみ、ルーチンget_tuples()を呼び出す。get_tuple()では、RDT中の当該チャンクを検索した後、チャンク内を順次チェックして当該タップルを出力する。その後、wcを次のチャンクを指示するように更新する。

【0131】
(S4)座標値wc[lev]を更新して、再帰の深さlevを1インクリメントして、search_chunks()を再帰的に呼び出す。

【0132】
2.5 チャンクのランク値の決定について
チャンクのランク値kは記憶コストと検索時間コストに大きく影響する。すなわち、kが大きいほどCBMのサイズが減少する。しかし、チャンク内のオフセット(タップル)は全検索する必要があるので、検索時間コストは逆に増大する。このトレードオフはチャンク内のタップルの平均密度を勘案して、決定する必要があるが、kを変更すれば、CBMとRDTの再編成を必要とするため、実時間処理を阻害する。

【0133】
3. 先行研究との比較
前掲の(非特許文献1)~(非特許文献8)は、拡張可能配列に関する研究であるが、経歴・オフセット法や経歴・パターン法のタップルエンコードの考え方は一切表れていない。下記に、経歴・オフセット法に関連する先行研究論文のリストを示す。すべて、本発明者等による研究である(文献[9]~[16])。なお、これらの研究の一部はすでに、PCT出願しており(出願番号:05805308.1)、現在審査中である。これらの研究は本発明と同様に、拡張可能配列の概念を基盤としており、タップルのエンコード方式を経歴・オフセット法と呼んでいる。両方式ともに、n次元タップルの各次元の属性値はCVTにより、拡張可能配列の添字の座標に変換される。変換された座標に対して、経歴・オフセット法では、それが含まれる拡張可能配列の部分配列の拡張経歴値hと部分配列のアドレス関数により変換された、部分配列内での位置(オフセット)を表す単一値oの対 <h,o> にエンコードされたのに対して、本方式(経歴・パターン方式)では、経歴値hと各次元の添字値のビットパターンを次元順に固定長の記憶域に順次並べたパターンpの対 <h,p> にエンコードされる。

【0134】
両方式の長所、短所を以下に比較する。以下では、経歴・パターン法をhp法、経歴・オフセット法をho法と表記して、タップルの次元数をnとする。

【0135】
(a)記憶領域の消費
hp法の方が消費が少ない。ho法において必要であった、〔発明が解決しようとする課題〕で説明した係数ベクトル(サイズのオーダ:O(n2))が不要。また、ho法では経歴値のサイズは4バイト程度必要であったのに対して、hp法では1バイトで十分(2256の論理拡張可能配列の空間が表現可能)である。したがって、タップルのエンコード値を収容するRDTのサイズが減少し、記憶領域の消費抑制に貢献できる。

【0136】
(b)論理空間の消費
hp法では論理拡張可能配列の論理サイズは実サイズに比べて、最悪の場合2n 倍の大きさになり得る(論理拡張可能配列の論理サイズ、実サイズについては1節を参照のこと)。すなわち、同じタップル数に対して、最悪の場合、論理サイズのビット数は実サイズのビット数より、nビット余分に消費する。また、最良の場合は論理サイズと実サイズは一致し、余分な消費はない。これに対して、ho法では論理拡張可能配列の論理サイズと実サイズは常に一致しており、論理アドレス空間の無駄な消費は起こらない。

【0137】
(c)タップル挿入・検索速度
ho法ではタップル挿入時に必要なエンコーディングにn-2回の乗算と加算が必要であり、タップルの検索時にはタップルが指定された属性値を持つかどうかのチェックに2回の割り算を必要とする。これに対して、hp法では、これらの処理はすべて、機械語命令のマスク命令とシフト命令で行うことができ、この相違がhp法での挿入・検索速度の向上に大きく貢献し得る。

【0138】
逆に、拡張可能配列の部分配列はho法ではn-1次元であるのに対して、hp法ではn次元である。したがって、タップルの検索範囲はhp法の方が大きく、この点ではhp法は不利である。

【0139】
次に、2つのエンコード方式をチャンク化した場合の方式をそれぞれc-ho法、c-hp法と表記して、c-ho法、c-hp法も含めて比較する。

【0140】
(a')記憶領域の消費
c-ho法、c-hp法の両方式ともチャンク単位に経歴値テーブル(H)および各次元の経歴値テーブル(Hi)が確保されるため、これらのテーブル領域サイズのho法およびhp法の場合と比べて減少するが、その減少度はほぼ同一である。CVTi、RDTおよび他のデータ構造サイズはho法およびhp法の場合とほぼ同一である。c-ho法とc-hp法の比較では、c-hp法でも係数テーブルが不要な分c-ho法より有利である。しかし、c-ho法およびc-hp法ともにタップルのエンコード結果の対の第1項は経歴値ではなく、チャンク番号であるので、エンコード結果のサイズに変わりはない。したがって、RDTのサイズも同一である。

【0141】
(b')論理空間の消費
上記(b)のho法とhp法の比較がそのまま、c-ho法、c-hp法についても当てはまる。しかし、チャンク化の利点の一つは、エンコードされるタップルの論理アドレス空間の拡大である。すなわち、チャンクのランクkに対して、チャンク化しない場合に比べてこの論理アドレス空間はk倍に拡大する。一般には論理拡張可能配列はかなり疎であることが多いので、kの値をある程度大きくできる。c-hp法はc-ho法に比べて論理アドレス空間の使用率が低下するが、チャンク化により、論理アドレス空間を格段に拡大可能であり、大規模なタップル集合にもある程度まで対応し得る。もちろん、チャンク化による論理空間の拡大は“ただ”であり、拡大しても、実記憶量に影響はない。

【0142】
(c')タップル挿入・検索速度
ho法とhp法における、上記(c)での「タップルが指定された属性値を持つかどうかのチェック」の時間的コストの比較はそのまま、c-ho法、c-hp法についても当てはまる。hp法はho法に比べて、タップルの検索範囲が大きいことが難点であったが、チャンク化によるc-ho法とc-hp法では解消される。すなわち、指定された属性値のタップルを含み得るチャンクの番号のみを計算で求めることにより、検索ターゲットのチャンク集合の範囲を大幅に絞り込むことが可能である。この範囲絞り込みの効果はc-ho法でもc-hp法でも同じであり、検索ターゲットのチャンク集合の範囲は同一である。また、ho法とhp法ともに検索速度に関して“経歴値依存性”がある。すなわち、1.5節で述べた、hp法の性質はそのまま、ho法においても当てはまり、経歴値が大きいほど、検索範囲を限定することができる。指定された属性値に対応する基部分配列の経歴値が大きいほど検索対象の部分配列集合は少ないが、この経歴値が小さいほど多くの部分配列を検索する必要がある。チャンク化を行った場合、この検索速度の“経歴値依存性”は解消される。すなわち検索対象属性が同じ場合、どのような属性値の検索でもその検索速度はほぼ一定である。

【0143】
〔関連先行技術研究文献〕
[9] M.Kuroda, N.Azuma, K.M.A.Hasan, T.Tsuji, K.Higuchi, “An Implementation Scheme of Relational Tables”, Proc. of International Conference of Data Engineering Workshops, 2005.
[10] K.M.A.Hasan, M.Kuroda, N.Azuma, T.Tsuji, K.Higuchi, “An Extendible Array Based Implementation of Relational Tables for Multidimensional Databases”, 7th International Conference on Data Warehousing and Knowledge Discovery, pp.233-242, 2005.
[11] K.M.A.Hasan, T.Tsuji, K.Higuchi, “A parallel implementation scheme of relational tables based on multidimensional extendible array”, International Journal of Data Warehousing and Mining, Vol.2, No.4, pp.66-85, 2006.
[12] K.M.A.Hasan, T.Tsuji, K.Higuchi, “An Efficient Implementation for MOLAP Basic Data Structure and Its Evaluation”, Proc. of Int'l Conference on Database Systems for Advanced Applications (DASFAA2007), pp.288-299, 2007.
[13] Tatsuo Tsuji, Masayuki Kuroda, Ken Higuchi, “History offset implementation scheme for large scale multidimensional data sets”, Proc. of the 2008 ACM Symposium on Applied Computing (SAC2008), pp.1021-1028, 2008.
[14] Dong Jin, Tatsuo Tsuji, Takayuki Tsuchida, Ken Higuch, “An Incremental Maintenance Scheme of Data Cubes”, Proc. of Int'l Conference on Database Systems for Advanced Applications (DASFAA 2008), pp.172-187, 2008.
[15] Tatsuo Tsuji, Dong Jin, Ken Higuchi, “Data Compression for Incremental Data Cube Maintenance”, Proc. of Int'l Conference on Database Systems for Advanced Applications (DASFAA 2008), pp.682-685, 2008.
[16] 土田隼之, 都司達夫, 樋口健, “MOLAP用多次元配列構築のためのバッファリング方式”, 日本データベース学会論文誌, Vol.7, No.1, pp.19-24, 2008.
4. データベース装置
つづいて、図1を参照しながら、上述した関係テーブルの記憶、操作方式を実現するデータベース装置の一構成例について説明する。図1は、本発明の一実施の形態に係るデータベース装置1の構成の概略を示す機能ブロック図である。

【0144】
図1に示すように、データベース装置1は、データ格納部(データベース記憶部)10、補助テーブル部(データベース記憶部)20、テーブル管理部30、入出力部40を備えて構成されている。

【0145】
データ格納部10は、ディスク装置2上に、CVT(第1データ、第1のB+木データ)11、RDT(第2データ、第2のB+木データ、要素位置データ、要素位置B+木データ)12、および各種補助テーブル(属性毎経歴値テーブル21、経歴値テーブル22、属性値テーブル23)を格納している。

【0146】
RDT12は、関係テーブルの各タップルに対応する拡張可能配列の要素の位置を示す位置情報をキー値として登録したデータである。具体的には、本実施の形態では、上記位置情報は、要素が属する拡張可能配列の区画の位置を示す区画位置情報と、区画内における要素の位置を示す、当該タップルの各属性の属性値に一意に対応した値を所定の属性順に並べた座標情報と、を含む情報である。

【0147】
(1)HPMD法
以下、区画が拡張可能配列の部分配列である場合について説明するが、この場合、RDT12は、関係テーブルのタップルに対応する拡張可能配列の要素が属する部分配列の経歴値(区画位置情報)、および、当該タップルの各属性値に対応する上記拡張可能配列の各添字のビットパターンを所定の属性順に並べた座標パターン(座標情報)、の2項組表現をキー値として登録したB+木データである。

【0148】
CVT11は、関係テーブルの属性毎に設けられ、属性の各属性値から拡張可能配列の添字に変換するためのB+木データである。

【0149】
ここで、関係テーブルがn個の属性からなる場合、データ格納部10には、n個のCVT(key-subscript ConVersion Tree)とRDT(Real Data Tree)とからなるn+1個のB+木のデータが格納されている。なお、データベースが複数の関係テーブルから構成される場合、このn+1個のB+木のセットが複数存在することになる。

【0150】
なお、CVT11は、キー指定によるランダムアクセス機能とキーの値順による順次的アクセス機能を実現するキー編成のデータ構造であればよく、RDT12は、キー指定によるランダムアクセス機能を実現するキー編成のデータ構造であればよい。本実施の形態では、この2つの機能を効率よく実現し、HPMDの性能を高めるため、CVT11およびRDT12にB+木データを採用する。

【0151】
補助テーブル部20は、属性毎経歴値テーブル21、経歴値テーブル22、属性値テーブル23を、主メモリ3上に保持している。

【0152】
なお、CVT11、RDT12、および補助テーブル群(属性毎経歴値テーブル21、経歴値テーブル22、属性値テーブル23)は、データ格納部10に格納されている。データ格納部10は、ハードディスク等のディスク装置2上に配置されている。属性毎経歴値テーブル21、経歴値テーブル22、属性値テーブル23の補助テーブル群は、データベース装置1の処理開始時にディスク装置2から読み出されて主メモリ3上の補助テーブル部20に保持され、データベース処理中に変更が加えられた場合に、ディスク装置2上のデータ格納部10の対応部分に書き戻される。

【0153】
属性毎経歴値テーブル21は、属性毎の配列拡張の時間的順序を表す経歴値の1次元配列である。経歴値テーブル22は、経歴値に対応する配列拡張した属性の次元、および、当該経歴値に対応する拡張部分配列の任意の要素について、属性毎に拡張可能配列における対応次元の添字の表現に要するビット数を要素とする境界ベクトルを記録している。属性値テーブル23は、拡張可能配列の添字毎にその添字に対応する属性値および該属性値を持つすべてのタップル数を記録している。

【0154】
テーブル管理部30は、タップル検索部(タップル検索手段)31、タップル挿入部(タップル挿入手段)32、タップル削除部(タップル削除手段)33を備えている。

【0155】
タップル検索部31は、タップルの検索の処理を行う。タップル挿入部32は、タップルの挿入の処理を行う。タップル削除部33は、タップルの削除の処理を行う。特に、タップル挿入部32、タップル削除部33は、CVT11、RDT12、属性毎経歴値テーブル21、経歴値テーブル22、属性値テーブル23に対して、必要な保守を行う。

【0156】
具体的には、タップル検索部31は、ある属性値を持つタップルを検索するとき、属性値が属する属性のCVT11を用いて、該属性値を拡張可能配列の添字に変換し、当該次元の経歴値テーブルより経歴値を求めた後、RDT12を参照して、2項組表現されたキー値中の座標パターンに含まれる、属性の属性値に対応するビットパターンが、上記添字のビットパターンと一致するタップルを抽出する。

【0157】
ここで、入出力部40を介してユーザから得た検索要求は、タップル検索部31により、<経歴値、座標パターン>対であるキー値の集合として検索されるが、キー値は本データベースにおけるタップルの内部表現であり、ユーザには理解できない。そこで、キー値-属性値逆変換部34は、この検索結果をユーザが理解できる表現として返すために、2項組表現のキー値から属性値の組としてのタップルに逆変換する。具体的には、タップル検索部31が抽出した<経歴値、座標パターン>の2項組から、各属性の属性毎経歴値テーブル21、経歴値テーブル22、属性値テーブル23を参照してデコードを行って、拡張可能配列の各属性の添字に変換し、属性毎に得た配列添字値から得た属性値を、属性順に並べてタップルを得る。

【0158】
また、タップル挿入部32は、新たな属性値を持つタップルを挿入するとき、配列拡張が必要である場合には、属性値が属する属性の部分配列を追加するとともに、経歴値をインクリメントして当該属性の属性毎経歴値テーブル21に登録する基本データ拡張処理を行い、配列拡張が不必要である場合、および、配列拡張が必要である場合に上記基本データ拡張処理を行った後、属性値を属性値テーブル23およびCVT11に登録するとともに、当該タップルの各属性値に対応する座標パターンを生成して、経歴値および座標パターンの2項組表現をキー値としてRDT12へ挿入する。

【0159】
また、タップル削除部33は、タップル挿入部32がタップルを検索する際のアルゴリズムを適用して当該タップルを同定した後、タップル削除に伴うRDTやCVT等のHPMDデータ構造に対して必要な削除とメンテナンスを行う。

【0160】
なお、テーブル管理部30は、データベースの管理全般を行うものである。よって、タップル検索部31などのように個別に機能ブロックとして明記しないが、データベースの管理に付随する処理なども行うことは言うまでもない。

【0161】
入出力部40は、データベース装置1を操作するためのインターフェイスである。すなわち、入出力部40は、データベース装置1に対して、ユーザが直接、処理要求を入力して、データベース装置1からその結果を出力するためのユーザインターフェイス、および、それらの送受信をネットワーク経由で制御するための通信インターフェイスである。

【0162】
(2)C-HPMD法
なお、2節で説明したC-HPMD法の場合には、上記データ記録システム1を以下のように変更すればよい。

【0163】
区画がチャンク化拡張可能配列の部分配列である場合、RDT12は、関係テーブルのタップルに対応するチャンク化拡張可能配列の要素が属するチャンクのチャンク番号(区画位置情報)、および、当該タップルの各属性値に対応する上記チャンク化拡張可能配列の当該チャンクにおける各添字のビットパターンを所定の属性順に並べたチャンク内座標パターン(座標情報)、の2項組表現をキー値として登録したB+木データである。

【0164】
CVT11は、関係テーブルの属性毎に設けられ、属性の各属性値からチャンクを要素とするチャンク化拡張可能配列の添字に変換するためのB+木データである。

【0165】
なお、C-HPMD法でもHPMD法と同様、CVT11は、キー指定によるランダムアクセス機能とキーの値順による順次的アクセス機能を実現するキー編成のデータ構造であればよく、RDT12は、キー指定によるランダムアクセス機能を実現するキー編成のデータ構造であればよい。本実施の形態では、この2つの機能を効率よく実現し、C-HPMDの性能を高めるため、CVT11およびRDT12にB+木データを採用する。

【0166】
属性毎経歴値テーブル21は、属性毎のチャンク配列拡張の時間的順序を表す経歴値の1次元配列である。経歴値テーブル22は、チャンク番号に対応するチャンク配列拡張した属性の次元、および、当該経歴値に対応する拡張チャンク部分配列中の任意のチャンクについて,属性毎にチャンク拡張可能配列における対応次元の添字の表現に要するビット数を要素とする境界ベクトルを記録している。属性値テーブル23は、チャンク化拡張可能配列の添字毎にその添字に対応する属性値および該属性値を持つすべてのタップル数を記録している。

【0167】
ここで、C-HPMD法の場合、主メモリ3上のテーブル管理部30には、CBM35が保持される。CBM35は、チャンク総数と同じビット数を持ち、チャンク番号に対応するビット位置に、当該チャンクにタップルが登録されていれば“1”、登録されていなければ“0”がセットされる1次元ビットマップである。

【0168】
また、タップル検索部31は、ある属性値を持つタップルを検索するとき、属性値が属する属性のCVT11を用いて、該属性値をチャンク化拡張可能配列の添字に変換し、当該次元の経歴値テーブルより経歴値を求めた後、RDT12を参照して、2項組表現されたキー値中のチャンク内座標パターンに含まれる、属性の属性値に対応するビットパターンが、上記添字のビットパターンと一致するタップルを抽出する。タップル検索部31は、指定されたチャンク番号のチャンクを検索する際、CBM35の当該ビットを調べ、“1”の時にのみRDT12を検索する。

【0169】
ここで、キー値-属性値逆変換部34は、HPMD法の場合と同様に、タップル検索部31が抽出した<チャンク番号、チャンク内座標パターン>の2項組から、各属性の属性毎経歴値テーブル21、経歴値テーブル22、属性値テーブル23を参照してデコードを行って、チャンク化拡張可能配列の各属性の添字に変換し、属性毎に得た配列添字値から得た属性値を、属性順に並べてタップルを得る。

【0170】
また、タップル挿入部32は、新たな属性値を持つタップルを挿入するとき、チャンク配列拡張が必要である場合には、属性値が属する属性のチャンク部分配列を追加するとともに、経歴値をインクリメントして当該属性の属性毎経歴値テーブル21に登録する基本データ拡張処理を行い、チャンク配列拡張が不必要である場合、および、チャンク配列拡張が必要である場合に上記基本データ拡張処理を行った後、属性値を属性値テーブル23およびCVT11に登録するとともに、当該タップルの各属性値に対応するチャンク内座標パターンを生成して、チャンク番号およびチャンク内座標パターンの2項組表現をキー値としてRDT12へ挿入する。

【0171】
ここで、C-HPMDの場合、RDT12には<チャンク番号,チャンク内座標パターン>を登録するが、属性毎経歴値テーブル21にはHPMDの場合と同様に経歴値を登録する。C-HPMDの場合、区画の単位はチャンクであり、区画中のタップルの同定はRDT12に格納されるキー値、すなわち、チャンクである区画の位置情報であるチャンク番号とその区画(チャンク)内の座標パターンの対で行われる。つまり、属性毎経歴値テーブル21に書き込む経歴値は、拡張時に確保されるチャンク部分配列を同定するのに使われ、このチャンク部分配列中の区画(チャンク)の同定、すなわち、チャンク番号の同定には、HPMDにおける区画(拡張可能配列の部分配列)中のタップル同定の方法が、タップルをチャンクと見立てることにより、大略そのまま適用される。

【0172】
経歴値を属性毎経歴値テーブル21に書き込む操作は、HPMDでも、C-HPMDでも同様である。HPMDとC-HPMDとの違いは、拡張可能配列の基本要素の単位だけの違いであり、HPMDの場合にはタップルに1対1に対応する配列要素が拡張の基本要素であり、C-HPMDの場合には配列要素の集まりであるチャンクが拡張の基本要素となる。

【0173】
最後に、データベース装置1は、ワークステーションやパーソナルコンピュータ等の汎用のコンピュータをベースに構成できる。よって、データベース装置1の各ブロック、特にテーブル管理部30は、次のようにCPUを用いてソフトウェアによって実現することができる。なお、データベース装置1は、その機能を複数の装置に分散させたシステムとして構成することもできる。

【0174】
すなわち、データベース装置1は、各機能を実現する制御プログラムの命令を実行するCPU(central processing unit)、上記プログラムおよびデータベースデータを格納した二次記憶装置(磁気ディスク装置)、上記プログラムおよびデータベースデータを展開するRAM(random access memory)などを備えている。そして、本発明の目的は、上述した機能を実現するソフトウェアであるテーブル管理部30の制御プログラム(データベースの管理プログラム)のプログラムコード(実行形式プログラム、中間コードプログラム、ソースプログラム)をコンピュータで読み取り可能に記録した記録媒体を、上記データベース装置1に供給し、そのコンピュータ(またはCPUやMPU)が記録媒体に記録されているプログラムコードを読み出し実行することによって、達成可能である。

【0175】
上記記録媒体としては、例えば、磁気テープやカセットテープ等のテープ系、フロッピー(登録商標)ディスク/ハードディスク等の磁気ディスクやCD-ROM/MO/MD/DVD/CD-R等の光ディスクを含むディスク系、ICカード(メモリカードを含む)/光カード等のカード系、あるいはマスクROM/EPROM/EEPROM/フラッシュROM等の半導体メモリ系などを用いることができる。

【0176】
また、データベース装置1を通信ネットワークと接続可能に構成し、上記プログラムコードを通信ネットワークを介して供給してもよい。この通信ネットワークとしては、特に限定されず、例えば、インターネット、イントラネット、エキストラネット、LAN、ISDN、VAN、CATV通信網、仮想専用網(virtual private network)、電話回線網、移動体通信網、衛星通信網等が利用可能である。また、通信ネットワークを構成する伝送媒体としては、特に限定されず、例えば、IEEE1394、USB、電力線搬送、ケーブルTV回線、電話線、ADSL回線等の有線でも、IrDAやリモコンのような赤外線、Bluetooth(登録商標)、802.11無線、HDR、携帯電話網、衛星回線、地上波デジタル網等の無線でも利用可能である。なお、本発明は、上記プログラムコードが電子的な伝送で具現化された、搬送波に埋め込まれたコンピュータデータ信号の形態でも実現され得る。

【0177】
本実施の形態は本発明の範囲を限定するものではなく、本発明の範囲内で種々の変更が可能である。
【産業上の利用可能性】
【0178】
本発明は関係データベースに広く適用できるものであり、特に、データウエアハウジングやデータマイニング分野など、大規模関係テーブルの高速検索処理が必要な産業上の多くの分野に好適である。記憶効率も優れている。また、本発明は、オブジェクトIDの導入により、関係テーブルのみではなく、複合オブジェクトの効率よい実装方式も提供できる。さらに、大規模なXML(EXtensible Markup Language)文書の効率よい記憶構造としての使用の他、動的に大きさが変化する多次元データ集合一般の実装にも応用できる。
【符号の説明】
【0179】
1 データベース装置
2 ディスク装置
3 主メモリ
10 データ格納部(データベース記憶部)
11 CVT(第1データ、第1のB+木データ)
12 RDT(第2データ、第2のB+木データ、要素位置データ、要素位置B+木データ)
20 補助テーブル部(データベース記憶部)
21 属性毎経歴値テーブル
22 経歴値テーブル
23 属性値テーブル
30 テーブル管理部
31 タップル検索部(タップル検索手段)
32 タップル挿入部(タップル挿入手段)
33 タップル削除部(タップル削除手段)
34 キー値-属性値逆変換部(キー値-属性値逆変換手段)
35 CBM
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9