(57)【要約】【課題】より高度なプランの精度（つまり、コスト）の最適化を図ることができるクエリ処理装置を提供する。【解決手段】データベース上のオブジェクトが束縛される変数に相当する変数ノードと当該変数ノード間の条件を示した述語ノードとを含むグラフで表現したものであってクエリ解析手段１１で生成された解析グラフと、当該解析グラフから抽出されたプランおよびサブプランに対する制約をノードやノード間の条件として表したものであって制約抽出手段１２で抽出されたプラン合成制約データとを用いて、プラン合成手段１４でサブプランについてコストの低いものを選びながら当該サブプランのサイズを段階的に増加させることで全ての述語ノードが含まれるプランを合成する。これにより、より高度なプランの精度（つまり、コスト）の最適化を図ることができる。【選択図】        図２
2008234430.tif 000002
【特許請求の範囲】
【請求項１】
木構造のノードで表される構造化文書データを格納するデータベースに対して所定の条件に合致する前記構造化文書データを抽出する命令を伝えるために使われるクエリデータを受け付けるクエリ受付手段と、
前記クエリデータを構文解析し、前記データベース上のオブジェクトが束縛される変数に相当する変数ノードと当該変数ノード間の条件を示した述語ノードとを含むグラフで表現した解析グラフを生成するクエリ解析手段と、
前記解析グラフから前記クエリデータを処理する手順であるプランおよび前記プランの前記述語ノードに対応するサブプランに対する制約をノードやノード間の条件として表したプラン合成制約データを抽出する制約抽出手段と、
前記解析グラフと前記プラン合成制約データとを用いて、前記サブプランについてコストの低いものを選びながら当該サブプランのサイズを段階的に増加させることで全ての述語ノードが含まれる前記プランを合成処理するプラン合成手段と、
前記プランを実行することで前記クエリデータを満足する前記構造化文書データを生成するプラン実行手段と、
を備えることを特徴とするクエリ処理装置。
【請求項２】
前記プラン合成手段の合成処理に対応するデフォルトのプラン合成制約データを予め記憶する制約記憶手段を更に備え、
前記制約抽出手段は、抽出した前記プラン合成制約データに基づいて前記制約記憶手段に記憶されている前記プラン合成制約データを更新する、
ことを特徴とする請求項１記載のクエリ処理装置。
【請求項３】
前記プラン合成手段は、任意個数のサブプランを合成して新たなサブプランを生成するための任意個数のサブプラン合成手段を備える、
ことを特徴とする請求項１記載のクエリ処理装置。
【請求項４】
前記制約抽出手段が抽出する前記プラン合成制約データは、論理和（ＯＲ）条件を処理する前記サブプランが合成可能な条件である、
ことを特徴とする請求項１記載のクエリ処理装置。
【請求項５】
前記制約抽出手段が抽出する前記プラン合成制約データは、入れ子（ｌｅｔ）節を処理する前記サブプランが合成可能な条件である、
ことを特徴とする請求項１記載のクエリ処理装置。
【請求項６】
木構造のノードで表される構造化文書データを格納するデータベースに対して所定の条件に合致する前記構造化文書データを抽出する命令を伝えるために使われるクエリデータを受け付けるクエリ受付機能と、
前記クエリデータを構文解析し、前記データベース上のオブジェクトが束縛される変数に相当する変数ノードと当該変数ノード間の条件を示した述語ノードとを含むグラフで表現した解析グラフを生成するクエリ解析機能と、
前記解析グラフから前記クエリデータを処理する手順であるプランおよび前記プランの前記述語ノードに対応するサブプランに対する制約をノードやノード間の条件として表したプラン合成制約データを抽出する制約抽出機能と、
前記解析グラフと前記プラン合成制約データとを用いて、前記サブプランについてコストの低いものを選びながら当該サブプランのサイズを段階的に増加させることで全ての述語ノードが含まれる前記プランを合成処理するプラン合成機能と、
前記プランを実行することで前記クエリデータを満足する前記構造化文書データを生成するプラン実行機能と、
をコンピュータに実行させることを特徴とするプログラム。
【請求項７】
木構造のノードで表される構造化文書データを格納するデータベースに対して所定の条件に合致する前記構造化文書データを抽出する命令を伝えるために使われるクエリデータを受け付けるクエリ受付工程と、
前記クエリデータを構文解析し、前記データベース上のオブジェクトが束縛される変数に相当する変数ノードと当該変数ノード間の条件を示した述語ノードとを含むグラフで表現した解析グラフを生成するクエリ解析工程と、
前記解析グラフから前記クエリデータを処理する手順であるプランおよび前記プランの前記述語ノードに対応するサブプランに対する制約をノードやノード間の条件として表したプラン合成制約データを抽出する制約抽出工程と、
前記解析グラフと前記プラン合成制約データとを用いて、前記サブプランについてコストの低いものを選びながら当該サブプランのサイズを段階的に増加させることで全ての述語ノードが含まれる前記プランを合成処理するプラン合成工程と、
前記プランを実行することで前記クエリデータを満足する前記構造化文書データを生成するプラン実行工程と、
を含むことを特徴とするクエリ処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、木構造のノードで表される構造化文書データを格納するデータベースに対するクエリ処理装置、プログラムおよびクエリ処理方法に関する。
【背景技術】
【０００２】
ＸＭＬ（Extensible  Markup  Language）などで記述された構造化文書データを記憶・検索するための構造化文書管理システムには、いくつかの方式が考えられている。
【０００３】
近年、新たな格納方式として、ネイティブに構造化文書データを管理する方式が提案されている。この方式によれば、多種多様な階層構造を持つＸＭＬデータ（構造化文書データ）を特別なマッピング処理すること無しに格納するため、格納や取得時に特別なオーバヘッドが存在しないというメリットがある。また、コストのかかる事前のスキーマ設計が不要になり、ビジネス環境の変化により必要に応じてＸＭＬデータの構造を自由に変更することが可能である。
【０００４】
一方、ＸＭＬデータを検索する問合せ言語として、ＸＱｕｅｒｙ（XML  Query  Language）が策定されている。ＸＱｕｅｒｙは、ＸＭＬデータをデータベースのように扱うための言語である。このため、条件に合致するデータ集合の取り出しや集計・分析を行うための手段が提供されている。また、ＸＭＬデータは親子や兄弟などの要素が組み合わさった階層構造を持つため、この階層構造を辿る手段が提供されている。格納された構造化文書データの階層構造を辿りながら、検索条件で指定された特定の要素と特定の構造が含まれている構造化文書データを検索するための技術は、特許文献１などに既に開示されている。
【０００５】
ところで、構造化文書データの構造が大規模になるほど、データベースに格納されている構造化文書データの数が多いほど、検索条件が複雑なほど、各構造化文書データの階層構造を構成する要素間をたどるという処理には時間がかかる。また、構造化文書データの数、サイズが大きくなれば、格納された構造化文書データをメモリ上に展開することは不可能であり、多くはハードディスクなどの二次記憶装置に格納されることになる。
【０００６】
上述したネイティブに構造化文書データを管理する方式では、構造化文書データは要素間の階層構造をそのまま記憶するため、検索条件として指定された要素や構造があるか否かを調べるためには、二次記憶装置上に格納された構造化文書データの要素間を頻繁にアクセスしなければならない。複雑な検索条件の場合はなおさらである。すなわち、ネイティブに構造化文書データを管理する方式では、構造化文書データのサイズが大きくなるほど、検索対象の構造化文書データの数が多いほど、検索条件が複雑であるほど、検索処理の高速化が困難になるという問題がある。
【０００７】
そこで、近年においては、検索条件が複雑な問い合わせを高速化するための問い合わせ最適化技術が開発されている（特許文献２，３参照）。
【０００８】
特許文献２に記載されている問い合わせ最適化技術は、適用可能な検索グラフノードのクラス、適用コスト、適用条件部、検索プラン実行時に実行されるアクションを表すプラン生成ルールを記憶し、検索要求の記述を構文解析することにより、プラン生成ルールにより具体化可能な変数ノードを含む検索グラフノードを有する検索グラフを生成し、検索グラフの検索グラフノードにおいて適用条件を満たし、かつ適用コストが最小の検索グラフノードを選択してプラン生成ルールを適用し、アクションの実行により変数ノードを具体化しながらプラン生成ルールの適用を繰り返すことにより構造化文書データベースに対する検索処理手順を示す検索プランを生成する、というものである。この技術によれば、プラン生成ルールを直線的に適用するので、高速にプランが生成できる。
【０００９】
特許文献３に記載されている問い合わせ最適化技術は、ＸＭＬデータから指定された条件に適合する部分を検索するに際し、検索実行前に、問い合わせの最適化を図るとともに、検索実行時、処理順序の入れ替え、既に得た処理結果の再利用をすることによる実行最適化を図る、というものである。例えば、ネステツドループをまわす場合の内外の入れ替え、セルフジョインを処理する際の右辺と左辺の入れ替え、実行順序の入れ替え、などの書き換えを行う例が挙げられている。この技術によれば、特許文献２に記載されている方式には劣るが、プラン変更ルールを直線的に適用するので、高速にプランが生成できる。
【００１０】
【特許文献１】特開２０００−０５７１６３号公報
【特許文献２】特許第３７５４２５３号公報
【特許文献３】特許第３４９２２４６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、特許文献２，３に記載されている問い合わせ最適化技術は、まだ完全とはいえず、いまだ解決されねばならない課題が存在する。
【００１２】
特許文献２に記載されている問い合わせ最適化技術の課題としては、第１には、プラン生成ルールを数多く事前に洗い出す必要がある点が挙げられる。第２には、干渉が発生する可能性があり、数多くのルールの適用順番をうまく制御するためには、相当のチューニングが必要になる点が挙げられる。第３には、高速にプランが生成できるが、プランの精度（つまり、コスト）は最適ではない点が挙げられる。
【００１３】
一方、特許文献３に記載されている問い合わせ最適化技術の課題としては、第１には、プラン変更ルールを数多く事前に洗い出す必要がある点が挙げられる。第２には、プランの精度（つまり、コスト）は最適ではない点が挙げられる。
【００１４】
すなわち、特許文献２，３に記載されている問い合わせ最適化技術によれば、問い合わせ最適化のために、事前に多くのプラン生成ルールやプラン変更ルールなど背景知識を網羅的に生成する必要がある。しかしながら、ＸＱｕｅｒｙの言語仕様は、下記に示す特徴を有しているため、上記の背景知識が増大し、最適化が困難になることが予想される。
・シーケンスを伴う入れ子（ｌｅｔ式）
・ＸＭＬデータの要素間の階層条件を指定するパス（／、／／、など）
【００１５】
本発明は、上記に鑑みてなされたものであって、より高度なプランの精度（つまり、コスト）の最適化を図ることができるクエリ処理装置、プログラムおよびクエリ処理方法を提供することを目的とする。
【課題を解決するための手段】
【００１６】
上述した課題を解決し、目的を達成するために、本発明のクエリ処理装置は、木構造のノードで表される構造化文書データを格納するデータベースに対して所定の条件に合致する前記構造化文書データを抽出する命令を伝えるために使われるクエリデータを受け付けるクエリ受付手段と、前記クエリデータを構文解析し、前記データベース上のオブジェクトが束縛される変数に相当する変数ノードと当該変数ノード間の条件を示した述語ノードとを含むグラフで表現した解析グラフを生成するクエリ解析手段と、前記解析グラフから前記クエリデータを処理する手順であるプランおよび前記プランの前記述語ノードに対応するサブプランに対する制約をノードやノード間の条件として表したプラン合成制約データを抽出する制約抽出手段と、前記解析グラフと前記プラン合成制約データとを用いて、前記サブプランについてコストの低いものを選びながら当該サブプランのサイズを段階的に増加させることで全ての述語ノードが含まれる前記プランを合成処理するプラン合成手段と、前記プランを実行することで前記クエリデータを満足する前記構造化文書データを生成するプラン実行手段と、を備える。
【００１７】
また、本発明のプログラムは、木構造のノードで表される構造化文書データを格納するデータベースに対して所定の条件に合致する前記構造化文書データを抽出する命令を伝えるために使われるクエリデータを受け付けるクエリ受付機能と、前記クエリデータを構文解析し、前記データベース上のオブジェクトが束縛される変数に相当する変数ノードと当該変数ノード間の条件を示した述語ノードとを含むグラフで表現した解析グラフを生成するクエリ解析機能と、前記解析グラフから前記クエリデータを処理する手順であるプランおよび前記プランの前記述語ノードに対応するサブプランに対する制約をノードやノード間の条件として表したプラン合成制約データを抽出する制約抽出機能と、前記解析グラフと前記プラン合成制約データとを用いて、前記サブプランについてコストの低いものを選びながら当該サブプランのサイズを段階的に増加させることで全ての述語ノードが含まれる前記プランを合成処理するプラン合成機能と、前記プランを実行することで前記クエリデータを満足する前記構造化文書データを生成するプラン実行機能と、をコンピュータに実行させる。
【００１８】
また、本発明のクエリ処理方法は、木構造のノードで表される構造化文書データを格納するデータベースに対して所定の条件に合致する前記構造化文書データを抽出する命令を伝えるために使われるクエリデータを受け付けるクエリ受付工程と、前記クエリデータを構文解析し、前記データベース上のオブジェクトが束縛される変数に相当する変数ノードと当該変数ノード間の条件を示した述語ノードとを含むグラフで表現した解析グラフを生成するクエリ解析工程と、前記解析グラフから前記クエリデータを処理する手順であるプランおよび前記プランの前記述語ノードに対応するサブプランに対する制約をノードやノード間の条件として表したプラン合成制約データを抽出する制約抽出工程と、前記解析グラフと前記プラン合成制約データとを用いて、前記サブプランについてコストの低いものを選びながら当該サブプランのサイズを段階的に増加させることで全ての述語ノードが含まれる前記プランを合成処理するプラン合成工程と、前記プランを実行することで前記クエリデータを満足する前記構造化文書データを生成するプラン実行工程と、を含む。
【発明の効果】
【００１９】
本発明によれば、データベース上のオブジェクトが束縛される変数に相当する変数ノードと当該変数ノード間の条件を示した述語ノードとを含むグラフで表現した解析グラフと当該解析グラフから抽出されたプランおよびサブプランに対する制約をノードやノード間の条件として表したプラン合成制約データとを用いて、サブプランについてコストの低いものを選びながら当該サブプランのサイズを段階的に増加させることで全ての述語ノードが含まれるプランを合成するようにしたので、より高度なプランの精度（つまり、コスト）の最適化を図ることができる、という効果を奏する。
【発明を実施するための最良の形態】
【００２０】
以下に添付図面を参照して、この発明にかかるクエリ処理装置、プログラムおよびクエリ処理方法の最良な実施の形態を詳細に説明する。
【００２１】
本発明の実施の一形態を図１ないし図２２に基づいて説明する。図１は、本発明の実施の一形態にかかるクエリ処理装置１のモジュール構成図である。クエリ処理装置１は、例えば、一般的なパーソナルコンピュータである。
【００２２】
図１に示すように、クエリ処理装置１は、情報処理を行うＣＰＵ（Central Processing Unit）１０１、ＢＩＯＳなどを記憶した読出し専用メモリであるＲＯＭ（Read Only Memory）１０２、各種データを書換え可能に記憶するＲＡＭ（Random Access Memory）１０３、各種データベースとして機能するとともに各種のプログラムを格納するＨＤＤ（Hard Disk Drive）１０４、記憶媒体１１０を用いて情報を保管したり外部に情報を配布したり外部から情報を入手するためのＣＤ−ＲＯＭドライブ等の媒体駆動装置１０５、ネットワーク２を介して外部の他のコンピュータと通信により情報を伝達するための通信制御装置１０６、処理経過や結果等を操作者に表示するＣＲＴ（Cathode Ray Tube）やＬＣＤ（Liquid Crystal Display）等の表示部１０７、並びに操作者がＣＰＵ１０１に命令や情報等を入力するためのキーボードやマウス等の入力部１０８等から構成されており、これらの各部間で送受信されるデータをバスコントローラ１０９が調停して動作する。
【００２３】
このようなクエリ処理装置１では、ユーザが電源を投入するとＣＰＵ１０１がＲＯＭ１０２内のローダーというプログラムを起動させ、ＨＤＤ１０４よりＯＳ（Operating System）というコンピュータのハードウェアとソフトウェアとを管理するプログラムをＲＡＭ１０３に読み込み、このＯＳを起動させる。このようなＯＳは、ユーザの操作に応じてプログラムを起動したり、情報を読み込んだり、保存を行ったりする。ＯＳのうち代表的なものとしては、Ｗｉｎｄｏｗｓ（登録商標）等が知られている。これらのＯＳ上で走る動作プログラムをアプリケーションプログラムと呼んでいる。なお、アプリケーションプログラムは、所定のＯＳ上で動作するものに限らず、後述の各種処理の一部の実行をＯＳに肩代わりさせるものであってもよいし、所定のアプリケーションソフトやＯＳなどを構成する一群のプログラムファイルの一部として含まれているものであってもよい。
【００２４】
ここで、クエリ処理装置１は、アプリケーションプログラムとして、クエリ処理プログラムをＨＤＤ１０４に記憶している。この意味で、ＨＤＤ１０４は、クエリ処理プログラムを記憶する記憶媒体として機能する。
【００２５】
また、一般的には、クエリ処理装置１のＨＤＤ１０４にインストールされるアプリケーションプログラムは、ＣＤ−ＲＯＭやＤＶＤなどの各種の光ディスク、各種光磁気ディスク、フレキシブルディスクなどの各種磁気ディスク、半導体メモリ等の各種方式のメディア等の記憶媒体１１０に記録され、この記憶媒体１１０に記録された動作プログラムがＨＤＤ１０４にインストールされる。このため、ＣＤ−ＲＯＭ等の光情報記録メディアやＦＤ等の磁気メディア等の可搬性を有する記憶媒体１１０も、アプリケーションプログラムを記憶する記憶媒体となり得る。さらには、アプリケーションプログラムは、例えば通信制御装置１０６を介して外部から取り込まれ、ＨＤＤ１０４にインストールされても良い。
【００２６】
クエリ処理装置１は、ＯＳ上で動作するクエリ処理プログラムが起動すると、このクエリ処理プログラムに従い、ＣＰＵ１０１が各種の演算処理を実行して各部を集中的に制御する。クエリ処理装置１のＣＰＵ１０１が実行する各種の演算処理のうち、本実施の形態の特長的な処理について以下に説明する。
【００２７】
図２は、クエリ処理装置１の概略構成を示すブロック図である。図２に示すように、クエリ処理装置１は、クエリ処理プログラムに従うことにより、記憶部であるＨＤＤ１０４に、階層構造を有している構造化文書データであるＸＭＬ（Extensible  Markup  Language）データを格納するデータベースであるＸＭＬデータベース１０を形成する。また、クエリ処理装置１は、クエリ処理プログラムに従うことにより、クエリ受付手段として機能するＸＱｕｅｒｙ受付部９と、クエリ解析手段として機能するＸＱｕｅｒｙ解析部１１と、制約抽出手段として機能するＸＱｕｅｒｙ制約抽出部１２と、制約記憶手段として機能するＸＱｕｅｒｙ制約記憶部１３と、プラン合成手段として機能するプラン合成部１４と、プラン実行手段として機能するプラン実行部１５とを備える。このような構成により、クエリ処理装置１は、ユーザや他システムからに入力されたＸＱｕｅｒｙデータを受け付けて、ＸＭＬデータベース１０を参照して受け付けたＸＱｕｅｒｙデータを満足するＸＭＬデータを生成する。
【００２８】
ここで、図３はＸＭＬデータベース１０に格納されるＸＭＬデータの一例を示す模式図である。ＸＭＬでは、文書構造を構成する個々のパーツを「要素」（エレメント：Element）と呼び、要素はタグ（ｔａｇ）を使って記述する。具体的には、要素の始まりを示すタグ（開始タグ）と、終わりを示すタグ（終了タグ）の２つのタグでデータを挟み込んで、１つの要素を表現している。なお、開始タグと終了タグで挟み込まれたテキストデータは、当該開始タグと終了タグで表された１つの要素に含まれるテキスト要素（テキストノード）である。
【００２９】
図３に示す例では、＜ＲＯＯＴ＞というタグに囲まれた要素のルート要素が存在する。この＜ＲＯＯＴ＞要素の直下には、４件の＜本＞要素が存在し、各＜本＞要素直下には、＜キーワード＞要素、＜タイトル＞要素、＜関連情報＞要素などが存在する。＜関連情報＞要素直下には、＜キーワード＞要素が存在する。４件の＜本＞要素の文書構造は異なっており、それぞれに発生する要素、発生しない要素が存在する。
【００３０】
図４は、図３に示したＸＭＬデータのＸＭＬデータベース１０での格納イメージを示す模式図である。このようなＸＭＬデータベース１０は、本実施の形態においてはＨＤＤ１０４に保存されるが、メモリに常駐する形で存在することもある。
【００３１】
図４に示すように、ＸＭＬデータは、ＤＯＭ（Document  Object  Model）に似た形式でオブジェクトとリンクで表現される。＜ＲＯＯＴ＞オブジェクトの直下には４件の＜本＞オブジェクトが存在し、＜ＲＯＯＴ＞オブジェクトから親子関係を示すリンクでつながれている。オブジェクトの最下層には、テキストデータを示すテキストオブジェクトが存在している。
【００３２】
また、図４の左下には、テキストデータに関する索引が付加されている。ＸＭＬデータベース１０に対するＸＭＬデータの格納時に、事前に指定された要素について、テキスト索引を付けることができる。ここでは、タイトル要素直下にあるテキストについて、テキスト索引が付いている。“ＸＭＬ”、“ＤＢ”、“ＳＧＭＬ”などのキーワードを格納した目次テーブルがあり、それらのキーワードが発生するテキストオブジェクトへの索引リンク（破線）がはられている。
【００３３】
次に、ＸＱｕｅｒｙについて説明する。ＸＭＬデータベース１０に対して所定の条件に合致するＸＭＬデータを抽出する命令を伝えるために使われる問い合わせ言語であるＸＱｕｅｒｙは、ＦＬＷＲ（ｆｏｒ−ｌｅｔ−ｗｈｅｒｅ−ｒｅｔｕｒｎ）という構文パターンで説明できる。以下に、ＸＱｕｅｒｙの言語仕様を手続き的な観点で説明する。
【００３４】
ｆｏｒ節の構文は、「ｆｏｒ  変数  ｉｎ  式」である。ｆｏｒ節の構文は、式を満足するものを変数に代入してループするという意味を持つ。
【００３５】
ｌｅｔ節の構文は、「ｌｅｔ  変数  ：＝  式」である。ｌｅｔ節の構文は、式を満足するものを集約してシーケンスとして変数に代入するという意味を持つ。シーケンスとは、フラットなリストである。
【００３６】
ｗｈｅｒｅ節は、Ｆで繰り返されるループを制限するものである。ｗｈｅｒｅ節の構文は、「ｗｈｅｒｅ  式」である。ｗｈｅｒｅ節の構文は、式を満足するものだけループをまわし、そうでないものはループをスキップするという意味を持つ。
【００３７】
ｒｅｔｕｒｎ節は、ＸＱｕｅｒｙを処理した結果をフォーマット化するものである。ｒｅｔｕｒｎ節の構文は、「ｒｅｔｕｒｎ  式」である。ｒｅｔｕｒｎ節の構文は、変数を含む任意のＸＭＬデータを記述することができる。
【００３８】
変数の構文は、「＄文字列」である。入れ子問い合わせなどで二重宣言された場合を除き、同じ文字列を持つ変数は同一のものと見なされる。
【００３９】
ＸＭＬデータの要素間の階層条件を指定するオペレータとして、ＸＱｕｅｒｙでは以下のようなものがある。
・“／”              要素間は親子関係であることを示すオペレータ
・“／／”       要素間は先祖子孫関係であることを示すオペレータ
・“．”              任意の要素
【００４０】
ここで、図５はＸＱｕｅｒｙデータの一例を示す模式図である。図５に示すＸＱｕｅｒｙデータは、「ＸＭＬデータベースのルート直下にある本（＄ｂｏｏｋ）について、タイトルが“ＸＭＬ”を持つものを集約し（＄ｔｉｔｌｅ）、タイトルのテキストと＜本＞要素の全てを展開したＸＭＬデータを＜結果＞要素で囲んで一覧にせよ」という要求を示している。
【００４１】
次に、図２に示したクエリ処理装置１のクエリ処理機能を構成する各部について詳述する。
【００４２】
ＸＱｕｅｒｙ受付部９は、ユーザや他システムからに入力されたＸＱｕｅｒｙデータを受け付ける。
【００４３】
ＸＱｕｅｒｙ解析部１１は、ＸＱｕｅｒｙ受付部９で受け付けたＸＱｕｅｒｙデータを構文解析し、ＸＱｕｅｒｙ解析グラフを生成する。ＸＱｕｅｒｙ解析グラフは、Ｙａｃｃ（Yet  Another  Compiler  Compiler）などの構文解析ツールを使うことで機械的に生成することができる。ここで、図６は図５のＸＱｕｅｒｙデータに基づいて生成したＸＱｕｅｒｙ解析グラフを示す模式図である。図６に示すように、ＸＱｕｅｒｙ解析グラフとは、ＸＱｕｅｒｙデータを構成する条件をグラフで表現したものになっている。図５のＸＱｕｅｒｙデータを構成する条件は、以下の通りである。
・ＸＭＬデータの要素間の階層に関する条件
−ｒｏｏｔ要素直下（／）に本要素がある。
−本要素の子孫（／／）にタイトル要素がある。
−タイトル要素直下（／）にテキスト要素がある。
・ＸＭＬデータのテキストに関する条件
−タイトル要素直下のテキストは“ＸＭＬ”と等しい（＝）。
・ｌｅｔ節やｗｈｅｒｅ節に関する情報
−タイトル要素直下のテキストが“ＸＭＬ”と等しい本は入れ子である。
【００４４】
ここで、ＸＭＬデータベース１０上のオブジェクトが束縛される変数に相当するものを変数ノードと呼ぶ（図６中では、丸で示している）。また、ＸＱｕｅｒｙデータで明示的に宣言された変数「＄文字列」に相当する変数ノードを軸ノードと呼ぶ（図６中では、二重丸で示している）。また、変数ノード間に対する条件をＸＱｕｅｒｙ解析グラフ述語（以下、述語ノード）と呼ぶ（図６中では、四角形で示している）。さらに、ｌｅｔ節やｗｈｅｒｅ節を表す情報は、ＸＱｕｅｒｙ解析グラフメタノード（以下、メタノード）と呼ぶ（図６中では、菱形で示している）。
【００４５】
ＸＱｕｅｒｙ制約抽出部１２は、ＸＱｕｅｒｙ解析部１１が生成したＸＱｕｅｒｙ解析グラフをスキャンし、そこからプラン合成する上でのプラン合成制約データを抽出し、ＸＱｕｅｒｙ制約記憶部１３を更新する。なお、ＸＱｕｅｒｙ制約抽出部１２における制約データ抽出処理の詳細については後述する。
【００４６】
プラン合成部１４は、ＸＱｕｅｒｙ解析グラフとＸＱｕｅｒｙ制約記憶部１３に記憶されているプラン合成制約データを使って、要求であるＸＱｕｅｒｙデータを満足するＸＭＬデータを生成するためのプランを生成する。プランとは、ＸＭＬデータベース１０に対するアクセス操作、またはメモリ上の操作を実行する様々なオペレータ列から構成される。このようなプラン合成部１４は、任意個数のサブプランを合成して新たなサブプランを生成するための任意個数のサブプラン合成手段であるサブプラン合成部を備えている。すなわち、プラン合成部１４は、２サブプラン合成部１４ａ、３サブプラン合成部１４ｂ、Ｎサブプラン合成部１４ｃという構成要素からなっている。なお、サブプランとは、プランを構成する部分オペレータ列を意味する。２サブプラン合成部１４ａは、２つのサブプランを合成し、新たなサブプランを生成する。３サブプラン合成部１４ｂは、３つのサブプランを合成し、新たなサブプランを生成する。Ｎサブプラン合成部１４ｃは、任意個数（Ｎ個）のサブプランを合成し、新たなサブプランを生成する。
【００４７】
プラン実行部１５は、プラン合成部１４で生成したプランを実行することで、要求であるＸＱｕｅｒｙデータを満足するＸＭＬデータを結果ＸＭＬデータとして生成する。
【００４８】
ここで、ＸＱｕｅｒｙ制約記憶部１３に記憶されているデフォルトのプラン合成制約データ（開始制約１３ａ，合成制約１３ｂ）について説明する。図７は、デフォルトのプラン合成制約データを示す模式図である。デフォルトのプラン合成制約データは、後述するプラン合成部１４の各処理に対応するプラン合成制約データであって、開始制約、合成制約Ａ、合成制約Ｂ、合成制約Ｃの各プラン合成制約データで構成されている。以下において、図７に示すデフォルトのプラン合成制約データについて詳述する。
【００４９】
図７に示す開始制約は、「末端述語ノードを開始述語ノードとできる。」である。これは、サブプランの開始は末端述語ノードからであるという制約を示している。
【００５０】
図７に示す合成制約Ａは、２サブプラン合成部１４ａにおいて、以下の（１）（２）（３）を満足することである。
（１）ｐｘとｐｙが変数ノードｎで接続している。
（２）ｐｘとｐｙの共通述語ノードが存在しない。
（３）ｐｘとｐｙが異なるＯＲ／ＡＮＤ述語ノードを処理していない。
【００５１】
（１）は、ｐｘとｐｙが隣接するという制約を示している。（２）は、既に処理されている述語ノードを繰り返し処理しないという制約を示している。（３）は、各ＯＲ／ＡＮＤ処理は個別に行い、同時に処理してはならないという制約を示している。各ＯＲ／ＡＮＤは個別に処理した上で論理和（ＵＮＩＯＮ）をとるべきだからである。
【００５２】
図７に示す合成制約Ｂは、３サブプラン合成部１４ｂにおいて、以下の（１）（２）（３）を満足することである。
（１）ｐｘとｐｙ、ｐｘとｐｚがそれぞれ変数ノードｎ、ｍで接続している。
（２）ｐｘとｐｙ、ｐｘとｐｚ、ｐｙとｐｚ、それぞれに共通述語ノードが存在しない。
（３）ｐｘとｐｙ、ｐｘとｐｚ、ｐｙとｐｚ、それぞれ異なるＯＲ／ＡＮＤ述語ノードを処理していない。
【００５３】
（１）は、ｐｘを仲介として、ｐｙとｐｚが隣接するという制約を示している。（２）は、既に処理されている述語ノードを繰り返し処理しないという制約を示している。（３）は、各ＯＲ／ＡＮＤ処理は個別に行い、同時に処理してはならないという制約を示している。各ＯＲ／ＡＮＤは個別に処理した上で論理和（ＵＮＩＯＮ）をとるべきだからである。なお、（２）（３）については、合成制約Ａの（２）（３）と同じである。
【００５４】
図７に示す合成制約Ｃは、Ｎサブプラン合成部１４ｃにおいて、以下の（１）（２）を満足することである。
（１）ｐｘ，ｐｙ，．．．（複数個のサブプラン）をそれぞれＯＲ／ＡＮＤ述語ノードを全て処理している。
（２）ｐｘ，ｐｙ，．．．（複数個のサブプラン）を合成したサブプランのサイズがＬｅｖｅｌである。
【００５５】
以上のように、本実施の形態によれば、事前に宣言的な制約条件だけを背景知識に加えるだけでよく、ルールのような干渉性を意識する必要はない。また、網羅的なルールを生成する必要はない。
【００５６】
次に、ＸＱｕｅｒｙ制約抽出部１２における制約データ抽出処理について説明する。図８は、ＸＱｕｅｒｙ制約抽出部１２における制約データ抽出処理の流れを示すフローチャートである。図８に示すように、ＸＱｕｅｒｙ制約抽出部１２は、ＸＱｕｅｒｙ解析部１１が生成したＸＱｕｅｒｙ解析グラフを受け取ると（ステップＳ１のＹｅｓ）、ＸＱｕｅｒｙ解析グラフからノードを選択する（ステップＳ２）。
【００５７】
ＯＲを表すメタノードがある場合には（ステップＳ３のＹｅｓ）、プラン合成制約データの合成制約Ａに対し、「各ＯＲ／ＡＮＤが含んでいる軸ノード集合に差があれば、各軸ノードをつなぐ共通述語ノードに対応するサイズ１のサブプランのみがＯＲ／ＡＮＤ処理サブプランと合成できる」を追加し、ＸＱｕｅｒｙ制約記憶部１３を更新する（ステップＳ４）。このようなプラン合成制約データを追加するのは、以下の理由による。
【００５８】
ｗｈｅｒｅ節を記述できる論理式は、積和形に正規化されているものとする。ＯＲを処理する場合、各論理積（ＡＮＤ式）の処理結果の和集合（ＵＮＩＯＮ）を取ればよい。ただし、各論理積が異なる軸変数を対象にしている場合は、各処理結果が同じデータ構造を持たない可能性がある。その場合、各処理結果のデータ構造を合わせるために制約を追加する。
【００５９】
入れ子を表すメタノードがある場合には（ステップＳ５のＹｅｓ）、プラン合成制約データの合成制約Ａに対し、「上位変数ノードと下位変数ノードの間に導出の順序制約が存在する」を追加し、ＸＱｕｅｒｙ制約記憶部１３を更新する（ステップＳ６）。このようなプラン合成制約データを追加するのは、以下の理由による。
【００６０】
ｌｅｔ節を処理する場合、気をつけなければならないことがある。図５のＸＱｕｅｒｙデータで説明する。「ｒｏｏｔ要素直下（／）に本要素がある。その直下にタイトル要素があり、そのタイトル要素のテキストデータが“ＸＭＬ”である。」というのが条件になっているが、本要素は必ずしもタイトル要素を子要素として持つ必要はなく、またタイトル要素があっても、必ずしも“ＸＭＬ”と等しくなる必要はない。その場合の＄ｔｉｔｌｅ変数は空シーケンス｛｝になる。ｌｅｔ節とは、このようにＦｏｒ節が指定するループを束縛するものではないのである。これに気をつけないと誤った結果を出力してしまう。そのために、＄ｂｏｏｋとそれ以下のｌｅｔ節に導出の順序制約を設定することで、誤りを回避する。
【００６１】
述語ノードが「＝“テキスト”」であり、ＸＭＬデータベース１０中にテキスト索引が付いていない場合には（ステップＳ７のＹｅｓ）、プラン合成制約データの開始制約に対し、「該当する述語ノードから開始できない」を追加し、ＸＱｕｅｒｙ制約記憶部１３を更新する（ステップＳ８）。このようなプラン合成制約データを追加するのは、テキスト索引が無いので、それから開始するサブプランはありえないことを示している。
【００６２】
上述したようなステップＳ２〜Ｓ８の処理は、ＸＱｕｅｒｙ解析グラフに走査していないノードが無いと判定されるまで（ステップＳ７のＮｏ）、繰り返される。
【００６３】
図９は、図６のＸＱｕｅｒｙ解析グラフに対してＸＱｕｅｒｙ制約抽出部１２で処理した結果である合成制約Ａの追加内容である。図６において入れ子を表すメタノードが存在するので、合成制約Ａに以下を追加する。
「上位変数ノードと下位変数ノードの間に導出の順序制約が存在する」
ここでは上位変数ノードは“本”変数ノード［２］を示し、下位変数ノードは“タイトル”変数ノード［３］を示す。変数ノード［３］を処理した後、変数ノード［２］を導出してはいけないという制約が示されている。つまり、「変数ノード［２］を具体化する述語ノード［１０］を処理した後で述語ノード［１１］が処理できる」ということになる。
【００６４】
以上のように、本実施の形態によれば、プラン合成制約データは、論理和（ＯＲ）条件を処理するサブプランが合成可能な条件や入れ子（ｌｅｔ）節を処理するサブプランが合成可能な条件であることにより、入れ子やパスも含めたプランの最適化を行うことができる。
【００６５】
続いて、プラン合成部１４におけるプラン合成処理について説明する。図１０は、プラン合成部１４におけるプラン合成処理の流れを示すフローチャートである。図１０に示すように、プラン合成部１４は、前述したように、ＸＱｕｅｒｙ解析グラフとＸＱｕｅｒｙ制約記憶部１３に記憶されているプラン合成制約データを使って、要求であるＸＱｕｅｒｙデータを満足するＸＭＬデータを生成するためのプランを生成する。
【００６６】
図１０に示すように、プラン合成部１４は、開始制約を満足するサイズ１の初期サブプラン集合を作成した後（ステップＳ１１）、“Ｌｅｖｅｌ”という当該プラン合成処理で更新および参照される変数を“２”にする（ステップＳ１２）。この“Ｌｅｖｅｌ”は、２サブプラン合成部１４ａにおける処理（ステップＳ１３）、３サブプラン合成部１４ｂにおける処理（ステップＳ１４）、Ｎサブプラン合成部１４ｃにおける処理（ステップＳ１５）でそれぞれ参照される。ステップＳ１３〜Ｓ１４の処理は、“Ｌｅｖｅｌ”を１ずつ増やしながら（ステップＳ１７）、繰り返される。終了条件は、ＸＱｕｅｒｙ解析グラフを構成する全述語ノード数に等しくなるまで、すなわち“Ｌｅｖｅｌ＝Ｎ”になることである（ステップＳ１６のＹｅｓ）。これは、段階的にサブプランサイズを増加させながら、サブプランを合成していき、最終的にプランに到達する戦略をとるようにしたものである。
【００６７】
ここで、ステップＳ１３の２サブプラン合成部１４ａにおける処理について、図１１のフローチャートを参照して説明する。図１１に示すように、２サブプラン合成部１４ａは、まず、サイズ１のサブプラン集合ＳｅｔｘをプランＤＢ２０より取り出すとともに、サイズＬｅｖｅｌ−１のサブプラン集合ＳｅｔｙをプランＤＢ２０より取り出す（ステップＳ１３１）。ここで、プランＤＢ２０について説明する。前述したように、プラン合成部１４では、段階的にサブプランサイズを増加させながらサブプランを合成していく。そこで、生成された中間解であるサブプランは、サブプランを特徴付けるキーとともにプランＤＢ２０に登録される。ここで、サブプランのキーは、サブプランが処理した述語集合、および述語集合のサイズとする。
【００６８】
この時点で、Ｌｅｖｅｌサイズまで到達したということは、必ずサイズ１のサブプランとサイズＬｅｖｅｌ−１のサブプランは存在することになる。
【００６９】
続くステップＳ１３２では、ｐｘ∈Ｓｅｔｘ、ｐｙ∈Ｓｅｔｙを選ぶ。より詳細には、任意のサイズ１のｐｘをＳｅｔｘから選び、任意のサイズＬｅｖｅｌ−１のｐｙをＳｅｔｙから選ぶ。
【００７０】
そして、ｐｘとｐｙが先に説明した合成制約Ａを満足していると判断した場合には（ステップＳ１３３のＹｅｓ）、ｐｘ，ｐｙを合成し、サイズＬｅｖｅｌのサブプランｐｚとする（ステップＳ１３４）。プラン上は、以下の２通りの解釈を行う。
【００７１】
第１には、ｐｙを起点にｐｘを取り込んでいく、というものである。例えば、ＸＭＬデータのパスをたどる操作がこれに該当する。ルート要素からある要素へ下がっていく下流走査（Ｄｅｓｃｅｎｄａｎｔ）、さらにその要素からより深い要素へ下がっていく下流走査（Ｄｅｓｃｅｎｄａｎｔ）を行う、などのケースに該当する。例えば、図１４に示す左上のプラン列において、テキスト索引（Ｉｎｄｅｘ）から要素の上流走査（Ａｎｃｅｓｔｏｒ）がそれに該当する。
【００７２】
第２には、ｐｘとｐｙの結果を結合（ＪＯＩＮ）する、というものである。例えば、２つのテキスト索引の処理（Ｉｎｄｅｘ）の結果をＪＯＩＮする、などのケースに該当する。
【００７３】
続くステップＳ１３５においては、ｐｚのコストを計算し、プランＤＢ２０より同じキーを持つサブプランｐｚ’と比較する。
【００７４】
プランニング段階でのコスト計算は、あくまでも見込みに過ぎない。また、コストの定義にはいろいろあるが、例として中間件数を用いる。中間件数を見積もるため、ＸＭＬデータベース１０には下記に示すようなプロファイルデータがあるものとする。
・テキスト索引の結果件数、絞込み率
・上位要素から見た下位要素の階層構造上の展開率
コストは、各サブプランのコストと、直前に実行された合成に対応するオペレータの処理コストとの総和で計算される。例えば、ｐｘの中間件数が１００で、ｐｙの中間件数が１０００で、その合成により中間件数が２００になったとすれば、コスト＝１００＋１０００＋２００とする。それぞれの中間件数は、プロファイルデータから導ける。
【００７５】
次いで、ｐｚのコストとｐｚ’のコストとを比較し（ステップＳ１３６）、ｐｚのコストよりもｐｚ’のコストが大きい場合には、プランＤＢ２０のｐｚ’をｐｚで置き換える（ステップＳ１３６）。一方、仮にｐｚのコストの方が小さければ、そのままステップＳ１３２に戻る。
【００７６】
ステップＳ１３２〜Ｓ１３７の処理は、ｐｘとｐｙの組み合わせがなくなるまで（Ｓ１３８のＮｏ）、繰り返される。
【００７７】
ここで、ステップＳ１４の３サブプラン合成部１４ｂにおける処理について、図１２のフローチャートを参照して説明する。３サブプラン合成部１４ｂは、概略的には、プランＤＢ２０に格納された３つのサブプランを使ってサブプランを合成していくものである。
【００７８】
図１２に示すように、３サブプラン合成部１４ｂは、まず、Ｌｅｆｔ＝１とし（ステップＳ１４１）、Ｒｉｇｈｔ＝Ｌｅｖｅｌ−Ｌｅｆｔとする（ステップＳ１４２）。
【００７９】
続くステップＳ１４３では、以下の処理を実行する。
・サイズ１のサブプラン集合ＳｅｔｘをプランＤＢ２０より取り出す。
・サイズＬｅｆｔのサブプラン集合ＳｅｔｙをプランＤＢ２０より取り出す。
・サイズＲｉｇｈｔのサブプラン集合ＳｅｔｚをプランＤＢ２０より取り出す。
【００８０】
その後、ｐｘ∈Ｓｅｔｘ，ｐｙ∈Ｓｅｔｙ，ｐｚ∈Ｓｅｔｚを選んだ後（ステップＳ１４４）、ｐｘ，ｐｙ，ｐｚが合成制約Ｂを満足しているか否かを判定する（ステップＳ１４５）。これは、ｐｘを仲介として、ｐｙとｐｚが隣接するという制約を示している。
【００８１】
ｐｘ，ｐｙ，ｐｚが合成制約Ｂを満足していると判定された場合には（ステップＳ１４５のＹｅｓ）、ｐｘ，ｐｙ，ｐｚを合成し、サイズＬｅｖｅｌのサブプランｐｗとする（ステップＳ１４６）。
【００８２】
一方、ｐｘ，ｐｙ，ｐｚが合成制約Ｂを満足していないと判定された場合には（ステップＳ１４５のＮｏ）、ステップＳ１４４に戻り、ｐｘ∈Ｓｅｔｘ，ｐｙ∈Ｓｅｔｙ，ｐｚ∈Ｓｅｔｚを選択する。
【００８３】
続くステップＳ１４７では、ｐｗのコストを計算し、プランＤＢ２０より同じキーを持つサブプランｐｗ’と比較する。その結果、ｐｗのコストよりもｐｗ’のコストの方が大きいと判定された場合には、プランＤＢ２０のｐｗ’をｐｗで置き換える（ステップＳ１４９）。
【００８４】
一方、ｐｗのコストよりもｐｗ’のコストの方が小さいと判定された場合には、ステップＳ１４４に戻り、ｐｘ∈Ｓｅｔｘ，ｐｙ∈Ｓｅｔｙ，ｐｚ∈Ｓｅｔｚを選択する。
【００８５】
ステップＳ１４４〜Ｓ１４９の処理は、ｐｘとｐｙとの全ての組み合わせについて処理するまで（ステップＳ１５０のＮｏ）、繰り返される。
【００８６】
ｐｘとｐｙとの全ての組み合わせについての処理が終了すると（ステップＳ１５０のＮｏ）、Ｌｅｆｔと（Ｌｅｖｅｌ−１）とを比較する（ステップＳ１５１）。
【００８７】
ステップＳ１４２〜Ｓ１５０の処理は、Ｌｅｆｔが（Ｌｅｖｅｌ−１）よりも大きくなるまで繰り返される。
【００８８】
ここで、ステップＳ１５のＮサブプラン合成部１４ｃにおける処理について、図１３のフローチャートを参照して説明する。Ｎサブプラン合成部１４ｃは、概略的には、プランＤＢ２０に格納されたＯＲメタノード下にある各ＯＲ／ＡＮＤを含むサブプランを合成していくものである。
【００８９】
図１３に示すように、Ｎサブプラン合成部１４ｃは、まず、ＯＲ／ＡＮＤ処理を含むサブプラン集合ＳｅｔｘをプランＤＢ２０より取り出した後（ステップＳ１６１）、ｐｘ，ｐｙ，．．．∈Ｓｅｔｘを選ぶ（ステップＳ１６２）。
【００９０】
次いで、ｐｘ，ｐｙ，．．が合成制約Ｃを満足しているか否かを判定する（ステップＳ１６３）。
【００９１】
ｐｘ，ｐｙ，．．が合成制約Ｃを満足していると判定した場合には（ステップＳ１６３のＹｅｓ）、ｐｘ，ｐｙ，．．．を合成し、サイズＬｅｖｅｌのサブプランｐｗとする（ステップＳ１６３）。
【００９２】
一方、ｐｘ，ｐｙ，．．が合成制約Ｃを満足していないと判定された場合には（ステップＳ１６３のＹｅｓ）、ステップＳ１６２に戻り、ｐｘ，ｐｙ，．．．∈Ｓｅｔｘを選択する。
【００９３】
続くステップＳ１６５では、ｐｗのコストを計算し、プランＤＢ２０より同じキーを持つサブプランｐｗ’と比較する。その結果、ｐｗのコストよりもｐｗ’のコストの方が大きいと判定された場合には、プランＤＢ２０のｐｗ’をｐｗで置き換える（ステップＳ１６７）。
【００９４】
一方、ｐｗのコストよりもｐｗ’のコストの方が小さいと判定された場合には、ステップＳ１６２に戻り、ｐｘ，ｐｙ，．．．∈Ｓｅｔｘを選択する。
【００９５】
ステップＳ１６２〜Ｓ１６７の処理は、ｐｘとｐｙとの全ての組み合わせについて処理するまで（ステップＳ１６８のＮｏ）、繰り返される。
【００９６】
以上により、プラン合成部１４においてプラン合成処理が実行される。
【００９７】
図１４は、図６のＸＱｕｅｒｙ解析グラフと図９の合成制約Ａに対してプラン合成部１４で処理した結果であるプランの一例を示す模式図である。図１４に示すように、初期サブプラン集合として、述語ノード［１２］と［１０］とが存在する。
Ｌｅｖｅｌ＝２
・２サブプラン合成部１４ｂで、述語ノード［１２］に対応するサイズ１のサブプランと［１１］に対応するサイズ１のサブプランを合成する→Ｐｘ
Ｌｅｖｅｌ＝３
・２サブプラン合成部１４ｂで述語ノード［１０］とＰｘを合成する。
・その場合、上位変数を制限しないように、プラン上ではＯｕｔｅｒＪｏｉｎを選択する。
プラン［１２］に対応：Ｉｎｄｅｘ（タイトル／ｔｅｘｔ（）、  “ＸＭＬ”）
プラン［１１］に対応：Ａｎｃｅｓｔｏｒ（タイトル、本）
プラン［１０］に対応：Ｄｅｓｃｅｎｄａｎｔ（ＤＢ、本）
最後に、ＯｕｔｅｒＪｏｉｎ（本）を行う。
【００９８】
最後に、プラン実行部１５は、プラン合成部１４で生成したプランを実行することで、要求であるＸＱｕｅｒｙデータを満足するＸＭＬデータを結果ＸＭＬデータとして生成する。図１５は、図１４に示すプランをプラン実行部１５で実行した結果であるＸＭＬデータを示す模式図である。
【００９９】
このように本実施の形態によれば、ＸＭＬデータベース１０上のオブジェクトが束縛される変数に相当する変数ノードと当該変数ノード間の条件を示した述語ノードとを含むグラフで表現した解析グラフと当該解析グラフから抽出されたプランおよびサブプランに対する制約をノードやノード間の条件として表したプラン合成制約データとを用いて、サブプランについてコストの低いものを選びながら当該サブプランのサイズを段階的に増加させることで全ての述語ノードが含まれるプランを合成するようにしたので、より高度なプランの精度（つまり、コスト）の最適化を図ることができる。
【０１００】
［実施例］
ここで、クエリ処理装置１を利用した実施例について説明する。
【０１０１】
（実施例１）
図１６は、ＸＱｕｅｒｙデータの一例を説明する模式図である。図１６に示すＸＱｕｅｒｙデータは、
「ＸＭＬデータベースのルート直下にある本（＄ｂｏｏｋ）とタイトル（＄ｔｉｔｌｅ）について、タイトルが“ＸＭＬ”を持つもの、または本のテキスト部分が“ＸＭＬデータベース”であるものを選択し、タイトルのテキストと＜本＞要素の全てを展開したＸＭＬデータを＜結果＞要素で囲んで一覧にせよ」
という要求を示している。
【０１０２】
図１７は、図１６に示したＸＱｕｅｒｙデータをＸＱｕｅｒｙ解析グラフにしたものである。図１６のＸＱｕｅｒｙデータを構成する条件は、以下の通りである。
・ＸＭＬデータの要素間の階層に関する条件
−ｒｏｏｔ要素直下（／）に本要素がある。
−本要素の子孫（／／）にタイトル要素がある。
−タイトル要素直下（／）にテキスト要素がある。
−本の子孫（／／）に任意要素がある。
・ＸＭＬデータのテキストに関する条件
−タイトル要素直下のテキストは”ＸＭＬ”と等しい（＝）。
−本の子孫となる任意要素直下のテキストは“ＸＭＬデータベース”と等しい（＝）。
・ｗｈｅｒｅ節に関する情報
−タイトルが“ＸＭＬ”と等しい、または“任意要素直下のテキストは”ＸＭＬデータベース“と等しい。
【０１０３】
図１８は、図１７のＸＱｕｅｒｙ解析グラフに対してＸＱｕｅｒｙ制約抽出部１２で処理した結果である開始制約と合成制約Ａの追加内容である。図１７において、ＯＲを表すメタノードが存在するので、合成制約Ａに以下の制約を追加する。
「各ＯＲ／ＡＮＤが含んでいる軸ノード集合に差があれば、各軸ノードをつなぐ共通述語ノードに対応するサイズ１のサブプランのみがＯＲ／ＡＮＤ処理サブプランと合成できる」
【０１０４】
図１７では、ＯＲ／ＡＮＤ［８］の軸ノード集合は、タイトル要素を示す［３］である。また、ＯＲ／ＡＮＤ［９］の軸ノード集合は、本要素を示す［２］である。ここで軸ノード集合に差があるので、これらをつなぐ共通述語（つまり、ＯＲ／ＡＮＤとは関係ない述語）を選ぶ。このケースでは、述語ノード［１１］である。以下の制約を追加する。
（１）［１３］を含むＯＲ／ＡＮＤ処理サブプランに追加できる述語ノードは［１１］のみ
（２）［１２］，［１４］を含むＯＲ／ＡＮＤ処理サブプランに追加できる述語ノードは［１１］のみ
【０１０５】
ＯＲを処理する場合、各論理積（ＡＮＤ式）の処理結果の和集合（ＵＮＩＯＮ）を取ればよい。ただし、各論理積が異なる軸変数を対象にしている場合は、各処理結果が同じデータ構造を持たない可能性がある。その場合、各処理結果のデータ構造を合わせるために制約を追加する。
【０１０６】
このケースでは、タイトルにテキスト索引が付加されていない場合を想定している。述語ノードが「＝“テキスト”」であり、ＸＭＬデータベース中にテキスト索引が付いていないことがわかったので、開始制約に以下を追加する。
（１）述語［１４］から始まるサブプランは不可である。
【０１０７】
図１９は、図１７のＸＱｕｅｒｙ解析グラフと図１８の合成制約Ａに対してプラン合成部１４で処理した結果であるプランの一例を示す模式図である。図１９に示すように、初期サブプラン集合として、述語ノード［１３］と［１０］とが存在する。
Ｌｅｖｅｌ＝２
・２サブプラン合成部１４ａで、述語ノード［１３］に対応するサイズ１のサブプランと［１１］に対応するサイズ１のサブプランを合成する→Ｐｘ
・２サブプラン合成部１４ａで、述語ノード［１０］に対応するサイズ１のサブプランと［１２］に対応するサイズ１のサブプランを合成する→Ｐｙ
Ｌｅｖｅｌ＝３
・２サブプラン合成部１４ａで、述語ノード［１４］とＰｘを合成する→Ｐｚ
Ｌｅｖｅｌ＝４
・２サブプラン合成部１４ａで、述語ノード［１１］とＰｚを合成する。
Ｌｅｖｅｌ＝５
・Ｎサブプラン合成部１４ｃで、ＰｚとＰｘを合成する。
和集合をとるために、ＵＮＩＯＮオペレータを使う。
プラン［１３］に対応：Ｉｎｄｅｘ（タイトル／ｔｅｘｔ（）、“ＸＭＬ”）
プラン［１１］に対応：Ａｎｃｅｓｔｏｒ（タイトル、本）
プラン［１０］に対応：Ｄｅｓｃｅｎｄａｎｔ（ＤＢ、本）
プラン［１２］に対応：Ｄｅｓｃｅｎｄａｎｔ（本、・）
プラン［１４］に対応：Ｔｅｓｔ（・／ｔｅｘｔ（）、“ＸＭＬデータベース“）
変数ノード［４］は求められているので、Ｔｅｓｔになる。
プラン［１１］に対応：Ｄｅｓｃｅｎｄａｎｔ（本、タイトル）
プラン［１０］に対応：Ａｎｃｅｓｔｏｒ（本、ＤＢ）
【０１０８】
図２０は、図１９のプランをプラン実行部１５で実行した結果であるＸＭＬデータを示す模式図である。
【０１０９】
（実施例２）
図２１は、図１７のＸＱｕｅｒｙ解析グラフと図１８の合成制約Ａに対してプラン合成部で処理した結果であるプランの一例を示す模式図である。
【０１１０】
実施例２では、入力されるＸＱｕｅｒｙは図１６に示すようなＸＱｕｅｒｙであり、実施例１と同様である。しかしながら、実施例２は、タイトルにテキスト索引が付加されている場合を想定している点で、実施例１とは異なっている。述語ノードが「＝“テキスト”」であり、ＸＭＬデータベース中にテキスト索引が付いていることがわかったので、開始制約に以下を追加しない。
（１）述語［１４］から始まるサブプランは不可である。
【０１１１】
図２１に示すように、初期サブプラン集合として、述語ノード［１３］と［１０］と［１４］とが存在する。
Ｌｅｖｅｌ＝２
・２サブプラン合成部１４ａで、述語ノード［１３］に対応するサイズ１のサブプランと［１１］に対応するサイズ１のサブプランを合成する→Ｐｘ
・２サブプラン合成部１４ａで、述語ノード［１４］に対応するサイズ１のサブプランと［１２］に対応するサイズ１のサブプランを合成する→Ｐｙ
Ｌｅｖｅｌ＝３
・２サブプラン合成部１４ａで、述語ノード［１１］とＰｙを合成する→Ｐｚ
Ｌｅｖｅｌ＝５
・Ｎサブプラン合成部１４ｃで、ＰｚとＰｘを合成する。
和集合をとるために、ＵＮＩＯＮオペレータを使う。
【０１１２】
このように入力が同じＸＱｕｅｒｙであっても、ＸＭＬデータベース１０の索引設定などの状況が異なれば、図１９と図２１のようにプランが変化することがわかる。
【０１１３】
図２２は、図２１のプランをプラン実行部１５で実行した結果であるＸＭＬデータを示す模式図である。
【図面の簡単な説明】
【０１１４】
【図１】本発明の実施の一形態にかかるクエリ処理装置のモジュール構成図である。
【図２】クエリ処理装置の概略構成を示すブロック図である。
【図３】ＸＭＬデータの一例を示す模式図である。
【図４】図３に示したＸＭＬデータの格納イメージを示す模式図である。
【図５】ＸＱｕｅｒｙデータの一例を示す模式図である。
【図６】図５のＸＱｕｅｒｙデータに基づいて生成したＸＱｕｅｒｙ解析グラフを示す模式図である。
【図７】デフォルトのプラン合成制約データを示す模式図である。
【図８】制約データ抽出処理の流れを示すフローチャートである。
【図９】合成制約Ａの追加内容を示す模式図である。
【図１０】プラン合成処理の流れを示すフローチャートである。
【図１１】２サブプラン合成部における処理の流れを示すフローチャートである。
【図１２】３サブプラン合成部における処理の流れを示すフローチャートである。
【図１３】Ｎサブプラン合成部における処理の流れを示すフローチャートである。
【図１４】プランの一例を示す模式図である。
【図１５】図１４に示すプランを実行したＸＭＬデータを示す模式図である。
【図１６】ＸＱｕｅｒｙデータの一例を説明する模式図である。
【図１７】図１６のＸＱｕｅｒｙデータに基づいて生成したＸＱｕｅｒｙ解析グラフを示す模式図である。
【図１８】合成制約Ａの追加内容を示す模式図である。
【図１９】プランの一例を示す模式図である。
【図２０】図１９のプランを実行したＸＭＬデータを示す模式図である。
【図２１】プランの一例を示す模式図である。
【図２２】図２１のプランを実行したＸＭＬデータを示す模式図である。
【符号の説明】
【０１１５】
１        クエリ処理装置
９        クエリ受付手段
１１      クエリ解析手段
１２      制約抽出手段
１３      制約記憶手段
１４      プラン合成手段
１４ａ〜１４ｃ    サブプラン合成手段
１５      プラン実行手段
【図１】
2008234430.tif 000003
【図２】
2008234430.tif 000004
【図３】
2008234430.tif 000005
【図４】
2008234430.tif 000006
【図５】
2008234430.tif 000007
【図６】
2008234430.tif 000008
【図７】
2008234430.tif 000009
【図８】
2008234430.tif 000010
【図９】
2008234430.tif 000011
【図１０】
2008234430.tif 000012
【図１１】
2008234430.tif 000013
【図１２】
2008234430.tif 000014
【図１３】
2008234430.tif 000015
【図１４】
2008234430.tif 000016
【図１５】
2008234430.tif 000017
【図１６】
2008234430.tif 000018
【図１７】
2008234430.tif 000019
【図１８】
2008234430.tif 000020
【図１９】
2008234430.tif 000021
【図２０】
2008234430.tif 000022
【図２１】
2008234430.tif 000023
【図２２】
2008234430.tif 000024