(57)【要約】  各ノードが属性名及び属性値によって表現される複数のノードからなるツリー構造データは、１個のレコードが１個のノードに対応し、各レコードがレコードの並び順を表すレコード順序番号によって識別される、仮想的なレコードの配列によって表現される。レコードは、当該レコードに対応するノードの親ノードのレコード順序番号を格納する親子関係フィールドと、当該ノードに属する属性名を指定する属性名番号を格納する属性名フィールドと、当該ノードに属する属性値を指定する属性値番号を格納する属性値フィールドとを含む。
2009095981.tif 000002
【特許請求の範囲】
【請求項１】
各ノードが属性名及び属性値によって表現される複数のノードからなるツリー構造データを各レコードがレコードの並び順を表すレコード順序番号によって識別される仮想的なレコードの配列として記憶装置上に構築する装置であって、
階層構造を有する複数のテーブルを階層毎にマッチングキーによってマッチングさせ、親側のテーブルと子側のテーブルとの間で親子関係がある行番号同士の行番号対応表を作成する手段と、
前記行番号対応表から親子関係がある前記親側のテーブル中の行番号及び前記子側のテーブル中の行番号を探索する手段と、
前記探索する手段によって見つけられた順に、前記子側のテーブル中の行に割り当てられるレコード順序番号を決定し、前記仮想的なレコードの配列中の前記レコード順序番号によって識別される位置に、親子関係フィールド値として前記子側のテーブル中の行に対応するノードの親ノードのレコード順序番号を格納し、前記ノードの属性名フィールド値として前記子側のテーブル中の行に属する項目名を格納し、前記ノードの属性値フィールド値として前記子側のテーブル中の行に属する項目値を格納する手段と、
を備える装置。
【請求項２】
前記ノードの属性名フィールド値が前記レコード順序番号の順番に格納されている配列から、前記レコード順序番号の順に前記属性名を一意に特定する属性名番号が格納されている属性名番号配列、前記属性名番号配列の要素の順番に前記属性名番号によって一意に特定される前記属性名が格納されている属性名配列、前記レコード順序番号の順に前記属性値を一意に特定する属性値番号が格納されている属性値番号配列、及び、前記属性値番号配列の要素の順番に前記属性値番号によって一意に特定される前記属性値が格納されている属性値配列を作成する手段をさらに備える、請求項１に記載の装置。
【請求項３】
前記複数のテーブルが部品の親子関係を表現するストラクチャー型部品表であり、
前記行番号対応表を作成する手段が、最上位階層のテーブルとして、前記ツリー構造データのルートノードに対応する部品を選択し、その他の階層のデータとして同一の前記ストラクチャー型部品表を利用する、
請求項１又は２に記載の装置。
【請求項４】
前記行番号対応表を作成する手段が、前記マッチングキーとして、前記親側のテーブルにおけるデータの出現順に割り当てられた順序番号と、前記子側のテーブルにおけるデータに対応する親側のデータに割り当てられた順序番号との対を利用する、請求項１又は２に記載の装置。
【請求項５】
階層構造を有する複数のテーブルを記憶するメモリを備え、前記複数のテーブルを各ノードが属性名及び属性値によって表現される複数のノードからなるツリー構造データに変換し前記メモリに格納する装置であって、
前記複数のテーブルを階層毎にマッチングキーによってマッチングさせるマッチング部と、
前記複数のテーブルの階層毎にマッチングした親側のテーブルと子側のテーブルとの間で親子関係がある行番号同士の行番号対応表を作成する対応表作成部と、
前記行番号対応表から親子関係がある前記親側のテーブル中の行番号及び前記子側のテーブル中の行番号を探索する探索部と、
前記探索部によって見つけられた順に、前記子側のテーブル中の行に割り当てられるレコード順序番号を決定し、前記仮想的なレコードの配列中の前記レコード順序番号によって識別される位置に、親子関係フィールド値として前記子側のテーブル中の行に対応するノードの親ノードのレコード順序番号を格納し、前記ノードの属性名フィールド値として前記子側のテーブル中の行に属する項目名を格納し、前記ノードの属性値フィールド値として前記子側のテーブル中の行に属する前記原データに属する項目値を格納するレコード生成部と、
を備え、
前記ツリー構造データが、各レコードがレコードの並び順を表す前記レコード順序番号によって識別される、仮想的なレコードの配列として前記メモリに構築される装置。
【請求項６】
前記ノードの属性名フィールド値が前記レコード順序番号の順番に格納されている配列から、前記レコード順序番号の順に前記属性名を一意に特定する属性名番号が格納されている属性名番号配列、前記属性名番号配列の要素の順番に前記属性名番号によって一意に特定される前記属性名が格納されている属性名配列、前記レコード順序番号の順に前記属性値を一意に特定する属性値番号が格納されている属性値番号配列、及び、前記属性値番号配列の要素の順番に前記属性値番号によって一意に特定される前記属性値が格納されている属性値配列を作成する値分離部をさらに備える、請求項５に記載の装置。
【請求項７】
前記複数のテーブルが部品の親子関係を表現するストラクチャー型部品表であり、
前記対応表作成部が、最上位階層の表構造の中間データとして、前記ツリー構造データのルートノードに対応する部品を選択し、その他の表構造の中間データとして同一の前記ストラクチャー型部品表を利用する、
請求項５又は６に記載の装置。
【請求項８】
前記対応表作成部が、前記マッチングキーとして、前記親側のテーブルにおけるデータの出現順に割り当てられた順序番号と、前記子側のテーブルにおけるデータに対応する親側のデータに割り当てられた順序番号との対を利用する、請求項５又は６に記載の装置。
【請求項９】
各ノードが属性名及び属性値によって表現される複数のノードからなるツリー構造データを各レコードがレコードの並び順を表すレコード順序番号によって識別される仮想的なレコードの配列として記憶装置上に構築する方法であって、
階層構造を有する複数のテーブルを階層毎にマッチングキーによってマッチングさせ、親側のテーブルと子側のテーブルとの間で親子関係がある行番号同士の行番号対応表を作成するステップと、
前記行番号対応表から親子関係がある前記親側のテーブル中の行番号及び前記子側のテーブル中の行番号を探索し、探索によって見つけられた順に、前記子側のテーブル中の行に割り当てられるレコード順序番号を決定し、前記仮想的なレコードの配列中の前記レコード順序番号によって識別される位置に、親子関係フィールド値として前記子側のテーブル中の行に対応するノードの親ノードのレコード順序番号を格納し、前記ノードの属性名フィールド値として前記子側のテーブル中の行に属する項目名を格納し、前記ノードの属性値フィールド値として前記子側のテーブル中の行に属する項目値を格納するステップと、
を備える方法。
【請求項１０】
前記ノードの属性名フィールド値が前記レコード順序番号の順番に格納されている配列から、前記レコード順序番号の順に前記属性名を一意に特定する属性名番号が格納されている属性名番号配列、前記属性名番号配列の要素の順番に前記属性名番号によって一意に特定される前記属性名が格納されている属性名配列、前記レコード順序番号の順に前記属性値を一意に特定する属性値番号が格納されている属性値番号配列、及び、前記属性値番号配列の要素の順番に前記属性値番号によって一意に特定される前記属性値が格納されている属性値配列を作成するステップをさらに備える、請求項９に記載の方法。
【請求項１１】
前記複数のテーブルが部品の親子関係を表現するストラクチャー型部品表であり、
前記行番号対応表を作成するステップにおいて、最上位階層のテーブルとして、前記ツリー構造データのルートノードに対応する部品を選択し、その他の階層のテーブルとして同一の前記ストラクチャー型部品表を利用する、
請求項９又は１０に記載の方法。
【請求項１２】
前記行番号対応表を作成するステップにおいて、前記マッチングキーとして、前記親側のテーブルにおけるデータの出現順に割り当てられた順序番号と、前記子側のテーブルにおけるデータに対応する親側のデータに割り当てられた順序番号との対を利用する、請求項９又は１０に記載の方法。
【請求項１３】
階層構造を有する複数のテーブルを記憶するメモリを備え、前記複数のテーブルを各ノードが属性名及び属性値によって表現される複数のノードからなるツリー構造データに変換し前記メモリに格納するコンピュータに、
前記複数のテーブルを階層毎にマッチングキーによってマッチングさせる機能と、
前記複数のテーブルの階層毎に、マッチングした親側のテーブルと子側のテーブルとの間で、親子関係がある行番号同士の行番号対応表を作成する機能と、
前記行番号対応表から親子関係がある前記親側のテーブル中の行番号及び前記子側のテーブル中の行番号を探索する機能と、
探索によって見つけられた順に、前記子側のテーブル中の行に割り当てられる前記レコード順序番号を決定する機能と、
前記ツリー構造データが、各レコードがレコードの並び順を表す前記レコード順序番号によって識別される、仮想的なレコードの配列として前記メモリに構築されるように、前記仮想的なレコードの配列中の前記レコード順序番号によって識別される位置に、親子関係フィールド値として前記子側のテーブル中の行に対応するノードの親ノードのレコード順序番号を格納し、前記ノードの属性名フィールド値として前記子側のテーブル中の行に属する項目名を格納し、前記ノードの属性値フィールド値として前記子側のテーブル中の行に属する項目値を格納する機能と、
を実現させるためのプログラム。
【請求項１４】
前記ノードの属性名フィールド値が前記レコード順序番号の順番に格納されている配列から、前記レコード順序番号の順に前記属性名を一意に特定する属性名番号が格納されている属性名番号配列、前記属性名番号配列の要素の順番に前記属性名番号によって一意に特定される前記属性名が格納されている属性名配列、前記レコード順序番号の順に前記属性値を一意に特定する属性値番号が格納されている属性値番号配列、及び、前記属性値番号配列の要素の順番に前記属性値番号によって一意に特定される前記属性値が格納されている属性値配列を作成する機能を前記コンピュータさらに実現させるための請求項１３に記載のプログラム。
【請求項１５】
前記複数のテーブルが部品の親子関係を表現するストラクチャー型部品表であり、
最上位階層のテーブルとして、前記ツリー構造データのルートノードに対応する部品を選択し、その他の階層のテーブルとして同一の前記ストラクチャー型部品表を利用する機能を前記コンピュータにさらに実現させるための請求項１３又は１４に記載のプログラム。
【請求項１６】
前記マッチングキーとして、前記親側のテーブルにおけるデータの出現順に割り当てられた順序番号と、前記子側のテーブルにおけるデータに対応する親側のデータに割り当てられた順序番号との対を利用する機能を前記コンピュータにさらに実現させるための請求項１３又は１４に記載のプログラム。
【請求項１７】
請求項１３乃至１６のうちの何れか１項に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１８】
階層構造を有する複数のテーブルを記憶するメモリを備え、前記複数のテーブルを各ノードが属性名及び属性値によって表現される複数のノードからなるツリー構造データに変換し前記メモリに格納するコンピュータに、
前記複数のテーブルを階層毎にマッチングキーによってマッチングさせる機能と、
前記複数のテーブルの階層毎に、マッチングした親側のテーブルと子側のテーブルとの間で、親子関係がある行番号同士の行番号対応表を作成する機能と、
前記行番号対応表から親子関係がある前記親側のテーブル中の行番号及び前記子側のテーブル中の行番号を探索する機能と、
探索によって見つけられた順に、前記子側のテーブル中の行に割り当てられるレコード順序番号を決定する機能と、
前記ツリー構造データが、各レコードがレコードの並び順を表す前記レコード順序番号によって識別される、仮想的なレコードの配列として前記メモリに構築されるように、前記仮想的なレコードの配列中の前記レコード順序番号によって識別される位置に、親子関係フィールド値として前記子側のテーブル中の行に対応するノードの親ノードのレコード順序番号を格納し、前記ノードの属性名フィールド値として前記子側のテーブル中の行に属する項目名を格納し、前記ノードの属性値フィールド値として前記子側のテーブル中の行に属する項目値を格納する機能と、
を実現させるためのプログラムプロダクト。
【請求項１９】
各ノードが属性名及び属性値によって表現される複数のノードからなるツリー構造データを記録したコンピュータ読み取り可能な記録媒体であって、
前記ツリー構造データは、各レコードがレコードの並び順を表すレコード順序番号によって識別される、仮想的なレコードの配列によって表現され、
レコードは、前記レコードに対応するノードの親ノードのレコード順序番号を格納する親子関係フィールドと、前記ノードに属する属性名を指定する属性名番号を格納する属性名フィールドと、前記ノードに属する属性値を指定する属性値番号を格納する属性値フィールドとを含み、
前記ノードの親ノードが前記ノードに対応する前記レコードに含まれる前記親子関係フィールドに格納されている前記レコード順序番号によって特定され、
前記ノードに属する属性名が前記ノードに対応する前記レコードに含まれる前記属性名番号と前記属性名が前記属性名番号の順番に格納されている属性名配列とによって特定され、
前記ノードに属する属性値が前記ノードに対応する前記レコードに含まれる前記属性値番号と前記属性値が前記属性名番号の順番に格納されている属性値配列とによって特定される、
コンピュータ読み取り可能な記録媒体。
【請求項２０】
前記レコード順序番号は、深さ優先探索又は幅優先探索の順で前記複数のノードのうちの各ノードに対応する前記レコードに割り当てられている、請求項１９に記載のコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、表形式データからツリー構造データを構築する方法及び装置に係わり、特に、各ノードが属性名及び属性値によって表現される複数のノードからなるツリー構造データを、各レコードがレコードの並び順を表すレコード順序番号によって識別される仮想的なレコードの配列として、記憶装置上に構築する方法及び装置に関係する。【０００２】
本発明は、表構造の原データを記憶するメモリを備え、上記原データを各ノードが属性名及び属性値によって表現される複数のノードからなるツリー構造データに変換し上記メモリに格納する装置にも関係する。【０００３】
さらに、本発明は、コンピュータに上記方法を実行させるためのプログラム、プログラムプロダクト、及び、プログラムを記録した記録媒体に関係する。【０００４】
さらに、本発明は、各ノードが属性名及び属性値によって表現される複数のノードからなるツリー構造データが、各レコードがレコードの並び順を表す上記レコード順序番号によって識別される、仮想的なレコードの配列として記録された記録媒体に関係する。
【背景技術】
【０００５】
現在最も普及しているデータベースマネージメントシステム（ＤＢＭＳ）はリレーショナルデータベース（ＲＤＢ）である。ＲＤＢは表形式データベースであるため、ツリー構造データの取り扱いを苦手としていることがよく知られている。【０００６】
また、一般に、表形式データからツリー構造データを抽出（又は解釈）する作業は非常に厄介である。たとえば、対象とする表のレコードが、最上位項目から最下位項目までの複数個の項目により定義されている場合を考える。このとき、表形式データからツリー構造データを解釈するためには、
（１）最上位項目に同じ項目値を有するレコードをグループ分けし、
（２）上位項目に関して同じグループに分類されたレコードを、現在項目に関して同じ項目値を有するレコード毎にグループ分けし、
（３）現在項目が最下位項目に達するまで（２）を繰り返す、
という操作が必要である。この操作は、表形式データがｎ行ｍ列（レコード数＝ｎ、項目数＝ｍ）であるならば、Ｏ（ｎ＊ｍ）回の比較演算を必要とする。また、同じ項目名が多数回出現し、かつ、同じ項目値が多数回出現するので、これらの情報を記憶するために多量のメモリが必要である。さらに、同じ項目値が多数回出現するので、データ更新時に多数個の値を書き換えなければならない。【０００７】
そこで、ツリー構造データを階層化された複数個の表形式データで記述する種々の手法が提案されている。【０００８】
第一に、一般的に木構造を持つ拡張マークアップ言語（ＸＭＬ）データをＲＤＢに関連付けることは困難であるが、ＸＭＬデータの持つ自由度や柔軟性を大きく阻害することなく、ＸＭＬデータを表形式のデータ構造で表現する技術が提案されている（特許文献１）。特許文献１に記載されている技術では、ＸＭＬデータは、ルートエレメントから順にたどって各テーブルに格納され、格納されたデータには出現順序情報を付与される。各テーブルには、出現順序情報を含むダウングリップカラムと、格納されたデータと親子関係にある親データのダウングリップカラムの出現順序情報が割り当てられたアップグリップカラムとが作成されている。さらに、各テーブルには、ルートエレメントからの階層の深さを表すレベル値を格納するレベルカラムが作成されている。しかし、この技術では、ＸＭＬデータのスキーマ情報に基づいてデータの単位となるエレメント毎に１つのテーブルが作成され、テーブルにスキーマ情報に従ったデータが格納される。【０００９】
第二に、項目に属する項目値を含むレコードの配列として表現される複数の表形式データを結合し、深さの浅い表形式データのレコードから深さの深い表形式データのレコードまでを順次特定し、これにより、深さと、レコードを示す値とからなるツリー記述テーブルを作成することにより、ツリー構造データを複数の表形式データへ変換する技術も提案されている（特許文献２）。この例でも、深さ毎に１つの表形式データが存在している。【００１０】
特許文献１又は特許文献２において取り扱われている表形式データは、ツリー構造データに変換することが意図されたデータである。たとえば、特許文献１では、ダウングリップカラム及びアップグリップカラムがテーブルの中に存在している。これに対して、近年、生産管理システムやトレーサビリティシステムで使用されている部品表と呼ばれるＢＯＭ（Ｂｉｌｌ  ｏｆ  Ｍａｔｅｒｉａｌｓ）は、本来、ツリー構造データに変換されることが予定されていないが、データを分析したり、データを理解したりするとき、部品表をツリーデータ構造に展開すること（ＢＯＭ展開）が必要とされる。たとえば、ストラクチャー型部品表では親部品図番と子部品図番の対が１つのデータとして格納されている。たとえば、親部品Ａに子部品Ｂ１、Ｂ２及びＢ３が存在する場合、（Ａ，Ｂ１）、（Ａ，Ｂ２）及び（Ａ，Ｂ３）の３組の対がストラクチャー型部品表に格納されている。さらに、子部品Ｂ１がＣ１及びＣ２という子部品を含むならば、（Ｂ１，Ｃ１）及び（Ｂ１，Ｃ２）という２組の対もまたストラクチャー型部品表に格納されている。
【特許文献１】特開２００４−１７８０８４号公報
【特許文献２】国際公開第２００４／０３８６１２号公報
【特許文献３】国際公開第２００５／０８８４７９号公報
【特許文献４】国際公開第００／１０１０３号公報
【特許文献５】国際公開第０３／０４０９６０号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
特許文献１に記載されている従来技術では、予めどのようなデータ構造が存在するかをスキャンによって、又は、文書型定義（ＤＴＤ）のような定義によって知った上で、データを格納する格納先テーブルを作成する必要がある。よって、様々なデータ構造が現場で生成されるエディタなどの用途には、性能の面で不適当である。【００１２】
また、特許文献１又は特許文献２に記載されているような、ツリー構造データを複数個の階層化された表形式データで記述する従来のデータ表現形式は、１個の表形式データで記述する手法より、比較演算回数が削減され、メモリ使用量が削減されているが、任意のトポロジーをもつツリーを追加することが困難であり、データ編集の自由度が低い。【００１３】
よって、ツリー構造データを記述するデータ表現形式は、データ構造の動的な変化に対応可能であり、高い編集の自由度を有することが好ましい。【００１４】
ツリー構造データは、それ自体を解釈するための比較操作が削減され、それ自体を格納するためのメモリ使用量が削減され、ツリー構造の更新時に書き換えるべきデータ量が削減され、事前のデータ構造の定義を不要とすることが好ましい。
【課題を解決するための手段】
【００１５】
本発明の一実施例によれば、各ノードが属性名及び属性値によって表現される複数のノードからなるツリー構造データを各レコードがレコードの並び順を表すレコード順序番号によって識別される仮想的なレコードの配列として記憶装置上に構築する装置であって、
階層構造を有する複数のテーブルを階層毎にマッチングキーによってマッチングさせ、親側のテーブルと子側のテーブルとの間で親子関係がある行番号同士の行番号対応表を作成する手段と、
上記行番号対応表から親子関係がある上記親側のテーブル中の行番号及び上記子側のテーブル中の行番号を探索する手段と、
上記探索する手段によって見つけられた順に、上記子側のテーブル中の行に割り当てられるレコード順序番号を決定し、上記仮想的なレコードの配列中の上記レコード順序番号によって識別される位置に、親子関係フィールド値として上記子側のテーブル中の行に対応するノードの親ノードのレコード順序番号を格納し、上記ノードの属性名フィールド値として上記子側のテーブル中の行に属する項目名を格納し、上記ノードの属性値フィールド値として上記子側のテーブル中の行に属する項目値を格納する手段と、
を備える装置が提供される。【００１６】
一実施例では、1個のレコードは1個のノードに対応していてもよい。階層構造を有する複数のテーブルは、ツリー構造データに展開されるべき表構造の原データである。また、マッチングキーはジョインキーでよい。ジョインキーを用いるマッチング、すなわち、ジョインは、原データからジョインテーブル、すなわち、中間データを生成する。ジョインテーブルは、親子関係にある原データ自体と、親子関係にある原データ間の結合関係を表現するようなテーブルである。【００１７】
本発明の一実施例によれば、上記装置は、上記ノードの属性名フィールド値が上記レコード順序番号の順番に格納されている配列から、上記レコード順序番号の順に上記属性名を一意に特定する属性名番号が格納されている属性名番号配列、上記属性名番号配列の要素の順番に上記属性名番号によって一意に特定される上記属性名が格納されている属性名配列、上記レコード順序番号の順に上記属性値を一意に特定する属性値番号が格納されている属性値番号配列、及び、上記属性値番号配列の要素の順番に上記属性値番号によって一意に特定される上記属性値が格納されている属性値配列を作成する手段をさらに備える。【００１８】
本発明の一実施例によれば、上記複数のテーブルが部品の親子関係を表現するストラクチャー型部品表であり、上記行番号対応表を作成する手段が、最上位階層のテーブルとして、上記ツリー構造データのルートノードに対応する部品を選択し、その他の階層のデータとして同一の上記ストラクチャー型部品表を利用する。【００１９】
本発明の一実施例によれば、上記行番号対応表を作成する手段が、上記マッチングキーとして、上記親側のテーブルにおけるデータの出現順に割り当てられた順序番号と、上記子側のテーブルにおけるデータに対応する親側のデータに割り当てられた順序番号との対を利用する。【００２０】
本発明の一実施例によれば、階層構造を有する複数のテーブルを記憶するメモリを備え、上記複数のテーブルを各ノードが属性名及び属性値によって表現される複数のノードからなるツリー構造データに変換し上記メモリに格納する装置であって、
上記複数のテーブルを階層毎にマッチングキーによってマッチングさせるマッチング部と、
上記複数のテーブルの階層毎にマッチングした親側のテーブルと子側のテーブルとの間で親子関係がある行番号同士の行番号対応表を作成する対応表作成部と、
上記行番号対応表から親子関係がある上記親側のテーブル中の行番号及び上記子側のテーブル中の行番号を探索する探索部と、
上記探索部によって見つけられた順に、上記子側のテーブル中の行に割り当てられるレコード順序番号を決定し、上記仮想的なレコードの配列中の上記レコード順序番号によって識別される位置に、親子関係フィールド値として上記子側のテーブル中の行に対応するノードの親ノードのレコード順序番号を格納し、上記ノードの属性名フィールド値として上記子側のテーブル中の行に属する項目名を格納し、上記ノードの属性値フィールド値として上記子側のテーブル中の行に属する上記原データに属する項目値を格納するレコード生成部と、
を備え、
上記ツリー構造データが、各レコードがレコードの並び順を表す上記レコード順序番号によって識別される、仮想的なレコードの配列として上記メモリに構築される装置が提供される。【００２１】
本発明の一実施例によれば、上記装置は、上記ノードの属性名フィールド値が上記レコード順序番号の順番に格納されている配列から、上記レコード順序番号の順に上記属性名を一意に特定する属性名番号が格納されている属性名番号配列、上記属性名番号配列の要素の順番に上記属性名番号によって一意に特定される上記属性名が格納されている属性名配列、上記レコード順序番号の順に上記属性値を一意に特定する属性値番号が格納されている属性値番号配列、及び、上記属性値番号配列の要素の順番に上記属性値番号によって一意に特定される上記属性値が格納されている属性値配列を作成する値分離部をさらに備える。【００２２】
本発明の一実施例によれば、上記複数のテーブルが部品の親子関係を表現するストラクチャー型部品表であり、上記対応表作成部が、最上位階層の表構造の中間データとして、上記ツリー構造データのルートノードに対応する部品を選択し、その他の表構造の中間データとして同一の上記ストラクチャー型部品表を利用する。【００２３】
本発明の一実施例によれば、上記対応表作成部が、上記マッチングキーとして、上記親側のテーブルにおけるデータの出現順に割り当てられた順序番号と、上記子側のテーブルにおけるデータに対応する親側のデータに割り当てられた順序番号との対を利用する。【００２４】
本発明の一実施例によれば、各ノードが属性名及び属性値によって表現される複数のノードからなるツリー構造データを各レコードがレコードの並び順を表すレコード順序番号によって識別される仮想的なレコードの配列として記憶装置上に構築する方法であって、
階層構造を有する複数のテーブルを階層毎にマッチングキーによってマッチングさせ、親側のテーブルと子側のテーブルとの間で親子関係がある行番号同士の行番号対応表を作成するステップと、
上記行番号対応表から親子関係がある上記親側のテーブル中の行番号及び上記子側のテーブル中の行番号を探索し、探索によって見つけられた順に、上記子側のテーブル中の行に割り当てられるレコード順序番号を決定し、上記仮想的なレコードの配列中の上記レコード順序番号によって識別される位置に、親子関係フィールド値として上記子側のテーブル中の行に対応するノードの親ノードのレコード順序番号を格納し、上記ノードの属性名フィールド値として上記子側のテーブル中の行に属する項目名を格納し、上記ノードの属性値フィールド値として上記子側のテーブル中の行に属する項目値を格納するステップと、
を備える方法が提供される。【００２５】
本発明の一実施例によれば、上記方法は、上記ノードの属性名フィールド値が上記レコード順序番号の順番に格納されている配列から、上記レコード順序番号の順に上記属性名を一意に特定する属性名番号が格納されている属性名番号配列、上記属性名番号配列の要素の順番に上記属性名番号によって一意に特定される上記属性名が格納されている属性名配列、上記レコード順序番号の順に上記属性値を一意に特定する属性値番号が格納されている属性値番号配列、及び、上記属性値番号配列の要素の順番に上記属性値番号によって一意に特定される上記属性値が格納されている属性値配列を作成するステップをさらに備える。【００２６】
本発明の一実施例によれば、上記複数のテーブルが部品の親子関係を表現するストラクチャー型部品表であり、上記行番号対応表を作成するステップにおいて、最上位階層のテーブルとして、上記ツリー構造データのルートノードに対応する部品を選択し、その他の階層のテーブルとして同一の上記ストラクチャー型部品表を利用する。【００２７】
本発明の一実施例によれば、上記行番号対応表を作成するステップにおいて、上記マッチングキーとして、上記親側のテーブルにおけるデータの出現順に割り当てられた順序番号と、上記子側のテーブルにおけるデータに対応する親側のデータに割り当てられた順序番号との対を利用する。【００２８】
本発明の一実施例によれば、階層構造を有する複数のテーブルを記憶するメモリを備え、上記複数のテーブルを各ノードが属性名及び属性値によって表現される複数のノードからなるツリー構造データに変換し上記メモリに格納するコンピュータに、
上記複数のテーブルを階層毎にマッチングキーによってマッチングさせる機能と、
上記複数のテーブルの階層毎に、マッチングした親側のテーブルと子側のテーブルとの間で、親子関係がある行番号同士の行番号対応表を作成する機能と、
上記行番号対応表から親子関係がある上記親側のテーブル中の行番号及び上記子側のテーブル中の行番号を探索する機能と、
探索によって見つけられた順に、上記子側のテーブル中の行に割り当てられる上記レコード順序番号を決定する機能と、
上記ツリー構造データが、各レコードがレコードの並び順を表す上記レコード順序番号によって識別される、仮想的なレコードの配列として上記メモリに構築されるように、上記仮想的なレコードの配列中の上記レコード順序番号によって識別される位置に、親子関係フィールド値として上記子側のテーブル中の行に対応するノードの親ノードのレコード順序番号を格納し、上記ノードの属性名フィールド値として上記子側のテーブル中の行に属する項目名を格納し、上記ノードの属性値フィールド値として上記子側のテーブル中の行に属する項目値を格納する機能と、
を実現させるためのプログラムが提供される。【００２９】
本発明の一実施例によれば、上記プログラムは、上記ノードの属性名フィールド値が上記レコード順序番号の順番に格納されている配列から、上記レコード順序番号の順に上記属性名を一意に特定する属性名番号が格納されている属性名番号配列、上記属性名番号配列の要素の順番に上記属性名番号によって一意に特定される上記属性名が格納されている属性名配列、上記レコード順序番号の順に上記属性値を一意に特定する属性値番号が格納されている属性値番号配列、及び、上記属性値番号配列の要素の順番に上記属性値番号によって一意に特定される上記属性値が格納されている属性値配列を作成する機能を上記コンピュータさらに実現させる。【００３０】
本発明の一実施例によれば、上記複数のテーブルが部品の親子関係を表現するストラクチャー型部品表であり、上記プログラムは、最上位階層のテーブルとして、上記ツリー構造データのルートノードに対応する部品を選択し、その他の階層のテーブルとして同一の上記ストラクチャー型部品表を利用する機能を上記コンピュータにさらに実現させる。【００３１】
本発明の一実施例によれば、上記プログラムは、上記マッチングキーとして、上記親側のテーブルにおけるデータの出現順に割り当てられた順序番号と、上記子側のテーブルにおけるデータに対応する親側のデータに割り当てられた順序番号との対を利用する機能を上記コンピュータにさらに実現させる。【００３２】
本発明の一実施例によれば、上記プログラムを記録したコンピュータ読み取り可能な記録媒体が提供される。【００３３】
本発明の一実施例によれば、階層構造を有する複数のテーブルを記憶するメモリを備え、上記複数のテーブルを各ノードが属性名及び属性値によって表現される複数のノードからなるツリー構造データに変換し上記メモリに格納するコンピュータに、
上記複数のテーブルを階層毎にマッチングキーによってマッチングさせる機能と、
上記複数のテーブルの階層毎に、マッチングした親側のテーブルと子側のテーブルとの間で、親子関係がある行番号同士の行番号対応表を作成する機能と、
上記行番号対応表から親子関係がある上記親側のテーブル中の行番号及び上記子側のテーブル中の行番号を探索する機能と、
探索によって見つけられた順に、上記子側のテーブル中の行に割り当てられるレコード順序番号を決定する機能と、
上記ツリー構造データが、各レコードがレコードの並び順を表す上記レコード順序番号によって識別される、仮想的なレコードの配列として上記メモリに構築されるように、上記仮想的なレコードの配列中の上記レコード順序番号によって識別される位置に、親子関係フィールド値として上記子側のテーブル中の行に対応するノードの親ノードのレコード順序番号を格納し、上記ノードの属性名フィールド値として上記子側のテーブル中の行に属する項目名を格納し、上記ノードの属性値フィールド値として上記子側のテーブル中の行に属する項目値を格納する機能と、
を実現させるためのプログラムプロダクトが提供される。【００３４】
本発明の一実施例によれば、各ノードが属性名及び属性値によって表現される複数のノードからなるツリー構造データを記録したコンピュータ読み取り可能な記録媒体であって、
上記ツリー構造データは、各レコードがレコードの並び順を表すレコード順序番号によって識別される、仮想的なレコードの配列によって表現され、
レコードは、上記レコードに対応するノードの親ノードのレコード順序番号を格納する親子関係フィールドと、上記ノードに属する属性名を指定する属性名番号を格納する属性名フィールドと、上記ノードに属する属性値を指定する属性値番号を格納する属性値フィールドとを含み、
上記ノードの親ノードが上記ノードに対応する上記レコードに含まれる上記親子関係フィールドに格納されている上記レコード順序番号によって特定され、
上記ノードに属する属性名が上記ノードに対応する上記レコードに含まれる上記属性名番号と上記属性名が上記属性名番号の順番に格納されている属性名配列とによって特定され、
上記ノードに属する属性値が上記ノードに対応する上記レコードに含まれる上記属性値番号と上記属性値が上記属性名番号の順番に格納されている属性値配列とによって特定される、
コンピュータ読み取り可能な記録媒体が提供される。【００３５】
本発明の一実施例によれば、上記レコード順序番号は、深さ優先探索又は幅優先探索の順で上記複数のノードのうちの各ノードに対応する上記レコードに割り当てられている。
【発明の効果】
【００３６】
本発明の少なくとも1つの実施例によれば、ツリー構造データを解釈するための比較操作が削減され、メモリ使用量が削減され、ツリー構造の更新時に書き換えるべきデータ量が削減され、事前のデータ構造の定義を不要とするようなツリー構造データの構築が可能になる。
【図面の簡単な説明】
【００３７】
【図１】図１は、本発明の一実施形態によるツリー構造データを処理するコンピュータシステムのハードウェア構成を示すブロック図である。
【図２】図２は、ツリー構造データの例におけるノードの階層関係を示す図である。
【図３】図３Ａは、本発明の一実施形態によるツリー構造データを記述する深さ優先によるデータ表現形式の説明図である。図３Ｂは、本発明の一実施形態によるツリー構造データを記述する幅優先によるデータ表現形式の説明図である。
【図４】図４Ａは、本発明の一実施形態によるツリー構造データを記述する値が分離されたデータ表現形式の説明図である。図４Ｂは、本発明の一実施形態によるツリー構造データを記述する情報ブロック型のデータ表現形式の説明図である。
【図５】図５は、情報ブロックに基づくデータ管理機構を説明するための表形式データの一例を表す図である。
【図６】図６は、情報ブロック型のデータ表現形式の説明図である。
【図７】図７は、ストラクチャー型部品表の一例の説明図である。
【図８】図８は、ストラクチャー型部品表に埋め込まれている階層関係を示す図である。
【図９】図９は、ストラクチャー型部品表から作成された中間データと中間データ間のレコードの対応関係を示す図である。
【図１０】図１０Ａは、ストラクチャー型部品表から生成された深さ優先形式によるツリー構造データの一例の説明図である。図１０Ｂは、ストラクチャー型部品表から生成された幅優先形式によるツリー構造データの一例の説明図である。
【図１１】図１１Ａは、ストラクチャー型部品表から生成された深さ優先形式によるツリー構造データ（情報ブロック型）の一例の説明図である。図１１Ｂは、ストラクチャー型部品表から生成された幅優先形式によるツリー構造データ（情報ブロック型）の一例の説明図である。
【図１２】図１２Ａは、ツリー構造データを記述する複数のテーブルの一例の説明図である。図１２Ｂは、複数のテーブルで記述されたツリー構造データの階層関係を示す図である。
【図１３】図１３Ａは、本発明の一実施形態によるレコード番号対応表の作成処理の説明図である。図１３Ｂは、本発明の一実施形態によるレコード番号対応表の作成処理の説明図である。
【図１４】図１４Ａは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。図１４Ｂは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。図１４Ｃは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。
【図１５】図１５Ａは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。図１５Ｂは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。図１５Ｃは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。
【図１６】図１６Ａは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。図１６Ｂは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。図１６Ｃは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。
【図１７】図１７Ａは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。図１７Ｂは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。図１７Ｃは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。
【図１８】図１８Ａは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。図１８Ｂは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。図１８Ｃは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。
【図１９】図１９Ａは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。図１９Ｂは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。図１９Ｃは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。
【図２０】図２０Ａは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。図２０Ｂは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。図２０Ｃは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図である。
【図２１】図２１Ａは、統合されたツリー構造データを示す図である。図２１Ｂは、値リストが分離されたツリー構造データを示す図である。図２１Ｃは、情報ブロック型のツリー構造データを示す図である。
【図２２】図２２は、本発明の一実施形態による情報ブロックに基づくデータ形式への変換処理の説明図である。
【図２３】図２３は、本発明の一実施形態による値リストの共通化処理の説明図である。
【図２４】図２４は、本発明の一実施形態による項目値のリストを値番号と値リストに分離する処理の説明図である。
【図２５】図２５Ａは、本発明の一実施形態によるジョインを利用するレコード番号対応表の作成処理の説明図である。図２５Ｂは、本発明の一実施形態によるジョインを利用するレコード番号対応表の作成処理の説明図である。
【図２６】図２６Ａは、本発明の一実施例によるジョインを利用するレコード番号対応表の作成処理の説明図である。図２６Ｂは、本発明の一実施例によるジョインを利用するレコード番号対応表の作成処理の説明図である。
【図２７】図２７は、本発明の一実施形態によるツリー構造データの生成処理を適用した結果の説明図である。
【図２８】図２８は、本発明の他の実施形態によるツリー構造データの生成処理を適用した結果の説明図である。
【図２９】図２９は、本発明の一実施形態による幅優先方式のツリー構造データ生成処理の説明図である。
【図３０】図３０は、本発明の一実施形態による幅優先方式のツリー構造データ生成処理の説明図である。
【図３１】図３１は、本発明の一実施形態による幅優先方式のツリー構造データ生成処理の説明図である。
【図３２】図３２は、本発明の一実施形態による幅優先方式のツリー構造データ生成処理の説明図である。
【図３３】図３３は、本発明の一実施形態による幅優先方式のツリー構造データ生成処理の説明図である。
【図３４】図３４は、本発明の一実施形態による幅優先方式のツリー構造データ生成処理の説明図である。
【図３５】図３５は、本発明の一実施形態による幅優先方式のツリー構造データ生成処理を用いて生成された情報ブロック型ツリー構造データの説明図である。
【図３６】図３６は、本発明の一実施形態によるツリー構造データの生成処理を適用した結果の説明図である。
【図３７】図３７は、本発明の他の実施形態によるツリー構造データの生成処理を適用した結果の説明図である。
【符号の説明】
【００３８】
１０      コンピュータシステム
１２      ＣＰＵ
１４      ＲＡＭ
１６      ＲＯＭ
１８      ハードディスク
１９      ＣＤ−ＲＯＭ
２０      ＣＤ−ＲＯＭドライバ
２２      インタフェース
２４      入力装置
２６      表示装置
２８      バス
【発明を実施するための最良の形態】
【００３９】
以下、本発明を実施するための種々の形態を図面と共に詳細に説明する。【００４０】
［コンピュータシステム構成］
図１は、本発明の一実施形態によるツリー構造データを処理するコンピュータシステムのハードウェア構成を示すブロック図である。図１に示すように、このコンピュータシステム１０は、通常のコンピュータシステムと同様の構成であり、プログラムを実行することによりシステム全体および個々の構成部分を制御するＣＰＵ１２と、ワークデータなどを記憶するＲＡＭ(Random Access Memory)１４と、プログラム等を記憶するＲＯＭ(Read Only Memory)１６と、ハードディスク等の固定記憶装置１８と、ＣＤ−ＲＯＭ１９を駆動するためのＣＤ−ＲＯＭドライバ２０と、ＣＤ−ＲＯＭドライバ２０や外部ネットワーク（図示せず）と接続された外部端子との間に設けられたインタフェース（Ｉ／Ｆ）２２と、キーボードやマウスからなる入力装置２４と、表示装置２６とを備えている。ＣＰＵ１２、ＲＡＭ１４、ＲＯＭ１６、外部記憶装置１８、Ｉ／Ｆ２２、入力装置２４および表示装置２６は、バス２８を介して相互に接続されている。【００４１】
本発明の一実施形態によるツリー構造データを処理するプログラムは、ＣＤ−ＲＯＭ１９に収容され、ＣＤ−ＲＯＭドライバ２０によって読取られても良く、或いは、ＲＯＭ１６に予め記憶されていても良い。また、いったんＣＤ−ＲＯＭ１９から読み出したものを、外部記憶装置１８の所定の領域に記憶しておいても良い。或いは、上記プログラムは、ネットワーク（図示せず）、外部端子およびＩ／Ｆ２２を経て外部から供給されるものであっても良い。【００４２】
また、本発明の一実施形態による情報処理装置は、コンピュータシステム１０にツリー構造データを処理するプログラムを実行させることにより実現される。【００４３】
なお、以下の説明では、特に断らない限り、本発明の種々の実施形態は、コンピュータシステムの環境で実施され、動作の主体は、プログラム命令等のソフトウェアを実行するＣＰＵ等のプロセッサ、専用ハードウェア、又は、ファームウェア、或いは、それらの組み合わせである。【００４４】
［ツリー構造データのデータ表現形式］
最初に、本発明の一実施形態によるツリー構造データのデータ表現形式を説明する。以下の説明では、一例として、ＸＭＬ形式では、
＜Ｓｔｏｒｙ＞Ｈａｒｒｙ  Ｐｏｔｔｅｒ
＜Ｆａｍｉｌｙ＞Ｐｏｔｔｅｒ
＜Ｎａｍｅ＞Ｊａｍｅｓ＜／Ｎａｍｅ＞
＜Ｎａｍｅ＞Ｌｉｌｙ＜／Ｎａｍｅ＞
＜Ｎａｍｅ＞Ｈａｒｒｙ＜／Ｎａｍｅ＞
＜／Ｆａｍｉｌｙ＞
＜Ｆａｍｉｌｙ＞Ｂｌａｃｋ
＜Ｎａｍｅ＞Ｓｉｒｉｕｓ＜／Ｎａｍｅ＞
＜／Ｆａｍｉｌｙ＞
＜／Ｓｔｏｒｙ＞
と記述されるツリー構造データの例を考える。このＸＭＬテキストの１行目は、属性名＝Ｓｔｏｒｙと属性値＝Ｈａｒｒｙ  Ｐｏｔｔｅｒとからなる属性を定義している。２行目は、属性名＝Ｆａｍｉｌｙと属性値＝Ｐｏｔｔｅｒとからなる属性を定義している。【００４５】
図２はこのツリー構造データの例におけるノードの階層関係を示す図である。同図によれば、ルートノードは、属性名：属性値＝Ｓｔｏｒｙ：Ｈａｒｒｙ  Ｐｏｔｔｅｒという属性を保有するノードであり、ルートノードには、Ｆａｍｉｌｙ：Ｐｏｔｔｅｒという属性を保有する子ノードと、Ｆａｍｉｌｙ：Ｂｌａｃｋという属性を保有する子ノードとが存在することがわかる。さらに、ノードＦａｍｉｌｙ：Ｐｏｔｔｅｒには、子ノードＮａｍｅ：Ｊａｍｅｓと、子ノードＮａｍｅ：Ｌｉｌｙと、子ノードＮａｍｅ：Ｈａｒｒｙとが存在する。一方、ノードＦａｍｉｌｙ：Ｂｌａｃｋには、子ノードＮａｍｅ：Ｓｉｒｉｕｓが存在する。ここで、ノードは、ノード属性名：属性値という表記によって指定されている。【００４６】
図３は、本発明の一実施形態によるツリー構造データを記述するデータ表現形式の説明図である。特に、図３Ａは、図２に示されたツリー構造データの例における深さ優先でのデータ表現形式を示し、図３Ｂは幅優先でのデータ表現形式を示している。【００４７】
ここで、深さ優先方式と幅優先方式について簡単に説明する。たとえば、図２のツリー構造データのノードをルートノードから順番に深さ優先方式で探索し、見つけられた順番にノードにノード識別子を付与する場合を考える。このとき、各ノードに付与されるノード識別子は、ルートノードのノード識別子を０とすると、
ノードＳｔｏｒｙ：Ｈａｒｒｙ  Ｐｏｔｔｅｒのノード識別子＝０
ノードＦａｍｉｌｙ：Ｐｏｔｔｅｒのノード識別子＝１
ノードＮａｍｅ：Ｊａｍｅｓのノード識別子＝２
ノードＮａｍｅ：Ｌｉｌｙのノード識別子＝３
ノードＮａｍｅ：Ｈａｒｒｙのノード識別子＝４
ノードＦａｍｉｌｙ：Ｂｌａｃｋのノード識別子＝５
ノードＮａｍｅ：Ｓｉｒｉｕｓのノード識別子＝６
となる。一方、図２のツリー構造データのノードを幅優先方式で探索し、同様に、ノードにノード識別子を付与すると、
ノードＳｔｏｒｙ：Ｈａｒｒｙ  Ｐｏｔｔｅｒのノード識別子＝０
ノードＦａｍｉｌｙ：Ｐｏｔｔｅｒのノード識別子＝１
ノードＮａｍｅ：Ｊａｍｅｓのノード識別子＝３
ノードＮａｍｅ：Ｌｉｌｙのノード識別子＝４
ノードＮａｍｅ：Ｈａｒｒｙのノード識別子＝５
ノードＦａｍｉｌｙ：Ｂｌａｃｋのノード識別子＝２
ノードＮａｍｅ：Ｓｉｒｉｕｓのノード識別子＝６
となる。すなわち、深さ優先探索とは、同じ世代のノードより子ノードを優先するノード探索を表し、幅優先探索とは、子ノードより同じ世代のノードを優先するノード検索を表している。このようなツリー構造データの記述法は特許文献３に記載されている。【００４８】
ここで、本明細書中での配列の記法について説明する。一般に、配列Ａは、添字をｉとすると、配列の要素がＡ［ｉ］のように表記できるが、図面中では、配列は、配列の要素Ａ［ｉ］は、実線で囲まれた領域内に示され、要素Ａ［ｉ］と要素Ａ［ｉ＋１］の境界は点線で示されている。また、要素Ａ［ｉ］の添字ｉが要素Ａ［ｉ］の左側に示されている。また、配列の添字ｉは０から始まる整数で表されている。【００４９】
図３Ａ、Ｂを再び参照すると、ツリー構造データは、１個のレコードが１個のノードに対応し、各レコードがレコードの並び順を表すレコード順序番号によって識別される、レコードの配列によって表現されている。なお、ノードとレコードが１対１で対応しているので、レコード順序番号は上述のノード識別子と一致している。【００５０】
レコードは、レコードに対応するノードの親ノードのレコード順序番号を格納する親子関係フィールドＴｏｐｏｌｏｇｙと、当該ノードに属する属性名を指定する属性名フィールドＴｉｔｌｅと、当該ノードに属する属性値を指定する属性値フィールドＶａｌｕｅとを含む。たとえば、レコード順序番号＝ｉであるレコードＲｅｃｏｒｄ［ｉ］の各フィールドの要素は、Ｔｏｐｏｌｏｇｙ［ｉ］、Ｔｉｔｌｅ［ｉ］及びＶａｌｕｅ［ｉ］によって表される。【００５１】
深さ優先による図３Ａの例では、レコード順序番号＝０のレコードの各フィールドの要素は、
Ｔｏｐｏｌｏｇｙ［０］＝−１
Ｔｉｔｌｅ［０］＝Ｓｔｏｒｙ
Ｖａｌｕｅ［０］＝Ｈａｒｒｙ  Ｐｏｔｔｅｒ
となる。親子関係フィールドＴｏｐｏｌｏｇｙに、レコード順序番号として存在しない値、たとえば、−１が格納されているレコードは、このレコードが親ノードの存在しないノードに対応していること示している。よって、レコード順序番号＝０のレコードはルートノードに対応し、ルートノードの属性名がＳｔｏｒｙであり、属性値がＨａｒｒｙ  Ｐｏｔｔｅｒであることもわかる。【００５２】
さらに、図３Ａの例において、レコード順序番号＝３のレコードの各フィールドの要素は、
Ｔｏｐｏｌｏｇｙ［３］＝１
Ｔｉｔｌｅ［３］＝Ｎａｍｅ
Ｖａｌｕｅ［３］＝Ｌｉｌｙ
である。よって、このレコードは、親ノードのレコード順序番号が１であるノードに対応し、かつ、ノードの属性名＝Ｎａｍｅ、ノードの属性値＝Ｌｉｌｙであることを示している。当該ノードの親ノードは、レコード順序番号＝１のレコードに対応するノード、すなわち、親ノードのレコード順序番号＝０、ノードの属性名＝Ｆａｍｉｌｙ、かつ、ノードの属性値＝Ｐｏｔｔｅｒを保有するノードであることがわかる。【００５３】
一方、幅優先による図３Ｂの例においても、たとえば、レコード順序番号＝６のレコードの各フィールドの要素は、
Ｔｏｐｏｌｏｇｙ［６］＝２
Ｔｉｔｌｅ［６］＝Ｎａｍｅ
Ｖａｌｕｅ［６］＝Ｓｉｒｉｕｓ
である。よって、このレコードは、親ノードのレコード順序番号が２であるノードに対応し、かつ、ノードの属性名＝Ｎａｍｅ、ノードの属性値＝Ｓｉｒｉｕｓであることを示している。当該ノードの親ノードは、レコード順序番号＝２のレコードに対応するノード、すなわち、親ノードのレコード順序番号＝０、ノードの属性名＝Ｆａｍｉｌｙ、かつ、ノードの属性値＝Ｂｌａｃｋを保有するノードであることがわかる。【００５４】
このように、本発明の一実施形態によるツリー構造データを記述するデータ表現形式は、１つの表に統合されているので、非常に操作性に優れ、新しいツリーの追加又はツリーの削除に柔軟に対応し、データ編集の自由度が高い。【００５５】
ここで、図３Ａ及び３Ｂに示されているツリー構造データを記述するレコードの配列は、メモリ等の記憶装置上にこのままの形式で、すなわち、配列Ｔｏｐｏｌｏｇｙ、配列Ｔｉｔｌｅ及び配列Ｖａｌｕｅとして記憶されている必要はなく、このレコードの配列を実質的に表現可能であればどのような表現でも構わない。このようにレコードの配列を等価的に表現できるデータは、本書中では、「仮想的な」レコードの配列と呼ばれることがある。【００５６】
たとえば、レコードは、当該レコードに対応するノードの親ノードのレコード順序番号を格納する親子関係フィールドと、当該ノードに属する属性名を指定する属性名番号を格納する属性名フィールドと、当該ノードに属する属性値を指定する属性値番号を格納する属性値フィールドとによって定義することができる。そして、当該ノードの親ノードが当該ノードに対応するレコードに含まれる親子関係フィールドに格納されているレコード順序番号によって特定され、当該ノードに属する属性名が当該ノードに対応するレコードに含まれる属性名番号と属性名が属性名番号の順番に格納されている属性名配列とによって特定され、当該ノードに属する属性値が当該ノードに対応するレコードに含まれる属性値番号と属性値が属性名番号の順番に格納されている属性値配列とによって特定されるように構成することが可能である。【００５７】
これは、属性名や属性値のような値を、値リストＶＬと値リストへのポインタ配列ＶＮｏとの組み合わせによって表現する考え方に基づいている。値リストＶＬと値リストへのポインタ配列との組み合わせは「情報ブロック」とも呼ばれ、特許文献４において提案されている概念である。【００５８】
図４Ａ、Ｂは、この情報ブロックの概念を導入することにより記憶装置上に構築された、本発明の一実施形態によるツリー構造データのデータ表現形式の説明図である。同図の例は、深さ優先方式に従っている。図４Ａは、属性名Ｔｉｔｌｅが属性名番号配列Ｔｉｔｌｅ＿ＶＮｏと属性名配列Ｔｉｔｌｅ＿ＶＬとに分離され、属性値Ｖａｌｕｅが属性値番号配列Ｖａｌｕｅ＿ＶＮｏと属性値配列Ｖａｌｕｅ＿ＶＬとに分離されたデータ表現形式の説明図であり、図４Ｂは図４Ａの表現形式に基づいて導出された情報ブロック型のデータ表現形式の説明図である。たとえば、レコード順序番号ｉを指定すると、親子関係フィールドの値は、Ｔｏｐｏｌｏｇｙ［ｉ］によって特定され、属性名は、Ｔｉｔｌｅ＿ＶＬ［Ｔｉｔｌｅ＿ＶＮｏ［ｉ］］によって特定され、属性値は、Ｖａｌｕｅ＿ＶＬ［Ｖａｌｕｅ＿ＶＮｏ［ｉ］］によって特定されることがわかるであろう。【００５９】
［情報ブロックに基づくデータ管理機構］
図４Ａ、Ｂのデータ表現形式がより良く理解されるように、情報ブロックに基づくデータ管理機構について簡単に説明する。【００６０】
図５は情報ブロックに基づくデータ管理機構を説明するための表形式データの一例を表す図である。この表形式データは、上述の特許文献４に提案されたデータ管理機構を用いることにより、コンピュータ内では図６に示されるようなデータ構造として、メモリ（たとえばＲＡＭ１４）に記憶される。このデータ構造は、市販されているコンピュータ、たとえば、パーソナルコンピュータのハードウェア資源、特に、プロセッサ及びメモリを使用して大規模な表形式データの検索、ソート、集計等を実現するために提案された、コンピュータのメモリ上に置かれる表形式データのデータ構造であることに注意すべきである。【００６１】
なお、「元の表形式データ中でレコードが収容されている位置を表す情報レコード番号（すなわち、原始レコード位置番号）」と「レコードの並び順を表す情報（すなわち、レコード順序番号）」とは明確に区別されるべきである。すべてのレコードには原始レコード位置番号が関連付けられている。この原始レコード位置番号は、データ項目に対応した項目値を含む個々のレコードを特定するために利用される仮想的な情報である。一般に、表形式データは、レコードが常に原始レコード位置番号の順番に配列されているとは限らない。たとえば、元の表形式データをある項目の項目値に関して昇順にソートすると、得られる表形式データのレコードの並び順は元の表形式データのレコードの並び順とは異なる。但し、元々の表形式データ中のレコードは、レコードが原始レコード位置番号の順番に並べられていることがあり、この場合には、原始レコード位置番号とレコード順序番号とが初期的に一致している。【００６２】
図６に示すように、表形式データの各レコードの並び順の番号（レコード順序番号）と、原始レコード位置番号は、レコード順序指定配列６０１（以下、この配列を「ＯｒｄＳｅｔ」のように略記する。）によって対応付けられる。レコード順序指定配列６０１は、レコード順序番号の順に原始レコード位置番号を格納している。図６の例では、レコードは原始レコード位置番号の順番に並べられている。【００６３】
図６を参照すると、性別に関しては、表形式データのレコード順序番号＝０に対応する原始レコード位置番号は、配列ＯｒｄＳｅｔ［０］から「０」であることがわかる。原始レコード位置番号が「０」であるレコードに関する実際の性別の値、即ち、「男」又は「女」は、実際の値が所定の順序（たとえば、昇順又は降順）に従ってソートされた値リストである項目値配列６０３（以下、項目値配列、すなわち、値リストを「ＶＬ」のように略記する。）へのポインタ配列である項目値番号配列６０２（以下、項目値番号配列、すなわち、ポインタ配列を「ＶＮｏ」のように略記する。）を参照することによって取得できる。ポインタ配列６０２は、配列ＯｒｄＳｅｔ６０１に格納されている原始レコード位置番号の順番に従って、実際の値リスト６０３中の要素を指し示すポインタを格納している。これにより、表形式データのレコード「０」に対応する性別の項目値は、（１）配列ＯｒｄＳｅｔ６０１からレコード順序番号＝０に対応する原始レコード位置番号＝０を取り出し、（２）値リストへのポインタ配列６０２から原始レコード位置番号＝０に対応する要素「１」を取り出し、（３）値リスト６０３から、値リストへのポインタ配列６０２から取り出された要素「１」によって指し示される要素「女」を取り出すことにより取得できる。【００６４】
他のレコードに対しても、また、年齢及び身長に関しても同様に項目値を取得することができる。【００６５】
このように表形式データは、値リストＶＬと、値リストへのポインタ配列ＶＮｏの組合せにより表現され、この組合せを、特に、「情報ブロック」と称する。図６には、性別、年齢及び身長に関する情報ブロックがそれぞれ情報ブロック６０８、６０９及び６１０として示されている。【００６６】
単一のコンピュータが単一のメモリ（物理的には複数であっても良いが、単一のアドレス空間に配置されアクセスされるという意味で単一のメモリ）を有するならば、単一のコンピュータは、当該メモリに、順序集合の配列ＯｒｄＳｅｔ、各情報ブロックを構成する値リストＶＬおよびポインタ配列ＶＮｏとを記憶しておけばよい。しかしながら、本発明の種々の実施形態では、表形式データの操作は、複数台の演算ユニットにより並列的に実行することも可能である。【００６７】
［部品表（ＢＯＭ）展開］
次に、生産管理システムにおける部品表（ＢＯＭ）展開に関して本発明の一実施形態を説明する。以下の説明では、Ｃａｒ＿Ａという車とＣａｒ＿Ｂという車の構成（又は、構成に対応した部品図番）が部品表の形で与えられている場合を考える。図７は、車の構成に関するストラクチャー型部品表の一例の説明図である。同図に示された部品表には、１０組の親部品の図番（すなわち、親図番）と子部品の図番（すなわち、子図番）の対が格納されている。左端の０から９までの番号は、部品表のレコード番号を表している。部品表の親図番と子図番の対、すなわち、レコードは、このレコード番号によって識別される。たとえば、部品表の先頭行（すなわち、レコード番号＝０のレコード）には、親図番＝Ｃａｒ＿Ａと子図番＝Ｂｏｄｙ＿１の対が格納されている。また、レコード番号＝１のレコードには、親図番＝Ｃａｒ＿Ａと子図番＝Ｅｎｇｉｎｅ＿１の対が格納されている。さらに、レコード番号＝４、レコード番号＝５及びレコード番号＝６のレコードには、親図番＝Ｂｏｄｙ＿１が格納されているので、それぞれの子図番は、Ｔｉｒｅ＿１、Ｃｈａｓｓｉｓ＿１及びＤｏｏｒ＿１であることがわかる。このように、図７の部品表には、部品の階層関係が埋め込まれているので、特に、ストラクチャー型部品表とも呼ばれる。【００６８】
図８は図７の部品表に記述されている車の構成の階層関係を示す図である。本発明の一実施形態は、図７に示されている部品表（原データ）を、図８に示されているツリー構造データに変換（展開）する方法を提供する。この方法は、本発明の一実施形態では、図１に示されたコンピュータシステム１０によって実行される。つまり、以下に述べる処理ステップは、コンピュータシステム１０、特に、コンピュータシステム１０中のＣＰＵ１２により実行される。また、処理ステップにおいて生成されるデータ、表、配列は、それぞれ、メモリ（たとえば、ＲＡＭ１４）中に格納される。変換後のツリー構造データは、図３Ａ、Ｂ又は図４Ａ、Ｂを参照して説明したツリー構造データのデータ表現形式によって記述される。【００６９】
ステップ１：展開したいデータの指定
部品表自体は、親子関係を記述しているが、たとえば、深さ優先順又は幅優先順に整列されているとは限らない。したがって、部品表をツリー構造データに変換するために、最初に、展開したいデータ（ツリー構造データのルートノード）が指定される。展開したいデータは、たとえば、図１に示されたコンピュータシステム１０のハードディスク１８、入力装置２４に予め記憶され、又は、ＣＤ−ＲＯＭドライバ２０を介してＣＤ−ＲＯＭ１９から供給され、又は、Ｉ／Ｆ２２を介して外部端子から供給されるなどの様々な形で与えられる。コンピュータシステム１０のＣＰＵ１２は、何れかの形で与えられたデータを展開したいデータとして指定する。本例では、Ｃａｒ＿Ａをツリー構造データに変換する場合を考える。【００７０】
ステップ２：展開したいデータの表の作成
次に、第１階層の中間データとして、展開したいデータの表が作成される。具体的には、項目名＝展開指令、項目値＝Ｃａｒ＿Ａという１個のレコード（レコード番号＝０）からなる表が作成される。なお、中間データとして作成されるレコードは、レコード順序の入れ替えを想定する必要がないので、簡単のため、レコード順序番号がレコード番号と呼ばれることもある。また、項目名と項目値を併せて項目と呼ぶことがあるが、このとき、項目は項目名で区別される。よって、項目＝展開指令という表記は、項目名＝展開指令という項目を指している。【００７１】
ステップ３：レコード番号対応表の作成（１回目）
第２階層の中間データとして、原データである部品表が準備される。そして、第１階層の中間データ（すなわち、親側のテーブル）と第２階層の中間データ（すなわち、子側のテーブル）との間で、共通化のためのキー項目（すなわち、マッチングキー）に関してマッチングが実行され、２つの階層間でレコード番号対応表が作成される。たとえば、第１階層の中間データ中のあるレコード（たとえば、レコードａ）と、第２階層の中間データ中のあるレコード（たとえば、レコードｂ）が、当該キー項目に関して同一の項目値を有するならば、第１階層の中間データ中のレコードａと第２階層の中間データ中のレコードｂの組み合わせがレコード番号対応表に登録される。なお、本書において、原データ又は中間データに含まれているレコードは、仮想的なレコード配列中のレコードと区別するために、「行」と呼ばれることがある。同様に、レコード番号が「行番号」と呼ばれ、レコード番号対応表が「行番号対応表」と呼ばれることがある。【００７２】
このようなマッチングの一例はジョインによって実現することが可能である。ジョインとは、たとえば、特許文献５に記載されているように、情報ブロックを用いて記述されている２個の表形式データの間で、等価な項目（すなわち、ジョインキー）を見出し、等価な項目に関する情報ブロックに含まれる値リストを比較し、両方の表形式データで参照される値リストを共通化する技術である。ジョインを使ってレコード番号対応表を作成する方法は後述されている。【００７３】
本例では、第１階層の中間データの項目＝展開指令と、第２階層の中間データの項目＝親図番が共通化のためのキー項目として選択される。第１階層の中間データのレコード番号＝０のレコード（以下では、簡単のため、レコード番号＝ＮのレコードをレコードＮと表記することがある）には、項目値＝Ｃａｒ＿Ａが格納されている。一方、第２階層の中間データの項目＝親図番に項目値＝Ｃａｒ＿Ａが格納されているレコードは、レコード０及びレコード１であることがわかる。よって、第１階層の中間データと第２階層の中間データとの間に、
０  →  ０，１
というレコード番号対応表が作成される。【００７４】
ステップ４：レコード番号対応表の作成（２回目）
レコード番号対応表は、共通化のためのキー項目に関して項目値が一致するレコードが存在しなくなるまで続けられる。具体的には、ステップ３において作成されたレコード番号対応表に出現した第２階層の中間データのレコード０及びレコード１に関して、さらに親子関係のあるデータが存在するかどうかが調べられる。本例では、第３階層の中間データとして、原データである部品表がさらに準備される。部品表展開の場合、中間データとして原データが繰り返し利用される。なぜならば、ストラクチャー型部品表は、１つの表の中に階層関係が埋め込まれているからである。第２階層の中間データと第３階層の中間データとの間では、第２階層の中間データの項目＝子図番と第３階層の中間データの項目＝親図番が共通化のためのキー項目として選択される。【００７５】
第２階層の中間データのレコード０の項目＝子図番は、項目値＝Ｂｏｄｙ＿１であり、レコード１の項目＝子図番は、項目値＝Ｅｎｇｉｎｅ＿１である。一方、第３階層の中間データ、すなわち、原データである部品表の項目＝親図番に項目値＝Ｂｏｄｙ＿１が格納されているレコードは、レコード４、レコード５及びレコード６である。また、第３階層の中間データ、すなわち、原データである部品表の項目＝親図番に項目値＝Ｅｎｇｉｎｅ＿１が格納されているレコードは存在しない。よって、第２階層の中間データと第３階層の中間データとの間に、
０  →  ４，５，６
１  →  
というレコード番号対応表が作成される。【００７６】
ステップ５：レコード番号対応表の作成（３回目）
第２階層と第３階層との間に作成されたレコード番号表を参照して、第３階層の中間データのレコード４、レコード５及びレコード６に属する項目＝子図番と、第４階層の中間データ、すなわち、原データである部品表の項目＝親図番とをキー項目として、さらにレコード番号対応表を作成する。しかし、本例では、第３階層の中間データのレコード４の項目値＝Ｔｉｒｅ＿１、レコード５の項目値＝Ｃｈａｓｓｉｓ＿１及びレコード６の項目値＝Ｄｏｏｒ＿１に対応する項目値が第４階層の中間データのレコードの項目＝親図番に存在しない。よって、第４階層の中間データ、及び、第３階層と第４階層との間のレコード番号対応表を作成する必要がないことがわかった。【００７７】
図９は、上記のステップ１からステップ５の処理によって、ストラクチャー型部品表から作成された中間データと中間データ間のレコードの対応関係を示す図である。中間データＴａｂｌｅ＿０と中間データＴａｂｌｅ＿１との間の矢印、及び、中間データＴａｂｌｅ＿１と中間データＴａｂｌｅ＿２との間の矢印は、それぞれ、第１階層と第２階層との間のレコード番号対応表、及び、第２階層と第３階層との間のレコード番号対応表と等価である。【００７８】
ステップ６：レコード番号対応表からツリー構造データの生成
次に、取得されたレコード番号対応表からツリー構造データを生成する。上述されているように、Ｔａｂｌｅ＿０とＴａｂｌｅ＿１との間のレコード番号対応表は、
０  →  ０，１
であり、Ｔａｂｌｅ＿１とＴａｂｌｅ＿２との間のレコード番号対応表は、
０  →  ４，５，６
１  →  
である。図１０Ａ、Ｂには生成されたツリー構造データが示されている。図１０Ａはストラクチャー型部品表から生成された深さ優先形式によるツリー構造データの一例の説明図であり、図１０Ｂは同じストラクチャー型部品表から生成された幅優先形式によるツリー構造データの一例の説明図である。【００７９】
レコード番号対応表からツリー構造データを生成するステップは、深さ優先又は幅優先の何れかの方式で、レコード番号対応表から、親子関係のある親側の中間データ中のレコード番号と子側の中間データ中のレコード番号を探索するステップ６−１と、ツリー構造データの仮想的なレコードの配列中のレコードを生成するステップ６−２とを含む。【００８０】
ステップ６−１において、深さ優先探索を実行すると、深さ優先形式によるツリー構造データが生成され、幅優先探索を実行すると、幅優先形式によるツリー構造データが生成される。深さ優先と幅優先の何れを選択するかは、予め設定されていてもよく、ユーザによって毎回指定されてもよく、又は、アプリケーションに応じて自動的に選択されてもよい。【００８１】
たとえば、本例において、深さ優先探索を実行すると、
（１）Ｔａｂｌｅ＿０［０］  →  Ｔａｂｌｅ＿１［０］
（２）    Ｔａｂｌｅ＿１［０］  →  Ｔａｂｌｅ＿２［４］
（３）    Ｔａｂｌｅ＿１［０］  →  Ｔａｂｌｅ＿２［５］
（４）    Ｔａｂｌｅ＿１［０］  →  Ｔａｂｌｅ＿２［６］
（５）Ｔａｂｌｅ＿０［０］  →  Ｔａｂｌｅ＿１［１］
という順番で親子関係のあるレコードが取得される。【００８２】
ステップ６−２は、ステップ６−１において１つの親子関係が取得されるたびに実行される。たとえば、ステップ６−１において、最初に、親子関係（１）が取得されると、新たに仮想的なレコードの配列に作成されるべきレコードにレコード順序番号０が割り当てられ、レコード順序番号０が割り当てられたレコードＲｅｃｏｒｄ［０］には、このレコードに対応するノードの親ノードのレコード順序番号Ｔｏｐｏｌｏｇｙ［０］と、このレコードに対応する原データの項目名Ｔｉｔｌｅ［０］と、このレコードに対応する原データの項目値Ｖａｌｕｅ［０］がそれぞれ格納される。本例では、Ｒｅｃｏｒｄ［０］は、中間データＴａｂｌｅ＿０［０］に対応している。このレコードに対応するノードには親ノードが存在しないので、Ｔｏｐｏｌｏｇｙ［０］＝−１である。また、Ｔｉｔｌｅ［０］にはＴａｂｌｅ＿０［０］の項目名＝展開指令が格納され、Ｖａｌｕｅ［０］にはＴａｂｌｅ＿０［０］の項目値＝Ｃａｒ＿Ａが格納される。続いて、親子関係（１）の子側のレコードに関する新たなレコードがツリー構造データに生成される。そのため、子側のレコードに対応して新たに生成されるべきレコードには次のレコード順序番号１が割り当てられる。よって、新たに生成されるレコードはＲｅｃｏｒｄ［１］である。そして、Ｔｏｐｏｌｏｇｙ［１］には、このレコードに対応するノードの親ノードに対応するレコードのレコード順序番号、すなわち、０が格納され、Ｔｉｔｌｅ［１］には、Ｔａｂｌｅ＿１の項目名＝子図番が格納され、Ｖａｌｕｅ［１］にはＴａｂｌｅ＿１［０］の項目＝子図番に収容されている項目値＝Ｂｏｄｙ＿１が格納される。ステップ６−２において、新たなレコードが生成されると、処理はステップ６−１へ戻り、次の親子関係が探索される。【００８３】
本例では、次に、親子関係（２）が見つけられ、再びステップ６−２へ進み、新たなレコードが生成される。このステップでは、既に、親側のＴａｂｌｅ＿１［０］に関するレコードは生成されているので、子側のＴａｂｌｅ＿２［４］に関するレコードＲｅｃｏｒｄ［２］がＲｅｃｏｒｄ［１］と同様に生成される。レコード２に対応するノードの親ノードはレコード１であるため、Ｔｏｐｏｌｏｇｙ［２］＝１である。また、Ｔｉｔｌｅ［２］には、Ｔａｂｌｅ＿２の項目名＝子図番が格納され、Ｖａｌｕｅ［２］には、Ｔａｂｌｅ＿２［４］の項目＝子図番に収容されている項目値＝Ｔｉｒｅ＿１が格納される。以下、深さ優先方式でステップ６−１とステップ６−２を繰り返し実行することにより、図１０Ａに示されているようなツリー構造データを表す仮想的なレコードの配列が生成される。【００８４】
幅優先方式の場合も、深さ優先方式と同様にステップ６−１とステップ６−２を繰り返し実行することにより、図１０Ｂに示されているようなツリー構造データを表す仮想的なレコードの配列が生成される。【００８５】
ステップ７：値の分離
図４Ａ、Ｂを参照して説明したように、ツリー構造データ中の項目＝Ｔｉｔｌｅと項目＝Ｖａｌｕｅは、項目値配列と項目値配列へのポインタ配列とに分離することができる。よって、好ましい一実施形態では、ツリー構造データに基づく検索・集計・ソートなどの処理を効率化するため、項目＝Ｔｉｔｌｅと項目＝Ｖａｌｕｅは情報ブロック型に変換される。一方、項目＝Ｔｏｐｏｌｏｇｙは要素が整数の配列によって記述されているので、情報ブロック型に変換する必要はない。【００８６】
図１１Ａ、Ｂは、図１０Ａ、Ｂに示されたツリー構造データを情報ブロック型へ変換することによって生成されたツリー構造データを示す図である。図１１Ａは図１０Ａの深さ優先型のツリー構造データに対応し、図１１Ｂは図１０Ｂの幅優先型のツリー構造データに対応している。【００８７】
以上の説明のように、本発明の一実施形態によれば、ストラクチャー型部品表から統合されたツリー構造データを生成することが可能である。ツリー構造データは、必要に応じて、深さ優先、幅優先の何れの形式でも生成できる。【００８８】
［複数のテーブルで記述されたツリー構造データの統合］
特許文献１又は特許文献２に記載では、ツリー構造データは複数のテーブルの連鎖又は連結によって表現されている。そのため、ツリー構造データを対象とする検索・ソート・集計などの操作が容易ではない。そこで、本発明の一実施形態では、複数のテーブルで記述されたツリー構造データを統合されたツリー構造データに変換する方法が提供される。【００８９】
図１２Ａ、Ｂは、複数のテーブルで記述されたツリー構造データの一例の説明図であり、図１２Ａには、ツリー構造データを記述する複数のテーブルが示され、図１２Ｂには、複数のテーブルによって記述されているツリー構造データの階層関係が示されている。【００９０】
図１２Ａにおいて、１番目のテーブルＴａｂｌｅ＿０は、項目Ｓｔｏｒｙと項目ＤＧｒｉｐとを保有している。ここで、項目Ｓｔｏｒｙは、データに属している実体的な情報であり、項目ＤＧｒｉｐはテーブルの要素間の親子関係を表現するために利用される情報である。２番目のテーブルＴａｂｌｅ＿１は、項目ＵＧｒｉｐと項目Ｆａｍｉｌｙと項目ＤＧｒｉｐとを保有している。ここでも、項目Ｆａｍｉｌｙは実体的な情報であり、項目ＵＧｒｉｐ及び項目ＤＧｒｉｐは親子関係を表現するために利用される情報である。３番目のテーブルＴａｂｌｅ＿２は、親子関係を表現するための情報である項目ＵＧｒｉｐと、実体的な情報である項目Ｎａｍｅとを保有している。ＤＧｒｉｐとして表記されているダウングリップは、データの出現順に割り当てられた順番号である。ＵＧｒｉｐとして表記されているアップグリップは、親エレメントに割り当てられたダウングリップの値である。よって、一般に、あるテーブル中のあるレコードｉのＵＧｒｉｐの値がｍであり、直前のテーブル中のレコードｊのＤＧｒｉｐの値がｍであるならば、あるテーブル中のレコードｉの親エレメントは、直前のテーブル中のレコードｊである。それぞれのレコードは、ツリー構造データ中の１つのノードに対応し、それぞれのレコードの実体的な情報である項目名と項目値が、当該レコードに対応するノードに属する属性名及び属性値を表している。このように、アップグリップとダウングリップを組み合わせることにより、ツリー構造データが複数のテーブルで記述されている。【００９１】
図１２Ｂを参照すると、図１２Ａの複数のテーブルは、Ｈａｒｒｙ  Ｐｏｔｔｅｒをルートノードとするツリーと、Ｍｒ．Ｉｎｃｒｅｄｉｂｌｅをルートノードとするツリーの２つのツリーを含むツリー構造データを表していることがわかる。このような複数のテーブルは、予めデータのスキャン、又は、データ構造の定義などによって、どのようなデータ構造が存在しているかを知り、それに応じて格納先テーブルを作成し、データを格納するという手順に従って構築されるので、様々なデータ構造が随時生成されるエディタのようなアプリケーションには、性能の面で不適当である。【００９２】
［深さ優先方式の統合されたツリー構造データ］
最初に、複数のテーブルで記述されたツリー構造データ、すなわち、原データを深さ優先方式の統合されたツリー構造データへ変換する本発明の一実施形態を説明する。以下に述べる処理ステップは、コンピュータシステム１０、特に、コンピュータシステム１０中のＣＰＵ１２により実行される。また、処理ステップにおいて生成されるデータ、表、配列は、それぞれ、メモリ（たとえば、ＲＡＭ１４）中に格納される。【００９３】
ステップ１：レコード番号対応表の作成
第１階層のテーブルＴａｂｌｅ＿０と第２階層のテーブルＴａｂｌｅ＿１との間でレコード番号対応表が作成される。レコード番号対応表は、Ｔａｂｌｅ＿０の項目ＤＧｒｉｐとＴａｂｌｅ＿１の項目ＵＧｒｉｐをキー項目として、Ｔａｂｌｅ＿０とＴａｂｌｅ＿１の２つのテーブルをジョインすることにより作成される。なお、本発明の一実施形態によれば、ジョインはレコード番号対応表を作成するために使用されるので、ジョインテーブルを生成する必要がないことに注意すべきである。Ｔａｂｌｅ＿０のレコード０と、Ｔａｂｌｅ＿１のレコード１及びレコード２のキー項目値＝０が一致し、Ｔａｂｌｅ＿０のレコード１とＴａｂｌｅ＿１のレコード０のキー項目値＝１が一致しているので、
０  →  １，２
１  →  ０
というレコード対応表が完成される。第２階層のテーブルＴａｂｌｅ＿１と第３階層のテーブルＴａｂｌｅ＿２との間でも同様にレコード番号対応表を作成すると、
０  →  ４，５，６，７
１  →  １，２，３
２  →  ０
というレコード番号対応表が得られる。図１３Ａ、Ｂは、本発明の一実施形態によるレコード番号対応表の作成処理の説明図であり、図１３Ａには、Ｔａｂｌｅ＿０とＴａｂｌｅ＿１との間のレコード番号対応表が示され、図１３Ｂには、Ｔａｂｌｅ＿１とＴａｂｌｅ＿２との間のレコード番号対応表が示されている。【００９４】
ステップ２：レコード番号対応表からツリー構造データの生成
次に、取得されたレコード番号対応表からツリー構造データを生成する。具体的には、仮想的なレコードの配列の各レコードにＴｏｐｏｌｏｇｙフィールドの値、Ｔｉｔｌｅフィールドの値、及び、Ｖａｌｕｅフィールドの値を格納する。【００９５】
ステップ２−１：レコード０の生成
ステップ２−１−１：初期化
配列Ｔｏｐｏｌｏｇｙ、配列Ｔｉｔｌｅ、配列Ｖａｌｕｅ、及び、親ノードのレコード識別番号を格納するスタック配列ＰａｒｅｎｔＮｏｄｅＮｏの領域をメモリに確保し、スタック配列の先頭、すなわち、ＰａｒｅｎｔＮｏｄｅＮｏ［０］に−１をセットする。さらに、スタック配列ＰａｒｅｎｔＮｏｄｅＮｏに格納されている値−１をＴｏｐｏｌｏｇｙ［０］へコピーする。図１４Ａ−Ｃは、本発明の一実施形態による深さ優先方式に基づくツリー構造データ生成処理の説明図であり、図１４Ａには、ステップ２−１−１の処理が示されている。【００９６】
ステップ２−１−２：値の格納
図１４Ｂには、ルートノード（ノード０）に対応するレコード０の生成処理が示されている。同図に上向き矢印で示されているレコード番号対応表中の現在位置は、Ｔａｂｌｅ＿０のレコード０であるので、Ｔａｂｌｅ＿０のレコード０の項目名及び項目値を取得して、Ｔｉｔｌｅ［０］及びＶａｌｕｅ［０］にそれぞれ格納する。【００９７】
ステップ２−１−３：子ノードへの移動
図１４Ｃには、子ノードへの移動処理が示されている。同図に示されているように、レコード番号対応表に従って、現在位置を子ノードへ移動させる。このとき、親ノードの格納アドレス（添字）、すなわち、レコード順序番号＝０をスタック配列ＰａｒｅｎｔＮｏｄｅＮｏにプッシュする。また、同図に横向き矢印で示されている配列Ｔｏｐｏｌｏｇｙ、配列Ｔｉｔｌｅ、及び、配列Ｖａｌｕｅへのポインタが値を格納済みのレコード位置を指しているので、当該ポインタをインクリメントする（１つ先へ進める）。【００９８】
ステップ２−２：レコード１の生成
図１５Ａ−Ｃには、ノード１に対応するレコード１を生成する処理が示されている。最初に、図１５Ａに示されているように、スタック配列ＰａｒｅｎｔＮｏｄｅＮｏに格納されている値を配列Ｔｏｐｏｌｏｇｙ［１］へコピーする。次に、図１５Ｂに示されているように、レコード番号対応表中の現在位置は、Ｔａｂｌｅ＿１のレコード１であるので、Ｔａｂｌｅ＿１のレコード１の項目名及び項目値を取得して、Ｔｉｔｌｅ［１］及びＶａｌｕｅ［１］にそれぞれ格納する。最後に、図１５Ｃに示されているように、レコード番号対応表に従って、現在位置を子ノードへ移動させる。このとき、親ノードの格納アドレス（添字）、すなわち、レコード順序番号＝１をスタック配列ＰａｒｅｎｔＮｏｄｅＮｏにプッシュする。また、同図に横向き矢印で示されている配列Ｔｏｐｏｌｏｇｙ、配列Ｔｉｔｌｅ、及び、配列Ｖａｌｕｅへのポインタが値を格納済みのレコード位置を指しているので、当該ポインタをインクリメントする（１つ先へ進める）。【００９９】
ステップ２−３：レコード２の生成
図１６Ａ−Ｃには、ノード２に対応するレコード２を生成する処理が示されている。最初に、図１６Ａに示されているように、スタック配列ＰａｒｅｎｔＮｏｄｅＮｏに格納されている値を配列Ｔｏｐｏｌｏｇｙ［２］へコピーする。次に、図１６Ｂに示されているように、レコード番号対応表中の現在位置は、Ｔａｂｌｅ＿２のレコード１であるので、Ｔａｂｌｅ＿２のレコード１の項目名及び項目値を取得して、Ｔｉｔｌｅ［２］及びＶａｌｕｅ［２］にそれぞれ格納する。最後に、図１６Ｃに示されているように、レコード番号対応表に従って、子ノードが存在するかどうかをチェックし、子ノードが無ければ、弟ノードが存在するかどうかをチェックする。本例では、弟ノードが存在するので、レコード番号対応表中の現在位置を弟ノードへ移動させる。深さ優先方式であるため、子ノードが弟ノードより優先して調べられている。現在位置を弟ノードへ移動させるとき、スタック配列ＰａｒｅｎｔＮｏｄｅＮｏは操作されない。また、図１６Ｃに横向き矢印で示されている配列Ｔｏｐｏｌｏｇｙ、配列Ｔｉｔｌｅ、及び、配列Ｖａｌｕｅへのポインタが値を格納済みのレコード位置を指しているので、当該ポインタをインクリメントする（１つ先へ進める）。【０１００】
ステップ２−４：レコード３の生成
図１７Ａ−Ｃに示されているように、図１６Ａ−Ｃに示されたステップ２−３と同様にレコード３が生成される。【０１０１】
ステップ２−５：レコード４の生成
図１８Ａ−Ｃには、ノード４に対応するレコード４を生成する処理が示されている。最初に、図１８Ａに示されているように、スタック配列ＰａｒｅｎｔＮｏｄｅＮｏに格納されている値を配列Ｔｏｐｏｌｏｇｙ［４］へコピーする。次に、図１８Ｂに示されているように、レコード番号対応表中の現在位置は、Ｔａｂｌｅ＿２のレコード３であるので、Ｔａｂｌｅ＿２のレコード３の項目名及び項目値を取得して、Ｔｉｔｌｅ［４］及びＶａｌｕｅ［４］にそれぞれ格納する。最後に、図１８Ｃに示されているように、レコード番号対応表に従って、子ノードが存在するかどうかをチェックし、子ノードが無ければ、弟ノードが存在するかどうかをチェックする。本例では、弟ノードも存在しないので、レコード番号対応表中の現在位置を親ノードへ移動させる（戻す）。現在位置を親ノードへ戻すとき、スタック配列ＰａｒｅｎｔＮｏｄｅＮｏから格納されているレコード順序番号をポップする。親ノードは、Ｔａｂｌｅ＿１のレコード１に対応している。次に、この親ノードに弟ノードが存在するかどうかをチェックする。本例では、弟ノードが存在するので、レコード番号対応表中の現在位置をＴａｂｌｅ＿１のレコード１の弟ノード、すなわち、Ｔａｂｌｅ＿１のレコード２へ移動させる。また、図１８Ｃに横向き矢印で示されている配列Ｔｏｐｏｌｏｇｙ、配列Ｔｉｔｌｅ、及び、配列Ｖａｌｕｅへのポインタが値を格納済みのレコード位置を指しているので、当該ポインタをインクリメントする（１つ先へ進める）。【０１０２】
ステップ２−６：レコード５の生成
図１９Ａ−Ｃには、ノード５に対応するレコード５を生成する処理が示されている。最初に、図１９Ａに示されているように、スタック配列ＰａｒｅｎｔＮｏｄｅＮｏに格納されている値を配列Ｔｏｐｏｌｏｇｙ［５］へコピーする。次に、図１９Ｂに示されているように、レコード番号対応表中の現在位置は、Ｔａｂｌｅ＿１のレコード２であるので、Ｔａｂｌｅ＿１のレコード２の項目名及び項目値を取得して、Ｔｉｔｌｅ［５］及びＶａｌｕｅ［５］にそれぞれ格納する。最後に、図１９Ｃに示されているように、レコード番号対応表に従って、現在位置を子ノードへ移動させる。このとき、親ノードの格納アドレス（添字）、すなわち、レコード順序番号＝５をスタック配列ＰａｒｅｎｔＮｏｄｅＮｏへプッシュする。また、図１９Ｃに横向き矢印で示されている配列Ｔｏｐｏｌｏｇｙ、配列Ｔｉｔｌｅ、及び、配列Ｖａｌｕｅへのポインタが値を格納済みのレコード位置を指しているので、当該ポインタをインクリメントする（１つ先へ進める）。【０１０３】
ステップ２−７：レコード６の生成
図２０Ａ−Ｃには、ノード６に対応するレコード６を生成する処理が示されている。最初に、図２０Ａに示されているように、スタック配列ＰａｒｅｎｔＮｏｄｅＮｏに格納されている値を配列Ｔｏｐｏｌｏｇｙ［６］へコピーする。次に、図２０Ｂに示されているように、レコード番号対応表中の現在位置は、Ｔａｂｌｅ＿２のレコード０であるので、Ｔａｂｌｅ＿２のレコード０の項目名及び項目値を取得して、Ｔｉｔｌｅ［６］及びＶａｌｕｅ［６］にそれぞれ格納する。最後に、図２０Ｃに示されているように、レコード番号対応表に従って、子ノードが存在するかどうかをチェックする。子ノードが存在しないので、弟ノードが存在するかどうかをチェックする。本例では、弟ノードも存在しないので、レコード番号対応表中の現在位置を親ノードへ移動させる（戻す）。現在位置を親ノードへ戻すとき、スタック配列ＰａｒｅｎｔＮｏｄｅＮｏから格納されているレコード順序番号をポップする。親ノードは、Ｔａｂｌｅ＿１のレコード２に対応している。次に、この親ノードに弟ノードが存在するかどうかをチェックする。本例では、弟ノードも存在しないので、レコード番号対応表中の現在位置をＴａｂｌｅ＿１のレコード２の親ノード、すなわち、Ｔａｂｌｅ＿０のレコード０へ移動させる。このとき、スタック配列ＰａｒｅｎｔＮｏｄｅＮｏから格納されているレコード順序番号をポップする。また、図２０Ｃに横向き矢印で示されている配列Ｔｏｐｏｌｏｇｙ、配列Ｔｉｔｌｅ、及び、配列Ｖａｌｕｅへのポインタが値を格納済みのレコード位置を指しているので、当該ポインタをインクリメントする（１つ先へ進める）。【０１０４】
以上の処理により、レコード番号対応表中の現在位置がＴａｂｌｅ＿０のレコード０まで戻ったので、Ｈａｒｒｙ  Ｐｏｔｔｅｒに関する深さ優先方式の統合されたツリー構造データが完成した。【０１０５】
もう一方のＴａｂｌｅ＿０のレコード１のＭｒ．Ｉｎｃｒｅｄｉｂｌｅに関する深さ優先方式の統合されたツリー構造データも同様の処理によって生成される。Ｔａｂｌｅ＿０のレコード１の処理は、１台のプロセッサによって、Ｔａｂｌｅ＿０のレコード０に関する処理の後に逐次的に実行されてもよいが、たとえば、複数台のプロセッサを用いて、Ｔａｂｌｅ＿０のレコード０に関する処理と、Ｔａｂｌｅ＿０のレコード１に関する処理が並列的に実行されてもよい。【０１０６】
ステップ３：値リストが分離されたツリー構造データの生成
ステップ２で生成されたツリー構造データは、値リストが分離されたツリー構造データに変換することが可能である。そして、値リストが分離されたツリー構造データは、情報ブロック型のツリー構造データと等価である。よって、本発明の一実施形態では、統合されたツリー構造データを値リストが分離されたツリー構造データに変換する方法が提供される。図２１Ａ−Ｃは、図１２Ａの原データから生成された、値リストが分離されたツリー構造データの説明図である。図２１Ａには統合されたツリー構造データが示されている。【０１０７】
本実施形態では、配列Ｔｉｔｌｅに出現する値が値番号と一意かつ昇順（又は降順）の値リストとに分離され、配列Ｖａｌｕｅに出現する値もまた値番号と一意かつ昇順（又は降順）の値リストとに分離される。たとえば、配列Ｔｉｔｌｅを参照すると、配列Ｔｉｔｌｅ中に出現する値は、
Ｓｔｏｒｙ
Ｎａｍｅ
Ｆａｍｉｌｙ
の３個である。これらの３個の値をアルファベット順に並べ替えると、
Ｆａｍｉｌｙ
Ｎａｍｅ
Ｓｔｏｒｙ
の順になる。よって、値Ｆａｍｉｌｙに値番号０を、値Ｎａｍｅに値番号１を、値Ｓｔｏｒｙに値番号２を割り当て、かつ、
ＶＬ［０］＝Ｆａｍｉｌｙ
ＶＬ［１］＝Ｎａｍｅ
ＶＬ［２］＝Ｓｔｏｒｙ
という値リストを準備すると、値は値番号ＶＮｏと値リストＶＬに分離される。図２１Ｂには、このようにして、値が値番号と値リストに分離されたツリー構造データが示されている。図２１Ｃには、値番号と値リストの組を項目Ｔｉｔｌｅと項目Ｖａｌｕｅに関して分離した情報ブロック型のツリー構造データが示されている。【０１０８】
このように値リストが分離されると、配列Ｔｉｔｌｅや配列Ｖａｌｕｅが整数型配列になるので、コンピュータで高速に処理できるようになる。また、値リストの分離によって重複値の保持が無くなるので、データサイズがコンパクトになる。さらに、値リストの分離によって、検索の際に、同じ値について検索条件の成立を何回も調べる必要がなくなるので、検索が容易になる。また、値リストの分離によって、集計の際に、次元値の一覧が即座に利用できるので、集計が容易になる。その上、値リストの分離によって、ソートの際に、カウンティングソートを利用できるので、ソートが容易になる。【０１０９】
［順序集合と値リストを用いたツリー構造データの生成］
上記の本発明の一実施形態では、ツリー構造データ中の値は、統合されたツリー構造データが作成された後に、値番号と値リストに分離されている。これに対して、本発明の他の実施形態では、複数のテーブルで記述されたツリー構造データ、すなわち、原データを順序集合と情報ブロックとに分離した後に、統合されたツリー構造データを生成する方法が提供される。以下に述べる処理ステップも、コンピュータシステム１０、特に、コンピュータシステム１０中のＣＰＵ１２により実行される。また、処理ステップにおいて生成されるデータ、表、配列は、それぞれ、メモリ（たとえば、ＲＡＭ１４）中に格納される。【０１１０】
ステップ１：データ形式の変換
最初に、図１２Ａに示された原データ、すなわち、Ｔａｂｌｅ＿０、Ｔａｂｌｅ＿１及びＴａｂｌｅ＿２は、順序集合配列ＯｒｄＳｅｔと情報ブロックとからなるデータ形式に変換される。このデータ形式は、既に［情報ブロックに基づくデータ管理機構］において説明した通りである。図２２は、図１２Ａに示された原データから情報ブロックに基づくデータ形式への変換の説明図である。【０１１１】
ステップ２：項目Ｖａｌｕｅのための値リストの共通化
次に、項目Ｓｔｏｒｙ、項目Ｆａｍｉｌｙ及び項目Ｎａｍｅの値リストが共通化される。そのため、最初に項目Ｓｔｏｒｙの値リストと項目Ｆａｍｉｌｙの値リストを共通化し、その後に、最初に共通化された値リストと項目Ｎａｍｅの値リストを共通化する。値リストの共通化は、最終的な情報ブロック型のツリー構造データの項目Ｖａｌｕｅの情報ブロックを作成するために必要な処理である。図２３は、値リストの共通化処理の説明図である。項目Ｓｔｏｒｙの値リストと項目Ｆａｍｉｌｙの値リストを共通化すると、共通化された値リストには、それぞれの値リストからの要素が、重複することなく、アルファベット順に格納されている。そして、各項目の値番号配列の要素は、共通化された値リスト中の対応する値を指定するように値番号が書き換えられる。複数の項目の値リストを共通化すると、複数の項目を１つの情報ブロックとして取り扱えるようになる。【０１１２】
ステップ３：項目Ｔｉｔｌｅの値番号と値リストの分離
次に、ツリー構造データの項目Ｔｉｔｌｅを記述するため、Ｔｉｔｌｅのリストを値番号配列ＶＮｏと値リストＶＬに分離する。図２４は、値配列を値番号と値リストへ分離する処理の説明図である。【０１１３】
ステップ４：レコード番号対応表の作成
次に、Ｔａｂｌｅ＿０とＴａｂｌｅ＿１との間、及び、Ｔａｂｌｅ＿１とＴａｂｌｅ＿２との間でレコード番号対応表が作成される。この処理は図１３を参照して説明した処理と同様である。この処理は、上述されているように、特許文献５に記載されたジョイン処理を利用することによって実現される。図２５Ａ、Ｂは、本発明の一実施形態による、ジョインを利用するレコード番号対応表の作成処理の説明図である。図２５ＡはＴａｂｌｅ＿０とＴａｂｌｅ＿１との間のジョイン処理を示し、図２５ＢはＴａｂｌｅ＿１とＴａｂｌｅ＿２との間のジョイン処理を示している。図２５Ａ、Ｂにおいて、マスタ側とは、元のテーブルの順序集合の順序が保存されている方のテーブルを表し、本例では、上位階層のテーブルがマスタ側に相当し、反対に、スレイブ側とは、元のテーブルの順序集合の順序がジョインキーでソートされている方のテーブルを表し、本例では、下位階層のテーブルがスレイブ側に相当する。【０１１４】
図２５Ｂを参照して、ジョインを利用した、レコード番号対応表の作成処理を詳細に説明する。Ｔａｂｌｅ＿１とＴａｂｌｅ＿２をジョインするとき、キー項目は、マスタ側であるＴａｂｌｅ＿１のＤＧｒｉｐと、スレイブ側であるＴａｂｌｅ＿２のＵＧｒｉｐである。たとえば、マスタ側テーブルのレコードｍのキー項目値と一致するキー項目値を有する要素がスレイブ側データにｎ個存在している場合、ジョインによって生成されるジョインテーブルには、マスタ側テーブルのレコードｍがｎ回繰り返して出現する。本例では、マスタ側のＴａｂｌｅ＿１のレコード０に対応するスレイブ側のＴａｂｌｅ＿２のレコードは、レコード４、レコード５、レコード６及びレコード７の４個存在している。同様に、マスタ側のレコード１には、スレイブ側のレコード１、レコード２及びレコード３が対応し、マスタ側のレコード２には、スレイブ側のレコード０が対応している。図２５Ｂに示されているマスタ側累計数配列と、マスタ側順序集合配列と、マスタ側ジョインキー配列と、スレイブ側累計数配列と、スレイブ側順序集合配列は、このようなマスタ側レコードとスレイブ側レコードの対応関係を記述している。【０１１５】
マスタ側累計数配列は、スレイブ側の対応するレコードの個数を累計数化することにより得られる配列であり、マスタ側累計数配列［１］＝４から、マスタ側順序集合配列［０］＝０によって指定されるマスタ側レコード０に対応するスレイブ側レコードの個数が４個であることがわかる。同様に、マスタ側累計数配列［２］＝７から、マスタ側順序集合配列［１］＝１によって指定されるマスタ側レコード１に対応するスレイブ側レコードの個数が７−４＝３個であることがわかる。さらに、マスタ側累計数配列［３］＝８から、マスタ側順序集合配列［２］＝２によって指定されるマスタ側レコード２に対応するスレイブ側レコードの個数が８−７＝１個であることがわかる。よって、マスタ側累計数配列とマスタ側順序集合配列の組み合わせは、図２６Ａに示されているような仮想的な順序集合配列をコンパクトに表現していることがわかる。換言すると、マスタ側累計数配列［ｉ］は、対応するマスタ側順序集合配列［ｉ］で指定される要素が仮想的な順序集合配列中に出現する開始位置を表している。【０１１６】
スレイブ側順序集合は、ジョインキー、本例では、ＵＧｒｉｐの値でソートされている。図２６Ｂに示されているように、スレイブ側累計数配列［ｉ］もまた、共通化されたジョインキーＶＬ［ｉ］に対応する要素がスレイブ側順序集合配列中に出現する開始位置を示している。【０１１７】
図２５Ｂに示されているようなデータを取得する処理の一例として、特許文献５に記載されているジョイン処理を簡単に説明する。【０１１８】
最初に、複数の表形式データの間で、共通化すべき項目（ジョインキー）を見出す。次に、複数の表形式データにおいて、値リストを比較して、双方の値リストを等価にする。値リストを等価にする際には、項目値の追加に伴ってポインタ配列を変換して、新たなポインタ配列を生成する。さらに、スレイブ表形式データに関するレコードの個数を示す存在数を、項目値に対応して格納するスレイブ側存在数配列を生成し、スレイブ側存在数配列中の存在数を参照して、項目値に対応した存在数の累計数を格納したスレイブ側累計数配列を生成する。一方、マスタ側のレコード番号が示すポインタ配列中のポインタ値を取り出し、ポインタ値が指し示す項目値に対応したスレイブ側存在数配列中の要素を特定し、マスタ側のレコード番号と対応付けて、マスタ表形式データの各レコードに対応するスレイブ表形式データのレコード数を示すレコード数指示配列中に収容し、レコード数指示配列中のレコード数を参照して、マスタ側のレコード番号に対応した、レコード数の累計数を格納するマスタ側累計数配列を生成する。さらに、マスタ側累計数配列に関して、レコード数の累計数の総和を求め、当該総和の数だけの要素を収容可能な、結合された表形式データに関する新たなレコードを特定するための新たなレコード番号配列中の新たなレコード番号と、マスタ側累計数配列中の要素とを比較することにより、重複を考慮した、マスタ表形式データにおけるレコード番号を収容したマスタ側順序集合配列を求める。次に、マスタ側順序集合配列中の要素であるマスタ表形式データにおけるレコード番号により指し示される、スレイブ表形式データに関するポインタ配列中の要素を特定し、スレイブ表形式データに関するポインタ配列中の要素が指し示す、スレイブ側累計数配列中の要素を特定し、これをスレイブ側の開始アドレスとして一時的に保持し、新たなレコード番号配列中のレコード番号と、当該レコード番号により特定されるマスタ累計数配列中の要素と、スレイブ側の開始アドレスとから、重複を考慮した、スレイブ表形式データにおけるレコード番号を収容したスレイブ側順序集合配列を求める。【０１１９】
もう一度図２５Ｂに戻り、マスタ側レコードから対応するスレイブ側レコードを取得する処理を説明する。マスタ側順序集合配列［０］＝０と、対応するマスタ側ジョインキーＶＮｏ「０」＝０とから、マスタ側レコード０に対応するスレイブ側レコードのレコード番号は、スレイブ側順序集合配列中のスレイブ側累計数配列［０］＝０番目から、スレイブ側累計数配列［０＋１］＝４−１＝３番目までの要素、すなわち、レコード番号＝４、５、６及び７であることがわかる。これにより、レコード番号対応表の１行目の
０  →  ４，５，６，７
が取得できる。同様に、マスタ側レコード１に対応するスレイブ側レコードは、スレイブ側順序集合配列中のスレイブ側累計数配列［１］＝４番目から、スレイブ側累計数配列［１＋１］＝７−１＝６番目までの要素、すなわち、レコード番号＝１、２及び３であることがわかる。これにより、レコード番号対応表の２行目の
１  →  １，２，３
が取得できる。さらに、同様に、マスタ側レコード２に対応するスレイブ側レコードは、スレイブ側順序集合配列中のスレイブ側累計数配列［２］＝７番目から、スレイブ側累計数配列［２＋１］＝８−１＝７番目までの要素、すなわち、レコード番号＝０であることがわかる。これにより、レコード番号対応表の３行目の
２  →  ０
が取得できる。【０１２０】
Ｔａｂｌｅ＿０とＴａｂｌｅ＿１との間のレコード番号対応表もジョイン処理を利用して同様に取得できる。【０１２１】
ステップ５：ツリー構造データの生成
ステップ４において取得されたレコード番号対応表が生成されると、ツリー構造データのＴｏｐｏｌｏｇｙ配列と、Ｔｉｔｌｅ＿ＶＮｏ配列と、Ｖａｌｕｅ＿ＶＮｏ配列に、レコード０から順に値を格納することにより、値が分離されたツリー構造データが生成される。このとき、図２３に示されているような、項目Ｓｔｏｒｙ、項目Ｆａｍｉｌｙ及び項目Ｎａｍｅを共通化した項目Ｖａｌｕｅに関する値番号及び値リストと、図２４に示されているような、項目Ｔｉｔｌｅに関する値番号及び値リストが使用される。【０１２２】
ステップ５−１：レコード０の生成
ステップ５−１−１：初期化
配列Ｔｏｐｏｌｏｇｙ、配列Ｔｉｔｌｅ、配列Ｖａｌｕｅ、及び、親ノードのレコード識別番号を格納するスタック配列ＰａｒｅｎｔＮｏｄｅＮｏの領域をメモリに確保し、スタック配列の先頭、すなわち、ＰａｒｅｎｔＮｏｄｅＮｏ［０］に−１をセットする。さらに、スタック配列ＰａｒｅｎｔＮｏｄｅＮｏに格納されている値−１をＴｏｐｏｌｏｇｙ［０］へコピーする。この処理は、図１４Ａを参照して説明した処理に類似している。【０１２３】
ステップ５−１−２：値の格納
この処理は、図１４Ｂを参照して説明したルートノード（ノード０）に対応するレコード０の生成処理と類似している。レコード番号対応表中の現在位置は、Ｔａｂｌｅ＿０のレコード０であるので、Ｔａｂｌｅ＿０のレコード０の項目名ｓｔｏｒｙの値番号＝２、及び、項目値の値番号４を取得して、Ｔｉｔｌｅ［０］及びＶａｌｕｅ［０］にそれぞれ格納する。このように、本実施形態では、配列Ｔｉｔｌｅ及び配列Ｖａｌｕｅに格納される値が、項目名及び項目値ではなく、項目名の値番号及び項目値の値番号である。【０１２４】
ステップ５−１−３：子ノードへの移動
この処理は、図１４Ｃを参照して説明された子ノードへの移動処理と類似している。レコード番号対応表に従って、現在位置を子ノードへ移動させる。このとき、親ノードの格納アドレス（添字）、すなわち、レコード順序番号＝０をスタック配列ＰａｒｅｎｔＮｏｄｅＮｏにプッシュする。また、同図に横向き矢印で示されている配列Ｔｏｐｏｌｏｇｙ、配列Ｔｉｔｌｅ、及び、配列Ｖａｌｕｅへのポインタが値を格納済みのレコード位置を指しているので、当該ポインタをインクリメントする（１つ先へ進める）。【０１２５】
ステップ５−２：レコード１の生成
この処理は、図１５Ａ−Ｃを参照して説明されたノード１に対応するレコード１を生成する処理と類似している。最初に、スタック配列ＰａｒｅｎｔＮｏｄｅＮｏに格納されている値を配列Ｔｏｐｏｌｏｇｙ［１］へコピーする。次に、レコード番号対応表中の現在位置は、Ｔａｂｌｅ＿１のレコード１であるので、Ｔａｂｌｅ＿１のレコード１の項目名Ｆａｍｉｌｙの値番号＝０及び項目値Ｐｏｔｔｅｒの値番号＝１０を取得して、Ｔｉｔｌｅ［１］及びＶａｌｕｅ［１］にそれぞれ格納する。最後に、レコード番号対応表に従って、現在位置を子ノードへ移動させる。このとき、親ノードの格納アドレス（添字）、すなわち、レコード順序番号＝１をスタック配列ＰａｒｅｎｔＮｏｄｅＮｏにプッシュする。また、図１５Ｃに横向き矢印で示されている配列Ｔｏｐｏｌｏｇｙ、配列Ｔｉｔｌｅ、及び、配列Ｖａｌｕｅへのポインタが値を格納済みのレコード位置を指しているので、当該ポインタをインクリメントする（１つ先へ進める）。【０１２６】
以下、図１６Ａ−Ｃ乃至図２０Ａ−Ｃを参照して説明した処理と同様の処理を実行することにより、図２１Ｂに示されているように、値リストが分離されたツリー構造データが生成される。この値リストが分離されたツリー構造データを、図２１Ｃに示されるような情報ブロック型のツリー構造データへ変換する処理は前述されている通りである。【０１２７】
最後に、もう一方のＴａｂｌｅ＿０のレコード１のＭｒ．  Ｉｎｃｒｅｄｉｂｌｅに関する深さ優先方式のツリー構造データも同様の処理によって生成される。Ｔａｂｌｅ＿０のレコード１の処理は、１台のプロセッサによって、Ｔａｂｌｅ＿０のレコード０に関する処理の後に逐次的に実行されてもよいが、たとえば、複数台のプロセッサを用いて、Ｔａｂｌｅ＿０のレコード０に関する処理と、Ｔａｂｌｅ＿０のレコード１に関する処理が並列的に実行されてもよい。【０１２８】
図２７には、Ｔａｂｌｅ＿０のレコード０とレコード１の両方に対して、本発明の一実施形態によるツリー構造データの生成処理を適用した結果が示されている。この例では、Ｔａｂｌｅ＿０のレコード０が一方のルートノードに対応し、Ｔａｂｌｅ＿１のレコード１がもう一方のルートノードに対応している。これに対して、Ｔａｂｌｅ＿０のレコード０に対応するノードとＴａｂｌｅ＿１のレコード１に対応するノードが兄弟ノードとなるようなツリー構造データを生成することも可能である。図２８には、Ｔａｂｌｅ＿０のレコード０とレコード１を兄弟ノードとして取り扱うような、本発明の別の実施形態によるツリー構造データの生成処理を適用した結果が示されている。【０１２９】
［幅優先方式の統合されたツリー構造データ］
今度は、複数のテーブルで記述されたツリー構造データ、すなわち、原データを幅優先方式の統合されたツリー構造データへ変換する本発明の一実施形態を説明する。ここでも、原データは、図１２Ａに示されているような複数のテーブルで記述されたツリー構造データである。以下に述べる処理ステップも、コンピュータシステム１０、特に、コンピュータシステム１０中のＣＰＵ１２により実行される。また、処理ステップにおいて生成されるデータ、表、配列は、それぞれ、メモリ（たとえば、ＲＡＭ１４）中に格納される。【０１３０】
ステップ１：レコード番号対応表の作成
図１３Ａ、Ｂを参照して説明した、深さ優先方式におけるレコード番号対応表の作成処理が幅優先方式においても全く同様に適用される。【０１３１】
ステップ２：レコード番号対応表からツリー構造データの生成
次に、取得されたレコード番号対応表からツリー構造データを生成する。具体的には、幅優先方式であるため、最上位階層から順に仮想的なレコードの配列での格納位置を決定し、仮想的なレコードの配列の各レコードにＴｏｐｏｌｏｇｙフィールドの値、Ｔｉｔｌｅフィールドの値、及び、Ｖａｌｕｅフィールドの値を格納する。【０１３２】
ステップ３：レコード０の生成
最上位ノードは、Ｔａｂｌｅ＿０のレコード０である。最上位ノードには親ノードが存在しないので、−１をＴｏｐｏｌｏｇｙ［０］に格納する（転送１）。Ｔａｂｌｅ＿０のレコード０の項目名及び項目値を取得して、Ｔｉｔｌｅ［０］及びＶａｌｕｅ［０］にそれぞれ格納する（転送２）。確定したレコード順序番号（すなわち、ノード番号、この例では、０）をレコード番号対応表に追記する（転送３）。ノード０には弟ノードが存在しないので、次のノードは、次の階層（深さ）に存在する最初のノードである。図２９は、このような本発明の一実施形態による幅優先方式のツリー構造データ生成処理の説明図である。【０１３３】
ステップ４：レコード１の生成
次に、図３０を参照して、ツリー構造データのレコード１の生成処理を説明する。現在のノードは、Ｔａｂｌｅ＿１のレコード１である。親ノードのレコード順序番号は０であるので、Ｔｏｐｏｌｏｇｙ［１］に０を格納する（転送１）。Ｔａｂｌｅ＿１のレコード１の項目名及び項目値を取得して、Ｔｉｔｌｅ［１］及びＶａｌｕｅ［１］にそれぞれ格納する（転送２）。確定したノード番号（この例では、１）をレコード番号対応表に追記する（転送３）。ノード１には弟ノードが存在するので、次のノードは弟ノードである。【０１３４】
ステップ５：レコード２の生成
次に、図３１を参照して、ツリー構造データのレコード２の生成処理を説明する。現在のノードは、Ｔａｂｌｅ＿１のレコード２である。親ノードのレコード順序番号は０であるので、Ｔｏｐｏｌｏｇｙ［２］に０を格納する（転送１）。Ｔａｂｌｅ＿１のレコード２の項目名及び項目値を取得して、Ｔｉｔｌｅ［２］及びＶａｌｕｅ［２］にそれぞれ格納する（転送２）。確定したノード番号（この例では、２）をレコード番号対応表に追記する（転送３）。ノード２には弟ノードが存在せず、かつ、同世代にも未確定ノードが存在しないので、次のノードは、次の階層（深さ）に存在する最初のノードである。【０１３５】
ステップ６：レコード３の生成
次に、図３２を参照して、ツリー構造データのレコード３の生成処理を説明する。現在のノードは、Ｔａｂｌｅ＿２のレコード１である。親ノードのレコード順序番号は１であるので、Ｔｏｐｏｌｏｇｙ［３］に１を格納する（転送１）。Ｔａｂｌｅ＿２のレコード１の項目名及び項目値を取得して、Ｔｉｔｌｅ［３］及びＶａｌｕｅ［３］にそれぞれ格納する（転送２）。確定したノード番号（この例では、３）をレコード番号対応表に追記する（転送３）。ノード３には弟ノードが存在するので、次のノードは弟ノードである。【０１３６】
ステップ７：レコード４の生成
次に、ツリー構造データのレコード４の生成処理を説明する。現在のノードは、Ｔａｂｌｅ＿２のレコード２である。親ノードのレコード順序番号は１であるので、Ｔｏｐｏｌｏｇｙ［４］に１を格納する（転送１）。Ｔａｂｌｅ＿２のレコード２の項目名及び項目値を取得して、Ｔｉｔｌｅ［４］及びＶａｌｕｅ［４］にそれぞれ格納する（転送２）。確定したノード番号（この例では、４）をレコード番号対応表に追記する（転送３）。ノード４には弟ノードが存在するので、次のノードは弟ノードである。【０１３７】
ステップ８：レコード５の生成
次に、図３３を参照して、ツリー構造データのレコード５の生成処理を説明する。現在のノードは、Ｔａｂｌｅ＿２のレコード３である。親ノードのレコード順序番号は１であるので、Ｔｏｐｏｌｏｇｙ［５］に１を格納する（転送１）。Ｔａｂｌｅ＿２のレコード３の項目名及び項目値を取得して、Ｔｉｔｌｅ［５］及びＶａｌｕｅ［５］にそれぞれ格納する（転送２）。確定したノード番号（この例では、５）をレコード番号対応表に追記する（転送３）。ノード５には弟ノードは存在しないが、同世代の未確定ノードが存在するので、次のノードは同世代の次のデータである。【０１３８】
ステップ９：レコード６の生成
次に、図３４を参照して、ツリー構造データのレコード６の生成処理を説明する。現在のノードは、Ｔａｂｌｅ＿２のレコード０である。親ノードのレコード順序番号は２であるので、Ｔｏｐｏｌｏｇｙ［６］に２を格納する（転送１）。Ｔａｂｌｅ＿２のレコード０の項目名及び項目値を取得して、Ｔｉｔｌｅ［６］及びＶａｌｕｅ［６］にそれぞれ格納する（転送２）。確定したノード番号（この例では、６）をレコード番号対応表に追記する（転送３）。ノード６には、弟ノードも次の世代のノードも存在しないので、ツリー構造データの生成処理が完了する。【０１３９】
幅優先方式によるツリー構造データの生成処理の場合も、深さ優先方式と同様に、値リストが分離されたツリー構造データの生成処理や、順序集合と値リストを用いたツリー構造データの生成処理を実現することが可能である。図３５は、本発明の一実施形態による幅優先方式のツリー構造データ生成処理を用いて生成された情報ブロック型ツリー構造データの説明図である。【０１４０】
最後に、もう一方のＴａｂｌｅ＿０のレコード１のＭｒ．  Ｉｎｃｒｅｄｉｂｌｅに関する幅優先方式のツリー構造データも同様の処理によって生成される。Ｔａｂｌｅ＿０のレコード１の処理は、１台のプロセッサによって、Ｔａｂｌｅ＿０のレコード０に関する処理の後に逐次的に実行されてもよいが、たとえば、複数台のプロセッサを用いて、Ｔａｂｌｅ＿０のレコード０に関する処理と、Ｔａｂｌｅ＿０のレコード１に関する処理が並列的に実行されてもよい。【０１４１】
図３６には、Ｔａｂｌｅ＿０のレコード０とレコード１の両方に対して、本発明の一実施形態によるツリー構造データの生成処理を適用した結果が示されている。この例では、Ｔａｂｌｅ＿０のレコード０が一方のルートノードに対応し、Ｔａｂｌｅ＿１のレコード１がもう一方のルートノードに対応している。これに対して、Ｔａｂｌｅ＿０のレコード０に対応するノードとＴａｂｌｅ＿１のレコード１に対応するノードが兄弟ノードとなるようなツリー構造データを生成することも可能である。図３７には、Ｔａｂｌｅ＿０のレコード０とレコード１を兄弟ノードとして取り扱うような、本発明の別の実施形態によるツリー構造データの生成処理を適用した結果が示されている。【０１４２】
本発明は、以上の実施の形態に限定されることなく、特許請求の範囲に記載された発明の範囲内で、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【図１】
2009095981.tif 000003
【図２】
2009095981.tif 000004
【図３】
2009095981.tif 000005
【図４】
2009095981.tif 000006
【図５】
2009095981.tif 000007
【図６】
2009095981.tif 000008
【図７】
2009095981.tif 000009
【図８】
2009095981.tif 000010
【図９】
2009095981.tif 000011
【図１０】
2009095981.tif 000012
【図１１】
2009095981.tif 000013
【図１２】
2009095981.tif 000014
【図１３】
2009095981.tif 000015
【図１４】
2009095981.tif 000016
【図１５】
2009095981.tif 000017
【図１６】
2009095981.tif 000018
【図１７】
2009095981.tif 000019
【図１８】
2009095981.tif 000020
【図１９】
2009095981.tif 000021
【図２０】
2009095981.tif 000022
【図２１】
2009095981.tif 000023
【図２２】
2009095981.tif 000024
【図２３】
2009095981.tif 000025
【図２４】
2009095981.tif 000026
【図２５】
2009095981.tif 000027
【図２６】
2009095981.tif 000028
【図２７】
2009095981.tif 000029
【図２８】
2009095981.tif 000030
【図２９】
2009095981.tif 000031
【図３０】
2009095981.tif 000032
【図３１】
2009095981.tif 000033
【図３２】
2009095981.tif 000034
【図３３】
2009095981.tif 000035
【図３４】
2009095981.tif 000036
【図３５】
2009095981.tif 000037
【図３６】
2009095981.tif 000038
【図３７】
2009095981.tif 000039
【国際調査報告】
2009095981.tif 000040
2009095981.tif 000041
2009095981.tif 000042
2009095981.tif 000043
2009095981.tif 000044
2009095981.tif 000045