(57)【要約】【課題】  ＸＭＬデータを更新する場合に、ＸＭＬデータの木構造における節点の混み具合を容易に把握することができるＸＭＬデータに付与する節点の近似ヒストグラム作成方法および、上記近似ヒストグラムを用いた、節点のラベルの設計・管理手法を提供することを目的とするものである。【解決手段】  ＸＭＬデータベースに予め格納されているＸＭＬデータに、ＸＭＬデータを挿入、削除することを内容とする更新操作の列である更新操作列に関して、上記挿入、削除されたＸＭＬデータの節点の位置と、上記節点の所定数の位置に対応する上記挿入されたＸＭＬデータの数から、上記節点の所定数の位置に対応する上記削除されたＸＭＬデータの数を引いた数とを保持する近似ヒストグラムを作成する段階を有することを特徴とするＸＭＬデータに付与する節点の近似ヒストグラム作成方法である。【選択図】  図２
2005115466.tif 000002
【特許請求の範囲】
【請求項１】
ＸＭＬデータベースに予め格納されているＸＭＬデータに関して、上記挿入、削除されたＸＭＬデータの節点の位置と、上記節点の所定数の位置に対応する上記挿入された節点の数から、上記節点の所定数の位置に対応する上記削除された節点の数を引いた数とを保持する近似ヒストグラムを作成する段階を有することを特徴とするＸＭＬデータに付与する節点の近似ヒストグラム作成方法。
【請求項２】
請求項１において、
上記ＸＭＬデータの更新操作に応じて、上記近似ヒストグラムを更新する段階を有することを特徴とするＸＭＬデータに付与する節点の近似ヒストグラム作成方法。
【請求項３】
請求項１において、
上記近似ヒストグラムにおけるヒストグラムの値を、正値に正規化する段階を有することを特徴とするＸＭＬデータに付与する節点の近似ヒストグラム作成方法。
【請求項４】
請求項２において、
上記近似ヒストグラムを更新する段階は、上記ＸＭＬデータの更新操作毎に、上記近似ヒストグラムを更新する段階であることを特徴とするＸＭＬデータに付与する節点の近似ヒストグラム作成方法。
【請求項５】
請求項４において、
上記ＸＭＬデータの更新操作を所定回数実行した後に、上記ＸＭＬデータの節点に付与するラベルに付与されている数字を、上記近似ヒストグラムに基づいて、付け直す段階を有することを特徴とするＸＭＬデータに付与する節点の近似ヒストグラム作成方法。
【請求項６】
請求項４において、
上記ＸＭＬデータを更新操作する毎に、上記ＸＭＬデータの節点に付与するラベルに付与されている数字の混み具合を判定し、この混み具合に応じて、上記ラベルに付与されている数字を、上記近似ヒストグラムに基づいて、付け直す段階を有することを特徴とするＸＭＬデータに付与する節点の近似ヒストグラム作成方法。
【請求項７】
ＸＭＬデータベースに予め格納されているＸＭＬデータに関して、上記挿入、削除されたＸＭＬデータの節点の位置と、上記節点の所定数の位置に対応する上記挿入された節点の数から、上記節点の所定数の位置に対応する上記削除された節点の数を引いた数とを保持する近似ヒストグラムを作成する手順を、コンピュータに実行させるプログラム。
【請求項８】
ＸＭＬデータベースに予め格納されているＸＭＬデータに関して、上記挿入、削除されたＸＭＬデータの節点の位置と、上記節点の所定数の位置に対応する上記挿入された節点の数から、上記節点の所定数の位置に対応する上記削除された節点の数を引いた数とを保持する近似ヒストグラムを作成する手順を、コンピュータに実行させるプログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＸＭＬデータベースについての問合せの処理を効率化する技術であり、ＸＭＬデータの節点に付与するラベルを設けられる技術に係り、特に、ＸＭＬデータを更新した場合、上記ラベルを効率よく管理し、高速かつ安全に、ディスクに格納されているＸＭＬデータを更新する技術に関する。
【背景技術】
【０００２】
図６は、木構造でＸＭＬデータを表現した場合、上記木構造の節点に設けられているラベルの数字の例を示す図であり、ラベル付け手法に従ってラベルの数字を付与した例を示す図である。
【０００３】
図６（１）は、木構造でＸＭＬデータを表現した場合、上記木構造の節点に付与されているラベルの数字を密に付与した例を示す図である。図６（２）は、木構造でＸＭＬデータを表現した場合、上記木構造の節点に付与されているラベルの数字を、その間隔をあけて付与した例を示す図である。
【０００４】
従来の「範囲ラベル付け手法」は、木構造の節点に、前置順（ＸＭＬデータにおける文書順に相当）によって決まる数字と、また、後置順（ＸＭＬデータにおける終了タグの順に相当）によって決まる数字からなる対のラベルを付与する手法である。
【０００５】
そして、木構造における２つの節点同士における先祖子孫関係を判定する場合、上記２つの節点のうちの一方の節点に前置順で付与された数字と、他方の節点に前置順で付与された数字とを比較し、また、上記一方の節点に後置順で付与された数字と、上記他方の節点に後置順で付与された数字とを比較することによって、木構造における上記２つの節点同士における先祖子孫関係を、判定することができる。
【０００６】
このように、節点に付与されたラベルに数字を付与し、これら付与された数字を比較することによって、ＸＭＬデータベースにおける２つの節点の間における先祖子孫関係を指定した問い合わせに回答すれば、コストのかかる親子関係のリンクナヴィゲーションを回避することができる。
【０００７】
図７は、ＸＭＬデータの一例を示す図である。
【０００８】
図８は、図７に示すＸＭＬデータを木構造で表現した図である。
【０００９】
図９は、図８に示す木構造における節点のそれぞれに数字が付与されている例を示す図である。
【００１０】
たとえば、図７に示すＸＭＬデータを、図８に示すように木構造で表現し、図９に示すように、範囲ラベル付けした場合、ＸＭＬデータにおける任意の節点ｖ＝（ａｉ，ｂｊ）と、節点w＝（ａｋ，ｂｌ）との間に、ａｉ＜ａｋ、かつ、ｂｊ＞ｂｌの関係が成り立つときにのみ、節点ｖ＝（ａｉ，ｂｊ）は、節点w＝（ａｋ，ｂｌ）の先祖である。
【００１１】
なお、ａｉは、節点ｖにおいて前置順で付与された数字であり、ｂｊは、節点ｖにおいて後置順で付与された数字であり、ａｋは、節点wにおいて前置順で付与された数字であり、ｂｊは、節点wにおいて後置順で付与された数字である。
【００１２】
この性質を利用すると、／／ｒｄｆ：ＲＤＦ／／ｇｏ：ｎａｍｅのようなＸPathによる問い合わせ（節点「ｒｄｆ：ＲＤＦ」の子孫であるような節点「ｇｏ：ｎａｍｅ」を返す問い合わせ）を処理する際に、大量のＸＭＬデータの節点の親子関係リンクを辿らなくても、節点間の先祖子孫関係がわかるので、「ｒｄｆ：ＲＤＦ」という名前を持つ節点の集合と、「ｇｏ：ｎａｍｅ」という名前を持つ節点の集合とを、Ｂ＋ｔｒｅｅ等の高速な索引を用いて集め、所定の判定条件を用いて、先祖子孫関係を持つもののみを取り出せば、問い合わせの結果を得ることができる。
【００１３】
しかし、上記従来例では、ラベルを付与し、データベースに格納された後に、ＸＭＬデータベースが更新されると、ラベルの更新に手間がかかるという問題がある。
【００１４】
つまり、たとえば、図６（１）に示すように、ラベルの数字を密に付与すると、前置順に付与された数字、後置順に付与された数字ともに、付与された数字の間隔が詰まった状態であるので、図６（１）に示す木構造のどこかにＸＭＬデータを挿入しようとしても、挿入することができない。したがって、上記の場合、ＸＭＬデータが挿入された箇所以降の節点に付与されている前置順の数字と、後置順に付与されている数字とを、全て付け直す必要がある。
【００１５】
図６（２）に示す、節点に設けられるラベルの数字を付与するときに、上記数字を飛び飛びに振る従来例（たとえば、非特許文献１参照）では、ＸＭＬデータ（部分木）を挿入した場合、挿入すべきＸＭＬデータがそれ程大きくなければ、挿入箇所の間隔を利用してＸＭＬデータをラベル付けすればよく、ラベルの数字を付け直す必要がない。つまり、ラベルに付与される数字の間隔をあけておけば、前置順、後置順における順序関係が維持されている限り、節点同士の間における先祖子孫関係を、正しく判定することができる。
【００１６】
しかし、図６（２）に示す従来例では、節点に付与されている数字の間隔は有限であるので、大きなＸＭＬデータを挿入する場合は間隔が足りず、挿入不可能である。また、図６（２）に示す従来例では、小さなＸＭＬデータでも、何回も挿入すると、同様に間隔が足りなくなり、挿入ができなくなる。
【００１７】
一方、動的範囲ラベル付け手法が提案されている（非特許文献２、３）。この「動的範囲ラベル付け手法」は、ＸＭＬデータが更新された場合、図６（２）に示す木構造における所定の節点の周辺の節点のラベルに付与されている数字を、小規模に付け直す手法である。
【００１８】
たとえば、１つの例としては、図６（２）に示す例において、前置順に付与されている数字「１８」が付与されている節点と、前置順に付与されている数字「２７」が付与されている節点との間に、比較的大きなＸＭＬデータを挿入しようとする場合には、上記数字「１８」をたとえば「１１」に付け直し、上記数字「２７」をたとえば「３４」に付け直す。
【００１９】
このように、更新操作の度に、小規模に挿入箇所の間隔を広げてやることによって、大規模なラベルの付け直しを回避し続け、さらに上記大きなＸＭＬデータの挿入や、連続したＸＭＬデータの挿入も可能にする。
【非特許文献１】Shu-Yao Chien, Carlo Zaniolo, Vassilis J. Tsotras, and Donghui Zhang. Storing and Querying Multi-version XML Documents using Durable Node Numbers. In Proc. WISE, 2001.
【非特許文献２】江田毅晴、天笠俊之、吉川正俊、植村俊亮、「更新に強いＸＭＬ節点数え上げ手法とその管理」、情報処理学会研究報告、データベースシステム  2002-DBS-128、2002.
【非特許文献３】江田毅晴、天笠俊之、吉川正俊、植村俊亮、「ＸＭＬのための動的範囲ラベル付け手法：その評価およびＸＲｅｌへの適用について」、情報処理学会研究報告、データベースシステム  DBS-129/BCC-4、2003.
【発明の開示】
【発明が解決しようとする課題】
【００２０】
しかし、上記「動的範囲ラベル付け手法」においては、更新操作列を構成し、ＸＭＬデータを更新し続けると、いずれ、更新操作箇所（ＸＭＬデータの挿入箇所）が偏った場合、つまりある箇所に集中した場合には、そして、ＸＭＬデータの挿入回数が、その削除回数よりも多い場合には、ラベルに付与された数字の間隔が詰まり、小規模なラベルの付け直しでは、ラベルを管理することができず、大規模なラベルの付け直しが発生し、ＸＭＬデータを効率よく更新することができないという問題がある。
【００２１】
本発明は、範囲ラベル付け手法を、ＸＭＬデータベースの更新操作に対応させ、更新操作箇所の分布が偏り、しかも、ＸＭＬデータの挿入回数が削除回数よりも多くなっても、コストを抑えて、ＸＭＬデータの節点に設けられるラベルを管理することができるＸＭＬデータに付与する節点の近似ヒストグラム作成方法を提供することを目的とするものである。
【００２２】
つまり、本発明は、ＸＭＬデータを更新する場合に、ＸＭＬデータの木構造における節点の混み具合を容易に把握することができるＸＭＬデータに付与する節点の近似ヒストグラム作成方法および、上記近似ヒストグラムを用いた、節点のラベルの設計・管理手法を提供することを目的とするものである。
【課題を解決するための手段】
【００２３】
本発明は、ＸＭＬデータベースに予め格納されているＸＭＬデータに、ＸＭＬデータを挿入、削除することを内容とする更新操作の列である更新操作列に関して、上記挿入、削除されたＸＭＬデータの節点の位置と、上記節点の所定数の位置に対応する上記挿入されたＸＭＬデータの数から、上記節点の所定数の位置に対応する上記削除されたＸＭＬデータの数を引いた数とを保持する近似ヒストグラムを作成する段階を有することを特徴とするＸＭＬデータに付与する節点の近似ヒストグラム作成方法である。
【発明の効果】
【００２４】
本発明によれば、ＸＭＬデータを更新する場合に、ＸＭＬデータの節点に付与するラベルの混み具合を容易に把握することができるという効果を奏し、さらに、作成された近似ヒストグラムに基づいて、節点に付与するラベルの設計および更新を効率よく行うことができるという効果を奏する。
【発明を実施するための最良の形態】
【００２５】
発明を実施するための最良の形態は、以下の実施例である。
【実施例１】
【００２６】
図１は、本発明の実施例１であるＸＭＬデータに付与する節点の近似ヒストグラム作成方法によって作成された近似ヒストグラムＨの例を示す図である。
【００２７】
上記「近似ヒストグラムＨ」は、ＸＭＬデータベースに予め格納されているＸＭＬデータに、ＸＭＬデータを挿入、削除することを内容とする更新操作の列である更新操作列に関して、上記挿入、削除されたＸＭＬデータの節点の位置と、上記節点の所定数の位置に対応する上記挿入されたＸＭＬデータの数から、上記節点の所定数の位置に対応する上記削除されたＸＭＬデータの数を引いた数とを保持するものである。
【００２８】
ヒストグラムＨの初期化パラメータとして、ヒストグラムの大きさsizeと、ＸＭＬデータを更新することができる操作回数の最大値deltaとを与え、下記のようにヒストグラムＨを作成する。
【００２９】
ヒストグラムＨ＝（ｈ１，ｈ２，…，ｈsize）
なお、ｈ１，ｈ２，…，ｈsizeは、ヒストグラムの値であり、ｈ（ｉ）とｈｉとは、同じ意味である。ｉは、上記更新操作列に関して、上記挿入、削除されたＸＭＬデータの節点の位置である。
【００３０】
初期化時において、ＸＭＬデータの更新操作が生じていないので、ヒストグラムの値ｈ（ｉ）＝０である。なお、１≦ｉ≦sizeである。
【００３１】
ＸＭＬデータを更新変更することができる操作回数の最大値deltaは、近似ヒストグラムＨにおける有効更新回数を定めるものであり、更新操作回数が、最大値delta回に達した時点で、近似ヒストグラムＨを利用して、節点に付与されているラベルの数字を全て付け直す処理を実行することができ、または、近似ヒストグラムＨをクリアする処理を実行することができる。
【００３２】
また、近似ヒストグラムＨの状態を保持する変数は、最小値min、和sum、ＸＭＬデータを更新操作した回数countである。上記「最小値min」は、ヒストグラムＨ中に出現したヒストグラムの値ｈｉの最小値である。和sumは、ヒストグラムの値ｈｉの全ての和である。更新操作の回数countは、実際に更新操作した回数である。
【実施例２】
【００３３】
拡張前置順列を、（ａ１，ａ２，…，ａｎ）とし、ＸＭＬデータを、位置ａｋとａｋ＋１との間に挿入したとする。なお、１≦ｋ≦ｎ−１である。また、ここでは、挿入されるＸＭＬデータの節点数、または削除されるＸＭＬデータの節点数を考慮しない。
【００３４】
また、０＜ａｋ／width≦１である。
【００３５】
なお、上記「width」は、ＸＭＬデータの木構造における節点に設けられるラベルに付与される数字の最大値である。
【００３６】
したがって、０＜ａｋ／width×size≦sizeであるので、ＸＭＬデータを１回、挿入すれば、ヒストグラム中の値ｈ（［ａｋ／width×size］）に、挿入操作が１回起こった記録として、１を加える。
【００３７】
位置ａｋ〜ａｋ＋ｍの間で、ＸＭＬデータの削除が１回生じれば、近似ヒストグラムＨ中の位置を決めるまでは、ＸＭＬデータの挿入処理を実行する処理と同様に処理し、削除操作が１回起こった記録として、ヒストグラム中の値ｈ（［ｋ／width×size］）から１を引く。
【００３８】
パラメータである和sumについては、ＸＭＬデータを挿入する場合、sum＝sum＋１とし、ＸＭＬデータを削除する場合、sum＝sum−１とすることによって、和sumを更新する。
【００３９】
更新操作の回数countは、ＸＭＬデータを更新する度に、単純に加算すれば充分である。
【００４０】
ＸＭＬデータを更新操作する度に、和sumと更新操作回数countとを、近似ヒストグラムＨ中の値にアクセスしなくても、更新することができるのに対して、最小値minは更新することができない。そこで最小値ｍｉｎはヒストグラムの値をスキャンして、更新することにする。
【００４１】
なお、拡張前置順列（ａ１，ａ２，…，ａｎ）に関する上記説明を、拡張後置順列についても同様に適用することができる。
【実施例３】
【００４２】
ＸＭＬデータの操作回数が、操作回数の最大値delta回に達したタイミングで、近似ヒストグラムＨの分布を利用して、拡張前置順列（ａ１，ａ２，…，ａｎ）の全てのラベルに付与されている数字を均す。近似ヒストグラムＨを利用することによって、ＸＭＬデータの挿入が多く起こる箇所では、ラベルに付与される数字の間隔を予め広げ、削除が多い箇所では、ラベルに付与される数字の間隔を予め狭めることができる。
【００４３】
実施例３は、拡張前置順列（ａ１，ａ２，…，ａｎ）の間隔列の分布を考え、この間隔列を、近似ヒストグラムＨ中の値の分布に近似させる実施例である。
【００４４】
図２は、上記実施例１において、節点に設けられるラベルに付与される数字を、近似ヒストグラムＨを用いて、均す動作を示すフローチャートである。
【００４５】
まず、拡張前置順列（ａ１，ａ２，…ａｎ）、近似ヒストグラムＨにおけるヒストグラムの値（ｈ１，ｈ２，…ｈｍ）（ｍは、ｓiｚeである）、ヒストグラムの値の和sum、ヒストグラムの値の最小値minを、実施例１によって得る（Ｓ１）。
【００４６】
そして、図３で後述するように、近似ヒストグラムＨを正値に変換し（正規化し）、つまり、最小値minを正しい値に更新し、ヒストグラムの値（ｈ１，ｈ２，…ｈｍ）を、（ｈ１＋１−min，ｈ２＋１−min，・・・，ｈｍ＋１−min）に正値化し、sum＝sum−（min−１）ｍとし、正値化されたヒストグラムの和を得る（Ｓ２）。次に、近似ヒストグラムＨを参照しながら、ＸＭＬデータにおける節点に設けられているラベルに付与されている数字を、昇順に付け直し（Ｓ３）、必要であれば近似ヒストグラムＨを初期化し（Ｓ４）、終了する。
【００４７】
上記近似ヒストグラムＨを参照しながら、ラベルに付与されている数字を、昇順に付け直す（Ｓ３）場合、定数constを、ｍ＊width／（ｎ＊sum）とし、拡張前置順列における数字ａ０を、０とし、位置ｉを、０とする（Ｓ３１）。
【００４８】
そして、数字ａｉ＋１に、ａｉ＋｛ｈ（｜ｉ＊ｍ／ｎ｜）＋１−ｍ｝｝＊ｃｏｎｓｔを代入し（Ｓ３２）、位置ｉがｎ未満であれば（Ｓ３３）（ｎは、節点数である）、ステップＳ３２における代入を再び実行し、これを繰り返し、位置ｉがｎに等しくなれば（Ｓ３３）、リターンする。
【００４９】
ステップＳ３（近似ヒストグラムＨを参照しながら、ラベルに付与される数字を、昇順に付け直す処理）において、ＸＭＬデータの節点に設けられるラベルに付与される数字を、拡張前置順列に対して昇順に付け直すが、その際に、数字ａｉ＋１から、数字ａｉを引いた差分が、近似ヒストグラムＨ上で対応する値を、ラベル列上の値に変換したものになるように、先程のconstの値を用いて、数字ａｉ＋１の値を付け直す。つまり、定数constはヒストグラム中の値をラベル列中の値に変換している。
【００５０】
上記実施例１、２において作成した近似ヒストグラムＨは、ＸＭＬデータを削除する際に、ＸＭＬデータを１つ削除する毎に、該当するヒストグラムの値から１を引くので、所定の時点で、ヒストグラムの値が負になる位置がある。
【００５１】
図２に示す例では、この近似ヒストグラムＨ中の値の分布を、拡張前置順列の分布へ反映する場合の一例として、ヒストグラムの値を正値に正規化する。これによって、ヒストグラムの値の和の中で、対応するヒストグラム中の値がどれくらいの割合であるのかを計算することができる。
【００５２】
図３は、実施例３において、ヒストグラムの値を、正値に正規化する一例を示す図である。
【００５３】
最小値minを更新し、各ヒストグラムの値から、最小値minを引き、１を加えることによって、図３の下に示すように、全てのヒストグラムの値を正の値に変換する。つまり、各ヒストグラムの値を一律に底上げする。
【００５４】
なお、各ヒストグラムの値から、最小値minを引いただけで、その後に「１を加えない」と、ヒストグラムの値が「０」である位置がある。
【００５５】
さらに、和sumに、｜size＊（min−１）｜を加算し、この加算結果を、変換された正値近似ヒストグラムＨの和に置き換えることができる。このように置き換えられた（更新された）和sumで、位置に対応するヒストグラムの値を割ることによって、所定の位置において、数字ａｉ＋１とａｉとの間隔を、どの程度あけるかを判定する。つまり、（対応する部分）／（ヒストグラム全体）を求めることによって、全体の中での割合を考える。
【実施例４】
【００５６】
そして、ＸＭＬデータを所定回数、更新する毎に、上記更新された近似ヒストグラムＨを利用して、当該ラベルに付与されている数字（位置）の周辺において、その付与されている数字を小規模に付け直し、これによって、ラベルに付与されている数字を大規模に付け直す処理を避け続ける。
【００５７】
ＸＭＬデータの更新操作が、ＸＭＬデータを挿入する場合であっても、また、削除する場合であっても、節点に設けられているラベルに付与されている数字を付け直す方法は、基本的には変わらない。以下、ＸＭＬデータを挿入する操作について説明する。
【００５８】
図４は、実施例４において、ＸＭＬデータを所定回数、更新する毎に、上記更新された近似ヒストグラムＨを利用して、当該ラベルに付与されている数字（位置）の周辺において、その付与されている数字を小規模に付け直す動作を示すフローチャートである。
【００５９】
まず、挿入箇所を示す変数として、positionを設定し、節点の数として、numを設定し（Ｓ１１）、ＸＭＬデータを挿入することができれば（Ｓ１２）、挿入箇所の間隔の割合が、対応する近似ヒストグラムＨの全体での割合の上下定数倍の閾値内に収まるかどうかを判断し（Ｓ１３）、挿入不可能であると判断されれば（Ｓ１２）、処理を終了する。挿入箇所の間隔の割合が、対応する近似ヒストグラムＨの全体での割合の上下定数倍の閾値内に収まれば（Ｓ１３）、挿入箇所の間隔を、挿入節点に割り当て、対応する近似ヒストグラムＨの分布を反映させて挿入し（Ｓ１４）、終了する。
【００６０】
挿入箇所の間隔の割合が、対応する近似ヒストグラムＨの全体での割合の上下定数倍の閾値内に収まらなければ（Ｓ１３）、節点の数numを、num＋２、挿入箇所の変数positionを、position−１とし、ステップＳ１３に戻る（Ｓ１５）。
【００６１】
拡張前値順列中の挿入箇所に対応する近似ヒストグラムＨにおける各ヒストグラムの値を認識する方法は、基本的には、実施例３と同じであるが、小規模にしか、ラベルを付け直さないので、位置に対応するヒストグラムの値を、必ずしも正確に反映せずに、上限、下限の閾値を決め（対応するヒストグラム箇所をラベル列上の値に変換した値に、定数ｍｉｎ、ｍａｘをかけて求める）、挿入箇所の間隔が、上記決めた上限と下限とによって定められる範囲に収まらないときにのみ、ラベル列の周辺のラベルを、閾値に収まるまで、昇順降順に辿り（挿入箇所の間隔から両脇へ１つずつ広げ）、収まったら、挿入箇所の間隔を、等分割または対応するヒストグラムの分布を反映させて、小規模に付け直す。
【００６２】
ＸＭＬデータを削除する操作の場合も、ＸＭＬデータを挿入する操作と同様であり、削除対象の節点を削除した後に、新たに発生した数字の間隔にＸＭＬデータを挿入する操作と同じアルゴリズムを適用すればよい。
【００６３】
図５は、上記範囲ラベル付け手法を利用したＸＭＬデータベース１０を示すブロック図である。
【００６４】
ＸＭＬデータベース１０は、ＸＭＬデータ２０を受け、ＸＭＬデータの木構造の節点に設けられるラベルに数字を付与するラベル付け手段３０と、ＸＭＬデータの木構造を分解し、格納する分解・格納手段４０と、上記分解された木構造を記憶する二次記憶装置５０と、問い合わせ・更新処理モジュール６０をと有する。
【００６５】
問い合わせ・更新処理モジュール６０は、利用者７０が問い合わせると、問い合わせと更新要求とを処理し、問い合わせ構文解析モジュールと、評価・実行（検索）モジュールと、更新操作実行モジュールとを有する。
【００６６】
上記更新操作実行モジュールは、格納されているＸＭＬデータの再構成と、ラベルの付け直しとを伴い、従来は、コストの高い処理が要求されている。
【００６７】
しかし、上記実施例によって、再構成（ラベルに付与されている数字の総付け替え）の回数が大幅に減り（再構成を、小規模な部分付け直し処理に分散させて、コストを減らし）、小規模な部分更新を中心としてデータを保持することができる。
【００６８】
上記実施例によれば、ＸＰａｔｈによる問い合わせを高速に処理するＸＭＬデータベースにおいて、更新処理等によるシステム停止を避け続けることができる。
【００６９】
上記実施例を、コンピュータで使用可能なプログラムとして実施することができる。
【００７０】
つまり、上記実施例は、ＸＭＬデータベースに予め格納されているＸＭＬデータに関して、上記挿入、削除されたＸＭＬデータの節点の位置と、上記節点の所定数の位置に対応する上記挿入された節点の数から、上記節点の所定数の位置に対応する上記削除された節点の数を引いた数とを保持する近似ヒストグラムを作成する手順を、コンピュータに実行させるプログラムの例である。
【００７１】
また、上記プログラムを、ハードディスク、ＣＤ−ＲＯＭ、光記憶装置または磁気記憶装置等、コンピュータ可読の記録媒体に記録するようにしてもよい。
【００７２】
つまり、上記実施例は、ＸＭＬデータベースに予め格納されているＸＭＬデータ関して、上記挿入、削除されたＸＭＬデータの節点の位置と、上記節点の所定数の位置に対応する上記挿入された節点の数から、上記節点の所定数の位置に対応する上記削除された節点の数を引いた数とを保持する近似ヒストグラムを作成する手順を、コンピュータに実行させるプログラムを記録したコンピュータ読取可能な記録媒体の例である。
【図面の簡単な説明】
【００７３】
【図１】本発明の実施例１であるＸＭＬデータに付与する節点の近似ヒストグラム作成方法によって作成された近似ヒストグラムＨの例を示す図である。
【図２】上記実施例１において、節点に設けられるラベルに付与される数字を、近似ヒストグラムＨを用いて、均す動作を示すフローチャートである。
【図３】実施例３において、ヒストグラムの値を、正値に正規化する一例を示す図である。
【図４】実施例４において、ＸＭＬデータを所定回数、更新する毎に、上記更新された近似ヒストグラムＨを利用して、当該ラベルに付与されている数字（位置）の周辺において、その付与されている数字を小規模に付け直す動作を示すフローチャートである。
【図５】上記範囲ラベル付け手法を利用したＸＭＬデータベース１０を示すブロック図である。
【図６】木構造でＸＭＬデータを表現した場合、上記木構造の節点に設けられているラベルの数字の例を示す図である。
【図７】ＸＭＬデータの一例を示す図である。
【図８】図７に示すＸＭＬデータを木構造で表現した図である。
【図９】図８に示す木構造における節点のそれぞれに数字が付与されている例を示す図である。
【符号の説明】
【００７４】
Ｈ…近似ヒストグラム、
ｈｉ…ヒストグラムの値、
i…位置、
width…ラベルに付与する数字の最大値、
sum…ヒストグラムの値の和、
ｍiｎ…ヒストグラムの値の最小値、
const…更新操作の回数、
size…ヒストグラムの大きさ、
delta…操作回数の最大値。
【図１】
2005115466.tif 000003
【図２】
2005115466.tif 000004
【図３】
2005115466.tif 000005
【図４】
2005115466.tif 000006
【図５】
2005115466.tif 000007
【図６】
2005115466.tif 000008
【図７】
2005115466.tif 000009
【図８】
2005115466.tif 000010
【図９】
2005115466.tif 000011