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

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

国内特許コード P110005055
掲載日 2011年8月18日
出願番号 特願2009-041176
公開番号 特開2010-198217
登録番号 特許第5419069号
出願日 平成21年2月24日(2009.2.24)
公開日 平成22年9月9日(2010.9.9)
登録日 平成25年11月29日(2013.11.29)
発明者
  • 都司 達夫
出願人
  • 国立大学法人福井大学
発明の名称 データベース装置、データベースの管理方法、データベースのデータ構造、データベースの管理プログラムおよびそれを記録したコンピュータ読み取り可能な記録媒体 コモンズ
発明の概要

【課題】タップルの追加と高速検索が可能であり、ディスクスペースを効率良く使用する。
【解決手段】データベース装置1は、各属性値から拡張可能配列の添字に変換するためのCVT11と、タップルに対応する拡張可能配列の要素が属する部分配列の経歴値及びタップルの各属性値に対応する拡張可能配列の各添字のビットパターンを属性順に並べた座標パターンの2項組表現をキー値として登録したRDT12と、属性毎の配列拡張の時間的順序を表す経歴値を登録した属性毎経歴値テーブル21と、経歴値に対応する配列拡張した属性の次元、及び、当該経歴値に対応する拡張部分配列の任意の要素について、属性毎に拡張可能配列における対応次元の添字の表現に要するビット数を要素とする境界ベクトルを登録した経歴値テーブル22と、拡張可能配列の添字毎に対応する属性値及び該属性値を持つ全てのタップル数を登録した属性値テーブル23とを格納している。
【選択図】 図1

従来技術、競合技術の概要


多次元データとは複数種類のデータの組(以下、タップルという)の集合であり、代表的な多次元データとして関係データベースにおける関係テーブルがあげられる。近年、情報処理分野の多様化と拡大に応じて、その重要性は急激に増大している。多次元データを計算機内部において記憶し、処理するための効率よい方式を提供することは、多次元情報処理を必要とする諸分野の発展に基本レベルで貢献し得ると考えられる。ここでは、計算機内部での記憶サイズおよび検索効率において、きわめて優れた、多次元データの処理方式を提案する。多次元データの例として、以降では、広く知られている関係データベーステーブルを取り上げて、説明する。



関係データベースは、図8のような関係テーブルの集合であり、関係テーブルはその中のタップルの集合である。その検索は属性名や検索の条件を指定することにより、行われる。



このような、関係テーブルは通常2次記憶上に置かれ、各タップルは入力された順に逐次、配置される。したがって、次のような欠点がある。



(1)例えば、年齢が23のタップルを検索する場合、テーブル中のすべてのタップルをメモリ上にロードして年齢属性をチェックする必要がある。したがって、検索時間が大きくなる。



(2)例えば、出身地が福井のタップルは数多く現れ、文字列「福井」を重複して多く格納する必要がある。したがって、ディスク使用量が大きくなる。



このような欠点を回避するための方法として、多次元配列を使用することが考えられる。ここで、配列の各次元はテーブルの属性に対応し、配列の要素は対応するタップルを表す。



図9は、配列による関係テーブルの表現の一例を示す説明図である。



この時、年齢が23のタップル集合は「年齢」次元の値が23の平面上に空でない配列要素として、存在する。配列要素[*,*,23]の番地はアドレス関数により高速に求めることができる。したがって、(1)の欠点は回避される。また、各次元の値は値順にソートされて並べられ、1度しか現れないので、(2)の欠点も回避される。



なお、拡張可能配列に関する先行技術文献としては、以下のものがある。

産業上の利用分野


本発明は、関係データベースを用いるデータベースに関するものであり、詳細には、データベース装置、データベースの管理方法、データベースのデータ構造、データベースの管理プログラムおよびそれを記録したコンピュータ読み取り可能な記録媒体に関するものである。

特許請求の範囲 【請求項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項に記載のデータベース装置を動作させるデータベース管理プログラムであって、コンピュータを上記の各手段として機能させるためのデータベース管理プログラム。
【請求項12】
請求項11に記載のデータベース管理プログラムを記録したコンピュータ読み取り可能な記録媒体。
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2009041176thum.jpg
出願権利状態 登録
ライセンスをご希望の方、特許の内容に興味を持たれた方は、下記までご連絡ください。


PAGE TOP

close
close
close
close
close
close
close