(57)【要約】【課題】データ検索を効率化するための事前処理を提供する。【解決手段】判定部１２が、複数のフィールドを含むデータの集合から少なくとも１つのフィールドの値を指定する条件を満たすデータを検索するための条件に含まれる複数の条件式の各々の種類を判定し、生成部１４が、各条件式に応じた階層毎に、データの集合のうちの所定のデータに含まれ、かつ該条件式に関連するフィールドの値の各々を、判定部１２により判定された該条件式の種類に応じた形式の要素とするノードを含むツリー構造であって、該ノードに含まれる要素が示すフィールドの値を有するデータを、該要素に接続する子ノードにおける所定のデータとする検索用データ構造２０を生成する。【選択図】図１
2018200623.tif 000002
【特許請求の範囲】
【請求項１】
複数のフィールドを含むデータの集合から少なくとも１つのフィールドの値を指定する条件を満たすデータを検索するための前記条件に含まれる複数の条件式の各々の種類を判定する判定部と、
各条件式に応じた階層毎に、前記データの集合のうちの所定のデータに含まれ、かつ該条件式に関連するフィールドの値の各々を、前記判定部により判定された該条件式の種類に応じた形式の要素とするノードを含むツリー構造であって、該ノードに含まれる要素が示す前記フィールドの値を有するデータを、該要素に接続する子ノードにおける前記所定のデータとするデータ構造を生成する生成部と、
を含む情報処理装置。
【請求項２】
前記判定部は、前記条件式の種類として、等号を用いた条件式、不等号を用いた条件式、及び論理和を用いた条件式のいずれかを判定し、
前記生成部は、
前記条件式の種類が前記等号を用いた条件式の場合、該条件式に関連するフィールドの値をハッシュ値とするハッシュ表をノードとして生成し、
前記条件式の種類が前記不等号を用いた条件式の場合、該条件式に関連するフィールドの値を昇順又は降順で整列したリストをノードとして生成し、
前記条件式の種類が前記論理和を用いた条件式の場合、論理和で接続される部分条件式の各々に対応する配列要素を含む配列をノードとして生成すると共に、前記部分条件式の各々の種類に応じた形式のノードを、前記配列要素の子ノードとして生成する
請求項１に記載の情報処理装置。
【請求項３】
前記生成部は、前記等号を用いた条件式に対応するノード、前記不等号を用いた条件式に対応するノード、前記論理和を用いた条件式に対応するノードの順に、前記ツリー構造において階層が上位となるように前記データ構造を生成する請求項２に記載の情報処理装置。
【請求項４】
前記生成部により生成されたデータ構造のルートノードから順に、各条件式のパラメータが指定された条件を満たすノードを辿ることにより、前記条件を満たすデータを検索する検索部を含み、
前記検索部は、
検索対象のノードが前記等号を用いた条件式に対応するノードの場合、前記ハッシュ表に含まれる前記条件を満たすハッシュ値から接続される子ノードを辿り、
検索対象のノードが前記不等号を用いた条件式に対応するノードの場合、前記リストの先頭又は末尾の値から順に前記条件を満たすか否かを判定し、該条件を満たすリスト要素から接続される子ノードを辿り、
検索対象のノードが前記論理和を用いた条件式に対応するノードの場合、前記配列の配列要素のそれぞれに接続される子ノードを順次辿る
請求項２又は請求項３に記載の情報処理装置。
【請求項５】
前記生成部は、異なる要素間で、該要素が示す前記フィールドの値を有するデータが共通する場合には、前記異なる要素の各々を同一の子ノードに接続する請求項１〜請求項４のいずれか１項に記載の情報処理装置。
【請求項６】
前記判定部は、否定を含む条件式を、ド・モルガンの法則及び逆の演算子への変換により否定を除去した条件式に変換する請求項１〜請求項５のいずれか１項に記載の情報処理装置。
【請求項７】
前記判定部は、論理積を含む条件を該論理積で区切られる部分毎に分割し、分割した各部分を前記条件式の各々とする請求項１〜請求項６のいずれか１項に記載の情報処理装置。
【請求項８】
複数のフィールドを含むデータの集合から少なくとも１つのフィールドの値を指定する条件を満たすデータを検索するための前記条件に含まれる複数の条件式の各々の種類を判定し、
各条件式に応じた階層毎に、前記データの集合のうちの所定のデータに含まれ、かつ該条件式に関連するフィールドの値の各々を、判定した該条件式の種類に応じた形式の要素とするノードを含むツリー構造であって、該ノードに含まれる要素が示す前記フィールドの値を有するデータを、該要素に接続する子ノードにおける前記所定のデータとするデータ構造を生成する
ことを含む処理をコンピュータが実行する情報処理方法。
【請求項９】
複数のフィールドを含むデータの集合から少なくとも１つのフィールドの値を指定する条件を満たすデータを検索するための前記条件に含まれる複数の条件式の各々の種類を判定し、
各条件式に応じた階層毎に、前記データの集合のうちの所定のデータに含まれ、かつ該条件式に関連するフィールドの値の各々を、判定した該条件式の種類に応じた形式の要素とするノードを含むツリー構造であって、該ノードに含まれる要素が示す前記フィールドの値を有するデータを、該要素に接続する子ノードにおける前記所定のデータとするデータ構造を生成する
ことを含む処理をコンピュータに実行させる情報処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
開示の技術は、情報処理装置、情報処理方法、及び情報処理プログラムに関する。
【背景技術】
【０００２】
データの集合から指定された条件を満たすデータを検索することは様々な場面で使用され、高速な演算が求められる。そこで、データ検索の高速化に関する技術が存在する。
【０００３】
例えば、データベースに対するユーザからの問合せを解析して対応する処理手順を決定し、それを実行するデータベース処理システムにおける問合せ処理方法が提案されている。この方法では、入力された問合せを解析し、その解析結果とデータベースの統計情報とから単一あるいは複数の内部処理手順を選定、格納し、問合せに代入される値と処理手順の問い合わせ条件式とから判断して条件評価不要となる条件式を検出する。そして、検出された条件式を除き、選定、格納された内部処理手順の中から条件式評価が必要となる条件式だけからなる処理手順を選択し、実行する。
【０００４】
また、データベース構造に依存しない自律的な検索手段を提供すると共に高速検索することを目的とするデータベース検索装置が提案されている。この装置は、キーの値とゴールの値を入力し、データベースからキーの値と一致する値を持つレコードを検索し、該レコードのデータフィールドの値を取り出す。そして、取り出したデータフィールドの値がゴールの値に一致したときに出力し、一致しないときに取り出したデータフィールドの値を新たなキーの値にして検索を繰り返す。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平５−３４２２７７号公報
【特許文献２】特開平９−６２６９５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
データ集合から指定された条件を満たすデータを検索する場合において、複数の条件式を組み合わせた条件であって、条件式は同一だが条件式に適用されるパラメータが異なる条件で繰り返し検索を行う場合がある。検索を高速化するために、従来技術では、処理手順を選定するなどの事前処理を行っているが、特に、上記のような検索を行う場合などには、より適した事前処理を行えることが望ましい。
【０００７】
開示の技術は、一つの側面として、データ検索を効率化するための事前処理を提供することを目的とする。
【課題を解決するための手段】
【０００８】
開示の技術は、一つの態様として、複数のフィールドを含むデータの集合から少なくとも１つのフィールドの値を指定する条件を満たすデータを検索するための前記条件に含まれる複数の条件式の各々の種類を判定する判定部を含む。また、開示の技術は、検索用データ構造を生成する生成部を含む。検索用データ構造は、各条件式に応じた階層毎に、前記データの集合のうちの所定のデータに含まれ、かつ該条件式に関連するフィールドの値の各々を、前記判定部により判定された該条件式の種類に応じた形式の要素とするノードを含むツリー構造である。また、検索用データ構造において、該ノードに含まれる要素が示す前記フィールドの値を有するデータが、該要素に接続する子ノードにおける前記所定のデータとなる。
【発明の効果】
【０００９】
開示の技術は、一つの側面として、データ検索を効率化するための事前処理を提供することができる、という効果を有する。
【図面の簡単な説明】
【００１０】
【図１】第１及び第２実施形態に係る情報処理装置の機能ブロック図である。
【図２】検索の一例を説明するための図である。
【図３】検索対象テーブルの一例を示す図である。
【図４】等式条件式に対応するノードの生成を説明するための図である。
【図５】不等式条件式に対応するノードの生成を説明するための図である。
【図６】ＯＲ条件式に対応するノードの生成を説明するための図である。
【図７】関数ｆ’テーブルの一例を示す図である。
【図８】情報処理装置として機能するコンピュータの概略構成を示すブロック図である。
【図９】生成処理の一例を示すフローチャートである。
【図１０】検索対象テーブルの一例を示す図である。
【図１１】条件パラメータテーブルの一例を示す図である。
【図１２】ＯＲ条件式処理の一例を示すフローチャートである。
【図１３】検索用データ構造の一例を示す図である。
【図１４】検索処理の一例を示すフローチャートである。
【図１５】検索処理の一例を示すフローチャートである。
【図１６】検索用データ構造の一例を示す図である。
【図１７】条件式に対応したノードとして二分探索用のテーブルを生成する場合を説明するための図である。
【発明を実施するための形態】
【００１１】
以下、図面を参照して開示の技術に係る実施形態の一例を詳細に説明する。
【００１２】
＜第１実施形態＞
図１に示すように、第１実施形態に係る情報処理装置１０は、機能部として、判定部１２と、生成部１４と、検索部１６とを含む。情報処理装置１０に、複数のフィールド（列）を含むレコードの集合である検索対象テーブルＲと、検索対象テーブルＲから、所定のレコードを検索するための条件Ｌとが入力された場合、判定部１２及び生成部１４が検索用データ構造２０を生成する。また、情報処理装置１０に、条件Ｌに適用されるパラメータの組が１つ以上記憶された条件パラメータテーブルＭが入力された場合、検索部１６が検索用データ構造２０を用いて、検索対象テーブルＲに含まれるレコードから、条件を満たすレコードを検索する。情報処理装置１０の各機能部の詳細については後述する。なお、レコードは開示の技術のデータの一例であり、検索対象テーブルは開示の技術のデータの集合の一例である。
【００１３】
ここで、本実施形態では、一例として、条件式は同一だが条件式に設定するパラメータを異ならせた条件で繰り返し検索を行う場合を想定する。例えば、図２に示すように、テーブルＡのデータの「出身県」フィールドの値を、テーブルＢの「地方」フィールドの単位で分類してテーブルＡのレコード数を集計し、分類毎のレコード数を各階級の頻度するヒストグラムを作成する場合などが考えられる。すなわち、テーブルＡのレコードの値がパラメータとして適用された条件によりテーブルＢのレコードを検索することで、テーブルＡの各レコードがヒストグラムのどの階級に属するかを特定する。したがって、この場合、テーブルＢが検索対象テーブルＲに相当し、テーブルＡが条件パラメータテーブルＭに相当する。
【００１４】
また、ヒストグラムの階級幅を変更する場合、すなわち、分類する「地方」の単位を変更する場合は、例えば図２に示すように、テーブルＢとは「地方」の分類が異なるテーブルＣを検索対象テーブルＲに変更する。これにより、分類方法の変更に柔軟に対応することができる。
【００１５】
図２の例では、テーブルＢ（又はＣ）を検索する際の条件は、テーブルＢ（又はＣ）において、「県」フィールドの値が、テーブルＡの「出身県」フィールドの値と一致するレコードを検索することを指定するものとなる。以下では、テーブルＸのＹフィールドを「Ｘ．Ｙ」と表記する。上記の条件は、「Ａ．出身県＝Ｂ．県」と表すことができ、テーブルＡの各レコードの「出身県」の値が、この条件の「Ａ．出身県」に入るパラメータである。
【００１６】
上記の例では、検索対象テーブルＲからレコードを検索する際の条件が１つの場合を示しているが、検索対象テーブルＲ及び条件パラメータテーブルＭに含まれるフィールドが複数ある場合には、条件に含まれる条件式も複数となる場合がある。そこで、本実施形態では、複数の条件式を組み合わせた条件で検索を行う場合を想定する。なお、一般的に、検索条件に用いられる演算子は論理積（ＡＮＤ）、論理和（ＯＲ）、及び否定（ＮＯＴ）であり、比較演算における等式には等号（＝）が用いられ、不等式には等号付き不等号を含む不等号（＜、＞、≦、≧）が用いられる。本実施形態においても、情報処理装置１０に入力される条件Ｌは、これらの演算子、等号、及び不等号を用いて表されているものとする。
【００１７】
上記のような検索を行う場合に、レコードの検索を高速化するために、１つの条件式での検索で抽出されたレコードに対して、次の条件式での検索を行うというようにレコードを絞り込んで、条件と検索対象のレコードとの比較回数を減らすことが考えられる。しかし、この場合、条件パラメータテーブルＭのレコード１つに付き少なくとも１回は検索対象テーブルＲの全てのレコードを検索する必要がある。また、データベースのインデックスやハッシュ表を使って、条件を満たすレコードを絞り込むことも考えられる。しかし、この場合、複数の条件式を含むような複雑な条件を用いた検索には適用することができない。
【００１８】
そこで、本実施形態では、特に、複数の条件式を組み合わせた条件であって、条件式は同一だが条件式のパラメータが異なる条件で繰り返し検索を行う場合に、事前処理として、効率的に検索を行うためのデータ構造を検索対象テーブルＲから生成する。以下、情報処理装置１０の各機能部について詳述する。
【００１９】
判定部１２は、入力された条件Ｌ（テキストデータ）を、条件式の各々に分割する。具体的には、判定部１２は、条件ＬにＮＯＴが含まれる場合、ド・モルガンの法則及び逆の演算子への変換によってＮＯＴを変換（例えば、「ＮＯＴ  ａ＜ｂ」を「ａ≧ｂ」に変換）することにより、ＮＯＴを除去する。そして、判定部１２は、ＮＯＴが除去された条件Ｌを、条件Ｌに含まれる「ＡＮＤ」で区切られる部分毎に分割し、分割した各部分を条件式の各々とする。判定部１２は、各条件式に条件番号を付与する。以下では、条件Ｌに含まれる条件番号ｉの条件式を「Ｌｉ」と表記する。
【００２０】
また、判定部１２は、各条件式の種類を判定する。本実施形態では、条件式の種類として、等号を用いた条件式（以下、「等式条件式」という）、不等号を用いた条件式（以下、「不等式条件式」という）、及び論理和を用いた条件式（以下、「ＯＲ条件式」という）のいずれかを判定する。判定部１２は、判定結果を生成部１４に受け渡す。
【００２１】
生成部１４は、検索対象テーブルＲと条件式とに基づいて、各条件式に対応した階層毎に、その条件式に対応するノードを配置したツリー構造の検索用データ構造２０を生成する。具体的には、生成部１４は、条件式毎に、その条件式に関連するフィールドの値を、判定部１２により判定された、その条件式の種類に応じた形式で表したノードを生成する。条件式に関連するフィールドの値とは、条件式Ｌｉに対応するノードと接続される上位層のノードに対応付けられた関数ｆ（Ｌｉ−１，ｘ）（詳細は後述）が返すレコードにおける、条件式Ｌｉで指定されているフィールドの値のバリエーションである。
【００２２】
より具体的には、生成部１４は、条件式の種類が等式条件式の場合、その条件式に関連するフィールドの値をハッシュ値とするハッシュ表を、その条件式に対応するノードとして生成する。例えば、図３に示すような検索対象テーブルＲについて、等式条件式に対応するノードを生成する場合について説明する。例えば、条件式Ｌ０：Ｒ．ｃ１＝Ｍ．ｃ１であるとすると、検索対象テーブルＲの「ｃ１」フィールドの値のバリエーションは、「１」及び「２」である。したがって、生成部１４は、図４に示すように、「１」及び「２」をハッシュ値として含むハッシュ表３１を生成する。
【００２３】
また、生成部１４は、条件式の種類が不等式条件式の場合、その条件式に関連するフィールドの値を不等式に応じて昇順又は降順で整列したリストを、その条件式に対応するノードとして生成する。例えば、図３に示すような検索対象テーブルＲについて、不等式条件式に対応するノードを生成する場合について説明する。例えば、条件式Ｌ０：Ｒ．ｃ１＞Ｍ．ｃ１であるとすると、検索対象テーブルＲの「ｃ１」フィールドの値のバリエーションは、「１」及び「２」である。また、パラメータ「Ｍ．ｃ１」が与えられ、「Ｒ．ｃ１＞Ｍ．ｃ１」か否かを判定する際には、「Ｒ．ｃ１」が大きい方から順に判定して行く方が効率的である。したがって、生成部１４は、図５に示すように、検索対象テーブルＲの「ｃ１」フィールドの値のバリエーション「１」及び「２」を降順で並べたリスト３２を生成する。
【００２４】
「検索対象テーブルＲの値≧条件パラメータテーブルＭの値」の場合も同様に、生成部１４は、検索対象テーブルＲの該当フィールドの値のバリエーションを降順で並べたリスト３２を生成する。また、「検索対象テーブルＲの値＜（又は≦）条件パラメータテーブルＭの値」の場合は、生成部１４は、検索対象テーブルＲの該当フィールドの値のバリエーションを昇順で並べたリスト３２を生成する。なお、不等式に係わらず、常に昇順又は降順で並び替え、検索の際に、リストの先頭から見るか末尾から見るかを設定しておくようにしてもよい。
【００２５】
また、生成部１４は、条件式の種類がＯＲ条件式の場合、ＯＲで接続される部分条件式の各々に対応する配列要素を含む配列を表すノードを生成すると共に、部分条件式の各々の種類に応じた形式のノードを下位層に生成して、各配列要素と接続する。例えば、図３に示すような検索対象テーブルＲについて、ＯＲ条件式に対応するノードを生成する場合について説明する。例えば、条件式Ｌ０：Ｐ１  ＯＲ  Ｐ２（Ｐ０：Ｒ．ｃ１＝Ｍ．ｃ１，Ｐ１：  Ｒ．ｃ２＝Ｍ．ｃ２）であるとする。なお、Ｐｊは条件式Ｌｉのｊ番目の部分条件式を表す。この場合、図６に示すように、生成部１４は、部分条件式Ｐ０及びＰ１の各々に対応する配列要素を含む配列３３を生成する。そして、生成部１４は、部分条件式Ｐ０及びＰ１の種類が等式条件式であることから、図４の場合と同様に、部分条件式Ｐ０及びＰ１のそれぞれについてハッシュ表３１を生成し、Ｐ０及びＰ１の配列要素の各々とハッシュ表３１の各々とを接続する。
【００２６】
また、生成部１４は、生成したハッシュ表３１の各ハッシュ値、リスト３２の各リスト要素、又は配列３３の各配列要素（以下、これらをまとめて「ノード要素３４」ともいう）に、関数ｆ（Ｌｉ，ｘ）を対応付ける。関数ｆ（Ｌｉ，ｘ）は、与えられたレコード集合のうち、関数ｆ（Ｌｉ，ｘ）が対応付けられるノード要素３４が示す値ｘを有するレコードを出力する関数である。生成部１４は、関数ｆ（Ｌｉ，ｘ）に与えるレコード集合を、関数ｆ（Ｌｉ−１，ｘ）が返すレコード集合とする。すなわち、生成部１４は、関数ｆ（Ｌｉ−１，ｘ）の出力先に、条件式Ｌｉに対応するノードを生成する。このため、関数ｆ（Ｌｉ−１，ｘ）は、条件式Ｌｉ−１を満たす値として、値ｘを示すノード要素が選択された場合に、次の条件式Ｌｉを満たすか否かの判定対象となるレコードを出力することになる。なお、次の条件式Ｌｉが存在しない場合、関数ｆ（Ｌｉ−１，ｘ）が返すレコードは、条件を満たすレコードを示す検索結果として出力される。
【００２７】
上記のように、生成部１４は、関数ｆ（Ｌｉ−１，ｘ）の出力先に、次の条件式Ｌｉに対応するノードを生成するため、原則、上位層に存在するノードのノード要素３４の各々に対応して次の層のノードが生成される。ただし、ＯＲ条件式においてＯＲで接続される部分条件式の各々に対応するノードに含まれるノード要素３４の各々に対応付けられた関数ｆ（Ｌｉ，Ｐｊ，ｘ）の各々が返すレコードが共通する場合がある。この場合には、生成部１４は、それらのノード要素の接続先を同一のノードとする。
【００２８】
この処理を実現するために、生成部１４は、各ノード要素３４に関数ｆ（Ｌｉ，Ｐｊ，ｘ）を対応付ける際に、図７に示すような関数ｆ’テーブル３５に、対応付け済みの関数ｆ’の情報を記憶しておく。図７の例では、関数ｆ’テーブル３５には、「ｆ’」の情報と、ｆ’が示す関数ｆ（Ｌｉ，Ｐｊ，ｘ）が返すレコードの情報とが対応付けて記憶されている。
【００２９】
生成部１４は、各ノード要素３４に関数ｆ（Ｌｉ，Ｐｊ，ｘ）を対応付ける際に、図７に示すような関数ｆ’テーブル３５を参照し、対応付ける関数ｆ（Ｌｉ，Ｐｊ，ｘ）と同一のレコードを返す関数ｆ’が既に他のノード要素３４に対応付けられているか否かを確認する。例えば、図６の例で、部分条件式Ｐ１に対応するハッシュ表３１のうち、値が「１」のノード要素３４に対応付ける関数ｆ（Ｌ０，Ｐ１，１）が返すレコードは、｛ｒ１，ｒ２｝である。図７を参照すると、矢印Ｂの情報が示すように、｛ｒ１，ｒ２｝を返す関数ｆ（Ｌ０，Ｐ０，１）が既に他のノード要素３４に対応付け済みの関数ｆ’として記憶されている。この場合、生成部１４は、図６の破線矢印Ａに示すように、該当のノード要素３４に対応付けた関数ｆ（Ｌｉ，Ｐｊ，ｘ）の出力先を、関数ｆ’テーブル３５で特定した関数ｆ’の出力先と同一になるように設定する。
【００３０】
また、生成部１４は、ＯＲ条件式に対応するノードを生成する際、関数ｆ（Ｌｉ−１，ｘ）が返すレコード集合のサイズ（レコードの数）が予め定めた閾値を超える場合、ｆ（Ｌｉ−１，ｘ）が返すレコード集合を閾値以下のサイズのレコード集合に分割する。そして、生成部１４は、分割された各レコード集合について、上述の処理を実行する。これにより、検索時の組み合わせ爆発の発生を抑制する。
【００３１】
生成部１４は、生成した検索用データ構造２０を所定の記憶領域に記憶する。
【００３２】
検索部１６は、生成部１４により生成された検索用データ構造２０のルートノードから順に、入力された各条件式のパラメータにしたがって、条件を満たすノードを辿ることにより、条件を満たすレコードを検索する。
【００３３】
具体的には、検索部１６は、検索対象のノードが等式条件式に対応するノード（ハッシュ表３１）の場合、ハッシュ表３１に含まれるハッシュ値のうち、該当の等式条件式を満たすハッシュ値を探索し、そのハッシュ値に接続された子ノードを次の検索対象のノードとする。検索部１６は、ハッシュ表３１に条件を満たすハッシュ値が存在しない場合には、「該当レコード無し」を示す検索結果を出力する。
【００３４】
また、検索部１６は、検索対象のノードが不等式条件式に対応するノード（リスト３２）の場合、リスト３２の先頭の値から順に、該当の不等式条件式を満たすか否かを判定し、不等式条件を満たす場合、そのリスト要素に接続された子ノードを次の検索対象のノードとする。検索部１６は、リスト要素が示す値が条件を満たさなくなった段階で、残りのリスト要素についての検索を行うことなく、上位層の未処理のノードに戻るか、又は「該当レコード無し」を示す検索結果を出力する。
【００３５】
また、検索部１６は、検索対象のノードがＯＲ条件式に対応するノード（配列３３）の場合、配列３３の配列要素のそれぞれに接続されるノードを順次、次の検索対象のノードとする。検索部１６は、検索結果が得られないまま検索対象に設定すべき配列要素が存在しなくなると、上位層の未処理のノードに戻るか、又は「該当レコード無し」を示す検索結果を出力する。
【００３６】
また、検索部１６は、検索対象ノードがリーフノードの場合、検索対象ノードに含まれるノード要素３４のうち、検索対象ノードに対応する条件式を満たす値を示すノード要素３４に対応付けられた関数ｆ（Ｌｉ，ｘ）が返すレコードを、検索結果として出力する。
【００３７】
情報処理装置１０は、例えば図８に示すコンピュータ４０で実現することができる。コンピュータ４０は、Central Processing Unit（ＣＰＵ）４１と、一時記憶領域としてのメモリ４２と、不揮発性の記憶部４３とを備える。また、コンピュータ４０は、表示装置、出力装置等の入出力装置４４と、記憶媒体４９に対するデータの読み込み及び書き込みを制御するRead/Write（Ｒ／Ｗ）部４５とを含む。また、コンピュータ４０は、インターネット等のネットワークに接続される通信インターフェース（Ｉ／Ｆ）４６を備える。ＣＰＵ４１、メモリ４２、記憶部４３、入出力装置４４、Ｒ／Ｗ部４５、及び通信Ｉ／Ｆ４６は、バス４７を介して互いに接続される。
【００３８】
記憶部４３は、Hard Disk Drive（ＨＤＤ）、Solid State Drive（ＳＳＤ）、フラッシュメモリ等によって実現できる。記憶媒体としての記憶部４３には、コンピュータ４０を、情報処理装置１０として機能させるための情報処理プログラム５０が記憶される。情報処理プログラム５０は、判定プロセス５２と、生成プロセス５４と、検索プロセス５６とを有する。また、記憶部４３は、検索用データ構造２０を構成する情報が記憶される情報記憶領域６０を有する。
【００３９】
ＣＰＵ４１は、情報処理プログラム５０を記憶部４３から読み出してメモリ４２に展開し、情報処理プログラム５０が有するプロセスを順次実行する。ＣＰＵ４１は、判定プロセス５２を実行することで、図１に示す判定部１２として動作する。また、ＣＰＵ４１は、生成プロセス５４を実行することで、図１に示す生成部１４として動作する。また、ＣＰＵ４１は、検索プロセス５６を実行することで、図１に示す検索部１６として動作する。また、ＣＰＵ４１は、情報記憶領域６０から情報を読み出して、検索用データ構造２０をメモリ４２に展開する。これにより、情報処理プログラム５０を実行したコンピュータ４０が、情報処理装置１０として機能することになる。なお、プログラムを実行するＣＰＵ４１はハードウェアである。
【００４０】
次に、第１実施形態に係る情報処理装置１０の作用について説明する。情報処理装置１０に、検索対象テーブルＲと、条件Ｌとが入力されると、情報処理装置１０が、図９に示す生成処理を実行する。また、検索対象テーブルＲから生成された検索用データ構造２０が情報処理装置１０に記憶された状態で、情報処理装置１０に、条件パラメータテーブルＭが入力されると、情報処理装置１０が、図１４及び図１５に示す検索処理を実行する。以下、生成処理及び検索処理の各々について詳述する。
【００４１】
まず、図９を参照して、生成処理について説明する。なお、ここでは、図１０に示す検索対象テーブルＲ、及び条件Ｌ「Ｒ．ＳＹ  ≦  Ｍ．Ｙ  ＡＮＤ  Ｍ．Ｙ  ≦  Ｒ．ＥＹ  ＡＮＤ  Ｍ．ｎａｍｅ  ＝  Ｒ．ｎａｍｅ」が入力されるものとする。なお、条件Ｌは、図１１に示す条件パラメータテーブルＭのフィールドを用いて表されている。
【００４２】
ステップＳ１１で、判定部１２が、ド・モルガンの法則及び逆の演算子への変換により、入力された条件Ｌに含まれるにＮＯＴを変換することによりＮＯＴ除去する。そして、判定部１２は、ＮＯＴが除去された条件Ｌを、条件Ｌに含まれる「ＡＮＤ」で区切られる部分毎に分割し、分割した各部分を条件式Ｌｉ（ｉは条件式番号）とする。ここでは、以下のような条件式Ｌｉ（ｉ＝０，１，２）が得られる。
【００４３】
Ｌ０：  Ｒ．ＳＹ  ≦  Ｍ．Ｙ
Ｌ１：  Ｍ．Ｙ  ≦  Ｒ．ＥＹ
Ｌ２：  Ｍ．ｎａｍｅ  ＝  Ｒ．ｎａｍｅ
【００４４】
次に、ステップＳ１２で、生成部１４が、条件式を特定するための変数ｉに０を設定する。また、生成部１４は、ルートノードを生成し、関数ｆ（Ｌｉ，ｘ）の初期値として、入力された検索対象テーブルＲに含まれる全てのレコードを返す関数ｆ（Ｌｉ−１）を、生成したルートノードに対応付ける。
【００４５】
次に、ステップＳ１３で、判定部１２が、上記ステップＳ１１で分割した条件式に、上記ステップＳ１２又は後述するステップＳ４０で設定された変数ｉで示される条件式Ｌｉが存在するか否かを判定する。条件式Ｌｉが存在する場合には、処理はステップＳ１４へ移行する。
【００４６】
ステップＳ１４では、判定部１２が、条件式Ｌｉが等式条件式か否かを判定する。条件式Ｌｉが等式条件式の場合には、処理はステップＳ１５へ移行し、等式条件式ではない場合には、処理はステップＳ１７へ移行する。
【００４７】
ステップＳ１５では、生成部１４が、上位層のノードに含まれるノード要素３４の各々に対応付けられた関数ｆ（Ｌｉ−１，ｘ）の出力先の各々に対応付けて、条件式Ｌｉに対応するノードを生成する。具体的には、生成部１４は、関数ｆ（Ｌｉ−１，ｘ）が返すレコードにおける、条件式Ｌｉで指定されているフィールドの値のバリエーションをハッシュ値とするハッシュ表３１を、条件式Ｌｉに対応するノードとして生成する。
【００４８】
次に、ステップＳ１６で、生成部１４が、生成したハッシュ表３１のノード要素３４（ハッシュ値）の各々に、関数ｆ（Ｌｉ−１，ｘ）が返すレコードのうち、該当のノード要素３４が示す値ｘを有するレコードを出力する関数ｆ（Ｌｉ，ｘ）を対応付ける。そして、処理はステップＳ４０へ移行する。
【００４９】
ステップＳ１７では、判定部１２が、条件式Ｌｉが不等式条件式か否かを判定する。条件式Ｌｉが不等式条件式の場合には、処理はステップＳ１８へ移行し、不等式条件式ではない場合には、処理はステップＳ２０へ移行する。
【００５０】
ステップＳ１８では、生成部１４が、上位層のノードに含まれるノード要素３４の各々に対応付けられた関数ｆ（Ｌｉ−１，ｘ）の出力先の各々に対応付けて、条件式Ｌｉに対応するノードを生成する。具体的には、生成部１４は、関数ｆ（Ｌｉ−１，ｘ）が返すレコードにおける、条件式Ｌｉで指定されているフィールドの値のバリエーションを、不等式に応じて昇順又は降順で整列したリスト３２を、条件式Ｌｉに対応するノードとして生成する。
【００５１】
次に、ステップＳ１９で、生成部１４が、生成したリスト３２のノード要素３４（リスト要素）の各々に、関数ｆ（Ｌｉ−１，ｘ）が返すレコードのうち、該当のノード要素３４が示す値ｘを有するレコードを出力する関数ｆ（Ｌｉ，ｘ）を対応付ける。そして、処理はステップＳ４０へ移行する。
【００５２】
上記ステップＳ１７で否定判定となった場合、条件式ＬｉはＯＲ条件式である。そこで、ステップＳ２０では、生成部１４が、関数ｆ（Ｌｉ−１，ｘ）が返すレコード集合のサイズ（レコードの数）が予め定めた閾値以下か否かを判定する。関数ｆ（Ｌｉ−１，ｘ）が返すレコード集合のサイズが閾値以下の場合は、処理はステップＳ３０へ移行し、後述するＯＲ条件式処理が実行される。関数ｆ（Ｌｉ−１，ｘ）が返すレコード集合のサイズが閾値を超える場合は、ステップＳ２１へ移行し、生成部１４が、ｆ（Ｌｉ−１，ｘ）が返すレコード集合を閾値以下のサイズのレコード集合に分割する。例えば、ｆ（Ｌｉ−１，ｘ）＝｛ｒ１，ｒ２，・・・，ｒ１００｝で、閾値が５０とする。この場合、生成部１４は、例えば、ｆ（Ｌｉ−１，ｘ）を、ｆ０（Ｌｉ−１，ｘ）＝｛ｒ１，・・・，ｒ５０｝と、ｆ１（Ｌｉ−１，ｘ）＝｛ｒ５１，・・・，ｒ１００｝とに分割し、ｆ（Ｌｉ−１，ｘ）の出力先を分岐させる。そして、処理はステップＳ３０へ移行し、分割したレコード集合毎に、後述するＯＲ条件式処理が実行される。
【００５３】
ここで、図１２を参照して、生成処理のステップＳ３０で実行されるＯＲ条件式処理について説明する。
【００５４】
ステップＳ３１で、生成部１４が、上位層のノードに含まれるノード要素３４の各々に対応付けられた関数ｆ（Ｌｉ−１，ｘ）の出力先の各々に対応付けて、条件式Ｌｉに対応するノードを生成する。具体的には、生成部１４は、ＯＲで接続される部分条件式Ｐｊの各々に対応する配列要素を含む配列３３を、条件式Ｌｉに対応するノードとして生成する。
【００５５】
次に、ステップＳ３２で、生成部１４が、生成した配列３３のノード要素３４（配列要素）の各々に、関数ｆ（Ｌｉ−１，ｘ）を対応付ける。
【００５６】
次に、ステップＳ３３で、部分条件式Ｐｊの各々の種類に応じて、上記ステップＳ３１で生成したノード（配列３３）の下位層に、条件式Ｌｉの部分条件式Ｐｊに対応するノードを生成して、上位層の部分条件式Ｐｊに対応する各配列要素と接続する。部分条件式Ｐｊの種類に応じたノードの生成の具体的方法は、生成処理（図９）のステップＳ１５及びＳ１６、又はステップＳ１８及びＳ１９と同様である。
【００５７】
次に、ステップＳ３４で、生成部１４が、生成したノードのノード要素３４（ハッシュ値又はリスト要素）の各々に、関数ｆ（Ｌｉ，Ｐｊ，ｘ）を対応付ける。関数ｆ（Ｌｉ，Ｐｊ，ｘ）は、関数ｆ（Ｌｉ−１，ｘ）が返すレコードのうち、該当のノード要素３４が示す値ｘを有するレコードを出力する関数である。
【００５８】
次に、ステップＳ３５で、生成部１４が、上記ステップＳ３４で対応付けた関数ｆ（Ｌｉ，Ｐｊ，ｘ）と同一のレコードを返す関数ｆ’が、例えば図７に示すような関数ｆ’テーブル３５に記憶されているか否かを判定する。該当の関数ｆ’が関数ｆ’テーブル３５に記憶されている場合には、処理はステップＳ３６へ移行し、記憶されていない場合には、処理はステップＳ３７へ移行する。
【００５９】
ステップＳ３６では、生成部１４が、上記ステップＳ３４で、ノード要素３４に対応付けた関数ｆ（Ｌｉ，Ｐｊ，ｘ）の出力先を、上記ステップＳ３５で、関数ｆ’テーブル３５から特定した関数ｆ’の出力先と同一になるように設定する。そして、処理は生成処理（図９）にリターンする。
【００６０】
一方、ステップＳ３７では、上記ステップＳ３４で、ノード要素３４に対応付けた関数ｆ（Ｌｉ，Ｐｊ，ｘ）の情報を、関数ｆ’テーブル３５に記憶して、処理は生成処理（図９）にリターンする。
【００６１】
なお、上記ステップＳ３５〜Ｓ３７の処理は、条件式Ｌｉの部分条件式Ｐｊに対応するノードのノード要素３４毎に実行する。
【００６２】
次に、生成処理（図９）のステップＳ４０で、判定部１２が、変数ｉを１インクリメントして、処理はステップＳ１３に戻る。ステップＳ１３で、条件式Ｌｉが存在しないと判定される場合、すなわち、条件Ｌに含まれる全ての条件式についてステップＳ１４〜Ｓ３０の処理が終了した場合には、処理はステップＳ４１へ移行する。
【００６３】
ステップＳ４１では、生成部１４が、生成した検索用データ構造２０を所定の記憶領域に記憶して、生成処理は終了する。なお、検索用データ構造２０には、ノードの情報、ノード間の接続の情報、各ノード要素３４に対応付けた関数ｆ（Ｌｉ，ｘ）又はｆ（Ｌｉ，Ｐｊ，ｘ）の情報、ツリー構造の各階層と条件式Ｌｉとの対応関係を示す情報等が含まれる。
【００６４】
上記の図１０の検索対象テーブルＲから生成した検索用データ構造２０の一例を図１３に示す。図１３に示す丸印のノードはルートノード３６である。ルートノード３６には関数ｆ（Ｌ−１）、すなわち、検索対象テーブルＲの全てのレコードを返す関数が対応付けられる。関数ｆ（Ｌ−１）の出力先には、条件式Ｌ０に対応するノードとして、検索対象テーブルＲの「ＳＹ」フィールドの値のバリエーション（「１９８０」及び「１９９０」）を昇順で整列したリスト３２Ａが生成される。リスト３２Ａのノード要素３４のうち、値が「１９８０」のノード要素３４Ａには、検索対象テーブルＲの「ＳＹ」フィールドの値が「１９８０」であるレコード｛ｒ２，ｒ３｝を返す関数ｆ（Ｌ０，１９８０）が対応付けられる。同様に、値が「１９９０」のノード要素３４Ｂには、レコード｛ｒ１，ｒ４，ｒ５｝を返す関数ｆ（Ｌ０，１９９０）が対応付けられる。
【００６５】
また、関数ｆ（Ｌ０，１９８０）の出力先には、条件式Ｌ１に対応するノードとして、ｆ（Ｌ０，１９８０）が返すレコード｛ｒ２，ｒ３｝の「ＥＹ」フィールドの値のバリエーション（「１９８９」）を含むリスト３２Ｃが生成される。同様に、関数ｆ（Ｌ０，１９９０）の出力先には、条件式Ｌ１に対応するノードとして、レコード｛ｒ１，ｒ４，ｒ５｝の「ＥＹ」フィールドの値のバリエーション（「１９９４」及び「１９９９」）を降順で整列したリスト３２Ｃが生成される。リスト３２Ｃのノード要素３４のうち、値が「１９８９」のノード要素３４Ｃには、レコード｛ｒ２，ｒ３｝のうち、「ＥＹ」フィールドの値が「１９８９」であるレコード｛ｒ２，ｒ３｝を返す関数ｆ（Ｌ１，１９８９）が対応付けられる。同様に、値が「１９９９」のノード要素３４Ｄには、レコード｛ｒ１，ｒ４｝を返す関数ｆ（Ｌ１，１９９９）が対応付けられ、値が「１９９４」のノード要素３４Ｅには、レコード｛ｒ５｝を返す関数ｆ（Ｌ１，１９９４）が対応付けられる。
【００６６】
また、関数ｆ（Ｌ１，１９８９）の出力先には、条件式Ｌ２に対応するノードとして、レコード｛ｒ２，ｒ３｝における「ｎａｍｅ」フィールドの値のバリエーション（「ｎｏｂｕ」及び「ｙａｓｕ」）をハッシュ値とするハッシュ表３１Ａが生成される。同様に、関数ｆ（Ｌ１，１９９９）の出力先には、レコード｛ｒ１，ｒ４｝の「ｎａｍｅ」フィールドの値のバリエーション（「ｙｏｓｈｉ」及び「ｈｉｄｅ」）をハッシュ値とするハッシュ表３１Ｂが生成される。同様に、関数ｆ（Ｌ１，１９９４）の出力先には、レコード｛ｒ５｝の「ｎａｍｅ」フィールドの値のバリエーション（「ｎａｏ」）をハッシュ値とするハッシュ表３１Ｃが生成される。ハッシュ表３１Ａのハッシュ値が「ｎｏｂｕ」であるノード要素３４Ｆには、レコード｛ｒ２，ｒ３｝のうち、「ｎａｍｅ」フィールドの値が「ｎｏｂｕ」であるレコード｛ｒ２｝を返す関数ｆ（Ｌ２，ｎｏｂｕ）が対応付けられる。同様に、ハッシュ値「ｙａｓｕ」のノード要素３４Ｇには、レコード｛ｒ３｝を返す関数ｆ（Ｌ２，ｙａｓｕ）が対応付けられる。他のハッシュ値のノード要素３４Ｈ、３４Ｉ、３４Ｊについても同様である。
【００６７】
図１３の例では、条件式Ｌ２が条件Ｌに含まれる最後の条件式であるため、条件式Ｌ２に対応するノード（ハッシュ表３１Ａ、３１Ｂ、３１Ｃ）の各々はリーフノードとなる。
【００６８】
次に、図１４及び図１５を参照して、検索処理について説明する。ここでは、図１１に示す条件パラメータテーブルＭが入力されるものとする。図１４及び図１５に示す検索処理は、条件パラメータテーブルＭに含まれるレコード毎に実行される。以下では、検索対象ノードの階層に対応する条件式に、条件パラメータテーブルＭのレコードが示すパラメータを適用した条件を「対象条件式」という。
【００６９】
ステップＳ５１で、検索部１６が、所定の記憶領域から検索用データ構造２０を読み出し、例えば図１３に示すようなツリー構造を展開し、ルートノード３６を検索対象ノードに設定する。
【００７０】
次に、ステップＳ５２で、検索部１６が、検索対象ノードがリーフノードか否かを判定する。検索対象ノードがリーフノードではない場合には、処理はステップＳ５３へ移行する。
【００７１】
ステップＳ５３では、検索部１６が、検索対象ノードが、等式条件式に対応して生成されたハッシュ表３１か否かを判定する。検索対象ノードがハッシュ表３１の場合には、処理はステップＳ５４へ移行し、ハッシュ表３１ではない場合には、処理はステップＳ６０へ移行する。
【００７２】
ステップＳ５４では、検索部１６が、ハッシュ表３１に対象条件式を満たすハッシュ値が存在するか否かを判定する。該当のハッシュ値が存在する場合には、処理はステップＳ５５へ移行し、存在しない場合には、処理はステップＳ５６へ移行する。
【００７３】
ステップＳ５５では、検索部１６が、上記ステップＳ５４で特定されたハッシュ値に接続された子ノードを次の検索対象ノードに設定し、処理はステップＳ５２に戻る。
【００７４】
ステップＳ５６では、検索部１６が、検索対象ノードからルートノード３６まで順次親ノードを辿る途中に、未処理のリスト要素を含むリスト３２が存在するか否かを判定する。該当のリスト３２が存在する場合には、処理はステップＳ５７へ移行し、検索部１６が、該当のリスト３２を検索対象ノードに設定し、処理はステップＳ６２へ移行する。該当のリスト３２が存在しない場合には、処理はステップＳ５８へ移行する。
【００７５】
ステップＳ５８では、検索部１６が、検索対象ノードからルートノード３６まで順次親ノードを辿る途中に、未処理の配列要素を含む配列３３が存在するか否かを判定する。該当の配列３３が存在する場合には、処理はステップＳ５９へ移行し、検索部１６が、該当の配列３３を検索対象ノードに設定し、処理はステップＳ６６へ移行する。該当の配列３３が存在しない場合には、処理はステップＳ６８へ移行する。
【００７６】
ステップＳ６０では、検索部１６が、検索対象ノードが、不等式条件式に対応して生成されたリスト３２か否かを判定する。検索対象ノードがリスト３２の場合には、処理はステップＳ６１へ移行し、リスト３２ではない場合には、処理はステップＳ６５へ移行する。
【００７７】
ステップＳ６１では、検索部１６が、検索対象ノードであるリスト３２に未処理のリスト要素が存在するか否かを判定する。未処理のリスト要素が存在する場合には、処理はステップＳ６２へ移行し、存在しない場合には、処理はステップＳ５６へ移行する。
【００７８】
ステップＳ６２では、検索部１６が、検索対象ノードであるリスト３２の先頭から順に未処理のリスト要素を１つ選択する。次に、ステップＳ６３で、検索部１６が、選択したリスト要素が示す値が対象条件式を満たすか否かを判定する。対象条件式を満たす場合は、処理はステップＳ６４へ移行し、対象条件式を満たさない場合には、該当のリスト３２における残りのリスト要素も処理済みとしたうえで、処理はステップＳ５６へ移行する。
【００７９】
ステップＳ６４では、検索部１６が、選択したリスト要素に接続された子ノードを次の検索対象ノードに設定し、処理はステップＳ５２に戻る。
【００８０】
ステップＳ６０で否定判定となりステップＳ６５へ移行する場合には、検索対象ノードは、ＯＲ条件式に対応する配列３３である。そこで、ステップＳ６５で、検索部１６が、検索対象ノードである配列３３に、未処理の配列要素が存在するか否かを判定する。未処理の配列要素が存在する場合には、処理はステップＳ６６へ移行し、存在しない場合には、処理はステップＳ５６へ移行する。
【００８１】
ステップＳ６６では、検索部１６が、検索対象ノードである配列３３の先頭から順に未処理の配列要素を１つ選択し、処理はステップＳ６４へ移行し、検索部１６が、選択した配列要素に接続された子ノードを次の検索対象ノードに設定する。そして、処理はステップＳ５２に戻る。
【００８２】
ステップＳ５２で、検索部１６が、検索対象ノードがリーフノードであると判定した場合には、処理はステップＳ６７へ移行する。ステップＳ６７では、検索部１６が、検索対象ノードに含まれるノード要素３４のうち、対象条件式を満たす値を示すノード要素３４に対応付けられた関数ｆ（Ｌｉ，ｘ）が返すレコードを、検索結果として出力し、検索処理は終了する。
【００８３】
一方、ステップＳ６８では、検索部１６が、条件パラメータテーブルＭのレコードをパラメータとして適用した条件Ｌを満たすレコードが検索対象テーブルＲに存在しないことを示す「該当レコード無し」を出力し、検索処理は終了する。
【００８４】
図１３に示す検索用データ構造２０を用いて、図１１に示す条件パラメータテーブルＭのレコードが示すパラメータを適用した条件で、図１０に示す検索対象テーブルＲを検索する例について説明する。
【００８５】
まず、条件式Ｌ０に対応するリスト３２Ａの先頭のノード要素３４Ａの値「１９８０」は、Ｍ．Ｙ＝１９９３以下であり、条件式Ｌ０を満たすため、次に、ノード要素３４Ａの子ノードを検索する。ノード要素３４Ａの子ノードである、条件式Ｌ１に対応するリスト３２Ｂの先頭のノード要素３４Ｃの値「１９８９」は、Ｍ．Ｙ＝１９９３以下であり、条件式Ｌ１を満たさない。そこで、親ノードを辿っていくと、リスト３２Ａに未処理のノード要素３４Ｂが存在するため、リスト３２Ａに戻る。リスト３２Ａのノード要素３４Ｂの値「１９９０」は、Ｍ．Ｙ＝１９９３以下であり、条件式Ｌ０を満たすため、次に、ノード要素３４Ｂの子ノードを検索する。ノード要素３４Ｂの子ノードである、条件式Ｌ１に対応するリスト３２Ｃの先頭のノード要素３４Ｄの値「１９９９」は、Ｍ．Ｙ＝１９９３以上であり、条件式Ｌ１を満たすため、次に、ノード要素３４Ｄの子ノードを検索する。ノード要素３４Ｄの子ノードである、条件式Ｌ２に対応するハッシュ表３１Ｂには、Ｍ．ｎａｍｅ＝ｙｏｓｈｉを満たすハッシュ値を示すノード要素３４Ｈが存在するため、条件式Ｌ２を満たす。また、ノード要素３４Ｈはリーフノードであるため、ノード要素３４Ｈに対応付けられた関数ｆ（Ｌ２，ｙｏｓｈｉ）が返すレコード｛ｒ１｝が検索結果として出力される。
【００８６】
以上説明したように、第１実施形態に係る情報処理装置１０によれば、レコード集合から条件を満たすレコードを検索するための条件に含まれる複数の条件式の各々の種類を判定する。そして、情報処理装置１０は、各条件式に応じた階層毎に、親ノードから出力されるレコード集合に含まれ、かつ条件式に関連するフィールドの値の各々を、条件式の種類に応じた形式の要素とするノードを含むツリー構造の検索用データ構造を生成する。この検索用データ構造では、ノードに含まれる要素が示すフィールドの値を有するレコードを、その要素に接続する子ノードに出力する。これにより、データ検索を効率化するための事前処理を提供することができる。
【００８７】
また、レコード集合から条件を満たすレコードを検索する際に、この検索用データ構造を用いることで、レコード集合の全てのレコードと条件とを比較するのではなく、条件を満たす値を有するレコードを各条件式の種類に応じて効率的に絞り込む。そのため、複数の条件式を含む条件であっても、効率的に検索を行うことができる。また、条件式は同一だが条件式のパラメータが異なる条件で繰り返し検索を行う場合でも、条件式が同じである限り、同一の検索用データ構造を検索に用いることができるため、検索の高速化を図ることができる。
【００８８】
＜第２実施形態＞
次に、第２実施形態について説明する。
【００８９】
第２実施形態に係る情報処理装置２１０は、図１に示すように、判定部２１２が第１実施形態に係る情報処理装置１０と異なるだけであるため、以下では、判定部２１２について説明する。
【００９０】
判定部２１２は、条件Ｌを分割した各条件式が、生成部１４において、等式条件式、不等式条件式、ＯＲ条件式の順に処理されるように、各条件式に条件式番号を付与する。上記の条件Ｌ「Ｒ．ＳＹ  ≦  Ｍ．Ｙ  ＡＮＤ  Ｍ．Ｙ  ≦  Ｒ．ＥＹ  ＡＮＤ  Ｍ．ｎａｍｅ  ＝  Ｒ．ｎａｍｅ」の場合、判定部２１２は、以下のように条件Ｌを各条件式に分割すると共に、各条件式に条件式番号を付与する。
【００９１】
Ｌ０：  Ｍ．ｎａｍｅ  ＝  Ｒ．ｎａｍｅ
Ｌ１：  Ｒ．ＳＹ  ≦  Ｍ．Ｙ
Ｌ２：  Ｍ．Ｙ  ≦  Ｒ．ＥＹ
【００９２】
情報処理装置２１０は、例えば図８に示すコンピュータ４０で実現することができる。コンピュータ４０の記憶部４３には、コンピュータ４０を、情報処理装置２１０として機能させるための情報処理プログラム２５０が記憶される。情報処理プログラム２５０は、判定プロセス２５２と、生成プロセス５４と、検索プロセス５６とを有する。
【００９３】
ＣＰＵ４１は、情報処理プログラム２５０を記憶部４３から読み出してメモリ４２に展開し、情報処理プログラム２５０が有するプロセスを順次実行する。ＣＰＵ４１は、判定プロセス２５２を実行することで、図１に示す判定部２１２として動作する。他のプロセスについては、第１実施形態の情報処理プログラム５０と同様である。これにより、情報処理プログラム２５０を実行したコンピュータ４０が、情報処理装置２１０として機能することになる。
【００９４】
第２実施形態に係る情報処理装置２１０の作用については、生成処理（図９）のステップＳ１１に、分割した条件式を上記のように並び替えて条件式番号を付与する処理が加わるだけであるため、説明を省略する。
【００９５】
第２実施形態に係る情報処理装置２１０によれば、生成部１４において、等式条件式に対応するノード、不等式条件式に対応するノード、ＯＲ条件式に対応するノードの順に、ツリー構造において階層が上位となるように検索用データ構造２０が生成される。図１６に、第１実施形態と同じ検索対象テーブルＲ及び条件Ｌについて、各条件式の並べ替えを行った上で生成した検索用データ構造２０の一例を示す。この場合、ルートノード３６→値「ｙｏｓｈｉ」のノード→値「１９９０」のノード→値「１９９９」のノードを辿って、レコード｛ｒ１｝が検出結果として出力される。このように、図１３に示すように条件式の並べ替えを行っていない場合に比べ、ツリー構造における上位のノードを処理した段階、すなわち、検索の初期の段階で、条件を満たすレコードの候補を少数に絞り込むことができる。結果として、データ検索の高速化をより促進することができる。
【００９６】
なお、上記各実施形態では、条件式の種類に応じたノードとして、ハッシュ表、リスト、又は配列を生成する場合について説明したが、これに限定されず、例えば、ビットマップをノードとして生成してもよい。この場合、条件式に関連するフィールドの値のバリエーション毎にビットマップを生成し、ビットマップの各ビットと、親ノードに対応付けられた関数ｆ（Ｌｉ−１，ｘ）が返すレコードの各々とを対応付ける。そして、レコードが条件式を満たす値を有する場合には、対応するビットに１を設定し、レコードが条件式を満たす値を有さない場合には、対応するビットに０を設定する。そして、検索の際には、条件式に関連するフィールドに対応するビットマップから、１が設定されているビットに対応するレコードを特定すればよい。
【００９７】
また、不等式条件に対応するノードとして、二分探索用のテーブルを生成してもよい。例えば、図１７の上図に示すように、検索対象テーブルＲが、何らかの分類（ｃｌａｓｓ）毎の下限値（ＬＢ）と上限値（ＵＢ）とを定めたレコード集合の場合で、条件パラメータテーブルＭの各レコードがどの分類に属するかを特定する場合を考える。この場合、条件式Ｌｉ「Ｒ．ＬＢ  ≦  Ｍ．Ｃ  ＡＮＤ  Ｍ．Ｃ  ＜  Ｒ．ＵＢ」とし、上記実施形態のように、ＡＮＤで分割することなく、１つの条件式として扱う。そして、生成部１４は、二分探索用のテーブルとして、図１７の下図に示すように、検索対象テーブルＲと同様のフィールドと、「探索用フラグ」とを含み、いずれかのフィールドの値が昇順又は降順となるようにレコードを並べたテーブルを生成する。「探索用フラグ」としては、二分探索の探索範囲を示す「ｍｉｎ」及び「ｍａｘ」と、探索範囲の真ん中に位置するレコードを示す「ｍｉｄ」が設定される。
【００９８】
検索時には、最初に、図１７の下図に示すように、昇順又は降順で並べたフィールドの最小値を持つレコードに「ｍｉｎ」を設定し、最大値を持つレコードに「ｍａｘ」を設定し、その真ん中に位置するレコードに「ｍｉｄ」を設定する。そして、通常の二分探索の手法を用いて探索範囲を狭めながら、「ｍｉｄ」が設定されたレコードと、Ｍ．Ｃの値とを比較して、条件式を満たすレコードを探索する。このように、検索対象テーブルＲ及び条件Ｌが特定の形の場合には、二分探索用テーブルを生成することで、条件式をまとめて効率的な検索を行うことができる。
【００９９】
また、上記各実施形態では、情報処理プログラム５０が記憶部４３に予め記憶（インストール）されている態様を説明したが、これに限定されない。開示の技術に係るプログラムは、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＵＳＢメモリ等の記憶媒体に記憶された形態で提供することも可能である。
【０１００】
以上の各実施形態に関し、更に以下の付記を開示する。
【０１０１】
（付記１）
複数のフィールドを含むデータの集合から少なくとも１つのフィールドの値を指定する条件を満たすデータを検索するための前記条件に含まれる複数の条件式の各々の種類を判定する判定部と、
各条件式に応じた階層毎に、前記データの集合のうちの所定のデータに含まれ、かつ該条件式に関連するフィールドの値の各々を、前記判定部により判定された該条件式の種類に応じた形式の要素とするノードを含むツリー構造であって、該ノードに含まれる要素が示す前記フィールドの値を有するデータを、該要素に接続する子ノードにおける前記所定のデータとするデータ構造を生成する生成部と、
を含む情報処理装置。
【０１０２】
（付記２）
前記判定部は、前記条件式の種類として、等号を用いた条件式、不等号を用いた条件式、及び論理和を用いた条件式のいずれかを判定し、
前記生成部は、
前記条件式の種類が前記等号を用いた条件式の場合、該条件式に関連するフィールドの値をハッシュ値とするハッシュ表をノードとして生成し、
前記条件式の種類が前記不等号を用いた条件式の場合、該条件式に関連するフィールドの値を昇順又は降順で整列したリストをノードとして生成し、
前記条件式の種類が前記論理和を用いた条件式の場合、論理和で接続される部分条件式の各々に対応する配列要素を含む配列をノードとして生成すると共に、前記部分条件式の各々の種類に応じた形式のノードを、前記配列要素の子ノードとして生成する
付記１に記載の情報処理装置。
【０１０３】
（付記３）
前記生成部は、前記等号を用いた条件式に対応するノード、前記不等号を用いた条件式に対応するノード、前記論理和を用いた条件式に対応するノードの順に、前記ツリー構造において階層が上位となるように前記データ構造を生成する付記２に記載の情報処理装置。
【０１０４】
（付記４）
前記生成部により生成されたデータ構造のルートノードから順に、各条件式のパラメータが指定された条件を満たすノードを辿ることにより、前記条件を満たすデータを検索する検索部を含み、
前記検索部は、
検索対象のノードが前記等号を用いた条件式に対応するノードの場合、前記ハッシュ表に含まれる前記条件を満たすハッシュ値から接続される子ノードを辿り、
検索対象のノードが前記不等号を用いた条件式に対応するノードの場合、前記リストの先頭又は末尾の値から順に前記条件を満たすか否かを判定し、該条件を満たすリスト要素から接続される子ノードを辿り、
検索対象のノードが前記論理和を用いた条件式に対応するノードの場合、前記配列の配列要素のそれぞれに接続される子ノードを順次辿る
付記２又は付記３に記載の情報処理装置。
【０１０５】
（付記５）
前記生成部は、異なる要素間で、該要素が示す前記フィールドの値を有するデータが共通する場合には、前記異なる要素の各々を同一の子ノードに接続する付記１〜付記４のいずれか１項に記載の情報処理装置。
【０１０６】
（付記６）
前記判定部は、否定を含む条件式を、ド・モルガンの法則及び逆の演算子への変換により否定を除去した条件式に変換する付記１〜付記５のいずれか１項に記載の情報処理装置。
【０１０７】
（付記７）
前記判定部は、論理積を含む条件を該論理積で区切られる部分毎に分割し、分割した各部分を前記条件式の各々とする付記１〜付記６のいずれか１項に記載の情報処理装置。
【０１０８】
（付記８）
複数のフィールドを含むデータの集合から少なくとも１つのフィールドの値を指定する条件を満たすデータを検索するための前記条件に含まれる複数の条件式の各々の種類を判定し、
各条件式に応じた階層毎に、前記データの集合のうちの所定のデータに含まれ、かつ該条件式に関連するフィールドの値の各々を、判定した該条件式の種類に応じた形式の要素とするノードを含むツリー構造であって、該ノードに含まれる要素が示す前記フィールドの値を有するデータを、該要素に接続する子ノードにおける前記所定のデータとするデータ構造を生成する
ことを含む処理をコンピュータが実行する情報処理方法。
【０１０９】
（付記９）
前記条件式の種類として、等号を用いた条件式、不等号を用いた条件式、及び論理和を用いた条件式のいずれかを判定し、
前記データ構造を生成する際、
前記条件式の種類が前記等号を用いた条件式の場合、該条件式に関連するフィールドの値をハッシュ値とするハッシュ表をノードとして生成し、
前記条件式の種類が前記不等号を用いた条件式の場合、該条件式に関連するフィールドの値を昇順又は降順で整列したリストをノードとして生成し、
前記条件式の種類が前記論理和を用いた条件式の場合、論理和で接続される部分条件式の各々に対応する配列要素を含む配列をノードとして生成すると共に、前記部分条件式の各々の種類に応じた形式のノードを、前記配列要素の子ノードとして生成する
付記８に記載の情報処理方法。
【０１１０】
（付記１０）
前記等号を用いた条件式に対応するノード、前記不等号を用いた条件式に対応するノード、前記論理和を用いた条件式に対応するノードの順に、前記ツリー構造において階層が上位となるように前記データ構造を生成する付記９に記載の情報処理方法。
【０１１１】
（付記１１）
生成したデータ構造のルートノードから順に、各条件式のパラメータが指定された条件を満たすノードを辿ることにより、前記条件を満たすデータを検索することをさらに含む処理を前記コンピュータが実行する情報処理方法であって、
前記条件を満たすデータを検索する際、
検索対象のノードが前記等号を用いた条件式に対応するノードの場合、前記ハッシュ表に含まれる前記条件を満たすハッシュ値から接続される子ノードを辿り、
検索対象のノードが前記不等号を用いた条件式に対応するノードの場合、前記リストの先頭又は末尾の値から順に前記条件を満たすか否かを判定し、該条件を満たすリスト要素から接続される子ノードを辿り、
検索対象のノードが前記論理和を用いた条件式に対応するノードの場合、前記配列の配列要素のそれぞれに接続される子ノードを順次辿る
付記９又は付記１０に記載の情報処理方法。
【０１１２】
（付記１２）
前記データ構造を生成する際、異なる要素間で、該要素が示す前記フィールドの値を有するデータが共通する場合には、前記異なる要素の各々を同一の子ノードに接続する付記８〜付記１１のいずれか１項に記載の情報処理方法。
【０１１３】
（付記１３）
前記条件式の種類を判定する際、否定を含む条件式を、ド・モルガンの法則及び逆の演算子への変換により否定を除去した条件式に変換して、変換した条件式の種類を判定する付記８〜付記１２のいずれか１項に記載の情報処理方法。
【０１１４】
（付記１４）
前記条件式の種類を判定する際、論理積を含む条件を該論理積で区切られる部分毎に分割し、分割した各部分を前記条件式の各々とする付記８〜付記１３のいずれか１項に記載の情報処理方法。
【０１１５】
（付記１５）
複数のフィールドを含むデータの集合から少なくとも１つのフィールドの値を指定する条件を満たすデータを検索するための前記条件に含まれる複数の条件式の各々の種類を判定し、
各条件式に応じた階層毎に、前記データの集合のうちの所定のデータに含まれ、かつ該条件式に関連するフィールドの値の各々を、判定した該条件式の種類に応じた形式の要素とするノードを含むツリー構造であって、該ノードに含まれる要素が示す前記フィールドの値を有するデータを、該要素に接続する子ノードにおける前記所定のデータとするデータ構造を生成する
ことを含む処理をコンピュータに実行させる情報処理プログラム。
【０１１６】
（付記１６）
前記条件式の種類として、等号を用いた条件式、不等号を用いた条件式、及び論理和を用いた条件式のいずれかを判定し、
前記データ構造を生成する際、
前記条件式の種類が前記等号を用いた条件式の場合、該条件式に関連するフィールドの値をハッシュ値とするハッシュ表をノードとして生成し、
前記条件式の種類が前記不等号を用いた条件式の場合、該条件式に関連するフィールドの値を昇順又は降順で整列したリストをノードとして生成し、
前記条件式の種類が前記論理和を用いた条件式の場合、論理和で接続される部分条件式の各々に対応する配列要素を含む配列をノードとして生成すると共に、前記部分条件式の各々の種類に応じた形式のノードを、前記配列要素の子ノードとして生成する
付記１５に記載の情報処理プログラム。
【０１１７】
（付記１７）
前記等号を用いた条件式に対応するノード、前記不等号を用いた条件式に対応するノード、前記論理和を用いた条件式に対応するノードの順に、前記ツリー構造において階層が上位となるように前記データ構造を生成する付記１６に記載の情報処理プログラム。
【０１１８】
（付記１８）
生成したデータ構造のルートノードから順に、各条件式のパラメータが指定された条件を満たすノードを辿ることにより、前記条件を満たすデータを検索することをさらに含む処理を前記コンピュータに実行させる情報処理プログラムであって、
前記条件を満たすデータを検索する際、
検索対象のノードが前記等号を用いた条件式に対応するノードの場合、前記ハッシュ表に含まれる前記条件を満たすハッシュ値から接続される子ノードを辿り、
検索対象のノードが前記不等号を用いた条件式に対応するノードの場合、前記リストの先頭又は末尾の値から順に前記条件を満たすか否かを判定し、該条件を満たすリスト要素から接続される子ノードを辿り、
検索対象のノードが前記論理和を用いた条件式に対応するノードの場合、前記配列の配列要素のそれぞれに接続される子ノードを順次辿る
付記１６又は付記１７に記載の情報処理プログラム。
【０１１９】
（付記１９）
前記データ構造を生成する際、異なる要素間で、該要素が示す前記フィールドの値を有するデータが共通する場合には、前記異なる要素の各々を同一の子ノードに接続する付記１５〜付記１８のいずれか１項に記載の情報処理プログラム。
【０１２０】
（付記２０）
前記条件式の種類を判定する際、否定を含む条件式を、ド・モルガンの法則及び逆の演算子への変換により否定を除去した条件式に変換して、変換した条件式の種類を判定する付記１５〜付記１９のいずれか１項に記載の情報処理プログラム。
【符号の説明】
【０１２１】
１０、２１０  情報処理装置
１２、２１２  判定部
１４   生成部
１６   検索部
２０   検索用データ構造
３１   ハッシュ表
３２   リスト
３３   配列
３４   ノード要素
３５   関数ｆ’テーブル
３６   ルートノード
４０   コンピュータ
４１   ＣＰＵ
４２   メモリ
４３   記憶部
４９   記憶媒体
５０、２５０  情報処理プログラム
Ｒ     検索対象テーブル
Ｍ     条件パラメータテーブル
【図１】
2018200623.tif 000003
【図２】
2018200623.tif 000004
【図３】
2018200623.tif 000005
【図４】
2018200623.tif 000006
【図５】
2018200623.tif 000007
【図６】
2018200623.tif 000008
【図７】
2018200623.tif 000009
【図８】
2018200623.tif 000010
【図９】
2018200623.tif 000011
【図１０】
2018200623.tif 000012
【図１１】
2018200623.tif 000013
【図１２】
2018200623.tif 000014
【図１３】
2018200623.tif 000015
【図１４】
2018200623.tif 000016
【図１５】
2018200623.tif 000017
【図１６】
2018200623.tif 000018
【図１７】
2018200623.tif 000019