(57)【特許請求の範囲】
【請求項１】
階層化された論理構造を有する構造化文書の入力を受け付ける構造化文書受付部と、
入力された前記構造化文書データを記憶する構造化文書記憶部と、
クエリデータの入力を受け付けるクエリデータ受付部と、
入力されたクエリデータの構文を解析して、各変数が一度のみ代入されるよう定義された静的単一代入となるように分解された構文解析木を取得する構文解析部と、
前記構文解析部で得られた構文解析木から、各構文解析木の変数が満たす必要がある階層条件、及び変数の値の条件を含む制約条件を取得する制約条件取得部と、
前記制約条件取得部で得られた制約条件に基づいて、前記制約条件によって対象とする前記構造化文書を絞り込み可能な態様へと前記クエリデータを書き換える構文解析木書換え部と、
前記構文解析木書換え部によって書き換えられた前記クエリデータを入力として、検索結果を出力するクエリ実行部と、
を備え、
前記制約条件取得部は、前記制約条件に、前記変数が満たす必要がある階層条件と、同一の要素名によって規定された別の階層条件も追加し、
前記構文解析木書換え部は、追加された前記制約条件に基づいて前記クエリデータを書き換える際に、前記制約条件に対して、別の階層条件が追加される前の制約条件と同じ結果を求めることができる別の条件を付加する
ことを特徴とする構造化文書管理装置。 
【請求項２】
前記構文解析木書換え部は、前記制約条件取得部で得られた前記制約条件に基づく書換え結果を、元のクエリデータと同じ文法形式とする
請求項１記載の構造化文書管理装置。
【請求項３】
構造化文書受付部が、階層化された論理構造を有する構造化文書の入力を受け付けるステップと、
構造化文書記憶部が、入力された前記構造化文書データを記憶するステップと、
クエリデータ受付部がクエリデータの入力を受け付けるステップと、
構文解析部が入力されたクエリデータの構文を解析して、各変数が一度のみ代入されるよう定義された静的単一代入となるように分解された構文解析木を取得するステップと、
制約条件取得部が前記構文解析木から、各構文解析木の変数が満たす必要がある階層条件、及び変数の値の条件を含む制約条件を取得するステップと、
構文解析木書換え部が前記制約条件に基づいて、前記制約条件によって対象とする前記構造化文書を絞り込み可能な態様へと前記クエリデータを書き換えるステップと、
クエリ実行部が前記書き換えられた前記クエリデータを入力として、検索結果を出力するステップと、
前記制約条件取得部が、前記制約条件に、前記変数が満たす必要がある階層条件と、同一の要素名によって規定された別の階層条件も追加するステップと、
前記構文解析木書換え部が、追加された前記制約条件に基づいて前記クエリデータを書き換える際に、前記制約条件に対して、別の階層条件が追加される前の制約条件と同じ結果を求めることができる別の条件を付加するステップと、
を含むことを特徴とする構造化文書管理方法。 
【請求項４】
コンピュータに、
階層化された論理構造を有する構造化文書の入力を受け付ける構造化文書受付部と、
入力された前記構造化文書データを記憶する構造化文書記憶部と、
クエリデータの入力を受け付けるクエリデータ受付部と、
入力されたクエリデータの構文を解析して、各変数が一度のみ代入されるよう定義された静的単一代入となるように分解された構文解析木を取得する構文解析部と、
前記構文解析部で得られた構文解析木から、各構文解析木の変数が満たす必要がある階層条件、及び変数の値の条件を含む制約条件を取得する制約条件取得部と、
前記制約条件取得部で得られた制約条件に基づいて、前記制約条件によって対象とする前記構造化文書を絞り込み可能な態様へと前記クエリデータを書き換える構文解析木書換え部と、
前記構文解析木書換え部によって書き換えられた前記クエリデータを入力として、検索結果を出力するクエリ実行部と、
を実行させるための構造化文書管理プログラムであって、
前記制約条件取得部は、前記制約条件に、前記変数が満たす必要がある階層条件と、同一の要素名によって規定された別の階層条件も追加し、
前記構文解析木書換え部は、追加された前記制約条件に基づいて前記クエリデータを書き換える際に、前記制約条件に対して、別の階層条件が追加される前の制約条件と同じ結果を求めることができる別の条件を付加する
構造化文書管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、構造化文書管理装置、方法およびプログラムに関する。
【背景技術】
【０００２】
従来、ＸＭＬ（Ｅｘｔｅｎｓｉｂｌｅ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）などで記述された構造化文書データを記憶・検索するための構造化文書管理装置が知られている。構造化文書管理装置における構造化文書データの検索のために、ＲＤＢＭＳ（Ｒｅｌａｔｉｏｎａｌ  Ｄａｔａｂａｓｅ  Ｍａｎａｇｅｍａｎｔ  Ｓｙｓｔｅｍ）における問い合わせ言語ＳＱＬのように、ＸＭＬデータに対する問い合わせ言語ＸＱｕｅｒｙ（ＸＭＬ  Ｑｕｅｒｙ  Ｌａｎｇｕａｇｅ）が策定されており、多くの構造化文書管理装置でサポートされている。【０００３】
ＸＱｕｅｒｙは、ＸＭＬデータ集合をデータベースのように扱うための言語であり、条件に合致するデータ集合の取り出しや集計・分析を行うための手段が提供されている。ＸＭＬデータは親子や兄弟などの要素が組み合わさった階層化された論理構造（階層構造）を持つため、条件にはこの階層構造に関する条件（構造条件）を指定することができる。【０００４】
ＸＭＬが指定した構造条件を満たすかを検索する技術は、代表的なＸＭＬデータのｐａｒｓｅ処理であるＳＡＸ（Simple  API  for  XML）などにより提供されている。しかし、ＳＡＸでは、検索対象となる構造化文書（ここではＸＭＬ）に対しては、上位の階層から下位の階層へしかアクセスできない。そのため、下位の階層で指定された絞り込み条件があった場合に、下位の階層まで辿らない限り絞り込み条件を適用できない。そのため絞り込み条件があるまでは全構造化文書に対して最上位から下位の階層へ辿る必要がある。【０００５】
構造化文書管理装置における検索処理を高速にするためには、できるだけ絞り込み条件を早期に適用し、検索中に生成される中間データを削減することが望ましい。そのために、索引処理を用いて絞り込んだ構造化文書集合のみに対して、構造条件を検索する技術も存在する。しかしながら、この技術はクエリが複数のサブクエリから構成される入れ子クエリに関しては対応していない。【０００６】
なお入れ子クエリにおいて、サブクエリをまたがって絞り込み条件を早期に適用するように様々な試みがなされている。例えば、リレーショナルデータベースモデルにおいて、クエリを構成するサブクエリ間の関係をグラフの形で定義し、グラフ間で述語を移動できる条件を定義して、可能な場合であれば述語を別のサブクエリに移動することで最適化を図る技術が存在する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００７−２２６４５２号公報
【特許文献２】特開２０１０−７９６４６号公報
【非特許文献】
【０００８】
【非特許文献１】Query  Optimization  by  Predicate  Move-Around(1994)
【非特許文献２】Shifting  Predicates  to  Inner  Sub-expressions  for  XQuery  Optimization(2006)
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしリレーショナルデータベースモデルは構造化文書のデータモデルと異なり階層構造や要素間の順序関係といった問題がなく、要素に対する識別子（ＩＤ）をサポートしていない。そのためリレーショナルデータベースにおけるクエリ書換えのアプローチが、構造化文書に対しては適用できないケースが存在する。【００１０】
また、構造化文書であるＸＭＬの問い合わせクエリにおいて、ビューと呼ばれる仮想的なＸＭＬ文書に対する条件を、ビューを作成する直前及び直後にコピーして適用することで、無駄な構造化文書のビューの要素を辿ることを回避することもできる。しかし対象がビューに限定されることに加え、単純に対象となる条件を、ビューを作成する段階で適用可能な箇所全てにコピーして適用するため同一の条件が複数の箇所で評価されてしまう。さらにコピー可能な複数の条件が存在していた場合、無条件に述語条件の論理和をコピーしてしまうため、述語条件による絞込みの効果が十分ではない問題が存在する。本発明が解決しようとする課題は、検索を高速に行うことが可能な構造化文書管理装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
実施形態の構造化文書管理装置は、階層化された論理構造を有する構造化文書データの入力を受け付ける構造化文書データ受付部と、入力された前記構造化文書データを記憶する構造化文書データ記憶部と、クエリデータの入力を受け付けるクエリデータ受付部と、入力されたクエリデータの構文を解析して、各変数が一度のみ代入されるよう定義された静的単一代入となるように分解された構文解析木を取得する構文解析部と、前記構文解析部で得られた構文解析木から、各構文解析木の変数が満たす必要がある階層条件、及び変数の値の条件を含む制約条件を取得する制約条件取得部と、前記制約条件取得部で得られた制約条件に基づいて、前記クエリデータを前記制約条件によって対象とする前記構造化文書を絞り込み可能な態様へと書き換える構文解析木書換え部と、前記構文解析木書換え部によって書き換えられた前記クエリデータを入力として、検索結果を出力するクエリ実行部と、を備え、前記制約条件取得部は、前記制約条件に、前記変数が満たす必要がある階層条件と、同一の要素名によって規定された別の階層条件も追加し、前記構文解析木書換え部は、追加された前記制約条件に基づいて前記クエリデータを書き換える際に、前記制約条件に対して、別の階層条件が追加される前の制約条件と同じ結果を求めることができる別の条件を付加する。
【図面の簡単な説明】
【００１２】
【図１】実施形態における構造化文書管理システムのシステム構築例を示す模式図。
【図２】実施形態におけるサーバおよびクライアント端末のモジュール構成図。
【図３】実施形態におけるサーバおよびクライアント端末の概略構成を示すブロック図。
【図４】実施形態における構造化文書ＤＢに登録される構造化文書データの一例を示す説明図。
【図５】実施形態における構造化文書ＤＢに登録される構造化文書データの一例を示す説明図。
【図６】実施形態における構造化文書ＤＢに登録される構造化文書データの一例を示す説明図。
【図７】実施形態におけるクエリデータの一例を示す説明図。
【図８】実施形態における検索処理の流れを示すフローチャート。
【図９】実施形態におけるクエリデータについて構文解析処理を行った結果を示す説明図。
【図１０】実施形態における制約条件取得処理の流れを示すフローチャート。
【図１１】実施形態における入力から出力への制約条件取得処理の流れを示すフローチャート。
【図１２】実施形態における出力から入力への制約条件取得処理の流れを示すフローチャート。
【図１３】実施形態におけるクエリデータについて入力から出力への制約条件取得処理を行って得られた制約条件のリストを示す説明図。
【図１４】実施形態におけるクエリデータについて入力から出力への制約条件取得処理を行って得られたパス情報リストを示す説明図。
【図１５】実施形態におけるクエリデータについて入力から出力への制約条件取得処理を行って得られた制約条件取得対象変数リストを示す説明図。
【図１６】実施形態におけるクエリデータについて出力から入力への制約条件取得処理を行って得られた制約条件のリストを示す説明図。
【図１７】実施形態における書換えの際に利用する書換えテンプレートの一例を示す説明図。
【図１８】実施形態における構造解析木書換え処理の流れを示すフローチャート。
【図１９】実施形態におけるクエリデータについて構造解析木書換え処理を行って得られた構文解析木を示す説明図。
【図２０】実施形態におけるクエリデータについて検索した結果を示す説明図。
【発明を実施するための形態】
【００１３】
以下、実施形態の構造化文書管理装置、方法およびプログラムを、図面を参照して説明する。
【００１４】
図１は、実施形態にかかる構造化文書管理システムのシステム構築例を示す模式図である。ここでは、実施形態の構造化文書管理システムとして、図１に示すように、構造化文書管理装置であるサーバコンピュータ（以下、サーバという。）１に、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）等のネットワーク２を介して、クライアントコンピュータ（以下、クライアント端末という。）３が複数台接続されたサーバクライアントシステムを想定する。
【００１５】
図２は、サーバ１およびクライアント端末３のモジュール構成図である。サーバ１およびクライアント端末３は、例えば、通常のコンピュータを利用したハードウェア構成を有している。すなわち、サーバ１およびクライアント端末３は、情報処理を行うＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１０１、ＢＩＯＳなどを記憶した読出し専用メモリであるＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１０２、各種データを書換え可能に記憶するＲＡＭ（Ｒ∧ｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１０３、各種データベースとして機能するとともに各種のプログラムを格納するＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）１０４、記憶媒体１１０を用いて情報を保管したり外部に情報を配布したり外部から情報を入手するためのＣＤ−ＲＯＭドライブ等の媒体駆動装置１０５、ネットワーク２を介して外部の他のコンピュータと通信により情報を伝達するための通信制御装置１０６、処理経過や結果等を操作者に表示するＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）やＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｉｓｔａｌ  Ｄｉｓｐｌａｙ）等の表示部１０７、並びに操作者がＣＰＵ１０１に命令や情報等を入力するためのキーボードやマウス等の入力部１０８等を備えた構成であり、これらの各部間で送受信されるデータをバスコントローラ１０９が調停して動作する。
【００１６】
このようなサーバ１およびクライアント端末３では、ユーザが電源を投入するとＣＰＵ１０１がＲＯＭ１０２内のローダーというプログラムを起動させ、ＨＤＤ１０４よりＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）というコンピュータのハードウェアとソフトウェアとを管理するプログラムをＲＡＭ１０３に読み込み、このＯＳを起動させる。このようなＯＳは、ユーザの操作に応じてプログラムを起動したり、情報を読み込んだり、保存を行ったりする。ＯＳのうち代表的なものとしては、Ｗｉｎｄｏｗｓ（登録商標）、ＵＮＩＸ（登録商標）等が知られている。これらのＯＳ上で動作するプログラムをアプリケーションプログラムと呼んでいる。なお、アプリケーションプログラムは、所定のＯＳ上で動作するものに限らず、後述の各種処理の一部の実行をＯＳに肩代わりさせるものであってもよいし、所定のアプリケーションソフトやＯＳなどを構成する一群のプログラムファイルの一部として含まれているものであってもよい。
【００１７】
ここで、サーバ１は、アプリケーションプログラムとして、構造化文書管理プログラムをＨＤＤ１０４に記憶している。この意味で、ＨＤＤ１０４は、構造化文書管理プログラムを記憶する記憶媒体として機能する。また、一般的には、サーバ１のＨＤＤ１０４にインストールされるアプリケーションプログラムは、ＣＤ−ＲＯＭやＤＶＤなどの各種の光ディスク、各種光磁気ディスク、フレキシブルディスクなどの各種磁気ディスク、半導体メモリ等の各種方式のメディア等の記憶媒体１１０に記録されて提供される。このため、ＣＤ−ＲＯＭ等の光情報記録メディアやＦＤ等の磁気メディア等の可搬性を有する記憶媒体１１０も、構造化文書管理プログラムを記憶する記憶媒体となり得る。さらには、構造化文書管理プログラムは、例えば通信制御装置１０６を介して外部から取り込まれ、ＨＤＤ１０４にインストールされてもよい。
【００１８】
サーバ１は、ＯＳ上で動作する構造化文書管理プログラムが起動すると、この構造化文書管理プログラムに従い、ＣＰＵ１０１が各種の演算処理を実行して各部を集中的に制御する。一方、クライアント端末３は、ＯＳ上で動作するアプリケーションプログラムが起動すると、このアプリケーションプログラムに従い、ＣＰＵ１０１が各種の演算処理を実行して各部を集中的に制御する。サーバ１およびクライアント端末３のＣＰＵ１０１が実行する各種の演算処理のうち、実施形態の構造化文書管理システムにおいて特徴的な処理について、以下に説明する。
【００１９】
図３は、本実施形態におけるサーバ１およびクライアント端末３の概略構成を示すブロック図である。図３に示すように、クライアント端末３は、アプリケーションプログラムにより実現される機能構成として、構造化文書登録部１１と、検索部１２とを備える。
【００２０】
構造化文書登録部１１は、入力部１０８から入力された構造化文書データやクライアント端末３のＨＤＤ１０４に予め記憶された構造化文書データを、後述するサーバ１の構造化文書データベース（構造化文書ＤＢ）２１に登録するためのものである。この構造化文書登録部１１は、登録すべき構造化文書データとともに格納要求をサーバ１に送信する。
【００２１】
図４〜図６は、構造化文書ＤＢに登録された構造化文書データの一例を示したものである。構造化文書データを記述するための代表的な言語としてＸＭＬ（Ｅｘｔｅｎｓｉｂｌｅ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）が挙げられる。図４〜図６に示す３つ構造化文書データは、ＸＭＬで記述されたものである。ＸＭＬでは、文書構造を構成する個々のパーツを「要素」（エレメント：Ｅｌｅｍｅｎｔ）と呼び、要素はタグ（ｔａｇ）を使って記述する。具体的には、要素の始まりを示すタグ（開始タグ）と、終わりを示すタグ（終了タグ）の２つのタグでデータを挟み込んで、１つの要素を表現している。なお、開始タグと終了タグで挟み込まれたテキストデータは、当該開始タグと終了タグで表された１つの要素に含まれるテキスト要素である。但し構造化文書の最上位にはタグとして記述されない文書要素が存在し、文書要素の下には必ず要素が１つだけ存在する。
【００２２】
図４に示す例では、構造化文書Ｄ１は文書要素の下に＜ｂｏｏｋ＞というタグで囲まれた要素が存在する。この＜ｂｏｏｋ＞要素は、ｙｅａｒ属性と、＜ｔｉｔｌｅ＞、＜ａｕｔｈｏｒ＞、＜ｓｅｃｔｉｏｎ＞の各タグで囲まれた複数の子要素を包含する。＜ｔｉｔｌｅ＞要素は、「Ｄａｔａ  Ｏｎ  Ｔｈｅ  Ｗｅｂ」などのテキスト要素をもつ。  ＜ａｕｔｈｏｒ＞要素は＜ｌａｓｔ＞、＜ｆｉｒｓｔ＞の順番で現れる２つの子要素を包含する。＜ｓｅｃｔｉｏｎ＞要素は複数の＜ｐ＞のタグで囲まれた子要素を包含する。
【００２３】
図５、図６に示す例も図４と同様の形で要素を持ち＜ａｕｔｈｏｒ＞要素や＜ｓｅｃｔｉｏｎ＞要素の数や要素が持つ値が異なるだけである。
【００２４】
図３に戻り、検索部１２は、ユーザにより入力部１０８から入力された指示に従って、構造化文書ＤＢ２１から所望のデータを検索するための検索条件などが記述されたクエリデータを作成し、当該クエリデータを含む検索要求をサーバ１へ送信する。また、検索部１２は、サーバ１から送信された当該検索要求に対応する結果データを受け取り、これを表示部１０７に表示する。
【００２５】
一方、サーバ１は、構造化文書管理プログラムにより実現される機能構成として、格納処理部２２と、検索処理部２３とを備える。また、サーバ１は、ＨＤＤ１０４などの記憶装置を利用した構造化文書ＤＢ２１を備える。
【００２６】
格納処理部２２は、クライアント端末３からの格納要求を受けて、クライアント端末３から送信された構造化文書データを構造化文書ＤＢ２１に格納する格納インタフェース部２４を備えている。
【００２７】
格納インタフェース部２４（構造化文書受付部）は、構造化文書データの入力を受け付けて、構造化文書データを構造化文書ＤＢ２１（構造化文書記憶部）に格納する。
【００２８】
検索処理部２３は、クライアント端末３からの検索要求を受けて、クエリデータにより指定された条件に合致するデータを構造化文書ＤＢ２１から探し出し、この探し出したデータを結果データとして返す処理を行う。この検索処理部２３は、検索インタフェース部２６と、構文解析部２７と、制約条件取得部２８と、構文解析木書換え部２９と、クエリ実行部３０を備えている。
【００２９】
検索インタフェース部２６は、クエリデータの入力を受け付けて（クエリデータ受付部）、受け付けたクエリデータの構文を解析して構文解析木３１を作成する構文解析部２７を呼び出す。
【００３０】
構文解析部２７は、クライアント端末３から送信され、検索インタフェース部２６を介して入力されたクエリデータ（以下、入力クエリデータという。）を構文解析し、１つの演算の単位を必ずＸＱｕｅｒｙにおけるｆｏｒ文またはｌｅｔ文の変数に代入するように入力クエリデータを分解して書き換えた構文解析木３１を生成する。すなわち、構文解析木３１とは、変数が一度のみ代入されるよう定義された静的単一代入となるように分解された構文である。
【００３１】
制約条件取得部２８は、制約条件取得部として機能するものであって、構文解析部２７で出力された構文解析木３１内において、構造化文書装置内の全ての構造化文書の文書要素の集合を指定する“／”を格納する変数を起点として、関連する全ての演算を辿り、構造化文書における階層条件を緩和した上で、各変数における制約条件３２を抽出して出力する。
【００３２】
構文解析木書換え部２９は、構文解析木書換え部として機能するものであって、制約条件取得部２８で出力された制約条件３２に基づいて、構文解析部２７で出力した構文解析木３１を書き換える。書き換えた構文解析木３１は入力クエリデータと同じくＸＱｕｅｒｙの文法に従った形で出力する。
【００３３】
クエリ実行部３０は、クエリ実行部として機能するものであって、構文解析木書換え部２９から出力された書換えクエリデータを構造化文書データのデータ集合に対して実行し、得られた結果データ３３を出力する。
【００３４】
検索インタフェース部２６は、クエリ実行部３０から出力された結果データを、検索の結果データとしてクライアント端末３へ返却する。
【００３５】
なお、本実施形態ではＸＱｕｅｒｙにより記述されたクエリデータで説明する。ＸＭＬでは、Ｗ３Ｃで提案されているＸＱｕｅｒｙという問合せ言語があり、ＸＱｕｅｒｙは基本的にＰｒｏｌｏｇ部と、それ以外のＦＬＷＯＲ（ｆｏｒ−ｌｅｔ−ｗｈｅｒｅ−ｏｒｄｅｒｂｙ−ｒｅｔｕｒｎ）という構文パターンで説明できる。以下に、ＸＱｕｅｒｙの言語仕様を説明する。Ｐｒｏｌｏｇ部は１つのＸＱｕｅｒｙの先頭に１つだけ存在し、ＸＱｕｅｒｙで共通して使用される宣言変数と宣言関数で構成される。宣言変数の構文は「ｄｅｃｌａｒｅ  ｖａｒｉａｂｌｅ  変数  ：＝  式」である。ＸＱｕｅｒｙ内のどこからでも参照可能という点を除き変数宣言は後述するｌｅｔ文と同じである。
【００３６】
宣言関数の構文は「ｄｅｃｌａｒｅ  ｆｕｎｃｔｉｏｎ  関数名（引数宣言）｛式｝」であり、引数宣言部には任意の数の変数と型を記述する。宣言関数はＸＱｕｅｒｙ内のどこからでも呼び出し可能である。ｆｏｒの構文は「ｆｏｒ  変数  ｉｎ  式」である。ｆｏｒ文は式を満足するシーケンスの要素を変数に代入してループするという意味を持つ。ここでシーケンスとはフラットなリストである。ｌｅｔの構文は「ｌｅｔ  変数  ：＝  式」である。ｌｅｔ文は１回のループ毎に、式を満足するシーケンスを格納する。ｗｈｅｒｅの構文は「ｗｈｅｒｅ  式」である。ｗｈｅｒｅ文はｆｏｒ文で繰り返されるループを制限するものであり式を満たさない場合はループをスキップする。
【００３７】
ｏｒｄｅｒｂｙの構文は「ｏｒｄｅｒ  ｂｙ  式」である。ｏｒｄｅｒｂｙ文はｆｏｒ−ｌｅｔ−ｗｈｅｒｅで得られた結果を式で指定されたキーでソートするものである。ｒｅｔｕｒｎの構文は「ｒｅｔｕｒｎ  式」である。ｒｅｔｕｒｎ文は変数を含む任意のＸＭＬデータを記述することができる。式にはＦＬＷＯＲ文を記述できる。
【００３８】
また、ｆｏｒ文やｌｅｔ文などの式に再びＦＬＷＯＲ文が記述された場合入れ子クエリと呼ぶ。変数の構文は「＄文字列」である。入れ子クエリなどで二重に宣言された場合を除き、同じ文字列を持つ変数は同一のものと見なされる。
【００３９】
ＸＭＬデータの要素間の階層条件を指定する演算として、ＸＱｕｅｒｙでは以下のようなものがある。
・“／”要素間は親子関係であることを示すオペレータ
・“／／”要素間は先祖子孫関係であることを示すオペレータ
なお、“／”や“／／”の左に何もない場合は、ＤＢやプログラム側がデフォルトで示すＸＭＬまたはＸＭＬ集合の文書要素が対象となる。本実施形態では構造化文書ＤＢの構造化文書集合を指している。
【００４０】
図７は、ＸＱｕｅｒｙのクエリデータの一例を示す説明図である。分かりやすくするため、図７の各行には［］で囲んだ行番号を振っている。図７は「姓が“Ｓｕｃｉｕ”で名が“Ｄａｎ”という著者であり、１９９９年以前に出版されたもののうち、本のタイトルと、著者名と、本の内容で“ＸＭＬ”が含まれた節と、を出せ」という意図であり、下記のようなクエリデータＱ１が示されている。
【００４１】
Ｑ１：［Ｌ１］は、ｆｏｒ文で構造化文書ＤＢ２１の各構造化文書データについて、文書要素の直下の階層にある「ｂｏｏｋ」という要素を取得して変数＄ｈに代入してループすることを示す。［Ｌ２］のｌｅｔ文は入れ子クエリになっており、［Ｌ３］〜［Ｌ７］のＦＬＷＯＲ文の結果を変数＄ｉに格納することを示している。［Ｌ３］は［Ｌ１］のループで代入された変数＄ｈに格納された要素に対して、その子要素である「ａｕｔｈｏｒ」という要素を取得して変数＄ｘに代入してループすることを示している。［Ｌ４］、［Ｌ５］は［Ｌ３］のループで代入された変数＄ｘに格納された要素に対して、その子要素である「ｌａｓｔ」、「ｆｉｒｓｔ」という要素を取得して変数＄ｕ、＄ｖに代入することを示している。［Ｌ６］はループ変数＄ｘに対応する変数＄ｕ、＄ｖについて、変数＄ｕの持つ値が“Ｓｕｃｉｕ”に等しく、＄ｖの持つ値が“Ｄａｎ”に等しいもののみをループさせる。［Ｌ７］は［Ｌ６］を満たした＄ｘのみを返却することを示している。
【００４２】
［Ｌ８］は［Ｌ２］と同様のｌｅｔ文は入れ子クエリになっており、［Ｌ９］〜［Ｌ１１］のＦＬＷＯＲ文の結果を変数＄ｊに格納することを示している。［Ｌ９］は［Ｌ１］のループで代入された変数＄ｈに格納された要素に対して、その子要素である「ｓｅｃｔｉｏｎ」という要素の子要素である「ｐ」という要素を取得して変数＄ａに代入してループする。［Ｌ１０］はループ変数＄ａに対して、変数＄ａの持つ値に“ＸＭＬ”という値が含まれるもののみをループさせることを示している。［Ｌ１１］は［Ｌ１０］を満たした＄ａのみを返却することを示している。
【００４３】
［Ｌ１２］と［Ｌ１３］はｌｅｔ文であり、変数＄ｈに格納された要素に対して、属性である“ｙｅａｒ”と、子要素である「ｔｉｔｌｅ」という要素を取得して、各々変数＄ｋ、＄ｌにシーケンスとして代入することを示している。［Ｌ１４］はループ変数＄ｈに対応する変数＄ｉ、＄ｋについて、変数＄ｉのシーケンスに要素が存在し、かつ＄ｋの持つ数値が１９９９より等しいか小さいもののみをループさせることを示している。［Ｌ１５］はこれまで求めた＄ｌ、＄ｉ、＄ｊの３つの変数の指す値を＜ｉｔｅｍ＞で始まるＸＭＬの指定位置に埋め込んで新たなＸＭＬを生成し、結果として返却することを示している。
【００４４】
図８は、サーバ１の検索処理部２３による検索処理の流れを示すフローチャートである。まず、検索インタフェース部２６は、クライアント端末３からネットワーク２経由で送信されたクエリデータの入力を受け付ける（ステップＳ１）。
【００４５】
次に、構文解析部２７は、入力クエリデータについての構文を解析し、構文解析木を生成する（ステップＳ２）。構文解析では、クエリデータを構成する各要素が、ＸＱｕｅｒｙを構成する全ての演算を１演算単位でｆｏｒ文またはｌｅｔ文に格納するように分解される。またｗｈｅｒｅ、ｏｒｄｅｒｂｙ、ｒｅｔｕｒｎ文は１つの変数のみを入力とするように書き換えられる。
【００４６】
但し、式の先頭が“／”または“／／”で開始される構造条件の場合、先頭の“／”または“／／”のみを式として格納するｌｅｔ文（以降、起点文と呼ぶ）と、そのｌｅｔ文の出力変数を入力変数とする式に分解される。また先頭が“変数”であり後続に“／”または“／／”で指定される階層条件が連続して並ぶ場合は、１つの演算としてまとめてｆｏｒ文、またはｌｅｔ文に格納される。さらに、入れ子クエリが存在した場合、入れ子クエリのＦＬＷＯＲ文で記述された宣言関数がＸＱｕｅｒｙのＰｒｏｌｏｇ部で記述され、記述された宣言関数の関数を、入れ子クエリに渡されていた親クエリの変数を引数にする形で元場所に記述した関数呼び出しの形に書き換えられる。
【００４７】
図９は図７のクエリデータに対して構文解析部２７によって構文解析を実施した結果である。［Ｌ１］から［Ｌ２７］の２７行で記述されている。図９の［Ｌ１］〜［Ｌ１０］は図７における［Ｌ３］〜［Ｌ７］の入れ子クエリを宣言関数ｕｄｆ１として切り出したものである。図７における［Ｌ３］の変数＄ｈは入れ子クエリの親クエリにおけるｆｏｒ文［Ｌ１］で代入された変数であるため宣言関数では引数入力変数＄ｈ１としている。
【００４８】
構文解析では１演算単位で切り出してｌｅｔ文に格納し、ｗｈｅｒｅ文には変数のみを入力するように書き換えるため、図７における［Ｌ６］は図９において［Ｌ５］〜［Ｌ８］に書き換えられる。
【００４９】
また、図９の［Ｌ１１］〜［Ｌ１６］は図７における［Ｌ９］〜［Ｌ１１］の入れ子クエリを宣言関数ｕｄｆ２として切り出したものである。構文解析ではｗｈｅｒｅ文には変数のみを入力するように書き換えるため、図７における［Ｌ１０］は図９において［Ｌ１３］〜［Ｌ１４］に書き換えられる。
【００５０】
図９の［Ｌ１７］〜［Ｌ１８］は図７における［Ｌ１］を先頭の“／”を単独でｌｅｔ文として切り出して変数＄ｇに代入する起点文と、後続の式の残りの部分を、変数＄ｇを入力とするｆｏｒ文に分解したものである。図９における［Ｌ１９］及び［Ｌ２０］は図７における［Ｌ２］及び［Ｌ８］に該当し、各々入れ子クエリを宣言関数として切り出したｕｄｆ１、ｕｄｆ２として呼び出す形になっている。
【００５１】
図９における［Ｌ２３］、［Ｌ２４］、及び［Ｌ２６］は図７における［Ｌ１４］を書き換えたものであり、１つの演算単位にｌｅｔ文に分解され、ｗｈｅｒｅ文は入力変数のみとなっている。図９における［Ｌ２５］及び［Ｌ２７］は図７における［Ｌ１５］に該当し、ｒｅｔｕｒｎ文は変数のみになり、ＸＭＬを生成する式はｌｅｔ文として書き換えられている。
【００５２】
構文解析部２７による構文解析処理が終了すると、次に、制約条件取得部２８は、構文解析部２７の処理結果を解析し、構造化文書における階層条件を緩和した上で、各変数における制約条件を取得する（ステップＳ４）。
【００５３】
ここで制約条件とは、その変数が満たす必要がある条件の全部、または一部を並べたものである。本実施形態ではある変数に関してその変数に格納される要素が含まれる文書集合が満たすべき条件を、制約条件として記述する。例えば、変数にＢｏｏｌ型の値が格納される場合は、その値がＴＲＵＥになるために必要な条件を記述する。
【００５４】
その際に複数の条件が並べられた際に、制約条件取得部２８は、各条件間における構造化文書内の階層条件の依存関係を無視した形に条件を緩和する。例えば、制約条件を構成する２つの条件で出現する構造条件／Ａ／Ｂ／Ｃ、／Ａ／Ｂ／Ｄが、／Ａ／Ｂで指定された要素集合内の同一のＢに対する子要素Ｃ及びＤである場合に、この条件を緩和して同じ要素名を持つものの、異なるＢの要素に対する子要素Ｃ及びＤも成立するように条件を緩和する。これにより制約条件だけでは、本来対象外となる文書も含まれることになるが、それについてはＸＭＬの要素ＩＤを利用した演算により解消する。
【００５５】
図１０は、制約条件取得の流れを示すフローチャートである。制約条件取得部２８は、はじめに、入力として与えられた構文解析木から、全ての起点文（ｌｅｔの文）を取得し、起点文の出力変数を抜き出してリストＲに格納する。次に、制約条件取得部２８は、最終出力となる制約条件のリストＣＡ、書換え対象リストＦＡ、パス情報のリストＰを用意する。ここでパス情報とはその変数が示す要素を“／”または“／／”から始まる１つまたは複数の構造条件のみで示したものである（ステップＳ２１）。
【００５６】
次に、制約条件取得部２８は、ステップＳ２１で取得した要素をチェックして、出力変数のリストＲが空かを判定する（ステップＳ２２）。
【００５７】
出力変数のリストＲが空でなかった場合（ステップＳ２２：Ｎｏ）、制約条件取得部２８は、出力変数のリストＲから先頭の要素である変数＄ｒを取得してリストから削除した後、＄ｒをリストＬに挿入する。さらに＄ｒのパス情報をパス情報リストＰに挿入する。（ステップＳ２３）。
【００５８】
次に制約条件取得部２８は、リストＬ、及びパス情報リストＰを入力として演算の入力から出力への制約条件取得処理を実施し、制約条件を格納するリストＣ、制約条件取得対象変数リストＴ、リストＴの変数のうち、ｗｈｅｒｅ文の入力となる変数を格納するリストＷ、リストＴの変数のパス情報を格納するリストＰを出力する（ステップＳ２４）。
【００５９】
ステップ２４の処理については図１１のフローチャートで詳細を記述する。次にステップＳ２４の処理で取得した４つのリストＣ、Ｔ、Ｗ、Ｐを入力として、制約条件取得部２８は、出力から入力への制約条件取得処理を実施し、書換え対象変数リストＦ、制約情報リストＣ、パス情報リストＰを出力する（ステップＳ２５）。
【００６０】
ステップ２５の処理については図１２のフローチャートで詳細を記述する。次に制約条件取得部２８は、ステップＳ２５で得られた制約情報リストＣとパス情報リストＰ内の各要素を各々制約条件のリストＣＡ、ＦＡに挿入する（ステップＳ２６）。次に再びステップ２２に戻り処理を繰り返す。
【００６１】
一方、ステップＳ２２の判定で出力変数のリストＲが空だった場合（ステップＳ２２がＹｅｓ）、制約条件取得部２８は、これまでの処理で取得した制約条件のリストＣＡ、ＰＡ、パス情報リストＰを出力して制約条件取得処理を終了する。
【００６２】
図１１は、図１０のステップ２４で実施する入力から出力への制約条件取得処理の流れを示すフローチャートである。入力から出力への制約条件取得処理でははじめに、制約条件取得部２８は、図１０のステップ２３で取得したリストＬ、パス情報リストＰを入力として受け取り、出力用の空のリストとして、ステップＳ２４で説明した３つの制約条件のリストＣ、制約条件取得対象変数リストＴ、リストＴの変数のうち、ｗｈｅｒｅ文の入力となる変数を格納するリストＷと、ＦＬＷＯＲ文を格納するリストＮを用意する（ステップＳ３１）。次に、制約条件取得部２８は、Ｌが空かを判定する（ステップＳ３２）。
【００６３】
入力されたリストＬが空でなかった場合（ステップＳ３２：Ｎｏ）、制約条件取得部２８は、Ｌの最後尾の要素である変数＄ｌを取得してリストから削除する（ステップＳ３３）。次に、制約条件取得部２８は、＄ｌが制約条件取得対象変数リストＴに存在するかを判定する（ステップＳ３４）。
【００６４】
＄ｌが制約条件取得対象変数リストＴに存在しない場合（ステップＳ３２：Ｎｏ）、制約条件取得部２８は、数＄ｌを入力とするｆｏｒ、ｌｅｔ、ｗｈｅｒｅ、ｏｒｄｅｒｂｙ、ｒｅｔｕｒｎ文リストＮを取得する（ステップＳ３５）。次に、制約条件取得部２８は、文リストＮが空かを判定する（ステップＳ３６）。
【００６５】
Ｎが空でなかった場合（ステップＳ３６：Ｙｅｓ）、制約条件取得部２８は、Ｎの先頭の要素である文ｎを取得してリストから削除し、文ｎの出力変数＄ｐを取得する（ステップＳ３７）。次に、制約条件取得部２８は、文ｎが構造条件Ｋであるかを判定する（ステップＳ３８）。
【００６６】
文ｎが構造条件の場合（ステップＳ３８：Ｙｅｓ）、制約条件取得部２８は、＄ｐの制約条件Ｃ（＄ｐ）に＄ｌの制約条件Ｃ（＄ｌ）を条件として追加する。次に制約条件取得部２８は、構造条件ＫとリストＰから＄ｐのパス情報をリストＰに追加する。さらに＄ｐをＬとＴに追加する（ステップＳ４４）。次に制約条件取得部２８は、ステップＳ３６に戻り引き続き処理を続行する。
【００６７】
一方、文ｎが構造条件ではない場合（ステップＳ３８：Ｎｏ）、制約条件取得部２８は、文ｎが宣言関数の呼び出しかを判定する（ステップＳ３９）。
【００６８】
文ｎが宣言関数の呼び出しの場合（ステップＳ３９：Ｙｅｓ）、制約条件取得部２８は、＄ｌの引数の位置と同じ宣言関数の引数＄ｉを取得し、＄ｉの制約条件Ｃ（＄ｉ）に＄ｌの制約条件Ｃ（＄ｌ）を条件として追加する。次に制約条件取得部２８は、＄ｉをＬとＴに追加する（ステップＳ４５）。次に制約条件取得部２８は、ステップＳ３６に戻り引き続き処理を続行する。
【００６９】
一方、ステップＳ３９の判定で文ｎが宣言関数の呼び出しではない場合（ステップＳ３９：Ｎｏ）、制約条件取得部２８は、文ｎが定数値と＄ｌとの比較関数かを判定する（ステップＳ４０）。
【００７０】
文ｎが比較関数の場合（ステップＳ４０：Ｙｅｓ）、制約条件取得部２８は、＄ｐの制約条件Ｃ（＄ｐ）に＄ｌの制約条件Ｃ（＄ｌ）と比較式の制約条件Ｃ（比較式）を条件として追加する。次に制約条件取得部２８は、＄ｐをＬとＴに追加する（ステップＳ４６）。次に制約条件取得部２８は、ステップＳ３６に戻り引き続き処理を続行する。
【００７１】
一方、ステップＳ４０の判定で文ｎが比較関数ではない場合（ステップＳ４０：Ｎｏ）、制約条件取得部２８は、文ｎがａｎｄ演算かを判定する（ステップＳ４１）。
【００７２】
文ｎがａｎｄ演算の場合（ステップＳ４１：Ｙｅｓ）、制約条件取得部２８は、＄ｐをＬとＴに追加する（ステップＳ４７）。次に制約条件取得部２８は、ステップＳ３６に戻り引き続き処理を続行する。
【００７３】
一方、ステップＳ４１の判定で文ｎがａｎｄ演算ではない場合（ステップＳ４１：Ｎｏ）、制約条件取得部２８は、文ｎが宣言関数内のｒｅｔｕｒｎ文かを判定する（ステップＳ４２）。
【００７４】
文ｎが宣言関数内のｒｅｔｕｒｎ文の場合（ステップＳ４２：Ｙｅｓ）、制約条件取得部２８は、宣言関数の呼び出し元の文の出力変数＄ｕを取得し、＄ｕの制約条件Ｃ（＄ｕ）にＣ（＄ｌ）を追加する。次に＄ｕをＬとＴに追加する（ステップＳ４８）。次に制約条件取得部２８は、ステップＳ３６に戻り引き続き処理を続行する。
【００７５】
一方、ステップＳ４２の判定で文ｎが宣言関数内のｒｅｔｕｒｎ文ではない場合（ステップＳ４２：Ｎｏ）、制約条件取得部２８は、文ｎがｗｈｅｒｅ文かを判定する（ステップＳ４３）。
【００７６】
文ｎがｗｈｅｒｅ文の場合（ステップＳ４３：Ｙｅｓ）、制約条件取得部２８は、＄ｌをＷに追加する（ステップＳ４９）。次にステップＳ３６に戻り引き続き処理を続行する。
【００７７】
一方、ステップＳ４３の判定で文ｎがｗｈｅｒｅ文ではない場合（ステップＳ４３：Ｎｏ）、制約条件取得部２８は、ステップＳ３６に戻り引き続き処理を続行する。
【００７８】
一方、ステップＳ３６の判定でＮが空の場合（ステップＳ３６：Ｙｅｓ）、制約条件取得部２８は、ステップＳ３２に戻り引き続き処理を続行する。
【００７９】
一方、ステップＳ３４の判定で＄ｌがＴに存在する場合（ステップＳ３４：Ｙｅｓ）、制約条件取得部２８は、ステップＳ３２に戻り引き続き処理を続行する。
【００８０】
一方、ステップＳ３２の判定でＬが空だった場合（ステップＳ３２がＹｅｓ）、制約条件取得部２８は、これまでの処理で取得したＣ、Ｔ、Ｗ、Ｐを出力して上位から下位への制約条件取得処理を終了する。
【００８１】
図１２は、図１０のステップＳ２５で実施する出力から入力への制約条件取得処理の流れを示すフローチャートである。出力から入力への制約条件取得処理でははじめに、制約条件取得部２８は、入力として図１０のステップＳ２４で取得したリストＣ、Ｔ、Ｗ、Ｐを入力として受け取り、出力用の空のリストとしてステップＳ２５で説明したリストＦと、内部でのみ使用する式の入力変数リストＶを用意する（ステップＳ７１）。次に、制約条件取得部２８は、Ｗが空かを判定する（ステップＳ７２）。
【００８２】
Ｗが空でなかった場合（ステップＳ７２：Ｎｏ）、制約条件取得部２８は、Ｗの最後尾の要素である変数＄ｗを取得してリストから削除し、＄ｗを出力とするＦＬＷＯＲ文ｎと文ｎの入力変数のリストＶを取得する。（ステップＳ７３）。次に、制約条件取得部２８は、Ｖが空か、または文ｎが存在しないかを判定する（ステップＳ７４）。
【００８３】
Ｖが空でもなく、かつ文ｎが存在する場合（ステップＳ７４：Ｎｏ）、制約条件取得部２８は、文ｎがａｎｄ演算かを判定する（ステップＳ７５）。
【００８４】
文ｎがａｎｄ演算の場合（ステップＳ７５：Ｙｅｓ）、制約条件取得部２８は、ａｎｄ演算の２つの入力変数＄ｖ１、＄ｖ２を取得する（ステップＳ８１）。次に制約条件取得部２８は、＄ｖ１がＴに存在するかを判定する（ステップＳ８２）。
【００８５】
＄ｖ１がＴに存在する場合（ステップＳ８２：Ｙｅｓ）、制約条件取得部２８は、＄ｖ１をＷに追加する（ステップＳ８３）。次に＄ｖ２がＴに存在するかを判定する（ステップＳ８４）。
【００８６】
＄ｖ２がＴに存在する場合（ステップＳ８４：Ｙｅｓ）、制約条件取得部２８は、＄ｖ２をＷに追加する（ステップＳ８５）。次に制約条件取得部２８は、Ｖから＄ｖ１、＄ｖ２を削除する（ステップＳ８６）。次に制約条件取得部２８は、ステップＳ７２に戻り引き続き処理を続行する。
【００８７】
一方、＄ｖ２がＴに存在しない場合（ステップＳ８４：Ｎｏ）、制約条件取得部２８は、ステップＳ７２に戻り引き続き処理を続行する。
【００８８】
一方、＄ｖ１がＴに存在しない場合（ステップＳ８２：No）、制約条件取得部２８は、ステップＳ７２に戻り引き続き処理を続行する。
【００８９】
一方、ステップＳ７５の文ｎがａｎｄ演算ではない場合（ステップＳ７５：Ｎｏ）、制約条件取得部２８は、Ｖの先頭の変数＄ｉを取得しＶから削除する（ステップＳ７６）。次に制約条件取得部２８は、＄ｉがＴに存在するかを判定する（ステップＳ７７）。
【００９０】
＄ｉがＴに存在する場合（ステップＳ７７：Ｙｅｓ）、制約条件取得部２８は、＄ｉの制約条件Ｃ（＄ｉ）に＄ｗの制約条件Ｃ（＄ｗ）の内容を展開して追加する。次に制約条件取得部２８は、＄ｉをＷに追加する（ステップＳ７８）。次に制約条件取得部２８は、＄ｉが起点文の出力変数、または宣言関数の入力変数かを判定する（ステップＳ７９）。
【００９１】
＄ｉが起点文の出力変数、または宣言関数の入力変数の場合（ステップＳ７９：Ｙｅｓ）、制約条件取得部２８は、＄ｗをＦに追加する（ステップＳ８０）。次に制約条件取得部２８は、ステップＳ７４に戻り引き続き処理を続行する。
【００９２】
一方、ステップＳ７９の判定で＄ｉが起点文の出力変数ではなく、かつ宣言関数の入力変数でもない場合（ステップＳ７９：Ｎｏ）、制約条件取得部２８は、ステップＳ７４に戻り引き続き処理を続行する。
【００９３】
一方、ステップＳ７７の判定で＄ｉがＴに存在しない場合（ステップＳ７７：Ｎｏ）、制約条件取得部２８は、ステップＳ７４に戻り引き続き処理を続行する。
【００９４】
一方、ステップＳ７４の判定でＶが空または文ｎが存在しない場合（ステップＳ７４：Ｙｅｓ）、制約条件取得部２８は、ステップＳ７２に戻り引き続き処理を続行する。
【００９５】
一方、ステップＳ７２の判定でＷが空の場合（ステップＳ７２：Ｙｅｓ）、制約条件取得部２８は、Ｆ内の各変数＄ｆに関する制約条件Ｃ（＄ｆ）について、条件から比較条件以外がなくなるまで、制約条件を展開する（ステップＳ８７）。次に制約条件取得部２８は、これまでの処理で取得したＣ，Ｆ、Ｐを出力して下位から上位への制約条件取得処理を終了する。
【００９６】
ここで、図９に例示した構文解析結果を用いて、制約条件取得処理を行った場合の処理の概要を、図１０〜図１５を参照して説明する。
【００９７】
制約条件取得部２８は、はじめに入力として図９の構文解析結果を受け取り、全ての文を探索して図９の［Ｌ１７］を起点文として取得し、出力変数＄ｇをリストＲに格納する。次に制約条件取得部２８は、空のリストＣＡ、ＦＡ、Ｐを用意する（ステップＳ２１）。次に制約条件取得部２８は、リストＲから先頭の要素である＄ｇ（＝変数＄ｒ）を取り出してＲから削除し、＄ｇをチェックリストＬに格納する。さらに制約条件取得部２８は、＄ｇのパス情報Ｐ（＄ｇ）＝／をリストＰに格納する（ステップＳ２２、Ｓ２３）。次にチェックリストＬとパス情報Ｐを入力として、入力から出力への制約条件取得処理を行う（ステップＳ２４）。
【００９８】
ここでステップＳ２４について図１１を用いて詳細に述べる。はじめに制約条件取得部２８は、入力として＄ｇが格納されたリストＬと、Ｐ（＄ｇ）の情報が格納されたパス情報Ｐを入力として受け取り、空リストとしてＣ、Ｔ、Ｗ、Ｎを用意する（ステップＳ３１）。
【００９９】
次に制約条件取得部２８は、チェックリストＬから変数＄ｇが取り出されて削除され、＄ｇがＴに存在しないため＄ｇを入力とする文［Ｌ１８］がＮに格納される（ステップＳ３２〜Ｓ３５）。
【０１００】
次に制約条件取得部２８は、文［Ｌ１８］がＮから取得されて削除され、出力変数＄ｈが取得される（ステップＳ３６、Ｓ３７）。次に制約条件取得部２８は、［Ｌ１８］が階層構造を指定する構造条件であるためＣ（＄ｈ）にＣ（＄ｇ）を追加し、［Ｌ１８］の構造条件＄ｇ／ｂｏｏｋとＰ（＄ｇ）＝／から＄ｈのパス情報Ｐ（＄ｈ）＝／ｂｏｏｋとしてＰに格納する。さらに制約条件取得部２８は、＄ｈをＬとＴに格納する（ステップＳ３８、Ｓ４４）。
【０１０１】
次に、制約条件取得部２８は、Ｎが空なためチェックリストＬから＄ｈを取り出して削除し、＄ｈを入力とする文であるＬ１９〜Ｌ２２を取得してＮに格納する（ステップＳ３６、Ｓ３２〜Ｓ３５）。次に制約条件取得部２８は、Ｎの先頭のＬ１９が宣言関数の呼び出しであるため、＄ｈに該当する宣言関数の引数変数＄ｈ１を取得して、＄ｈ１の制約条件Ｃ（＄ｈ１）に＄ｈの制約条件Ｃ（＄ｈ）を追加する。さらに制約条件取得部２８は、＄ｈ１をＬとＴに追加する（ステップＳ３６〜Ｓ３９、Ｓ４５）。
【０１０２】
次に制約条件取得部２８は、Ｎの先頭のＬ２０が宣言関数の呼び出しであるため、＄ｈに該当する宣言関数の引数変数＄ｈ２を取得して、＄ｈ２の制約条件Ｃ（＄ｈ２）に＄ｈの制約条件Ｃ（＄ｈ）を追加する。さらに制約条件取得部２８は、＄ｈ２をＬとＴに追加する（ステップＳ３６〜Ｓ３９、Ｓ４５）。
【０１０３】
次に制約条件取得部２８は、Ｎの先頭のＬ２１が構造条件であるためＣ（＄ｋ）にＣ（＄ｈ）を追加し、［Ｌ２１］の構造条件＄ｈ／＠ｙｅａｒとＰ（＄ｈ）からパス情報Ｐ（＄ｋ）＝／ｂｏｏｋ／＠ｙｅａｒをＰに格納する。さらに制約条件取得部２８は、＄ｋをＬとＴに格納する（ステップＳ３６〜Ｓ３８、Ｓ４４）。
【０１０４】
次に制約条件取得部２８は、Ｎの先頭のＬ２２が構造条件であるためＣ（＄ｌ）にＣ（＄ｈ）を追加し、パス情報Ｐ（＄ｌ）＝／ｂｏｏｋ／ｔｉｔｌｅをＰに格納する。さらに制約条件取得部２８は、＄ｌをＬとＴに格納する（ステップＳ３６〜Ｓ３８，Ｓ４４）。
【０１０５】
次に制約条件取得部２８は、Ｎが空なためＬから変数＄ｌを取得して、＄ｌを入力とする文Ｌ２５を取得してＮに格納する（ステップＳ３６、Ｓ３２〜Ｓ３５）。次に制約条件取得部２８は、Ｎの先頭のＬ２５がステップＳ３７〜Ｓ４３のいずれの条件も満たさないため、再びＬから変数＄ｋを取得して＄ｋを削除し、＄ｋを入力とする文Ｌ２３を取得してＮに格納する（ステップＳ３６〜Ｓ４３、Ｓ３６、Ｓ３２〜Ｓ３５）。
【０１０６】
次に制約条件取得部２８は、Ｎの先頭のＬ２３が比較式であるため、Ｌ２３の出力変数＄ｍの制約条件に変数＄ｋの制約条件Ｃ（＄ｋ）∧（＄ｋ＜＝１９９９）を追加する。さらに制約条件取得部２８は、＄ｍをＬとＴに追加する（ステップＳ３６〜Ｓ４０、Ｓ４６）。
【０１０７】
次に制約条件取得部２８は、Ｎが空なためＬから＄ｍを取得して、＄ｍを入力とする文Ｌ２４を取得してＮに格納する（ステップＳ３６、Ｓ３２〜Ｓ３５）。
【０１０８】
次に制約条件取得部２８は、Ｎの先頭のＬ２４がａｎｄ演算であるため出力変数＄ｎをＬとＴに追加する（ステップＳ３６〜Ｓ４１、Ｓ４７）。
【０１０９】
次に制約条件取得部２８は、Ｎが空なためＬから＄ｎを取得して、＄ｎを入力とする文Ｌ２６を取得してＮに格納する（ステップＳ３６、Ｓ３２〜Ｓ３５）。次にＬ２６がｗｈｅｒｅ文であるため＄ｎをＷに追加する（ステップＳ３６〜Ｓ４３、Ｓ４９）。
【０１１０】
次に制約条件取得部２８は、Ｎが空なためＬから＄ｈ２を取得して、＄ｈ２を入力とする文Ｌ１２を取得してＮに格納する（ステップＳ３６、Ｓ３２〜Ｓ３５）。次に制約条件取得部２８は、Ｎの先頭のＬ１２が構造条件であるため出力変数＄ａの制約条件Ｃ（＄ａ）にＣ（＄ｈ２）を追加し、パス情報Ｐ（＄ａ）＝／ｂｏｏｋ／ｓｅｃｔｉｏｎ／ｐをＰに格納する。さらに制約条件取得部２８は、＄ａをＬとＴに格納する（ステップＳ３６〜Ｓ３８，Ｓ４４）。
【０１１１】
次に制約条件取得部２８は、Ｎが空のためＬから変数＄ａを取得し、＄ａを入力とする文Ｌ１３、Ｌ１５を取得する（ステップＳ３６、Ｓ３２〜Ｓ３５）。制約条件取得部２８は、Ｎの先頭の要素Ｌ１３が比較式であるため、Ｌ１３の出力変数＄ｂの制約条件に変数＄ａの制約条件Ｃ（＄ａ）∧（Ｃｏｎｔａｉｎｓ（＄ａ，“ＸＭＬ”））を追加する。さらに制約条件取得部２８は、＄ｂをＬとＴに追加する（ステップＳ３６〜Ｓ４０、Ｓ４６）。
【０１１２】
次に制約条件取得部２８は、Ｎの先頭要素Ｌ１５が宣言関数のｒｅｔｕｒｎ文であるため、呼び出し元の文Ｌ２０の出力変数＄ｊを取得し、＄ｊの制約条件Ｃ（＄ｊ）にＣ（＄ａ）を追加する。次に制約条件取得部２８は、ＬとＴに＄ｊを追加する（ステップＳ３６〜Ｓ４２、Ｓ４８）。
【０１１３】
次に制約条件取得部２８は、Ｎが空のためＬから変数＄ｊを取得し、＄ｊを入力とする文Ｌ２５を取得する（ステップＳ３６、Ｓ３２〜Ｓ３５）。次に制約条件取得部２８は、Ｎの先頭のＬ２５がステップＳ３７〜Ｓ４３のいずれの条件も満たさないため、再びＬから変数＄ｂを取得して削除し、＄ｂを入力とする文Ｌ１４を取得する（ステップＳ３６〜Ｓ４３、Ｓ３６、Ｓ３２〜Ｓ３５）。次に制約条件取得部２８は、Ｌ１４がｗｈｅｒｅ文であるため＄ｂをＷに追加する（ステップＳ３６〜Ｓ４３、Ｓ４９）。
【０１１４】
次に制約条件取得部２８は、Ｎが空のためＬから変数＄ｈ１を取得し、＄ｈ１を入力とする文Ｌ２を取得してＮに格納する（ステップＳ３６、Ｓ３２〜Ｓ３５）。次に制約条件取得部２８は、Ｎの先頭のＬ２が構造条件であるため出力変数＄ｘの制約条件Ｃ（＄ｘ）にＣ（＄ｈ１）を追加し、パス情報Ｐ（＄ｘ）＝／ｂｏｏｋ／ａｕｔｈｏｒをＰに格納する。さらに制約条件取得部２８は、＄ｘをＬとＴに格納する（ステップＳ３６〜Ｓ３８，Ｓ４４）。
【０１１５】
次に制約条件取得部２８は、Ｎが空のためＬから変数＄ｘを取得して削除し、＄ｘを入力とする文Ｌ３、Ｌ４、Ｌ９を取得する（ステップＳ３６、Ｓ３２〜Ｓ３５）。
【０１１６】
次に制約条件取得部２８は、Ｎの先頭のＬ３が構造条件であるため出力変数＄ｕの制約条件Ｃ（＄ｕ）にＣ（＄ｘ）を追加し、パス情報Ｐ（＄ｕ）＝／ｂｏｏｋ／ａｕｔｈｏｒ／ｌａｓｔをＰに格納する。さらに制約条件取得部２８は、＄ｕをＬとＴに格納する（ステップＳ３６〜Ｓ３８，Ｓ４４）。
【０１１７】
次に制約条件取得部２８は、Ｎの先頭のＬ４が構造条件であるため出力変数＄ｖの制約条件Ｃ（＄ｖ）にＣ（＄ｘ）を追加し、パス情報Ｐ（＄ｖ）＝／ｂｏｏｋ／ａｕｔｈｏｒ／ｆｉｒｓｔをＰに格納する。さらに制約条件取得部２８は、＄ｖをＬとＴに格納する（ステップＳ３６〜Ｓ３８，Ｓ４４）。
【０１１８】
次に制約条件取得部２８は、Ｎの先頭のＬ９が宣言関数のｒｅｔｕｒｎ文であるため、呼び出し元の文Ｌ１９の出力変数＄ｉを取得し、＄ｉの制約条件Ｃ（＄ｉ）にＣ（＄ｘ）を追加する。次に制約条件取得部２８は、ＬとＴに＄ｉを追加する（ステップＳ３６〜Ｓ４２、Ｓ４８）。
【０１１９】
次に制約条件取得部２８は、Ｎが空のためＬから変数＄ｉを取得し、＄ｉを入力とする文Ｌ２４を取得する（ステップＳ３６、Ｓ３２〜Ｓ３５）。次に制約条件取得部２８は、Ｌ２４がａｎｄ演算であるため出力変数＄ｎをＬとＴに追加する（ステップＳ３６〜Ｓ４１、Ｓ４７）。
【０１２０】
次に制約条件取得部２８は、Ｎが空なためＬから＄ｎを取得して削除する。制約条件取得部２８は、＄ｎをＴに存在するため、再びＬに戻り、Ｌから＄ｖを取得して削除し、＄ｖを入力とする文Ｌ６を取得してＮに格納する（ステップＳ３６、Ｓ３２〜Ｓ３４、Ｓ３２〜Ｓ３５）。
【０１２１】
次に制約条件取得部２８は、Ｎの先頭の要素Ｌ６が比較式であるため、Ｌ６の出力変数＄ｚの制約条件に変数＄ｖの制約条件Ｃ（＄ｖ）∧（＄ｖ＝“Ｄａｎ”）を追加する。さらに制約条件取得部２８は、＄ｚをＬとＴに追加する（ステップＳ３６〜Ｓ４０、Ｓ４６）。
【０１２２】
次に制約条件取得部２８は、Ｎが空のためＬから変数＄ｚを取得し、＄ｚを入力とする文Ｌ７を取得する（ステップＳ３６、Ｓ３２〜Ｓ３５）。次に制約条件取得部２８は、Ｌ７がａｎｄ演算であるため出力変数＄ｗをＬとＴに追加する（ステップＳ３６〜Ｓ４１、Ｓ４７）。
【０１２３】
次に制約条件取得部２８は、Ｎが空のためＬから変数＄ｗを取得し、＄ｗを入力とする文Ｌ８を取得する（ステップＳ３６、Ｓ３２〜Ｓ３５）。次に制約条件取得部２８は、Ｌ８がｗｈｅｒｅ文であるため＄ｚをＷに追加する（ステップＳ３６〜Ｓ４３、Ｓ４９）。
【０１２４】
次に制約条件取得部２８は、Ｎが空のためＬから変数＄ｕを取得し、＄ｕを入力とする文Ｌ５を取得する（ステップＳ３６、Ｓ３２〜Ｓ３５）。次に制約条件取得部２８は、Ｎの先頭の要素Ｌ５が比較式であるため、Ｌ５の出力変数＄ｙの制約条件に変数＄ｕの制約条件Ｃ（＄ｕ）∧（＄ｕ＝“Ｓｕｃｉｕ”）を追加する。さらに制約条件取得部２８は、＄ｙをＬとＴに追加する（ステップＳ３６〜Ｓ４０、Ｓ４６）。
【０１２５】
次に制約条件取得部２８は、Ｎが空のためＬから変数＄ｙを取得して削除し、＄ｙを入力とする文Ｌ７を取得する（ステップＳ３６、Ｓ３２〜Ｓ３５）。次に制約条件取得部２８は、Ｌ７がａｎｄ演算であるため出力変数＄ｗをＬとＴに追加する（ステップＳ３６〜Ｓ４１、Ｓ４７）。
【０１２６】
次に制約条件取得部２８は、Ｎが空なためＬから＄ｗを取得して削除する。＄ｗがＴに存在するため、再びＬに戻る（ステップＳ３６、Ｓ３２〜Ｓ３４）。次に制約条件取得部２８は、Ｌが空であるため入力から出力への制約条件取得処理を終了する。制約条件取得部２８は、変数＄ｎ、＄ｂ、＄ｗを含むリストＷと、図１３に示す制約情報リストＣ、図１４に示すパス情報リストＰ、図１５に示す制約条件取得対象変数リストＴを出力し図１０のステップＳ２４に戻る。
【０１２７】
次に制約条件取得部２８は、Ｗ、Ｃ、Ｐ、Ｔを入力として、出力から入力への制約条件取得処理を行う（ステップＳ２５）。
【０１２８】
ここでステップＳ２５について図１２を用いて詳細に述べる。制約条件取得部２８は、はじめに入力としてＷ、Ｃ、Ｐ、Ｔを受け取り、空のリストＦ，Ｖを用意する（ステップＳ７１）。
【０１２９】
次に制約条件取得部２８は、Ｗの最後尾から＄ｗを取り出してＷから削除し、＄ｗを出力とする文［Ｌ７］と変数＄ｙ、＄ｚを格納したリストＶを取得する（ステップＳ７２〜Ｓ７３）。次に制約条件取得部２８は、文［Ｌ７］が引数を持つａｎｄ演算であり、２つの入力変数＄ｙ、＄ｚが共にＴに存在するためＷに＄ｙ、＄ｚを格納する（ステップＳ７４、Ｓ７５、Ｓ８１〜Ｓ８６）。
【０１３０】
次に制約条件取得部２８は、Ｗから＄ｚを取り出してＷから削除し、＄ｚを出力とする文［Ｌ６］と変数＄ｖを格納したリストＶを取得する（ステップＳ７２〜Ｓ７３）。次に制約条件取得部２８は、文［Ｌ６］がａｎｄ演算ではないため、入力変数＄ｖを取得し、Ｖから変数＄ｖを削除する。制約条件取得部２８は、＄ｖがＴに存在するため制約条件Ｃ（＄ｖ）にＣ（＄ｚ）を追加する。この時Ｃ（＄ｚ）は図１３の[１３]の「＝」の右側の形に展開して追加されるためＣ（＄ｖ）＝Ｃ（＄ｖ）∧（＄ｖ＝“Ｄａｎ”）に展開され、さらにＣ（＄ｖ）＝（＄ｖ＝“Ｄａｎ”）に展開される。次に制約条件取得部２８は、＄ｖをＷに追加する（ステップＳ７３〜Ｓ７８）。次に制約条件取得部２８は、＄ｖが起点文の出力変数や宣言関数の入力変数ではなく、Ｖが空であるため、ステップＳ７２に戻る（ステップＳ７９、Ｓ７４）。
【０１３１】
次に制約条件取得部２８は、Ｗから変数＄ｖを取得してＷから削除し、＄ｖを出力とする文［Ｌ４］と変数＄ｘを格納したリストＶを取得する（ステップＳ７２〜Ｓ７３）。次に文［Ｌ４］がａｎｄ演算ではないため、入力変数＄ｘを取得する。＄ｘがＴに存在するため制約条件Ｃ（＄ｘ）にＣ（＄ｖ）を追加する。［この時Ｃ（＄ｖ）を展開して追加するため、Ｃ（＄ｘ）＝Ｃ（＄ｈ１）∧（＄ｖ＝“Ｄａｎ”）に展開される。さらに制約条件取得部２８は、Ｗに＄ｘ追加して、ステップ７２に戻る（ステップＳ７４〜Ｓ７９、Ｓ７４）。
【０１３２】
次に制約条件取得部２８は、Ｗから変数＄ｘを取得してＷから削除し、＄ｘを出力とする文［Ｌ２］と変数＄ｈ１を格納したリストＶを取得する（ステップＳ７２〜Ｓ７３）。［Ｌ２］はＣ（＄ｈ１）にＣ（＄ｘ）を展開して追加し、Ｃ（＄ｈ１）＝Ｃ（＄ｈ）∧（＄ｖ＝“Ｄａｎ”）となる。さらに制約条件取得部２８は、Ｗに＄ｈ１追加する。制約条件取得部２８は、＄ｈ１は宣言関数の入力変数であるため＄ｈ１をＦに追加して、ステップ７２に戻る（ステップＳ７４〜Ｓ８０、Ｓ７４）。
【０１３３】
次に制約条件取得部２８は、Ｗから変数＄ｈ１を取得してＷから削除し、＄ｈ１を出力とする文が存在しないためステップ７２に戻る（ステップＳ７２〜Ｓ７４）。
【０１３４】
次に制約条件取得部２８は、Ｗから変数＄ｙを取得してＷから削除し、＄ｙを出力とする文［Ｌ５］と変数＄ｕを格納したリストＶを取得する（ステップＳ７２〜Ｓ７３）。次に文［Ｌ５］がａｎｄ演算ではないため、入力変数＄ｕを取得する。＄ｕがＴに存在するため制約条件Ｃ（＄ｕ）にＣ（＄ｙ）を追加する。この時Ｃ（＄ｕ）にＣ（＄ｙ）を展開して追加するため、Ｃ（＄ｕ）＝Ｃ（＄ｘ）∧（＄ｕ＝“Ｓｕｃｉｕ”）となる。さらに制約条件取得部２８は、Ｗに＄ｕを追加してステップ７２に戻る（ステップＳ７４至〜Ｓ７９、Ｓ７４）。
【０１３５】
次に制約条件取得部２８は、Ｗから変数＄ｕを取得してＷから削除し、＄ｕを出力とする文［Ｌ３］と変数＄ｘを格納したリストＶを取得する（ステップＳ７２〜Ｓ７３）。次に文［Ｌ３］がａｎｄ演算ではないため、入力変数＄ｘを取得する。＄ｘがＴに存在するため制約条件Ｃ（＄ｘ）にＣ（＄ｕ）を追加する。この時Ｃ（＄ｕ）を展開して追加するため、Ｃ（＄ｘ）＝Ｃ（＄ｈ１）∧（＄ｖ＝“Ｄａｎ”）∧（＄ｕ＝“Ｓｕｃｉｕ”）となる。さらに制約条件取得部２８は、Ｗに＄ｘを追加してステップ７２に戻る（ステップＳ７４〜Ｓ７９、Ｓ７４）。
【０１３６】
次に制約条件取得部２８は、Ｗから変数＄ｘを取得してＷから削除し、＄ｘを出力とする文［Ｌ２］と変数＄ｈ１を格納したリストＶを取得する（ステップＳ７２〜Ｓ７３）。次に文［Ｌ２］がａｎｄ演算ではないため、入力変数＄ｈ１を取得する。＄ｈ１がＴに存在するため制約条件Ｃ（＄ｈ１）にＣ（＄ｘ）を追加する。この時Ｃ（＄ｘ）を展開して追加するため、Ｃ（＄ｈ１）＝Ｃ（＄ｈ）∧（＄ｖ＝“Ｄａｎ”）∧（＄ｕ＝“Ｓｕｃｉｕ”）となる。さらに制約条件取得部２８は、Ｗに＄ｈ１追加する。＄ｈ１は宣言関数の入力変数であるため＄ｈ１をＦに追加して、ステップ７２に戻る（ステップＳ７４〜Ｓ８０、Ｓ７４）。
【０１３７】
次に制約条件取得部２８は、Ｗから変数＄ｂを取得してＷから削除し、＄ｂを出力とする文［Ｌ１３］と変数＄ａ格納したリストＶを取得する（ステップＳ７２〜Ｓ７３）。次に文［Ｌ１３］がａｎｄ演算ではないため、入力変数＄ａを取得する。＄ａがＴに存在するため制約条件Ｃ（ａ）にＣ（＄ｂ）を追加する。この時Ｃ（＄ｂ）を展開して追加するため、Ｃ（＄ａ）＝Ｃ（＄ｈ２）∧（ｃｏｎｔａｉｎｓ（＄ａ，  “ＸＭＬ”））となる。さらに制約条件取得部２８は、Ｗに＄ａを追加してステップ７２に戻る（ステップＳ７４〜Ｓ７９、Ｓ７４）。
【０１３８】
次に制約条件取得部２８は、Ｗから変数＄ａを取得してＷから削除し、＄ａを出力とする文［Ｌ１２］と変数＄ｈ２格納したリストＶを取得する（ステップＳ７２〜Ｓ７３）。次に文［Ｌ１２］がａｎｄ演算ではないため、入力変数＄ｈ２を取得する。＄ｈ２がＴに存在するため制約条件Ｃ（ｈ２）にＣ（＄ａ）を追加する。この時Ｃ（＄ａ）を展開して追加するため、Ｃ（＄ｈ２）＝Ｃ（＄ｈ）∧（ｃｏｎｔａｉｎｓ（＄ａ，  “ＸＭＬ”））となる。さらに制約条件取得部２８は、Ｗに＄ｈ２を、Ｆに＄ａを追加してステップ７２に戻る（ステップＳ７４〜Ｓ８０、Ｓ７４）。
【０１３９】
次に制約条件取得部２８は、Ｗから変数＄ｈ２を取得してＷから削除し、＄ｈ２を出力とする文が存在しないためステップ７２に戻る（ステップＳ７２〜Ｓ７４）。
【０１４０】
次に制約条件取得部２８は、Ｗから＄ｎを取り出してＷから削除し、＄ｎを出力とする文［Ｌ２４］と変数＄ｉ、＄ｍを格納したリストＶを取得する（ステップＳ７２〜Ｓ７３）。次に制約条件取得部２８は、文［Ｌ２４］が引数を持つａｎｄ演算であり、２つの入力変数＄ｉ、＄ｍが共にＴに存在するためＷに＄ｉ、＄ｍを格納する（ステップＳ７４、Ｓ７５、Ｓ８１〜Ｓ８６）。
【０１４１】
次に制約条件取得部２８は、Ｗから＄ｍを取り出してＷから削除し、＄ｍを出力とする文［Ｌ２３］と変数＄ｋを格納したリストＶを取得する（ステップＳ７２〜Ｓ７３）。次に文［Ｌ２３］がａｎｄ演算ではないため、入力変数＄ｋを取得する。＄ｋがＴに存在するため制約条件Ｃ（＄ｋ）にＣ（＄ｙ）を追加する。この時Ｃ（＄ｍ）を展開して追加するため、Ｃ（＄ｋ）＝Ｃ（＄ｈ）∧Ｃ（＄ｋ  ＜＝  １９９９）となる。さらにＷに＄ｋを追加してステップ７２に戻る（ステップＳ７４〜Ｓ７９、Ｓ７４）。
【０１４２】
次に制約条件取得部２８は、Ｗから変数＄ｋを取得してＷから削除し、＄ｋを出力とする文［Ｌ２１］と変数＄ｈを格納したリストＶを取得する（ステップＳ７２〜Ｓ７３）。次に文［Ｌ２１］がａｎｄ演算ではないため、入力変数＄ｈを取得する。＄ｈがＴに存在するため制約条件Ｃ（＄ｈ）にＣ（＄ｋ）を追加する。この時Ｃ（＄ｋ）を展開して追加するため、Ｃ（＄ｈ）＝Ｃ（＄ｇ）∧Ｃ（＄ｋ  ＜＝  １９９９）となる。さらに制約条件取得部２８は、Ｗに＄ｈを追加してステップ７２に戻る（ステップＳ７４〜Ｓ７９、Ｓ７４）。
【０１４３】
次に制約条件取得部２８は、Ｗから変数＄ｈを取得してＷから削除し、＄ｈを出力とする文［Ｌ１８］と変数＄ｇを格納したリストＶを取得する（ステップＳ７２〜Ｓ７３）。次に文［Ｌ１８］がａｎｄ演算ではないため、入力変数＄ｇを取得する。＄ｇがＴに存在するため制約条件Ｃ（＄ｇ）にＣ（＄ｈ）を追加する。この時Ｃ（＄ｈ）を展開して追加するため、Ｃ（＄ｇ）＝Ｃ（＄ｋ  ＜＝  １９９９）となる。さらにＷに＄ｇ追加する。制約条件取得部２８は、＄ｇは起点文の出力変数であるため＄ｈをＦに追加して、ステップ７２に戻る（ステップＳ７４〜Ｓ８０、Ｓ７４）。
【０１４４】
次に制約条件取得部２８は、Ｗから変数＄ｇを取得してＷから削除し、＄ｇを出力とする文［Ｌ１７］と空のリストＶを取得する（ステップＳ７２〜Ｓ７３）。制約条件取得部２８は、Ｖが空であるためステップ７２に戻る（ステップＳ７４）。
【０１４５】
次に制約条件取得部２８は、Ｗから＄ｉを取り出してＷから削除し、＄ｉを出力とする文［Ｌ１９］と変数＄ｈを格納したリストＶを取得する（ステップＳ７２〜Ｓ７３）。次に文［Ｌ１９］がａｎｄ演算ではないため、入力変数＄ｈを取得する。＄ｈがＴに存在するため制約条件Ｃ（＄ｈ）にＣ（＄ｉ）を追加する。この時Ｃ（＄ｉ）を展開して追加するため、Ｃ（＄ｈ）＝Ｃ（＄ｇ）∧Ｃ（＄ｋ  ＜＝  １９９９）∧Ｃ（＄ｕ＝“Ｓｕｃｉｕ”）∧Ｃ（＄ｖ＝“Ｄａｎ”)となる。さらに制約条件取得部２８は、Ｗに＄ｈを追加してステップ７２に戻る（ステップＳ７４〜Ｓ７９、Ｓ７４）。
【０１４６】
次に制約条件取得部２８は、Ｗから変数＄ｈを取得してＷから削除し、＄ｈを出力とする文［Ｌ１８］と変数＄ｇを格納したリストＶを取得する（ステップＳ７２〜Ｓ７３）。次に文［Ｌ１８］がａｎｄ演算ではないため、入力変数＄ｇを取得する。＄ｇがＴに存在するため制約条件Ｃ（＄ｇ）にＣ（＄ｈ）を追加する。この時Ｃ（＄ｈ）を展開して追加するため、Ｃ（＄ｇ）＝Ｃ（＄ｋ  ＜＝  １９９９）∧Ｃ（＄ｕ＝“Ｓｕｃｉｕ”）∧Ｃ（＄ｖ＝“Ｄａｎ”）となる。さらに制約条件取得部２８は、Ｗに＄ｇ追加する。＄ｇは起点文の出力変数であるため＄ｈをＦに追加して、ステップ７２に戻る（ステップＳ７４〜Ｓ８０、Ｓ７４）。
【０１４７】
次に制約条件取得部２８は、Ｗから変数＄ｇを取得してＷから削除し、＄ｇを出力とする文［Ｌ１７］と空のリストＶを取得する（ステップＳ７２〜Ｓ７３）。制約条件取得部２８は、Ｖが空であるためステップ７２に戻る（ステップＳ７４）。
【０１４８】
次に制約条件取得部２８は、Ｗが空なため、Ｆに登録した３つの変数＄ｘ、＄ａ、＄ｈの制約条件Ｃ（＄ｘ）、Ｃ（＄ａ）、Ｃ（＄ｈ）から比較条件のみになるまで展開する。Ｃ（＄ｇ）が比較条件のみになっているため、この条件を伝播することで比較条件のみになる（ステップＳ７２、Ｓ８７）。以上で出力から入力への制約条件取得処理を終了する。変数＄ｘ、＄ａ、＄ｈを含むリストＦと、図１６に示す制約情報リストＣ、図１４に示すパス情報リストＰを出力し図１０のステップＳ２５に戻る。
【０１４９】
次に制約条件取得部２８は、Ｓ２５で得られた制約情報リストＣ、パス情報リスＰの要素を各々ＣＡ、ＰＡに追加する。ＣＡ、ＰＡは空リストのためＣ、Ｐと一致する（ステップＳ２６）。
【０１５０】
次に制約条件取得部２８は、Ｒが空なため、制約条件取得処理を終了する（ステップＳ２２）。変数＄ｘ、＄ａ、＄ｈを含むリストＦと、図１６に示す制約情報リストＣＡ、図１４に示すパス情報リストＰＡを出力し、図８のステップＳ３に戻る。
【０１５１】
制約条件取得部２８による制約条件取得処理が終了すると、次に、構文解析木書換え処理部２９は、制約条件取得処理の出力を受け取り、制約条件に基づいた構文解析木書換え処理を行う（ステップＳ４）。構文解析木書換え処理部２９は、得られた制約条件をＸＱｕｅｒｙの処理の最初に実施するように移動し、さらに制約条件の元の位置には、移動した式で得られた要素の集合と、構造化文書を最上位から辿ってきた要素の集合のＩＤの積を取ることで書換え前と同じ結果を取得するように書き換える。構文解析木書換え処理部２９による書換え処理の一例を、図１７〜図１８を参照して説明する。
【０１５２】
図１７は図１８のフローチャートで利用する書換え用のテンプレートの一例である。図１７は「テンプレート名」、「ベーステンプレート」、「パラメータ」の項目を有する。「テンプレート名」はテンプレートを一意に指定する名前である。「ベーステンプレート」は作成する文のベースとなるテンプレートであり、［Ａ］〜［Ｅ］は変更可能なパラメータ部分である。［パラメータ］はベーステンプレートに埋め込まれる値の内容を記述するところであり、「［Ｆ］：Ｇ」のフォーマットで複数記述される。［Ｆ］はベーステンプレートにおける［Ａ］〜［Ｅ］に該当する箇所の名前であり、Ｇはその［Ｆ］に入る値を説明したものである。図１７においてＴＰ１のテンプレートは、ベーステンプレートで「ｄｅｃｌａｒｅ  ｖａｒｉａｂｌｅ」で始まる２つの宣言変数の文を記述している。［］で囲まれた部分は［Ｙ］に対するフィルター条件を示すＸＱｕｅｒｙの文法である。［＄Ｘ］／ｆｎ：ｒｏｏｔ（．）は＄Ｘに格納された各要素に対して構造化文書の最上位の文書要素を取得する関数である。ＴＰ１は入力として比較条件式ｄが渡され、ｄに記述された変数＄ｅの構造条件Ｐ（＄ｅ）、ｄ内の比較演算子、ｄ内の比較定数値を各々［Ｙ］、［Ｚ］、［Ｖ］として扱われる。ＴＰ２のテンプレートはｌｅｔ文１つで構成され、＄［Ｘ］ｉｎｔｅｒｓｅｃｔ  ＄［Ｙ］は＄［Ｘ］と＄［Ｙ］の各要素集合の集合積を残す演算である。ＴＰ３のテンプレートはｌｅｔ文１つで構成され、入力リストＥの各要素［＄ｅ［１］．．．＄ｅ［ｎ］］全てに対してｉｎｔｅｒｓｅｃｔ演算により集合積を残す文である。Σはｉが２からｎまでの繰り返しを表現している。ＴＰ４のテンプレートは文の途中に埋め込むフィルター表現であり、ＴＰ４の左にある変数に格納された各要素に対して構造化文書の最上位の文書要素を取得して＄［Ｘ］と集合積を残すものである。
【０１５３】
図１８は、構文解析木書換えの流れを示すフローチャートである。構文解析木書換え処理部２９は、はじめに、入力として与えられた書換え対象変数リストＦ、Ｆ内の変数に対する制約情報リストＣ、パス情報リストＰを受け取り、空のリストＡ、Ｂ、Ｄ、Ｅを用意する。（ステップＳ１０１）。次に、構文解析木書換え処理部２９は、Ｐが空かを判定する（ステップＳ１０２）。
【０１５４】
Ｐが空でなかった場合（ステップＳ１０２：Ｎｏ）、構文解析木書換え処理部２９は、Ｐの先頭の要素であるパス式Ｐ（＄１）を取得してＰから削除する（ステップＳ１０３）。次に、＄１がＦに存在するかを判定する（ステップＳ１０４）。
【０１５５】
＄１がＦに存在する場合（ステップＳ１０４：Ｙｅｓ）、構文解析木書換え処理部２９は、Ｃから＄１の制約条件Ｃ（＄１）を取得する（ステップＳ１０５）。次に構文解析木書換え処理部２９は、Ａ内にＣ（＄１）と制約条件が一致する変数が存在するかを判定する（ステップＳ１０６）。
【０１５６】
Ａ内にＣ（＄１）と制約条件が一致する変数が存在しない場合（ステップＳ１０６：Ｎｏ）、構文解析木書換え処理部２９は、＄１をＡに追加し、Ｃ（＄１）内のリストＢに存在しない条件を集めたリストＤを取得する。次に構文解析木書換え処理部２９は、Ｄの全要素をＢに取得する（ステップＳ１０７）。
【０１５７】
次にＤの先頭の要素ｄを取得し、構文解析木書換え処理部２９は、Ｄからｄを削除する（ステップＳ１０８）。構文解析木書換え処理部２９は、図１８のテンプレートＴＰ１のパラメータに条件ｄを入力として適用してクエリに追加する。次に構文解析木書換え処理部２９は、ｄが記述された文を図１８のテンプレートＴＰ２に適用したものに置き換える（ステップＳ１０９）。次に構文解析木書換え処理部２９は、Ｄが空かを判定する（ステップＳ１１０）。
【０１５８】
Ｄが空の場合（ステップＳ１１０：Ｙｅｓ）、構文解析木書換え処理部２９は、Ｅの要素数が２以上かを判定する（ステップＳ１１１）。
【０１５９】
Ｅの要素数が２以上の場合（ステップＳ１１１：Ｙｅｓ）、構文解析木書換え処理部２９は、構文解析木書換え処理部２９は、図１８のテンプレートＴＰ３にパラメータとしてリストＥを入力として適用してクエリに追加する。追加した結果の出力変数を＄３とする（ステップＳ１１２）。次に構文解析木書換え処理部２９は、ステップＳ１１３に移動し処理を続行する。
【０１６０】
一方、Ｅの要素数が１の場合（ステップＳ１１１：Ｎｏ）、構文解析木書換え処理部２９は、Ｅの先頭要素を＄３とする（ステップＳ１１６）。次に構文解析木書換え処理部２９は、ステップＳ１１３に移動し処理を続行する。
【０１６１】
次に構文解析木書換え処理部２９は、＄１を出力する式ｃを取得する（ステップＳ１１３）。次に構文解析木書換え処理部２９は、式ｃの入力変数＄４が起点文の出力変数かを判定する（ステップＳ１１４）。
【０１６２】
一方、式ｃの入力変数＄４が起点文の出力変数の場合（ステップＳ１１４：Ｙｅｓ）、構文解析木書換え処理部２９は、＄４を＄３に書き換える（ステップＳ１１５）。次にステップＳ１１８に移動し処理を続行する。
【０１６３】
一方、式ｃの入力変数＄４が起点文の出力変数ではない場合（ステップＳ１１４：Ｎｏ）、構文解析木書換え処理部２９は、図１８のテンプレートＴＰ４にパラメータに＄３を入力として適用し、式ｃの入力変数＄４の後ろに追加する（ステップＳ１１７）。次にステップＳ１１８に移動し処理を続行する。
【０１６４】
次にＥを空にして（ステップＳ１１３）、構文解析木書換え処理部２９は、ステップＳ１０２に戻り引き続き処理を続行する。
【０１６５】
一方、Ｄが空でない場合（ステップＳ１１０：Ｎｏ）、構文解析木書換え処理部２９は、ステップＳ１０８に戻り引き続き処理を続行する。
【０１６６】
一方、Ａ内にＣ（＄１）と制約条件が一致する変数が存在する場合（ステップＳ１０６：Ｙｅｓ）、構文解析木書換え処理部２９は、ステップＳ１０２に戻り引き続き処理を続行する。
【０１６７】
一方、＄１がＦに存在しない場合（ステップＳ１０４：Ｎｏ）、構文解析木書換え処理部２９は、ステップＳ１０２に戻り引き続き処理を続行する。
【０１６８】
一方、ステップＳ１０２の判定でＰが空だった場合（ステップＳ１０２がＹｅｓ）、構文解析木書換え処理部２９は、構文解析木書換え処理を終了する。
【０１６９】
ここで、変数＄ｘ、＄ａ、＄ｈを含むリストＦと、図１６に示す制約情報リストＣ、図１４に示すパス情報リストＰを用いて、構文解析木書換え処理を行った場合の処理の概要を、図１７〜図１８を参照して説明する。
【０１７０】
はじめに構文解析木書換え処理部２９は、入力として変数＄ｘ、＄ａ、＄ｈを含むリストＦと、図１６に示す制約情報リストＣ、図１４に示すパス情報リストＰを受け取り、空のリストとしてＡ、Ｂ、Ｄ、Ｅを用意する（ステップＳ１０１）。次に構文解析木書換え処理部２９は、Ｐの先頭からＰ（＄ｈ）を受け取りＰから削除する（ステップＳ１０２〜Ｓ１０３）。
【０１７１】
次に構文解析木書換え処理部２９は、＄ｈがＦに存在するので＄ｈの制約条件Ｃ（＄ｈ）を取得する（ステップＳ１０４、ステップＳ１０２〜Ｓ１０５）。
【０１７２】
次にリストＡが空であるため、構文解析木書換え処理部２９は、ＡにＣ（＄ｈ）の制約条件（＄ｋ＜＝１９９９）、（＄ｖ＝“Ｄａｎ”）、（＄ｕ＝“Ｓｕｃｉｕ”）を追加し、リストＢが空であるため（＄ｋ＜＝１９９９）、（＄ｖ＝“Ｄａｎ”）、（＄ｕ＝“Ｓｕｃｉｕ”）を要素とするリストＤを取得する（ステップＳ１０６〜Ｓ１０７）。
【０１７３】
次に構文解析木書換え処理部２９は、Ｄの先頭の要素（＄ｋ＜＝１９９９）を取得してＤから削除する（ステップＳ１０８）。次に構文解析木書換え処理部２９は、図１７のＴＰ１に（＄ｋ＜＝１９９９）を入力として渡し、２つの宣言変数の文をクエリ追加する。ＴＰ１の［Ｙ］には＄ｋのパス情報Ｐ（＄ｋ）の構造条件「／ｂｏｏｋ／＠ｙｅａｒ」、［Ｚ］が比較演算子「＜＝」、［Ｖ］は値「１９９９」が代入され、［Ｘ］、［Ｗ］にはこれまで出現した変数名に被らないように新規変数＄１、＄１＿ｒｏｏｔが代入される。追加した文は図１９の［Ｌ１］、［Ｌ２］に該当する。次に構文解析木書換え処理部２９は、＄１＿ｒｏｏｔをリストＥに追加する。さらに、構文解析木書換え処理部２９は、図１７のＴＰ２に（＄ｋ＜＝１９９９）を入力として渡し、＄ｋ  ＜＝  １９９９が記述されていた文を書き換える。ＴＰ２の［Ｘ］には条件＄ｋ  ＜＝  １９９９を格納する変数＄ｍ、［Ｙ］に＄ｋ、＄ｚに＄１が代入される。図９の［Ｌ２３］が図１９の［Ｌ３３］に書き換えられる（ステップＳ１０８〜Ｓ１０９）。
【０１７４】
次にＤの残りの要素（＄ｖ＝“Ｄａｎ”）、（＄ｕ＝“Ｓｕｃｉｕ”）についても同様にステップＳ１０９の処理が適用される。（＄ｖ＝“Ｄａｎ”）にＴＰ１を適用した結果は図１９の［Ｌ３］、［Ｌ４］に該当し、ＴＰ２を適用した結果は図１９の［Ｌ１６］に該当する。また、（＄ｕ＝“Ｓｕｃｉｕ”）にＴＰ１を適用した結果は図１９の［Ｌ５］、［Ｌ６］に該当し、ＴＰ２を適用した結果は図１９の［Ｌ１５］に該当する。Ｅには＄２＿ｒｏｏｔ、＄３＿ｒｏｏｔが追加される（ステップＳ１１０、ステップＳ１０８〜Ｓ１０９）。
【０１７５】
次にＤが空であり、Ｅの要素数が３であるため構文解析木書換え処理部２９は、図１７のＴＰ３にリストＥを入力として渡し、１つの宣言変数の文を追加する。ＴＰ３の［ｎ］にはＥの要素数３、ｅ［１］からｅ［３］にはＥの各要素＄１＿ｒｏｏｔ、＄２＿ｒｏｏｔ、＄３＿ｒｏｏｔが代入され、［Ｘ］にはこれまで出現した変数名に被らないように新規変数＄４＿ｒｏｏｔが代入される。ＴＰ３を適用した結果は図１９の［Ｌ９］に該当する（ステップＳ１１０〜Ｓ１１２）。
【０１７６】
次に＄ｈを出力する式が図９の［Ｌ１８］に該当し、［Ｌ１８］の入力変数＄ｇが起点文の出力変数であるため、構文解析木書換え処理部２９は、＄ｇを＄４＿ｒｏｏｔに書き換える。書き換えた結果は図１９の［Ｌ２８］に該当する（ステップＳ１１３〜Ｓ１１５）。
【０１７７】
次に構文解析木書換え処理部２９は、Ｅを空にして、Ｐの先頭からＰ（＄ｋ）を取り出す（ステップＳ１１８、Ｓ１０２〜Ｓ１０３）。Ｐ（＄ｋ）及びＰ（＄ｌ）の変数＄ｋ、＄ｌはＦに存在しないため処理をスキップする（ステップＳ１０４、Ｓ１０２〜Ｓ１０３）。次に構文解析木書換え処理部２９は、Ｐの先頭からＰ（＄ａ）を受け取りＰから削除する（ステップＳ１０４）。
【０１７８】
次に構文解析木書換え処理部２９は、＄ａがＦに存在するので＄ａの制約条件Ｃ（＄ａ）を取得する（ステップＳ１０４〜Ｓ１０５）。
【０１７９】
次にＡ内の変数＄ｈの制約情報Ｃ（＄ｈ）とＣ（＄ａ）が一致しないため、構文解析木書換え処理部２９は、Ａに＄ａを追加する。次に構文解析木書換え処理部２９は、Ｃ（＄ａ）内のＢに存在しない条件（Ｃｏｎｔａｉｎｓ（＄ａ，“ＸＭＬ”））を要素とするリストＤを取得する。次に構文解析木書換え処理部２９は、Ｄの要素である条件（Ｃｏｎｔａｉｎｓ（＄ａ，“ＸＭＬ”））をＢに追加する（ステップＳ１０６〜Ｓ１０７）。
【０１８０】
次に構文解析木書換え処理部２９は、Ｄの先頭の要素（Ｃｏｎｔａｉｎｓ（＄ａ，“ＸＭＬ”））を取得してＤから削除する（ステップＳ１０８）。次に構文解析木書換え処理部２９は、図１７のＴＰ１に（Ｃｏｎｔａｉｎｓ（＄ａ，“ＸＭＬ”））を入力として渡し、２つの宣言変数の文をクエリ追加する。ＴＰ１の［Ｙ］には＄ａのパス情報Ｐ（＄ａ）の構造条件「／ｂｏｏｋ／ｓｅｃｔｉｏｎ／ｐ」、［Ｚ］が比較演算子「ｃｏｎｔａｉｎｓ（）」、［Ｖ］は値「“ＸＭＬ”」が代入され、［Ｘ］、［Ｗ］にはこれまで出現した変数名に被らないように新規変数＄５、＄５＿ｒｏｏｔが代入される。追加した文は図１９の［Ｌ８］、［Ｌ９］に該当する。次に構文解析木書換え処理部２９は、＄５＿ｒｏｏｔをリストＥに追加する。さらに、構文解析木書換え処理部２９は、図１７のＴＰ２に（Ｃｏｎｔａｉｎｓ（＄ａ，“ＸＭＬ”））を入力として渡し、（Ｃｏｎｔａｉｎｓ（＄ａ，“ＸＭＬ”））が記述されていた文を書き換える。ＴＰ２の［Ｘ］には（Ｃｏｎｔａｉｎｓ（＄ａ，“ＸＭＬ”））を格納する変数＄ｂ、［Ｙ］に＄ａ、＄ｚに＄５が代入される。図９の［Ｌ１３］が図１９の［Ｌ２３］に書き換えられる（ステップＳ１０８〜Ｓ１０９）。
【０１８１】
次にＤが空であり、Ｅの要素数が１であるため、構文解析木書換え処理部２９は、＄ａを出力する式が図９の［Ｌ１２］を取得し、［Ｌ１２］の入力変数＄ｈ２が起点文の出力変数ではないため、図１７のＴＰ４に＄５＿ｒｏｏｔを入力として渡し、得られた式を図９の［Ｌ１２］の入力変数＄ｈ２の後ろに追加する。ＴＰ４の［Ｘ］には変数＄５＿ｒｏｏｔが代入され、追加した式は図１９の［Ｌ２２］に該当する（ステップＳ１１０〜Ｓ１１１、Ｓ１１６、Ｓ１１３〜Ｓ１１４、Ｓ１１７）。
【０１８２】
次に構文解析木書換え処理部２９は、Ｅを空にして、Ｐの先頭からＰ（＄ｘ）を受け取りＰから削除する（ステップＳ１０４）。
【０１８３】
次に構文解析木書換え処理部２９は、＄ｘがＦに存在するので＄ｘの制約条件Ｃ（＄ｘ）を取得する（ステップＳ１０４〜Ｓ１０５）。
【０１８４】
次に構文解析木書換え処理部２９は、Ａ内の変数＄ｈの制約情報Ｃ（＄ｈ）とＣ（＄ｘ）が一致するため、ステップＳ１０２に戻り、Ｐの先頭からＰ（＄ｕ）を受け取りＰから削除する（ステップＳ１０６、Ｓ１０２〜Ｓ１０３）。Ｐ（＄ｕ）及び、Ｐに残ったＰ（＄ｖ）の変数＄ｕ、＄ｖはいずれもＦに存在しないためステップＳ１０２に戻る。Ｐが空になったため構文解析木書換え処理を終了する（ステップＳ１０４、Ｓ１０２〜Ｓ１０４、Ｓ１０２）。図１９のＸＱｕｅｒｙを構文解析木として出力し、図８のステップＳ４に戻る。
【０１８５】
構文解析木書換え部２９による構文解析木書換え処理が終了すると、書き換えられた構文解析木が出力される。構文解析木はＸＱｕｅｒｙの文法を再現できる形で表現されている。次に、クエリ実行部３０により、書き換えられた構文解析木、ここではＸＱｕｅｒｙを実行する処理が行われる（ステップＳ５）。書き換えられた後もＸＱｕｅｒｙの形を保っているため、クエリ実行処理は、任意のＸＱｕｅｒｙ処理系で実行可能である。
【０１８６】
クエリ実行部３０によるクエリ実行処理が終了すると、最後に、検索インタフェース部２６により、クエリ実行部３０による出力が、結果データとしてクライアント端末３に返却される（ステップＳ６）。
【０１８７】
図２０は、図４〜図６の構造化文書装置内の文書集合に対して図７に例示したＸＱｕｅｒｙを書換えた図１９のＸＱｕｅｒｙを実行した結果である。［Ｌ１］〜［Ｌ６］及び［Ｌ９］により、最初に構造化文書集合で制約条件を満たすものとして図４、図５の構造化文書のみに対象を絞っている。絞られた構造化文書に対して［Ｌ２７］から処理を実施している。さらに［Ｌ１５］〜［Ｌ１７］を満たす構造化文書は図４のみとなる。そのため結果は図４の＜ｔｉｔｌｅ＞、＜ａｕｔｈｏｒ＞要素及び、［Ｌ２４］の条件を満たす図４内の＜ｐ＞要素を組み合わせたＸＭＬとして出力される。
【０１８８】
以上、具体的な例を挙げながら説明したように、本実施形態によれば、サーバ１が、構造化文書データを構造化文書ＤＢ２１に格納する。また、サーバ１は、構造化文書データの検索時には、クライアント端末３からの入力クエリデータを構文解析して、入力クエリデータを１つの文が単一の演算式からなる構文解析木を生成し、得られた構文解析木を入力から出力、出力から入力方向に辿ることにより対象構造化文書集合に関する制約条件を取得している。制約条件を構成する各条件の階層構造が互いに依存しないように条件を緩和する。これにより得られた制約条件を書き換える際に、単純に互いに独立した形で宣言変数として記述できる。緩和した条件は、書換え前の入力変数と要素のＩＤに関する積をとることで元の条件と同じ結果を取得できる。このように書き換えることにより、入れ子クエリを含むような複雑なＸＱｕｅｒｙにおいても、対象となる構造化文書集合を早い段階で絞り込むことができるように書き換えることができる。さらに厳密な条件を求める際に、要素のＩＤの積をとることで同じ条件式を二度評価することを回避している。そのため早期に絞り込まれた構造化文書集合に対してＸＱｕｅｒｙの処理を実施すれば良いため検索を高速に実行することができる。
【０１８９】
なお、実施形態においては、書換え結果を入力と同じクエリの文法に従って書き換えたが、本提案はこれに限定するものではない。例えば構造化文書検索装置が実行計画を生成するために用いる内部形式に書き換える形でも適用でき、その場合は緩和した制約条件の実行順序をＪＯＩＮ（結合演算）やＯＲＤＥＲＢＹ（ソート演算）を含めたクエリ全体での最適化が可能である。また、構造化文書の最上位要素を取得してＸＱｕｅｒｙの構文に存在するＩＮＴＥＲＳＥＣＴ演算によって絞り込みを記述したが、本提案はこれに限定するものではない。例えば特許文献２のように構造化文書の要素リストを入力として、リスト内にある構造化文書のみに対して演算を実施する関数を用意することで、ＩＮＴＥＲＳＥＣＴ演算を利用しなくても同等の機能を実現可能である。
【０１９０】
また実施形態においては、制約条件を構成する各条件間で発生する構造化文書内の階層構造の依存関係を無視するよう緩和したが、本提案はこれに限定するものではない。例えば依存関係を無視する構造条件を、一部の階層構造条件のみに限定してもよい。また階層構造条件の親子関係を祖先子孫関係に緩和する、あるいは任意の要素名を指定するように緩和してもよい。さらに、制約条件を緩和するための情報として、ＸＭＬのスキーマ情報であるＤＴＤやＸＭＬ  ＳＣＨＥＭＡの利用などを用いてもよい。
【０１９１】
さらに実施形態においては、複数の条件を指定する演算子としてａｎｄ条件のみについて記述したが本提案はこれに限定するものではない。制約条件をｏｒに対応させることで、ｏｒ条件が含まれた場合についても同様に処理することができる。
【０１９２】
以上説明した実施形態におけるサーバ１の機能は、例えば、コンピュータの演算装置であるＣＰＵ１０１が、アプリケーションプログラムとして実装された構造化文書管理プログラムを実行することにより実現される。
【０１９３】
実施形態におけるサーバ１で実行される構造化文書管理プログラムは、例えば、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）などのコンピュータで読み取り可能な記録媒体１１０に記録されて提供される。
【０１９４】
また、実施形態におけるサーバ１で実行される構造化文書管理プログラムを、インターネットなどのネットワーク２に接続されたコンピュータ上に格納し、ネットワーク２経由でダウンロードさせることにより提供するように構成してもよい。また、実施形態におけるサーバ１で実行される構造化文書管理プログラムを、インターネットなどのネットワーク２経由で提供または配布するように構成してもよい。さらに、実施形態におけるサーバ１で実行される構造化文書管理プログラムを、ＲＯＭ１０２などに予め組み込んで提供するように構成してもよい。
【０１９５】
第１の実施形態におけるサーバ１で実行される構造化文書管理プログラムは、格納インタフェース部２４、検索インタフェース部２６、構文解析部２７、制約条件取得部２８、構文解析木書換え部２９、クエリ実行部３０などを含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵ（プロセッサ）１０１がＨＤＤ１０４などから構造化文書管理プログラムを読み出して実行することにより上記各部が主記憶装置（例えばＲＡＭ１０３）上にロードされ、格納インタフェース部２４、検索インタフェース部２６、構文解析部２７、制約条件取得部２８、構文解析木書換え部２９、クエリ実行部３０、などが主記憶装置上に生成されるようになっている。
【０１９６】
以上述べた実施形態にかかる構造化文書管理システムによれば、入力クエリデータを構文解析し、構造化文書内の要素の階層構造条件と、値の条件を制約条件として抽出している。その際に構造化文書の要素がみたす階層条件を緩和し、元の階層条件では得られない要素も含む形に条件を緩和している。そのため緩和した条件を入れ子サブクエリ間で移動が可能に形で書き換えることができる。緩和した条件は要素の識別子の積集合をとる述語条件を適用することで元の条件と同じ結果を取得するよう書き換えている。これにより早期に構造化文書集合に対する絞り込みを適用できるため、検索を高速に実行することができる。
【０１９７】
なお、本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１９８】
１    サーバ
２４  格納インタフェース部
２６  検索インタフェース部
２７  構文解析部
２８  制約条件取得部
２９  構文解析木書換え部
３０  クエリ実行部
【要約】
実施形態の構造化文書管理装置は、入力されたクエリに含まれる階層条件と、階層条件で指定された構造化文書の要素に対する述語条件を解析し、各要素を格納する変数における制約条件と、変数間の依存関係を抽出する。本手法では制約条件を抽出する際に、構造に関する制約条件を、元々対象となる要素だけでなく、対象となる要素以外も含むように緩めた形で取得する。緩めた制約条件をできるだけ早期に適用できるように述語を移動した後、緩めた条件を補完する述語条件を挿入する。【図１】
0005422751.tif 000002
【図２】
0005422751.tif 000003
【図３】
0005422751.tif 000004
【図４】
0005422751.tif 000005
【図５】
0005422751.tif 000006
【図６】
0005422751.tif 000007
【図７】
0005422751.tif 000008
【図８】
0005422751.tif 000009
【図９】
0005422751.tif 000010
【図１０】
0005422751.tif 000011
【図１１】
0005422751.tif 000012
【図１２】
0005422751.tif 000013
【図１３】
0005422751.tif 000014
【図１４】
0005422751.tif 000015
【図１５】
0005422751.tif 000016
【図１６】
0005422751.tif 000017
【図１７】
0005422751.tif 000018
【図１８】
0005422751.tif 000019
【図１９】
0005422751.tif 000020
【図２０】
0005422751.tif 000021