(57)【特許請求の範囲】
【請求項１】
記憶装置に展開されたルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを検索する方法であって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードは当該ノードのパス及びノード格納値を表す実体情報が関連付けられ、
ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーが、当該頂点ノードに付与されたノード識別子によって代表され、
パス及び／又はノード格納値に関する検索条件を指定し、部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて検索範囲を指定する条件指定ステップと、
検索範囲に含まれるノード毎に、当該ノードに関連付けられた実体情報が前記検索条件と一致するかどうかを判定し、一致した場合に当該ノードに検索ヒット情報を関連付け、前記ノード間の親子関係を辿って当該ノードの祖先ノードに検索ヒット情報を関連付ける検索ステップと、
検索ヒット情報が関連付けられたノードを含む部分ツリーを代表する頂点ノードリストを検索結果として保存するステップと、
を有する方法。
【請求項２】
前記検索ステップにおいて、前記ノード間の親子関係が頂点ノードの個数に応じて、親ノードから子ノード又は子ノードから親ノードの順番に辿られる、
請求項１に記載の方法。
【請求項３】
記憶装置に展開されたルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを検索する方法であって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードは当該ノードのパス及びノード格納値を表す実体情報が関連付けられ、
ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーが、当該頂点ノードに付与されたノード識別子によって代表され、
パス及び／又はノード格納値に関する検索条件を指定し、部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて検索範囲を指定するステップと、
検索範囲に含まれる各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーと特定の関係にあるノードに関連付けられた実体情報が前記検索条件と一致するかどうかを判定し、一致したノードが存在する場合に、当該部分ツリーを代表する頂点ノードを含む頂点ノードリストを検索結果として保存するステップと、
を有する方法。
【請求項４】
前記保存するステップにおいて、当該部分ツリーと特定の関係にあるノードが当該部分ツリーに属するノードである、請求項３に記載の方法。
【請求項５】
前記保存するステップにおいて、当該部分ツリーと特定の関係にあるノードが当該部分ツリーの祖先ノード及び／又は当該部分ツリーの頂点ノードである、請求項３に記載の方法。
【請求項６】
記憶装置に展開されたルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを第１の検索条件と第２の検索条件を論理的に組み合わせて検索する方法であって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードは当該ノードのパス及びノード格納値を表す実体情報が関連付けられ、
ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーが、当該頂点ノードに付与されたノード識別子によって代表され、
部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて検索範囲を指定するステップと、
パス及び／又はノード格納値に関する前記第１の検索条件を指定するステップと、
検索範囲内で前記ノード間の親子関係を辿って当該第１の検索条件に一致するノードが属する部分ツリーを代表する頂点ノードを含む第１の頂点ノードリストを第１の検索結果として保存するステップと、
実体情報に関する前記第２の検索条件を指定するステップと、
検索範囲内で前記ノード間の親子関係を辿って当該第２の検索条件に一致するノードが属する部分ツリーを代表する頂点ノードを含む第２の頂点ノードを第２の検索結果として保存するステップと、
前記第１の検索条件と前記第２の検索条件の論理的な組み合わせに対応した論理演算を前記第１の頂点ノードリストと前記第２の頂点ノードリストに実行することにより、第１の検索条件と第２の検索条件を論理的に組み合わせた検索結果を表す頂点ノードリストを生成するステップと、
を有する方法。
【請求項７】
記憶装置に展開されたルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを集計する方法であって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードは当該ノードのノードタイプ及びノード格納値を表す実体情報が関連付けられ、
ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーが、当該頂点ノードに付与されたノード識別子によって代表され、
集計の分類対象を表す第１のノードタイプを指定し、集計の対象を表す第２のノードタイプを指定し、部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて集計の範囲を指定するステップと、
集計の範囲に含まれる各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群の中に集計の対象を表す第２のノードタイプが関連付けられたノードが存在するかどうかを判定し、存在する場合に、当該ノードに関連付けられたノード格納値を、当該部分ツリーに属するノード群に関係した集計の分類対象を表す第１のノードタイプ毎に集計するステップと、
を有する方法。
【請求項８】
記憶装置に展開されたルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータの少なくとも二つのノード群に順序を付ける方法であって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードは当該ノードのノードタイプ及びノード格納値を表す実体情報が関連付けられ、
ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーが、当該頂点ノードに付与されたノード識別子によって代表され、
集計の対象を表すノードタイプを指定し、少なくとも二つの部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて集計の範囲を指定するステップと、
集計の範囲に含まれる各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群の中に集計の対象を表すノードタイプが関連付けられたノードが存在するかどうかを判定し、存在する場合に、当該ノードに関連付けられたノード格納値を集計するステップと、
部分ツリー毎に集計されたノード格納値の順序関係に従って当該少なくとも二つの部分ツリーに順序を付けるステップと、
を有する方法。
【請求項９】
記憶装置に展開されたルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータの少なくとも二つのノード群に順序を付ける方法であって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードは当該ノードのノードタイプ及びノード格納値を表す実体情報が関連付けられ、
ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーが、当該頂点ノードに付与されたノード識別子によって代表され、
少なくとも二つの部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて順序付けの対象を指定し、順序付けの指標となるノードタイプを指定するステップと、
順序付けの対象に含まれる各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群の中で、順序付けの指標となるノードタイプが関連付けられたノードに関連付けられたノード格納値を取得するステップと、
部分ツリー毎に取得されたノード格納値の順序関係に従って当該少なくとも二つの部分ツリーに順序を付けるステップと、
を有する方法。
【請求項１０】
ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有し、記憶装置に記憶されたデータを検索する情報処理装置であって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付け、これにより、ツリー型データ構造を構成するノード間の親子関係を表現し、各ノードに当該ノードのパス及びノード格納値を表す実体情報を関連付け、ツリー型データ構造を記憶装置上に構築するデータ展開手段と、
パス及び／又はノード格納値に関する検索条件を指定し、ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーを当該頂点ノードに付与された識別子によって代表させることにより、部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて検索範囲を指定する条件指定手段と、
検索範囲に含まれるノード毎に、当該ノードに関連付けられた実体情報が前記検索条件と一致するかどうかを判定し、一致した場合に当該ノードに検索ヒット情報を関連付け、前記ノード間の親子関係を辿って当該ノードの祖先ノードに検索ヒット情報を関連付ける検索手段と、
検索ヒット情報が関連付けられたノードを含む部分ツリーを代表する頂点ノードリストを検索結果として保存する手段と、
を有する情報処理装置。
【請求項１１】
前記検索手段が、頂点ノードの個数に応じて、親ノードから子ノード又は子ノードから親ノードの順番に前記ノード間の親子関係を辿る、
請求項１０に記載の情報処理装置。
【請求項１２】
ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有し、記憶装置に記憶されたデータを検索する情報処理装置であって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付け、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、各ノードに当該ノードのパス及びノード格納値を表す実体情報を関連付け、ツリー型データ構造を記憶装置上に構築するデータ展開手段と、
パス及び／又はノード格納値に関する検索条件を指定し、ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーを当該頂点ノードに付与された識別子によって代表させることにより、部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて検索範囲を指定する条件指定手段と、
検索範囲に含まれる各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーと特定の関係にあるノードに関連付けられた実体情報が前記検索条件と一致するかどうかを判定し、一致したノードが存在する場合に、当該部分ツリーを代表する頂点ノードを含む頂点ノードリストを検索結果として保存する検索手段と、
を有する情報処理装置。
【請求項１３】
前記検索手段において、当該部分ツリーと特定の関係にあるノードが当該部分ツリーに属するノードである、請求項１２に記載の情報処理装置。
【請求項１４】
前記検索手段において、当該部分ツリーと特定の関係にあるノードが当該部分ツリーの祖先ノード及び／又は当該部分ツリーの頂点ノードである、請求項１２に記載の情報処理装置。
【請求項１５】
ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有し、第１の検索条件と第２の検索条件を論理的に組み合わせて検索する情報処理装置であって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付け、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、各ノードに当該ノードのパス及びノード格納値を表す実体情報を関連付け、ツリー型データ構造を記憶装置上に構築するデータ展開手段と、
パス及び／又はノード格納値に関する前記第１の検索条件及び前記第２の検索条件を指定し、ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーを当該頂点ノードに付与された識別子によって代表させることにより、部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて検索範囲を指定する条件指定手段と、
前記第１の検索条件に従って、前記検索範囲内で前記ノード間の親子関係を辿って当該第１の検索条件に一致するノードが属する部分ツリーを代表する頂点ノードを含む第１の頂点ノードリストを第１の検索結果として保存し、前記第２の検索条件に従って、前記検索範囲内で前記ノード間の親子関係を辿って当該第２の検索条件に一致するノードが属する部分ツリーを代表する頂点ノードを含む第２の頂点のノードリストを第２の検索結果として保存する検索手段と、
前記第１の検索条件と前記第２の検索条件の論理的な組み合わせに対応した論理演算を前記第１の頂点ノードリストと前記第２の頂点ノードリストに実行することにより、第１の検索条件と第２の検索条件を論理的に組み合わせた検索結果を生成する組み合わせ手段と、
を有する情報処理装置。
【請求項１６】
ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有し、記憶装置に記憶されたデータを集計する情報処理装置であって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付け、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、各ノードに当該ノードのノードタイプ及びノード格納値を表す実体情報を関連付け、ツリー型データ構造を記憶装置上に展開するデータ展開手段と、
集計の分類対象を表す第１のノードタイプを指定し、集計の対象を表す第２のノードタイプを指定し、ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーを当該頂点ノードに付与された識別子によって代表させることにより、部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて集計の範囲を指定する条件指定手段と、
集計の範囲に含まれる各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群の中に集計の対象を表す第２のノードタイプが関連付けられたノードが存在するかどうかを判定し、存在する場合に、当該ノードに関連付けられたノード格納値を、当該部分ツリーに属するノード群に関係した集計の分類対象を表す第１のノードタイプ毎に集計する集計手段と、
を有する情報処理装置。
【請求項１７】
ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有し、記憶装置に記憶されたデータの少なくとも二つのノード群に順序を付ける情報処理装置であって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付け、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、各ノードに当該ノードのノードタイプ及びノード格納値を表す実体情報を関連付け、ツリー型データ構造を記憶装置上に展開するデータ展開手段と、
集計の対象を表すノードタイプを指定し、ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーを当該頂点ノードに付与された識別子によって代表させることにより、少なくとも二つの部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて集計の範囲を指定する条件指定手段と、
集計の範囲に含まれる各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群の中に集計の対象を表すノードタイプが関連付けられたノードが存在するかどうかを判定し、存在する場合に、当該ノードに関連付けられたノード格納値を集計する集計手段と、
部分ツリー毎に集計されたノード格納値の順序関係に従って当該少なくとも二つの部分ツリーに順序を付ける順序付け手段と、
を有する情報処理装置。
【請求項１８】
ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有し、記憶装置に記憶されたデータの少なくとも二つのノード群に順序を付ける情報処理装置であって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付け、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、各ノードに当該ノードのノードタイプ及びノード格納値を表す実体情報を関連付け、ツリー型データ構造のデータを記憶装置上に展開するデータ展開手段と、
ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーを当該頂点ノードに付与された識別子によって代表させることにより、少なくとも二つの部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて順序付けの対象を指定し、順序付けの指標となるノードタイプを指定する条件指定手段と、
順序付けの対象に含まれる各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群の中で、順序付けの指標となるノードタイプが関連付けられたノードに関連付けられたノード格納値を取得する指標取得手段と、
部分ツリー毎に取得されたノード格納値の順序関係に従って当該少なくとも二つの部分ツリーに順序を付ける順序付け手段と、
を有する情報処理装置。
【請求項１９】
ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有するコンピュータに、記憶装置に記憶されたデータを検索する検索機能を実現させるためのプログラムであって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードに当該ノードのパス及びノード格納値を表す実体情報が関連付けられ、
ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーが、当該頂点ノードに付与されたノード識別子によって代表され、
前記検索機能は、
パス及び／又はノード格納値に関する検索条件を指定し、部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて検索範囲を指定する機能と、
検索範囲に含まれるノード毎に、当該ノードに関連付けられた実体情報が前記検索条件と一致するかどうかを判定し、一致した場合に当該ノードに検索ヒット情報を関連付け、前記ノード間の親子関係を辿って当該ノードの祖先ノードに検索ヒット情報を関連付ける機能と、
検索ヒット情報が関連付けられたノードを含む部分ツリーを代表する頂点ノードリストを検索結果として保存する機能と、を含む、プログラム。
【請求項２０】
前記検索ヒット情報を関連付ける機能において、前記ノード間の親子関係が頂点ノードの個数に応じて、親ノードから子ノード又は子ノードから親ノードの順番に辿られる、請求項１９に記載のプログラム。
【請求項２１】
ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有するコンピュータに、記憶装置に記憶されたデータを検索する検索機能を実現させるためのプログラムであって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードに当該ノードのパス及びノード格納値を表す実体情報が関連付けられ、
前記検索機能は、
パス及び／又はノード格納値に関する検索条件を指定し、ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーを当該頂点ノードに付与された識別子によって代表させることにより、部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて検索範囲を指定する機能と、
検索範囲に含まれる各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーと特定の関係にあるノードに関連付けられた実体情報が前記検索条件と一致するかどうかを判定し、一致したノードが存在する場合に、当該部分ツリーを代表する頂点ノードを含む頂点ノードリストを検索結果として保存する機能と、
を含む、プログラム。
【請求項２２】
前記検索結果として保存する機能において、当該部分ツリーと特定の関係にあるノードが当該部分ツリーに属するノードである、請求項２１に記載のプログラム。
【請求項２３】
前記検索結果として保存する機能において、当該部分ツリーと特定の関係にあるノードが当該部分ツリーの祖先ノード及び／又は当該部分ツリーの頂点ノードである、請求項２１に記載のプログラム。
【請求項２４】
ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有するコンピュータに、第１の検索条件と第２の検索条件を論理的に組み合わせて検索する検索機能を実現させるためのプログラムであって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードに当該ノードのパス及びノード格納値を表す実体情報が関連付けられ、
前記検索機能は、
パス及び／又はノード格納値に関する前記第１の検索条件及び前記第２の検索条件を指定し、ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーを当該頂点ノードに付与された識別子によって代表させることにより、部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて検索範囲を指定する機能と、
前記第１の検索条件に従って、前記検索範囲内で前記ノード間の親子関係を辿って当該第１の検索条件に一致するノードが属する部分ツリーを代表する頂点ノードを含む第１の頂点ノードリストを第１の検索結果として保存し、前記第２の検索条件に従って、前記検索範囲内で前記ノード間の親子関係を辿って当該第１の検索条件に一致するノードが属する部分ツリーを代表する頂点ノードを含む第２の頂点ノードリストを第２の検索結果として保存する機能と、
前記第１の検索条件と前記第２の検索条件の論理的な組み合わせに対応した論理演算を前記第１の頂点ノードリストと前記第２の頂点ノードリストに実行することにより、第１の検索条件と第２の検索条件を論理的に組み合わせた検索結果を生成する機能と、
を含む、プログラム。
【請求項２５】
ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有するコンピュータに、記憶装置に記憶されたデータを集計する集計機能を実現させるためのプログラムであって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードに当該ノードのノードタイプ及びノード格納値を表す実体情報が関連付けられ、
前記集計機能は、
集計の分類対象を表す第１のノードタイプを指定し、集計の対象を表す第２のノードタイプを指定し、ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーを当該頂点ノードに付与された識別子によって代表させることにより、部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて集計の範囲を指定する機能と、
集計の範囲に含まれる各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群の中に集計の対象を表す第２のノードタイプが関連付けられたノードが存在するかどうかを判定し、存在する場合に、当該ノードに関連付けられたノード格納値を、当該部分ツリーに属するノード群に関係した集計の分類対象を表す第１のノードタイプ毎に集計する機能と、
を含む、プログラム。
【請求項２６】
ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有するコンピュータに、記憶装置に記憶されたデータの少なくとも二つのノード群に順序を付ける順序付け機能を実現させるためのプログラムであって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードに当該ノードのノードタイプ及びノード格納値を表す実体情報が関連付けられ、
前記順序付け機能は、
集計の対象を表すノードタイプを指定し、ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーを当該頂点ノードに付与された識別子によって代表させることにより、少なくとも二つの部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて集計の範囲を指定する機能と、
集計の範囲に含まれる各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群の中に集計の対象を表すノードタイプが関連付けられたノードが存在するかどうかを判定し、存在する場合に、当該ノードに関連付けられたノード格納値を集計する機能と、
部分ツリー毎に集計されたノード格納値の順序関係に従って当該少なくとも二つの部分ツリーに順序を付ける機能と、
を含む、プログラム。
【請求項２７】
ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有するコンピュータに、記憶装置に記憶されたデータの少なくとも二つのノード群に順序を付ける順序付け機能を実現させるためのプログラムであって、
ルート・ノードを含む全ノードに、０又は１から始まる整数連番である固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードに当該ノードのノードタイプ及びノード格納値を表す実体情報が関連付けられ、
前記順序付け機能は、
ツリー型データ構造の特定のノードである頂点ノードと当該頂点ノードの子孫ノードとを含むノード群である部分ツリーを当該頂点ノードに付与された識別子によって代表させることにより、少なくとも二つの部分ツリーを代表する頂点ノードのノード識別子からなる配列である頂点ノードリストを用いて順序付けの対象を指定し、順序付けの指標となるノードタイプを指定する機能と、
順序付けの対象に含まれる各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群の中で、順序付けの指標となるノードタイプが関連付けられたノードに関連付けられたノード格納値を取得する機能と、
部分ツリー毎に取得されたノード格納値の順序関係に従って当該少なくとも二つの部分ツリーに順序を付ける機能と、
を含む、プログラム。
【請求項２８】
請求項１９乃至２７のうちいずれか１項に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はツリー型データ構造を取り扱う方法、特に、ツリー型データ構造のデータを検索・集計・ソートする方法に関する。また、本発明は、このような方法を実施する情報処理装置に関する。更に、本発明は、このような方法を実行するためのプログラム、及び、このプログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
データベースは種々の用途に用いられているが、中規模ないし大規模システムにおいては、論理的な矛盾が排除できるリレーショナルデータベース（ＲＤＢ）の使用が主流となっている。たとえば、ＲＤＢは飛行機の座席予約等のシステムに利用されている。この場合、キー項目を指定することにより、（多くの場合１件の）ターゲットを迅速に検索することもでき、或いは、予約の確定、キャンセル或いは変更などを行うことができる。また、各便の座席数はせいぜい数百であるため、特定の航空便の空席数を求めることも可能である。【０００３】
このようなＲＤＢは、表形式データの取り扱いに適しているが、ツリー形式データの取り扱いには適していないことが知られている（例えば、非特許文献１を参照。）。【０００４】
更に、アプリケーションの中には、表形式による表現よりもツリー形式による表現の方が適しているものが存在する。特に、近年、イントラネットやインターネットのアプリケーションのデータ標準として、ツリー型データ構造を採用するＸＭＬが普及している（ＸＭＬの詳細については、例えば、非特許文献２を参照。）。【０００５】
しかし、ツリー型データ構造の取り扱い、例えば、ツリー形式データの検索は、一般に、大変効率が悪い。この効率の悪さの第１の理由は、データが各所のノードに分散して存在するため、データの存在すべき場所を直ちに特定することが困難である点にある。ＲＤＢでは、例えば、「年齢」というデータは、あるテーブルの「年齢」という項目だけに格納されている。しかし、ツリー型データ構造では、「年齢」というデータを保持するノードが各所に散在しているので、一般的には、ツリー型データ構造の全体を調べなければ、該当するデータを検索することができない。【０００６】
効率の悪さの第２の理由は、検索の結果を表現するために時間がかかるという点にある。検索にヒットしたノード群を表現しようとすると、屡々、そのノードの子孫にあたるノードも表現しなければならないが、ＲＤＢＭＳとは異なりデータ構造が非定型であるため、子孫ノードを表現するために時間がかかる。【０００７】
そこで、データベースの主流であるＲＤＢの利点をいかすため、従来、ツリー型データ構造をデータベース化するとき、ツリー形式データをＲＤＢ化する方法（例えば、特許文献１を参照。）が提案されている。ＲＤＢでは、データはテーブル（表）に分解して保持される。そのため、実際のツリー形式データをＲＤＢ化するには、ツリー形式データをテーブルに押し込める必要がある。しかし、様々のツリー型データ構造を取り扱うためには、その構造毎に個別にデータをテーブルに押し込め、システム設計を行わなければならない。したがって、ＲＤＢに基づくシステム構築は非常に手間のかかる作業である。【０００８】
これに対して、ツリー形式データ、特に、ＸＭＬデータをそのままの形でデータベース化する方法も提案されている。ツリー型データ構造の場合、一つのノードに子孫ノードをぶら下げることができ、多様な表現が可能であるため、システム設計の手間を大幅に削減することができる。したがって、ＸＭＬのようなツリー構造を取り扱える技術を核として、ツリー形式データを処理することへのニーズが高まっている。【０００９】
ＸＭＬデータをそのままの形でデータベース化する方法の一例のアプローチは、ツリー構造に記入されているデータのコピーを取り出し、例えば、「年齢」という項目であれば、「年齢」の検索用インデックスデータを別途保持する（例えば、特許文献２を参照。）。これにより、データ自身に属性を付加できるというＸＭＬデータのメリットを十分に活用すると共に、タグを用いて表現された各項目の関係構造をそのまま記憶できるようにしている。【００１０】
また、ＸＭＬ文書をツリー構造でメモリ上に展開するためのＤＯＭと呼ばれるオブジェクトモデルのインタフェースが公開されている（例えば、非特許文献３を参照。）。
【特許文献１】特開２００３−２４８６１５号公報
【特許文献２】特開２００１−１９５４０６号公報
【非特許文献１】株式会社セック、"Karearea White Paper"、[online]、［平成１６年２月１９日検索］、インターネット＜URL:http://www.sec.co.jp/products/karearea/＞
【非特許文献２】W3C、"Extensible Markup Language (XML) 1.0 (ThirdEdition)"、[online]、２００４年２月４日、［平成１６年２月１９日検索］、インターネット＜URL:http://www.w3.org/TR/2004/REC-xml-20040204/＞
【非特許文献３】Ｒ．  アラン  ワイク、ブラッド  ルーペン、サルタン  ルーマン、「プログラミングＸＭＬ」、日経ＤＰソフトプレス、２００２年、ｐ．５９−８４
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかし、上記の検索用インデックスデータを別途保持するようなアプローチでは、少なくともデータは二重に保持され、かつ、インデックスを作成するコスト及びインデックスを格納するためのデータ領域が必要となり、大規模なデータを保持する上で不利である。【００１２】
このようなメカニズムによって、実際に検索を行い、ノードを特定したとしても、そのノードを表現するためには時間がかかる。また、このメカニズムは、ノード間の関係を問題とする検索（例えば、祖先に「６０歳」という「年齢」を含み、子孫に「１歳」という「年齢」を含むツリーの抽出）には利用できない。【００１３】
このような従来技術の根本的な問題点は、個々のデータのみに着目し、データを蓄えたノード間をポインタで接続することによりツリー型データ構造が表現されているため、データ間の関係、例えば、親子、祖先、子孫、兄弟（シブリング）、世代などの関係を効率的にトレースすることができないことにある。換言すると、ポインタは、その値が一定しないため、データの格納アドレスを示すという用途にしか使用できず、ノード間の関係を直接的に表現することができない。その結果として、従来技術では、ツリー型データ構造のデータを検索、集計、ソートすることが困難であった。また、上記のＤＯＭは、ツリー型データ構造のトポロジーを編集する操作のインタフェースを規定するだけであり、操作の具体的手法を規定するものではない。【００１４】
そこで、本発明は、効率的にツリー型データ構造のデータを検索、集計、ソートすることができる方法、情報処理装置、プログラム、および、プログラムを記録した記録媒体の提供を目的とする。
【課題を解決するための手段】
【００１５】
上記目的を達成するため、本発明は、ツリー型データ構造を構成するノード間の親子関係を、親ノードに子ノードを対応付ける「親→子」関係ではなく、子ノードに親ノードを対応付ける「子→親」関係によって表現するという親子関係表現に基づいて、ツリー型データ構造のデータを検索、集計、ソートする。【００１６】
したがって、本発明によれば、記憶装置に展開されたルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを検索する方法は、請求項１に記載されるように、
ルート・ノードを含む全ノードに固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードはデータを表す少なくとも一つの実体情報が関連付けられ、
実体情報に関する検索条件を指定する条件指定ステップと、
各ノードについて、当該ノードに関連付けられた実体情報が前記検索条件と一致するかどうかを判定し、一致した場合に当該ノードに検索ヒット情報を関連付け、前記ノード間の親子関係を辿って当該ノードの祖先ノードに検索ヒット情報を関連付ける検索ステップと、
を有する。これにより、実体情報を指定して、全ツリーを検査し、条件に合致するノードを検出することができる。【００１７】
従来から知られている「親→子」関係によって親子関係を表現する場合、一つの親ノードに複数の子ノードが対応する場合があるので、親ノードと子ノードの二つの要素を特定しなければ親子関係を定義できない。即ち、親ノードを特定しても、その親ノードと親子関係にある子ノードを特定することができない。これに対して、本発明のように「子→親」関係によって親子関係を表現する場合、一つの子ノードには必ず唯一の親ノードが対応するので、子ノードを特定することによって、この子ノードに対応する唯一の親ノードを直ちに特定することができる。これにより、ツリー型データ構造のデータを高速に検索できるようになる。【００１８】
特に、ノード識別子を整数により定義すると、親子関係を定義する際に、子ノードの識別子を収容する配列が不要になるので（すなわち、ツリー型データ構造のトポロジーは一つの配列で記述できるので）、メモリ使用量が削減され、処理速度が高速化する。好ましくは、ノード識別子は整数連番にされる。【００１９】
また、本発明は、請求項２に記載されるように、
部分ツリーはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、
条件指定ステップは、検索範囲を表す少なくとも一つの部分ツリーを指定するステップを含み、
検索ステップの後に、検索ヒット情報が関連付けられたノードを含む部分ツリーを表す識別子を検索結果として保存するステップをさらに有する。これにより、検索結果が部分ツリーを表す識別子のリストとして得られる。【００２０】
このように、特定のノードとその特定のノードの子孫ノードは部分ツリーという形でまとめて取り扱うと、この部分ツリーを用いて検索の範囲を指定したり、検索の結果を表したりすることができるので、非常に便利である。【００２１】
また、本発明によれば、記憶装置に展開されたルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを検索する方法は、請求項３に記載されるように、
ルート・ノードを含む全ノードに固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードはデータを表す少なくとも一つの実体情報が関連付けられ、
部分ツリーはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、
少なくとも一つの実体情報に関する検索条件を指定し、検索範囲を表す少なくとも一つの部分ツリーを指定するステップと、
各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群に関連付けられた少なくとも一つの実体情報が前記検索条件と一致するかどうかを判定し、一致したノードに検索ヒット情報を関連付けるステップと、
を有する。これにより、指定された部分ツリーを検査し、ヒットしたノードを検索結果として得ることができる。【００２２】
また、本発明によれば、記憶装置に展開されたルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを検索する方法は、請求項４に記載されるように、
ルート・ノードを含む全ノードに固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードはデータを表す少なくとも一つの実体情報が関連付けられ、
部分ツリーはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、
少なくとも一つの実体情報に関する検索条件を指定し、検索範囲を表す少なくとも一つの部分ツリーを指定するステップと、
各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノードに関連付けられた少なくとも一つの実体情報が前記検索条件と一致するかどうかを判定し、一致したノードが存在する場合に、当該部分ツリーを表す識別子を検索結果として保存するステップと、
を有する。これにより、実体情報を検索条件として指定し、部分ツリーを検査し、部分ツリーの識別子を検索結果として得ることができる。【００２３】
また、本発明によれば、記憶装置に展開されたルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを検索する方法は、請求項５に記載されるように、
ルート・ノードを含む全ノードに固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードはデータを表す少なくとも一つの実体情報が関連付けられ、
部分ツリーはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、
少なくとも一つの実体情報に関する検索条件を指定し、検索範囲を表す少なくとも一つの部分ツリーを指定するステップと、
各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーの祖先ノードを特定し、当該部分ツリーの特定のノード及び／又は祖先ノードに関連付けられた少なくとも一つの実体情報が前記検索条件と一致するかどうかを判定し、一致したノードに検索ヒット情報を関連付けるステップと、
を有する。これにより、実体情報を検索条件として指定し、祖先ノードを検査して、検索条件に合致したノードを検索結果として得ることができる。【００２４】
また、本発明によれば、記憶装置に展開されたルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを検索する方法は、請求項６に記載されるように、
ルート・ノードを含む全ノードに固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードはデータを表す少なくとも一つの実体情報が関連付けられ、
部分ツリーはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、
少なくとも一つの実体情報に関する検索条件を指定し、検索範囲を表す少なくとも一つの部分ツリーを指定するステップと、
各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーの祖先ノードを特定し、当該部分ツリーの特定のノード及び／又は祖先ノードに関連付けられた少なくとも一つの実体情報が前記検索条件と一致するかどうかを判定し、一致したノードが存在する場合に、当該部分ツリーを表す識別子を検索結果として保存するステップと、
を有する。これにより、検索条件として実体情報を指定し、祖先ノードを検査し、検索にヒットした祖先ノードを有する部分ツリーの識別子を検索結果として得ることができる。【００２５】
また、本発明によれば、記憶装置に展開されたルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを第１の検索条件と第２の検索条件を論理的に組み合わせて検索する方法は、請求項７に記載されるように、
ルート・ノードを含む全ノードに固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードはデータを表す少なくとも一つの実体情報が関連付けられ、
部分ツリーはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、
検索範囲を表す少なくとも一つの部分ツリーが指定され、
少なくとも一つの実体情報を指定する第１の検索条件に従って、前記ノード間の親子関係を辿って当該第１の検索条件に一致するノードが属する部分ツリーを表す識別子を第１の検索結果として保存するステップと、
少なくとも一つの実体情報を指定する第２の検索条件に従って、前記ノード間の親子関係を辿って当該第１の検索条件に一致するノードが属する部分ツリーを表す識別子を第２の検索結果として保存するステップと、
第１の検索条件と第２の検索条件の論理的な関係に対応した論理演算を第１の検索結果と第２の検索結果に実行することにより、第１の検索条件と第２の検索条件を論理的に組み合わせた検索結果を生成するステップと、
を有する。これにより、検索条件を組み合わせた検索が、個別の検索条件による検索と、個別の検索の検索結果の論理演算として実現される。【００２６】
また、本発明によれば、記憶装置に展開されたルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを集計する方法は、請求項８に記載されるように、
ルート・ノードを含む全ノードに固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードはデータを表す少なくとも一つの実体情報が関連付けられ、
部分ツリーはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、
集計の対象を表す実体情報を指定し、集計の範囲を表す少なくとも一つの部分ツリーを指定するステップと、
各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群の中に集計の対象を表す実体情報が関連付けられたノードが存在するかどうかを判定し、存在する場合に、当該ノードに関連付けられた実体情報を集計するステップと、
を有する。この方法は、各部分ツリーを明示的に指定することにより、次元を指定しない集計、すなわち、部分ツリー内の測度の集計を実現する。【００２７】
また、本発明によれば、記憶装置に展開されたルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを集計する方法は、請求項９に記載されるように、
ルート・ノードを含む全ノードに固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードはデータを表す少なくとも一つの実体情報が関連付けられ、
部分ツリーはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、
集計の分類対象を表す実体情報を指定し、集計の対象を表す実体情報を指定し、集計の範囲を表す少なくとも一つの部分ツリーを指定するステップと、
各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群の中に集計の対象を表す実体情報が関連付けられたノードが存在するかどうかを判定し、存在する場合に、当該ノードに関連付けられた実体情報を、当該部分ツリーに属するノード群に関係した集計の分類対象を表す実体情報毎に集計するステップと、
を有する。この方法は、集計の対象＝測度、集計の範囲＝カテゴリ、及び、集計の分類対象＝次元を指定して、部分ツリー内の測度を集計することができる。【００２８】
また、本発明によれば、記憶装置に展開されたルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータの少なくとも二つのノード群に順序を付ける方法は、請求項１０に記載されるように、
ルート・ノードを含む全ノードに固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードはデータを表す少なくとも一つの実体情報が関連付けられ、
部分ツリーはツリー型データ構造のデータの特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、
集計の対象を表す実体情報を指定し、集計の範囲を表す少なくとも二つの部分ツリーを指定するステップと、
各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群の中に集計の対象を表す実体情報が関連付けられたノードが存在するかどうかを判定し、存在する場合に、当該ノードに関連付けられた実体情報を集計するステップと、
部分ツリー毎に集計された項目値情報の順序関係に従って当該少なくとも二つの部分ツリーに順序を付けるステップと、
を有する。この方法は、集計結果を利用して、部分ツリーをソートすることができる。【００２９】
また、本発明によれば、記憶装置に展開されたルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータの少なくとも二つのノード群に順序を付ける方法は、
ルート・ノードを含む全ノードに固有のノード識別子が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、
各ノードはデータを表す少なくとも一つの実体情報が関連付けられ、
部分ツリーはツリー型データ構造のデータの特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、
順序付けの対象となる少なくとも二つの部分ツリーを指定し、順序付けの指標となる実体情報を指定するステップと、
各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群の中で、順序付けの指標となる実体情報が関連付けられたノードに関連付けられた実体情報を取得するステップと、
部分ツリー毎に取得された実体情報の順序関係に従って当該少なくとも二つの部分ツリーに順序を付けるステップと、
を有する。この方法は、実体情報を利用して部分ツリーをソートすることができる。【００３０】
本発明の好ましい実施の形態によれば、請求項１２に記載されるように、各実体情報はデータの項目を表す項目名情報又はデータの項目値を表す項目値情報である。【００３１】
また、本発明の好ましい実施の形態によれば、請求項１３に記載されるように、特定のノード及び当該特定のノードの子孫ノードを含む部分ツリーは当該特定のノードのノード識別子によって表される。これにより、一つの頂点ノードで部分ツリーを代表させることができる。検索の結果や、検索や集計の対象範囲をこの頂点ノードで記述することが可能になる。【００３２】
また、本発明の一部の好ましい実施の形態では、請求項１４に記載されるように、ルート・ノードを含む全ノードに付与された固有のノード識別子は同じ世代のノードよりも子ノードを優先して付与される。このような深さ優先の親子表現を利用すると、あるノードの子孫ノードが親子表現の連続領域に出現するという優れた性質が得られ、検索、集計、ソートの処理を高速化することが可能である。【００３３】
本発明の別の実施の形態では、請求項１５に記載されるように、ツリー型データ構造のデータはツリー識別子が付与された複数のツリーデータを含む。これにより、複数のツリーデータを検索、集計、ソートの対象として処理することが可能になる。【００３４】
請求項１乃至１５に記載された方法を実施する情報処理装置は請求項１６乃至３０に記載されている。本発明の情報処理装置は、請求項１６に記載されるように、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有し、記憶装置に記憶されたデータを検索する情報処理装置であって、
ルート・ノードを含む全ノードに固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付け、これにより、ツリー型データ構造を構成するノード間の親子関係を表現し、各ノードにデータを表す少なくとも一つの実体情報を関連付け、ツリー型データ構造を記憶装置上に構築するデータ展開手段と、
少なくとも一つの実体情報に関する検索条件を指定する条件指定手段と、
各ノードについて、当該ノードに関連付けられた少なくとも一つの実体情報が前記検索条件と一致するかどうかを判定し、一致した場合に当該ノードに検索ヒット情報を関連付け、前記ノード間の親子関係を辿って当該ノードの祖先ノードに検索ヒット情報を関連付ける検索手段と、
を有する。【００３５】
この情報処理装置において、請求項１７に記載されるように、
部分ツリーはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、
条件指定手段は、検索範囲を表す少なくとも一つの部分ツリーを指定する手段を含み、
検索手段は、検索ヒット情報が関連付けられたノードを含む部分ツリーを表す識別子を検索結果として保存する手段を含む。【００３６】
また、請求項１８に記載された情報処理装置は、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有し、記憶装置に記憶されたデータを検索する情報処理装置であって、
ルート・ノードを含む全ノードに同じ世代のノードよりも子ノードを優先して固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付け、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、各ノードにデータを表す少なくとも一つの実体情報を関連付け、ツリー型データ構造を記憶装置上に構築するデータ展開手段と、
部分ツリーはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、少なくとも一つの実体情報に関する検索条件を指定し、検索範囲を表す少なくとも一つの部分ツリーを指定する条件指定手段と、
各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群に関連付けられた少なくとも一つの実体情報が前記検索条件と一致するかどうかを判定し、一致したノードに検索ヒット情報を関連付ける検索手段と、
を有する。【００３７】
請求項１９に記載された情報処理装置は、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有し、記憶装置に記憶されたデータを検索する情報処理装置であって、
ルート・ノードを含む全ノードに同じ世代のノードよりも子ノードを優先して固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付け、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、各ノードにデータを表す少なくとも一つの実体情報を関連付け、ツリー型データ構造を記憶装置上に構築するデータ展開手段と、
部分ツリーはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、少なくとも一つの実体情報に関する検索条件を指定し、検索範囲を表す少なくとも一つの部分ツリーを指定する条件指定手段と、
各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群に関連付けられた少なくとも一つの実体情報が前記検索条件と一致するかどうかを判定し、一致したノードが存在する場合に、当該部分ツリーを表す識別子を検索結果として保存する検索手段と、
を有する。【００３８】
請求項２０に記載された情報処理装置は、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有し、記憶装置に記憶されたデータを検索する情報処理装置であって、
ルート・ノードを含む全ノードに固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付け、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、各ノードにデータを表す少なくとも一つの実体情報を関連付け、ツリー型データ構造を記憶装置上に構築するデータ展開手段と、
部分ツリーはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、少なくとも一つの実体情報に関する検索条件を指定し、検索範囲を表す少なくとも一つの部分ツリーを指定する条件指定手段と、
各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーの祖先ノードを特定し、当該部分ツリーの特定のノード及び／又は祖先ノードに関連付けられた少なくとも一つの実体情報が前記検索条件と一致するかどうかを判定し、一致したノードに検索ヒット情報を関連付ける検索手段と、
を有する。【００３９】
請求項２１に記載された情報処理装置は、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有し、記憶装置に記憶されたデータを検索する情報処理装置であって、
ルート・ノードを含む全ノードに固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付け、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、各ノードにデータを表す少なくとも一つの実体情報を関連付け、ツリー型データ構造を記憶装置上に構築するデータ展開手段と、
部分ツリーはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、少なくとも一つの実体情報に関する検索条件を指定し、検索範囲を表す少なくとも一つの部分ツリーを指定する条件指定手段と、
各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーの祖先ノードを特定し、当該部分ツリーの特定のノード及び／又は祖先ノードに関連付けられた少なくとも一つの実体情報が前記検索条件と一致するかどうかを判定し、一致したノードが存在する場合に、当該部分ツリーを表す識別子を検索結果として保存する検索手段と、
を有する。【００４０】
請求項２２に記載された情報処理装置は、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有し、第１の検索条件と第２の検索条件を論理的に組み合わせて検索する情報処理装置であって、
ルート・ノードを含む全ノードに固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付け、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、各ノードにデータを表す少なくとも一つの実体情報を関連付け、ツリー型データ構造を記憶装置上に構築するデータ展開手段と、
部分ツリーはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、検索範囲を表す少なくとも一つの部分ツリーを指定する条件指定手段と、
少なくとも一つの実体情報を指定する第１の検索条件に従って、前記ノード間の親子関係を辿って当該第１の検索条件に一致するノードが属する部分ツリーを表す識別子を第１の検索結果として保存し、少なくとも一つの実体情報を指定する第２の検索条件に従って、前記ノード間の親子関係を辿って当該第１の検索条件に一致するノードが部分ツリーを表す識別子を第２の検索結果として保存する検索手段と、
第１の検索条件と第２の検索条件の論理的な関係に対応した論理演算を第１の検索結果と第２の検索結果に実行することにより、第１の検索条件と第２の検索条件を論理的に組み合わせた検索結果を生成する組み合わせ手段と、
を有する。【００４１】
請求項２３に記載された情報処理装置は、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有し、記憶装置に記憶されたデータを集計する情報処理装置であって、
ルート・ノードを含む全ノードに同じ世代のノードよりも子ノードを優先して固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付け、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、各ノードにデータを表す少なくとも一つの実体情報を関連付け、ツリー型データ構造を記憶装置上に展開するデータ展開手段と、
部分ツリーはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、集計の対象を表す実体情報を指定し、集計の範囲を表す少なくとも一つの部分ツリーを指定する条件指定手段と、
各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群の中に集計の対象を表す実体情報が関連付けられたかどうかを判定し、存在する場合に、当該ノードに関連付けられた実体情報を集計する集計手段と、
を有する。【００４２】
請求項２４に記載された情報処理装置は、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有し、記憶装置に記憶されたデータを集計する情報処理装置であって、
ルート・ノードを含む全ノードに同じ世代のノードよりも子ノードを優先して固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付け、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、各ノードにデータを表す少なくとも一つの実体情報を関連付け、ツリー型データ構造を記憶装置上に展開するデータ展開手段と、
部分ツリーはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、集計の分類対象を表す実体情報を指定し、集計の対象を表す実体情報を指定し、集計の範囲を表す少なくとも一つの部分ツリーを指定する条件指定手段と、
各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群の中に集計の対象を表す実体情報が関連付けられたノードが存在するかどうかを判定し、存在する場合に、当該ノードに関連付けられた実体情報を、当該部分ツリーに属するノード群に関係した集計の分類対象を表す実体情報毎に集計する集計手段と、
を有する。【００４３】
請求項２５に記載された情報処理装置は、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有し、記憶装置に記憶されたデータの少なくとも二つのノード群に順序を付ける情報処理装置であって、
ルート・ノードを含む全ノードに同じ世代のノードよりも子ノードを優先して固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付け、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、各ノードにデータを表す少なくとも一つの実体情報を関連付け、ツリー型データ構造を記憶装置上に展開するデータ展開手段と、
部分ツリーはツリー型データ構造のデータの特定のノード及び当該特定のノードの子孫を含むノード群であり、集計の対象を表す実体情報を指定し、集計の範囲を表す少なくとも二つの部分ツリーを指定する条件指定手段と、
各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群の中に集計の対象を表す実体情報が関連付けられたノードが存在するかどうかを判定し、存在する場合に、当該ノードに関連付けられた実体情報を集計する集計手段と、
部分ツリー毎に集計された項目値情報の順序関係に従って当該少なくとも二つの部分ツリーに順序を付ける順序付け手段と、
を有する。【００４４】
請求項２６に記載された情報処理装置は、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する記憶装置を有し、記憶装置に記憶されたデータの少なくとも二つのノード群に順序を付ける情報処理装置であって、
ルート・ノードを含む全ノードに同じ世代のノードよりも子ノードを優先して固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付け、これにより、ツリー型データ構造を構成するノード間の親子関係が表現され、各ノードにデータを表す少なくとも一つの実体情報を関連付け、ツリー型データ構造のデータを記憶装置上に展開するデータ展開手段と、
部分ツリーはツリー型データ構造のデータの特定のノード及び当該特定のノードの子孫ノードを含むノード群であり、順序付けの対象となる少なくとも二つの部分ツリーを指定し、順序付けの指標となる実体情報を指定する条件指定手段と、
各ツリーデータに属する各部分ツリーについて、前記ノード間の親子関係を辿って当該部分ツリーに属するノード群を特定し、当該ノード群の中で、順序付けの指標となる実体情報が関連付けられたノードに関連付けられた実体情報を取得する指標取得手段と、
部分ツリー毎に取得された項目値情報の順序関係に従って当該少なくとも二つの部分ツリーに順序を付ける順序付け手段と、
を有する。【００４５】
また、本発明によれば、請求項３１乃至４５に記載されているように、請求項１乃至１５に係る方法を実行するためのプログラムが提供される。【００４６】
更に、本発明によれば、請求項３１乃至４５に記載されたプログラムを記録した記録媒体が提供される。
【発明の効果】
【００４７】
本発明によれば、ツリー型データ構造のノード間の親子関係は、「子→親」表現に基づいて表現されているので、ツリー型データ構造を操作する際にアクセスされるメモリの量が低減し、これにより、検索、集計、ソートを高速に実現することが可能となる。
【発明を実施するための最良の形態】
【００４８】
以下、添付図面を参照して、本発明の実施の形態につき説明を加える。【００４９】
［コンピュータシステム構成］
図１は、本発明の実施の形態にかかるツリー型データ構造のデータを検索、集計、ソートするコンピュータシステムのハードウェア構成を示すブロックダイヤグラムである。図１に示すように、このコンピュータシステム１０は、通常のものと同様の構成であり、プログラムを実行することによりシステム全体および個々の構成部分を制御するＣＰＵ１２、ワークデータなどを記憶するＲＡＭ(Random Access Memory)１４、プログラム等を記憶するＲＯＭ(Read Only Memory)１６、ハードディスク等の固定記憶媒体１８、ＣＤ−ＲＯＭ１９をアクセスするためのＣＤ−ＲＯＭドライバ２０、ＣＤ−ＲＯＭドライバ２０や外部ネットワーク（図示せず）と接続された外部端子との間に設けられたインタフェース（Ｉ／Ｆ）２２、キーボードやマウスからなる入力装置２４、ＣＲＴ表示装置２６を備えている。ＣＰＵ１２、ＲＡＭ１４、ＲＯＭ１６、外部記憶媒体１８、Ｉ／Ｆ２２、入力装置２４および表示装置２６は、バス２８を介して相互に接続されている。【００５０】
本実施の形態にかかる、ツリー型データ構造のデータを検索、集計、ソートするプログラム、及び、ツリー型データ構造を記憶装置上で変換するプログラムは、ＣＤ−ＲＯＭ１９に収容され、ＣＤ−ＲＯＭドライバ２０に読取られても良いし、ＲＯＭ１６に予め記憶されていても良い。また、いったんＣＤ−ＲＯＭ１９から読み出したものを、外部記憶媒体１８の所定の領域に記憶しておいても良い。或いは、上記プログラムは、ネットワーク（図示せず）、外部端子およびＩ／Ｆ２２を経て外部から供給されるものであっても良い。【００５１】
また、本発明の実施の形態にかかる情報処理装置は、コンピュータシステム１０にツリー型データ構造のデータを検索、集計、ソートするプログラムを実行させることにより実現される。【００５２】
［ツリー型データ構造］
図２Ａ、Ｂは、ツリー形式データの一例であるＰＯＳデータの説明図であり、図２Ａは、このツリー形式データのデータ構造（即ち、トポロジー）及びデータ値を視覚的に表現した一例である。図２Ｂは、同じツリー形式データをＸＭＬ形式で表現した一例である。同図に示されるようにツリー型データ構造は、ルート・ノード（本例では、ＰＯＳデータ）から始めて、各ノードで枝分かれしてリーフ・ノード（端点）に至るノードとアークの組み合わせによって表現される。各ノードには、項目名情報、すなわち、ノードのタイプと、項目値情報、すなわち、ノードの値が関連付けられ、図２Ａ、Ｂの例では、ＸＭＬ形式の
<shopName>フランス店</shopName>
に対応したノードは、「shopName（＝店名）」というノードタイプと「フランス店」というノード値が関連付けられている。この関連付けは、例えば、ノードタイプ及びノード値を記述する情報が格納されたノード情報格納領域へのポインタを、ノード識別子に随伴させることによって実現することができる。しかし、本発明は、ツリー型データ構造の実体的な値の取り扱い方によって限定されないことに注意する必要がある。【００５３】
これに対して、ツリー型データ構造のデータの検索、集計、ソートを効率的に実行するためには、ツリー型データ構造のトポロジーを表現する手法、すなわち、記憶装置に展開する手法が非常に重要な役割を果たす。そこで、以下では、主として、ツリー型データ構造のトポロジーに関して説明する。【００５４】
従来、このようなツリー型データ構造は、データを蓄えたノード間をポインタで接続することによって表現されている。しかし、ポインタ表現は、ポインタ値に必然性がないという欠点がある。即ち、ある場合には特定のノードＡがある番地（例えば、１００番地）に格納され、別の場合には同じノードＡが別の番地（例えば、２００番地）に格納されるので、ポインタ値が一定ではなく、ポインタ値は、本質的にノードの格納アドレスを表現するに過ぎない。そのため、例えば、ノードが深さ優先の規則に従ってポインタで接続されている場合、これらのノードを幅優先の規則に従ってポインタで再接続することは困難である。【００５５】
これに対して、本発明者は、ツリー型データ構造のトポロジーがアークリストによって記述可能であることに着目した。アークリストとは、ノード間の親子関係を表すアークのリストである。図３Ａ〜Ｃは、アークリストを用いたツリー型データ構造の表現形式の一例の説明図である。同図の例では、０、１０、２０、３０、４０、５０、６０、７０、８０、９０、１００及び１１０のノード識別子（ＩＤ）が付与された１２個のノードからなるツリー型データ構造が示されている。図３Ａはツリー型データ構造の全体を示している。図３Ａにおいて、（ノードのタイプを表している）丸形、ハート形などの図形の中央に記載された数字は、ノードＩＤを表し、矢印と矢印の側に記載された＜０，１０＞などの数字の対は、アークを表している。尚、ノードＩＤは、文字列には限られず、数値、特に、整数でもよい。図３Ｂは、親ノード（Ｆｒｏｍ−ＩＤ）から子ノード（Ｔｏ−ＩＤ）へのアークリストを示し、図３Ｃは、ノードＩＤとノードＴｙｐｅの対のリストからなるノードリストを示す。尚、ツリー型データ構造を表現するだけの目的のためにはノードリストが無くても構わない。原理的には、このようなアークリストを用いることによって、ノード間の関係をポインタによらずに直接的に記述することが可能である。【００５６】
［「子→親」関係に基づく表現］
図３Ａ〜Ｃの例では、アークリストは、親ノードに子ノードを対応付ける「親→子」関係に基づいて記述されている。そのため、一つの親ノード、例えば、ルート・ノード０には、３個の子ノード１０、６０及び８０が存在するため、アークリストのＦｒｏｍ−ＩＤには、同じノードＩＤの０が３回出現している。つまり、親ノードを特定しても子ノードを特定することができないので、アークリストは、要素Ｆｒｏｍ−ＩＤの配列と要素Ｔｏ−ＩＤの配列により構成される。アークリストを使用する場合、あるノードは、Ｆｒｏｍ−ＩＤの配列と、Ｔｏ−ＩＤの配列の両方の配列に出現する。【００５７】
これに対して、親子関係は、「子→親」関係によっても表現することが可能である。この場合、ノード間の親子関係は、ルート・ノード以外のノードである非ルート・ノードの各々と、関連付けられた親ノードと、の組の配列によって表現される。この「子→親」関係によって親子関係を表現する場合、「親→子」関係の場合には得られなかった重要な性質がある。即ち、一つの子ノードには必ず唯一の親ノードが対応するので、子ノードを特定することによって、この子ノードに対応する唯一の親ノードを直ちに特定することができる。つまり、アークリストは、実際には、要素Ｔｏ−ＩＤの配列だけを準備すればよい。この結果として、アークリストを格納するための記憶容量が削減される。この記憶容量の削減は、メモリへのアクセス回数が低減するという効果があるので、結果的に、処理の高速化が実現できる。【００５８】
図４Ａ〜Ｄは、「子→親」関係に基づくツリー型データ構造の表現方法の説明図である。図４Ａはツリー全体の説明図であり、図４Ｂは「子→親」関係に基づくアークリストである。図４Ｂのアークリストは、ルート・ノードに対する親ノードの格納領域を含んでいるので、ルート・ノードの親ノードとして、便宜的に"−"が設定されている。但し、ルート・ノードに対応する親ノードは存在しないので、図４Ｃに示されるように、「子→親」関係に基づくアークリストからルート・ノードに対する親ノードの格納領域を除いても構わない。このように、ルート・ノード以外のノードである非ルート・ノードの各々に対して、非ルート・ノードの親ノードを関連付けることによりノード間の親子関係を表現する。そして、「子→親」表現された子のノードから親のノードのリストを辿ることでツリーのトポロジーを表現することができる。【００５９】
このような「子→親」関係に基づくツリー型データ構造は、本発明の一実施例によれば、図５に示されるように、図１に示されたコンピュータシステム１０に、ルート・ノードを含むノードに固有のノード識別子を付与するノード定義ステップ５０１と、前記ルート・ノード以外のノードである非ルート・ノードの各々に付与されたノード識別子に、前記非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付ける親子関係定義ステップ５０２と、を実行させることによってＲＡＭ１４上に構築される。このように、最初に、文字列、浮動小数、整数などの任意の識別情報によってノードにノード識別子を付与し、次に、「子→親」表現に基づいて親子関係を定義することによって、子ノードのノード識別子から親ノードのノード識別子を引く（ルックアップする）ことでツリーのトポロジーを表現することができる。【００６０】
［ノード識別子］
好ましくは、ノード定義ステップはノード識別子として数値を使用し、より好ましくは、連続する整数を使用し、更に好ましくは、０又は１からの整数連番を使用する。これにより、ノード識別子から、そのノードに対応する親ノードのノード識別子が格納されているアドレスを簡単に取得することができるので、子ノードのノード識別子から親ノードのノード識別子を引く処理を高速化することができる。【００６１】
ツリー型データ構造のノードにノード識別子として順序付きの番号を付与してノード間の親子関係を表現する場合、番号の付与順序に規則を定めることによって、その後のツリー型データ構造の取り扱いが容易になるという利点がある。この番号の付与順序の規則として、同じ世代のノードよりも子ノードを優先する深さ優先モードと、子ノードよりも同じ世代のノードを優先する幅優先モードが利用される。【００６２】
図６Ａ〜Ｃは、ＩＤ形式のツリー構造型データを整数連番形式のツリー構造型データへ変換する処理の説明図である。図６Ａには、各ノードにＩＤ番号が付与されたツリー構造型データが示されている。図６Ｂには、変換規則が示され、図６Ｃには、各ノードに整数連番が付与されたツリー構造型データが示されている。本例の変換規則は、深さ優先で連続番号を付与する規則であり、具体的には、複数の子ノードが存在する場合、長子（一番上の兄）ノードに最小番号を付与し、末子（一番下の弟）ノードに大きい番号を付与し、かつ、兄弟ノードよりも子ノードを優先して番号を付与する。本例では、昇順に番号付けをしているが、降順に番号付けをしてもよい。【００６３】
また、図７Ａ〜Ｃは、ＩＤ形式のツリー構造型データを整数連番形式のツリー構造型データへ変換する処理の説明図である。図７Ａには、各ノードにＩＤ番号が付与されたツリー構造型データが示されている。図７Ｂには、変換規則が示され、図７Ｃには、各ノードに整数連番が付与されたツリー構造型データが示されている。本例の変換規則は、幅優先で連続番号を付与する規則であり、具体的には、複数の子ノードが存在する場合、長子（一番上の兄）ノードに最小番号を付与し、末子（一番下の弟）ノードに大きい番号を付与し、かつ、子ノードよりも兄弟ノードを優先して番号を付与する。本例では、昇順に番号付けをしているが、降順に番号付けをしてもよい。【００６４】
このようにノード識別子として番号を使用すると、ノード番号から直ちに、即ち、Ｏ（１）のオーダーで、そのノードに関する格納値が格納されているアドレスを引くことができる。また、親子関係を「子→親」表現することによって、子ノードから親ノードを直ちに、即ち、Ｏ（１）のオーダーで引くことができる。【００６５】
［深さ優先モード］
図６Ｃに示されるような深さ優先に基づくツリー型データ構造は、図１に示されたコンピュータシステム１０に、
同じ世代のノードよりも子ノードを優先して、ルート・ノードを含むノードに固有の連続する整数を付与するノード定義ステップと、
ルート・ノード以外のノードである非ルート・ノードの各々に付与された整数の順に、非ルート・ノードの各々の親ノードに付与された整数を並べることにより形成される配列を前記記憶装置に格納する親子関係定義ステップと、
を実行させることによって、記憶装置上に構築される。これにより、ノードは深さ優先で連続整数が付与され、ノード間の親子関係は「子→親」関係の配列によって表現される。【００６６】
図８は、深さ優先に基づくノード定義処理のフローチャートである。このノード定義処理は、コンピュータシステム１０に
最初にルート・ノードに番号を付与するステップ８０１と、
既に番号が付与されたあるノードに唯一の子ノードが存在する場合には、当該子ノードに当該あるノードに付与された前記番号の次の番号を付与するステップ８０２と、
既に番号が付与されたあるノードに複数の子ノードが存在する場合には、当該複数の子ノードの間の兄弟関係に従って、弟ノードは直上の兄ノードの全ての子孫ノードに番号が付与された後に次の番号が付与されるように、一番上の兄ノードから一番下の弟ノードまで番号を付与するステップ８０３と、
を実行させる。これにより、深さ優先モードで同一の親ノードから派生した複数の子ノードの間に兄弟関係が定義される。【００６７】
図９は、図６Ｃに示された深さ優先のツリー型データ構造から作成された「子→親」表現に基づく親子関係の配列の説明図である。同図にサブツリー１又はサブツリー２として示されているように、深さ優先で連続番号が付与されたノードの親子関係を「子→親」関係に基づいて配列表現すると、あるノードの子孫ノードが連続領域に出現するという優れた性質が得られる。【００６８】
一例として、深さ優先モードの優れた性質を利用することにより、前記配列から、あるノードに付与された整数以上の値が格納されている連続領域を抽出することにより、前記あるノードの全ての子孫ノードを特定することができる。これにより、あるノードの子孫ノードを表すノード群が前記配列内の連続ブロックとして獲得できる。例えば、連続ブロックのサイズをｍとすると、あるノードの全ての子孫ノードを特定するための処理速度は、Ｏ（ｍ）のオーダーになる。【００６９】
既に説明したように、ノード間の親子関係は、「子→親」関係の配列の他に、「親→子」関係の配列によっても表現できる。図１０は、図６Ｃに示された深さ優先のツリー型データ構造から作成された「親→子」表現に基づく親子関係の配列の説明図である。一つの親ノードに対して複数の子ノードが存在し得るので、親子関係の配列は、各ノードに対する子ノードの番号が格納されている領域を示すための配列Ａｇｇｒと、子ノードの番号が格納されている配列Ｐ→Ｃの二つの配列により構成される。例えば、配列Ａｇｇｒの先頭から２番目の要素Ａｇｇｒ［１］の値は”３”であり、これは、ノード［１］に対する子ノードの番号は、配列Ｐ→Ｃの要素Ｐ→Ｃ［３］以降に格納されていることを表している。これにより、ノード［０］、即ち、ルート・ノードに対する子ノードは、配列Ｐ→Ｃの先頭から３個の要素、Ｐ→Ｃ［０］の１、Ｐ→Ｃ［１］の６、及びＰ→Ｃ［２］の８であることがわかる。【００７０】
この「親→子」表現に基づく親子関係の配列の求め方を説明する。
（１）ノードの番号が配列Ｐ→Ｃの最大の添字（＝１１）と一致する場合、このノードに属する子ノードは存在しない。したがって、処理は継続されない。
（２）同図に太字で表された親ノードの番号からＡｇｇｒ値を求める。このＡｇｇｒ値は、配列Ｐ→Ｃの開始点を表す。
（３）太字で表された親ノード番号＋１に対応するＡｇｇｒ値を求める。このＡｇｇｒ値−１が配列Ｐ→Ｃの終了点である。【００７１】
例えば、ノード０の子ノードの開始点は、Ａｇｇｒ［０］、即ち、０であり、終了点は、Ａｇｇｒ［１］−１、即ち、３−１＝２である。したがって、ノード０の子ノードは、配列Ｐ→Ｃの０〜２番目の要素、即ち、１、６及び８である。【００７２】
或いは、「親→子」表現に基づく親子関係は、より単純に、親ノード番号の配列と、対応する子ノード番号の配列と、の二つの配列により表現することも可能である。しかし、この配列を利用して親子関係を見つけるためには、親ノードの番号を検索しなければならないので、即ち、ｌｏｇ（ｎ）のアクセス時間を要するので効率が悪い。【００７３】
［幅優先モード］
さらに、図７Ｃに示されるような幅優先に基づくツリー型データ構造は、図１に示されたコンピュータシステム１０に、
子ノードよりも同じ世代のノードを優先して、ルート・ノードを含むノードに固有の連続する整数を付与するノード定義ステップと、
前記ルート・ノード以外のノードである非ルート・ノードの各々に付与された整数の順に、前記非ルート・ノードの各々の親ノードに付与された整数を並べることにより形成される配列を前記記憶装置に格納する親子関係定義ステップと、
を実行させることによって、記憶装置上に構築される。これにより、ノードは幅優先モードで連続整数が付与され、ノード間の親子関係は「子→親」関係の配列によって表現される。【００７４】
図１１は、幅優先に基づくノード定義処理のフローチャートである。このノード定義処理は、コンピュータシステム１０に、
各ノードが前記ルート・ノードから何世代目のノードであるか、及び、各世代に含まれるノード数を算出するステップ１１０１と、
最初に前記ルート・ノードに番号を付与するステップ１１０２と、
ある世代に含まれる全てのノードに番号が付与されたならば、当該ある世代の次の世代にノードが存在しなくなるまで、当該次の世代に含まれる全てのノードに対して、親ノードが異なる場合には、当該親ノードに番号が付与された順番に当該ノードに番号を付与し、当該親ノードが同一である場合には、当該親ノードから派生した複数の子ノードの間に兄弟関係を定義し、一番上の兄ノードから一番下の弟ノードまで直前に付与された番号の次の番号から連続的に変化する固有の整数を順に付与するステップ１０１３と、
を実行させる。これにより、幅優先モードで同一の親ノードから派生した複数の子ノードの間に兄弟関係が定義される。【００７５】
図１２は、図７Ｃに示された幅優先のツリー型データ構造から作成された「子→親」表現に基づく親子関係の配列の説明図である。同図に示されているように、幅優先で連続番号が付与されたノードの親子関係を「子→親」関係に基づいて配列表現すると、あるノードの子ノードは連続領域に出現するという優れた性質が得られる。これは、幅優先モードで連続番号が付与されたノードの親子関係を「子→親」関係に基づいて配列表現すると、親ノードに付与された番号が前記配列中に順序付き（昇順又は降順）で出現することによる。【００７６】
したがって、幅優先モードの優れた性質を利用することにより、前記配列から、あるノードに付与された整数と同じ値が格納されている連続領域を抽出することにより、前記あるノードの全ての子ノードを特定する。これにより、あるノードの子ノードを、例えば、二分探索などの手法を用いて検索することが可能であり、即ち、Ｏ（ｌｏｇ（ｎ））のオーダーで検索することが可能になる。【００７７】
既に説明したように、ノード間の親子関係は、「子→親」関係の配列の他に、「親→子」関係の配列によっても表現できる。図１３は、図７Ｃに示された幅優先のツリー型データ構造から作成された「親→子」表現に基づく親子関係の配列の説明図である。図１３一つの親ノードに対して複数の子ノードが存在し得るので、親子関係の配列は、各ノードに対する子ノードの番号が格納されている領域を示すための配列Ａｇｇｒと、子ノードの番号が格納されている配列Ｐ→Ｃの二つの配列により構成される。例えば、配列Ａｇｇｒの先頭から２番目の要素Ａｇｇｒ［１］の値は”３”であり、これは、ノード［１］に対する子ノードの番号は、配列Ｐ→Ｃの要素Ｐ→Ｃ［３］以降に格納されていることを表している。これにより、ノード［０］、即ち、ルート・ノードに対する子ノードは、配列Ｐ→Ｃの先頭から３個の要素、Ｐ→Ｃ［０］の１、Ｐ→Ｃ［１］の２、及び、Ｐ→Ｃ［２］の３であることがわかる。【００７８】
この「親→子」表現に基づく親子関係の配列の求め方を説明する。
（１）ノードの番号が配列Ｐ→Ｃの最大の添字（＝１１）と一致する場合、このノードに属する子ノードは存在しない。したがって、処理は継続されない。
（２）同図に太字で表された親ノードの番号からＡｇｇｒ値を求める。このＡｇｇｒ値は、配列Ｐ→Ｃの開始点を表す。
（３）太字で表された親ノード番号＋１に対応するＡｇｇｒ値を求める。このＡｇｇｒ値−１が配列Ｐ→Ｃの終了点である。【００７９】
例えば、ノード０の子ノードの開始点は、Ａｇｇｒ［０］、即ち、０であり、終了点は、Ａｇｇｒ［１］−１、即ち、３−１＝２である。したがって、ノード０の子ノードは、配列Ｐ→Ｃの０〜２番目の要素、即ち、１、２及び３である。【００８０】
［ツリー型データ構造の表現形式の相互変換］
上述のように、ノードに連続番号を付与するための深さ優先モード及び幅優先モードは、それぞれ、固有の優れた性質を備えている。また、一つのツリー型データ構造は、深さ優先に基づく「子→親」表現形式と、幅優先に基づく「子→親」表現形式と、「親→子」表現形式の何れの表現形式でも表現可能である。したがって、深さ優先に基づく「子→親」表現形式と、幅優先に基づく「子→親」表現形式と、「親→子」表現形式は、適宜に相互変換可能であることに注意する必要がある。【００８１】
［頂点ノードおよび部分ツリー群］
ツリー型データ構造のデータを検索、集計、ソートする際に、ツリーデータの全体の中で特定の部分を処理の対象、例えば、検索の対象範囲とする場合がある。本発明者は、複数のノードを含む特定の部分を代表する一つのノードを導入することにより、種々の処理を効率化する手法を提案した。次に、この手法について詳述する。【００８２】
ツリー型データ構造をもつツリーデータにおいて、ルート・ノードに最も近いノードの値で、当該ノードおよびそのノードから枝分かれしてリーフ・ノード（端点）に至るまでの全てのノードを表現することを考える。ここで、あるノードおよびそのノードから枝分かれしてリーフ・ノードに至るまでのノード群を、部分ツリーと称する。また、上記ノード（ルート・ノード）に最も近いノードを頂点ノードと称する。【００８３】
図１４Ａは、前述した幅優先モードに基づくツリー型データ構造、図１４Ｂは、当該ツリー型データ構造を、「子→親」表現に基づく親子関係の配列を示す図である。たとえば、頂点ノード［４］は、ノード識別子｛４，８，９｝を含み、頂点ノード［６］は、ノード識別子｛６｝を含み、また、頂点ノード［３］は、ノード識別子｛３，７，１０，１１｝を含む。このような、複数の頂点ノードからなる配列を、頂点ノードリストと称する。頂点ノードリストにより複数の部分ツリーを指定でき、指定された複数の部分ツリーを部分ツリー群と称する。【００８４】
以下、頂点ノードリストを、［ａ，ｂ，・・・］と表す。ここに、「ａ」、「ｂ」、・・・は、頂点ノードに対応するノード識別子である。頂点ノードリストを構成する頂点ノードの各々を展開して、当該頂点ノードを頂点とする部分ツリーに含まれるすべてのノードのノード識別子を求めることを考える。求められたノード識別子のリストにおいて、あるノード識別子は１つしか存在しない場合、すなわち、ノード識別子が重複して出現しない場合、このような部分ツリー群を、「正規部分ツリー群」と称する。そうでないような部分ツリー群を、「非正規部分ツリー群」と称する。【００８５】
尚、部分ツリー群は正規部分ツリー群へ変換することが可能であり、この処理を「正規化」と称する。正規化は、集合演算を効率的に実施する上で重要になる。正規化された部分ツリー群では、どのノードも高々１つの頂点ノードに属するのみであるため、各ノードが所属する頂点ノードのリストは、高々頂点ノードの数に等しいサイズの配列で記述することができる。このため、正規化された状態では、論理積や論理和に代表される集合演算を効率的に実施することができる。【００８６】
正規部分ツリー群であっても、非正規部分ツリー群であっても、頂点ノードリストによって、頂点ノードおよびその子孫ノードからなる部分ツリー群を特定することができる。たとえば、図１５Ａに示すように、頂点ノードリスト［４，６，３］により、図１５Ｂに示すような部分ツリー群（部分ツリー｛４，８，９｝、｛６｝、｛３，７，１０，１１｝）が特定される。【００８７】
頂点ノードリストにより特定される部分ツリー群は、検索、集計、ソート、集合演算の対象とすることができる。【００８８】
たとえば、図１５Ａ、Ｂの例で、「ハート形」のノードを含む部分ツリーを検索すると、図１６Ｂに示すような部分ツリー群が得られる。図１６Ａは、この部分ツリー群を表わす頂点ノードリストである。【００８９】
また、各部分ツリーに属するノード数を集計すると、図１７Ｂに示すようになる。図１７Ａにおいて、配列１７０１は頂点ノードリスト、配列１７０２は、各頂点ノードにより特定される部分ツリーに属するノード数を示す配列である。【００９０】
たとえば、ソートとして、各部分ツリーに属するノード数によるソートを考えることができる。図１８Ａ中、配列１８０１は、ソートされた頂点ノードリスト、配列１８０２は、頂点ノードリストにより特定される部分ツリーに属するノード数を示す配列である。また、図１８Ｂは、部分ツリーがノード数にしたがってソートされた状態を示す。【００９１】
さらに、複数の部分ツリー群の間の集合演算として、論理積について説明する。図１４Ａ、Ｂに示すツリーにおいて、図１９Ｂに示す部分ツリー群（対応する頂点ノードリストを図１９Ａに示す）と、図１９Ｄに示す部分ツリー群（対応する頂点ノードリストを図１９Ｃに示す）との論理積を考える。【００９２】
図１９Ｂにおける、ノード識別子「４」の頂点ノードにて特定される部分ツリー１９０１と、図１９Ｄにおける、ノード識別子「１」の頂点ノード識別子にて特定される部分ツリー１９１１とを比較すると、部分ツリー１９０１は、部分ツリー１９０２に包含される。図１９Ｂにおける部分ツリー１９０２と包含関係をもつような部分ツリーは、図１９Ｄに示す部分ツリー群には存在しない。また、図１９Ｂにおけるノード識別子「３」の頂点ノードにて特定される部分ツリー１９０３と、図１９Ｄにおける、ノード識別子「７」にて特定される部分ツリー１９１３とを比較すると、部分ツリー１９１３は、部分ツリー１９０３に包含される。その結果、論理積演算の結果を示す頂点ノードリストは、図２０Ａに示すように、［４，７］となる。図２０Ｂは、論理積演算の結果に対応する部分ツリー群である。【００９３】
図１６Ａ、Ｂ〜図２０Ａ、Ｂにより理解できるように、頂点ノードリスト（集計においては、これに加えて、頂点ノードリストと同一サイズの、集計結果（ノード数）を格納する配列）によって、それぞれの処理や演算の結果を表わすことができる。【００９４】
［集合演算］
本実施の形態にかかる正規部分ツリー群の間では、論理積（ＡＮＤ）や論理輪（ＯＲ）、否定（ＮＯＴ）、減算（ＳＵＢ）、排他的論理和（ＸＯＲ）を定義することができる。このような演算の結果も正規部分ツリー群にて表わす。以下、これら演算について説明する。以下、図２１Ａ、Ｂに示す例において、それぞれの演算について説明する。
（１）論理和（ＯＲ）
たとえば、正規部分ツリー群［２］、［３］の論理和を考える。【００９５】
正規部分ツリー群［２］：｛２，６｝
正規部分ツリー群［３］：｛３，７，１０，１１｝
これらの論理和［２］ＯＲ［３］＝［２，３］
（［２，３］：｛２，６｝，｛３，７，１０，１１｝）
となる。【００９６】
同様に、正規部分ツリー群［３］、「７」の論理和を考える。【００９７】
正規部分ツリー群［３］：｛３，７，１０，１１｝
正規部分ツリー群［７］：｛７，１０，１１｝
したがって、これらの論理和［３］ＯＲ［７］＝［３］となる。
（２）論理積（ＡＮＤ）
正規部分ツリー群［２，３］、［７］の論理積を考える。【００９８】
正規部分ツリー群［２，３］：｛２，６，３，７，１０，１１｝
正規部分ツリー群［７］：［７，１０，１１］
したがって、これらの論理積［２，３］ＡＮＤ［７］＝［７］となる。【００９９】
演算のうち、これらの演算において実行される処理について以下に説明する。【０１００】
［論理積演算］
まず、論理積演算の原理について説明する。図２２Ａに示すように、２つの正規部分ツリー群２２０１および２２０２を考える。２つの正規部分ツリー群は、以下に述べるような関係を有する。【０１０１】
たとえば、正規部分ツリー群２２０１が正規部分ツリー群２２０２を含む場合（図２２Ｂ参照）には、２つの正規部分ツリー群の論理積は、正規部分ツリー群２２０２となる。その一方、正規部分ツリー群２２０２が正規部分ツリー群２２０１を含む場合（図２２Ｃ参照）には、２つの正規部分ツリー群の論理積は、正規部分ツリー群２２０１となる。さらに、図示しないが、双方の正規部分ツリー群が包含関係を持たない場合には、これらの間の論理積は空集合となる。【０１０２】
図２３は、論理積演算の際にシステムにて実行される処理を示すフローチャートである。図２３に示すように、論理積演算の対象となる正規部分ツリー群のそれぞれについて、マーキング配列を生成する（ステップ２３０１）。マーキング配列は、正規化演算にて生成されたフラグ配列および所属ノード配列と等価である。すなわち、正規化演算の第１の手法および第２の手法と同様の処理を実施することでマーキング配列を取得することができる。【０１０３】
次いで、システム１０は、双方のマーキング配列の対応する値を比較する（ステップ２３０２）。より詳細には、システム１０は、２つのマーキング配列中の対応する値を特定するためのポインタを初期化し（ステップ２３１１）、ポインタが示すマーキング配列の双方の値を取り出す（ステップ２３１２）。双方の値或いは一方の値が、初期値「−１」であった場合には（ステップ２３１３でノー(No)）、システム１０は、ポインタが配列の末尾を指していなければ（ステップ２３１５でノー(No)）、ポインタを移動して（ステップ２３１６）、ステップ２３１２に戻る。【０１０４】
マーキング配列の双方の値が初期値「−１」以外の値であった場合には（ステップ２３１２でイエス(Yes)）、マーキング配列の値のうち大きいほうの値が、格納番地、つまり、対応するノード識別子と等しいか否かが判断される（ステップ２３１３）。ステップ２３１３でイエス(Yes)と判断された場合には、システム１０は、当該一致する値を、論理積演算の結果を示す頂点ノード配列の値として、当該頂点ノード配列に格納する（ステップ２３１４）。その後、ポインタが配列の末尾を指していなければ（ステップ２３１５でノー(No)）、ポインタを移動して（ステップ２３１６）、ステップ２３１２に戻る。【０１０５】
ステップ２３１２でノー(No)と判断された場合には、ポインタが配列の末尾を指していなければ（ステップ２３１５でノー(No)）、ポインタを移動して（ステップ２３１６）、ステップ２３１２に戻る。【０１０６】
以下、正規部分ツリー群［３，６］と、正規部分ツリー群［２，７］のＡＮＤ演算の例について説明する。図２４は、正規部分ツリー群［３，６］および正規部分ツリー群［２，７］のそれぞれのマーキング配列が生成された状態を示す。図２４において、符号２４０１が、正規部分ツリー群［３，６］のマーキング配列（第１のマーキング配列）を示し、符号２４０２が、正規部分ツリー群［２，７］のマーキング配列（第２のマーキング配列）を示す。【０１０７】
図２５に示すように、ポインタがノード識別子「６」を示すときに（符号２５０１参照）、第１のマーキング配列の値は「６」であり、かつ、第２のマーキング配列の値が「２」である。大きい方の値は「６」であり、ノード識別子に一致する。したがって、値「６」は、論理積演算の結果を格納するための頂点ノードリストに格納される。【０１０８】
また、ポインタがノード識別子「７」を示すときに（符号２５０２参照）、第１のマーキング配列の値は「３」であり、かつ、第２のマーキング配列の値が「７」である。大きいほうの値は「７」であり、ノード識別子に一致する。したがって、値「７」は、論理積演算の結果を格納するための頂点ノードリストに格納される。このような処理の結果、［３，６］ＡＮＤ［２，７］＝［６，７］を得ることができる。【０１０９】
［論理和演算］
論理和演算は、以下のように記述することができる。【０１１０】
［ａ１，ａ２，・・・，ａｎ］ＯＲ［ｂ１，ｂ２，・・・，ｂｎ］
＝ＮＯＲＭ［ａ１，ａ２，・・・，ａｎ，ｂ１，ｂ２，・・・，ｂｎ］
つまり、上述した正規化の手法を用いれば、論理和演算の結果を示す頂点ノードリストを得ることができる。【０１１１】
たとえば、図２４に示す例において、［３，６］ＯＲ［２，７］＝ＮＯＲＭ［３，６，２，７］＝［２，３］となる。【０１１２】
［減算］
上述した論理和演算および論理積演算を利用して、正規部分ツリー群の減算は、以下のように定義することができる。なお、以下において、減算は「−（マイナス）」で表わす。【０１１３】
Ａ，Ｂ，Ｃ，Ｄをそれぞれ正規部分ツリー群とする。【０１１４】
（Ａ−Ｂ）ＡＮＤ（Ｃ−Ｄ）＝（Ａ  ＡＮＤ  Ｃ）−（Ｂ  ＯＲ  Ｄ）    （式１）
（Ａ−Ｂ）ＯＲ（Ｃ−Ｄ）＝（Ａ  ＯＲ  Ｃ）ＡＮＤ（Ｂ  ＡＮＤ  Ｄ）  （式２）
Ａ−Ｂ−Ｃ＝Ａ−（Ｂ  ＯＲ  Ｃ）      （式３）
つまり、ブール代数と同じ演算規則が成立する。【０１１５】
正規化演算などで説明したように、正規部分ツリー群は、頂点ノードリストで表わすことができる。【０１１６】
本例においては、たとえば、（式１）は、２つの頂点ノードリスト（Ａ、Ｃの論理積演算結果を示す頂点ノードリスト、および、Ｂ、Ｄの論理和演算結果を示す頂点ノードリスト）と、その間の「減算」という演算子とで表わすことができる。つまり、本来であれば、正規部分ツリー群Ａ〜Ｃのそれぞれの４つの頂点ノードリストおよびそれらの間の演算子にて表わすべきところ、２つの頂点リストおよびその間の演算子で表わすことができる。つまり、被減数の頂点ノードリストと、減数の頂点ノードリスト（除外頂点ノードリスト）とで表わすことが可能となる。【０１１７】
（式２）や（式３）についても同様である。【０１１８】
［否定、排他的論理和等］
また、正規部分ツリー群の否定（ＮＯＴ）も、除外頂点ノードリストとして表わすことができる。つまり、「ＮＯＴ  Ａ」（Ａは正規部分ツリー群）は、除外頂点ノードリストにリストされた頂点ノードおよびその子孫のノードを除いた全てのノードが、正規部分ツリー群Ａの否定となる。【０１１９】
同様に、排他的論理和も、頂点ノードリストおよび除外頂点ノードリストで表わすことが可能である。【０１２０】
［ツリーデータ検索の概要］
ツリーデータ検索は、パスの検索とノード格納値の検索の二つの側面がある。パスの検索とは、図２Ａ、Ｂにおいて、例えば、"/shop/shopName"というパス条件を満たすノードを抽出することである。また、ノード格納値の検索とは、図２Ａ、Ｂにおいて、"shopName=フランス店"であるノードを抽出することである。【０１２１】
そして、一般的なツリーデータ検索は、パスの検索とノード格納値の検索の組み合わせであり、上記の例では、"/shop/shopName=フランス店"を満たすノードを抽出することに相当する。すなわち、一般的なツリーデータ検索は、パスの条件とノード格納値の条件を同時に満たすＡＮＤ条件による検索である。ある頂点ノードが、このＡＮＤ条件を満たすかどうかは、パスの条件を調べ、パスの条件を満たすノードのノード格納値の条件を調べることにより判定することが可能である。また、このＡＮＤ条件指定による検索は、パス条件による検索の結果集合とノード格納値条件による検索の結果集合のＡＮＤ（論理積）演算を実行することにより実現できる。【０１２２】
さらに、ツリーデータ検索は、上記のパス条件とノード格納値条件のＡＮＤ条件指定による検索に限られない。例えば、パス条件とノード格納値条件の何れかを満たすノードを抽出するＯＲ条件指定による検索がある。このＯＲ条件指定による検索は、パス条件による検索の結果集合とノード格納値条件による検索の結果集合のＯＲ（論理和）演算を実行することにより実現できる。【０１２３】
［ノードの実体的な値の取り扱い方］
ツリーデータ検索では、検索条件として、パスを表すためのノードの項目名情報（例えば、ノードタイプ）と、ノード格納値を表すためのノードの項目値情報（例えば、ノード値）のような実体情報が利用される。これらの実体情報は、例えば、図２６に示されるように、ノードタイプ及びノード値を記述する情報が格納されたノード情報格納領域へのポインタを、ノード識別子に随伴させることによって特定することができる。【０１２４】
尚、すべてのノードのノードタイプが同じである場合には、ノード情報格納領域にはノード値だけを格納するように構成することが可能である。【０１２５】
［子孫のパス条件による検索］
次に、本発明の実施の形態にかかる子孫のパス条件による検索方法を説明する。子孫のパス条件による検索とは、指定されたノードタイプを有するノードを子孫ノードとして含む頂点ノードを抽出する処理である。図２７Ａ、Ｂは、本発明の一実施例にかかる子孫のパス条件による検索の対象となるツリー型データ構造と、ノードの親子関係の「子→親」表現の説明図である。本例では、各ノードの項目名情報であるノードタイプは、シンボル番号によって表され、図２７Ａでは、各ノードのノード識別子（例えば、ノード番号）が、そのノードのシンボル番号に対応した図形と共に表されている。例えば、ルート・ノードは、丸型シンボルである。また、頂点ノードは黒塗りの星印（★）で示されている。図２７Ｂは、シンボル番号と表示図形とシンボル名の対応関係を表す図である。【０１２６】
本例では、頂点ノードの子孫ノードの条件を検索条件としてノード抽出を行う。より具体的には、子孫ノードにボタン型のノードを含む頂点ノードを抽出する。【０１２７】
子孫のパス条件による検索においては、子ノードから親ノードの順番にチェックする方法１と、親ノードから子ノードの順番にチェックする方法２の２通りの方法がある。方法１は、「子→親」表現の先頭から順にチェックする方法であって、頂点ノードの個数が多い場合に効果的である。一方、方法２は、頂点ノードから始めて親から子へ順にチェックするので、頂点ノード数が少ない場合に効果的である。アプリケーションに応じて、方法１と方法２を選択的に実行してもよい。【０１２８】
［子孫のパス条件検索の方法１：子→親でチェックする方法］
本発明の実施の形態にかかるパス条件検索方法１を実行するコンピュータシステム１０のＲＡＭ１４には、図２７Ａに示されるように、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータが展開されている。より具体的には、ルート・ノードを含む全ノードに固有のノード識別子であるノード番号が付与され、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子が関連付けられ、これにより、ツリー型データ構造を構成するノード間の親子関係、すなわち、深さ優先の「子→親」による親子関係が表現されている。しかし、パス条件検索の方法１は、幅優先の「子→親」による表現形式でも同様に適用できることに注意する必要がある。各ノードは、例えば、図２６に示されるように、項目名情報であるノードタイプ（又は、シンボル番号）と、項目値情報であるノード値とが関連付けられている。【０１２９】
コンピュータシステム１０は、検索条件として、ノードのシンボル番号＝１（シンボル番号１はボタン型を表す）という条件を設定する。この条件は、例えば、ユーザがコンピュータシステム１０の入力装置２４を介して入力してもよく、又は、外部記憶媒体１８から読み出してもよく、或いは、Ｉ／Ｆ２２を介して外部から設定してもよい。【０１３０】
コンピュータシステム１０は、次に、各ノードについて、当該ノードに関連付けられたノードタイプがボタン型と一致するかどうかを判定し、一致した場合に当該ノードに検索ヒット情報を関連付け、「子→親」表現形式の親子関係を辿って当該ノードの祖先ノードに検索ヒット情報を関連付ける。検索ヒット情報は、例えば、各ノード識別子に対応したフラグ情報領域を準備し、検索がヒットした場合に、そのフラグ情報をセットすることによってノード識別子に関連付けることができる。【０１３１】
図２８は、本発明の一実施例にかかる子孫のパス条件によるツリー検索方法のフローチャートである。また、図２９Ａ〜図３３Ｃは、本発明の一実施例にかかる子孫のパス条件によるツリー検索方法の動作状態を説明する図である。【０１３２】
システム１０は、最初に、図２９Ａに示されるように、フラグ領域Flagを初期化し、シンボル番号読み出しアドレスを初期化する（ステップ２８０１）。本例では、フラグ領域は値０で初期化され、シンボル番号読み出しアドレスは先頭のアドレス０で初期化され、また、シンボル番号(Symbol
No.)は配列の形で格納されているが、この例に限定されるものではない。次に、システム１０は、このシンボル番号読み出しアドレスに対応したシンボル番号(Symbol
No.)を読み出し（ステップ２８０２）、このシンボル番号が１であるかどうかをチェックする（ステップ２８０３）。図中、チェック場所を示すポインタは太い矢印で示されている。先頭アドレス０に対応するシンボル番号は２であるため、ステップ２８０３のチェック結果はＮｏであり、次のアドレスがあるかどうかをチェックすると（ステップ２８０８）、次のアドレス１が存在するので（Ｙｅｓ）、シンボル番号読み出しアドレスを次のアドレス１に移動し（ステップ２８０５）、ステップ２８０２へ戻る。図２９Ｂに示されるように、読み出されたシンボル番号が１に合致するか、又は、次のシンボル番号読み出しアドレスがなくなるまで、ステップ２８０２、２８０３、２８０４、２８０５が繰り返される。本例では、アドレス０からアドレス６までは、シンボル番号が１に合致しない。図２９Ｃに示されるように、シンボル番号読み出しアドレスが７まで進むと、シンボル番号は１に合致する（ステップ２８０３）。【０１３３】
システム１０は、ステップ２８０３で１に合致するシンボル番号を見出すと（Ｙｅｓ）、図３０Ａに示されるように、見出したアドレス７のノードのフラグにマークを付け（ステップ２８０６）、親子関係表現Ｃ→Ｐを利用して、アドレス７の親ノードのアドレス、すなわち、アドレス６を見つけ、着目ノードを親ノードへ移動する（ステップ２８０７）。以下では、簡単のため、アドレス７のノードをノード７と称し、一般に、アドレスｎのノードをノードｎと称する。次に、システム１０は、図３０Ｂに示されるように、移動先の親ノード６がマーキングされているかどうかをチェックすると（ステップ２８０８）、ノード６のフラグはマーキングされていないため（Ｎｏ）、親ノード６のフラグにマークを付け（ステップ２８０９）、さらに親ノードがあるかどうかを調べるためステップ２８０７へ戻る。図３０Ｃに示されるように、ノード６の親ノードはノード０であり、このノード０のフラグはマーキングされていないので（ステップ２８０８、Ｎｏ）、ノード０のフラグにマークを付け（ステップ２８０９）、親ノードがあるかどうかをチェックすると（ステップ２８０７）、親ノードが存在しないため（Ｎｏ）、システム１０はステップ２８０４へ進む。【０１３４】
システム１０は、図３１Ａに示されるように、シンボル番号読み出しアドレスを次のアドレス８へ移動し（ステップ２８０５）、図３１Ｂに示されるように、読み出されたシンボル番号が１に合致するか、又は、次のシンボル番号読み出しアドレスがなくなるまで、ステップ２８０２、２８０３、２８０４、２８０５を繰り返す。図３１Ｃに示されるように、シンボル番号読み出しアドレス１１まで進むと、シンボル番号は１に合致する（ステップ２８０３）。【０１３５】
システム１０は、ステップ２８０３で１に合致するシンボル番号を見出したので（Ｙｅｓ）、図３２Ａに示されるように、見出したノード１１のフラグにマークを付け（ステップ２８０６）、親子関係表現Ｃ→Ｐを利用して、ノード１１の親ノードであるノード９へ移動する（ステップ２８０７）。次に、システム１０は、図３２Ｂに示されるように、移動先の親ノード９がマーキングされているかどうかをチェックすると（ステップ２８０８）、ノード９のフラグはマーキングされていないため（Ｎｏ）、ノード９のフラグにマークを付け（ステップ２８０９）、さらに親ノードがあるかどうかを調べるためステップ２８０７へ戻る。図３２Ｃに示されるように、ノード９の親ノードはノード８であり、ノード８のフラグはマーキングされていないため（Ｎｏ）、ノード８のフラグにマークを付け（ステップ２８０９）、さらに親ノードがあるかどうかを調べるためステップ２８０７へ戻る。ノード８の親ノードはノード０であり、図３２Ｄに示されるように、ノード０が既にマーキングされているかどうかを調べると（ステップ２８０８）、既にマーキングされているので（Ｙｅｓ）、ステップ２８０４へ進む。現在のシンボル番号読み出しアドレス１１の次のアドレスがあるかどうかをチェックすると（ステップ２８０４）と、これ以上のアドレスは存在しないため（Ｎｏ）、マーキングが終了する。【０１３６】
フラグ領域の結果は、ノードの全数検索の結果としてそのまま利用することができる。【０１３７】
さらに、システム１０は、図３３Ａに示されるように、検索範囲として、検索前の頂点ノードリストが指定されている場合、マーキングの終了後に、頂点ノードリストの各頂点ノードのフラグがマークされているかどうかをチェックし、マークされている頂点ノードを検索結果として、検索後の頂点ノードリストに格納する。頂点ノード１は、図３３Ａに示されるように、対応するフラグが０であるため、ノード１を頂点とする部分ツリーはボタン型ノードを含まないが、頂点ノード６は、図３３Ｂに示されるように、対応するフラグが１であるため（すなわち、マークされているため）、ノード６を頂点とする部分ツリーはボタン型ノードを含む。頂点ノード８も同様にして、ボタン型ノードを含む部分ツリーの頂点ノードであることがわかる。したがって、図３３Ｃに示されるように、頂点ノード６及び８を含む頂点ノードリストが検索結果として生成される。【０１３８】
上記の例では、シンボル番号が１に合致するノードが検出されたとき、そのノードのすべての親ノードを辿って、親ノードをマーキングしているが、検索範囲として、子孫の段数が指定されている場合、例えば、直下の子ノードまで、孫ノードまでなどの条件が指定されている場合、「子→親」表現による親子関係を辿る段数が制約される。【０１３９】
さらに、ノード数が膨大になると、フラグ領域の初期化のために要する時間も増加するので、この初期化の時間を短縮するテクニックを提案する。システム立ち上げ直後のような初期化時には、整数要素からなるフラグ配列のすべてを０で初期化する。システム動作時には、フラグ配列の要素がオーバーフローして０に戻るまで初期化を行わない。例えば、フラグ配列を格納する領域が３２ビット整数であるならば、２32−１回までの検索回数の範囲内では再度初期化をする必要がない。このとき、ヒットしたノードは、未使用の最小整数でマーキングする。すなわち、初回は１であり、以降、２、３、４のように増加する。したがって、頂点ノードリストが検索条件に合致しているかどうかのチェックは、マーキングに使用した値に一致するかどうかをチェックすればよい。【０１４０】
尚、上記の例では、初期値は０としたが、０以外の値でも構わない。また、マーキングに使用する整数は、未使用であれば、最小の整数に限定されない。【０１４１】
［子孫のパス条件検索の方法２：親→子でチェックする方法］
次に、親→子の順にチェックを行う本発明の実施の形態にかかるパス条件検索方法２について説明する。パス条件検索方法２を実行するコンピュータシステム１０のＲＡＭ１４には、図２７Ａに示されるように、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータが展開されている。ツリー型データ構造を構成するノード間の親子関係は、深さ優先の「子→親」による表現形式で構築される。パス条件検索方法２は、深さ優先で連続番号が付与されたノードの親子関係を「子→親」関係に基づいて配列表現すると、あるノードの子孫ノードが連続領域に出現するという上述の優れた性質を利用する。また、各ノードは、例えば、図２６に示されるように、項目名情報であるノードタイプ（又は、シンボル番号）と、項目値情報であるノード値とが関連付けられている。【０１４２】
コンピュータシステム１０は、検索条件として、ノードのシンボル番号＝１（シンボル番号１はボタン型を表す）という条件を設定する。さらに、システム１０は、検索範囲を表す少なくとも一つの部分ツリーを設定する。本例では、頂点ノード１、６、８を含む頂点ノードリスト［１，６，８］が指定される。この検索条件と検索範囲は、例えば、ユーザがコンピュータシステム１０の入力装置２４を介して入力してもよく、又は、外部記憶媒体１８から読み出してもよく、或いは、Ｉ／Ｆ２２を介して外部から設定してもよい。頂点ノードはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群を代表するノードである。【０１４３】
コンピュータシステム１０は、次に、各頂点ノードについて、前記ノード間の親子関係を辿って当該頂点ノードの子孫ノードを特定し、当該頂点ノード及び／又は当該頂点ノードの子孫ノードに関連付けられたノードタイプがボタン型と一致するかどうかを判定し、一致したノードが存在する場合に、当該頂点ノードに付与されたノード識別子を検索結果として保存する。【０１４４】
図３４は、本発明の一実施例にかかる子孫のパス条件によるツリー検索方法のフローチャートである。また、図３５Ａ〜図３７Ｃは、本発明の一実施例にかかる子孫のパス条件によるツリー検索方法の動作状態を説明する図である。【０１４５】
システム１０は、最初に、図３５Ａに示されるように、頂点ノードリストから頂点ノードを読み出すためのアドレスを示すポインタを頂点ノードリストの先頭アドレスで初期化し（ステップ３４０１）、頂点ノードリストから先頭の頂点ノード１を取り出す（ステップ３４０２）。次に、システム１０は、深さ優先の「子→親」による親子関係の表現を参照して、頂点ノード１の子孫ノードを特定する（ステップ３４０３）。一般に、深さ優先の「子→親」による親子関係の表現は上記の優れた性質を備えているので、特定ノードの子孫ノードは、この特定ノードに付与されたノード識別子が格納されている位置の次の位置から、この特定ノードに付与されたノード識別子の値以上の値が格納されている連続領域を抽出することにより特定することができる。本例では、Ｃ→Ｐにおいて、ノード１に付与されたノード識別子０が格納されている次の位置から、このノード１のノード識別子１以上の値が格納されている位置までの連続領域、すなわち、ノード識別子１、２、２、１が格納されている領域がノード１の子孫ノードの範囲である。この領域は、ノード２、ノード３、ノード４及びノード５に付与されたノード識別子を格納する領域であるため、ノード１の子孫ノードは、ノード２、ノード３、ノード４及びノード５であることがわかる。【０１４６】
次に、システム１０は、特定された子孫ノードの中に、検索条件に合致するノード、すなわち、ノードタイプがボタン型であるノードが存在するかどうかをチェックする（ステップ３４０４）。本例の場合、図３５Ｂに示されるように、頂点ノード１の子孫ノードの範囲にボタン型のノードは存在しないので、図３５Ｃに示されるように、検索結果の頂点ノードリストには何も登録せずに、システム１０はステップ３４０５へ進む。本例の場合、頂点ノードリストに次の頂点ノード６が存在するので（ステップ３４０５でＹｅｓ）、システム１０はポインタを頂点ノード６へ移動して（ステップ３４０６）、ステップ３４０２へ戻る。【０１４７】
次に、システム１０は、図３６Ａに示されるように、頂点ノードリストから頂点ノード６を取り出し（ステップ３４０２）、既に説明した子孫ノードの特定手法を用いて頂点ノード６の子孫ノードとしてノード７を特定する（ステップ３４０３）。続いて、システム１０は、図３６Ｂに示されるように、子孫ノード７のノードタイプがボタン型であるかどうかをチェックし（ステップ３４０４）、子孫ノード７が検索条件に合致することを判定する（Ｙｅｓ）。したがって、システム１０は、図３６Ｃに示されるように、頂点ノード６を検索結果である検索後の頂点ノードリストに登録し（ステップ３４０７）、ステップ３４０５へ進む。【０１４８】
本例の場合、頂点ノードリストに次の頂点ノード８が存在するので（ステップ３４０５でＹｅｓ）、システム１０はポインタを頂点ノード６へ移動して（ステップ３４０６）、ステップ３４０２へ戻る。【０１４９】
次に、システム１０は、図３７Ａに示されるように、頂点ノードリストから頂点ノード８を取り出し（ステップ３４０２）、既に説明した子孫ノードの特定手法を用いて頂点ノード８の子孫ノードとしてノード９、ノード１０及びノード１１を特定する（ステップ３４０３）。続いて、システム１０は、図３７Ｂに示されるように、子孫ノードの中にノードタイプがボタン型であるかどうかをチェックし（ステップ３４０４）、子孫ノード１１が検索条件に合致することを判定する（Ｙｅｓ）。したがって、システム１０は、図３７Ｃに示されるように、頂点ノード８を検索結果である検索後の頂点ノードリストに登録し（ステップ３４０７）、ステップ３４０５へ進む。本例では、頂点ノードリストに次の頂点ノードが存在しないので、システム１０は検索処理を終了する。【０１５０】
以上の検索処理によって、検索後の頂点ノードリスト［６，８］が得られる。【０１５１】
上記の説明では、頂点ノードの子孫ノードを特定する際に、すべての子孫ノードを特定しているが、例えば、例えば、子ノードまで、孫ノードまでのように、子孫の世代数を限定することによって検索範囲を限定することも可能である。【０１５２】
また、上記の例では、検索結果として頂点ノードリストを生成しているが、例えば、図２９Ａ〜Ｃを参照して説明したようなフラグ領域を準備し、検索条件にヒットしたすべての子孫ノードのノード識別子を検索結果として生成することも可能である。【０１５３】
［祖先のパス条件による検索］
次に、本発明の実施の形態にかかる祖先のパス条件による検索方法を説明する。祖先のパス条件による検索とは、指定されたノードタイプを有するノードを祖先ノードとしてもつ頂点ノードを抽出する処理である。図３８Ａ〜Ｃは、パス条件による検索の対象となるツリー型データ構造と、ノードの親子関係の「子→親」表現の説明図である。本例では、頂点ノードは、ノード２、ノード７及びノード９であり、頂点ノードは黒塗りの星印（★）で示されている。シンボル番号と表示図形とシンボル名の対応関係は、図２７Ｂに関して説明した通りである。本例では、頂点ノードの祖先ノードの条件を検索条件としてノード抽出を行う。より具体的には、祖先ノードにハート型のノードを含む頂点ノードを抽出する。【０１５４】
本例では、親子関係は、深さ優先の「子→親」による表現形式で表されているが、幅優先の「子→親」による表現形式でも構わない。また、各ノードは、例えば、図２６に示されるように、項目名情報であるノードタイプ（又は、シンボル番号）と、項目値情報であるノード値とが関連付けられている。【０１５５】
コンピュータシステム１０は、検索条件として、ノードのシンボル番号＝３（シンボル番号３はハート形を表す）という条件を設定する。さらに、システム１０は、検索範囲を表す少なくとも一つの部分ツリーを設定する。本例では、頂点ノード２、７、９を含む頂点ノードリスト［２，７，９］が指定される。この検索条件と検索範囲は、例えば、ユーザがコンピュータシステム１０の入力装置２４を介して入力してもよく、又は、外部記憶媒体１８から読み出してもよく、或いは、Ｉ／Ｆ２２を介して外部から設定してもよい。頂点ノードはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群を代表するノードである。【０１５６】
コンピュータシステム１０は、各頂点ノードについて、前記ノード間の親子関係を辿って当該頂点ノードの祖先ノードを特定し、当該頂点ノード又は当該頂点ノードの祖先ノードに関連付けられた少なくとも一つの実体情報が前記検索条件と一致するかどうかを判定し、一致したノードが存在する場合に、当該頂点ノードに付与されたノード識別子を検索結果として保存する。【０１５７】
図３９は、本発明の一実施例にかかる祖先のパス条件によるツリー検索方法のフローチャートである。また、図４０Ａ〜図４２Ｃは、本発明の一実施例にかかる祖先のパス条件によるツリー検索方法の動作状態を説明する図である。【０１５８】
システム１０は、最初に、図４０Ａに示されるように、頂点ノードリストから頂点ノードを読み出すためのアドレスを示すポインタを頂点ノードリストの先頭アドレスで初期化し（ステップ３９０１）、頂点ノードリストから先頭の頂点ノード２を取り出す（ステップ３９０２）。次に、システム１０は、この頂点ノード２に対応したシンボル番号(Symbol No.)を読み出し（ステップ３９０３）、このシンボル番号が３であるかどうかをチェックする（ステップ３９０４）。頂点ノード２のシンボル番号は３ではないため（Ｎｏ）、システム１０はステップ３９０５へ進み、深さ優先の「子→親」による親子関係の表現を参照して、頂点ノード２の親ノードがあるかどうかを判定し、この場合、図４０Ｂに示されるように、親ノード１が存在するので（Ｙｅｓ）、システム１０は、親ノード１に対応したシンボル番号を読み出す（ステップ３９０６）。ノード１に関連付けられたシンボル番号は５であり、検索条件に合致しないので（ステップ３９０７，Ｎｏ）、システム１０は、ステップ３９０５へ戻り、ノード１の親ノードが存在するかどうかをチェックする。この場合、図４０Ｃに示されるように、ノード１の親ノード０が存在し（Ｙｅｓ）、システム１０は、ノード０に対応したシンボル番号を読み出す（ステップ３９０６）。ノード０に関連付けられたシンボル番号は２であり、検索条件に合致しないので（ステップ３９０７，Ｎｏ）、システム１０は、ステップ３９０５へ戻り、ノード０の親ノードが存在するかどうかをチェックする。ノード０はルート・ノードであり、親ノードが存在しないため（Ｎｏ）、システム１０はステップ３９０９へ進む。【０１５９】
頂点ノードリストには次の頂点ノード７が存在するので、システム１０は、図４１Ａに示されるように、頂点ノードリストから頂点ノードを読み出すためのアドレスを示すポインタを頂点ノードリストの次のアドレスへ移動し（ステップ３９１０）、頂点ノードリストから２番目の頂点ノード７を取り出す（ステップ３９０２）。次に、システム１０は、この頂点ノード７に対応したシンボル番号を読み出し（ステップ３９０３）、このシンボル番号が３であるかどうかをチェックする（ステップ３９０４）。頂点ノード７のシンボル番号は３ではないため（Ｎｏ）、システム１０はステップ３９０５へ進み、深さ優先の「子→親」による親子関係の表現を参照して、頂点ノード７の親ノードがあるかどうかを判定し、この場合、図４１Ｂに示されるように、親ノード６が存在するので（Ｙｅｓ）、システム１０は、親ノード６に対応したシンボル番号を読み出す（ステップ３９０６）。ノード６に関連付けられたシンボル番号は３であり、検索条件に合致するので（ステップ３９０７，Ｙｅｓ）、システム１０は、ステップ３９０８へ進み、図４１Ｃに示されるように、現在のポインタが指し示す頂点ノード７を検索結果として検索後の頂点ノードリストに登録する。頂点ノード７が登録されたため、これ以上親ノードを辿る必要がないので、システム１０はステップ３９０９へ進む。【０１６０】
頂点ノードリストには次の頂点ノード９が存在するので、システム１０は、図４２Ａに示されるように、頂点ノードリストから頂点ノードを読み出すためのアドレスを示すポインタを頂点ノードリストの次のアドレスへ移動し（ステップ３９１０）、頂点ノードリストから３番目の頂点ノード９を取り出す（ステップ３９０２）。次に、システム１０は、この頂点ノード９に対応したシンボル番号を読み出し（ステップ３９０３）、このシンボル番号が３であるかどうかをチェックする（ステップ３９０４）。頂点ノード９のシンボル番号は３ではないため（Ｎｏ）、システム１０はステップ３９０５へ進み、深さ優先の「子→親」による親子関係の表現を参照して、頂点ノード９の親ノードがあるかどうかを判定し、この場合、図４２Ｂに示されるように、親ノード８が存在するので（Ｙｅｓ）、システム１０は、親ノード８に対応したシンボル番号を読み出す（ステップ３９０６）。ノード８に関連付けられたシンボル番号は３であり、検索条件に合致するので（ステップ３９０７，Ｙｅｓ）、システム１０は、ステップ３９０８へ進み、図４２Ｃに示されるように、現在のポインタが指し示す頂点ノード９を検索結果として検索後の頂点ノードリストに登録する。頂点ノード９が登録されたため、これ以上親ノードを辿る必要がないので、システム１０はステップ３９０９へ進む。頂点ノードリストには次の頂点ノードが存在しないため（ステップ３９０９，Ｎｏ）、システム１０は検索処理を終了する。【０１６１】
以上の検索処理によって、検索後の頂点ノードリスト［７，９］が得られる。【０１６２】
上記の説明では、頂点ノードの祖先ノードを辿る際に、すべての祖先ノードを探索しているが、祖先の世代数を限定することによって検索範囲を限定することも可能である。【０１６３】
また、上記の例では、検索結果として頂点ノードリストを生成しているが、例えば、図２９Ａ〜Ｃを参照して説明したようなフラグ領域を準備し、検索条件にヒットしたすべての子孫ノードのノード識別子を検索結果として生成することも可能である。【０１６４】
［値条件による検索］
ここまでは、パス条件による検索について説明したが、本発明は値条件による検索を実施することが可能である。値条件による検索とは、指定された項目値情報（例えば、ノード値）が関連付けられたノードを抽出する処理である。例えば、図２６に示されるように、項目名情報（例えば、ノードタイプ）と項目値情報（例えば、ノード値）は、ノードに対して同じように関連付けられているので、パス条件による検索、すなわち、ノードタイプを条件とする検索のアルゴリズムは、値条件による検索、すなわち、ノード値を条件とする検索に適用できることが明らかである。【０１６５】
さらに、アプリケーションによっては、すべてのノードが同じノードタイプに関連付けられる場合がある。このようなケースでは、各ノードにノードタイプを関連付ける必要がなくなるので、ノードにはノード値だけが関連付けられ、値条件による検索だけが行われる。例えば、本発明のツリー型データ構造が、プログラミング言語の構文解析に適用される場合、ノードの実体的な値は、分離されたトークン文字列だけであるため、ノードには、この文字列だけが関連付けられ、ノードタイプは使用されない。【０１６６】
［組み合わせ検索］
既に説明したように、検索でヒットしたノードを頂点ノードで代表させることが可能であり、検索の結果をこの頂点ノードのリスト、すなわち、頂点ノードリストで表現することができる。例えば、あるツリー型データ構造のデータを独立した第１の検索条件と第２の検索条件の二つの検索条件で検索した結果をそれぞれ第１の頂点ノードリストと第２の頂点ノードリストで表す場合を考える。このとき、第１の頂点ノードリストと第２の頂点ノードリストとの間で上記論理積（ＡＮＤ）集合演算を実行すると、第１の検索条件と第２の検索条件の両方を満たす検索結果を表す頂点ノードリストが得られる。【０１６７】
より具体的に、図２７Ａのツリー型データ構造のデータに対して、頂点ノードリスト［１，６，８］を検索範囲として、検索条件１＝「子孫にボタン型（シンボル番号＝１）のノードが存在する頂点ノード」及び検索条件２＝「子孫に変形四角型（シンボル番号＝４）のノードが存在する頂点ノード」を検索条件として、検索を実行する例を考える。【０１６８】
検索条件１による検索の結果は、図２８乃至３３を参照して説明したように、頂点ノードリスト１＝［６，８］である。また、検索条件２についても検索条件１と同様の検索を実行すると、検索の結果は、頂点ノードリスト２＝［１，８］であることがわかる。さらに、検索条件３＝（検索条件１）ＡＮＤ（検索条件２）を検索条件として、すなわち、検索条件３＝「子孫にボタン型のノードと変形四角型のノードが存在する頂点ノード」を検索条件として、同様に検索を実行すると、検索の結果は、頂点ノードリスト３＝［８］である。【０１６９】
一方、頂点ノードリスト１＝［６，８］と頂点ノードリスト２＝［１，８］の論理積演算を実行すると、頂点ノードリスト１と頂点ノードリスト２は共に正規部分ツリー群であるので、（頂点ノードリスト１）ＡＮＤ（頂点ノードリスト２）＝［８］＝頂点ノードリスト３であることがわかる。【０１７０】
このように、本発明によれば、複数の検索条件の論理積を検索条件とする検索の結果は、各検索条件による検索の結果の頂点ノードリストの論理積演算によって得られる。さらに、論理積の代わりに論理和を用いても同様に、複数の検索条件の論理和を検索条件とする検索の結果は、各検索条件による検索の結果の頂点ノードリストの論理和演算によって得られる。【０１７１】
［ツリーデータ集計の概要］
ツリーデータの集計は、一般に、ツリーのある範囲のノードに関連付けられた項目値情報を項目名情報ごとに分類して集計する。集計には、集計の測度である項目値情報の個数のカウント、或いは、合計値、平均値、最大値、最小値などの計算のように様々な処理が含まれる。集計の対象である測度は、例えば、ノードに関連付けられた特定のノードタイプに対応したノード値である。集計の範囲は、例えば、部分ツリー群であり、部分ツリーの頂点ノードのリスト、すなわち、頂点ノードリストによって指定できる。集計の分類対象である次元は、例えば、ノードに関連付けられた特定のノードタイプに対応したノード値である。【０１７２】
図４３Ａ、Ｂは、本発明の一実施例にかかる集計を説明するための図であり、図４３Ａは集計の対象となるツリー型データ構造とノードの親子関係の「子→親」表現の説明図であり、図４３Ｂはシンボル番号と表示図形とシンボル名の対応関係を表す図である。図４３Ａ、Ｂに示された例を参照して、２種類のツリーデータ集計を説明する。【０１７３】
第１のツリーデータ集計とは、例えば、メーカ名（次元）ごとに、重量（測度）の件数と合計を算出することである。そして、集計の範囲を指定するために、この例では、頂点ノードリスト＝［１，６，８］が使用される。勿論、集計の範囲は、ツリー全体でも構わない。【０１７４】
上記の例では、次元を指定しているが、ツリーデータ集計では次元を指定しない集計、すなわち、第２のツリーデータ集計も考えられる。例えば、頂点ノードリストを指定し、頂点ノードごとに測度を集計することができる。第２のツリーデータ集計は、この頂点ノード、すなわち、部分ツリーを明示的に指定するタイプの集計である。第２のツリーデータ集計は、図４３Ａ、Ｂの例では、頂点ノードリスト＝［１，６，８］を指定し、頂点ノード１、頂点ノード６及び頂点ノード８のそれぞれについて、頂点ノードで表された部分ツリーに含まれるノードに関連付けられた重量（測度）の件数と合計を算出する。【０１７５】
［第１のツリーデータ集計］
次に、第１のツリーデータ集計を詳細に説明する。この集計は、集計の対象＝測度、集計の範囲＝カテゴリ、集計の分類対象＝次元を指定して集計を行う。【０１７６】
ツリー型データ構造のデータは、図４３Ａに示されるように、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含み、集計を行うコンピュータシステム１０の記憶装置、例えば、ＲＡＭ１４に展開されている。ノード間の親子関係は、ルート・ノードを含む全ノードに同じ世代のノードよりも子ノードを優先して固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付けることにより定義される。各ノードはデータを表す少なくとも一つの実体情報が関連付けられている。また、頂点ノードはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群を代表するノードである。【０１７７】
コンピュータシステム１０は、集計の分類対象を表す項目名情報を指定し、集計の対象を表す項目名情報を指定し、集計の範囲を表す少なくとも一つの部分ツリーを指定する。集計の分類対象、集計の対象、及び、集計の範囲は、例えば、ユーザがコンピュータシステム１０の入力装置２４を介して入力してもよく、又は、外部記憶媒体１８から読み出してもよく、或いは、Ｉ／Ｆ２２を介して外部から設定してもよい。【０１７８】
次に、コンピュータシステム１０は、各頂点ノードについて、前記ノード間の親子関係を辿って当該頂点ノードの子孫ノードを特定し、当該頂点ノード又は当該頂点ノードの子孫ノードに関連付けられた項目名情報が集計の対象を表す項目名情報と一致するかどうかを判定し、一致したノードに関連付けられた項目値情報を、当該頂点ノードによって代表されたノード群に関係した集計の分類対象を表す項目名情報に関連付けられた項目値情報毎に集計する。【０１７９】
第１のツリーデータ集計の一実施例では、頂点ノードリストと次元と測度を指定して、頂点ノードリストで指定される範囲のノードに存在している次元値、測度を集計する。この場合、ある頂点ノードで指定される範囲（すなわち、部分ツリー）に同じ次元の次元値が関連付けられたノードが複数個存在する場合、測度がどの次元値に属するかを別途指定する必要がある。そこで、以下の例では、簡単のため、「部分ツリー内に同じ次元の次元値が関連付けられた複数のノードが存在する場合には集計を行わない」という規則を適用することにする。【０１８０】
図４３Ａに示された例を参照して、次元と集計実施可能性との関係を詳述する。図４４Ａ〜Ｄは、図４３Ａの各頂点ノードによって代表される部分ツリーの説明図である。ここで、メーカ名（次元）ごとに、重量（測度）の件数と合計を算出する集計を行うことを考える。【０１８１】
図４４Ａは、頂点ノード１によって代表される部分ツリー１を表し、ノード２とノード５の二つのノードに次元であるメーカ名が関連付けられているので、ノード１とノード３に関連付けられた重量がどのメーカ名に属しているかを特定できない。したがって、部分ツリー１に対する集計は実施しない。【０１８２】
図４４Ｂは、頂点ノード６によって代表される部分ツリー２を表している。この部分ツリー２には、次元であるメーカ名が関連付けられたノードは存在しないが、測度である重量が関連付けられたノード７が存在する。このように、次元が存在しない場合には、次元値がＮＵＬＬ値であるとして、集計を実施することにする。【０１８３】
図４４Ｃは、頂点ノード８によって代表される部分ツリー３を表している。この部分ツリー３には、次元であるメーカ名が関連付けられたノード１０が存在し、測度である重量が関連付けられたノード９及びノード１１が存在する。このように、次元が１個だけ存在し、１個以上の測度が存在する部分ツリーの場合、各測度がどの次元値に属するかを特定できるので、唯一の次元値について、１個以上の測度を集計する。【０１８４】
以上の規則に従って、メーカ名（次元）ごとに、重量（測度）の件数と合計を集計すると、図４４Ｄに示されるような集計結果が得られる。すなわち、メーカ名＝「ＮＵＬＬ」に対応した重量は、ノード７に関連付けられた重量１件であり、その重量の合計＝「ノード７に関連付けられたノード値」である。また、メーカ名＝「ノード１０に関連付けられたノード値」に対応した重量は、ノード９とノード１１に関連付けられた重量２件であり、その重量の合計＝「ノード９に関連付けられたノード値＋ノード１１に関連付けられたノード値」である。【０１８５】
図４５は、本発明の一実施例にかかる第１のツリーデータ集計方法のフローチャートである。また、図４６乃至４８は、本発明の一実施例にかかる第１のツリーデータ集計方法の動作状態を説明する図である。【０１８６】
システム１０は、最初に、図４６に示されるように、頂点ノードリストから頂点ノードを読み出すためのアドレスを示すポインタを頂点ノードリストの先頭アドレスで初期化し（ステップ４５０１）、頂点ノードリストから先頭の頂点ノード１を取り出す（ステップ４５０２）。次に、システム１０は、深さ優先の「子→親」による親子関係の表現を参照して、頂点ノード１の部分ツリーを特定する（ステップ４５０４）。一般に、深さ優先の「子→親」による親子関係の表現は上記の優れた性質を備えているので、部分ツリーは、頂点ノードに付与されたノード識別子が格納されている位置の次の位置から、この頂点ノードに付与されたノード識別子の値以上の値が格納されている連続領域を抽出することにより特定することができる。本例では、Ｃ→Ｐにおいて、ノード１に付与されたノード識別子０が格納されている位置から、このノード１のノード識別子１以上の値が格納されている位置までの連続領域、すなわち、ノード識別子０，１、２、２、１が格納されている領域が頂点ノード１によって表される部分ツリーである。この領域は、ノード１、ノード２、ノード３、ノード４及びノード５に付与されたノード識別子を格納する領域であるため、部分ツリーは、ノード1、ノード２、ノード３、ノード４及びノード５であることがわかる（図４６の※１）。【０１８７】
次に、システム１０は、特定された部分ツリーの中で、測度（＝重量）と次元（＝メーカ名）に関連付けられているノードを特定する（ステップ４５０４）。本例では、ノード１のノードタイプは重量であり、ノード２のノードタイプはメーカ名であり、ノード３のノードタイプは重量であり、ノード４のノードタイプは価格であり、ノード５のノードタイプはメーカ名である（図４６の※２）。したがって、本例では、測度が２個存在し、次元も２個存在する。システム１０は、測度の個数が０個であるかどうかを判定すると（ステップ４５０５）、測度の個数は０個ではないことがわかり（Ｎｏ）、次に、次元の個数が２個以上であるかどうかを判定する（ステップ４５０６）。次元の個数は２個以上であり（Ｙｅｓ）、この部分ツリーは集計の対象外であるため、システム１０は、次の頂点ノードが存在するかどうかを判定する（ステップ４５１１）。本例の場合、頂点ノードリストに次の頂点ノード６が存在するので（Ｙｅｓ）、システム１０はポインタを頂点ノード６へ移動して（ステップ４５１２）、ステップ４５０２へ戻る。【０１８８】
次に、システム１０は、図４７に示されるように、頂点ノードリストから頂点ノード６を取り出し（ステップ４５０２）、既に説明した方法と同様に頂点ノード６で代表される部分ツリーを特定すると（ステップ４５０３）、この部分ツリーにノード６及びノード７が属していることわかる（図４７の※１）。【０１８９】
次に、システム１０は、特定された部分ツリーの中で、測度（＝重量）と次元（＝メーカ名）に関連付けられているノードを特定する（ステップ４５０４）。本例では、ノード６のノードタイプは価格であり、ノード７のノードタイプは重量である（図４７の※２）。したがって、本例では、測度が１個存在し、次元は０個である。システム１０は、測度の個数が０個であるかどうかを判定すると（ステップ４５０５）、測度の個数は０個ではないことがわかり（Ｎｏ）、次に、次元の個数が２個以上であるかどうかを判定する（ステップ４５０６）。次元の個数は２個以上ではなく（Ｎｏ）、次元の個数が１個であるかどうかを判定すると（ステップ４５０７）、次元の個数が１個ではないため（Ｎｏ）、次元値をＮＵＬＬ値とみなし（ステップ４５０８）、測度を集計する（ステップ４５１０）。本例では、頂点ノード６で代表される部分ツリーの重量の件数は１件であり、重量の合計は、ノード７に関連付けられたノード値の値である（図示されない）。さらに、システム１０は、次の頂点ノードが存在するかどうかを判定する（ステップ４５１１）。本例の場合、頂点ノードリストに次の頂点ノード８が存在するので（Ｙｅｓ）、システム１０はポインタを頂点ノード８へ移動して（ステップ４５１２）、ステップ４５０２へ戻る。【０１９０】
次に、システム１０は、図４８に示されるように、頂点ノードリストから頂点ノード８を取り出し（ステップ４５０２）、既に説明した方法と同様に頂点ノード８で代表される部分ツリーを特定すると（ステップ４５０３）、この部分ツリーにノード８、ノード９、ノード１０及びノード１１が属していることわかる（図４８の※１）。【０１９１】
次に、システム１０は、特定された部分ツリーの中で、測度（＝重量）と次元（＝メーカ名）に関連付けられているノードを特定する（ステップ４５０４）。本例では、ノード８のノードタイプは価格であり、ノード９のノードタイプは重量であり、ノード１０のノードタイプはメーカ名であり、ノード１１のノードタイプは重量である（図４８の※２）。したがって、本例では、測度が２個存在し、次元が１個存在する。システム１０は、測度の個数が０個であるかどうかを判定すると（ステップ４５０５）、測度の個数は０個ではないことがわかり（Ｎｏ）、次に、次元の個数が２個以上であるかどうかを判定する（ステップ４５０６）。次元の個数は２個以上ではなく（Ｎｏ）、次元の個数が１個であるかどうかを判定すると（ステップ４５０７）、次元の個数が１個であるため（Ｙｅｓ）、ノード１０に関連付けられたノード値を次元値として（ステップ４５０９）、測度を集計する（ステップ４５１０）。本例では、頂点ノード８で代表される部分ツリーの重量の件数は２件であり、重量の合計は、ノード９に関連付けられたノード値の値と、ノード１１に割り当てられたノード値の値との合計である（図示されない）。【０１９２】
さらに、システム１０は、次の頂点ノードが存在するかどうかを判定する（ステップ４５１１）。本例の場合、頂点ノードリストにこれ以上頂点ノードが存在しないため（Ｎｏ）、システム１０は、部分ツリー毎に得られた集計結果を統合する（ステップ４５１３）。本例では、集計の次元値は、ＮＵＬＬ値と、ノード１０に割り当てられたメーカ名（ノード１０に関連付けられたノード値）であり、ＮＵＬＬ値に対応する重量の件数は１件であり、重量の合計は、ノード７に割り当てられた重量（ノード７に関連付けられたノード値）であり、ノード１０に割り当てられたメーカ名に対応する重量の件数は２件であり、重量の合計は、ノード９に関連付けられたノード値の値と、ノード１１に割り当てられたノード値の値との合計である。以上の処理により、本発明の一実施例による第１のツリーデータ集計方法が終了する。【０１９３】
上記の説明では、頂点ノードによって代表される部分ツリーを特定する際に、すべての子孫ノードを特定しているが、例えば、例えば、子ノードまで、孫ノードまでのように、子孫の世代数を限定することによって集計範囲を限定することも可能である。【０１９４】
また、上記の例では、ノード間の親子関係が深さ優先モードで表現されているが、幅優先モードで表現し、そこから部分ツリーを特定しても構わない。【０１９５】
［第２のツリーデータ集計］
次に、次元を指定しない第２のツリーデータ集計方法をより詳しく説明する。【０１９６】
ツリー型データ構造のデータは、図４３Ａに示されるように、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含み、集計を行うコンピュータシステム１０の記憶装置、例えば、ＲＡＭ１４に展開されている。ノード間の親子関係は、ルート・ノードを含む全ノードに同じ世代のノードよりも子ノードを優先して固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付けることにより定義される。各ノードはデータを表す少なくとも一つの実体情報が関連付けられている。また、頂点ノードはツリー型データ構造の特定のノード及び当該特定のノードの子孫ノードを含むノード群を代表するノードである。【０１９７】
コンピュータシステム１０は、集計の分類対象を表す項目名情報を指定し、集計の範囲を表す少なくとも一つの部分ツリーを指定する。集計の分類対象、及び、集計の範囲は、例えば、ユーザがコンピュータシステム１０の入力装置２４を介して入力してもよく、又は、外部記憶媒体１８から読み出してもよく、或いは、Ｉ／Ｆ２２を介して外部から設定してもよい。【０１９８】
次に、コンピュータシステム１０は、各頂点ノードについて、前記ノード間の親子関係を辿って当該頂点ノードの子孫ノードを特定し、当該頂点ノード及び／又は当該頂点ノードの子孫ノードに関連付けられた項目名情報が集計の対象と一致するかどうかを判定し、一致したノードに関連付けられた項目値情報を集計する。【０１９９】
図４３Ａ、Ｂの例では、第２のツリーデータ集計方法は、頂点ノードリスト＝［１，６，８］を指定し、頂点ノード１、頂点ノード６及び頂点ノード８のそれぞれについて、頂点ノードで表された部分ツリーに含まれるノードに関連付けられた重量（測度）の件数と合計を算出する。図４９は本発明の一実施例にかかる第２のツリーデータ集計方法のフローチャートであり、図５０Ａ〜Ｄはこの第２のツリーデータ集計方法の動作状態の説明図である。【０２００】
図４９に示されるように、第２のツリーデータ集計方法は、図４５に示された第１のツリーデータ集計方法と類似した動作を実行するが、次元を定義しないため、次元についての処理は省略され、また、部分ツリー毎の集計結果を統合する処理も省かれている。【０２０１】
システム１０は、頂点ノードリストから頂点ノードを取り出し、その部分ツリーを特定することにより（図４９のステップ４９０２、ステップ４９０３）、図５０Ａ、Ｂ及びＣに示されるような部分ツリー１、部分ツリー２及び部分ツリー３を特定し、それぞれの部分ツリーについて、重量の件数と重量の合計を算出する（ステップ４９０６）。図５０Ｄには、頂点ノード毎の集計結果が示されている。【０２０２】
上記の説明では、頂点ノードによって代表される部分ツリーを特定する際に、すべての子孫ノードを特定しているが、例えば、例えば、子ノードまで、孫ノードまでのように、子孫の世代数を限定することによって集計範囲を限定することも可能である。【０２０３】
また、上記の例では、ノード間の親子関係が深さ優先モードで表現されているが、幅優先モードで表現し、そこから部分ツリーを特定しても構わない。【０２０４】
［ツリーデータソートの概要］
本発明にかかるツリーデータのソート処理は、記憶装置に展開されたルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータの少なくとも二つのノード群（ノードの集まり、例えば、部分ツリー）に順序を付ける処理である。以下では、簡単のため、ノード群が部分ツリーである場合について説明する。【０２０５】
本発明のツリーデータのソート処理は、個々の部分ツリーに関連付けられたある指標（比較基準値）を収集し、次に、この指標に順序関係を付けることにより、部分ツリー自体に順序を付けることにより実現される。【０２０６】
ソート処理は、指標の収集の仕方によって二通りに大別できる。第１のツリーデータソート方法は、集計の結果を利用する方法である。例えば、上記の第２のツリーデータ集計方法では、部分ツリー毎に集計結果が収集されている。したがって、例えば、図５０Ａ〜Ｄの例において、部分ツリー１〜３を「重量の件数」の多い順に並べることが要求された場合、図５０Ｄに示された「重量の件数」を指標として用いると、この指標の大小関係に応じて、部分ツリー１〜３に順序関係を定義することができ、すなわち、部分ツリー１〜３をソートすることができる。【０２０７】
これに対して、第２のツリーデータソート方法は、集計結果を利用するのではなく、部分ツリーのノードに関連付けられた情報をそのまま指標として利用して、部分ツリーに順序関係を定義する。第２のツリーデータソート方法は、例えば、図５０Ａ〜Ｄの例では、部分ツリーの中で、ノードタイプが「価格」であるノードのノード値、すなわち、「価格の値」の順に部分ツリーをソートする。【０２０８】
［第１のツリーデータソート］
本発明の一実施例にかかる第１のツリーデータソート方法は、例えば、図４３Ａに示されるようなツリー型データ構造のデータの頂点ノード１、頂点ノード６及び頂点ノード８でそれぞれ表される部分ツリー１（図５０Ａ）、部分ツリー２（図５０Ｂ）及び部分ツリー３（図５０Ｃ）を重量の件数を指標としてソートする。【０２０９】
コンピュータシステム１０の記憶装置、例えば、ＲＡＭ１４には、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータが展開されている。ノード間の親子関係は、図４３Ａに示されるように、ルート・ノードを含む全ノードに同じ世代のノードよりも子ノードを優先して固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付けることにより表現されている。各ノードはデータの項目を表す項目名情報（例えば、ノードタイプ）とデータの項目値を表す項目値情報（例えば、ノード値）とが関連付けられ、各ノード群（例えば、部分ツリー１、部分ツリー２及び部分ツリー３）は当該ノード群を代表する頂点ノード（例えば、頂点ノード１、頂点ノード６及び頂点ノード８）及び当該頂点ノードの子孫ノードを含む。【０２１０】
コンピュータシステム１０は、集計の対象を表す項目名情報（例えば、ノードタイプ＝「重量」）を指定し、集計の範囲を表す少なくとも二つの頂点ノード（例えば、頂点ノード１、頂点ノード６及び頂点ノード８を含む頂点ノードリストを指定する。集計の対象、及び、集計の範囲は、例えば、ユーザがコンピュータシステム１０の入力装置２４を介して入力してもよく、又は、外部記憶媒体１８から読み出してもよく、或いは、Ｉ／Ｆ２２を介して外部から設定してもよい。【０２１１】
次に、コンピュータシステム１０は、各頂点ノードについて、前記ノード間の親子関係を辿って当該頂点ノードの子孫ノードを特定し、当該頂点ノード又は当該頂点ノードの子孫ノードに関連付けられた項目名情報が集計の対象と一致するかどうかを判定し、一致したノードに関連付けられた項目値情報を集計する。この集計は、例えば、図４９および図５０Ａ〜Ｄを参照して説明した上記の第２のツリーデータ集計方法を実行する。図５１Ａ〜Ｃは、本発明の一実施例にかかる第１のツリーデータソート方法の説明図であり、図５１Ａには、第２のツリーデータ集計方法を実行することにより得られた比較基準値の収集結果が示されている。本例では、頂点ノード毎の重量の件数が比較基準値の収集結果である。【０２１２】
次に、コンピュータシステム１０は、頂点ノード毎に集計された項目値情報の順序関係に従って当該少なくとも二つの頂点ノードに順序を付けることにより、当該頂点ノードによって代表されるノード群に順序を付ける。本例では、頂点ノード１に対応する重量の件数である２と、頂点ノード６に対応する重量の件数である１と、頂点ノード８に対応する重量の件数である２を、昇順に並べ換えることにより、頂点ノードに順序が付けられる。この順序付けにより、頂点ノードは、頂点ノード６、頂点ノード１、頂点ノード８の順に並べられる。例えば、比較基準値が一致する場合には、元の頂点ノードの順番を保存して頂点ノードの順序付けを行う。図５１Ｂは、このようにして得られた比較基準値のソート結果である。頂点ノードに順序を付けることにより、図５１Ｃに示されるように、これらの頂点ノードによって代表される部分ツリーに順序を付けることができる。【０２１３】
上記の説明では、頂点ノードによって代表される部分ツリーを特定する際に、すべての子孫ノードを特定しているが、例えば、例えば、子ノードまで、孫ノードまでのように、子孫の世代数を限定することによって集計範囲を限定することも可能である。【０２１４】
また、上記の例では、ノード間の親子関係が深さ優先モードで表現されているが、幅優先モードで表現し、そこから部分ツリーを特定しても構わない。【０２１５】
［第２のツリーデータソート］
次に、本発明の一実施例にかかる第２のツリーデータソート方法について説明する。図５２Ａ〜Ｃは、本発明の一実施例にかかる第２のツリーデータソート方法の処理の対象となるツリー型データ構造及びノードの親子関係の「子→親」表現（図５２Ａ）と、ノードタイプ毎のノード値のリスト（図５２Ｂ）と、ノードに関連付けられたノードタイプ及びノード値（図５２Ｃ）と、を説明する図である。頂点ノードは黒塗りの星印（★）で示されている。本例では、各ノードの項目名情報であるノードタイプは、シンボル番号（＝Ｓｙｍｂｏｌ  Ｎｏ．）によって表される。図形とシンボル番号との対応関係は、図４３Ｂに示されている。【０２１６】
本例では、各ノードの項目値情報であるノード値は、シンボル番号と値番号（＝ＶＮｏ）を組み合わせて表される。シンボル番号毎に、すなわち、ノードタイプ毎に、そのノードタイプが表す項目の値が昇順（又は降順）に配置された値リスト（＝ＶＬ）が設けられる。値番号は、値リストへのポインタであり、例えば、ノードｘにシンボル番号ｉと値番号ｊが関連付けられている場合、ノードｘのノード値は、シンボル番号ｉに固有の値リストのｊ番目の要素を参照することによって取得できる（例えば、先頭の要素が０番目の要素であるとする）。このような値番号と値リストの組み合わせによって実際の値を指定する方式は、本願発明者によって提案されている（例えば、国際公開第ＷＯ００／１０１０３号パンフレットを参照のこと）。【０２１７】
例えば、図５２Ａ〜Ｃに示されたツリーデータにおいて、頂点ノード１、頂点ノード６及び頂点ノード８によって代表される部分ツリーをそれぞれ部分ツリー１、部分ツリー２及び部分ツリー３とする。各部分ツリーに属する価格の値を参照するためには、最初に、各部分ツリーに属するノードの中で、ノードタイプ＝「価格」に関連付けられたノードを特定し、次に、特定されたノードに関連付けられたノード値を参照することが必要である。部分ツリー１には、ノード１、ノード２、ノード３、ノード４及びノード５が属している。これらのノードの中で、ノードタイプが「価格」であるノードには、シンボル番号＝「２」が関連付けられている。同図の例では、ノード４はシンボル番号＝「２」が関連付けられている。よって、ノード４はノードタイプ＝「価格」である。次に、ノード４の価格の値を参照するため、最初に、ノード４に関連付けられた値番号を参照すると、値番号＝「３」である。したがって、ノード４に関連付けられたノード値は、シンボル番号＝「２」に対応した値リスト、すなわち、（価格）ＶＬの値番号３に対応した要素（すなわち、先頭から４番目の要素）である。本例では、（価格）ＶＬの値番号３に対応した要素は「２００」である。このようにして、ノード４に関連付けられたノード値が取得される。【０２１８】
コンピュータシステム１０の記憶装置、例えば、ＲＡＭ１４には、図５２Ａ〜Ｃに示されるように、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータが展開されている。ノード間の親子関係は、ルート・ノードを含む全ノードに同じ世代のノードよりも子ノードを優先して固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付けることにより定義される。各ノードはデータを表す少なくとも一つの実体情報が関連付けられ、各ノード群は当該ノード群を代表する頂点ノードである特定のノード及び当該特定のノードの子孫ノードを含む。【０２１９】
次に、コンピュータシステム１０は、順序付けの対象となる少なくとも二つのノード群を表す頂点ノードを指定し、順序付けの指標となる項目名情報を指定する順序付けの対象（例えば、頂点ノードリスト）、及び、順序付けの指標（例えば、ノードタイプ）は、例えば、ユーザがコンピュータシステム１０の入力装置２４を介して入力してもよく、又は、外部記憶媒体１８から読み出してもよく、或いは、Ｉ／Ｆ２２を介して外部から設定してもよい。【０２２０】
次に、コンピュータシステム１０は、各頂点ノードについて、前記ノード間の親子関係を辿って当該頂点ノードの子孫ノードを特定し、当該頂点ノード又は当該頂点ノードの子孫ノードの中で、順序付けの指標となる項目名情報が関連付けられたノードに関連付けられた項目値情報を取得する。図５２Ａ〜Ｃの例では、上記の方法でノード値を取得すればよい。【０２２１】
さらに、コンピュータシステム１０は、頂点ノード毎に取得された項目値情報の順序関係（例えば、取得されたノード値の大小関係）に従って当該少なくとも二つの頂点ノードに順序を付けることにより、当該頂点ノードによって代表されるノード群（例えば、部分ツリー）に順序を付ける。【０２２２】
次に、ノード値の取得と部分ツリーの順序付けについてより詳細に説明する。図５３は、本発明の一実施例にかかる第２のツリーデータソート方法のフローチャートである。コンピュータシステム１０は、頂点ノードリスト及び指標を指定し（ステップ５３０１）、作業用領域を初期化する（ステップ５３０２）。続いて、コンピュータシステム１０は、頂点ノードリスト（＝［１，６，８］）の各頂点ノードについて、順序付けの指標値（＝価格の値）に対応した値番号を取得する（ステップ５３０３）。続いて、コンピュータシステム１０は、各頂点ノードについて取得された値番号の出現回数をカウントし（ステップ５３０４）、さらに、値番号毎にカウントされた出現回数を累計数化する（ステップ５３０５）。最後に、コンピュータシステム１０は、頂点ノードリスト中の各頂点ノードを、累計数に基づいて、各頂点ノードに対応した値番号の順番にソートする（ステップ５３０６）。尚、値番号の順序（昇順又は降順）はソートの順番に対応している。【０２２３】
図５４乃至６２は、図５２Ａ〜Ｃに示されたツリー型データ構造のデータに本発明の一実施例にかかる第２のツリーデータソート方法を適用したときの動作状態を説明する図である。【０２２４】
コンピュータシステム１０は、図５４に示されるように、ソート前頂点ノードリスト＝［１，６，８］を指定し（ステップ５３０１）、このソート前頂点ノードリストと同じサイズの一時的値番号格納領域Ｔｍｐ−ＶＮｏ、及び、ソート後頂点ノードリスト格納領域を用意し、また、価格の値リストＶＬと同じサイズのカウント領域Ｃｏｕｎｔを用意する（ステップ５３０２）。【０２２５】
次に、コンピュータシステム１０は、図５５に示されるように、頂点ノードリストから１番目の頂点ノード１を取り出し、頂点ノード１に対応した部分ツリーを特定する（図５５の※１）。次に、コンピュータシステム１０は、部分ツリーの中で、シンボル番号＝２であるノード（すなわち、ノードタイプが「価格」であるノード）を特定し、その特定されたノードに関連付けられた値番号ＶＮｏである「３」を、Ｔｍｐ−ＶＮｏの１番目の領域に格納する（図５５の※２）。次に、コンピュータシステム１０は、図５６に示されるように、頂点ノードリストから２番目の頂点ノード６を取り出し、頂点ノード６に対応した部分ツリーを特定する（図５６の※１）。次に、コンピュータシステム１０は、部分ツリーの中で、シンボル番号＝２であるノード（すなわち、ノードタイプが「価格」であるノード）を特定し、その特定されたノードに関連付けられた値番号ＶＮｏである「２」を、Ｔｍｐ−ＶＮｏの２番目の領域に格納する（図５６の※２）。次に、コンピュータシステム１０は、図５７に示されるように、頂点ノードリストから３番目の頂点ノード８を取り出し、頂点ノード８に対応した部分ツリーを特定する（図５７の※１）。次に、コンピュータシステム１０は、部分ツリーの中で、シンボル番号＝２であるノード（すなわち、ノードタイプが「価格」であるノード）を特定し、その特定されたノードに関連付けられた値番号ＶＮｏである「１」を、Ｔｍｐ−ＶＮｏの３番目の領域に格納する（図５７の※２）。これにより、コンピュータシステム１０は頂点ノードに関連した値番号を取得できる（ステップ５３０３）。【０２２６】
コンピュータシステム１０は、次に、頂点ノードリストに対応したＴｍｐ−ＶＮｏに格納された値番号の出現回数（存在数）をカウントする（ステップ５３０４）。図５８に示されるように、頂点ノードリストの先頭の要素＝頂点ノード１に対応したＴｍｐ−ＶＮｏの要素Ｔｍｐ−ＶＮｏ［０］が「３」であるため、値番号＝３に対応したカウント領域の要素Ｃｏｕｎｔ［３］をインクリメントし、同様に、Ｔｍｐ−ＶＮｏ［１］＝２であるため、Ｃｏｕｎｔ［２］をインクリメントし、Ｔｍｐ−ＶＮｏ［２］＝１であるため、Ｃｏｕｎｔ［１］をインクリメントする。これにより、図５８の完成したＣｏｕｎｔが得られる。【０２２７】
コンピュータシステム１０は、次に、Ｃｏｕｎｔの要素を累計して、カウント配列Ｃｏｕｎｔを累計数配列Ａｇｇｒに変換する（ステップ５３０５）。図５９に示されるように、カウント配列Ｃｏｕｎｔが、
Ｃｏｕｎｔ［０］＝０
Ｃｏｕｎｔ［１］＝１
Ｃｏｕｎｔ［２］＝１
Ｃｏｕｎｔ［３］＝１
であるので、累計数配列Ａｇｇｒの要素は、
Ａｇｇｒ［０］＝０
Ａｇｇｒ［１］＝Ｃｏｕｎｔ［０］＝０
Ａｇｇｒ［２］＝Ｃｏｕｎｔ［０］＋Ｃｏｕｎｔ［１］＝１
Ａｇｇｒ［３］＝Ｃｏｕｎｔ［０］＋Ｃｏｕｎｔ［１］＋Ｃｏｕｎｔ［２］＝２
となる。尚、説明の便宜上、カウント配列Ｃｏｕｎｔと累計数配列Ａｇｇｒは区別されているが、物理的にはカウント配列Ｃｏｕｎｔの領域と累計数配列Ａｇｇｒの領域が同じ領域でも構わない。このようにして得られた累計数配列Ａｇｇｒは、ステップ５３０３で取得された値番号を昇順に並べたときに（同じ値番号が２個以上存在するときには、その個数分が重複して並べられる）、各値番号の先頭の位置を示している。本例では、値番号＝３、値番号＝２、値番号＝１が１回ずつ出現しているので、これらの値番号を昇順に並べると、
値番号＝１
値番号＝２
値番号＝３
の順番になる。このとき、値番号＝０は存在しないので、値番号の昇順配列における値番号＝０の先頭の位置はアドレス０（＝Ａｇｇｒ［０］）であり、値番号＝１の先頭の位置はアドレス０（＝Ａｇｇｒ［１］）であり、値番号２の先頭の位置はアドレス１（＝Ａｇｇｒ［２］）であり、値番号３の先頭の位置はアドレス２（＝Ａｇｇｒ［３］）である。このようにして、図５９に示されるように、累計数配列Ａｇｇｒが得られる。この累計数配列Ａｇｇｒは、ソート後頂点ノードリストの格納位置を示すポインタの配列であるとみなすことができる。【０２２８】
最後に、コンピュータシステム１０は、累計数配列Ａｇｇｒを利用して、頂点ノードリスト中の頂点ノードを、その頂点ノードに関連付けられた値番号の順に並べ換える（ステップ５３０６）。【０２２９】
コンピュータシステム１０は、図６０に示されるように、頂点ノードリストから１番目の要素であるソート前頂点ノードリスト［０］＝頂点ノード１を取り出し、頂点ノード１に対応したＴｍｐ−ＶＮｏ［０］＝３が指し示す累計数配列Ａｇｇｒの要素であるＡｇｇｒ［３］＝２によって示されるソート後頂点ノードリストの要素、すなわち、ソート後頂点ノードリスト［２］に、ソート前頂点ノードリスト［０］＝１をセットする。そして、Ａｇｇｒ［３］をインクリメントする。このインクリメントによって、ソート後頂点ノードリストの格納位置を示すポインタが次の位置へ移動するので、値番号が重複している場合でも、正しく頂点ノードリストをソートすることができる。【０２３０】
コンピュータシステム１０は、図６１に示されるように、ソート前頂点ノードリストの要素であるソート前頂点ノードリスト［１］＝６に対しても同様に、頂点ノード６に対応したＴｍｐ−ＶＮｏ［１］＝２が指し示す累計数配列Ａｇｇｒの要素であるＡｇｇｒ［２］＝１によって示されるソート後頂点ノードリストの要素、すなわち、ソート後頂点ノードリスト［１］に、ソート前頂点ノードリスト［１］＝６をセットする。そして、Ａｇｇｒ［２］をインクリメントする。【０２３１】
さらに、コンピュータシステム１０は、図６２Ａに示されるように、ソート前頂点ノードリストの要素であるソート前頂点ノードリスト［３］＝８に対しても同様に、頂点ノード８に対応したＴｍｐ−ＶＮｏ［２］＝１が指し示す累計数配列Ａｇｇｒの要素であるＡｇｇｒ［１］＝０によって示されるソート後頂点ノードリストの要素、すなわち、ソート後頂点ノードリスト［０］に、ソート前頂点ノードリスト［２］＝８をセットする。そして、Ａｇｇｒ［１］をインクリメントする。【０２３２】
以上の処理により、コンピュータシステム１０は、図６２Ｂに示されるように、ソート前頂点ノードリストを、価格で昇順にソートすることにより、ソート後頂点ノードリストに変換することができる。【０２３３】
尚、以上の説明では、ある項目名情報（例えば、あるノードタイプ）の値がソートの指標として指定されたときに、一つの部分ツリーには、その項目名情報が関連付けられているノードが一つである例に関して第２のツリーデータソートを記述しているが、一つの部分ツリー内に、指標としてヒットするノードが２個以上存在する場合がある。その場合には、ソートの目的や仕様等のアプリケーションに応じて一つのノードを選択する。また、一つの部分ツリー内に、指標としてヒットするノードが存在しない場合、その部分ツリーは、アプリケーションに応じて、ソートの対象から外す、又は、最下位の順番を付与する、などの取扱をすることができる。【０２３４】
さらに、上記の説明では、頂点ノードによって代表される部分ツリーを特定する際に、すべての子孫ノードを特定しているが、例えば、例えば、子ノードまで、孫ノードまでのように、子孫の世代数を限定することによって集計範囲を限定することも可能である。【０２３５】
また、上記の例では、ノード間の親子関係が深さ優先モードで表現されているが、幅優先モードで表現し、そこから部分ツリーを特定しても構わない。【０２３６】
［ツリー群への拡張］
ここまでの説明では、ツリー型データ構造のデータの検索、集計及びソートは、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含む一つのツリーデータを処理の対象としている。しかし、実際的なアプリケーションでは、ツリー型データ構造のデータは、複数のツリーデータにより構成される場合がある。このような場合には、各ツリーデータは、ツリー識別子が付与され、このツリー識別子によって区別される。そして、本発明は、各ツリーデータに対して、上記のツリー型データ構造のデータの検索、集計及びソートの方法を実施することにより、複数のツリーデータを含むツリー型データ構造のデータにも適用可能である。【０２３７】
図６３Ａ〜Ｅは、複数のツリーデータにより構成されたツリー型データ構造のデータ、すなわち、ツリー群の一例を示す図である。同図の例では、ある製品の生産するために必要な部品の仕入れに関する情報（仕入先、メーカ、品番、重量、価格など）がツリー型データ構造のデータとして表されている。さらに、その部品には、複数の代替品と複数の仕入先があるため、入手ルート毎に別個のツリーデータが準備されている。各ノードは、そのノードに関連付けられた項目名情報（すなわち、ノードタイプ）と項目値情報（すなわち、ノード値）を用いて、（ノードタイプ、ノード値）の形で表されている。【０２３８】
図６３Ａのデータは、ツリー識別子がツリーデータ１であり、ルート・ノードが（品番、１）であり、ルート・ノードの子ノードとして、ノード（メーカ、Ａ）、ノード（重量、１０）、ノード（価格、５０００）、ノード（仕入先、α）が存在する。図６３ＡからＥに示されるように、各ツリーデータは構造が異なっていても構わない。また、図６３Ｅに示されたツリーデータ５は、ノードタイプ＝メーカに対応したノードを含まない。【０２３９】
このようなツリー型データ構造のデータに対しても、検索、集計、ソートを行うことが可能である。検索、集計、ソートは、ツリーデータ毎に個別に行われ、その後、検索、集計、ソートの結果が統合される。統合された結果は、ツリーデータ識別子を介して、各ツリーデータと関連付けられる。本例では、各ツリーデータのルート・ノードは頂点ノードである。【０２４０】
例えば、項目名情報＝「メーカ」であるパス条件による検索を実行すると、ツリーデータ１の頂点ノード、ツリーデータ２の頂点ノード、ツリーデータ３の頂点ノード、及び、ツリーデータ４の頂点ノードが検索にヒットする。しかし、ツリーデータ５の頂点ノードは検索にヒットしない。なぜならば、ツリーデータ５には、項目名情報＝「メーカ」に関連付けられたノードが存在しないからである。この検索の結果は、ツリーデータのツリーデータ識別子と頂点ノードのノード識別子の組の集合により表現される。検索にヒットしたノードそのものを検索結果とする場合も同様に、ツリーデータ識別子とノード識別子の組の集合により検索結果が表現される。【０２４１】
また、項目名情報＝「価格」、項目値情報≦４２００であるノードを検索する項目値検索を行うことが可能である。頂点ノードを検索結果として返却する場合、この検索条件を満たす頂点ノードは、ツリーデータ３の頂点ノード、ツリーデータ４の頂点ノード、ツリーデータ５の頂点ノードである。同様に、項目名情報＝「重量」であり、項目値情報≦１２であるノードを検索する項目値検索を実行すると、この検索にヒットする頂点ノードは、ツリーデータ１の頂点ノード、ツリーデータ２の頂点ノード、ツリーデータ３の頂点ノードである。【０２４２】
次に、検索条件１＝「項目名情報＝「価格」、項目値情報≦４２００」と検索条件２＝「項目名情報＝「重量」、項目値情報≦１２」を満たす頂点ノードを検索すると、価格の値が４２００以下のノードと、重量の値が１２以下のノードの両方のノードを子孫ノードとして含む頂点ノードは、ツリーデータ３の頂点ノードであることがわかる。一方、このＡＮＤ検索の結果は、検索条件１の検索結果＝「ツリーデータ３の頂点ノード、ツリーデータ４の頂点ノード、ツリーデータ５の頂点ノード」と、検索条件２の検索結果＝「ツリーデータ１の頂点ノード、ツリーデータ２の頂点ノード、ツリーデータ３の頂点ノード」との間の論理積演算の結果と一致している。【０２４３】
さらに、「仕入先毎の件数」や「重量毎の価格平均」などの集計を行うことが可能である。このような集計は、上記の本発明の第１のノードデータ集計方法において、集計の範囲を表す頂点ノードリストの要素がツリーデータ識別子とノード識別子の組によって特定されるように拡張することによって実現できる。【０２４４】
最後に、「低価格順」のようなソートも、上記の本発明の第１のツリーデータソート方法或いは第２のツリーデータソート方法において、頂点ノードリストの要素がツリーデータ識別子とノード識別子の組によって特定されるように拡張することによって実現できる。【０２４５】
以上のように、本発明は、ノードをツリーデータ識別子とノード識別子の組によって識別し、各ツリーデータに対して、ツリー型データ構造のデータの検索、集計及びソートの方法を実施することにより、複数のツリーデータを含むツリー型データ構造のデータにも拡張できる。【０２４６】
［情報処理装置］
図６４は、本発明の一実施例によるツリー型データ構造のデータを処理する情報処理装置６４００のブロック図である。情報処理装置６４００は、ツリー型データ構造を表現するデータを記憶する記憶部６４０１と、ツリー型データ構造のデータを記憶部６４０１上に展開するデータ展開部６４０２と、ツリーデータ処理のための条件を設定する条件指定部６４０３と、条件指定部６４０３によって設定された条件に従って記憶部６４０１上に展開されたデータを処理するツリーデータ処理部６４０４と、を含む。【０２４７】
ツリーデータ処理部６４０４は、ツリーデータ検索を実行する検索部６４０５と、ツリーデータ集計を実行する集計部６４０６と、ツリーデータソートのための指標を取得する指標取得部６４０８と、集計部６４０６からの集計結果又は指標取得部６４０８からの指標を受け取って、ツリーデータソートを実行する順序付け部６４０７と、を含む。【０２４８】
記憶部６４０１は、ルート・ノードとルート・ノード以外のノードである非ルート・ノードを含むツリー型データ構造のデータを記憶する。データ展開部６４０２は、ルート・ノードを含む全ノードに固有のノード識別子を付与し、非ルート・ノードの各々に付与されたノード識別子に非ルート・ノードの各々の親ノードに付与されたノード識別子を関連付け、これにより、ツリー型データ構造を構成するノード間の親子関係を表現し、各ノードにデータを表す少なくとも一つの実体情報を関連付け、ツリー型データ構造を記憶装置上に構築する。データ展開部６４０２は、ルート・ノードを含む全ノードに同じ世代のノードよりも子ノードを優先して固有のノード識別子を付与してもよい。【０２４９】
条件指定部６４０３は、検索、集計、ソートの目的に応じて各種の条件を設定する。これらの条件は、ユーザによって図示されないユーザ・インタフェース装置を介して指定され、或いは、外部装置から取り込まれる。各種の条件には、少なくとも一つの実体情報に関する検索条件、検索範囲を表す少なくとも一つの部分ツリー、集計の対象を表す項目名情報、集計の範囲を表す少なくとも一つの部分ツリー、順序付けの対象となる少なくとも二つのノード群を表す頂点ノード、或いは、順序付けの指標となる項目名情報などが含まれる。【０２５０】
検索部６４０５は、各ノードについて、当該ノードに関連付けられた少なくとも一つの実体情報が前記検索条件と一致するかどうかを判定し、一致した場合に当該ノードに検索ヒット情報を関連付け、前記ノード間の親子関係を辿って当該ノードの祖先ノードに検索ヒット情報を関連付ける。また、検索部６４０５は、少なくとも一つの頂点ノードのうち検索ヒット情報が関連付けられた頂点ノードに付与されたノード識別子を検索結果として保存してもよい。或いは、検索部６４０５は、各頂点ノードについて、前記ノード間の親子関係を辿って当該頂点ノードの祖先ノードを特定し、当該頂点ノード及び／又は当該頂点ノードの祖先ノードに関連付けられた少なくとも一つの実体情報が前記検索条件と一致するかどうかを判定し、一致したノードに検索ヒット情報を関連付ける。【０２５１】
他の一実施例では、検索部６４０５は、少なくとも一つの実体情報を指定する第１の検索条件に従って、前記ノード間の親子関係を辿って当該第１の検索条件に一致するノードが属するノード群を代表する頂点ノードに付与されたノード識別子を第１の検索結果として保存し、少なくとも一つの実体情報を指定する第２の検索条件に従って、前記ノード間の親子関係を辿って当該第１の検索条件に一致するノードが属するノード群を代表する頂点ノードに付与されたノード識別子を第２の検索結果として保存し、第１の検索条件と第２の検索条件の論理的な関係に対応した論理演算を第１の検索結果と第２の検索結果に実行することにより、第１の検索条件と第２の検索条件を論理的に組み合わせた検索結果を生成する。【０２５２】
集計部６４０６は、各頂点ノードについて、前記ノード間の親子関係を辿って当該頂点ノードの子孫ノードを特定し、当該頂点ノード及び／又は当該頂点ノードの子孫ノードに関連付けられた項目名情報が集計の対象と一致するかどうかを判定し、一致したノードに関連付けられた項目値情報を集計する。他の一実施例では、集計部６４０６は、各頂点ノードについて、前記ノード間の親子関係を辿って当該頂点ノードの子孫ノードを特定し、当該頂点ノード又は当該頂点ノードの子孫ノードに関連付けられた項目名情報が集計の対象を表す項目名情報と一致するかどうかを判定し、一致したノードに関連付けられた項目値情報を、当該頂点ノードによって代表されたノード群に関係した集計の分類対象を表す項目名情報に関連付けられた項目値情報毎に集計する。【０２５３】
順序付け部６４０７は、頂点ノード毎に集計された項目値情報の順序関係に従って当該少なくとも二つの頂点ノードに順序を付けることにより、当該頂点ノードによって代表されるノード群に順序を付ける。【０２５４】
他の一実施例では、指標取得部６４０８は、各ツリーデータに属する各頂点ノードについて、前記ノード間の親子関係を辿って当該頂点ノードの子孫ノードを特定し、当該頂点ノード又は当該頂点ノードの子孫ノードの中で、順序付けの指標となる項目名情報が関連付けられたノードに関連付けられた項目値情報を取得する。順序付け部６４０７は、頂点ノード毎に取得された項目値情報の順序関係に従って当該少なくとも二つの頂点ノードに順序を付けることにより、当該頂点ノードによって代表されるノード群に順序を付ける。【０２５５】
本発明は、以上の実施の形態に限定されることなく、特許請求の範囲に記載された発明の範囲内で、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【図面の簡単な説明】
【０２５６】
【図１】図１は、本発明の実施の形態にかかるツリー型データ構造を取り扱うコンピュータシステムのブロックダイヤグラムである。
【図２】図２Ａ、Ｂは、ツリー形式データの一例であるＰＯＳデータの説明図であり、図２Ａは、このツリー形式データのデータ構造（即ち、トポロジー）及びデータ値を視覚的に表現した例であり、図２Ｂは、同じツリー形式データをＸＭＬ形式で表現した例である。
【図３】図３Ａ〜Ｃは、アークリストを用いたツリー型データ構造の表現形式の一例の説明図である。
【図４】図４Ａ〜Ｃは、「子→親」関係に基づくツリー型データ構造の表現方法の説明図である。
【図５】図５は、ツリー型データ構造を記憶装置上に構築する方法のフローチャートである。
【図６】図６Ａ〜Ｃは、ＩＤ形式のツリー構造型データを整数連番形式のツリー構造型データへ変換する処理の説明図である。
【図７】図７Ａ〜Ｃは、ＩＤ形式のツリー構造型データを整数連番形式のツリー構造型データへ変換する処理の説明図である。
【図８】図８は、深さ優先に基づくノード定義処理のフローチャートである。
【図９】図９は、「子→親」表現に基づく親子関係の配列の説明図である。
【図１０】図１０は、図６Ｃに示された深さ優先のツリー型データ構造から作成された「親→子」表現に基づく親子関係の配列の説明図である。
【図１１】図１１は、幅優先に基づくノード定義処理のフローチャートである。
【図１２】図１２は、「子→親」表現に基づく親子関係の配列の説明図である。
【図１３】図１３は、図７Ｃに示された深さ優先のツリー型データ構造から作成された「親→子」表現に基づく親子関係の配列の説明図である。
【図１４】図１４Ａは、幅優先モードに基づくツリー型データ構造、図１４Ｂは、当該ツリー型データ構造を、「子→親」表現に基づく親子関係の配列を示す図である。
【図１５】図１５Ａは、頂点ノードリストの例、図１５Ｂは、頂点ノードリストで特定される部分ツリー群の例を示す図である。
【図１６】図１６Ａは、検索処理により得られた頂点ノードリストの例、図１６Ｂは、頂点ノードリストで特定される部分ツリー群の例を示す図である。
【図１７】図１７Ａは、集計処理により得られた頂点ノードリストおよび集計結果を示す配列の例、図１７Ｂは、頂点ノードリストで特定される部分ツリー群の例を示す図である。
【図１８】図１８Ａは、ノード数でソートされた頂点ノードリスト、および、対応するノード数を示す配列の例、図１８Ｂは、頂点ノードリストで特定される部分ツリーの例を示す図である。
【図１９】図１９Ａ、Ｃは、それぞれ、論理積演算の対象となる頂点ノードリストの例、図１９Ｂ、Ｄは、それぞれ頂点ノードリストで特定される部分ツリー群の例を示す図である。
【図２０】図２０Ａは、論理積演算の結果を示す頂点ノードリストの例、図２０Ｂは、頂点ノードリストで特定される部分ツリー群を示す図である。
【図２１】図２１Ａは、幅優先モードに基づくツリー型データ構造、図２１Ｂは、当該ツリー型データ構造を、「子→親」表現に基づく親子関係の配列を示す図である。
【図２２】図２２Ａ、Ｂは、論理積演算を説明する図である。
【図２３】図２３は、論理積演算の処理を示すフローチャートである。
【図２４】図２４は、論理積演算の処理例を示す図である。
【図２５】図２５は、論理積演算の処理例を示す図である。
【図２６】図２６は、実体的な値の取り扱い方の一例を示す図である。
【図２７】図２７Ａは、本発明の一実施例にかかる子孫のパス条件による検索の対象となるツリー型データ構造とノードの親子関係の「子→親」表現の説明図であり、図２７Ｂはシンボル番号と表示図形とシンボル名の対応関係を表す図である。
【図２８】図２８は、本発明の一実施例にかかる子孫のパス条件によるツリー検索方法のフローチャートである。
【図２９】図２９Ａ〜Ｃは、本発明の一実施例にかかる子孫のパス条件によるツリー検索方法の動作状態を説明する図である。
【図３０】図３０Ａ〜Ｃは、本発明の一実施例にかかる子孫のパス条件によるツリー検索方法の動作状態を説明する図である。
【図３１】図３１Ａ〜Ｃは、本発明の一実施例にかかる子孫のパス条件によるツリー検索方法の動作状態を説明する図である。
【図３２】図３２Ａ〜Ｄは、本発明の一実施例にかかる子孫のパス条件によるツリー検索方法の動作状態を説明する図である。
【図３３】図３３Ａ〜Ｃは、本発明の一実施例にかかる子孫のパス条件によるツリー検索方法の動作状態を説明する図である。
【図３４】図３４は、本発明の一実施例にかかる子孫のパス条件によるツリー検索方法のフローチャートである。
【図３５】図３５Ａ〜Ｃは、本発明の一実施例にかかる子孫のパス条件によるツリー検索方法の動作状態を説明する図である。
【図３６】図３６Ａ〜Ｃは、本発明の一実施例にかかる子孫のパス条件によるツリー検索方法の動作状態を説明する図である。
【図３７】図３７Ａ〜Ｃは、本発明の一実施例にかかる子孫のパス条件によるツリー検索方法の動作状態を説明する図である。
【図３８】図３８Ａ〜Ｃは、本発明の一実施例にかかる祖先のパス条件による検索の対象となるツリー型データ構造とノードの親子関係の「子→親」表現の説明図である。
【図３９】図３９は、本発明の一実施例にかかる祖先のパス条件によるツリー検索方法のフローチャートである。
【図４０】図４０Ａ〜Ｃは、本発明の一実施例にかかる祖先のパス条件によるツリー検索方法の動作状態を説明する図である。
【図４１】図４１Ａ〜Ｃは、本発明の一実施例にかかる祖先のパス条件によるツリー検索方法の動作状態を説明する図である。
【図４２】図４２Ａ〜Ｃは、本発明の一実施例にかかる祖先のパス条件によるツリー検索方法の動作状態を説明する図である。
【図４３】図４３Ａは、本発明の一実施例にかかる集計の対象となるツリー型データ構造とノードの親子関係の「子→親」表現の説明図であり、図４３Ｂはシンボル番号と表示図形とシンボル名の対応関係を表す図である。
【図４４】図４４Ａ〜Ｄは、図４３Ａの各頂点ノードによって代表される部分ツリーの説明図である。
【図４５】図４５は、本発明の一実施例にかかる第１のツリーデータ集計方法のフローチャートである。
【図４６】図４６は、本発明の一実施例にかかる第１のツリーデータ集計方法の動作状態を説明する図である。
【図４７】図４７は、本発明の一実施例にかかる第１のツリーデータ集計方法の動作状態を説明する図である。
【図４８】図４８は、本発明の一実施例にかかる第１のツリーデータ集計方法の動作状態を説明する図である。
【図４９】図４９は、本発明の一実施例にかかる第２のツリーデータ集計方法のフローチャートである。
【図５０】図５０Ａ〜Ｄは、本発明の一実施例にかかる第２のツリーデータ集計方法の動作状態を説明する図である。
【図５１】図５１Ａ〜Ｃは、本発明の一実施例にかかる第１のツリーデータソート方法の説明図である。
【図５２】図５２Ａは本発明の一実施例にかかる第２のツリーデータソート方法の処理の対象となるツリー型データ構造及びノードの親子関係の「子→親」表現を示し、図５２Ｂはノードタイプ毎のノード値のリストを示し、図５２Ｃはノードに関連付けられたノードタイプ及びノード値を示す図である。
【図５３】図５３は、本発明の一実施例にかかる第２のツリーデータ集計方法のフローチャートである。
【図５４】図５４は、図５２Ａ〜Ｃに示されたツリー型データ構造のデータに本発明の一実施例にかかる第２のツリーデータソート方法を適用したときの動作状態の説明図である。
【図５５】図５５は、図５２Ａ〜Ｃに示されたツリー型データ構造のデータに本発明の一実施例にかかる第２のツリーデータソート方法を適用したときの動作状態の説明図である。
【図５６】図５６は、図５２Ａ〜Ｃに示されたツリー型データ構造のデータに本発明の一実施例にかかる第２のツリーデータソート方法を適用したときの動作状態の説明図である。
【図５７】図５７は、図５２Ａ〜Ｃに示されたツリー型データ構造のデータに本発明の一実施例にかかる第２のツリーデータソート方法を適用したときの動作状態の説明図である。
【図５８】図５８は、図５２Ａ〜Ｃに示されたツリー型データ構造のデータに本発明の一実施例にかかる第２のツリーデータソート方法を適用したときの動作状態の説明図である。
【図５９】図５９は、図５２Ａ〜Ｃに示されたツリー型データ構造のデータに本発明の一実施例にかかる第２のツリーデータソート方法を適用したときの動作状態の説明図である。
【図６０】図６０は、図５２Ａ〜Ｃに示されたツリー型データ構造のデータに本発明の一実施例にかかる第２のツリーデータソート方法を適用したときの動作状態の説明図である。
【図６１】図６１は、図５２Ａ〜Ｃに示されたツリー型データ構造のデータに本発明の一実施例にかかる第２のツリーデータソート方法を適用したときの動作状態の説明図である。
【図６２】図６２Ａ、Ｂは、図５２Ａ〜Ｃに示されたツリー型データ構造のデータに本発明の一実施例にかかる第２のツリーデータソート方法を適用したときの動作状態の説明図である。
【図６３】図６３Ａ〜Ｅは、複数のツリーデータにより構成されたツリー型データ構造のデータの一例を示す図である。
【図６４】図６４は、本発明の一実施例による情報処置装置のブロック図である。
【符号の説明】
【０２５７】
１０        コンピュータシステム
１２        ＣＰＵ
１４        ＲＡＭ
１６        ＲＯＭ
１８        固定記憶装置
２０        ＣＤ−ＲＯＭドライバ
２２        Ｉ／Ｆ
２４        入力装置
２６        表示装置
６４００    情報処理装置
６４０１    記憶部
６４０２    データ展開部
６４０３    条件指定部
６４０４    ツリーデータ処理部
６４０５    検索部
６４０６    集計部
６４０７    順序付け部
６４０８    指標取得部
【図１】
0004796970.tif 000002
【図２】
0004796970.tif 000003
【図３】
0004796970.tif 000004
【図４】
0004796970.tif 000005
【図５】
0004796970.tif 000006
【図６】
0004796970.tif 000007
【図７】
0004796970.tif 000008
【図８】
0004796970.tif 000009
【図９】
0004796970.tif 000010
【図１０】
0004796970.tif 000011
【図１１】
0004796970.tif 000012
【図１２】
0004796970.tif 000013
【図１３】
0004796970.tif 000014
【図１４】
0004796970.tif 000015
【図１５】
0004796970.tif 000016
【図１６】
0004796970.tif 000017
【図１７】
0004796970.tif 000018
【図１８】
0004796970.tif 000019
【図１９】
0004796970.tif 000020
【図２０】
0004796970.tif 000021
【図２１】
0004796970.tif 000022
【図２２】
0004796970.tif 000023
【図２３】
0004796970.tif 000024
【図２４】
0004796970.tif 000025
【図２５】
0004796970.tif 000026
【図２６】
0004796970.tif 000027
【図２７】
0004796970.tif 000028
【図２８】
0004796970.tif 000029
【図２９】
0004796970.tif 000030
【図３０】
0004796970.tif 000031
【図３１】
0004796970.tif 000032
【図３２】
0004796970.tif 000033
【図３３】
0004796970.tif 000034
【図３４】
0004796970.tif 000035
【図３５】
0004796970.tif 000036
【図３６】
0004796970.tif 000037
【図３７】
0004796970.tif 000038
【図３８】
0004796970.tif 000039
【図３９】
0004796970.tif 000040
【図４０】
0004796970.tif 000041
【図４１】
0004796970.tif 000042
【図４２】
0004796970.tif 000043
【図４３】
0004796970.tif 000044
【図４４】
0004796970.tif 000045
【図４５】
0004796970.tif 000046
【図４６】
0004796970.tif 000047
【図４７】
0004796970.tif 000048
【図４８】
0004796970.tif 000049
【図４９】
0004796970.tif 000050
【図５０】
0004796970.tif 000051
【図５１】
0004796970.tif 000052
【図５２】
0004796970.tif 000053
【図５３】
0004796970.tif 000054
【図５４】
0004796970.tif 000055
【図５５】
0004796970.tif 000056
【図５６】
0004796970.tif 000057
【図５７】
0004796970.tif 000058
【図５８】
0004796970.tif 000059
【図５９】
0004796970.tif 000060
【図６０】
0004796970.tif 000061
【図６１】
0004796970.tif 000062
【図６２】
0004796970.tif 000063
【図６３】
0004796970.tif 000064
【図６４】
0004796970.tif 000065