JP2000348038A - 半構造データベースのためのデータ格納装置および方法 - Google Patents

Abstract

(57)【要約】 【課題】 半構造データベースにおいて、大規模なデー
タの検索を効率化することが課題である。 【解決手段】 指定手段１は、木構造データにおいて、
検索対象となる可能性のある部分木の構造を、エッジの
ラベル等を用いて指定する。抽出手段２は、木構造デー
タを走査して、指定された構造に適合する１つ以上の部
分木の情報を抽出し、格納手段３は、抽出された部分木
に含まれるノード、エッジ等の情報を、部分木毎にまと
めて物理的な記憶領域に格納する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、半構造データベー
スを構成するために用いられるデータ格納装置およびそ
の方法に関する。

【０００２】

【従来の技術】従来のリレーショナルデータベースやオ
ブジェクト指向データベース等においては、あらかじめ
データ構造を定義するスキーマとスキーマに従うデータ
の集まりとが管理される。

【０００３】例えば、リレーショナルデータベースを用
いて蔵書目録等を作るときは、書籍のスキーマを作る際
に、著者、書籍名、出版社等の属性を定義する。しか
し、著者の人数は事前に決定できないため、通常は著者
の人数の上限を仮定して、スキーマではその上限の人数
までの繰り返しを定義する。このため、上限を超える数
の著者により執筆された書籍が出現した場合には、その
情報を格納することができない。

【０００４】これに対して、オブジェクト指向データベ
ースでは、スキーマにより任意数の繰り返しを記述でき
るので、このような問題は解決できる。しかし、あらか
じめ想定していた属性と全く異なるものを格納する必要
があるときには、やはり対応することができない。例え
ば、蔵書目録のスキーマに著者の所属組織の属性が定義
されていない場合、研究レポートの研究機関の名前等を
格納することができない。

【０００５】このように、リレーショナルデータベース
やオブジェクト指向データベースを利用できる分野は、
あらかじめ業務の分析ができ、扱うデータの構造を限定
できるような分野である。したがって、外部から新規の
構造のデータを収集して格納する用途には、これらのデ
ータベースは適していない。例えば、小説等を想定した
蔵書目録のスキーマでは、研究レポートのような文献が
飛び込んできた場合に、著者の人数や所属組織等の属性
を格納できずに困ることになる。

【０００６】これに対して、半構造（semi-structured
）データベースでは、リレーショナルデータベースや
オブジェクト指向データベースとは異なり、データ構造
を規定するスキーマがなく、データの中に構造情報が一
緒に管理される。このため、半構造データベースは、あ
らかじめ想定していない新規の構造を持つ未知データ
を、通信ネットワークや外部のソースから収集して格納
していくことが可能である。

【０００７】近年のネットワークの発達により、様々な
業務分野で外部から新規の構造のデータを収集して管理
するシステムが必要になっている。これらの分野におい
ては、新規の構造のデータを格納するために半構造デー
タベースが利用されるようになるだろうと期待される。

【０００８】最近では、半構造データベースが、特に、
ＸＭＬ（extensible markup language）等で記述された
構造化文書のデータベース化に利用できるとして注目を
集めている。ＸＭＬは、電子商取引等で使われるデータ
構造で、その需要は急激に増加しており、これを取り扱
うデータベースやそのデータベースを核としたインフラ
ストラクチャが望まれている。すでに、半構造データベ
ースに格納されることを前提にしたＸＭＬデータに関す
る問い合わせ言語が、Ｗ３Ｃ（The World WideWeb Cons
ortium ）により提案されている。

【０００９】そこで、半構造データベースにおけるデー
タモデルと格納形式について説明する。半構造データベ
ースはスキーマを持たず、データの中に構造情報を持っ
ている。半構造データベースとして提案されているシス
テムはいくつかあるが、そのデータモデルは、おおむね
図３７に示すようなものである。

【００１０】図３７のデータモデルは、ノードとエッジ
（リンク）からなる木構造で表現され、複数の論文に関
するデータを表している。エッジにはデータの属性を表
現するラベルが付けられ、末端のノードには値が格納さ
れる。ラベル“ｐａｐｅｒ”、“ｉｄ”、“ｔｉｔｌ
ｅ”、“ａｕｔｈｏｒ”、“ｎａｍｅ”、“ｐｏｓｉｔ
ｉｏｎ”、“ｐａｇｅ”、“ｆｉｒｓｔｐａｇｅ”、お
よび“ｌａｓｔｐａｇｅ”は、それぞれ、論文、論文Ｉ
Ｄ（識別子）、タイトル、著者、著者名、著者の所属組
織、ページ情報、最初のページ、および最後のページを
表している。

【００１１】このような木構造モデルを表現するため
に、半構造データベースでは、エッジ情報とノード情報
が分離して記憶装置上に格納される。エッジは、その両
端のノードのノードＩＤとエッジのラベルからなるテー
ブル形式で格納され、ノードは、ノードＩＤとノードの
値を納めたレコードからなるテーブル形式で格納され
る。このようなデータモデルと格納形式により、半構造
データベースでは、外部から取得した新規の構造のデー
タを自由に追加することが可能である。

【００１２】また、半構造データベースでは、一般的
に、以下のようなインデックスを用いてデータ検索の高
速化が図られている。 （１）値インデックス 値からノードＩＤを求める値インデックスを使って、検
索条件の値や範囲から、それに適合するノードＩＤを検
索することができる。 （２）構造（パス）インデックス パスからノードＩＤを求める構造インデックスを使っ
て、検索条件のパスからノードＩＤを検索することがで
きる。パスは木構造モデルの枝を指定する情報であり、
通常、１つ以上のエッジのラベルを用いて表される。図
３７のデータモデルの場合は、例えば、“／ｐａｐｅｒ
／ａｕｔｈｏｒ／ｎａｍｅ”というパスと２つのノード
ＩＤ“３”、“６”の対応関係が構造インデックスに登
録され、このパスからノードＩＤ“３”、“６”を検索
できる。 （３）エッジインデックス エッジの両端のノードのノードＩＤに対するエッジイン
デックスを使って、ノードＩＤからそのノードに隣接す
るエッジを求めることができる。これにより、エッジを
辿る（トラバースする）処理が高速化される。

【００１３】

【発明が解決しようとする課題】しかしながら、上述し
た従来の半構造データベースに大規模なデータを格納し
てデータ検索を行う場合、以下の理由により、十分な性
能が得られない可能性がある。 （１）検索対象の部分木に含まれるデータが物理記憶領
域に分散する。

【００１４】ノードおよびエッジの各テーブル内ではレ
コードの並び順に特に制限がないので、図３７の“ｐａ
ｐｅｒ”以下の部分木のような単一の部分木に属するノ
ードやエッジが、物理記憶領域に分散して格納される可
能性がある。このため、この部分木を検索する際に記憶
装置へのアクセスに膨大な時間を要し、検索対象を１つ
のレコードとして格納できるリレーショナルデータベー
スに比べて不利となる。 （２）検索対象の部分木内のトラバースが必要である。

【００１５】例えば、著者名が“金政泰彦”でタイトル
が“ｘｘｘｘ”の“ｐａｐｅｒ”というような検索の場
合、木構造モデルではエッジを辿る処理、すなわち、部
分木内のトラバースが必要になる。エッジインデックス
を用いてトラバースを高速化したとしても、検索対象を
１つのレコードとして格納できるリレーショナルデータ
ベースに比べて不利となる。 （３）構造インデックスは必ずしも効果的ではない。

【００１６】構造インデックスは、データの構造（パ
ス）が多種なわりには同じ構造のデータの数が少ないと
きに、効果の大きな技術である。これに対して、同じ構
造のデータが大量にある場合は、絞り込みがきかず、効
果が小さい。

【００１７】本発明の課題は、半構造データベースにお
いて、大規模なデータの検索を効率化するデータ格納装
置およびその方法を提供することである。

【００１８】

【課題を解決するための手段】図１は、本発明のデータ
格納装置の原理図である。図１のデータ格納装置は、指
定手段１、抽出手段２、および格納手段３を備える。

【００１９】指定手段１は、木構造データにおいて、検
索対象となる可能性のある部分木の構造を指定し、抽出
手段２は、その木構造データから、指定された構造に適
合する部分木を抽出する。そして、格納手段３は、抽出
された部分木の情報をまとめて格納する。

【００２０】検索対象となる可能性のある部分木の構造
とは、木構造データ内でデータ検索の対象となることが
予想されるような部分木を定義する情報である。指定手
段１は、例えば、特定のラベルを指定情報として入力す
ることで、そのラベルを持つエッジの下に接続された部
分木を指定することができる。このような指定情報は、
例えば、ユーザが入力したり、システムが自動的に生成
して入力したりする。

【００２１】抽出手段２は、木構造データを走査して、
指定された構造に適合する１つ以上の部分木の情報を抽
出し、格納手段３は、抽出された部分木に含まれるノー
ド、エッジ等の情報をまとめて格納する。このとき、格
納手段３は、例えば、１つの部分木の情報を物理的に近
接した連続領域にまとめて格納する。したがって、複数
の部分木が抽出された場合には、部分木毎に情報がまと
められて格納される。

【００２２】このようなデータ格納装置によれば、指定
された構造の部分木の情報が分散することなくまとめて
格納されるため、その部分木を検索対象としてデータ検
索が行われたとき、必要な情報に効率良くアクセスする
ことができる。したがって、大規模な半構造データベー
スにおいても、データ検索が効率化される。

【００２３】また、指定手段１は、検索対象となる可能
性のある部分木内の１つ以上のパスを個別に指定して、
それらのパスにより構成される構造を指定することもで
きる。この場合、抽出手段２は、木構造データから、指
定されたパスの末端にあるノードを抽出し、格納手段３
は、抽出されたノードの情報をまとめて格納する。

【００２４】このようなデータ格納装置によれば、１つ
以上のパス上に格納された情報が分散することなくまと
めて格納されるため、それらの情報を検索対象としてデ
ータ検索が行われたとき、必要な情報に効率良くアクセ
スすることができる。

【００２５】例えば、図１の指定手段１は、後述する図
３５の入力装置２３に対応し、図１の抽出手段２は、図
３５のＣＰＵ（中央処理装置）２１とメモリ２２に対応
する。また、図１の格納手段３は、例えば、図３５のメ
モリ２２、外部記憶装置２５、または可搬記録媒体２
９、あるいは、後述する図３６のデータベース３０に対
応する。

【００２６】

【発明の実施の形態】以下、図面を参照しながら、本発
明の実施の形態を詳細に説明する。本実施形態のデータ
格納装置では、半構造データベースの中に存在している
複数の類似の構造を指定して、データアクセスを効率化
するような格納形式を採用する。これにより、リレーシ
ョナルデータベースやオブジェクト指向データベースに
おけるスキーマに基づく最適化と同等の効果が得られ
る。また、既存のリレーショナルデータベースやオブジ
ェクト指向データベースを補助的に用いることで、半構
造データベースにおけるデータ検索が高速化される。

【００２７】まず、木構造モデルの部分木のクラスタリ
ングを行って、木構造モデルをノード毎に分割してデー
タベースに格納することで、検索を高速化することを考
える。データを格納する際に、検索対象となることが予
想される部分木をあらかじめ指定して、その部分木内の
情報を物理的に近接する格納領域（近傍領域）にまとめ
て格納することで、検索を高速化することができる。

【００２８】例えば、図３７の木構造モデルにおいて、
“ｐａｐｅｒ”以下の部分木を検索対象として指定し、
データベースの更新時に、その部分木内の情報をノード
およびエッジの各テーブル内でなるべく連続領域に配置
する。これにより、図２のようなノードテーブルと図３
のようなエッジテーブルが得られる。リレーショナルデ
ータベースの場合は、ノードテーブルとエッジテーブル
がそれぞれ異なるリレーションとして実装される。

【００２９】図２において、“ＩＤ”はノードＩＤを表
し、“ＶＡＬＵＥ”はそのノードの値を表す。ここで
は、ノード“１”、“２”、“３”、“４”、“６”、
“７”、“８”、および“９”に対して、それぞれ、値
“１２”、“○○に関する研究”、“金政泰彦”、“富
士通研究所”、“久保田和己”、“富士通研究所”、
“５８”、および“６３”が格納されている。

【００３０】また、図３において、“ＬＡＢＥＬ”はエ
ッジのラベルを表し、“ＩＤ”はそのエッジの両端のノ
ードのノードＩＤを表す。ここでは、指定された部分木
内の１２個のエッジのラベルと、各エッジの両端のノー
ドのノードＩＤが格納されている。これらのテーブルを
用いれば、１つの“ｐａｐｅｒ”に属する様々な属性デ
ータを、１回のアクセスで記憶装置から主記憶に読み出
すことが可能になる。

【００３１】このように、検索対象となる可能性のある
部分木のノードやエッジを記録媒体の物理的な近傍領域
にまとめて格納することにより、記録媒体アクセスの頻
度が減少し、検索の高速化が図られる。

【００３２】次に、部分木をレコード化して、検索を高
速化することを考える。部分木の一部の情報を１つのレ
コードとして集めることにより、部分木内のトラバース
を軽減して、検索をさらに高速化することができる。部
分木のレコード化は、次のようにして行われる。

【００３３】まず、部分木に選択規則を作用させること
で、レコードを生成する。選択規則は、部分木内の１つ
以上のパスを個別に数え上げて指定する指定情報であ
り、部分木内のパス群を外延的に記述している。この選
択規則は、ユーザまたは外部のシステムから与えられる
か、またはシステムにより自動的に生成される。

【００３４】例えば、図４の部分木Ｔ１は、ノード“ｎ
１”、“ｎ２”、“ｎ３”、“ｎ４”、“ｎ５”、およ
び“ｎ６”と、エッジ“ｅ１”、“ｅ２”、“ｅ３”、
“ｅ４”、“ｅ５”、および“ｅ６”からなっている。

【００３５】部分木Ｔ１に属するパスは、｛ｅ１／ｅ
２，ｅ１／ｅ２，ｅ１／ｅ２，ｅ３，ｅ４／ｅ５，ｅ
６｝の６つである。このうち、５つのパスの末端のノー
ド“ｎ１”、“ｎ２”、“ｎ３”、“ｎ４”、および
“ｎ６”には、それぞれ、値“ａｂｃ”、“ｘｙｚ”、
“ｉｊｋ”、“１００”、および“３００”が格納され
ている。

【００３６】ここで、パス“ｅ１／ｅ２”を出現順に２
つ選択し、パス“ｅ３”および“ｅ６”を出現順に１つ
ずつ選択して、それらの４つのパスを１つのレコードに
まとめることを意味する選択規則｛ｅ１／ｅ２，ｅ１／
ｅ２，ｅ３，ｅ６｝を適用する。この場合、パス“ｅ４
／ｅ５”は選択されない。

【００３７】この選択規則により生成されたレコードｒ
１は、選択されたパスに対応する４つのフィールドｆ
１、ｆ２、ｆ３、およびｆ４を含む。そして、これらの
フィールドには、それぞれ、値“ａｂｃ”、“ｘｙ
ｚ”、“１００”、および“３００”が格納される。こ
のように、各フィールドには、対応するパスにより指定
されるノードの値が格納される。

【００３８】また、図５の部分木Ｔ２は、ノード“ｎ
７”、“ｎ８”、“ｎ９”、“ｎ１０”、および“ｎ１
１”と、エッジ“ｅ１”、“ｅ２”、“ｅ３”、“ｅ
４”、“ｅ５”、“ｅ６”、および“ｅ７”からなって
いる。部分木Ｔ２に属するパスは、｛ｅ１／ｅ２，ｅ
３，ｅ４／ｅ５，ｅ６，ｅ７｝の５つである。このう
ち、３つのパスの末端のノード“ｎ７”、“ｎ８”、お
よび“ｎ１０”には、それぞれ、値“ｌｍｎ”、“４０
０”、および“５００”が格納されている。

【００３９】部分木Ｔ２に、上述の選択規則｛ｅ１／ｅ
２，ｅ１／ｅ２，ｅ３，ｅ６｝を適用すると、レコード
ｒ２が生成される。この場合、フィールドｆ１、ｆ２、
ｆ３、およびｆ４には、それぞれ、値“ｌｍｎ”、“Ｎ
ＵＬＬ”、“４００”、および“５００”が格納され
る。フィールドｆ２の“ＮＵＬＬ”は、選択規則の２番
目のパス“ｅ１／ｅ２”に対応するパスが部分木Ｔ２に
存在しないことを表している。

【００４０】次に、生成されたレコードへのポインタを
部分木に付加する。このとき、部分木のルートに新たな
エッジ“ｅｒ”を付加し、このエッジ“ｅｒ”の先に新
たなノードを生成して、そのノードにレコードへのポイ
ンタを格納する。これにより、部分木のルートとレコー
ドがエッジ“ｅｒ”を介して結合される。そして、レコ
ードに集められたパス群に含まれるエッジとノードを部
分木から削除し、レコードには、新たに生成されたノー
ドへのポインタを格納する。

【００４１】図４および図５のデータにこのような操作
を施すと、図６のようなデータ表現が得られる。図６に
おいては、修正された部分木Ｔ１′およびＴ２′と、選
択規則｛ｅ１／ｅ２，ｅ１／ｅ２，ｅ３，ｅ６｝と、レ
コードｒ１およびｒ２とにより、データ表現が最適化さ
れている。

【００４２】部分木Ｔ１′のルートにはエッジ“ｅｒ”
を介してノード“ｎ１２”が付加され、このノードには
レコードｒ１へのポインタ“ｐ−ｒ１”が格納される。
また、レコードｒ１のフィールドｆ０には、ノード“ｎ
１２”へのポインタ“ｐ−ｎ１２”が格納される。

【００４３】部分木Ｔ２′のルートにはエッジ“ｅｒ”
を介してノード“ｎ１３”が付加され、このノードには
レコードｒ２へのポインタ“ｐ−ｒ２”が格納される。
また、レコードｒ２のフィールドｆ０には、ノード“ｎ
１３”へのポインタ“ｐ−ｎ１３”が格納される。

【００４４】図７は、このようにして最適化された部分
木を繋ぎ合わせた全体木のデータ表現を示している。一
般には、複数の選択規則を用いて部分木の構造を定義す
ることにより、様々な部分木をレコード化することがで
きる。ここでは、２つの選択規則Ｓ１＝｛ｓ１，ｓ２，
ｓ３｝、Ｓ２＝｛ｓ４，ｓ５，ｓ６，ｓ７｝を用いて、
それぞれ異なる部分木群に対応するレコード群Ｒ１、Ｒ
２を生成している。

【００４５】修正された全体木に格納されたポインタｐ
−ｒ１，ｐ−ｒ２，．．．，ｐ−ｒｎは、それぞれ、レ
コード群Ｒ１のレコードｒ１，ｒ２，．．．，ｒｎを指
し、ポインタｐ−ｒ（ｎ＋１），ｐ−ｒ（ｎ＋
２），．．．，ｐ−ｒｍは、それぞれ、レコード群Ｒ２
のレコードｒ（ｎ＋１），ｒ（ｎ＋２），．．．，ｒｍ
を指している。

【００４６】リレーショナルデータベースとのアナロジ
ーでとらえれば、選択規則がスキーマに対応し、レコー
ド群がリレーションに対応し、レコードがタプルに対応
する。また、修正された全体木にレコードへのポインタ
が存在している点が、リレーショナルデータベースとは
異なっている。

【００４７】このような修正された全体木のノードとエ
ッジをテーブル形式で格納すると、図８のようなデータ
ベースが得られる。図８では、ノードテーブルおよびエ
ッジテーブルが、修正された全体木の情報に対応し、選
択規則Ｓ１、Ｓ２とレコード群Ｒ１、Ｒ２に対応する２
つのレコードテーブルが、全体木から削除された情報に
対応する。

【００４８】リレーショナルデータベースの場合は、こ
れらのテーブルがそれぞれ異なるリレーションとして実
装され、選択規則は部分木内のパス群の指定情報として
保存される。こうしてレコード化された部分木に関して
も、レコード用のインデックス等を用いて検索の高速化
を図ることが可能である。

【００４９】次に、このようにして格納されたデータを
検索する手順について説明する。例えば、図３７のよう
な木構造モデルにおいて、選択規則を｛／ｐａｐｅｒ／
ｉｄ／，／ｐａｐｅｒ／ｔｉｔｌｅ／，／ｐａｐｅｒ／
ａｕｔｈｏｒ／ｎａｍｅ／｝として、部分木をレコード
化する。

【００５０】これにより、各論文の論文ＩＤ、タイト
ル、および第１著者名の情報が全体木から削除されて、
それらの値が、それぞれ、レコードのフィールドｆ１、
ｆ２、およびｆ３に格納される。第１著者の所属組織、
第２著者以降の著者名および所属組織、ページ情報等は
全体木に残される。

【００５１】こうして生成された最適化データベースに
おいて、タイトルが“ｘｘｘｘ”で著者名が“ｙｙｙ
ｙ”の論文をデータ検索装置が検索する場合の手順は、
以下のようになる。 ［Ｐ１］まず、データ検索装置は、図９に示すように、
部分木のレコード群において、ｆ２（ｔｉｔｌｅ）およ
びｆ３（ｎａｍｅ）のインデックスを順に使って、与え
られた検索条件“ｆ２：ｘｘｘｘ ＡＮＤ ｆ３：ｙｙ
ｙｙ”を満たすレコードを検索する。そして、得られた
レコードを結果Ａ１として保持する。また、タイトルに
対する検索条件“ｆ２：ｘｘｘｘ”のみを用いて絞り込
みを行い、得られたレコードを中間結果Ｂ１として保持
する。 ［Ｐ２］次に、図１０に示すように、全体木においてパ
ス“／ｐａｐｅｒ／ａｕｔｈｏｒ／ｎａｍｅ／”を用い
て第２著者以降の著者名を検索し、著者名に対する検索
条件“ｙｙｙｙ”を満たすノード“６”を求める。そし
て、そのノードからエッジを辿ってその部分木に含まれ
るエッジ“ｅｒ”を求め、そのエッジの先のノード“１
４”に格納されたレコードへのポインタ“ｐ−ｒｉ”を
取り出す。このような処理を繰り返して、得られたポイ
ンタの集合｛ｐ−ｒｉ，ｐ−ｒｊ，．．．｝を中間結果
Ｂ２として保持する。 ［Ｐ３］次に、中間結果Ｂ１と中間結果Ｂ２をジョイン
して、中間結果Ｂ２の各ポインタが指すレコードを中間
結果Ｂ１から抽出し、得られたレコードを結果Ａ２とし
て保持する。 ［Ｐ４］結果Ａ１は、タイトルが“ｘｘｘｘ”で第１著
者名が“ｙｙｙｙ”の論文のレコードに対応し、結果Ａ
２は、タイトルが“ｘｘｘｘ”で第２著者以降の著者名
が“ｙｙｙｙ”の論文のレコードに対応する。そこで、
結果Ａ１と結果Ａ２のユニオン（和集合）を求めて、検
索結果とする。

【００５２】これらのレコードのフィールドｆ１の論文
ＩＤを用いれば、論文のテキストや添付図等の情報を得
ることができる。また、ページ情報等の全体木に残って
いる属性データを求める場合は、レコードのフィールド
ｆ０のポインタを用いて、全体木に残された部分木を辿
ればよい。

【００５３】この検索方法の特徴は、［Ｐ１］のレコー
ド群の検索にあり、レコード化された部分木を用いるこ
とで、部分木内のトラバースを抑制することができる。
したがって、検索対象のレコード化率を上げれば、検索
速度をリレーショナルデータベースに近づけることが可
能である。また、［Ｐ１］と［Ｐ２］の処理を並列に行
えば、検索速度はさらに向上する。

【００５４】次に、上述した部分木のクラスタリングと
選択的レコード化の処理について、より詳細に説明す
る。まず、図３７の部分木のクラスタリングにおいて、
図２のノードテーブルと図３のエッジテーブルをリレー
ショナルデータベースのテーブルとして格納する場合を
考える。この場合、データベースへのアクセスには、Ｓ
ＱＬ（structured query language ）等のインタフェー
スが用いられる。ここでは、高速化のため、図３のエッ
ジテーブルを図１１、１２、１３に示す３つのテーブル
に分割して格納し、さらに、図１４のパステーブルを追
加している。これらのテーブルは、それぞれ、リレーシ
ョナルデータベースの異なるリレーションとして実装さ
れる。

【００５５】図１１のラベルテーブルは、ラベルＩＤ
（ＬＡＢＥＬＩＤ）とラベル（ＬＡＢＥＬ）の対応関係
を格納し、図１２の親ノードテーブルは、ノードＩＤ
（ＩＤ）、そのノードの親ノードのノードＩＤ（ＰＡＲ
ＥＮＴ）、およびそれらのノードを結ぶエッジのラベル
のラベルＩＤ（ＬＡＢＥＬＩＤ）の対応関係を格納す
る。

【００５６】また、図１３の子ノードテーブルは、ノー
ドＩＤ（ＩＤ）、そのノードの子ノードのノードＩＤ
（ＣＨＩＬＤ）、およびそれらのノードを結ぶエッジの
ラベルのラベルＩＤ（ＬＡＢＥＬＩＤ）の対応関係を格
納し、図１４のパステーブルは、ノードＩＤ（ＩＤ）と
ルートノードからそのノードに至るパス（ＰＡＴＨ）の
対応関係を格納する。

【００５７】ノードテーブルは、値インデックスとして
用いることができ、親ノードテーブルと子ノードテーブ
ルは、エッジインデックスとして用いることができ、パ
ステーブルは、構造インデックスとして用いることがで
きる。

【００５８】これらのテーブルで用いられる属性データ
のデータ型と長さは、例えば、図１５に示すようにな
る。図１５において、データ型“ＮＵＭＢＥＲ”は数を
表し、データ型“ＶＡＲＣＨＡＲ２”は可変長文字列を
表す。また、図２のノードテーブルと図１１のラベルテ
ーブルは、それぞれ、深さ優先（depth-first traversa
l ）アルゴリズムによりクラスタリングされている。

【００５９】明示的に検索対象の部分木を指定しないで
クラスタリングを行う場合は、全体木に対してクラスタ
リングのアルゴリズムを指定することにより、階層的に
部分木がクラスタリングされる。したがって、図３７に
示されていない他の論文の部分木についても、同様のク
ラスタリングが行われ、その結果が各テーブルに追加さ
れる。このようなクラスタリングによれば、木構造モデ
ルの各階層において、１つの部分木に属するノードやエ
ッジの情報が近傍領域にまとめて格納され、検索が高速
化される。

【００６０】図１６は、このようなクラスタリングに基
づくデータ格納処理のフローチャートである。データ格
納装置は、まず、ルートノードを現在ノードとしてセッ
トし（ステップＳＴ１）、現在ノードをデータベースに
格納する（ステップＳＴ２）。

【００６１】次に、現在ノードが終端ノードか否かをチ
ェックする（ステップＳＴ３）。終端ノードとは、図３
７のノード“３”等のように、それより下にエッジが存
在しないノードを意味する。現在ノードが終端ノードで
なければ、まだトラバースされていないエッジの１つを
選択し、現在エッジとしてセットする（ステップＳＴ
７）。そして、現在エッジを下方向にトラバースして、
子ノードを現在ノードにセットし（ステップＳＴ８）、
ステップＳＴ２以降の処理を繰り返す。ステップＳＴ２
では、現在ノードと現在エッジがデータベースに格納さ
れる。

【００６２】ステップＳＴ３において、現在ノードが終
端ノードであれば、現在エッジを上方向にトラバースし
て、親ノードを現在ノードにセットする（ステップＳＴ
４）。そして、現在ノードのすべてのエッジについて、
下方向のトラバースが終了したか否かをチェックし（ス
テップＳＴ５）、トラバースされていないエッジがあれ
ば、ステップＳＴ２以降の処理を繰り返す。

【００６３】ステップＳＴ５において、すべてのエッジ
が下方向にトラバースされていれば、現在ノードがルー
トノードか否かをチェックする（ステップＳＴ６）。現
在ノードがルートノードでなければ、ステップＳＴ４以
降の処理を繰り返し、現在ノードがルートノードであれ
ば、処理を終了する。

【００６４】図１７は、図１６のステップＳＴ２におけ
る現在ノードと現在エッジの格納処理のフローチャート
である。データ格納装置は、まず、現在ノードをノード
テーブルに追加する（ステップＳＴ１１）。次に、現在
エッジが選択されていれば、そのラベルが新規のラベル
か否かをチェックする（ステップＳＴ１２）。ここで、
ラベルテーブルに存在しないラベルは、新規のラベルと
みなされる。

【００６５】現在エッジのラベルが新規のラベルでなけ
れば、現在ノードに関する情報を親ノードテーブルに追
加し（ステップＳＴ１３）、現在ノードのパスをパステ
ーブルに追加して（ステップＳＴ１４）、図１６の処理
に復帰する。また、ステップＳＴ１２において、現在エ
ッジのラベルが新規のラベルであれば、そのラベルをラ
ベルテーブルに追加して（ステップＳＴ１５）、ステッ
プＳＴ１３以降の処理を行う。

【００６６】また、図１８は、図１６のステップＳＴ８
における下方向のトラバース処理のフローチャートであ
る。データ格納装置は、まず、現在エッジに関する情報
を子ノードテーブルに追加する（ステップＳＴ２１）。
そして、現在エッジの先の子ノードを現在ノードにセッ
トして（ステップＳＴ２２）、図１６の処理に復帰す
る。

【００６７】このようなデータ格納処理により、半構造
データベースの木構造モデルがリレーショナルデータベ
ースに格納される。ラベルテーブル、親ノードテーブ
ル、および子ノードテーブルの代わりに、図３のような
エッジテーブルを用いる場合も同様である。また、リレ
ーショナルデータベースの代わりにオブジェクト指向デ
ータベースを利用する場合は、各テーブルのレコードに
対応するオブジェクトを生成して、オブジェクト指向デ
ータベースに格納すればよい。

【００６８】また、ノードテーブル、ラベルテーブル、
親ノードテーブル、子ノードテーブル、およびパステー
ブルをリレーショナルデータベースに格納する代わり
に、直接、ページ管理機構上に実装することも可能であ
る。ページとは、あらかじめ決められた固定長の格納領
域（ブロック）に格納された情報に対応する。ページ管
理機構上に実装する場合、５つのテーブルのそれぞれに
対応するページが用意される。

【００６９】この場合のデータ格納処理は、基本的に図
１６と同様であるが、ステップＳＴ２における現在ノー
ドと現在エッジの格納処理は、図１９に示すようにな
る。データ格納装置は、まず、現在ノードをノードのペ
ージに追加し（ステップＳＴ３１）。現在エッジのラベ
ルが新規のラベルか否かをチェックする（ステップＳＴ
３２）。

【００７０】現在エッジのラベルが新規のラベルでなけ
れば、現在ノードに関する情報を親ノードのページに追
加し（ステップＳＴ３３）、現在ノードのパスをパスの
ページに追加して（ステップＳＴ３４）、図１６の処理
に復帰する。また、ステップＳＴ３２において、現在エ
ッジのラベルが新規のラベルであれば、そのラベルをラ
ベルのページに追加して（ステップＳＴ３５）、ステッ
プＳＴ３３以降の処理を行う。

【００７１】ステップＳＴ３１、ＳＴ３３、ＳＴ３４、
およびＳＴ３５において、格納領域が不足する場合は、
データ格納装置は、新たなページを確保する。また、情
報を追加する毎に、アクセスのためのインデックスを更
新する。

【００７２】また、図１６のステップＳＴ８における下
方向のトラバース処理は、図２０に示すようになる。デ
ータ格納装置は、まず、現在エッジに関する情報を子ノ
ードのページに追加し、インデックスを更新する（ステ
ップＳＴ４１）。このとき、格納領域が不足する場合
は、新たなページを確保する。そして、現在エッジの先
の子ノードを現在ノードにセットして（ステップＳＴ４
２）、図１６の処理に復帰する。

【００７３】ところで、リレーショナルデータベースに
は、複数のテーブルを共通属性でクラスタリングする機
能を持つものがある。このクラスタリング機能を利用し
て、ノードテーブル、親ノードテーブル、および子ノー
ドテーブルをノードＩＤでクラスタリングすることがで
きる。この場合のデータ格納処理は、図１６、１７、１
８の処理と同様である。このようなクラスタリングによ
り、記憶装置アクセスをさらに削減することができる。

【００７４】また、共通属性によるクラスタリングをペ
ージ管理機構上で実現する場合は、ノードテーブル、親
ノードテーブル、および子ノードテーブルに対応する共
通のページと、ラベルテーブルおよびパステーブルのそ
れぞれに対応するページが用意される。

【００７５】この場合のデータ格納処理は、基本的に図
１６と同様であるが、ステップＳＴ２における現在ノー
ドと現在エッジの格納処理は、図２１に示すようにな
る。図２１のステップＳＴ５１〜ＳＴ５５の処理は、基
本的に図１９のステップＳＴ３１〜ＳＴ３５と同様であ
る。ただし、ステップＳＴ５１、ＳＴ５３、およびＳＴ
５４においては、ノードテーブル、親ノードテーブル、
および子ノードテーブルに対応する共通のページに情報
が追加される。

【００７６】また、図１６のステップＳＴ８における下
方向のトラバース処理は、図２２に示すようになる。図
２２のステップＳＴ６１、ＳＴ６２の処理は、基本的に
図２０のステップＳＴ４１、ＳＴ４２と同様である。た
だし、ステップＳＴ６１においては、ノードテーブル、
親ノードテーブル、および子ノードテーブルに対応する
共通のページが新たに作成され、そのページに情報が追
加される。

【００７７】次に、部分木内のパス群を記述する選択規
則を用いて、部分木の選択的レコード化を行う場合を考
える。例えば、図２３のような木構造のデータモデルが
与えられたとき、検索対象として“ｐａｐｅｒ”以下の
部分木を指定し、その部分木に選択規則を作用させて、
全体木を最適化する。

【００７８】図２３において、ラベル“ｐｏｓ．”、
“ｆｉｒｓｔ．”、および“ｌａｓｔ．”は、それぞ
れ、“ｐｏｓｉｔｉｏｎ”、“ｆｉｒｓｔｐａｇｅ”、
および“ｌａｓｔｐａｇｅ”と等価であるものとする。
また、選択規則としては、ｓ＝｛ｉｄ，ｔｉｔｌｅ，ａ
ｕｔｈｏｒ／ｎａｍｅ，ａｕｔｈｏｒ／ｐｏｓｉｔｉｏ
ｎ，ａｕｔｈｏｒ／ｎａｍｅ，ａｕｔｈｏｒ／ｐｏｓｉ
ｔｉｏｎ｝が用いられる。

【００７９】このとき、選択規則ｓにより最適化された
全体木とレコード群は、図２４のようになる。ここで
は、選択規則ｓにより、２つの論文の部分木に対応する
２つのレコードｒ１およびｒ２が生成され、レコードテ
ーブルに格納されている。また、全体木において、ラベ
ル“ｓ”を有するエッジの先のノードには、生成された
レコードのＩＤがそのレコードへのポインタとして格納
されている。ノード“２９”は、レコードｒ１のＩＤ
“１”を格納し、ノード“３０”は、レコードｒ２のＩ
Ｄ“２”を格納する。

【００８０】また、レコードテーブルのレコードｒ１お
よびｒ２の先頭のフィールドｆｉｄには、レコードＩＤ
が格納され、２番目のフィールドｆ０には、全体木の対
応するノードのノードＩＤがポインタとして格納され
る。３番目以降のフィールドｆ１〜ｆ６は、選択規則ｓ
の６つのパスに対応し、それぞれ、対応するパスの末端
のノードの値を格納している。

【００８１】例えば、レコードｒ１のフィールドｆ１、
ｆ２、ｆ３、ｆ４、ｆ５、およびｆ６には、それぞれ、
値“ｉｄ１”、“ｘｘｘｘ”、“ｎａｍｅ１”、“ｐｏ
ｓ１”、“ｎａｍｅ２”、および“ｐｏｓ２”が格納さ
れている。

【００８２】図２４のデータ構造をリレーショナルデー
タベースに格納する場合は、全体木に対応して図２５か
ら図２９までに示すような５つのテーブルが生成され
る。図２５はノードテーブルを表し、図２６はラベルテ
ーブルを表し、図２７は親ノードテーブルを表し、図２
８は子ノードテーブルを表し、図２９はパステーブルを
表す。これらの５つのテーブルと図２４のレコードテー
ブルとを合わせて、合計６つのテーブルが格納される。

【００８３】このように、検索対象の部分木に選択規則
を適用してレコード化を行う場合も、深さ優先アルゴリ
ズムのような適当なアルゴリズムを用いてクラスタリン
グを行うことができる。この場合のデータ格納処理は、
基本的に図１６と同様であるが、ステップＳＴ２におけ
る現在ノードと現在エッジの格納処理は、図３０に示す
ようになる。

【００８４】データ格納装置は、まず、現在ノードが選
択規則を満たすか否かをチェックする（ステップＳＴ７
１）。現在ノードが選択規則を満たさなければ、現在ノ
ードをノードテーブルに追加する（ステップＳＴ７
２）。次に、現在エッジが選択されていれば、そのラベ
ルが新規のラベルか否かをチェックする（ステップＳＴ
７３）。

【００８５】現在エッジのラベルが新規のラベルでなけ
れば、現在ノードを親ノードテーブルに追加し、現在ノ
ードのパスをパステーブルに追加して（ステップＳＴ７
４）、現在エッジが指定された部分木の先頭に対応する
か否かをチェックする（ステップＳＴ７５）。そして、
現在エッジが部分木の先頭に対応しなければ、図１６の
処理に復帰する。

【００８６】また、ステップＳＴ７１において、現在ノ
ードが選択規則を満たせば、現在ノードの値をレコード
の対応するフィールドに格納し（ステップＳＴ７６）、
ステップＳＴ７３以降の処理を行う。

【００８７】また、ステップＳＴ７３において、現在エ
ッジのラベルが新規のラベルであれば、そのラベルをラ
ベルテーブルに追加して（ステップＳＴ７７）、ステッ
プＳＴ７４以降の処理を行う。

【００８８】また、ステップＳＴ７５において、現在エ
ッジが部分木の先頭に対応していれば、その部分木の情
報を格納するレコードを生成し、各フィールドに“ＮＵ
ＬＬ”を格納して、レコードを初期化する（ステップＳ
Ｔ７８）。次に、現在ノードとレコードの間のエッジを
生成し、そのエッジのラベルが新規のラベルか否かをチ
ェックする（ステップＳＴ７９）。

【００８９】生成されたエッジのラベルが新規のラベル
でなければ、そのエッジを親ノードテーブルと子ノード
テーブルに追加し（ステップＳＴ８０）、図１６の処理
に復帰する。生成されたエッジのラベルが新規のラベル
であれば、そのエッジのラベルをラベルテーブルに追加
し（ステップＳＴ８１）、ステップＳＴ８０以降の処理
を行う。

【００９０】例えば、図２３において、現在ノードがノ
ード“１２”であり、現在エッジが“ｐａｐｅｒ”であ
る場合、現在エッジは指定された部分木の先頭に対応す
ることになる。そこで、図２４に示すように、この部分
木に対応するレコードｒ１が生成される（ステップＳＴ
７８）。また、ノード“１２”とレコードｒ１の間のエ
ッジ“ｓ”が生成され、このエッジの情報が図２７の親
ノードテーブルと図２８の子ノードテーブルに追加され
る（ステップＳＴ８０）。

【００９１】図２４ではラベル“ｓ”を持つ２つのエッ
ジが生成されているが、最初のエッジ“ｓ”が生成され
たときに、ラベル“ｓ”がラベルテーブルに追加され
（ステップＳＴ８１）、２番目のエッジ“ｓ”が生成さ
れたときは、ラベルの追加は行われない。

【００９２】また、図２３において、現在ノードがノー
ド“１”であり、現在エッジが“ｉｄ”である場合、ノ
ード“１”は、選択規則ｓに含まれる最初のパス“ｉ
ｄ”に対応するため、選択規則ｓを満たしていることが
分かる。そこで、このノードの値“ｉｄ１”が、図２４
のレコードｒ１のフィールドｆ１に格納される（ステッ
プＳＴ７６）。ノード“２”、“３”、“４”、
“６”、“７”の値についても、同様にしてレコードｒ
１に格納される。

【００９３】また、図１６のステップＳＴ８における下
方向トラバース処理は、図１８と同様であるが、現在エ
ッジがレコードへのエッジである場合は、そのレコード
のレコードＩＤを格納するノードが現在ノードにセット
される。

【００９４】例えば、図２４において、現在エッジがノ
ード“１２”とノード“２９”の間のエッジ“ｓ”であ
る場合、ノード“２９”が新たな現在ノードとなる。こ
のとき、図３０のステップＳＴ７２においては、ノード
“２９”に対応するレコードｒ１のＩＤ“１”が図２５
のノードテーブルに格納される。現在エッジがノード
“２７”とノード“３０”の間のエッジ“ｓ”である場
合も、同様にして、レコードｒ２のＩＤ“２”がノード
テーブルに格納される。

【００９５】また、これらのテーブルをリレーショナル
データベースに格納する代わりに、直接、ページ管理機
構上に実装することも可能である。この場合のデータ格
納処理も、基本的に図１６と同様であるが、ステップＳ
Ｔ２における現在ノードと現在エッジの格納処理は、図
３１に示すようになる。

【００９６】データ格納装置は、まず、現在ノードが選
択規則を満たすか否かをチェックする（ステップＳＴ９
１）。現在ノードが選択規則を満たさなければ、現在ノ
ードをノードのページに追加する（ステップＳＴ９
２）。次に、現在エッジが選択されていれば、そのラベ
ルが新規のラベルか否かをチェックする（ステップＳＴ
９３）。

【００９７】現在エッジのラベルが新規のラベルでなけ
れば、現在ノードを親ノードのページに追加し、現在ノ
ードのパスをパスのページに追加して（ステップＳＴ９
４）、現在エッジが指定された部分木の先頭に対応する
か否かをチェックする（ステップＳＴ９５）。そして、
現在エッジが部分木の先頭に対応しなければ、図１６の
処理に復帰する。

【００９８】また、ステップＳＴ９１において、現在ノ
ードが選択規則を満たせば、現在ノードの値をレコード
の対応するフィールドに格納し（ステップＳＴ９６）、
ステップＳＴ９３以降の処理を行う。

【００９９】また、ステップＳＴ９３において、現在エ
ッジのラベルが新規のラベルであれば、そのラベルをラ
ベルのページに追加して（ステップＳＴ９７）、ステッ
プＳＴ９４以降の処理を行う。

【０１００】また、ステップＳＴ９５において、現在エ
ッジが部分木の先頭に対応していれば、その部分木の情
報を格納するレコードを生成し、そのレコードを初期化
する（ステップＳＴ９８）。次に、現在ノードとレコー
ドの間のエッジを生成し、そのエッジのラベルが新規の
ラベルか否かをチェックする（ステップＳＴ９９）。

【０１０１】生成されたエッジのラベルが新規のラベル
でなければ、そのエッジを親ノードのページと子ノード
のページに追加し（ステップＳＴ１００）、図１６の処
理に復帰する。生成されたエッジのラベルが新規のラベ
ルであれば、そのエッジのラベルをラベルのページに追
加し（ステップＳＴ１０１）、ステップＳＴ１００以降
の処理を行う。

【０１０２】ステップＳＴ９２、ＳＴ９４、ＳＴ９７、
ＳＴ１００、およびＳＴ１０１において、格納領域が不
足する場合は、データ格納装置は、新たなページを確保
する。また、情報を追加する毎に、アクセスのためのイ
ンデックスを更新する。

【０１０３】また、図１６のステップＳＴ８における下
方向トラバース処理は、図２０と同様であるが、現在エ
ッジがレコードへのエッジである場合は、そのレコード
のレコードＩＤを格納するノードが現在ノードにセット
される。

【０１０４】また、前述したように、リレーショナルデ
ータベースにおいて、複数のテーブルを共通属性でクラ
スタリングする機能を利用して、ノードテーブル、親ノ
ードテーブル、および子ノードテーブルをノードＩＤで
クラスタリングしてもよい。さらに、共通属性によるク
ラスタリングをページ管理機構上で実現することも可能
である。

【０１０５】次に、本実施形態のデータ格納方法を、Ｘ
ＭＬで記述された構造化文書に適用した例について説明
する。図３２は、ＸＭＬ文書のデータの例を示してい
る。図３２において、例えば、最も外側のタグ＜ｐａｐ
ｅｒ＞と＜／ｐａｐｅｒ＞の間には、１つの論文に関す
る情報が記述されている。また、その内側のタグ＜ｉｄ
＞と＜／ｉｄ＞の間には、その論文のＩＤが記述され、
タグ＜ｔｉｔｌｅ＞と＜／ｔｉｔｌｅ＞の間には、その
論文のタイトルが記述されている。一般には、多数の論
文がデータベースに登録されるため、各論文について同
様のＸＭＬデータが作成される。

【０１０６】このように、ＸＭＬデータでは、複数のタ
グの包含関係が階層的なデータ構造を表しており、対応
する２つのタグの間のデータを階層的な部分木とみなせ
ば、ＸＭＬデータを木構造データに置き換えることがで
きる。例えば、図３２のＸＭＬデータを木構造で表す
と、図３７に示したデータが得られる。ここでは、タグ
の名称をエッジのラベルとして用いており、ルートノー
ド“１３”には、図３２の論文以外の論文の部分木も接
続されている。

【０１０７】このようにして、ＸＭＬデータを木構造デ
ータとみなすことにより、検索対象となる可能性のある
部分木の構造を指定したり、その部分木内のパス群を指
定したりすることができ、ＸＭＬデータをリレーショナ
ルデータベースに格納したり、ページに格納したりする
ことができる。図３７の木構造データの格納処理および
クラスタリング方法については、上述した通りである。

【０１０８】図３２のＸＭＬデータを図２、図１１〜図
１４のようなテーブル形式でリレーショナルデータベー
スに格納した場合、テーブルへのアクセスはＳＱＬ等を
用いて行われる。例えば、‘著者名が“○△◇☆”であ
る論文のタイトルをｓｅｌｅｃｔせよ’という問い合わ
せを行う場合のＳＱＬ文は、図３３に示すようになる。

【０１０９】さらに、ＸＭＬデータを選択的にレコード
化する場合、データ格納装置は、対話的に選択規則を生
成する。このとき、文書型定義（document type defini
tion，ＤＴＤ）やＸＭＬデータを解析して、図３４のよ
うなダイアログ画面をディスプレイに表示する。文書型
定義は、ＸＭＬ文書のタグ構造を定義するスキーマに対
応し、これを解析することで、木構造データにおけるパ
スを抽出することができる。

【０１１０】図３４において、ユーザは、ボックス１１
に選択規則の名称を入力し、ボックス１２に適当なエッ
ジのラベルを入力すると、そのラベルを持つエッジ以下
の部分木がレコード化の対象として指定される。そし
て、その部分木に含まれるすべてのパスが、自動的にボ
ックス１３内に表示される。

【０１１１】次に、ユーザが表示されたパスのうち所望
のものを選択すると、選択されたパスが選択規則として
登録される。このような処理を対話的に繰り返すことに
より、複数の選択規則を生成することができる。そし
て、データ格納装置は、図７に示したように、生成され
た選択規則毎にレコード化を行い、レコードテーブルを
生成する。

【０１１２】また、データ格納装置は、ＸＭＬデータ以
外にも、任意のＳＧＭＬ（standardgeneralized markup
language）で記述された構造化文書を、同様にして格
納することができる。例えば、ＨＴＭＬ（hypertext ma
rkup language ）データの場合も、同様にして、タグ構
造が木構造に置き換えられる。

【０１１３】ところで、本実施形態のデータ格納装置
は、図３５に示すような情報処理装置（コンピュータ）
を用いて構成することができる。図３５の情報処理装置
は、ＣＰＵ（中央処理装置）２１、メモリ２２、入力装
置２３、出力装置２４、外部記憶装置２５、媒体駆動装
置２６、およびネットワーク接続装置２７を備え、それ
らはバス２８により互いに接続されている。

【０１１４】メモリ２２は、例えば、ＲＯＭ（read onl
y memory）、ＲＡＭ（random access memory）等を含
み、処理に用いられるプログラムとデータを格納する。
ＣＰＵ２１は、メモリ２２を利用してプログラムを実行
することにより、必要な処理を行う。

【０１１５】入力装置２３は、例えば、キーボード、ポ
インティングデバイス、タッチパネル等であり、ユーザ
からの指示や情報の入力に用いられる。出力装置２４
は、例えば、ディスプレイ、プリンタ、スピーカ等であ
り、ユーザへのメッセージや処理結果の出力に用いられ
る。

【０１１６】外部記憶装置２５は、例えば、磁気ディス
ク装置、光ディスク装置、光磁気ディスク（magneto-op
tical disk）装置等であり、上述した様々なテーブル等
を格納するデータベースとして用いられる。また、情報
処理装置は、この外部記憶装置２５に、上述のプログラ
ムとデータを保存しておき、必要に応じて、それらをメ
モリ２２にロードして使用することができる。

【０１１７】媒体駆動装置２６は、可搬記録媒体２９を
駆動し、その記録内容にアクセスする。可搬記録媒体２
９としては、メモリカード、フロッピーディスク、ＣＤ
−ＲＯＭ（compact disk read only memory ）、光ディ
スク、光磁気ディスク等、任意のコンピュータ読み取り
可能な記録媒体が用いられる。ユーザは、この可搬記録
媒体２９に上述のプログラムとデータを格納しておき、
必要に応じて、それらをメモリ２２にロードして使用す
ることができる。

【０１１８】ネットワーク接続装置２７は、任意のネッ
トワーク（回線）を介して外部の装置と通信し、通信に
伴うデータ変換を行う。情報処理装置は、必要に応じ
て、ネットワーク接続装置２７を介して上述のプログラ
ムとデータを外部の装置から受け取り、それらをメモリ
２２にロードして使用することができる。

【０１１９】図３６は、図３５の情報処理装置にプログ
ラムとデータを供給することのできるコンピュータ読み
取り可能な記録媒体を示している。可搬記録媒体２９や
外部のデータベース３０に保存されたプログラムとデー
タは、メモリ２２にロードされる。そして、ＣＰＵ２１
は、そのデータを用いてそのプログラムを実行し、必要
な処理を行う。

【０１２０】

【発明の効果】本発明によれば、半構造データベース等
において、木構造データの部分木を対象とするデータ検
索が行われたとき、その部分木のデータをまとめて読み
出すことができ、検索が高速化される。また、部分木の
データの一部をレコード化することにより、検索がさら
に高速化される。

【図面の簡単な説明】

【図１】本発明のデータ格納装置の原理図である。

【図２】第１のノードテーブルを示す図である。

【図３】エッジテーブルを示す図である。

【図４】第１の部分木のレコード化を示す図である。

【図５】第２の部分木のレコード化を示す図である。

【図６】最適化された部分木を示す図である。

【図７】第１の最適化された全体木を示す図である。

【図８】全体木の格納形式を示す図である。

【図９】第１のデータ検索を示す図である。

【図１０】第２のデータ検索を示す図である。

【図１１】第１のラベルテーブルを示す図である。

【図１２】第１の親ノードテーブルを示す図である。

【図１３】第１の子ノードテーブルを示す図である。

【図１４】第１のパステーブルを示す図である。

【図１５】各属性のデータ型と長さを示す図である。

【図１６】データ格納処理のフローチャートである。

【図１７】第１のノード／エッジ格納処理のフローチャ
ートである。

【図１８】第１の下方向トラバース処理のフローチャー
トである。

【図１９】第２のノード／エッジ格納処理のフローチャ
ートである。

【図２０】第２の下方向トラバース処理のフローチャー
トである。

【図２１】第３のノード／エッジ格納処理のフローチャ
ートである。

【図２２】第３の下方向トラバース処理のフローチャー
トである。

【図２３】２つの論文に関する木構造データを示す図で
ある。

【図２４】第２の最適化された全体木を示す図である。

【図２５】第２のノードテーブルを示す図である。

【図２６】第２のラベルテーブルを示す図である。

【図２７】第２の親ノードテーブルを示す図である。

【図２８】第２の子ノードテーブルを示す図である。

【図２９】第２のパステーブルを示す図である。

【図３０】第４のノード／エッジ格納処理のフローチャ
ートである。

【図３１】第５のノード／エッジ格納処理のフローチャ
ートである。

【図３２】ＸＭＬデータを示す図である。

【図３３】ＳＱＬ文を示す図である。

【図３４】ダイアログ画面を示す図である。

【図３５】情報処理装置の構成図である。

【図３６】記録媒体を示す図である。

【図３７】複数の論文に関する木構造データを示す図で
ある。

【符号の説明】

１ 指定手段 ２ 抽出手段 ３ 格納手段 １１、１２、１３ ボックス ２１ ＣＰＵ ２２ メモリ ２３ 入力装置 ２４ 出力装置 ２５ 外部記憶装置 ２６ 媒体駆動装置 ２７ ネットワーク接続装置 ２８ バス ２９ 可搬記録媒体 ３０ データベース

フロントページの続き (72)発明者 久保田 和己 神奈川県川崎市中原区上小田中４丁目１番 １号 富士通株式会社内 (72)発明者 野口 泰生 神奈川県川崎市中原区上小田中４丁目１番 １号 富士通株式会社内 Ｆターム(参考） 5B075 NK04 NK44 NK46 NR06 QT06 QT10 5B082 BA09 GA02

Claims (14)

【特許請求の範囲】
1. 【請求項１】 木構造データにおいて、検索対象となる
   可能性のある部分木の構造を指定する指定手段と、 前記木構造データから、指定された構造に適合する部分
   木を抽出する抽出手段と、 抽出された部分木の情報をまとめて格納する格納手段と
   を備えることを特徴とするデータ格納装置。
2. 【請求項２】 前記指定手段は、前記検索対象となる可
   能性のある部分木内の１つ以上のパスを個別に指定し、
   前記抽出手段は、前記木構造データから、指定されたパ
   スの末端にあるノードを抽出し、前記格納手段は、抽出
   されたノードの情報をまとめて格納することを特徴とす
   る請求項１記載のデータ格納装置。
3. 【請求項３】 木構造データをノードとエッジに分離し
   て格納するデータ格納装置であって、 前記木構造データにおいて、検索対象となる可能性のあ
   る部分木の構造を指定する指定手段と、 前記木構造データから、指定された構造に適合する部分
   木を抽出する抽出手段と、 抽出された部分木のノードの情報をまとめて格納するノ
   ード格納手段と、 抽出された部分木のエッジの情報をまとめて格納するエ
   ッジ格納手段とを備えることを特徴とするデータ格納装
   置。
4. 【請求項４】 前記ノード格納手段の格納領域は、リレ
   ーショナルデータベースの１つのリレーションとして実
   装され、前記エッジ格納手段の格納領域は、該リレーシ
   ョナルデータベースの１つ以上のリレーションとして実
   装されることを特徴とする請求項３記載のデータ格納装
   置。
5. 【請求項５】 前記指定手段は、タグで構造化された文
   書データを前記木構造データとみなし、該文書データ内
   の２つのタグの間の情報を部分木とみなして、前記検索
   対象となる可能性のある部分木の構造を指定することを
   特徴とする請求項３記載のデータ格納装置。
6. 【請求項６】 前記検索対象となる可能性のある部分木
   の一部の情報をレコードとして格納するレコード格納手
   段をさらに備え、前記指定手段は、前記検索対象となる
   可能性のある部分木内の１つ以上のパスをパス群として
   指定し、前記抽出手段は、前記木構造データから、指定
   されたパスの末端にあるノードを抽出し、前記レコード
   格納手段は、抽出されたノードの情報をレコードとして
   まとめて格納し、前記エッジ格納手段は、該レコード格
   納手段内のレコードに対応するパスを構成するエッジの
   情報の格納を省略することを特徴とする請求項３記載の
   データ格納装置。
7. 【請求項７】 前記レコード格納手段の格納領域は、リ
   レーショナルデータベースの１つのリレーションとして
   実装されることを特徴とする請求項６記載のデータ格納
   装置。
8. 【請求項８】 前記ノード格納手段の格納領域は、リレ
   ーショナルデータベースの１つのリレーションとして実
   装され、前記エッジ格納手段の格納領域は、該リレーシ
   ョナルデータベースの１つ以上のリレーションとして実
   装され、前記レコード格納手段の格納領域は、該リレー
   ショナルデータベースの１つのリレーションとして実装
   されることを特徴とする請求項６記載のデータ格納装
   置。
9. 【請求項９】 前記指定手段が複数のパス群を指定した
   とき、該複数のパス群の指定情報を格納する指定情報格
   納手段をさらに備え、前記レコード格納手段は、前記複
   数のパス群のそれぞれに対応するレコードを格納するこ
   とを特徴とする請求項６記載のデータ格納装置。
10. 【請求項１０】 前記指定手段は、タグで構造化された
    文書データを前記木構造データとみなし、該文書データ
    内の２つのタグの間の情報を部分木とみなして、前記検
    索対象となる可能性のある部分木内の前記パス群を指定
    することを特徴とする請求項６記載のデータ格納装置。
11. 【請求項１１】 木構造データの各階層から部分木を抽
    出する抽出手段と、 抽出された部分木の情報をまとめて格納する格納手段と
    を備えることを特徴とするデータ格納装置。
12. 【請求項１２】 コンピュータのためのプログラムを記
    録した記録媒体であって、 木構造データにおいて、検索対象となる可能性のある部
    分木の構造を指定するステップと、 前記木構造データから、指定された構造に適合する部分
    木を抽出するステップと、 抽出された部分木の情報をまとめて格納するステップと
    を含む処理を前記コンピュータに実行させるためのプロ
    グラムを記録したコンピュータ読み取り可能な記録媒
    体。
13. 【請求項１３】 コンピュータのための木構造データを
    記録した記録媒体であって、 前記木構造データにおいて、前記コンピュータが検索対
    象とする可能性のある部分木の構造が指定されたとき、
    指定された構造に適合する部分木の情報を、該コンピュ
    ータがアクセスできるようにまとめて記録したことを特
    徴とするコンピュータ読み取り可能な記録媒体。
14. 【請求項１４】 木構造データにおいて、検索対象とな
    る可能性のある部分木の構造を指定し、 前記木構造データから、指定された構造に適合する部分
    木を抽出し、 抽出された部分木の情報をまとめて格納することを特徴
    とするデータ格納方法。