(57)【要約】【課題】  テーブル形式（２次元の表）に展開されたツリー構造の情報を効率よく検索・収集可能としたデータベースの検索方法を提供する。【解決手段】  １レコード内に、経路フィールドと、親のポインタフィールドとを設けて、ツリー構造の情報をデータベースに展開しておき、検索条件に応じて、経路フィールド、あるいは、親子のポインタフィールドを選択して、情報を検索する。本発明では、検索時に検索の特性にあったフィールドを用いる（検索方法を使い分ける）ことで、テーブル形式（２次元の表）に展開されたツリー構造の情報を効率よく検索・収集可能とする。【選択図】        図２
2006107077.tif 000002
【特許請求の範囲】
【請求項１】
ツリー構造の情報がテーブル形式に展開されたデータベースであって、
１レコード内に、経路フィールドと、親子のポインタフィールドとを有することを特徴するデータベース。
【請求項２】
ツリー構造の情報がテーブル形式に展開されたデータベースであって、
１レコード内に、経路フィールドと、親子のポインタフィールドと、子の順列フィールドとを有することを特徴とするデータベース。
【請求項３】
１レコード内に、経路フィールドと、親のポインタフィールドとを設けて、ツリー構造の情報をデータベースに展開しておき、検索条件に応じて、前記経路フィールド、あるいは、前記親子のポインタフィールドを選択して、情報を検索することを特徴とするデータベースの検索方法。
【請求項４】
１レコード内に、経路フィールドと、親のポインタフィールドと、子の順列フィールドとを設けて、ツリー構造の情報をデータベースに展開しておき、検索条件に応じて、前記経路フィールド、または、前記親子のポインタフィールド、あるいは、前記子の順列フィールドを選択して、情報を検索することを特徴とするデータベースの検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースおよびデータベースの検索方法に係り、特に、テーブル形式（２次元の表）に展開されたツリー構造の情報を効率よく検索・収集可能としたリレーショナルデータベースおよびリレーショナルデータベースの検索方法に関する。
【背景技術】
【０００２】
リレーショナルデータベースでは、情報（あるいは、データ）を表形式（テーブル構造）で表現するため、データ・モデルが理解しやすいという特徴を有する。
リレーショナルデータベースのテーブル構造は、表計算ソフトと同様に行・列からなり、行はレコード、列はカラムやフィールドという。テーブルは、１個以上のフィールドを持ったレコードの集合で構成される。
従来、ツリー構造の情報を、リレーショナルデータベースのテーブルに展開する場合、主に、経路フィールドを用いる方法（以下、展開方式Ａという）と、親子のポインタフィールドを用いる方法（以下、展開方式Ｂという）の、次の２つの方法が知られている。
以下、この展開方式Ａ、展開方式Ｂについて説明する。
例えば、ツリー構造の情報が、図１に示すように、ノードＡ〜ノードＥの情報からなり、ノードＡの下位に、ノードＢとノードＣが位置し、ノードＣの下位に、ノードＤとノードＥが位置するものであるとする。なお、ノードＡ〜ノードＥの情報は、例えば、フォルダ、ファイルである。
【０００３】
展開方式Ａにより、図１に示すツリー構造の情報を、リレーショナルデータベースのテーブルへ展開すると、図３に示すようになる。
図３に示すように、展開方式Ａの場合、各レコードに、経路１１のフィールドが設けられる。なお、図３において、１０はレコードの識別子、１２はノードの値である。
また、展開方式Ｂにより、図１に示すツリー構造の情報を、リレーショナルデータベースのテーブルへ展開すると、図４に示すようになる。
図４に示すように、展開方式Ｂの場合、各レコードに、親子のポインタ２３のフィールドが設けられる。ここでは、親子のポインタとしては、親ノードの情報を使用している。
なお、図４において、２０はレコードの識別子、２１はノードの名前、２２はノードの値である。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
図１に示すツリー構造の情報を、前述した展開方式Ａによりリレーショナルデータベースのテーブルへ展開した場合、例えば、図５に示すように、ノードＣの親を特定したい場合は、以下の処理手順が必要となる。
（１）経路フィールドがＣで終了しているレコードを特定する。
（２）そして、レコードの経路フィールドを取得する。
（３）文字列を区切り文字である「／」で分解、解析することによって、Ｃの上位のノードＡを特定する。
このように、前述した展開方式Ａによりリレーショナルデータベースのテーブルへ展開した場合、親ノードを特定するときには、リレーショナルデータベース管理システム（ＲＤＢＭＳ）のほかに、文字列解析処理が必要となり、この方式は、例えば、ＸＭＬ（Extensible Markup Language）などのように、パスの記述が複雑になるほどコスト高になるという問題点があった。
【０００５】
また、図１に示すツリー構造の情報を、前述した展開方式Ｂによりリレーショナルデータベースのテーブルへ展開した場合、例えば、図６に示すように、ノードＡ以下すべてのノードを取得したい場合は、検索手順は以下のようになる。
（１）Ａノードを親ノードに設定しているノードを選択する。
（２）（１）で対象となった各ノードについて子ノードを検索する。
（３）（２）の処理を繰り返す。
このように、展開方式Ｂによりリレーショナルデータベースのテーブルへ展開した場合、特定のノード以下すべてのノードを取得したいときには、下位ノードを順次検索（あるいは、探索）する回数分の検索命令を発行する必要があり、リレーショナルデータベース管理システムでは、単発の検索の繰り返しは処理コストが高くつき、ツリーの構造が大きくなるほどこの問題は顕著に表れるという問題点があった。
本発明は、前記従来技術の問題点を解決するためになされたものであり、本発明の目的は、テーブル形式（２次元の表）に展開されたツリー構造の情報を効率よく検索・収集可能としたデータベースおよびデータベースの検索方法を提供することにある。
本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述及び添付図面によって明らかにする。
【課題を解決するための手段】
【０００６】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、下記の通りである。
前述の課題を解消するために、本発明では、１レコード内に、経路フィールドと、親子のポインタフィールド（あるいは、経路フィールドと、親子のポインタフィールドと、子の順列フィールド）とを設けて、ツリー構造の情報をデータベースに展開しておき、検索条件に応じて、経路フィールド、または、親子のポインタフィールド、（あるいは、経路フィールド、親子のポインタフィールド、または、子の順列フィールド）を選択して、情報を検索することを特徴とする。
前述の展開方式Ａによりデータベースのテーブルへ展開した場合、『ノードＡ以下すべてのノード（ノードＡの子・孫・曾孫・・・）といったツリー構造上の範囲を指定した検索が効率よく行える』という長所を有するが、『「ノードＡの子は？」、「ノードＢの親は？」といったようなツリー構造の順次検索処理には非効率で、かつ、リレーショナルデータベース管理システム（ＲＤＢＭＳ）で実現することができない』という短所がある。
一方、前述の展開方式Ｂによりデータベースのテーブルへ展開した場合、『「ノードＡの子は？」、「ノードＢの親は？」といったようにツリー構造の順次検索処理に向いている』という長所を有するが、『ノードＡ以下すべてのノード（ノードＡの子・孫・曾孫・・・）といったツリー構造上の範囲を指定した検索には不向きである』という短所がある。
そこで、本発明では、展開方式Ａと、展開方式Ｂの２種類の展開方式を組み合わせて、検索時に検索の特性にあったフィールドを用いる（検索方法を使い分ける）ことで、テーブル形式（２次元の表）に展開されたツリー構造の情報を効率よく検索・収集可能とする。
【発明の効果】
【０００７】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば、下記の通りである。
本発明によれば、テーブル形式（２次元の表）に展開されたツリー構造の情報を効率よく検索・収集することが可能となる。
【発明を実施するための最良の形態】
【０００８】
以下、図面を参照して本発明の実施例を詳細に説明する。
なお、実施例を説明するための全図において、同一機能を有するものは同一符号を付け、その繰り返しの説明は省略する。
図２は、本発明の実施例のリレーショナルデータベースにおいて、図１に示すツリー構造の情報をテーブルへ展開した場合を示す図である。
図２に示すように、本実施例では、各レコードに、経路２のフィールドと、親子のポインタ５のフィールドが共に設けられる。ここでは、親子のポインタとして、親ノードの情報を使用している。
なお、図２において、１はレコードの識別子、３はノードの名前、４はノードの値である。ここで、レコードの識別子１は、ノードを一意に識別可能な、重複しない番号や記号であり、一意に識別できるものであれは、アルファベット、乱数などであってもよい。
また、経路２は、ルートノード(根) から対象のノードまでの経路をあらわす文字列である。この経路の記述方法は、ツリー構造のルートノード（木の根）から当該ノードまで経路を、各ノード間に区切り文字（／）を間に挟みながら記述する。なお、区切り文字は、データベースによっては、（／）以外の文字を用いてもよい。
また、ノードの名前３は、ノードの名称であり、例えば、ＸＭＬ文書などの構造化文書ではタグ名を表す。また、ノードの値４は、ノードに割り当てられた値であり、例えば、ＸＭＬなどの構造化文書では、特定の属性値またはコンテンツ(タグに挟まれた文字列部) を表す。さらに、親子のポインタ５は、親ノードを識別できる情報であり、前述の親ノードの情報の他に、識別子１を用いてもよい。
本実施例は、従来の展開方式Ａと、展開方式Ｂの２種類の展開方式を組み合わせたものであり、本実施例によれば、最小限の検索命令の発行回数で、目的のノードを収集、特定することが可能であるとともに、ツリー構造の階層関係による検索が可能となる。
【０００９】
今、図２で示されるテーブルをＴ１とするとき、例えば、図５に示すように、図１に示すツリー構造の情報において、ノードＣの親を特定したい場合、本実施例のリレーショナルデータベースの検索方法では、下記（１）式に示す検索命令を１回発行するだけでよい。
［数１］  
SELECT 親ノード FROM T1 WHERE ノード名=Ｃ  ・・・・・・・・・・・・  （１）
また、例えば、図１に示すツリー構造の情報において、ノードＡの直下のノード（子ノード）を特定する場合、本実施例のリレーショナルデータベースの検索方法では、下記（２）式に示す検索命令を１回発行するだけでよい。
［数２］  
SELECT ノード名 FROM T1 WHERE 親ノード=Ａ  ・・・・・・・・・・・・  （２）
また、例えば、図６に示すように、図１に示すツリー構造の情報において、ノードＡ以下すべてのノードを取得したい場合、本実施例のリレーショナルデータベースの検索方法では、下記（３）式に示す検索命令を１回発行するだけでよい。
［数３］  
SELECT ノード名 FROM T1 WHERE 経路 LIKE（‘/a/*’）  ・・・・・・・  （３）
ここで、LIKE中の「*」は任意文字の繰り返しを意味する。
以上説明したように、本実施例のリレーショナルデータベースの検索方法では、従来の展開方式Ａと、展開方式Ｂの２種類の展開方式を組み合わせて、検索時に検索の特性にあったフィールドを用いる（検索方法を使い分ける）ようにしたので、テーブル形式（２次元の表）に展開されたツリー構造の情報を効率よく検索、収集することが可能となる。
【００１０】
図７は、ツリー構造の情報の他の例を示す図である。図７では、ノードＣの下位に、２つのノードＤが位置している。例えば、ＸＭＬなどの構造化文書では、同じ階層に同じ名前のノードが存在することが許される。その為、図７では、１番目の子、２番目の子・・・といったように連番や位置で特定できる情報を付与している。
図８は、本発明の実施例のリレーショナルデータベースにおいて、図７に示すツリー構造の情報をテーブルへ展開した場合を示す図である。
図８の場合は、親ノードの情報４として、識別子１が記述され、さらに、ノードの順列６と、子ノードの順列７が、追加されている点で、図２の場合と相違する。
ここで、ノードの順列６は、親ノードから見たノードの並び順を表し、また、子ノードの順列７は、同じレベル（階層）に名前が同じノードが存在した時の並び順を表す。
さらに、図８でも、経路の記述方法は、ツリー構造のルートノード（木の根）から当該ノードまで経路を、各ノード間に区切り文字（／）を間に挟みながら記述するが、区切り文字の間には、ノードの［名前］の値と、［子の順列］の値（番号）を鍵括弧で囲って記述する。
なお、区切り文字は、データベースの形式によって、（／）以外の文字を用いてもよく、子の順列を囲う鍵括弧文字は、データベースの形式によっては、別の文字を用いてもよい。
【００１１】
図８に示すテーブルの展開例の場合に、指定したノードの直下の子ノード全てを検索する（子を探す）の場合の検索方法を方式Ａとすると、本実施例のリレーショナルデータベースの方式Ａの検索方法は、以下のようになる。
（１）指定したノードの行を検索し、検索結果をＲとする。
（２）行Ｒの識別子フィールドの値を取り出し、取り出した値をＦとする。
（３）親ノードの情報フィールドが値Ｆと同値の行を検索する。
また、図８に示すテーブルの展開例の場合に、指定したノードの親ノードを検索する（親を探す）場合の検索方法を方式Ｂとすると、本実施例のリレーショナルデータベースの方式Ｂの検索方法は、以下のようになる。
（１）指定したノードの行を検索し、検索結果をＲとする。
（２）行Ｒの親ノードの情報フィールドの値を取り出し、取り出した値をＰとする。
（３）識別子フィールドがＰと同値になる行を検索する。
また、図８に示すテーブルの記述例の場合に、指定したノードにより下位のノードの全てを検索する（子孫を探す）場合の検索方法を方式Ｃとすると、本実施例のリレーショナルデータベースの方式Ｃの検索方法は、以下のようになる。
（１）指定したノードの行を検索し、検索結果をＲとする。
（２）行Ｒの経路フィールドの情報を抽出し、取り出した値をＴとする。
（３）経路フィールドがＴと同値であり、Ｔより文字数の多い行を検索する。
リレーショナルデータベースの検索条件では、経路 LIKE“T*”のようになる。
さらに、図８に示すテーブルの記述例の場合に、ルートノード（根）検索する場合の検索方法を方式Ｚとすると、本実施例のリレーショナルデータベースの方式Ｚの検索方法は、以下のようになる。
（１）親ノード列がルートノードを示す値の行を選択する。この場合に、ルートノードを示す値としは、例えば、無し（NULL）、｛ROOT｝などの記述がある。
【００１２】
ユーザが組織構造を表現した構造化文書が図９に示す場合に、構造化文書は、後述するユーザ・プログラムでは、図１０に示すツリー構造の情報として扱われる。
図１１は、本発明の実施例のリレーショナルデータベースにおいて、図１０に示すツリー構造の情報を、テーブルへ展開した場合を示す図である。なお、図１１では、タグ名をノードの名前、name属性をノードの値として扱っている。
図１１に示すテーブルの記述例の場合に、課長（名前CCC）以下の構成員すべての情報を得る場合の検索方法は、以下のようになる。
（１）基準ノードを指定する。名前が課長、値がCCCの識別子は３であるので、図１１中で、３の識別子１で示される行が基準ノードの情報となる。
（２）検索方式を決定する。検索対象は、「課長より下位のノードすべて」なので、検索方式は、前述の方式Ｃを選択する。
（３）検索実行する。（方式Ｃで表形式を検索する。）
（４）識別子が４と５の行で示されるノードが検索結果となる。
【００１３】
次に、図９に示す構造化文書において、名前（ノードの値のフィールド）が「ＣＣＣ」の「課長」に所属する２番目の「社員」を検索する場合について説明する。
これは、図１０に示すツリー構造の情報において、名前（ノードの値のフィールド）が「ＥＥＥ」の社員を検索する場合に相当する。
（１）始めに、下記（４）式に検索命令を発行し、課長ＣＣＣを特定する。
［数４］  
SELECT 識別子 FROM T2 WHERE 値＝”CCC”AND 名前＝”課長”
・・・・ ・・・・・・・・・・・・・・・  （４）
ここで、Ｔ２は、図１１で示されるテーブルであり、また、結果をＲ１とする。
（２）次に、下記（５）式に検索命令を発行し、２番目の子を特定する。
［数５］  
SELECT 識別子 FROM T2 WHERE 親ノード情報＝R1 AND 子ノードの順番＝2 
・・・・ ・・・・・・・・・・・・・・・  （５）
以上説明したように、ＸＭＬに代表される構造化文書では、同じ階層に同じ名前のノードが存在するが、本実施例では、子の順列のフィールドを採用することで、データベース部へ展開することできる。
また、リレーショナルデータベースでは検索回数が多いと実行効率が悪いが、本実施例では、検索方式を切り替えることにより、値が何以上、以下と言ったように範囲で指定することで検索回数を少なくすることができる。
【００１４】
図１２は、本実施例のリレーショナルデータベースの全体構成を示す概略ブロック図である。同図において、１００はユーザ・プログラム、１１０はリレーショナルデータベース、１１１は変換部、１１２はデータベース部である。
ユーザ・プログラム１００は、ツリー構造で情報（データ）を扱うプログラムである。また、データベース部１１２には、表形式（テーブル構造）でデータが格納され、行・列を基準に検索およびデータの取り出しが可能である。
ここで、ユーザ・プログラム１００と、変換部１１１との間は、ツリー構造で情報の送受信が行われ、変換部１１１とデータベース部１１２との間は、行・列で情報の送受信が行われる。
そのため、変換部１１１は、ツリー構造の情報を、表形式の情報に変換する。また、変換部１１１は、データベース部１１２の表形式で格納されたデータに対して、ツリー構造に即した検索を行い、結果として当該サブツリー（部分木）のデータを出力する。
なお、リレーショナルデータベース１１０は、ＣＳＶ（カンマ区切り）ファイルと、ＡＷＫ、Ｐｅｒｌなどの簡易検索プログラムであってもよい。
【００１５】
変換部１１１が、図７に示すツリー構造の情報を、図８の表形式に変換する手順は以下のようになる。
（１）識別子１を、識別子フィールドに記録する。
（２）ノードの名前３を、ノードの名前フィールドに記録する。
（３）ルートノード（根）から当該ノードまでの経路２を、経路フィールドに記録する。
（４）ノードの親ノードの識別子を、親ノードの情報フィールドに記録する。
（５）親から見た当該ノードの子の順番を、ノードの順列フィールドに記録する。
（６）同名のノードが同階層に存在する場合の当該ノードの順番を、子ノードの順列フィールドに記録する。
（７）ノードの持つ値を、ノードの値フィールドに記録する。
以上、本発明者によってなされた発明を、前記実施例に基づき具体的に説明したが、本発明は、前記実施例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【図面の簡単な説明】
【００１６】
【図１】ツリー構造の情報の一例を示す図である。
【図２】本発明の実施例のリレーショナルデータベースにおいて、図１に示すツリー構造の情報をテーブルへ展開した場合を示す図である。
【図３】従来の展開方式Ａにより、図１に示すツリー構造の情報を、リレーショナルデータベースのテーブルへ展開した場合を示す図である。
【図４】従来の展開方式Ｂにより、図１に示すツリー構造の情報を、リレーショナルデータベースのテーブルへ展開した場合を示す図である。
【図５】図１に示すツリー構造の情報において、ノードＣの親を特定したい場合を説明するための図である。
【図６】図１に示すツリー構造の情報において、ノードＡ以下すべてのノードを取得したい場合を説明するための図である。
【図７】ツリー構造の情報の他の例を示す図である。
【図８】本発明の実施例のリレーショナルデータベースにおいて、図７に示すツリー構造の情報をテーブルへ展開した場合を示す図である。
【図９】組織構造を表現した構造化文書の一例を示す図である。
【図１０】図９に示す構造化文書のツリー構造を示す図である。
【図１１】本発明の実施例のリレーショナルデータベースにおいて、図１０に示すツリー構造の情報をテーブルへ展開した場合を示す図である。
【図１２】本発明の実施例のリレーショナルデータベースの全体構成を示す概略ブロック図である。
【符号の説明】
【００１７】
１，１０，２０  レコードの識別子
２，１１  経路
３，２１  ノードの名前
５，２３  親子のポインタ
４，１２，２２  ノードの値
６  ノードの順列
７  子ノードの順列
１００  ユーザ・プログラム
１１０  リレーショナルデータベース
１１１  変換部
１１２  データベース部
【図１】
2006107077.tif 000003
【図２】
2006107077.tif 000004
【図３】
2006107077.tif 000005
【図４】
2006107077.tif 000006
【図５】
2006107077.tif 000007
【図６】
2006107077.tif 000008
【図７】
2006107077.tif 000009
【図８】
2006107077.tif 000010
【図９】
2006107077.tif 000011
【図１０】
2006107077.tif 000012
【図１１】
2006107077.tif 000013
【図１２】
2006107077.tif 000014