(57)【要約】【課題】構造化文書を構成するノード間の先祖・子孫関係を高速に判別することを可能とする。【解決手段】ＸＭＬ解析部１０１は、ＸＭＬ文書を解析して、そのＸＭＬ文書のノードに関する情報を出力する。格納部１０２は、ＸＭＬ文書のノードに関する情報中の処理対象ノードの出現順を表す順番号と、処理対象ノードより後に出現する情報中のノードのうち処理対象ノードの子孫ノードを除いて最も先に出現するノードの順番号である次番号とを少なくとも決定し、処理対象ノードのノード型等と共にノードテーブル２に格納する。検索部１０５には格納情報中の比較元ノードの順番号が比較先ノードの順番号より大きく、かつ、比較元ノードの順番号が比較先ノードの次番号より小さいときに、比較元ノードが比較先ノードの子孫ノードであると判断する子孫ノード検索手段１０５ｇを有する。【選択図】図１
2012073706.tif 000002
【特許請求の範囲】
【請求項１】
構造化文書を解析して、その構造化文書に含まれるノードに関する情報を出力する構造化文書解析手段と、
前記構造化文書のノードに関する情報が格納されるノードテーブルを有する記憶手段と、
前記構造化文書解析手段から出力された前記構造化文書のノードに関する情報中の対象ノードの出現順を表す順番号を決定すると共に、前記対象ノードより後に前記情報中に出現するノードのうち前記対象ノードの子孫ノードを除いて最も先に出現するノードの前記順番号を前記対象ノードに付す次番号として決定し、前記対象ノードに関する情報と共に前記順番号と前記次番号とを前記ノードテーブルに格納する格納手段と、
供給される検索手順リストに従い、前記ノードテーブルの格納情報を参照して検索結果を出力する検索手段と
を備え、前記検索手段は、前記格納情報中の比較元ノードの前記順番号が比較先ノードの前記順番号より大きく、かつ、前記比較元ノードの前記順番号が前記比較先ノードの前記次番号より小さいときに、前記比較元ノードが前記比較先ノードの子孫ノードであると判断する子孫ノード検索手段を有することを特徴とする構造化文書格納装置。
【請求項２】
前記構造化文書は、出現順が定義される第１のノードと、出現順が定義されない第２のノードとを含み、
前記格納手段は、前記第１のノードの前記順番号に、その第１のノードの出現順に２ずつ増加する０以上の整数を割り当て、前記第２のノードの前記順番号に、その第２のノードの一つ上位のノードである親ノードの前記順番号に１を加算した値を割り当て、
前記子孫ノード検索手段は、前記比較元ノードの前記順番号が前記比較先ノードの前記順番号に１を加算した値より大きく、かつ、前記比較元ノードの前記順番号が前記比較先ノードの前記次番号より小さいときに、前記比較元ノードが前記比較先ノードの子孫ノードであると判断する
ことを特徴とする請求項１記載の構造化文書格納装置。
【請求項３】
構造化文書を解析して、その構造化文書に含まれるノードに関する情報を出力する構造化文書解析ステップと、
前記構造化文書解析ステップにより解析して得られた前記構造化文書のノードに関する情報中の対象ノードの出現順を表す順番号を決定すると共に、前記対象ノードより後に前記情報中に出現するノードのうち前記対象ノードの子孫ノードを除いて最も先に出現するノードの前記順番号を前記対象ノードに付す次番号として決定し、前記対象ノードに関する情報と共に前記順番号と前記次番号とを、前記構造化文書のノードに関する情報が格納されるノードテーブルに格納する格納ステップと、
供給される検索手順リストに従い、前記ノードテーブルの格納情報を参照して検索結果を出力する検索ステップと
を備え、前記検索ステップは、前記格納情報中の比較元ノードの前記順番号が比較先ノードの前記順番号より大きく、かつ、前記比較元ノードの前記順番号が前記比較先ノードの前記次番号より小さいときに、前記比較元ノードが前記比較先ノードの子孫ノードであると判断する子孫ノード検索ステップを含むことを特徴とする構造化文書格納方法。
【請求項４】
前記構造化文書は、出現順が定義される第１のノードと、出現順が定義されない第２のノードとを含み、
前記格納ステップは、前記第１のノードの前記順番号に、その第１のノードの出現順に２ずつ増加する０以上の整数を割り当て、前記第２のノードの前記順番号に、その第２のノードの一つ上位のノードである親ノードの前記順番号に１を加算した値を割り当て、
前記子孫ノード検索ステップは、前記比較元ノードの前記順番号が前記比較先ノードの前記順番号に１を加算した値より大きく、かつ、前記比較元ノードの前記順番号が前記比較先ノードの前記次番号より小さいときに、前記比較元ノードが前記比較先ノードの子孫ノードであると判断する
ことを特徴とする請求項３記載の構造化文書格納方法。
【請求項５】
コンピュータに、
構造化文書を解析して、その構造化文書に含まれるノードに関する情報を出力する構造化文書解析ステップと、
前記構造化文書解析ステップにより解析して得られた前記構造化文書のノードに関する情報中の対象ノードの出現順を表す順番号を決定すると共に、前記対象ノードより後に前記情報中に出現するノードのうち前記対象ノードの子孫ノードを除いて最も先に出現するノードの前記順番号を前記対象ノードに付す次番号として決定し、前記対象ノードに関する情報と共に前記順番号と前記次番号とを、前記構造化文書のノードに関する情報が格納されるノードテーブルに格納させる格納ステップと、
供給される検索手順リストに従い、前記ノードテーブルの格納情報を参照して検索結果を出力する検索ステップと
を実行させ、前記検索ステップは、前記格納情報中の比較元ノードの前記順番号が比較先ノードの前記順番号より大きく、かつ、前記比較元ノードの前記順番号が前記比較先ノードの前記次番号より小さいときに、前記比較元ノードが前記比較先ノードの子孫ノードであると判断する子孫ノード検索ステップを含むことを特徴とする構造化文書格納プログラム。
【請求項６】
前記構造化文書は、出現順が定義される第１のノードと、出現順が定義されない第２のノードとを含み、
前記格納ステップは、前記第１のノードの前記順番号に、その第１のノードの出現順に２ずつ増加する０以上の整数を割り当て、前記第２のノードの前記順番号に、その第２のノードの一つ上位のノードである親ノードの前記順番号に１を加算した値を割り当て、
前記子孫ノード検索ステップは、前記比較元ノードの前記順番号が前記比較先ノードの前記順番号に１を加算した値より大きく、かつ、前記比較元ノードの前記順番号が前記比較先ノードの前記次番号より小さいときに、前記比較元ノードが前記比較先ノードの子孫ノードであると判断する
ことを特徴とする請求項５記載の構造化文書格納プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は構造化文書格納装置、構造化文書格納方法及び構造化文書格納プログラムに係り、特にＸＭＬ（拡張可能なマーク付け言語；Extensible Markup Language）に代表される構造化文書を格納する構造化文書格納装置、構造化文書格納方法及び構造化文書格納プログラムに関する。
【背景技術】
【０００２】
ＸＭＬに代表される構造化文書を格納し、格納した構造化文書を構成する要素を高速に検索する方法として、構造化文書を表形式のテーブルから成るリレーショナルデータベースに格納する方法がある。
【０００３】
例えば、特許文献１には、ＸＭＬデータの各エレメントの内容及び属性値の項目と、データ間のリンク関係をテーブルに格納するとともに、データの出現順に順番号を割り当て、データの順番号と親エレメントの順番号をテーブルに格納するＸＭＬデータの格納方法が開示されている。この特許文献１記載のＸＭＬデータ、すなわち構造化文書の格納方法では、テーブルに格納されているエレメントの順番号及びそのエレメントの親エレメントの順番号により、エレメント間の親子関係を高速に判別できるとともに、データ間の階層関係についても判別可能である。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第３５６００４３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１に記載の構造化文書の格納方法では、エレメント間の先祖・子孫関係を即座に判別することができない。あるいは、エレメント間の親子関係を順次判別しながらエレメントを辿ることにより先祖・子孫関係を判別する方法も考えられるが、その方法では高速に判別することはできないことが課題である。
【０００６】
本発明は上記の点に鑑みなされたもので、構造化文書を構成するノード間の先祖・子孫関係を高速に判別することを可能とする構造化文書格納装置、構造化文書格納方法及び構造化文書格納プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するため、第１の発明の構造化文書格納装置は、構造化文書を解析して、その構造化文書に含まれるノードに関する情報を出力する構造化文書解析手段と、構造化文書のノードに関する情報が格納されるノードテーブルを有する記憶手段と、構造化文書解析手段から出力された構造化文書のノードに関する情報中の対象ノードの出現順を表す順番号を決定すると共に、対象ノードより後に情報中に出現するノードのうち対象ノードの子孫ノードを除いて最も先に出現するノードの順番号を対象ノードに付す次番号として決定し、対象ノードに関する情報と共に順番号と次番号とをノードテーブルに格納する格納手段と、供給される検索手順リストに従い、ノードテーブルの格納情報を参照して検索結果を出力する検索手段とを備え、検索手段は、格納情報中の比較元ノードの順番号が比較先ノードの順番号より大きく、かつ、比較元ノードの順番号が比較先ノードの次番号より小さいときに、比較元ノードが比較先ノードの子孫ノードであると判断する子孫ノード検索手段を有することを特徴とする。
【０００８】
また、上記の目的を達成するため、第２の発明の構造化文書格納装置は、第１の発明における上記構造化文書が、出現順が定義される第１のノードと、出現順が定義されない第２のノードとを含み、格納手段が、第１のノードの順番号に、その第１のノードの出現順に２ずつ増加する０以上の整数を割り当て、第２のノードの順番号に、その第２のノードの一つ上位のノードである親ノードの順番号に１を加算した値を割り当て、子孫ノード検索手段が、比較元ノードの順番号が比較先ノードの順番号に１を加算した値より大きく、かつ、比較元ノードの順番号が比較先ノードの次番号より小さいときに、比較元ノードが比較先ノードの子孫ノードであると判断することを特徴とする。
【０００９】
また、上記の目的を達成するため、第３の発明の構造化文書格納方法は、構造化文書を解析して、その構造化文書に含まれるノードに関する情報を出力する構造化文書解析ステップと、構造化文書解析ステップにより解析して得られた構造化文書のノードに関する情報中の対象ノードの出現順を表す順番号を決定すると共に、対象ノードより後に情報中に出現するノードのうち対象ノードの子孫ノードを除いて最も先に出現するノードの順番号を対象ノードに付す次番号として決定し、対象ノードに関する情報と共に順番号と次番号とを、構造化文書のノードに関する情報が格納されるノードテーブルに格納する格納ステップと、供給される検索手順リストに従い、ノードテーブルの格納情報を参照して検索結果を出力する検索ステップとを備え、検索ステップは、格納情報中の比較元ノードの順番号が比較先ノードの順番号より大きく、かつ、比較元ノードの順番号が比較先ノードの次番号より小さいときに、比較元ノードが比較先ノードの子孫ノードであると判断する子孫ノード検索ステップを含むことを特徴とする。
【００１０】
また、上記の目的を達成するため、第４の発明の構造化文書格納方法は、第３の発明における構造化文書が、出現順が定義される第１のノードと、出現順が定義されない第２のノードとを含み、格納ステップが、第１のノードの順番号に、その第１のノードの出現順に２ずつ増加する０以上の整数を割り当て、第２のノードの順番号に、その第２のノードの一つ上位のノードである親ノードの順番号に１を加算した値を割り当て、子孫ノード検索ステップが、比較元ノードの順番号が比較先ノードの順番号に１を加算した値より大きく、かつ、比較元ノードの順番号が比較先ノードの次番号より小さいときに、比較元ノードが比較先ノードの子孫ノードであると判断することを特徴とする。
【００１１】
また、上記の目的を達成するため、第５の発明の構造化文書格納プログラムは、コンピュータに、第３の発明の構造化文書格納方法における構造化文書解析ステップ、格納ステップ、及び子孫ノード検索ステップを含む検索ステップを実行させることを特徴とする。
【００１２】
更に、上記の目的を達成するため、第６の発明の構造化文書格納プログラムは、第５の発明における構造化文書が、出現順が定義される第１のノードと、出現順が定義されない第２のノードとを含み、格納ステップが、第１のノードの順番号に、その第１のノードの出現順に２ずつ増加する０以上の整数を割り当て、第２のノードの順番号に、その第２のノードの一つ上位のノードである親ノードの順番号に１を加算した値を割り当て、上記子孫ノード検索手段が、比較元ノードの順番号が比較先ノードの順番号に１を加算した値より大きく、かつ、比較元ノードの順番号が比較先ノードの次番号より小さいときに、比較元ノードが比較先ノードの子孫ノードであると判断する構成である。
【発明の効果】
【００１３】
本発明によれば、格納された構造化文書のノード間の先祖・子孫関係を検索する手順を従来に比べて短時間で行うことができ、その結果、従来に比べて構造化文書の検索を高速に行うことができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の構造化文書格納装置の一実施の形態のブロック図である。
【図２】図１中のリレーショナルデータベースにおけるノードテーブルの構成の一例を示す図である。
【図３】図２のノードテーブル中のノード型の一覧の一例を示す図である。
【図４】図１の構造化文書格納装置の格納部における文書格納処理を説明するフローチャートである。
【図５】図４中のノード格納処理の詳細を説明するフローチャートである。
【図６】図５中の属性格納処理の詳細を説明するフローチャートである。
【図７】ＸＭＬ文書の一例を示す図である。
【図８】図７のＸＭＬ文書を格納したノードテーブル例を示す図である。
【図９】図１中のＸＱｕｅｒｙ解析部が生成する検索手順の種別の一覧を示す図である。
【図１０】図１中の検索部における検索処理を説明するフローチャートである。
【図１１】図１０中の検索手順実行処理の詳細を説明するフローチャートである。
【図１２】図１１中の子孫ノード検索処理の詳細を説明するフローチャートである。
【図１３】図１１中の先祖ノード検索処理の詳細を説明するフローチャートである。
【図１４】図１０中のサブツリーデータ抽出処理の詳細を説明するフローチャートである。
【図１５】図１中のＸＱｕｅｒｙ解析部に入力される検索クエリの一例を示す図である。
【図１６】図１中のＸＱｕｅｒｙ解析部により生成される検索手順リストの一例を示す図である。
【図１７】図１中の検索部が図１６の検索手順リストを用いて行う検索処理によるコンテクストノードリストの遷移を示す図である。
【図１８】図１中のＸＭＬ成形部から出力される検索結果の一例を示す図である。
【発明を実施するための形態】
【００１５】
以下、発明を実施するための形態について図面と共に詳細に説明する。
【００１６】
図１は、本発明になる構造化文書格納装置の一実施の形態のブロック図を示す。
【００１７】
図１に示すように、本実施の形態の構造化文書格納装置１は、ＸＭＬ解析部１０１と、格納部１０２と、リレーショナルデータベース１０３と、クエリ（ＸＱｕｅｒｙ）解析部１０４と、検索部１０５と、ＸＭＬ成形部１０６とから構成されている。この構造化文書格納装置１は、入力された構造化文書であるＸＭＬ文書をリレーショナルデータベース１０３に格納するとともに、入力された検索クエリに従ってＸＭＬ文書内を検索部１０５で検索し、検索クエリに合致するノードのリストを検索結果として出力する構造化文書格納装置である。
【００１８】
ＸＭＬ解析部１０１は、テキストデータとして入力されたＸＭＬ文書を解析し、ＸＭＬ文書を構成する各ノードに対応するオブジェクトを木構造に配置したＤＯＭ（文書オブジェクトモデル；Document Object Model）データを生成して格納部１０２へ供給する。
【００１９】
ここで、ＸＭＬ文書の概要について説明する。周知のように、ＸＭＬ文書では、「＜要素名＞」で表される開始タグと「＜／要素名＞」で表される終了タグとの間にテキストや要素の集合を記述する。また、１つのタグで完結する要素は、空要素と呼ばれる。また、開始タグ、または空要素タグの中に「＜要素名  属性名＝“属性値”＞」のように属性を記述することができる。また、構造化文書であるＸＭＬ文書は、ＸＭＬの論理構造に基づいて木構造に変換できる。ＸＭＬ文書の各要素、属性やテキストは、木構造においてノードと呼ばれる。
【００２０】
このノードにおいて、「親ノード」、「子ノード」、「子孫ノード」、「先祖ノード」という表現が用いられることがある。「親ノード」は、処理対象ノードの一つ上位のノードであり、「子ノード」は、処理対象ノードの一つ下位のノードであり、「子孫ノード」は、処理対象ノードの全下位ノードを示し、「先祖ノード」は、処理対象ノードの全上位ノードを示す。なお、要素はノードの一種であるので、開始タグは「＜ノード名＞」、終了タグは「＜／ノード名＞」で表されると表現することもできる。
【００２１】
格納部１０２は、ＸＭＬ解析部１０１からＤＯＭデータが供給されると、供給されたＤＯＭデータによって表わされるＸＭＬ文書をリレーショナルデータベース１０３に格納するものであり、その機能上、ノードＩＤ決定手段１０２ａと、順番号決定手段１０２ｂと、ノードデータ挿入手段１０２ｃと、属性データ挿入手段１０２ｄと、属性格納手段１０２ｅと、子ノード格納手段１０２ｆとを備える。
【００２２】
ノードＩＤ決定手段１０２ａは、処理対象ノードを一意に識別するノードＩＤを決定する。具体的には、ノードＩＤ決定手段１０２ａは、リレーショナルデータベース１０３内のノードテーブル２に格納されている、いずれのノードＩＤとも一致しない０以外の正の整数を選択し、それを処理対象ノードのノードＩＤとする。
【００２３】
順番号決定手段１０２ｂは、処理対象ノードに対し、ノードの出現順を表す順番号を決定する。さらに、順番号決定手段１０２ｂは、処理対象ノードに対し、処理対象ノードより後に出現するノードのうち処理対象ノードの子孫ノードを除いて最も先に出現するノードの順番号である次番号を決定する。ただし、処理対象ノードより後に出現するノードが全て処理対象ノードの子孫ノードである場合、次番号は、処理対象ノードより後に処理対象ノードの子孫ノードではない仮想ノードが存在すると仮定した場合の仮想ノードの順番号となる。
【００２４】
ノードデータ挿入手段１０２ｃは、処理対象ノードのノードデータをリレーショナルデータベース１０３内のノードテーブル２に挿入する。属性データ挿入手段１０２ｄは、処理対象ノードがノードの一種である属性である場合に、処理対象属性の属性データをリレーショナルデータベース１０３内のノードテーブル２に挿入する。
【００２５】
属性データ挿入手段１０２ｅは、処理対象ノードが保持する属性、すなわち処理対象ノードの子ノードである属性を格納する処理を行う。子ノード格納手段１０２ｆは、処理対象ノードの属性以外の子ノードを格納する処理を行う。
【００２６】
リレーショナルデータベース１０３は、例えばハードディスク等の記憶装置と、記憶装置を読み書きしてリレーショナルデータベースとしての機能を提供する処理部とにより構成され、表形式のノードテーブル２を有し、ノードテーブル２に格納されたデータを検索する機能を備える。
【００２７】
ＸＱｕｅｒｙ解析部１０４は、ＸＱｕｅｒｙ（ＸＭＬクエリ言語；XML Query Language）の形式で記述された検索クエリが入力されると、入力された検索クエリを解析し、検索処理を実行するための検索手順リストを生成して検索部１０５へ供給する。ＸＱｕｅｒｙは、ＸＭＬデータを検索する問い合わせ言語として策定されている。
【００２８】
検索部１０５は、ＸＱｕｅｒｙ解析部１０４から検索手順リストが供給されると、供給された検索手順リストに従ってリレーショナルデータベース１０３に格納されているＸＭＬ文書に対する検索を実行し、検索結果であるサブツリーデータのリストをＸＭＬ成形部１０６へ供給するものであり、その機能上、検索制御手段１０５ａと、ノード型検索手段１０５ｂと、ノード名検索手段１０５ｃと、ノード値検索手段１０５ｄと、子ノード検索手段１０５ｅと、親ノード検索手段１０５ｆと、子孫ノード検索手段１０５ｇと、先祖ノード検索手段１０５ｈと、サブツリーデータ抽出手段１０５ｉとを備える。
【００２９】
検索制御手段１０５ａは、検索部１０５における検索処理の全体を制御する。ノード型検索手段１０５ｂは、検索手順がノード型検索である場合に、ノード型による検索を実行する。ノード名検索手段１０５ｃは、検索手順がノード名検索である場合に、ノード名による検索を実行する。ノード値検索手段１０５ｄは、検索手順がノード値検索である場合に、ノード値による検索を実行する。
【００３０】
子ノード検索手段１０５ｅは、検索手順が子ノード検索である場合に、子ノードの検索を実行する。親ノード検索手段１０５ｆは、検索手順が親ノード検索である場合に、親ノードの検索を実行する。子孫ノード検索手段１０５ｇは、検索手順が子孫ノード検索である場合に、子孫ノードの検索を実行する。先祖ノード検索手段１０５ｈは、検索手順が先祖ノード検索である場合に、先祖ノードの検索を実行する。
【００３１】
サブツリーデータ抽出手段１０５ｉは、検索結果のノードリストの各ノードのサブツリーデータをリレーショナルデータベース１０３から読み出し、読み出したサブツリーデータをノードデータに含まれる順番号の順に並び替えてＸＭＬ成形部１０６へ供給する。「ノードのサブツリーデータ」とは、ＸＭＬ文書の木構造において、対象ノードと、対象ノードの下位となる全てのノード（子孫ノード）を含むサブツリーの各ノードのノードデータである。
【００３２】
なお、検索部１０５は、ＸＱｕｅｒｙによって記述できる検索手順のうち、本発明に直接関係する検索手順、及び代表的な検索手順を実行するための各検索手段１０５ｂ乃至１０５ｈを備える構成となっているが、ＸＱｕｅｒｙによって記述できるその他の検索手順を実行するための検索手段をも備える構成とするのが望ましい。
【００３３】
ＸＭＬ成形部１０６は、検索部１０５からサブツリーデータのリストが供給されると、供給されたサブツリーデータをテキストデータとして記述されたＸＭＬ文書の形式に成形し、検索結果として出力する。
【００３４】
次に、構造化文書格納装置１のリレーショナルデータベース１０３におけるノードデータを格納するための表形式のノードテーブルの構成について説明する。
【００３５】
図２は、リレーショナルデータベース１０３におけるノードテーブルの構成を示す。図２において、ノードテーブル２の「列名」の欄はテーブルの各列の名前を示し、「内容」の欄は各列に格納するデータの内容を示す。
【００３６】
ノードテーブル２は、ｉｄ列２０１と、ｔｙｐｅ列２０２と、ｐａｒｅｎｔ列２０３と、ｏｒｄｅｒ列２０４と、ｎｅｘｔ列２０５と、ｎａｍｅ列２０６と、ｖａｌｕｅ列２０７とにより構成される。
【００３７】
ｉｄ列２０１は、対象ノードを一意に識別するノードＩＤである０以外の正の整数を格納する列である。ｔｙｐｅ列２０２は、対象ノードのノード型（ｔｙｐｅ）を表す数値を格納する列である。ｐａｒｅｎｔ列２０３は、対象ノードの親ノードのノードＩＤである「０」以外の整数、または親ノードが存在しないことを示す数値「０」を格納する列である。
【００３８】
ｏｒｄｅｒ列２０４は、対象ノードの順番号を格納する列である。なお、ＸＭＬではノードの種別によって出現順が定義されるノードと定義されないノードがあるが、ｏｒｄｅｒ列２０４に格納される順番号は、出現順が定義されるノードに対してはその出現順に「０」から始まる２つおきの整数を割り振った偶数の値となり、出現順が定義されないノードに対してはその親ノードの出現順に「１」を加えた奇数の値となる。
【００３９】
ｎｅｘｔ列２０５は、対象ノードの次番号を格納する列である。ただし、対象ノードが出現順が定義されないノードである場合は順番号と同じ値を格納する。ｎａｍｅ列２０６は、対象ノードのノード名（ｎａｍｅ）を格納する列である。ただし、対象ノードのノード種別がノード名を持たないものである場合、ｎａｍｅ列２０６は空（ヌル）となる。ｖａｌｕｅ列２０７は、対象ノードのノード値（ｖａｌｕｅ）を格納する列である。ただし、対象ノードのノード種別がノード値を持たないものである場合、ｖａｌｕｅ列２０７は空（ヌル）となる。
【００４０】
次に、図２の本発明の一実施形態である構造化文書格納装置１のノードテーブル２におけるｔｙｐｅ列２０２に格納されるノード型を表す数値について説明する。
【００４１】
図３は、ノードテーブル２におけるｔｙｐｅ列２０２に格納されるノード型の一覧を示す。図３の「ｔｙｐｅ値」の欄はノードテーブル２におけるｔｙｐｅ列２０２に格納されるノード型を表す数値を示し、「ノード型」の欄は「ｔｙｐｅ値」に対応するノード型を示すものである。
【００４２】
ノード型には、要素(Element)３０１と、属性(Attribute)３０２と、テキストノード(Text Node)３０３と、ＣＤＡＴＡセクション(CDATA Section)３０４と、エンティティ参照(Entity Reference)３０５と、エンティティ(Entity)３０６と、処理命令(Processing Instruction)３０７と、コメント(Comment)３０８と、文書(Document)３０９と、文書型(Document Type)３１０と、文書断片(Document Fragment)３１１と、表記法(Notation)３１２とがある。これらの各ノード型に対して、「ｔｙｐｅ値」欄に示す数値が割り振られる。
【００４３】
なお、ＸＭＬにおいて、属性３０２以外のノード型はノードの出現順が定義されるが、属性３０２は出現順が定義されないものである。すなわち、同一のノードで構成される２つのＸＭＬ文書において、属性３０２以外のノードの出現順が異なる場合は異なるＸＭＬ文書となるが、属性３０２の見かけ上の出現順が異なる場合は同一のＸＭＬ文書となる。
【００４４】
また、ＸＭＬにおいて、属性３０２を含む一部のノード型は子ノードを持たないものである。また、ＸＭＬにおいて、処理対象ノードの子孫ノードには、処理対象ノードの保持する属性、すなわち処理対象ノードの子ノードとなる属性は含まれない。
【００４５】
次に、本発明の一実施形態である構造化文書格納装置１の格納部１０２における文書格納処理の詳細について説明する。
【００４６】
図４は、本実施の形態の構造化文書格納装置１の格納部１０２における文書格納処理を説明するフローチャートを示す。
【００４７】
格納部１０２のノードＩＤ決定手段１０２ａは、ＸＭＬ解析部１０１からＤＯＭデータが供給されると、文書格納処理を開始し、変数ｐに「０」を代入する（ステップＳ４０１）。なお、変数ｐは親ノードのノードＩＤを記憶しておくための変数である。次に、格納部１０２の順番号決定手段１０２ｂは、変数ｏに「０」を代入する（ステップＳ４０２）。なお、変数ｏは順番号を記憶しておくための変数である。
【００４８】
次に、格納部１０２の子ノード格納手段１０２ｆは、ルートノードを処理対象ノードとする（ステップＳ４０３）。なお、ルートノードは親ノードを持たないノードであり、ノードテーブル２におけるｐａｒｅｎｔ列２０３の値が「０」となるものである。そして、格納部１０２は、後述するノード格納処理を実行する（ステップＳ４０４）。なお、ステップＳ４０１で値を代入した変数ｐ、ステップＳ４０２で値を代入した変数ｏ、及びステップＳ４０３で決定した処理対象ノードはノード格納処理に引き継ぐ。
【００４９】
次に、図４の構造化文書格納装置１の格納部１０２における文書格納処理のステップＳ４０４のノード格納処理の詳細について説明する。
【００５０】
図５は、本実施の形態の構造化文書格納装置１の格納部１０２におけるノード格納処理を説明するフローチャートを示す。
【００５１】
格納部１０２のノードＩＤ決定手段１０２ａは、ノード格納処理を開始すると、ステップＳ４０３またはステップＳ５１５で決定した処理対象ノードのノードＩＤを決定し、決定したノードＩＤを変数ｉに代入する（ステップＳ５０１）。具体的には、ノードテーブル２のｉｄ列２０１に格納されているいずれのノードＩＤとも一致しない「０」以外の正の整数を選択し、ノードＩＤとする。
【００５２】
次に、格納部１０２のノードＩＤ決定手段１０２ａは、変数ｐの値を処理対象ノードの親ノードＩＤ、すなわちノードテーブル２のｐａｒｅｎｔ列２０３に挿入すべき値とする（ステップＳ５０２）。次に、格納部１０２の順番号決定手段１０２ｂは、変数ｏの値を処理対象ノードの順番号、すなわちノードテーブル２のｏｒｄｅｒ列２０４に挿入すべき値とする（ステップＳ５０３）。
【００５３】
次に、格納部１０２のノードデータ挿入手段１０２ｃは、処理対象ノードの次番号以外のノードデータをノードテーブル２に挿入する（ステップＳ５０４）。具体的には、ステップＳ５０１で変数ｉに代入したノードＩＤをｉｄ列２０１のノードＩＤの値とし、処理対象ノードのＤＯＭオブジェクトからノード型を取得して、ノード型一覧３におけるそのノード型に対応するｔｙｐｅ値をｔｙｐｅ列２０２の値とする。また、ステップＳ５０２で決定した親ノードＩＤをｐａｒｅｎｔ列２０３の値とし、ステップＳ５０３で決定した順番号をｏｒｄｅｒ列２０４の値とする。更に、処理対象ノードのＤＯＭオブジェクトからノード名を取得して、そのノード名をｎａｍｅ列２０６の値とし、処理対象ノードのＤＯＭオブジェクトからノード値を取得して、その値をｖａｌｕｅ列２０７の値として、ノードテーブル２に新たな行を追加する。なお、追加する行のｎｅｘｔ列２０５は空（ヌル）にしておく。
【００５４】
次に、格納部１０２のノードＩＤ決定手段１０２ａは、変数ｉの値を変数ｐに代入する（ステップＳ５０５）。次に、格納部１０２の順番号決定手段１０２ｂは、変数ｏの値に「１」を加算して変数ｏに代入する（ステップＳ５０６）。次に、格納部１０２の属性格納手段１０２ｅは、処理対象ノードが持つ属性、すなわち処理対象ノードの子ノードである属性の数を変数Ｎａに代入し、変数ａに「０」を代入する（ステップＳ５０７）。続いて、格納部１０２の属性格納手段１０２ｅは、変数ａの値が変数Ｎａの値より小さいか否かを判定する（ステップＳ５０８）。変数ａの値が変数Ｎａの値より小さいと判定された場合、ステップＳ５０９へ処理を移行し、変数Ｎａの値より小さくない、すなわち変数Ｎａの値以上であると判定された場合、ステップＳ５１１へ処理を移行する。
【００５５】
ステップＳ５０８において、変数ａの値が変数Ｎａの値より小さいと判定された場合、格納部１０２の属性格納手段１０２ｅは、変数ａの値に「１」を加算して変数ａに代入する（ステップＳ５０９）。続いて、格納部１０２の属性格納手段１０２ｅは、加算後の変数ａ番目の属性を処理対象とし、後述する属性格納処理を実行する（ステップＳ５１０）。なお、あるノードの持つ属性の間には順番が定義されていないので、例えば属性をノード名の辞書順に並べ、それを属性の順番とすればよい。また、変数ｐと変数ｏ、及びこのステップで決定した処理対象属性は属性格納処理に引き継ぐ。
【００５６】
一方、ステップＳ５０８において、変数ａの値が変数Ｎａの値より小さくない、すなわち変数Ｎａ以上であると判定された場合、格納部１０２の順番号決定手段１０２ｂは、変数ｏの値に「１」を加算して変数ｏに代入する（ステップＳ５１１）。
【００５７】
次に、格納部１０２の子ノード格納手段１０２ｆは、処理対象ノードの属性以外の子ノードの数を変数Ｎｃに代入して、変数ｃに「０」を代入する（ステップＳ５１２）。続いて、子ノード格納手段１０２ｆは、変数ｃの値が変数Ｎａの値より小さいか否かを判定する（ステップＳ５１３）。変数ｃの値が変数Ｎｃの値より小さいと判定された場合、ステップＳ５１４へ処理を移行し、変数Ｎｃの値より小さくない、すなわち変数Ｎｃの値以上であると判定された場合、ステップＳ５１６へ処理を移行する。
【００５８】
ステップＳ５１３において、変数ｃの値が変数Ｎｃの値より小さいと判定された場合、格納部１０２の子ノード格納手段１０２ｆは、変数ｃの値に「１」を加算して変数ｃに代入する（ステップＳ５１４）。続いて、子ノード格納手段１０２ｆは、加算後の変数ｃ番目の子ノードを処理対象とし、ノード格納処理を再帰的に実行する（ステップＳ５１５）。このとき、処理対象ノードの子ノードを出現順に並べて子ノードの順番とする。また、変数ｐと変数ｏ、及びこのステップＳ５１５で決定した処理対象ノードを再帰的に実行するノード格納処理に引き継ぐ。
【００５９】
一方、ステップＳ５１３において、変数ｃの値が変数Ｎｃの値より小さくない、すなわち変数Ｎｃの値以上であると判定された場合、格納部１０２の順番号決定手段１０２ｂは、変数ｏの値を処理対象ノードの次番号とする（ステップＳ５１６）。なお、このステップＳ５１６における処理対象ノードはノード格納処理開始時の処理対象ノードであり、ステップＳ５１５で決定した処理対象ノードではない。
【００６０】
次に、格納部１０２のノードデータ挿入手段１０２ｃは、ノードテーブル２における処理対象ノードの次番号を設定する（ステップＳ５１７）。具体的には、ノードテーブル２のｉｄ列２０１に対して変数ｉに格納されている処理対象ノードのノードＩＤを用いて検索を行い、ｉｄ列２０１のノードＩＤの値が変数ｉの値に一致する行のｎｅｘｔ列２０５の値をステップＳ５１６で決定した次番号の値に設定する。
【００６１】
次に、図５の本実施の形態の構造化文書格納装置１の格納部１０２におけるノード格納処理のステップＳ５１０の属性格納処理の詳細について、図６のフローチャートを参照して説明する。
【００６２】
格納部１０２のノードＩＤ決定手段１０２ａは、ステップＳ５１０の属性格納処理を開始すると、処理対象属性のノードＩＤを決定する（ステップＳ６０１）。具体的な決定方法はステップＳ５０１と同様である。続いて、ノードＩＤ決定手段１０２ａは、変数ｐの値を処理対象属性の親ノードＩＤ、すなわちノードテーブル２のｐａｒｅｎｔ列２０３に挿入すべき値とする（ステップＳ６０２）
次に、格納部１０２の順番号決定手段１０２ｂは、変数ｏの値を処理対象属性の順番号、すなわちノードテーブル２のｏｒｄｅｒ列２０４に挿入すべき値とするとともに、同じ値を処理対象属性の次番号、すなわちノードテーブル２のｎｅｘｔ列２０５に挿入すべき値とする（ステップＳ６０３）。
【００６３】
次に、格納部１０２の属性データ挿入手段１０２ｄは、処理対象属性のノードデータをノードテーブル２に挿入する（ステップＳ６０４）。具体的には、ステップＳ６０１で決定したノードＩＤをｉｄ列２０１のノードＩＤの値とし、ノード型一覧３における属性３０２に対応するｔｙｐｅ値をｔｙｐｅ列２０２の値とし、ステップＳ６０２で決定した親ノードＩＤをｐａｒｅｎｔ列２０３の値とし、ステップＳ６０３で決定した順番号をｏｒｄｅｒ列２０４の値とし、ステップＳ６０３で決定した次番号をｎｅｘｔ列２０５の値とし、処理対象属性のＤＯＭオブジェクトからノード名を取得して、そのノード名をｎａｍｅ列２０６の値とし、処理対象属性のＤＯＭオブジェクトからノード値を取得して、そのノード値をｖａｌｕｅ列２０７の値として、ノードテーブル２に新たな行を追加する。
【００６４】
次に、本発明の一実施形態である構造化文書格納装置１におけるノードテーブル２へ格納されるＸＭＬ文書の具体例について説明する。
【００６５】
図７は、構造化文書格納装置１におけるノードテーブル２へ格納されるＸＭＬ文書の一具体例を示す。同図に示すＸＭＬ文書７全体を示す文書がルートノードである。ルートノードの子ノードとして、要素名が「ｌｉｂｒａｒｙ」である要素が存在する。また、要素名が「ｂｏｏｋ」や「ｔｉｔｌｅ」等の山括弧で囲まれた部分も要素である。また、要素名が「ｂｏｏｋ」である要素はノード名が「ｉｄ」である属性を持っている。また、開始タグ「＜ｔｉｔｌｅ＞」と終了タグ「＜／ｔｉｔｌｅ＞」で挟まれた「Ｔｉｔｌｅ １」や、開始タグ「＜ａｕｔｈｏｒ＞」と終了タグ「＜／ａｕｔｈｏｒ＞」で挟まれた「Ａｕｔｈｏｒ １」等の文字列の部分は、それらの文字列がノード値であるテキストノードである。
【００６６】
図８は、本実施の形態の構造化文書格納装置１におけるノードテーブル２の一具体例を示す。この図８に示すノードテーブル例８は、図７に示したＸＭＬ文書７を格納した状態を示す。すなわち、図８において、ｉｄ列には「１」を初期値として「１」ずつ増加するノードＩＤ値が格納されている。また、図８において、図２に示したようにｔｙｐｅ列にはノード型一覧３におけるｔｙｐｅ値（すなわち、ノード型を識別する値）が格納されている。また、ｐａｒｅｎｔ列には親ノードＩＤの値が、ｏｒｄｅｒ列には順番号が、ｎｅｘｔ列には次番号が、ｎａｍｅ列にはノード名（要素名）が、ｖａｌｕｅ列にはノード値がそれぞれ格納されている。
【００６７】
例えば、ＸＭＬ文書７の１行目の開始タグ「＜ｌｉｂｒａｒｙ＞」については、ｉｄ列のノードＩＤの値が「２」、ｔｙｐｅ列のｔｙｐｅ値がノード型が要素であることを示す「１」、ｐａｒｅｎｔ列の親ノードＩＤの値が「１」が格納される。また、このノードＩＤ値「２」の「＜ｌｉｂｒａｒｙ＞」は出現順が定義されるノードであり、出現順に偶数の値「２」の順番号がｐａｒｅｎｔ列に格納され、次番号としてノードＩＤ値「１」と同じ「３４」が格納され、ノード名「ｌｉｂｒａｒｙ」がｎａｍｅ列に格納される。
【００６８】
ＸＭＬ文書７の２行目の「＜ｂｏｏｋ ｉｄ＝“１”＞」は、出現が定義されるノード「ｂｏｏｋ」と出現が定義されないノード「ｉｄ＝“１”」からなるので、ノードＩＤの値が「３」の欄に、ｔｙｐｅ値が「１」、親ノードＩＤの値が「２」、次の出現順の値「４」の順番号、値「１４」の次番号、ノード名「ｂｏｏｋ」が対応して格納される。続くノードＩＤの値が「４」の欄に、ｔｙｐｅ値が属性を示す「２」、親ノードＩＤの値が「３」、ノード名「ｉｄ」、ｖａｌｕｅ列のノード値として「１」が格納される。また、この「ｉｄ＝“１”」は出現が定義されていないので順番号はその親ノード「ｂｏｏｋ」の順番号に「１」を加算した「５」となり、また、次番号は「５」となる。
【００６９】
なお、図８のノードテーブル例８は、便宜上、各行を対応するノードの出現順に並べて示しているが、リレーショナルデータベース１０３においてノードテーブル２の行の並び順は不定である。
【００７０】
次に、本発明の一実施の形態である構造化文書格納装置１のＸＱｕｅｒｙ解析部１０４が生成する検索手順の詳細について説明する。なお、クエリ（ＸＱｕｅｒｙ）を解析して検索手順を生成する処理の詳細については、本発明と直接関係がないため、説明を省略する。
【００７１】
図９は、本実施の形態の構造化文書格納装置１のＸＱｕｅｒｙ解析部１０４が生成する検索手順の種別の一覧を示す。図９において、「検索種別」の欄は検索手順の種別を示し、「引数」の欄は検索手順に付随する引数を示し、「処理内容」の欄は検索処理の内容を示す。
【００７２】
検索手順の種別には、ノード型検索９０１と、ノード名検索９０２と、ノード値検索９０３と、子ノード検索９０４と、親ノード検索９０５と、子孫ノード検索９０６と、先祖ノード検索９０７とがある。
【００７３】
ノード型検索９０１は、ノード型一覧３のｔｙｐｅ値を引数にとり、ノード型を表す数値が引数のｔｙｐｅ値に一致するノードを検索する手順である。ノード名検索９０２は、文字列を引数にとり、ノード名が引数の文字列に一致するノードを検索する手順である。ノード値検索９０３は、文字列を引数にとり、ノード値が引数の文字列に一致するノードを検索する手順である。
【００７４】
子ノード検索９０４は、引数をとらず、コンテクストノードの子ノードを検索する手順である。なお、「コンテクストノード」とは、検索手順のリストを実行する過程において、これから実行する検索手順の直前の検索手順を実行することによって検索されたノードである。
【００７５】
親ノード検索９０５は、引数をとらず、コンテクストノードの親ノードを検索する手順である。子孫ノード検索９０６は、引数をとらず、コンテクストノードの子孫ノードを検索する手順である。先祖ノード検索９０７は、引数をとらず、コンテクストノードの先祖ノードを検索する手順である。
【００７６】
なお、検索手順一覧９には、クエリ（ＸＱｕｅｒｙ）によって記述できる検索手順のうち、本発明に直接関係する検索手順、及び代表的な検索手順を実行するための検索手順９０１乃至９０７が含まれているが、クエリ（ＸＱｕｅｒｙ）によって記述できるその他の検索手順を実行するための検索手段をも含めるのが望ましい。
【００７７】
次に、本実施の形態の構造化文書格納装置１の検索部１０５における検索処理の詳細について説明する。
【００７８】
図１０は、検索部１０５における検索処理を説明するフローチャートである。図１に示した検索部１０５内の検索制御手段１０５ａは、ＸＱｕｅｒｙ解析部１０４から検索手順リストが供給されると、検索処理を開始し、ルートノードのノードＩＤを取得し、コンテクストノードリストに追加する（ステップＳ１００１）。具体的には、リレーショナルデータベース１０３内のノードテーブル２におけるｐａｒｅｎｔ列２０３の値が「０」である行を検索し、その行のｉｄ列２０１のノードＩＤの値をルートノードのノードＩＤとして取得し、取得したルートノードのノードＩＤのみからなるコンテクストノードリストを生成する。
【００７９】
次に、検索部１０５内の検索制御手段１０５ａは、ＸＱｕｅｒｙ解析部１０４から供給された検索手順リストに含まれる検索手順の数を変数Ｎに代入し、変数ｉに「０」を代入する（ステップＳ１００２）。
【００８０】
次に、検索部１０５内の検索制御手段１０５ａは、変数ｉの値が変数Ｎの値（すなわち、検索手順リストに含まれる検索手順の数）より小さいか否かを判定する（ステップＳ１００３）。検索制御手段１０５ａは、変数ｉの値が変数Ｎの値より小さいと判定された場合、変数ｉの値に「１」を加算して変数ｉに代入する（ステップＳ１００４）。続いて、検索制御手段１０５ａは、ＸＱｕｅｒｙ解析部１０４から供給された検索手順リストに含まれる変数ｉ番目の検索手順を実行する（ステップＳ１００５）。ステップＳ１００５の処理後はステップＳ１００３に戻り、再び変数ｉの値が変数Ｎの値より小さいか否かを判定する。
【００８１】
一方、検索制御手段１０５ａは、ステップＳ１００２において、変数ｉの値が変数Ｎの値より小さくない、すなわち変数Ｎの値以上であると判定された場合、検索手順リストに含まれるすべての検索手順について検索手順を実行したと判断し、続いて、コンテクストノードリストに含まれるノード数を変数Ｍに代入すると共に、変数ｊに「０」を代入する（ステップＳ１００６）。
【００８２】
次に、検索制御手段１０５ａは、変数ｊの値が変数Ｍの値（すなわち、コンテクストノードリストに含まれるノード数）より小さいか否かを判定する（ステップＳ１００７）。変数Ｍの値より小さいと判定された場合、検索制御手段１０５ａは、変数ｊの値に「１」を加算して変数ｊに代入する（ステップＳ１００８）。続いて、検索制御手段１０５ａは、コンテクストノードリストに含まれる変数ｊ番目のノードのサブツリーデータ抽出処理を後述するように実行する（ステップＳ１００９）。ステップＳ１００９の処理後は、ステップＳ１００７に戻り、変数ｊの値が変数Ｍの値より小さいか否かを判定する。
【００８３】
一方、検索制御手段１０５ａは、ステップＳ１００７において、変数ｊの値が変数Ｍの値より小さくない、すなわち変数Ｍの値以上であると判定された場合、コンテクストノードリストに含まれるノード数のすべてについてサブツリーデータ抽出処理を実行したと判断し、ステップＳ１００９で抽出したサブツリーデータをノードの順番号で並び替える（ステップＳ１０１０）。具体的には、ステップＳ１００９で抽出した各コンテクストノードに対応する各サブツリーデータに含まれる各コンテクストノードの順番号を用いて、順番号の昇順にサブツリーデータを並び替える。これにより、検索結果のサブツリーデータがＸＭＬ文書における出現順に並ぶこととなる。
【００８４】
次に、図１０に示した検索部１０５によるステップＳ１００５の検索手順実行処理の詳細について、図１１のフローチャートを参照して説明する。
【００８５】
検索部１０５の検索制御手段１０５ａは、検索手順実行処理を開始すると、実行する検索手順がノード型検索９０１か否かを判定する（ステップＳ１１０１）。ノード型検索９０１であると判定された場合、図１に示した検索部１０５のノード型検索手段１０５ｂは、コンテクストノードリストからノード型が条件に合致するノードを選択する（ステップＳ１１０２）。具体的には、ノード型検索手段１０５ｂは、ノードテーブル２に対して、ｉｄ列２０１のノードＩＤの値がコンテクストノードリストに含まれる各ノードＩＤに一致し、かつ、ｔｙｐｅ列２０２のノード型を示す値が検索手順の引数であるｔｙｐｅ値に一致する行を検索し、検索に合致した各行のｉｄ列２０１のノードＩＤの値をノードＩＤとして読み出し、読み出したノードＩＤのリストでコンテクストノードリストを置き換える。
【００８６】
一方、ステップＳ１１０１において、実行する検索手順がノード型検索９０１ではないと判断された場合、検索制御手段１０５ａは、実行する検索手順がノード名検索９０２か否かを判定する（ステップＳ１１０３）。
【００８７】
ステップＳ１１０３において、実行する検索手順がノード名検索９０２であると判断された場合、図１に示した検索部１０５のノード名検索手段１０５ｃは、コンテクストノードリストからノード名が条件に合致するノードを選択する（ステップＳ１１０４）。具体的には、ノード名検索手段１０５ｃは、ノードテーブル２に対して、ｉｄ列２０１のノードＩＤの値がコンテクストノードリストに含まれる各ノードＩＤに一致し、かつ、ｎａｍｅ列２０６のノード名が検索手順の引数である文字列に一致する行を検索し、検索に合致した各行のｉｄ列２０１のノードＩＤの値をノードＩＤとして読み出し、読み出したノードＩＤのリストでコンテクストノードリストを置き換える。
【００８８】
一方、ステップＳ１１０３において、実行する検索手順がノード名検索９０２ではないと判断された場合、検索部１０５の検索制御手段１０５ａは、実行する検索手順がノード値検索９０３か否かを判定する（ステップＳ１１０５）。
【００８９】
ステップＳ１１０５において、実行する検索手順がノード値検索９０３であると判断された場合、図１に示した検索部１０５のノード値検索手段１０５ｄは、コンテクストノードリストからノード値が条件に合致するノードを選択する（ステップＳ１１０６）。具体的には、ノード値検索手段１０５ｄは、ノードテーブル２に対して、ｉｄ列２０１のノードＩＤの値がコンテクストノードリストに含まれる各ノードＩＤに一致し、かつ、ｖａｌｕｅ列２０７のノード値が検索手順の引数である文字列に一致する行を検索し、検索に合致した各行のｉｄ列２０１のノードＩＤの値をノードＩＤとして読み出し、読み出したノードＩＤのリストでコンテクストノードリストを置き換える。
【００９０】
一方、ステップＳ１１０５において、実行する検索手順がノード値検索９０３ではないと判断された場合、検索部１０５の検索制御手段１０５ａは、実行する検索手順が子ノード検索９０４か否かを判定する（ステップＳ１１０７）。
【００９１】
ステップＳ１１０７において、実行する検索手順が子ノード検索９０４であると判断された場合、図１に示した検索部１０５の子ノード検索手段１０５ｅは、コンテクストノードリストの各ノードの子ノードを検索する（ステップＳ１１０８）。具体的には、子ノード検索手段１０５ｅは、ノードテーブル２に対して、ｐａｒｅｎｔ列２０３の親ノードＩＤの値がコンテクストノードリストに含まれる各ノードＩＤに一致する行を検索し、検索に合致した各行のｉｄ列２０１のノードＩＤの値をノードＩＤとして読み出し、読み出したノードＩＤのリストでコンテクストノードリストを置き換える。
【００９２】
一方、ステップＳ１１０７において、実行する検索手順が子ノード検索９０４ではないと判断された場合、検索部１０５の検索制御手段１０５ａは、実行する検索手順が親ノード検索９０５か否かを判定する（ステップＳ１１０９）。
【００９３】
ステップＳ１１０９において、実行する検索手順が親ノード検索９０５であると判断された場合、図１に示した検索部１０５の親ノード検索手段１０５ｆは、コンテクストノードリストの各ノードの親ノードを検索する（ステップＳ１１１０）。具体的には、親ノード検索手段１０５ｆは、ノードテーブル２に対して、ｉｄ列２０１のノードＩＤの値がコンテクストノードリストに含まれる各ノードＩＤに一致する行を検索し、検索に合致した各行のｐａｒｅｎｔ列２０３の親ノードＩＤの値をノードＩＤとして読み出し、読み出したノードＩＤのリストでコンテクストノードリストを置き換える。
【００９４】
一方、ステップＳ１１０９において、実行する検索手順が親ノード検索９０５ではないと判断された場合、検索部１０５の検索制御手段１０５ａは、実行する検索手段が子孫ノード検索９０６か否かを判定する（ステップＳ１１１１）。
【００９５】
ステップＳ１１１１において、実行する検索手順が子孫ノード検索９０６であると判断された場合、図１に示した検索部１０５の子孫ノード検索手段１０５ｇは、後述する子孫ノード検索処理を実行する（ステップＳ１１１２）。一方、ステップＳ１１１１において、実行する検索手順が子孫ノード検索９０６ではないと判断された場合、検索部１０５の検索制御手段１０５ａは、実行する検索手順が先祖ノード検索９０７か否かを判定する（ステップＳ１１１３）。
【００９６】
ステップＳ１１１３において、実行する検索手順が先祖ノード検索９０７であると判断された場合、図１に示した検索部１０５の先祖ノード検索手段１０５ｈは、後述する先祖ノード検索処理を実行する（ステップＳ１１１４）。一方、ステップＳ１１１３において、実行する検索手順が先祖ノード検索９０７ではないと判断された場合、検索部１０５の検索制御手段１０５ａは、検索手順一覧９に記載しないその他の検索手順を実行する（ステップＳ１１１５）。その他の検索手順実行処理の詳細については説明を省略する。
【００９７】
次に、図１１に示した検索部１０５によるステップＳ１１１２の子孫ノード検索処理の詳細について図１２のフローチャートを参照して説明する。
【００９８】
検索部１０５の子孫ノード検索手段１０５ｇは、子孫ノード検索処理を開始すると、ノードテーブル２に対して、ｉｄ列２０１のノードＩＤの値がコンテクストノードリストに含まれるノードＩＤに一致する行を検索する（ステップＳ１２０１）。
【００９９】
次に、検索部１０５の子孫ノード検索手段１０５ｇは、ノードテーブル２に対して、ｏｒｄｅｒ列２０４の順番号の値がステップＳ１２０１で検索された各行のｏｒｄｅｒ列２０４の順番号の値に「１」を加算した値より大きく、ステップＳ１２０１で検索された各行のｎｅｘｔ列２０５の次番号の値より小さい行を子孫ノードとして検索する（ステップＳ１２０２）。
【０１００】
次に、検索部１０５の子孫ノード検索手段１０５ｇは、ステップＳ１２０２で検索された子孫ノードと検索された各行のｉｄ列２０１のノードＩＤの値を読み出し、読み出したノードＩＤのリストでコンテクストノードリストを置き換える（ステップＳ１２０３）。
【０１０１】
なお、ステップＳ１２０２において、ｏｒｄｅｒ列２０４の順番号の値に「１」を加算して検索を行うことにより、コンテクストノードの属性を子孫ノードの検索から除外できる効果がある。
【０１０２】
次に、図１１に示した検索部１０５によるステップＳ１１１４の先祖ノード検索処理の詳細について、図１３のフローチャートを参照して説明する。
【０１０３】
検索部１０５の先祖ノード検索手段１０５ｈは、先祖ノード検索処理を開始すると、ノードテーブル２に対して、ｉｄ列２０１のノードＩＤの値がコンテクストノードリストに含まれるノードＩＤに一致する行を検索する（ステップＳ１３０１）。
【０１０４】
次に、検索部１０５の先祖ノード検索手段１０５ｈは、ノードテーブル２に対して、ｏｒｄｅｒ列２０４の順番号の値がステップＳ１３０１で検索された各行のｏｒｄｅｒ列２０４の順番号の値より小さく、ｎｅｘｔ列２０５の次番号の値がステップＳ１３０１で検索された各行のｏｒｄｅｒ列２０４の順番号の値より大きい行を検索する（ステップＳ１３０２）。
【０１０５】
次に、検索部１０５の先祖ノード検索手段１０５ｈは、ステップＳ１３０２で検索された各行のｉｄ列２０１のノードＩＤの値を読み出し、読み出したノードＩＤのリストでコンテクストノードリストを置き換える（Ｓ１３０３）。
【０１０６】
次に、図１０に示した検索部１０５によるステップＳ１００９のサブツリーデータ抽出処理の詳細について、図１４のフローチャートを参照して説明する。
【０１０７】
図１に示した検索部１０５のサブツリーデータ抽出手段１０５ｉは、サブツリーデータ抽出処理を開始すると、ノードテーブル２に対して、ｉｄ列２０１のノードＩＤの値が処理対象ノードのノードＩＤに一致する行を検索する（ステップＳ１４０１）。
【０１０８】
次に、検索部１０５のサブツリーデータ抽出手段１０５ｉは、ノードテーブル２に対して、ｏｒｄｅｒ列２０４の順番号の値がステップＳ１４０１で検索された行のｏｒｄｅｒ列２０４の順番号の値以上であり、ステップＳ１４０１で検索された行のｎｅｘｔ列２０５の次番号の値より小さい行を検索する（ステップＳ１４０２）。そして、検索部１０５のサブツリーデータ抽出手段１０５ｉは、ステップＳ１４０２で検索された各行のｉｄ列の値を読み出す（ステップＳ１４０３）。
【０１０９】
次に、本発明の一実施の形態の構造化文書格納装置１における検索の具体例について説明する。
【０１１０】
図１５は、本発明の一実施の形態の構造化文書格納装置１内のＸＱｕｅｒｙ解析部１０４に入力される検索クエリの一例を示す。図１５に示す検索クエリ１５は、ＸＭＬ文書例７が格納されていることを前提としており、ノード値が「Ａｕｔｈｏｒ １」に一致するテキストノードを子孫に含む「ｂｏｏｋ」要素を検索するときのものである。
【０１１１】
図１６は、ＸＱｕｅｒｙ解析部１０４により生成される検索手順リストの一例を示す。この検索手順リスト１６は、検索クエリ１５を解析して生成されたものであり、子孫ノード検索、ノード型検索、ノード値検索、先祖ノード検索、ノード型検索、ノード名検索の順からなる６つの検索手順を示す。
【０１１２】
図１７は、本発明の一実施の形態の構造化文書格納装置１の検索部１０５の検索処理におけるコンテクストノードリストの遷移の例を示す。この例は、図１６に示した検索手順リスト１６を用いてテキストノードの検索処理を行ったときのコンテクストノードリストの遷移を示したものである。
【０１１３】
すなわち、図１７に１７０で示すように、コンテクストノードリストは、最初は図８に示したノードテーブル例８のｉｄ列の欄の一行目に示されるルートノードのノードＩＤ＝１のみを含む。
【０１１４】
次に、検索部１０５は図１６に示した検索手順１の子孫ノード検索を実行する。これにより、図１７に１７０で示すように、コンテクストノードリストには、図８に示したノードテーブル例８における子孫ノードのノードＩＤである「２」、「３」、「４」、「５」、「６」、「７」、「８」、「９」、「１０」、「１１」、「１２」、「１３」、「１４」、「１５」、「１６」、「１７」、「１８」、「１９」、「２０」が記述される。
【０１１５】
続いて、検索部１０５は図１６に示した検索手順２の引数３のノード型検索を実行する。これにより、図１７に１７１で示すように、コンテクストノードリストには、図８に示したノードテーブル例８において、引数３からｔｙｐｅ値が「３」のテキストノードのノード型を示すノードＩＤである「６」、「８」、「１２」、「１４」、「１８」、「２０」が記述される。
【０１１６】
続いて、検索部１０５は図１６に示した検索手順３の引数「Ａｕｔｈｏｒ１」のノード値検索を実行する。これにより、図１７に１７３で示すように、コンテクストノードリストには、図８に示したノードテーブル例８において、引数「Ａｕｔｈｏｒ１」からノード値を示す「ｖａｌｕｅ」が「Ａｕｔｈｏｒ１」である「８」、「２０」が記述される。
【０１１７】
続いて、検索部１０５は図１６に示した検索手順４の先祖ノード検索を実行する。これにより、図１７に１７４で示すように、コンテクストノードリストには、検索手順３の検索結果であるノードＩＤ「８」、「２０」のうちノードＩＤ「８」の先祖ノードである「１」、「２」、「３」、「７」と、ノードＤ「２０」の先祖ノードである「１５」、「１９」とが記述される。
【０１１８】
続いて、検索部１０５は図１６に示した検索手順５の引数１のノード型検索を実行する。これにより、図１７に１７５で示すように、コンテクストノードリストには、検索手順４の検索結果のうち、図８に示す引数１（ｔｙｐｅ値が「１」）のテキストノードのノード型を示すノードＩＤである「２」、「３」、「７」、「１５」、「１９」が記述される。
【０１１９】
そして、検索部１０５は図１６に示した最後の検索手順６の引数「ｂｏｏｋ」のノード名検索を実行する。これにより、図１７に１７６で示すように、コンテクストノードリストには、検索手順５の検索結果のうち、図８のｎａｍｅ列の欄に示されるノード名が「ｂｏｏｋ」である検索結果のノードＩＤ「３」、「１５」が記述される。このように、検索部１０５が検索手順を１つずつ実行する毎に、コンテクストノードリストに含まれるノードＩＤが変化していき、最終的に検索クエリによる所望の検索結果が得られる。
【０１２０】
図１８は、本発明の一実施の形態の構造化文書格納装置１のＸＭＬ成形部１０６から出力される検索結果の一例を示す。この検索結果は、図１５に示した検索クエリ１５に基づいて得られる図１７に示す検索結果を示したものである。
【０１２１】
すなわち、図１８の１行目から４行目は、図７に示したＸＭＬ文書例７において図１７の検索結果のノードＩＤ「３」が示すノード名「ｂｏｏｋ」を開始タグとし、その後の最初の「／ｂｏｏｋ」を終了タグとするノード値が「Ａｕｔｈｏｒ １」に一致するテキストノードを示す。また、図１８の５行目から８行目は、図７に示したＸＭＬ文書例７において図１７の検索結果のノードＩＤ「１５」が示すノード名「ｂｏｏｋ」を開始タグとし、その後の最初の「／ｂｏｏｋ」を終了タグとするノード値が「Ａｕｔｈｏｒ １」に一致するテキストノードを示す。
【０１２２】
このように、本実施の形態の構造化文書格納装置１によれば、構造化文書の対象ノードの出現順を示す順番号と、対象ノードより後に出現するノードのうち、対象ノードの子孫ノードを除くノードのうちで最も先に出現するノードの順番号を示す次番号とをノードテーブル２に格納し、検索部１０５において、ノードテーブル２を参照して構造化文書の比較元ノードの順番号を比較先ノードの順番号及び次番号と比較して比較元ノードが比較先ノードの子孫ノードであるか否かを判定するようにしたため、検索手順の数は従来と同じであるが、従来に比べて構造化文書のノード間の先祖・子孫関係を検索する手順を短時間で行うことができ、その結果、従来に比べて構造化文書の検索を高速に行うことができる。
【０１２３】
なお、本発明は以上の実施の形態に限定されるものではなく、例えば本実施の形態の構造化文書格納装置１において、ＸＭＬ文書をテキストデータとして入力し格納しているが、ＸＭＬ文書の入力方法はテキストデータによるものに限定されない。ＸＭＬ文書の入力方法を、ＤＯＭデータによるものや、その他の方法によるものとしてもよい。また、本実施の形態の構造化文書格納装置１において、検索結果をテキストデータとして出力しているが、検索結果の出力方法はテキストデータによるものに限定されない。検索結果の出力方法を、ＤＯＭデータによるものや、その他の方法によるものとしてもよい。
【０１２４】
また、本実施の形態の構造化文書格納装置１は、出現順が定義されない属性を含むＸＭＬ文書を格納するものであるが、全てのノードの出現順が定義される構造化文書を格納するものとしてもよい。この場合、格納部１０２には、属性データ挿入手段１０２ｄと属性格納手段１０２ｅとが不要となる。
【０１２５】
また、ノードテーブル２におけるｏｒｄｅｒ列２０４に格納される順番号は、ノードの出現順に「０」から始まり「１」ずつ増加する整数を割り振った値としてもよい。また、ノードに属性がない場合は図５のノード格納処理におけるステップＳ５０６乃至ステップＳ５１０が不要となる。また、図１２の子孫ノード検索処理のステップＳ１２０２において、ｏｒｄｅｒ列２０４の値に「１」を加算する処理が不要となる。
【０１２６】
更に、本発明は上述した構造化文書格納装置１の動作を実現する構造化文書格納方法、及びコンピュータにより構造化文書格納装置１の動作を実行させるための構造化文書格納プログラムも包含する。この構造化文書格納プログラムは、例えば、構造化文書格納プログラムが記憶された記録媒体から読み出され、コンピュータに取り込まれて実行されることにより構造化文書格納装置を構成するようにしてもよいし、通信ネットワークを介して配信されてコンピュータにインストールされて実行されることにより構造化文書格納装置を構成するようにしてもよい。
【符号の説明】
【０１２７】
１  構造化文書格納装置
２  ノードテーブル
３  ノード型一覧
７  ＸＭＬ文書例
８  ノードテーブル例
９  検索手順一覧
１０１  ＸＭＬ解析部
１０２  格納部
１０２ａ  ノードＩＤ決定手段
１０２ｂ  順番号決定手段
１０２ｃ  ノードデータ挿入手段
１０２ｄ  属性データ挿入手段
１０２ｅ  属性格納手段
１０２ｆ  子ノード格納手段
１０３  リレーショナルデータベース
１０４  ＸＱｕｅｒｙ解析部
１０５  検索部
１０５ａ  検索制御手段
１０５ｂ  ノード型検索手段
１０５ｃ  ノード名検索手段
１０５ｄ  ノード値検索手段
１０５ｅ  子ノード検索手段
１０５ｆ  親ノード検索手段
１０５ｇ  子孫ノード検索手段
１０５ｈ  先祖ノード検索手段
１０５ｉ  サブツリーデータ抽出手段
１０６  ＸＭＬ成形部
【図１】
2012073706.tif 000003
【図２】
2012073706.tif 000004
【図３】
2012073706.tif 000005
【図４】
2012073706.tif 000006
【図５】
2012073706.tif 000007
【図６】
2012073706.tif 000008
【図７】
2012073706.tif 000009
【図８】
2012073706.tif 000010
【図９】
2012073706.tif 000011
【図１０】
2012073706.tif 000012
【図１１】
2012073706.tif 000013
【図１２】
2012073706.tif 000014
【図１３】
2012073706.tif 000015
【図１４】
2012073706.tif 000016
【図１５】
2012073706.tif 000017
【図１６】
2012073706.tif 000018
【図１７】
2012073706.tif 000019
【図１８】
2012073706.tif 000020