(57)【要約】【課題】  祖先・子孫包含関係を含むクエリーを効率良く処理する。【解決手段】  親ノードのラベルの後に兄弟関係を示すコードを付加することで子ノードのラベルが決定されるラベルを用い、ＸＭＬ文書の各項目に前記ラベルを付して格納したデータベースにおける祖先・子孫の包含関係の検索条件を含むデータの検索方法を提供する。  このデータの検索方法は、祖先候補のラベルの長さを示したラベル長リストを作成するＡ１段階と、前記ラベル長リスト中のラベル長分だけ子孫候補の各ラベルから先頭部分を各種１つずつ取得し先頭部分リストを作成するＡ２段階と、前記祖先候補の各ラベルと、前記先頭部分リストとを比較して、一致するラベルのみを取得するＡ３段階と、を有してなる。【選択図】      図２
2006228070.tif 000002
【特許請求の範囲】
【請求項１】
親ノードのラベルの後に兄弟関係を示すコードを付加することで子ノードのラベルが決定されるラベルを用い、ＸＭＬ文書の各項目に前記ラベルを付して格納したデータベースにおける祖先・子孫の包含関係の検索条件を含むデータの検索方法であって、
祖先候補のラベルの長さを示したラベル長リストを作成するＡ１段階と、
前記ラベル長リスト中のラベル長分だけ子孫候補の各ラベルから先頭部分を各種１つずつ取得し先頭部分リストを作成するＡ２段階と、
前記祖先候補の各ラベルと、前記先頭部分リストとを比較して、一致するラベルのみを取得するＡ３段階と、
を有することを特徴とするデータの検索方法。
【請求項２】
前記子孫候補のラベルの長さを祖先候補のラベルの長さと比較し、最も短い祖先候補のラベルの長さより長い子孫候補のラベルのみに前記子孫候補を絞り込むＢ１段階を前記Ａ３段階より前に行うことを特徴とする請求項１に記載のデータの検索方法。
【請求項３】
前記祖先候補のラベルの長さを子孫候補のラベルの長さと比較し、最も長い子孫候補のラベルの長さより短い祖先候補のラベルのみに前記祖先候補を絞り込むＢ２段階を前記Ａ３段階より前に行うことを特徴とする請求項１または請求項２に記載のデータの検索方法。
【請求項４】
前記ラベルは、兄弟関係を示すラベルが、ある値ｖに対し大きい値である場合に一の符号を付加し、小さい場合には他の符号を付加してなることを特徴とする請求項１から請求項３のいずれか１項に記載のデータの検索方法。
【請求項５】
前記コードを３進数以上の進数に変換することを特徴とする請求項４に記載のデータの検索方法。
【請求項６】
前記コードを３進数から１０進数のいずれかの進数に変換することを特徴とする請求項４に記載のデータの検索方法。
【請求項７】
前記ラベルとして、数字からなる親を示すラベルに対し、数字からなる子を示すコードを左側に付加してなるラベルを用い、
前記Ａ２段階において、前記子孫候補の各ラベルを、１０の［前記ラベル長リスト中のラベル長］乗で除した余りを求めることで前記先頭部分リストの候補を求めることを特徴とする請求項１から請求項４、および請求項６のいずれか１項に記載のデータの検索方法。
【請求項８】
前記ラベルとして、親を示すラベルと子を示すコードとを、コードに出現しない数字からなる区切り符号で区切ったラベルを用いることを特徴とする請求項７に記載のデータの検索方法。
【請求項９】
前記ラベルとして、符号からなる親を示すラベルに対し、符号からなる子を示すコードを右側に付加してなるラベルを用い、
前記Ａ２段階において、前記子孫候補の各ラベルから、左から前記ラベル長リスト中のラベル長分の文字数の符号を取得することにより、前記先頭部分リストの候補を求めることを特徴とする請求項１から請求項６のいずれか１項に記載のデータの検索方法。
【請求項１０】
前記ラベルとして、親を示す符号からなるラベルと子を示すコードとを区切り符号により区切ったラベルを用いることを特徴とする請求項９に記載のデータの検索方法。
【請求項１１】
請求項１から請求項１０のいずれか１項に記載のデータの検索方法をコンピュータに実行させることを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＸＭＬ文書の各項目をラベル付きで格納してなるデータベースにおけるデータの検索方法に関する。
【背景技術】
【０００２】
最近、様々のデータがＸＭＬで記述されることが多くなって来ている。そのような大量のＸＭＬ文書を効率よく管理し、高速に検索するために、ＸＭＬ文書をＲＤＢ(Relational Database)に格納する方法が注目されている。ＲＤＢに格納することにより、検索機能や同時実行制御、障害処理など現在のＲＤＢＭＳ(Management System)が持つ様々な機能を容易にＸＭＬ文書の管理に利用することができる。
【０００３】
ＸＭＬ文書は、タグによってノード毎にデータを持たせて表現される。各ノード間には包含関係があり、木構造と見なすことができる。ＲＤＢにＸＭＬ文書を格納する場合には、この木構造を認識させる必要がある。そのための方法として、一般にＸＭＬの各ノードにラベルを割り当て、ラベルとノードをＲＤＢのタプル（１レコード）として格納する方法が採られている。つまり、ラベルに規則性を持たせることによって、各ノード間の包含関係や、ノードのＸＭＬ文書中の位置を認識可能にしている。
【０００４】
木構造とその要素の包含関係をラベル付けする方法としては、Dewey Order法や前順後順法が知られている（非特許文献１，２参照）。これらの手法をＸＭＬのノードのラベルを適用することで、ＸＭＬ文書の木構造を表現することが可能となる。
Dewey Order法は、図８に示したように、親ノードのラベルの後に何らかのデリミタ（多くは”．”）を挟んで兄弟間の順序を示すコードを付与する方法である。このDewey Order法は、木構造が更新された場合に、ラベルを更新する処理が煩雑であるため、あまり実用はされてこなかった。
前順後順法は、木構造の各ノードに前順と後順との２つのラベルを付する方法である。この方法は、ラベルを更新する処理は、Dewey Orderよりは煩雑ではなく、広く用いられている。そして、２つのラベルの祖先・子孫の包含関係を検索する場合には、前順ラベルの大小関係と後順ラベルの大小関係の２つの大小関係を見ることで行われていた。
例えば、あるＸＭＬ文書中でタグが＜Ａ＞…．＜Ｂ＞…．＜／Ｂ＞…＜Ａ＞のようになっていた場合、このＸＭＬ文書に対応する木構造ではノードＡがノードＢの祖先であり、それぞれのノードのラベル間には次の大小関係が成立するので、この大小関係を調べることで、祖先・子孫の包含関係を調べていた。
Ａの［前順］＜Ｂの［前順］  ＡＮＤ  Ａの［後順］＞Ｂの［後順］
【０００５】
ところで、本出願の発明者等は、他のノードのラベルを変更することなく、無制限に挿入することができるＶＬＥＩ(Variable Length Endless Insertable)コードと、ＶＬＥＩコードを前述の前順後順法とDewey Order法に適用したラベル付け手法を提案している（非特許文献３）。また、簡単な検索と挿入の実験によって、ＶＬＥＩコードを用いたラベル付け手法と他手法との比較を行い、ＶＬＥＩコードを用いたラベル付け手法の有効性を示した。しかし、これまでの手法では、祖先・子孫の包含関係の判定においてすべての組合せについてマッチングを行っていたことから検索性能に関して改善の余地があった。
【０００６】
【非特許文献１】Igor Tatarinov, Stratis Viglasand Kevin S. Beyer, Jayavel Shanmugasundaram, Eugene J. Shekita, and Chun Zhang. Storing and querying ordered xml using a relational database system. In Proc. of SIGMOD Conf., pp. 204-215, 2002.
【非特許文献２】Paul F. Dietz. Maintaining order in a linked list. In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pp. 122-127, 1982.
【非特許文献３】小林一仁,横田治夫,「挿入制限のないコードVLEIを用いたXMLラベリング手法の検討とその評価」,第１５回電子情報通信学会データ工学ワークショップ(DEWS2004論文集,7-A-1, 2004.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、このような背景に鑑みてなされたものであり、ＸＭＬ文書の各項目をラベル付きで格納してなるデータベースにおいて、祖先・子孫包含関係を含むクエリーを効率良く処理することができるデータの検索方法およびコンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
前記した課題を解決するため、本発明は、親ノードのラベルの後に兄弟関係を示すコードを付加することで子ノードのラベルが決定されるラベルを用い、ＸＭＬ文書の各項目に前記ラベルを付して格納したデータベースにおける祖先・子孫の包含関係の検索条件を含むデータの検索方法を提供する。
このデータの検索方法は、祖先候補のラベルの長さを示したラベル長リストを作成するＡ１段階と、前記ラベル長リスト中のラベル長分だけ子孫候補の各ラベルからラベルの先頭部分を各種１つずつ取得し先頭部分リストを作成するＡ２段階と、前記祖先候補の各ラベルと、前記先頭部分リストとを比較して、一致するラベルのみを取得するＡ３段階と、を有してなる。
【０００９】
このようなデータの検索方法によれば、Ａ１段階で取得したラベル長の分だけＡ２段階で子孫候補の各ラベルから先頭部分を各種１つずつ（重複させずに）取得するので、候補が絞り込まれる。また、Ａ３段階で一致検索により検索結果を得ることができるので、処理コストを低くすることができる。
【００１０】
前記したデータの検索方法においては、前記子孫候補のラベルの長さを祖先候補のラベルの長さと比較し、最も短い祖先候補のラベルの長さより長い子孫候補のラベルのみに前記子孫候補を絞り込むＢ１段階を前記Ａ３段階より前に行うことができる。また、前記祖先候補のラベルの長さを子孫候補のラベルの長さと比較し、最も長い子孫候補のラベルの長さより短い祖先候補のラベルのみに前記祖先候補を絞り込むＢ２段階を前記Ａ３段階より前に行うことができる。
【００１１】
このようなデータの検索方法によれば、祖先・子孫の包含関係の検索の際に、祖先と子孫の総組合せについて包含関係を調べる前に、Ｂ１，Ｂ２段階で明らかに包含関係を満たさないラベルを排除できるので、Ａ３段階で包含関係を検索（チェック）する処理コストが低くなる。
【００１２】
また、前記ラベルは、兄弟関係を示すコードが、ある値ｖに対し大きい値である場合に一の符号を付加し、小さい場合には他の符号を付加してなるラベルであることが望ましい。そして、この場合には、コードが２種類の符号で表現されることになるが、このコードを２進数とみなした上で３進数以上の進数に変換すると、コードを効率よく（圧縮して）表現できる。また、前記コードを３進数から１０進数のいずれかの進数に変換して表現することで、効率よく表現できるとともに、数字として扱うことができる。
すなわち、本明細書でいうＶＬＥＩコードを、兄弟関係を示すコードとして用いることで、木構造を更新する際に、処理コストを低減することができる。
【００１３】
前記データの検索方法のより具体的な方法としては、ラベルを数値として表して、modを用いる方法や、ラベルを文字列として表して、文字列操作により行う方法がある。
すなわち、前記ラベルとして、数字からなる親を示すラベルに対し、数字からなる子を示すコードを左側に付加してなるラベルを用い、前記Ａ２段階において、前記子孫候補の各ラベルを、１０の［前記ラベル長リスト中のラベル長］乗で除した余りを求めることで前記先頭部分リストの候補を求めることができる。この場合に、前記ラベルとして、親を示すラベルと子を示すコードとを、コードに出現しない数字からなる区切り符号で区切ったラベルを用いることで、コードの桁数を制限なくとることができる。
もしくは、前記ラベルとして、符号からなる親を示すラベルに対し、符号からなる子を示すコードを右側に付加してなるラベルを用い、前記Ａ２段階において、前記子孫候補の各ラベルから、左から前記ラベル長リスト中のラベル長分の文字数の符号を取得することにより、前記先頭部分リストの候補を求めることができる。この場合に、前記ラベルとして、親を示す符号からなるラベルと子を示すコードとを区切り符号により区切ったラベルを用いることで、コードの桁数を制限なくとることができる。
【００１４】
さらに、前記したデータの検索方法をコンピュータに実行させるコンピュータプログラを提供することができる。
【発明の効果】
【００１５】
本発明によれば、Dewey Orderや、ＶＬＥＩコードなどの、親ノードのラベルの後に兄弟関係を示すコードを付加することで子ノードのラベルが決定されるラベルを用いてＲＤＢに格納したＸＭＬ文書について、低処理コストで祖先・子孫の包含関係を検索することが可能になる。
【発明を実施するための最良の形態】
【００１６】
次に、本発明の実施形態について図面を参照しながら詳細に説明する。
まず、本発明を好適に適用することができるＸＭＬ文書のラベル付けの手法として、ＶＬＥＩコードおよびＶＬＥＩラベルの概要を説明する。
【００１７】
［ＶＬＥＩコード］
ＶＬＥＩコードｖを1から始まる｛０，１｝からなるビット列とし、次式（１）の大小関係を満足する場合にＶＬＥＩコードと呼ぶ。
ｖ・０・｛０｜１｝*＜ｖ＜ｖ・１・｛０｜１｝*  ・・・（１）
すなわち、あるコードｖに対して、右に０のつくものはｖよりも小さく、１のつくものはｖよりも大きい。なお、ここでは、「一の符号」および「他の符号」として「０」および「１」を用いて大小を示しているが、Ａ，Ｂなど別の符号を用いて大小関係を示すことができることはもちろんである。
【００１８】
任意のｖl＜ｖrであるＶＬＥＩコードの組みに対し、表１に示すアルゴリズムは、ｖlとｖrの間を表すＶＬＥＩコードを容易に無制限に作成することができる。つまり、任意の大小関係をもつｖl＜ｖrに対して、ｖl＜ｖ＜ｖrとなるコードｖが存在する。これは、木構造の挿入要素のコードが容易に求まり、挿入されるノード以外のコードを変更する必要がないことを示している。このため、ＶＬＥＩコードを前順後順法やDewey Order法に適用することによって、他のノードのラベルの付け変えが不要な更新コストの低いラベル付けが可能となる。
【表１】
2006228070.tif 000003
【００１９】
具体的な例を挙げて説明すれば、「１」というＶＬＥＩコードより小さなコードとして、右側に０を付けて「１０」を作成でき、大きなコードとして、右側に１を付けて「１１」を作成することができる。「１０」に対しても同様に、これより小さいコードは、「１００」を作成でき、大きいコードは「１０１」を作成できる。このように、どのコードに対してもそれより小さいコードおよび大きいコードを、他のコードと重複すること無く作成することができる。
【００２０】
［ＶＬＥＩラベル］
次に、ＸＭＬ文書の各ノードに割り当て、ノード間の包含関係を表現するラベルにＶＬＥＩコードを用いたものをＶＬＥＩラベルと呼ぶことにする。ＶＬＥＩラベルは、Dewey OrderにＶＬＥＩコードを適用して作ることができる（ＤＯ−ＶＬＥＩラベルとする）。すなわち、デリミタ（区切り符号）を用いてひとつ下の子ノードをサフィックスとして表現し、兄弟ノード間の順序の表現にＶＬＥＩコードを用いて作ることができる。これを先の１と０の表現で記述すれば、木構造について、図１のようなラベルを付すことができる。
【００２１】
このラベルを効率良く表現するために、例えばＶＬＥＩコードを８進数に変換し、デリミタに９を用いて、全体を１０進数で表現することができる。
すなわち、このＤＯ−ＶＬＥＩラベルは、次のように定義できる。
DO-VLEIラベル＝"親ノードのDO-VLEIラベル"
+  "9"  +  [兄弟順を表すVLEIコードを8進数に変換したもの]
例えば、「１．１１１．１０１．１１１１」は「１９７９５９１７」になる。このＤＯ−ＶＬＥＩラベルでは、祖先のＤＯ−ＶＬＥＩラベルに“９”（デリミタ）を付けたもので始まるＤＯ−ＶＬＥＩラベルを探すことで子孫を求めることができる。また、ＤＯ−ＶＬＥＩラベルの右からｎ個目の９から右の桁数を取り除けば、ｎ番目の祖先ラベルがわかる。例えば、ｎ＝１として、上記の例のＤＯ−ＶＬＥＩラベル「１９７９５９１７」から右から１番目の９より右の部分を削除すると、「９１７」を削除することになるが、これは、兄弟順を示す部分のみが削除され、親ノードを示すことになる。
【００２２】
［検索処理の改善］
次にＤＯ−ＶＬＥＩラベルを用いてＸＭＬ文書を格納したＲＤＢにおける検索処理の実施形態について説明する。なお、本発明の検索処理は、ＣＰＵ、記憶装置、入力装置、出力装置を有したコンピュータにプログラムを実行させることで行うことができる。ここで具体例として挙げる検索手法には２つあり、１つは、ＤＯ−ＶＬＥＩラベルを数値として扱う方法（第１実施形態）であり、ＤＯ−ＶＬＥＩを数値として、mod()を用いて下の桁を取り出す方法である。もう１つは、ＤＯ−ＶＬＥＩを文字列として扱い、パターンマッチングを使用せずに文字列操作により判定する方法（第２実施形態）であり、文字列関数substring()を用いて先頭の文字列を取り出す方法である。
これらの２つの手法では、Dewey Orderの、ラベルの一部から祖先のラベルを判定可能であるという特長を利用している。
【００２３】
［検索手法の概要］
この手法の概要を示した図２を参照して説明する。図２は、本発明の概要を説明する図であり、単純な１０進数の自然数で表したDewey Orderのラベルを使用した場合を示す。なお、この例は、概要であって、実際にコーディングする場合には、ラベル長の取り方など、効率的な処理のために異なる部分もある。
図２に示すように、本発明では、ラベル間の祖先・子孫関係を最初からパターンマッチングにより判定するのではなく、子孫候補から祖先候補と祖先・子孫関係を満たす可能性があるものだけに絞り込み、その絞り込んだリストと祖先候補とを比較して検索結果を得る。
図２において、祖先候補とは、ある検索条件に適合する祖先ノードのことであり、祖先候補ラベルは、その祖先ノードのラベルである。同様に、子孫候補とは、ある検索条件に適合する子孫ノードのことであり、子孫候補ラベルは、その子孫ノードのラベルである。
まず、祖先候補ラベルと子孫候補ラベルを取得する。そして、各祖先候補ラベルのラベル長を取得する（Ａ１段階）。図２の例では、デリミタ“．”を除いた数字部分の長さを取得している。すなわち、「１．２」のような長さ２のラベル長と、「１．１．０」のような長さ３のラベル長とを取得している。なお、説明を簡単にするため、デリミタで区切られる兄弟を示す数字が一桁である場合を例にしている。
そして、このラベル長リストと子孫候補ラベルとに基づいて、子孫候補ラベルの中から、ラベル長リスト内のラベル長分だけの先頭部分（左側の部分）を取得する（Ａ２段階９。このとき、各種１つずつ、すなわち重複して取得された先頭部分は、１つのみ取得する。このＡ２段階により、通常、先頭部分リストのデータ数は、子孫候補ラベルのデータ数よりも小さくなる。
【００２４】
そして、先頭部分リストと祖先候補ラベルとを比較して、一致するラベルのみを取得する（Ａ３段階）。このＡ３段階で得られたラベルのリストが、祖先候補ラベルと、子孫候補ラベルとの間で祖先・子孫関係を有するラベルを示している。
以上のような方法により祖先・子孫関係を満たすラベルを検索することで、各子孫候補ラベルと各祖先候補ラベルとの間で、すべての祖先・子孫関係を検索するパターンマッチングに比較すると、飛躍的に処理量を減らすことができる。
【００２５】
以上の検索方法は、さらに、ラベル長の長さから候補を絞り込むことで処理の効率化を図ることができる。
例えば、図３は、さらに処理の効率化を実現した手法の例である。
図３に示す例では、図２の例に対し祖先候補ラベルとして「１．１．２．３．１」のラベルがある。
祖先候補ラベルの子孫となりうるラベルは、必ず祖先候補ラベルのいずれよりも長いはずであるから、子孫候補ラベルの長さを、祖先候補ラベルの長さと比較して、最も短い祖先候補ラベルよりも長いラベルのみに絞り込んでも、検索結果は変わらないといえる。従って、子孫候補ラベルのうち、「１．５」のラベルは祖先候補ラベルのうち最も短いラベルである「１．２」（または「１．３」）よりも長くないため、祖先・子孫関係を満たすことはなく、子孫候補ラベルのリストから除外する。
同様にして、子孫候補ラベルの祖先となりうるラベルは、必ず子孫候補ラベルのいずれよりも短いはずであるから、祖先候補ラベルの長さを、子孫候補ラベルの長さと比較して、最も長い子孫候補ラベルよりも短いラベルのみに絞り込んでも、検索結果は変わらないといえる。従って、祖先候補ラベルのうち、「１．１．２．３．１」のラベルは子孫候補ラベルのうち最も長いラベルである「１．１．０．１．１」などよりも短くないため、祖先・子孫関係を満たすことはなく、祖先候補ラベルのリストから除外する。
【００２６】
以上のような絞り込みの段階は、Ａ１段階やＡ２段階よりも前に行ってもよいし、Ａ１段階やＡ２段階と同時に行ってもよい。すなわち、Ａ３段階での比較、抽出よりも前に行っていればよい。
なお、祖先候補ラベルの取得と子孫候補ラベルの取得は、Ａ１段階やＡ２段階と同時に行うこともできる。
【００２７】
次に、ＤＯ−ＶＬＥＩラベルを用いた場合について、具体的なコードを示した実施形態を説明する。
【００２８】
［第１実施形態］（mod()による方法）
前述したＡ１段階からＡ３段階をmod()を用いて行う方法を説明する。この方法では文字列のパターンマッチングは行なわず、数値として格納したＶＬＥＩラベルを数値のままで用いて祖先子孫関係の判定を行うことができる。また、祖先候補ラベルとの比較においても“＝”を用いて数値が等しいか、等しくないか、を判定すればよい。まずそのために、逆ＤＯ−ＶＬＥＩラベルを用いる。
【００２９】
逆ＤＯ−ＶＬＥＩラベルは、Dewey Orderにおいて、デリミタを９で表し、rootノードの逆ＤＯ−ＶＬＥＩラベルＬroot＝９１とする。兄弟ノード間の順序をＶＬＥＩコードの大小関係で表し、これを８進数に変換したものとする。このとき、親ノードの逆ＤＯ−ＶＬＥＩラベルをＬparentとし、
逆ＤＯ−ＶＬＥＩラベル＝９・Ｃchild・Ｌparent
とする。
例えば、
親ノードの逆ＤＯ−ＶＬＥＩラベル：９２９１
兄弟順序（８進数表現）：１３
のとき、その逆ＤＯ−ＶＬＥＩラベルは、「９１３９２９１」となる
【００３０】
このような逆ＤＯ−ＶＬＥＩラベルでは、子孫候補のラベルを「１０の［祖先候補のラベル長］乗」で割った余りを求めると、この余りが祖先ノードを示すラベルとなる。
例えば、
祖先候補ノードの逆ＤＯ−ＶＬＥＩラベル：９２９１(length（長さ）＝４)
１０＾［祖先候補ノードのラベル長］：１０4＝１００００
子孫候補の逆ＤＯ−ＶＬＥＩラベル：９１３９２９１
のとき、求める余りは、mod(9139291 , 10000)=９２９１となる。
【００３１】
このようなmod()を用いた方法をＳＱＬ文の構造を示しながら説明する。ここでは、子孫の選択条件と祖先の選択条件が与えられたとき、これらの選択条件を満たす子孫候補および祖先候補のなかから、互いに祖先・子孫関係を有する祖先候補を求める方法を説明する。子孫候補を求める場合も同様の方法で求めることができる。
【００３２】
（１）手順１（Ａ１段階）
祖先候補ラベルの長さのリストを作成するために、祖先候補のラベル長を求めるとともに、「１０の［祖先候補のラベル長］乗」を求め、テーブルｔ１を作成する。これがラベル長リストとなる。
なお、以下のコードにおいて、
label：逆ＤＯ−ＶＬＥＩラベル
length：labelの長さをintegerで有する
である。
CREATE TABLE t1 AS
(SELECT DISTINCT length, (10^(length)) AS divider
FROM node WHERE [祖先候補の選択条件])
このＳＱＬ文により、祖先候補の選択条件を満たす祖先候補ラベルの中から、ラベル長と、１０のラベル長乗の数字を関係づけたテーブルｔ１が得られる。このとき、SELECT DISTINCTを用いているので、重複したラベル長は１つのみ抽出される。
【００３３】
（２）手順２（Ａ２段階、Ｂ１段階）
mod(子孫ラベル,t1.divider)により子孫候補のラベルの下［祖先候補の長さ］桁を取得してテーブルｔ２を作成する。このテーブルｔ２が先頭部分リストとなる。
CREATE TABLE t2 AS
(SELECT DISTINCT mod(descendant.label,t1.divider)
FROM node descendant, t1
WHERE [子孫の選択条件] 
AND descendant.length > t1.length)
このＳＱＬ文により、子孫の選択条件を満たすとともに、子孫候補ラベルのラベル長が祖先候補のラベル長よりも長い子孫候補ラベル（Ｂ１段階）の中から、手順（１）で作成したテーブルｔ１に示された長さ分の下位桁を取得する（Ａ２段階）。このとき、SELECT DISTINCTを用いているので、重複した子孫候補ラベルのうち各種１つずつのラベルのみが取得される。
【００３４】
（３）手順３（Ａ３段階）
手順２で作成したテーブルｔ２の先頭部分リストと祖先候補ラベルとの間で一致するものを各種１つ取得する。
SELECT DISTINCT ancestor
FROM node ancestor, t2
WHERE ancestor.label = t2.mod
AND [祖先候補の選択条件];
このＳＱＬ文により、「ancestor.label = t2.mod」で先頭部分リストと祖先候補ラベルとで一致の判定を行い、一致しているラベルのみが選択される。
【００３５】
以上のように、逆ＤＯ−ＶＬＥＩラベルを使用することで、mod()を用いて本発明を実施することができる。なお、Ｂ１段階を実行する場合には、例えば手順１の前に実行して祖先候補ラベルを絞り込んでおくとよい。
【００３６】
［第２実施形態］（substring()による方法）
次にsubstring()を用いて文字列操作により行う方法を説明する。
ＤＯ−ＶＬＥＩラベルは、上述したように、
[親ノードのラベル]+"9"+[兄弟順ＶＬＥＩコード（８進数）]
となっており、左端から所定文字数の文字列を取り出すことで祖先ラベルを取り出すことができる。
この方法では、逆ＤＯ−ＶＬＥＩラベルでの判定のような１０nを計算する必要がない。文字列処理であるが、従来の祖先・子孫関係の判定方法と異なり処理コストが高いパターンマッチングを行なわない。また、LIKEよりも＝で判定するほうが速いことから、文字列一致の判定にはLIKEではなく＝を使う。
ＤＯ−ＶＬＥＩラベルでは、先頭から［祖先候補のラベル長］文字分だけの文字を取得すれば、祖先ノードのラベルが得られる。
例えば、
祖先候補ノードのＤＯ−ＶＬＥＩラベル：１９２(length（長さ）＝４)
子孫候補ラベル：１９２９１３
substring(192913 , 1 , 3)＝１９２
このようなsubstring()を用いた方法をＳＱＬ文の構造を示しながら説明する。ここでは、子孫の選択条件と祖先の選択条件が与えられたとき、これらの選択条件を満たす子孫候補および祖先候補のなかから、互いに祖先・子孫関係を有する祖先候補を求める方法を説明する。子孫候補を求める場合も同様の方法で求めることができる。
【００３７】
（１）手順１（Ａ１段階）
祖先候補ラベルの長さを求め、テーブルｔ１を作成する（Ａ１段階）。
CREATE TABLE t1 AS
(SELECT DISTINCT length FROM node WHERE [祖先候補の選択の条件]);
このＳＱＬ文により、祖先候補の選択条件を満たす祖先候補ラベルの中から、ラベル長リストとしてテーブルｔ１が得られる。このとき、SELECT DISTINCTを用いているので、重複したラベル長は１つのみ抽出される。
【００３８】
（２）手順２（Ａ２段階、Ｂ１段階）
substring(子孫ラベル、1、t1.length)により子孫候補のラベルの左端1文字目から手順１で作成したラベル長リスト中の［ラベル長］文字目までを取り出してテーブルｔ２を作成する。このテーブルｔ２が先頭部分リストとなる
CREATE TABLE t2 AS
(SELECT DISTINCT substring(descendant.label,1,t1.length)
FROM node descendant, t1
WHERE [子孫の選択条件] AND descendant.length > t1.length);
このＳＱＬ文により、子孫の選択条件を満たすとともに、子孫候補ラベルのラベル長が祖先候補のラベル長よりも長い子孫候補ラベル（Ｂ１段階）の中から、手順（１）で作成したテーブルｔ１に示された長さ分の先頭文字列を取得する（Ａ２段階）。このとき、SELECT DISTINCTを用いているので、重複した子孫候補ラベルのうち各種１つずつのラベルのみが取得される。
【００３９】
（３）手順３
手順２で作成した、テーブルｔ２の先頭部分リストと祖先候補ラベルとの間で一致するものを各種１つ取得する。
SELECT DISTINCT ancestor FROM node ancestor, t2 
WHERE ancestor.label = t2.substring AND [祖先候補の選択の条件];
このＳＱＬ文により、「ancestor.label = t2.mod」で先頭部分リストと祖先候補ラベルとで一致の判定を行い、一致しているラベルのみが選択される。
【００４０】
以上のように、ＤＯ−ＶＬＥＩラベルを使用することで、substring()を用いて本発明を実施することができる。なお、Ｂ１段階を実行する場合には、例えば手順１の前に実行して祖先候補ラベルを絞り込んでおくとよい。
【００４１】
以上、本発明の実施形態について説明したが、本発明は、前記した実施形態に限定されるものではなく、適宜変更して実施することが可能である。たとえば、ＳＱＬ文によるコードは一例であって、手順を複数に分けて行うこともできるし、順序を一部入れ換えて行うことも可能である。
また、第１実施形態においては、コードを８進数に変換して効率よく表現したが、８進数に限らず、３進数以上の他の進数に変換して表現することもできる。さらに、３進数から１０進数のいずれかの進数を用いることで、効率よく表現できるとともに、数字として扱うことが可能となる。
また、兄弟関係を示すコードの表現においてデリミタ（区切り符号）の使用は必須ではなく、例えば、コードの桁数を予め決めておくことにより、デリミタを用いずに処理することも可能である。
【実施例】
【００４２】
本発明の効果を評価するため、改良したＤＯ−ＶＬＥＩラベルの祖先・子孫関係の判定方法の実験を行った。評価においては、Michigan Benchmark（Kanda Runapongsa, Jignesh M.Patel, H.V.Jagadish, Yun Chen, and Shurug Al-Khalifa. Michigan benchmark: Towards xml query performance diagnostics. In Proceedings of the 29th VLDB Conference, 2003. 参照）を用いた。なお、Michigan Benchmarkは、ＸＭＬデータベースのsize，fanout，depthが問い合わせ処理(ＸＭＬ query processing) に与える影響を測定し、データベースの処理性能を評価することができるソフトウェアである。
Query Setは、その性能評価の内容によって分類されている。ＸＭＬ dataは、nodeの選択度(selectivity)，depth，fanout、などの特性を指定し、それぞれの特性がquery processingに与える影響を測定できるようになっている。祖先・子孫関係の判定処理を評価することが目的であることから、Michigan Benchmarkの中のStructural Selection Query(QS)を使用した。
【００４３】
1.実験準備
実験に用いたＸＭＬ文書は、Michigan BenchmarkのDataSetsの１つであるds0.1xを用いた(file size：45MB、要素ノード数：67696nodes)。表２にds0.1xの情報を示す。
【表２】
2006228070.tif 000004
【００４４】
ds0.1xをPostgreSQLのRDBに格納した。ＸＭＬ文書を格納するテーブルのスキーマを表３に示す。
【表３】
2006228070.tif 000005
【００４５】
Michigan Benchmarkを行なうに当たり、ノードのSelectivity(選択度)の指標となる("aLevel","aFour","aSixteen","aSixtyFour")というcolumnを加え、それぞれに値を格納した。表４にSelectivityを示す。例えば、属性"aFour"のSelectivityは1/4であり、「aFour=0」という条件からは、66655nodesのうち16663nodes(=666551/4)が選ばれる。
表４において、aFour=0,1,2,3の値をとり、各値のselectivityは等しい。selectivity＝1/4は全体のノードの1/4が同じ値を持つということを意味する。また、aLevelの値は深さを表す。fanoutは１つのノードの子の数を表す。
【表４】
2006228070.tif 000006
【００４６】
逆ＤＯ−ＶＬＥＩラベルの格納データ型には、PostgreSQLの可変長数値型であるNUMERICを用いた。文字列ＤＯ−ＶＬＥＩラベルは、可変長文字列型TEXTで格納した。NUMERICで格納した場合の検索速度も測定したが、TEXTで格納した場合とほとんど差はなかった。
本実施例では、
（１）従来の文字列DeweyＶＬＥＩラベルを使用し、パターンマッチングにより判定する方法
（２）整数を用いた前順後順法(2つの番号[preoder,postorder]の大小関係比較により判定する方法)
（３）逆ＤＯ−ＶＬＥＩラベルでmod()を使う方法
（４）文字列ＤＯ−ＶＬＥＩラベルでsubstring()を使う方法
の４つの祖先子孫関係の判定方法による検索処理時間を比較した。QS21を例として、祖先子孫関係の判定方法の違いを下記に示す。
【００４７】
［先祖子孫関係の判定法の比較(QS21の例)］
QS21:Select nodes with aLevel = 13
that have a descendant with aSixteen = 3
SQL example for each method
<Range Labeling (Preoder Postorder method)>
SELECT  DISTINCT  ancestor
FROM  node ancestor,
node descendant
WHERE  ancestor.aLevel=13
AND  descendant.aSixteen=3
AND  descendant.PREORDER > ancestor.PREORDER
AND  descendant.POSTORDER < ancestor.POSTORDER;
<original DeweyVLEI (Using Pattern Matching)>
SELECT  DISTINCT  ancestor
FROM  node ancestor,
node descendant
WHERE  ancestor.aLevel=13
AND  descendant.aSixteen=3
AND  descendant.LABEL  LIKE  ancestor.LABEL||'9%';
<new DeweyVLEI (Using Substring() method)>
CREATE  TABLE  t1  AS
(SELECT  DISTINCT  LENGTH  FROM  node WHERE aLevel=13);
CREATE  TABLE  t2  AS
(SELECT  DISTINCT  substring(descendant.LABEL,1,t1.LENGTH)
FROM  node descendant,  t1 
WHERE  descendant.LENGTH > t1.LENGTH
AND  descendant.aSixteen=3);
SELECT  DISTINCT  ancestor
FROM  node  ancestor,   t2
WHERE  ancestor.LABEL = t2.substring
AND  ancestor.aLevel = 13;
【００４８】
実験環境は表５の通りである。
【表５】
2006228070.tif 000007
【００４９】
２．問合わせの内容
本実施例では、Michigan Benchmarkの問い合わせのうち、祖先子孫判定を必要とする問い合わせを用いた。Michigan Benchmarkには問い合わせのセットに、Ancestor-Descendant Selection(QS21〜27、QS31〜35)があり、これを用いた。このAncestor-Descendant Selectionは、祖先の条件と子孫の条件が与えられ、条件を満たす祖先を求めるものである(QS(A)とする)。本実施例では、同じ条件で子孫を求めた場合の処理時間も測定した(QS(D))とする。QS21〜27の各問い合わせの祖先条件、子孫条件を表６に示す。例）QS21:Select nodes with aLevel=13 that have a descendant with aSixteen=3.(祖先条件aLevel=13，子孫条件aSixteen=3)QS31〜33は、図４のように複数の祖先子孫の組がある問い合わせである。
【表６】
2006228070.tif 000008
【００５０】
問い合わせ処理時間(QueryTime)を計測した結果を表７にまとめた。図５〜７では、クエリタイプ別に前順後順法とＤＯ−ＶＬＥＩラベリングのパフォーマンス比をグラフで示す。
図５〜７において、各棒グラフは、以下の場合を示す。
ＶＬＥＩ-mod  ：逆ＤＯ−ＶＬＥＩラベルでmod()を用いた判定法
ＶＬＥＩ-sub  ：ＤＯ−ＶＬＥＩラベルでsubstring()を用いた判定法
ＶＬＥＩ-like ：ＤＯ−ＶＬＥＩラベルをLIKEによるパターンマッチングで用いた従来の判定法
PP(int)       ：整数をラベルに用いた範囲ラベリング法
【００５１】
各QSごとにこの順番でグラフ棒が並んでいる。ＶＬＥＩ-mod、ＶＬＥＩ-subが本稿で改良を試みた判定手法である。
グラフの縦軸は、ＤＯ−ＶＬＥＩラベリング(ＶＬＥＩ-mod,ＶＬＥＩ-sub,ＶＬＥＩ-like)と範囲ラベリング法のパフォーマンス比である。ここでパフォーマンスとは(1/query処理時間)とし、ＤＯ−ＶＬＥＩによる問い合わせ処理時間をＴVLEI、PP(int)による問い合わせ処理時間をＴPPとすると、縦軸のパフォーマンス比は、
Ｒ＝（１／ＴVLEI）／（１／ＴPP）＝ＴPP／ＴVLEI
である。図５〜７では、この値の対数をとって示している。
グラフから、特に祖先選択の問い合わせQS(A)において、新しく用いた祖先子孫判定法ＶＬＥＩ-mod，ＶＬＥＩ-subが格段に速いことがわかる。ＶＬＥＩ-modとＶＬＥＩ-subでは、文字列関数substring()を用いる方法ＶＬＥＩ-subのほうが速い。これは、ＶＬＥＩ-modの処理におけるmod()で大きな桁数の割算が生じているためである。今回は、数値の格納に可変長数値型NUMERICを用いており、計算にコストがかかっている。
【表７】
2006228070.tif 000009
【図面の簡単な説明】
【００５２】
【図１】ＤＯ−ＶＬＥＩによるノードへのラベル付けの例である。
【図２】本発明の概要を説明する図であり、単純な１０進数の自然数で表したDewey Orderのラベルを使用した場合を示す。
【図３】図２の例に対し、処理を効率化した場合を説明する図である。
【図４】実施例に用いたＱＳのQuery Typeを示す図である。
【図５】ＱＳ（Ａ）の範囲ラベリング法とＤＯ−ＶＬＥＩによる方法の性能比を示すグラフである。
【図６】ＱＳ（Ｄ）の範囲ラベリング法をＤＯ−ＶＬＥＩによる方法のパフォーマンス比を示すグラフである。
【図７】ＱＳ３１〜３３，３５の範囲ラベリング法とＤＯ−ＶＬＥＩによる方法のパフォーマンス比を示すグラフである。
【図８】Dewey Order法によるノードへのラベル付けの例である。
【図１】
2006228070.tif 000010
【図２】
2006228070.tif 000011
【図３】
2006228070.tif 000012
【図４】
2006228070.tif 000013
【図５】
2006228070.tif 000014
【図６】
2006228070.tif 000015
【図７】
2006228070.tif 000016
【図８】
2006228070.tif 000017