(57)【特許請求の範囲】
【請求項１】
第１のテーブルに含まれる第１のレコードのキーが、第２のテーブルに含まれる複数のレコードのキーを登録したトライ木に登録されている場合、該第１のレコードと、該第１のレコードのキーを含み該第２のテーブルに含まれる第２のレコードとを用いて第３のレコードを生成し、
前記複数のレコードにそれぞれ対応する前記トライ木の複数の葉への複数のリンクを格納する配列から、前記第２のレコードに対応する葉へのリンクを削除し、
前記第１のテーブルに含まれる第４のレコードのキーが前記トライ木に登録されていない場合、該第４のレコードを用いて第５のレコードを生成し、
前記配列中に残されたリンクによりリンクされる葉に対応する前記第２のテーブルに含まれる第６のレコードを用いて第７のレコードを生成し、
前記第３、第５、及び第７のレコードを出力する
処理をコンピュータに実行させるプログラム。
【請求項２】
前記配列は、前記複数のリンクを複数のインデクスの位置にそれぞれ格納し、前記トライ木の複数の葉は、それぞれ対応するインデクスの値を有し、前記第２のレコードに対応する葉へのリンクを削除する処理は、前記第１のレコードのキーに対応する前記トライ木の葉が有するインデクスの値に基づいて、該配列の対応するインデクスの位置に格納されたリンクを削除することを特徴とする請求項１記載のプログラム。
【請求項３】
前記第２のレコードに対応する葉へのリンクを削除する処理は、前記配列の対応するインデクスの位置に格納されたリンクをＮＵＬＬに変更し、前記第７のレコードを生成する処理は、該配列に格納されたＮＵＬＬ以外のリンクによりリンクされる葉に対応する前記第６のレコードを用いて前記第７のレコードを生成することを特徴とする請求項２記載のプログラム。
【請求項４】
第１のテーブルと第２のテーブルからレコードを生成するテーブル処理装置であって、
前記第２のテーブルに含まれる複数のレコードのキーを登録したトライ木と、該複数のレコードにそれぞれ対応する該トライ木の複数の葉への複数のリンクの配列とを格納する格納手段と、
前記第１のテーブルに含まれる第１のレコードのキーが前記トライ木に登録されている場合、該第１のレコードと、該第１のレコードのキーを含み該第２のテーブルに含まれる第２のレコードとを用いて第３のレコードを生成し、前記配列から該第２のレコードに対応する葉へのリンクを削除し、前記第１のテーブルに含まれる第４のレコードのキーが前記トライ木に登録されていない場合、該第４のレコードを用いて第５のレコードを生成し、前記配列中に残されたリンクによりリンクされる葉に対応する前記第２のテーブルに含まれる第６のレコードを用いて第７のレコードを生成するレコード生成手段と、
前記第３、第５、及び第７のレコードを出力する出力手段と
を備えることを特徴とするテーブル処理装置。
【請求項５】
コンピュータによって実行されるテーブル処理方法であって、
第１のテーブルに含まれる第１のレコードのキーが、第２のテーブルに含まれる複数のレコードのキーを登録したトライ木に登録されている場合、該第１のレコードと、該第１のレコードのキーを含み該第２のテーブルに含まれる第２のレコードとを用いて第３のレコードを生成し、
前記複数のレコードにそれぞれ対応する前記トライ木の複数の葉への複数のリンクを格納する配列から、前記第２のレコードに対応する葉へのリンクを削除し、
前記第１のテーブルに含まれる第４のレコードのキーが前記トライ木に登録されていない場合、該第４のレコードを用いて第５のレコードを生成し、
前記配列中に残されたリンクによりリンクされる葉に対応する前記第２のテーブルに含まれる第６のレコードを用いて第７のレコードを生成し、
前記第３、第５、及び第７のレコードを出力する
ことを特徴とするテーブル処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、テーブル処理装置、テーブル処理方法、及びプログラムに関する。
【背景技術】
【０００２】
データベースシステムのデータや情報処理装置（コンピュータ）のファイル等において、コード化されたカラムを名称に置き換えたり、異なる複数の種類のレコードを連結して１つのレコードを生成したりすることがある。コード化されたカラムを名称に置き換える例としては、例えば、テーブルの都道府県番号を都道府県名称に置き換える場合が挙げられ、情報処理装置のファイルとしては、例えば、Extensible Markup Language（ＸＭＬ）形式やComma Separated Values（ＣＳＶ）形式のファイルが挙げられる。
【０００３】
ソートされていない２つのテーブルを結合して１つのテーブルを生成する方法としては、等価結合と非等価結合がある。等価結合では、２つのテーブルに含まれるレコードのキーとなる項目（フィード）の文字列が一致する場合に、それらのレコードが連結される。一方、非等価結合では、キーとなる文字列の一致だけでなく、他の結合条件も用いてレコードが連結される。他の結合条件としては、例えば、一方の文字列が他方の文字列の一部分に一致することや、一方の数値が他方の数値範囲に含まれること等の条件が用いられる。
【０００４】
また、出力されるレコードに基づく結合方法の種類としては、内部結合（Inner Join）、左外部結合（Left Outer Join）、全外部結合（Full Outer Join）等が挙げられる。
図１は、内部結合、左外部結合、及び全外部結合の例を示している。ジャーナルテーブル１０１とマスタテーブル１０２を結合してテーブル１０３を生成するとき、内部結合では、テーブル１０１のレコードとテーブル１０２のレコードを連結したレコード１３１〜１３３のみが、テーブル１０３のレコードとして出力される。レコード１３１は、テーブル１０１のレコード１１１とテーブル１０２のレコード１２３を連結したレコードであり、レコード１３２は、テーブル１０１のレコード１１５とテーブル１０２のレコード１２３を連結したレコードである。レコード１３３は、テーブル１０１のレコード１１４とテーブル１０２のレコード１２４を連結したレコードである。
【０００５】
一方、左外部結合では、レコード１３１〜１３３に加えて、連結されなかったテーブル１０１のレコード１１２及び１１３も、テーブル１０３のレコード１３４及び１３５として出力される。さらに、全外部結合では、レコード１３１〜１３５に加えて、連結されなかったテーブル１０２のレコード１２２及び１２１も、テーブル１０３のレコード１３６及び１３７として出力される。
【０００６】
ところで、等価結合及び非等価結合を実現可能な全外部結合として、マージ結合が知られている。マージ結合では、結合対象の２つのテーブルのレコードをソートしてからレコード同士が連結される。
【０００７】
図２乃至図８は、このようなマージ結合の例を示している。まず、図２に示すように、ジャーナルテーブル１０１のレコード１１１〜１１５及びマスタテーブル１０２のレコード１２１〜１２４がレコードの値の昇順にソートされて、テーブル２０１及び２０２が生成される。
【０００８】
次に、図３に示すように、テーブル２０１及び２０２の先頭のレコード２１１及び２２１が比較される。この場合、レコード２１１及び２２１の値が一致しないため、小さい方の値“１”を有するレコード２１１が、テーブル２０３のレコード２３１として出力される。
【０００９】
次に、図４に示すように、テーブル２０１の次のレコード２１２とテーブル２０２のレコード２２１が比較される。この場合、レコード２１２及び２２１の値が一致しないため、小さい方の値“２”を有するレコード２２１が、テーブル２０３のレコード２３２として出力される。
【００１０】
次に、図５に示すように、テーブル２０１のレコード２１２とテーブル２０２の次のレコード２２２が比較される。この場合、レコード２１２及び２２２の値が一致するため、レコード２１２及び２２２が連結され、テーブル２０３のレコード２３３として出力される。
【００１１】
次に、図６に示すように、レコード２１２の次のレコード２１３とレコード２２２の次のレコード２２３のうち、小さい方の値“３”を有するレコード２１３が比較対象として選択され、レコード２１３とレコード２２２が比較される。この場合、レコード２１３及び２２２の値が一致するため、レコード２１３及び２２２が連結され、テーブル２０３のレコード２３４として出力される。
【００１２】
次に、図７に示すように、レコード２１３の次のレコード２１４とレコード２２２の次のレコード２２３のうち、小さい方の値“４”を有するレコード２２３が比較対象として選択され、レコード２１３とレコード２２３が比較される。この場合、レコード２１３及び２２３の値が一致せず、小さい方の値“３”を有するレコード２１３は既に出力済みのため、いずれのレコードも出力されない。
【００１３】
このようなレコードの比較と出力を、テーブル２０１及び２０２の末尾のレコード２１５及び２２４に到達するまで繰り返すことで、図８に示すように、テーブル２０１及び２０２のすべてのレコードが出力される。テーブル２０２のレコード２２３は、テーブル２０３のレコード２３５として出力され、テーブル２０１のレコード２１５は、テーブル２０３のレコード２３７として出力される。また、テーブル２０１のレコード２１４とテーブル２０２のレコード２２４は連結されて、テーブル２０３のレコード２３６として出力される。
【００１４】
レコードのキーとなる文字列を登録したオートマトンを用いたデータソート方法や、トライ（ＴＲＩＥ）構造の統計ヒドラを用いたデータ集計方法も知られている。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】特開２００３−４４２６７号号公報
【特許文献２】特開２００６−１７１８００号公報
【特許文献３】特開２０１０−１０８０９３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１６】
上述した従来のテーブル結合方法には、以下のような問題がある。
マージ結合により２つのテーブルを結合するには、レコードを連結する前にそれぞれのテーブルのレコードをソートする必要があり、ソートに一定の時間を要する。また、レコードの比較回数が多いため、レコードの比較にもかなりの時間を要する。仮にソートを行うことなくレコードを連結しようとすると、一方のテーブルのレコードを他方のテーブルのすべてのレコードと比較する必要があり、比較に要する時間はさらに増加する。
【００１７】
一方、マスタテーブルのキーを登録したトライ構造のオートマトン又は統計ヒドラを用いてレコードの比較を行えば、ソートが不要になると考えられる。しかし、マスタテーブルのトライ構造に基づく比較では、連結されなかったジャーナルテーブルのレコードを特定することはできても、連結されなかったマスタテーブルのレコードを特定することはできない。このため、連結されなかったマスタテーブルのレコードを出力することができず、全外部結合は実現されない。
【００１８】
１つの側面において、本発明の課題は、２つのテーブルの全外部結合を効率良く行うことである。
【課題を解決するための手段】
【００１９】
１つの側面において、プログラムは以下の処理をコンピュータに実行させる。
（１）第１のテーブルに含まれる第１のレコードのキーが、第２のテーブルに含まれる複数のレコードのキーを登録したトライ木に登録されている場合、第１のレコードと、第２のテーブルに含まれる第２のレコードとを用いて第３のレコードを生成する処理。この場合、第２のレコードは、第１のレコードのキーを含むレコードである。
（２）上記複数のレコードにそれぞれ対応するトライ木の複数の葉への複数のリンクを格納する配列から、第２のレコードに対応する葉へのリンクを削除する処理。
（３）第１のテーブルに含まれる第４のレコードのキーがトライ木に登録されていない場合、第４のレコードを用いて第５のレコードを生成する処理。
（４）配列中に残されたリンクによりリンクされる葉に対応する第２のテーブルに含まれる第６のレコードを用いて、第７のレコードを生成する処理。
（５）第３、第５、及び第７のレコードを出力する処理。
【発明の効果】
【００２０】
上述したプログラムによれば、２つのテーブルの全外部結合を効率良く行うことができる。
【図面の簡単な説明】
【００２１】
【図１】内部結合、左外部結合、及び全外部結合を示す図である。
【図２】マージ結合を示す図（その１）である。
【図３】マージ結合を示す図（その２）である。
【図４】マージ結合を示す図（その３）である。
【図５】マージ結合を示す図（その４）である。
【図６】マージ結合を示す図（その５）である。
【図７】マージ結合を示す図（その６）である。
【図８】マージ結合を示す図（その７）である。
【図９】未連結レコードを特定する方法を示す図である。
【図１０】第１のテーブル処理装置の機能的構成図である。
【図１１】第１のテーブル結合処理のフローチャートである。
【図１２】第２のテーブル処理装置の機能的構成図である。
【図１３】第２のテーブル結合処理のフローチャートである。
【図１４】トライ木及び配列を生成する処理のフローチャートである。
【図１５】連結処理のフローチャートである。
【図１６】未連結レコード処理のフローチャートである。
【図１７】第１のトライ木及び第１の配列を示す図である。
【図１８】第１の連結処理を示す図（その１）である。
【図１９】第１の連結処理を示す図（その２）である。
【図２０】第１の連結処理を示す図（その３）である。
【図２１】第１の未連結レコード処理を示す図である。
【図２２】マスタテーブルを示す図である。
【図２３】ジャーナルテーブルを示す図である。
【図２４】第２のトライ木を示す図である。
【図２５】第２のトライ木の構成を示す図である。
【図２６】第２のトライ木及び第２の配列を示す図である。
【図２７】第２の連結処理を示す図である。
【図２８】第２の未連結レコード処理を示す図である。
【図２９】情報処理装置の構成図である。
【発明を実施するための形態】
【００２２】
以下、図面を参照しながら、実施形態を詳細に説明する。
図９は、状態遷移を表すデータ構造の一種であるトライ木を利用して、連結されなかったマスタテーブルのレコードを特定する方法の例を示している。図９のトライ木は、先頭ノード９０１及び最終ノード９１１〜９１４を含み、最終ノード９１１〜９１４は、それぞれ葉９２１〜９２４へのリンク（葉のアドレス）を有する。このトライ木には、図１のマスタテーブル１０２のレコード１２１〜１２４の値がキーとして登録されている。トライ木は、ヒドラと呼ばれることもある。
【００２３】
先頭ノード９０１から最終ノード９１１〜９１４への矢印は、比較対象として入力される文字列に基づく状態遷移を表す。この例では、“２”、“３”、“４”、又は“５”が入力されると、最終ノード９１１、９１２、９１３、又は９１４へ状態が遷移する。各々の葉は、対応するレコードが連結済みか否かを示すフラグ、次の葉へのリンク（次の葉のアドレス）、及び対応するレコードへのリンク（レコードのアドレス）を有する。
【００２４】
フラグの初期値は論理“０”で、対応するレコードが未連結であることを表す。テーブル結合処理において、ジャーナルテーブル１０１のレコードの値がトライ木に登録されたいずれかの値と一致すれば、その値が示す最終ノードへの状態遷移が行われる。そして、テーブル１０１のレコードが、遷移先の最終ノードの葉に対応するテーブル１０２のレコードと連結され、その葉のフラグが論理“１”に変更される。
【００２５】
そして、テーブル１０１のすべてのレコードとトライ木との照合が終了すると、葉９２１から葉９２４に向かって次の葉へのリンクを辿りながら、論理“０”のフラグを有する葉に対応するレコードが抽出される。これにより、連結されなかったマスタテーブル１０２のレコードが特定され、全外部結合が実現できる。
【００２６】
しかしながら、図９の方法では葉の一覧をリンク構造で辿るため、広範囲のメモリ領域を参照することになり、処理の効率が低下する。そこで、連結されなかったマスタテーブルのレコード（未連結レコード）を、より効率良く抽出する方法が望まれる。
【００２７】
図１０は、実施形態のテーブル処理装置の機能的構成例を示している。図１のテーブル処理装置１００１は、レコード生成部１０１１、出力部１０１２、及び格納部１０１３を含み、第１及び第２のテーブルからレコードを生成する。第１のテーブルは、例えば、ジャーナルテーブルであり、第２のテーブルは、例えば、マスタテーブルである。第１及び第２のテーブルの定義は逆でも構わない。
【００２８】
格納部１０１３は、第２のテーブルに含まれる複数のレコードのキーを登録したトライ木１０２１と、それらのレコードにそれぞれ対応するトライ木１０２１の複数の葉への複数のリンクの配列１０２２とを格納する。
【００２９】
図１１は、図１０のテーブル処理装置１００１によるテーブル結合処理の例を示すフローチャートである。
レコード生成部１０１１は、第１のテーブルに含まれる第１のレコードのキーがトライ木１０２１に登録されているか否かをチェックする。第１のレコードのキーがトライ木１０２１に登録されている場合、第１のレコードと、第１のレコードのキーを含み第２のテーブルに含まれる第２のレコードとを用いて、第３のレコードを生成する（ステップ１１０１）。そして、配列１０２２から第２のレコードに対応する葉へのリンクを削除する（ステップ１１０２）。
【００３０】
次に、第１のテーブルに含まれる第４のレコードのキーがトライ木１０２１に登録されていない場合、第４のレコードを用いて第５のレコードを生成する（ステップ１１０３）。そして、配列１０２２中に残されたリンクによりリンクされる葉に対応する、第２のテーブルに含まれる第６のレコードを用いて、第７のレコードを生成する（ステップ１１０４）。
【００３１】
出力部１０１２は、第３、第５、及び第７のレコードを出力する（ステップ１１０５）。なお、ステップ１１０３の処理は、ステップ１１０１の処理の前に行ってもよい。
このようなテーブル結合処理によれば、トライ木１０２１を利用した高速な照合が可能であり、配列１０２２を用いて未連結レコードを特定可能なため、２つのテーブルの全外部結合を効率良く行うことができる。また、配列１０２２中に残されたリンクを検索する処理ではメモリの参照範囲が局所化されるため、未連結レコードを高速に抽出することができる。
【００３２】
テーブル処理装置１００１を情報処理装置により実現する場合、テーブル結合処理に要する時間が短縮されるため、Central Processing Unit（ＣＰＵ）の負荷が軽減され、装置の性能が向上する。さらに、マスタテーブルが多数のレコードを含む場合や、ジャーナルテーブルを複数のマスタテーブルと結合する場合でも、未連結レコードの出力を容易に並列化することが可能である。
【００３３】
図１２は、別のテーブル処理装置の機能的構成例を示している。図１２のテーブル処理装置１２０１は、トライ木生成部１２１１、格納部１２１２、レコード生成部１２１３、及び出力部１２１４を含む。レコード生成部１２１３は、連結処理部１２３１及び未連結レコード処理部１２３２を含む。
【００３４】
図１３は、図１２のテーブル処理装置１２０１によるテーブル結合処理の例を示すフローチャートである。まず、トライ木生成部１２１１は、入力された結合条件１２４１及びマスタテーブル１２４２に基づいてトライ木１２２１及び配列１２２２を生成し、格納部１２１２に格納する（ステップ１３０１）。
【００３５】
次に、レコード生成部１２１３は、トライ木１２２１を参照しながら、マスタテーブル１２４２及びジャーナルテーブル１２４３のレコードを連結する連結処理を行い、配列１２２２を更新する（ステップ１３０２）。そして、更新された配列１２２２に基づいて未連結レコードを出力する未連結レコード処理を行う（ステップ１３０３）。
【００３６】
出力部１２１４は、レコード生成部１２１３により生成されたレコードを、マスタテーブル１２４２とジャーナルテーブル１２４３の結合結果１２４４として出力する（ステップ１３０４）。
【００３７】
図１４は、図１３のステップ１３０１においてトライ木１２２１及び配列１２２２を生成する処理の例を示すフローチャートである。また、図１５及び図１６は、それぞれ、図１３のステップ１３０２における連結処理及びステップ１３０３における未連結レコード処理の例を示すフローチャートである。
【００３８】
図１４の処理において、まず、トライ木生成部１２１１は、マスタテーブル１２４２のレコードのうち未処理のレコードがあるか否かをチェックする（ステップ１４０１）。未処理のレコードがあれば（ステップ１４０１，ＹＥＳ）、マスタテーブル１２４２から１つの未処理のレコードを読み込む（ステップ１４０２）。そして、読み込んだレコードの項目のうち、結合条件１２４１により指定されたキー項目の文字列が、トライ木１２２１に登録済みか否かをチェックする（ステップ１４０３）。
【００３９】
キー項目の文字列がトライ木１２２１に登録済みでなければ（ステップ１４０３，ＮＯ）、その文字列に対応するトライ木１２２１のノードを生成し（ステップ１４０４）、読み込んだレコードへのリンクを最終ノードの葉に登録する（ステップ１４０５）。そして、最終ノードの葉へのリンクを配列１２２２の末尾に格納し（ステップ１４０６）、ステップ１４０１以降の処理を繰り返す。最初に生成された最終ノードの場合は、葉へのリンクが配列１２２２の先頭に格納され、配列１２２２の各要素はメモリ内の連続するアドレスに格納される。
【００４０】
一方、キー項目の文字列がトライ木１２２１に登録済みであれば（ステップ１４０３，ＹＥＳ）、ステップ１４０５以降の処理を行い、マスタテーブル１２４２のすべてのレコードを処理した場合は（ステップ１４０１，ＮＯ）、処理を終了する。こうして、トライ木１２２１及び配列１２２２が生成される。
【００４１】
例えば、図１のジャーナルテーブル１０１とマスタテーブル１０２を結合する場合、各レコードの値をキーとして用いることが結合条件１２４１として指定される。この場合、図１７に示すように、マスタテーブル１０２の４つのレコード１２１〜１２４の値がトライ木１７０１に登録される。トライ木１７０１は、図９に示した先頭ノード９０１及び最終ノード９１１〜９１４を含み、最終ノード９１１〜９１４は、それぞれ葉１７１１〜１７１４へのリンクを有する。葉１７１１〜１７１４は、それぞれレコード１２２、１２３、１２１、及び１２４へのリンクを有する。そして、配列１７０２の要素１７２１〜１７２４には、それぞれ葉１７１１〜１７１４へのリンクが格納される。
【００４２】
図１５の連結処理において、まず、レコード生成部１２１３の連結処理部１２３１は、ジャーナルテーブル１２４３のレコードのうち未処理のレコードがあるか否かをチェックする（ステップ１５０１）。未処理のレコードがあれば（ステップ１５０１，ＹＥＳ）、ジャーナルテーブル１２４３から１つの未処理のレコードを読み込む（ステップ１５０２）。そして、読み込んだレコードの項目のうち、結合条件１２４１により指定されたキー項目の文字列が、トライ木１２２１に登録されているか否かをチェックする（ステップ１５０３）。
【００４３】
キー項目の文字列がトライ木１２２１に登録されていれば（ステップ１５０３，ＹＥＳ）、その文字列に対応するトライ木１２２１の最終ノードのリンク先の葉を特定する。そして、その葉のリンク先のマスタテーブル１２４２のレコードを抽出する（ステップ１５０４）。
【００４４】
次に、読み込んだジャーナルテーブル１２４３のレコードと、抽出したマスタテーブル１２４２のレコードとを連結し、新たなレコードを生成する（ステップ１５０５）。そして、配列１２２２の要素のうち、抽出したマスタテーブル１２４２のレコードに対応する葉へのリンクをＮＵＬＬに変更することで、そのリンクを削除し（ステップ１５０６）、ステップ１５０１以降の処理を繰り返す。
【００４５】
一方、キー項目の文字列がトライ木１２２１に登録されていなければ（ステップ１５０３，ＮＯ）、読み込んだジャーナルテーブル１２４３のレコードを用いて新たなレコードを生成し（ステップ１５０７）、ステップ１５０１以降の処理を繰り返す。そして、ジャーナルテーブル１２４３のすべてのレコードを処理した場合は（ステップ１５０１，ＮＯ）、処理を終了する。
【００４６】
図１８に示すように、ジャーナルテーブル１０１の先頭のレコード１１１が読み込まれた場合、レコード１１１の値“３”をトライ木１７０１上で検索することで、その値が最終ノード１７１２に登録されていることが分かる。そこで、最終ノード１７１２の葉１７１２のリンク先のマスタテーブル１０２のレコード１２３が抽出され、レコード１１１とレコード１２３を連結したレコード１８１１が生成される。生成されたレコード１８１１は、結合結果のテーブル１８０１のレコードとして格納される。そして、配列１７０２の要素１７２２に格納された、葉１７１２へのリンクがＮＵＬＬに変更される。
【００４７】
次に、図１９に示すように、ジャーナルテーブル１０１の次のレコード１１２が読み込まれると、レコード１１２の値“１”がトライ木１７０１上で検索され、その値がトライ木１７０１に登録されていないことが分かる。そこで、レコード１１２を用いてレコード１８１２が生成され、テーブル１８０１に格納される。
【００４８】
同様にして、図２０に示すように、ジャーナルテーブル１０１の次のレコード１１３を用いてレコード１８１３が生成される。続いて、レコード１１４とマスタテーブル１０２のレコード１２４を連結したレコード１８１４が生成され、レコード１１５とマスタテーブル１０２のレコード１２３を連結したレコード１８１５が生成される。このとき、配列１７０２の要素１７２４に格納された、葉１７１４へのリンクがＮＵＬＬに変更される。そして、レコード１１５の処理が終了すると、連結処理が終了する。
【００４９】
図１６の未連結レコード処理において、まず、レコード生成部１２１３の未連結レコード処理部１２３２は、配列１２２２の要素のうち、未処理の要素があるか否かをチェックする（ステップ１６０１）。未処理の要素があれば（ステップ１６０１，ＹＥＳ）、ジャーナルテーブル１２４３から１つの未処理の要素を抽出する（ステップ１６０２）。そして、抽出した要素の値がＮＵＬＬか否かをチェックする（ステップ１６０３）。
【００５０】
要素の値がＮＵＬＬでなければ（ステップ１６０３，ＮＯ）、その要素に格納されたリンクのリンク先の葉を特定する。そして、その葉のリンク先のマスタテーブル１２４２のレコードを抽出する（ステップ１６０４）。次に、抽出したマスタテーブル１２４２のレコードを用いて新たなレコードを生成し（ステップ１６０５）、ステップ１６０１以降の処理を繰り返す。
【００５１】
一方、要素の値がＮＵＬＬであれば（ステップ１６０３，ＹＥＳ）、新たなレコードを生成せずに、ステップ１６０１以降の処理を繰り返す。そして、配列１２２２のすべての要素を処理した場合は（ステップ１６０１，ＮＯ）、処理を終了する。
【００５２】
図２１に示すように、配列１７０２の先頭の要素１７２１が抽出された場合、要素１７２１の値はＮＵＬＬではないので、リンク先の葉１７１１のリンク先であるマスタテーブル１０２のレコード１２２が抽出される。そして、レコード１２２を用いてレコード１８１６が生成され、テーブル１８０１に格納される。次の要素１７２２の値はＮＵＬＬなので、新たなレコードは生成されない。
【００５３】
次の要素１７２３が抽出された場合、要素１７２３の値はＮＵＬＬではないので、リンク先の葉１７１３のリンク先であるマスタテーブル１０２のレコード１２１が抽出される。そして、レコード１２１を用いてレコード１８１７が生成され、テーブル１８０１に格納される。次の要素１７２４の値はＮＵＬＬなので、新たなレコードは生成されない。
【００５４】
こうして、ジャーナルテーブル１０１とマスタテーブル１０２の全外部結合の結果であるテーブル１８０１が生成される。配列１７０２の各要素はメモリ内の連続するアドレスに格納されているため、未連結レコード処理においてメモリの参照範囲が局所化され、未連結レコードを高速に抽出することができる。
【００５５】
次に、図２２乃至図２８を参照しながら、図２２のマスタテーブルと図２３のジャーナルテーブルを結合する処理について説明する。
図２２のマスタテーブルは、レコード２２０１〜２２０３を含み、各レコードは、「Ｃｏｄｅ」、「商品名」、及び「価格」の３つの項目の文字列を含む。一方、図２３のジャーナルテーブルは、レコード２３０１〜２３０４を含み、各レコードは、「日付」、「番号」、及び「個数」の３つの項目の文字列を含む。
【００５６】
また、結合条件１２４１としては、例えば、以下のような条件を指定することができる。
Ｊｃｏｎｄｉｔｉｏｎ｛ｊｏｉｎ（Ｊｏｕｒｎａｌ，Ｍａｓｔｅｒ，＄番号＝＝＄Ｃｏｄｅ，“ＦＵＬＬ  ＯＵＴＥＲ”）｝
ＯｕｔｐｕｔＤｅｆ｛＄日付  日付，＄商品名  商品名，ｖａｌ（＄価格）＊ｖａｌ（＄個数）  売り上げ｝
【００５７】
この例では、各テーブルの項目名が記号＄を付加して表記されている。Ｊｃｏｎｄｉｔｉｏｎは、ジャーナルテーブルの項目「番号」とマスタテーブルの項目「Ｃｏｄｅ」とをキーとして、ジャーナルテーブルとマスタテーブルを全外部結合により結合することを示している。一方、ＯｕｔｐｕｔＤｅｆは、「日付」、「商品名」、及び「売り上げ」の３つの項目からなるテーブルを結合結果１２４４として出力することを示している。「日付」の項目としては、ジャーナルテーブルの「日付」の文字列が出力され、「商品名」の項目としては、マスタテーブルの「商品名」の文字列が出力される。また、「売り上げ」の項目としては、ジャーナルテーブルの「個数」の値とマスタテーブルの「価格」の値を乗算した結果が出力される。
【００５８】
結合条件１２４１は上記の条件に限らず、キー項目や結合結果の項目を変更した別の結合条件を指定することも可能である。
上記の条件が指定された場合、図２４に示すように、マスタテーブルの３つのレコード２２０１〜２２０３のキー項目である「Ｃｏｄｅ」の文字列「Ａ０１」、「Ａ０２」、及び「Ａ０３」がトライ木１２２１に登録される。図２４のトライ木は、先頭ノード２４０１、中間ノード２４０２、２４０３、及び最終ノード２４０４〜２４０６を含み、最終ノード２４０４〜２４０６は、それぞれ葉２４０７〜２４０９へのリンクを有する。
【００５９】
最終ノード２４０４〜２４０６は、文字列「Ａ０１」、「Ａ０２」、及び「Ａ０３」にそれぞれ対応し、葉２４０７〜２４０９は、それぞれレコード２４１１〜２４１３へのリンクを有する。レコード２４１１〜２４１３は、マスタテーブルのレコード２２０１〜２２０３にそれぞれ対応し、結合結果１２４４の生成に必要な「商品名」及び「価格」の文字列のみを含んでいる。葉２４０７〜２４０９が有するインデクスの値については後述する。
【００６０】
図２５は、図２４のトライ木の構成例を示している。文字列「Ａ０１」、「Ａ０２」、及び「Ａ０３」は、American Standard Code for Information Interchange（ＡＳＣＩＩ）コード表に従って、以下のような１６進の文字コードに変換される。
Ａ０１  ０ｘ４  ０ｘ１  ０ｘ３  ０ｘ０  ０ｘ３  ０ｘ１
Ａ０２  ０ｘ４  ０ｘ１  ０ｘ３  ０ｘ０  ０ｘ３  ０ｘ２
Ａ０３  ０ｘ４  ０ｘ１  ０ｘ３  ０ｘ０  ０ｘ３  ０ｘ３
【００６１】
図２５のトライ木は、これらの３つの文字コード列を登録した配列２５０１〜２５０６を含む。配列２５０１は、先頭ノードの配列であり、配列２５０２〜２５０５は、中間ノードの配列であり、配列２５０６は、最終ノードの配列である。配列２５０１〜２５０６の各要素のインデクスは、１６進コード０ｘ０、０ｘ１、０ｘ２等で表され、各インデクスの位置には次の配列へのリンク（次の配列の先頭アドレス）又はＮＵＬＬが格納される。ただし、最終ノードの配列２５０６には、次の配列へのリンクの代わりに葉へのリンクが格納される。
【００６２】
例えば、配列２５０１のインデクス０ｘ４の位置には、配列２５０２へのリンクが格納され、配列２５０２のインデクス０ｘ１の位置には、配列２５０３へのリンクが格納され、配列２５０３のインデクス０ｘ３の位置には、配列２５０４へのリンクが格納される。また、配列２５０４のインデクス０ｘ０の位置には、配列２５０５へのリンクが格納され、配列２５０５のインデクス０ｘ３の位置には、配列２５０６へのリンクが格納される。そして、配列２５０６のインデクス０ｘ１、０ｘ２、及び０ｘ３の位置には、それぞれ葉２４０７、２４０８、及び２４０９へのリンクが格納される。
【００６３】
図１５の連結処理では、読み込んだレコードのキー項目の文字コード列に含まれる各文字コードをインデクスとして用いて、配列２５０１〜２５０６に格納されたリンクを辿ることで、その文字コード列がトライ木に登録されているか否かがチェックされる。
【００６４】
なお、図２５のトライ木では、登録される文字列をＡＳＣＩＩコードに変換しているが、他の文字コードに変換しても構わない。例えば、Japan Industrial Standard（ＪＩＳ）コード、Ｓｈｉｆｔ−ＪＩＳコード、Extended Unix Code（ＥＵＣ）コード、Unicode等の文字コードを登録に用いることができる。
【００６５】
図２６は、図２４のトライ木とともに生成される配列１２２２の構成例を示している。図２６の例では、配列１２２２は、配列２６０１及びＭ個（Ｍは１以上の整数）の配列２６１１−１〜２６１１−Ｍを含む。配列２６０１は、配列２６１１−１〜２６１１−Ｍへのリンクを有する。配列２６１１−１〜２６１１−Ｍの各要素のインデクスは、１０進数０、１、２等で表され、各インデクスの位置にはトライ木の葉へのリンク又はＮＵＬＬが格納される。
【００６６】
例えば、配列２６１１−１のインデクス０、１、及び２の位置には、葉２４０７、２４０８、及び２４０９へのリンクとして、葉２４０７、２４０８、及び２４０９の先頭アドレス「０ｘ１２００」、「０ｘ５６２０」、及び「０ｘ２Ｆ００」がそれぞれ格納される。配列２６１１−１〜２６１１−Ｍの他のインデクスの位置には、ＮＵＬＬが格納される。
【００６７】
一方、葉２４０７、２４０８、及び２４０９には、対応する配列２６１１−１のインデクス０、１、及び２の値がそれぞれ格納され、図１５の連結処理において葉へのリンクをＮＵＬＬに変更する際に用いられる。
【００６８】
図１５の連結処理において、図２３のジャーナルテーブルの先頭のレコード２３０１が読み込まれた場合、レコード２３０１のキー項目である「番号」の文字列「Ａ０３」をトライ木上で検索することで、その文字列が最終ノード２４０６に登録されていることが分かる。
【００６９】
そこで、最終ノード２４０６の葉２４０９のリンク先のレコード２４１３が抽出され、レコード２３０１とレコード２４１３を連結したレコード２７１１が生成される。このとき、ＯｕｔｐｕｔＤｅｆに従って、レコード２３０１の「日付」の文字列「２０１１／１０／１０」が、レコード２７１１の「日付」の項目として格納される。また、レコード２４１３の「商品名」の文字列「消しゴム」が、レコード２７１１の「商品名」の項目として格納される。そして、レコード２３０１の「個数」の値「３」とレコード２４１３の「価格」の値「８０」を乗算した結果である「２４０」が、レコード２７１１の「売り上げ」の項目として格納される。生成されたレコード２７１１は、結合結果のテーブル２７０１のレコードとして格納される。
【００７０】
次に、葉２４０９に格納されたインデクスの値「２」を用いて、配列２６１１−１のインデクス「２」の要素がアクセスされる。そして、その要素に格納された、葉２４０９の先頭アドレス「０ｘ２Ｆ００」がＮＵＬＬに変更される。
【００７１】
次に、ジャーナルテーブルのレコード２３０２が読み込まれると、レコード２３０２の「番号」の文字列「Ａ０１」がトライ木上で検索され、その文字列が最終ノード２４０４に登録されていることが分かる。そこで、図２８に示すように、最終ノード２４０４の葉２４０７のリンク先のレコード２４１１が抽出され、レコード２３０２とレコード２４１１を連結したレコード２７１２が生成されて、テーブル２７０１に格納される。
【００７２】
次に、葉２４０７に格納されたインデクスの値「０」を用いて、配列２６１１−１のインデクス「０」の要素がアクセスされる。そして、その要素に格納された、葉２４０７の先頭アドレス「０ｘ１２００」がＮＵＬＬに変更される。
【００７３】
次に、ジャーナルテーブルのレコード２３０３が読み込まれると、レコード２３０３の「番号」の文字列「Ａ０４」がトライ木上で検索され、その文字列がトライ木に登録されていないことが分かる。そこで、レコード２３０３を用いてレコード２７１３が生成され、テーブル２７０１に格納される。このとき、ＯｕｔｐｕｔＤｅｆに従って、レコード２３０３の「日付」の文字列「２０１１／１０／１１」が、レコード２７１３の「日付」の項目として格納される。また、レコード２７１３の「商品名」及び「売り上げ」の項目にはＮＵＬＬが設定される。
【００７４】
次に、ジャーナルテーブルのレコード２３０４が読み込まれると、レコード２３０４の「番号」の文字列「Ａ０１」がトライ木上で検索され、その文字列が最終ノード２４０４に登録されていることが分かる。そこで、最終ノード２４０４の葉２４０７のリンク先のレコード２４１１が抽出され、レコード２３０４とレコード２４１１を連結したレコード２７１４が生成されて、テーブル２７０１に格納される。
【００７５】
次に、葉２４０７に格納されたインデクスの値「０」を用いて、配列２６１１−１のインデクス「０」の要素がアクセスされる。この場合、その要素には既にＮＵＬＬが設定されているため、その要素は変更されない。そして、未処理のレコードがなくなったため、連結処理が終了する。
【００７６】
図１６の未連結レコード処理において、配列２６１１−１のインデクス「０」の要素が抽出された場合、その要素の値はＮＵＬＬなので、対応する新たなレコードは生成されない。
【００７７】
次に、インデクス「１」の要素が抽出されると、その要素の値はＮＵＬＬではないので、リンク先の葉２４０８のリンク先であるレコード２４１２が抽出される。そして、レコード２４１２を用いてレコード２７１５が生成され、テーブル２７０１に格納される。このとき、ＯｕｔｐｕｔＤｅｆに従って、レコード２４１２の「商品名」の文字列「赤鉛筆」が、レコード２７１５の「商品名」の項目として格納される。また、レコード２７１５の「日付」及び「売り上げ」の項目にはＮＵＬＬが設定される。
【００７８】
インデクス「２」以降の要素の値はＮＵＬＬなので、対応する新たなレコードは生成されない。こうして、図２２のマスタテーブルと図２３のジャーナルテーブルとの全外部結合の結果であるテーブル２７０１が生成される。
【００７９】
図１３乃至図１６に示した各フローチャートは一例に過ぎず、テーブル処理装置の構成や条件に応じて一部の処理を省略又は変更しても構わない。例えば、図１５のステップ１５０５及び１５０７と図１６のステップ１６０５において、レコード生成部１２１３の代わりに出力部１２１４がレコードを生成してもよい。
【００８０】
また、結合対象となるテーブルは、図１、図２２、及び図２３の具体例には限られず、別の項目を有するテーブルでも構わない。図１７のトライ木１７０１及び図２４のトライ木は、結合条件として等価結合が指定された場合のトライ木であるが、非等価結合が指定された場合も同様にしてトライ木を生成することが可能である。非等価結合の場合は、２つのテーブルの一方の文字列が他方の文字列の一部分に一致することや、一方の数値が他方の数値範囲に含まれること等の条件を反映して、トライ木における遷移の矢印が等価結合の場合より増加する。
【００８１】
図１０のテーブル処理装置１００１及び図１２のテーブル処理装置１２０１は、例えば、図２９に示すような情報処理装置を用いて実現可能である。
図２９の情報処理装置は、Central Processing Unit （ＣＰＵ）２９０１、メモリ２９０２、入力装置２９０３、出力装置２９０４、外部記憶装置２９０５、媒体駆動装置２９０６、及びネットワーク接続装置２９０７を備える。これらはバス２９０８により互いに接続されている。
【００８２】
メモリ２９０２は、例えば、Read Only Memory（ＲＯＭ）、Random Access Memory（ＲＡＭ）、フラッシュメモリ等の半導体メモリであり、処理に用いられるプログラム及びデータを格納する。例えば、ＣＰＵ２９０１は、メモリ２９０２を利用してプログラムを実行することにより、テーブル処理装置１００１及び１２０１の処理を行う。メモリ２９０２は、図１０の格納部１０１３又は図１２の格納部１２１２としても使用できる。
【００８３】
入力装置２９０３は、例えば、キーボード、ポインティングデバイス等であり、ユーザ又はオペレータからの指示や情報の入力に用いられる。出力装置２９０４は、例えば、表示装置、プリンタ、スピーカ等であり、ユーザ又はオペレータへの問い合わせや処理結果の出力に用いられる。この処理結果には、図１２の結合結果１２４４が含まれる。
【００８４】
外部記憶装置２９０５は、例えば、磁気ディスク装置、光ディスク装置、光磁気ディスク装置、テープ装置等である。この外部記憶装置２９０５には、ハードディスクドライブも含まれる。情報処理装置は、外部記憶装置２９０５にプログラム及びデータを格納しておき、それらをメモリ２９０２にロードして使用することができる。
【００８５】
媒体駆動装置２９０６は、可搬型記録媒体２９０９を駆動し、その記録内容にアクセスする。可搬型記録媒体２９０９は、メモリデバイス、フレキシブルディスク、光ディスク、光磁気ディスク等である。この可搬型記録媒体２９０９には、Compact Disk Read Only Memory （ＣＤ−ＲＯＭ）、Digital Versatile Disk（ＤＶＤ）、Universal Serial Bus（ＵＳＢ）メモリ等も含まれる。ユーザ又はオペレータは、この可搬型記録媒体２９０９にプログラム及びデータを格納しておき、それらをメモリ２９０２にロードして使用することができる。
【００８６】
このように、各種処理に用いられるプログラム及びデータを格納するコンピュータ読み取り可能な記録媒体には、メモリ２９０２、外部記憶装置２９０５、及び可搬型記録媒体２９０９のような、物理的な（非一時的な）記録媒体が含まれる。
【００８７】
ネットワーク接続装置２９０７は、Local Area Network（ＬＡＮ）、インターネット等の通信ネットワークに接続され、通信に伴うデータ変換を行う通信インタフェースである。情報処理装置は、プログラム及びデータを外部の装置からネットワーク接続装置２９０７を介して受け取り、それらをメモリ２９０２にロードして使用することもできる。
【００８８】
なお、情報処理装置が図２９のすべての構成要素を含む必要はなく、用途や条件に応じて一部の構成要素を省略することも可能である。
開示の実施形態とその利点について詳しく説明したが、当業者は、特許請求の範囲に明確に記載した本発明の範囲から逸脱することなく、様々な変更、追加、省略をすることができるであろう。
【符号の説明】
【００８９】
１０１、１２４３  ジャーナルテーブル
１０２、１２４２  マスタテーブル
１０３、２０１、２０２、２０３、１８０１、２７０１  テーブル
１１１〜１１５、１２１〜１２４、１３１〜１３７、２１１〜２１５、２２１〜２２４、２３１〜２３７、１８１１〜１８１７、２２０１〜２２０３、２３０１〜２３０４、２４１１〜２４１３、２７１１〜２７１５  レコード
９０１、２４０１  先頭ノード
２４０２、２４０３  中間ノード
９１１〜９１４、２４０４〜２４０６  最終ノード
９２１〜９２４、１７１１〜１７１４、２４０７〜２４０９  葉
１００１、１２０１  テーブル処理装置
１０１１、１２１３  レコード生成部
１０１２、１２１４  出力部
１０１３、１２１２  格納部
１０２１、１２２１、１７０１  トライ木
１０２２、１２２２、１７０２、２５０１〜２５０６、２６０１、２６１１−１〜２６１１−Ｍ  配列
１２１１  トライ木生成部
１２３１  連結処理部
１２３２  未連結レコード処理部
１２４１  結合条件
１２４４  結合結果
１７２１〜１７２４  要素
２９０１  ＣＰＵ
２９０２  メモリ
２９０３  入力装置
２９０４  出力装置
２９０５  外部記憶装置
２９０６  媒体駆動装置
２９０７  ネットワーク接続装置
２９０８  バス
２９０９  可搬型記録媒体
【図１】
0005765244.tif 000002
【図２】
0005765244.tif 000003
【図３】
0005765244.tif 000004
【図４】
0005765244.tif 000005
【図５】
0005765244.tif 000006
【図６】
0005765244.tif 000007
【図７】
0005765244.tif 000008
【図８】
0005765244.tif 000009
【図９】
0005765244.tif 000010
【図１０】
0005765244.tif 000011
【図１１】
0005765244.tif 000012
【図１２】
0005765244.tif 000013
【図１３】
0005765244.tif 000014
【図１４】
0005765244.tif 000015
【図１５】
0005765244.tif 000016
【図１６】
0005765244.tif 000017
【図１７】
0005765244.tif 000018
【図１８】
0005765244.tif 000019
【図１９】
0005765244.tif 000020
【図２０】
0005765244.tif 000021
【図２１】
0005765244.tif 000022
【図２２】
0005765244.tif 000023
【図２３】
0005765244.tif 000024
【図２４】
0005765244.tif 000025
【図２５】
0005765244.tif 000026
【図２６】
0005765244.tif 000027
【図２７】
0005765244.tif 000028
【図２８】
0005765244.tif 000029
【図２９】
0005765244.tif 000030