(57)【特許請求の範囲】
【請求項１】
コンピュータに、
通信部を介して、１つの命題、もしくは１又は複数の命題同士の論理積である命題群による論理和となる論理式を受け付ける受付部、
前記論理式に含まれる前記１つの命題および前記命題群のそれぞれと、前記１つの命題か、前記命題群の前記１又は複数の命題のいずれかを共通に含む他の命題群を生成する生成部、
記憶装置からデータを読み出す読出部、
前記データに対して前記論理式の判定処理を行なうとともに、前記他の命題群に含まれる各命題が満たされない旨の判定結果が得られた場合に、前記論理式が満たされないと判定する判定部、及び、
前記判定結果に基づいて応答情報を生成し、前記通信部を介して送信する通知部、
としての処理を実行させることを特徴とする判定プログラム。
【請求項２】
前記コンピュータに、さらに、前記判定部として、
前記他の命題群に含まれる各命題が満たされない旨の判定結果が得られた場合に、前記論理式の判定処理を終了する、
処理を実行させることを特徴とする請求項１に記載の判定プログラム。
【請求項３】
前記複数の命題群のそれぞれは、１または複数の命題を含み、論理和演算子を含まない、
ことを特徴とする請求項１または２に記載の判定プログラム。
【請求項４】
前記コンピュータに、さらに、前記判定部として、
前記論理式の判定処理の結果が、前記他の命題群に含まれる各命題が満たされない旨の判定結果よりも先に得られた場合に、前記他の命題群に含まれる各命題が満たされるか否かを判定する処理を終了する、
処理を実行させることを特徴とする請求項１〜３のいずれか１項に記載の判定プログラ
ム。
【請求項５】
前記コンピュータに、さらに、前記判定部として、
前記論理式に含まれる各命題の判定処理と、前記論理式に含まれる各命題の判定処理の処理結果に基づいて前記論理式が満たされるか否かを判定する判定処理と、前記論理式に含まれる各命題の判定処理の処理結果に基づいて前記他の命題群に含まれる各命題が満たされるか否かを判定する判定処理と、を並列で実行させる、
処理を実行させることを特徴とする請求項１〜４のいずれか１項に記載の判定プログラム。
【請求項６】
前記コンピュータに、さらに、前記判定部として、
前記論理式に含まれるある命題の判定処理と、前記論理式に含まれる他の命題の判定処理と、を並列で実行させる、
処理を実行させることを特徴とする請求項５に記載の判定プログラム。
【請求項７】
コンピュータに、
通信部を介して、１つの命題、もしくは１又は複数の命題同士の論理積である命題群による論理和となる論理式を受け付ける受付部、
前記論理式に含まれる前記１つの命題および前記命題群のそれぞれと、前記１つの命題か、前記命題群の前記１又は複数の命題のいずれかを共通に含む他の命題群を生成する生成部、
記憶装置からデータを読み出す読出部、
前記データに対して前記論理式の判定処理を行なうとともに、前記他の命題群に含まれる各命題が満たされない旨の判定結果が得られた場合に、前記論理式が満たされないと判定する判定部、及び、
前記判定結果に基づいて応答情報を生成し、前記通信部を介して送信する通知部、
としての処理を実行させることを特徴とする判定方法。
【請求項８】
１つの命題、もしくは１又は複数の命題同士の論理積である命題群による論理和となる論理式を受け付けた場合に、前記論理式に含まれる前記１つの命題および前記命題群のそれぞれと、前記１つの命題か、前記命題群の前記１又は複数の命題のいずれかを共通に含む他の命題群を生成する生成部と、
前記論理式の判定処理を行なうとともに、前記他の命題群に含まれる各命題が満たされない旨の判定結果が得られた場合に、前記論理式が満たされないと判定する判定制御部と、
を含むことを特徴とする判定装置。
【請求項９】
判定対象のデータを記憶する記憶装置と、
論理式を受け付けた場合に、前記判定対象のデータについて前記論理式の判定処理を行なう判定装置と、を含む判定システムであって、
前記判定装置は、
受け付けた前記論理式が、１つの命題、もしくは１又は複数の命題同士の論理積である命題群による論理和となる場合に、前記論理式に含まれる前記１つの命題および前記命題群のそれぞれと、前記１つの命題か、前記命題群の前記１又は複数の命題のいずれかを共通に含む他の命題群を生成する生成部と、
前記論理式の判定処理を行なうとともに、前記他の命題群に含まれる各命題が満たされない旨の判定結果が得られた場合に、前記論理式が満たされないと判定する判定制御部と、
を含むことを特徴とする判定システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、論理式の判定技術に関する。
【背景技術】
【０００２】
１または複数の命題の論理和や論理積を含む論理式の判定処理を、二分決定図（ＢＤＤ：Ｂｉｎａｒｙ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）を用いて行なう方法がある。その方法において、論理式を受け付けた場合に、受け付けた論理式に基づいてＢＤＤが形成される。ＢＤＤは、論理式に含まれる各命題の判定順序が定められたものであり、各命題の判定結果が「真」である場合と「偽」である場合とのそれぞれについて、次の判定対象の命題もしくは論理式全体の判定結果（「真」または「偽」）が定められている。【０００３】
例えば、判定処理の計算コストが小さい命題を先に判定させるＢＤＤを用いて、論理式全体の判定処理のコストが小さくなる確率を上げる方法がある（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００９−２１１３１２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、ＢＤＤを用いた判定処理においては、論理式全体の判定結果が得られるまでに、論理式に含まれるほとんどの命題の判定を経由するケースがある。【０００６】
本発明の一側面において、論理式全体の判定処理の速度劣化が生じにくくすることを目的とする。
【課題を解決するための手段】
【０００７】
１態様において、判定プログラムは、コンピュータに、１つの命題、もしくは１又は複数の命題同士の論理積である命題群による論理和となる論理式を受け付けた場合に、前記論理式に含まれる前記１つの命題および前記命題群のそれぞれと、前記１つの命題か、前記命題群の前記１又は複数の命題のいずれかを共通に含む他の命題群を生成し、前記論理式の判定処理を行なうとともに、前記他の命題群に含まれる各命題が満たされない旨の判定結果が得られた場合に、前記論理式が満たされないと判定する、処理を実行させる。【０００８】
１態様において、判定装置は、１つの命題、もしくは１又は複数の命題同士の論理積となる命題群による論理和である論理式を受け付けた場合に、前記論理式に含まれる前記１つの命題および前記命題群のそれぞれと、前記１つの命題か、前記命題群の前記１又は複数の命題のいずれかを共通に含む他の命題群を生成する生成部と、前記論理式の判定処理を行なうとともに、前記他の命題群に含まれる各命題が満たされない旨の判定結果が得られた場合に、前記論理式が満たされないと判定する判定制御部と、を含む。【０００９】
１態様において、コンピュータに、１つの命題、もしくは１又は複数の命題同士の論理積となる命題群による論理和である論理式を受け付けた場合に、前記論理式に含まれる前記１つの命題および前記命題群のそれぞれと、前記１つの命題か、前記命題群の前記１又は複数の命題のいずれかを共通に含む他の命題群を生成し、前記論理式の判定処理を行なうとともに、前記他の命題群に含まれる各命題が満たされない旨の判定結果が得られた場合に、前記論理式が満たされないと判定する、ことを実行させる判定方法が実施される。【００１０】
１態様において、判定システムは、判定対象のデータを記憶する記憶装置と、論理式を受け付けた場合に、前記判定対象のデータについて前記論理式の判定処理を行なう判定装置と、を含む判定システムであって、前記判定装置は、受け付けた前記論理式が、１つの命題、もしくは１又は複数の命題同士の論理積である命題群による論理和となる場合に、前記論理式に含まれる前記１つの命題および前記命題群のそれぞれと、前記１つの命題か、前記命題群の前記１又は複数の命題のいずれかを共通に含む他の命題群を生成する生成部と、前記論理式の判定処理を行なうとともに、前記他の命題群に含まれる各命題が満たされない旨の判定結果が得られた場合に、前記論理式が満たされないと判定する判定制御部と、を含むことを特徴とする判定システム。
【発明の効果】
【００１１】
本発明の一側面において、論理式全体の判定処理の速度劣化が生じにくくすることができる。
【図面の簡単な説明】
【００１２】
【図１】図１は、二分決定図の例を示す。
【図２】図２は、本実施形態におけるシステム構成例を示す。
【図３】図３は、図２に示すシステムのコンピュータ１の機能構成例を示す。
【図４】図４は、コンピュータ１に含まれる判定部１１４の機能構成例を示す。
【図５】図５は、本実施形態における他のシステム構成例を示す。
【図６】図６は、図５に示すシステムのコンピュータ１Ａ１の機能構成例を示す。
【図７】図７は、図５に示すシステムのコンピュータ１Ｂ１の機能構成例を示す。
【図８】図８は、コンピュータ１のハードウェア構成例を示す。
【図９】図９は、コンピュータ１のソフトウェア構成例を示す。
【図１０】図１０は、管理テーブルＴ１の例を示す。
【図１１】図１１Ａ〜Ｃは、それぞれ論理判定テーブルＴ２の例を示す。
【図１２】図１２Ａ及びＢは、状態情報の例を示す。
【図１３】図１３は、判定情報の例を示す。
【図１４】図１４は、応答処理の流れを示すフローチャート例を示す。
【図１５】図１５は、論理判定テーブルＴ２ａに対応する有向非循環グラフの例を示す。
【図１６】図１６は、論理判定テーブルＴ２ａに対応する有向非循環グラフの例を示す。
【図１７】図１７は、生成部１１２の処理のフローチャートの例を示す。
【図１８】図１８は、図１７のＳ２０１の処理のフローチャートの例を示す。
【図１９】図１９は、論理式の構文解析結果の例を示す。
【図２０】図２０Ａ〜Ｆは、図１５の有向非循環グラフの生成過程を示す。
【図２１】図２１は、生成部１１２の処理のフローチャートの例を示す。
【図２２】図２２は、生成部１１２の処理のフローチャートの例を示す。
【図２３】図２３は、論理判定部１１４１の処理のフローチャートの例を示す。
【発明を実施するための形態】
【００１３】
論理式に基づいて二分決定図（ＢＤＤ）を作成し、作成したＢＤＤを用いて論理式を満たすか否かを判定する方法がある。図１は、ＢＤＤの例を示す。図１に示すＢＤＤは、論理式（Ａ  ａｎｄ  （Ｂ  ｏｒ  Ｃ）  ａｎｄ  Ｄ）  ｏｒ  Ｅ  ｏｒ  （Ｆ  ａｎｄ  Ｇ）に基づくものである。この論理式は単なる例示であり、当然のことであるが、以後論理式（Ａ  ａｎｄ  （Ｂ  ｏｒ  Ｃ）  ａｎｄ  Ｄ）  ｏｒ  Ｅ  ｏｒ  （Ｆ  ａｎｄ  Ｇ）を用いて説明する事項は、この論理式に限定される事項ではなく、他の論理式にも成り立つ事項である。論理式中のＡは、例えば、「判定対象のデータはＡというデータを含む」という命題を意味する。命題Ａは、判定対象のデータがＡというデータを含む場合に、「真」であると判定される。判定対象のデータは、例えば、文字列、画像、音声などの形式のデータである。Ｂ，Ｃ，Ｄ，Ｅ，ＦおよびＧについても同様である。「ａｎｄ」は論理積の演算子であり、「ｏｒ」は論理和の演算子である。ＢＤＤを用いた判定処理おいては、命題の判定結果が「真」である場合には実線で図示される矢印の先の命題の判定に移行し、命題の判定結果が「偽」である場合には点線で図示される矢印の先の命題の判定に移行する。例えば、図１に示すＢＤＤでは、まず、命題Ａを満たすか否か（「真」か「偽」か）の判定が行われる。その後、命題Ａの判定が「真」である場合には命題Ｂの判定が行われ、命題Ａの判定が「偽」である場合には命題Ｅの判定が行われる。ＢＤＤは、さらに「真（Ｔ：Ｔｒｕｅ）」と「偽（Ｆ：Ｆａlｓｅ）」という情報を有する。ＢＤＤに基づく順序で各命題の判定が行われ、図１のＢＤＤにおいては、例えば、命題Ｅの判定結果が「真」である場合に、データが論理式全体を満たす（「真（Ｔ：Ｔｒｕｅ）」である）と判断される。
【００１４】
図１のＢＤＤを用いて論理式の判定処理を行なった場合に、判定結果が必要な命題の数が判定対象のデータによって異なることがある。例えば、Ａ，Ｃ，Ｆを含むレコードに対しては、命題Ａ（真）→命題Ｂ（偽）→命題Ｃ（真）→命題Ｄ（偽）→命題Ｅ（偽）→命題Ｆ（真）→命題Ｇ（偽）→「偽」の順で判定処理が行なわれ、判定結果が必要な命題の数が７となる。また、Ａ〜Ｇのいずれも含まないレコードに対しては、命題Ａ（偽）→命題Ｅ（偽）→命題Ｆ（偽）→「偽」の順で判定処理が行なわれ、判定結果が必要な命題の数が３となる。
【００１５】
上記の論理式は、３つの論理式が論理和演算子で接続されており、そのいずれが満たされても論理式は満たされる。この形式を加法標準形といい、論理和演算子、論理積演算子及び論理否定演算子を含む論理式は、二重否定の除去、ド・モルガンの法則、分配法則といった論理的に等価な変換を行う法則により、加法標準形に変換可能である。３つの論理式とは、（Ａ  ａｎｄ  （Ｂ  ｏｒ  Ｃ）  ａｎｄ  Ｄ）およびＥおよび（Ｆ  ａｎｄ  Ｇ）である。逆に、３つの論理式それぞれについて一部でも満たされない場合には、上記の論理式は満たされない。例えば、Ｄ（（Ａ  ａｎｄ  （Ｂ  ｏｒ  Ｃ）  ａｎｄ  Ｄ）の一部）と、Ｅと、Ｆ（（Ｆ  ａｎｄ  Ｇ）の一部）と、を満たさない場合には、上記の論理式は満たされない。
【００１６】
そこで、例えば、命題Ｄ、Ｅ及びＦのいずれも満たさないか（「偽」であるか）の判定処理により、Ｄ、Ｅ及びＦのいずれも「偽」であるという判定結果が、図１のＢＤＤに基づく判定処理の結果よりも先に得られた場合には、図１のＢＤＤに基づく判定処理は終了させてもよい。命題Ｄ、Ｅ及びＦのいずれも「偽」であることが明らかになれば、別途行なわれている論理式の判定処理の結果を得るまでもなく、論理式全体について「偽」であることが明らかなためである。上述したＡ，Ｃ，Ｆを含むレコードに対して図１のＢＤＤに基づいて判定処理を行なうと、判定結果が必要な命題の数が７であるのに対し、Ｄ、Ｅ及びＦの３つの命題についての判定結果により結果を得ることができる。
【００１７】
論理式に含まれる各命題の判定処理に要する時間は、互いに異なることがある。命題によって判定対象のデータと照合させるデータ（命題Ａであれば「Ａ」というデータ）のサイズが異なれば、照合に要する演算量も異なる。また、例えば、ある命題の判定処理においてデータ読み出しなどにエラーが発生した場合など、各命題の内容と関係なく、処理に時間がかかることもある。
【００１８】
上述の通り、例えば、Ａ，Ｃ，Ｆを含むレコードに対しては、命題Ａ（真）→命題Ｂ（偽）→命題Ｃ（真）→命題Ｄ（偽）→命題Ｅ（偽）→命題Ｆ（真）→命題Ｇ（偽）→「偽」の順で、７つの命題に対して判定処理が行なわれる。例えば、上記の論理式に含まれる命題Ｃの処理に多くの時間を要したとすると、命題Ｃの判定処理の遅れにより、Ａ，Ｃ，Ｆを含むレコードに対して図１のＢＤＤに基づいて行なわれる検索処理全体が遅れてしまう。しかしながら、命題Ｄ、Ｅ及びＦの判定処理の結果が「偽」であることが先に明らかになる場合には、命題Ｃの判定処理が遅れたとしても、論理式全体についての処理時間が長くなることが抑制される。
【００１９】
上記のような論理式の判定処理は、例えば、検索処理に用いられる。検索条件を論理式で表し、データベースから順次読み出されるデータに対して論理式を満たすか否かの判定処理を行ない、論理式を満たすデータを検索条件に合致するデータとして返すなどにより、検索処理が行なわれる。
【００２０】
図２は、本実施形態におけるシステム構成例を示す。図２に示すシステムは、コンピュータ１、記憶装置２、ネットワーク３、コンピュータ４、ネットワーク５を含む。コンピュータ１は、例えば、記憶装置２に記憶されたファイルの格納処理、管理、検索処理（判定処理を含む）を行なう。記憶装置２は、記録媒体２ａを含み、コンピュータ１の制御に応じて記録媒体２ａへのデータの書き込み・読み出しを行なう。コンピュータ４は、ネットワーク３を介してコンピュータ１と通信する。コンピュータ４は、例えば、コンピュータ１に検索要求を送信し、コンピュータ１から検索結果を受信する。また、例えば、コンピュータ４は、コンピュータ１にファイルをアップロードする。コンピュータ４は図２に示す台数に限定されるものではない。ネットワーク３は、例えば、インターネットやイントラネットなどのネットワークである。コンピュータ１と記憶装置２とは、ネットワーク５を介して通信する。ネットワーク５はインターネットやイントラネットでもよいし、ＳＡＮ（Ｓｔｏｒａｇｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）など、ファイバチャネルなどを用いたネットワークでもよい。コンピュータ１は、例えば、コンピュータ４から検索要求を受けた場合に、記憶装置２に記憶されたファイルを検索し、検索結果をコンピュータ４に送信する。また、例えば、コンピュータ１は、コンピュータ４からファイルのアップロード要求を受けた場合に、記憶装置２に含まれる記録媒体２ａにファイルを書込む。
【００２１】
図３は、図２に示すシステム構成に含まれるコンピュータ１の機能構成例を示す。コンピュータ１は、処理部１１、記憶部１２、通信部１３及び通信部１４を含む。処理部１１は、受付部１１１、生成部１１２、読出部１１３、判定部１１４及び通知部１１５を含む。処理部１１は、記憶装置２への検索処理、ファイル管理処理、ファイル格納処理に関する演算と、記憶部１２、通信部１３及び通信部１４の制御を行なう。記憶部１２は、処理部１１のワークエリアとしてデータを記憶する。通信部１３は、ネットワーク３を介したコンピュータ４との通信処理を行なう。通信部１４は、ネットワーク５を介した記憶装置２との通信処理を行なう。
【００２２】
受付部１１１は、例えば、コンピュータ４から通信部１３を介して検索要求を受け付け、受け付けた検索要求について、記憶部１２に記憶された管理テーブルＴ１（図１０参照）に情報を書込む。生成部１１２は、受付部１１１が受け付けた検索要求に含まれる検索条件の論理式に基づいて、論理式の判定処理に用いる論理判定テーブルＴ２（図１１Ａ〜Ｃ参照）を生成する。
【００２３】
生成部１１２が生成する論理判定テーブルＴ２は、判定部１１４（または、後述の論理判定部１１４１）の論理判定において用いられる。論理判定テーブルＴ２は、命題及びその命題の判定結果の組と、他の命題と、を関連付けた情報を含む。例えば、命題及びその判定結果の１つの組に対して、１または複数の命題、もしくは論理式全体の判定結果を示す情報が関連付けられる。命題同士がどのように関連付けられるかは、生成部１１２により、受付部１１１が受け付けた論理式に基づいて決められる。論理判定テーブルＴ２の生成方法の詳細については後述する。例えば、論理式（Ａａｎｄ（ＢｏｒＣ）ａｎｄＤ）ｏｒＥｏｒ（ＦａｎｄＧ）について作成した論理判定テーブルＴ２には、図１に示される全ての命題同士の関連性が含まれてよい。例えば、論理判定テーブルＴ２に含まれる各レコードは、命題Ａ（真）→命題Ｂ、命題Ｂ（偽）→命題Ｃ・・・などの関連性を示す情報を含む。
【００２４】
また、論理式が命題群（１または複数の命題を含む）の論理和となる（前述の通り、論理式は加法標準形に変換可能される）場合に、論理判定テーブルＴ２により、少なくとも、論理和演算子で接続された複数の命題群のそれぞれと少なくとも１つの命題が共通する命題群に含まれる命題同士の関連性が示される。すなわち、生成部１１２は、受付部１１１が受け付けた論理式内で、論理和演算子で互いに接続された１つの命題または命題群のそれぞれから少なくとも命題を１つ選択し、選択された命題群に含まれる命題同士の関連性（判定結果と次に判定する命題との関係）を示す情報を生成する。ちなみに、この場合に、論理式内で論理和演算子により接続される命題群は、１又は複数の命題同士が論理積演算子で接続されたものである。上記のように論理和演算子により接続される各命題群から命題を選択する場合に、生成部１１２は、互いに論理積演算子で接続された１又は複数の命題のうちのいずれかを選択する。生成部１１２により選択された命題群は、例えば、論理式（Ａａｎｄ（ＢｏｒＣ）ａｎｄＤ）ｏｒＥｏｒ（ＦａｎｄＧ）については、命題Ｄ、命題Ｅおよび命題Ｆを含む。１つの命題、もしくは１又は複数の命題同士の論理積である命題群による論理和である論理式である論理式（Ａａｎｄ（ＢｏｒＣ）ａｎｄＤ）ｏｒＥｏｒ（ＦａｎｄＧ）に対して、命題Ｄ、命題Ｅおよび命題Ｆを含む命題群は、論理式（Ａａｎｄ（ＢｏｒＣ）ａｎｄＤ）ｏｒＥｏｒ（ＦａｎｄＧ）に含まれる１つの命題および命題群のそれぞれと、１つの命題か、命題群に含まれる１又は複数の命題のいずれかを共通に含んでいる。その場合、作成される論理判定テーブルＴ２は、例えば、命題Ｄ（偽）→命題Ｅ、命題Ｅ（偽）→命題Ｆ、命題Ｆ（偽）→「偽」といった関連性を示す。
【００２５】
読出部１１３は、生成部１１２が論理判定テーブルＴ２を生成すると、通信部１４を介して記憶装置２に記憶されたデータを読み出す。判定部１１４は、読出部１１３が読み出したデータに対して、論理判定テーブルＴ２に基づいて論理式の判定処理を行なう。判定部１１４は、判定処理の結果、論理式を満たすデータが存在した場合に、そのデータを管理テーブルＴ１に書き込む。判定部１１４は、判定処理の結果、１つも論理式を満たすデータが存在しなかった場合には、データが存在しなかった旨を管理テーブルＴ１に書き込む。通知部１１５は、判定部１１４が判定処理を終えた場合に、管理テーブルＴ１に書き込まれた情報に基づいて応答情報を生成し、生成した応答情報をコンピュータ４宛に送信させる制御を通信部１３に対して行なう。
【００２６】
図４は、コンピュータ１に含まれる判定部１１４の機能構成例を示す。判定部１１４は、例えば、論理判定部１１４１、命題判定部１１４２および記憶部１１４３を含む。論理判定部１１４１は、生成部１１２が生成した論理判定テーブルＴ２と、命題判定部１１４２の判定結果に応じて、読出部１１３が読み出したデータに対して、論理式全体の判定を行なう。命題判定部１１４２は、論理式に含まれる各命題についての判定処理を、読出部１１３が読み出したデータに対して行なう。記憶部１１４３は、命題判定部１１４２が各命題について判定した結果を記憶する。記憶部１１４３が記憶する判定情報は、命題判定部１１４２によって更新される。また、記憶部１１４３は、論理判定部１１４１による判定状況を示す状態情報を記憶する。記憶部１１４３が記憶する状態情報は、論理判定部１１４１によって更新される。状態情報は、例えば、図１２に示す２種類の情報を含む。論理判定部１１４１および命題判定部１１４２の処理は、例えば、それぞれで並列に行なわれる。さらに、例えば、論理判定部１１４１および命題判定部１１４２は、それぞれの処理を１または複数に並列処理で実行する。
【００２７】
論理判定部１１４１の処理について、さらに説明する。論理判定部１１４１は、例えば、論理判定テーブルＴ２を参照して、処理対象の命題を決定する。次いで、論理判定部１１４１は、例えば、処理対象の命題について命題判定部１１４２が判定した結果を読み出し、論理判定テーブルＴ２において、処理対象の命題とその命題についての判定結果との組と関連付けられた命題をさらに読み出し、次の処理対象の命題とする。命題判定部１１４２による判定結果が得られない場合には、論理判定部１１４１は、例えば、処理対象の命題を識別する情報を保持したまま、判定結果が得られるまで待機する。論理判定テーブルＴ２から繰り返し情報を読み出し、論理判定テーブルＴ２から論理式全体の判定結果を示す情報が読み出された場合に、論理判定部１１４１は、読出部１１３が読み出したデータに対する処理を終了する。論理式全体の判定結果が真である場合には、管理テーブルＴ１に判定対象のデータを示す情報を格納する。
【００２８】
論理判定部１１４１は、さらに、上記の処理とともに、論理判定テーブルＴ２を参照して、生成部１１２により選択された命題群について命題群について関連性を辿る処理を行なう。例えば、論理式（Ａａｎｄ（ＢｏｒＣ）ａｎｄＤ）ｏｒＥｏｒ（ＦａｎｄＧ）においては、命題Ｄ（偽）→命題Ｅ（偽）→命題Ｆ（偽）→「偽」などの順序で判定結果を辿る。命題Ｅが真であるなど、判定結果を辿れなくなった場合には、論理判定部１１４１はこの処理を終了する。
【００２９】
論理判定部１１４１は、例えば、図１１Ｂの論理判定テーブルＴ２ｂに示される関連性を辿ることにより図１に示すＢＤＤと同じ手順で命題の判定結果を参照してもよい。しかしながら、その場合は、論理判定部１１４１は、他方で、図１１Ｃの論理判定テーブルＴ２ｃを用いて、論理和演算子で接続された複数の命題群のそれぞれと少なくとも１つの命題が共通する命題群について関連性を辿る処理を行なう。他にも、論理判定部１１４１は、例えば、図１１Ａの論理判定テーブルＴ２ａを用いて、一方で命題の判定結果が真である場合の命題同士の関連性を辿るとともに、他方で命題の判定結果が偽である場合の命題同士の関連性を辿ることとしてもよい。論理判定テーブルＴ２ａ〜Ｔ２ｃについては後述する。
【００３０】
図３及び４に示す機能構成のコンピュータにより処理が行なわれると、ＢＤＤを用いた場合には、論理式に含まれるほとんどの命題の判定を経由してしまうケースにおいても、論理式全体の判定結果を遅れにくくすることができる。例えば、論理判定部１１４１は、少なくとも、論理和演算子で接続された複数の命題群のそれぞれと少なくとも１つの命題が共通する命題群の命題同士の関連性を辿ることとなる。その場合、複数の命題群のそれぞれと少なくとも１つの命題が共通する命題群のいずれも偽であれば、論理式全体が偽であることが明らかであり、ＢＤＤを用いた判定処理が遅れたとしても、論理式全体の判定処理を終了することができる。
【００３１】
図５は、本実施形態における他のシステム構成例を示す。図２に示したシステムは、図５に示すように構成されてもよい。図５のシステムにおいては、図２に示すコンピュータ１の機能を複数のコンピュータにより実現する。例えば、図２のコンピュータ１に代えて、コンピュータ１Ａ１，１Ａ２、コンピュータ１Ｂ１〜１Ｂ４、ロードバランサ６及びネットワーク７がシステムに含まれる。コンピュータ１Ａ１，１Ａ２は、検索要求の受け付けと検索結果の応答を行ない、コンピュータ１Ｂ１〜１Ｂ４を用いて検索処理を実行させる制御を行なう。コンピュータ１Ｂ１〜１Ｂ４は、コンピュータ１Ａ１，１Ａ２の制御に応じて検索要求に含まれる論理式の判定処理を行なう。コンピュータ１Ａ１〜１Ａ２は２台設けられ、コンピュータ１Ｂ１〜１Ｂ４は４台設けられているが、台数はこれに限定されるものではない。例えば、検索要求の数が増大する場合には、それに応じてコンピュータ１Ａ１，１Ａ２の台数を増やしてもよい。その場合には、論理式の判定処理の数も増大するので、コンピュータ１Ｂ１〜１Ｂ４の台数を増やしてもよい。さらに、検索処理の性能要件に応じてコンピュータ１Ｂ１〜１Ｂ４の台数を増やしてもよい。１つの検索要求に対して、複数のコンピュータで検索対象のデータの範囲を分担して処理を行なうことで、より短い時間で検索処理を行なうことができるためである。ロードバランサ６は、例えば、コンピュータ４から送られてきた検索要求をコンピュータ１Ａ１，１Ａ２のいずれかに振り分ける処理を行なう。ネットワーク７は、例えば、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）などのネットワークであり、コンピュータ１Ａ１〜１Ａ２及びコンピュータ１Ｂ１〜１Ｂ４を接続する。
【００３２】
図６は、図５に示すシステム構成におけるコンピュータ１Ａ１の機能構成例を示す。コンピュータ１Ａ１は、処理部１１Ａ、記憶部１２Ａ、通信部１３及び通信部１５を含む。処理部１１Ａは、受付部１１１及び通知部１１５を含む。受付部１１１は、例えば、コンピュータ４からロードバランサ６及び通信部１３を介して検索要求を受け付けた場合に、コンピュータ１Ｂ１〜１Ｂ４のそれぞれに、判定処理対象のデータ範囲の指定と、受け付けた検索要求に基づく判定処理の要求と、を通信部１５に送信させる。通信部１５は、ネットワーク７を介した通信処理を行なう。通知部１１５は、コンピュータ１Ｂ１〜１Ｂ４から通信部１５を介して判定処理の結果を受け取った場合に、受け取った結果に基づく応答をコンピュータ４に対して行なう。記憶部１２Ａは、処理部１１Ａの処理に用いるデータを記憶するワークエリアであり、例えば、各コンピュータ１Ｂ１〜１Ｂ４に割り当てるデータ範囲などを記憶する。
【００３３】
図７は、図５に示す他のシステム構成におけるコンピュータ１Ｂ１の機能構成例を示す。コンピュータ１Ｂ１は、処理部１１Ｂ、記憶部１２Ｂ、通信部１４及び通信部１６を含む。処理部１１Ｂは、生成部１１２、読出部１１３及び判定部１１４を含む。通信部１６は、ネットワーク７を介した通信処理を行なう。生成部１１２は、通信部１６を介してコンピュータ１Ａ１またはコンピュータ１Ａ２から受信した判定処理の要求に基づいて、論理判定テーブルＴ２を生成する。読出部１１３は、通信部１６を介してコンピュータ１Ａ１またはコンピュータ１Ａ２から受信したデータ範囲の指定に応じて読出し処理を行なう。判定部１１４は、読出部１１３が読み出したデータに対して、論理判定テーブルＴ２に基づいて判定処理を行ない、判定処理の結果を、判定処理の要求元のコンピュータに送信する。判定処理の結果は、例えば、論理式を満たすデータ（またはデータを識別する情報、データの所在を示す情報など）もしくは論理式を満たすデータが存在しない旨を示すデータである。
【００３４】
図８は、コンピュータ１のハードウェア構成例を示す。コンピュータ１は、例えば、プロセッサ３０１、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）３０２、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）３０３、ドライブ装置３０４、記録媒体３０５、通信インターフェース（Ｉ／Ｆ）３０６、入力インターフェース（Ｉ／Ｆ）３０７、出力インターフェース（Ｉ／Ｆ）３０８、ＳＡＮインターフェース（Ｉ／Ｆ）３０９、などを含む。それぞれのハードウェアはバス３１０を介して接続している。通信Ｉ／Ｆ３０６はネットワーク３を介した通信の制御を行なう。ＳＡＮ  Ｉ／Ｆ３０９は、ネットワーク５を介した通信の制御を行なう。入力インターフェース３０７は、入力装置３１１と接続されており、入力装置３１１から受信した入力信号をプロセッサ３０１に伝達する。出力インターフェース３０８は、出力装置３１２と接続されており、出力装置３１２に、プロセッサ３０１の指示に応じた出力を実行させる。
【００３５】
ＲＡＭ３０２は読み書き可能なメモリ装置であって、例えば、ＳＲＡＭ（Ｓｔａｔｉｃ  ＲＡＭ）やＤＲＡＭ（Ｄｙｎａｍｉｃ  ＲＡＭ）などの半導体メモリ、またはＲＡＭ以外にもフラッシュメモリなどが用いられる。ＲＯＭ３０３は、ＰＲＯＭ（Ｐｒｏｇｒａｍｍａｂｌｅ  ＲＯＭ）なども含む。ドライブ装置３０４は、記録媒体３０５に記録された情報の読み出しか書き込みかの少なくともいずれか一方を行なう装置である。記録媒体３０５は、ドライブ装置３０４によって書き込まれた情報を記憶する。記録媒体３０５は、例えば、ハードディスク、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）、ブルーレイディスクなどの記録媒体である。また、例えば、コンピュータ１は、複数種類の記録媒体それぞれについて、ドライブ装置３０４及び記録媒体３０５を設ける。
【００３６】
入力装置３１１は、操作に応じて入力信号を送信する装置である。入力装置３１１は、例えば、キーボードやコンピュータ１の本体に取り付けられたボタンなどのキー装置や、マウスやタッチパネルなどのポインティングデバイスである。出力装置３１２は、コンピュータ１の制御に応じて情報を出力する装置である。出力装置３１２は、例えば、ディスプレイなどの画像出力装置（表示デバイス）や、スピーカーなどの音声出力装置などである。また、例えば、タッチスクリーンなどの入出力装置が、入力装置３１１及び出力装置３１２として用いられる。
【００３７】
プロセッサ３０１は、ＲＯＭ３０３や記録媒体３０５に記憶されたプログラムをＲＡＭ３０２に読み出し、読み出されたプログラムの手順に従って処理部１１の処理を行なう。その際に、ＲＡＭ３０２はプロセッサのワークエリアとして用いられ、記憶部１２の機能が実現される。プロセッサ３０１が読み出すプログラムについては、図９を用いて説明する。
【００３８】
図９は、コンピュータ１のソフトウェア構成例を示す。コンピュータ１において、図８に示すハードウェア群２４の制御を行なうＯＳ２３（オペレーティングシステム）が動作する。ＯＳ２３に従った手順でプロセッサ３０１が動作して、ハードウェア２４の制御・管理が行なわれることにより、アプリケーションプログラムやミドルウェアによる処理がハードウェア２４により実行される。さらに、コンピュータ１において、例えば、検索プログラム２１やＳＡＮ制御プログラム２２などのミドルウェアが、ＲＡＭ３０２に読み出されてプロセッサ３０１により実行される。プロセッサ３０１がＳＡＮ制御プログラム２２に基づく処理を行なうことにより、通信部１４の処理を行なうように、ＨＢＡ（Ｈｏｓｔ  Ｂｕｓ  Ａｄａｐｔｏｒ）などのＳＡＮ  Ｉ／Ｆ３０９が制御される。また、プロセッサ３０１が検索プログラム２１に基づく処理を行なうことにより、（それらの処理をＯＳ２３に基づいてハードウェア２４を制御して）処理部１１（１１Ａおよび１１Ｂも含む）、記憶部１２（１２Ａおよび１２Ｂも含む）、通信部１３、通信部１４、通信部１５、通信部１６の機能が実現される。図９に示すソフトウェア構成例において、検索プログラム２１およびＳＡＮ制御プログラム２２はミドルウェアと説明しているが、ＯＳ２３に一機能として含まれても良いし、ＯＳ２３上で動作するアプリケーションプログラムであってもよい。
【００３９】
受付部１１１の機能は、例えば、プロセッサ３０１が検索プログラム２１に基づき、ＲＡＭ３０２などにデータを書き込むことなどにより実現される。生成部１１２の機能は、例えば、プロセッサ３０１が検索プログラム２１に基づき、ＲＡＭ３０２に記憶されたデータを用いて演算を行ない、演算結果をＲＡＭ３０２に書き込むなどにより実現される。読出部１１３の機能は、例えば、プロセッサ３０１が検索プログラム２１に基づき、ＳＡＮ  Ｉ／Ｆ３０９を制御し、取得したデータをＲＡＭ３０２に書き込むなどにより実現される。判定部１１４の機能は、例えば、プロセッサ３０１が検索プログラム２１に基づき、ＲＡＭ３０２に格納されたデータを用いて演算を行ない、演算結果をＲＡＭ３０２もしくはプロセッサ３０１が備えるレジスタに格納するなどにより実現される。さらに詳述すると、論理判定部１１４１の機能は、例えば、プロセッサ３０１が検索プログラム２１に基づき、ＲＡＭ３０２に格納されたデータを読み出して演算を行ない、レジスタやＲＡＭ３０２などに演算結果を保持させるなどにより実現される。論理判定部１１４２の機能は、例えば、プロセッサ３０１が検索プログラム２１に基づき、ＲＡＭ３０２に格納されたデータを読み出して演算を行ない、レジスタなどに演算結果を保持させるなどにより実現される。記憶部１１４３の機能は、例えば、プロセッサ３０１が備えるレジスタなどにより実現される。通知部１１５の機能は、例えば、プロセッサ３０１が検索プログラム２１に基づき、ＲＡＭ３０２に格納されたデータを送信させるように通信Ｉ／Ｆ３０６を制御するなどにより実現される。
【００４０】
図１０は、管理テーブルＴ１を示す。管理テーブルＴ１は、検索要求ごとにレコード設け、例えば、受信日時、検索要求元、検索条件式、照合テーブルおよび検索結果の項目を有する。受付部１１１の処理により、受信日時の項目に、例えば、検索要求を受付部１１１が受信した日時を示す情報が格納される。受信日時の項目に格納される情報は、検索要求を識別する情報として用いられてもよい。受付部１１１の処理により、検索要求元の項目に、例えば、検索要求を送信したコンピュータを識別する情報が格納される。検索要求を送信したコンピュータを識別する情報は、例えば、検索要求を送信したコンピュータのＩＰアドレスである。例えば、通知部１１５は、管理テーブルＴ１の検索要求元の項目に格納された情報を、検索処理の結果（応答）の送信先に用いる。受付部１１１の処理により、照合テーブルの項目に、例えば、検索要求に基づいて生成された照合テーブルへのポインタが格納される。生成部１１２が照合テーブルを生成した際にポインタを格納し、判定部１１４は管理テーブルのポインタに基づいて照合テーブルから情報を読み出す。受付部１１１の処理により、検索結果の項目に、例えば、検索要求に応じて行なわれた処理の結果を示す情報が格納される。処理の結果を示す情報は、例えば、検索条件の論理式を満たすデータ、論理式を満たすデータを識別する情報または所在を示す情報、もしくは論理式を満たすデータが存在しない旨を示す情報などである。管理テーブルＴ１が、図６に示すコンピュータ１Ａ１の記憶部１２Ａに記憶される場合には、例えば、各コンピュータ１Ｂ１〜１Ｂ４に判定処理を要求したデータの範囲を示す情報を、さらに管理テーブルＴ１に含めてもよい。さらに、例えば、処理の結果を示す情報を、コンピュータ１Ｂ１〜１Ｂ４のそれぞれについて格納するように項目を設けてもよい。
【００４１】
図１１は論理判定テーブルの例を示す。図１１Ａは、論理判定テーブルＴ２ａを示す。論理判定テーブルＴ２ａは、論理判定における要素ごとにレコードを有する。論理判定における要素とは、例えば、命題や、論理判定の初期状態を示す情報である。論理判定テーブルＴ２ａは、例えば、論理判定の初期状態を２つ（［真］始点および［偽］始点）含む。各レコードは、要素、［真］子要素および［偽］子要素の項目を有する。各レコードにおいて、要素の項目には、要素を識別する情報が格納される。［真］子要素の項目には、次に「真」であるか判定される要素を識別する情報が格納される。また、［偽］子要素の項目には、次に「偽」であるか判定される要素を識別する情報が格納される。［真］子要素および［偽］子要素の項目のそれぞれには、１または複数の要素を示す情報が格納される。また、［真］子要素および［偽］子要素の項目には、次に判定される要素以外にも、判定処理の終了を示す情報（［真］終点または［偽］終点）が含まれる。
【００４２】
論理判定部１１４１が論理判定テーブルＴ２ａに基づいて命題間の関連性を辿る例について説明する。論理判定部１１４１は、［真］始点から辿る際には［真］子要素のみを参照し、［偽］始点から辿る際には［偽］子要素のみを参照する。［真］始点から辿る際には、論理判定部１１４１は、Ａ，Ｅ及びＦのいずれかを選択し、選択した命題についての判定結果を読み出す。論理判定部１１４１は、複数の子要素がある場合にいずれかを選択することとしなくとも、複数の子要素それぞれについて関連性を辿る処理を並列で行なうようにしてもよい。Ａを選択した場合に、Ａの判定結果が真であると、論理判定部１１４１は、さらに、ＢまたはＣを選択する。論理判定部１１４１がＢを選択した場合にＢの判定結果が偽であると、論理判定部１１４１は、［真］始点から辿る処理を中止する。もしくは［真］始点から辿る処理において、選択されなかった命題（Ｅ，Ｆ及びＣ）から処理を再開することとしても良い。［偽］始点から辿る際には、論理判定部１１４１は、Ａ，Ｂ及びＤのいずれかを選択し、選択した命題についての判定結果を読み出す。Ｄを選択した場合に、Ｄの判定結果が偽であると、論理判定部１１４１は、さらにＥを選択する。論理判定部１１４１がＥを選択した場合にＥの判定結果が真であると、論理判定部１１４１は、［偽］始点から辿る処理を中止する。もしくは［偽］始点から辿る処理において、選択されなかった命題（Ｅ，Ｆ及びＣ）から処理を再開することとしても良い。
【００４３】
図１１Ｂは論理判定テーブルＴ２ｂを示し、図１１Ｃは論理判定テーブルＴ２ｃを示す。論理判定テーブルＴ２ｂ及び論理判定テーブルＴ２ｃは、論理判定における要素ごとにレコードを有する。論理判定における要素とは、例えば、命題や、論理判定の初期状態（始点）を示す情報である。各レコードは、要素、判定結果および子要素の項目を有する。各レコードにおいて、要素の項目には、要素を識別する情報が格納される。判定結果の項目には、その要素についての判定結果が格納される。また、子要素の項目には、次に判定結果を参照される要素を識別する情報が格納される。子要素の項目には、１つの要素を示す情報、または論理式全体の判定結果を示す情報が格納される。
【００４４】
図１１Ｂ及びＣを用いて、図４に示す論理判定部１１４１が行なう処理の例を説明する。論理判定部１１４１は、図１１Ｂの論理判定テーブルＴ２ｂの始点と図１１Ｃの論理判定テーブルＴ２ｃの始点から関連性を辿る。論理判定部１１４１は、それぞれの始点から、要素と要素の判定結果（真または偽）に応じて次に参照する子要素を決定する。例えば、論理判定部１１４１は、論理判定テーブルＴ２ｂの始点の情報を参照してＡを選択する。Ａを選択すると、論理判定部１１４１は、命題判定部１１４２のＡについての判定結果を参照する。論理判定部１１４１は、Ａの判定結果が真である場合には、Ｂを選択する。論理判定部１１４１がＢを選択し、Ｂの判定結果が偽であると、論理判定部１１４１はＣを選択する。Ｃ以降も論理判定部１１４１は、命題判定部１１４２の判定結果に基づいて論理判定テーブルＴ２ｂを辿り、論理式全体の判定を行なう。その一方で、論理判定部１１４１は、論理判定テーブルＴ２ｃを始点から辿る。始点の子要素のＤを選択すると、論理判定部１１４１は、命題判定部１１４２がＤについて偽と判定していれば、Ｄの子要素のＥを選択する。さらに、命題判定部１１４２がＥについて偽と判定していれば、論理判定部１１４１は、例えば、Ｅの子要素のＦを選択する。論理判定部１１４１は、Ｆを選択し、命題判定部１１４２がＦについて偽と判定していれば、論理式全体が偽であると判定する。例えば、Ｄが真であるなどと判定された場合には関連性を辿る処理を停止する。
【００４５】
図１２は、状態情報の例を示す。図１２Ａ及びＢは、論理判定部１１４１が命題判定部１１４２の判定結果を参照中である命題（要素）を示している。図１２Ａ及びＢに示されるテーブルＴ３ａ及びＴ３ｂは、記憶部１１４３に保持される。図１１Ａを用いて関連性を辿る場合も、図１１Ｂ及びＣを用いて関連性を辿る場合も、論理判定部１１４１は、図１２に示す２以上の情報を記憶部１１４３に保持して処理を行なう。図１１Ａを用いて関連性を辿る場合には、例えば、図１２Ａに示すテーブルＴ３ａに［真］始点から辿って得られた要素が保持され、図１２Ｂに示すテーブルＴ３ｂに［偽］始点から辿って得られた要素が保持される。また、図１１Ｂ及びＣを用いて関連性を辿る場合には、例えば、図１２Ａに示すテーブルＴ３ａに図１１Ｂを用いて辿って得られた結果が保持され、図１２Ｂに示すテーブルＴ３ｂに図１１Ｃを用いて辿って得られた結果が保持される。また、論理判定部１１４１は、論理判定テーブルＴ２を参照して子要素を選択した場合に、テーブルＴ３に保持される情報を、選択した子要素を識別する情報に更新する。
【００４６】
図１３は、判定情報の例を示す。記憶部１１４３は、判定情報を含むテーブルＴ４を保持する。テーブルＴ４は、論理式に含まれる各命題と、各命題についての判定結果を格納する領域を備える。命題判定部１１４２は、判定対象のデータが命題を満たすか否かを判定し、判定結果をテーブルＴ４に格納する。
【００４７】
以下に、論理式判定処理の全体の流れを説明する。図１４は、コンピュータ１による検索要求への応答処理の流れを示すフローチャートである。コンピュータ１が検索プログラム２１に基づく処理を開始し（Ｓ１００）、受付部１１１が検索要求をコンピュータ４から受け付ける（Ｓ１０１）と、生成部１１２は、論理判定テーブルＴ２を生成する（Ｓ１０２）。読出部１１３が、受付部１１１が受け付けた検索要求に含まれる論理式の判定対象のデータを、記憶装置から読み出す。読出部１１３は、判定対象のデータがあるか否かを判定する（Ｓ１０３）。判定対象のデータがある場合には、読出部１１３は、判定対象のデータを取り出す（Ｓ１０４）。判定部１１４に含まれる命題判定部１１４２は、論理式に含まれる各命題を、Ｓ１０４で取りだした判定対象のデータが満たすか否かを判定する（Ｓ１０５）。Ｓ１０６では、論理判定部１１４１が、Ｓ１０５の結果と、Ｓ１０２で生成した論理判定テーブルとを参照して、判定対象のデータが論理式全体を満たすか否かを判定する（Ｓ１０６）。Ｓ１０６の処理を終え、論理式が真である場合（Ｓ１０７：Ｙｅｓ）には、判定部１１４が、判定対象のデータを管理テーブルＴ１に書き込み（Ｓ１０８）、次にＳ１０３の処理が行なわれる。論理式が偽である場合（Ｓ１０７：Ｎｏ）には、次にＳ１０３の処理が行なわれる。一方で、読出部１１３が、Ｓ１０３で、判定対象のデータがないと判断した場合（Ｓ１０３：Ｎｏ）には、論理式が真であるデータがあったか否かを判定し（Ｓ１０９）、真のデータがあった場合（Ｓ１０９：Ｙｅｓ）には、次にＳ１０１の処理が行なわれる。論理式が真であるデータが無かった場合には、管理テーブルＴ１に、論理式を満たすデータがなかった旨の情報が書込まれ（Ｓ１１０）、次にＳ１０１の処理が行なわれる。
【００４８】
以下に、生成部１１２が論理判定テーブルを生成する処理について、さらに説明する。
【００４９】
まず、図１１Ａに示す論理判定テーブルＴ２ａを生成する処理について説明する。論理判定テーブルＴ２ａは、図１５及び図１６に示す有向非循環グラフに対応するテーブルである。
【００５０】
図１５及び図１６に、論理判定テーブルＴ２ａに対応する有向非循環グラフを示す。図１５に示すグラフは、図１１Ａにおける［真］始点から関連性を辿る経路に対応する。図１１Ａにおいて、［真］始点の次には［真］子要素としてＡ，Ｅ及びＦが対応付けられており、図１５においても［真］始点の配下にＡ，Ｅ及びＦが配置されている。さらに、図１１Ａでは、Ａには［真］子要素としてＢ及びＣが対応付けられており、図１５でもＡの配下にＢ及びＣが配置されている。一方、図１６に示すグラフは、図１１Ａにおける［偽］始点から関連性を辿る経路に対応する。図１１Ａにおいて、［偽］始点の次には［偽］子要素としてＡ，Ｂ及びＤが対応付けられており、図１６においても［偽］始点の配下にＡ，Ｂ及びＤが配置されている。さらに、図１１Ａでは、Ｄには［偽］子要素としてＥが対応付けられており、図１６でもＤの配下にＥが配置されている。論理判定部１１４１による判定では、図１５及び図１６に図示される有向非循環グラフは、各ノードの条件を充足した（Ｓａｔｉｓｆｉｅｄ）場合にのみ次ノードに移行させる構造になっている。そのため、この有向非循環グラフの図について『ＳＡＴ  ｇｒａｐｈ（Ｓａｔｉｓｆｉａｂｉｌｉｔｙ  ｇｒａｐｈ）』などの呼称が用いられると分かりやすい。
【００５１】
図１７に、論理判定テーブルＴ２ａを生成する処理のフローチャートを示す。生成部１１２は、受付部１１１が検索要求を受け付けて管理テーブルＴ１に情報を格納する（Ｓ２００）と、論理判定テーブルＴ２ａ生成の前処理を行なう（Ｓ２０１）。
【００５２】
図１８は、論理判定処理の前処理のフローチャートである。前処理が開始される（Ｓ３００）と、生成部１１２は、論理式の構文解析処理を行なう（Ｓ３０１）。例えば、論理式（Ａ  ａｎｄ  （Ｂ  ｏｒ  Ｃ）  ａｎｄ  Ｄ）  ｏｒ  Ｅ  ｏｒ  （Ｆ  ａｎｄ  Ｇ）が構文解析されて、図１９の有向非循環グラフのデータが得られる。生成部１１２は、図１９に示す有向非循環グラフデータが得られると、記憶部１２に有向非循環グラフデータを格納する。図１９の有向非循環グラフにおいて、葉部分のデータは命題であり、節部分のデータは論理演算子であり、有向非循環グラフ全体で命題間の接続関係を示す。
【００５３】
図１９の有向非循環グラフデータは、例えば、論理式の始めから順に論理式に含まれる要素で有向非循環グラフデータを生成していくことで生成される。生成部１１２は、例えば、論理式（Ａ  ａｎｄ  （Ｂ  ｏｒ  Ｃ）  ａｎｄ  Ｄ）  ｏｒ  Ｅ  ｏｒ  （Ｆ  ａｎｄ  Ｇ）においては、Ａおよび（Ｂ  ｏｒ  Ｃ）がａｎｄ演算子で接続されている部分について、有向非循環グラフデータを生成する。生成部１１２は、Ａについてのデータ構造体、Ｂ  ｏｒ  Ｃについてのデータ構造体、ａｎｄについてのデータ構造体を生成する。Ａについてのデータ構造体は、その構造体自身を示すポインタ情報（図１９ではポインタ１）および命題Ａを示す情報を含む。Ｂ  ｏｒ  Ｃについてのデータ構造体は、その構造体自身を示すポインタ情報（図１９ではポインタ２）および部分的な論理式Ｂ  ｏｒ  Ｃを示す情報を含む。ａｎｄ演算子についてのデータ構造体は、その構造体自身を示すポインタ情報（図１９ではポインタ３）、演算子ａｎｄを示す情報、Ａについてのデータ構造体のポインタ情報（ポインタ１）およびＢｏｒＣについてのデータ構造体のポインタ情報（ポインタ２）を含む。
【００５４】
データ構造体が生成されたＢ  ｏｒ  Ｃは、論理式であるため、さらに構文解析される。生成部１１２は、論理式Ｂ  ｏｒ  Ｃに基づき、Ｂについてのデータ構造体、Ｃについてのデータ構造体、ｏｒについてのデータ構造体を生成する。Ｂについてのデータ構造体は、その構造体自身を示すポインタ情報（図１９ではポインタ４）および命題Ｂを示す情報を含む。Ｃについてのデータ構造体は、その構造体自身を示すポインタ情報（図１９ではポインタ５）および命題Ｃを示す情報を含む。ｏｒ演算子についてのデータ構造体は、その構造体自身を示すポインタ情報（図１９ではポインタ２）、演算子ｏｒを示す情報、Ｂについてのデータ構造体のポインタ情報（ポインタ４）およびＣについてのデータ構造体のポインタ情報（ポインタ５）を含む。
【００５５】
生成部１１２は、同様の手順により、さらに論理式中の未解析部分を解析して有向非循環グラフデータを生成する。例えば、解析済のＡ  ａｎｄ  （Ｂ  ｏｒ  Ｃ）に対し、命題Ｄがａｎｄで接続されている部分について、生成部１１２は、有向非循環グラフデータをさらに生成する。例えば、ａｎｄについてのデータ構造体が、命題Ｄについてのデータ構造体のポインタ情報と、先に生成されたａｎｄ演算子についてのデータ構造体のポインタ情報（図１９ではポインタ３）とを含む。上記の例では、論理式の始めから有向非循環グラフデータを生成する手順を示したが、この手順のみに限られるものではなく、論理式の後ろから記憶像データを生成してもよい。
【００５６】
上記の手順で論理式の構文解析が行なわれることで、有向非循環グラフデータが生成されると、生成部１１２は、記憶部１２に記憶領域を確保し、確保した記憶領域内に［真］始点の要素を持つレコードと、［偽］始点の要素を持つレコードを追加する（Ｓ３０２）。さらに、生成部１１２は、Ｓ３０１で生成した有向非循環グラフデータの最上位ノード（ｒｏｏｔ要素）のレコードを追加する（Ｓ３０３）。この際、生成部１１２は、論理判定テーブルＴ２ａの［真］始点を要素とするレコードの［真］子要素にｒｏｏｔ要素を示す情報を格納し、ｒｏｏｔ要素を要素とするレコードの［真］子要素に［真］終点という要素を追加する。逆に、生成部１１２は、論理判定テーブルＴ２ａの［偽］始点を要素とするレコードの［偽］子要素にｒｏｏｔ要素を示す情報を追加し、ｒｏｏｔ要素を要素とするレコードの［偽］子要素に［偽］終点という要素を追加する。Ｓ３０３の処理後、生成部１１２は、キュー（グラフ作成キュー）を用意し、用意したキューにｒｏｏｔ要素を示す情報を格納する（Ｓ３０４）。生成部１１２は、Ｓ３０４の処理を終えると、図１７に示すフローチャートの処理に戻る（Ｓ３０５）。
【００５７】
Ｓ２０１の処理後、生成部１１２は、グラフ作成キューに要素が格納されているか否かを判断する（Ｓ２０２）。グラフ作成キューに要素が格納されていない場合（Ｓ２０２：Ｎｏ）には、図１７のフローを終了する（Ｓ２０３）。グラフ作成キューに要素が格納されている場合（Ｓ２０２：Ｙｅｓ）には、生成部１１２は、グラフ作成キューから１つ要素を取得する（Ｓ２０４）。例えば、初回の処理においては、ｒｏｏｔ要素が取得される。次に、生成部１１２は、取得した要素が論理演算子であるか否かを判断する（Ｓ２０５）。取得した要素が演算子でない場合（Ｓ２０５：Ｎｏ）は、生成部１１２は、Ｓ２０２の処理に戻る。一方、取得した要素が演算子の場合（Ｓ２０５：Ｙｅｓ）には、生成部１１２は、取得した要素を示す情報を、「要素」の項目に含むレコードを、取得した要素の子要素の数だけコピーする（Ｓ２０６）。Ｓ２０６の処理において、生成部１１２は、図１９の有向非循環グラフのデータを参照して子要素の数を判断する。例えばｒｏｏｔ要素であれば、子要素のポインタを２つ（ポインタ７及びポインタ８）有しているので、子要素の数は２である。Ｓ２０６の処理後、生成部１１２は、コピーして得られたレコードの「要素」の項目を、子要素を示す情報に更新する（Ｓ２０７）。例えば、取得した要素がｒｏｏｔ要素である場合には、生成部１１２は、コピーして得られたそれぞれのレコードの「要素」の項目を、ポインタ７のａｎｄ要素、ポインタ８のｏｒ要素に更新する。
【００５８】
Ｓ２０７の処理後、生成部１１２は、取得した要素がａｎｄ演算子であるかｏｒ演算子であるかの判定を行なう。（Ｓ２０８）。取得した要素がｏｒ演算子である場合（Ｓ２０８：ｏｒ）には、生成部１１２は、「［真］子要素」の項目に取得した要素を示す情報を含むレコードを抽出し、そのレコードの「［真］子要素」の項目に含まれる取得した要素を示す情報を、取得した要素の子要素を示す情報に更新する（Ｓ２０９）。例えば、取得した要素がｒｏｏｔ要素である場合には、ポインタ９のｏｒ要素を除いて、ポインタ７のａｎｄ要素とポインタ８のｏｒ要素が追加される。
【００５９】
一方、取得した要素がａｎｄ演算子である場合（Ｓ２０８：ａｎｄ）には、生成部１１２は、取得した要素の子要素のうち、一方の子要素（Ａ）のレコードの「［真］子要素」の項目を、他方の子要素（Ｂ）を示す情報に更新する（Ｓ２１０）。さらに、Ｓ２１０の処理後、生成部１１２は、「［真］子要素」の項目に取得した要素を示す情報を含むレコードを抽出し、そのレコードの「［真］子要素」の項目に含まれる、取得した要素を示す情報を、Ｓ２１０の処理における一方の子要素（Ａ）を示す情報に更新する（Ｓ２１１）。例えば、取得した要素がポインタ７のａｎｄ要素である場合には、ポインタ７のａｎｄ要素を除いて、ポインタ３のａｎｄ要素が追加される。その場合は、ポインタ３のａｎｄ要素のレコードの「［真］子要素」の項目には、ポインタ６の命題Ｄを示す情報が格納される。
【００６０】
Ｓ２１１またはＳ２０９の処理後、生成部１１２は、取得した要素のレコードを削除し（Ｓ２１２）、取得した要素の子要素をグラフ作成キューに格納し（Ｓ２１３）、Ｓ２０２の処理に戻る。Ｓ２１３の処理で、例えば、取得した要素がｒｏｏｔ要素である場合は、グラフ作成キューに、ポインタ７のａｎｄ要素及びポインタ８のｏｒ要素が追加される。ちなみに、Ｓ２１０とＳ２１１の処理は順序を入れ替えても構わないし、Ｓ２１２とＳ２１３の処理も順序を入れ替えて構わない。
【００６１】
生成部１１２が図１７に示すＳ２０２〜Ｓ２１３の処理を繰り返すことにより、論理判定テーブルＴ２ａが生成される。その経過を、図１５に示すような論理判定テーブルＴ２ａに対応する有向非循環グラフを用いて説明する。例えば、Ｓ２０１処理後の論理判定テーブルＴ２ａに基づいてグラフ（［真］始点から関連性を辿る場合のグラフ）を生成すると、図２０Ａに示すグラフになる。この時点でグラフ作成キューには、ｒｏｏｔ要素を示す情報（例えばポインタ９）が格納されている。生成部１１２がＳ２０２〜Ｓ２１３の処理を行なうことにより、ｒｏｏｔ要素であるポインタ９のｏｒ要素に関する情報が、ポインタ９のｏｒ要素の子要素であるポインタ７のａｎｄ要素およびポインタ８のｏｒ要素に置き換えられる。その時点の論理判定テーブルＴ２ａに対応するグラフを図２０Ｂに示す。図２０Ｂにおいては、［真］始点に、ポインタ７のａｎｄ要素及びポインタ８のｏｒ要素が関連付けられている。さらに、生成部１１２がＳ２０２〜Ｓ２１３の処理を行なうことにより、ポインタ７のａｎｄ要素に関する情報が、ポインタ３のａｎｄ要素およびポインタ６の命題Ｄに置き換えられる。この時点での論理判定テーブルＴ２ａに対応するグラフを図２０Ｃに示す。さらに、生成部１１２がＳ２０２〜Ｓ２１３の処理を行なうことにより、ポインタ３のａｎｄ要素に関する情報が、ポインタ１の命題Ａおよびポインタ２のｏｒ要素に置き換えられる。この時点での論理判定テーブルＴ２ａに対応するグラフを図２０Ｄに示す。ポインタ６の命題Ｄの要素がグラフ作成キューから取得された場合には、Ｓ２０５の判定により、論理判定テーブルＴ２ａの更新は行なわれない。さらに、生成部１１２がＳ２０２〜Ｓ２１３の処理を行なうことにより、ポインタ２のｏｒ要素に関する情報が、ポインタ４の命題Ｂおよびポインタ５の命題Ｃに置き換えられる。この時点での論理判定テーブルＴ２ａに対応するグラフを図２０Ｅに示す。ｒｏｏｔ要素（ポインタ９のｏｒ要素）がグラフ作成キューから取得された場合のＳ２１３の処理により、グラフ作成キューにポインタ８のｏｒ要素が格納されている。グラフ作成キューからポインタ８のｏｒ要素が取得された場合に生成部１１２がＳ２０２〜Ｓ２１３の処理を行なうことにより、ポインタ８のｏｒ要素に関する情報が、ポインタ１０の命題Ｅおよびポインタ１１のａｎｄ要素に置き換えられる。この時点での論理判定テーブルＴ２ａに対応するグラフを図２０Ｆに示す。さらに、グラフ作成キューからポインタ１１のａｎｄ要素が取得された場合に生成部１１２がＳ２０２〜Ｓ２１３の処理を行なうことにより、ポインタ１１のａｎｄ要素に関する情報が、ポインタ１２の命題Ｆおよびポインタ１３の命題Ｇに置き換えられる。この時点で論理判定テーブルＴ２ａに対応するグラフは、図１５に示すグラフとなる。
【００６２】
図２１は、「［偽］始点」から関連性を辿る処理に用いられる論理判定テーブルＴ２ａの生成処理のフローチャートを示す。生成部１１２は、図１７に示すフローチャートの処理を終了すると、図２１に示すフローチャートの処理を開始する（Ｓ４００）。まず、生成部１１２は、図１８に示すＳ３０２〜Ｓ３０４の処理を行なう（Ｓ４０１）。図２１のＳ４０1に含まれるＳ３０２の処理においては、生成部１１２は、［偽］の値を要素カラムに持つ行を追加する。次いで生成部１１２は、図１７に示すＳ２０２の処理を行なう（Ｓ４０２）。生成部１１２は、Ｓ２０２の判断でＹｅｓと判断する場合（Ｓ４０２：Ｙｅｓ）はＳ２０４〜Ｓ２０７の処理を行ない（Ｓ４０４）、Ｓ２０２の判断でＮｏと判断する場合（Ｓ４０２：Ｎｏ）には図２１のフローチャートの処理を終了する（Ｓ４０３）。Ｓ４０４の処理が終了すると、生成部１１２は、Ｓ２０８の判断を行なう（Ｓ４０５）。Ｓ４０５の判断の結果、判断対象の演算子がｏｒ演算子であると判断した場合には、生成部１１２は、取得した要素の子要素のうち、一方の子要素（Ａ）のレコードの「［偽］子要素」の項目を、他方の子要素（Ｂ）を示す情報に更新する（Ｓ４０６）。さらに、Ｓ４０６の処理後、生成部１１２は、「［偽］子要素」の項目に取得した要素を示す情報を含むレコードを抽出し、そのレコードの「［偽］子要素」の項目に含まれる、取得した要素を示す情報を、Ｓ４０６の処理における一方の子要素（Ａ）を示す情報に更新する（Ｓ４０７）。Ｓ４０５の判断の結果、判断対象の演算子がａｎｄ演算子であると判断した場合（Ｓ４０５：ａｎｄ）では生成部１１２はＳ４０８の処理を行なう。すなわち、生成部１１２は、「［偽］子要素」の項目に取得した要素を示す情報を含むレコードを抽出し、そのレコードの「［偽］子要素」の項目に含まれる取得した要素を示す情報を、取得した要素の子要素を示す情報に更新する（Ｓ４０８）。［真］始点から関連性を辿る処理に用いられる論理判定テーブルＴ２ａの生成とは、ｏｒ演算子の場合に行なう処理とａｎｄ演算子の場合に行なう処理とが逆になっている。Ｓ４０７またはＳ４０８の処理を終えると、生成部１１２は、Ｓ２１２およびＳ２１３の処理を行ない（Ｓ４０９）、Ｓ４０２の処理に戻る。上記の手順（図１７、図１８および図２１に記載のフローチャート）により生成された論理判定テーブルがマージされることで、図１１Ａに示す論理判定テーブルＴ２ａが生成される。また、図１７、図１８および図２１に記載のフローチャートに基づく処理が同時に行なわれ、図１１Ａに示す論理判定テーブルＴ２ａが生成されてもよい。
【００６３】
次に、図１１Ｃの論理判定テーブルＴ２ｃを生成する場合の処理について図２２のフローチャートに基づいて説明する。図１１Ｂの論理判定テーブルＴ２ｂについては、図１に示すＢＤＤに対応するテーブル構造であり、ＢＤＤを生成する様々な手法で生成可能である。まず、生成部１１２は、受付部１１１が検索要求を受け付けて管理テーブルＴ１に情報を格納する（Ｓ５００）と、Ｓ２０１の処理を行なう（Ｓ５０１）。このＳ５０１の処理においても、Ｓ４０１と同様に、Ｓ５０１に含まれるＳ３０２の処理においては、生成部１１２は、［偽］の値を要素カラムに持つ行を追加する。次に、生成部１１２は、Ｓ２０２の判断を行ない（Ｓ５０２）、判断の結果がＮｏである場合（Ｓ５０２：Ｎｏ）には処理を終了し（Ｓ５０３）、判断の結果がＹｅｓである場合（Ｓ５０２：Ｙｅｓ）には、Ｓ２０４〜Ｓ２０７の処理を行なう（Ｓ５０４）。Ｓ５０４の処理後、生成部１１２は、Ｓ２０８の判断を行なう（Ｓ５０５）。Ｓ５０５の判断において演算子がｏｒ演算子である場合には、生成部１１２は、Ｓ４０６およびＳ４０７の処理を行ない（Ｓ５０６）、さらにＳ２１３の処理を行なう（Ｓ５０７）。一方、Ｓ５０５の判断において、演算子がａｎｄ演算子である場合には、生成部１１２は、「［偽］子要素」の項目に取得した要素を示す情報を含むレコードを抽出し、そのレコードの「［偽］子要素」の項目に含まれる取得した要素を示す情報を、取得した要素の子要素のうちの１つ（子要素（Ｃ））を示す情報に更新する（Ｓ５０８）。Ｓ５０８の処理後、生成部１１２は、グラフ作成キューに子要素（Ｃ）を示す情報を格納する（Ｓ５０９）。Ｓ５０７またはＳ５０９の処理後、生成部１１２は、Ｓ２１２の処理を行ない（Ｓ５１０）、Ｓ５０２の処理に戻る。
【００６４】
論理判定テーブルＴ２ｃは、論理判定テーブルＴ２ａのうちの［偽］始点から始まる１経路を含むテーブルである。論理判定テーブルＴ２ｃを用いた偽判定処理を従来のＢＤＤに基づく判定処理に組み合わせると、ＢＤＤに基づく判定処理よりも論理判定テーブルＴ２ｃを用いた偽判定処理の方が早く結論を得られる場合がある。その場合には、従来のＢＤＤに基づく判定処理よりも早く論理式の判定結果が得られたことになる。
【００６５】
ちなみに、受付部１１１が受け付けた検索条件の論理式に論理否定演算子（ＮＯＴ）が命題に作用している場合には、生成部１１２は、論理否定演算子と命題をまとめて１つの命題と見なして論理判定テーブルＴ２を生成する。例えば、ｎｏｔ（Ａ）は１つの命題と見なされる。さらに、論理式に否定演算子が作用している場合には、生成部１１２は、構文解析を行なう前に、ド・モルガンの法則を用いて、単一の命題に論理否定演算子が作用している形式に論理式を変形する。さらに命題判定部１１４２は、命題に論理否定演算子が作用している命題については、元の命題の真偽を判定し、その判定結果を反転して結果を出力する。例えば、命題判定部１１４２は、ｎｏｔ（Ａ）に対しては命題Ａの真偽判定結果が真であれば判定結果を偽とし、命題Ａの真偽判定結果が偽であれば判定結果を真とする。
【００６６】
以下に判定部１１４が行なう判定処理について、さらに説明する。
【００６７】
まず、命題判定部１１４２は、図１４に示すＳ１０５の処理を行なう。まず、Ｓ１０５の処理において、命題判定部１１４２は、記憶部１１４３または記憶部１２にテーブルＴ４の記憶領域を確保する。次に、命題判定部１１４２は、論理式に含まれる各命題についてテーブルＴ４にレコードを生成する。さらに、論理式に含まれる各命題について、命題が判定対象のデータに含まれているか否かを判定し、判定結果をテーブルＴ４に格納する。命題判定部１１４２は、論理式に含まれる全ての命題の判定が終了するか、論理式の判定が終了した場合に、処理を終了とする。
【００６８】
次に、論理判定部１１４１は、図１４に示すＳ１０６の処理を行なう。図２３はＳ１０６の論理判定テーブルＴ２ａを用いた論理判定処理のフローチャートを示す。論理判定部１１４１は、読出部１１３が判定対象のデータを読み出す（Ｓ６０１）と、記憶部１１４３または記憶部１２にテーブルＴ３ａおよびテーブルＴ３ｂの記憶領域を確保する。さらに、論理判定部１１４１は、記憶部１２に記憶された論理判定テーブルＴ２ａを参照して、「［真］始点」のレコードの「［真］子要素」に格納された要素をテーブルＴ３ａに格納し、「［偽］始点」のレコードの「［偽］子要素」に格納された要素をテーブルＴ３ｂに格納する（Ｓ６０２）。Ｓ６０２の処理が行なわれると、論理判定部１１４１は、Ｓ６０３〜Ｓ６１０の処理と、Ｓ６１１〜Ｓ６１８の処理とを並列で行なう。さらに、例えば、Ｓ６０３〜Ｓ６１０の処理と、Ｓ６１１〜Ｓ６１８の処理とのそれぞれについても、並列で多重に処理されてもよい。すなわち、複数のプロセッサコアがそれぞれでＳ６０３〜Ｓ６１０の処理を行ない、さらに別の複数のプロセッサコアがそれぞれでＳ６１１〜Ｓ６１８の処理を行なっても良い。
【００６９】
論理判定部１１４１は、記憶部１１４３に確保された所定の領域に停止を示す情報が格納されていないかどうか（停止フラグが立っているか）を判断する（Ｓ６０３）。停止を示す情報が格納されている場合（Ｓ６０３：Ｎｏ）には、論理判定部１１４１は、Ｓ６０４〜Ｓ６１０の処理をスキップする。停止を示す情報が格納されていない場合（Ｓ６０３：Ｙｅｓ）には、論理判定部１１４１は、テーブルＴ３ａに格納された要素を１つ読み出す（Ｓ６０４）。Ｓ６０３〜Ｓ６１０の処理が並列で処理される場合には、Ｓ６０４で読み出された要素は他のプロセッサコアに読み出されない制御を行なうこととしてもよい。Ｓ６０４が行なわれると、論理判定部１１４１は、Ｓ６０４で読み出した要素について判定結果をテーブルＴ４から読み出す（Ｓ６０５）。Ｓ６０５で読み出した判定結果が真である場合（Ｓ６０５：Ｙｅｓ）は、論理判定部１１４１は、Ｓ６０７の処理を行なう。Ｓ６０５で読み出した判定結果が偽であるか、判定結果が読み出せない（命題判定部１１４２がまだ判定結果を格納していない）場合（Ｓ６０５：Ｎｏ）は、論理判定部１１４１は、Ｓ６０３の処理に戻る。Ｓ６０７では、論理判定部１１４１は、論理判定テーブルＴ２ａから、Ｓ６０４で読み出した要素のレコードの「［真］子要素」に格納された要素を読み出す（Ｓ６０７）。Ｓ６０７の処理後、論理判定部１１４１は、テーブルＴ３ａに格納されており、Ｓ６０４で読み出された要素の情報を、Ｓ６０７で読みだした要素の情報に更新する。（Ｓ６０８）。さらに、論理判定部１１４１は、Ｓ６０７で読みだした要素が「［真］終点」であるか否かを判断する（Ｓ６０９）。Ｓ６０７で読みだした要素が「［真］終点」でない場合（Ｓ６０９：Ｎｏ）は、論理判定部１１４１は、Ｓ６０３に戻って処理を行なう。Ｓ６０７で読みだした要素が「［真］終点」である場合（Ｓ６０９：Ｙｅｓ）は、判定対象のデータに対して論理式が「真」である旨を判断し、記憶部１１４３の所定の領域に停止を示す情報を格納する（Ｓ６１０）。Ｓ６１０の処理後、論理判定処理を終了する（Ｓ６１９）。
【００７０】
論理判定部１１４１は、Ｓ６０３〜Ｓ６１０の処理を行なう一方で、Ｓ６１１〜Ｓ６１８の処理を行なう。論理判定部１１４１は、記憶部１１４３に確保された所定の領域に停止を示す情報が格納されていないかどうか（停止フラグが立っているか）を判断する（Ｓ６１１）。停止を示す情報が格納されている場合（Ｓ６１１：Ｎｏ）には、論理判定部１１４１は、Ｓ６１２〜Ｓ６１８の処理をスキップする。停止を示す情報が格納されていない場合（Ｓ６１１：Ｙｅｓ）には、論理判定部１１４１は、テーブルＴ３ｂに格納された要素を１つ読み出す（Ｓ６１２）。Ｓ６１１〜Ｓ６１８の処理が並列で処理される場合には、Ｓ６１２で読み出された要素は他のプロセッサコアに読み出されない制御を行なうこととしてもよい。Ｓ６１２が行なわれると、論理判定部１１４１は、Ｓ６１２で読み出した要素について判定結果をテーブルＴ４から読み出す（Ｓ６１３）。Ｓ６１３で読み出した判定結果が偽である場合（Ｓ６１４：Ｙｅｓ）は、論理判定部１１４１は、Ｓ６１５の処理を行なう。Ｓ６１３で読み出した判定結果が真である場合（Ｓ６１４：Ｎｏ）は、Ｓ６０５で判定結果が読み出せない（命題判定部１１４２がまだ判定結果を格納していない）場合と同様に、論理判定部１１４１は、Ｓ６１１の処理に戻る。Ｓ６１５では、論理判定部１１４１は、論理判定テーブルＴ２ａから、Ｓ６１２で読み出した要素のレコードの「［偽］子要素」に格納された要素を読み出す（Ｓ６１５）。Ｓ６１５の処理後、論理判定部１１４１は、テーブルＴ３ｂに格納されており、Ｓ６１２で読み出された要素の情報を、Ｓ６１５で読みだした要素の情報に更新する（Ｓ６１６）。さらに、論理判定部１１４１は、Ｓ６１５で読みだした要素が「［偽］終点」であるか否かを判断する（Ｓ６１７）。Ｓ６１５で読みだした要素が「［偽］終点」でない場合（Ｓ６１７：Ｎｏ）は、論理判定部１１４１は、Ｓ６１１に戻って処理を行なう。Ｓ６１５で読みだした要素が「［偽］終点」である場合（Ｓ６１７：Ｙｅｓ）は、判定対象のデータに対して論理式が「偽」である旨を判断し、記憶部１１４３の所定の領域に停止を示す情報を格納する（Ｓ６１８）。Ｓ６１８の処理後、論理判定処理を終了する（Ｓ６１９）。
【００７１】
論理判定テーブルＴ２ｂ及びＴ２ｃを用いた論理判定処理は、ほぼ図２３のフローチャートと同様に行なわれる。その場合、論理判定部１１４１は、例えば、Ｓ６０７において論理判定テーブルＴ２ｂを参照して要素を読み出す。その際、論理判定部１１４１は、例えば、Ｓ６０６の判定処理を省略して、Ｓ６０５で読みだした判定結果に応じて、Ｓ６０７で論理判定テーブルＴ２ｂから要素を読み出す。また、論理判定部１１４１は、例えば、Ｓ６１５においてテーブルＴ２ｃを参照してデータを読み出す。
【００７２】
上記の処理により、論理式の判定処理の効率化が達成される。上述の実施例に限らず、発明を実施できる範囲内において、その構成は、適宜変更可能である。
【００７３】
ちなみに、例えば異常データを検出する場合などには、判定対象データのほとんどが正常なデータであり、そのため、ほとんどの判定対象のデータは、論理式に対して真であると考えられる。論理判定テーブルＴ２ｂおよびＴ２ｃを用いた判定よりも、論理判定テーブルＴ２ａを用いることで、ＢＤＤを用いた場合よりも、判定するまでに判定結果が必要な命題の数が抑制される（ＢＤＤでは定められた判定順序に従って判定する）ので、平均判定速度が速くなることが期待できる。
【００７４】
また、そのような場合、例えば、論理判定部１１４１は、Ｓ６１１〜Ｓ６１８を行なわないようにしてもよい。Ｓ６０４とＳ６０５により論理式に含まれる全要素について判定結果が参照され、［真］終点に到達しない場合は、論理式は［偽］であると判定できる。上述のように、論理式が［真］であることがほとんどであり、論理式が［真］であることの判定を高速化したい場合には、Ｓ６１１〜Ｓ６１８を行なわないようにしてもよい。逆に、論理式が［偽］であることがほとんどであり、論理式が［偽］であることの判定を高速化したい場合には、Ｓ６０３〜Ｓ６１０を行なわないようにしてもよい。
【００７５】
また、論理式の判定（例えばＢＤＤ）を、論理式全体を［真］と判定するのに必要な命題群のそれぞれを満たすか否かの判定と組み合わせてもよい。例えば、論理式（Ａ  ａｎｄ  （Ｂ  ｏｒ  Ｃ）  ａｎｄ  Ｄ）  ｏｒ  Ｅ  ｏｒ  （Ｆ  ａｎｄ  Ｇ）の判定と並行して、例えば、命題Ｅ（もしくは、Ａ  ａｎｄ  Ｂ  ａｎｄ  Ｄなど）の判定を行ない、いずれかの判定結果が得られた場合に、論理式判定の処理が終了されることとすればよい。この場合に用いられる論理判定テーブルは、例えば、生成部１１２が、図１７のフローを、Ｓ２０４で取得した要素がｏｒ要素である場合に、Ｓ２０６，Ｓ２０７及びＳ２１３を片方の子要素のみを対象として行なうことなどにより生成される。
【符号の説明】
【００７６】
１      コンピュータ
２      記憶装置
３      ネットワーク
４      コンピュータ
５      ネットワーク
６      ロードバランサ
７      ネットワーク
１１（１１Ａ，１１Ｂ）    処理部
１２（１２Ａ，１２Ｂ）    記憶部
１３    通信部
１４    通信部
１５    通信部
１６    通信部
【図１】
0005928577.tif 000002
【図２】
0005928577.tif 000003
【図３】
0005928577.tif 000004
【図４】
0005928577.tif 000005
【図５】
0005928577.tif 000006
【図６】
0005928577.tif 000007
【図７】
0005928577.tif 000008
【図８】
0005928577.tif 000009
【図９】
0005928577.tif 000010
【図１０】
0005928577.tif 000011
【図１１】
0005928577.tif 000012
【図１２】
0005928577.tif 000013
【図１３】
0005928577.tif 000014
【図１４】
0005928577.tif 000015
【図１５】
0005928577.tif 000016
【図１６】
0005928577.tif 000017
【図１７】
0005928577.tif 000018
【図１８】
0005928577.tif 000019
【図１９】
0005928577.tif 000020
【図２０】
0005928577.tif 000021
【図２１】
0005928577.tif 000022
【図２２】
0005928577.tif 000023
【図２３】
0005928577.tif 000024