JPH1063671A - 木構造データ管理方法 - Google Patents

Abstract

(57)【要約】 【課題】 ノード間の祖孫関係の評価を少ないデータ量
で迅速に行うことのできるとともに、部分的な更新を容
易に実現する。 【解決手段】 各ノードに階層の下位方向を優先した順
番でノード識別番号を付与し、各ノードに自己のノード
識別番号と自己ノードの最後の順番の子孫ノードに付与
したノード識別番号（子孫識別番号）とのみを対応付け
て記憶することにより、各ノードに関連する子孫ノード
を管理する。さらに、第１の木構造データ内の更新対象
であるノードを、第２の木構造データの親ノード「Ｆ」
に置換させて、第１の木構造データを増加させる場合
に、第２の木構造データのノードに階層の下位方向を優
先した順番でノード識別番号を付与し、前記第１の木構
造データの木構造データ識別子、第２の木構造データの
木構造データ識別子及び前記第１の木構造データの置換
されるノードのノード識別番号とを対応付けて管理する
ことによって、各ノードに関連する子孫ノードを管理す
る。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、複数のノードをリ
ンクさせて階層を形成した木構造データを管理する木構
造データ管理方法に関し、例えば、ノード間の接続関係
を検索式等によって評価等される木構造データを管理す
る木構造データ管理方法に関する。

【０００２】

【従来の技術】従来から文書情報等を複数のノードによ
って階層を形成した木構造データとして管理し、例えば
文書情報の検索等が行われている。このような複数のノ
ードによって階層を形成された木構造データを検索する
場合には、ノードの情報を検索するだけでなく、ノード
間の親子関係、兄弟関係、祖孫関係といった接続条件を
評価するといったことが生じている。

【０００３】例えば、親子関係、兄弟関係の接続関係を
評価する場合には、評価する対象のノードは限られた狭
い範囲に属しているため、関連するデータをまとめてお
いたり、関連するノード間のリンク情報を利用すること
で容易に評価することができる一方、祖孫関係を評価す
る場合には、評価する対象のノードが広範囲に渡るため
に、前者に比べて困難となっている。

【０００４】ここで、従来の木構造データの管理方法を
祖孫関係を評価する場合を例にとって以下に説明する。
まず、オブジェクト指向データベースの永続データと永
続データへのポインタによって木構造データを管理する
方法（以下、第１従来例という。）を説明する。

【０００５】この方法は、永続データオブジェクトと永
続ポインタとを利用してノードとノード間の接続状況を
表すリンク情報を格納しており、ノードを検索する場合
には索引を利用することができる。この方法において、
子孫候補のノードと祖先候補のノードとの２つのノード
に対する祖孫関係を評価する場合には、まず、子孫候補
のノードの親であるノードをリンク情報によって取り出
し、さらに、リンク情報を辿ることを繰り返し、祖先候
補のノードと比較することになる。したがって、子孫候
補のノードから当該子孫候補に対するすべての祖先のノ
ードを取り出さなければ祖孫関係を有しないことを知る
ことができない。

【０００６】図６の木構造データを参照して具体的に説
明すると、例えば、子孫候補がノード「ｇ」であり、祖
先候補がノード「ｄ」である場合に、祖孫関係の評価を
行う場合には、ノード「ｇ」の親のノード「ｆ」を取り
出さなければ評価することができない。また、子孫候補
がノード「ｇ」であり、祖先候補がノード「ｂ」である
場合に祖孫関係を評価する場合には、ノード「ｆ」
「ｄ」「ａ」の３つのノードを取り出してノード「ｂ」
と比較することではじめて祖孫関係がないことを知るこ
とができる。したがって、ノードの取り出し回数が多く
なってしまい、迅速に祖孫関係を評価することができな
い。

【０００７】次に、公開特許公報 平 ４−３０９１７２
号に記載された発明及びマルチインデックスの場合にお
ける木構造データを管理する方法（以下、第２従来例と
いう。）として、図６に示す木構造データに適用した例
を図７を参照して説明する。この方法は、或るノードか
ら別のノードへ木構造データの構造に関係なく、素早く
アクセスするためのパスを用意しており、祖孫関係を評
価するためには、すべてのノードから当該ノードの全子
孫へのパスを用意することになる。

【０００８】このままでは祖孫関係を評価する場合に、
第１従来例と同様な回数の比較処理が必要となってしま
うため、新たにパスの集合に対して索引を生成すること
によって比較処理の回数を減少することを可能にしてい
る。しかしながら、上記したように全ノードに対してパ
スの集合を用意しなければならないため、パス集合の生
成コスト及びパスの集合が必要とするデータ量が膨大と
なってしまう。

【０００９】次に、特許公報 平４−６５４２７号に記
載された発明及びパスインデックスを使用した場合にお
ける木構造データを管理する方法（以下、第３従来例と
いう。）として、図６に示す木構造データに適用した例
を図８を参照して説明する。

【００１０】この方法は、或るノードの索引として、当
該ノードの祖先への情報のリストを用意しており、前記
索引を利用することによって、或るノードからその子孫
のノードへ素早くアクセスできる。このように、或るノ
ードから個々のノードへアクセスする処理のコストを改
善することができるものの、祖孫関係を評価する場合に
おいては、祖先候補のノードから辿れる各子孫のノード
にアクセスすることが必要となっており、ノードに対す
るアクセス回数、比較回数を何ら改善することはできな
い。

【００１１】次に、接続行列によって木構造データを管
理する方法（以下、第４従来例という。）を説明する。
この方法は、すべてのノードに対して祖孫関係に関する
接続行列を保持しており、図６に示す木構造データを接
続行列で表した例を図９を参照して説明する。各ノード
に各行が対応しており、行内の数値の桁数は木構造デー
タ中のノードの総数と同数になっている。そして、数値
のそれぞれの桁がノード「ａ」からノード「ｉ」の各ノ
ードを表しており、数値に「１」が設定されている場合
には、該当するノードが行に対応するノードの階層以下
であることを示している。例えば、ノード「ｂ」の対応
する行の数値は「０１１００００００」となっており、
ノード「ｂ」の階層以下には自分自身のノード「ｂ」と
ノード「ｃ」があることを表している。上記した接続行
列にはノード総数の自乗ものデータ量が必要となってお
り、例えば、木構造データに対して追加や更新を行う場
合には、接続行列内のデータ全体を更新する必要が生じ
ている。

【００１２】次に、デューイの１０進分類法によって木
構造データを管理する方法（以下、第５従来例とい
う。）として、図６に示した木構造データをＯＤＡ（Of
fice Document Architecture:ＩＳＯ ８６１３）文書
とみなした場合にＯＤＡ文書のオブジェクト識別子を適
用した例を図１０を参照して説明する。

【００１３】この方法は、ノードの階層の深さと同数の
数値列をノードに与えて、当該ノードの木構造データ内
での位置を表しており、祖孫関係の評価対象となる２つ
のノードの評価を行う場合には、他のノードにアクセス
することなく、与えられた数値列のデータを比較するだ
けで祖孫関係を評価できる。この方法では、数値列の大
きさは階層の深さに比例し、祖孫関係の評価において行
われる数値列の各数値の比較の回数も階層の深さに比例
する。また、ノードに与える数値列が必要となるデータ
量は階層の深さが深くなるほど大きくなる。一般的な木
構造データでは、数十もの数値列の大きさが必要とな
る。

【００１４】次に、ＨｙＴｉｍｅ（ＩＳＯ １０７４
４）のパスロケーションによって木構造データを管理す
る方法（以下、第６従来例という。）を説明する。この
方法は、祖孫関係をもったノードに同じ番号を割り当て
たパスロケーションによって木構造データを管理する方
法であり、ノードに対してアクセスすることなく、祖孫
関係を評価することができる。

【００１５】例えば、図６に示す木構造データにパスロ
ケーションの番号を割り当てたものを図１１を参照して
説明する。１つのカラムは祖孫関係を持ったノードの集
合を保持しており、各カラムには番号が割り当てられて
いる。例えば、ノード「ａ」「ｂ」「ｃ」は、番号
「１」のカラムに保持されており、ノード「ａ」「ｂ」
「ｃ」には祖孫関係があることを表す。また、同様にノ
ード「ａ」「ｄ」「ｅ」も番号「２」のカラムによって
祖孫関係があることが表されている。上記したカラムの
数は末端となるノードの数と同数となっており、祖孫関
係を評価する際には最大で末端となるノードの数と同数
の比較処理が必要となる。

【００１６】この方法においては、例えば、中間の階層
に存在するノード情報に変更が加えられた場合において
は、ルートのノードから順にパスロケーションを振り直
さなければならず、更新に手間がかかるとともに、木構
造データを共同して編集することができない。

【００１７】

【発明が解決しようとする課題】上記したように、従来
の木構造データ管理方法では、祖孫関係の評価を行うた
めに多くのデータ量を必要とするといった問題や、祖孫
関係を評価する場合に評価処理に手間がかかるといった
問題や、木構造データを部分的に更新する場合に祖孫関
係の評価ができるように維持するための手間がかかると
いった問題があった。

【００１８】本発明は、ノード間の祖孫関係の評価を少
ないデータ量で迅速に行うことのできるとともに、部分
的な更新を容易に行うことのできる木構造データを管理
する木構造データ管理方法を提供することを目的として
いる。

【００１９】

【課題を解決するための手段】上記目的を達成するため
に本発明の請求項１に係る木構造データ管理方法は、複
数のノードをリンクさせて階層を形成した木構造データ
を管理する木構造データ管理方法において、各ノードに
階層の下位方向を優先した順番で番号を付与し、各ノー
ドに自己の番号と自己ノードの最後の順番の子孫ノード
に付与した番号とのみを対応付けて記憶することによ
り、各ノードに関連する子孫ノードを管理することを特
徴とする。

【００２０】したがって、請求項１に係る木構造データ
管理方法によって管理される木構造データでは、祖先対
象のノードと子孫対象のノードとの祖孫関係の評価を行
う場合においては、各ノードが記憶している自己の番号
と自己のノードの最後の順番の子孫ノードに付与した番
号とのみといった少ないデータ量の情報だけで、祖先対
象のノードに付与されている番号から祖先対象ノードの
子孫ノードを把握することによって当該子孫ノードに子
孫対象のノードが属しているか否かといった祖孫関係の
有無を知ることができる。ただし、上記ではノードに２
つの情報のみを記憶することによって祖孫関係を管理し
ているが、これは管理において各ノードに必要に応じて
前記２つの情報以外の情報を付与することを除外するも
のではない。

【００２１】本発明の請求項２に係る木構造データ管理
方法は、請求項１に記載した木構造データ管理方法にお
いて、更新される対象であり識別子を有する第１の木構
造データ内のノードを、識別子を有する第２の木構造デ
ータの親ノードに置換させて、第１の木構造データを増
加させる場合に、第２の木構造データ内のノードに階層
の下位方向を優先した順番で固有の番号及び、自己ノー
ドの最後の順番の子孫ノードに付与した番号とを付与
し、前記第１の木構造データの識別子、第２の木構造デ
ータの識別子及び前記第１の木構造データの置換される
ノードの番号とを対応付けて管理することによって、各
ノードに関連する子孫ノードを管理することを特徴とす
る。

【００２２】したがって、請求項２に係る木構造データ
管理方法では、第２の木構造データといった限られた範
囲のノードに対して固有の番号と各ノードの最後の順番
の子孫ノードに付与した固有の番号を付与するととも
に、第１の木構造データの識別子、第２の木構造データ
の識別子、第１の木構造データの置換されたノードの番
号とを対応付けることによって、第１の木構造データと
第２の木構造データとを組み合わせるといった更新処理
ができる。

【００２３】そして、この第１の木構造データと第２の
木構造データが組み合わされた木構造データにおいて
は、第２の木構造データのノード間の祖孫関係について
は上記固有の番号と自己ノードの最後の順番の子孫ノー
ドに付与した固有の番号とによって評価することができ
る。また、第１の木構造データのノードと第２の木構造
データのノードとの祖孫関係については、第１の木構造
データの識別子と第２の木構造データの識別子とに対応
付けられている第１の木構造データ内の置換されたノー
ドの番号を、第２の木構造データのノードの番号として
扱うことによって評価することができる。

【００２４】ここで、各ノードに階層の下位方向を優先
した順番で番号を付与するとは、木構造データにおいて
ノードからリンクが結ばれている下位のノードがあれ
ば、当該下位のノードを優先して辿り、辿った順番に従
って一定の順番を表す番号を付与することをいい、図６
で示す木構造データにおいては、例えば、ノード「ａ」
「ｂ」「ｃ」「ｄ」「ｅ」「ｆ」「ｇ」「ｈ」「ｉ」に
対して、それぞれ、「１」、「２」「３」「４」「５」
「６」「７」「８」「９」といった番号を付与すること
をいう。また、自己のノードの最後の順番の子孫ノード
に付与した番号とは、例えば、図６でのノード「ｄ」の
場合には最後の順番となっている子孫ノード「ｈ」に与
えられている番号「８」のことをいう。

【００２５】

【発明の実施の形態】本実施例に係る木構造データ管理
方法を実施する管理装置の一例を図１を参照して説明す
る。この管理装置は、ノード及びノードの階層を表すリ
ンク情報によって形成された木構造データを入力する構
造データ入力手段１と、木構造データの格納処理及び削
除処理を制御する木構造データ格納／削除手段２と、ノ
ードを格納するノード情報蓄積手段３と、リンク情報を
格納するリンク情報格納手段４と、木構造データを識別
する構造データ識別子及びノードに付与するノード識別
番号を入力する識別子入力手段５と、ノードにノード識
別番号を割り当てるノード識別番号設定手段６と、構造
データ識別子を管理する構造データ識別管理手段７と、
を備えている。

【００２６】まず、この管理装置が木構造データを新規
に格納する場合の動作を説明する。構造データ入力手段
１から木構造データが入力されると、入力された木構造
データを構造データ格納／削除手段２に渡す。そして、
構造データ識別子管理手段７が入力された木構造データ
に与える構造データ識別子を生成する。

【００２７】そして、ノード識別番号設定手段６がルー
トとなるノードから階層の下位方向を優先した順番でノ
ード識別番号を各ノードに割り当て、各ノードに自己の
ノード識別番号を設定し、リンク情報に当該ノード識別
番号と当該ノードの最後の順番の子孫ノードに付与した
ノード識別番号とを設定する。以下、設定した子孫ノー
ドのノード識別番号を子孫識別番号という。次いで、構
造データ格納／削除手段２が構造データ識別子とノード
識別番号とノードとを組にしてノード情報蓄積手段３に
格納するとともに、構造データ識別子とノード識別番号
と子孫識別番号とをリンク情報蓄積手段４に格納する。

【００２８】この動作によって、図６に示す木構造デー
タを格納した場合には、図２に示すようにノード情報蓄
積手段３にはノード情報３ａが格納され、リンク情報蓄
積手段４にはリンク情報４ａが格納される。

【００２９】すなわち、ノード情報３ａには、当該ノー
ドの属する木構造データの構造データ識別子３ａ−１
と、当該ノードに与えられたノード識別番号３ａ−２
と、ノード３ａ−３と、が組として格納されている。な
お、同図中では各ノード間のリンクをわかりやすくする
ために各ノード間に破線を繋げて記載している。

【００３０】また、リンク情報４ａには、構造データ識
別子４ａ−１と、ノード識別番号４ａ−２と、子孫識別
番号４ａ−３とが組として保持されており、例えば、ノ
ード「ｄ」のノード識別番号は「４」、子孫識別番号は
「８」であることを表している。なお、同図中のリンク
情報では、各組と対応するノードとをわかりやすくする
ためにアルファベットを用いているが、実際には当該ア
ルファベットはリンク情報内に存在していない。

【００３１】次に、この管理装置が木構造データを更新
する場合の動作を説明する。更新には、１つの木構造デ
ータ全体を更新する場合と、木構造データの一部を構成
している或る部分木構造データを更新する場合とがあ
り、以下それぞれの場合について説明する。

【００３２】１つの木構造データ全体を更新する場合に
は次のように行われる。構造データ入力手段１によっ
て、新たな木構造データが入力されると、当該木構造デ
ータを構造データ格納／削除手段２に渡す。一方、識別
子入力手段５が更新される元の木構造データのルートと
なるノードの構造データ識別子を入力し、当該構造デー
タ識別子を構造データ格納／削除手段２に渡し、削除処
理を行わせる。

【００３３】すなわち、構造データ格納／削除手段２は
構造データ識別子管理手段７から、受け取った構造デー
タ識別子の与えられた木構造データの子孫となる木構造
データの構造データ識別子の集合を受け取り、受け取っ
た集合に含まれている構造データ識別子を持っているノ
ード情報及びリンク情報をノード情報蓄積手段３及びリ
ンク情報蓄積手段４から削除する。次いで、構造データ
識別子管理手段７が、前記集合に属する構造データ識別
子に関するデータを削除する。なお、木構造データを削
除のみする場合の削除処理も上記同様に行われる。

【００３４】上記削除処理を行った後に、ノード識別番
号設定手段６がルートとなるノードから階層の下位方向
を優先した順番でノード識別番号を各ノードに割り当
て、各ノードに自己のノード識別番号を設定し、リンク
情報に当該ノード識別番号と当該ノードの子孫識別番号
とを設定する。次いで、構造データ格納／削除手段２が
構造データ識別子とノード識別番号とノードとを組にし
てノード情報蓄積手段３に格納するとともに、構造デー
タ識別子とノード識別番号と子孫識別番号とをリンク情
報蓄積手段４に格納する。

【００３５】木構造データの部分木構造データを更新す
る場合は次のように行われる。構造データ入力手段１に
よって、更新する新たな部分木構造データが入力される
と、当該部分木構造データを構造データ格納／削除手段
２に渡す。一方、識別子入力手段５が更新される元の部
分木構造データのルートとなるノードの構造データ識別
子を入力し、当該構造データ識別子を構造データ格納／
削除手段２に渡し、ノード情報蓄積手段３及びリンク情
報蓄積手段４に格納されている元の部分木構造データに
相当するノード情報とリンク情報を削除する。

【００３６】削除した後に、構造データ識別子管理手段
７が新たな部分木構造データに与える構造データ識別子
を生成するとともに、当該生成した構造データ識別子と
元の部分木構造データのルートとなるノードの構造デー
タ識別子及びノード識別番号とを関連付けて管理する。

【００３７】そして、ノード識別番号設定手段６が新た
な部分木構造データのルートとなるノードから階層の下
位方向を優先した順番でノード識別番号を各ノードに割
り当て、各ノードに自己のノード識別番号を設定し、リ
ンク情報に当該ノード識別番号と当該ノードの子孫識別
番号を設定する。次いで、構造データ格納／削除手段２
が構造データ識別子とノード識別番号とノードとを組に
してノード情報蓄積手段３に格納するとともに、構造デ
ータ識別子とノード識別番号と子孫識別番号とをリンク
情報蓄積手段４に格納する。

【００３８】例えば、図６に示した木構造データのノー
ド「ｆ」以下の階層をノード「Ｆ」「Ｇ」「Ｈ」「Ｉ」
に更新した結果を図３を参照して説明する。この更新に
よって、ノード「ｆ」「ｇ」「ｈ」のノード情報及びリ
ンク情報が削除され、新たにノード「Ｆ」「Ｇ」「Ｈ」
「Ｉ」の４つのノード情報及びリンク情報が追加されて
いる。

【００３９】また、この更新によって、構造データ識別
子管理手段７には、図４に示す管理データが管理され、
この管理データによってノード「ａ」をルートとする木
構造データに割り当てられた構造データ識別子「Ｘ」
と、ノード「Ｆ」をルートとする構造データに割り当て
られた構造データ識別子「Ｙ」と、ノード「ｆ」に与え
られていたノード識別番号「６」と、が関連付けられて
いる。

【００４０】ここで、上記したような更新処理によって
更新した新たな部分木構造データを含む木構造データを
削除する場合の削除処理を以下に説明する。削除する木
構造データのルートノードを指定する構造データ識別子
とノード識別番号とを識別子入力手段６が入力し、構造
データ格納／削除手段２に渡す。

【００４１】構造データ格納／削除手段２は、削除する
木構造データのルートノードが有する子孫識別番号をリ
ンク情報蓄積手段３から取り出し、前記ノード識別番号
と子孫識別番号の間にあるノード識別番号を与えられた
ノードは、削除する木構造データを構成するノードであ
るので、ノード蓄積手段３から削除するとともに、当該
ノードに関するリンク情報をリンク蓄積手段４から削除
する。

【００４２】次いで、構造データ格納／削除手段２は、
前記削除した複数のノード情報と同一の構造データ識別
子と、削除する木構造データのルートのノード識別番号
と子孫識別番号との間にある番号と、をキーとして、構
造データ識別子管理手段７から該当する構造データ識別
子を検出し、構造データ識別子が検出された場合には、
当該構造データ識別子を有するノードは、削除する木構
造データを構成するノードであるので、当該構造データ
識別子が与えられたノード情報、リンク情報をすべて削
除する。

【００４３】例えば、図７に示すノード「ｄ」を削除す
る場合には、まず、ノード「ｄ」の子孫識別番号「８」
を得る。次に当該ノード「ｄ］のノード識別番号「４」
から「８」を削除対象のノードとする。該当するノード
［ｄ］［ｅ］のノード情報とリンク情報を削除する。次
いで、ノード「ｄ」に与えられた構造データ識別子
「Ｘ」と各ノード識別番号「５」「６」「７」「８」と
をキーとして図４に示す管理データから該当する構造デ
ータ識別子を検出する。検出の結果、構造データ識別子
「Ｙ」が得られ、この得られた構造データ識別子が与え
られたノード情報及びリンク情報のすべて削除して終了
する。したがって、構造データ識別子「Ｙ」が与えられ
たノード「Ｆ」をルートノードとする部分木構造データ
に対しても適切な削除ができる。

【００４４】上記管理装置によって管理されている木構
造データに対して検索処理を行う場合には、例えば、図
５に示す検索装置によって行われる。この検索装置は、
検索式を入力する検索入力手段８と、入力された検索式
をノード検索部分とノード間の接続関係を評価する部分
に分ける検索式評価手段９と、ノードを格納するノード
情報蓄積手段３と、リンク情報を格納するリンク情報格
納手段４と、ノード情報のノード識別番号を利用して祖
孫関係を判定する接続関係評価手段１０と、木構造デー
タの構造データ識別子を管理する構造データ識別子管理
手段７と、を備えている。

【００４５】この検索装置による検索処理の中で、ノー
ド間の祖孫関係を評価する場合を例にとって以下に動作
を説明する。検索式入力手段８がユーザ或いはアプリケ
ーション等の指示によって検索式を入力して、検索式評
価手段９に渡す。検索式を受け取った検索式評価手段９
は、検索式をノードに対する検索部分とノード間の接続
関係の評価部分とに分け、ノード蓄積手段３を利用して
検索式に含まれたノードを検索する。次いで、検索式評
価手段９は評価対象となる２つのノード（祖先候補と子
孫候補）を接続関係評価手段１０に渡す。

【００４６】評価対象のノードを受け取った接続関係評
価手段１０は、２つのノードの構造データ識別子が同一
であるか否かによって以下に示すいずれかの評価動作を
行う。評価対象の２つのノードの構造データ識別子が同
一である場合には、２つのノード情報は同時に格納され
たものであるため、ノード識別番号のみで容易且つ迅速
に祖孫関係の評価ができる。

【００４７】すなわち、祖先候補となるノードが持つ構
造データ識別子とノード識別番号を利用して、リンク情
報から子孫識別番号を取得し、祖先候補のノード識別番
号と子孫識別番号との間に子孫候補のノードのノード識
別番号が含まれる否かを検出する。検出の結果、子孫候
補のノードのノード識別番号が含まれている場合には、
評価対象の２つのノードは祖孫関係を有することがわか
る一方、含まれていない場合には、評価対象の２つのノ
ードは祖孫関係を有していないことがわかる。

【００４８】例えば、構造データ識別子が同一である図
６に示すノード「ｄ」とノード「ｇ」との祖孫関係を判
定する場合には、まず、ノード「ｄ」のノード識別番号
「４」をキーにして子孫識別番号「８」をリンク情報蓄
積手段４より取得する。なお、ノード「ｇ」のノード識
別番号は「７」である。次いで、接続関係評価手段１０
では、（ノード「ｄ」のノード識別番号「４」）＜（ノ
ード「ｇ」のノード識別番号「７」）＜＝（ノード
「ｄ」の子孫識別番号「８」）の評価が成立することが
検出され、ノード「ｄ」はノード「ｇ」の祖先であるこ
とが分かる。

【００４９】評価対象の２つのノードの構造データ識別
子が異なる場合には、以下の評価処理が行われる。ま
ず、構造データ識別子管理手段７に祖先候補のノードの
構造データ識別子と、子孫候補のノードの構造データ識
別子とをキーとして渡し、該当するノード識別番号を取
得する。

【００５０】構造データ識別子管理手段７からノード識
別番号が取得できない場合には、２つのノードは祖孫関
係を有しないことが評価できる。したがって、全く関係
のない木構造データのノード同士の祖孫関係を評価する
場合にも問題なく且つ、迅速に評価することができる。
一方、ノード識別番号を得られた場合は、当該ノード識
別番号を祖先候補に対する子孫候補のノード識別番号と
みなして、祖先候補のノード識別番号と子孫識別番号と
の比較処理を行う。この比較処理は上記した構造データ
識別子が同一の場合と同じ処理となっている。これによ
って、評価対象の２つのノードの祖孫関係を評価するこ
とができる。

【００５１】例えば、構造データ識別子が異なった図７
に示すノード「ｄ」とノード「Ｇ］との祖孫関係を評価
する場合には、まず、図４に示す管理情報から、ノード
「ｄ」の構造データ識別子「Ｘ」とノード「Ｇ］の構造
データ識別子「Ｙ」とをキーとして、ノード「ｆ」のノ
ード識別番号「６」を取得し、当該ノード識別番号をノ
ード「Ｇ」のノード「ｄ」に対するノード識別番号とす
る。次いで、ノード「ｄ」のノード識別番号「４」をキ
ーとして子孫識別番号「８」を取得する。そして、比較
処理を行うことによって、（ノード「ｄ」のノード識別
番号「４」）＜（ノード「Ｇ」のノード「ｄ」に対する
ノード識別番号「６」）＜＝（ノード「ｄ」の子孫識別
番号「８」）が成立するために、ノード「ｄ」はノード
「Ｇ」の祖先であることが分かる。

【００５２】なお、ノード「Ｇ」のノード「ｄ」に対す
るノード識別番号をノード「ｆ」に与えていたノード識
別番号とみなすことができるのは、ノード「ｄ」からみ
たノード「Ｇ」は、更新処理が行われる前のノード
「ｆ」との関係と同様に扱うことができるためで、ノー
ド「Ｆ」「Ｈ」「Ｉ」の場合もノード「Ｇ」と同様に祖
孫関係の評価ができる。

【００５３】なお、上記実施例では、構造データ識別子
管理手段７は、図４に示す管理データを管理していた
が、例えば、構造データ識別子「Ｙ」を生成する際に、
当該「Ｙ」の一部に構造データ識別子「Ｘ」を用いて、
例えば、ＹをＸ＋αといった構造データ識別子とするこ
とによって、管理データを構造データ識別子「Ｙ」すな
わち「Ｘ＋α」と、ノード「ｆ」に与えられていたノー
ド識別番号「６」と、に減らすことができる。

【００５４】次に、本発明の木構造データ管理方法の効
果を従来例の木構造データ管理方法と比較して説明す
る。なお、従来例では考慮されていない関係のない木構
造データに属するノード間の接続条件の評価処理に使用
する部分、すなわち、図２に示す構造データ識別子につ
いては比較の対象から外して比較を行っている。まず、
木構造データを管理するために使用するデータ量につい
て比較する。本発明ではノード数と同数のノード識別番
号と子孫識別番号を有するだけであり、ノード数をｎと
するとデータ量のオーダはＯ（ｎ）となっている一方、
第２従来例、第３従来例、第４従来例、第５従来例、第
６従来例の方法ではデータ量のオーダはＯ（ｎ²）、も
しくはノード数ｎの対数（Ｌｏｇ）の関数で表されたＯ
（ｎ＊Ｌｏｇｎ）となっており、多くのデータ量を必要
とする。

【００５５】次に、木構造データにおいて接続条件を評
価する処理の処理時間等といった処理コストについて、
評価候補となる２つのノードを検索した後、祖孫関係を
比較する際にかかる処理コストを例に比較する。本発明
の管理方法がされた木構造データでは、表へのアクセス
と１、２回といった比較処理だけである一方、第５従来
例では、比較処理の回数が対象ノードの深さに比例す
る。また、第１従来例、第２従来例、第３従来例の方法
ではノードへのアクセスが伴うため、より多くのコスト
がかかってしまう。

【００５６】次に、木構造データにおいて更新処理にか
かる処理コストについて比較する。本発明では、更新す
るノード以下の階層のノードに対してノード識別番号を
割り当て、当該ノードに関するリンク情報として子孫識
別番号を割り当てるだけで済む一方、第２従来例、第４
従来例、第６従来例では、すべての更新する以外のノー
ドに対しても更新処理を行わなければならず処理コスト
が高い。

【００５７】上記したように、本発明の木構造データ管
理方法を行うことによって、データ量、祖孫関係の評価
コスト、更新コストのすべての面において本発明は効果
がある。

【００５８】

【発明の効果】以上説明したように、本発明の木構造デ
ータ管理方法によると、各ノードに階層の下位方向を優
先した順番で番号を付与し、各ノードに自己の番号と自
己ノードの最後の順番の子孫ノードに付与した番号との
みを対応付けて記憶するようにしたために、当該発明に
よって管理されている木構造データにおいてノード間の
祖孫関係を迅速且つ少ないデータ量で実現することがで
きる。さらに、本発明の木構造データ管理方法によると
或る木構造データに新たに置換する木構造データ内のノ
ードといった限られた範囲のノードに対して更新処理を
行うようにしたために、更新処理を容易に行うことがで
きるとともに、新たに置換して関連付けられた木構造デ
ータ内のノードに対しても他のノードとの祖孫関係の評
価を迅速且つ容易に行うことができる。

【図面の簡単な説明】

【図１】 本発明に係る木構造データ管理方法を実施す
る一実施例の管理装置の構成図である

【図２】 本発明に係る木構造データ管理方法の木構造
データの格納状況を説明する図である。

【図３】 本発明に係る木構造データ管理方法の更新処
理を行った木構造データの格納状況を説明する第１図で
ある。

【図４】 本発明に係る木構造データ管理方法の更新処
理を行った木構造データの格納状況を説明する第２図で
ある。

【図５】 本発明に係る木構造データ管理方法によって
管理されている木構造データを検索する検索装置の構成
図である。

【図６】 第１従来例に係る木構造データ管理方法を説
明する図である。

【図７】 第２従来例に係る木構造データ管理方法を説
明する図である。

【図８】 第３従来例に係る木構造データ管理方法を説
明する図である。

【図９】 第４従来例に係る木構造データ管理方法を説
明する図である。

【図１０】 第５従来例に係る木構造データ管理方法を
説明する図である。

【図１１】 第６従来例に係る木構造データ管理方法を
説明する図である。

【符号の説明】

１・・構造データ入力手段、 ２・・構造データ格納
／削除手段、３・・ノード情報蓄積手段、 ３ａ・・
ノード情報、３ａ−１・・構造データ識別子、 ３ａ−
２・・ノード識別番号、３ａ−３・・ノード、４・・リ
ンク情報蓄積手段、 ４ａ・・リンク情報、４ａ−１
・・構造データ識別子、 ４ａ−２・・ノード識別番
号、４ａ−３・・子孫識別番号、５・・ノード識別番号
設定手段、 ６・・識別子入力手段、７・・構造データ
識別子管理手段、

Claims (2)

【特許請求の範囲】
1. 【請求項１】複数のノードをリンクさせて階層を形成し
   た木構造データを管理する木構造データ管理方法におい
   て、 各ノードに階層の下位方向を優先した順番で番号を付与
   し、 各ノードに自己の番号と自己ノードの最後の順番の子孫
   ノードに付与した番号とのみを対応付けて記憶すること
   により、各ノードに関連する子孫ノードを管理すること
   を特徴とする木構造データ管理方法。
2. 【請求項２】請求項１に記載した木構造データ管理方法
   において、 更新される対象であり識別子を有する第１の木構造デー
   タ内のノードを、 識別子を有する第２の木構造データの親ノードに置換さ
   せて、第１の木構造データを増加させる場合に、 第２の木構造データ内のノードに階層の下位方向を優先
   した順番で固有の番号を付与し、 前記第１の木構造データの識別子、第２の木構造データ
   の識別子及び前記第１の木構造データの置換されるノー
   ドの番号とを対応付けて管理することによって、 各ノードに関連する子孫ノードを管理することを特徴と
   する木構造データ管理方法。