(57)【要約】【課題】連鎖したジョインテーブルをツリー構造に、高速変換する。【解決手段】まず、各表形式データを、各々が、特定の項目に属する項目値に対応した項目値番号の順に当該項目値が格納されている値リストと、一意的なレコード番号の順に、当該項目値番号を指示するためのポインタ値が格納されたポインタ配列とからなる一以上の情報ブロックに分割する。次いで、項目を共通化すべき表形式データを選択して、所定の項目の値リストを等価にして、ジョインを実行する（ステップ４０１）。ジョインは、必要な表形式データ間で繰り返される。次いで、結合された表形式データのうち、根となるものを選択し、表形式データの結合にしたがって、各表形式データの深さを決定し、表形式データの結合および深さにしたがって、レコードを示す値を、ツリーを記述するためのツリー記述テーブルに配置していく（ステップ４０４〜４１１）。【選択図】　図４
2004145640.tif 000002
【特許請求の範囲】
【請求項１】
各々が、項目とこれに含まれる項目値とを含むレコードの配列として表わされる複数の表形式データを結合し、結合された表形式データであるジョインテーブルをツリー構造に変換する方法であって、
ａ）各表形式データを、各々が、特定の項目に属する項目値に対応した項目値番号の順に当該項目値が格納されている値リストと、一意的なレコード番号の順に、当該項目値番号を指示するためのポインタ値が格納されたポインタ配列とからなる一以上の情報ブロックに分割するように構成するステップと、
ｂ）項目を共通化すべき二つの表形式データを選択するステップと、
ｃ）当該選択された二つの表形式データにおいて、共通化すべき項目を見出すステップと、
ｄ）前記特定された情報ブロックのうち、デフォルトのソート順が反映される表形式データをマスタ表形式データと決定し、それ以外の表形式データをスレイブ表形式データと決定するステップと、
ｅ）前記選択された表形式データにおいて、前記特定された情報ブロックに含まれる値リストを相互に等価にした場合に、マスタ側のレコードに対応するスレイブ側のレコードを対応付けるステップと、
ｆ）前記二つの表形式データのうちのスレイブ側の表形式データをマスタ側とするような、他の二つの表形式データを選択し、当該他の二つの表形式データについて、前記ｃ）項目を見出すステップ、ｄ）マスタ表形式データおよびスレイブ表形式データを決定するステップ、および、ｅ）対応付けるステップとを実行するステップと、
ｇ）前記ｆ）のステップを、ジョインが必要な表形式データに関して繰り返すステップと、
ｈ）ジョインにより結合された表形式データのうち、根となるものを選択し、前記表形式データの結合にしたがって、各表形式データの深さを決定するステップと、
ｉ）前記深さおよびレコード番号の組み合わせを値とするツリー記述テーブルのための領域を確保するステップと、
ｊ）初期的には最も浅い深さとなるような、ある深さのレコードを特定し、前記レコードを示す値を、深さとともに、前記ツリー記述テーブルのための領域に配置するステップと、
ｋ）前記特定されたレコードから、スレイブ側の表形式データのレコードを特定し、当該レコードに基づき、スレイブ側の表形式データがマスタ側となるような表形式データのレコードを示す値を、前記マスタ側の表形式データの深さとともに、前記ツリー記述テーブルのための領域に配置するステップと、
ｌ）前記ｋ）のステップを、表形式データが存在しない深さになるまで、或いは、レコードが存在しなくなるまで繰り返すステップと、
ｍ）前記ｊ）ないしｌ）のステップを繰り返すことにより、ツリー記述テーブルのための領域に、所定の深さおよびレコードを特定する値を配置することにより、ツリー記述テーブルを完成させるステップとを備えたことを特徴とする方法。
【請求項２】
前記ｅ）のステップにおいて、
前記値リストを等価にする際に、マスタ側の情報ブロックにおいて、その項目値の追加にともなって、前記情報ブロックのポインタ配列を指し示すための第２の射影配列を生成するステップと、
前記スレイブ側の情報ブロックにおいて、共通化された項目の値の存在する数を累計化した第３の射影配列を生成するステップと、
スレイブ側の情報ブロックにおいて、前記共通化された項目にてソートされたレコードを指し示す値の集合である第４の射影配列を生成するステップとを備え、
前記第２の射影配列、マスタ側の情報ブロックのポインタ配列、第３の射影配列および第４の射影配列を順次たどることにより、スレイブ側のレコードが特定されることを特徴とする請求項１に記載の方法。
【請求項３】
さらに、
ｎ）最も浅い深さの表形式データを除き、マスタ側に関する第２の射影配列の逆写像配列を生成するステップを備え、
前記第４の射影配列からの要素が指し示す逆写像配列の要素により、次の深さの表形式データにおけるマスタ側の第２の射影配列の要素が特定されることを特徴とする請求項２に記載の方法。
【請求項４】
前記逆写像を生成するステップにおいて、
前記マスタ側に関する第２の射影配列の要素数と等しい要素を収容する、逆写像のための配列を配置するステップと、
前記各要素として、レコードを特定し得ない他の値を配置するステップと、
前記第４の射影配列の位置を要素に、かつ、要素を位置とするように、前記逆写像配列に値を付与するステップとを備えたことを特徴とする請求項３に記載の方法。
【請求項５】
さらに、前記項目を共通化すべき二つの表形式データの少なくとも一方において、前記表形式データの共通化すべき項目について、検索、集計およびソートの何れかを施すステップを備えたことを特徴とする請求項１ないし４の何れか一項に記載の方法。
【請求項６】
各々が、項目とこれに含まれる項目値とを含むレコードの配列として表わされる複数の表形式データを結合し、結合された表形式データであるジョインテーブルをツリー構造に変換するプログラムであって、
ａ）各表形式データを、各々が、特定の項目に属する項目値に対応した項目値番号の順に当該項目値が格納されている値リストと、一意的なレコード番号の順に、当該項目値番号を指示するためのポインタ値が格納されたポインタ配列とからなる一以上の情報ブロックに分割するように構成するステップと、
ｂ）項目を共通化すべき二つの表形式データを選択するステップと、
ｃ）当該選択された二つの表形式データにおいて、共通化すべき項目を見出すステップと、
ｄ）前記特定された情報ブロックのうち、デフォルトのソート順が反映される表形式データをマスタ表形式データと決定し、それ以外の表形式データをスレイブ表形式データと決定するステップと、
ｅ）前記選択された表形式データにおいて、前記特定された情報ブロックに含まれる値リストを相互に等価にした場合に、マスタ側のレコードに対応するスレイブ側のレコードを対応付けるステップと、
ｆ）前記二つの表形式データのうちのスレイブ側の表形式データをマスタ側とするような、他の二つの表形式データを選択し、当該他の二つの表形式データについて、前記ｃ）項目を見出すステップ、ｄ）マスタ表形式データおよびスレイブ表形式データを決定するステップ、および、ｅ）対応付けるステップとを実行するステップと、
ｇ）前記ｆ）のステップを、ジョインが必要な表形式データに関して繰り返すステップと、
ｈ）ジョインにより結合された表形式データのうち、根となるものを選択し、前記表形式データの結合にしたがって、各表形式データの深さを決定するステップと、
ｉ）前記深さおよびレコード番号の組み合わせを値とするツリー記述テーブルのための領域を確保するステップと、
ｊ）初期的には最も浅い深さとなるような、ある深さのレコードを特定し、前記レコードを示す値を、深さとともに、前記ツリー記述テーブルのための領域に配置するステップと、
ｋ）前記特定されたレコードから、スレイブ側の表形式データのレコードを特定し、当該レコードに基づき、スレイブ側の表形式データがマスタ側となるような表形式データのレコードを示す値を、前記マスタ側の表形式データの深さとともに、前記ツリー記述テーブルのための領域に配置するステップと、
ｌ）前記ｋ）のステップを、表形式データが存在しない深さになるまで、或いは、レコードが存在しなくなるまで繰り返すステップと、
ｍ）前記ｊ）ないしｌ）のステップを繰り返すことにより、ツリー記述テーブルのための領域に、所定の深さおよびレコードを特定する値を配置することにより、ツリー記述テーブルを完成させるステップとを、前記コンピュータに実行させることを特徴とするプログラム。
【請求項７】
前記ｅ）のステップにおいて、
前記値リストを等価にする際に、マスタ側の情報ブロックにおいて、その項目値の追加にともなって、前記情報ブロックのポインタ配列を指し示すための第２の射影配列を生成するステップと、
前記スレイブ側の情報ブロックにおいて、共通化された項目の値の存在する数を累計化した第３の射影配列を生成するステップと、
スレイブ側の情報ブロックにおいて、前記共通化された項目にてソートされたレコードを指し示す値の集合である第４の射影配列を生成するステップとを、前記コンピュータに実行させ、
前記第２の射影配列、マスタ側の情報ブロックのポインタ配列、第３の射影配列および第４の射影配列を順次たどることにより、スレイブ側のレコードが特定されるよう、前記コンピュータを動作させることを特徴とする請求項６に記載のプログラム。
【請求項８】
さらに、
ｎ）最も浅い深さの表形式データを除き、マスタ側に関する第２の射影配列の逆写像配列を生成するステップを、前記コンピュータに実行させ、
前記第４の射影配列からの要素が指し示す逆写像配列の要素により、次の深さの表形式データにおけるマスタ側の第２の射影配列の要素が特定されるように、前記コンピュータを動作させることを特徴とする請求項７に記載のプログラム。
【請求項９】
前記逆写像を生成するステップにおいて、
前記マスタ側に関する第２の射影配列の要素数と等しい要素を収容する、逆写像のための配列を配置するステップと、
前記各要素として、レコードを特定し得ない他の値を配置するステップと、
前記第４の射影配列の位置を要素に、かつ、要素を位置とするように、前記逆写像配列に値を付与するステップとを、前記コンピュータに実行させることを特徴とする請求項８に記載のプログラム。
【請求項１０】
さらに、前記項目を共通化すべき二つの表形式データの少なくとも一方において、前記表形式データの共通化すべき項目について、検索、集計およびソートの何れかを施すステップを、前記コンピュータに実行させることを特徴とする請求項６ないし９の何れか一項に記載のプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、連鎖したジョインテーブルをツリー構造に、高速変換する手法に関する。
【０００２】
【従来の技術】
データベースは種々の用途に用いられているが、中規模ないし大規模システムにおいては、論理的な矛盾が排除できるリレーショナルデータベース（ＲＤＢ）の使用が主流となっている。ＲＤＢは、基本的には、項目および値と、当該値と関連付けられた他の項目の値へのポインタとから構成されているため、これをツリー構造化することは容易ではなかった。特に、大量のデータを取り扱う必要がある場合に、ＲＤＢでは大量のリレーションが発生し、データ量が著しく大きくなり、かつ、処理にも著しい時間を要する。
【０００３】
これに対して、ＸＭＬデータベースなどオブジェクト指向データベースが提案されている。このオブジェクト指向データベースは、データをそもそもツリー構造で保存し、その木（ツリー）の枝を順次たどっていくことが可能となる。
【０００４】
【発明が解決しようとする課題】
しかしながら、従来のデータベースにおけるツリー構造においては、以下の挙げるような問題点があった。
（１）根（ルート）が固定される。
従来のツリー構造では、特定のノードから他の特定のノードへのポインタで構成されているため、ノード間のリンクの繋ぎ代えが不可能である。また、ポインタを１方向にしかたどることができない。このため、ツリーは、論理的には、どの要素を根（ルート）としても良いはずであるにもかかわらず、実際には、根が固定されている。
【０００５】
（２）ツリー構造が固定される。
各ノードは、様々な属性を有している。たとえば、職場の住所と、住まいの住所という項目がある場合に、職場の住所に基づくツリー（たとえば、日本−東京都−港区・・・）というツリーと、住まいの住所に基づくツリー（たとえば、日本−神奈川県−横浜市・・・）とは、論理的に別々のツリーを構成する。しかしながら、従来のデータベースにおけるツリー構造においては、これら別々のツリーを構築することが不可能であった。
【０００６】
（３）処理速度が著しく遅く、また、ソートや集計が困難である。
検索はツリーを順次たどる必要があるため著しい処理時間を要する。また、同様にツリーを順次たどって要素を特定する必要があるため、ソートや集計が困難である。
【０００７】
その一方、本発明者は、特許文献１に記載したような、表形式データを、各々が、特定の項目に属する項目値に対応した項目値番号の順に当該項目値が格納されている値リストと、一意的なレコード番号の順に、当該項目値番号を指示するためのポインタ値が格納されたポインタ配列とからなる一以上の情報ブロックに分割し、レコード番号、ポインタ配列中、当該レコード番号に対応する位置の要素（ポインタ値）、および、値リスト中、ポインタ値が指し示す位置の要素（項目値）を順次たどることにより、レコード番号に対応する項目値を特定する技術を考案している。
【０００８】
【特許文献１】
国際公開第ＷＯ００／１０１０３号パンフレット（第３図および第４図）
このようなデータ形式を採用することにより、従来のＲＤＢと比較して、検索、集計、ソートなどを著しく高速に実現することができた。
また、特許文献２に開示したように、上記データ形式を採用した複数のテーブルをジョインする手法も、本発明者は提案している。
【０００９】
【特許文献２】
特開２０００−３３９３９０号公報（第（１４）頁〜第（１７）頁および図１０ないし図１８）
これにより、項目値が共通する項目をキーとして、複数のテーブルをジョインすることが可能となり、かつ、当該ジョインされたテーブルの検索、集計なども容易に実現することができる。
【００１０】
本発明者は、上記特許文献１および特許文献２を利用して、１以上のツリー構造を構築することができることに知見し、これを実現した。この方法およびプログラムによれば、上述した（１）〜（３）の問題点が解決され、任意の根（ルート）から、種々の項目のツリー構造を構築できた。かつ、その処理速度は高速であり、また、集計やソートを実現することもできた。
つまり、本発明は、任意の根を選択して、所望の１以上のツリー構造を高速に構築することができ、検索、集計、ソートが高速に実行できる方法およびプログラムを提供することを目的とする。
【００１１】
【課題を解決するための手段】
本発明の目的は、各々が、項目とこれに含まれる項目値とを含むレコードの配列として表わされる複数の表形式データを結合し、結合された表形式データであるジョインテーブルをツリー構造に変換する方法であって、
ａ）各表形式データを、各々が、特定の項目に属する項目値に対応した項目値番号の順に当該項目値が格納されている値リストと、一意的なレコード番号の順に、当該項目値番号を指示するためのポインタ値が格納されたポインタ配列とからなる一以上の情報ブロックに分割するように構成するステップと、
ｂ）項目を共通化すべき二つの表形式データを選択するステップと、
ｃ）当該選択された二つの表形式データにおいて、共通化すべき項目を見出すステップと、
ｄ）前記特定された情報ブロックのうち、デフォルトのソート順が反映される表形式データをマスタ表形式データと決定し、それ以外の表形式データをスレイブ表形式データと決定するステップと、
ｅ）前記選択された表形式データにおいて、前記特定された情報ブロックに含まれる値リストを相互に等価にした場合に、マスタ側のレコードに対応するスレイブ側のレコードを対応付けるステップと、
ｆ）前記二つの表形式データのうちのスレイブ側の表形式データをマスタ側とするような、他の二つの表形式データを選択し、当該他の二つの表形式データについて、前記ｃ）項目を見出すステップ、ｄ）マスタ表形式データおよびスレイブ表形式データを決定するステップ、および、ｅ）対応付けるステップとを実行するステップと、
ｇ）前記ｆ）のステップを、ジョインが必要な表形式データに関して繰り返すステップと、
ｈ）ジョインにより結合された表形式データのうち、根となるものを選択し、前記表形式データの結合にしたがって、各表形式データの深さを決定するステップと、
ｉ）前記深さおよびレコード番号の組み合わせを値とするツリー記述テーブルのための領域を確保するステップと、
ｊ）初期的には最も浅い深さとなるような、ある深さのレコードを特定し、前記レコードを示す値を、深さとともに、前記ツリー記述テーブルのための領域に配置するステップと、
ｋ）前記特定されたレコードから、スレイブ側の表形式データのレコードを特定し、当該レコードに基づき、スレイブ側の表形式データがマスタ側となるような表形式データのレコードを示す値を、前記マスタ側の表形式データの深さとともに、前記ツリー記述テーブルのための領域に配置するステップと、
ｌ）前記ｋ）のステップを、表形式データが存在しない深さになるまで、或いは、レコードが存在しなくなるまで繰り返すステップと、
ｍ）前記ｊ）ないしｌ）のステップを繰り返すことにより、ツリー記述テーブルのための領域に、所定の深さおよびレコードを特定する値を配置することにより、ツリー記述テーブルを完成させるステップとを備えたことを特徴とする方法により達成される。
【００１２】
本発明によれば、二つの表形式データの組を、連鎖（チェイン）して、深さの浅い表形式データのレコードから、深い位置にある表形式データのレコードを、順次特定していく。これにより、深さとレコードを示す値とからなるツリー記述テーブルを作ることができる。ツリー記述テーブルの深さにより、表形式データが特定され、レコードを示す値により、当該表形式データの実際の値を取得することが可能となる。表形式データの選択や、チェインのための表形式データの組み合わせ、さらには、ルートとなる表形式データの選択は、自由である。したがって、きわめて柔軟性の高いツリー構造を構築することが可能となる。
【００１３】
また、同じ表形式データに関して、複数の異なるツリー記述テーブルを持つことができる。したがって、同じデータについて、複数のツリー構造を構築することも可能となる。
【００１４】
好ましい実施態様においては、前記ｅ）のステップにおいて、
前記値リストを等価にする際に、マスタ側の情報ブロックにおいて、その項目値の追加にともなって、前記情報ブロックのポインタ配列を指し示すための第２の射影配列を生成するステップと、
前記スレイブ側の情報ブロックにおいて、共通化された項目の値の存在する数を累計化した第３の射影配列を生成するステップと、
スレイブ側の情報ブロックにおいて、前記共通化された項目にてソートされたレコードを指し示す値の集合である第４の射影配列を生成するステップとを備え、
前記第２の射影配列、マスタ側の情報ブロックのポインタ配列、第３の射影配列および第４の射影配列を順次たどることにより、スレイブ側のレコードが特定される。
【００１５】
より好ましい実施態様においては、さらに、
ｎ）最も浅い深さの表形式データを除き、マスタ側に関する第２の射影配列の逆写像配列を生成するステップを備え、
前記第４の射影配列からの要素が指し示す逆写像配列の要素により、次の深さの表形式データにおけるマスタ側の第２の射影配列の要素が特定される。
【００１６】
さらに、逆写像を生成するステップにおいて、
前記マスタ側に関する第２の射影配列の要素数と等しい要素を収容する、逆写像のための配列を配置するステップと、
前記各要素として、レコードを特定し得ない他の値を配置するステップと、
前記第４の射影配列の位置を要素に、かつ、要素を位置とするように、前記逆写像配列に値を付与するステップとが設けられているのが望ましい。
別の好ましい実施態様においては、さらに、前記項目を共通化すべき二つの表形式データの少なくとも一方において、前記表形式データの共通化すべき項目について、検索、集計およびソートの何れかを施すステップを備えている。
上記実施態様によれば、検索、集計、ソートなどが施された表形式データを使ったツリー構造の構築が可能となる。
【００１７】
このように、本発明によれば、任意の根を選択し、かつ、所望のツリー構造を作成することができる。また、ツリー構造を作成するための基となるデータとして、検索、集計、ソートを施したものを利用することも可能となる。
【００１８】
また、本発明の目的は、各々が、項目とこれに含まれる項目値とを含むレコードの配列として表わされる複数の表形式データを結合し、結合された表形式データであるジョインテーブルをツリー構造に変換するプログラムであって、
ａ）各表形式データを、各々が、特定の項目に属する項目値に対応した項目値番号の順に当該項目値が格納されている値リストと、一意的なレコード番号の順に、当該項目値番号を指示するためのポインタ値が格納されたポインタ配列とからなる一以上の情報ブロックに分割するように構成するステップと、
ｂ）項目を共通化すべき二つの表形式データを選択するステップと、
ｃ）当該選択された二つの表形式データにおいて、共通化すべき項目を見出すステップと、
ｄ）前記特定された情報ブロックのうち、デフォルトのソート順が反映される表形式データをマスタ表形式データと決定し、それ以外の表形式データをスレイブ表形式データと決定するステップと、
ｅ）前記選択された表形式データにおいて、前記特定された情報ブロックに含まれる値リストを相互に等価にした場合に、マスタ側のレコードに対応するスレイブ側のレコードを対応付けるステップと、
ｆ）前記二つの表形式データのうちのスレイブ側の表形式データをマスタ側とするような、他の二つの表形式データを選択し、当該他の二つの表形式データについて、前記ｃ）項目を見出すステップ、ｄ）マスタ表形式データおよびスレイブ表形式データを決定するステップ、および、ｅ）対応付けるステップとを実行するステップと、
ｇ）前記ｆ）のステップを、ジョインが必要な表形式データに関して繰り返すステップと、
ｈ）ジョインにより結合された表形式データのうち、根となるものを選択し、前記表形式データの結合にしたがって、各表形式データの深さを決定するステップと、
ｉ）前記深さおよびレコード番号の組み合わせを値とするツリー記述テーブルのための領域を確保するステップと、
ｊ）初期的には最も浅い深さとなるような、ある深さのレコードを特定し、前記レコードを示す値を、深さとともに、前記ツリー記述テーブルのための領域に配置するステップと、
ｋ）前記特定されたレコードから、スレイブ側の表形式データのレコードを特定し、当該レコードに基づき、スレイブ側の表形式データがマスタ側となるような表形式データのレコードを示す値を、前記マスタ側の表形式データの深さとともに、前記ツリー記述テーブルのための領域に配置するステップと、
ｌ）前記ｋ）のステップを、表形式データが存在しない深さになるまで、或いは、レコードが存在しなくなるまで繰り返すステップと、
ｍ）前記ｊ）ないしｌ）のステップを繰り返すことにより、ツリー記述テーブルのための領域に、所定の深さおよびレコードを特定する値を配置することにより、ツリー記述テーブルを完成させるステップとを、前記コンピュータに実行させることを特徴とするプログラムによっても達成される。
【００１９】
【発明の実施の形態】
以下、添付図面を参照して、本発明の実施の形態につき説明を加える。図１は、本発明の実施の形態にかかる連鎖的な表形式データのジョイン、および、ジョインされたテーブル（ジョインテーブル）をツリー構造に変換するコンピュータシステムのハードウェア構成を示すブロックダイヤグラムである。図１に示すように、このコンピュータシステム１０は、通常のものと同様の構成であり、プログラムを実行することによりシステム全体および個々の構成部分を制御するＣＰＵ１２、ワークデータなどを記憶するＲＡＭ（Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）１４、プログラム等を記憶するＲＯＭ（Ｒｅａｄ　Ｏｎｌｙ　Ｍｅｍｏｒｙ）１６、ハードディスク等の固定記憶媒体１８、ＣＤ−ＲＯＭ１９をアクセスするためのＣＤ−ＲＯＭドライバ２０、ＣＤ−ＲＯＭドライバ２０や外部ネットワーク（図示せず）と接続された外部端子との間に設けられたインタフェース（Ｉ／Ｆ）２２、キーボードやマウスからなる入力装置２４、ＣＲＴ表示装置２６を備えている。ＣＰＵ１２、ＲＡＭ１４、ＲＯＭ１６、外部記憶媒体１８、Ｉ／Ｆ２２、入力装置２４および表示装置２６は、バス２８を介して相互に接続されている。
【００２０】
本実施の形態にかかる、表形式データを連鎖的に結合（ジョイン）するプログラム、結合されたテーブル（ジョインテーブル）をツリー構造に変換するプログラムなどは、ＣＤ−ＲＯＭ１９に収容され、ＣＤ−ＲＯＭドライバ２０に読取られても良いし、ＲＯＭ１６に予め記憶されていても良い。また、いったんＣＤ−ＲＯＭ１９から読み出したものを、外部記憶媒体１８の所定の領域に記憶しておいても良い。或いは、上記プログラムは、ネットワーク（図示せず）、外部端子およびＩ／Ｆ２２を経て外部から供給されるものであっても良い。
【００２１】
また、本実施の形態においては、ツリー構造への高速変換を実現するために、後述するように所定のデータ形式の情報ブロックを生成する必要がある。この情報ブロック生成プログラムも同様に、ＣＤ−ＲＯＭ１９に収容され、ＲＯＭ１６に記憶され、或いは、外部記憶媒体１８に記憶されても良い。或いは、これらプログラムは、ネットワーク（図示せず）を介して、外部から供給されても良いことはいうまでもない。また、本実施の形態において、情報ブロック生成プログラムにて生成されたデータ（情報ブロック）は、ＲＡＭ１４に記憶され、或いは、外部記憶媒体１８の所定の領域に記憶される。
【００２２】
本実施の形態においては、図２および図３に示すように、表形式データ（テーブル）を、所定のデータ形式により保持している。たとえば、図２（ａ）に示すように、テーブル＃０である組織テーブルは、実際の項目値である「組織名」が、５０音順（英字ではアルファベット順）でソートされて配置された値リスト（以下、場合によって「ＶＬ」と称する。）２０３と、各レコード番号に対応して、当該レコードが指し示す値リスト中の番号が格納された、値リストへのポインタ配列（以下、場合によって「ＰＶＬ」と称する。）２０２とを備えた、情報ブロック２０１により構成される。レコード番号に対応するＰＶＬ２０２中の要素が示す番号の、ＶＬ中の要素（項目値）が、当該レコードに対応する項目値となる。なお、ＰＶＬ２０２は、テーブルのレコード数だけ要素があることが理解できるであろう。
【００２３】
図２（ｂ）は、「部署」という項目の値（項目値）と、「Ｓ氏名」という項目の値（項目値）とから構成される社員所属テーブルを示している。社員所属テーブルは、情報ブロック２１１および情報ブロック２２１とから構成される。「部署」の情報ブロック２１１には、（「組織名」のＶＬと、その要素が共通する）「部署名」がソートされて格納されたＶＬ２１３と、ＶＬ２１３中の要素（部署名）を指し示すためのＰＶＬ２１２とが含まれる。また、「Ｓ氏名」の情報ブロック２２１は、氏名が、ソートされて格納されたＶＬ２２３と、ＶＬ２２３中の要素（氏名）を指し示すためのＰＶＬ２２２とが含まれる。
【００２４】
同様に、図３に示す容易、社員履歴テーブルも、「Ｒ氏名」という項目の値から構成される情報ブロック３０１と、「プロジェクト」という項目の値から構成される情報ブロック３１１とから構成される。図２（ａ）、（ｂ）に示す例と同様に、図３の例でも、情報ブロックは、それぞれ、ＰＶＬ（符号３０２、３１２参照）と、ＶＬ（３０３、３１３参照）とを含む。
【００２５】
ここで、組織テーブルと社員所属テーブルとを参照すると、組織テーブルの「組織名」と、社員所属テーブルの「部署」とを共有できることがわかる。また、社員所属テーブルと、社員履歴テーブルとを参照すると、社員所属テーブルの「Ｓ氏名」と、社員履歴テーブルの「Ｒ氏名」とを共有できることがわかる。本実施の形態においては、項目を共有させたジョインテーブルを連鎖的に生成することにより、ツリー構造を表す。以下、ツリー構造への変換処理につき、より詳細に説明を加える。
【００２６】
図４は、本実施の形態にかかるツリー構造への変換処理を示すフローチャートである。図４において、ジョイン（Ｊｏｉｎ）テーブルの作成（ステップ３０１）、２番目以降のジョイン（Ｊｏｉｎ）テーブルへの逆写像配列の付加（ステップ３０２）、および、ツリー記述テーブルのための領域の確保（ステップ３０３）が、処理の準備段階を構成する。まず、これらについて詳細に説明を加える。
なお、図２および図３に示す例では、組織テーブル、社員所属テーブル、および、社員履歴テーブルの３つのテーブルが存在する。ここでは、組織テーブルと社員所属テーブルとの間で、「組織名」（「部署」）をキーとしたジョイン（Ｊｏｉｎ＃０）が実行され、テーブルを共有する処理、および、社員所属テーブルと社員履歴テーブルとの間で、「Ｓ氏名」（「Ｒ氏名」）をキーとしたジョイン（Ｊｏｉｎ＃１）が実行される。
【００２７】
図５は、組織テーブルと社員所属テーブルとのジョインを説明する図である。ここでは、組織テーブルの項目値の順序が維持された状態で、組織テーブル（符号５０１参照）と社員所属テーブル（符号５０２参照）とがジョインされている。
図４にしたがって、まず、組織テーブルと社員所属テーブルとのジョインテーブルが生成される。図５（ａ）において、組織テーブルの項目値の順序が維持されているため、これを「マスタ側」と称し、社員所属テーブルの側を「スレイブ側」と称する。ここでは、組織テーブル５０１と、社員所属テーブル中の「部署」のテーブル５０２とがジョインされ、これがジョイン（Ｊｏｉｎ＃０）テーブルとなる。
【００２８】
図５（ｂ）に示すように、マスタ側（符号５１１参照）に関しては、当該マスタ側の各行（レコード）の重複数を累計化した配列（射影配列「ｉ」とも称する）５１２およびマスタ側の順序付き集合（射影配列「ｉｉ」とも称する）５１３とが生成される。
【００２９】
射影配列「ｉ」は、元の組織テーブル（図２（ａ））参照の行番号が繰り返される数（累計数）が表される。たとえば、１行目（行番号「０」）の要素は、「０」であり、２行目（行番号「１」）の要素は、「３」であることから、元の組織テーブルにおける行番号「０」に位置する「東京本店」という項目値の重複数は、「３−０＝３」であることがわかる。また、射影配列「ｉ」において、２行目（行番号「１」）の要素は「３」であり、３行目（行番号「２」）の要素は「５」であることから、元の組織テーブルにおける行番号「１」に対応する「大阪支店」という項目値の重複数は、「５−３＝２」であることがわかる。なお、射影配列「ｉ」の末尾（最下行）には、ジョインされたテーブルの行の総数（ジョインした組織テーブルでは「６」）が配置される。
【００３０】
射影配列「ｉｉ」は、ジョイン（共通化）した組織テーブルの行番号を指定する、元の組織テーブルの行番号が示されている。つまり、この射影配列「ｉｉ」は、共通化により項目が追加された場合に、新たな組織テーブルの行番号を指定するために利用される。射影配列「ｉ」５１２および射影配列「ｉｉ」５１３を参照することにより、ジョインされた組織テーブルに配置される値を特定することができる。たとえば、ジョインされた組織テーブル（Ｊｏｉｎ＃０）に関する行番号「０」ないし「２」の３行について、順序配列「ｉｉ」の行番号「０」の要素は、「０」である。したがって、元の組織テーブルの行番号「０」の要素、つまり、「東京本店」が、ジョインされた組織テーブル中に配置されることがわかる。
【００３１】
次に、スレイブ側（符号５２１）においては、ジョイン（Ｊｏｉｎ＃０）でキーとなった項目、つまり、「部署」の値ごとに、ジョインテーブルにおける各行の重複数を累計化した配列（射影配列「ｉｉｉ」とも称する）５２２、および、スレイブ側のジョインでキーとなった項目でソートされた順序付き集合（射影配列「ｉｖ」とも称する）５２３とが生成される。
【００３２】
スレイブ側では、ジョイン（Ｊｏｉｎ＃０）でキーとなった項目「部署」でソートされているため、射影配列「ｉｉｉ」は符号５２２にて示すものとなる。射影配列「ｉｉｉ」により、ソート順にしたがって、「部署」という項目中、項目値「大阪支店」の重複数が「２−０＝２」、項目値「東京本店」の重複数が「５−２＝３」、項目値「名古屋店」の重複数が「６−５＝１」となる。
【００３３】
また、射影配列「ｉｖ」中の値は、元の社員所属テーブルの行番号を示す。射影テーブル「ｉｉｉ」および射影テーブル「ｉｖ」により、ジョインされたテーブルの要素と、元の社員所属テーブルの要素とを対応させることができる。たとえば、「射影配列「ｉｉｉ」の行番号「０」および行番号「１」の要素を参照することにより、ソートされた「部署」という項目の最初の要素である「大阪支店」に関して、２つの要素が存在し、それぞれ、元の社員所属テーブルの行番号「１」および「５」に対応することがわかる。
【００３４】
このようにして、組織テーブルと社員所属テーブルとの間で、「組織名」という項目および「部署」という項目をキーとしたジョイン（Ｊｏｉｎ＃０）が終了すると、社員所属テーブルと社員履歴テーブルとの間で、「Ｓ氏名」という項目および「Ｒ氏名」という項目をキーとしたジョイン（Ｊｏｉｎ＃１）が実行される。
図６は、社員所属テーブルと社員履歴テーブルとのジョインを説明する図である。先に説明したジョイン（Ｊｏｉｎ＃０）と同様に、このジョインにおいても、社員所属テーブルの「Ｓ氏名」の値の順序が維持された状態となる。したがって、社員所属テーブルがマスタ側となり、社員履歴テーブルがスレイブ側となる。図６（ｂ）は、社員所属テーブル中の「Ｓ氏名」のテーブル６０１と、社員履歴テーブル中の「Ｒ氏名」のテーブル６０２とがジョインされ、これがジョイン（Ｊｏｉｎ＃１）テーブルとなる。
【００３５】
図６（ｂ）は、このジョイン（Ｊｏｉｎ＃１）におけるマスタ側６１１に関する、各行（レコード）の重複数を累計化した配列（射影配列「ｉ」）６１２、および、順序付き集合（射影配列「ｉｉ」）６１３を示す。また、図６（ｃ）は、ジョイン（Ｊｏｉｎ＃１）におけるスレイブ側６１２に関する、ジョイン（Ｊｏｉｎ＃１）でキーとなった項目「Ｒ氏名」の値ごとに、ジョインテーブルにおける各行の重複数を累計化した配列（射影配列「ｉｉｉ」）６２２、および、ジョインでキーとなった項目でソートされた順序付き集合（射影配列「ｉｖ」）６２３を示す。これらの生成は、図５に示したジョイン（Ｊｏｉｎ＃０）のものと同様である。
【００３６】
なお、最初のジョイン（Ｊｏｉｎ＃０）のスレイブ側の順序付き集合（射影配列「ｉｖ」）５２３と、２番目のジョイン（Ｊｏｉｎ＃１）のマスタ側の順序付き集合（射影配列「ｉｉ」）６１３とについて、双方の配列において、同じ値は、同じレコードを指している。これは、対象とする値（要素）が同一のテーブル（社員所属テーブル）だからである。
【００３７】
このように、ジョインテーブルの作成処理（図４のステップ４０１）により、図７に示すような組織テーブル７０１と社員所属テーブル７０３との間に介在するジョインテーブル（組織：所属テーブルＪｏｉｎ＃１）７０２が作られ、社員所属テーブル７０３と社員履歴テーブル７０５との間に介在するジョインテーブル（所属：履歴テーブルＪｏｉｎ＃１）７０４が作られる。さらに、社員履歴テーブルと、さらに、ジョインすべきテーブルが存在すれば、これらの間に介在する他のジョインテーブル（Ｊｏｉｎ＃２）が作られることは言うまでもない。
【００３８】
ジョインテーブルの作成が完了すると、最初のジョインテーブル以外のジョインテーブル、つまり、２番目以降のジョインテーブルについて、逆写像配列を生成して、これを付加する（ステップ４０２）。逆写像配列は、配列中の値により、もとの配列を示す番号を指定するものである。
図８に示すように、逆写像配列を作成するためには、逆写像の元になる配列（写像配列「ｉｉ」）と同じレコード数の配列の領域８００を確保し（図８（ａ）参照）、当該配列中の要素として、レコードを示す番号となり得ない値（たとえば、「−１」）を与える（図８（ｂ）参照）。次いで、元の配列（射影配列「ｉｉ」６１３）の値が指し示す番号の要素に、元の配列の番号（レコード番号）を配置する（図８（ｃ）参照）。このようにして、図８（ｃ）の右端にあるような、最終的な写像配列８００を得ることが可能となる。
【００３９】
次いで、ツリー記述テーブルのための領域が確保される（ステップ４０３）。図１０は、ツリー記述テーブルの例を示す図である。ツリー記述テーブルは、複数の、深さ（Ｄｅｐｔｈ）とレコード番号（Ｒｅｃ　Ｎｏ）との組み合わせから構成される。初期的には、それぞれの項目には、値が付与されず、以下に説明する処理により、順次、値が付与されていく。深さとは、ツリーノードの深さを表す。図７に示す例においては、「組織テーブル」、「社員所属テーブル」、「社員履歴テーブル」の深さは、それぞれ、「０（ゼロ）」、「１」、「２」である。
【００４０】
本実施の形態においては、ツリー構造を記述したツリー記述テーブルを作成するために、図９に示すように、確保されたツリー記述テーブルのための領域と、第１のジョイン（Ｊｏｉｎ＃０）、つまり、組織テーブルと社員所属テーブルとの間のジョインに関する第１の配列群９１０と、第２のジョイン（Ｊｏｉｎ＃１）、つまり、社員所属テーブルと社員履歴テーブルとの間のジョインに関する第２の配列群９２０と、これらの間を結びつける逆写像配列９２１とが利用される。
【００４１】
第１の配列群９１０は、第１のジョイン（Ｊｏｉｎ＃０）の順序付集合（射影配列「ｉｉ」）９１１、ジョインキーのＰＶＬ９１２、累計数配列（射影配列「ｉｉｉ」）９１３および順序付集合（射影配列「ｉｖ」）９１４を含む。また、第２の配列群９２０も、同様に、第２のジョイン（Ｊｏｉｎ＃１）の順序付集合（射影配列「ｉｉ」）９２２、ジョインキーのＰＶＬ９２３、累計数配列（射影配列「ｉｉｉ」）９２４および順序付集合（射影配列「ｉｖ」）９２５を含む。
【００４２】
まず、深さが「０（ゼロ）」に初期化された後（ステップ４０４）、現在の深さの要素が取得される（ステップ４０５）。要素が取得された場合には（ステップ４０６でイエス（Ｙｅｓ））、現在の深さの要素が、その深さとともにツリー記述テーブルに登録される（ステップ４０７）。上記例では、「組織テーブル」中の要素が取得される。図１１において、順序付集合（射影配列「ｉｉ」）の先頭（行番号「０」）の要素が、その深さ「０」とともに、ツリー記述テーブルの最初の要素として配置される（符号１０００参照）。
【００４３】
次いで、「子」がいるか否かが判断される（ステップ４０８）。ここに、「子」とは、ある深さのテーブル（たとえば、深さ「０」のテーブル（組織テーブル））の順序付集合（射影配列「ｉｉ」）から配列をたどることで達する、次の深さのテーブル（たとえば、深さ「１」のテーブル）中の順序付集合（射影配列「ｉｉ」）中の対応する要素（つまり、次の深さのテーブルのレコード番号）をいう。図１１の例では、図１２に示すように、順序付集合（射影配列「ｉｉ」）の行番号「０」の要素「０」は、深さ「０」のテーブル（組織テーブル）のＰＶＬ、累計数配列（射影配列「ｉｉｉ」）および順序付集合（射影配列「ｉｖ」）、並びに、逆写像配列および深さ「１」のテーブル（社員所属テーブル）の順序付集合（射影配列「ｉｉ」）を順にたどっていくことで、要素が存在することがわかる。したがって、ステップ４０８でイエス（Ｙｅｓ）と判断される。
【００４４】
この場合には、深さがインクリメントされ（ステップ４０９）、当該深さ（上記例では「１」）の要素が取得され、深さ（上記例では「１」）とともに、取得された要素が、ツリー記述テーブルの次の要素として配置される（符号１００１参照）。なお、最初のジョイン（Ｊｏｉｎ＃０）における射影配列「ｉｖ」の要素、および、これに引き続いているジョイン（Ｊｏｉｎ＃１）における射影配列「ｉｉ」の要素は、双方とも、同じテーブルのレコードを指している。したがって、これらが同一であれば、同じレコードを指していることに留意されたい。
【００４５】
図１２において、深さ「０」のテーブル（組織テーブル）の累計数配列（射影配列「ｉｉｉ」）において、行番号「１」の要素「２」と、次の行番号「２」の要素「５」とから、３個の要素が存在することがわかる（符合１２０１参照）。つまり、この深さ「０」において、上記累計数配列の行番号「１」の要素は、次に位置する順序付集合（射影配列「ｉｖ」）の行番号「２」、「３」、「４」の３つを指し示していることがわかる。なお、図１２以降、累計数配列（射影配列「ｉｉｉ」）の右側に付与された矢印は、矢印の先に位置する要素と、矢印の元に位置する要素との差だけ、矢印の元に位置する要素が指し示すことができる、順序付集合（射影配列「ｉｖ」）の要素が存在することを意味している。
【００４６】
次いで、さらに深さがインクリメントされ（ステップ４０９）、次の深さの要素が取得される（ステップ４０５）。図１２の例に関しては、深さがインクリメントされて「２」となり、深さ「１」のテーブルの順序付集合（射影配列「ｉｉ」）、ＰＶＬ、累計数配列（射影配列「ｉｉｉ」）および順序付集合（射影配列「ｉｖ」）をたどる。図１３に示すように、順序付集合（射影配列「ｉｉ」）の行番号「０」の要素をたどると、最終的に、順序付集合（射影集合「ｉｖ」）の行番号「０」、「１」のそれぞれの要素「０」、「７」が取り出される。これは、累計数配列（射影配列「ｉｉｉ」の関連する要素が「０」で、かつ、次の行番号の要素が「２」であるため、要素が「２−０＝２」だけあることがわかるからである。したがって、これら順序付集合（射影配列「ｉｖ」）の行番号「０」および「１」の要素、「０」および「７」が、それぞれ、深さ「２」とともに、ツリー記述テーブルの要素として配置される（符号１００２、１００３参照）。
【００４７】
これ以上の深さ（深さ「３」）は存在しないため、深さ方向の探索が終了する。つまり、ステップ４０５〜ステップ４０９のループにおいて、次のステップ４０６においてノー（Ｎｏ）と判断され、深さがデクリメントされる（ステップ４１０）。つまり、ひとつ浅い深さに戻り、当該深さが「０」以上であれば処理が続行される（ステップ４１１参照）。
【００４８】
上記例では、深さが「２」から「１」になるため、当該深さ「１」の要素が再度取得される。図１２の符号１２０１に関連して説明したように、深さ「１」の累計数配列（射影配列「ｉｉｉ」）に関して、３つの要素が存在することがわかっている。これらのうち、２つ目の要素および３つ目の要素については未処理である。したがって、次のステップ４０５においては、上記２つめの要素に基づいて処理が実行される。図１４に示すように、順序付集合（射影配列「ｉｖ」）の２つ目の要素（行番号「２」の次に位置する行番号「３」の要素）から、逆写像配列、および、次の順序付集合（射影配列「ｉｉ」）がたどられ、対応する要素が取得される。これが、深さ「１」とともに、ツリー記述テーブルの要素として配置される（符号１００４参照）。
【００４９】
さらに、深さがインクリメントされて（ステップ４０９参照）、深さ「２」の要素を取得する処理が実行される。図１５に示すように、順序付集合（射影配列「ｉｉ」）、ＰＶＬ、累計数配列（射影配列「ｉｉｉ」）および順序付集合（射影配列「ｉｖ」）をたどることで、深さ「２」の要素が取得される。なお、累計数配列に配置された矢印から理解できるように、ここでは、２つの要素が取得される。取得された要素は、それぞれ、深さ「２」とともに、ツリー記述テーブルの要素として配置される（符号１００５、１００６）。なお、深さ「３」は存在しないため、深さ方向の探索は終了する。
【００５０】
同様に、図１６に示すように、深さ「１」の３つ目の要素（順序付集合（射影配列「ｉｖ」の行番号「４」の要素）から、逆写像配列および順序付集合（射影配列「ｉｉ」）をたどることで、深さ「１」の要素を取得することができる。これも、その深さ「１」とともにツリー記述テーブルに配置される（符号１００７参照）。さらに、図１７に示すように、深さ「２」に関しても、配列をたどることにより、要素が取得され、その深さ「２」とともに、ツリー記述テーブルに配置される（符号１００８参照）。なお、ここでも、深さ「３」は存在しないため、深さ方向の探索は終了する。
【００５１】
このような終了の後は、深さをデクリメントして「１」としても要素が取得できないため（ステップ４１０、４１１、４１５および４０６）、さらに深さがデクリメントされて「０」とされて、深さ「０」の要素が取得される。図１８に示すように、順序付集合（射影配列「ｉｉ」）の次（つまり、行番号「１」）の要素「１」が、ツリー記述テーブルに登録すべき要素となる。したがって、深さ「０」とともに、これがツリー記述テーブルに配置される（符号１００９参照）。その後、図４、および、図１１ないし図１８を参照して説明したものと同様に、深さ方向への順次探索、および、要素のツリー記述テーブルへの配置が繰り返される。
【００５２】
図１９は、このような処理を続けた結果、最終的なツリー記述テーブルの要素が取得された状態を示す図である。ここに示す処理は、図示しない先の処理にて、深さ「１」の要素をツリー記述テーブルに配置したことに引き続いて実行される。ツリー記述テーブルに配置された要素は、当該深さ「１」に関する「Ｊｏｉｎ＃１」側の順序付集合（射影配列「ｉｉ」）と共通の意味を持つ。したがって、この要素をたどることで、深さ「２」の要素を探索することができる。
図１９の例では、順序付集合（射影配列「ｉｉ」）の行番号「２」の要素「２」から、ＰＶＬおよび累計数配列（射影配列「ｉｉｉ」）をたどり、順序付集合（射影配列「ｉｖ」）の行番号「４」の要素である「４」が取得され、これが、深さ「２」とともに、ツリー記述テーブルに配置される。
【００５３】
このようにして完成したツリー記述テーブル９００の意味につき、図２０を参照して説明する。前述したように、ツリー記述テーブル９００には、深さ（Ｄｅｐｔｈ）とレコード番号（Ｒｅｃ　Ｎｏ）との組み合わせが配置されている。たとえば、深さの項目の値は、それがどの深さのテーブルに関連するかを特定し、かつ、レコード番号は、深さにて特定されたテーブルのレコード番号を特定している。
【００５４】
たとえば、ツリー記述テーブルの最初の要素の組み合わせ（０，０）により、深さ「０」のテーブル（組織テーブル）の、レコード番号「０」の要素、つまり、「東京本店」が示される。また、これに引き続く要素の組み合わせ（１，０）により、深さ「１」のテーブル（社員所属テーブル）のレコード番号「０」の要素、つまり、「東京本店」および「Ａ氏」を示している。同様に、さらに引き続く要素の組み合わせ（２，０）、（２，７）は、それぞれ、深さ「２」のテーブル（社員履歴テーブル）の、それぞれ、レコード番号「０」および「７」の要素、つまり、「Ａ氏」および「Ｐｒｊ−１」、並びに、「Ａ氏」および「Ｐｒｊ−４」を示すことになる。このように、ツリー記述テーブルは、複数のジョインされたテーブルをツリー構造にて記述したことが理解できるであろう。
このように、本実施の形態によれば、所望のテーブルを指定することで、上述した処理により、ツリー記述テーブルを作成し、ジョインされたテーブルをツリー構造にて記述することが可能となる。
【００５５】
次に、本発明の第２の実施の形態につき説明を加える。第１の実施の形態においては、表形式データの全体集合をジョインしたもののツリー記述テーブルを生成したが、第２の実施の形態では、一部の表形式データを、所定の項目で検索し、かつ、ソートした部分集合を用いている。なお、第２の実施の形態においても、システムのハード構成（図１）およびツリー構造への変換処理の概略（図４）については、第１の実施の形態のものとほぼ同様である。
【００５６】
図２１〜図２２は、第２の実施の形態にかかる表形式データ（テーブル）の例を示す図である。第２の実施の形態においては、組織テーブルおよび社員履歴テーブルは、第１の実施の形態と同様のものを利用し（図２１の符号２０１および図２３の符号３０１，３１１参照）、かつ、ジョインの対象は全体集合としている（図２１の符号２１０１および図２３の符号２３０１参照）。その一方、社員所属テーブル自体は、第１の実施の形態のものと同様であるが（図２２の符号２１１、２２１参照）が、テーブルを「部署」の項目の「大阪支店」、「名古屋支店」でＯＲ検索し（図２２の符号２２０２参照）、かつ、項目「Ｓ氏名」でソートしている（図２２の符号２２０３参照）。
【００５７】
これら表形式データの間で、「組織名」（「部署」）をキーとしたジョイン（Ｊｏｉｎ＃０）は、全体集合（符号２１０１、２２０１参照）の間のジョインであり、その一方、「Ｓ氏名」（「Ｒ氏名」）をキーとしたジョイン（Ｊｏｉｎ＃１）は、検索およびソートされた部分集合（図２２の符号２２０３参照）と全体集合（図２３の符号２３０１参照）との間のジョインとなる。
【００５８】
「組織名」（「部署」）をキーとしたジョイン（Ｊｏｉｎ＃０）に関して作成される配列は、全体集合に関するものであるため、図５に示すものと同様になる。その一方、「Ｓ氏名」（「Ｒ氏名」）をキーとしたジョイン（Ｊｏｉｎ＃１）は、図２４に示すようなものとなる。図２４に示すように、このジョイン（Ｊｏｉｎ＃１）では、項目「部署」の「大阪支店」、「名古屋店」でＯＲ検索され、項目「Ｓ氏名」でソートされた社員所属テーブル（マスタ側）２４０１、および、上記ＯＲ検索により抽出された「Ｓ氏名」と同一の「Ｒ氏名」をもつような社員履歴テーブル（スレイブ側）２４０２に関連して種々の配列が作成される。
【００５９】
図２４（ｂ）に示すように、マスタ側に関しては、マスタ側の各行の重複数を類型化した射影配列「ｉ」２４１２、および、マスタ側の順序付き集合である射影配列「ｉｉ」２４１３が生成される。その一方、図２４（ｃ）に示すように、スレイブ側に関しては、ジョイン（Ｊｏｉｎ＃１）でキーとなった項目、つまり、「Ｒ氏名」の値ごとに、ジョインテーブルにおける各行の重複数を累計化した配列である射影配列「ｉｉｉ」２４２２、および、上記キーとなった項目でソートされた順序付き集合である射影配列「ｉｖ」２４２３が生成される。これら各種配列およびその要素が示す意味については、図５および図６を参照して説明した、第１の実施の形態のものと同様である。
【００６０】
次いで、逆写像配列の作成（図４のステップ４０２）につき説明を加える。逆写像配列の作成も、基本的には第１の実施の形態と同様である。ただし、逆写像配列の要素数は、社員所属テーブル（マスタ側）の全レコード数に対応する（図２５（ａ）参照）。次いで、図２５（ｂ）に示すように、第１の実施の形態と同様に、各要素に、レコード番号となり得ない値（たとえば、「−１」）を付与し、その後、図２５（ｃ）に示すように、元の配列の値が指し示す番号の要素に、元の配列の番号（レコード番号）を配置する。これにより、図２５（ｃ）の右端に示すような逆写像配列２５００を得ることができる。第２の実施の形態においては、逆写像配列の要素中、レコード番号を示していないものが含まれることに留意すべきである。
【００６１】
このようにして、種々の射影配列および逆写像配列が生成された後に、図４のステップ４０４〜４１１の処理が繰り返され、ツリー記述テーブルが出来上がる。図２６は、ツリー記述テーブルを作成するために利用される配列群などを示す図である。図２６に示すように、ツリー記述テーブルを作成するために、確保されたツリー記述テーブルのための領域と、第１のジョイン（Ｊｏｉｎ＃０）、つまり、組織テーブルと社員所属テーブルとの間のジョインに関する第１の配列群２６１０と、第２のジョイン（Ｊｏｉｎ＃１）、つまり、社員所属テーブルと社員履歴テーブルとの間のジョインに関する第２の配列群２６２０と、これらの間を結びつける逆写像配列２６２１とが利用される。
【００６２】
第１の配列群２６１０は、図９に示す第１の配列群９１０と同様であり、第１のジョイン（Ｊｏｉｎ＃０）の順序付集合（射影配列「ｉｉ」）２６１１、ジョインキーのＰＶＬ２６１２、累計数配列（射影配列「ｉｉｉ」）２６１３および順序付集合（射影配列「ｉｖ」）２６１４を含む。また、第２の配列群２６２０も、同様に、第２のジョイン（Ｊｏｉｎ＃１）の順序付集合（射影配列「ｉｉ」）２６２２、ジョインキーのＰＶＬ２６２３、累計数配列（射影配列「ｉｉｉ」）２６２４および順序付集合（射影配列「ｉｖ」）２６２５を含む。
【００６３】
図２７に示すように、ツリー記述テーブル２６００においては、深さ（Ｄｅｐｔｈ）およびレコード番号（Ｒｅｃ　Ｎｏ）の組み合わせが、順次配置されていく。
ツリー記述テーブルに要素を配置する処理においては、まず、深さが「０（ゼロ）」に初期化された後（図４のステップ４０４）、現在の深さの要素が取得され、これが、深さとともに配置される（ステップ４０５〜４０７）。図２８に示すように、初期的には、第１のジョイン（Ｊｏｉｎ＃０）の順序付集合（射影配列「ｉｉ」）の行番号「０」の要素が、ツリー記述テーブル２６００の最初の要素として配置される（符号２７００参照）。
【００６４】
次いで、図４にしたがって、「子」がいるか否かが判断される（ステップ４０８）。図２９に示すように、第１のジョイン（Ｊｏｉｎ＃０）に関して、順序付集合（射影配列「ｉｉ」）の行番号「０」の要素から、ＰＶＬ、累計数配列（射影配列「ｉｉｉ」）および順序付集合（射影配列「ｉｖ」）の対応する要素をたどった結果、指し示される逆写像配列の３つの要素がすべて「−１」となる。前述したように逆写像配列の要素「−１」は、レコードが存在しないことを示しているため、この場合には、第２のジョイン（Ｊｏｉｎ＃１）に関して、「子」となる要素が存在していないことになる（符合２９０１参照）。
【００６５】
したがって、図４の処理においては、ステップ４０８でノー（Ｎｏ）と判断され、同じ深さ「０」の次の要素が取得される（ステップ４０５参照）。上記例では、図３０に示すように、順序付集合（射影配列「ｉｉ」）の行番号「１」の要素「１」が、その深さ「０」とともにツリー記述テーブルに配置される（符号２７０１参照）。
【００６６】
次いで、「子」となる要素の有無が判断される。上記順序付集合（射影配列「ｉｉ」）の要素から、ＰＶＬ、累計数配列（射影配列「ｉｉｉ」）、順序付集合（射影配列「ｉｖ」）、および、逆写像配列の対応する要素をたどった結果、第２のジョイン（Ｊｏｉｎ＃１）の順序付集合（射影配列「ｉｉ」）の要素が特定される。したがって、この順序付集合（射影配列「ｉｉ」）の行番号「１」の要素「１」が、その深さ「１」とともに、ツリー記述テーブルに配置される（符号２７０２参照）。
【００６７】
さらに、「子」となる要素の有無が判断される。上記例では、第２のジョイン（Ｊｏｉｎ＃１）の順序付集合の要素から、ＰＶＬ、累計数配列（射影配列「ｉｉｉ」）、および、順序付集合（射影配列「ｉｖ」）の要素が特定され、順序付集合（射影配列「ｉｖ」）の２つの要素が、それぞれ、その深さ「２」とともに、ツリー記述テーブルに配置される（符号２７０３、２７０４参照）。
【００６８】
このような処理を繰り返すことにより、図２７に示すようなツリー記述テーブルを完成させることができる。このようにして完成されたツリー記述テーブルの意味も、図２０を参照して説明した第１の実施の形態のものと同様である。図３３に示すように、ツリー記述テーブルの深さの項目の値は、どの深さのテーブルに関連するかを特定し、かつ、対応するレコード番号は、深さにて特定されたテーブルのレコード番号を特定している。
【００６９】
図３３において、たとえば、最初の要素の組み合わせ（０，０）により、深さ「０」のテーブル（組織テーブル）の、レコード番号「０」の要素、つまり、「東京本店」が示される。また、これに引き続く、要素の組み合わせ（０，１）により、深さ「０」のテーブル（組織テーブル）の、レコード番号「１」の要素、つまり、「大阪支店」が示される。同様に、さらに引き続く要素の組み合わせ（１，１）および（２，１）により、深さ「１」のテーブル（社員所属テーブル）および深さ「２」のテーブル（社員履歴テーブル）の、それぞれ、レコード番号「１」および「１」の要素、つまり、「大阪支店」および「Ｄ氏」、並びに、「Ｄ氏」および「Ｐｒｊ−１」が示される。
【００７０】
これら実施の形態によれば、任意のノードをルートに設定して、ツリー構造を構築することが可能となる。たとえば、第２の実施の形態においては、図３４の符号３４００に示すようなツリー構造を構築することができた。本実施の形態を利用することで、任意の項目をルートとしてツリー構造を再構築することができる。たとえば、図３４のうち、社員所属テーブルの行番号「１」のレコードである「大阪支店」および「Ｄ氏」をルートと選択して、新たなツリー構造３４１０を構築することも可能である。
【００７１】
ツリー構造を構築する場合には、親ノード群となるレコード群（表形式データ）と、子ノード群となるレコード群（表形式データ）とを選択し、これらをジョインさせればよい。これを所望の回数だけ連鎖的に繰り返した後、ツリー記述テーブルを作成することにより、任意の深さのツリー構造を構築することが可能となる。
【００７２】
第１および第２の実施の形態によれば、非常に高速に、複数の表形式データをジョインさせることで、ツリー構造を構築することができる。たとえば、「Ｐｅｎｔｉｕｍ（登録商標）４」プロセッサ（１．８ＧＨｚ）を利用すると、ジョインに関する種々の配列の作成を除き、１０００万行／秒ほどの速度で、ツリー記述テーブルに、値を配置することが可能となる。これは、従来の１００〜１０００倍程度の速さである。
【００７３】
また、図３４を参照して説明したように、任意のノードをルートとしたツリー構造を構築することができ、非常に高い柔軟性を備えている。また、ツリー記述テーブルによりツリー構造が表されるため、同じ表形式データによる複数の異なるツリー構造を保持することが可能となる。たとえば、社員名簿を、所属部署によるツリーで表現するとともに、出生地域によるツリーで表現することが可能となる。
【００７４】
さらに、ソートや集計を組み合わせることができる（第２の実施の形態参照）。
また、従来のツリー構造と比較して、使用するメモリ領域をコンパクトにすることが可能となる。たとえば、ＸＭＬデータベースにおいては、ノードの接続情報にパス名を表す文字列を埋め込むため、著しく多量なメモリ領域を必要とする。その一方、本実施の形態によれば、ツリー記述テーブルによりツリー構造を記述することができる。本発明者の実験によれば、株価情報に関して、ＸＭＬデータベースと比較して、１／５のメモリ量にてツリー構造を表現できた。
【００７５】
本発明は、以上の実施の形態に限定されることなく、特許請求の範囲に記載された発明の範囲内で、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
たとえば、前記実施の形態においては、３つの表形式データを、連鎖的にジョインしているが、連鎖の数はこれに限定されるものでないことは言うまでもない。
また、第１の実施の形態において、あるジョインと引き続くジョインとの間に、逆写像配列を介在させている。しかしながら、表形式データの全体集合をそのまま利用する場合には、この逆写像配列を省略しても良い。
【００７６】
さらに、前記実施の形態においては、一般のコンピュータシステム１０内に、所定のプログラムを読み込み、当該プログラムを実行することにより、複数の表形式データのジョインおよびジョインされた表形式データに関する処理を実現しているが、本発明はこれに限定されるものではなく、パーソナルコンピュータ等のような一般のコンピュータシステムに、データベース処理専用のボードコンピュータを接続し、当該ボードコンピュータが上記処理を実行できるように構成しても良いことは言うまでもない。したがって、本明細書において、手段とは必ずしも物理的手段を意味するものではなく、各手段の機能が、ソフトウェアおよび／またはハードウェアによって実現される場合を包含する。さらに、一つの手段の機能が、二つ以上の物理的手段により実現されても、若しくは、二つ以上の手段の機能が、一つの物理的手段により実現されてもよい。
【００７７】
本発明は、たとえば、ＲＤＢにて保持される部品リストに基づき、部品表（ＢＯＭ）を作成するための処理（ＢＯＭ展開）などに利用することができる。また、本発明は、分流や合流を特徴とするフローにおいて、これを体系的に手際よく管理することが可能となる。たとえば、
ある食品（たとえば、畜肉）が、一頭ごとにどの部位がどのような経路を経て、そこで販売されたかを管理する場合に、これはツリー状のデータとなる。一般に、第１次産業や第２次産業において作られた生産物は、消費されるか、或いは、形を変えるまで、ツリー状に拡散をしていく。本発明は、このように、分流する状態を示すツリー構造を構築し、これを管理することが可能となる。また、本発明によれば、時間の経過に伴いツリーが伸張する状態を、ツリー記述テーブルを作成することにより把握することが可能となる。
【００７８】
その一方、ある工業製品を生産するために、様々な部品、エネルギーおよびサービスを購入する場合にも、ツリー状のデータとなる。たとえば、自動車（最終製品）を生産するために、ある部品会社から点火プラグを購入し、部品会社は、電力会社から電力を購入するとともに、点火プラグの部品であるセラミックを、他の部品会社から購入する。このように、時間を遡るのにしたがって、ツリーが拡散する。本発明では、このような合流する状態を示すツリー構造を構築し、これを管理することも可能となる。
【００７９】
【発明の効果】
本発明によれば、任意の根を選択して、所望の１以上のツリー構造を高速に構築することができ、検索、集計、ソートが高速に実行できる方法およびプログラムを提供することが可能となる。
【図面の簡単な説明】
【図１】図１は、本発明の実施の形態にかかるツリー構造の構築方法を実現できるコンピュータシステムのハードウェア構成を示すブロックダイヤグラムである。
【図２】図２は、表形式データの例、および、当該表形式データに基づく情報ブロックの例を示す図である。
【図３】図３は、表形式データの例、および、当該表形式データに基づく情報ブロックの例を示す図である。
【図４】図４は、本実施の形態にかかるツリー構造への変換処理を示すフローチャートである。
【図５】図５は、組織テーブルと社員所属テーブルとのジョインを説明する図である。
【図６】図６は、本実施の形態にかかる社員所属テーブルと社員履歴テーブルとのジョインを説明する図である。
【図７】図７は、本実施の形態にかかるジョインの連鎖（チェイン）の例を示す図である。
【図８】図８は、本実施の形態にかかる逆写像配列の生成を説明する図である。
【図９】図９は、本実施の形態にかかるツリー記述テーブルの生成に利用する種々の配列を示す図である。
【図１０】図１０は、本実施の形態にかかるツリー記述テーブルの例を示す図である。
【図１１】図１１は、第１の実施の形態にかかるツリー記述テーブルに値を配置する処理を説明するための図である。
【図１２】図１２は、第１の実施の形態にかかるツリー記述テーブルに値を配置する処理を説明するための図である。
【図１３】図１３は、第１の実施の形態にかかるツリー記述テーブルに値を配置する処理を説明するための図である。
【図１４】図１４は、第１の実施の形態にかかるツリー記述テーブルに値を配置する処理を説明するための図である。
【図１５】図１５は、第１の実施の形態にかかるツリー記述テーブルに値を配置する処理を説明するための図である。
【図１６】図１６は、第１の実施の形態にかかるツリー記述テーブルに値を配置する処理を説明するための図である。
【図１７】図１７は、第１の実施の形態にかかるツリー記述テーブルに値を配置する処理を説明するための図である。
【図１８】図１８は、第１の実施の形態にかかるツリー記述テーブルに値を配置する処理を説明するための図である。
【図１９】図１９は、第１の実施の形態にかかるツリー記述テーブルに値を配置する処理を説明するための図である。
【図２０】図２０は、第１の実施の形態にかかるツリー記述テーブルにより構築されたツリー構造を説明するための図である。
【図２１】図２１は、表形式データの他の例、および、当該表形式データに基づく情報ブロックの例を示す図である。
【図２２】図２２は、表形式データの他の例、および、当該表形式データに基づく情報ブロックの例を示す図である。
【図２３】図２３は、表形式データの他の例、および、当該表形式データに基づく情報ブロックの例を示す図である。
【図２４】図２４は、第２の実施の形態にかかる社員所属テーブルと社員履歴テーブルとのジョインを説明する図である。
【図２５】図２５は、第２の実施の形態にかかる逆写像配列の生成を説明する図である。
【図２６】図２６は、第２の実施の形態にかかるツリー記述テーブルの生成に利用する種々の配列を示す図である。
【図２７】図２７は、第２の実施の形態にかかるツリー記述テーブルを示す図である
【図２８】図２８は、第２の実施の形態にかかるツリー記述テーブルに値を配置する処理を説明するための図である。
【図２９】図２９は、第２の実施の形態にかかるツリー記述テーブルに値を配置する処理を説明するための図である。
【図３０】図３０は、第２の実施の形態にかかるツリー記述テーブルに値を配置する処理を説明するための図である。
【図３１】図３１は、第２の実施の形態にかかるツリー記述テーブルに値を配置する処理を説明するための図である。
【図３２】図３２は、第２の実施の形態にかかるツリー記述テーブルに値を配置する処理を説明するための図である。
【図３３】図３３は、第２の実施の形態にかかるツリー記述テーブルにより構築されたツリー構造を説明するための図である。
【図３４】図３４は、本発明にかかるツリー構造のさらに他の例を示す図である。
【符号の説明】
１０　　　　コンピュータシステム
１２　　　　ＣＰＵ
１４　　　　ＲＡＭ
１６　　　　ＲＯＭ
１８　　　　固定記憶装置
２０　　　　ＣＤ−ＲＯＭドライバ
２２　　　　Ｉ／Ｆ
２４　　　　入力装置
２６　　　　表示装置
【図１】
2004145640.tif 000003
【図２】
2004145640.tif 000004
【図３】
2004145640.tif 000005
【図４】
2004145640.tif 000006
【図５】
2004145640.tif 000007
【図６】
2004145640.tif 000008
【図７】
2004145640.tif 000009
【図８】
2004145640.tif 000010
【図９】
2004145640.tif 000011
【図１０】
2004145640.tif 000012
【図１１】
2004145640.tif 000013
【図１２】
2004145640.tif 000014
【図１３】
2004145640.tif 000015
【図１４】
2004145640.tif 000016
【図１５】
2004145640.tif 000017
【図１６】
2004145640.tif 000018
【図１７】
2004145640.tif 000019
【図１８】
2004145640.tif 000020
【図１９】
2004145640.tif 000021
【図２０】
2004145640.tif 000022
【図２１】
2004145640.tif 000023
【図２２】
2004145640.tif 000024
【図２３】
2004145640.tif 000025
【図２４】
2004145640.tif 000026
【図２５】
2004145640.tif 000027
【図２６】
2004145640.tif 000028
【図２７】
2004145640.tif 000029
【図２８】
2004145640.tif 000030
【図２９】
2004145640.tif 000031
【図３０】
2004145640.tif 000032
【図３１】
2004145640.tif 000033
【図３２】
2004145640.tif 000034
【図３３】
2004145640.tif 000035
【図３４】
2004145640.tif 000036