(57)【特許請求の範囲】
【請求項１】
上下の関係を持つ２つ以上のデータから成る階層構造データを操作するデータ構造判定装置であって、
識別子を付加された、前記階層構造データの各要素となるデータを格納するデータ格納手段と、
第１のデータの下に第２のデータを挿入してできる上下方向のデータ列の中で、前記第２のデータが下位の第３のデータを所有できるかどうかを調べ、該第２のデータが該第３のデータを所有できれば、該第１のデータの識別子が、該第２のデータおよび該第２のデータより下位のデータのうちの１つのデータの識別子と一致するかどうかを調べ、該第１のデータの識別子が該１つのデータの識別子と一致すれば、該第１のデータの下に該第２のデータを挿入すると無限階層構造が生じると判定し、該第１のデータの識別子が該第２のデータおよび該第２のデータより下位のデータのうちのいずれのデータの識別子とも一致しなければ、該第１のデータの下に該第２のデータを挿入しても無限階層構造は生じないと判定し、該第２のデータが該第３のデータを所有できなければ、該第１のデータの下に該第２のデータを挿入しても無限階層構造は生じないと判定する処理手段と
を備えることを特徴とするデータ構造判定装置。
【請求項２】
前記データ格納手段は、子ポインタを含む管理情報を前記階層構造データの各要素となるデータと関連付けて格納し、
前記処理手段は、前記管理情報を参照して、前記第２のデータが前記第３のデータを所有できるかどうかと、前記第１のデータの識別子が、該第２のデータおよび該第２のデータより下位のデータのうちの１つのデータの識別子と一致するかどうかを調べることを特徴とする請求項１記載のデータ構造判定装置。
【請求項３】
前記処理手段は、無限階層構造が生じると判定したとき、前記第１のデータの下に前記第２のデータを挿入せず、無限階層構造が生じないと判定したとき、前記第１のデータの下に前記第２のデータを挿入するように構成されることを特徴とする請求項１記載のデータ構造判定装置。
【請求項４】
前記処理手段は、前記第１のデータの識別子が前記第２のデータの識別子と一致しないとき、前記第３のデータが下位の第４のデータを所有できるかどうかを調べ、該第３のデータが該第４のデータを所有できれば、該第１のデータの識別子が、該第３のデータおよび該第３のデータより下位のデータのうちの１つのデータの識別子と一致するかどうかを調べ、該第１のデータの識別子が、該第３のデータおよび該第３のデータより下位のデータのうちの１つのデータの識別子と一致すれば、無限階層構造が生じると判定することを特徴とする請求項１記載のデータ構造判定装置。
【請求項５】
前記処理手段は、前記第３のデータが前記第４のデータを所有できないとき、該第３のデータと同じ階層に下位のデータを所有できるデータがあるかどうかを調べ、該下位のデータを所有できるデータがなければ、無限階層構造は生じないと判定することを特徴とする請求項４記載のデータ構造判定装置。
【請求項６】
前記処理手段が無限階層構造が生じると判定したとき、前記第１のデータの下に前記第２のデータを挿入するかどうかをユーザに問い合わせて、問い合わせに対する回答を受け取る入出力手段をさらに備え、
前記処理手段は、前記入出力手段がデータ挿入を行わない旨の回答を受け取ったとき、前記第１のデータの下に前記第２のデータを挿入せず、前記入出力手段がデータ挿入を行う旨の回答を受け取ったとき、前記第１のデータの下に前記第２のデータを挿入することを特徴とする請求項１記載のデータ構造判定装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、チェインによって管理された階層構造データにデータを挿入する際に、階層構造データの構造を判定する判定方法およびその装置に関する。
【０００２】
【従来の技術】
情報処理装置において、複数の異なるデータを互いに関連付けて管理する方法の１つに階層構造を用いる方法がある。互いに上下の関係を持ついくつかのデータから成る階層構造データは、例えばポインタ等によりデータを連結したチェインによって管理される。
【０００３】
図１１は、このような階層構造データの一例を示している。図１１の階層構造データは、下位層のデータ構造を持つデータα、β、γ、および下位層のデータ構造を持たないデータＡ、Ｂの５つのデータより成っている。このうち、データＡはα、βのそれぞれの下位層に存在しているが、階層構造データはチェインによって管理されているため、その実際のデータ（実体データ）は１つである。このように、チェインによって階層を管理する場合、同一のデータを階層構造の複数の箇所から参照できる長所がある。階層構造データにおいてデータ間の新たな上下関係を付加することにより、データを挿入すると、無限階層になる場合とならない場合とがある。
【０００４】
図１２は、図１１の階層構造データにおいて無限階層にならないようなデータ挿入の一例を示している。図１２においては、データγの下位層にデータβが挿入され、データγはデータβのみならずその配下のデータ、つまりデータＡおよびＢをも内包する関係になっている。
【０００５】
これに対して、図１３は、図１１の階層構造データにおいて無限階層になるようなデータ挿入の一例を示している。図１３においては、データαの下位層に同じデータαが挿入された結果、上下方向のチェインがループ状に繋がってしまう。このため、データαの下位層にそのデータαを延々と繰り返すような無限階層ができる。
【０００６】
【発明が解決しようとする課題】
上述のような従来のデータ操作方法には次のような問題がある。図１３に示すような無限階層を持った階層構造データ内の全てのデータの取り出しを試みた場合、データα、β、γ、Ａ、Ｂから成る同じデータ構造が下位層に何度も現れるため、その都度同じ実体データを取り出さなければならない。したがって、処理が煩雑になり、処理速度の低下を招く結果となる。
【０００７】
仮に、同じ名称を持つデータ同士を上下に繋げることが禁止されていたとしても、無限階層が生じる可能性は残されている。例えば、図１１において、データγの下にデータαを挿入した場合にも無限階層が生じてしまう。また、あるデータがコピーされて別の名称を付加されている場合、元のデータの下に別の名称を持つそのデータを挿入して、無限階層を生じさせることもあり得る。このような場合には、図１３の場合と同様にデータ操作が煩雑になる。
【０００８】
本発明は、チェインによって管理された階層構造データのデータ処理が煩雑になるのを防止するために、データ構造を調べて無限階層が生じるかどうかを判定するデータ構造判定方法およびその装置を提供することを目的とする。
【０００９】
【課題を解決するための手段】
図１は本発明のデータ構造判定方法の原理図である。
図１において、まず上下の関係を持つ２つ以上のデータから成る階層構造データの各要素となるデータに識別子を付加し（ステップＳ１）、第１のデータの下に第２のデータを挿入してできる上下方向のデータ列の中に、同一の識別子を持つデータが２つ以上あるかどうかを調べる（ステップＳ２）。
【００１０】
そして、同一の識別子を持つデータが２つ以上あれば、第１のデータの下に第２のデータを挿入すると無限階層構造になると判定し（ステップＳ３）、同一の識別子を持つデータが２つ以上なければ、第１のデータの下に第２のデータを挿入しても無限階層構造にならないと判定する（ステップＳ４）。
本発明のデータ構造判定装置は、データ格納手段および処理手段を備え、上下の関係を持つ２つ以上のデータから成る階層構造データを操作する。データ格納手段は、識別子を付加された、階層構造データの各要素となるデータを格納する。処理手段は、第１のデータの下に第２のデータを挿入してできる上下方向のデータ列の中で、第２のデータが下位の第３のデータを所有できるかどうかを調べ、第２のデータが第３のデータを所有できれば、第１のデータの識別子が、第２のデータおよび第２のデータより下位のデータのうちの１つのデータの識別子と一致するかどうかを調べ、第１のデータの識別子がそのデータの識別子と一致すれば、第１のデータの下に第２のデータを挿入すると無限階層構造が生じると判定し、第１のデータの識別子が第２のデータおよび第２のデータより下位のデータのうちのいずれのデータの識別子とも一致しなければ、第１のデータの下に第２のデータを挿入しても無限階層構造は生じないと判定し、第２のデータが第３のデータを所有できなければ、第１のデータの下に第２のデータを挿入しても無限階層構造は生じないと判定する。
【００１１】
【作用】
階層構造データの各要素となるデータは他のデータとの間の上下の関係を表す情報を持っており、この情報を操作することによりそのデータと他のデータとの上下関係を定義して、そのデータを階層構造の中に挿入することができる。
【００１２】
ここでは、各データにそれらを一意に識別する識別子をさらに付加する（ステップＳ１）。この識別子を比較することにより、２つのデータが実質的に同じものかどうかを容易に判断できるようになる。
【００１３】
第１のデータの下に第２のデータを挿入して、新しく階層構造データを生成するとき、あるいは、第１のデータを含む既存の階層構造データに第２のデータを付加するとき、第１のデータと第２のデータを結ぶ上下方向に位置する複数のデータ（データ列）の識別子を調べる（ステップＳ２）。そして、これらの中に同一の識別子を持つデータが２つ以上あればデータのチェインにループが生じるので、データ挿入を行うと無限階層構造になると判定する（ステップＳ３）。もし、同一の識別子を持つデータが２つ以上なければ、データ挿入を行っても無限階層構造にならないと判定する（ステップＳ４）。
【００１４】
この判定結果を利用して、第１のデータの下に第２のデータを挿入すると無限階層構造になる場合は、そのデータ挿入を禁止することができる。したがって、階層構造データの処理の効率化が図られる。
【００１５】
【実施例】
以下、図面を参照しながら本発明の実施例について詳細に説明する。
図２は、実施例の情報処理装置のシステム構成図である。図２の情報処理装置は、ＣＰＵ（中央処理装置）１、データ格納部２、入出力機器３と、それらを結合するバス４より構成される。データ格納部２は、例えば磁気ディスクや光ディスク等を備えるディスク装置であり、階層構造データの各要素となる個別のデータを格納している。これらの各データには、それらを識別するユニークな識別子が付加されている。入出力機器３は、例えばキーボード等の入力装置を備えたディスプレイ装置であり、ユーザからデータ操作の指示を受け取ったり、処理の結果を表示したりする。ＣＰＵ１は、入出力機器３から渡されるデータ操作の指示コマンドに従って、データ格納部２からデータを取り出し処理を実行する。
【００１６】
例えば、ユーザがいくつかの個別のデータ間に上下関係を定義する指示を行うと、ＣＰＵ１は各データの管理情報に上下関係を表すポインタを格納して、階層構造データを生成する。そして、その階層構造データをデータ格納部２に格納する。
【００１７】
ＣＰＵ１は、データ間に新たな上下関係を設定して階層構造データにデータを挿入するとき、その新たな上下関係により無限階層が生じないかどうかをチェックする。そして、場合によってはそのチェック結果を入出力機器３を介してユーザに提示し、ユーザの指示に従ってデータの挿入を行う。
【００１８】
図３は、ＣＰＵ１が階層構造データを下方に向かって検索してその構造を判定し、データ挿入を行う処理のフローチャートである。図３において処理が開始されると、まずＣＰＵ１はユーザから階層構造データを構成する第１のデータの下に第２のデータを挿入する指示を受け取る（ステップＳ１１）。次に、第１のデータの識別子が、第２のデータおよびそれより下位のデータのうちいずれかの識別子と一致するかどうかを調べる（ステップＳ１２）。もしいずれのデータの識別子とも一致しなければ、第１のデータの下に第２のデータを挿入して（ステップＳ１３）、処理を終了する。
【００１９】
第２のデータおよびそれより下位のデータの識別子の中に第１のデータの識別子と一致するものがあれば、その旨を入出力機器３を介してユーザに知らせて、データ挿入を行うかどうかを問い合わせる（ステップＳ１４）。そして、ユーザがデータ挿入を許可すれば第１のデータの下に第２のデータを挿入し（ステップＳ１３）、許可しなければそのまま処理を終了する。
【００２０】
第２のデータ以下の階層内に第１のデータの識別子と同じ識別子を持つデータがあるとき、データ挿入を行うことにより上下方向に同じデータ構造が繰り返され、無限階層が生じることになる。図３のデータ挿入処理では、このような場合にユーザがデータ挿入を禁止することができる。
【００２１】
次に、図４から図８までを参照しながら、データ挿入処理の具体例について説明する。
図４は、データ挿入前の階層構造データの具体例を示している。図４において、グループα、βは下位層を持つデータであり、メンバａ、ｂ、ｃは下位層を持たないデータである。グループβの下にはメンバｂ、ｃおよびグループαが存在し、グループαの下にはメンバａが存在している。
【００２２】
図５は、図４の各データ毎に設定されている管理情報の形式を示しており、図６は、図４の各データの管理情報の内容を示している。これらのデータの管理情報はデータ格納部２に格納される。
【００２３】
図５において、名称はそのデータの名称を表し、識別子はそのデータを一意に識別する番号を表す。また、子ポインタはそのデータの下位階層のデータの管理情報を指すポインタであり、下位階層がないデータの場合は何も指さないように設定される。前ポインタはそのデータと同階層内のデータのうちそのデータの前のデータの管理情報を指すポインタであり、同階層内で先頭に位置するデータの場合は何も指さないように設定される。後ポインタは同階層内のデータのうちそのデータの次のデータの管理情報を指すポインタであり、同階層内で終端に位置するデータの場合は何も指さないように設定される。実ポインタはデータの実体（実体データ）を指すポインタである。
【００２４】
図４の各データの場合は図６に示すように、グループαの識別子は１であり、その子ポインタはメンバａの管理情報を指し、前ポインタはメンバｃの管理情報を指し、後ポインタは何も指さない。また、グループβの識別子は２であり、その子ポインタはメンバｂの管理情報を指し、前ポインタおよび後ポインタは何も指さない。メンバａの識別子は３であり、その子ポインタ、前ポインタ、および後ポインタは何も指さない。メンバｂの識別子は４であり、その子ポインタおよび前ポインタは何も指さず、後ポインタはメンバｃの管理情報を指す。メンバｃの識別子は５であり、その子ポインタは何も指さず、前ポインタはメンバｂの管理情報を指し、後ポインタはグループαの管理情報を指す。
【００２５】
図７は、ＣＰＵ１によるデータ挿入処理の詳細なフローチャートであり、図８は、図７のステップＳ２２で呼び出されるサブルーチンの処理のフローチャートである。ＣＰＵ１は次に示すような順序で処理を行う。
【００２６】
まず、挿入するデータ（挿入データ）が下位層を所有できるかどうか、つまり、そのデータの管理情報の子ポインタがいずれかのデータを指しているかどうかを調べる（ステップＳ２１）。挿入データが下位層を所有できる場合は、既に階層構造データ内に存在する挿入を受ける側のデータ（挿入先データ）の管理情報と挿入データの管理情報とを引数として、サブルーチンＦｉｎｄＧｒｏｕｐ  を呼び出す（ステップＳ２２）。
【００２７】
例えば、図４においてグループαの下にグループβを挿入する指示があった場合、グループβが下位層を所有できるかどうかを調べる（ステップＳ２１）。図６に示すグループβの管理情報を見ると、その子ポインタはメンバｂを指しており、グループβは下位層を所有できるデータであることを示している。そこで、グループαの管理情報とグループβの管理情報を引数として、サブルーチンＦｉｎｄＧｒｏｕｐ  を呼び出す（ステップＳ２２）。
【００２８】
サブルーチンＦｉｎｄＧｒｏｕｐ  は、引数として渡された挿入先データおよび挿入データの管理情報をもとに、挿入データ以下の階層内を検索し、挿入先データの識別子と同じ識別子を持つデータの有無を検出する。同じ識別子のデータを検出した場合、その復帰値は１となる。
【００２９】
次に、サブルーチンＦｉｎｄＧｒｏｕｐ  の復帰値を検査し（ステップＳ２３）、復帰値が１でなければ挿入データを挿入先データの下に挿入して（ステップＳ２４）終了し、復帰値が１であればそのまま終了する。ここで、復帰値が１の場合は無限階層構造になることを表しており、それが１でない場合は無限階層構造にならないことを表している。
【００３０】
ステップＳ２２で挿入データが下位層を所有できない場合は、挿入データの下にデータ構造が繰り返されることがないので、そのまま挿入データを挿入先データの下に挿入して（ステップＳ２４）、終了する。例えば、挿入データがメンバａ、ｂ、ｃのいずれかであれば、これらはともに下位層を所有できないデータなので、直ちに挿入先データの下に挿入される。
【００３１】
次に、図７のサブルーチンＦｉｎｄＧｒｏｕｐ  の処理について説明する。
まず、引数として渡された各管理情報からそれぞれの識別子を取り出して、両者を比較する（ステップＳ３１）。両者が等しい場合は復帰値に１を設定して（ステップＳ３９）、終了する。
【００３２】
２つの識別子が異なる場合は、次に挿入データの下位層の先頭のデータの管理情報を取り出し（ステップＳ３２）、そのデータが下位層を所有できるかどうかを調べる（ステップＳ３３）。そのデータが下位層を所有できない場合は、挿入データの下位層内のデータを全て調べたかどうか判定する。同じ階層内にまだ調べていない次のデータがあれば、その管理情報を取り出し（ステップＳ３５）、ステップＳ３３以降の処理を繰り返す。挿入データの下位層内の全てのデータが下位層を所有できないことが分かれば、復帰値に０を設定して（ステップＳ３６）、終了する。
【００３３】
ステップＳ３３でそのデータが下位層を所有できる場合は、引数として渡された挿入先データの管理情報と、取り出したそのデータの管理情報とを引数として、ＦｉｎｄＧｒｏｕｐ  を再帰的に呼び出す（ステップＳ３７）。次に、再帰的に呼び出したＦｉｎｄＧｒｏｕｐ  の復帰値を検査し（ステップＳ３８）、それが１であれば呼出し元のＦｉｎｄＧｒｏｕｐ  の復帰値に１を設定して（ステップＳ３９）、終了する。再帰的に呼び出したＦｉｎｄＧｒｏｕｐ  の復帰値が１でなければ、ステップＳ３４以降の処理を行う。
【００３４】
図７のステップＳ２２において、グループαの管理情報とグループβの管理情報を引数として、サブルーチンＦｉｎｄＧｒｏｕｐ  が呼び出された場合は、まずグループαの識別子とグループβの識別子を比較する（ステップＳ３１）。図６よりグループα、βの識別子はそれぞれ１、２であり、両者は異なった値であるため、次に挿入データであるグループβの下位層の先頭にあるメンバｂの管理情報を取り出す（ステップＳ３２）。
【００３５】
次に、メンバｂが下位層を所有できるかどうかを調べる（ステップＳ３３）。メンバｂの管理情報には子ポインタが格納されておらず、メンバｂは下位層を所有できないことが分かるので、グループβの下位層にある全てのデータを調べてたかどうかを判定する（ステップＳ３４）。この判定は、メンバｂの後ポインタがデータを指しているかどうかを調べることにより行われる。メンバｂの後ポインタはメンバｃを指しているので、グループβの下位層にはまだ調べていないメンバｃがあることが分かり、その管理情報を取り出す（ステップＳ３５）。
【００３６】
次に、メンバｃが下位層を所有できるかどうかを調べる（ステップＳ３３）。しかし、メンバｃは下位層を所有できないので、メンバｃの後ポインタがデータを指しているかどうかを調べる（ステップＳ３４）。メンバｃの後ポインタは次のデータであるグループαを指しているので、その管理情報を取り出す（ステップＳ３５）。
【００３７】
次に、グループαは下位層を所有できるかどうかを調べる（ステップＳ３３）。グループαの子ポインタはメンバａを指しており、グループαは下位層を所有できることが分かるので、引数として渡されたグループαの管理情報と、取り出したグループαの管理情報とを引き数として、ＦｉｎｄＧｒｏｕｐ  を再帰的に呼び出す（ステップＳ３７）。再帰的に呼び出されたＦｉｎｄＧｒｏｕｐ  は、２つの管理情報からそれぞれの識別子を取り出して比較する（ステップＳ３１）。今の場合は２つの管理情報がともにグループαの管理情報であるため、それらの識別子はともに１である。したがって、２つの識別子は同じ値なので、復帰値１を呼出し元のＦｉｎｄＧｒｏｕｐ  に返す（ステップＳ３９）。
【００３８】
一方、呼出し元のＦｉｎｄＧｒｏｕｐ  は、再帰的に呼び出したＦｉｎｄＧｒｏｕｐ  が復帰値１を返してきたので（ステップＳ３８）、復帰値に１を設定して（ステップＳ３９）、制御を呼出し元のデータ挿入処理へ戻す。
【００３９】
ここで、最初に呼び出されたＦｉｎｄＧｒｏｕｐ  の復帰値が１なので（ステップＳ２３）、グループαの下にグループβを挿入する処理を行わずに終了する。こうして、グループαを下位層に持つグループβをグループαの下に挿入することが禁止され、無限階層の形成が防止できる。
【００４０】
図７では、ステップＳ２３においてＦｉｎｄＧｒｏｕｐ  の復帰値が１のときは、そのデータ挿入を常に禁止するフローとなっているが、図３のステップＳ１４と同様のステップを設けて、データ挿入を行うかどうかをユーザに問い合わせるようにしてもよい。これにより、無限階層のデータ構造を許すかどうかをユーザが指示することが可能になる。
【００４１】
以上の実施例では、管理情報の子ポインタを利用して下位層のデータの管理情報を取り出し、識別子の値を調べて、データ構造を判定する方法を用いている。しかし、管理情報がそのデータの上位層にある親を指す情報を持っていれば、親の管理情報を順に取り出して、データ構造を判定することもできる。
【００４２】
図９は、ＣＰＵ１が階層構造データを上方に向かって検索してその構造を判定し、データ挿入を行う処理のフローチャートである。図９において処理が開始されると、まずＣＰＵ１はユーザから階層構造データを構成する第１のデータの下に第２のデータを挿入する指示を受け取る（ステップＳ４１）。次に、第２のデータの識別子が、第１のデータおよびそれより上位のデータのうちいずれかの識別子と一致するかどうかを調べる（ステップＳ４２）。もしいずれのデータの識別子とも一致しなければ、第１のデータの下に第２のデータを挿入して（ステップＳ４３）、処理を終了する。
【００４３】
第１のデータおよびそれより上位のデータの識別子の中に第２のデータの識別子と一致するものがあれば、その旨を入出力機器３を介してユーザに知らせて、データ挿入を行うかどうかを問い合わせる（ステップＳ４４）。そして、ユーザがデータ挿入を許可すれば第１のデータの下に第２のデータを挿入し（ステップＳ４３）、許可しなければそのまま処理を終了する。
【００４４】
挿入先データである第１のデータ以上の階層内に、挿入データである第２のデータの識別子と同じ識別子を持つデータがあるとき、データ挿入を行うことにより上下方向に同じデータ構造が繰り返され、無限階層が生じることになる。図９のデータ挿入処理では、このような場合にユーザがデータ挿入を禁止することができる。
【００４５】
図１０は、図９のようなデータ挿入処理を行う場合のデータの管理情報の形式を示している。図１０において、名称、識別子、子ポインタ、前ポインタ、後ポインタ、および実ポインタについては図５と同様である。親ポインタはそのデータの親データの管理情報を指すポインタであり、階層構造の最上位のデータ（ルート）の場合は何も指さないように設定される。この親ポインタを順に手繰ることにより、挿入先データより上位の階層のデータの管理情報を取り出すことができる。
【００４６】
【発明の効果】
本発明によれば、チェインによって管理されたデータの構造を自動的に判定することが可能になる。これにより、階層構造のデータを操作する際に起こり得る無限階層の形成を未然に防ぐことができ、その階層構造が簡略化され、データ処理の高速化に寄与するところが大きい。
【図面の簡単な説明】
【図１】本発明の原理図である。
【図２】実施例のシステム構成図である。
【図３】下方への検索によるデータ挿入処理のフローチャートである。
【図４】実施例の階層構造データを示す図である。
【図５】データの管理情報の形式を示す図である。
【図６】データの管理情報の例を示す図である。
【図７】データ挿入処理の詳細なフローチャートである。
【図８】サブルーチンのフローチャートである。
【図９】上方への検索によるデータ挿入処理のフローチャートである。
【図１０】親ポインタを持つデータの管理情報の形式を示す図である。
【図１１】階層構造データの例を示す図である。
【図１２】無限階層にならないデータ挿入の例を示す図である。
【図１３】無限階層になるデータ挿入の例を示す図である。
【符号の説明】
１  ＣＰＵ
２  データ格納部
３  入出力機器
４  バス
【図１】
0003549608.tif 000002
【図２】
0003549608.tif 000003
【図３】
0003549608.tif 000004
【図４】
0003549608.tif 000005
【図５】
0003549608.tif 000006
【図６】
0003549608.tif 000007
【図７】
0003549608.tif 000008
【図８】
0003549608.tif 000009
【図９】
0003549608.tif 000010
【図１０】
0003549608.tif 000011
【図１１】
0003549608.tif 000012
【図１２】
0003549608.tif 000013
【図１３】
0003549608.tif 000014