情報検索装置及びデータベース検索前処理回路及び情報検索方法
【課題】 複合データベースの検索において、通常の検索指定に基づけば、リソース消費量が装置で利用可能な上限値を超えて、従来方式では検索実行が不可能となる場合でも、検索の実行を可能とする装置、方法を得る。
【解決手段】 所望の情報検索を記述する検索式を読込み、所定の簡易形式に分割する検索式分割部１０４と、この分割した簡易形式検索式による検索時の必要リソースがシステムで持つリソース上限値内であるかを評価する検索式評価部１０３と、検索式分割部が出力する検索命令リストに従って所望の情報検索を行う検索処理部と、を備えて、検索式分割部は、検索式評価部がリソース上限値内であると評価する簡易形式に分割して、検索処理部１０５は、この簡易形式に基づいて情報検索を行うようにした。
【解決手段】 所望の情報検索を記述する検索式を読込み、所定の簡易形式に分割する検索式分割部１０４と、この分割した簡易形式検索式による検索時の必要リソースがシステムで持つリソース上限値内であるかを評価する検索式評価部１０３と、検索式分割部が出力する検索命令リストに従って所望の情報検索を行う検索処理部と、を備えて、検索式分割部は、検索式評価部がリソース上限値内であると評価する簡易形式に分割して、検索処理部１０５は、この簡易形式に基づいて情報検索を行うようにした。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、マルチデータベース・システムにおけるデータ検索の容易化、特に複雑な検索条件により多量の資源を使用する検索の容易化に関するものである。
【背景技術】
【０００２】
従来、マルチデータベース・システムにおけるデータ検索に関して、検索コスト、つまり検索時間や検索時のメモリ等の資源を少なくしたり、検索意図に添った適切対象に絞り込む、といった検索装置、方法が多数提案されている。
例えば特許文献１の「データベース照会最適化システム」によれば、マルチデータベースシステムのデータ照会に要するコストを、最適化する方式が提案されている。上記特許文献１の方式では、最適化の第１段階として、ＳＱＬのようなデータ照会言語から、先ずリソース全体の消費量の最適化を考えて、例えば左に深く分岐した、つまり検索処理回数が多い、照会ツリーを一旦生成する。その後に第２段階として、応答時間の短縮を考えて、左に深い照会ツリーを平衡の取れたツリーに変換する。このとき上記文献では、第２段階の平衡の取れたツリーへの変換方式として、ボトムアップ・アプローチや、トップダウン・アプローチという方式が示されている。
【０００３】
ところで、昨今、流通するマルチメディアデータの増加に伴い、データベース（ＤＢ）に蓄積されるデータ規模の巨大化、検索対象の多様化が予測される。こうなると、必然的にこれらＤＢ中に登録されたデータの増加、検索処理の負荷が高い検索方式の適用、検索式の複雑化などの要因で、検索時のリソースの消費量が増加する。その場合、従来の検索式の最適化を行う検索装置では、検索式の複雑化により装置で利用可能なリソースの上限値を超えることも起こり得る。
【特許文献１】特開平８−３２８９２０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来のデータ検索装置、方法においては、ＳＱＬのような検索式を入力として、複数のデータベースで構成される複合データベースから所望の情報を得す場合に、上記特許文献１等のさまざまな検索式の最適化方法が考えられてきた。しかしそれらの検索式の最適化方法は、検索時間や、リソース使用量を最小化することである。従って、検索条件が複雑化してリソース使用量が利用可能な上限値を超えるような場合については言及されていず、従って複雑な検索式または多量のデータベースのために検索が実行不可能となる場合が生じるという課題がある。
【０００５】
この発明は上記の課題を解決するためになされたもので、複合データベースの検索において、通常の検索指定に基づけば、リソース消費量が装置で利用可能な上限値を超えて、従来方式では検索実行が不可能となる場合でも、検索の実行を可能とする装置、方法を得ることを目的とする。
また更に、そのままでは検索不可能な条件を検索可能とした上で、その可能な検索処理を高速化する装置、方法を得ることを目的とする。
【課題を解決するための手段】
【０００６】
この発明に係る情報検索装置は、データベースから所望の情報を検索する情報検索装置において、
上記所望の情報検索を記述する検索式を読込み、この読込んだ検索式を所定の簡易形式に分割する検索式分割部と、
上記検索式分割部が分割した簡易形式検索式による検索時の必要リソースがシステムで持つリソース上限値内であるかを評価する検索式評価部と、
上記検索式分割部が出力する検索命令リストに従って上記所望の情報検索を行う検索処理部と、を備えて、
上記検索式分割部は、上記検索式評価部がリソース上限値内であると評価する簡易形式に分割して、上記検索処理部は、この簡易形式に基づいて情報検索を行うようにした。
【発明の効果】
【０００７】
この発明によれば、検索式分割部と検索式評価部とを備えて、検索式分割部は検索式評価部がリソース上限値内であると評価する簡易形式に分割して、検索処理を行うので、検索不可能な条件でも検索可能にして検索処理ができる効果がある。
【発明を実施するための最良の形態】
【０００８】
実施の形態１．
従来方式では検索実行が不可能となる場合でも、検索の実行を可能とする装置、方法を図に基づいて説明する。
なお、本実施の形態における装置が検索の対象とするデータベースは、マルチメディアデータを蓄積した個別ＤＢを複数照合する複合ＤＢである。マルチメディアデータとは、文書データや、画像データ、音声データ、映像データ、その他バイナリデータなどの、電子化されたデータのことである。また複合ＤＢは、個別ＤＢと同じ装置上に構成されていてもよいし、ネットワークで接続された異なる個別ＤＢ装置を集合した形態であってもよい。
【０００９】
図１は本実施の形態における情報検索装置の構成を示す図である。図において、情報検索装置は、以下の要素で構成される。即ち、検索を依頼するユーザから検索式１０１の入力を受け付ける検索式入力部１０２、本発明の重要な要素である、入力された検索式による検索時のリソース消費量を評価する検索式評価部１０３、同じく重要な要素である、検索式を分割して部分検索式と検索命令リストを出力する検索式分割部１０４、入力された検索式や、検索式分割部１０４より出力された検索命令リストに従って、実際の検索処理を実行する検索処理部１０５、検索結果１１２を検索依頼したユーザに出力する検索結果出力部１０６、である。
検索処理部１０５は、更に以下の要素で構成される。即ち、検索式や検索命令リストに従って検索処理を制御する検索制御部１０７と、複合ＤＢに関連付けられている１種類以上の個別ＤＢ１１１に対して検索を実行する検索実行部１０９、検索実行部１０９で得られた検索結果を中間結果として管理する中間結果管理部１１０、中間結果間の集計（論理演算）処理を実行する中間結果集計部１０８、である。
なお、検索実行部１０９は、個別ＤＢに対する検索機能を内包していてもよいし、別の装置上にある個別ＤＢの検索機能を呼び出して検索結果を得るものであってもよい。
またこれらの検索式評価部等の各部は、その機能を実現するソフトウェアのプログラムで記述されており、図示はされていないが、プロセッサ（ＣＰＵ）とメモリがあって、これら各部の記述されたプログラムを実行して、検索式評価等の各機能を得ている。
【００１０】
ここで言うリソースは、情報検索装置に搭載されている、検索処理部１０５や検索実行部１０９が、バッファとして使用する際の容量が問題となるメモリであってもよいし、一時的に使用する他のメモリでもよい。また、一時ファイルを格納するディスク装置でもよい。または他にも、ＣＰＵ使用率の基となるＣＰＵや、ネットワーク使用率の基となるチャネルでもよい。同様に、異なる装置上にある個別ＤＢ検索装置のメモリやディスク装置、ＣＰＵ、チャネルでもよい。
その他に検索が出来なくなるファクターとして、情報検索装置で設定される検索式の長さが長過ぎる場合や、演算子の数が多過ぎるなど、情報検索装置の諸元も考えられる。また更に、個別ＤＢが全文検索を実行する場合の、検索キーワード数や、ユニークな文字数が多過ぎる場合もある。
【００１１】
検索時のリソース消費量の評価では、複合ＤＢに関連づけられている個別のＤＢに対する検索処理や、結果の集計処理について、実行時のリソース情報を検索式評価部１０３が保持し、その情報を元に全体の検索実行時のリソース消費量を評価する。
具体的には例えば、個別のＤＢが文書検索用のＤＢであった場合は、検索時にディスク装置からメモリ上に読み込まれる索引のサイズを、検索キーワードの文字数から計算しても良い。多くの文書検索では、文書中に出現するキーワードや文字の出現位置の情報を、索引としてＤＢに保持している。キーワードの文書中での出現頻度によって、該当する出現位置情報のサイズは変化するが、検索式中の検索キーワードの出現位置情報の合計サイズを調べることで、それがメモリの容量を超えるか否かを評価することができる。そのために、出現位置情報のサイズの情報を、出現位置情報とは別に記録しておいてもよいし、直接出現位置情報の記録されたファイルのサイズを調べても良い。また、キーワードや文字の出現頻度と、検索式中の検索キーワード数やキーワードの文字数をパラメータにして、索引サイズ等の必要となるメモリサイズを計算する計算式を予め定義しておいても良い。例えば単純に、（比例定数Ｋ×キーワードの出現頻度）を１検索キーワードの出現位置情報のサイズとして、その総和をとる等の計算式が考えられる。いずれの場合も、キーワードの出現頻度や、出現位置情報のサイズは、文書をＤＢに登録する時点で取得することができる。
【００１２】
所定のパーセンテージ、例えば最初の１０パーセントを検索してみて、検索に該当する出現頻度を抽出して、それを１０倍してオーバフローするかどうかを調べてもよい。または、過去に入力された検索式とその消費リソース量の記録を一定回数分保存しておき、検索時にはそれら検索式によるリソース消費量の統計的情報を利用しても良い。例えば統計情報の中には、検索式毎の検索ヒット件数や、検索実行中のメモリやＣＰＵのリソースの消費量の推移などを含んでも良い。中間結果集計処理の場合では、予想される検索のヒット件数から見積もるようにしてもよい。
また、検索時にリソースを大量に消費する個別のＤＢ１１１と、そうでない個別のＤＢが共存している場合は、ＤＢ毎の重みを設定してもよい。
また、リソースが検索実行部の諸元であった場合、例えば受理できる検索式の長さの上限が設定されている場合は、文字数やバイト数をカウントするだけでよい。すなわち個別のＤＢの検索実行部１０９が１回に受理できる検索式の長さの上限がＮバイトと定められている場合、ｓｔｒｌｅｎ（）のような文字列の長さを取得する関数で、検索式１０１の長さを取得することで、上限Ｎバイトを超えているか否かを容易に判定することができる。
このように、評価するための上限情報と方式を検索式評価部１０３が保持しており、その情報を元にリソース消費量を評価する。
【００１３】
図２は、本実施の形態における情報検索装置の、検索式分割部１０４と検索式評価部１０３による、検索処理の流れを示した動作フロー図である。
この図により本実施の形態における情報検索装置の動作を説明する。情報検索装置は、ステップＳ２０１（以後ステップの記述を省略する）で検索式入力部１０２により入力された所望の情報検索を記述した所定検索式を読み込むと、Ｓ２０２でこれをその所定形式での最簡易形式に分解して、Ｓ２０３で検索式評価部１０３により、この簡易形式による検索式で検索した時に情報検索装置が使用するリソースの消費量を評価する。この検索式の評価により、検索時のリソース消費量が、情報検索装置で利用可能なリソースの上限値（以降、リソース上限値と呼ぶ）の範囲であった場合（Ｎｏ）は、Ｓ２０４に進む。そして検索式分割部１０４は簡易形式を合成して、上位の簡易形式とする。そしてＳ２０３の評価をして、以後この評価がリソース上限値を超えるまでＳ２０４のループを繰返す。
ところがＳ２０２の検索式による評価で、検索時のリソース消費量が情報検索装置で利用可能なリソースの上限値を超えていた場合（Ｙｅｓ）は、Ｓ２０５で検索式分割部１０４により、先のＳ２０３でリソース上限値を超える直前の検索式について、検索時のリソース消費量がリソース上限値の範囲内に収まるよう、複数の部分検索式に分割する等、検索式を再構成する。Ｓ２０３’においてこの部分検索式でよいことを確認すると、Ｓ２０６でこの部分検索式を検索命令リストとして出力する。そして検索処理部１０５により、この検索命令リストに従った検索処理が実行される。最後にこの検索処理によって得られた検索結果を、検索結果出力部１０６からユーザに対して出力して終了する。
【００１４】
検索命令リストとは、ユーザから入力された検索式と等価になるよう、部分検索式による検索の実行や、中間結果の集計処理の実行順を指定するリストである。例を図４に検索式と検索命令リストの一例を示す。いま、検索式４０１が入力され、検索式の評価の結果、検索時のリソース消費量がリソース上限値を超えていたとする。この検索式４０１を検索式分割部１０４で分割した結果として、検索命令リスト４０２が出力される。図４の例では、検索命令リスト４０２は、最初に検索実行部で部分検索式（Ａ ＡＮＤ Ｂ）を実行し、次に検索実行部で部分検索式（Ｃ ＡＮＤ Ｄ）を実行し、最後に直前の２回の検索で得られた中間結果の集計処理ＯＲを実施することを指定している。検索命令リスト４０２のように処理することで、検索式４０１と同じ検索結果を得ることができる。
単純に行うにはこのように、分割は論理演算の各論理毎に分割すればよい。
また検索結果や中間結果とは、検索式で与えられた検索条件に適合したレコード情報の集合である。レコード情報には、ＤＢ中のレコードの識別子や、検索条件に適合したレコードを評価したスコア、ＤＢのカラムに格納されているデータなどを含んでよい。
【００１５】
図３は、本実施の形態における情報検索装置の検索処理部１０５による検索処理の流れを示した動作フロー図である。検索処理部１０５は、ユーザから入力された検索式や、部分検索式と検索命令リストに従って、検索を処理する。
例えば部分検索式を含む検索命令リストが入力されると、検索制御部１０７はＳ３０１で、検索命令リストから検索の実行命令を１つ、例えば検索（Ａ ＡＮＤ Ｂ）を取得する。続いてＳ３０２で、取得した命令が部分検索式を実行する内容であれば（検索）に移り、検索実行部１０９に対して部分検索式による検索の実行命令を発行する。検索実行部１０９はＳ３０３で、後の実施の形態で述べるように、必要に応じて部分検索式から検索を実行するための検索プランを生成する。Ｓ３０４では、複合ＤＢに関連づけられている個別のＤＢ１１１に対して検索を実行し、検索結果を取得する。取得した検索結果はＳ３０５で、検索の中間結果として中間結果管理部１１０に格納する。
Ｓ３０２で、取得した命令が中間結果の集計の実行であった場合は（集計）に移り、Ｓ３０６で中間結果管理部１１０から複数の中間結果を取得する。Ｓ３０７で中間結果の集計処理を行い、Ｓ３０８で次の部分検索式に移り、Ｓ３０４またはＳ３０６の処理を繰り返す。こうして得られた中間結果を、Ｓ３０９で、最終検索式に基づいて中間結果を集計する。中間結果の集計は、Ｓ３０６で逐次実行してもよい。そして、検索結果出力部１０６に対して出力する。
【００１６】
検索処理部１０５への入力が、ユーザから入力された検索式であった場合は、Ｓ３０１や、Ｓ３０２をスキップして、直接検索実行部１０９でＳ３０４以降、またはＳ３０６を実行してもよい。また、中間結果管理部１１０を介さずに、直接ステップＳ３０９で検索結果出力部１０６に検索結果を出力してもよい。
また検索実行部１０９では、Ｓ３０３の検索プラン生成処理ステップで、部分検索式による検索時間や、検索時のメモリ使用量が最小になるよう、部分検索式の最適化を行ってもよい。
検索実行や、中間結果集計の処理では、それ以前の処理の結果によっては、実行する必要がないものもある。そのような場合、実行する必要がない検索命令をスキップしてもよい。例えば、次の検索式が与えられ、それ以降の（０１），（０２），（０４）の３つの部分木に分割されたとする。
「（（Ａ ＡＮＤ Ｂ） ＯＲ （Ｃ ＡＮＤ Ｄ）） ＡＮＤ （Ｅ ＯＲ Ｆ）」
（０１）検索（Ａ ＡＮＤ Ｂ）
（０２）検索（Ｃ ＡＮＤ Ｄ）
（０３）集計ＯＲ（検索１、２の中間結果を集計）
（０４）検索（Ｅ ＯＲ Ｆ）
（０５）集計ＡＮＤ（検索４、集計３の中間結果を集計）
このとき、例えば、集計（０３）の実行結果が偽であった（中間結果が何も無い）場合、検索（０４）を実行しなくてよい。
【００１７】
図１の検索式入力部１０２ないし中間結果管理部１１０の各処理部は、１つのプロセッサで実行されるプログラムであってもよいし、それぞれ専用のプロセッサで実行されるように構成してもよい。
またユーザが入力する検索式は、ユーザが直接キーボードなどの入力装置で入力してもよいし、検索式を記述したファイルを入力し、これを検索式入力部１０２が読取るようにしてもよい。
入力された検索式１０１や、検索式入力部１０２から検索処理部１０５に伝達する検索式、部分検索式、検索命令リストは、メモリ上の情報としてプロセッサが図示しないバスを通じて伝達してよいし、一時ファイルを介して一括伝達してもよい。また、グラフィカルユーザインターフェースを通してユーザが入力した検索条件を、情報検索装置の入力の形式に変換する処理を含んでもよい。
中間結果管理部１１０では、メモリ上で中間結果を管理してもよいし、中間結果をディスク装置など外部記憶装置上に一時ファイルとして記憶し、後で利用してもよい。検索実行部１０９や検索処理部１０５が出力する検索結果も、メモリ上の情報として伝達してもよいし、ファイルを介して伝達してもよい。
検索結果出力部１０６は、結果を画面などの出力装置に出力してもよいし、ファイルに出力してもよい。また、検索結果を編集・加工・利用する別の装置にメモリ上の情報として出力してもよい。
【００１８】
本実施の形態における情報検索装置は、上記のように、ユーザが入力した検索式の検索時のリソース消費量を評価し、リソース上限値を超えていた場合は検索式を分割して検索を実行するように構成されている。このため従来の方式で、ユーザから入力された検索式により検索時のリソース消費量がリソース上限値を超えるため検索の実行が不可能であった場合でも、検索の実行が可能である。
【００１９】
実施の形態２．
先の実施の形態における情報検索装置では、検索式を分割して、検索の処理を分割する装置を説明した。こうすると、検索式の分割数が多いと、検索の初期化処理や中間結果管理部へのデータの入出力処理等により、検索時間が増大することが予想される。言い換えれば、検索式の分割数が少ないほど、全体の検索処理の効率は良くなる。ここでは情報検索装置が、検索式分割部により検索処理を向上する分割を行う方式を説明する。
一般に論理式は、木構造の論理に展開可能である。そこで本実施の形態における検索式の分割方式は、検索式を木構造の論理式とみなして、２分木と呼ばれる木構造に展開する。２分木とは、リーフを除く全てのノードにおける子の数が２以下である木構造である。検索式を２分木に展開したとき、その木のリーフは、１つの検索実行部の検索処理に対応し、内部ノードは中間結果集計部の集計処理に対応する。この２分木の高さをＤとする。
【００２０】
図５は、本実施の形態における情報検索装置の検索式分割部による検索式分割処理を示す動作フロー図である。
図において、検索式分割部１０４ｂは、検索式が入力されると、ステップＳ５０１で検索式を２分木に展開する。Ｓ５０２では高さｉが１の部分木を構築する。次にＳ５０３で、前のステップで構築した部分木に対して、検索式評価部１０３により検索時のリソース消費量を評価する。Ｓ５０３で部分木による検索時リソース消費量がリソース上限を超えていない場合（Ｎｏ）は、次のＳ５０４で高さｉ＋１の部分木を構築する。そしてＳ５０３で上限値になるまで木を高くして行く。
そしてＳ５０３で部分木による検索時リソース消費量がリソース上限を超える場合（Ｙｅｓ）はＳ５０５で、Ｓ５０３で調べてＹｅｓになる直前の最も高さが高い部分木による部分検索式を分割して新しい部分検索式を持つ部分木によってもリソースの上限値を超えないかをＳ５０３’で確認して、Ｓ５０６で部分検索式と、中間結果集計処理（ルート）を検索命令リストとして出力する。即ちＳ５０３とＳ５０４の処理を、高さｉ＝１（すなわちリーフのみの部分木）から、最大Ｄまで繰り返す。そしてＳ５０１で展開した２分木の分割が完了したら、Ｓ５０６で検索命令リストを出力して終了する。
【００２１】
このようにＳ５０１で検索式を２分木に展開したが、検索式を２分木に展開する方法は複数ある。例えば図１３の検索式１１０１は、木１１０２のようにも、木１１０３のようにも展開可能である。しかし木１１０２のように、左（または右）に深い木の場合は、検索式の分割数が多くなる可能性がある。例えば、部分木１１０４がひとつの部分検索式として分割された場合、リーフＣ、リーフＤは、単独で部分検索式となり、分割効率がよくない。一方で、木１１０３のように平衡の取れた木（高さが最小の木）の場合、木１１０２のような問題がない。従って検索式を２分木に展開する場合は、木１１０３のような、平衡の取れた木に展開する。
【００２２】
本実施の形態における検索式分割処理の動作を図６により説明する。その場合の例として図４の検索式４０１を用いる。
１）検索式６０１が入力されると、Ｓ５０１で検索式６０１は２分木６０２に展開される。ここで、ＡないしＤはリーフで、複合ＤＢに関連づけられた個別のＤＢに対する検索条件でもある。内部ノードＥないしＧは、中間結果の集計処理である。この例では中間結果の集計は、ＡＮＤまたはＯＲの論理演算としている。ところで例としてリソース上限値を１００、ＡないしＤ単体の検索時のリソース消費量を３０とする。説明を判りやすくするため、中間結果の集計処理はリソースを消費しないものとする。また部分木による検索時のリソース消費量は、リーフ単体での検索時のリソース消費量の和とする。なお、木６０２の高さは３である。
２）Ｓ５０２で、高さ１の部分木、即ち木Ａ、木Ｂ、木Ｃ、木Ｄを構築する。
【００２３】
３）Ｓ５０３で、Ｓ５０２で構築した部分木の、検索時のリソース消費量を評価する。評価の結果、いずれも３０であり、リソース上限（１００）の範囲内である。
４）Ｓ５０４で、高さ２の部分木を構築する。即ち木ＡＢＥ，木ＣＤＥを構築する。
５）Ｓ５０３で、Ｓ５０２で構築した部分木の、検索時のリソース消費量を評価する。評価の結果はいずれも６０であり、リソース上限の範囲内である。
６）Ｓ５０４で、高さ３の部分木を構築する。即ち木ＡＢＣＤＥＦＧを構築する。
７）Ｓ５０３で、Ｓ５０２で構築した部分木の、検索時のリソース消費量を評価する。評価の結果は１２０であり、リソース上限（１００）を超えている。
８）Ｓ５０５で、木ＡＢＣＤＥＦＧ中の、２つの高さ２の部分木に対応した検索式を構築する。これは明らかに評価が６０であり、リソース範囲内である。Ｓ５０６でこの高さ２の部分木に対応した検索式の情報と、リーフＧの情報を、検索命令リストとして出力する。すなわち、部分検索式（Ａ ＡＮＤ Ｂ）、部分検索式（Ｃ ＡＮＤ Ｄ）、中間結果集計処理ＯＲを、検索命令リスト（図４の検索命令リスト４０２）とする。
【００２４】
本実施の形態における情報検索装置は、上記のように検索式を２分木に展開後、リーフからボトムアップに部分木を長く構築して、リソース消費量がリソース上限値を超えたところで、その直前の最長部分木で分割するように構成しているので、検索式の分割処理において、部分検索式による検索時のリソース消費量がリソース上限の範囲内で最大にできる。その結果、検索式の分割数を少なくできる。
【００２５】
実施の形態３．
先の実施の形態と同様目的で、他の動作を行う情報検索装置を説明する。
本実施の形態における情報検索装置の動作を図７のフロー図により説明する。図において、情報検索装置の検索式分割部１０４ｃは、検索式が入力されるとステップＳ７０１で、検索式を２分木に展開し、さらに２分木の内部ノードを走査して、同じラベルを持つ親子関係にあるノードを結合する。Ｓ７０１の処理により、２分木では内部ノードの子の数が必ず２以下であったものが、内部ノードが２以上の子を持つことになる。この木の高さをＤとする。Ｓ７０２以降では、実施の形態２に示した処理の流れと同様に、ボトムアップに部分木を構築する。Ｓ７０２で、高さ１の部分木を構築する。次にＳ７０３で、Ｓ７０２で構築した部分木に対して検索式評価部１０３により検索時のリソース消費量を評価する。Ｓ７０３で部分木による検索時リソース消費量がリソース上限を超えていない場合（Ｎｏ）は、Ｓ７０４で高さｉ＋１の部分木を構築する。このＳ７０３とＳ７０４を最大Ｄの高さまで繰返す。
そしてＳ７０３で部分木による検索時リソース消費量がリソース上限を超える場合（Ｙｅｓ）は、Ｓ７０５でその直前の部分木による分割を再検討して、各々の部分木による分割が検索時のリソース消費量がリソース上限の範囲で最大となり、つまり分割数が最小となる部分木を構築する。これをＳ７０６で、集計処理論理と、分割された高さｉの部分木に対応する部分検索式の情報として検索命令リストを出力し、分割を終了する。
【００２６】
先の実施の形態２における図５のＳ５０４の処理では、高さｉの木は、一意に２つの高さｉ−１の部分木に分割できた。しかし本実施の形態における図７のＳ７０５の処理で、高さｉの木を高さｉ−１の木に分割する方法は、何通りも存在する。Ｓ７０４における部分木の分割処理のような、部分木の検索時のリソース消費量をリソース上限の範囲内で最大とする、ノードの組合せ最適化問題は、近似解を多項式時間で得るアルゴリズムが考案されており、高速に処理することが可能である。
【００２７】
図８は、本実施の形態における、検索式分割処理の例を示す図である。
いま、検索式８０１が入力されたとする。このとき、先の実施の形態２に示した、検索式を２分木８０２に展開してから分割する方式では、２分木８０２は、部分木ＡＢＧ、部分木ＣＤＨ、部分木ＥＦＩの３つの部分木に分割される。検索命令リストは以下の５つの処理からなる。
（１）検索（Ａ ＯＲ Ｂ）（Ｇをルートとする部分木の処理）
（２）検索（Ｃ ＯＲ Ｄ）（Ｈをルートとする部分木の処理）
（３）中間結果集計ＯＲ （内部ノードＪの処理）
（４）検索（Ｅ ＯＲ Ｆ）（Ｉをルートとする部分木の処理）
（５）中間結果集計ＯＲ（内部ノードＫの処理）
【００２８】
本実施の形態における検索式分割処理の流れは以下の通りである。
１１）検索式８０１が入力されると、Ｓ７０１で検索式８０１を２分木８０２に展開する。ここで、ＡないしＥはリーフで、複合ＤＢに関連づけられた個別のＤＢに対する検索条件である。内部ノードＧないしＫは、中間結果の集計処理である。実施の形態２と同様に、この例では中間結果の集計は、ＡＮＤまたはＯＲの論理演算としている。リソース上限値を１００とし、ＡないしＥの検索処理のリソース消費量は、図８に示す通りであるとする。更に、木８０２で同じラベルを持ち、親子関係にある内部ノードＧないしＫを結合して、木８０３が得られる。
１２）Ｓ７０２で、高さ１の部分木を構築する。すなわち木Ａ〜木Ｆである。
１３）Ｓ７０３で、Ｓ７０２で構築した部分木の、検索時のリソース消費量を評価する。評価の結果、リソース消費量は３０または４０で、いずれもリソース上限（１００）の範囲内である。
【００２９】
１４）Ｓ７０４で、高さ２の部分木を構築する。すなわち木ＡＢＣＤＥＦＫである。
１５）Ｓ７０３で、Ｓ７０４で構築した部分木の、検索時のリソース消費量を評価する。評価の結果は２００であり、リソース上限を超えている。
１６）Ｓ７０５で、この場合に木ＡＢＣＤＥＦＧは高さ２であり、高さ１にすることは意味がないので、木ＡＢＣＤＥＦＧを２つ以上の各種の部分木に分割する。ここで例えば、木８０３のリーフを左から順に選んで部分木に分割した場合、リーフＡＢを含む部分木、リーフＣＤＥを含む部分木、リーフＫを含む３つの部分木８０３に分割できる。または木８０４のようにリーフの組合せを変えると、最終的に木８０５のように、部分木ＡＣＤＧと部分木ＢＥＦＨの２の部分木と、ルートに分割できる。
１７）木８０３の分割が完了したので、Ｓ７０６で検索命令リストを出力して終了する。
このときの、検索命令リストは以下の３つの処理からなる。
（１１）検索（Ａ ＯＲ Ｃ ＯＲ Ｄ）（Ｇをルートとする部分木の処理）
（１２）検索（Ｂ ＯＲ Ｅ ＯＲ Ｆ）（Ｈをルートとする部分木の処理）
（１３）中間結果集計ＯＲ（内部ノードＫの処理）
【００３０】
本実施の形態における情報検索装置は、上記のように、検索式を２分木に展開後、更に同じラベルを持つ親子関係にあるノードを結合し、リーフからボトムアップに部分木を構築し、リソース消費量がリソース上限値を超えたところで、部分木を分割するように構成しているので、検索式の分割処理において、先の実施の形態における方式と比べ、更に分割数を少なくできる。
【００３１】
実施の形態４．
特別な形式の検索式について説明する。本実施の形態においては、情報検索装置の検索式分割部１０４ｄは、検索式をＤＮＦ（Ｄｉｓｊｕｎｃｔｉｖｅ Ｎｏｒｍａｌ Ｆｏｒｍ）形式の木構造に変形する。ＤＮＦは、積和標準形とも呼ばれる論理式の形式の一つで、論理変数を論理演算子ＡＮＤで結合した項を、論理演算子ＯＲで結合した形の論理式であり、高さ３の木として表現できる。なお任意の論理式をＤＮＦ形式に変形可能である。
【００３２】
図９は、本実施の形態における情報検索装置の、検索式分割部１０４ｄによる検索式分割処理の動作を示すフロー図である。検索式分割部１０４ｄは、検索式が入力されるとＳ９０１で、検索式をＤＮＦ形式の木に変形する。Ｓ９０２以降は、実施の形態３に示した処理の流れと同様に、ボトムアップに部分木を構築する。即ちＳ９０２で、高さｉの部分木を構築する。次にＳ９０３で、Ｓ９０２で構築した部分木に対して検索式評価部１０３により検索時のリソース消費量を評価する。Ｓ９０３で部分木による検索時リソース消費量がリソース上限を超えていない場合（Ｎｏ）は、Ｓ９０４で高さｉ＋１の部分木を構築する。こうしてＳ９０３とＳ９０４で高さを順次高くした木を構築して行く。
Ｓ９０３で部分木による検索時リソース消費量がリソース上限を超える場合（Ｙｅｓ）は、Ｓ９０５で高さｉの部分木を、各々の部分木を検索時にリソース消費量がリソース上限の範囲で最大となるよう、すなわち分割数が最小となるよう、２つ以上の高さｉの部分木に分割する。こうしてＳ５０３ないしＳ５０５を高さｉ＝１からこの場合は最大３まで繰返して、ルート（中間結果集計処理）の情報と、分割された高さｉの部分木に対応する、部分検索式の情報を、Ｓ９０６で検索命令リストとして作成し、出力する。
このように、図７，図９に示す検索式の論理木の変換を行うことで、最適解が見つけやすくなる。
【００３３】
図１０を用いて本実施の形態における検索式分割処理の動作を説明する。
いま、検索式１００１が入力されたとする。このとき、先の実施の形態に示した方式では、検索式を２分木に展開後、更に同じラベルを持つ親子関係にあるノードを結合した木１００２に変形する。ここで、ＡないしＥはリーフである。内部ノードＪないしＮは、中間結果の集計処理である。実施の形態２と同様に、この例では中間結果の集計はＡＮＤまたはＯＲの論理演算としている。リソース上限値を１００、ＡないしＨの検索処理のリソース消費量は、図８の通りであるとする。またこの例での、中間結果集計処理のリソース消費量を以下のように定める。
ＡＮＤ処理・・・子のリソース消費量の最も大きいものと等しい
ＯＲ処理・・・子のリソース消費量の総和と等しい
先の実施の形態における方式では、木１００２は、部分木ＡＢＣＤＬ、部分木ＥＦＪ、部分木ＧＩＫ、部分木Ｈの４つの部分木に分割される。このときの検索命令リストは以下の７つの処理からなる。
（２１）検索（Ａ ＡＮＤ Ｂ ＡＮＤ Ｃ ＡＮＤ Ｄ）
（２２）検索（Ｅ ＯＲ Ｆ）
（２３）検索（Ｇ ＯＲ Ｉ）
（２４）検索（Ｈ）
（２５）中間結果集計ＯＲ（内部ノードＫの処理）
（２６）中間結果集計ＡＮＤ（内部ノードＭの処理）
（２７）中間結果集計ＯＲ（内部ノードＮの処理）
【００３４】
本実施の形態における検索式分割処理の動作は以下の通りとなる。
２１）検索式１００１が入力されると、Ｓ９０１で検索式１００１をＤＮＦ形式の木１００３に変形する。
２２）Ｓ９０２で、高さ１の部分木を構築する。すなわち木Ａないし木Ｈである。
２３）Ｓ９０３で、Ｓ９０２で構築した部分木の、検索時のリソース消費量を評価する。評価の結果、いずれもリソース上限（１００）の範囲内である。
２４）Ｓ９０４で、高さ２の部分木を構築する。すなわち木ＡＢＣＤＬ、木ＥＩＬ、木ＥＧＬ、木ＥＨＬ、木ＦＧＬ、木ＦＨＬ、木ＦＩＬである。
２５）Ｓ９０３で、Ｓ９０４で構築した部分木の、検索時のリソース消費量を評価する。評価の結果は、木ＡＢＣＤＬ、木ＥＩＬ、木ＦＩＬが５０、木ＥＧＬ、木ＦＧＬが４０、木ＥＨＬ、木ＦＨＬが２０であり、いずれもリソース上限の範囲内である。
２６）再びＳ９０４で、高さ３の木を構築する。すなわち、木ＡないしＮである。
２７）再びＳ９０３で、Ｓ９０４で構築した高さ３の木の、検索時のリソース消費量を評価する。評価の結果、リソース消費量は２７０であり、リソース上限値を超えている。
２８）Ｓ９０５で、木ＡないしＮを２つ以上の部分木に分割する。木１００４に示したように、部分木１００５、部分木１００６、部分木１００７の、３つの部分木に分割できる。
２９）Ｓ９０３’で、これらの個別の部分木を評価すると、部分木１００５と部分木１００６でも１００となり、リソース上限内である。従って木１００３の分割が完了したので、Ｓ９０６で検索命令リストを出力して終了する。
【００３５】
このときの、検索命令リストは以下の４つの処理からなる。
（３１）検索（（Ａ ＡＮＤ Ｂ ＡＮＤ Ｃ ＡＮＤ Ｄ）ＯＲ（Ｅ ＡＮＤ Ｉ））
（３２）検索（（Ｅ ＡＮＤ Ｇ）ＯＲ（Ｅ ＡＮＤ Ｈ）ＯＲ（Ｆ ＡＮＤ Ｇ））
（３３）検索（（Ｆ ＡＮＤ Ｈ）ＯＲ（Ｆ ＡＮＤ Ｉ））
（３４）中間結果集計ＯＲ（ルートノードの処理）
こうして実施の形態３と同様に、Ｓ９０５における部分木の分割処理のような、部分木の検索時のリソース消費量をリソース上限の範囲内で最大とするノードの組合せ最適化問題は、近似解を多項式時間で得るアルゴリズムが考案されており、高速に処理することが可能である。
【００３６】
本実施の形態における情報検索装置は、上記したように検索式をＤＮＦ形式の木に変形後、リーフからボトムアップに部分木を構築し、リソース消費量がリソース上限値を超えたところで、部分木を分割するように構成しているので、検索式の分割処理において、部分検索式による検索時のリソース消費量がリソース上限の範囲内で最大とすることができる。その結果、検索式の分割数を少なくすることができる。
【００３７】
本実施の形態の変形として、他の検索式分割部１０４ｅによる検索式の分割方式を説明する。即ち検索式をＣＮＦ（Ｃｏｎｊｕｎｃｔｉｖｅ Ｎｏｒｍａｌ Ｆｏｒｍ）形式の木構造に変形する。ＣＮＦは、和積標準形とも呼ばれる論理式の形式の一つで、論理変数を論理演算子ＯＲで結合した節を、論理演算子ＡＮＤで結合した形の論理式であり、この場合は高さ３の木として表現できる。また任意の論理式は、ＣＮＦに変形可能である。
【００３８】
この検索式分割部１０４ｅによる検索式分割処理の動作は、図９のＳ９０１の処理を「検索式をＣＮＦに変形する」ものと同等である。
この検索式分割部１０４ｅによる情報検索は、検索式をＣＮＦ形式の木に変形後、リーフからボトムアップに部分木を構築し、リソース消費量がリソース上限値を超えたところで、部分木を分割するように構成する。
従って検索式の分割処理において、部分検索式による検索時のリソース消費量を上限値内で最大にでき、検索式の分割数を少なくできる。
【００３９】
実施の形態５．
先の各実施の形態では、情報検索装置は内部的に部分木を構築し、リソース上限値内で最大リソース消費となる検索式を生成して、検索を実行した。本実施の形態では、情報検索装置が分割した検索式を画面やログファイルに出力する構成とした。
図１２は、本実施の形態における情報検索装置の構成例を示す図である。この構成は、先の各実施の形態における情報検索装置に、検索式分割部から出力された部分検索式を画面などの出力装置やログファイル１２０８などに出力する検索式出力部１２０５を追加した構成になっている。その他の検索式入力部１２０２、検索式評価部１２０３、検索式分割部１２０４、検索処理部１２０６、検索結果出力部１２０７は、先の実施の形態のそれらと同じ要素である。
なお、検索式出力部１２０５が画面などの出力装置やログファイル１２０８に出力する情報は、検索式分割部１２０４から出力された部分検索式や検索命令リスト、検索式を分割したか否かのフラグ情報、検索式の分割方法が複数ある場合はその分割方法などの情報でもよい。また、検索式入力部１２０２に入力された検索式をそのまま出力してもよい。
【００４０】
図１１は、本実施の形態における情報検索装置による、検索処理の動作を示した図である。
図に基づいて動作を説明する。Ｓ１３０１において検索式入力部１２０２で検索式の入力を受け付けると、Ｓ１３０２において検索式評価部１２０３で入力された検索式による検索時のリソースの消費量を評価する。検索式の評価により、検索時のリソース消費量がリソース上限値内であった場合（Ｎｏ）は、図示では詳細を示していないが、先の各実施の形態で説明したように、部分木の高さを順次高くして部分検索式を作成して、リソース上限内の最高高さの部分木でＳ１３０４に進む。即ちＳ１３０２の検索式の評価で、検索時のリソース消費量が利用可能な上限値を超える場合（Ｙｅｓ）に、Ｓ１３０３で検索式分割部１２０４によりリソース消費量が上限値内となるように複数の部分検索式に分割する。
そしてＳ１３０４では、検索式を分割した部分検索式や検索命令リストを、画面やログファイル等１２０８に出力する。Ｓ１２０５では、入力された検索式や、Ｓ１３０３で分割された部分検索式と検索命令リストに従って、検索処理部１２０６により検索処理が実行される。最後にＳ１３０６で、Ｓ１３０５の検索処理によって得られた検索結果を検索結果出力部１２０７からユーザに対して出力して終了する。
なおＳ１３０４の部分検索式の出力処理は、Ｓ１３０３後に実行される動作とすれば、どの段階で実行するようにしてもかまわない。
【００４１】
このように本実施の形態の情報検索装置は、検索式分割部で分割された検索式に関する情報を画面表示等で出力するので、ユーザが必要に応じて、検索式の分割状況を参照することができる。
【００４２】
なお、上記各実施の形態では、検索式分割部、検索式評価部等の各要素は、専用の機能を持つとして説明した。しかし汎用の計算機を用いて各実施の形態で説明した図２、３、５、７、９等の各図で示される機能を持たせたプログラムにより、同等の動作をさせる方法としてもよい。
このようにしても情報検索方法として同じ優れた効果が得られる。
【００４３】
実施の形態６．
以下、図１４を元に一般的な検索式分割処理の流れを示す。検索式を論理木に展開後の処理の流れは、図７のＳ７０２と同等である。
３１）検索式１４０１が入力されると、検索式１４０１を論理木１４０２に展開する。この例では中間結果の集計は、ＡＮＤまたはＯＲの論理演算としている。リソース上限値を１００とし、ＡないしＮの検索処理のリソース消費量は、図１４に示す通りであるとする。また、部分木のリソース消費量は、単純のため、その部分木の根のリソース消費量の総和とする。
３２）高さ１の部分木を構築する。すなわち、部分木Ａ〜Ｎである。この部分木の検索時のリソース消費量を評価すると、全て１００未満であり、リソース上限の範囲内である。
３３）高さ２の部分木を構築する。すなわち部分木１４０６，１４０７，１４０８である。これらの部分木の検索時のリソース消費量を評価すると、全て１００未満であるので、リソース上限の範囲内である。
３４）高さ３の部分木を構築する。すなわち部分木１４０９，１４１０である。
これらの部分木の検索時リソース消費量を評価すると、部分木１４０９のリソース消費量は３０であり、リソース上限の範囲内である。一方、部分木１４１０のリソース消費量は１７０であり、リソース上限を超えて得いる。
３５）部分木１４１０の検索時のリソース消費量が、リソース上限を超えているため、部分木を分割する。最適な分割の例として部分木１４１２と１４１３のように分割される。分割後は、分割された部分木の検索式と、高さ３の部分木の根のラベルの情報が、検索命令リストに出力される。このとき検索命令リストは以下のようになる。
（４１）検索（部分木１４１２）
（４２）検索（部分木１４１３）
（４３）中間結果集計ＡＮＤ（部分木１４１２，１４１３の実行結果の集計）
３６）高さ４の部分木を構築する。すなわち部分木１４１１である。部分木１４１１の検索時のリソース消費量を評価すると６０であり、リソース上限の範囲内である。
３７）高さ５の部分木を構築する。すなわちノードＴを根とする木１４０５であるが、既にノードＳを根とする部分木は分割済みであり、木１４０５の検索時のリソース消費量が、リソース上限を超えることは明らかである。このような場合は、単に部分木１４１１の検索命令、ノードＳを根とする部分木の検索命令、根Ｔのラベルの情報を検索命令リストに出力する。すなわち、検索命令リストは以下のようになる。
（５１）検索（部分木１４１１）
（５２）検索（部分木１４１２）
（５３）検索（部分木１４１３）
（５４）中間結果集計ＡＮＤ（部分木１４１２，１４１３の実行結果の集計）
（５５）中間結果集計ＯＲ（１の検索および４の集計の実行結果の集計）
【図面の簡単な説明】
【００４４】
【図１】この発明の実施の形態１における情報検索装置の構成を示す図である。
【図２】実施の形態１における情報検索装置による検索処理の動作フロー図である。
【図３】実施の形態１における検索処理部による検索処理の動作フロー図である。
【図４】この発明の実施の形態１及び２における情報検索装置が取扱う検索式の例を示す図である。
【図５】実施の形態２における情報検索装置が行う検索式構築及び分割処理の動作フロー図である。
【図６】実施の形態２における検索式構築及び分割処理の動作を説明する図である。
【図７】この発明の実施の形態３における情報検索装置が行う検索式構築及び分割処理の動作フロー図である。
【図８】実施の形態３における検索式構築及び分割処理の動作を説明する図である。
【図９】この発明の実施の形態４における情報検索装置が行う検索式構築及び分割処理の動作フロー図である。
【図１０】実施の形態４における検索式構築及び分割処理の動作を説明する図である。
【図１１】この発明の実施の形態５における情報検索装置が行う検索式構築及び分割処理の動作フロー図である。
【図１２】実施の形態５における情報検索装置の構成を示す図である。
【図１３】実施の形態２で比較対象とした検索式の分割を示す図である。
【図１４】実施の形態６における一般的な検索式分割処理の流れを示す図である。
【符号の説明】
【００４５】
１０２ 検索式入力部、１０３ 検索式評価部、１０４，１０４ｂ，１０４ｃ，１０４ｄ，１０４ｅ 検索式分割部、１０５ 検索処理部、１０６ 検索結果出力部、１０７ 検索制御部、１０８ 中間結果集計部、１０９ 検索実行部、１１０ 中間結果管理部、１１１ データベース（ＤＢ）、１２０５ 検索式出力部、Ｓ２０１ 所望の情報検索を記述した検索式読込みステップ、Ｓ２０２ 所定形式の最簡易形式への分解ステップ、Ｓ２０３ 分解（合成）後の簡易形式による検索時にリソースが上限値を超えるかを評価するステップ、Ｓ２０４ 簡易形式の合成ステップ、Ｓ２０５ 直前の簡易形式による検索式の再構成ステップ、Ｓ２０６ 部分検索式と中間集計処理からなる検索命令リスト出力ステップ、Ｓ５０１ 検索式を２分木展開ステップ、Ｓ５０２ 高さｉ＝１の部分木構築ステップ、Ｓ５０３ 部分木記述による検索時にリソースが上限値を超えるかを評価するステップ、Ｓ５０４ ｉ＋１の部分木構築ステップ、Ｓ５０５ 直前の部分木を分割した検索式を持つ部分木構築ステップ、Ｓ７０１ 検索式を２分木展開して同じラベルを持つ親子ノード結合ステップ、Ｓ７０２ 高さｉ＝１の部分木構築ステップ、Ｓ７０３ 部分木記述による検索時にリソースが上限値を超えるかを評価するステップ、Ｓ７０４ ｉ＋１の部分木構築ステップ、Ｓ７０５ 直前の部分木を分割した検索式を持つ部分木構築ステップ、Ｓ９０１ 検索式をＤＮＦに変形するステップ、Ｓ９０２ 高さｉ＝１の部分木構築ステップ、Ｓ９０３ 部分木記述による検索時にリソースが上限値を超えるかを評価するステップ、Ｓ９０４ ｉ＋１の部分木構築ステップ、Ｓ９０５ 直前の部分木を分割した検索式を持つ部分木構築ステップ。
【技術分野】
【０００１】
この発明は、マルチデータベース・システムにおけるデータ検索の容易化、特に複雑な検索条件により多量の資源を使用する検索の容易化に関するものである。
【背景技術】
【０００２】
従来、マルチデータベース・システムにおけるデータ検索に関して、検索コスト、つまり検索時間や検索時のメモリ等の資源を少なくしたり、検索意図に添った適切対象に絞り込む、といった検索装置、方法が多数提案されている。
例えば特許文献１の「データベース照会最適化システム」によれば、マルチデータベースシステムのデータ照会に要するコストを、最適化する方式が提案されている。上記特許文献１の方式では、最適化の第１段階として、ＳＱＬのようなデータ照会言語から、先ずリソース全体の消費量の最適化を考えて、例えば左に深く分岐した、つまり検索処理回数が多い、照会ツリーを一旦生成する。その後に第２段階として、応答時間の短縮を考えて、左に深い照会ツリーを平衡の取れたツリーに変換する。このとき上記文献では、第２段階の平衡の取れたツリーへの変換方式として、ボトムアップ・アプローチや、トップダウン・アプローチという方式が示されている。
【０００３】
ところで、昨今、流通するマルチメディアデータの増加に伴い、データベース（ＤＢ）に蓄積されるデータ規模の巨大化、検索対象の多様化が予測される。こうなると、必然的にこれらＤＢ中に登録されたデータの増加、検索処理の負荷が高い検索方式の適用、検索式の複雑化などの要因で、検索時のリソースの消費量が増加する。その場合、従来の検索式の最適化を行う検索装置では、検索式の複雑化により装置で利用可能なリソースの上限値を超えることも起こり得る。
【特許文献１】特開平８−３２８９２０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来のデータ検索装置、方法においては、ＳＱＬのような検索式を入力として、複数のデータベースで構成される複合データベースから所望の情報を得す場合に、上記特許文献１等のさまざまな検索式の最適化方法が考えられてきた。しかしそれらの検索式の最適化方法は、検索時間や、リソース使用量を最小化することである。従って、検索条件が複雑化してリソース使用量が利用可能な上限値を超えるような場合については言及されていず、従って複雑な検索式または多量のデータベースのために検索が実行不可能となる場合が生じるという課題がある。
【０００５】
この発明は上記の課題を解決するためになされたもので、複合データベースの検索において、通常の検索指定に基づけば、リソース消費量が装置で利用可能な上限値を超えて、従来方式では検索実行が不可能となる場合でも、検索の実行を可能とする装置、方法を得ることを目的とする。
また更に、そのままでは検索不可能な条件を検索可能とした上で、その可能な検索処理を高速化する装置、方法を得ることを目的とする。
【課題を解決するための手段】
【０００６】
この発明に係る情報検索装置は、データベースから所望の情報を検索する情報検索装置において、
上記所望の情報検索を記述する検索式を読込み、この読込んだ検索式を所定の簡易形式に分割する検索式分割部と、
上記検索式分割部が分割した簡易形式検索式による検索時の必要リソースがシステムで持つリソース上限値内であるかを評価する検索式評価部と、
上記検索式分割部が出力する検索命令リストに従って上記所望の情報検索を行う検索処理部と、を備えて、
上記検索式分割部は、上記検索式評価部がリソース上限値内であると評価する簡易形式に分割して、上記検索処理部は、この簡易形式に基づいて情報検索を行うようにした。
【発明の効果】
【０００７】
この発明によれば、検索式分割部と検索式評価部とを備えて、検索式分割部は検索式評価部がリソース上限値内であると評価する簡易形式に分割して、検索処理を行うので、検索不可能な条件でも検索可能にして検索処理ができる効果がある。
【発明を実施するための最良の形態】
【０００８】
実施の形態１．
従来方式では検索実行が不可能となる場合でも、検索の実行を可能とする装置、方法を図に基づいて説明する。
なお、本実施の形態における装置が検索の対象とするデータベースは、マルチメディアデータを蓄積した個別ＤＢを複数照合する複合ＤＢである。マルチメディアデータとは、文書データや、画像データ、音声データ、映像データ、その他バイナリデータなどの、電子化されたデータのことである。また複合ＤＢは、個別ＤＢと同じ装置上に構成されていてもよいし、ネットワークで接続された異なる個別ＤＢ装置を集合した形態であってもよい。
【０００９】
図１は本実施の形態における情報検索装置の構成を示す図である。図において、情報検索装置は、以下の要素で構成される。即ち、検索を依頼するユーザから検索式１０１の入力を受け付ける検索式入力部１０２、本発明の重要な要素である、入力された検索式による検索時のリソース消費量を評価する検索式評価部１０３、同じく重要な要素である、検索式を分割して部分検索式と検索命令リストを出力する検索式分割部１０４、入力された検索式や、検索式分割部１０４より出力された検索命令リストに従って、実際の検索処理を実行する検索処理部１０５、検索結果１１２を検索依頼したユーザに出力する検索結果出力部１０６、である。
検索処理部１０５は、更に以下の要素で構成される。即ち、検索式や検索命令リストに従って検索処理を制御する検索制御部１０７と、複合ＤＢに関連付けられている１種類以上の個別ＤＢ１１１に対して検索を実行する検索実行部１０９、検索実行部１０９で得られた検索結果を中間結果として管理する中間結果管理部１１０、中間結果間の集計（論理演算）処理を実行する中間結果集計部１０８、である。
なお、検索実行部１０９は、個別ＤＢに対する検索機能を内包していてもよいし、別の装置上にある個別ＤＢの検索機能を呼び出して検索結果を得るものであってもよい。
またこれらの検索式評価部等の各部は、その機能を実現するソフトウェアのプログラムで記述されており、図示はされていないが、プロセッサ（ＣＰＵ）とメモリがあって、これら各部の記述されたプログラムを実行して、検索式評価等の各機能を得ている。
【００１０】
ここで言うリソースは、情報検索装置に搭載されている、検索処理部１０５や検索実行部１０９が、バッファとして使用する際の容量が問題となるメモリであってもよいし、一時的に使用する他のメモリでもよい。また、一時ファイルを格納するディスク装置でもよい。または他にも、ＣＰＵ使用率の基となるＣＰＵや、ネットワーク使用率の基となるチャネルでもよい。同様に、異なる装置上にある個別ＤＢ検索装置のメモリやディスク装置、ＣＰＵ、チャネルでもよい。
その他に検索が出来なくなるファクターとして、情報検索装置で設定される検索式の長さが長過ぎる場合や、演算子の数が多過ぎるなど、情報検索装置の諸元も考えられる。また更に、個別ＤＢが全文検索を実行する場合の、検索キーワード数や、ユニークな文字数が多過ぎる場合もある。
【００１１】
検索時のリソース消費量の評価では、複合ＤＢに関連づけられている個別のＤＢに対する検索処理や、結果の集計処理について、実行時のリソース情報を検索式評価部１０３が保持し、その情報を元に全体の検索実行時のリソース消費量を評価する。
具体的には例えば、個別のＤＢが文書検索用のＤＢであった場合は、検索時にディスク装置からメモリ上に読み込まれる索引のサイズを、検索キーワードの文字数から計算しても良い。多くの文書検索では、文書中に出現するキーワードや文字の出現位置の情報を、索引としてＤＢに保持している。キーワードの文書中での出現頻度によって、該当する出現位置情報のサイズは変化するが、検索式中の検索キーワードの出現位置情報の合計サイズを調べることで、それがメモリの容量を超えるか否かを評価することができる。そのために、出現位置情報のサイズの情報を、出現位置情報とは別に記録しておいてもよいし、直接出現位置情報の記録されたファイルのサイズを調べても良い。また、キーワードや文字の出現頻度と、検索式中の検索キーワード数やキーワードの文字数をパラメータにして、索引サイズ等の必要となるメモリサイズを計算する計算式を予め定義しておいても良い。例えば単純に、（比例定数Ｋ×キーワードの出現頻度）を１検索キーワードの出現位置情報のサイズとして、その総和をとる等の計算式が考えられる。いずれの場合も、キーワードの出現頻度や、出現位置情報のサイズは、文書をＤＢに登録する時点で取得することができる。
【００１２】
所定のパーセンテージ、例えば最初の１０パーセントを検索してみて、検索に該当する出現頻度を抽出して、それを１０倍してオーバフローするかどうかを調べてもよい。または、過去に入力された検索式とその消費リソース量の記録を一定回数分保存しておき、検索時にはそれら検索式によるリソース消費量の統計的情報を利用しても良い。例えば統計情報の中には、検索式毎の検索ヒット件数や、検索実行中のメモリやＣＰＵのリソースの消費量の推移などを含んでも良い。中間結果集計処理の場合では、予想される検索のヒット件数から見積もるようにしてもよい。
また、検索時にリソースを大量に消費する個別のＤＢ１１１と、そうでない個別のＤＢが共存している場合は、ＤＢ毎の重みを設定してもよい。
また、リソースが検索実行部の諸元であった場合、例えば受理できる検索式の長さの上限が設定されている場合は、文字数やバイト数をカウントするだけでよい。すなわち個別のＤＢの検索実行部１０９が１回に受理できる検索式の長さの上限がＮバイトと定められている場合、ｓｔｒｌｅｎ（）のような文字列の長さを取得する関数で、検索式１０１の長さを取得することで、上限Ｎバイトを超えているか否かを容易に判定することができる。
このように、評価するための上限情報と方式を検索式評価部１０３が保持しており、その情報を元にリソース消費量を評価する。
【００１３】
図２は、本実施の形態における情報検索装置の、検索式分割部１０４と検索式評価部１０３による、検索処理の流れを示した動作フロー図である。
この図により本実施の形態における情報検索装置の動作を説明する。情報検索装置は、ステップＳ２０１（以後ステップの記述を省略する）で検索式入力部１０２により入力された所望の情報検索を記述した所定検索式を読み込むと、Ｓ２０２でこれをその所定形式での最簡易形式に分解して、Ｓ２０３で検索式評価部１０３により、この簡易形式による検索式で検索した時に情報検索装置が使用するリソースの消費量を評価する。この検索式の評価により、検索時のリソース消費量が、情報検索装置で利用可能なリソースの上限値（以降、リソース上限値と呼ぶ）の範囲であった場合（Ｎｏ）は、Ｓ２０４に進む。そして検索式分割部１０４は簡易形式を合成して、上位の簡易形式とする。そしてＳ２０３の評価をして、以後この評価がリソース上限値を超えるまでＳ２０４のループを繰返す。
ところがＳ２０２の検索式による評価で、検索時のリソース消費量が情報検索装置で利用可能なリソースの上限値を超えていた場合（Ｙｅｓ）は、Ｓ２０５で検索式分割部１０４により、先のＳ２０３でリソース上限値を超える直前の検索式について、検索時のリソース消費量がリソース上限値の範囲内に収まるよう、複数の部分検索式に分割する等、検索式を再構成する。Ｓ２０３’においてこの部分検索式でよいことを確認すると、Ｓ２０６でこの部分検索式を検索命令リストとして出力する。そして検索処理部１０５により、この検索命令リストに従った検索処理が実行される。最後にこの検索処理によって得られた検索結果を、検索結果出力部１０６からユーザに対して出力して終了する。
【００１４】
検索命令リストとは、ユーザから入力された検索式と等価になるよう、部分検索式による検索の実行や、中間結果の集計処理の実行順を指定するリストである。例を図４に検索式と検索命令リストの一例を示す。いま、検索式４０１が入力され、検索式の評価の結果、検索時のリソース消費量がリソース上限値を超えていたとする。この検索式４０１を検索式分割部１０４で分割した結果として、検索命令リスト４０２が出力される。図４の例では、検索命令リスト４０２は、最初に検索実行部で部分検索式（Ａ ＡＮＤ Ｂ）を実行し、次に検索実行部で部分検索式（Ｃ ＡＮＤ Ｄ）を実行し、最後に直前の２回の検索で得られた中間結果の集計処理ＯＲを実施することを指定している。検索命令リスト４０２のように処理することで、検索式４０１と同じ検索結果を得ることができる。
単純に行うにはこのように、分割は論理演算の各論理毎に分割すればよい。
また検索結果や中間結果とは、検索式で与えられた検索条件に適合したレコード情報の集合である。レコード情報には、ＤＢ中のレコードの識別子や、検索条件に適合したレコードを評価したスコア、ＤＢのカラムに格納されているデータなどを含んでよい。
【００１５】
図３は、本実施の形態における情報検索装置の検索処理部１０５による検索処理の流れを示した動作フロー図である。検索処理部１０５は、ユーザから入力された検索式や、部分検索式と検索命令リストに従って、検索を処理する。
例えば部分検索式を含む検索命令リストが入力されると、検索制御部１０７はＳ３０１で、検索命令リストから検索の実行命令を１つ、例えば検索（Ａ ＡＮＤ Ｂ）を取得する。続いてＳ３０２で、取得した命令が部分検索式を実行する内容であれば（検索）に移り、検索実行部１０９に対して部分検索式による検索の実行命令を発行する。検索実行部１０９はＳ３０３で、後の実施の形態で述べるように、必要に応じて部分検索式から検索を実行するための検索プランを生成する。Ｓ３０４では、複合ＤＢに関連づけられている個別のＤＢ１１１に対して検索を実行し、検索結果を取得する。取得した検索結果はＳ３０５で、検索の中間結果として中間結果管理部１１０に格納する。
Ｓ３０２で、取得した命令が中間結果の集計の実行であった場合は（集計）に移り、Ｓ３０６で中間結果管理部１１０から複数の中間結果を取得する。Ｓ３０７で中間結果の集計処理を行い、Ｓ３０８で次の部分検索式に移り、Ｓ３０４またはＳ３０６の処理を繰り返す。こうして得られた中間結果を、Ｓ３０９で、最終検索式に基づいて中間結果を集計する。中間結果の集計は、Ｓ３０６で逐次実行してもよい。そして、検索結果出力部１０６に対して出力する。
【００１６】
検索処理部１０５への入力が、ユーザから入力された検索式であった場合は、Ｓ３０１や、Ｓ３０２をスキップして、直接検索実行部１０９でＳ３０４以降、またはＳ３０６を実行してもよい。また、中間結果管理部１１０を介さずに、直接ステップＳ３０９で検索結果出力部１０６に検索結果を出力してもよい。
また検索実行部１０９では、Ｓ３０３の検索プラン生成処理ステップで、部分検索式による検索時間や、検索時のメモリ使用量が最小になるよう、部分検索式の最適化を行ってもよい。
検索実行や、中間結果集計の処理では、それ以前の処理の結果によっては、実行する必要がないものもある。そのような場合、実行する必要がない検索命令をスキップしてもよい。例えば、次の検索式が与えられ、それ以降の（０１），（０２），（０４）の３つの部分木に分割されたとする。
「（（Ａ ＡＮＤ Ｂ） ＯＲ （Ｃ ＡＮＤ Ｄ）） ＡＮＤ （Ｅ ＯＲ Ｆ）」
（０１）検索（Ａ ＡＮＤ Ｂ）
（０２）検索（Ｃ ＡＮＤ Ｄ）
（０３）集計ＯＲ（検索１、２の中間結果を集計）
（０４）検索（Ｅ ＯＲ Ｆ）
（０５）集計ＡＮＤ（検索４、集計３の中間結果を集計）
このとき、例えば、集計（０３）の実行結果が偽であった（中間結果が何も無い）場合、検索（０４）を実行しなくてよい。
【００１７】
図１の検索式入力部１０２ないし中間結果管理部１１０の各処理部は、１つのプロセッサで実行されるプログラムであってもよいし、それぞれ専用のプロセッサで実行されるように構成してもよい。
またユーザが入力する検索式は、ユーザが直接キーボードなどの入力装置で入力してもよいし、検索式を記述したファイルを入力し、これを検索式入力部１０２が読取るようにしてもよい。
入力された検索式１０１や、検索式入力部１０２から検索処理部１０５に伝達する検索式、部分検索式、検索命令リストは、メモリ上の情報としてプロセッサが図示しないバスを通じて伝達してよいし、一時ファイルを介して一括伝達してもよい。また、グラフィカルユーザインターフェースを通してユーザが入力した検索条件を、情報検索装置の入力の形式に変換する処理を含んでもよい。
中間結果管理部１１０では、メモリ上で中間結果を管理してもよいし、中間結果をディスク装置など外部記憶装置上に一時ファイルとして記憶し、後で利用してもよい。検索実行部１０９や検索処理部１０５が出力する検索結果も、メモリ上の情報として伝達してもよいし、ファイルを介して伝達してもよい。
検索結果出力部１０６は、結果を画面などの出力装置に出力してもよいし、ファイルに出力してもよい。また、検索結果を編集・加工・利用する別の装置にメモリ上の情報として出力してもよい。
【００１８】
本実施の形態における情報検索装置は、上記のように、ユーザが入力した検索式の検索時のリソース消費量を評価し、リソース上限値を超えていた場合は検索式を分割して検索を実行するように構成されている。このため従来の方式で、ユーザから入力された検索式により検索時のリソース消費量がリソース上限値を超えるため検索の実行が不可能であった場合でも、検索の実行が可能である。
【００１９】
実施の形態２．
先の実施の形態における情報検索装置では、検索式を分割して、検索の処理を分割する装置を説明した。こうすると、検索式の分割数が多いと、検索の初期化処理や中間結果管理部へのデータの入出力処理等により、検索時間が増大することが予想される。言い換えれば、検索式の分割数が少ないほど、全体の検索処理の効率は良くなる。ここでは情報検索装置が、検索式分割部により検索処理を向上する分割を行う方式を説明する。
一般に論理式は、木構造の論理に展開可能である。そこで本実施の形態における検索式の分割方式は、検索式を木構造の論理式とみなして、２分木と呼ばれる木構造に展開する。２分木とは、リーフを除く全てのノードにおける子の数が２以下である木構造である。検索式を２分木に展開したとき、その木のリーフは、１つの検索実行部の検索処理に対応し、内部ノードは中間結果集計部の集計処理に対応する。この２分木の高さをＤとする。
【００２０】
図５は、本実施の形態における情報検索装置の検索式分割部による検索式分割処理を示す動作フロー図である。
図において、検索式分割部１０４ｂは、検索式が入力されると、ステップＳ５０１で検索式を２分木に展開する。Ｓ５０２では高さｉが１の部分木を構築する。次にＳ５０３で、前のステップで構築した部分木に対して、検索式評価部１０３により検索時のリソース消費量を評価する。Ｓ５０３で部分木による検索時リソース消費量がリソース上限を超えていない場合（Ｎｏ）は、次のＳ５０４で高さｉ＋１の部分木を構築する。そしてＳ５０３で上限値になるまで木を高くして行く。
そしてＳ５０３で部分木による検索時リソース消費量がリソース上限を超える場合（Ｙｅｓ）はＳ５０５で、Ｓ５０３で調べてＹｅｓになる直前の最も高さが高い部分木による部分検索式を分割して新しい部分検索式を持つ部分木によってもリソースの上限値を超えないかをＳ５０３’で確認して、Ｓ５０６で部分検索式と、中間結果集計処理（ルート）を検索命令リストとして出力する。即ちＳ５０３とＳ５０４の処理を、高さｉ＝１（すなわちリーフのみの部分木）から、最大Ｄまで繰り返す。そしてＳ５０１で展開した２分木の分割が完了したら、Ｓ５０６で検索命令リストを出力して終了する。
【００２１】
このようにＳ５０１で検索式を２分木に展開したが、検索式を２分木に展開する方法は複数ある。例えば図１３の検索式１１０１は、木１１０２のようにも、木１１０３のようにも展開可能である。しかし木１１０２のように、左（または右）に深い木の場合は、検索式の分割数が多くなる可能性がある。例えば、部分木１１０４がひとつの部分検索式として分割された場合、リーフＣ、リーフＤは、単独で部分検索式となり、分割効率がよくない。一方で、木１１０３のように平衡の取れた木（高さが最小の木）の場合、木１１０２のような問題がない。従って検索式を２分木に展開する場合は、木１１０３のような、平衡の取れた木に展開する。
【００２２】
本実施の形態における検索式分割処理の動作を図６により説明する。その場合の例として図４の検索式４０１を用いる。
１）検索式６０１が入力されると、Ｓ５０１で検索式６０１は２分木６０２に展開される。ここで、ＡないしＤはリーフで、複合ＤＢに関連づけられた個別のＤＢに対する検索条件でもある。内部ノードＥないしＧは、中間結果の集計処理である。この例では中間結果の集計は、ＡＮＤまたはＯＲの論理演算としている。ところで例としてリソース上限値を１００、ＡないしＤ単体の検索時のリソース消費量を３０とする。説明を判りやすくするため、中間結果の集計処理はリソースを消費しないものとする。また部分木による検索時のリソース消費量は、リーフ単体での検索時のリソース消費量の和とする。なお、木６０２の高さは３である。
２）Ｓ５０２で、高さ１の部分木、即ち木Ａ、木Ｂ、木Ｃ、木Ｄを構築する。
【００２３】
３）Ｓ５０３で、Ｓ５０２で構築した部分木の、検索時のリソース消費量を評価する。評価の結果、いずれも３０であり、リソース上限（１００）の範囲内である。
４）Ｓ５０４で、高さ２の部分木を構築する。即ち木ＡＢＥ，木ＣＤＥを構築する。
５）Ｓ５０３で、Ｓ５０２で構築した部分木の、検索時のリソース消費量を評価する。評価の結果はいずれも６０であり、リソース上限の範囲内である。
６）Ｓ５０４で、高さ３の部分木を構築する。即ち木ＡＢＣＤＥＦＧを構築する。
７）Ｓ５０３で、Ｓ５０２で構築した部分木の、検索時のリソース消費量を評価する。評価の結果は１２０であり、リソース上限（１００）を超えている。
８）Ｓ５０５で、木ＡＢＣＤＥＦＧ中の、２つの高さ２の部分木に対応した検索式を構築する。これは明らかに評価が６０であり、リソース範囲内である。Ｓ５０６でこの高さ２の部分木に対応した検索式の情報と、リーフＧの情報を、検索命令リストとして出力する。すなわち、部分検索式（Ａ ＡＮＤ Ｂ）、部分検索式（Ｃ ＡＮＤ Ｄ）、中間結果集計処理ＯＲを、検索命令リスト（図４の検索命令リスト４０２）とする。
【００２４】
本実施の形態における情報検索装置は、上記のように検索式を２分木に展開後、リーフからボトムアップに部分木を長く構築して、リソース消費量がリソース上限値を超えたところで、その直前の最長部分木で分割するように構成しているので、検索式の分割処理において、部分検索式による検索時のリソース消費量がリソース上限の範囲内で最大にできる。その結果、検索式の分割数を少なくできる。
【００２５】
実施の形態３．
先の実施の形態と同様目的で、他の動作を行う情報検索装置を説明する。
本実施の形態における情報検索装置の動作を図７のフロー図により説明する。図において、情報検索装置の検索式分割部１０４ｃは、検索式が入力されるとステップＳ７０１で、検索式を２分木に展開し、さらに２分木の内部ノードを走査して、同じラベルを持つ親子関係にあるノードを結合する。Ｓ７０１の処理により、２分木では内部ノードの子の数が必ず２以下であったものが、内部ノードが２以上の子を持つことになる。この木の高さをＤとする。Ｓ７０２以降では、実施の形態２に示した処理の流れと同様に、ボトムアップに部分木を構築する。Ｓ７０２で、高さ１の部分木を構築する。次にＳ７０３で、Ｓ７０２で構築した部分木に対して検索式評価部１０３により検索時のリソース消費量を評価する。Ｓ７０３で部分木による検索時リソース消費量がリソース上限を超えていない場合（Ｎｏ）は、Ｓ７０４で高さｉ＋１の部分木を構築する。このＳ７０３とＳ７０４を最大Ｄの高さまで繰返す。
そしてＳ７０３で部分木による検索時リソース消費量がリソース上限を超える場合（Ｙｅｓ）は、Ｓ７０５でその直前の部分木による分割を再検討して、各々の部分木による分割が検索時のリソース消費量がリソース上限の範囲で最大となり、つまり分割数が最小となる部分木を構築する。これをＳ７０６で、集計処理論理と、分割された高さｉの部分木に対応する部分検索式の情報として検索命令リストを出力し、分割を終了する。
【００２６】
先の実施の形態２における図５のＳ５０４の処理では、高さｉの木は、一意に２つの高さｉ−１の部分木に分割できた。しかし本実施の形態における図７のＳ７０５の処理で、高さｉの木を高さｉ−１の木に分割する方法は、何通りも存在する。Ｓ７０４における部分木の分割処理のような、部分木の検索時のリソース消費量をリソース上限の範囲内で最大とする、ノードの組合せ最適化問題は、近似解を多項式時間で得るアルゴリズムが考案されており、高速に処理することが可能である。
【００２７】
図８は、本実施の形態における、検索式分割処理の例を示す図である。
いま、検索式８０１が入力されたとする。このとき、先の実施の形態２に示した、検索式を２分木８０２に展開してから分割する方式では、２分木８０２は、部分木ＡＢＧ、部分木ＣＤＨ、部分木ＥＦＩの３つの部分木に分割される。検索命令リストは以下の５つの処理からなる。
（１）検索（Ａ ＯＲ Ｂ）（Ｇをルートとする部分木の処理）
（２）検索（Ｃ ＯＲ Ｄ）（Ｈをルートとする部分木の処理）
（３）中間結果集計ＯＲ （内部ノードＪの処理）
（４）検索（Ｅ ＯＲ Ｆ）（Ｉをルートとする部分木の処理）
（５）中間結果集計ＯＲ（内部ノードＫの処理）
【００２８】
本実施の形態における検索式分割処理の流れは以下の通りである。
１１）検索式８０１が入力されると、Ｓ７０１で検索式８０１を２分木８０２に展開する。ここで、ＡないしＥはリーフで、複合ＤＢに関連づけられた個別のＤＢに対する検索条件である。内部ノードＧないしＫは、中間結果の集計処理である。実施の形態２と同様に、この例では中間結果の集計は、ＡＮＤまたはＯＲの論理演算としている。リソース上限値を１００とし、ＡないしＥの検索処理のリソース消費量は、図８に示す通りであるとする。更に、木８０２で同じラベルを持ち、親子関係にある内部ノードＧないしＫを結合して、木８０３が得られる。
１２）Ｓ７０２で、高さ１の部分木を構築する。すなわち木Ａ〜木Ｆである。
１３）Ｓ７０３で、Ｓ７０２で構築した部分木の、検索時のリソース消費量を評価する。評価の結果、リソース消費量は３０または４０で、いずれもリソース上限（１００）の範囲内である。
【００２９】
１４）Ｓ７０４で、高さ２の部分木を構築する。すなわち木ＡＢＣＤＥＦＫである。
１５）Ｓ７０３で、Ｓ７０４で構築した部分木の、検索時のリソース消費量を評価する。評価の結果は２００であり、リソース上限を超えている。
１６）Ｓ７０５で、この場合に木ＡＢＣＤＥＦＧは高さ２であり、高さ１にすることは意味がないので、木ＡＢＣＤＥＦＧを２つ以上の各種の部分木に分割する。ここで例えば、木８０３のリーフを左から順に選んで部分木に分割した場合、リーフＡＢを含む部分木、リーフＣＤＥを含む部分木、リーフＫを含む３つの部分木８０３に分割できる。または木８０４のようにリーフの組合せを変えると、最終的に木８０５のように、部分木ＡＣＤＧと部分木ＢＥＦＨの２の部分木と、ルートに分割できる。
１７）木８０３の分割が完了したので、Ｓ７０６で検索命令リストを出力して終了する。
このときの、検索命令リストは以下の３つの処理からなる。
（１１）検索（Ａ ＯＲ Ｃ ＯＲ Ｄ）（Ｇをルートとする部分木の処理）
（１２）検索（Ｂ ＯＲ Ｅ ＯＲ Ｆ）（Ｈをルートとする部分木の処理）
（１３）中間結果集計ＯＲ（内部ノードＫの処理）
【００３０】
本実施の形態における情報検索装置は、上記のように、検索式を２分木に展開後、更に同じラベルを持つ親子関係にあるノードを結合し、リーフからボトムアップに部分木を構築し、リソース消費量がリソース上限値を超えたところで、部分木を分割するように構成しているので、検索式の分割処理において、先の実施の形態における方式と比べ、更に分割数を少なくできる。
【００３１】
実施の形態４．
特別な形式の検索式について説明する。本実施の形態においては、情報検索装置の検索式分割部１０４ｄは、検索式をＤＮＦ（Ｄｉｓｊｕｎｃｔｉｖｅ Ｎｏｒｍａｌ Ｆｏｒｍ）形式の木構造に変形する。ＤＮＦは、積和標準形とも呼ばれる論理式の形式の一つで、論理変数を論理演算子ＡＮＤで結合した項を、論理演算子ＯＲで結合した形の論理式であり、高さ３の木として表現できる。なお任意の論理式をＤＮＦ形式に変形可能である。
【００３２】
図９は、本実施の形態における情報検索装置の、検索式分割部１０４ｄによる検索式分割処理の動作を示すフロー図である。検索式分割部１０４ｄは、検索式が入力されるとＳ９０１で、検索式をＤＮＦ形式の木に変形する。Ｓ９０２以降は、実施の形態３に示した処理の流れと同様に、ボトムアップに部分木を構築する。即ちＳ９０２で、高さｉの部分木を構築する。次にＳ９０３で、Ｓ９０２で構築した部分木に対して検索式評価部１０３により検索時のリソース消費量を評価する。Ｓ９０３で部分木による検索時リソース消費量がリソース上限を超えていない場合（Ｎｏ）は、Ｓ９０４で高さｉ＋１の部分木を構築する。こうしてＳ９０３とＳ９０４で高さを順次高くした木を構築して行く。
Ｓ９０３で部分木による検索時リソース消費量がリソース上限を超える場合（Ｙｅｓ）は、Ｓ９０５で高さｉの部分木を、各々の部分木を検索時にリソース消費量がリソース上限の範囲で最大となるよう、すなわち分割数が最小となるよう、２つ以上の高さｉの部分木に分割する。こうしてＳ５０３ないしＳ５０５を高さｉ＝１からこの場合は最大３まで繰返して、ルート（中間結果集計処理）の情報と、分割された高さｉの部分木に対応する、部分検索式の情報を、Ｓ９０６で検索命令リストとして作成し、出力する。
このように、図７，図９に示す検索式の論理木の変換を行うことで、最適解が見つけやすくなる。
【００３３】
図１０を用いて本実施の形態における検索式分割処理の動作を説明する。
いま、検索式１００１が入力されたとする。このとき、先の実施の形態に示した方式では、検索式を２分木に展開後、更に同じラベルを持つ親子関係にあるノードを結合した木１００２に変形する。ここで、ＡないしＥはリーフである。内部ノードＪないしＮは、中間結果の集計処理である。実施の形態２と同様に、この例では中間結果の集計はＡＮＤまたはＯＲの論理演算としている。リソース上限値を１００、ＡないしＨの検索処理のリソース消費量は、図８の通りであるとする。またこの例での、中間結果集計処理のリソース消費量を以下のように定める。
ＡＮＤ処理・・・子のリソース消費量の最も大きいものと等しい
ＯＲ処理・・・子のリソース消費量の総和と等しい
先の実施の形態における方式では、木１００２は、部分木ＡＢＣＤＬ、部分木ＥＦＪ、部分木ＧＩＫ、部分木Ｈの４つの部分木に分割される。このときの検索命令リストは以下の７つの処理からなる。
（２１）検索（Ａ ＡＮＤ Ｂ ＡＮＤ Ｃ ＡＮＤ Ｄ）
（２２）検索（Ｅ ＯＲ Ｆ）
（２３）検索（Ｇ ＯＲ Ｉ）
（２４）検索（Ｈ）
（２５）中間結果集計ＯＲ（内部ノードＫの処理）
（２６）中間結果集計ＡＮＤ（内部ノードＭの処理）
（２７）中間結果集計ＯＲ（内部ノードＮの処理）
【００３４】
本実施の形態における検索式分割処理の動作は以下の通りとなる。
２１）検索式１００１が入力されると、Ｓ９０１で検索式１００１をＤＮＦ形式の木１００３に変形する。
２２）Ｓ９０２で、高さ１の部分木を構築する。すなわち木Ａないし木Ｈである。
２３）Ｓ９０３で、Ｓ９０２で構築した部分木の、検索時のリソース消費量を評価する。評価の結果、いずれもリソース上限（１００）の範囲内である。
２４）Ｓ９０４で、高さ２の部分木を構築する。すなわち木ＡＢＣＤＬ、木ＥＩＬ、木ＥＧＬ、木ＥＨＬ、木ＦＧＬ、木ＦＨＬ、木ＦＩＬである。
２５）Ｓ９０３で、Ｓ９０４で構築した部分木の、検索時のリソース消費量を評価する。評価の結果は、木ＡＢＣＤＬ、木ＥＩＬ、木ＦＩＬが５０、木ＥＧＬ、木ＦＧＬが４０、木ＥＨＬ、木ＦＨＬが２０であり、いずれもリソース上限の範囲内である。
２６）再びＳ９０４で、高さ３の木を構築する。すなわち、木ＡないしＮである。
２７）再びＳ９０３で、Ｓ９０４で構築した高さ３の木の、検索時のリソース消費量を評価する。評価の結果、リソース消費量は２７０であり、リソース上限値を超えている。
２８）Ｓ９０５で、木ＡないしＮを２つ以上の部分木に分割する。木１００４に示したように、部分木１００５、部分木１００６、部分木１００７の、３つの部分木に分割できる。
２９）Ｓ９０３’で、これらの個別の部分木を評価すると、部分木１００５と部分木１００６でも１００となり、リソース上限内である。従って木１００３の分割が完了したので、Ｓ９０６で検索命令リストを出力して終了する。
【００３５】
このときの、検索命令リストは以下の４つの処理からなる。
（３１）検索（（Ａ ＡＮＤ Ｂ ＡＮＤ Ｃ ＡＮＤ Ｄ）ＯＲ（Ｅ ＡＮＤ Ｉ））
（３２）検索（（Ｅ ＡＮＤ Ｇ）ＯＲ（Ｅ ＡＮＤ Ｈ）ＯＲ（Ｆ ＡＮＤ Ｇ））
（３３）検索（（Ｆ ＡＮＤ Ｈ）ＯＲ（Ｆ ＡＮＤ Ｉ））
（３４）中間結果集計ＯＲ（ルートノードの処理）
こうして実施の形態３と同様に、Ｓ９０５における部分木の分割処理のような、部分木の検索時のリソース消費量をリソース上限の範囲内で最大とするノードの組合せ最適化問題は、近似解を多項式時間で得るアルゴリズムが考案されており、高速に処理することが可能である。
【００３６】
本実施の形態における情報検索装置は、上記したように検索式をＤＮＦ形式の木に変形後、リーフからボトムアップに部分木を構築し、リソース消費量がリソース上限値を超えたところで、部分木を分割するように構成しているので、検索式の分割処理において、部分検索式による検索時のリソース消費量がリソース上限の範囲内で最大とすることができる。その結果、検索式の分割数を少なくすることができる。
【００３７】
本実施の形態の変形として、他の検索式分割部１０４ｅによる検索式の分割方式を説明する。即ち検索式をＣＮＦ（Ｃｏｎｊｕｎｃｔｉｖｅ Ｎｏｒｍａｌ Ｆｏｒｍ）形式の木構造に変形する。ＣＮＦは、和積標準形とも呼ばれる論理式の形式の一つで、論理変数を論理演算子ＯＲで結合した節を、論理演算子ＡＮＤで結合した形の論理式であり、この場合は高さ３の木として表現できる。また任意の論理式は、ＣＮＦに変形可能である。
【００３８】
この検索式分割部１０４ｅによる検索式分割処理の動作は、図９のＳ９０１の処理を「検索式をＣＮＦに変形する」ものと同等である。
この検索式分割部１０４ｅによる情報検索は、検索式をＣＮＦ形式の木に変形後、リーフからボトムアップに部分木を構築し、リソース消費量がリソース上限値を超えたところで、部分木を分割するように構成する。
従って検索式の分割処理において、部分検索式による検索時のリソース消費量を上限値内で最大にでき、検索式の分割数を少なくできる。
【００３９】
実施の形態５．
先の各実施の形態では、情報検索装置は内部的に部分木を構築し、リソース上限値内で最大リソース消費となる検索式を生成して、検索を実行した。本実施の形態では、情報検索装置が分割した検索式を画面やログファイルに出力する構成とした。
図１２は、本実施の形態における情報検索装置の構成例を示す図である。この構成は、先の各実施の形態における情報検索装置に、検索式分割部から出力された部分検索式を画面などの出力装置やログファイル１２０８などに出力する検索式出力部１２０５を追加した構成になっている。その他の検索式入力部１２０２、検索式評価部１２０３、検索式分割部１２０４、検索処理部１２０６、検索結果出力部１２０７は、先の実施の形態のそれらと同じ要素である。
なお、検索式出力部１２０５が画面などの出力装置やログファイル１２０８に出力する情報は、検索式分割部１２０４から出力された部分検索式や検索命令リスト、検索式を分割したか否かのフラグ情報、検索式の分割方法が複数ある場合はその分割方法などの情報でもよい。また、検索式入力部１２０２に入力された検索式をそのまま出力してもよい。
【００４０】
図１１は、本実施の形態における情報検索装置による、検索処理の動作を示した図である。
図に基づいて動作を説明する。Ｓ１３０１において検索式入力部１２０２で検索式の入力を受け付けると、Ｓ１３０２において検索式評価部１２０３で入力された検索式による検索時のリソースの消費量を評価する。検索式の評価により、検索時のリソース消費量がリソース上限値内であった場合（Ｎｏ）は、図示では詳細を示していないが、先の各実施の形態で説明したように、部分木の高さを順次高くして部分検索式を作成して、リソース上限内の最高高さの部分木でＳ１３０４に進む。即ちＳ１３０２の検索式の評価で、検索時のリソース消費量が利用可能な上限値を超える場合（Ｙｅｓ）に、Ｓ１３０３で検索式分割部１２０４によりリソース消費量が上限値内となるように複数の部分検索式に分割する。
そしてＳ１３０４では、検索式を分割した部分検索式や検索命令リストを、画面やログファイル等１２０８に出力する。Ｓ１２０５では、入力された検索式や、Ｓ１３０３で分割された部分検索式と検索命令リストに従って、検索処理部１２０６により検索処理が実行される。最後にＳ１３０６で、Ｓ１３０５の検索処理によって得られた検索結果を検索結果出力部１２０７からユーザに対して出力して終了する。
なおＳ１３０４の部分検索式の出力処理は、Ｓ１３０３後に実行される動作とすれば、どの段階で実行するようにしてもかまわない。
【００４１】
このように本実施の形態の情報検索装置は、検索式分割部で分割された検索式に関する情報を画面表示等で出力するので、ユーザが必要に応じて、検索式の分割状況を参照することができる。
【００４２】
なお、上記各実施の形態では、検索式分割部、検索式評価部等の各要素は、専用の機能を持つとして説明した。しかし汎用の計算機を用いて各実施の形態で説明した図２、３、５、７、９等の各図で示される機能を持たせたプログラムにより、同等の動作をさせる方法としてもよい。
このようにしても情報検索方法として同じ優れた効果が得られる。
【００４３】
実施の形態６．
以下、図１４を元に一般的な検索式分割処理の流れを示す。検索式を論理木に展開後の処理の流れは、図７のＳ７０２と同等である。
３１）検索式１４０１が入力されると、検索式１４０１を論理木１４０２に展開する。この例では中間結果の集計は、ＡＮＤまたはＯＲの論理演算としている。リソース上限値を１００とし、ＡないしＮの検索処理のリソース消費量は、図１４に示す通りであるとする。また、部分木のリソース消費量は、単純のため、その部分木の根のリソース消費量の総和とする。
３２）高さ１の部分木を構築する。すなわち、部分木Ａ〜Ｎである。この部分木の検索時のリソース消費量を評価すると、全て１００未満であり、リソース上限の範囲内である。
３３）高さ２の部分木を構築する。すなわち部分木１４０６，１４０７，１４０８である。これらの部分木の検索時のリソース消費量を評価すると、全て１００未満であるので、リソース上限の範囲内である。
３４）高さ３の部分木を構築する。すなわち部分木１４０９，１４１０である。
これらの部分木の検索時リソース消費量を評価すると、部分木１４０９のリソース消費量は３０であり、リソース上限の範囲内である。一方、部分木１４１０のリソース消費量は１７０であり、リソース上限を超えて得いる。
３５）部分木１４１０の検索時のリソース消費量が、リソース上限を超えているため、部分木を分割する。最適な分割の例として部分木１４１２と１４１３のように分割される。分割後は、分割された部分木の検索式と、高さ３の部分木の根のラベルの情報が、検索命令リストに出力される。このとき検索命令リストは以下のようになる。
（４１）検索（部分木１４１２）
（４２）検索（部分木１４１３）
（４３）中間結果集計ＡＮＤ（部分木１４１２，１４１３の実行結果の集計）
３６）高さ４の部分木を構築する。すなわち部分木１４１１である。部分木１４１１の検索時のリソース消費量を評価すると６０であり、リソース上限の範囲内である。
３７）高さ５の部分木を構築する。すなわちノードＴを根とする木１４０５であるが、既にノードＳを根とする部分木は分割済みであり、木１４０５の検索時のリソース消費量が、リソース上限を超えることは明らかである。このような場合は、単に部分木１４１１の検索命令、ノードＳを根とする部分木の検索命令、根Ｔのラベルの情報を検索命令リストに出力する。すなわち、検索命令リストは以下のようになる。
（５１）検索（部分木１４１１）
（５２）検索（部分木１４１２）
（５３）検索（部分木１４１３）
（５４）中間結果集計ＡＮＤ（部分木１４１２，１４１３の実行結果の集計）
（５５）中間結果集計ＯＲ（１の検索および４の集計の実行結果の集計）
【図面の簡単な説明】
【００４４】
【図１】この発明の実施の形態１における情報検索装置の構成を示す図である。
【図２】実施の形態１における情報検索装置による検索処理の動作フロー図である。
【図３】実施の形態１における検索処理部による検索処理の動作フロー図である。
【図４】この発明の実施の形態１及び２における情報検索装置が取扱う検索式の例を示す図である。
【図５】実施の形態２における情報検索装置が行う検索式構築及び分割処理の動作フロー図である。
【図６】実施の形態２における検索式構築及び分割処理の動作を説明する図である。
【図７】この発明の実施の形態３における情報検索装置が行う検索式構築及び分割処理の動作フロー図である。
【図８】実施の形態３における検索式構築及び分割処理の動作を説明する図である。
【図９】この発明の実施の形態４における情報検索装置が行う検索式構築及び分割処理の動作フロー図である。
【図１０】実施の形態４における検索式構築及び分割処理の動作を説明する図である。
【図１１】この発明の実施の形態５における情報検索装置が行う検索式構築及び分割処理の動作フロー図である。
【図１２】実施の形態５における情報検索装置の構成を示す図である。
【図１３】実施の形態２で比較対象とした検索式の分割を示す図である。
【図１４】実施の形態６における一般的な検索式分割処理の流れを示す図である。
【符号の説明】
【００４５】
１０２ 検索式入力部、１０３ 検索式評価部、１０４，１０４ｂ，１０４ｃ，１０４ｄ，１０４ｅ 検索式分割部、１０５ 検索処理部、１０６ 検索結果出力部、１０７ 検索制御部、１０８ 中間結果集計部、１０９ 検索実行部、１１０ 中間結果管理部、１１１ データベース（ＤＢ）、１２０５ 検索式出力部、Ｓ２０１ 所望の情報検索を記述した検索式読込みステップ、Ｓ２０２ 所定形式の最簡易形式への分解ステップ、Ｓ２０３ 分解（合成）後の簡易形式による検索時にリソースが上限値を超えるかを評価するステップ、Ｓ２０４ 簡易形式の合成ステップ、Ｓ２０５ 直前の簡易形式による検索式の再構成ステップ、Ｓ２０６ 部分検索式と中間集計処理からなる検索命令リスト出力ステップ、Ｓ５０１ 検索式を２分木展開ステップ、Ｓ５０２ 高さｉ＝１の部分木構築ステップ、Ｓ５０３ 部分木記述による検索時にリソースが上限値を超えるかを評価するステップ、Ｓ５０４ ｉ＋１の部分木構築ステップ、Ｓ５０５ 直前の部分木を分割した検索式を持つ部分木構築ステップ、Ｓ７０１ 検索式を２分木展開して同じラベルを持つ親子ノード結合ステップ、Ｓ７０２ 高さｉ＝１の部分木構築ステップ、Ｓ７０３ 部分木記述による検索時にリソースが上限値を超えるかを評価するステップ、Ｓ７０４ ｉ＋１の部分木構築ステップ、Ｓ７０５ 直前の部分木を分割した検索式を持つ部分木構築ステップ、Ｓ９０１ 検索式をＤＮＦに変形するステップ、Ｓ９０２ 高さｉ＝１の部分木構築ステップ、Ｓ９０３ 部分木記述による検索時にリソースが上限値を超えるかを評価するステップ、Ｓ９０４ ｉ＋１の部分木構築ステップ、Ｓ９０５ 直前の部分木を分割した検索式を持つ部分木構築ステップ。
【特許請求の範囲】
【請求項１】
データベースから所望の情報を検索する情報検索装置において、
上記所望の情報検索を記述する検索式を読込み、該読込んだ検索式を所定の簡易形式に分割する検索式分割部と、
上記検索式分割部が分割した簡易形式検索式による検索時の必要リソースがシステムで持つリソース上限値内であるかを評価する検索式評価部と、
上記検索式分割部が出力する検索命令リストに従って上記所望の情報検索を行う検索処理部と、を備えて、
上記検索式分割部は、上記検索式評価部がリソース上限値内であると評価する評価内簡易形式に分割して、上記検索処理部は、該評価内簡易形式に基づいて情報検索を行うようにしたことを特徴とする情報検索装置。
【請求項２】
検索式分割部は、所定の簡易形式として２分木に展開して、該２分木による検索時に検索式評価部がリソース上限内であると評価する場合は、上記２分木の高さを高くして、該高くした２分木による検索時の上記検索式評価部による上記評価を繰返して、上記リソース上限に近い評価が得られる、高くした２分木を検索命令リストとして出力することを特徴とする請求項１記載の情報検索装置。
【請求項３】
検索式分割部は、２分木に展開する際に、先ず高さ１の部分木を作成するようにしたことを特徴とする請求項２記載の情報検索装置。
【請求項４】
検索式分割部は、２分木に展開する際に、同じラベルを持つ親子ノードを結合して部分木を作成するようにしたことを特徴とする請求項２記載の情報検索装置。
【請求項５】
検索式分割部は、所定の簡易形式として積和形または和積形の論理式で記述して、該論理式で検索時に検索式評価部がリソース上限内であると評価する場合は、上記論理式の結合高さを高くして、該高くした論理式による検索時の上記検索式評価部による上記評価を繰返して、上記リソース上限に近い評価が得られる、高くした論理式を検索命令リストとして出力することを特徴とする請求項１記載の情報検索装置。
【請求項６】
情報検索装置は、検索式分割部が出力する検索命令リストを表示出力する検索式出力部を備えて、上記検索命令リストを表示出力することを特徴とする請求項１記載の情報検索装置。
【請求項７】
データベースから所望の情報を検索するために、
上記所望の情報検索を記述する検索式を読込み、該読込んだ検索式を所定の簡易形式に分割する検索式分割部と、
上記検索式分割部が分割した簡易形式検索式による検索時の必要リソースがシステムで持つリソース上限値内であるかを評価する検索式評価部と、を備えて、
上記検索式分割部は、上記検索式評価部がリソース上限値内であると評価する評価内簡易形式に分割して、データベース検索のための検索式として出力することを特徴とするデータベース検索前処理回路。
【請求項８】
データベースから所望の情報を検索する情報検索方法において、
上記所望の情報検索を記述する検索式を読込み、該読込んだ検索式を所定の簡易形式に分割する検索式分割ステップと、
上記検索式分割ステップにより分割した簡易形式検索式による検索時の必要リソースがシステムで持つリソース上限値内であるかを評価する検索式評価ステップと、
上記検索式分割ステップは、上記検索式評価ステップでリソース上限値内であると評価する最長の長さの簡易形式検索式である最評価内簡易形式になるまで合成を繰返して、
上記検索式分割ステップで得られる上記最評価内簡易形式で記述される検索命令リストに従って上記所望の情報検索を行う検索処理ステップと、を備えたことを特徴とする情報検索方法。
【請求項９】
検索式分割ステップは、所定の簡易形式として２分木に展開して、該２分木による検索時に検索式評価ステップでリソース上限内であると評価された場合は、上記２分木の高さを高くして、該高くした２分木記述による検索時の上記検索式評価ステップによる上記評価を繰返して、上記リソース上限に近い評価が得られる、高くした２分木記述を検索命令リストとして出力することを特徴とする請求項８記載の情報検索方法。
【請求項１】
データベースから所望の情報を検索する情報検索装置において、
上記所望の情報検索を記述する検索式を読込み、該読込んだ検索式を所定の簡易形式に分割する検索式分割部と、
上記検索式分割部が分割した簡易形式検索式による検索時の必要リソースがシステムで持つリソース上限値内であるかを評価する検索式評価部と、
上記検索式分割部が出力する検索命令リストに従って上記所望の情報検索を行う検索処理部と、を備えて、
上記検索式分割部は、上記検索式評価部がリソース上限値内であると評価する評価内簡易形式に分割して、上記検索処理部は、該評価内簡易形式に基づいて情報検索を行うようにしたことを特徴とする情報検索装置。
【請求項２】
検索式分割部は、所定の簡易形式として２分木に展開して、該２分木による検索時に検索式評価部がリソース上限内であると評価する場合は、上記２分木の高さを高くして、該高くした２分木による検索時の上記検索式評価部による上記評価を繰返して、上記リソース上限に近い評価が得られる、高くした２分木を検索命令リストとして出力することを特徴とする請求項１記載の情報検索装置。
【請求項３】
検索式分割部は、２分木に展開する際に、先ず高さ１の部分木を作成するようにしたことを特徴とする請求項２記載の情報検索装置。
【請求項４】
検索式分割部は、２分木に展開する際に、同じラベルを持つ親子ノードを結合して部分木を作成するようにしたことを特徴とする請求項２記載の情報検索装置。
【請求項５】
検索式分割部は、所定の簡易形式として積和形または和積形の論理式で記述して、該論理式で検索時に検索式評価部がリソース上限内であると評価する場合は、上記論理式の結合高さを高くして、該高くした論理式による検索時の上記検索式評価部による上記評価を繰返して、上記リソース上限に近い評価が得られる、高くした論理式を検索命令リストとして出力することを特徴とする請求項１記載の情報検索装置。
【請求項６】
情報検索装置は、検索式分割部が出力する検索命令リストを表示出力する検索式出力部を備えて、上記検索命令リストを表示出力することを特徴とする請求項１記載の情報検索装置。
【請求項７】
データベースから所望の情報を検索するために、
上記所望の情報検索を記述する検索式を読込み、該読込んだ検索式を所定の簡易形式に分割する検索式分割部と、
上記検索式分割部が分割した簡易形式検索式による検索時の必要リソースがシステムで持つリソース上限値内であるかを評価する検索式評価部と、を備えて、
上記検索式分割部は、上記検索式評価部がリソース上限値内であると評価する評価内簡易形式に分割して、データベース検索のための検索式として出力することを特徴とするデータベース検索前処理回路。
【請求項８】
データベースから所望の情報を検索する情報検索方法において、
上記所望の情報検索を記述する検索式を読込み、該読込んだ検索式を所定の簡易形式に分割する検索式分割ステップと、
上記検索式分割ステップにより分割した簡易形式検索式による検索時の必要リソースがシステムで持つリソース上限値内であるかを評価する検索式評価ステップと、
上記検索式分割ステップは、上記検索式評価ステップでリソース上限値内であると評価する最長の長さの簡易形式検索式である最評価内簡易形式になるまで合成を繰返して、
上記検索式分割ステップで得られる上記最評価内簡易形式で記述される検索命令リストに従って上記所望の情報検索を行う検索処理ステップと、を備えたことを特徴とする情報検索方法。
【請求項９】
検索式分割ステップは、所定の簡易形式として２分木に展開して、該２分木による検索時に検索式評価ステップでリソース上限内であると評価された場合は、上記２分木の高さを高くして、該高くした２分木記述による検索時の上記検索式評価ステップによる上記評価を繰返して、上記リソース上限に近い評価が得られる、高くした２分木記述を検索命令リストとして出力することを特徴とする請求項８記載の情報検索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２００６−４００８１（Ｐ２００６−４００８１Ａ）
【公開日】平成１８年２月９日（２００６．２．９）
【国際特許分類】
【出願番号】特願２００４−２２１０３５（Ｐ２００４−２２１０３５）
【出願日】平成１６年７月２９日（２００４．７．２９）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
【公開日】平成１８年２月９日（２００６．２．９）
【国際特許分類】
【出願日】平成１６年７月２９日（２００４．７．２９）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
[ Back to top ]