(57)【要約】  XML文書をインデックス付けするための技術を提供する。一実施例に従うと、XML文書のインデックス付けされた各ノードについて１つの行を記憶するためのPATHテーブルが作成される。ノードのためのPATHテーブル行は、（１）ノードを含むXML文書の位置を特定するための情報と、（２）ノードの経路を識別する情報と、（３）ノードを含むXML文書の階層構造内におけるノードの位置を識別する情報とを含む。ノードが値に関連付けられている場合、当該ノードについてのPATHテーブル行はまた、当該値を含む。PATHテーブルを用いてのXPathクエリへの応答は、２次インデックスによって容易にされる。
2007533008.tif 000002
【特許請求の範囲】
【請求項１】
XML文書からの情報にアクセスするための方法であって、
XML文書内において、インデックス付けすべきノードの組を識別するステップと、
インデックス付けすべきノードの組における各ノードのために、ノードについてのエントリをインデックスに記憶するステップとを含み、所与のノードについてのエントリは、所与のノードに関連付けられるXML内容の位置を特定するための位置データと、
（ａ）所与のノードを含むXML文書内において所与のノードの階層位置を示す階層データ、および、
（ｂ）所与のノードを含むXML文書の構造を介する所与のノードへの経路に対応する経路データ、のうちの少なくとも１つとを含み、前記方法はさらに、
XML文書からの情報についての要求に応答して、インデックスを用いてXML文書内の情報の位置を特定するステップを含む、方法。
【請求項２】
インデックスはリレーショナルテーブルとして実現され、各ノードについてのエントリを記憶するステップは、リレーショナルテーブル内において、ノードの組における各ノードについての行を記憶することによって実行される、請求項１に記載の方法。
【請求項３】
インデックスは、ノードの組における１つ以上のノードに関連付けられる値を記憶する、請求項１に記載の方法。
【請求項４】
前記インデックスに記憶される値は、複数のデータ型の値を含み、前記方法は、前記複数のデータ型のうちの２つ以上のデータ型の各々についての２次インデックスを構築するステップをさらに含む、請求項３に記載の方法。
【請求項５】
所与のノードについての位置データは、XML文書の位置を特定するための第１のデータと、XML文書内において、所与のノードに関連付けられる情報の位置を特定するための第２のデータとを含む、請求項１に記載の方法。
【請求項６】
所与のノードについてのエントリは、所与のノードを含むXML文書内において所与のノードの階層位置を示す階層データを含み、
前記方法は、前記階層データに基づいて、前記インデックスにおけるエントリにアクセスするための２次インデックスを構築するステップをさらに含む、請求項１に記載の方法。
【請求項７】
所与のノードについてのエントリは、所与のノードを含むXML文書の構造を介する所与のノードへの経路に対応する経路データを含み、
前記方法はさらに、前記経路データに基づいて、前記インデックスにおけるエントリにアクセスするための２次インデックスを構築するステップを含む、請求項１に記載の方法。
【請求項８】
親ノードの子ノードに関連付けられる階層情報に基づいて、前記インデックスにおいて、前記親ノードについてのエントリにアクセスするための２次インデックスを構築するステップをさらに含む、請求項１に記載の方法。
【請求項９】
インデックス付けすべきノードの組を識別するステップは、
どの経路がインデックス付けされるべきであるかを決定するためのルールを受信するステップと、
インデックス付けされるべきXML文書におけるノードに関連付けられる経路を決定するステップと、
（ａ）どの経路がインデックス付けされるべきであるかを決定するためのルール、および、（ｂ）インデックス付けされるべきXML文書におけるノードに関連付けられる経路に基づいて、どのノードがインデックス付けされるべきであるかを識別するステップとを含む、請求項１に記載の方法。
【請求項１０】
ルールは、インデックスに含まれるべき経路を明示的に識別する、請求項９に記載の方法。
【請求項１１】
ルールは、インデックスから除外すべき経路を明示的に識別する、請求項９に記載の方法。
【請求項１２】
２次値インデックスが構築されるべきデータ型を示すユーザデータを受信するステップをさらに含む、請求項４に記載の方法。
【請求項１３】
１つ以上のプロセッサによって実行されるときに、１つ以上のプロセッサに請求項１に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能媒体。
【請求項１４】
１つ以上のプロセッサによって実行されるときに、１つ以上のプロセッサに請求項２に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能媒体。
【請求項１５】
１つ以上のプロセッサによって実行されるときに、１つ以上のプロセッサに請求項３に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能媒体。
【請求項１６】
１つ以上のプロセッサによって実行されるときに、１つ以上のプロセッサに請求項４に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能媒体。
【請求項１７】
１つ以上のプロセッサによって実行されるときに、１つ以上のプロセッサに請求項５に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能媒体。
【請求項１８】
１つ以上のプロセッサによって実行されるときに、１つ以上のプロセッサに請求項６に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能媒体。
【請求項１９】
１つ以上のプロセッサによって実行されるときに、１つ以上のプロセッサに請求項７に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能媒体。
【請求項２０】
１つ以上のプロセッサによって実行されるときに、１つ以上のプロセッサに請求項８に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能媒体。
【請求項２１】
１つ以上のプロセッサによって実行されるときに、１つ以上のプロセッサに請求項９に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能媒体。
【請求項２２】
１つ以上のプロセッサによって実行されるときに、１つ以上のプロセッサに請求項１０に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能媒体。
【請求項２３】
１つ以上のプロセッサによって実行されるときに、１つ以上のプロセッサに請求項１１に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能媒体。
【請求項２４】
１つ以上のプロセッサによって実行されるときに、１つ以上のプロセッサに請求項１２に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
優先権主張
本願は、２００４年４月９日に出願され「さまざまな記憶フォーマットで記憶されたXMLデータについてのXMLインデックス（“XML INDEX FOR XML DATA STORED IN VARIOUS STORAGE FORMATS”）」と題された米国仮特許出願連続番号第６０／５６０，９２７号と、２００４年６月１６日に出願され「さまざまな記憶フォーマットで記憶されたXMLデータについてのXMLインデックス（“XML INDEX FOR XML DATA STORED IN VARIOUS STORAGE FORMATS”）」と題された米国仮特許出願番号第６０／５８０，４４５号との優先権を主張し、その内容全体が、あらゆる目的で引用によりこの明細書中に援用されている。
【０００２】
発明の分野
この発明は情報の管理に関し、より具体的には、XML文書に含まれる情報へのアクセスに関する。
【背景技術】
【０００３】
背景
近年、拡張可能なマークアップ言語データ（「XMLデータ」）の記憶およびクエリを可能にする多くのデータベースシステムが存在する。XMLへのクエリための多くの規格が発展してきているが、それらはすべて、XPathの変形例をいくつか含む。しかしながら、データベースシステムは、通常、XPathクエリに対応するよう最適化されておらず、データベースシステムのクエリ性能には改善の余地が大いにある。XMLスキーマ定義が利用可能であり得る特定の場合には、XMLインスタンス文書において用いられる構造およびデータ型（datatype）は既知であり得る。しかしながら、XMLスキーマ定義が利用可能ではなく、探索すべき文書がいかなるスキーマにも準拠していない場合、XPathを用いるクエリのための効率的な技術は存在しない。
【０００４】
いくつかのデータベースシステムは、アドホック機構を用いて、文書のスキーマが未知である文書に対して実行されるXPathクエリを満たし得る。たとえば、データベースシステムは、すべての文書のフルスキャンを実行することによってXPathクエリを満たし得る。すべての文書のフルスキャンを用いてすべてのXPathクエリを満たすことができるが、インデックスが不足しているので、それは非常にゆっくりと実現されることとなる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
XPathクエリを満たす別の方法には、テキストキーワードの使用が含まれる。具体的には、多くのデータベースシステムがテキストインデックスをサポートし、これらは、ある一定のXPathを満たすのに用いられ得る。しかしながら、この技術は、XPathクエリの小さなサブセットしか満たすことができない。このため、既存のデータベースシステムには、多種多様なXPathクエリに対処するのに用いることのできる有効なインデックス付け技術がなかった。
【０００６】
この段落に記載される方策は追求可能な方策であるが、必ずしもこれまでに構想または追求された方策であるとは限らない。したがって、特に指定のない限り、この段落に記載されている方策のいずれも、単にこの段落に含まれているというだけで先行技術であると見なされるべきではない。
【０００７】
この発明は、同様の参照番号が同様の要素を指している添付の図面の図において、限定
ではなく例示のために説明される。
【発明を実施するための最良の形態】
【０００８】
詳細な説明
以下の記載においては、説明する目的で、この発明のさまざまな実施例を完全に理解させるために多数の具体的な詳細が述べられている。しかしながら、この発明がこれらの具体的な詳細なしに実施可能であることが認識されるだろう。他の場合には、この発明を不必要に曖昧にすることを避けるために、周知の構造および装置はブロック図の形で示されている。
【０００９】
機能概要
XML文書における経路、値および順序の情報にインデックス付けするための機構が提供される。当該機構は、実際のXMLデータを記憶するのに用いられるフォーマットおよびデータ構造（「ベース構造」）に係らず、用いることができる。たとえば、実際のXMLデータは、データベースの内部または外部の構造において、CLOB（実際のXMLテキストを記憶するキャラクタLOB）、O-R（XMLスキーマがある状態でのオブジェクトリレーショナル構造化形式）、または、BLOB（XMLの何らかのバイナリ形式を記憶するバイナリLOB）などのいかなる形式でも存在し得る。
【００１０】
ここで説明される技術は、インデックスを集合的に構成しXMLデータにアクセスするための１組の構造の使用を含む。一実施例に従うと、（この明細書中で「XMLインデックス」と称される）インデックスは３つの論理構造、すなわち、経路インデックス、順序インデックスおよび値インデックス、を含む。一実施例においては、３つの論理構造はすべて、この明細書においてPATH_TABLEと称される単一のテーブルに存在する。
【００１１】
XPathクエリ言語のうち最も一般的に用いられる部分は、値に基づいたナビゲーション（親−子−子孫）アクセスおよびプレディケイトを含む。後により詳細に説明されるように、経路、値および順序の情報を追跡することにより、XMLインデックスを用いてこれらのアクセス方法をともに有効に満たすことができる。加えて、XMLインデックスの実施例がいかに実現されるかに応じて、XMLインデックスを用いることにより結果として以下の利点のうちの１つ以上が得られる。すなわち、（１）XPathベースのクエリの探索性能の向上。これは、経路適合ならびに値（value）プレディケイトを含む。（２）フラグメントがXPath表現によって識別される場合のフラグメント抽出の処理。（３）適切なXMLスキーマ定義がある状態での、値プレディケイトに関するデータ型認識。（４）新しい定義を追加することによってXMLスキーマおよびXMLインデックスを発展させる能力に対するサポート。（５）子および子孫の軸、ならびに同等性および範囲のプレディケイトを含む大きなクラスのXPath表現の処理。（６）経路またはネーム空間の特定された組を含むかまたはインデックスから除外することによって、インデックス付けされた経路の組を制御するユーザの能力。これは、フォーマッティングなどに関するタグがインデックスから省かれている文書向きのシナリオにおいて特に有用である。（７）インデックスに記憶される実際のテキスト値のカスタマイゼーションの可能化。たとえば、余白が取除かれており、大文字小文字の区別なし。（８）インデックスの大容量負荷および並行したインデックス作成のためのサポートについての良好な性能。
【００１２】
XML文書の例
説明の目的で、以後、以下の２つのXML文書を参照して例を挙げる。
【００１３】
【数１】
2007533008.tif 000003
【００１４】
上述のとおり、po1.xmlおよびpo2.xmlは、単にXML文書の２つの例に過ぎない。ここに記載される技術は、いかなる特定の種類、構造または内容を有するXML文書にも限定されない。このような文書がこの発明のさまざまな実施例に従っていかにインデックス付けされ、アクセスされるかについての例を以下に挙げる。
【００１５】
XMLインデックス
一実施例に従うと、XMLインデックスは、Xpathベースのプレディケイトおよび／またはXpathベースのフラグメント抽出を含むクエリの性能を向上させるドメインインデックスである。XMLインデックスは、たとえば、CLOBまたは構造化されたストレージとして記憶されるXMLスキーマベースの列とスキーマのないXMLタイプの列との両方にわたって構築され得る。一実施例においては、XMLインデックスは、経路インデックス、値インデックスおよび順序インデックスを協働的に使用することに起因する論理インデックスである。
【００１６】
経路インデックスは、単純な（ナビゲーション）経路表現に基づいてフラグメントをルックアップする機構を提供する。値インデックスは、値の同等性または範囲に基づいたルックアップを提供する。複数の２次値インデックスが、各データ型に１つずつ存在し得る。順序インデックスは、階層的な順序情報をインデックス付けされたノードに関連付ける。順序インデックスは、XMLノード間における親−子、祖先−子孫および兄弟関係を決定
するのに用いられる。
【００１７】
ユーザが（プレディケイトまたはフラグメント識別子として）XPathを含むクエリを発信すると、ユーザXPathは、XMLインデックステーブルにアクセスするSQLクエリに分解される。生成されたクエリは、典型的には、一組の経路、値および順序の制約付きルックアップを実行して、それらの結果を適切にマージする。
【００１８】
経路テーブル
一実施例に従うと、論理的なXMLインデックスはPATHテーブルと２次インデックスの組とを含む。上述のとおり、インデックス付けされたXML文書は各々、多くのインデックス付けされたノードを含み得る。PATHテーブルはインデックス付けされたノードごとに１つの行を含む。各々のインデックス付けされたノードについて、ノードに対するPATHテーブル行は、当該ノードに関連付けられるさまざまな情報を含む。
【００１９】
一実施例に従うと、Pathテーブルに含まれる情報は、（１）ノードへの経路を示すPATHIDと、（２）ベース構造内におけるノードについてのフラグメントデータの位置を特定するための「位置データ」と、（３）ノードを含むXML文書の構造階層内におけるノードの位置を示す「階層データ」とを含む。随意には、PATHテーブルはまた、値に関連付けられるこれらのノードについての値情報を含み得る。これらの種類の情報の各々が、以下により詳細に説明される。
【００２０】
経路
XML文書の構造は、XML文書内のノード間における親−子関係を確立する。XML文書におけるノードについての「経路」は、特定のノードに到達するよう、「ルート」ノードから始まる一連の親−子リンクを反映する。たとえば、po2.xmlにおける「User」ノードへの経路は、/PurchaseOrder/Actions/Acthon/Userである。というのも、「User」ノードは「Action」ノードの子であり、「Action」ノードは「Actions」ノードの子であり、「Actions」ノードは「PurchaseOrder」ノードの子であるからである。
【００２１】
XMLインデックスがインデックス付けするXML文書の組は、この明細書中においては「インデックス付けされたXML文書」と称される。一実施例に従うと、XMLインデックスは、すべてのインデックス付けされたXML文書内における経路のすべて、または、インデックス付けされたXML文書内における経路のサブセットにおいて構築され得る。どの経路がインデックスであるかを特定するための技術が以下に説明される。特定のXMLインデックスによってインデックス付けされる経路の組は、この明細書中において「インデックス付けされたXML経路」と称される。
【００２２】
経路ID
一実施例に従うと、インデックス付けされたXML経路の各々には固有の経路ＩＤが割当てられている。たとえば、po1.xmlおよびpo2.xmlに存在する経路には、以下のテーブルに示されるとおりに経路ＩＤが割当てられてもよい。
【００２３】
【表１】
2007533008.tif 000004
【００２４】
経路を識別し、経路ＩＤを経路に割当てるのにさまざまな技術を用いることができる。たとえば、ユーザは、明示的に経路を列挙し、こうして識別される経路についての対応する経路ＩＤを特定し得る。代替的には、データベースサーバは、各々のXML文書を、それがインデックス付けされたXML文書の組に追加されると解析（parse）し得る。解析動作中、データベースサーバは、経路ＩＤがまだ割当てられていない経路をいずれも識別し、それらの経路に自動的に新しい経路ＩＤを割当てる。経路ＩＤ対経路（pathid-to-path）マッピングは、さまざまな方法でデータベース内に記憶され得る。一実施例に従うと、pathid-to-pathマッピングは、XMLインデックス自体とは別個のメタデータとして記憶される。
【００２５】
一実施例に従うと、異なるスキーマに準拠するXML文書のために同じアクセス構造が用いられる。インデックス付けされたXML文書が異なるスキーマに準拠し得るので、各々のXML文書は、典型的には、経路ＩＤ（pathid）が割当てられている経路のサブセットしか含まないだろう。
【００２６】
位置データ
ノードに関連付けられる位置データは、ノードを含むXML文書がベース構造内のどこに存在するかを示す。こうして、位置データの性質は、ベース構造の性質に基づいて実現例ごとに異なることとなる。実際のXML文書がどのように記憶されるかに応じて、位置データはまた、XML文書を指すロケータまたは論理ポインタを含み得る。論理ポインタは、XPathによって識別されるノードに関連付けられるフラグメントを抽出するのに用いられてもよい。
【００２７】
説明の目的で、（１）ベース構造がリレーショナルデータベース内のテーブルであり、（２）各々のインデックス付けされたXML文書がベーステーブルの対応する行に記憶されるものとする。このような文脈においては、ノードについての位置データは、たとえば、（１）ノードを含むXML文書が記憶されるベーステーブル内における行の行ＩＤ（rowid）と、（２）ノードに対応し、XML文書内においてフラグメントデータへの高速アクセスをもたらすロケータとを含み得る。
【００２８】
階層データ
ノードについてのPATHテーブル行はまた、ノードが、当該ノードを含むXML文書の階層構造内のどこに存在するかを示す情報を含む。このような階層的な情報は、この明細書中においてはノードの「順序キー（OrderKey）」と称される。
【００２９】
一実施例に従うと、階層的な順序情報は、デューイ（Dewey）タイプの値を用いて表わされる。具体的には、一実施例においては、ノードのOrderKeyは、ノードの直接の親のOrderKeyに値を付加することによって作成され、この場合、付加された値は、親ノードの子の中でも、その特定の子ノードの位置を示す。
【００３０】
たとえば、特定のノードＤがノードＣの子であり、それ自体が、ノードＡの子であるノードＢの子であると想定する。さらに、ノードＤがOrderKey１．２．４．３を有するものとする。OrderKeyにおける最後の「３」は、ノードＤがその親ノードＣの３番目の子であることを示す。同様に、４は、ノードＣがノードＢの４番目の子であることを示す。２は、ノードＢがノードＡの２番目の子であることを示す。先頭の１は、ノードＡがルートノードである（すなわち、親を持たない）ことを示す。
【００３１】
上述のとおり、子のOrderKeyは、子の番号に対応する値を親のOrderKeyに付加することによって容易に作成され得る。同様に、親のOrderKeyは、子のOrderKeyにおける最後の番号を取除くことによって子のOrderKeyから容易に得られる。
【００３２】
一実施例に従うと、各々のOrderKeyによって表わされる合成数が、バイト比較可能値に変換され、このため、２つのOrderKey間における数学的比較により、XML文書の構造階層内における、OrderKeyが対応するノードの相対位置が示される。
【００３３】
たとえば、OrderKey１．２．７．７に関連付けられるノードは、XML文書の階層構造におけるOrderKey１．３．１に関連付けられるノードの前にくる。こうして、データベースサーバは変換機構を用いて、OrderKey１．２．７．７を第１の値に変換し、OrderKey１．３．１を第２の値に変換するが、この場合、第１の値は第２の値未満となる。第２の値を第１の値と比較することにより、データベースサーバは、第１の値に関連付けられるノードが第２の値に関連付けられるノードの前にくると容易に判断することができる。さまざまな変換技術を用いてこの結果を達成することができ、この発明は特定のいかなる変換技術にも限定されない。
【００３４】
値情報
インデックス付けされた文書内におけるいくつかのノードは、属性ノードであり得るか、または、単純要素に対応するノードであり得る。一実施例に従うと、属性ノードおよび単純要素については、PATHテーブル行はまた、属性および要素の実効値を記憶する。このような値は、たとえば、PATHテーブルの「値列」に記憶され得る。後により詳細に説明される２次「値インデックス」は、値列上に構築される。
【００３５】
経路テーブルの例
一実施例に従うと、PATHテーブルは、以下のテーブルにおいて特定されるように規定される列を含む。
【００３６】
【表２】
2007533008.tif 000005
【００３７】
上述のとおり、PATHIDはノードに割当てられた番号であり、ノードにまで十分に拡張された経路を固有に表わす。ORDER_KEYは、ノードに関連付けられるDEWEY順序番号のシステム表現である。一実施例に従うと、順序キー（order key）の内部表現はまた、文書の順序付けを保存する。
【００３８】
VALUE列は、単純要素（すなわち要素子のない）ノードおよび属性ノードについての有効なテキスト値を記憶する。一実施例に従うと、連結によって、隣接するテキストノードを合体させる。以下により詳細に説明されるように、たとえば、混合したテキストの挙動、余白、大文字小文字の区別あり等がカスタマイズされ得るオプションをインデックス作成中に特定することにより、VALUE列に記憶された有効なテキスト値をユーザがカスタマイズすることを可能にする機構が提供される。ユーザは、有界のRAW列またはBLOBを含むVALUE列を任意の数のフォーマットに記憶することができる。ユーザが有界のストレージを選択する場合、インデックス作成中のいかなるオーバーフローもエラーとしてフラグが立てられる。
【００３９】
以下のテーブルは、（１）上述の列を有し、（２）po1.xmlおよびpo2.xmlについてのエントリが格納されるPATHテーブルの一例である。具体的には、PATHテーブルの各行は、po1.xmlまたはpo2.xmlのインデックス付けされたノードに対応する。この例においては、po1.xmlおよびpo2.xmlは、ベーステーブルの行Ｒ１および行Ｒ２にそれぞれ記憶されるものとする。
【００４０】
【表３】
2007533008.tif 000006
【００４１】
この例においては、rowid列は、PATHテーブルの各行についての固有の識別子を記憶する。PATHテーブルが作成されるデータベースシステムに応じて、rowid列は暗示的な列になる可能性がある。たとえば、行のディスク位置は、当該行についての固有の識別子として用いられてもよい。以下により詳細に説明されるように、２次順序および値インデックスは、PATHテーブルのrowid値を用いてPATHテーブル内の行の位置を特定し得る。
【００４２】
上述の実施例においては、ノードのPATHID、ORDERKEYおよびVALUEはすべて単一のテーブルに含まれる。代替的な実施例においては、別個のテーブルを用いて、PATHID、ORDERKEYおよびVALUE情報を、対応する位置データ（たとえば、ベーステーブルRidおよびロケータ（Locator））にマップし得る。
【００４３】
２次インデックス
PATHテーブルは、広範囲のクエリを満たすXML文書またはXMLフラグメントの位置を特定するのに必要な情報を含む。しかしながら、二次的なアクセス構造がない場合、PATHテーブルを用いてこのようなクエリを満たすには、しばしばPATHテーブルのフルスキャンが必要になる。したがって、一実施例に従うと、さまざまな２次インデックスが、（１）経路ルックアップの実行および／または（２）順序ベースの関係の識別、を行うクエリを加速するようデータベースサーバによって作成される。一実施例に従うと、以下の２次インデックスはPATHテーブル上で作成される。
【００４４】
・  （pathid，rid）上のPATHID_INDEX
・  （rid，order_key）上のORDERKEY_INDEX
・  VALUE INDEXES
・  （rid，SYS_DEWEY_PARENT（order_key））上のPARENT_ORDERKEY_INDEX
PATHID_INDEX
PATHID_INDEXは、PATHテーブルのpathid，rid列上に構築される。こうして、PATHID_INDEXにおけるエントリは（keyvalue，rowid）の形であり、この場合、キー値（keyvalue）は、特定のpathid/ridの組合せを表わす合成値であり、rowidはPATHテーブルの特定の行を識別する。
【００４５】
（１）  ベーステーブル行および（２）ノードのpathidが既知である場合、PATHID_INDEXを用いて、PATHテーブル内における当該ノードについての行の位置を迅速に特定することができる。たとえば、キー値「３．Ｒ１」に基づいて、PATHID_INDEXをトラバースして、キー値「３．Ｒ１」に関連付けられるエントリを見出し得る。PATHテーブルが上述のとおり格納されると想定すると、インデックスエントリは３のrowid値を有することとなる。３のrowid値は、pathid３およびrid Ｒ１に関連付けられるノードについての行である、PATHテーブルの３番目の行を指す。
【００４６】
ORDERKEY_INDEX
ORDERKEY_INDEXは、PATHテーブルのridおよびorderkeyの列上に構築される。こうして、ORDERKEY_INDEXにおけるエントリは、（keyvalue, rowid）の形であり、この場合、keyvalueは、特定のrid/orderkeyの組合せを表わす合成値であり、rowidはPATHテーブルの特定の行を識別する。
【００４７】
（１）  ベーステーブル行および（２）ノードのorderkeyが既知である場合、ORDERKEY_INDEXを用いて、PATHテーブル内における当該ノードについての行の位置を迅速に特定することができる。たとえば、キー値「Ｒ１．′１．２′」に基づいて、ORDERKEY_INDEXをトラバースして、キー値「Ｒ１．′１．２′」に関連付けられるエントリを見出し得る。PATHテーブルが上述のとおり格納されると想定すると、インデックスエントリは３のrowid値を有することとなる。３のrowid値は、orderkey１．２およびrid Ｒ１に関連付けられるノードについての行である、PATHテーブルの３番目の行を指す。
【００４８】
値インデックス
経路ルックアップに基づいたクエリがPATHID_INDEXを用いて加速され得ると、値ルックアップに基づいたクエリが、PATHテーブルの値列上に構築されたインデックスによって加速され得る。しかしながら、PATHテーブルの値列は、さまざまなデータ型についての値を保持し得る。したがって、一実施例に従うと、別個の値インデックスが、値列に記憶された各データ型に対して構築される。こうして、値列がストリング、番号およびタイムスタンプを保持する実現例においては、以下の値（２次）インデックスも作成される。
【００４９】
・  SYS_XMLVALUE_TO_STRING(value)上のSTRING_INDEX
・  SYS_XMLVALUE_TO_NUMBER(value)上のNUMBER_INDEX
・  SYS_XMLVALUE_TO_TIMESTAMP(value)上のTIMESTAMP_INDEX
これらの値インデックスを用いて、データ型をベースにした比較（同等性および範囲）を実行する。たとえば、NUMBER値インデックスは、ユーザXpath内における番号ベースの比較に対処するのに用いられる。NUMBER_INDEXにおけるエントリは、たとえば（number、rowid）の形であってもよく、この場合、rowidは、「number」の値に関連付けられるノードについての、PATHテーブル内の行を指す。同様に、STRING_INDEX内におけるエントリは（string，rowid）の形を有してもよく、TIMESTAMP_INDEX内におけるエントリは（timestamp，rowid）の形を有してもよい。
【００５０】
PATHテーブルにおける値のフォーマットは、データ型の本来のフォーマットに対応していない可能性がある。したがって、値インデックスを用いる場合、データベースサーバは、変換機能を呼出して、値バイトを、記憶されたフォーマットから特定されたデータ型に変換し得る。加えて、データベースサーバは、以下に説明されるように、必要な変換をい
ずれも適用する。一実施例に従うと、変換機能は、当該変換が可能でない場合、RAWおよびBLOBの値で動作し、NULLを戻す。
【００５１】
デフォルトにより、値インデックスは、XMLインデックスが作成される際に作成される。しかしながら、ユーザは、クエリ作業負荷の知識に基づいて値インデックスのうちの１つ以上の作成を抑制し得る。たとえば、すべてのXPathプレディケイトがストリング比較しか含まない場合、NUMBERおよびTIMESTAMPの値インデックスを回避することができる。
【００５２】
PARENT_ORDERKEY_INDEX
一実施例に従うと、PATHテーブル上に構築された２次インデックスの組は、PARENT_ORDERKEY_INDEXを含む。ORDER_KEYインデックスと同様に、PARENT_ORDERKEY_INDEXは、PATHテーブルのridおよびorder_keyの列上に構築される。結果として、PARENT_ORDERKEY_INDEXのインデックスエントリは（keyvalue，rowid）の形を有し、この場合、keyvalueは、特定のrid／order_keyの組合せに対応する合成値である。しかしながら、ORDER_KEYインデックスとは異なり、PARENT_ORDERKEY_INDEXエントリにおけるrowidは、特定のrid／order_keyの組合せを有するPATHテーブル行を指さない。むしろ、各々のPARENT_ORDERKEY_INDEXエントリのrowidは、rid／order_keyの組合せに関連付けられるノードの直接の親であるノードのPATHテーブル行を指す。
【００５３】
たとえば、上述の格納されたPATHテーブルにおいては、rid／order_keyの組合せ「Ｒ１．′１．２′」は、PATHテーブルの行３におけるノードに対応する。PATHテーブルの行３におけるノードの直接の親は、PATHテーブルの行１によって表わされるノードである。結果として、「Ｒ１．′１．２′」のキー値に関連付けられるPARENT_ORDERKEY_INDEXエントリは、PATHテーブルの行１を指すrowidを有することとなる。
【００５４】
XMLインデックスの作成
一実施例に従うと、XMLインデックスは、データベースサーバによって受信されるインデックス作成コマンドに応答してデータベース内に作成される。説明する目的で、XMLインデックスの作成は、インデックス付けされるべきXML文書がリレーショナルテーブルのXMLタイプ列に記憶される文脈において説明される。
【００５５】
たとえば、ベース構造が、ｉｄ列によって識別されるXMLタイプとしてスタイルシートを記憶するテーブルstylesheet_tabであると想定する。このようなテーブルは、たとえば、コマンド：
【００５６】
【数２】
2007533008.tif 000007
【００５７】
を用いて作成され得る。
XMLインデックスは、XPathプレディケイトを含むクエリと、Xpathに基づいたフラグメントの検索とを加速するよう、stylesheet_tabのスタイルシート（stylesheet）上で作成され得る。一実施例に従うと、このようなXMLインデックスは、以下のコマンド：
【００５８】
【数３】
2007533008.tif 000008
【００５９】
を用いて作成され得る。
以下のコマンドは、XMLインデックスがスキーマベースのXMLタイプでいかに作成され得るかを示す一例である。
【００６０】
【数４】
2007533008.tif 000009
【００６１】
上述のコマンドは、単に、データベースサーバにXMLインデックスを作成させるようにするために当該データベースサーバに提示され得るコマンドの例にすぎない。ここに記載される技術は、インデックスの作成を指定するためのいかなる形またはシンタックスにも限定されない。
【００６２】
一実施例に従うと、インデックス作成コマンドは、XMLインデックスのさまざまな特徴をユーザが特定することを可能にするパラメータを含み、たとえば以下のとおりである。
【００６３】
・  どの経路を含むべきか、またはインデックス付けされた経路の組からどの経路を除くべきか
・  PATHテーブルおよび２次インデックスの名前
・  PATHテーブルおよび２次インデックスについての記憶オプション（たとえば、PATHテーブルが分割されたテーブル、インデックス組織化テーブルなどとして記憶されるべきであるかどうか）
・  値を処理するためのルール
・  値列の列タイプ（たとえば、RAWまたはBLOB）
値を処理するためのルールは、たとえば、値が大文字小文字の区別ありとして扱われるべきであるかどうか、値が標準化されるべきであるかどうか（その場合、標準化がいかに実行されるべきであるかどうか）、ならびに、混合された内容ノード（値および子ノードをともに有するノード）についての値をいかに処理するか、を特定し得る。混合された内容ノードに関して、当該ルールは、たとえば、混合された内容ノードに関連付けられる値が無視されるべきであるか、連結されるべきであるか、または特別に取扱われるべきであることを特定し得る。これらは、単に、ユーザによって特定され得るルールに対応する値の例にすぎない。利用可能なルールの組は実現例によって異なり、さらには、含まれる値のタイプに基づいて異なり得る。
【００６４】
ユーザがXMLインデックスを作成すると、基礎をなすPATHテーブルおよび２次インデックスが自動的に作成される。デフォルトにより、PATHテーブルおよび２次インデックスの名前は、XMLインデックスの名前に基づいてシステムによって生成される。しかしながら、ユーザは、これらのオブジェクトの名前を明示的に特定することができる。
【００６５】
デフォルトにより、PATHテーブルおよび２次インデックスについての記憶オプションは、XMLインデックスが作成されるベーステーブルの記憶特性から得られる。しかしながら、ユーザはまた、これらのオブジェクトについての記憶特性を明示的に特定することができる。
【００６６】
以下の例は、番号インデックスがPATHテーブルとは別個のテーブル空間においていかに作成されるかを説明する。
【００６７】
【数５】
2007533008.tif 000010
【００６８】
どの経路にインデックス付けすべきかについてのユーザ選択
一実施例に従うと、XMLインデックスによってどのXML経路がインデックス付けされるべきかを決定するルールをユーザが特定することのできる機構が提供される。具体的には、ユーザは、あるXML経路を明確に含むルール、および／または、あるXML経路を明確に除外するルールを記録し得る。
【００６９】
一実施例に従うと、ユーザがXMLインデックスを作成すると、デフォルトにより、ベース文書におけるすべてのノードがインデックス付けされる（すなわち、当該文書におけるすべてのノードに対応するPATHテーブルに行が存在する）。しかしながら、ユーザは、インデックス付けすべきノードの組（サブツリー）を明示的に特定することができ、これにより、PATHテーブルから残りのノードを省き得る。これは、典型的には、クエリの観点からすれば無用であることが分かっているフラグメントを除外するのに用いられる。インデックス付けされたノードの数を減らすことにより、XMLインデックスの空間使用および管理効率を向上させることができる。
【００７０】
一実施例に従うと、XMLインデックスが作成されたときにルールの最初の記録が行われてもよい。たとえば、インデックス付けされるべき文書がPurchaseOrderテーブルに記憶されるものとする。ユーザがLineitem要素およびそれらの子、ならびに発注基準番号および要求側すべてにインデックス付けしたいと望む場合、以下の作成インデックス（Create
Index）DDLが発行され得る。
【００７１】
【数６】
2007533008.tif 000011
【００７２】
この例においては、POIndex_path_tableは、インデックスデータを記憶するのにドメインインデックスによって用いられるテーブルの名前を示す。前述の例においては、ルールは明確に何らかの経路を含む。当該ルールによって明確に含まれない経路はすべて、インデックスから除かれる。rule/PurchaseOrder/LineItems//*は、ワイルドカード記号「*」を含む。結果として、当該ルールは、path/PurchaseOrder/LineItemsと、path/PurchaseOrder/LineItemsから派生するすべてのノードへの経路とを明確に含む。これは、単に、当該ルールにおいてワイルドカードをいかに用い得るかを示す一例にすぎない。一実施例に従うと、経路選択ルール機構は、いくつの文脈においてもワイルドカードをサポートする。たとえば、rule/nodex/*/nodey/nodezは、nodexとnodey/nodezとの間の経路にかかわらず、（１）/nodex/から派生し、（２）/nodey/nodezにおいて終端するすべての経路を選択する。
【００７３】
ユーザはまた、経路を明確に除外するルールを特定し得る。たとえば、Lineitem記述およびpurchaseOrder動作を除いて文書の経路すべてにインデックス付けするために、以下の作成インデックス（Create Index）DDLを用いてインデックスを作成する。
【００７４】
【数７】
2007533008.tif 000012
【００７５】
インデックス付けされた文書の組への文書の追加
新しいXML文書がインデックス付けされる必要がある場合、経路、順序および値の情報が集められ、XMLインデックスに記憶される。一実施例に従うと、インデックス付けされたXML文書のリポジトリにXML文書が追加されると、新しいXML文書が、その中に含まれるノードへの経路を識別するよう解析される。新しいXML文書内のノードのための経路が識別されると、データベースサーバは、新しいXML文書に含まれるノードのうちのどれがインデックス付けされるべきかを決定する。次いで、データベースサーバは、それらのノードの各々に基づいてXMLインデックスを更新する。
【００７６】
図１を参照すると、この発明の一実施例に従って新しいXML文書がいかに処理されるかを示すフローチャートが示される。図１においては、ステップ１０２および１０８では、新しいXML文書内の各ノードが処理される間にループを規定する。具体的には、ステップ１０２では、予め処理されていないノードが選択される。最初の繰返し中に、処理のために選択された第１のノードが新しいXML文書のルートノードとなるだろう。
【００７７】
ステップ１０４では、データベースサーバが、現在選択されているノードの経路を決定する。ステップ１０６では、データベースサーバは、当該経路に基づいて、現在選択されているノードがインデックス付けされるべきであるかどうかを決定する。具体的には、ユーザが、インデックス付けされるべき経路のサブセットを特定していた場合、インデックスエントリは、経路の特定されたサブセットに対応するノードに対してのみ追加される。一実施例に従うと、ステップ１０６は、経路選択ルールに対して、現在のノードに関連付けられる経路を適合させて、現在のノードがインデックス付けされるべきかどうかチェックするステップを含む。（１）どの経路が含まれるべきかを示すルールをユーザが記録しており、（２）現在のノードに関連付けられる経路が、ユーザによって特定された経路のいずれにも適合しない場合、ノードをルートとするサブツリー（フラグメント）がインデックスから省かれる。一方では、（１）どの経路がインデックス付けから除外されるべきかを当該ルールが特定し、（２）当該ノードが、ユーザによって特定された除外すべき経路のいずれにも適合する場合、当該ノードをルートとするフラグメントがインデックスから省かれる。適合動作は、たとえば、有限オートマトンを用いて実行されてもよい。
【００７８】
選択されたノードが、インデックス付けされるべき経路に関連付けられていないとステップ１０６において判断された場合、制御がステップ１０８に渡る。ステップ１０８では、データベースサーバは、新しいXML文書が処理すべきノードをそれ以上有しているかどうか判断する。新しいXML文書が、処理すべきノードをそれ以上有していない場合、XMLインデックスを更新するプロセスが完了する。そうではなく、新しいXML文書が、処理すべきより多くのノードを有していた場合、制御がステップ１０２に戻り、別のノードが処理される。
【００７９】
ステップ１０６において、現在のノードがインデックス付けされるべきであると判断された場合、当該ノードをルートとするフラグメントがインデックスに追加される。加えて、そのすべての祖先（ルートまでの要素ノード）もインデックスに追加される。最後に、祖先要素ノード内におけるいかなるネーム空間属性も、インデックスに追加される。
【００８０】
インデックス付けされるべきノードを処理する動作が、図１においてより具体的に示される。ここで、ステップ１１０では、現在のノードに関連付けられる経路にPATHIDが割当てられているかどうか判断される。正確な経路が予めインデックス付けされたXML文書に存在していなかった場合、当該経路にはPATHIDが割当てられていないかもしれない。このような状況下では、制御がステップ１１２に渡され、ここで、PATHIDが当該経路に割当てられる。次いで、新しいpathid-to-pathマッピングがデータベース内に記憶される。
【００８１】
ステップ１１４では、現在のノードについての情報を含む行がPATHテーブルに追加される。ステップ１１６では、PATHID、OrderKeyおよびPARENT_OrderKeyのインデックスが現在のノードのためのエントリで更新される。上述のとおり、PATHIDおよびOrderKeyのエントリは現在のノードのための新しい行を指し、PARENT_OrderKeyエントリは、現在のノードの親のためのPATHテーブル行を指すだろう。
【００８２】
ステップ１１８では、現在のノードが値に関連付けられているかどうかが判断される。現在のノードが値に関連付けられていない場合、制御はステップ１０８に戻される。現在のノードが値に関連付けられており、値インデックスが値のデータ型のために作成されていた場合、ステップ１２０において、インデックスエントリが、その特定のデータ型に関連付けられる値インデックスに追加される。次いで、制御がステップ１０８に戻される。
【００８３】
一実施例に従うと、ノードが、インデックス付けされるべきでない経路に関連付けられていても、当該ノードが、インデックス付けされるいずれかのノードの祖先であればインデックス付けされる。こうして、/a/b/c/*に適合する経路だけが含まれるべきであるとユ
ーザが指定したとしても、経路/a、/a/bおよび/a/b/cに関連付けられるノードはまた、それらが、パターン/a/b/c/*に適合する経路に関連付けられるいずれかのノードの祖先である限り、インデックス付けされることとなる。
【００８４】
XMLインデックスの変更
一実施例に従うと、インデックスが作成された後にXMLインデックスの特徴を変更するための機構が提供される。XMLインデックスの作成後の変更は、たとえば、変更インデックスステートメントに応答して実行されてもよい。
【００８５】
XMLインデックスについての変更インデックスステートメントの重要な用途は、インデックス付けされた経路を追加するかまたは削除することである。一実施例に従うと、以下の変更インデックス（Alter Index）DDLにより、新しい経路がインデックスに追加され得る。
【００８６】
【数８】
2007533008.tif 000013
【００８７】
このDDLコマンドは、発注基準のすべておよびAction要素の子のすべてに、これらがインデックスによってまだインデックス付けされていない場合、インデックス付けする。同様に、以下のDDLは、これらの経路が既にインデックス付けされている場合、インデックスからこれらの経路を取除く。
【００８８】
【数９】
2007533008.tif 000014
【００８９】
変更インデックス改名（Alter Index Rename）DDLは、以下の例において説明されるとおり、ユーザがインデックスの名前を、明示的に削除したり作成したりすることなく、変更することを可能にする。
【００９０】
【数１０】
2007533008.tif 000015
【００９１】
XMLインデックスを使用できるかどうかの判断
クエリ時に、クエリXPathが、ユーザによって特定されたXpathのサブセットであると静的に判断され得る（従って、インデックスにあると保証され得る）場合、XMLインデックスを用いてクエリに応答することができる。サブセット関係をクエリのコンパイル時間に決定できない場合、XMLインデックスはクエリを満たすのに用いられない。
【００９２】
たとえば、ステートメントによって作成されるXMLインデックスPOIndex１について考察する。
【００９３】
【数１１】
2007533008.tif 000016
【００９４】
XMLインデックスは、query XPath/PurchaseOrder/LineItems/LineItem/Descriptionに応答するのに用いられてもよい。しかしながら、XMLインデックスは、query XPATH//Descriptionに応答するのに用いることができない。というのも、/PurchaseOrder/LineItemsとは異なる経路の下に<Description>要素が存在し得るからである。
【００９５】
XMLインデックスを用いることによるXPathクエリへの応答
XMLインデックスは、XPathクエリを値についての単純な経路およびプレディケイトに分解することによって当該XPathクエリを満たすのに用いることができる。結果として得られる分解された部分は、インデックスPATH_TABLE上のXQLクエリに翻訳される。一実施例に従うと、インデックスアクセス方法への入力は、以下のうちの１つ以上を含む複合式である。
【００９６】
・  単純な（ナビゲーション）経路表現、たとえば、/a/b
・  単純な値表現、たとえば、/a/b/c>50
・  表現間における構造的結合（すなわち、階層関係）。たとえば、XPath表現/a/b[c>50]は、(/a/b)PARENT-OF(/a/b/c>50)と表現される。
【００９７】
/a/b/c=fooなどの簡単なプレディケイトでのクエリについて考察する。このようなクエリは、以下のとおりPATHテーブルに対して実行され得る。
【００９８】
【数１２】
2007533008.tif 000017
【００９９】
経路/a/b/cについてのＩＤが変数１としてバインドされる。このクエリについて複数の実行プランが存在する。一実施例に従うと、クエリオプティマイザが、コストに基づいた最良の実行プランを選択する。データベースサーバは、（１）pathid上の２次インデックスを用いるか、（２）xmlvalue_to_string(value)上の２次インデックスを用いるか、または（３）両方、ならびにビットマップおよびその結果を用い得る。
【０１００】
XPath/a/b/cなどのフラグメントルックアップを特定するクエリについて考察する。このようなクエリは、ステートメント:
【０１０１】
【数１３】
2007533008.tif 000018
【０１０２】
を用いてPATHテーブルに対して実行され得る。
経路/a/b/cについてのＩＤは変数１としてバインドされる。結果として得られる適合は、クエリによって文書の順で戻される。単一の文書に対応するすべてのフラグメントが、必要に応じて連結される。
【０１０３】
/a/b[c=foo]などの単純なプレディケイトに基づいてフラグメントルックアップを特定するクエリについて考察する。入力XPathの標準化された表現は(/a/b)PARENT-OF(/a/b/c=foo)である。以下のクエリは、経路/a/bのための適合と単純なプレディケイト(/a/b/c=foo)のための適合とをルックアップするのに用いられてもよい。
【０１０４】
【数１４】
2007533008.tif 000019
【０１０５】
結果が、Dewey順序キーを用いて表現される構造的結合オペレータを用いてマージされる。経路/a/bおよび/a/b/cについてのＩｄは変数１および２としてバインドされる。一実施例に従うと、コストベースのオプティマイザが、実現可能なさまざまな実行プランのうちで最良の実行プランを選択する。
【０１０６】
XMLインデックスはまた、データ型認識動作を実行するのに用いられてもよい。データ型情報をXPathプレディケイトに取付けるための複数の機構が存在する。たとえば：
・  XMLスキーマの使用。ベーステーブル列が関連するXMLスキーマを有する場合、ユーザXPathはXMLスキーマに対してタイプチェックされ、これにより、適切なデータ型をその表現に関連付ける。
【０１０７】
・  明示的なタイプ強制。XPathは、明示的なタイプ強制についてオペレータに提供する。
【０１０８】
・  暗示的なタイプ強制。XPathは、いくつかの暗示的なタイプキャスティングルールを規定する。たとえば、比較オペレータのRHSがNUMBERである場合、LHSはまた、暗示的にNUMBERに強制される。
【０１０９】
一実施例に従うと、これらのすべてのシナリオにおいては、XMLインデックスアクセス方法への入力は、関連するデータ型情報を有するXPath表現となる。データ型情報は、適切な値インデックスが選択されることを確実にするために、生成されたXQLクエリ内で用いられる。たとえば、タイプチェックされたXPathは以下のとおり、
SYS_XMLVALUE_TO_NUMBER（／ａ／ｂ／ｃ）＞１０．５６７
であり、結果として、NUMBER値インデックスを用いるPATHテーブルに対する以下のクエリがもたらされる。
【０１１０】
【数１５】
2007533008.tif 000020
【０１１１】
XMLインデックスを用いると、この明細書中に記載されるように、XPathの大きな組を効
率的に評価することができるといったさまざまな利点が生じ得る。データ型認識比較を含むXPathを満たすことができる。フラグメントは、元のXML文書から効率的に抽出され得る。ユーザは、経路のサブセットだけにインデックス付けすることを選択し、こうしてインデックスの肥大化を回避し得る。インデックス値は、アプリケーションのニーズに基づいてカスタマイズされ得る。さらに非スキーマXML文書にインデックス付けする能力が、ユーザの大きなクラスについてのクエリ要件を満たすこととなる。これにより、クエリ性能について懸念することなく、オラクル（Oracle）におけるそれらのすべてのXML文書を記憶することが可能となる。
【０１１２】
シンタックス
データベースサーバが、それ自体が受信したコマンドに応答してXMLインデックスを作成および維持する文脈において実施例を説明してきた。当該コマンドは、データベースサーバが理解する言語に準拠していなければならない。この発明の一実施例に従うと、XMLインデックスを含むさまざまなDDLコマンドに用いられるシンタックスは以下のとおりである。
【０１１３】
【数１６】
2007533008.tif 000021
【０１１４】
一実施例に従うと、ドメインインデックスが親のXMLテーブルに等しく分割される。XMLテーブルが分割されない場合、ドメインインデックスは分割されない。PATH TABLEおよびその２次インデックスもXMLテーブルに等しく分割される。
【０１１５】
PARAMETERS文節についてのシンタックス：
【０１１６】
【数１７】
2007533008.tif 000022
【数１８】
2007533008.tif 000023
【０１１７】
一実施例に従うと、PARAMETERS文節は、以下を特定するのに用いられる。すなわち、
・  経路テーブルおよび２次インデックスについての名前および物理的なパラメータ（テーブル空間（tablespace）など）。PATH TABLE上の６個のインデックスはすべて、明示的に指定されていなくても作成される。
【０１１８】
−  列VALUEについてのタイプが明示的にBLOBとなるよう指定されている場合、値がBLOBセグメントにおいてずれて記憶される。そうでない場合、値はRAWデータとして一列に並んで記憶される。RAWについての<size>は整数である。
【０１１９】
−  STRING値についての属性は、
・  ストリングの先行および後続の余白がすべて除去されるべき場合、正規化（NORMALIZED）され、
・  IGNORE_MIXED_TEXTは、混合されたテキストがある状態で値をNULLとして記憶し、
・  すべてのストリングが小文字に変換されるべき場合、CASE_INSENSITIVEである。
【０１２０】
なお、上述の動作は、値をVALUE列に記憶する前に（および、PATH TABLE上での２次インデックスの作成前に）適用される。
【０１２１】
・  インデックス付けすべき経路の設定。ユーザは、以下を指定することによってインデックス付けされた経路の組を制御することができる。すなわち、
−  インデックス付けすべき経路の明示的なリスト。これはワイルドカードおよび//axesを含み得る。たとえば、/a/b/c、/d/*、/x//y。
【０１２２】
−  インデックス付けすべきでない経路の明示的なリスト。
【０１２３】
【数１９】
2007533008.tif 000024
【０１２４】
使用
・  XMLインデックスは、その構成要素、基礎をなすPATH TABLEおよびその２次インデックスとともに削除される。
【０１２５】
【数２０】
2007533008.tif 000025
【０１２６】
【数２１】
2007533008.tif 000026
【０１２７】
ハードウェア概要
図２は、この発明の実施例が実現され得るコンピュータシステム２００を示すブロック図である。コンピュータシステム２００は、情報を伝達するためのバス２０２または他の通信機構と、バス２０２に結合され情報を処理するためのプロセッサ２０４とを含む。コンピュータシステム２００はまた、プロセッサ２０４によって実行されるべき情報および命令を記憶するための、バス２０２に結合されるランダムアクセスメモリ（ＲＡＭ）または他の動的記憶装置等のメインメモリ２０６を含む。メインメモリ２０６はまた、プロセッサ２０４によって実行されるべき命令の実行中に一時変数または他の中間情報を記憶するのに用いられ得る。コンピュータシステム２００はさらに、プロセッサ２０４のための静的情報および命令を記憶するための、バス２０２に結合される読出専用メモリ（ＲＯＭ）２０８または他の静的記憶装置を含む。磁気ディスクまたは光ディスク等の記憶装置２１０が設けられ、情報および命令を記憶するためにバス２０２に結合される。
【０１２８】
コンピュータシステム２００は、コンピュータユーザに情報を表示するための、陰極線管（ＣＲＴ）等のディスプレイ２１２にバス２０２を介して結合され得る。英数字および他のキーを含む入力装置２１４がバス２０２に結合されて、情報およびコマンド選択をプロセッサ２０４に伝達する。別の種類のユーザ入力装置は、方向情報およびコマンド選択をプロセッサ２０４に伝達し、ディスプレイ２１２上でのカーソルの動きを制御するための、マウス、トラックボールまたはカーソル方向キー等のカーソル制御２１６である。この入力装置は、典型的には、２つの軸、すなわち第１の軸（たとえば、ｘ）および第２の軸（たとえば、ｙ）、において２自由度を有しており、これにより、装置が平面で位置を特定することが可能となる。
この発明は、ここで説明される技術を実現するためのコンピュータシステム２００の用途に関する。この発明の一実施例に従うと、これらの技術は、メインメモリ２０６に含まれる１つ以上の命令の１つ以上のシーケンスをプロセッサ２０４が実行することに応答して、コンピュータシステム２００によって実行される。このような命令は、記憶装置２１０等の別のコンピュータ読取り可能な媒体からメインメモリ２０６へと読取られてもよい。メインメモリ２０６内に含まれる命令シーケンスを実行することにより、ここで説明されるプロセスステップをプロセッサ２０４に実行させる。代替的な実施例では、ソフトウェア命令の代わりに、またはソフトウェア命令と組合せてハードワイヤード回路を用いてこの発明を実現することもできる。したがって、この発明の実施例は、ハードウェア回路とソフトウェアとの特定のいずれかの組合せに限定されない。
【０１２９】
ここで用いられる「コンピュータ読取り可能な媒体」という用語は、特定の態様で機械を動作させるデータの提供に関与するいかなる媒体をも指す。コンピュータシステム２００を用いて実現される実施例においては、さまざまな機械読取り可能な媒体は、たとえば、実行のための命令をプロセッサ２０４に提供することに関与する。このような媒体は、不揮発性媒体、揮発性媒体および伝送媒体を含むがそれらに限定されない多くの形をとり得る。不揮発性媒体は、たとえば、記憶装置２１０等の光ディスクまたは磁気ディスクを含む。揮発性媒体は、メインメモリ２０６等のダイナミックメモリを含む。伝送媒体は、バス２０２を含むワイヤを含んだ、同軸ケーブル、銅線および光ファイバを含む。伝送媒体はまた、電波および赤外線データ通信中に生成されるような音波または光波の形をとり得る。
【０１３０】
機械読取り可能な媒体の一般的な形は、たとえば、フロッピー（登録商標）ディスク、フレキシブルディスク、ハードディスク、磁気テープ、他のいずれかの磁気媒体、ＣＤ−ＲＯＭ、他のいずれかの光学媒体、パンチカード、紙テープ、孔のパターンを備えた他のいずれかの物理的媒体、ＲＡＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、他のいずれかのメモリチップもしくはカートリッジ、以下に記載される搬送波、またはコンピュータが読取ることのできる他のいずれかの媒体を含む。
【０１３１】
さまざまな形の機械読取り可能な媒体は、実行のための１つ以上の命令の１つ以上のシーケンスをプロセッサ２０４に搬送することに関与し得る。たとえば、当該命令は、最初にリモートコンピュータの磁気ディスク上で搬送され得る。リモートコンピュータは、命令をそのダイナミックメモリにロードし、モデムを用いて電話線上で命令を送信し得る。コンピュータシステム２００にとってローカルなモデムは、電話線上のデータを受信し、赤外線送信機を用いてデータを赤外線信号に変換し得る。赤外線検出器が、赤外線信号で搬送されたデータを受信し、適切な回路が当該データをバス２０２上に配置し得る。バス２０２はデータをメインメモリ２０６へと搬送し、ここから、プロセッサ２０４が命令を取出し、実行する。メインメモリ２０６が受取る命令は、随意には、プロセッサ２０４による実行の前または後に記憶装置２１０に記憶され得る。
【０１３２】
コンピュータシステム２００はまた、バス２０２に結合される通信インターフェイス２１８を含む。通信インターフェイス２１８は、ローカルネットワーク２２２に接続されるネットワークリンク２２０に対する双方向データ通信結合を提供する。たとえば、通信インターフェイス２１８は、データ通信接続を対応する種類の電話線に提供する統合サービスデジタル通信網（ＩＳＤＮ）カードまたはモデムであってもよい。別の例として、通信インターフェイス２１８は、データ通信接続を互換性のあるＬＡＮに提供するローカルエリアネットワーク（ＬＡＮ）カードであってもよい。ワイヤレスリンクも実現され得る。このようないずれの実現例においても、通信インターフェイス２１８は、さまざまな種類の情報を表わすデジタルデータストリームを搬送する電気信号、電磁信号または光信号を送受信する。
【０１３３】
ネットワークリンク２２０は、典型的には、１つ以上のネットワークを介して他のデータ装置にデータ通信を提供する。たとえば、ネットワークリンク２２０は、ローカルネットワーク２２２を介した、ホストコンピュータ２２４、またはインターネットサービスプロバイダ（ＩＳＰ）２２６が作動させるデータ設備への接続をもたらし得る。ＩＳＰ２２６は、現在では一般的に「インターネット」２２８と称される世界的なパケットデータ通信網を介してデータ通信サービスを提供する。ローカルネットワーク２２２およびインターネット２２８はともに、デジタルデータストリームを搬送する電気信号、電磁信号または光信号を用いる。さまざまなネットワークを介する信号ならびにネットワークリンク２２０上にあり通信インターフェイス２１８を介する信号は、コンピュータシステム２００との間でデジタルデータをやり取りするものであるが、情報を運ぶ搬送波の例示的な形で
ある。
【０１３４】
コンピュータシステム２００は、ネットワーク、ネットワークリンク２２０および通信インターフェイス２１８を介して、プログラムコードを含むデータを受取りかつメッセージを送ることができる。インターネットの例では、サーバ２３０は、インターネット２２８、ＩＳＰ２２６、ローカルネットワーク２２２および通信インターフェイス２１８を介してアプリケーションプログラムについての要求されたコードを伝送し得る。
【０１３５】
コードが受取られると、当該受取られたコードはプロセッサ２０４によって実行され、および／または、後の実行のために記憶装置２１０もしくは他の不揮発性記憶装置に記憶され得る。このように、コンピュータシステム２００は、搬送波の形でアプリケーションコードを獲得し得る。
【０１３６】
上述の明細書では、この発明の実施例を、実現例ごとに異なり得る多数の特定の詳細を参照して説明してきた。したがって、この発明が何であるか、およびこの発明を目指して出願人が何を意図しているかを独占的に示す唯一のものが、この出願から発生して特有の形態をとった請求項の組である。特有の形態であるこのような請求項は、以降の任意の補正を含んで発生する。このような請求項に含まれる用語に対してこの明細書で明示された任意の定義は、請求項で用いられている通りにこのような用語の意味を支配するものとする。したがって、請求項に明示的に記載されていない限定、要素、特性、特徴、利点または属性は、このような請求項の範囲を決して限定しない。したがって、明細書および図面は限定的な意味ではなく例示的な意味で捉えられるべきである。
【図面の簡単な説明】
【０１３７】
【図１】新しいXML文書に基づいてXMLインデックスを更新するためのステップを示すフローチャートである。
【図２】この明細書中に記載される技術を実現し得るシステムを示すブロック図である。
【図１】
2007533008.tif 000027
【図２】
2007533008.tif 000028
【手続補正書】
【提出日】平成18年4月15日(2006.4.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
XML文書からの情報にアクセスするための方法であって、
XML文書内において、インデックス付けすべきノードの組を識別するステップと、
インデックス付けすべきノードの組における各ノードのために、ノードについてのエントリをインデックスに記憶するステップとを含み、所与のノードについてのエントリは、
（ａ）所与のノードに関連付けられるXML内容の位置を特定し、
（ｂ）階層データを含み、前記階層データは、所与のノードと、所与のノードを含むXML文書内における階層のそれぞれのレベル内において所与のノードの祖先ノードの各々との相対位置を示し、前記方法はさらに、
XML文書からの情報についての要求に応答して、インデックスを用いてXML文書内の情報の位置を特定するステップを含む、方法。
【請求項２】
インデックスはリレーショナルテーブルとして実現され、各ノードについてのエントリを記憶するステップは、リレーショナルテーブル内において、ノードの組における各ノードについての行を記憶することによって実行される、請求項１に記載の方法。
【請求項３】
インデックスは、ノードの組における１つ以上のノードに関連付けられる値を記憶する、請求項１に記載の方法。
【請求項４】
前記インデックスに記憶される値は、複数のデータ型の値を含み、前記方法は、前記複数のデータ型のうちの２つ以上のデータ型の各々についての２次インデックスを構築するステップをさらに含む、請求項３に記載の方法。
【請求項５】
所与のノードについての位置データは、XML文書の位置を特定するための第１のデータと、XML文書内において、所与のノードに関連付けられる情報の位置を特定するための第２のデータとを含む、請求項１に記載の方法。
【請求項６】
前記方法は、前記階層データに基づいて、前記インデックスにおけるエントリにアクセ
スするための２次インデックスを構築するステップをさらに含む、請求項１に記載の方法。
【請求項７】
所与のノードについてのエントリは、所与のノードを含むXML文書の構造を介する所与のノードへの経路に対応する経路データを含み、
前記方法はさらに、前記経路データに基づいて、前記インデックスにおけるエントリにアクセスするための２次インデックスを構築するステップを含む、請求項１に記載の方法。
【請求項８】
親ノードの子ノードに関連付けられる階層情報に基づいて、前記インデックスにおいて、前記親ノードについてのエントリにアクセスするための２次インデックスを構築するステップをさらに含む、請求項１に記載の方法。
【請求項９】
インデックス付けすべきノードの組を識別するステップは、
どの経路がインデックス付けされるべきであるかを決定するためのルールを受信するステップと、
インデックス付けされるべきXML文書におけるノードに関連付けられる経路を決定するステップと、
（ａ）どの経路がインデックス付けされるべきであるかを決定するためのルール、および、（ｂ）インデックス付けされるべきXML文書におけるノードに関連付けられる経路に基づいて、どのノードがインデックス付けされるべきであるかを識別するステップとを含む、請求項１に記載の方法。
【請求項１０】
ルールは、インデックスに含まれるべき経路を明示的に識別する、請求項９に記載の方法。
【請求項１１】
ルールは、インデックスから除外すべき経路を明示的に識別する、請求項９に記載の方法。
【請求項１２】
２次値インデックスが構築されるべきデータ型を示すユーザデータを受信するステップをさらに含む、請求項４に記載の方法。
【請求項１３】
所与のノードについてのエントリはさらに、
（ｃ）所与のノードを含むXML文書の構造を介する所与のノードへの経路に対応する経路データを含む、請求項１に記載の方法。
【請求項１４】
１つ以上のプロセッサによって実行されるときに、１つ以上のプロセッサに請求項１から１３のいずれかに記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能媒体。
【国際調査報告】
2007533008.tif 000029
2007533008.tif 000030
2007533008.tif 000031