トップ :: G 物理学 :: G06 計算;計数




【発明の名称】 データベース演算処理装置
【発明者】 【氏名】田村 孝之
【要約】 【課題】従来のデータベースシステムでは、自己結合演算を行なう場合に異なるテーブルを結合する場合と同じ処理方式を用いていた。このため、自己結合演算が多用される相関ルールマイニングのような用途には実用上十分な性能を提供することができないという問題があった。

【解決手段】この発明のデータベース演算処理装置は、データベースのテーブルに対する問合せ文に自己結合演算が含まれているか否かを検出して自己結合演算式を生成する自己結合検出部と、生成された自己結合演算式に基づいて演算式中の結合条件に含まれている結合キーを等結合キーと不等結合キーとに分類する結合キー分類部と、等結合キーに基づいてテーブルに記憶されているレコードをソートして、ソート後のテーブルを入力して、上記生成された自己結合演算式を実行して、問合せ文に対する結果を生成する自己結合演算実行部とを備える。
【特許請求の範囲】
【請求項１】 データを記憶するデータベースと、上記データベースに対する問合せ文を入力して解析する問合せ解析部と、上記問合せ解析部による解析結果を入力して上記問合せ文を実行する演算式を生成する演算式生成部と、上記演算式生成部により生成された演算式を実行して上記問合せ文を満たすデータを上記データベースより取得する演算式実行部とを備えるデータベース演算処理装置において、上記データベースは、１つ以上のカラムを有するレコードを記憶する複数のテーブルを記憶し、上記演算式生成部は、上記問合せ解析部による解析結果を入力して２つのテーブルに記憶されているレコードを所定の結合条件に従い結合する結合処理を検出し、さらに、検出した結合処理が上記２つのテーブルが同一テーブルであり、かつ、上記所定の結合条件が同一カラムに対する結合条件である自己結合演算処理か否かを検出して、検出した自己結合演算処理を実行する自己結合演算式を生成する自己結合検出部を備え、上記演算式実行部は、上記自己結合検出部により生成された自己結合演算式を実行して上記自己結合処理の結果を生成する自己結合演算実行部を備えることを特徴とするデータベース演算処理装置。
【請求項２】 データを記憶するデータベースと、上記データベースに対する問合せ文を入力して解析する問合せ解析部と、上記問合せ解析部による解析結果を入力して上記問合せ文を実行する演算式を生成する演算式生成部と、上記演算式生成部により生成された演算式を実行して上記問合せ文を満たすデータを上記データベースより取得する演算式実行部とを備えるデータベース演算処理装置において、上記データベースは、１つ以上のカラムを有するレコードを記憶する複数のテーブルを記憶し、上記演算式実行部は、上記演算式生成部により生成された演算式を入力して２つのテーブルに記憶されているレコードを所定の結合条件に従い結合する結合演算式を検出し、さらに、検出した結合演算式が上記２つのテーブルが同一テーブルであり、かつ、上記所定の結合条件が同一カラムに対する結合条件である自己結合演算処理か否かを検出する自己結合検出部と、上記自己結合検出部により自己結合演算処理を検出された場合に上記自己結合処理の結果を生成する自己結合演算実行部とを備えることを特徴とするデータベース演算処理装置。
【請求項３】 データを記憶するデータベースと、上記データベースに対する問合せ文を入力して解析する問合せ解析部と、上記問合せ解析部による解析結果を入力して上記問合せ文を実行する演算式を生成する演算式生成部と、上記演算式生成部により生成された演算式を実行して上記問合せ文を満たすデータを上記データベースより取得する演算式実行部とを備えるデータベース演算処理装置において、上記データベースは、１つ以上のカラムを有するレコードを記憶する複数のテーブルを記憶し、上記問合せ解析部は、上記問合せ文を入力して２つのテーブルに記憶されているレコードを所定の結合条件に従い結合する結合処理を解析し、さらに、解析した結合処理が上記２つのテーブルが同一テーブルであり、かつ、上記所定の結合条件が同一カラムに対する結合条件である自己結合演算処理か否かを検出して、検出した自己結合演算処理を実行する自己結合演算式を上記演算式生成部に生成させるための自己結合演算解析結果を出力する自己結合検出部を備え、上記演算式生成部は、上記自己結合検出部により出力された自己結合演算解析結果に基づいて、自己結合演算式を生成し、上記演算式実行部は、上記自己結合検出部により出力された自己演算解析結果に基づいて上記演算式生成部により自己結合演算式を実行して上記自己結合処理の結果を生成する自己結合演算実行部を備えることを特徴とするデータベース演算処理装置。
【請求項４】 上記データベースは、上記カラムを識別するカラム識別子と、上記テーブルを識別するテーブル識別子を有し、上記自己結合検出部は、上記テーブル識別子と上記カラム識別子とに基づいて上記問合せ解析部による解析結果と上記演算式生成部により生成された演算式とのいずれかより上記自己結合処理を検出することを特徴とする請求項１または２に記載のデータベース演算処理装置。
【請求項５】 上記問合せ文は、上記自己結合処理を識別するコメントを有し、上記問合せ解析部は、上記コメントを上記解析結果に含ませ、上記自己結合検出部は、上記コメントにより上記自己結合処理を検出することを特徴とする請求項３記載のデータベース演算処理装置。
【請求項６】 上記問合せ文は、上記自己結合処理を明示的に示す問合せ言語によるキーワードを含み、上記問合せ解析部は、上記キーワードを上記解析結果に含ませ、上記自己結合検出部は、上記キーワードに基づいて上記自己結合処理を検出することを特徴とする請求項３記載のデータベース演算処理装置。
【請求項７】 上記自己結合検出部により生成された自己結合演算式は、上記同一のテーブルに記憶されたレコードを結合する結合条件を有し、上記結合条件は、１つ以上の比較項を有するとともに、複数の比較項を有する場合は、関係演算子を有して各比較項の関係を表し、上記比較項は、少なくとも上記結合するレコードの有するカラムを結合キーに指定するとともに、比較演算子を有して上記結合キーの関係を表し、上記演算式生成部は、上記自己結合検出部により生成された自己結合演算式を入力して上記結合条件を検出し、検出した結合条件の有する関係演算子がすべて論理積である場合に、上記結合条件の有する比較項の比較演算子に基づいて、上記比較項の有するカラムを等結合キーと不等結合キーのいずれかに分類する結合キー分類部を備え、上記自己結合演算実行部は、上記結合キー分類部により分類された等結合キーを並び替えのキーとして上記テーブルに記憶されているレコードを並び替える並び替え処理部を備え、上記並び替え処理部により並び替えの行われたテーブルを入力して、上記自己結合検出部により生成された自己結合演算式を実行することを特徴とする請求項１から３のいずれか記載のデータベース演算処理装置。
【請求項８】 上記データベース演算処理装置は、さらに、上記レコードを記憶するバッファを備え、上記自己結合演算実行部は、上記並び替え処理部により並び替えの行われたテーブルに記憶されているレコードより、上記結合キー分類部により等結合キーに分類されたカラムのデータが等しいレコードを上記バッファに記憶するレコード格納部と、上記バッファに記憶されたレコードの記憶位置を示す複数のポインタと、上記複数のポインタにより示されるレコード群を上記バッファより入力して上記自己結合演算式を実行し、上記自己結合処理の結果を生成する結合結果生成部と、上記結合結果生成部により生成された結果を出力する結果出力部とを備えることを特徴とする請求項７記載のデータベース演算処理装置。
【請求項９】 上記自己結合演算実行部は、上記テーブルに記憶されているレコードが上記等結合キーを並び替えのキーとしてあらかじめ並び替えが行われている場合に、上記並び替え処理部によるレコードの並び替えを省略することを特徴とする請求項７記載のデータベース演算処理装置。
【請求項１０】 上記結合結果生成部は、上記結合キー分類部により不等結合キーに分類された結合キーを指定された比較項の有する比較演算子が大小比較である場合、上記バッファに記憶されたレコードを上記不等結合キーに基づいて並び替えて、上記並び替えを行なったレコードを記憶するバッファより上記複数のポインタにより示されるレコード群を入力して、上記自己結合演算式を実行し自己結合処理の結果を生成することを特徴とする請求項８記載のデータベース演算処理装置。
【請求項１１】 上記自己結合検出部により生成された自己結合演算式は、上記同一のテーブルに記憶されたレコードを結合する結合条件を有し、上記結合条件は、１つ以上の比較項を有するとともに、複数の比較項を有する場合は、関係演算子を有して各比較項の関係を表し、上記比較項は、少なくとも上記結合するレコードの有するカラムを結合キーに指定するとともに、比較演算子を有して上記結合キーの関係を表し、上記演算式生成部は、上記自己結合検出部により生成された自己結合演算式を入力して上記結合条件を検出し、検出した結合条件の有する関係演算子がすべて論理積である場合に、上記結合条件の有する比較項の比較演算子に基づいて、上記比較項の有するカラムを等結合キーと不等結合キーのいずれかに分類する結合キー分類部を備え、上記自己結合演算実行部は、上記結合キー分類部により分類された等結合キーに対して第１のハッシュ関数を用いて上記テーブルに記憶されているレコードを複数のグループに分割して記憶するハッシュ分割処理部を備え、上記ハッシュ分割処理部により複数のグループに分割されて記憶されているレコードを入力して、上記自己結合検出部により生成された自己結合演算式を実行することを特徴とする請求項１から３のいずれか記載のデータベース演算処理装置。
【請求項１２】 上記データベース演算処理装置は、さらに、上記レコードを記憶する複数の第１のバッファサイズを有するバッファを備え、上記自己結合演算実行部は、上記ハッシュ分割処理部により複数のグループに分割されて記憶されているレコードに対して第２のハッシュ関数を用いてグループ毎に記憶されているレコードを複数のバッファに分割して記憶するレコード格納部と、上記複数のバッファに記憶されたレコードの記憶位置を示す複数のポインタと、上記複数のポインタにより示されるレコード群を上記複数のバッファより入力して上記自己結合演算式を実行し、上記自己結合処理の結果を生成する結合結果生成部と、上記結合結果生成部により生成された結果を出力する結果出力部とを備えることを特徴とする請求項１１記載のデータベース演算処理装置。
【請求項１３】 上記レコード格納部は、上記複数のバッファに記憶されたレコードを、上記結合キー分類部により等結合キーに分類されたカラムのデータに基づいて上記第１のバッファサイズよりも小さなバッファサイズを有する複数の小バッファに分割して格納し、上記結合結果生成部は、上記複数の小バッファ毎に上記自己結合演算式を実行して上記自己結合処理の結果を生成することを特徴とする請求項１２に記載のデータベース演算処理装置。
【請求項１４】 上記結合結果生成部は、上記結合キー分類部により不等結合キーに分類された結合キーを指定された比較項の有する比較演算子が大小比較である場合、上記複数の小バッファに記憶されたレコードを上記不等結合キーに基づいて並び替えて、上記並び替えを行なったレコードを記憶する小バッファ毎に上記自己結合演算式を実行して上記自己結合処理の結果を生成することを特徴とする請求項１３記載のデータベース演算処理装置。
【発明の詳細な説明】【０００１】
【発明の属する技術分野】この発明は、（関係）データベースシステムに係り、第一に同一テーブル内の複数のレコードの組み合わせから、問合せに指定された条件を満たすものを取り出す自己結合演算処理に関し、第二に自己結合演算を用いてデータベースに記録されたデータ間の相関関係を発見する、データマイニングに関する。
【０００２】
【従来の技術】関係データベースシステムにおける結合演算の処理方式としては、「ネストループ処理方式」、「ソートマージ処理方式」、および「ハッシュ処理方式」などが知られている。「ネストループ処理方式」は、一方のテーブルのレコードを一部ずつメモリ上のバッファに蓄え、他方のテーブルのレコードをすべて読みながら、結合条件を満たすレコードの組合せから出力するレコードを生成する。この「ネストループ処理方式」は、一方のテーブルを繰り返し読むことになるため、非効率的であるが、索引により結合条件を満たすレコードだけを読み出すことができれば効率を改善することができる。「ネストループ処理方式」は、どのような結合条件に対しても適用可能であるが、ほとんどの結合演算はキー値が等しいことを結合条件とする等結合演算である。等結合に対しては「ソートマージ処理方式」および「ハッシュ処理方式」を用いて、結合レコードの検索範囲を限定することにより処理の効率化を図ることができる。
【０００３】「ソートマージ処理方式」は、両方のテーブルのレコード群をまず結合キーでソートすることによって、同一キー値のレコードを連続的にアクセス可能にし、キー値の変化点を見付けて検索範囲の境界とするものである。「ハッシュ処理方式」は、両方のテーブルのレコード群を、結合キーにハッシュ関数を適用して得られる値に基づいて複数のグループに分け、対応するグループ同士の結合演算に処理を分割するものである。各グループ内には異なる結合キー値を持つレコードが存在する可能性があるが、グループ数を大きくすることによってその可能性を小さくすることができる。ハッシュ関数の計算はソートに比べると簡単なので、ＣＰＵ性能が問題になる場合には有利な処理方式である。
【０００４】「ソートマージ処理方式」および「ハッシュ処理方式」は、入力テーブルを前処理し、その処理した結果を中間データとして記憶装置に書き込むので、２つの入力テーブルが同一のテーブルであり、かつ、結合キーが同一である自己結合処理である場合、同じ内容の中間データが物理的に２つ作られることになる。そのため、同一テーブルの自己結合演算には異なるテーブル間の結合演算と同等の処理負荷がかかってしまう。
【０００５】大量のデータを統計的に分析して有用なルールや知識を発見する処理であるデータマイニングの一種の相関ルールマイニング（バスケット分析）は、例えば消費者の購買行動の履歴から購買品目の組合せについての傾向を導き出し、販売店における商品の配置やセット販売などを通じた売り上げの向上に利用される。相関ルールマイニングは、データベースシステムに蓄積された購買履歴データの中から一定回数以上現れる品目の組合せ（頻出品目集合）を全て抽出するフェーズと、抽出された組合せ間の包含関係を考慮して相関ルールを導出するフェーズとに分けられ、特に前半の抽出フェーズの処理負荷が高いことが知られている。
【０００６】抽出フェーズの処理方法としては、Ｒ．Ａｇｒａｗａｌらによって提案されたＡｐｒｉｏｒｉアルゴリズムが有名である。文献Ｒ．Ａｇｒａｗａｌ ａｎｄ Ｒ．Ｓｒｉｋａｎｔ．Ｆａｓｔ Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ Ｍｉｎｉｎｇ Ａｓｓｏｃｉａｔｉｏｎ Ｒｕｌｅｓ．Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０ｔｈ ＶＬＤＢ Ｃｏｎｆｅｒｅｎｃｅ，ｐａｇｅｓ４８７−４９９，１９９４に述べられているその処理方式は以下の通りである。
・各購買品目の購買履歴データ中の出現回数を数え、出現回数が一定値に達したものを頻出品目として抽出する。
・２つの異なる頻出品目の組合せを作り、２−候補品目集合とする（“２−候補品目集合”の“２”は組み合わされる品目の数を示す）。
・２−候補品目集合の購買履歴データにおける出現回数を数え、出現回数が一定値に達したものを２−頻出品目集合として抽出する。
・ｋ ＞＝ ３となるｋについて以下のステップを繰り返す。
・（ｋ−１）−頻出品目集合から品目が一つだけ異なっている２つの品目集合を選び、両者の品目を一つずつ含むｋ個の品目からなる品目集合、ｋ−候補品目集合を作る。ただし、（ｋ−１）−頻出品目集合に存在しない品目の組み合わせを含むものはｋ−候補品目集合から除外するｋ−候補品目集合が空になったら処理を終了する。
・ｋ−候補品目集合の購買履歴データにおける出現回数を数え、出現回数が一定値に達したものをｋ−頻出品目集合として抽出する。
【０００７】品目の組合せの出現回数を数える際には、同時に購入された場合だけを対象とする必要があるが、同時に購入される品目の数は可変であるため、購買履歴データの１つのレコードで同時に購入された品目全てを表現するのは妥当でなく、図２９の（１）のように品目毎にレコードを構成し、同じトランザクションＩＤを持つレコードが同時に購入された品目の組合せを表すようにするのが一般的である。そのため、ｋ個の品目の組合せを調べる際には、図３０のように購買履歴データをｋ−１回自分自身と結合（自己結合）して、同じトランザクションＩＤを持つｋ個の品目からなるレコードを生成する必要がある。
【０００８】しかし、既存のデータベースシステムでは自己結合演算の負荷が高く十分な性能が得られないため、例えば特開平１１−３３４２（平成１１年１月６日公開）「グループバイ処理方式」に述べられているデータマイニング処理方式のように、ほとんどの相関ルールマイニングシステムにおいて、あらかじめ購買履歴データをデータベースシステムから取り出し、図２９の（２）に示すような可変個の品目からなる独自形式のファイルに変換してから、専用のソフトウェアを用いて処理を行っている。
【０００９】
【発明が解決しようとする課題】従来の関係データベースシステムでは、同一テーブルの結合演算を想定していないために、テーブルが異なる場合の処理方式を用いることしかできず、自己結合演算が多用される相関ルールマイニングのような用途には実用上十分な性能を提供することができない。しかし、特開平１１−３３４２の発明のようにデータベースシステム外で頻出品目集合の抽出を行う従来のマイニングシステムは次のような問題点がある。
・大量データの取り出しに伴うオーバヘッドが発生する。
・データのコピーを持つため、余分なディスク領域や管理作業を必要とする。
【００１０】この発明は上記のような課題を解決するためになされたもので、以下のことを目的とする。
・大量データの取り出しに伴うオーバヘッドがない。
・データのコピーを持たないため、余分なディスク領域や管理作業を必要としない。
・並列化などによるデータベースシステムの高性能化により、マイニングシステムに手を加えることなく性能向上が得られる。
そして、上記の目的を達成するため、データベース演算処理装置において問合せの内容を解析して自己結合演算が用いられているかどうかを判定し、自己結合演算が用いられている場合には通常の結合演算処理方式ではなく、自己結合演算にのみ有効で効率的な処理方式を用いることで、自己結合演算が含まれる問合せも効率的に処理することを可能にする。
【００１１】
【課題を解決するための手段】この発明の係るデータベース演算処理装置は、データを記憶するデータベースと、上記データベースに対する問合せ文を入力して解析する問合せ解析部と、上記問合せ解析部による解析結果を入力して上記問合せ文を実行する演算式を生成する演算式生成部と、上記演算式生成部により生成された演算式を実行して上記問合せ文を満たすデータを上記データベースより取得する演算式実行部とを備えるデータベース演算処理装置において、上記データベースは、１つ以上のカラムを有するレコードを記憶する複数のテーブルを記憶し、上記演算式生成部は、上記問合せ解析部による解析結果を入力して２つのテーブルに記憶されているレコードを所定の結合条件に従い結合する結合処理を検出し、さらに、検出した結合処理が上記２つのテーブルが同一テーブルであり、かつ、上記所定の結合条件が同一カラムに対する結合条件である自己結合演算処理か否かを検出して、検出した自己結合演算処理を実行する自己結合演算式を生成する自己結合検出部を備え、上記演算式実行部は、上記自己結合検出部により生成された自己結合演算式を実行して上記自己結合処理の結果を生成する自己結合演算実行部を備えることを特徴とする。
【００１２】この発明に係るデータベース演算処理装置は、データを記憶するデータベースと、上記データベースに対する問合せ文を入力して解析する問合せ解析部と、上記問合せ解析部による解析結果を入力して上記問合せ文を実行する演算式を生成する演算式生成部と、上記演算式生成部により生成された演算式を実行して上記問合せ文を満たすデータを上記データベースより取得する演算式実行部とを備えるデータベース演算処理装置において、上記データベースは、１つ以上のカラムを有するレコードを記憶する複数のテーブルを記憶し、上記演算式実行部は、上記演算式生成部により生成された演算式を入力して２つのテーブルに記憶されているレコードを所定の結合条件に従い結合する結合演算式を検出し、さらに、検出した結合演算式が上記２つのテーブルが同一テーブルであり、かつ、上記所定の結合条件が同一カラムに対する結合条件である自己結合演算処理か否かを検出する自己結合検出部と、上記自己結合検出部により自己結合演算処理を検出された場合に上記自己結合処理の結果を生成する自己結合演算実行部とを備えることを特徴とする。
【００１３】この発明に係るデータベース演算処理装置は、データを記憶するデータベースと、上記データベースに対する問合せ文を入力して解析する問合せ解析部と、上記問合せ解析部による解析結果を入力して上記問合せ文を実行する演算式を生成する演算式生成部と、上記演算式生成部により生成された演算式を実行して上記問合せ文を満たすデータを上記データベースより取得する演算式実行部とを備えるデータベース演算処理装置において、上記データベースは、１つ以上のカラムを有するレコードを記憶する複数のテーブルを記憶し、上記問合せ解析部は、上記問合せ文を入力して２つのテーブルに記憶されているレコードを所定の結合条件に従い結合する結合処理を解析し、さらに、解析した結合処理が上記２つのテーブルが同一テーブルであり、かつ、上記所定の結合条件が同一カラムに対する結合条件である自己結合演算処理か否かを検出して、検出した自己結合演算処理を実行する自己結合演算式を上記演算式生成部に生成させるための自己結合演算解析結果を出力する自己結合検出部を備え、上記演算式生成部は、上記自己結合検出部により出力された自己結合演算解析結果に基づいて、自己結合演算式を生成し、上記演算式実行部は、上記自己結合検出部により出力された自己演算解析結果に基づいて上記演算式生成部により自己結合演算式を実行して上記自己結合処理の結果を生成する自己結合演算実行部を備えることを特徴とする。
【００１４】この発明に係るデータベース演算処理装置は、上記データベースは、上記カラムを識別するカラム識別子と、上記テーブルを識別するテーブル識別子を有し、上記自己結合検出部は、上記テーブル識別子と上記カラム識別子とに基づいて上記問合せ解析部による解析結果と上記演算式生成部により生成された演算式とのいずれかより上記自己結合処理を検出することを特徴とする。
【００１５】この発明に係るデータベース演算処理装置は、上記問合せ文は、上記自己結合処理を識別するコメントを有し、上記問合せ解析部は、上記コメントを上記解析結果に含ませ、上記自己結合検出部は、上記コメントにより上記自己結合処理を検出することを特徴とする。
【００１６】この発明に係るデータベース演算処理装置は、上記問合せ文は、上記自己結合処理を明示的に示す問合せ言語によるキーワードを含み、上記問合せ解析部は、上記キーワードを上記解析結果に含ませ、上記自己結合検出部は、上記キーワードに基づいて上記自己結合処理を検出することを特徴とする。
【００１７】また、この発明に係るデータベース演算処理装置は、上記自己結合検出部により生成された自己結合演算式は、上記同一のテーブルに記憶されたレコードを結合する結合条件を有し、上記結合条件は、１つ以上の比較項を有するとともに、複数の比較項を有する場合は、関係演算子を有して各比較項の関係を表し、上記比較項は、少なくとも上記結合するレコードの有するカラムを結合キーに指定するとともに、比較演算子を有して上記結合キーの関係を表し、上記演算式生成部は、上記自己結合検出部により生成された自己結合演算式を入力して上記結合条件を検出し、検出した結合条件の有する関係演算子がすべて論理積である場合に、上記結合条件の有する比較項の比較演算子に基づいて、上記比較項の有するカラムを等結合キーと不等結合キーのいずれかに分類する結合キー分類部を備え、上記自己結合演算実行部は、上記結合キー分類部により分類された等結合キーを並び替えのキーとして上記テーブルに記憶されているレコードを並び替える並び替え処理部を備え、上記並び替え処理部により並び替えの行われたテーブルを入力して、上記自己結合検出部により生成された自己結合演算式を実行することを特徴とする。
【００１８】また、この発明に係るデータベース演算処理装置は、上記データベース演算処理装置は、さらに、上記レコードを記憶するバッファを備え、上記自己結合演算実行部は、上記並び替え処理部により並び替えの行われたテーブルに記憶されているレコードより、上記結合キー分類部により等結合キーに分類されたカラムのデータが等しいレコードを上記バッファに記憶するレコード格納部と、上記バッファに記憶されたレコードの記憶位置を示す複数のポインタと、上記複数のポインタにより示されるレコード群を上記バッファより入力して上記自己結合演算式を実行し、上記自己結合処理の結果を生成する結合結果生成部と、上記結合結果生成部により生成された結果を出力する結果出力部とを備えることを特徴とする。
【００１９】また、この発明に係るデータベース演算処理装置は、上記自己結合演算実行部は、上記テーブルに記憶されているレコードが上記等結合キーを並び替えのキーとしてあらかじめ並び替えが行われている場合に、上記並び替え処理部によるレコードの並び替えを省略することを特徴とする。
【００２０】また、この発明に係るデータベース演算処理装置は、上記結合結果生成部は、上記結合キー分類部により不等結合キーに分類された結合キーを指定された比較項の有する比較演算子が大小比較である場合、上記バッファに記憶されたレコードを上記不等結合キーに基づいて並び替えて、上記並び替えを行なったレコードを記憶するバッファより上記複数のポインタにより示されるレコード群を入力して、上記自己結合演算式を実行し自己結合処理の結果を生成することを特徴とする。
【００２１】また、この発明に係るデータベース演算処理装置は、上記自己結合検出部により生成された自己結合演算式は、上記同一のテーブルに記憶されたレコードを結合する結合条件を有し、上記結合条件は、１つ以上の比較項を有するとともに、複数の比較項を有する場合は、関係演算子を有して各比較項の関係を表し、上記比較項は、少なくとも上記結合するレコードの有するカラムを結合キーに指定するとともに、比較演算子を有して上記結合キーの関係を表し、上記演算式生成部は、上記自己結合検出部により生成された自己結合演算式を入力して上記結合条件を検出し、検出した結合条件の有する関係演算子がすべて論理積である場合に、上記結合条件の有する比較項の比較演算子に基づいて、上記比較項の有するカラムを等結合キーと不等結合キーのいずれかに分類する結合キー分類部を備え、上記自己結合演算実行部は、上記結合キー分類部により分類された等結合キーに対して第１のハッシュ関数を用いて上記テーブルに記憶されているレコードを複数のグループに分割して記憶するハッシュ分割処理部を備え、上記ハッシュ分割処理部により複数のグループに分割されて記憶されているレコードを入力して、上記自己結合検出部により生成された自己結合演算式を実行することを特徴とする。
【００２２】また、この発明に係るデータベース演算処理装置は、上記データベース演算処理装置は、さらに、上記レコードを記憶する複数の第１のバッファサイズを有するバッファを備え、上記自己結合演算実行部は、上記ハッシュ分割処理部により複数のグループに分割されて記憶されているレコードに対して第２のハッシュ関数を用いてグループ毎に記憶されているレコードを複数のバッファに分割して記憶するレコード格納部と、上記複数のバッファに記憶されたレコードの記憶位置を示す複数のポインタと、上記複数のポインタにより示されるレコード群を上記複数のバッファより入力して上記自己結合演算式を実行し、上記自己結合処理の結果を生成する結合結果生成部と、上記結合結果生成部により生成された結果を出力する結果出力部とを備えることを特徴とする。
【００２３】また、この発明に係るデータベース演算処理装置は、上記レコード格納部は、上記複数のバッファに記憶されたレコードを、上記結合キー分類部により等結合キーに分類されたカラムのデータに基づいて上記第１のバッファサイズよりも小さなバッファサイズを有する複数の小バッファに分割して格納し、上記結合結果生成部は、上記複数の小バッファ毎に上記自己結合演算式を実行して上記自己結合処理の結果を生成することを特徴とする。
【００２４】さらに、この発明に係るデータベース演算処理装置は、上記結合結果生成部は、上記結合キー分類部により不等結合キーに分類された結合キーを指定された比較項の有する比較演算子が大小比較である場合、上記複数の小バッファに記憶されたレコードを上記不等結合キーに基づいて並び替えて、上記並び替えを行なったレコードを記憶する小バッファ毎に上記自己結合演算式を実行して上記自己結合処理の結果を生成することを特徴とする。
【００２５】
【発明の実施の形態】実施の形態１．図１はこの発明のデータベース演算処理装置であるデータベースシステムを示すブロック図である。図１において１は端末、２はデータベースシステム、３はアクセス回線、４はディスク装置である。２ａは、データベースシステム２のプロセッサであるＣＰＵ、２ｂはＣＰＵ２ａが実行するプログラムとプログラムの実行に必要な変数およびディスク装置４から読み込んだレコードや処理結果のレコードを格納するメモリ、２ｃはアクセス回線３との通信インタフェースをとるネットワークインタフェース、２ｄはディスク装置４をアクセスする際のディスクインタフェースである。
【００２６】また、図２は図１のデータベースシステム２の構成をより詳細に示したブロック図である。図２において、２−１は端末１からの問合せ要求を受け付ける手段であり、例えば公知のＳＱＬ言語（構造化照会言語）におけるＣＬＩ（ＣａｌｌＬｅｖｅｌ Ｉｎｔｅｒｆａｃｅ）やＯＤＢＣ（Ｏｐｅｎ ＤａｔａＢａｓｅＣｏｎｎｅｃｔｉｖｉｔｙ）などのインタフェースを用いることができる問合せ受付手段である。２−２は受け付けた問合せの問合せ文の意味を解析する問合せ解析部である問合せ解析手段であり、２−３は問合せ文の解析結果を元に問合せの実行方式を決定し、問合せ文を実行する演算式を生成する実行プラン生成手段（演算式生成部）である。一般に、問合せ解析手段２−２と実行プラン生成手段２−３を合わせて、例えばＳＱＬコンパイラとして実現されることが多い。２−３１と２−３２は実行プラン生成手段２−３の一部であり、それぞれ、問合せ文に結合演算が含まれている場合に結合キーを等結合キーと不等結合キーとに分類する結合キー分類手段（結合キー分類部）、問合せ文に含まれる結合演算が自己結合演算かどうかを判定し、判定の結果に基づいて自己結合演算式を生成する自己結合検出手段（自己結合検出部）である。２−４は実行プラン生成手段２−３が生成した問合せ実行プランに従って問合せ処理の実行を行う実行プラン実行手段（演算式実行部）であり、２−４２は問合せ実行プランのうち自己結合演算を実行する自己結合演算実行手段（自己結合演算実行部）である。４はデータベースが格納されるディスク装置であり、２−６はディスク装置４との入出力を制御する入出力制御手段である。
【００２７】この発明の実施の形態においては、従来のものと比べ、結合キー分類手段２−３１と、自己結合検出手段２−３２と、自己結合演算実行手段２−４２と、を有する点で異なる。
【００２８】図３は問合せ解析手段２−２が実行プラン生成手段２−３に渡す、問合せ文の解析結果を表す例である。問合せ文の解析結果は、例えば問合せの結果を頂点とし、入力テーブルを終端とする木構造で表すことができる。木構造の節点には入力に対する操作を表す演算子が置かれる。演算子は、演算の種類を示す情報と条件を示す情報と入力するテーブルを示す情報等の演算式を示すものである。演算子には、例えば、ディスク装置からレコード群を入力する走査演算子、与えられた条件を満たさないレコードを除外する選択演算子、カラムに対する操作を施す射影演算子、２つの入力レコードのカラムから出力レコードを生成する結合演算子、全入力レコードに対する統計値を計算する集計演算子、などが存在する。全ての演算子は中間テーブルと呼ばれる同一形式のレコード群を出力とし、走査演算子以外の演算子は他の演算子の出力する中間テーブルのレコード群を入力とする。結合演算子の入力は２つであり、選択、射影、集計などの演算子の入力は１つである。
【００２９】図４は走査演算子の具体的な表現の例である走査演算記述子を表す。走査対象のテーブルの名前と読み込むレコードのカラム情報をコンピュータのメモリ上に配置された走査演算記述子の領域に格納する。図５は選択演算子の具体的な表現の例である選択演算記述子を表す。入力を受け取る演算記述子へのポインタ、選択条件を表す条件式、結合結果レコードのカラム情報をコンピュータのメモリ上に配置された選択演算記述子の領域に格納する。図５の入力演算記述子「＃１」が演算記述子へのポインタであり、「＃１」は図４の演算識別子「＃１」に対応している。図６は結合演算子の具体的な表現の例である結合演算記述子を表す。入力を受け取る２つの演算記述子へのポインタ、結合条件を表す条件式、結合結果レコードのカラム情報をコンピュータのメモリ上に配置された結合演算記述子の領域に格納する。図６の第１の入力演算記述子「＃２」と第２の入力演算記述子「＃３」とが入力を受け取る２つの演算記述子へのポインタである。
【００３０】この発明の実施の形態においては、同一テーブル間の結合を表すための演算子として自己結合演算子を備える。図７は自己結合演算子の具体的な表現の例である自己結合演算記述子を表す。入力演算記述子へのポインタ、結合の多重度、結合条件を表す条件式、結合結果レコードのカラム情報をコンピュータのメモリ上に配置された自己結合演算記述子の領域に格納する。図７の入力演算記述子「＃２」が入力演算記述子へのポインタである。ここで結合の多重度は、入力テーブルを何回自己結合するかを表し、１回の自己結合に対する多重度を２とする。
【００３１】次に上記実施の形態における自己結合検出手段２−３２の動作を説明する。図８は自己結合検出手段２−３２の動作を説明するフローチャートである。図８のステップＳ８−１において、問合せ解析手段２−２から受け取った問合せ解析結果を正規化する。すなわち、結合演算記述子と走査演算記述子のテーブル名に着目し、テーブル名の辞書引き順に従って結合演算記述子の順序を入れ換え、同一テーブルを入力とする結合演算記述子が互いに隣接するようにする。正規化の操作は問合せ結果を変えないように行う必要があり、集計演算や合併演算などが含まれる場合には、それらの演算記述子を挟んだ結合演算子の入れ換えは行わない。このような問合せ解析結果の等価変換は公知の技術であり、例えばＣ．Ｊ． Ｄａｔｅ著Ａｎ Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ｄａｔａｂａｓｅ Ｓｙｓｔｅｍｓ第６版（Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ社、１９９５年）第１８章に述べられている。図９は、ある問合せ文に対して問合せ解析手段２−２が生成した解析結果の例のうち、結合演算記述子と入力テーブルだけを抽出したものを表し、図１０は図９の解析結果を正規化した結果のうち、結合演算記述子と入力テーブルだけを抽出したものを表す。
【００３２】次いでステップＳ８−２において、正規化結果の結合演算記述子のうち、同一テーブルを入力とし、同一カラムの集合を結合キーとするものを自己結合演算記述子に置き換える。図１１、図１２、図１３、および図１４は自己結合演算記述子置き換えの方法を示している。図１１は、正規化された問合せ解析結果の最下部の結合演算子の２つの入力が同一テーブルで、結合キーが同一カラム集合である場合に適用される置き換え規則を示す。結合演算子を自己結合演算子に置き換えると共に、２つの選択演算子を１つに統合する。統合された選択演算子の選択条件は元の２つの選択条件の論理和とする。特殊な場合として、いずれか一方または両方の選択演算子が存在しない場合、選択条件は常に「真」とみなす。そのため、統合後の選択条件も常に「真」となり、選択演算子が存在しないことと等価になる。また、両方の選択演算子の選択条件が等しい場合、統合後の選択条件は元の選択条件と等しくなる。自己結合演算子の結合条件は元の結合演算子の結合条件と、元の２つの選択条件との論理積とする。自己結合演算子の多重度は２である。
【００３３】図１２は、図１１の置き換えの後に有効となるもので、最下部の結合演算子の一方の入力があるテーブルの自己結合結果であり、かつ、他方の入力が同一のテーブルであって、結合キーが同一カラムである場合に適用される置き換え規則を示す。結合演算子を自己結合演算子に統合し、２つの選択演算子を１つに統合する。統合された選択演算子の選択条件は図１１と同様元の２つの選択条件の論理和とする。また、自己結合演算子の結合条件は元の自己結合演算子および結合演算子の結合条件と、元の２つの選択条件との論理積とする。自己結合演算子の多重度は元の自己結合演算子の多重度に１を加えたものとする。
【００３４】図１３は、正規化された問合せ解析結果の最下部にない２つの結合演算子の入力が同一のテーブルであって結合キーが同一カラム集合である場合に適用される置き換え規則を示す。２つの結合演算子を自己結合演算子と結合演算子に置き換えると共に、２つの選択演算子を１つに統合する。統合された選択演算子の選択条件は元の２つの選択条件の論理和とする。また、元の結合演算子のうち上位のものの結合条件を２つの条件Ｊ２１とＪ２２との論理積に分解し、条件Ｊ２１には自己結合されるテーブルのカラムだけが含まれるようにする。自己結合されるテーブルのカラムだけを含む結合条件が存在しない場合には、Ｊ２１は論理値「真」とし、元の結合条件をＪ２２とする。置き換えの結果作られる自己結合演算子の結合条件は条件Ｊ２１と元の２つの選択条件との論理積とし、結合演算子の結合条件は元の結合演算子のうち下位のものの結合条件Ｊ１と条件Ｊ２２との論理積とする。自己結合演算子の多重度は２である。
【００３５】図１４は、図１３の置き換えの後に有効となるもので、最下部にない２つの結合演算子の一方の入力があるテーブルの自己結合結果であり、かつ、他方の入力が同一のテーブルであって、結合キーが同一カラム集合である場合に適用される置き換え規則を示す。自己結合演算子と２つの結合演算子を自己結合演算子と結合演算子に置き換えると共に、２つの選択演算子を１つに統合する。統合された選択演算子の選択条件は元の２つの選択条件の論理和とする。また、元の結合演算子のうち上位のものの結合条件を２つの条件Ｊ２１とＪ２２との論理積に分解し、条件Ｊ２１には自己結合されるテーブルのカラムだけが含まれるようにする。置き換えの結果作られる自己結合演算子の結合条件は元の自己結合演算子の結合条件と、条件Ｊ２１と、元の２つの選択条件との論理積とし、結合演算子の結合条件は元の結合演算子のうち下位のものの結合条件Ｊ１と条件Ｊ２２との論理積とする。自己結合演算子の多重度は元の自己結合演算子の多重度に１を加えたものとする。
【００３６】次に、結合キー分類手段２−３１の動作を、図１５と図１６に示すフローチャートを用いて説明する。結合キー分類手段２−３１は、自己結合検出手段２−３２によって結合演算子の自己結合演算子への置換が行われた演算式を入力する。図１５のステップＳ１５−１において、演算式に記述されている２つのテーブル内のレコードを結合する条件が単純な比較式の論理積で表されるかどうか判断し、表されている場合ステップＳ１５−２に進み、そうでない場合ステップＳ１５−５に進む。ステップＳ１５−２において、後述する方法により結合条件に現れるカラムを等結合キーと不等結合キーに分類する。ステップＳ１５−３において、結合条件中に等結合キーが少なくとも１つ存在するかどうかを判断し、存在する場合はステップＳ１５−４に進み、そうでない場合はステップＳ１５−５に進む。ステップＳ１５−４において、結合演算の実行方式として等結合を選択する。また、ステップＳ１５−５において、結合演算の実行方式として不等結合を選択する。
【００３７】等結合は、結合キーの値で入力テーブルを分割あるいはソートすることで、突き合わせるレコードの探索範囲を狭めることができ、効率的に処理できるが、不等結合は全てのレコードの組み合わせに対して結合条件を満たしているかテストする必要があり、非常に処理負荷が重い。従来の等結合は、全ての結合キーが等結合キーである場合に限り適用されるが、この発明の実施の形態においては、一部の結合キーが等結合キーである場合にもまず等結合キーだけを結合キーとした等結合を行い、その結果に対して不等結合キーの条件式をテストして選択演算を行うことで、可能な限り等結合演算を用いるようにする点が異なる。
【００３８】また、図１６は図１５のステップＳ１５−２の動作を詳細に表したフローチャートである。図１６のステップＳ１６−１において、結合条件の有する比較項を論理積の関係演算子を用いて表された条件式から一つ取り出す。ステップＳ１６−２において取り出した項の比較演算子が等号かどうかを判断し、等号であればステップＳ１６−３に進み、そうでなければステップＳ１６−４へと進む。ステップＳ１６−３において、取り出した項に含まれるカラムを等結合キー候補に分類する。また、ステップＳ１６−４において、取り出した項に含まれるカラムを不等結合キー候補に分類する。ステップＳ１６−５において、条件式の項を全て処理したかどうか判断し、未処理のものがあればステップＳ１６−１に戻る。全ての項を処理し終えた後に、ステップＳ１６−６において等結合キー候補から等結合キー候補と不等結合キー候補に重複しているものを取り除いて等結合キーとし、不等結合キー候補を不等結合キーとする。
【００３９】図１７は具体的な結合条件を含む問合せ例に対する結合キー分類手段２−３１の動作を説明する図である。１７−１は元の問合せ文であり、１回の結合演算を表している。問合せ文１７−１で処理の対象とするテーブルは、「Ａ」であり、「ＦＲＯＭ Ａ Ａ１，ＡＡ２」の記述により、テーブル「Ａ」を「Ａ１」と「Ａ２」との２つの名前で参照することを示している。１７−２は問合せ文１７−１の解析結果から取り出した結合条件である。結合条件１７−２は比較項１と比較項２との二つの単純な比較演算項の論理積で表される。比較演算が等号かそれ以外かに基づいて分類した結果、等結合キーは１７−３に示すＡ１．ＩＤとＡ２．ＩＤ、不等結合キーは１７−４に示すＡ１．ＩＴＥＭとＡ２．ＩＴＥＭとなる。前述したように、「Ａ１」と「Ａ２」は一つの「Ａ」というテーブルであるため、「Ａ１．ＩＤ」「Ａ２．ＩＤ」とは同じカラムを示し、「Ａ１．ＩＴＥＭ」と「Ａ２．ＩＴＥＭ」とは同じカラムを示している。また、この問合せにおける結合演算は全体としては等結合ではないが、等結合キーを持つので「ＩＤ」というカラムに格納されているデータを結合キーとした等結合演算が選択される。
【００４０】図１８は自己結合演算実行手段２−４２の詳細を表すブロック図である。自己結合演算実行手段２−４２は、ソートマージ結合処理方式と類似しているが、テーブルの入力、テーブルのソート、結合結果の出力をそれぞれ１回ずつ行う間に複数回の自己結合を実行できる点が異なる。自己結合の多重度をＮとすると、ソートマージ結合処理方式ではＮ回のテーブル入力、Ｎ回のソート、Ｎ−１回の結合結果出力を伴うため、実行速度が低下する。
【００４１】図１８において、１８−７は入力テーブルを等結合キーに基づいてソートし、中間テーブルを生成する前処理手段（並び替え処理部）である。ただし、入力テーブルが既に等結合キーでソートされていることが判明した場合はソート処理を省略することもできる。図１７の例によれば前処理手段１８−７はテーブル「Ａ」をソート処理の対象として入力する。１８−１は入出力制御手段２−６を通じてソート済みの中間データまたはソート済みのテーブルからレコードを１つ入力するためのレコード入力手段、１８−２は入力した複数のレコードを図示しないメモリ上のバッファに格納するためのレコード格納手段（レコード格納部）、１８−３はレコード格納手段１８−２によって格納されているレコードの等結合キーの値を格納するための現在キー値格納手段、１８−４はレコード格納手段１８−２によってバッファに格納されているレコードから結合結果を生成する結合結果生成手段（結合結果生成部）である。１８−５１、１８−５２、１８−５３は結合結果生成手段１８−４がレコード格納手段１８−２によってバッファに格納されているレコードをアクセスする時に用いる第１、第２…第Ｎのポインタであり、ここでＮは自己結合演算の多重度である。自己結合演算の多重度は自己結合検出手段によって求められる。１８−６は結合結果生成手段１８−４が生成した結果レコードを出力する結果レコード出力手段（結果出力部）である。
【００４２】次に、図１９に示すフローチャートを用いて図１８の自己結合演算実行手段の動作のうち、前処理手段１８−７における処理以降について説明する。図１９のステップＳ１９−１において、レコード入力手段１８−１によりソート後の中間テーブルから最初のレコードにおける等結合キーの値を取得する。ステップＳ１９−２において、取得したキー値を現在キー値格納手段１８−３によって格納する。ステップＳ１９−３においてレコード格納手段１８−２によってバッファを初期化し、バッファにレコードが格納されていない状態にする。ステップＳ１９−４においてレコード入力手段１８−１を通じて入力したレコードをレコード格納手段１８−２によりバッファに格納する。ステップＳ１９−５においてソート後の中間テーブルに次のレコードが存在するかどうかを判断し、存在する場合にはステップＳ１９−６に進み、存在しない場合にはステップＳ１９−９に進む。ステップＳ１９−６において次のレコードにおける等結合キーの値を取得する。ステップＳ１９−７において、取得したキー値と現在キー値格納手段１８−３によって格納された値とを比較し、両者が等しい場合にはステップＳ１９−４に戻り、等しくない場合にはステップＳ１９−８に進む。ステップＳ１９−８において、結合結果生成手段１８−４によりレコード格納手段１８−２によってバッファに格納されているレコードを処理して結果レコードを生成し、ステップＳ１９−２へと戻る。ステップＳ１９−９において、結合結果生成手段１８−４によりレコード格納手段１８−２によってバッファに格納されているレコードを処理して結果レコードを生成し、処理を終了する。ステップＳ１９−２からステップＳ１９−７は、レコードのキー値が等しいレコード群を処理している。
【００４３】図２０は図１８の結合結果生成手段１８−４の動作の詳細を示すフローチャートである。ここでは簡単のため多重度Ｎ＝２の場合の例を示す。一般のＮに対しては、ループをＮ重にすることで簡単に拡張することができる。図２０のステップＳ２０−１において、第１のポインタ１８−５１をバッファの先頭レコードを指すように初期化する。ステップＳ２０−２において、第２のポインタ１８−５２をバッファの先頭レコードを指すように初期化する。ステップＳ２０−３において第１のポインタ１８−５１が指すレコードと第２のポインタ１８−５２が指すレコードが結合条件を満たすか判定し、満たす場合には結合結果に必要なカラムの値を取り出して結果レコードを生成する。図１７の結合条件１７−２を例にすると比較する２つのレコードの「ＩＤ」が等しく第１のポインタによるレコードの「ＩＴＥＭ」が第２のポインタによるレコードの「ＩＴＥＭ」よりも小さい場合に結果レコードを生成する。ステップＳ２０−４において第２のポインタ１８−５２を１レコード分進める。ステップＳ２０−５において、第２のポインタ１８−５２がレコード格納手段１８−２によってバッファに格納されている最後のレコードを越えたかどうか判断し、越えていない場合はステップＳ２０−３に戻り、越えた場合はステップＳ２０−６に進む。ステップＳ２０−６において第１のポインタ１８−５１を１レコード分進める。ステップＳ２０−７において、第１のポインタ１８−５１がレコード格納手段１８−２によってバッファに格納されている最後のレコードを越えたかどうか判断し、越えていない場合はステップＳ２０−２に戻り、越えた場合は処理を終了する。
【００４４】図２１にレコード格納手段１８−２によってバッファに格納された内容の一例を示し、図２２に図２０のステップＳ２０−２からステップＳ２０−７のループの様子を示す。図２２の（Ａ）は第１のポインタがレコード１を示す場合の処理であり、第２のポインタがレコード１からレコード６へと変化しながら、ステップＳ２０−３において第１と第２のポインタとにより示されるレコードの「ＩＤ」と「ＩＴＥＭ」を比較し、図１７の結合条件１７−２に一致するレコードを対象に結果レコードの生成を行う。第１のポインタはレコード２〜レコード６へと変化し、第１のポインタが１レコード分進む毎に第２のポインタがレコード１〜レコード６へと変化する。図２２の（Ｂ）は、第１のポインタがレコード２である時に第２のポインタがレコード１〜レコード６へと変化し、図２２の（Ｃ）は、第１のポインタがレコード６であるときに、第２のポインタがレコード１〜レコード６へと変化する様子を説明している。但し、図２２の（Ａ）〜（Ｃ）によると、例えば、第１のポインタがレコード１である時と、第１のポインタがレコード２である時とでは、比較するレコードが同じレコード１とレコード２であっても「ＩＴＥＭ」の値により結果レコードを生成する場合と、生成しない場合の別々の結果が発生してしまう。これを対処するために以下の工夫を行う。
【００４５】結合条件のうち不等結合キーに関するものが大小比較である場合、以下の方法を適用することができる。まず、上記ステップＳ２０−１に先立って、バッファ上のレコードを不等結合キーに基づいてソートする。また、上記ステップＳ２０−２における第２のポインタ１８−５２の初期化においては、バッファの先頭レコードではなく、第１のポインタ１８−５１が指すレコードの次のレコードを指すように変更する。これにより、バッファ上のレコード全ての組み合わせのうち、結合条件を満たさないことが明らかなものを除外することができるので、処理を高速化することができる。
【００４６】図２３に示したバッファのレコードをさらに、不等結合キーに基づいてソートした結果の例を示す。また、図２４（Ａ）〜（Ｃ）には、第１のポインタがレコード１〜レコード６へと変化する処理内容を示すが、第１のポインタがレコード６である時は、第２のポインタはレコード７より開始され、レコード７は存在しないため、第１のポインタがレコード６である処理は存在しない。このため、第１のポインタはレコード５までとなる。図２４と図２２を比較すると明らかに処理の回数が減っていることがわかる。
【００４７】以上のように、この発明の実施の形態１に記載された発明は、特に、自己結合検出手段と、結合キー分類手段と、自己結合演算実行手段と、を備えているので、同一テーブルの同一カラム間の１回または複数回の結合演算を検出し、入力の前処理の回数、入力レコードの読み込み回数、結果レコードの書き込み回数が少なく効率的な自己結合演算を実行することができる。また、結合条件が完全な等結合でなくても、部分的に等結合条件が含まれていれば、効率的な等結合処理方式を採用することができる。特に、データマイニングにおけるレコード間の相関関係抽出処理において、レコードの組み合わせを作るために必要な問合せのように、部分的な等結合による自己結合が多用される問合せを効率的に処理することが可能になる。
【００４８】この実施の形態１では記憶装置に格納された複数テーブルのレコードから、指定された条件を満たす組み合わせを得る結合問合せにおいて、同一テーブルの同一カラム間の結合条件が含まれるかどうかを判定する自己結合検出手段と、一つのテーブルから結合演算の結果を導出する自己結合演算実行手段と、を備えることを特徴とするデータベース演算処理装置の一例を説明した。また、結合キーに等結合キーが含まれる場合に、等結合キーだけを用いてテーブル内レコード群のソートを行う前処理手段を備えることを特徴とするデータベース演算処理装置の一例を説明した。また、結合条件を表す問合せの条件式がカラムの比較項の論理積で表される場合に、各比較項が等値比較であるかそれ以外の比較であるかに基づいて、条件式中のカラムを等結合キーと不等結合キーのいずれか一方に分類する結合キー分類手段を備えることを特徴とするデータベース演算処理装置の一例を説明した。また、テーブル内レコード群を等結合キーでソートする前処理手段と、ソート結果のレコードを記憶装置から順次読み出すレコード入力手段と、同一等結合キー値を持つレコードをバッファに格納するレコード格納手段と、バッファに蓄えられたレコードの等結合キーの値を保持する現在キー値格納手段と、バッファ上のレコードを指す複数のポインタと、複数のポインタが指すレコードの組み合わせから自己結合の結果を生成する結合結果生成手段と、自己結合の結果生成されたレコードを記憶装置に出力する結果レコード出力手段と、を備えることを特徴とするデータベース演算処理装置の一例を説明した。また、テーブル内レコード群があらかじめ等結合キーでソートされている場合にはソート処理を省略する前記前処理手段を備えることを特徴とするデータベース演算処理装置の一例を説明した。また、不等結合キーによる比較が大小比較である場合、前記バッファに蓄えられたレコードを不等結合キーでソートし、バッファ上の格納位置が昇順になっているレコードの組み合わせから自己結合結果を生成する前記結合結果生成手段を備えることを特徴とするデータベース演算処理装置の一例を説明した。また、問合せ言語のテーブルとカラムの識別子（名前）に基づいてテーブルおよびカラムの同一性を判定する前記自己結合検出手段を備えることを特徴とするデータベース演算処理装置の一例を説明した。
【００４９】実施の形態２．図２５はこの発明の第２の実施の形態を示すブロック図である。この発明の第２の実施の形態においては、第１の実施の形態の図２に示したブロック図と比べ、図２５に示すブロック図のように問合せ解析手段２−２が自己結合検出手段２−２２を含む点が異なる。例えば、図２６（２）に示すように自己結合を示す特殊なコメント「−−＃ｓｅｌｆｊｏｉｎ ｋｅｙ」を問合せに用いることにより、問合せ解析手段２−２が出力する問合せ解析結果に、図６に示す結合演算記述子６−１ではなく、図７に示す自己結合演算記述子７−１を含めるようにできる。また、図２６（３）に示すように自己結合を示すキーワードを問合せに用いることにより、問合せ解析手段２−２が出力する問合せ解析結果に、図６に示す結合演算記述子６−１ではなく、図７に示す自己結合演算記述子７−１を含めるようにできる。尚、図２６（１）は、第１の実施の形態１の図７に示した問い合せ文と同じであり、テーブルと、カラムの識別子（名前）に基づいてテーブル及びカラムの同一性を判定する例である。
【００５０】以上のように、この発明の実施の形態２に記載された発明は、特に、自己結合検出手段と、結合キー分類手段と、自己結合演算実行手段と、を備えているので、問合せに記述された自己結合の指示に従って、高速な自己結合演算を実行することができる。
【００５１】この実施の形態２では、問合せ言語に補助的に加えられたコメントに基づいてテーブルおよびカラムの同一性を判定する前記自己結合検出手段を備えることを特徴とするデータベース演算処理装置の一例を説明した。また、自己結合であることを明示的に示す問合せ言語のキーワードに基づいてテーブルおよびカラムの同一性を判定する前記自己結合検出手段を備えることを特徴とするデータベース演算処理装置の一例を説明した。
【００５２】実施の形態３．図２７はこの発明の第３の実施の形態を示すブロック図である。この発明の第３の実施の形態においては、第１の実施の形態の図２に示したブロック図と比べ、図２７に示すブロック図のように実行プラン実行手段２−４が自己結合検出手段２−４３を含む点が異なる。結合演算の実行に先立って２つの入力テーブルと結合キーの識別子（名前など）を比較し、両者が異なる場合には通常の結合演算実行手段による処理を行い、両者が一致する場合には自己結合演算実行手段２−４２による処理を行う。
【００５３】以上のように、この発明の実施の形態３に記載された発明は、特に、自己結合検出手段と、結合キー分類手段と、自己結合演算実行手段と、を備えているので、同一テーブルの同一カラム間の１回の結合演算を検出し、入力の前処理の回数、入力レコードの読み込み回数が少なく効率的な自己結合演算を実行することができる。
【００５４】この実施の形態３では、問合せ処理の実行時に入力テーブルとカラムの識別子を比較することでテーブルおよびカラムの同一性を判定する前記自己結合検出手段を備えることを特徴とするデータベース演算処理装置の一例を説明した。
【００５５】実施の形態４．この発明の第４の実施の形態においては、第１の実施の形態と比べ、自己結合演算実行手段２−４２における前処理手段１８−７（実施の形態４では前処理手段はハッシュ分割処理部である）が等結合キーによるソートではなく、等結合キーに第１のハッシュ関数を適用して得られる値に基づくハッシュ分割である点と、レコード入力手段１８−１が分割により生成された中間ファイルを１つずつ処理する点と、レコード格納手段１８−２がレコードを等結合キーに第２のハッシュ関数を適用して得られる値に基づいて複数のバッファに分割して格納する点と、が異なる。図２８はこの発明の第４の実施の形態におけるレコード格納手段の構成を示すブロック図である。ここで、例えば等結合キーをｋｅｙ１とｋｅｙ２とし、第２のハッシュ関数Ｈ２を、Ｈ２（ｋｅｙ１，ｋｅｙ２）＝（ｋｅｙ１＋ｋｅｙ２）ｍｏｄ １０１と定義すると、第１のバッファ２４−１にはＨ２の値が０となるレコードが格納され、第２のバッファ２４−２にはＨ２の値が１となるレコードが格納され、以下第１０１のバッファ２４−３までＨ２の値に基づいて１０１個のバッファに分割して格納される。
【００５６】また、それぞれのバッファには、ハッシュ値は一致するがキー値自体は一致しないレコードが混在するので、バッファ内をさらに小バッファに分割してキー値が同じレコードを隣接するメモリ領域に格納するようにする。すなわち、バッファに新たなレコードが追加される毎に、既に同じ等結合キー値を持つレコードが格納される小バッファが存在するかどうかを判定し、存在した場合にはその小バッファに新たなレコードを追加し、存在しなかった場合には新たな小バッファを設けて新たなレコードを格納する。あらかじめ必要な数の小バッファを用意し、直接レコードを格納するためには、等結合キーの値の範囲が判明しており、かつ、値の分布が密（値に抜けがない）でなければならず、また、第２のハッシュ関数を用いないとキーの値に対応する小バッファの検索が非効率的になる。
【００５７】また、この発明の第４の実施の形態においては、結合結果生成手段１８−４の動作は、小バッファ毎に処理を繰り返すことを除き、第１の実施の形態と同様である。不等結合キーに関する結合条件が大小比較である場合は、小バッファ上のレコードを不等結合キーに基づいてソートし、結合条件をテストするレコードの組み合わせを減らす点も同様である。
【００５８】以上のように、この発明の実施の形態４に記載された発明は、特に、自己結合検出手段と、結合キー分類手段と、ハッシュ処理方式に基づく自己結合演算実行手段と、を備えているので、同一テーブルの同一カラム間の１回の結合演算を検出し、入力の前処理の回数、入力レコードの読み込み回数が少なく効率的な自己結合演算を実行することができる。
【００５９】この実施の形態４では、結合キーに等結合キーが含まれる場合に、等結合キーだけを用いてテーブル内レコード群のハッシュ分割を行う前処理手段を備えることを特徴とするデータベース演算処理装置の一例を説明した。また、テーブル内レコード群を等結合キーに第１のハッシュ関数を適用して得られる値に基づいて複数グループに分割する前処理手段と、分割後のハッシュグループ内のレコードを記憶装置から順次読み出すレコード入力手段と、読み出したレコードを等結合キーに第２のハッシュ関数を適用して得られる値に基づいて複数バッファに分割して格納するレコード格納手段と、バッファ上のレコードを指す複数のポインタと、バッファ毎に複数のポインタが指すレコードの組み合わせから自己結合の結果を生成する結合結果生成手段と、自己結合の結果生成されたレコードを記憶装置に出力する結果レコード出力手段と、を備えることを特徴とするデータベース演算処理装置の一例を説明した。また、前記複数バッファ内のレコードを、等結合キーの値に基づいて複数の小バッファに分割して格納する前記レコード格納手段と、複数の小バッファ毎に自己結合結果を生成する結合結果生成手段と、を備えることを特徴とするデータベース演算処理装置の一例を説明した。また、不等結合キーによる比較が大小比較である場合、前記複数の小バッファ内のレコード群を不等結合キーでソートし、小バッファ上の格納位置が昇順になっているレコードの組み合わせから自己結合結果を生成する前記結合結果生成手段を備えることを特徴とするデータベース演算処理装置の一例を説明した。
【００６０】
【発明の効果】この発明は、以上に説明したように構成されているので、以下に記載されるような効果を奏する。
【００６１】この発明に係るデータベース演算処理装置においては、複数テーブルのレコードの組み合わせを得る結合演算の際に、問合せに指定された結合条件に同一テーブルの同一カラム間の結合条件が含まれるかどうかを判定する自己結合検出部と、一つのテーブルから結合演算の結果を導出する自己結合演算実行部と、を備えるので、自己結合演算を通常の結合演算に比べて高速に処理することができる。
【００６２】また、前記自己結合検出部は、問合せ言語のテーブルとカラムの識別子（名前）に基づいてテーブルおよびカラムの同一性を判定するので、従来より用いていた問合せ文の表記を変更することなく自己結合の検出を行うことができる。
【００６３】また、前記自己結合検出部は、問合せ言語に補助的に加えられたコメントに基づいてテーブルおよびカラムの同一性を判定するので、問合せ言語の規格を変更することなく自己結合の指定をユーザが行うことができる。
【００６４】また、前記自己結合検出部は、自己結合であることを明示的に示す問合せ言語のキーワードに基づいてテーブルおよびカラムの同一性を判定するので、ユーザが自己結合を明示的に指定することができる。
【００６５】また、前記自己結合検出部は、問合せ処理の実行時に入力テーブルとカラムの識別子を比較することでテーブルおよびカラムの同一性を判定するので、自己結合を高速に処理することができる。
【００６６】また、この発明に係るデータベース演算処理装置においては、結合条件を表す問合せの条件式がカラムの比較項の論理積で表される場合、各比較項が等値比較であるかその他の比較であるかに基づいて、条件式中のカラムを等結合キーと不等結合キーのいずれか一方に分類する結合キー分類部を備えるので、完全な等結合でない問合せに対しても等結合と同様の効率的な処理方式を用いることができる。
【００６７】また、結合キーのうち等結合キーだけを用いたテーブル内レコード群のソートを行う並び替え処理部を備えるので、等結合でない問合せに対してソートマージ処理方式を適用することができる。
【００６８】また、前記結合演算処理方式は、結合キーのうち等結合キーだけを用いてテーブル内レコード群のハッシュ分割を行うハッシュ分割処理部を備えるので、等結合でない問合せに対してハッシュ処理方式を適用することができる。
【００６９】また、この発明に係るデータベース演算処理装置は、テーブル内レコード群を等結合キーでソートする並び替え処理部と、ソート結果のレコードを記憶装置から順次読み出して、同一等結合キー値を持つレコードをバッファに格納するレコード格納部と、バッファ上のレコードを指す複数のポインタと、複数のポインタが指すレコードの組み合わせから自己結合の結果を生成する結合結果生成部と、自己結合の結果生成されたレコードを記憶装置に出力する結果出力部と、を備えるので、自己結合演算を高速に実行することができる。
【００７０】また、テーブル内レコード群があらかじめ等結合キーでソートされている場合には並び替え処理部によるソート処理を省略するので、あらかじめソートされたテーブルの自己結合演算を高速に実行することができる。
【００７１】また、前結合結果生成部は、不等結合キーによる比較が大小比較である場合、前記バッファに蓄えられたレコードを不等結合キーでソートし、バッファ上の格納位置が昇順になっているレコードの組み合わせから自己結合結果を生成するので、大小関係に基づく自己結合演算を高速に実行することができる。
【００７２】また、この発明に係るデータベース演算処理装置は、テーブル内レコード群を等結合キーに第１のハッシュ関数を適用して得られる値に基づいて複数グループに分割するハッシュ分割処理部と、分割後のハッシュグループ内のレコードを記憶装置から順次読み出して、読み出したレコードを等結合キーに第２のハッシュ関数を適用して得られる値に基づいて複数バッファに分割して格納するレコード格納部と、バッファ上のレコードを指す複数のポインタと、バッファ毎に複数のポインタが指すレコードの組み合わせから自己結合の結果を生成する結合結果生成部と、自己結合の結果生成されたレコードを記憶装置に出力する結果出力部と、を備えるので、自己結合演算を高速に実行することができる。
【００７３】また、前記レコード格納部は、前記複数バッファ内のレコードを、等結合キーの値に基づいて複数の小バッファに分割して格納し、前記結合結果生成部は複数の小バッファ毎に自己結合結果を生成するので、等結合キーの値に重複が多いデータに対しても自己結合演算を高速に実行することができる。
【００７４】また、前記結合結果生成部は、不等結合キーによる比較が大小比較である場合、前記複数の小バッファ内のレコード群を不等結合キーでソートし、小バッファ上の格納位置が昇順になっているレコードの組み合わせから自己結合結果を生成するので、大小関係に基づく自己結合演算を高速に実行することができる。
【出願人】 【識別番号】０００００６０１３
【氏名又は名称】三菱電機株式会社
【出願日】 平成１２年７月７日（２０００．７．７）
【代理人】 【識別番号】１０００９９４６１
【弁理士】
【氏名又は名称】溝井 章司 （外２名）
【公開番号】 特開２００２−２４２８１（Ｐ２００２−２４２８１Ａ）
【公開日】 平成１４年１月２５日（２００２．１．２５）
【出願番号】 特願２０００−２０６３４５（Ｐ２０００−２０６３４５）