(57)【特許請求の範囲】
【請求項１】
データベースに記憶され少なくとも１つの要素が階層付けられている構造化文書を検索するための検索条件を示す検索式を受け付ける検索要求受付手段と、
前記検索条件に該当する構造化文書を検索するための検索処理を実行する際に、処理単位となる少なくとも１つの操作を含む当該操作の実行順序を示す検索プランを生成する生成手段と、
前記検索プランに含まれる各前記操作のうち、前記要素の全部又は一部を参照して実行する第１操作が連続して実行されるよう実行順序を最適化する第１最適化手段と、
実行順序が最適化された前記第１操作が文書単位で一括で実行されるよう当該第１操作を複合して複合操作を生成することにより、前記検索プランを最適化する第２最適化手段と、
最適化された前記実行順序に従い、前記データベースを走査して、少なくとも１つの前記要素の全部又は一部を取得し、最適化された前記検索プランに含まれる前記複合操作を文書単位で一括して実行して実行結果を得る検索実行手段と、
前記実行結果を、前記検索式に応じた構造化文書形式に成形して出力する出力手段とを備える
ことを特徴とする構造化文書検索装置。
【請求項２】
最適化された前記実行順序に従い、最適化された前記検索プランに含まれる前記複合操作の実行を前記検索実行手段に順次要求する検索実行順序制御手段を更に備え、
前記検索実行手段は、前記検索実行順序制御手段からの要求に応じて、前記複合操作を実行して、実行結果を得る
ことを特徴とする請求項１に記載の構造化文書検索装置。
【請求項３】
前記検索実行手段は、少なくとも１つの前記構造化文書の前記要素の全部又は一部を取得して、前記構造化文書のそれぞれに対して前記複合操作に含まれる全ての前記第１操作を連続して実行することにより、前記複合操作を文書単位で一括して実行する
ことを特徴とする請求項２に記載の構造化文書検索装置。
【請求項４】
前記操作は、前記構造化文書の少なくとも１つの要素に対する処理内容を示す操作子を含み、
前記第１操作に含まれる第１操作子に対して、前記データベースに記憶されている前記構造化文書の前記要素の全部又は一部を参照して実行することを示す第１種別が対応付けられている割当情報を記憶する記憶手段を更に備え、
前記生成手段は、
前記検索プランに含まれる各前記操作のそれぞれについて、前記割当情報を参照して、当該操作に含まれる前記操作子に対して前記第１種別が対応付けられているか否かを判別することにより、当該操作が前記第１操作であるか否かを各々判別する判別手段と、
前記第１操作であると判別された前記操作に対して前記第１種別を割り当てる割当手段とを有し、
前記第１最適化手段は、前記検索プランに含まれる各前記操作のうち、前記第１種別が割り当てられた操作を前記第１操作として、当該第１操作が連続して実行されるよう実行順序を最適化する
ことを特徴とする請求項２又は３に記載の構造化文書検索装置。
【請求項５】
前記要素の値には、当該値の格納されている格納場所を示すインデクスが対応付けられており、
前記第２最適化手段は、前記検索プランに含まれる前記複合操作以外の操作のうち、前記構造化文書の前記要素の全部又は一部の値の走査を必要とする第２操作が前記複合操作と区別されるよう、前記複合操作を生成することにより、前記検索プランを最適化し、
前記検索実行手段は、
前記データベースを走査して、少なくとも１つの前記構造化文書の前記要素の全部又は一部を取得して、最適化された前記検索プランに含まれる前記複合操作を文書単位で一括して実行する文書単位検索実行手段と、
最適化された前記検索プランに含まれる前記第２操作を実行する手段であって、前記第２操作を実行する際、前記インデクスを走査することにより、前記構造化文書の前記要素の全部又は一部の値を走査して、該当の値を示す前記要素の格納場所を取得するＤＢ単位検索実行手段とを有する
ことを特徴とする請求項２乃至４のいずれか一項に記載の構造化文書検索装置。
【請求項６】
前記文書単位検索実行手段は、前記第２操作の実行後に前記複合操作を実行する場合、取得された前記格納場所を用いて前記データベースを走査して、当該格納場所に値が格納されている前記要素を少なくとも含む前記構造化文書を取得して、当該構造化文書に対して前記複合操作を文書単位で一括して実行する
ことを特徴とする請求項５に記載の構造化文書検索装置。
【請求項７】
前記検索実行手段は、
前記複合操作の実行が前記検索実行順序制御手段から要求された場合、当該複合操作の実行を前記文書単位検索実行手段に要求し、前記第２操作の実行が前記検索実行順序制御手段から要求された場合、当該第２操作の実行を前記ＤＢ単位検索実行手段に要求する実行制御手段を更に有する
ことを特徴とする請求項５に記載の構造化文書検索装置。
【請求項８】
前記実行制御手段は、前記複合操作の実行を前記文書単位検索実行手段に要求する際に、前記複合操作の種別及び当該複合操作の実行に必要な中間結果が、前記文書単位検索実行手段又は前記ＤＢ単位検索実行手段のいずれに保持されているかを、当該中間結果の取得先として示す格納場所識別情報を前記文書単位検索実行手段に送り、当該要求に応じて実行される前記複合操作の実行過程で求められる中間結果を取得し、前記第２操作の実行を前記ＤＢ単位検索実行手段に要求する際に、前記第２操作の種別及び当該第２操作の実行に必要な中間結果が、前記文書単位検索実行手段又は前記ＤＢ単位検索実行手段のいずれに保持されているかを、当該中間結果の取得先として示す格納場所識別情報を前記ＤＢ単位検索実行手段に送り、当該要求に応じて実行される前記第２操作の実行過程で求められる中間結果を取得し、各中間結果に対して集合演算を行い、当該集合演算の結果を前記検索プランの実行結果として得て、
前記文書単位検索実行手段は、前記複合操作の実行が要求された場合、前記格納場所識別情報によって示される前記取得先から前記中間結果を取得して、当該中間結果を用いて、前記複合操作を実行して、新たな中間結果を求め、
前記ＤＢ単位検索実行手段は、前記第２操作の実行が要求された場合、前記格納場所識別情報によって示される前記取得先から前記中間結果を取得して、当該中間結果を用いて、前記第２操作を実行して、新たな中間結果を求める
ことを特徴とする請求項７に記載の構造化文書検索装置。
【請求項９】
前記検索実行手段は、前記実行制御手段からの要求に応じて、前記複合操作の実行過程で求められる中間結果及び前記第２操作の実行過程で求められる中間結果に対して集合演算を実行することにより、当該集合演算の結果を前記検索プランの実行結果として得る演算実行手段を更に有し、
前記実行制御手段は、最適化された検索プランに従って、前記複合操作の実行を前記文書単位検索実行手段に要求する際に、前記複合操作の種別及び当該複合操作の実行に必要な前記中間結果を前記文書単位検索実行手段に送り、当該要求に応じて実行される前記複合操作の実行過程で求められる中間結果を取得し、前記第２操作の実行を前記ＤＢ単位検索実行手段に要求する際に、前記第２操作の種別及び当該第２操作の実行に必要な前記中間結果を前記ＤＢ単位検索実行手段に送り、当該要求に応じて実行される前記第２操作の実行過程で求められる中間結果を取得し、各中間結果に対する集合演算の実行を前記演算実行手段に要求し、
前記文書単位検索実行手段は、前記複合操作の実行が要求された場合、当該複合操作の実行に必要な前記中間結果を用いて、前記複合操作を実行して、新たな中間結果を求め、
前記ＤＢ単位検索実行手段は、前記第２操作の実行が要求された場合、当該第２操作の実行に必要な前記実行結果を用いて、前記第２操作を実行して、新たな中間結果を求める
ことを特徴とする請求項７に記載の構造化文書検索装置。
【請求項１０】
前記第２操作を実行する手段であって、前記第２操作を実行する際、前記データベースを走査することにより、前記構造化文書の前記要素の全部又は一部の値を走査して、該当の値を示す前記要素の格納場所を取得するＤＢ単位検索実行手段と、
前記実行制御手段からの要求に応じて、前記複合操作の実行過程で求められる中間結果及び前記第２操作の実行過程で求められる中間結果に対して集合演算を実行することにより、当該集合演算の結果を前記検索プランの実行結果として得る演算実行手段とを更に備え、
前記検索実行手段は、前記複合操作の実行を前記検索実行順序制御手段から要求された場合、当該複合操作の実行に必要な前記中間結果を前記演算実行手段から取得し、当該複合操作の実行に際して実行される前記第２操作を抽出し、当該第２操作の実行を前記ＤＢ単位検索実行手段に要求し、当該要求に応じて実行される前記第２操作の実行過程で求められる中間結果を取得し、前記第２操作の実行後に前記複合操作を実行する場合、取得された中間結果を用いて処理対象の前記構造化文書を取得して、当該構造化文書に対して前記複合操作を文書単位で一括して実行して、新たな中間結果を求め、前記第２操作の実行を前記検索実行順序制御手段から要求された場合、当該第２操作の実行に必要な前記中間結果を前記演算実行手段から取得し、当該第２操作の実行を前記ＤＢ単位検索実行手段に要求し、当該要求に応じて実行される前記第２操作の実行過程で求められる中間結果を取得し、
前記ＤＢ単位検索実行手段は、前記検索実行手段からの要求に応じて、前記第２操作を実行して、該当の値を示す前記要素の格納場所を前記中間結果として求める
ことを特徴とする請求項２乃至４のいずれか一項に記載の構造化文書検索装置。
【請求項１１】
前記文書単位検索実行手段は、文書単位で前記複合操作を実行する毎に、前記データベースを走査して、前記構造化文書の前記要素の全部又は一部を取得して、前記複合操作を文書単位で一括して実行する
ことを特徴とする請求項５乃至９のいずれか一項に記載の構造化文書検索装置。
【請求項１２】
検索要求受付手段と、生成手段と、第１最適化手段と、第２最適化手段と、検索実行手段と、出力手段とを備える構造化文書検索装置で実行される構造化文書検索方法であって、
前記検索要求受付手段が、データベースに記憶され少なくとも１つの要素が階層付けられている構造化文書を検索するための検索条件を示す検索式を受け付ける検索要求受付ステップと、
前記生成手段が、受け付けられた検索式を解析して、前記検索条件に該当する構造化文書を検索するための検索処理を実行する際の処理単位となる少なくとも１つの操作を含み当該操作の実行順序を示す検索プランを生成する生成ステップと、
前記第１最適化手段が、前記検索プランに含まれる各前記操作のうち、前記要素の全部又は一部を参照して実行する第１操作が連続して実行されるよう実行順序を最適化する第１最適化ステップと、
前記第２最適化手段が、実行順序が最適化された前記第１操作が文書単位で一括で実行されるよう当該第１操作を複合して複合操作を生成することにより、前記検索プランを最適化する第２最適化ステップと、
前記検索実行手段が、最適化された前記実行順序に従い、前記データベースを走査して、少なくとも１つの前記要素の全部又は一部を取得し、最適化された前記検索プランに含まれる前記複合操作を文書単位で一括して実行して実行結果を得る検索実行ステップと、
前記実行結果を、前記検索式に応じた構造化文書形式に成形して出力する出力ステップを含む
ことを特徴とする構造化文書検索方法。
【請求項１３】
請求項１２に記載の構造化文書検索方法をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースに記憶された構造化文書の検索を行う構造化文書検索装置、方法及びプログラムに関する。
【背景技術】
【０００２】
データベース（ＤＢ）に記憶されたデータの検索に際して、検索プランはＤＢ全体に対する操作を示すオペレータの列として表現される。例えば、データがレコード単位で記憶されるＲＤＢ（Relational Database）では、検索式を入力として検索プラナ部が検索プランを生成し、生成された検索プランに従い検索実行部がオペレータを順次取得し、各オペレータによる処理を順次適用することで、検索処理を実行する手順がとられる。即ち、各オペレータによる処理を各々１つの操作とすると、各操作が順次行われることで、検索処理が行われる。通常、各オペレータはＤＢ全体に対して一括で処理を行う方式がとられている。従来の検索プランの最適化では、検索処理時に検索操作で行われる走査処理の処理コストを考慮して、コストの低い操作から優先して実行する検索プランを生成していた（例えば非特許文献１参照）。これにより検索処理の高速化を計っていた。
【０００３】
【非特許文献１】Hector Garcia-Molina, Database System Implementation, Prentice Hall; United States Ed Chapter 6.2, Introduction to Physical-Query-Plan Operators
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ところで、階層構造を有する構造化文書を検索する際にも、従来ＲＤＢで行われているのと同様の手順で検索処理が行われている。しかしながら、構造化文書の場合、一般的に、ＲＤＢに格納されているレコードと比べてデータ量が大きいという特徴がある。また、構造化文書の検索の際には、検索要求に応じて、検索結果として得られた構造化文書中の値を組み合わせて適宜加工して新規の構造化文書として生成してこれを出力する場合がある。これらの処理を行うためには、検索処理時のオペレータの実行や検索結果の加工のための値の取得の際に、ＤＢを逐次走査する必要に迫られることが多い。ＤＢ全体の走査を繰り返し行うことは時間を要するため、検索速度の低下を招く恐れがあった。
【０００５】
本発明は、上記に鑑みてなされたものであって、構造化文書を検索する場合、データベースを走査する回数を低減させて検索速度を向上可能な構造化文書検索装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上述した課題を解決し、目的を達成するために、本発明は、構造化文書検索装置であって、データベースに記憶され少なくとも１つの要素が階層付けられている構造化文書を検索するための検索条件を示す検索式を受け付ける検索要求受付手段と、前記検索条件に該当する構造化文書を検索するための検索処理を実行する際に、処理単位となる少なくとも１つの操作を含む当該操作の実行順序を示す検索プランを生成する生成手段と、前記検索プランに含まれる各前記操作のうち、前記要素の全部又は一部を参照して実行する第１操作が連続して実行されるよう実行順序を最適化する第１最適化手段と、実行順序が最適化された前記第１操作が文書単位で一括で実行されるよう当該第１操作を複合して複合操作を生成することにより、前記検索プランを最適化する第２最適化手段と、最適化された前記実行順序に従い、前記データベースを走査して、少なくとも１つの前記要素の全部又は一部を取得し、最適化された前記検索プランに含まれる前記複合操作を文書単位で一括して実行して実行結果を得る検索実行手段と、前記実行結果を、前記検索式に応じた構造化文書形式に成形して出力する出力手段とを備えることを特徴とする。
【０００７】
また、本発明は、検索要求受付手段と、生成手段と、最適化手段と、検索実行手段と、出力手段とを備える構造化文書検索装置で実行される構造化文書検索方法であって、前記検索要求受付手段が、データベースに記憶され少なくとも１つの要素が階層付けられている構造化文書を検索するための検索条件を示す検索式を受け付ける検索要求受付ステップと、前記生成手段が、受け付けられた検索式を解析して、前記検索条件に該当する構造化文書を検索するための検索処理を実行する際の処理単位となる少なくとも１つの操作を含み当該操作の実行順序を示す検索プランを生成する生成ステップと、前記第１最適化手段が、前記検索プランに含まれる各前記操作のうち、前記要素の全部又は一部を参照して実行する第１操作が連続して実行されるよう実行順序を最適化する第１最適化ステップと、  前記第２最適化手段が、実行順序が最適化された前記第１操作が文書単位で一括で実行されるよう当該第１操作を複合して複合操作を生成することにより、前記検索プランを最適化する第２最適化ステップと、前記検索実行手段が、最適化された前記実行順序に従い、前記データベースを走査して、少なくとも１つの前記要素の全部又は一部を取得し、最適化された前記検索プランに含まれる前記複合操作を文書単位で一括して実行して実行結果を得る検索実行ステップと、前記実行結果を、前記検索式に応じた構造化文書形式に成形して出力する出力ステップを含むことを特徴とする。
【０００８】
また、本発明は、プログラムであって、上記の構造化文書検索方法をコンピュータに実行させることを特徴とする。
【発明の効果】
【０００９】
本発明によれば、構造化文書を検索する場合、データベースを走査する回数を低減させ、検索速度を向上可能にする。
【発明を実施するための最良の形態】
【００１０】
以下に添付図面を参照して、この発明にかかる構造化文書検索装置、方法及びプログラムの最良な実施の形態を詳細に説明する。
【００１１】
[第１の実施の形態]
（１）構成
まず、本実施の形態にかかる構造化文書検索装置のハードウェア構成について説明する。構造化文書検索装置は、装置全体の制御を行うＣＰＵ（Central Processing Unit）等の制御装置と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）等の記憶装置と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶装置と、外部のコンピュータと通信を行う通信制御装置と、これらを接続するバスとを備えており、通常のコンピュータを利用したハードウェア構成となっている。また、構造化文書検索装置には、情報を表示するディスプレイ装置等の表示装置と、ユーザが各種処理要求を入力するためのキーボードやマウス等の入力装置とが有線又は無線により接続される。
【００１２】
このようなハードウェア構成において、構造化文書検索装置が、記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される各種機能について図１を用いて説明する。構造化文書検索装置１００は、検索要求受付部１００１と、検索プラナ部１００２と、文書単位検索最適化部１００８と、検索実行順序制御部１００３と、構造化文書検索実行部１００４と、構造化文書データ管理部１００９とを有する。検索要求受付部１００１と、検索プラナ部１００２と、文書単位検索最適化部１００８と、検索実行順序制御部１００３と、構造化文書検索実行部１００４と、構造化文書データ管理部１００９との実体は各々、ＣＰＵが各種プログラムの際に例えばＲＡＭ等の記憶装置上に生成されるものである。尚、構造化文書データ管理部１００９には、構造化文書データ管理部１００９には構造化文書を記憶するデータベース（図示せず）が格納される。また、構造化文書検索装置１００は、図示しない後述の操作割当テーブルを有する。これらのデータベースや操作割当テーブルは、例えば、記憶装置や外部記憶装置に記憶される。
【００１３】
このデータベースには、例えば、オークションの会員に関する情報がＸＭＬ形式の構造化文書（ＸＭＬ文書）として記憶されている。以降、このデータベースをpeopleデータベースとする。図２は、peopleデータベースのスキーマの構造を例示する図である。同図によれば、peopleデータベースに記憶されるＸＭＬ文書は、要素として、オークションの会員の名前、住所、メールアドレス、電話番号、性別、年齢、趣味、入札回数及び落札回数を含んでいる。尚、各要素をＸＭＬノードという。各ＸＭＬノードの値は各々要素値という。また、このＸＭＬノードは、２つ以上の要素を含むこともある。
【００１４】
検索要求受付部１００１は、ＸＭＬ文書の検索を要求する検索要求として、ＸＭＬ文書の検索に関する検索条件を示す検索式を、例えば入力装置を介して受け付け、検索プラナ部１００２に入力する。図３は、図２に示したＸＭＬ文書に対する検索式を例示する図である。この検索式は、「peopleデータベースにおいて、入札回数が“10”回以上で且つ落札回数が“5”回以上の会員について、年代と住所とを出力する」ことを要求している。
【００１５】
検索プラナ部１００２は、入力された検索式を解析して、検索条件を表す検索条件制約グラフを生成する。検索条件制約グラフは検索で求めるべき各変数間の制約条件を表すグラフとして表現されている。検索条件制約グラフについては後述の動作欄で詳述する。そして、検索プラナ部１００２は、このような検索条件制約グラフに基づいて、ＸＭＬ文書を検索する検索処理を行うための各操作の実行順序を示す検索プランを生成する。次に、検索プラナ部１００２は、操作割当テーブルを参照して、検索プランに含まれる各操作の種別を判別する。
【００１６】
図４は、操作割当テーブルのデータ構成を例示する図である。同図に示されるように、操作割当テーブルは、操作子と、種別とを対応付けて記憶するものであり、記憶装置や外部記憶装置に記憶される。操作子とは、各操作に含まれるものであり、対象のＸＭＬノードを示す後述の変数に対する処理内容を示すものである。操作子には、例えば、“compare”や“traverse”や”function”などがある。種別は、操作子を含む操作の種別を示すものである。種別には、操作が文書単位で一括して実行可能であることを示す文書単位種別がある。本実施の形態においては、“compare”や“traverse”や”function”などの各操作子に対して、文書単位種別が割り当てられている。これらの各操作子を含む操作を文書単位種別として文書単位で一括して実行することにより、高速な検索を行うことが可能になる。検索プラナ部１００２は、このような操作割当テーブルを参照して、検索プランに含まれる各操作に含まれる操作子に対応する種別を判別し、判別した種別を各操作に割り当ててこれを含む検索プランを文書単位検索最適化部１００８に入力する。
【００１７】
文書単位検索最適化部１００８は、種別が割り当てられた各操作を含む当該操作の実行順序を示す検索プランを受け取り、各操作の種別に基づいて、文書単位で一括して実行可能な操作が連続して実行されるように実行順序を最適化し、当該各操作を複合して複合操作を生成することにより、検索プランを最適化し、最適化した検索プランを検索実行順序制御部１００３に入力する。
【００１８】
検索実行順序制御部１００３は、最適化された検索プランを受け取り、当該検索プランに含まれる各操作を構造化文書検索実行部１００４に順次入力することにより、各操作の実行を構造化文書検索実行部１００４に順次要求する。
【００１９】
構造化文書検索実行部１００４は、実行制御部１００５と、文書単位検索実行部１００７とを有する。実行制御部１００５は、検索実行順序制御部１００３から入力された操作の種別を判別し、種別に応じて、当該操作の実行をＤＢ単位検索実行部１００６又は文書単位検索実行部１００７に要求する。具体的には、実行制御部１００５は、入力された操作が、文書単位種別の操作が複合された複合操作である場合にはこれを文書単位検索実行部１００７に入力してその実行を要求する。文書単位検索実行部１００７は、入力された複合操作に含まれる各操作を文書単位で順に実行して、その実行過程で求められる中間結果を各々出力する。中間結果とは、例えば後述する変数の値である。この結果、文書単位種別の操作については、文書単位で一括して実行されることになる。
【００２０】
構造化文書データ管理部１００９は、上述したデータベースへのアクセスを制御し、検索プランの実行後に得られた実行結果をＸＭＬ形式のＸＭＬ文書に成形してこれを検索結果として出力する。例えば、構造化文書データ管理部１００９は、当該検索結果を表示装置に表示させたり外部記憶装置や記憶装置に記憶させたりして、当該検索結果を出力する。
【００２１】
（２）動作
次に、構造化文書検索装置１００の行う処理の手順について図５を用いて説明する。構造化文書検索装置１００の検索要求受付部１００１は、ＸＭＬ文書の検索を要求する検索要求として、ＸＭＬ文書の検索に関する検索条件を示す検索式を受け付け、検索プラナ部１００２に入力する（ステップＳ１）。ここでは例えば図３に示すような検索式が入力される。
【００２２】
検索プラナ部１００２は、入力された検索式を解析して、検索条件を表す検索条件制約グラフを生成する。具体的には、検索プラナ部１００２は、検索の結果として求めるべき変数をグラフのノードとして示し、それら変数に関する検索条件や変数間で満たすべき制約条件を、各変数を表すノード間のアークとして示すように検索条件制約グラフを生成する。各変数には、例えば、該当のＸＭＬノードの格納位置や該当のＸＭＬノードの値（要素値）などが割り当てられる。ここでは、検索プラナ部１００２は、peopleデータベースに記憶されたＸＭＬ文書のルートノードから順次、ＸＭＬ文書の構造を辿り、検索処理の対象となるＸＭＬノードを取得し、取得したノードの値を用いて検索条件との比較を行うことで検索プランを生成する。図６は、図３の検索式が入力された場合に得られる検索条件制約グラフを例示する図である。図３の検索式の場合、検索結果として求める変数は、変数$1から変数$11まで存在する。変数$1にはpeopleデータベースのルートノードが対応している。また、変数＄1と変数$2の間には、ＸＭＬノード間の階層関係に関する(/people, $1, $2)の制約関係がある。これは、変数$1が表すＸＭＬノードの下層の“people”タグにより特定されるＸＭＬノードが変数$2に対応する、という制約条件を示している。同様に、変数$2と変数$3、変数$3と変数$4、変数$3と変数$6、変数$3と変数$7、変数$3と変数$9、変数$3と変数$10のそれぞれの変数の間には、ＸＭＬノード間の階層関係に関する制約関係がある。また、変数$4と変数$5の間には、ＸＭＬノードの値に関する制約条件として(>, $4, 10, $5) の関係がある。これは、変数$4が示すＸＭＬノードのうち、その値が“10”以上であるＸＭＬノードが変数$5に対応する、という制約条件を示している。同様の制約として、変数$10と変数$11の間には(>, $10, 5, $11)の制約関係が有る。また、変数$7と変数$8の間には、(op:numeric-integer-divide, $7, 10, $8)の制約関係がある。これは、変数$7が示すＸＭＬノードと変数$8の値の間には、変数$7が表すＸＭＬノードの値を“10”で割って整数に丸めた値となる制約関係があることを示している。
【００２３】
そして、検索プラナ部１００２は、このような検索条件制約グラフに基づいて、ＸＭＬ文書を検索する検索処理を行うための各操作を含む当該操作の実行順序を示す検索プランを生成する（ステップＳ２）。図７は、図６に示した検索条件制約グラフに基づいて生成される検索プランを例示する図である。同図に示す検索プランは、操作６,５,２,１，４，３，７〜１０の順に実行することにより検索処理を進めることを示している。具体的には、検索プラナ部１００２は、まず、操作６では、ルートノードの格納位置を変数$1とし、このルートノードの子ノードとなる“/people”タグにより特定されるＸＭＬノードの格納位置を変数$2の値とする。操作５では、求めた変数$2に関し、“/people”タグにより特定されるＸＭＬノードの子ノードとなる“/people/person” タグにより特定されるＸＭＬノードの格納位置を、読み取った文書情報から求め、これを変数$3の値とする。操作２では、求めた変数$3に関し、“/people/person”タグにより特定されるＸＭＬノードの子ノードとなる“/people/person/wincount”タグにより特定されるＸＭＬノードの格納位置を、読み取った文書情報から求め、これを変数$10の値とする。操作１では、求めた変数$10に関し、“/people/person/wincount”タグにより特定されるＸＭＬノードの値について、比較条件を満たした変数$10の値を変数$11の値とする。ここでの比較条件とは、変数$10が“5”以上であることである。操作４では、求めた変数$3に関し、“/people/person”タグにより特定されるＸＭＬノードの子ノードとなる“/people/person/bidcount”タグにより特定されるＸＭＬノードの格納位置を変数$4の値とする。操作３では、求めた変数$4に関し、“/people/person/bidcount”タグにより特定されるＸＭＬノードの値について、比較条件を満たした変数$4の値を変数$5の値とする。ここでの比較条件とは、変数$4が“10”以上であることである。操作７では、求めた変数$3に関し、“/people/person”タグにより特定されるＸＭＬノードの子ノードとなる“/people/person@/id” タグにより特定されるＸＭＬノードの格納位置を変数$6の値とする。操作８では、求めた変数$3に関し、“/people/person”タグにより特定されるＸＭＬノードの子ノードとなる“/people/person/address”タグにより特定されるＸＭＬノードの格納位置を変数$9の値とする。さらに、操作９では、求めた変数$3に関し、“/people/person”タグにより特定されるＸＭＬノードの子ノードとなる“/people/person/age”タグにより特定されるＸＭＬノードの格納位置を変数$7の値とする。操作１０では、求めた変数$7に関し“/people/person/age”タグにより特定されるＸＭＬノードの値を用いて“op:numeric-integer-divide”の演算を行い、得られた値を変数$8の値とする。
【００２４】
次に、検索プラナ部１００２は、図４に示したような操作割当テーブルを参照して、検索プランに含まれる各操作の種別を判別する（ステップＳ３）。図８は、上述の各操作１〜１０の種別を示す図である。検索プラナ部１００２は、このように判別した種別を各操作に割り当ててこれを含む検索プランを文書単位検索最適化部１００８に入力する。この結果、図９に示すような検索プランが入力される。同図に示す検索プランは、上述した操作６,５,２,１，４，３，７〜１０の順に実行することにより検索処理を進めることを示している。
【００２５】
次に、文書単位検索最適化部１００８は、種別が割り当てられた各操作を含む検索プランを受け取ると、文書単位種別が割り当てられた操作が連続して実行されるように実行順序を最適化する。尚、ここでの文書単位種別が割り当てられた操作の実行順序は既に連続して実行されるようになっているので、その実行順序がそのまま最適化されたものとなる。結果として図８に例示された検索プランと同一の検索プランが得られる。最後に、文書単位検索最適化部１００８は、検索プランにおいて連続配置された文書単位種別の操作を複合した複合操作を生成することにより、検索プランを最適化する（ステップＳ４）。このとき、図９に示すように、操作６,５,２,１，４，３，７〜１０が複合されて複合操作として生成されることとなる。
【００２６】
図１０は、図８に示される検索プランが最適化されたものを例示する図である。同図に示される検索プランは、操作１０´に実行することにより検索処理を進めることを示している。操作１０´では、peopleデータベースに記憶されたＸＭＬ文書に対し、上述した操作６,５,２,１，４，３，７〜１０の順に文書単位で一括して処理を行う。
【００２７】
そして、文書単位検索最適化部１００８は、最適化された検索プランを検索実行順序制御部１００３に入力する。ステップＳ５では、検索実行順序制御部１００３は、最適化された検索プランを受け取ると、当該検索プランに含まれる各操作を構造化文書検索実行部１００４に順次入力することにより、各操作の実行を構造化文書検索実行部１００４に順次要求する。構造化文書検索実行部１００４の実行制御部１００５は、検索実行順序制御部１００３から操作が入力されると、当該操作の種別を判別し、種別に応じて、当該操作の実行をＤＢ単位検索実行部１００６又は文書単位検索実行部１００７に要求する。ここでは、具体的には、図１０に示される検索プランに含まれる操作１０´については、文書単位種別の操作であるから、実行制御部１００５はこれを文書単位検索実行部１００７に入力してその実行を要求する。文書単位検索実行部１００７は、まず、peopleデータベースに格納されているＸＭＬ文書のルートノードを１つ取り出し、ＸＭＬ文書全体の大元のルートノードのpeopleデータベースにおける格納位置を基に、peopleデータベースを走査して、検索処理の対象となるＸＭＬ文書に関し、ＸＭＬノード間の構造情報を含むＸＭＬ文書の情報（文書情報）を全体一括で読み取る。次に、文書単位検索実行部１００７は、読み取った文書情報に関して、操作１０´に含まれる上述の操作６,５,２,１，４，３，７〜１０をその順に連続して実行する。
【００２８】
具体的には以下の手順となる。まず、操作６(traverse,/people,$1,$2)の処理として、文書単位検索実行部１００７は、取り出したルートノードの格納位置を変数$1とし、このルートノードの子ノードとなる“/people”タグにより特定されるＸＭＬノードの格納位置を、読み取った文書情報から求め、これを変数$2の値とする。次に、操作５(traverse,/person,$2,$3)の処理として、文書単位検索実行部１００７は、求めた変数$2に関し、“/people”タグにより特定されるＸＭＬノードの子ノードとなる“/people/person” タグにより特定されるＸＭＬノードの格納位置を、読み取った文書情報から求め、これを変数$3の値とする。次に、操作２(traverse,/wincount,$3,$10)の処理として、文書単位検索実行部１００７は、求めた変数$3に関し、“/people/person”タグにより特定されるＸＭＬノードの子ノードとなる“/people/person/wincount”タグにより特定されるＸＭＬノードの格納位置を、読み取った文書情報から求め、これを変数$10の値とする。次に、操作１(compare, >, $10,5,$11)の処理として、文書単位検索実行部１００７は、求めた変数$10に関し、“/people/person/wincount”タグにより特定されるＸＭＬノードの値を、読み取った文書情報から求め、比較条件を満たした変数$10の値を変数$11の値とする。ここでの比較条件とは、変数$10が“5”以上であることである。次に、操作４(traverse,/bidcount,$3,$4)の処理として、文書単位検索実行部１００７は、求めた変数$3に関し、“/people/person”タグにより特定されるＸＭＬノードの子ノードとなる“/people/person/bidcount”タグにより特定されるＸＭＬノードの格納位置を、読み取った文書情報から求め、これを変数$4の値とする。
【００２９】
次に、操作３(compare, >, $4,10,$5)の処理として、文書単位検索実行部１００７は、求めた変数$4に関し、“/people/person/bidcount”タグにより特定されるＸＭＬノードの値を、読み取った文書情報から求め、比較条件を満たした変数$4の値を変数$5の値とする。ここでの比較条件とは、変数$4が“10”以上であることである。次に、操作７(traverse,@id,$3,$6)の処理として、文書単位検索実行部１００７は、求めた変数$3に関し、“/people/person”タグにより特定されるＸＭＬノードの子ノードとなる“/people/person@/id” タグにより特定されるＸＭＬノードの格納位置を、読み取った文書情報から求め、これを変数$6の値とする。次に、操作８(traverse,/address,$3,$9)の処理として、文書単位検索実行部１００７は、求めた変数$3に関し、“/people/person”タグにより特定されるＸＭＬノードの子ノードとなる“/people/person/address”タグにより特定されるＸＭＬノードの格納位置を、読み取った文書情報から求め、これを変数$9の値とする。次に、操作９(traverse,/age,$3,$7)の処理として、文書単位検索実行部１００７は、求めた変数$3に関し、“/people/person”タグにより特定されるＸＭＬノードの子ノードとなる“/people/person/age”タグにより特定されるＸＭＬノードの格納位置を、読み取った文書情報から求め、これを変数$7の値とする。次に、操作１０(function, op:numeric-integer-divide,$7,10,$8)の処理として、文書単位検索実行部１００７は、求めた変数$7に関し“/people/person/age”タグにより特定されるＸＭＬノードの値を、読み取った文書情報から求め、求めた値を用いて“op:numeric-integer-divide”の演算を行い、得られた値を変数$8の値とする。
【００３０】
以上のようにして、ＸＭＬ文書のルートノードを取得し、文書情報を読み出しながら、上記の一連の操作を実行して検索処理を行う。一連の操作の実行の際にデータベースの走査を１回行うだけで良いため、データベースの走査する回数を低減させることができ、検索速度を向上させることができる。
【００３１】
[第２の実施の形態]
次に、構造化文書検索装置の第２の実施の形態について説明する。なお、上述の第１の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００３２】
（１）構成
本実施の形態においては、peopleデータベースにはＸＭＬ文書に含まれる各要素値に関するインデクスが予め設定されているものとする。インデクスは検索の際の検索キーとなるキー値と、そのキー値が出現する、peopleデータベース内の格納位置を示すＤＢ内格納位置情報との対応関係を示す情報である。特定の値の出現する格納位置を求める際に、peopleデータベースを走査することなくインデクスを走査することで、当該格納位置を求めることができる。このインデクスは部分的な情報であり、データベース全体と比較するとデータサイズが小さい。そのため、データベース全体を走査する場合と比較すると、インデクスを走査する場合は、走査にかかる時間が少なくて済むので、インデクスを用いると高速に検索ができる。また、構造化文書に関するインデクス方式にはいくつかのバリエーションが考えられるが、ここでは要素値をキー値として要素値毎に個別のインデクスを作成して使用するものとする。また、目的に応じてキー値の格納構造もバリエーションがあるが、説明の都合上単純化のために直列に並んだ構造を用いるものとする。図１１は、本実施の形態で取り扱うインデクスを例示する図である。同図では、ＸＭＬ文書に含まれるＸＭＬノードのうち、“/people/person/wincount”タグで特定されるＸＭＬノードの値(要素値)に関するインデクスが例示されている。検索の際には、検索条件としてキー値が指定され、構造化文書検索装置１００は、指定されたキー値を用いてインデクスを走査する。そして、構造化文書検索装置１００は、見つかったキー値に対応するＤＢ内格納位置格納先情報を参照して、当該キー値を要素値として示すＸＭＬノードのpeopleデータベース内における実際の格納位置を取得する。即ち、このＤＢ内格納位置情報により、当該キー値を要素値として示す、ＸＭＬ文書中のＸＭＬノードを特定することができる。
【００３３】
図１２は、本実施の形態にかかる構造化文書検索装置１００の機能的構成を例示する図である。本実施の形態にかかる構造化文書検索装置１００の構成が、上述の第１の実施の形態における構造化文書検索装置１００の構成と異なる点は以下の通りである。構造化文書検索実行部１００４は、上述した実行制御部１００５と、文書単位検索実行部１００７とに加え、ＤＢ単位検索実行部１００６とを有する。このＤＢ単位検索実行部１００６の機能については後述する。また、本実施の形態にかかる構造化文書検索装置１００が有する操作割当テーブルは、上述のものとは異なる。
【００３４】
図１３は、本実施の形態にかかる構造化文書検索装置１００の有する操作割当テーブルのデータ構成を例示する図である。同図に例示されるように、本実施の形態においては、“compare”という操作子に対する操作種別が、ＤＢ単位種別となる。ＤＢ単位種別とは、操作がデータベースの走査を必要とすることを示すものである。本実施の形態においては、データベースにインデクスが設定されているため、操作子“compare”を含む操作では、インデクスによる絞り込みを行うことができる。このため、このような操作を、ＤＢ単位種別として、インデクスを用いてデータベースを走査して実行する一方、“traverse”や”function”などの操作子を含む操作を文書単位種別として文書単位で一括して実行することにより、高速な検索を行うことが可能になる。検索プラナ部１００２は、このような操作割当テーブルを参照して、検索プランに含まれる各操作に含まれる操作子に対応する種別を判別し、判別した種別を各操作に割り当ててこれを含む検索プランを文書単位検索最適化部１００８に入力する。
【００３５】
検索プラナ部１００２は、上述の第１の実施の形態と同様にして、入力された検索式を解析して、検索条件を表す検索条件制約グラフを生成するが、ここでは、インデクスを用いたキー値による効果的な絞込みを行うことができる。図１４は、図３に例示した検索式を基に、本実施の形態にかかる検索プラナ部１００２が生成する検索プランを例示する図である。同図に示す検索プランは、上述した操作１〜１０の順に実行することにより検索処理を進めることを示している。
【００３６】
文書単位検索最適化部１００８は、種別が割り当てられた各操作を含む検索プランを受け取り、各操作の種別に基づいて、文書単位で一括して実行可能な操作と、それ以外の操作とを区別して、文書単位で一括して実行可能な操作が連続して実行されるよう各操作の実行順序を最適化し、文書単位で一括して実行可能な操作を複合して複合操作を生成することにより、検索プランを最適化する。そして、文書単位検索最適化部１００８は、最適化した検索プランを検索実行順序制御部１００３に入力する。構造化文書検索実行部１００４の有する実行制御部１００５は、検索実行順序制御部１００３から入力された操作の種別を判別し、種別に応じて、当該操作の実行をＤＢ単位検索実行部１００６又は文書単位検索実行部１００７に要求する。ここでは、実行制御部１００５は、入力された操作がＤＢ単位種別の操作である場合にはこれをＤＢ単位検索実行部１００６に入力してその実行を要求する。ＤＢ単位検索実行部１００６は、入力された操作を実行して、構造化文書データ管理部１００９に格納されたデータベースを走査して、その実行過程で求められる中間結果を各々出力する。
【００３７】
（２）動作
次に、本実施の形態にかかる構造化文書検索装置１００の行う処理について説明する。処理の手順自体は、図５に示される手順と同様である。上述の第１の実施の形態と異なる点は以下の通りである。ステップＳ２では、検索プラナ部１００２は、例えば、図３に示される検索式から、図１４に示される検索プランを生成する。そして、ステップＳ３では、検索プラナ部１００２は、図１３に示される操作割当テーブルを参照して、検索プランに含まれる各操作の種別を判別する。このとき、各操作に対して判別される種別は、図１５に示されるように、“compare”を含む操作については、ＤＢ単位種別となり、“traverse”や”function”を含む操作をについては文書単位種別となる。検索プラナ部１００２は、このように判別した種別を各操作に割り当ててこれを含む検索プランを文書単位検索最適化部１００８に入力する。
【００３８】
次に、ステップＳ４では、文書単位検索最適化部１００８は、種別が割り当てられた各操作を含む検索プランを受け取ると、文書単位種別が割り当てられた操作が連続して実行されるよう各操作の実行順序を最適化する。具体的には、まず、文書単位検索最適化部１００８は、各操作における変数間の導出依存関係を求める。次に、文書単位検索最適化部１００８は、導出依存関係の制約内で、文書単位種別の操作が連続配置されるように、各操作の実行順序を変更する。このようにして、文書単位検索最適化部１００８は、各操作の実行順序を最適化する。これにより図１６に示すような検索プランが生成される。ここでは、操作１，２，５，６，７，８，９，１０，４，３の順に実行順序が変更される。最後に、文書単位検索最適化部１００８は、検索プランにおいて連続配置された文書単位種別の操作を複合した複合操作を生成する。これにより、図１７に示すように、操作２，５，６，７，８，９，１０，４が複合されて複合操作として生成されることとなる。操作１，３については、ＤＢ単位種別であるため、各々独立した操作となる。このようにして、文書単位検索最適化部１００８は、検索プランを最適化する。
【００３９】
図１８は、図１４に示される検索プランが最適化されたものを例示する図である。同図に示される検索プランは、操作１´〜３´の順に実行することにより検索処理を進めることを示している。まず、操作１´では、peopleデータベースに記憶されたＸＭＬ文書の“/people/person/wincount”タグにより特定されるＸＭＬノードのうち、そのＸＭＬノードの値（要素値）が“5”以上のものを変数$11を求め、求めた変数$11に対応する変数$10を求める。次に、操作２´では、文書単位の処理として、上述した操作２，５，６，７，８，９，１０，４の順に一括して処理を行う。操作３´では、上述した操作３の処理を行う。これらの各変数の値が各操作の実行の過程で求められる中間結果となる。
【００４０】
文書単位検索最適化部１００８は、このように最適化した検索プランを検索実行順序制御部１００３に入力する。検索実行順序制御部１００３は、最適化された検索プランを受け取ると、当該検索プランに含まれる各操作を構造化文書検索実行部１００４に順次入力することにより、各操作の実行を構造化文書検索実行部１００４に順次要求する。構造化文書検索実行部１００４の実行制御部１００５は、検索実行順序制御部１００３から操作が入力されると、当該操作の種別を判別し、種別に応じて、当該操作の実行をＤＢ単位検索実行部１００６又は文書単位検索実行部１００７に要求する（ステップＳ５）。具体的には、実行制御部１００５は、入力された操作がＤＢ単位種別の操作である場合にはこれをＤＢ単位検索実行部１００６に入力してその実行を要求する。また、実行制御部１００５は、入力された操作が、文書単位種別の操作が複合された複合操作である場合にはこれを文書単位検索実行部１００７に入力してその実行を要求する。また、実行制御部１００５は、各操作の実行を要求する際には、当該操作の実行に必要な変数の値（中間結果）が、文書単位検索実行部１００７又はＤＢ単位検索実行部１００６のいずれに保持されているかを、当該中間結果の取得先として示す格納場所識別情報も、当該操作の実行を要求する対象のＤＢ単位検索実行部１００６又は文書単位検索実行部１００７に送る。
【００４１】
図１８に示される検索プランに含まれる一番目の操作１´については、ＤＢ単位種別の操作であるから、実行制御部１００５はこれをＤＢ単位検索実行部１００６に入力してその実行を要求する。ＤＢ単位検索実行部１００６は、操作１´（上述の操作１と同様である）を実行する。このとき、ＤＢ単位検索実行部１００６は、まず、“/people/person/wincount”タグにより特定されるＸＭＬノードに関するインデクスを特定する。そして、ＤＢ単位検索実行部１００６は、特定したインデクスのキー値の部分を走査して、検索条件として指定されている“5”以上のキー値について、“5”から順に当該キー値に対応するＤＢ内格納先位置情報を取得する。即ち、ＤＢ単位検索実行部１００６は、“/people/person/wincount”タグにより特定され“5”以上の値を要素値（キー値）として示すＸＭＬノードのpeopleデータベースにおけるＤＢ内格納位置情報を順次取得する。この走査により得られたＤＢ内格納位置情報の集合が変数$11の値として求められ、記録される。この操作１´は、“/people/person/wincount”タグにより特定されるＸＭＬノードに関するインデクスに対する走査のみで行われ、peopleデータベース自体の走査は行う必要が無い。次に、変数$11に対応する変数$10の値を求めるが、変数$11と変数$10はともに“/people/person/wincount”タグに関するものなので、変数$11の値が変数$10の値として記録される。そして、ＤＢ単位検索実行部１００６は、操作１´の実行が終了すると、その旨を実行制御部１００５に通知する。
【００４２】
次に、実行制御部１００５は、検索プランに含まれる次に実行すべき操作として操作２´が入力されると、当該操作２´は文書単位種別の操作が複合されたものであるため、これを文書単位検索実行部１００７に入力してその実行を要求する。文書単位検索実行部１００７は、操作１´で得られた変数$10に関する“/people/person/wincount”タグにより特定されるＸＭＬノードの親ノードとなる“/people/person”タグで特定されるＸＭＬノードを求め、操作２´の複合操作を文書単位で実行することにより、最終的に変数$4の値を求める。この処理は次の手順で行われる。文書単位検索実行部１００７は、変数$10で求めた値を１つ取り出す。この値は上述したように、操作１´における検索条件に該当する要素値を示すＸＭＬノードのＤＢ内格納位置情報であるから、文書単位検索実行部１００７は、peopleデータベースを走査してこのＤＢ内格納位置情報によって示される格納位置を探し、その格納位置から該当するＸＭＬノードを読み出す。次に、文書単位検索実行部１００７は、読み出したＸＭＬノードを基にその親ノードを順次参照して、ＸＭＬ文書全体の大元のルートノードのpeopleデータベースにおける格納位置を求め、peopleデータベースを走査して、検索処理の対象となるＸＭＬ文書に関し、ＸＭＬノード間の構造情報を含むＸＭＬ文書の情報（文書情報）を全体一括で読み取る。ＸＭＬノード間の構造情報とは、例えば、各ＸＭＬノードの階層関係や各ＸＭＬノードの値の格納場所などの情報である。次に、文書単位検索実行部１００７は、読み取った文書情報に関して、操作２´に含まれる上述の操作２，５，６，７，８，９，１０，４をその順に連続して実行する。
【００４３】
具体的には、文書単位検索実行部１００７は、読み取った文書情報から、“/people/person/wincount”タグで特定されるＸＭＬノードのＤＢ内格納位置情報を取得する。次に、文書単位検索実行部１００７は、操作２(traverse,/wincount,$3,$10)の処理として、取得したＤＢ内格納位置情報に関し、“/people/person/wincount”タグで特定されるＸＭＬノードの親ノードである“/people/person” タグで特定されるＸＭＬノードのＤＢ内格納位置情報を、読み取った文書情報から求め、これを変数$3の値とする。次に、操作５(traverse,/person,$2,$3)の処理として、文書単位検索実行部１００７は、求めた変数$3に関し、“/people/person”タグで特定されるＸＭＬノードの親ノードである“/people” タグで特定されるＸＭＬノードのＤＢ内格納位置情報を、読み取った文書情報から求め、これを変数$2の値とする。次に、操作６(traverse,/people,$1,$2)の処理として、文書単位検索実行部１００７は、求めた変数$2に関し、“/people”タグで特定されるＸＭＬノードの親ノードであるルートノードのＤＢ内格納位置情報を、読み取った文書情報から求め、これを変数$1の値とする。次に、操作７(traverse,@id,$3,$6)の処理として、文書単位検索実行部１００７は、求めた変数$3に関し、“/people/person”ノードの子ノードである“/people/person/@id” タグで特定されるＸＭＬノードのＤＢ内格納位置情報を、読み取った文書情報から求め、これを変数$6の値とする。
【００４４】
次に、操作８(traverse,/address,$3,$9)の処理として、文書単位検索実行部１００７は、求めた変数$3に関し、“/people/person”タグで特定されるＸＭＬノードの子ノードである“/people/person/address”タグで特定されるＸＭＬノードのＤＢ内格納位置情報を、読み取った文書情報から求め、これを変数$9の値とする。次に、操作９(traverse,/age,$3,$7)の処理として、文書単位検索実行部１００７は、求めた変数$3に関し、“/people/person”タグで特定されるＸＭＬノードの子ノードである“/people/person/age”タグで特定されるＸＭＬノードのＤＢ内格納位置情報を、読み取った文書情報から求め、これを変数$7の値とする。次に、操作１０(function, op:numeric-integer-divide,$7,10,$8)の処理として、文書単位検索実行部１００７は、求めた変数$7に関し、“/people/person/age”タグで特定されるＸＭＬノードの値を、読み取った文書情報から求め、求めた値を用いて“op:numeric-integer-divide”の演算を行い、得られた値を変数$8の値とする。次に、操作４(traverse,/bidcount,$3,$4)の処理として、文書単位検索実行部１００７は、求めた変数$3に関し、“/people/person”タグで特定されるＸＭＬノードの子ノードである“/people/person/bidcount”タグで特定されるＸＭＬノードのＤＢ内格納位置情報を、読み取った文書情報から求め、これを変数$4の値とする。
【００４５】
そして、読み出した１つの文書情報に関して操作２´の実行が終了すると、文書単位検索実行部１００７は、操作１´で得られた変数$10の新たな値を１つ読み出し、これで特定される新たなＸＭＬノードを構造化文書データ管理部１００９から１つ読み出し、上述と同様にして、読み出したＸＭＬノードを基に、該当するＸＭＬ文書に関し、ＸＭＬノード間の構造情報を含むＸＭＬ文書の情報（文書情報）を全体一括で読み取る。そして、上述と同様にして、操作２´に含まれる操作２，５，６，７，８，９，１０，４をその順に連続して実行して、変数$4の値を求める。このようにして、文書単位検索実行部１００７は、操作１´で得られた変数$10の値によって特定される全てのＸＭＬノードに関して、文書単位で操作２´の実行を繰り返す。
【００４６】
以上のように、操作１´で得られた変数$10の値を順次取り出し、peopleデータベースを走査して、変数$10によって特定されるＸＭＬノードが含まれるＸＭＬ文書の情報の全体を読み取った後、複合操作に含まれる一連の操作を連続して実行する。即ち、ＸＭＬ文書の要素の全部又は一部の値毎に一連の操作を連続して実行することにより、一連の操作の実行に要する走査回数を１回に削減することができる。
【００４７】
そして、文書単位検索実行部１００７は、該当の全てのＸＭＬノードに関して、操作２´の実行が終了すると、その旨を実行制御部１００５に通知する。
【００４８】
次いで、実行制御部１００５は、検索プランに含まれる次に実行すべき操作として操作３´が入力されると、当該操作はＤＢ単位種別であるから、これをＤＢ単位検索実行部１００６に入力してその実行を要求する。ＤＢ単位検索実行部１００６は、操作３´（上述の操作３と同様である）を実行するが、“/people/person/bidcount” タグで特定されるＸＭＬノードに関するインデクスを参照して、その値が“10”以上のキー値に対応するＤＢ内格納位置情報を求め、これを変数$5の値として、変数$5の値を変数$4の値とする。そして、ＤＢ単位検索実行部１００６は、最終的に、求められた変数$4と事前の操作２´で求められた変数$4との論理積を求め、これを新たに変数$4の値とする。そして、ＤＢ単位検索実行部１００６は、操作３´の実行が終了すると、その旨を実行制御部１００５に通知する。
【００４９】
ここでは、検索プランには操作３´の次に実行すべき操作はないため、実行制御部１００５は、検索処理の終了を構造化文書データ管理部１００９に通知する。次いで、構造化文書データ管理部１００９は、検索プランの実行の結果得られた実行結果である変数$8の値をＸＭＬ形式のデータに成形してこれを検索結果として出力する（ステップＳ６）。
【００５０】
以上のように、文書単位で一括して実行可能な操作を、各変数の導出依存関係の制約内で連続配置することにより複合操作を生成して検索プランを最適化する。そして、検索プランの実行の際には、複合操作を文書単位で一括して実行することにより、時間を要するデータベース全体の走査を繰り返すことなく、一連の文書単位での検索条件の充足や変数の値の導出を一度のデータベース走査で行うことができる。
【００５１】
一方、従来の構造化文書検索装置は、文書単位での処理が考慮されていないため、図１４に示される検索プランを実行し、当該検索プランに含まれる操作１〜１０をその順に実行していた。このとき、当該構造化文書検索装置は、例えば、操作１では、本実施の形態の構造化文書検索装置１００と同様にして変数$10を求める。そして、操作２では、従来の構造化文書検索装置は、変数$10に関し、“/people/person/wincount”タグにより特定されるＸＭＬノードの親ノードとなる“/people/person”タグで特定されるＸＭＬノードを求め、この値を変数$3の値とする。この処理は次の手順で行われる。まず、当該構造化文書検索装置は、変数$10で求めた値（“/people/person/wincount”タグにより特定されるＸＭＬノードのＤＢ内格納位置情報である）を１つ取り出し、peopleデータベースを走査してこのＤＢ内格納位置情報によって示される格納位置を探し、その格納位置からその格納位置から該当するＸＭＬノードを読み出す。次に、当該構造化文書検索装置は、読み出したＸＭＬノードを基にその親ノードを参照して、親ノードのＤＢ内格納位置情報を求め、これを変数$3の値とする。以上の一連の処理を変数$10で求められている全ての値に関して繰り返し実行する。即ち、ここで、変数$10で求められている値の回数だけ、peopleデータベースの走査が繰り返し実行されることになる。
【００５２】
次に、操作３では、当該構造化文書検索装置は、“/people/person/bidcount” タグにより特定されるＸＭＬノードに関するインデクスを使用して、操作１と同様にして、“/people/person/bidcount”タグにより特定され“10”以上の値をキー値として示すＸＭＬノードのＤＢ内格納位置情報を順次取得する。この走査により得られたＤＢ内格納位置情報が変数$5と変数$4の値として求められ記録される。この操作は、“/people/person/bidcount” タグにより特定されるＸＭＬノードに関するインデクスに対する走査のみで行われ、peopleデータベース自体の走査は行う必要が無い。次に、操作４では、当該構造化文書検索装置は、変数$4に関し、“/people/person/bidcount”タグで特定されるＸＭＬノードの親ノードとなる“/people/person”タグで特定されるＸＭＬノードの値を、peopleデータベースを走査することにより求め、変数$3の値を求める。この処理は操作２と同様の手順で行われる。まず、当該構造化文書検索装置は、変数$4で求めた値（“/people/person/bidcount”タグで特定されるＸＭＬノードのＤＢ内格納位置情報である）を１つ取り出し、peopleデータベースを走査してこのＤＢ内格納位置情報によって示される格納位置を探し、その格納位置からその格納位置から該当するＸＭＬノードを読み出す。次に、当該構造化文書検索装置は、読み出したＸＭＬノードを基にその親ノードを参照して、親ノードのＤＢ内格納位置情報を求め、これを変数$3の値とする。以上の一連の処理を変数$4で求められている全ての値に関して繰り返し実行する。即ち、ここで、変数$4で求められている値の回数だけ、peopleデータベースの走査が繰り返し実行されることになる。
【００５３】
以下、操作５、操作６、操作７、操作８、操作９も操作２と同様に、当該構造化文書検索装置は、peopleデータベースの走査を行い、それぞれの操作で求めるべきＸＭＬノードのＤＢ内格納位置情報を求める。そして、操作１０では、当該構造化文書検索装置は、変数$7として求められたＤＢ内格納位置情報を順次取り出し、そのＤＢ内格納位置情報によって示される格納位置を、peopleデータベースの走査を行うことにより求め、その格納位置に格納されているＸＭＬノードの値を読み出し、読み出した値に対して“op:numeric-integer-divide”の演算を行い、結果を変数$8に格納する、という一連の動作を順次繰り返し実行する。即ち、操作１０では、当該構造化文書検索装置は、peopleデータベースの走査を繰り返し行うことにより演算すべき値を取得することになる。
【００５４】
以上のように、従来の構造化文書検索装置は、操作２，４〜１０においても、操作毎にデータベースを走査して各ＸＭＬノードの構造を辿ることで、各変数を求めていた。このため、データベースを走査する回数が多く、検索処理全体の時間が掛かってしまい、高速な検索を実現することは困難であった。
【００５５】
これに対し、本実施の形態によれば、上述したように、複合操作においてデータベースの走査を文書単位で１回行えば良い。このため、データベースの走査する回数を低減させることができ、検索速度を向上させることができる。
【００５６】
[変形例]
なお、本発明は前記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、前記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。また、以下に例示するような種々の変形が可能である。
【００５７】
＜変形例１＞
上述した各実施の形態において、構造化文書検索装置１００で実行される各種プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また、当該各種プログラムを、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録して提供するように構成しても良い。
【００５８】
＜変形例２＞
上述の各実施の形態においては、構造化文書検索装置１００は、入力装置を介して検索要求を受け付けるようにした。しかし、構造化文書検索装置１００は、クライアント装置とネットワークを介して接続され、クライアント装置から送信された検索要求を受信して、当該検索要求に応じて、上述のように検索処理を行うようにしても良い。また、構造化文書検索装置１００は、検索処理の実行結果を構造化文書形式に成形した後、これをクライアント装置にネットワークを介して出力するようにしても良い。
【００５９】
＜変形例３＞
上述の各実施の形態においては、構造化文書としてＸＭＬ形式で表現されるＸＭＬ文書を取り扱ったが、本実施の形態においてはこれに限らない。
【００６０】
＜変形例４＞
上述の各実施の形態においては、構造化文書検索装置１００は、インタプリタ実行やパイプライン実行を用いた検索処理に際しても、上述と同様に検索プランを最適化して検索処理を行うようにしても良い。
【００６１】
＜変形例５＞
上述の第２の実施の形態においては、ＤＢ単位種別の操作を取り扱わないようにしたが、これを取り扱うように構成しても良い。
【００６２】
また、上述の第２の実施の形態においては、検索プランの実行の際、peopleデータベースを走査して、検索処理の対象となるＸＭＬ文書の情報（文書情報）を全体一括で読み取る処理を、文書単位検索実行部１００７が行うようにしたが、これをＤＢ単位検索実行部１００６が行うように構成しても良い。
【００６３】
また、ＤＢ単位種別の操作を取り扱わない場合、構造化文書検索装置１００が実行制御部１００５やＤＢ単位検索実行部１００６を有さないように構成して良い。
【００６４】
＜変形例６＞
構造化文書検索装置の構成は、上述の各実施の形態のものに限らない。図１９は、本変形例にかかる構造化文書検索装置１００´の構成を例示する図である。同図に示されるように、構造化文書検索実行部１００４´は、実行制御部１００５と、ＤＢ単位検索実行部１００６と、文書単位検索実行部１００７とに加え、演算実行部１０１０を更に備える。演算実行部１０１０は、実行制御部１００５からの要求に応じて、複合操作の実行過程で求められる中間結果及びＤＢ単位種別の操作の実行過程で求められる中間結果を取得し、各中間結果に対して集合演算を実行することにより、当該集合演算の結果を検索プランの実行結果として得る。
【００６５】
実行制御部１００５は、最適化された検索プランに従って、複合操作の実行を文書単位検索実行部１００７に要求する際に、複合操作の種別及び当該複合操作の実行に必要な中間結果を文書単位検索実行部１００７に送る。そして、当該要求に応じて複合操作の実行過程で求められる中間結果を実行制御部１００５は取得する。また、実行制御部１００５は、ＤＢ単位種別の操作の実行をＤＢ単位検索実行部１００６に要求する際に、ＤＢ単位種別の操作の種別及び当該ＤＢ単位種別の操作の実行に必要な中間結果をＤＢ単位検索実行部１００６に送る。そして、当該要求に応じて前記ＤＢ単位種別の操作操作の実行過程で求められる中間結果を実行制御部１００５は取得する。更に、実行制御部１００５は、各実行結果に対する集合演算の実行を演算実行部１０１０に要求する。
【００６６】
文書単位検索実行部１００７は、複合操作の実行が実行制御部１００５から要求された場合、複合操作の種別及び当該複合操作の実行に必要な中間結果を用いて、複合操作を実行して、その中間結果を求める。ＤＢ単位検索実行部１００６は、ＤＢ単位種別の操作の実行が実行制御部１００５から要求された場合、ＤＢ単位種別の操作の種別及び当該ＤＢ単位種別の操作の実行に必要な中間結果を用いて、ＤＢ単位種別の操作を実行して、その中間結果を求める。それ以外の構成については、上述の構造化文書検索装置１００と同様であるため、その説明を省略する。
【００６７】
以上のような構成によっても、構造化文書を検索する場合、データベースを走査する回数を低減させて検索速度を向上可能である。
【００６８】
＜変形例７＞
構造化文書検索装置の構成は、上述の各実施の形態及び各変形例のものに限らない。図２０は、本変形例にかかる構造化文書検索装置１００"の構成を例示する図である。同図に示されるように、構造化文書検索実行部１００４"は、文書単位検索実行部１００７´と、演算実行部１０１０とを備える。構造化文書データ管理部１００９´は、ＤＢ単位検索実行部１００１１´と、構造化文書データ格納部１０１２とを備える。演算実行部１０１０は、上述の変形例６と略同様であるため、その説明を省略する。構造化文書データ格納部１０１２は、上述したデータベースのことである。
【００６９】
文書単位検索実行部１００７´は、操作の実行を検索実行順序制御部１００３から直接要求される。文書単位検索実行部１００７´は、複合操作の実行を検索実行順序制御部１００３から要求された場合、複合操作の種別及び当該複合操作の実行に必要な中間結果を演算実行部１０１０から取得し、当該複合操作の実行に際して実行されるＤＢ単位種別の操作を抽出し、当該ＤＢ単位種別の実行をＤＢ単位検索実行部１０１１´に要求する。当該要求に応じて実行されるＤＢ単位種別の操作の実行過程で求められる中間結果を文書単位検索実行部１００７´は取得する。そして、文書単位検索実行部１００７´は、当該ＤＢ単位種別の操作後に複合操作を実行する場合、取得された中間結果を用いて処理対象のＸＭＬ文書を取得して、当該ＸＭＬ文書に対して複合操作を文書単位で一括して実行して、新たな中間結果を求める。
【００７０】
また、文書単位検索実行部１００７´は、ＤＢ単位種別の操作の実行を検索実行順序制御部１００３から要求された場合、当該ＤＢ単位種別の操作の実行に必要な実行結果を演算実行部１０１０から取得し、当該ＤＢ単位種別の操作の実行をＤＢ単位検索実行部１０１１´に要求する。当該要求に応じて実行されるＤＢ単位種別の操作の実行過程で求められる中間結果を文書単位検索実行部１００７´は取得する。ＤＢ単位検索実行部１０１１´は、文書単位検索実行部１００７´からの要求に応じて、上述の実施形態と同様にして、構造化文書データ格納部１０１２を走査して、ＤＢ単位種別の操作を実行して、中間結果を求める。それ以外の構成については、上述の構造化文書検索装置１００と同様であるため、その説明を省略する。
【００７１】
以上のような構成によっても、構造化文書を検索する場合、データベースを走査する回数を低減させて検索速度を向上可能である。
【図面の簡単な説明】
【００７２】
【図１】第１の実施の形態にかかる構造化文書検索装置１００の機能的構成を例示する図である。
【図２】同実施の形態にかかるpeopleデータベースのスキーマの構造を例示する図である。
【図３】図２に示したＸＭＬ文書に対する検索式を例示する図である。
【図４】同実施の形態にかかる操作割当テーブルのデータ構成を例示する図である。
【図５】同実施の形態にかかる構造化文書検索装置１００の行う処理の手順を示すフローチャートである。
【図６】図３の検索式が入力された場合に得られる検索条件制約グラフを例示する図である。
【図７】図６に示した検索条件制約グラフに基づいて生成される検索プランを例示する図である。
【図８】同実施の形態にかかる各操作１〜１０の種別を示す図である。
【図９】同実施の形態にかかる検索プランの最適化を模式的に示す図である。
【図１０】図７に示される検索プランが最適化されたものを例示する図である。
【図１１】第２の実施の形態で取り扱うインデクスを例示する図である。
【図１２】同実施の形態にかかる構造化文書検索装置１００の機能的構成を例示する図である。
【図１３】同実施の形態にかかる操作割当テーブルのデータ構成を例示する図である。
【図１４】図６に示した検索条件制約グラフに基づいて生成される検索プランを例示する図である。
【図１５】同実施の形態にかかる各操作１〜１０の種別を示す図である。
【図１６】同実施の形態にかかる検索プランを例示する図である。
【図１７】同実施の形態にかかる検索プランの最適化を模式的に示す図である。
【図１８】図１３に示される検索プランが最適化されたものを例示する図である。
【図１９】一実施の形態の一変形例にかかる構造化文書検索装置１００´の機能的構成を例示する図である。
【図２０】一実施の形態の一変形例にかかる構造化文書検索装置１００"の機能的構成を例示する図である。
【符号の説明】
【００７３】
１００    構造化文書検索装置
１００１  検索要求受付部（要求受付手段）
１００２  検索プラナ部（生成手段）
１００３  検索実行順序制御部（検索実行順序制御手段）
１００４  構造化文書検索実行部（検索実行手段）
１００５  実行制御部（実行制御手段）
１００６  ＤＢ単位検索実行部（ＤＢ単位検索実行手段）
１００７  文書単位検索実行部（文書単位検索実行手段）
１００８  文書単位検索最適化部（最適化手段）
１００９  構造化文書データ管理部
１０１０  演算実行部（演算実行手段）
１０１１  ＤＢ単位検索実行部(ＤＢ単位検索実行手段)
１０１２  構造化文書データ格納部（データベース）
【図１】
0005060361.tif 000002
【図２】
0005060361.tif 000003
【図３】
0005060361.tif 000004
【図４】
0005060361.tif 000005
【図５】
0005060361.tif 000006
【図６】
0005060361.tif 000007
【図７】
0005060361.tif 000008
【図８】
0005060361.tif 000009
【図９】
0005060361.tif 000010
【図１０】
0005060361.tif 000011
【図１１】
0005060361.tif 000012
【図１２】
0005060361.tif 000013
【図１３】
0005060361.tif 000014
【図１４】
0005060361.tif 000015
【図１５】
0005060361.tif 000016
【図１６】
0005060361.tif 000017
【図１７】
0005060361.tif 000018
【図１８】
0005060361.tif 000019
【図１９】
0005060361.tif 000020
【図２０】
0005060361.tif 000021