JP5347965B2

JP5347965B2 - Ｘｍｌデータ処理システム、該システムに用いられるデータ処理方法及びｘｍｌデータ処理制御プログラム

Info

Publication number: JP5347965B2
Application number: JP2009531159A
Authority: JP
Inventors: 純平上村; 岳彦柏木
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 2007-09-07
Filing date: 2008-07-23
Publication date: 2013-11-20
Anticipated expiration: 2028-07-23
Also published as: JPWO2009031370A1; US20100250551A1; US8549009B2; WO2009031370A1

Description

本発明は、ＸＭＬデータ処理システム、該システムに用いられるデータ処理方法及びＸＭＬデータ処理制御プログラムに係り、特に、入力されたＸＭＬ（eXtensible Markup Language）データに対して、ＸＭＬデータの一部を特定するためのＸＰａｔｈ式で指定された部分を抽出する処理を高速で行う必要がある場合に用いて好適なＸＭＬデータ処理システム、該システムに用いられるデータ処理方法及びＸＭＬデータ処理制御プログラムに関する。

ＸＭＬ（eXtensible Markup Language）は、１９９８年にＷ３Ｃ（World Wide Web Consortium）によって勧告されて以来普及し、標準的な計算機間のデータ交換フォーマットとなっている。２００７年１月にＸＱｕｅｒｙが勧告されるなど、周辺の環境も整ってきている。ＸＭＬデータ（ＸＭＬ文書）は、ＸＭＬに準拠して作られた言語を用いて作成された文書やデータであり、要素や属性等のノードによって木構造が構成されるように記述される。

ＸＭＬデータは、たとえば、下記のように記述される。
［（ＸＭＬ宣言）］
１ <books>
１．１ <book>
１．１．１ <author>author_name1</author>
１．１．２ <title>title1</title>
１．１．３ <price>100</price>
</book>
１．２ <book>
１．２．１ <author>author_name2</author>
１．２．２ <title>title2</title2>
</book>
</books>
ノードの一つである要素は、開始タグ、コンテンツ、終了タグで構成される。たとえば、“<price>100</price>”は要素である。“<price>”は開始タグである。“100”はコンテンツである。”</price>”は終了タグである。要素は他の要素を含むことができる。ＸＰａｔｈは、ＸＭＬデータの特定部位を示す言語構文である。ＸＰａｔｈは、ＸＱｕｅｒｙ、ＸＳＬＴ（XSL Transformations：ＸＭＬファイルの間でデータの変換作業を行うための規格）といったＸＭＬデータに対する操作において重要な構成要素となっている。ＸＰａｔｈ式は、ＸＰａｔｈの仕様に従って作られた実際の式である。たとえば、“//books//book”や“//books/book”はＸＰａｔｈ式である。ＸＰａｔｈ式において、“//”は、ＸＭＬデータの木構造を構成する各要素を親子関係に見立てた場合の“子孫”を表す。また、“/”は“子”を表す。なお、上記ＸＭＬデータの左端の数字は、当該ＸＭＬデータを構成する各要素ノードの識別子（ノードＩＤ、ｎＩＤ）を表しており、説明のために付加したもので、実際のＸＭＬデータには含まれない。この例では、子要素の識別子は、親要素の識別子に“．”を付けたものに兄弟の順番を表す数字が付加されて作成されている。これにより、各識別子に基づいて先祖子孫関係が識別可能である。

ＸＭＬデータの中から、所定のＸＰａｔｈ式で特定されるＸＭＬノードを抽出する処理の方法がいくつか知られている。たとえば、ＸＭＬデータ木を探索する方法や、N.Koudas J.M.Patel S. Al-Khalifa,H.V.Jagadish,D.Srivastava, and Yuqing Wu.Structural Joins:A Primitive for Efficient XML Query Pattern Matching.In ICDE,2002.などに記載された構造ジョインを用いる方法や、江田毅晴、鬼塚真、山室雅司、ＸＭＬデータの要約情報を用いた高速なＸＰａｔｈ処理方法、電子情報通信学会論文誌Ｄ、2006、第J89-D 巻、p.139-150などに記載されたこれらの方法を組み合わせる（ハイブリッド）方法が知られている。

上記いずれの方法を用いても、上記のＸＭＬデータに対して、たとえば、ＸＰａｔｈ式“//books//book”が与えられた場合には、要素ノードの識別子の集合｛１．１，１．２｝を抽出することができる。

たとえば、ＸＭＬデータ木を探索する方法では、ＸＭＬデータ木のノードをたどりながら、ＸＰａｔｈ式のパターン“//books//book”とマッチングする構造を探索する。この場合、ＸＰａｔｈ式から生成したオートマトンを用いて、探索対象のＸＭＬデータを構成する各ノードをたどりながら目的となるノードを探す。これにより、識別子集合｛１．１，１．２｝が得られる。また、構造ジョインを用いる方法では、ＸＭＬデータを要素ノード単位で取得し、先祖子孫関係を要素ノードに付けられたラベルを用いて判定する。すなわち、ＸＰａｔｈ式（“//books//book”）をパターン“//books”とパターン“//book”とに分解し、同パターン“//books”に対する識別子の集合｛１｝を得て、また、同パターン“//book”に対して、識別子集合｛１．１，１．２｝を得る。そして、これらの識別子集合間で先祖子孫関係のあるものを探す。この例では、“１→１．１”及び“１→１．２”という親子関係があるので、識別子集合｛１．１，１．２｝が得られる。また、これらの方法を組み合わせる方法では、述語の部分でのみ構造ジョインをすることで、構造ジョインの回数を削減している。

しかしながら、ＸＭＬデータ木を探索する方法では、全ての枝を探索する必要があるため、ＸＭＬデータの量に対するスケーラビリティがない。つまり、ＸＭＬデータを構成するノードの数が増大するにつれ、処理時間が幾何級数的に増大する。また、構造ジョインを用いる方法では、ＸＭＬデータが増加した場合に、ノードの識別子の集合の要素数が増加するため、やはり、それら全ての先祖子孫関係を判定するための時間が幾何級数的に増大する。また、これらの方法を組み合わせる方法は、述語の部分でのみ構造ジョインが行われ、構造ジョインの回数が削減されるものであり、この発明とは異なる方法で効果を得るものである。

本発明は、上述の事情に鑑みてなされたもので、入力されたＸＭＬデータに対して、ＸＰａｔｈ式で指定された部分を抽出する処理を高速で行うことができるＸＭＬデータ処理システム、該システムに用いられるデータ処理方法及びＸＭＬデータ処理制御プログラムを提供することを目的とする。

上記課題を解決するために、本発明は、入力された第１のＸＭＬデータに対して、該第１のＸＭＬデータの一部を特定するためのＸＰａｔｈ式に適合する部分の抽出処理を行うＸＭＬデータ処理システムに係り、前記第１のＸＭＬデータを解析してノード単位に分解し、各ノード毎にノード識別子を付与して第２のＸＭＬデータを作成すると共に、該第２のＸＭＬデータに対して前記ノード識別子を前記ＸＰａｔｈ式に基づいて指定するための索引を作成するＸＭＬ解析部と、該ＸＭＬ解析部で作成された前記第２のＸＭＬデータを保持するＸＭＬデータ保持部と、前記ＸＭＬ解析部で作成された前記索引を保持する索引部と、該索引部で保持されている前記索引を用いて前記ＸＰａｔｈ式に対応した前記ノード識別子を取得し、前記ＸＭＬデータ保持部にアクセスして該ノード識別子に対応した前記第２のＸＭＬデータを取得するＸＰａｔｈ式処理部とを有している。

本発明の構成によれば、ＸＭＬ解析部で第１のＸＭＬデータが解析されてノード単位に分解され、各ノード毎にノード識別子が付与されて第２のＸＭＬデータが作成されると共に、この第２のＸＭＬデータに対してノード識別子をＸＰａｔｈ式に基づいて指定するための索引が作成され、ＸＭＬデータ保持部で第２のＸＭＬデータが保持されると共に、索引部でその索引が保持され、ＸＰａｔｈ式処理部では、索引を用いてＸＰａｔｈ式に対応したノード識別子が取得され、保持されている第２のＸＭＬデータからそのノード識別子に対応したＸＭＬデータが取得される。これにより、全ＸＭＬデータの探索や、構造ジョインを用いる場合での多数のノード間の先祖子孫関係の判定を行う必要がなくなり、第１のＸＭＬデータに対して、ＸＰａｔｈ式に適合する部分の抽出処理を高速に行うことができる。

本発明の第１の実施例であるＸＭＬデータ処理システムの要部の電気的構成を示すブロック図である。図１に示したＸＭＬ解析部にて作成されたＸＭＬデータの例を示す図である。図１に示したパステーブルを示す図である。図１に示したパス識別子集合テーブルを示す図である。図１に示したノードリストを示す図である。図１に示したＸＭＬデータ処理システムの動作を説明するフローチャートである。図１に示したパス識別子テーブルにおいて、パス識別子の集合に含むパス識別子を絶対パスのパス識別子に限ったものを示す図である。

ＸＭＬ解析部により作成される索引が、第２のＸＭＬデータに含まれる全て又は一部のパスのテキスト表現を、各パス識別子を付与して保持するパステーブルと、このパステーブルに保持されている各パスに包含されるパスに付与されたパス識別子の集合を各パス識別子毎に保持するパス識別子集合テーブルと、パステーブルに保持されている各パスのうちのフルパスに対応するパス識別子を、第２のＸＭＬデータ中の当該フルパスを構成するノードの最終のノード識別子を対応付けて保持するノードリストとから構成されているＸＭＬデータ処理システム、該システムに用いられるデータ処理方法及びＸＭＬデータ処理制御プログラムを提供する。

また、ＸＰａｔｈ式処理部は、ＸＰａｔｈ式に含まれるパスのテキスト表現を第１のキーとしてパステーブルを検索して第１のキーに対応する第１のパス識別子を取得し、第１のパス識別子を第２のキーとしてパス識別子集合テーブルを検索して第２のキーに対応するパス識別子集合を取得し、取得したパス識別子集合の中で共通する共通パス識別子を取得し、取得した共通パス識別子を第３のキーとしてパステーブルを検索して第３のキーに対応するパスを取得し、取得した第３のキーに対応するパスのテキスト表現中のタグの出現順序がＸＰａｔｈ式に含まれるパスのテキスト表現中のタグの出現順序と一致するとき、取得した第３のキーに対応するパスに対応する第２のパス識別子をパステーブルから取得し、ノードリストから第２のパス識別子に対応する最終のノード識別子を取得し、かつ、ＸＭＬデータ保持部から、最終のノード識別子が付与されたノードで構成されるフルパスに対応する第２のＸＭＬデータを取得する構成とされている。

また、ＸＰａｔｈ式処理部は、ＸＰａｔｈ式中のパスに全ての子要素を示す記号が含まれているとき、全ての子要素を示す記号を除去して第１のキーとする構成とされている。

また、ＸＰａｔｈ式処理部は、ＸＰａｔｈ式中のパスに全ての子要素を示す記号が含まれているとき、全ての子要素を示す記号を除去せずに当該パスを第１のキーとする構成とされ、パステーブルは、全ての子要素を示す記号が含まれているパスを、当該パステーブルに保持されているテキスト表現のうちの当該パスと共通のテキスト表現を有するパスに変換する構成とされている。

また、ノードリストは、ＸＰａｔｈ式処理部で取得された第３のキーに対応するパスのテキスト表現中のタグの出現順序がＸＰａｔｈ式に含まれるパスのテキスト表現中のタグの出現順序と一致するとき、取得した第３のキーに対応するパスに対応する第２のパス識別子をパステーブルから取得し、ＸＰａｔｈ式処理部と並行して、当該ノードリストから第２のパス識別子に対応する最終のノード識別子を取得する構成とされている。

図１は、本発明の第１の実施例であるＸＭＬデータ処理システムの要部の電気的構成を示すブロック図である。

本実施例のＸＭＬデータ処理システム１０は、たとえばパーソナルコンピュータなどの情報処理装置で構成され、図１に示すように、ＸＭＬデータ処理システム１０全体を制御するコンピュータとしてのＣＰＵ（中央処理装置）１０ａと、ＣＰＵ１０ａを動作させるためのＸＭＬデータ処理制御プログラムが記録されたＲＯＭ（リード・オンリ・メモリ）１０ｂとを有している。特に、本実施例では、ＸＭＬデータ処理システム１０は、ＸＭＬ解析部１１と、ストレージ部１２と、索引部１３と、ＸＰａｔｈ式処理部１４とを備え、入力されたＸＭＬデータｉｎａ（第１のＸＭＬデータ）に対して、ＸＭＬデータｉｎａの一部を特定するためのＸＰａｔｈ式Ｆに適合する部分の抽出処理を行う。

ＸＭＬ解析部１１は、ＸＭＬデータｉｎａを解析してノード単位に分解し、ＸＭＬデータｉｎａを構成する各文書毎にユニークな文書名、及び各ノード毎にユニークなノード識別子を付与してＸＭＬデータｉｎｂ（第２のＸＭＬデータ）を作成すると共に、作成したＸＭＬデータｉｎｂに対してノード識別子をＸＰａｔｈ式Ｆに基づいて指定するための索引ｉｘを作成する。ストレージ部１２は、ＸＭＬ解析部１１で作成されたＸＭＬデータｉｎｂを保持すると共に、ＸＰａｔｈ式処理部１４からの取得要求ｑに対して文書単位又はノード単位でＸＭＬデータｃを提供する。索引部１３は、ＸＭＬ解析部１１で作成された索引ｉｘを保持する。

索引ｉｘは、パステーブル１３ａ、パス識別子集合テーブル１３ｂ及びノードリスト１３ｃから構成されている。パステーブル１３ａは、ＸＭＬデータｉｎｂに含まれる全て又は一部のパスのテキスト表現を、各パス識別子を付与して保持すると共に、ＸＰａｔｈ式処理部１４からのパスのテキスト表現をキーとした問い合わせに対して、対応するパス識別子を返答する。パス識別子集合テーブル１３ｂは、パステーブル１３ａに保持されている各パスを包含するパスに付与されたパス識別子の集合を、各パス識別子毎に保持すると共に、ＸＰａｔｈ式処理部１４からのパス識別子をキーとした問い合わせに対して、パス識別子に対応するパス識別子の集合を返答する。ノードリスト１３ｃは、パステーブル１３ａに保持されている上記各パスのうちのフルパスに対応するパス識別子を、ＸＭＬデータｉｎｂ中の当該フルパスを構成するノードの最終のノード識別子を対応付けて保持する。

ＸＰａｔｈ式処理部１４は、索引部１３で保持されている索引ｉｘを用いてＸＰａｔｈ式Ｆに対応したノード識別子を取得し、ストレージ部１２に取得要求ｑを送出（アクセス）してノード識別子に対応したＸＭＬデータｉｎｃを取得する。特に、本実施例では、ＸＰａｔｈ式処理部１４は、ＸＰａｔｈ式Ｆに含まれるパスのテキスト表現を第１のキーとしてパステーブル１３ａを検索して第１のキーに対応する第１のパス識別子を取得し、取得した第１のパス識別子を第２のキーとしてパス識別子集合テーブル１３ｂを検索して第２のキーに対応するパス識別子集合を取得する。

また、ＸＰａｔｈ式処理部１４は、取得したパス識別子集合の中で共通する共通パス識別子を取得し、取得した共通パス識別子を第３のキーとしてパステーブル１３ａを検索して第３のキーに対応するパスを取得し、取得した第３のキーに対応するパスのテキスト表現中のタグの出現順序がＸＰａｔｈ式Ｆに含まれるパスのテキスト表現中のタグの出現順序と一致するとき、取得した第３のキーに対応するパスに対応する第２のパス識別子をパステーブル１３ａから取得する。また、ＸＰａｔｈ式処理部１４は、ノードリスト１３ｃから第２のパス識別子に対応する最終のノード識別子を取得し、かつ、ストレージ部１２から、最終のノード識別子が付与されたノードで構成されるフルパスに対応するＸＭＬデータｉｎｃを取得する。また、ＸＰａｔｈ式処理部１４は、ＸＰａｔｈ式Ｆ中のパスに全ての子要素を示す記号が含まれているとき、全ての子要素を示す記号を除去して第１のキーとする。

図２は、図１に示したＸＭＬ解析部１１にて作成されたＸＭＬデータｉｎｂの例を示す図、図３は、図１に示したパステーブル１３ａを示す図、図４は、図１に示したパス識別子集合テーブル１３ｂを示す図、図５は、図１に示したノードリスト１３ｃを示す図、図６は、図１に示したＸＭＬデータ処理システム１０の動作を説明するフローチャートである。

これらの図を参照して、図１に示したＸＭＬデータ処理システム１０に用いられるデータ処理方法の処理内容について説明する。

このＸＭＬデータ処理システム１０では、図６に示すように、ＸＭＬ解析部１１でＸＭＬデータｉｎａが解析されてノード単位に分解され、各ノード毎にユニークなノード識別子が付与されてＸＭＬデータｉｎｂが作成されると共に、作成されたＸＭＬデータｉｎｂに対してノード識別子をＸＰａｔｈ式Ｆに基づいて指定するための索引ｉｘが作成される（ステップＡ１、ＸＭＬ解析処理）。そして、ストレージ部１２でＸＭＬデータｉｎｂが保持されると共に（ステップＡ２、ＸＭＬデータ保持処理）、索引部１３で索引ｉｘが保持される（ステップＡ３、索引保持処理）。ＸＰａｔｈ式処理部１４では、索引保持処理で保持された索引ｉｘを用いてＸＰａｔｈ式Ｆに対応したノード識別子が取得され、ＸＭＬデータ保持処理で保持されているＸＭＬデータｉｎｂからノード識別子に対応したＸＭＬデータｉｎｃが取得される（ステップＡ４、ＸＰａｔｈ式データ処理）。これにより、ＸＭＬデータｉｎａに対して、ＸＰａｔｈ式Ｆに適合する部分の抽出処理が行われる。

ＸＰａｔｈ式データ処理では、ＸＰａｔｈ式Ｆに含まれるパスのテキスト表現を第１のキーとしてパステーブル１３ａが検索されて第１のキーに対応する第１のパス識別子が取得され、第１のパス識別子を第２のキーとしてパス識別子集合テーブル１３ｂが検索されて第２のキーに対応するパス識別子集合が取得される。そして、取得されたパス識別子集合の中で共通する共通パス識別子が取得され、取得された共通パス識別子を第３のキーとしてパステーブル１３ａが検索されて第３のキーに対応するパスが取得される。

また、取得された第３のキーに対応するパスのテキスト表現中のタグの出現順序がＸＰａｔｈ式Ｆに含まれるパスのテキスト表現中のタグの出現順序と一致するとき、取得された第３のキーに対応するパスに対応する第２のパス識別子がパステーブル１３ａから取得され、ノードリスト１３ｃから第２のパス識別子に対応する最終のノード識別子が取得され、かつ、ストレージ部１２から、最終のノード識別子が付与されたノードで構成されるフルパスに対応するＸＭＬデータｉｎｃが取得される。また、ＸＰａｔｈ式データ処理では、ＸＰａｔｈ式Ｆ中のパスに全ての子要素を示す記号が含まれているとき、全ての子要素を示す記号が除去されて第１のキーとされる。

すなわち、入力されるＸＭＬデータｉｎａは、たとえば、次のような２つのＸＭＬデータ（[data1.xml]，[data2.xml]）で構成されている。

[data1.xml]
<a>
<b>
<c>test_data1</c>
</b>
</a>
及び、
[data2.xml]
<c>
<b>
<a>test_data2</a>
</b>
</c>
ＸＭＬデータｉｎａは、ＸＭＬ解析部１１によりノード単位に分解され、図２に示すように、各ノード毎にノード識別子（“１”，“２”，“３”，“４”，“５”，“６”）が付与された後、ＸＭＬデータｉｎｂとしてストレージ部１２へ格納される。また、ＸＭＬデータｉｎｂは、含まれる全て又は一部のパスがＸＭＬ解析部１１により抽出され、図３に示すように、各パス（ｐａｔｈ）のテキスト表現が、各パス識別子（ｐＩＤ）が付与されてパステーブル１３ａに保持される。また、ＸＭＬ解析部１１により、パステーブル１３ａに保持されている各パスを包含するパスが検出され、図４に示すように、これらのパスに付与されたパス識別子（ｐＩＤ）の集合（ｌｉｓｔ）が各パス識別子（ｐＩＤ）毎にパス識別子集合テーブル１３ｂに保持される。

また、ＸＭＬ解析部１１により、パステーブル１３ａに保持されている各パスのうちのフルパスに対応するパス識別子（ｐＩＤ）（“１”，“２”，“３”，“６”，“７”，“８”）が検出され、図５に示すように、各パス識別子（ｐＩＤ）に対して、ＸＭＬデータｉｎｂ中の当該フルパスを構成するノードの最終のノード識別子が対応付けられてノードリスト１３ｃに保持される。

ＸＰａｔｈ式処理部１４では、入力されるＸＰａｔｈ式Ｆに基づいて、たとえば、次のような処理１，２が行われる。

処理１；ＸＰａｔｈ式Ｆが、たとえば“//a//c”のとき
［ステップ１；パス分解］
まず、ＸＰａｔｈ式Ｆ“//a//c”が“//”で分解された後、分解されて得られた各パスの前後に“//”が付加され、要素“//a//”と要素“//c//”とが得られる。

［ステップ２；候補パスの絞込み］
索引部１３のパステーブル１３ａ（図３参照）が検索され、要素“//a//”及び要素“//c//”に対応する各パス識別子（ｐＩＤ）からなるパス識別子集合｛１，６｝が得られる。索引部１３のパス識別子集合テーブル１３ｂが検索され、パス識別子“１”，“６”に対応するリスト
ｌｉｓｔ（１）＝｛１，２，３，８，９｝、及び、
ｌｉｓｔ（６）＝｛３，５，６，７，８｝
が得られる。そして、ｌｉｓｔ（１）とｌｉｓｔ（６）との共通部分（共通パス識別子）
ｌｉｓｔ（１）∧ｌｉｓｔ（６）＝｛３，８｝
が求められ、索引部１３のパステーブル１３ａが検索され、パス識別子ｐＩＤが｛３，８｝に対応するパス“//a/b/c//”，“//c/b/a//”が候補パスとして得られる。

［ステップ３；候補パスの検証］
上記で得られた候補パスをフルパス表現としてみなしたもの（“/a/b/c”，“/c/b/a”）が、ＸＰａｔｈ式Ｆ“//a//c”に適合するか否かが判定される。この場合、パス“a/b/c”は、タグの出現順序がＸＰａｔｈ式Ｆ“//a//c”と一致するため、目的のパス識別子が“３”と判定される。

［ステップ４；目的のノード識別子の取得］
パス識別子が“３”である索引部１３のノードリスト１３ｃ中の“ｎｃ３”に含まれるノード識別子“３”が、ＸＰａｔｈ式Ｆ“//a//c”に適合するノード識別子となる。

［ステップ５；目的ノードの取得］
ＸＰａｔｈ式処理部１４からストレージ部１２に取得要求ｑが送出され、ノード識別子“３”に対応するノードが取得される。

処理２；ＸＰａｔｈ式Ｆに、たとえば“//c/*//a”のように、パスに全ての子要素を示す記号（*）が含まれているとき
［ステップ１；パス分解］
まず、ＸＰａｔｈ式Ｆ“//c/*//a”が“//”で分解された後、分解されて得られた各パスの前後に“//”が付加され、要素“//c/*//”と要素“//a//”とが得られる。そして、要素“//c/*//”中の“/*”が除去され、要素“//c//”と要素“//a//”とが得られる。

［ステップ２；候補パスの絞込み］
索引部１３のパステーブル１３ａ（図３参照）が検索され、要素“//a//”及び要素“//c//”に対応する各パス識別子からなるパス識別子集合｛１，６｝が得られる。索引部１３のパス識別子集合テーブル１３ｂが検索され、パス識別子“１”，“６”に対応するリスト
ｌｉｓｔ（１）＝｛１，２，３，８，９｝、及び、
ｌｉｓｔ（６）＝｛３，５，６，７，８｝
が得られる。そして、ｌｉｓｔ（１）とｌｉｓｔ（６）との共通部分（共通パス識別子）
ｌｉｓｔ（１）∧ｌｉｓｔ（６）＝｛３，８｝
が求められる。索引部１３のパステーブル１３ａが検索され、パス識別子ｐＩＤが｛３，８｝に対応するパス“//a/b/c//”，“//c/b/a//”が候補パスとして得られる。

［ステップ３；候補パスの検証］
上記で得られた候補パスをフルパス表現としてみなしたもの（“/a/b/c”，“/c/b/a”）が、ＸＰａｔｈ式Ｆ“//c/*//a”に適合するか否かが判定される。この場合、パス“c/b/a”は、タグの出現順序がＸＰａｔｈ式Ｆ“//c/*//a”と一致するため、目的のパス識別子ｐＩＤが“８”と判定される。

［ステップ４；目的のノード識別子の取得］
パス識別子ｐＩＤが“８”である索引部１３のノードリスト１３ｃ“ｎｃ８”に含まれるノード識別子“６”が、ＸＰａｔｈ式Ｆ“//c/*//a”に適合するノード識別子となる。

［ステップ５；目的ノードの取得］
ＸＰａｔｈ式処理部１４からストレージ部１２に取得要求ｑが送出され、ノード識別子“６”に対応するノードが取得される。

以上のように、この第１の実施例では、ＸＭＬ解析部１１でＸＭＬデータｉｎａが解析されてノード単位に分解され、各ノード毎にノード識別子が付与されてＸＭＬデータｉｎｂが作成されると共に、作成されたＸＭＬデータｉｎｂに対してノード識別子をＸＰａｔｈ式Ｆに基づいて指定するための索引ｉｘが作成され、ストレージ部１２でＸＭＬデータｉｎｂが保持されると共に、索引部１３で索引ｉｘが保持され、ＸＰａｔｈ式処理部１４では、索引ｉｘを用いてＸＰａｔｈ式Ｆに対応したノード識別子が取得され、保持されているＸＭＬデータｉｎｂからノード識別子に対応したＸＭＬデータｉｎｃが取得される。これにより、全ＸＭＬデータの探索や、構造ジョインを用いる場合での多数のノード間の先祖子孫関係の判定を行う必要がなくなり、ＸＭＬデータｉｎａに対して、ＸＰａｔｈ式Ｆに適合する部分の抽出処理が高速に行われる。

この発明の第２の実施例では、図１に示したＸＰａｔｈ式処理部１４は、ＸＰａｔｈ式Ｆ中のパスに全ての子要素を示す記号が含まれているとき、全ての子要素を示す記号を除去せずにパスを第１のキーとする構成とされている。また、パステーブル１３ａは、全ての子要素を示す記号が含まれているパスを、パステーブル１３ａに保持されているテキスト表現のうちの当該パスと共通のテキスト表現を有するパスに変換する構成とされている。

ＸＰａｔｈ式処理部１４では、入力されるＸＰａｔｈ式Ｆに基づいて、たとえば、次のような処理が行われる。

ＸＰａｔｈ式Ｆに、たとえば“//c/*//a”のように、パスに全ての子要素を示す記号（*）が含まれているとき
［ステップ１；パス分解]
まず、ＸＰａｔｈ式Ｆ“//c/*//a”が“//”で分解された後、分解されて得られた各パスの前後に“//”が付加され、要素“//c/*//”と要素“//a//”とが得られる。

［ステップ２；候補パスの絞込み]
索引部１３のパステーブル１３ａ（図３参照）が検索され、要素“//c/*//”と要素“//a//”に対応する各パス識別子（ｐＩＤ）からなるパス識別子集合｛１，７｝が得られる。この場合、パステーブル１３ａは、要素“//c/*//”に対して、共通のテキスト表現を有するパスのパス識別子｛７｝（パス“//c/b”）が得られるように作成されている。索引部１３のパス識別子集合テーブル１３ｂが検索され、パス識別子“１”，“７”に対応するリスト
ｌｉｓｔ（１）＝｛１，２，３，８，９｝、及び、
ｌｉｓｔ（７）＝｛７，８｝
が得られる。

そして、ｌｉｓｔ（１）とｌｉｓｔ（７）との共通部分（共通パス識別子）
ｌｉｓｔ（７）∧ｌｉｓｔ（１）＝｛８｝
が求められる。索引部１３のパステーブル１３ａが検索され、パス識別子ｐＩＤが｛８｝に対応するパス“//c/b/a//”が候補パスとして得られる。

［ステップ３；候補パスの検証]
上記で得られたパスをフルパス表現としてみなしたもの（“/c/b/a”）が、ＸＰａｔｈ式Ｆ“//c/*//a”に適合するか否かが判定される。この場合、パス“c/b/a ”は、タグの出現順序がＸＰａｔｈ式Ｆ“//c/*//a”と一致するため、目的のパス識別子ｐＩＤが“８”と判定される。

［ステップ４；目的のノード識別子の取得]
パス識別子ｐＩＤが“８”である索引部１３のノードリスト１３ｃ中の“ｎｃ８”に含まれるノード識別子“６”が、ＸＰａｔｈ式Ｆ“//c/*//a”に適合するノード識別子となる。

以上のように、この第２の実施例では、パステーブル１３ａが、全ての子要素を示す記号が含まれているパスを、パステーブル１３ａに保持されているテキスト表現のうちのそのパスと共通のテキスト表現を有するパスに変換する構成とされているので、ＸＰａｔｈ式Ｆ中のパスに全ての子要素を示す記号が含まれているときでも、全ての子要素を示す記号を除去せずに第１の実施例と同様の利点が得られる。

以上、この発明の実施例を図面により詳述してきたが、具体的な構成はこれら実施例に限られるものではなく、この発明の要旨を逸脱しない範囲の設計の変更などがあっても、この発明に含まれる。

たとえば、ノードリスト１３ｃは、ＸＰａｔｈ式処理部１４で取得された第３のキーに対応するパスのテキスト表現中のタグの出現順序がＸＰａｔｈ式Ｆに含まれるパスのテキスト表現中のタグの出現順序と一致するとき、取得した第３のキーに対応するパスに対応する第２のパス識別子をパステーブル１３ａから取得し、ＸＰａｔｈ式処理部１４と並行して、ノードリスト１３ｃから第２のパス識別子に対応する最終のノード識別子を取得するようにしても良い。この場合、上記各実施例の［ステップ３；候補パスの検証］は、ＸＰａｔｈ式処理部１４と並行して、［ステップ４；目的のノード識別子の取得] でノードリスト１３ｃで行われる。これにより、処理の並列化が行われ、候補パスが多く、検証に時間がかかる場合でも、高速処理が期待できる。

また、上記各実施例のステップ２（候補パスの絞込み）では、パス識別子集合テーブル１３ｂから取得した全てのリスト間で共通パス識別子を求める必要はなく、パス識別子の数が所定の閾値以下になったところで、ステップ３（候補パスの検証）へ移行しても良い。たとえば、パス識別子の数がある閾値以下のリストがある場合、リストをステップ３における入力としても良く、また、リストが複数ある場合は、パス識別子の数が最少のリストを用いる。また、ストレージ部１２は、ＸＰａｔｈ式処理部１４からの取得要求ｑに対応するのみではなく、データの更新及び削除など、一般的なデータベースが有する機能を備えていても良い。

また、索引部１３が備えるパス識別子集合テーブル１３ｂに関して、パス識別子（ｐＩＤ）の集合（ｌｉｓｔ）に含むパス識別子は絶対パス（ルート要素からのパス）のパス識別子に限ってもよい。

上記［ステップ２；候補パスの絞込み］において、絞込みの結果から、部分パスとしては存在するが絶対パスとして存在しないパスを除外することができる。

パス識別子（ｐＩＤ）の集合（ｌｉｓｔ）に含むパス識別子を絶対パス（ルート要素からのパス）のパス識別子に限ったパス識別子集合テーブルの内容を図７に示す。

以下、ＸＰａｔｈ式Ｆ“//b//c”が入力された場合で処理の差分を例に示す。

図４に示したパス識別子集合テーブルを用いた場合、上記［ステップ２；候補パスの絞込み］の結果は、ｌｉｓｔ（４）∧ｌｉｓｔ（６）＝｛３，５，７，８｝となり、これらが［ステップ３；候補パスの検証］の入力となる。

このうち、パス識別子が５のパス（/b/c）は、絶対パスとしては入力ＸＭＬデータ（data1.xml, data2.xml）中に存在しないためこの識別子は冗長である。

一方、図７に示したパス識別子テーブルを用いた場合では、［ステップ２；候補パスの絞込み］の結果は、ｌｉｓｔ（４）∧ｌｉｓｔ（６）＝｛３，７，８｝となり、図４に示したパス識別子集合テーブルを用いた場合に含まれていた不要なパス識別子５を除外することができ、この後のステップでパス識別子５に関連した処理を行わずに済むので高速処理が期待できる。

この発明は、ＸＭＬデータに対して、ＸＰａｔｈ式に適合する部分の抽出処理を行う場合全般に適用でき、特に、大量のＸＭＬデータを扱うＸＭＬデータベースを検索する場合に有効である。

以上、実施例を参照して本願発明を説明したが、本願発明は上記実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。

この出願は、２００７年９月７日に出願された日本出願特願２００７−２３３１５９を基礎とする優先権を主張し、その開示の全てをここに取り込む。

Claims

入力された第１のＸＭＬデータに対して、該第１のＸＭＬデータの一部を特定するためのＸＰａｔｈ式に適合する部分の抽出処理を行うＸＭＬデータ処理システムであって、
前記第１のＸＭＬデータを解析してノード単位に分解し、各ノード毎にノード識別子を付与して第２のＸＭＬデータを作成すると共に、該第２のＸＭＬデータに対して前記ノード識別子を前記ＸＰａｔｈ式に基づいて指定するための索引を作成するＸＭＬ解析部と、
該ＸＭＬ解析部で作成された前記第２のＸＭＬデータを保持するＸＭＬデータ保持部と、
前記ＸＭＬ解析部で作成された前記索引を保持する索引部と、
該索引部で保持されている前記索引を用いて前記ＸＰａｔｈ式に対応した前記ノード識別子を取得し、前記ＸＭＬデータ保持部にアクセスして該ノード識別子に対応した前記第２のＸＭＬデータを取得するＸＰａｔｈ式処理部とを有し、
前記ＸＭＬ解析部により作成される前記索引は、
前記第２のＸＭＬデータに含まれる全て又は一部のパスのテキスト表現を、各パス識別子を付与して保持するパステーブルと、
該パステーブルに保持されている前記各パスを包含するパスに付与された前記パス識別子の集合を、前記各パス識別子毎に保持するパス識別子集合テーブルと、
前記パステーブルに保持されている前記各パスのうちのフルパスに対応するパス識別子を、前記第２のＸＭＬデータ中の当該フルパスを構成するノードの最終の前記ノード識別子を対応付けて保持するノードリストとから構成され、
前記ＸＰａｔｈ式処理部は、前記ＸＰａｔｈ式に含まれるパスのテキスト表現を第１のキーとして前記パステーブルを検索して該第１のキーに対応する第１のパス識別子を取得し、該第１のパス識別子を第２のキーとして前記パス識別子集合テーブルを検索して該第２のキーに対応するパス識別子集合を取得し、取得した前記パス識別子集合の中で共通する共通パス識別子を取得し、取得した前記共通パス識別子を第３のキーとして前記パステーブルを検索して該第３のキーに対応するパスを取得し、取得した前記第３のキーに対応するパスのテキスト表現中のタグの出現順序が前記ＸＰａｔｈ式に含まれるパスのテキスト表現中のタグの出現順序と一致するとき、取得した前記第３のキーに対応するパスに対応する第２のパス識別子を前記パステーブルから取得し、前記ノードリストから該第２のパス識別子に対応する前記最終のノード識別子を取得し、かつ、前記ＸＭＬデータ保持部から、前記最終のノード識別子が付与されたノードで構成されるフルパスに対応する前記第２のＸＭＬデータを取得するＸＭＬデータ処理システム。
請求項１に記載のＸＭＬデータ処理システムにおいて、
前記ＸＰａｔｈ式処理部は、前記ＸＰａｔｈ式中の前記パスに全ての子要素を示す記号が含まれているとき、該全ての子要素を示す記号を除去して前記第１のキーとするＸＭＬデータ処理システム。
請求項１に記載のＸＭＬデータ処理システムにおいて、
前記ＸＰａｔｈ式処理部は、前記ＸＰａｔｈ式中のパスに全ての子要素を示す記号が含まれているとき、該全ての子要素を示す記号を除去せずに当該パスを前記第１のキーとし、
前記パステーブルは、前記全ての子要素を示す記号が含まれている前記パスを、当該パステーブルに保持されているテキスト表現のうちの当該パスと共通のテキスト表現を有するパスに変換するＸＭＬデータ処理システム。
請求項１乃至３のいずれか１項に記載のＸＭＬデータ処理システムにおいて、
前記ノードリストは、前記ＸＰａｔｈ式処理部で取得された前記第３のキーに対応するパスのテキスト表現中のタグの出現順序が前記ＸＰａｔｈ式に含まれるパスのテキスト表現中のタグの出現順序と一致するとき、取得した前記第３のキーに対応するパスに対応する前記第２のパス識別子を前記パステーブルから取得し、前記ＸＰａｔｈ式処理部と並行して、当該ノードリストから該第２のパス識別子に対応する前記最終のノード識別子を取得するＸＭＬデータ処理システム。
ＸＭＬ解析部と、ＸＭＬデータ保持部と、索引部と、ＸＰａｔｈ式処理部とを具備し、入力された第１のＸＭＬデータに対して、該第１のＸＭＬデータの一部を特定するためのＸＰａｔｈ式に適合する部分の抽出処理を行うＸＭＬデータ処理システムに用いられるデータ処理方法であって、
前記ＸＭＬ解析部が、前記第１のＸＭＬデータを解析してノード単位に分解し、各ノード毎にノード識別子を付与して第２のＸＭＬデータを作成すると共に、該第２のＸＭＬデータに対して前記ノード識別子を前記ＸＰａｔｈ式に基づいて指定するための索引を作成するＸＭＬ解析処理と、
前記ＸＭＬデータ保持部が、該ＸＭＬ解析処理で作成された前記第２のＸＭＬデータを保持するＸＭＬデータ保持処理と、
前記索引部が、前記ＸＭＬ解析処理で作成された前記索引を保持する索引保持処理と、
前記ＸＰａｔｈ式処理部が、該索引保持処理で保持された前記索引を用いて前記ＸＰａｔｈ式に対応した前記ノード識別子を取得し、前記ＸＭＬデータ保持処理で保持されている前記第２のＸＭＬデータから該ノード識別子に対応した第２のＸＭＬデータを取得するＸＰａｔｈ式データ処理とを行い、
前記ＸＭＬ解析処理により前記索引部が作成する前記索引は、
前記第２のＸＭＬデータに含まれる全て又は一部のパスのテキスト表現を、各パス識別子を付与して保持するパステーブルと、
該パステーブルに保持されている前記各パスを包含するパスに付与された前記パス識別子の集合を、前記各パス識別子毎に保持するパス識別子集合テーブルと、
前記パステーブルに保持されている前記各パスのうちのフルパスに対応するパス識別子を、前記第２のＸＭＬデータ中の当該フルパスを構成するノードの最終の前記ノード識別子を対応付けて保持するノードリストとから構成され、
前記ＸＰａｔｈ式データ処理では、前記ＸＰａｔｈ式処理部が、前記ＸＰａｔｈ式に含まれるパスのテキスト表現を第１のキーとして前記パステーブルを検索して該第１のキーに対応する第１のパス識別子を取得し、該第１のパス識別子を第２のキーとして前記パス識別子集合テーブルを検索して該第２のキーに対応するパス識別子集合を取得し、取得した前記パス識別子集合の中で共通する共通パス識別子を取得し、取得した前記共通パス識別子を第３のキーとして前記パステーブルを検索して該第３のキーに対応するパスを取得し、取得した前記第３のキーに対応するパスのテキスト表現中のタグの出現順序が前記ＸＰａｔｈ式に含まれるパスのテキスト表現中のタグの出現順序と一致するとき、取得した前記第３のキーに対応するパスに対応する第２のパス識別子を前記パステーブルから取得し、前記ノードリストから該第２のパス識別子に対応する前記最終のノード識別子を取得し、かつ、前記ＸＭＬデータ保持部から、前記最終のノード識別子が付与されたノードで構成されるフルパスに対応する前記第２のＸＭＬデータを取得するデータ処理方法。
請求項５に記載のデータ処理方法において、
前記ＸＰａｔｈ式データ処理では、前記ＸＰａｔｈ式中の前記パスに全ての子要素を示す記号が含まれているとき、前記ＸＰａｔｈ式処理部が、該全ての子要素を示す記号を除去して前記第１のキーとするデータ処理方法。
請求項５に記載のデータ処理方法において、
前記ＸＰａｔｈ式データ処理では、前記ＸＰａｔｈ式中のパスに全ての子要素を示す記号が含まれているとき、前記ＸＰａｔｈ式処理部が、該全ての子要素を示す記号を除去せずに当該パスを前記第１のキーとし、
前記パステーブルが、前記全ての子要素を示す記号が含まれている前記パスを、当該パステーブルに保持されているテキスト表現のうちの当該パスと共通のテキスト表現を有するパスに変換するデータ処理方法。
請求項５乃至７のいずれか１項に記載のデータ処理方法において、
前記ＸＰａｔｈ式データ処理で取得された前記第３のキーに対応するパスのテキスト表現中のタグの出現順序が前記ＸＰａｔｈ式に含まれるパスのテキスト表現中のタグの出現順序と一致するとき、前記ノードリストが、取得した前記第３のキーに対応するパスに対応する前記第２のパス識別子を前記パステーブルから取得し、前記ＸＰａｔｈ式処理部と並行して、当該ノードリストから該第２のパス識別子に対応する前記最終のノード識別子を取得するデータ処理方法。
入力された第１のＸＭＬデータに対して、該第１のＸＭＬデータの一部を特定するためのＸＰａｔｈ式に適合する部分の抽出処理を行うＸＭＬデータ処理システムを実現するためのＸＭＬデータ処理制御プログラムであって、
コンピュータを、
前記第１のＸＭＬデータを解析してノード単位に分解し、各ノード毎にノード識別子を付与して第２のＸＭＬデータを作成すると共に、該第２のＸＭＬデータに対して前記ノード識別子を前記ＸＰａｔｈ式に基づいて指定するための索引を作成するＸＭＬ解析手段と、
該ＸＭＬ解析手段で作成された前記第２のＸＭＬデータを保持するＸＭＬデータ保持手段と、
前記ＸＭＬ解析手段で作成された前記索引を保持する索引手段と、
該索引手段で保持されている前記索引を用いて前記ＸＰａｔｈ式に対応した前記ノード識別子を取得し、前記ＸＭＬデータ保持手段にアクセスして該ノード識別子に対応した前記第２のＸＭＬデータを取得するＸＰａｔｈ式処理手段として機能させ、
前記ＸＭＬ解析手段により作成される前記索引は、
前記第２のＸＭＬデータに含まれる全て又は一部のパスのテキスト表現を、各パス識別子を付与して保持するパステーブルと、
該パステーブルに保持されている前記各パスを包含するパスに付与された前記パス識別子の集合を、前記各パス識別子毎に保持するパス識別子集合テーブルと、
前記パステーブルに保持されている前記各パスのうちのフルパスに対応するパス識別子を、前記第２のＸＭＬデータ中の当該フルパスを構成するノードの最終の前記ノード識別子を対応付けて保持するノードリストとから構成され、
前記ＸＰａｔｈ式処理手段は、前記ＸＰａｔｈ式に含まれるパスのテキスト表現を第１のキーとして前記パステーブルを検索して該第１のキーに対応する第１のパス識別子を取得し、該第１のパス識別子を第２のキーとして前記パス識別子集合テーブルを検索して該第２のキーに対応するパス識別子集合を取得し、取得した前記パス識別子集合の中で共通する共通パス識別子を取得し、取得した前記共通パス識別子を第３のキーとして前記パステーブルを検索して該第３のキーに対応するパスを取得し、取得した前記第３のキーに対応するパスのテキスト表現中のタグの出現順序が前記ＸＰａｔｈ式に含まれるパスのテキスト表現中のタグの出現順序と一致するとき、取得した前記第３のキーに対応するパスに対応する第２のパス識別子を前記パステーブルから取得し、前記ノードリストから該第２のパス識別子に対応する前記最終のノード識別子を取得し、かつ、前記ＸＭＬデータ保持手段から、前記最終のノード識別子が付与されたノードで構成されるフルパスに対応する前記第２のＸＭＬデータを取得するＸＭＬデータ処理制御プログラム。
請求項９に記載のＸＭＬデータ処理制御プログラムにおいて、
前記ＸＰａｔｈ式処理手段は、前記ＸＰａｔｈ式中の前記パスに全ての子要素を示す記号が含まれているとき、該全ての子要素を示す記号を除去して前記第１のキーとするＸＭＬデータ処理制御プログラム。
請求項９に記載のＸＭＬデータ処理制御プログラムにおいて、
前記ＸＰａｔｈ式処理手段は、前記ＸＰａｔｈ式中のパスに全ての子要素を示す記号が含まれているとき、該全ての子要素を示す記号を除去せずに当該パスを前記第１のキーとし、
前記パステーブルは、前記全ての子要素を示す記号が含まれている前記パスを、当該パステーブルに保持されているテキスト表現のうちの当該パスと共通のテキスト表現を有するパスに変換するＸＭＬデータ処理制御プログラム。
請求項９乃至１１のいずれか１項に記載のＸＭＬデータ処理制御プログラムにおいて、
前記ノードリストは、前記ＸＰａｔｈ式処理手段で取得された前記第３のキーに対応するパスのテキスト表現中のタグの出現順序が前記ＸＰａｔｈ式に含まれるパスのテキスト表現中のタグの出現順序と一致するとき、取得した前記第３のキーに対応するパスに対応する前記第２のパス識別子を前記パステーブルから取得し、前記ＸＰａｔｈ式処理手段と並行して、当該ノードリストから該第２のパス識別子に対応する前記最終のノード識別子を取得するＸＭＬデータ処理制御プログラム。