(57)【要約】　　　（修正有）【課題】関係型データベースにおいてユーザの質疑表現方法の違いと無関係に安定的に質疑を処理することのできるＸＭＬインデックス方法の経路インデックスルックアップ方法を提供する。【解決手段】経路ルックアップテーブル及び拡張幹線テーブルの構造を提示し、これらテーブルを用いて任意長さの正規経路式をただ一回のジョインにより処理することができる。よって、ＸＭＬの核心的なユーザ質疑形式の正規経路式質疑をユーザによる記述形式と無関係に安定的で且つ速く処理できる。【選択図】　図５Ｂ
2004030569.tif 000002
【特許請求の範囲】
【請求項１】
（ａ）拡張マークアップ言語（ＸＭＬ）を含む所定の言語にて作成され、表わされる情報が貯蔵されている前記情報の出所に関する少なくとも一つ以上の経路情報を含む文書から複数の前記経路情報を抽出する段階と、
（ｂ）前記複数の経路情報の各々に対応する経路識別子（ＩＤ）情報及び前記経路情報の詳細が他の貯蔵場所に貯蔵されているか否かを表わすインデックスフラグ情報をユーザから入力されて経路ルックアップテーブル貯蔵部に貯蔵する段階と、
（ｃ）前記インデックスフラグ情報が所定の値である場合、前記各々の経路ＩＤについてユーザから開始ノードＩＤ情報及び終了ノードＩＤ情報を入力されて拡張幹線テーブル貯蔵部に貯蔵する段階と、
（ｄ）ユーザから捜し出そうとする情報に関する検索式である正規経路式を入力されて、これと一致する経路式情報を経路ルックアップテーブル貯蔵部から捜し出して前記捜し出そうとする情報が貯蔵されている経路に対応する経路ＩＤ情報を求める段階と、
（ｅ）前記（ｄ）段階において求められた経路ＩＤ情報を検索キーとしてこれと一致する経路ＩＤ情報に対応する開始ノードＩＤ情報及び終了ノードＩＤ情報を前記拡張幹線テーブル貯蔵部から捜し出す段階と
を含む経路インデックスルックアップ方法。
【請求項２】
前記経路ルックアップテーブル貯蔵部に貯蔵された経路式情報は、
前記文書内において検索しようとする情報が貯蔵されている経路の名前を表わす経路名情報と、
前記経路を互いに識別させる機能を果たす前記経路に関する識別情報を表わす経路ＩＤ情報と、
文書内の様々な経路に関する開始ノードＩＤ情報及び終了ノードＩＤ情報を貯蔵している拡張幹線テーブルに前記経路がインデックスされているか否かを表わすインデックスフラグ情報と
を備えることを特徴とする請求項１に記載の経路インデックスルックアップ方法。
【請求項３】
前記拡張幹線テーブルは、
前記文書内において検索しようとする情報が貯蔵されている経路を互いに識別させる機能を果たす前記経路に関する識別情報を表わす経路ＩＤ情報と、
前記経路の開始ノードを表わす開始ノードＩＤ情報と、
前記経路の終了ノードを表わす終了ノードＩＤ情報と
を備えることを特徴とする請求項１に記載の経路インデックスルックアップ方法。
【請求項４】
請求項１に記載の方法をコンピュータにて実行するためのプログラムを記録したコンピュータにて読取り可能な記録媒体。
【請求項５】
ＸＭＬを含む所定の言語にて作成され、表わされる情報が貯蔵されている前記情報の出所に関する少なくとも一つ以上の経路情報を含む文書において、
前記複数の経路情報の各々に対応する経路ＩＤ情報及び前記経路情報の詳細が他の貯蔵場所に貯蔵されているか否かを表わすインデックスフラグ情報をユーザから入力されて貯蔵する経路ルックアップテーブル貯蔵部と、
前記インデックスフラグ情報が所定の値である場合、前記各々の経路ＩＤについてユーザから開始ノードＩＤ情報及び終了ノードＩＤ情報を入力されて貯蔵する拡張幹線テーブル貯蔵部と、
ユーザから捜し出そうとする情報に関する検索式である正規経路式を入力されてこれと一致する経路式情報を前記経路ルックアップテーブル貯蔵部から捜し出して前記捜し出そうとする情報が貯蔵されている経路に対応する経路ＩＤ情報を求める経路ＩＤ検索部と、
前記経路ＩＤ検索部において求められた経路ＩＤ情報を検索キーとしてこれと一致する経路ＩＤ情報に対応する開始ノードＩＤ情報及び終了ノードＩＤ情報を前記拡張幹線テーブル貯蔵部から捜し出して出力する経路情報判断及び出力部とを備える経路インデックスルックアップ装置。
【請求項６】
ＸＭＬを含む所定の言語にて作成され、表わされる情報が貯蔵されている前記情報の出所に関する少なくとも一つ以上の経路情報を含む文書を関係型データベースに貯蔵するのに用いられる資料構造において、
前記文書内において検索しようとする情報が貯蔵されている経路の名前を表わす経路名情報と、
前記経路を互いに識別させる機能を果たす前記経路に関する識別情報を表わす経路ＩＤ情報と、
文書内の様々な経路に関する経路の開始及び終了ノード情報を貯蔵している拡張幹線テーブルに前記経路がインデックスされているか否かを表わすインデックスフラグ情報と
を備え、
ユーザから捜し出そうとする情報に関する検索式である正規経路式が入力されればこれと一致する経路式情報に関する経路名情報を捜し出してこれと対応する経路ＩＤ情報を出力する経路ルックアップテーブル資料構造を記録したコンピュータにて読取り可能な記録媒体。
【請求項７】
ＸＭＬを含む所定の言語にて作成され、表わされる情報が貯蔵されている前記情報の出所に関する少なくとも一つ以上の経路情報を含む文書を関係型データベースに貯蔵するのに用いられる資料構造において、
前記文書内において検索しようとする情報が貯蔵されている経路を互いに識別させる機能を果たす前記経路に関する識別情報を表わす経路ＩＤ情報と、
前記経路の開始ノードを表わす開始ノードＩＤ情報と、
前記経路の終了ノードを表わす終了ノードＩＤ情報と
を備え、
ユーザから捜し出そうとする情報に関する経路ＩＤ情報が入力されればこれと対応する開始ノードＩＤ情報及び終了ノードＩＤ情報を出力する拡張幹線テーブル資料構造を記録したコンピュータにて読取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は関係型データベースにおいてユーザの質疑表現方法の違いと無関係に安定的に質疑を処理することのできる拡張マークアップ言語（ＸＭＬ：Ｅｘｔｅｎｄｅｄ　Ｍａｒｋｕｐ　Ｌａｎｇｕａｇｅ）インデックス方法である経路インデックスルックアップ方法に係り、経路ルックアップテーブル及び拡張幹線テーブルの構造を提示し、これらテーブルを用いて任意の長さの正規経路式をただ一回のジョイン演算により処理可能にする方法を提供する。
【０００２】
インターネットにおいて情報交換の標準言語として提案されたＸＭＬはコンピュータ及びネットワークシステム（ＳｙｎｃＭＬ，ＵＰｎＰ）においてはもとより、生物情報（ＢＳＭＬ，ＢｉｏＭＬ）、電子商取引き（ｅｂＸＭＬ，ＥＣＭＬ）、電子文書交換（ＸＭＬ−ＥＤＩ）、地理情報及び全域位置システム（ＧＰＳ：Ｇｌｏｂａｌ　Ｐｏｓｉｔｉｏｎｉｎｇ　Ｓｙｓｔｅｍ）（ＧＭＬ，ＮＶＭＬ）、マルチメディア（ＭＰＥＧ−７，ＩＭＬ）、エンターテイメント（ＭｕｓｉｃＸＭＬ，ＧＭＬ）、教育（ＬＭＭＬ，ＴＭＬ）、医療（ＣＴＤＭ，ＴＤＬ）、出版（ＢｉｂｌｉｏＭＬ，ＤｏｃＢｏｏｋ）、テレビ放送（ＴＶ−Ａｎｙｔｉｍｅ）など、産業全分野において幅広く用いられている。
【０００３】
各応用分野においてＸＭＬにより記述されたデータが関係型データベースや客体指向型データベースなど既存のデータベースにおける定形的なデータと異なる点の一つは、データ構造が半構造的であるということである。すなわち、ＸＭＬは、応用分野に合うデータ構造を表わす様式（ＤＴＤ：Ｄｏｃｕｍｅｎｔ　Ｔｙｐｅ　Ｄｅｆｉｎｉｔｉｏｎ）は定義するが、その様式に厳しく従わなくても良いという半構造的な特性を有する。
【０００４】
ＸＭＬの半構造的な特性は、相異なる情報ソース間のデータ表現及び交換において融通性を提供できるという長所がある。ＸＭＬが多くの応用分野において標準言語として用いられる理由の一つも、データ表現が容易であるということに加えて、このような半構造的な特性によるためであると見られる。
ＸＭＬの半構造的な特性のゆえに、ＸＭＬにて文書を作成する著作者は定義されたＤＴＤから外れてＸＭＬのデータを変形して生成することが許容されるだけではなく、ＸＭＬにて作成された文書のユーザもまたＸＭＬデータの正確な構造が分からなくてもデータに対する検索を行うことができる。
【０００５】
ＸＭＬの半構造的な特性に基づく検索はユーザが検索しようとするデータを表わしたＸＭＬの文書構造が正確に分からない時に有用である。例えば、ウェブにおいて特定分野のＸＭＬにて作成された文書を検索する時、ユーザはその特定分野のスキーマを正確に反映していない部分的な知識でも文書に関する質疑結果を得ることができる。
【０００６】
ユーザのＸＭＬデータに関する半構造的な特性に基づく検索式はＸＭＬの質疑語であるＸＱｕｅｒｙなどにおいて正規経路式質疑により表わせる。質疑を処理するシステム側面においてＸＭＬの正規経路式質疑は、定形化したスキーマに基づくデータベース質疑とは異なって質疑条件に相当するデータの構造を正確に記述しないため、同じ条件を表わす質疑がユーザの質疑記述方法によって異なる質疑として解釈されて行われる場合がある。従って、ＸＭＬを処理するシステムが正規経路式質疑を解釈して最適化する方法によって質疑処理性能に多くの違いを示す恐れがある。
【０００７】
ＸＭＬ文書を関係型データベースに貯蔵する方法は、代表的に、幹線技法とアトリビュート技法とに大別できる。幹線技法はＸＭＬ文書に関するスキーマ情報がない場合にも一般的にそのＸＭＬ文書を貯蔵して処理できるという長所があるものの、相対的に大きい幹線テーブルに関する経路式の長さだけの重なったセルフジョインにより性能低下が起こりうる。ジョイン演算はテーブル内のエレメント間の関係を求める演算を言い、セルフジョインは同じテーブル内においてエレメント間の関係を求める演算を言う。
【０００８】
アトリビュート技法はＸＭＬ文書のスキーマ情報が予め知られている時、エンティティ単位にテーブルを生成して処理する方法である。従って、幾つかのテーブルにデータを分割して貯蔵する効果があり、幹線技法に比べてその性能を高めることができるが、ＸＭＬスキーマによってはテーブルの数が多過ぎたり、不要にデータが断片化したりするという短所がある。
【０００９】
かかる問題点を補完するために、スキーマのないＸＭＬ文書を貯蔵するために、データマイニング方法を用いて分離可能なテーブルの種類及び数を定める方法に関する研究が進んできた。幹線技法及びアトリビュート技法ともに基本的には経路式を処理する方法であり、経路式の長さだけテーブル間のジョイン演算が必要である。また、正規経路式を処理するのに適した構造を有していない。
【００１０】
幹線技法のうちタッグの開始及び終了オフセットの情報を用いて正規経路式を処理する方法があるが、経路式が長い場合に効率的ではなく、ユーザによる質疑記述方法によって質疑処理性能が左右されるという短所がある。
ＸＭＬデータに関する経路式インデックス方法としてインデックスファブリックと呼ばれる方法があるが、これはＸＭＬ文書に存在する各種の経路に関するインデックスを一つのインデックス構造において管理できるという特徴を有する。このインデックス構造は関係型データベースを支援するためにさらなる拡張を行った構造である。インデックスファブリックにおいては、特定の正規経路式を処理するためにその特定経路を人工経路の形でインデックス構造に明らかに付加しなければならない。本発明による経路ルックアップテーブルはインデックスファブリックにおいて正規経路式を処理するのにも適用できる。
【００１１】
そして、インデックスの役割を果たすテーブル構造が提示されている。しかし、この方法をＸＭＬの経路式インデックスに直ちに適用する時の問題点は、インデックステーブルの数が増えるか、あるいは断片化するということである。ＸＭＬデータに対する経路式処理はツリーを巡回するという点で客体指向型データベースにおける経路式処理方法と類似している。
【００１２】
【発明が解決しようとする課題】
前記問題を解決するために、本発明においては、関係型データベースにおいてＸＭＬにて表わされた正規経路式質疑をユーザの表現方法の違いを問わずに同じ方法により解釈し、効率良いＸＭＬインデックス方法を提供することを目的とする。
詳細には、既存の方法において正規経路式が長くなるほど質疑処理性能が落ちるのとは異なって、正規経路式の長さと無関係に一回のジョインにて任意の正規経路式を処理することのできるＸＭＬインデックス方法を提供する。また、関係型データベースシステムエンジンの変形なしに用いることのできるテーブル及びＢツリーに基づくＸＭＬインデックステーブル資料構造を提供することを目的とする。
【００１３】
【課題を解決するための手段】
前記目的を達成するために、本発明においては、ＸＭＬを含む所定の言語にて作成され、表わされる情報が貯蔵されている前記情報の出所に関する少なくとも一つ以上の経路情報を含む文書から複数の前記経路情報を抽出する段階と、前記複数の経路情報の各々に対応する経路識別子（ＩＤ）情報及び前記経路情報の詳細が他の貯蔵場所に貯蔵されているか否かを表わすインデックスフラグ情報をユーザから入力されて経路ルックアップテーブル貯蔵部に貯蔵する段階と、前記インデックスフラグ情報が所定の値である場合、前記各々の経路ＩＤについてユーザから開始ノードＩＤ情報及び終了ノードＩＤ情報を入力されて拡張幹線テーブル貯蔵部に貯蔵する段階と、ユーザから捜し出そうとする情報に関する検索式である正規経路式を入力されてこれと一致する経路式情報を前記経路ルックアップテーブル貯蔵部から捜し出して前記経路に対応する経路ＩＤ情報を求める段階と、前記段階において求められた経路ＩＤ情報を検索キーとしてこれと一致する経路ＩＤ情報に対応する開始ノードＩＤ情報及び終了ノードＩＤ情報を前記拡張幹線テーブル貯蔵部から捜し出す段階とを含む経路インデックスルックアップ方法を提供する。
【００１４】
前記目的を達成するために、本発明においては、前記方法をコンピュータにて実行するためのプログラムを記録したコンピュータにて読取り可能な記録媒体を提供する。
前記目的を達成するために、本発明においては、ＸＭＬを含む所定の言語にて作成され、表わされる情報が貯蔵されている前記情報の出所に関する少なくとも一つ以上の経路情報を含む文書において、前記複数の経路情報の各々に対応する経路ＩＤ情報及び前記経路情報の詳細が他の貯蔵場所に貯蔵されているか否かを表わすインデックスフラグ情報をユーザから入力されて貯蔵する経路ルックアップテーブル貯蔵部と、前記インデックスフラグ情報が所定の値である場合、前記各々の経路ＩＤについてユーザから開始ノードＩＤ情報及び終了ノードＩＤ情報を入力されて貯蔵する拡張幹線テーブル貯蔵部と、ユーザから捜し出そうとする情報に関する検索式である正規経路式を入力されてこれと一致する経路式情報を前記経路ルックアップテーブル貯蔵部から捜し出して前記経路に対応する経路ＩＤ情報を求める経路ＩＤ検索部と、前記経路ＩＤ検索部において求められた経路ＩＤ情報を検索キーとしてこれと一致する経路ＩＤ情報に対応する開始ノードＩＤ情報及び終了ノードＩＤ情報を前記拡張幹線テーブル貯蔵部から捜し出して出力する経路情報判断及び出力部とを備える経路インデックスルックアップ装置を提供する。
【００１５】
前記目的を達成するために、本発明においては、ＸＭＬを含む所定の言語にて作成され、表わされる情報が貯蔵されている前記情報の出所に関する少なくとも一つ以上の経路情報を含む文書を関係型データベースに貯蔵するのに用いられる資料構造において、前記文書内において検索しようとする情報が貯蔵されている経路の名前を表わす経路名情報と、前記経路を互いに識別させる機能を果たす前記経路に関する識別情報を表わす経路ＩＤ情報と、文書内の様々な経路に関する経路開始及び終了ノード情報を貯蔵している拡張幹線テーブルに前記経路がインデックスされているか否かを表わすインデックスフラグ情報とを備え、ユーザから捜し出そうとする情報に関する検索式である正規経路式が入力されればこれと一致する経路式情報に関する経路名情報を捜し出してこれと対応する経路ＩＤ情報を出力する経路ルックアップテーブルを提供する。
【００１６】
前記目的を達成するために、本発明においては、ＸＭＬを含む所定の言語にて作成され、表わされる情報が貯蔵されている前記情報の出所に関する少なくとも一つ以上の経路情報を含む文書を関係型データベースに貯蔵するのに用いられる資料構造において、前記文書内において検索しようとする情報が貯蔵されている経路を互いに識別させる機能を果たす前記経路に関する識別情報を表わす経路ＩＤ情報と、前記経路の開始ノードを表わす開始ノードＩＤ情報と、前記経路の終了ノードを表わす終了ノードＩＤ情報とを備え、ユーザから捜し出そうとする情報に関する経路ＩＤ情報が入力されればこれと対応する開始ノードＩＤ情報及び終了ノードＩＤ情報を出力する拡張幹線テーブルを提供する。
従って、本発明においては、ユーザ質疑の形に対して依存的な性能を示す既存の技法とは異なって、ユーザの質疑表現とは独立的に正規経路式を安定的で且つ速く処理することのできる経路インデックスルックアップ方法を提供する。
【００１７】
【発明の実施の形態】
以下、添付した図面に基づき、本発明による好適な一実施形態について詳細に説明する。
正規経路式とは、ユーザがＸＭＬ文書内の接近しようとするあるエンティティの経路を指定する時、その経路を全て並べることなく、縮約して表わす経路式を言う。
【００１８】
図１Ａないし図１Ｂは、ＴＶ−Ａｎｙｔｉｍｅのメタデータ規格の一部を表わすＸＭＬにて作成された文書の一実施形態である。
ＴＶ−ＡｎｙｔｉｍｅのメタデータはＴＶ放送番組に関する情報を表わすが、プログラムＩＤ　ｐｒｏｇｒａｍＩｄ、題目Ｔｉｔｌｅ、要約情報Ｓｙｎｏｐｓｉｓ、キーワードＫｅｙｗｏｒｄｓ、ジャンルＧｅｎｒｅ、キャスティング情報ＣａｓｔＬｉｓｔなどを含んでいる。図１Ａは、　ＴＶ−ＡｎｙｔｉｍｅのＸＭＬにて作成された文書の例を示し、図１Ｂは、文書の内容をツリーの形で表わしたものである。
【００１９】
図１Ｂから分かるように、ＴＶ放送システムのように一般ビジネス応用分野におけるＸＭＬ文書構造はツリーが極めて深くて複雑であるため、ユーザは文書に対する検索を要請する時、正確な経路を記述し難い。例えば、本例においてユーザが特定番組に登場する俳優の名前を検索する時、
／ＰｒｏｇｒａｍＩｎｆｏｒｍａｔｉｏｎ／ＢａｓｉｃＤｅｓｃｒｉｐｔｉｏｎ／ＣａｓｔＬｉｓｔ／ＣａｓｔＭｅｍｂｅｒ／Ａｇｅｎｔ／Ｎａｍｅ
のようにルートエレメントから名称エレメントまでの経路を全て並べた絶対経路式にて記述しても良いが、
／ＰｒｏｇｒａｍＩｎｆｏｒｍａｔｉｏｎ／／ＣａｓｔＬｉｓｔ／／Ａｇｅｎｔ／Ｎａｍｅ
のようにユーザが必要であると思うエレメント名前よりなる正規経路式にてさらに簡単に記述することができる。前記絶対経路式において記号‘／’はＸＭＬ文書上において直接的な親子の関係を表わすのに対し、記号‘／／’は親子関係の意味を拡張して一般的な先祖−子孫の関係を表わす。記号‘／／’で表わされる先祖−子孫の関係は正規経路式のための代表関係の一つである。
【００２０】
図２は、正規経路式において用いられる主な記号及びその意味を示す図面である。
すなわち、ＸＭＬ質疑語であって、ワールドワイドウェブコンソーシアム（Ｗ３Ｃ）においてＸＭＬ標準言語として提案されたＸＱｕｅｒｙ上において正規経路式のための主要記号及びその意味を示すものである。一つの絶対経路式は図２に示された記号を用いて様々な正規経路式にて表わせる。
【００２１】
例えば、前記絶体経路式
／ＰｒｏｇｒａｍＩｎｆｏｒｍａｔｉｏｎ／ＢａｓｉｃＤｅｓｃｒｉｐｔｉｏｎ／ＣａｓｔＬｉｓｔ／ＣａｓｔＭｅｍｂｒ／Ａｇｅｎｔ／Ｎａｍｍｅは、前記正規経路式／ＰｒｏｇｒａｍＩｎｆｏｒｍａｔｉｏｎ／／ＣａｓｒＬｉｓｔ／／Ａｇｅｎｔ／Ｎａｍｅを含めて下記のように様々な正規経路式にて表せる。
／／ＣａｓｔＭｅｍｂｅｒ／／Ｎａｍｅ
／ＰｒｏｇｒａｍＩｎｆｏｒｍａｔｉｏｎ／＊／Ａｇｅｎｔ／Ｎａｍｅ
／／ＣａｓｔＬｉｓｔ／／Ａｇｅｎｔ／？
【００２２】
中でも前記正規経路式／／ＣａｓｔＭｅｍｂｅｒ／／Ｎａｍｅは、前記絶対経路式と比較して同じ内容を簡単に表わしている。このように正規経路式入り質疑においては、同じ内容がユーザにより異なって表わされる場合がある。このため、正規経路式質疑を処理するシステムはユーザ質疑を解釈する方法によってその性能に多くの違いが生じうる。
【００２３】
従来に提案された方法においては、関係型データベースにおいてＸＭＬ文書に関する正規経路式質疑を処理するために、下記の如く２つのテーブル構造を提案した。
Ｅｌｅｍｅｎｔｓ（ｔｅｒｍ，　ｄｏｃｎｏ，　ｂｅｇｉｎ，　ｅｎｄ，　ｌｅｖｅｌ）
Ｔｅｘｔｓ（ｔｅｒｍ，　ｄｏｃｎｏ，　ｗｏｒｄｎｏ，　ｌｅｖｅｌ）
【００２４】
Ｅｌｅｍｅｎｔｓテーブルは、ＸＭＬ文書においてタッグとして指定されたエレメント及びアトリビュートを個々のタップルとして貯蔵する。ｔｅｒｍはタッグの名前を、ｄｏｃｎｏはタッグの属する文書ＩＤを、ｂｅｇｉｎ及びｅｎｄは文書内においてｔｅｒｍの属するタッグのオフセット範囲を、ｌｅｖｅｌは文書内においてエレメントの重なった回数、すなわち、先祖の数を各々表わす。
【００２５】
ＴｅｘｔｓテーブルはＸＭＬ文書においてタッグ内に含まれた値を個々のタップルとして貯蔵する。ｄｏｃｎｏはある値の属するＩＤを、ｗｏｒｄｎｏは該当値の文書内のオフセットを、ｌｅｖｅｌは文書内において重なった回数を各々表わす。このような貯蔵構造下において、正規経路式はエレメントのオフセット値及びレベル値を用いたＥｌｅｍｅｎｔｓテーブルに対するセルフジョインにより処理される。
【００２６】
図３は、前記Ｅｌｅｍｅｎｔｓテーブル及びＴｅｘｔｓテーブル構造を用いて各エレメントを表わした一実施形態である。
すなわち、ｓｅｃｔｉｏｎというエレメントについて説明すれば、（１，１：２３，０），（１，８：２２，１），（１，１４：２１，２）があるが、最初の（１，１，１）はｄｏｃｎｏを表わし、１：２３，　８：２２，　１４：２１は開始及び終了を表わし、最後の数字０，　１，　２はレベルを表わす。
【００２７】
すなわち、従来の方法において、正規経路式はＥｌｅｍｅｎｔｓテーブルに対するセルフジョインにより処理される。例えば、前記正規経路式／／ＣａｓｔＭｅｍｂｅｒ／／Ｎａｍｅは下記の如きＳＱＬ質疑として表わされて処理される。
Ｓｅｌｅｃｔ　ｅ１
Ｆｒｏｍ　Ｅｌｅｍｅｎｔｓ　ｅ１，　Ｅｌｅｍｅｎｔｓ　ｅ２
Ｗｈｅｒｅ　ｅ１．　ｔｅｒｍ＝‘ＣａｓｔＭｅｍｂｅｒ’
Ａｎｄ　ｅ２．　ｔｅｒｍ＝‘Ｎａｍｅ’
Ａｎｄ　ｅ１．　ｂｅｇｉｎ＜ｅ２．　ｂｅｇｉｎ
Ａｎｄ　ｅ１．　ｅｎｄ＞ｅ２．　ｅｎｄ
Ａｎｄ　ｅ１．　ｄｏｃｎｏ＝ｅ２．　ｄｏｃｎｏ
【００２８】
この質疑はＣａｓｔＭｅｍｂｅｒを代表するＥｌｅｍｅｎｔｓテーブル及びＮａｍｅを代表するＥｌｅｍｅｎｔｓテーブルのセルフジョインにより処理される。先祖−子孫の関係を表わす‘／／’に対し、ジョイン条件には両エレメント間のオフセット包含関係となる。
すなわち、ＸＭＬ文書上における両エレメントＡ及びＢに対し、ＡのｂｅｇｉｎオフセットがＢのｂｅｇｉｎオフセットより小さく、ＡのｅｎｄオフセットがＢのｅｎｄオフセットより大きい時、Ａ／／Ｂという正規経路式が満足される。前記質疑においては両エレメントＣａｓｔＭｅｍｂｅｒ及びＮａｍｅに対し、ＣａｓｔＭｅｍｂｅｒのｂｅｇｉｎオフセットがＮａｍｅのｂｅｇｉｎオフセットより小さく、　ＣａｓｔＭｅｍｂｅｒのｅｎｄオフセットがＮａｍｅのｅｎｄオフセットより大きいという条件を表わしている。
【００２９】
既存に提案されている正規経路式処理方法の共通した問題点は、システムの質疑処理性能がユーザによる正規経路式の記述方法に対して依存的であるというところにある。すなわち、正規経路式に幾つのタッグが指定されたかによってその正規経路式を処理するために必要なジョインの回数が決まる。
前述したように、同じ絶対経路式に対して様々な正規経路式があり、それによりジョインの回数も変わる。
【００３０】
すなわち、同じ内容を表わす正規経路式のうち／／ＣａｓｔＭｅｍｂｅｒ／／Ｎａｍｅは、ジョインが一回のみ必要であるが
／ＰｒｏｇｒａｍＩｎｆｏｒｍａｔｉｏｎ／ＢａｓｉｃＤｅｓｃｒｉｐｔｉｏｎ／ＣａｓｔＬｉｓｔ／ＣａｓｔＭｅｍｂｅｒ／Ａｇｅｎｔ／Ｎａｍｅは、ジョインが５回行われなければならない。
そして、同じ質疑における正規経路式
／ＰｒｏｇｒａｍＩｎｆｏｒｍａｔｉｏｎ／／ＣａｓｔＬｉｓｔ／／Ａｇｅｎｔ／Ｎａｍｅに対し、３回のジョイン演算が必要となる。
このように、従来の技術においては、実際の応用分野に適用するのに多くの難点があった。このため、ＸＭＬ文書を貯蔵して検索する問題がＸＭＬを取り扱う応用分野における技術的なボトルネックであった　。
【００３１】
これに対し、本発明において提示する経路インデックスルックアップ方法は既存に提案されたＥｌｅｍｅｎｔｓテーブル及びＴｅｘｔｓテーブルに加え、下記の如き２種のテーブル構造を追加してＸＭＬ文書をインデックスする。
ＰａｔｈＬｏｏｋｕｐ（ｐａｔｈｎａｍｅ，　ｐａｔｈｉｄ，　ｉｎｄｅｘｆｌａｇ）
ＥｘｔｅｎｄｅｄＥｄｇｅ（ｐａｔｈｉｄ，　ｓｏｒｉｄ，　ｔａｒｉｄ）
経路ルックアップテーブルはＸＭＬ文書をパーシングした時に発生可能な経路をタップルとして貯蔵する。
【００３２】
ｐａｔｈｎａｍｅは経路の名前を表わし、ｐａｔｈｉｄはその経路に関するＩＤであり、ｉｎｄｅｘｆｌａｇは該当経路が拡張幹線テーブルにおいてインデックスされているか否かを表わす。拡張幹線テーブルは経路の長さが１以上である経路のインデックス情報を貯蔵する。ｐａｔｈｉｄは経路ルックアップテーブルにおけるタップルを示す経路ＩＤを、ｓｏｒｉｄ（ｓｏｕｒｃｅ　ｉｄ）及びｔａｒｉｄ（ｔａｒｇｅｔ　ｉｄ）はＥｌｅｍｅｎｔｓテーブルにおけるエレメントＩＤを各々表わす。
【００３３】
ＸＭＬにて作成された文書をデータベースに入力する時、全ての可能な経路名を選択してそれらをＩＤと共に経路ルックアップテーブルにタップルとして貯蔵する。ＸＭＬにて作成された文書に関する経路はその文書をパーシングする時に抽出することができるので、該当文書のためのＤＴＤあるいはＸＭＬスキーマが別途に必要ではない。
【００３４】
ＸＭＬにて作成された文書構造を表わすツリーにおいて、ルートからのレベルがｋであるノードＡに対する可能な長さが１以上である経路のうちＡで終わる経路の数はｋ個存在しうる。ここで注目すべき点は、ある文書に関する経路抽出に際し、以前の文書において生じた経路は重なって入力されないため、構造が類似した大容量のＸＭＬにて作成された文書をデータベースに入力しても経路ルックアップテーブルはあまり大きくならないということである。
【００３５】
経路ルックアップテーブルはユーザが入力した正規経路式を実際のＸＭＬデータ空間に存在する経路に迅速に変換するためのインデックスの役割を果たす。ユーザが記述した正規経路式を経路ルックアップテーブルに貯蔵されている経路にマッピングする演算はＳＱＬ（Ｓｔｒｕｃｔｕｒｅｄ　Ｑｕｅｒｙ　Ｌａｎｇｕａｇｅ）のｌｉｋｅ構文にて処理される。
【００３６】
正規経路式のＳＱＬのｌｉｋｅ構文へのマッピングを容易にするために、経路名を経路ルックアップテーブルに貯蔵する時には、経路の各ノードにタッグを付けて貯蔵する。例えば、経路‘Ａ／Ｂ／Ｃ’は‘＜Ａ＞＜Ｂ＞＜Ｃ＞’のように貯蔵される。
図４は、正規経路式に関するＳＱＬのｌｉｋｅ構文である。
【００３７】
図４の構文を用い経路ルックアップテーブルにおいて経路を検索するために、前記で例として取られた正規経路式／ＰｒｏｇｒａｍＩｎｆｏｒｍａｔｉｏｎ／／ＣａｓｔＬｉｓｔ／／Ａｇｅｎｔ／Ｎａｍｅに関するＳＱＬ構文を作成すれば、下記の通りである。
Ｓｅｌｅｃｔ　ｐａｔｈｉｄ
Ｆｒｏｍ　ＰａｔｈＬｏｏｋｕｐ
Ｗｈｅｒｅ　ｐａｔｈｎａｍｅ　ｌｉｋｅ‘＜ＰｒｏｇｒａｍＩｎｆｏｒｍａｔｉｏｎ＞％＜ＣａｓｔＬｉｓｔ＞％＜Ａｇｅｎｔ＞＜Ｎａｍｅ＞；
【００３８】
以下では、拡張幹線テーブルについて説明する。拡張幹線テーブルはＸＭＬにて作成された文書上の経路を速く処理するための経路インデックステーブルである。各タップルは経路ルックアップのための経路ＩＤを有しており、経路ルックアップテーブルのタップルを参照する。
各経路の開始ノードＩＤ　ｓｏｒｉｄ及び終了ノードＩＤ　ｔａｒｉｄを指定するフィールド値はＥｌｅｍｅｎｔｓテーブルのタップルを参照する。終了ノードＩＤ　ｔａｒｉｄがエレメントの代わりにテキストを指定する時には終了ノードＩＤ　ｔａｒｉｄはＴｅｘｔｓテーブルのタップルを参照する。注目すべき点は、以前の幹線技法などで繰り返しジョインを通じて経路を処理するのとは異なって、拡張幹線テーブルは極めて長い経路の場合にもさらなるジョイン演算無しにも一回に接近できる構造を有するということである。
【００３９】
図５は、ＸＭＬ文書に関する経路ルックアップテーブル及び拡張幹線テーブルの構成の一実施形態である。
すなわち、図５Ａの如きＸＭＬ文書がある時、図５Ｂは経路ルックアップテーブルを、図５Ｃは拡張幹線テーブルの構成例を各々示している。換言すれば、図５Ａは入力される文書の構造を示し、図５Ｂは文書入力時に新しく生じる経路に対して作成された経路ルックアップテーブルを示す。経路ルックアップテーブルのインデックスフラグｉｎｄｅｘｆｌａｇフィールドは該当経路が拡張幹線テーブルにインデックスされているか否かを表わす。
【００４０】
図５Ｂにおいて、経路／Ａ／Ｂ／Ｃ及び／Ａ／Ｂ／Ｄに対してのみ拡張幹線テーブルにおいてインデックスされているということが分かる。拡張幹線テーブルはＸＭＬにて作成された文書のノード数の自乗に比例するため、全ての経路をインデックスすればテーブルが大きすぎるため、インデックスする経路を区分し、その区分された経路のみを貯蔵するための方法である。
【００４１】
図５Ｃの拡張幹線テーブルにおいては、図５Ｂの経路ルックアップテーブルのインデックスフラグｉｎｄｅｘｆｌａｇにおいて指定された経路／Ａ／Ｂ／Ｃ及び／Ａ／Ｂ／Ｄに関する実際の経路インスタンスを貯蔵する。
拡張幹線テーブルにおいては、与えられた正規経路式に対して経路ルックアップテーブルにおいて捜し出された経路ＩＤをもって指定されたタップルが接近されるため、このテーブルに対して経路ＩＤをキーフィールドとして指定し、このフィールドにＢツリーインデックスを用いれば極めて早く接近することができる。
【００４２】
経路インデックスルックアップ方法における正規経路式の処理は下記の通りである。まず、与えられた正規経路式について可能な経路式を経路ルックアップテーブルから捜し出してそれらの経路ＩＤを求める。次に、求められた経路ＩＤに対応する開始ノードＩＤ及び終了ノードＩＤを拡張幹線テーブルから得る。これら２段階の演算は、経路ＩＤをジョインキーとするジョイン演算により表わせる。
【００４３】
図６は、経路インデックスルックアップ方法の構造を示す図面である。
図６に示されたように、経路インデックスルックアップ方法においては、ユーザが表わす正規経路式の形と無関係に該当正規経路式を経路ルックアップテーブルに対するテーブル検索及び拡張幹線テーブルに対するＢツリー検索演算により処理する。
【００４４】
前述した例において、ＴＶ放送用ＸＭＬ文書に関する正規経路式のうち／ＰｒｏｇｒａｍＩｎｆｏｒｍａｔｉｏｎ／／ＣａｓｔＬｉｓｔ／／Ａｇｅｎｔ／Ｎａｍｅを既存の方法により処理するＳＱＬ構文は下記の通りである。
2004030569.tif 000003
【００４５】
従って、前記のように３回のジョイン演算入りの質疑文により表わされるのに対し、経路インデックスルックアップ方法を通じたＳＱＬ構文は下記のように一回のジョインにより処理される。
2004030569.tif 000004
【００４６】
図７は、正規経路式質疑に関する経路インデックスルックアップ方法のフローチャートである。
まず、ＸＭＬにて作成された文書から抽出可能な全ての経路名を抽出して経路ＩＤ情報及びインデックスフラグ情報と共に経路ルックアップテーブルに貯蔵する（ステップ７１０）。そして、前記各々の経路ＩＤに対して開始ノードＩＤ及び終了ノードＩＤを拡張幹線テーブルに貯蔵する（ステップ７２０）。
【００４７】
次には、正規経路式を入力され（ステップ７３０）、これに対応する経路式を経路ルックアップテーブルにおいて検索して経路ＩＤを求める（ステップ７４０）。この時、ＳＱＬのｌｉｋｅ構文を用いて経路ルックアップテーブルにおいて経路ＩＤを求める。そして、求められた経路ＩＤをジョインキーとするジョイン演算により表わして行う。
【００４８】
そして、前記段階において求められた経路ＩＤを検索キーとして拡張幹線テーブルを検索し、経路の開始ノードＩＤ及び終了ノードＩＤを求める（ステップ７５０）。この時、拡張幹線テーブルに対するＢツリー検索演算により行われる。図８は、正規経路式質疑に関する経路インデックスルックアップ装置を示す図面である。
【００４９】
経路インデックスルックアップ装置は、経路ルックアップテーブル貯蔵部８１０と、拡張幹線テーブル貯蔵部８２０と、経路ＩＤ検索部８３０及び経路情報判断及び出力部８４０を備えてなる。
経路ルックアップテーブル貯蔵部８１０は、ＸＭＬにて作成された文書から複数の経路情報を抽出し、ユーザから入力された経路ＩＤ情報及びインデックスフラグ情報と共に貯蔵する。貯蔵形態はテーブル形態であり、図５Ｂの通りである。
【００５０】
拡張幹線テーブル貯蔵部８２０は、前記各々の経路ＩＤに対してユーザから開始ノードＩＤ情報及び終了ノードＩＤ情報を入力されて貯蔵する。貯蔵形態はテーブル形態であり、図５Ｃの通りである。
経路ＩＤ検索部８３０は、ユーザから正規経路式情報を入力されてこれと一致する経路を前記経路ルックアップテーブル貯蔵部から捜し出し、所望の経路に相当する経路ＩＤ情報を求める。
【００５１】
経路情報判断及び出力部８４０は、前記経路ＩＤ検索部８３０において求められた経路ＩＤ情報を検索キーとしてこれと一致する経路情報を前記拡張幹線テーブル貯蔵部８２０から捜し出し、経路の開始ノードＩＤ情報及び終了ノードＩＤ情報を求めて出力する。
そして、正規経路式質疑に対して本発明が提供する経路インデックスルックアップ方法の性能をオフセットを用いたジョイン技法の性能と比較した。実験に用いられたデータはＴＶ放送システムの文書１２００個を関係型データベースシステムに入力した。入力済みのＥｌｅｍｅｎｔｓテーブルのノード数は約１，０００，０００であった。
【００５２】
図９は、実験に用いられた正規経路式テーブルである。
実験においては、図９に示されたように、ノード数が２ないし９である正規経路式を処理するのにかかる反応時間を測定した。
図１０は、正規経路式のノード数による反応時間グラフである。
オフセットジョインはオフセット値に基づくジョイン技法における反応時間を、経路ルックアップは経路インデックスルックアップ技法における反応時間を各々表わす。
【００５３】
図１０から分かるように、既存のオフセットを用いたジョイン技法は正規経路式が長くなるほど反応時間が延びるのに対し、本発明が提供する経路インデックス方法は正規経路式の長さに敏感ではなく、平均的に良好な性能を示している。ノード数が２である時、すなわち、オフセットジョインにおいてジョインが一回生じる場合にも経路ルックアップ方法がさらに良好な性能を示す理由は、経路ルックアップ技法においてはＢツリーを用い拡張幹線テーブルから該当経路式に対するタップルへと早く接近するからである。これに対し、オフセットジョインは、オフセット間の包含関係を用いたジョインであるため、その反応時間がさらに長い。
【００５４】
一方、前記本発明の実施形態はコンピュータにて実行可能なプログラムにて作成でき、コンピュータにて読取り可能な記録媒体を用いて前記プログラムを動作させる汎用のデジタルコンピュータにより具現できる。
また、上述した本発明の実施形態において用いられたデータの構造はコンピュータにて読取り可能な記録媒体に各種の手段を通じて記録できる。
【００５５】
前記コンピュータにて読取り可能な記録媒体はマグネチック貯蔵媒体（例えば、ＲＯＭ、フロッピーディスク、ハードディスクなど）、光学的な判読媒体（例えば、ＣＤ−ＲＯＭ、ＤＶＤなど）及びキャリアウェーブ（例えば、インターネットを介した伝送）などの貯蔵媒体を含む。
以上、本発明についてその好適な実施形態を中心に調べてみた。本発明が属する技術分野における当業者であれば、本発明が本発明の本質的な特性から逸脱しない範囲内において変形された形態にて具現できるということが理解できるであろう。よって、開示された実施形態は限定的な観点ではなく説明的な観点から考慮さるべきである。本発明の範囲は前記詳細な説明ではなく特許請求の範囲上に現れており、それと同等な範囲内にあるあらゆる違いは本発明に含まれたものとして解釈さるべきである。
【００５６】
【発明の効果】
上述したように、本発明は、ＸＭＬにて作成された質疑形式のうち核心的な正規経路式質疑に対してユーザ質疑の形式と無関係にただ一回のジョインにより処理できる方法を提供することにより、デジタルＴＶの電子番組表の情報インデックス及び検索エンジンとそれ以外の様々な分野のＸＭＬ貯蔵が必要な情報機器に有用であるという効果がある。
【００５７】
また、本発明は、ＸＭＬにて作成された文書を関係型データベースに効率良くインデックスして貯蔵することにより、ＸＭＬの核心的なユーザ質疑形式である正規経路式質疑をユーザによる記述形式と無関係に安定的で且つ速く処理できる効果がある。特に、既存の方法はユーザによる質疑の記述形式に依存的であるために性能が不安定であるのに対し、本発明はユーザ質疑形式と無関係にただ一回のジョインにより処理できるという長所を有する。
【図面の簡単な説明】
【図１Ａ】ＴＶ放送システムのメタデータ規格の一部を表わすＸＭＬにて作成された文書の一実施形態の図である。
【図１Ｂ】ＴＶ放送システムのメタデータ規格の一部を表わすＸＭＬにて作成された文書に対するツリー構造を表す図である。
【図２】正規経路式において用いられる主要記号及びその意味を示す図面である。
【図３】Ｅｌｅｍｅｎｔｓ及びＴｅｘｔｓテーブル構造を用いて各エレメントを表わした一実施形態である。
【図４】正規経路式に対するＳＱＬのｌｉｋｅ構文である。
【図５Ａ】入力されたＸＭＬ文書の一実施形態の図である。
【図５Ｂ】本発明のＸＭＬ文書に対する経路ルックアップテーブル構成の一実施形態の図である。
【図５Ｃ】本発明のＸＭＬ文書に対する拡張幹線テーブルの構成の一実施形態の図である。
【図６】本発明の経路インデックスルックアップ方法の構造を示す図面である。
【図７】本発明の正規経路式質疑に関する経路インデックスルックアップ方法のフローチャートである。
【図８】本発明の正規経路式質疑に関する経路インデックスルックアップ装置を示す図面である。
【図９】本発明の実験に用いられた正規経路式テーブルである。
【図１０】本発明の正規経路式のノード数による反応時間グラフである。
【符号の説明】
８１０…経路ルックアップテーブル貯蔵部
８２０…拡張細線テーブル貯蔵部
８３０…経路ＩＤ検索部
８４０…経路情報判断及び出力部
【図１Ａ】
2004030569.tif 000005
【図１Ｂ】
2004030569.tif 000006
【図２】
2004030569.tif 000007
【図３】
2004030569.tif 000008
【図４】
2004030569.tif 000009
【図５Ａ】
2004030569.tif 000010
【図５Ｂ】
2004030569.tif 000011
【図５Ｃ】
2004030569.tif 000012
【図６】
2004030569.tif 000013
【図７】
2004030569.tif 000014
【図８】
2004030569.tif 000015
【図９】
2004030569.tif 000016
【図１０】
2004030569.tif 000017