(57)【特許請求の範囲】
【請求項１】
コンピュータによって実行されるデータベースの処理方法において、
前記コンピュータが、記録媒体から又はオンライン転送データとして、複数のキー値を有する少なくとも１以上の項目を有する、複数のレコードからなるオリジナルデータを取得し、前記オリジナルデータに対し、前記項目における前記複数のキー値にＩＤを一意に割り当て、前記キー値と前記ＩＤとを１つのノードとし、前記各ノードから構成される階層構造を作成し、さらに、前記各ノードへのポインタを有するノードＩＤリストを作成し、前記ノードＩＤリスト及び前記階層構造からなる圧縮復元インデックスを前記コンピュータの記憶媒体に記憶する、圧縮復元インデックスを作成及び保存する段階と、
前記コンピュータが、前記圧縮復元インデックスに基づき、前記オリジナルデータの項目毎に該項目中の前記キー値をそれぞれ対応する前記ＩＤで置き換え、圧縮結果セットキャッシュを作成し、前記圧縮結果セットキャッシュを記憶媒体に記憶する、圧縮結果セットキャッシュを作成及び保存する段階とを備え、
前記コンピュータに、検索条件が任意のＩＤで与えられたときに、前記コンピュータが、前記圧縮結果セットキャッシュにおいて一致するＩＤを検索する段階と、
前記コンピュータが、前記一致したＩＤに基づいて、前記圧縮復元インデックスを検索し、対応する前記オリジナルのキー値を読み出す段階と
を備えることを特徴とするデータベースの処理方法。
【請求項２】
前記コンピュータに、検索条件が複数のキー値を同時に呼び出すよう与えられたときに、前記コンピュータが、前記複数のキーにＩＤを一意に割り当て、前記同時に呼び出すべき複数のキー値に対応するＩＤを全て備えたレコードを検索する段階と、
前記コンピュータが、前記検索されたレコードに基づいて、前記圧縮復元インデックスを検索し、対応する前記オリジナルのキー値を読み出す段階とを備える
ことを特徴とする請求項１に記載のデータベースの処理方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、データベースの高速処理、とくに検索エンジンや膨大なキー項目を備えるクロス集計データ管理システムに適用可能なデータ処理技術に関する。
【０００２】
【技術の背景】
汎用コンピュータを用いたデータベース作成とその運営は、近年とくにデータ件数の増大から、従来公知の基本的な処理方式では対応が難しくなっており、より高速な演算処理を可能とする技術が望まれている。
【０００３】
膨大なデータを取り扱う際の技術的な困難性は、例えば、▲１▼取り扱うデータの種類によって処理すべきアルゴリズムが異なること、▲２▼多次元処理をするか否かによって処理方式の基本原理を異にすること、▲３▼使用すべきアルゴリズム（原理）はコンピュータの性能に依存すること、等の点にある。
【０００４】
▲１▼に関して云えば、取り扱うデータが文字列を主とするか、数字を主とするかによって処理技術を異にする。例えば人事データのように、部署名、氏名、性別、趣味、家族構成、社内評価内容の詳細など、主として文字（ひらがな、漢字、カタカナ）をもってレコード・データを作成し必要に応じて加工する場合と、チェーン店の各店舗における品名ごとの売り上げ台数、売上金額といった数字データを扱うケースでは、コンピュータ内部における処理アルゴリズムを異にすることは当然である。これはデータベースの基本であり、例えば階層型、関係型、網型などのデータの基本レコードの格納方法からしても構築方法を異にする。
【０００５】
▲２▼の点は、膨大なデータファイルのレコードを、どのように取り扱うかの問題である。例えば、データ作成時に数値の加減乗除といった演算処理を行い、単純なレコード・ファイルとしてメモリに格納した後は、随時当該レコード・ファイルを呼び出して確認する等の処理をするだけで良いならば、その場合の課題はデータ作成時の処理の高速化に絞られる。一方、どのような加工をするかを前提とせず、とりあえず事実（ファクト；主として数字）データだけをレコードし、この事実ファイルに基づいて後日の多様な加工（射影／選択／結合等）を施すのであれば、データの処理のための原理は自ずから異なり、より高速なキー項目の検索と数値集計を実現し、任意の項目次元において自由な集計結果を高速で取得する点に絞られる。その場合には、基本となるレコード・ファイルの作成はより単純であることが望まれる。
【０００６】
▲３▼の点は、従来提案された特許技術および今後期待されるデータベース処理との相関に於いて重要である。データ種別がどのような種類であれ、データの加工処理速度は高速の並列型ＣＰＵを多数搭載したり巨大なメモリを搭載した大型コンピュータを使用すれば、ほぼ問題なく解決できる。しかしながら、いわゆるスーパーコンピュータはきわめて高額であり、一般の実用レベルではそれを常時使用する環境は期待できない。むしろ現在の汎用コンピュータを利用し、膨大なレコード・ファイル（オリジナルデータ）を応答性の高いレベルで加工し、任意の要求に応答する自在な多次元加工結果を得ることが望まれる。
【０００７】
【従来の技術】
本発明は、例えば１００万件を越える膨大なオリジナルのデータファイルを自在に加工して任意の次元におけるクロス集計結果を短時間で得ることを目的とする。この場合、処理すべきデータファイルは、文字を主とするキー項目（本明細書においてキー値；店舗名等である）と、数字を主とするキー項目（本明細書において項目；数字を主とするファクト）を扱うことになる。
【０００８】
つまり店舗名や商品名といった文字列から構成されるキー項目と、売上台数、金額といった数字から構成されるキー項目を、自由な形式で記録ファイルとして蓄積し、蓄積した膨大なファイルを自由な次元で加工して集計結果を即時に得ることが目的である。
【０００９】
このような技術傾向をもったデータベースの処理方式は、もちろん、従来においてもいくつかの提案がある。第一に、クロス集計処理に目的を絞った処理方式としては、重みコードを使用して処理の高速化を図る技術がある（特開平８−７７２６６号）。これは、あるテーブルのデータの意味を包含する他のテーブルに相対的に低いレベルの重みコードを付与しておき、検索条件が与えられたときに重みコードを利用して必要なファクトを抽出する。具体的には、集団の中で、誰が、いつ、なにを食べ、その材料は何であったか、その値段はいくらであったか、といったデータを集計するときに、人名、日付、メニュー、その金額、材料、その金額、といった具合に、データの意味を階層化し、それらを事実データとして格納しておき、必要に応じて適当な階層領域のデータを重みコードを用いて抽出するものである。
【００１０】
しかし、この技術はデータの意味に上下の関連づけを行うため、システム設計者の主観に起因する勝手な上下関係が発生したり、もともと関連づけの出来ない項目についての処理が出来なくなる等、汎用システムとして利用しにくい面が残る。
【００１１】
第二に、クロス集計処理を直接の目的とするものではないが、膨大な文字データの中からキーワードを高速検索する技術は、多数存在する。例えば、
▲１▼特開平１１−０３１０９６号
インデックスを作成することなくデータを検索する技術
▲２▼特開平１１−００３３５４号
項目の従属関係を作り、従属関係から検索を行う技術
▲３▼特開平１０−１４３５３８号
インデックス・キー値をデータの識別子に関連づける方式
▲４▼特開平１０−００３４１４号
利用頻度の高いキー値を予め定義し格納しておく方式
▲５▼特開平９−１６７１１１号
重複するインデックスのキー値をクラスタリング処理する技術
等である。しかしながら、これらの技術は、例えばインターネット上に存在する膨大な文字データから検索キーを用いて、効率の良い結果を得るには適しているが、階層化されたデータファイルのすべてを検索するといった深度検索の能力はないし、オペレータの主観操作によるデータ保存がなされている場合は、非常に使い勝手の悪いシステムとなりやすい。
【００１２】
これらのデータ処理技術をふまえて、オリジナルデータを自在に加工しうる従来の公知技術を検討すると、特開平５−２５７７７４号を挙げることが出来る。これは、検索キー値と圧縮されたIRN（インデックス・レコード番号）をメモリ上に保有し、検索条件（キー項目の指定）に基づいて、検索キー値からIRNを抽出し、圧縮されたIRNを復元するものである。
【００１３】
【発明が解決しようとする課題】
問題は、項目の検索やクロス集計処理を行う場合の処理時間である。
たしかに特開平５−２５７７７４号の技術によれば、数千件〜１万件程度の比較的少ない件数のオリジナルデータを扱う場合には、圧縮したIRNを用いて任意の項目を比較的高速で検索し、項目に対応する数字の加減乗除演算も比較的高速で処理できる。しかしながら、オリジナルデータが膨大な数になったとき、例えば各チェーン店からリアルタイムで刻々と報告される多数の商品の売り上げデータを長期に渡って継続管理するようなケースを考える場合、単にIRNを圧縮するだけでは、処理能力には限界が生ずる。IRNの圧縮は、主としてファクト（数字）の圧縮であり、新商品の名称など、膨大に広がる可能性のある文字データ（項目）の部分については圧縮処理を施さないからである。
【００１４】
もちろん文字データの圧縮は容易であるし、特開平５−２５７７７４号の発明においても文字データを圧縮することも可能である。しかし、その場合の問題は、圧縮した文字データを高速で検索し且つ復元する手段が存在しない点にある。従って、この特開平５−２５７７７４号の発明では、数千件単位の少ないレコードを管理できるにとどまり、例えば１００万件を越えるような膨大な数のオリジナルデータを自由な視点で高速処理するパワーをもたない。
【００１５】
そこで本発明の目的は、第一に、多数のキー値と項目からなる膨大なオリジナルデータを効率よく格納する点、第二に、格納したデータに基づいて高速でオリジナルデータを復元可能とする点にある。
【００１６】
【課題を解決するための手段】
前記目的を達成するため、本発明に係るデータベースの処理方法は、第一に、オリジナルデータに基づき、項目毎にキー値を圧縮して圧縮復元インデックスを作成し保存する段階と、圧縮復元インデックスに基づき、項目毎に圧縮キーを書き込んだ圧縮結果セットキャッシュを作成し保存する段階とを備える。
第二に、検索条件が与えられたときに、前記圧縮結果セットキャッシュに基づいて圧縮キーを検索（探索）する段階と、検索した圧縮キーに基づいて前記圧縮復元インデックスからオリジナルのキー値を読み出す段階とを備える。尚、圧縮結果セットキャッシュに基づいて圧縮キーを検索する段階において、圧縮キーの階層構造を作成すれば多次元のクロス集計をきわめて高速で処理することが出来る。
【００１７】
【作用】
本発明は、刻々追加／更新されるような膨大なオリジナルデータを、効率よく格納し、随時高速検索（または集計）可能とするため以下の処理を行う。
【００１８】
▲１▼  オリジナルデータに基づき、キー値を項目毎に圧縮して圧縮復元インデックスを作成し保存する段階。これは実際の多次元集計時に絶対に必要となるオリジナルのキー値を、検索可能な状態で加工圧縮し、高速検索と復元が可能な状態で保存しておくための処理である。この圧縮復元インデックスは、検索用の階層構造としては例えばＰ木階層構造、Ｂ木階層構造、Ｔ木階層構造、ハッシュ階層構造など、従来公知のいずれの階層手段でも構わない。次段処理および検索の高速のという点で云えばＰ木構造が好ましい。
【００１９】
▲２▼  圧縮復元インデックスに基づき、項目毎に圧縮キーを書き込んだ圧縮結果セットキャッシュを作成し保存する段階。これは、▲１▼の圧縮復元インデックスで得られた圧縮キー値を項目毎に書き込んでおき、爾後における演算の自由性と検索の高速を実現するための処理段階である。多数の項目（店舗名、商品名、日付、金額等）を、▲１▼の処理段で得た圧縮キー（ノードＩＤ）を用いて保存しておくことにより、データ容量を著しく減らし、保存効率を最適化する。また、これらの処理によって、検索効率も飛躍的に向上する。
【００２０】
▲３▼  検索条件が与えられたときには、前記▲１▼および▲２▼の処理に加えて、以下の処理を行う。すなわち、▲２▼の圧縮結果セットキャッシュに基づいて圧縮キーを検索する段階。圧縮キーの検索は高速に行うことが出来るため、単一のまたは複数の項目の検索は非常に容易であり、簡単な構成で検索エンジンを生み出すことが出来る。また、この処理段において、検索するべき圧縮キーを階層構造をもって処理したときには（請求項２）、後段処理と相俟って任意次元の集計を高速で行うことが可能となる。圧縮結果セットキャッシュのデータは圧縮キー（ノードＩＤ）なので、検索用階層手段を作成する所要時間は現在の汎用コンピュータにおいてもせいぜい１秒以下である。尚、▲１▼の圧縮復元インデックスや▲２▼の圧縮結果セットキャッシュからダイレクトにオリジナルデータを復元させることも原理的には可能であるが、圧縮データとオリジナルデータとの間の呼び出し回数が増加するなど、高速処理は困難となる。
【００２１】
▲４▼  探索した圧縮キーに基づいて、圧縮復元インデックスからオリジナルのキー値を読み出す段階。▲１▼の圧縮復元インデックスに含まれるオリジナルのキー値は、▲３▼の圧縮キーの検索によって随時復元可能なデータとして処理できる。圧縮復元インデックスは項目毎に作成されているので、項目が指定されればオリジナルのキー値は直ちに復元さるからである。
【００２２】
以上のように本発明は、各項目毎にの圧縮キーを格納した圧縮結果セットキャッシュを必須の条件として、その前段にキー値を項目毎に圧縮した圧縮復元インデックスを備えてなる。検索時には、圧縮キーを検索した上で、圧縮復元インデックスからオリジナルのキー値を復元する。このような処理方法は、従来の多次元クロス集計等の処理方法に較べると処理段が増加するが、大量データを効率よく保存し、実行時における演算処理速度を確実に高速化できる。二段階の圧縮処理と、各段における生成ファイルの関係が汎用コンピュータの処理能力範囲内において実現でき、検索時に扱うデータ量が飛躍的に減少するからである。
【００２３】
【発明の実施の形態】
図１は、本発明に係るデータベースの高速処理方法の全体の原理を示すものである。
【００２４】
１は、多数の項目を含んだオリジナルデータ、１０は、オリジナルデータに基づいて作成する圧縮復元インデックス、２０は、圧縮復元インデックス１０に基づいて作成した圧縮結果セットキャッシュ、３０は、検索条件Ｃが与えられたときに、圧縮結果セットキャッシュ２０に基づいて作成される検索用階層構造である。
【００２５】
図２は、オリジナルデータ１と、圧縮復元インデックス１０との関係を例示するものである。この実施形態では、オリジナルデータ１は、店舗、日付、商品、数量、金額という５つの項目（カラム）をもっており、それぞれの項目は、それぞれユニークな値（キー値；カラム値）をもつ。また、この実施形態では例えば店舗を項目１、日付を項目２、商品を項目３・・として項目を区別してある。そして項目１の店舗Ａを例にとると、このキー値は文字「Ａ」である。さらに具体的に云えば店舗名が「霞が関商店」の場合、この項目のキー値は文字「霞が関商店」である。同様に、店舗「Ａ」の日付（項目２）のキー値は数字列「００，０４，０１」、商品（項目３）のキー値は文字「１」である。この例では商品１としてあるが実際には具体的な商標名を構成する文字／数字等がキー値となる。尚、オリジナルデータ１は、例えば各種の記録媒体やオンライン転送データの形式で受けとる。必要に応じてデータ形式を整えるための通常の前処理を施す。
【００２６】
オリジナルデータ１に基づいて作成する圧縮復元インデックス１０は、項目毎に作成する。つまり項目１であれば店舗、項目２であれば日付について、オリジナルのキー値を圧縮し保存する。ここで作成する圧縮復元インデックス１０は、少なくとも、オリジナルのキー値と圧縮キーを備え、復元時の高速性を確保するために適宜の階層構造をもっていることが望まれる。例えばＰ木構造、Ｂ木構造、Ｔ木構造、ハッシュ構造等である。これらの作成原理は公知であが、高速性の点ではＰ木構造が望ましい。作成した圧縮復元インデックスは、サーバ装置の適宜の格納場所（メモリ）にデータ保存しておく。書き換え可能としておくことが望ましい。
【００２７】
ところで、検索用の各種のツリー構造は従来公知であるが、任意データ長のオリジナルキーを検索用階層構造に配置するための手段は従来知られていない。しかし例えば、オリジナルのキー値をビット添字評価手法に基づいて各ノードに圧縮格納すると同時に、ビット添字の評価順序をビットストリームのＬＳＢからＭＳＢに向かって昇順で処理することにより無限ビット長の処理が可能になる。勿論、扱う各項目のビット長が十分短い場合には、このような処理を行う必要はない。
【００２８】
図３は、圧縮復元インデックス１０と、圧縮結果セットキャッシュ２０との関係を例示する図である。圧縮結果セットキャッシュ２０は、圧縮復元インデックス１０の作成段階で取得できる圧縮キー値を、項目毎に格納する手段である。図示した圧縮結果セットキャッシュ２０の項目１のファイルには、項目１の圧縮キー値が書き込まれている。例えば圧縮キー値「０」が「店舗Ａ」に該当し、圧縮キー値「１」が「店舗Ｂ」に該当する。この項目１のファイルデータは、項目１だけを格納しているものであるが、他のファイルには項目２、項目３・・・が同様の手法で書き込まれている。この圧縮結果セットキャッシュ２０は、サーバ装置等の適宜の格納フィールドに永久保存しておく。尚、書き換え可能とすることが望ましい。
【００２９】
図４は、ある検索条件が与えられた場合に、圧縮結果セットキャッシュ２０に基づいて作成する検索用階層構造３０を例示するものである。この検索用階層構造３０は、実行時演算方式を採用する本発明において必須の処理段階である。
【００３０】
検索用階層構造３０は、圧縮結果セットキャッシュ２０を構成する各項目の圧縮キーに基づいて、任意の次元で検索用階層構造を作成する。ここで用いる圧縮キーは、オリジナルのキー値を前段処理において格段に圧縮させたものであるから、階層構造（３０）の作成は通常瞬時（１秒以下）で行うことが出来る。
【００３１】
検索用階層構造３０も、圧縮復元インデックス１０と同様に、検索の信頼性と高速性の条件を満たす限り構造の原理を問わない。例えばＰ木構造、Ｂ木構造、Ｔ木構造、ハッシュ構造等が利用できる。但し、作成処理と検索効率を考慮すると現在のところはＰ木構造が優れる。
【００３２】
また検索用階層構造３０は、当該項目（例えば店舗）の圧縮キーに基づいて、指定条件に含まれる他項目（例えば日付と商品）の圧縮キーを同時に呼び出す機能を備えることが望ましい。勿論、検索用階層構造３０の本質的機能は、作成された階層構造（３０）から圧縮復元インデックス１０にアクセスし、オリジナルのキー値を復元させることであるから、他の項目は時分割処理等によって別途に行うことも可能であり、同時処理を絶対の条件とするものではない。
【００３３】
しかし、検索用階層構造３０の作成時に取り扱うデータ量は極めて少ないので、指定条件に含まれる他の次元項目を同時に呼び出して階層構造内に配置し（総合圧縮項目値）、圧縮復元インデックス１０から必要なオリジナルのキー値を得ることは極めて容易である。
【００３４】
従って、かかる多次元データベースの高速処理方法によれば、刻々増加する多数の項目とキー値を、圧縮結果セットキャッシュ２０の作成段階を経て集積し、随時、任意の次元で高速に集計できる。本発明の特徴は、オリジナルデータから圧縮復元インデックス１０を作成し、これに基づいて項目毎の圧縮結果セットキャッシュを作成する点、および、検索条件が与えられた時には圧縮結果セットキャッシュを用いて適宜の検索用階層を作成し、これを介してオリジナルのキー値を備える圧縮復元インデックス１０にアクセスして、高速でオリジナルのキー値を再現する点にある。
【００３５】
これらの処理の流れは、すべて本発明の要旨を構成するが、圧縮キー値を項目毎にファイルする圧縮結果セットキャッシュ２０の処理を除けば、他の処理段階における具体的手法は特に限定されない。例えば圧縮復元インデックス１０は、オリジナルのユニークなキー値を適宜の形式でデータ圧縮できれば良く、検索用階層構造３０も、圧縮結果セットキャッシュ２０に含まれる圧縮キー値の性質に応じて適宜の検索構造をとることが出来る。
【００３６】
尚、本発明において圧縮加工の処理を施すべきオリジナルデータ１のフォーム（データ形式）が統一されていない場合には、圧縮復元インデックス１０の作成に先立って、データ形式を本発明に係る処理システムにおいて取り扱い可能な形式に変換処理しておくことが望ましい。
【００３７】
【発明の効果】
以上説明したように本発明によれば、膨大な件数のレコードファイルを効率よく保存し、高速検索および任意次元でのクロス集計を高速で実現できる。
【図面の簡単な説明】
【図１】  本発明に係る処理方法の全体の原理を示す図である。
【図２】本発明に係る圧縮復元インデックスの作成を例示する図である。
【図３】本発明に係る圧縮結果セットキャッシュの作成を例示する図である。
【図４】本発明に係る検索用階層構造の作成を例示する図である。
【符号の説明】
１  オリジナルデータ
１０  圧縮復元インデックス
２０  圧縮結果セットキャッシュ
３０  検索用階層構造
【図１】
0004081236.tif 000002
【図２】
0004081236.tif 000003
【図３】
0004081236.tif 000004
【図４】
0004081236.tif 000005