(57)【特許請求の範囲】
【請求項１】
一つまたは複数の木構造データを記憶する格納装置と，データ検索式を受け取る入力装置と，データを出力する出力装置とに接続された計算機を動作させるためのデータ管理プログラムであって，
該格納装置に記憶されている木構造データ中の様々な深さの階層にある部分木の集合を取り出す検索式がパス式の形で複数個，該入力装置に与えられた際に，
与えられた該複数パス式の全てからなる集合の空でない任意の部分集合と，与えられた該複数パス式の全ての接頭辞からなる集合の任意の部分集合との，全ての組合せについて，該複数パス式のうち前者の部分集合に含まれるもの全てと，該接頭辞のうち後者の部分集合に含まれるもの全てとの積と，
該複数パス式のうち前者の部分集合に含まれないもの全てと，該接頭辞のうち後者の部分集合に含まれないもの全てとの和の，
これらの積と和の差から，
さらに，前記与えられた複数パス式の全ての和にマッチするデータの全ての子孫（自身を含まない）を取り除いた差
に相当するパス式を合成し，
これらの合成パス式の各々について，その解集合となる部分木集合を前記格納装置から取り出すことによって，
前記与えられた複数パス式のうちの一つ以上のパス式の解となる部分木のうち，該複数パス式のうちのいずれかのパス式の他の解の一部をなす部分木とならないものの全てを，それがどのパス式の解集合には含まれどのパス式の解集合には含まれないか，および，それがどのパス式のどの接頭辞にはマッチしどのパス式のどの接頭辞にはマッチしないかの，以上の二点に基づいて分類したものにあたる集合群を生成し，
これらの集合群を前記出力装置に出力するように計算機を動作させることを特徴とするデータ管理プログラム．
【請求項２】
一つまたは複数の木構造データを記憶する格納装置と，データ検索式を受け取る入力装置と，データを出力する出力装置とに接続された計算機を動作させるためのデータ管理プログラムであって，
該格納装置に記憶されている木構造データ中の様々な深さの階層にある部分木の集合を取り出す検索式がパス式の形で一つ，該入力装置に与えられた際に，
該パス式の全ての接頭辞からなる集合の全ての部分集合について，
前記与えられたパス式と，該接頭辞のうち該部分集合に含まれるもの全てとの積と，
該接頭辞のうち該部分集合に含まれないもの全てとの和の，
これらの積と和の差から，
さらに，前記与えられたパス式にマッチするデータの全ての子孫（自身を含まない）を取り除いた差
に相当するパス式を合成し，
これらの合成パス式の各々について，その解集合となる部分木集合を前記格納装置から取り出すことによって，
前記与えられたパス式の解となる部分木のうち，該パス式の他の解の一部をなす部分木とならないものの全てを，それが該パス式のどの接頭辞にはマッチし該パス式のどの接頭辞にはマッチしないかに基づいて分類したものにあたる集合群を生成し，
これらの集合群を前記出力装置に出力するように計算機を動作させることを特徴とするデータ管理プログラム．
【請求項３】
一つまたは複数の木構造データを記憶する格納装置と，データ検索式を受け取る入力装置と，データを出力する出力装置とに接続された計算機を動作させるためのデータ管理プログラムであって，
該格納装置に記憶されている木構造データ中の様々な深さの階層にある部分木の集合を取り出す検索式がパス式の形で複数個，該入力装置に与えられた際に，
該複数パス式を用いて該複数パス式の各々に対する解集合となる部分木集合を該格納装置から取り出した後に，
前記与えられた複数パス式のうちの一つ以上のパス式の解となる部分木のうち，該複数パス式のうちのいずれかのパス式の他の解の一部をなす部分木としても出現するものを取り除き，さらに，残った部分木の全てについて，それがどのパス式の解集合には含まれどのパス式の解集合には含まれないか，および，それがどのパス式のどの接頭辞にはマッチしどのパス式のどの接頭辞にはマッチしないかを調べて，以上の二点の結果に基づいて分類することによって，これらの各分類にあたる集合群を生成し，
これらの集合群を前記出力装置に出力するように計算機を動作させることを特徴とするデータ管理プログラム．
【請求項４】
一つまたは複数の木構造データを記憶する格納装置と，データ検索式を受け取る入力装置と，データを出力する出力装置とに接続された計算機を動作させるためのデータ管理プログラムであって，
該格納装置に記憶されている木構造データ中の様々な深さの階層にある部分木の集合を取り出す検索式がパス式の形で一つ，該入力装置に与えられた際に，
該パス式を用いてその解集合となる部分木集合を該格納装置から取り出した後に，
該パス式の解となる部分木のうち，該パス式の他の解の一部をなす部分木としても出現するものを取り除き，さらに，残った部分木の全てについて，それが該パス式のどの接頭辞にはマッチし該パス式のどの接頭辞にはマッチしないかを調べて，その結果に基づいて分類することによって，これらの各分類にあたる集合群を生成し，
これらの集合群を前記出力装置に出力するように計算機を動作させることを特徴とするデータ管理プログラム．
【請求項５】
データの集合を受け取る入力装置に接続された計算機を，動作させるためのデータ管理プログラムであって，
請求項１または３に記載のデータ管理プログラムによって出力された前記各分類を表す部分木集合群を該入力装置で受け取り，該データ管理プログラムに当初与えられた前記複数パス式の各々に対する解集合を，該パス式の解集合に含まれるとされていた分類の全て，および，該パス式の各接頭辞にマッチするとされていた各分類中の部分木から，該パス式中で該接頭辞と対になる接尾辞を用いて取り出した部分木の集合の，これら全ての和集合を取ることによって合成するように計算機を動作させることを特徴とするデータ管理プログラム．
【請求項６】
データの集合を受け取る入力装置に接続された計算機を，動作させるためのデータ管理プログラムであって，
請求項２または４に記載のデータ管理プログラムによって出力された前記各分類を表す部分木集合群を該入力装置で受け取り，該データ管理プログラムに当初与えられた前記パス式の解集合を，該各分類の全て，および，該パス式の各接頭辞にマッチするとされていた各分類中の部分木から，該パス式中で該接頭辞と対になる接尾辞を用いて取り出した部分木の集合の，これら全ての和集合を取ることによって合成するように計算機を動作させることを特徴とするデータ管理プログラム．
【請求項７】
複数のデータを記憶する格納装置と，データ検索式を受け取る入力装置と，データを出力する出力装置とに接続された計算機を動作させるためのデータ管理プログラムであって，該格納装置に記憶されているデータの部分集合を取り出す検索式が複数個，該入力装置に与えられた際に，
該複数検索式全てからなる集合の全ての空でない部分集合について，
該複数検索式のうち該部分集合に含まれるもの全ての積と，該複数検索式のうち該部分集合に含まれないもの全ての和の，これらの積と和の差に相当する検索式を合成し，
これらの合成検索式の各々について，その解集合となるデータ集合を前記格納装置から取り出すことによって，
前記与えられた複数検索式のうちの一つ以上の検索式の解となるデータの全てを，それがどの検索式の解集合には含まれどの検索式の解集合には含まれないかに基づいて分類したものにあたる集合群を生成し，
これらの集合群を前記出力装置に出力するように計算機を動作させることを特徴とするデータ管理プログラム．
【請求項８】
データの集合を受け取る入力装置に接続された計算機を，動作させるためのデータ管理プログラムであって，
請求項７に記載のデータ管理プログラムによって出力された前期各分類を表す集合群を該入力装置で受け取り，該データ管理プログラムに当初与えられた前記複数検索式の各々に対する解集合を，該検索式の解集合に含まれるとされていた分類全ての和集合を取ることで合成するように計算機を動作させることを特徴とするデータ管理プログラム．
【請求項９】
一つまたは複数の木構造データを記憶する格納装置と，データ検索式を受け取る入力装置と，データを出力する出力装置とに接続された計算機を動作させるためのデータ管理プログラムであって，
該格納装置に記憶されている木構造データ中の様々な深さの階層にある部分木の集合を取り出す検索式が複数個，該入力装置に与えられた際に，
該複数検索式を用いて該複数検索式の各々に対する解集合となる部分木集合を該格納装置から取り出した後に，
該複数検索式のうちのある検索式の解となる部分木の一つが，該複数検索式のうちのいずれかの検索式の他の解の一部をなす部分木としても出現する場合には，他の解の一部としても出現する該部分木を解集合から取り除いた上で，各解集合を前記出力装置に出力するように計算機を動作させることを特徴とするデータ管理プログラム．
【請求項１０】
一つまたは複数の木構造データを記憶する格納装置と，データ検索式を受け取る入力装置と，データを出力する出力装置とに接続された計算機を動作させるためのデータ管理プログラムであって，
該格納装置に記憶されている木構造データ中の様々な深さの階層にある部分木の集合を取り出す検索式が複数個，該入力装置に与えられた際に，
与えられた該複数検索式の全てに適当な全順序を定め，
該複数検索式の各々について，
該検索式から，該検索式より該全順序で若い順番を持つ全ての検索式にマッチするデータを取り除いた差から，
さらに，前記与えられた複数検索式のいずれかにマッチするデータの全ての子孫（自身を含まない）を取り除いた差
に相当する検索式を合成し，
これらの合成検索式の各々について，その解集合となる部分木集合を前記格納装置から取り出すことによって，
前記与えられた複数検索式のうちの一つ以上の検索式の解となる部分木のうち，該複数検索式のうちのいずれかの検索式の他の解の一部をなす部分木とならないものの全てを，重複なく取り出し，これらを前記出力装置に出力するように計算機を動作させることを特徴とするデータ管理プログラム．
【請求項１１】
一つまたは複数の木構造データを記憶する格納装置と，データ検索式を受け取る入力装置と，データを出力する出力装置と，これらに接続された計算機とからなるデータ管理システムであって，
該格納装置に記憶されている木構造データ中の様々な深さの階層にある部分木の集合を取り出す検索式がパス式の形で複数個，該入力装置に与えられた際に，
与えられた該複数パス式の全てからなる集合の空でない任意の部分集合と，与えられた該複数パス式の全ての接頭辞からなる集合の任意の部分集合との，全ての組合せについて，該複数パス式のうち前者の部分集合に含まれるもの全てと，該接頭辞のうち後者の部分集合に含まれるもの全てとの積と，
該複数パス式のうち前者の部分集合に含まれないもの全てと，該接頭辞のうち後者の部分集合に含まれないもの全てとの和の，
これらの積と和の差から，
さらに，前記与えられた複数パス式の全ての和にマッチするデータの全ての子孫（自身を含まない）を取り除いた差
に相当するパス式を合成し，
これらの合成パス式の各々について，その解集合となる部分木集合を前記格納装置から取り出すことによって，
前記与えられた複数パス式のうちの一つ以上のパス式の解となる部分木のうち，該複数パス式のうちのいずれかのパス式の他の解の一部をなす部分木とならないものの全てを，それがどのパス式の解集合には含まれどのパス式の解集合には含まれないか，および，それがどのパス式のどの接頭辞にはマッチしどのパス式のどの接頭辞にはマッチしないかの，以上の二点に基づいて分類したものにあたる集合群を生成し，
これらの集合群を前記出力装置に出力するように計算機が動作することを特徴とするデータ管理システム．
【請求項１２】
一つまたは複数の木構造データを記憶する格納装置と，データ検索式を受け取る入力装置と，データを出力する出力装置と，これらに接続された計算機とからなるデータ管理システムであって，
該格納装置に記憶されている木構造データ中の様々な深さの階層にある部分木の集合を取り出す検索式がパス式の形で一つ，該入力装置に与えられた際に，
該パス式の全ての接頭辞からなる集合の全ての部分集合について，
前記与えられたパス式と，該接頭辞のうち該部分集合に含まれるもの全てとの積と，
該接頭辞のうち該部分集合に含まれないもの全てとの和の，
これらの積と和の差から，
さらに，前記与えられたパス式にマッチするデータの全ての子孫（自身を含まない）を取り除いた差
に相当するパス式を合成し，
これらの合成パス式の各々について，その解集合となる部分木集合を前記格納装置から取り出すことによって，
前記与えられたパス式の解となる部分木のうち，該パス式の他の解の一部をなす部分木とならないものの全てを，それが該パス式のどの接頭辞にはマッチし該パス式のどの接頭辞にはマッチしないかに基づいて分類したものにあたる集合群を生成し，
これらの集合群を前記出力装置に出力するように計算機が動作することを特徴とするデータ管理システム．
【請求項１３】
一つまたは複数の木構造データを記憶する格納装置と，データ検索式を受け取る入力装置と，データを出力する出力装置と，これらに接続された計算機とからなるデータ管理システムであって，
該格納装置に記憶されている木構造データ中の様々な深さの階層にある部分木の集合を取り出す検索式がパス式の形で複数個，該入力装置に与えられた際に，
該複数パス式を用いて該複数パス式の各々に対する解集合となる部分木集合を該格納装置から取り出した後に，
前記与えられた複数パス式のうちの一つ以上のパス式の解となる部分木のうち，該複数パス式のうちのいずれかのパス式の他の解の一部をなす部分木としても出現するものを取り除き，さらに，残った部分木の全てについて，それがどのパス式の解集合には含まれどのパス式の解集合には含まれないか，および，それがどのパス式のどの接頭辞にはマッチしどのパス式のどの接頭辞にはマッチしないかを調べて，以上の二点の結果に基づいて分類することによって，これらの各分類にあたる集合群を生成し，
これらの集合群を前記出力装置に出力するように計算機が動作することを特徴とするデータ管理システム．
【請求項１４】
一つまたは複数の木構造データを記憶する格納装置と，データ検索式を受け取る入力装置と，データを出力する出力装置と，これらに接続された計算機とからなるデータ管理システムであって，
該格納装置に記憶されている木構造データ中の様々な深さの階層にある部分木の集合を取り出す検索式がパス式の形で一つ，該入力装置に与えられた際に，
該パス式を用いてその解集合となる部分木集合を該格納装置から取り出した後に，
該パス式の解となる部分木のうち，該パス式の他の解の一部をなす部分木としても出現するものを取り除き，さらに，残った部分木の全てについて，それが該パス式のどの接頭辞にはマッチし該パス式のどの接頭辞にはマッチしないかを調べて，その結果に基づいて分類することによって，これらの各分類にあたる集合群を生成し，
これらの集合群を前記出力装置に出力するように計算機が動作することを特徴とするデータ管理システム．
【請求項１５】
データの集合を受け取る入力装置と，これに接続された計算機とからなるデータ管理システムであって，
請求項１１または１３に記載のデータ管理システムによって出力された前記各分類を表す部分木集合群を該入力装置で受け取り，該データ管理システムに当初与えられた前記複数パス式の各々に対する解集合を，該パス式の解集合に含まれるとされていた分類の全て，および，該パス式の各接頭辞にマッチするとされていた各分類中の部分木から，該パス式中で該接頭辞と対になる接尾辞を用いて取り出した部分木の集合の，これら全ての和集合を取ることによって合成するように計算機が動作することを特徴とするデータ管理システム．
【請求項１６】
データの集合を受け取る入力装置と，これに接続された計算機とからなるデータ管理システムであって，
請求項１２または１４に記載のデータ管理システムによって出力された前記各分類を表す部分木集合群を該入力装置で受け取り，該データ管理システムに当初与えられた前記パス式の解集合を，該各分類の全て，および，該パス式の各接頭辞にマッチするとされていた各分類中の部分木から，該パス式中で該接頭辞と対になる接尾辞を用いて取り出した部分木の集合の，これら全ての和集合を取ることによって合成するように計算機が動作することを特徴とするデータ管理システム．
【請求項１７】
複数のデータを記憶する格納装置と，データ検索式を受け取る入力装置と，データを出力する出力装置と，これらに接続された計算機とからなるデータ管理システムであって，
該格納装置に記憶されているデータの部分集合を取り出す検索式が複数個，該入力装置に与えられた際に，
該複数検索式全てからなる集合の全ての空でない部分集合について，
該複数検索式のうち該部分集合に含まれるもの全ての積と，該複数検索式のうち該部分集合に含まれないもの全ての和の，これらの積と和の差に相当する検索式を合成し，
これらの合成検索式の各々について，その解集合となるデータ集合を前記格納装置から取り出すことによって，
前記与えられた複数検索式のうちの一つ以上の検索式の解となるデータの全てを，それがどの検索式の解集合には含まれどの検索式の解集合には含まれないかに基づいて分類したものにあたる集合群を生成し，
これらの集合群を前記出力装置に出力するように計算機が動作することを特徴とするデータ管理システム．
【請求項１８】
データの集合を受け取る入力装置と，これに接続された計算機とからなるデータ管理システムであって，
請求項１７に記載のデータ管理システムによって出力された前期各分類を表す集合群を該入力装置で受け取り，該データ管理システムに当初与えられた前記複数検索式の各々に対する解集合を，該検索式の解集合に含まれるとされていた分類全ての和集合を取ることで合成するように計算機が動作することを特徴とするデータ管理システム．
【請求項１９】
一つまたは複数の木構造データを記憶する格納装置と，データ検索式を受け取る入力装置と，データを出力する出力装置と，これらに接続された計算機とからなるデータ管理システムであって，
該格納装置に記憶されている木構造データ中の様々な深さの階層にある部分木の集合を取り出す検索式が複数個，該入力装置に与えられた際に，
該複数検索式を用いて該複数検索式の各々に対する解集合となる部分木集合を該格納装置から取り出した後に，
該複数検索式のうちのある検索式の解となる部分木の一つが，該複数検索式のうちのいずれかの検索式の他の解の一部をなす部分木としても出現する場合には，他の解の一部としても出現する該部分木を解集合から取り除いた上で，各解集合を前記出力装置に出力するように計算機が動作することを特徴とするデータ管理システム．
【請求項２０】
一つまたは複数の木構造データを記憶する格納装置と，データ検索式を受け取る入力装置と，データを出力する出力装置と，これらに接続された計算機とからなるデータ管理システムであって，
該格納装置に記憶されている木構造データ中の様々な深さの階層にある部分木の集合を取り出す検索式が複数個，該入力装置に与えられた際に，
与えられた該複数検索式の全てに適当な全順序を定め，
該複数検索式の各々について，
該検索式から，該検索式より該全順序で若い順番を持つ全ての検索式にマッチするデータを取り除いた差から，
さらに，前記与えられた複数検索式のいずれかにマッチするデータの全ての子孫（自身を含まない）を取り除いた差
に相当する検索式を合成し，
これらの合成検索式の各々について，その解集合となる部分木集合を前記格納装置から取り出すことによって，
前記与えられた複数検索式のうちの一つ以上の検索式の解となる部分木のうち，該複数検索式のうちのいずれかの検索式の他の解の一部をなす部分木とならないものの全てを，重複なく取り出し，これらを前記出力装置に出力するように計算機が動作することを特徴とするデータ管理システム．
【発明の詳細な説明】
【技術分野】
【０００１】本発明は，計算機に格納されているデータの一部をユーザからの要求に応じて取り出し，あるいはさらに，取り出したデータのネットワーク等を介しての送信や，ユーザ等への呈示や，記憶媒体等への保存等を行うシステムにおいて，データ中の冗長性を除去した状態で，取出し，送信，呈示，保存等を行うことによって，取出し処理，送信処理，保存領域等のコストの軽減ならびに，ユーザの閲覧利便性の向上を実現するためのプログラムおよびシステムに関する．
【背景技術】
【０００２】ユーザからのデータの取出し要求に応じて，管理しているデータの中から，その取出し要求への解となるデータの集合，すなわち解集合を取り出すデータ管理システムで，解集合中の重複を取り除くことを考慮するシステムに関しては，以下の四つの分類軸が考えられる．【０００３】（１）同一のデータが複数回，解として出現するような重複のみを考慮するか，あるいは対象データが木構造として表現できるような入れ子構造を持つ場合には，ある解が別の解の部分木として出現するような重複も考量するか．【０００４】（２）取り出したデータを調べて重複を発見し取り除くか，あるいは，与えられたデータ取出し要求を解析し，重複を含まない形でデータを取り出すようにこれらの取出し要求を変形したものを合成し，これらを用いてデータを取り出すことで，重複を取り除くか．【０００５】（３）一つのデータ取出し要求に対する解集合内の重複のみを考慮するか，あるいは，複数のデータ取出し要求を同時に受け取った場合は，これらのうちの異なる要求に対する解の間での重複についても考慮するか．【０００６】（４）重複を取り除いた状態のデータから，必要に応じて，当初の要求通りの，重複を含む解集合を合成する機能を有するかどうか．【０００７】これら四つの分類軸の組合わせから１６通りの場合が考えられる．それらのうち，分類軸の（１）に関して，同一のデータが複数回，解となるような重複のみを考慮するものに分類される８通りのうちのいくつかについては，先行技術が存在する．【０００８】まず，取り出したデータを調べて重複を発見する手法で，一つの取出し要求のみを考慮するシステムについては，下記特許文献１や下記特許文献２において，ユーザからの検索要求に応じて，検索結果を呈示するシステムで，検索結果の呈示前にその内容を調べ，同じデータが複数回含まれる場合には，このうちの一つを残して削除するシステムが開示されている．同様に，取り出したデータを調べて重複を発見する手法で，複数の問い合わせを考慮する点についても，下記特許文献１において言及されている．
【特許文献１】特開平０７−２９５９９４
【特許文献２】特開平１０−１４３５２３
【０００９】また，データ取出し要求を変形して重複を取り除く手法で，一つの要求のみを考慮する技術の例としては，関係データベースに対して「従業員の中で６０歳以上の者の社員番号の集合と，従業員の中で勤続年数が４０年以上の者の社員番号の集合の集合和を取り出せ」という要求を表すＳＱＬ検索式：
（ｓｅｌｅｃｔ  社員番号  ｆｒｏｍ  従業員  ｗｈｅｒｅ  年齢＞＝６０）
ｕｎｉｏｎ
（ｓｅｌｅｃｔ  社員番号  ｆｒｏｍ  従業員  ｗｈｅｒｅ  勤続年数＞＝４０）
が与えられた時，これを「従業員の中で年齢が６０歳以上か、もしくは，勤続年数が４０年以上の者の社員番号の集合を取り出せ」という要求を表すＳＱＬ検索式：
ｓｅｌｅｃｔ  社員番号  ｆｒｏｍ  従業員
ｗｈｅｒｅ  年齢＞＝６０ｏｒ  勤続年数＞＝４０
へと変形することで，同じ従業員の取出し処理を二回行う可能性を排除するといった手法が広く知られている．【００１０】また，データ取出し要求を変形して重複を取り除く手法で，複数の要求を考慮する技術の例としては，ｒｅｍｉｎｄｅｒ  ｑｕｅｒｙと呼ばれる手法が下記非特許文献１に開示されている．これは，以前に「年齢が６０歳以上の従業員の社員番号の集合を取り出せ」という要求があった場合，この要求内容とそれに対する結果のデータを保存しておき，その後に「年齢が５０歳以上の従業員の社員番号の集合を取り出せ」という要求があった場合には，これを，以前の要求の解集合との差分のみを取り出す「年齢が５０歳以上かつ６０歳未満の従業員の社員番号の集合を取り出せ」という要求に変形してデータを取り出し，その結果と，保存しておいた６０以上の従業員の社員番号の集合との集合和を取って，年齢が５０歳以上の従業員の社員番号の集合を生成する手法である．これにより，以前に取り出したことがある，６０以上の従業員の情報を繰り返し取り出す処理を排除することができる．この例からわかるように，ｒｅｍｉｎｄｅｒ  ｑｕｅｒｙは（４）の分類軸で述べた，冗長性を取り除いて取り出したデータから，当初の要求通りの解となるデータを合成する機能についても，これを有していることがわかる．
【非特許文献１】Ｓ．Ｄａｒ他著  ”Ｓｅｍａｎｔｉｃ  Ｄａｔａ  Ｃａｃｈｉｎｇ  ａｎｄ  Ｒｅｐｌａｃｅｍｅｎｔ”Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｖｅｒｙ  Ｌａｒｇｅ  Ｄａｔａｂａｓｅｓ（ＶＬＤＢ）予稿集，頁３３０−３４１，１９９６
【００１１】同様に，木構造を持つデータであるＸＭＬデータの管理においても，ｒｅｍｉｎｄｅｒ  ｑｕｅｒｙの手法を用いる研究が下記非特許文献２で示されている．しかし，非特許文献２で示されている手法では，扱うデータは木構造データであっても，過去の要求の解集合中のある要素が新しい要求の解ともなる場合のみを考慮していて，新しい要求のある解が過去の要求のある解の部分木になっているような場合については考慮しておらず，分類軸の（１）に関しては，通常のｒｅｍｉｎｄｅｒ  ｑｕｅｒｙの手法と同様に分類される．
【非特許文献２】Ｌ．Ｃｈｅｎ，Ｅ．Ａ．Ｒｕｎｄｅｎｓｔｅｉｎｅｒ著  ”ＡＣＥ−ＸＱ：Ａ  ＣａｃｈＥ−ａｗａｒｅ  ＸＱｕｅｒｙ  ａｎｓｗｅｒｉｎｇｓｙｓｔｅｍ”  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ  ｔｈｅ  Ｗｅｂ  ａｎｄ  Ｄａｔａｂａｓｅｓ（ＷｅｂＤＢ）予稿集，頁３１−３６，２００２
【００１２】また，木構造データが別の木構造データの部分木として出現する場合の冗長性とは異なるが，ある要求に対する解集合中の異なる要素の間で，その値の一部分のみが共通である場合に，その部分の冗長性を取り除くための手法が下記特許文献３に開示されている．
【特許文献３】特開平０７−１２１５７１
この手法では，取り出したデータが例えば
佐藤，総務部
田中，総務部
竹田，人事部
石井，人事部
のような表形式のデータであった場合，これを「同じ値」を表わす符合「〃」を用いて
佐藤，総務部
田中，  〃
竹田，人事部
石井，  〃
のような表現へと変形することで，冗長性を取り除く．
【発明の開示】
【発明が解決しようとする課題】
【００１３】しかしながら，上で分類軸（１）として挙げた点に関して，木構造として表現できるデータを管理する際に生じる，ある解が別の解の一部をなす部分木としても出現するような種類の重複についても考慮するような技術については，これまでに開示されていない．そのため，このような形での重複を含むデータを，取出し，送信，呈示，保存等を行うことによって，不必要に処理コストや必要記憶容量を増大させたり，ユーザの閲覧利便性を低下させるという問題がある．【００１４】また，同一のデータが解として複数回出現するような重複のみを考えた場合に関しても，前述のｒｅｍｉｎｄｅｒ  ｑｕｅｒｙの手法では，重複を取り除いた状態でデータを取り出してから，本来の解集合を合成するということが，常に可能とは限らない．例えば，以前に「４０歳以上６０歳未満の従業員の社員番号の集合を取り出せ」という要求があり，その結果を保存してある時に，新たな要求として「３０歳以上５０歳未満の従業員の社員番号の集合を取り出せ」という要求が与えられたとする．この場合，４０歳以上５０歳未満の従業員の社員番号については，全て保存しているデータの中に既に含まれており，これを再度取り出すのは冗長である．しかし，保存している４０歳以上６０歳未満の従業員の「社員番号」のデータを見ただけでは，どの社員番号が５０歳未満の社員の番号であるのか判定不可能であり，そのため，再び「３０歳以上５０歳未満の従業員の社員番号の集合を取り出せ」という要求でデータを取り出すしか方法がない．【００１５】これは，ｒｅｍｉｎｄｅｒ  ｑｕｅｒｙの手法が通常想定しているような，最初に「４０歳以上６０歳未満」という条件の要求が与えられた時点では，その後に「３０歳以上５０歳未満」という条件の要求が与えられることは予測不可能である状況では避けられない問題であるが，これら「４０歳以上６０歳未満」という条件の要求と「３０歳以上５０歳未満」という条件の要求の二つが同時に与えられるような場合には，これらの要求を「３０歳以上４０歳未満」と「４０歳以上５０歳未満」と「５０歳以上６０歳未満」の三つの要求に分割して実行すれば，重複を取り除いた形でデータを取得し，その後にこれらのデータを使って，当初の要求である「４０歳以上６０歳未満」の社員番号の集合と「３０歳以上５０歳未満」の社員番号の集合を生成することは容易である．よって，この例のように複数の取出し要求が「同時に」与えられる場合は，単純にｒｅｍｉｎｄｅｒ  ｑｕｅｒｙの手法を適用するのでは，重複するデータの取出しを行わずに，かつ後から当初の解集合を合成する方法が存在するにも関わらず，不必要に重複するデータの取出しを行って処理コストを増大させてしまう場合があるという問題がある．【００１６】本発明の目的は，以上のような問題点に鑑み，一つまたは複数のデータ取出し要求が同時に与えられた場合にはいかなる場合においても，かつ，ある解が木構造データを持つ他の解の一部をなす部分木として出現するような種類の重複まで含めて，重複を取り除き，かつ，この重複を取り除いたデータから，必要に応じて当初の取出し要求の解集合を合成する機能を持つデータ管理プログラムおよびシステムを提供することによって，データの取出し，送信の処理コストの低減や，データの保存の記憶容量の節減，データをユーザへ呈示する際の閲覧利便性の向上を達成することにある．
【課題を解決するための手段】
【００１７】本発明のデータ管理プログラムおよびシステムは，データの取出し要求の集合が与えられた際には，いずれかの取出し要求の解となるデータ全てを，それがどの取出し要求に対する解集合には含まれどの取出し要求に対する解集合には含まれないかに基づいて分類したものを生成する．これにより，同じデータが複数の取出し要求の解集合に重複して現れるという冗長性を除去することができると同時に，後述のように，これらの分類から当初の取出し要求の解集合を合成することができる．【００１８】本発明のデータ管理プログラムおよびシステムは，上記分類を，与えられた取出し要求を用いて各解集合を取り出した後に生成するか，または，与えられた取出し要求をもとに合成した取出し要求を用いて，直接，各分類を取り出す．後者の場合においては，各分類の取り出しを，その分類を解集合に含むとされる取出し要求の全ての積と，その分類を解集合に含まないとされる取出し要求の全ての和の，これら二つの差に相当する取出し要求を用いて行う．【００１９】そして，前述のように，本発明のデータ管理プログラムおよびシステムは，上述の各分類から，必要に応じて，当初の取出し要求の解集合を合成することができる．この合成は，該取出し要求の解集合に含まれるとされていた分類全ての和集合を取ることで行う．【００２０】また，本発明のデータ管理プログラムおよびシステムは，木構造データ中の様々な深さの階層にある部分木の集合の取出し要求が与えられて，該要求が取り出す部分木の一つが，該要求が取り出す別の部分木の中にその一部をなす部分木としても重複して出現する場合には，この前者の部分木を該要求に対する解集合から取り除く．ここで，ある要素がある要素の部分木であるとは，二つの要素が全く同じ木である場合も含む物とする．これにより，該取出し要求の解集合の中に存在する，木構造データ特有の部分木としての重複による冗長性を除去することができる．【００２１】同様に，本発明のデータ管理プログラムおよびシステムは，木構造データ中の様々な深さの階層にある部分木の集合の取出し要求が，複数個与えられて，該複数要求中のある要求が取り出す部分木の一つが，該複数要求中の別の要求が取り出すある部分木の中にその一部をなす部分木としても重複して出現する場合には，この前者の部分木を対応する要求に対する解集合から取り除く．ここでも，ある要素がある要素の部分木であるとは，二つの要素が全く同じ木である場合も含む物とする．これにより，該複数取出し要求の解集合の間に存在する，木構造データ特有の部分木としての重複による冗長性を除去することができる．【００２２】本発明のデータ管理プログラムおよびシステムは，上述の重複する部分木の除去を，与えられた取出し要求を用いて部分木集合を取り出した後に行うか，あるいは，与えられた取出し要求をもとに合成した取出し要求を用いて，重複が取り除かれた部分木集合を直接取り出すことで行う．【００２３】そして，本発明のデータ管理プログラムおよびシステムは，上述のようにして，重複を取り除かれた部分木集合から，当初の取出し要求の解となる部分木集合を合成する機能を有する．【００２４】また，本発明のデータ管理プログラムおよびシステムは，木構造データ中の様々な深さの階層にある部分木の集合の取出し要求がパス式の形で一つ与えられた際には，該パス式の解となる部分木のうち，該パス式の他の解の一部をなす部分木とならない物の全てを，それが該パス式のどの接頭辞にはマッチし該パス式のどの接頭辞にはマッチしないかに基づいて分類したものを生成する．これにより，該取出し要求の解集合中に存在する，木構造データ特有の部分木としての重複による冗長性を除去することができると同時に，後述のように，これらの分類から当初の取出し要求の解集合を合成することができる．ここで，パス式とは，木構造データから取り出したいノードの指定を，木構造データの根ノードを始点，取り出したいノードを終点とするパス上の各ノードが満たすべき条件を記述することで行うもので，通常，各ノードに関する条件を根ノードに近い側のノードの条件から順に並べた形で記述される．【００２５】同様に，本発明のデータ管理プログラムおよびシステムは，木構造データ中の様々な深さの階層にある部分木の集合の取出し要求がパス式の形で複数個与えられた際には，いずれかのパス式の解となる部分木のうち，いずれかのパス式の他の解の一部をなす部分木とならない物の全てを，それがどのパス式の解集合には含まれどのパス式の解集合には含まれないか，および，それがどのパス式のどの接頭辞にはマッチしどのパス式のどの接頭辞にはマッチしないかの，以上の二点に基づいて分類したものを生成する．これにより，該複数取出し要求の解集合の間に存在する，木構造データ特有の部分木としての重複による冗長性を除去することができると同時に，後述のように，これらの分類から当初の取出し要求の解集合を合成することができる．【００２６】本発明のデータ管理プログラムおよびシステムは，上記の分類を，与えられたパス式を用いて全データを取り出した後に生成するか，または，与えられたパス式をもとに合成したパス式を用いて，各分類を取り出す．後者の場合においては，パス式が一つ与えられた場合には，各分類を取り出すパス式の合成を，与えられたパス式およびその分類とマッチするとされていた接頭辞の全ての積と，その分類とマッチしないとされていた接頭辞の全ての和の，これら二つの差に相当するパス式を用いて行う．また，後者の場合において，パス式が複数個与えられた場合には，各分類を取り出すパス式の合成を，その分類を解集合に含むとされていた取出し要求およびその分類とマッチするとされていた接頭辞の全ての積と，その分類を解集合に含まないとされていた取出し要求およびその分類とマッチしないとされていた接頭辞の全ての和の，これら二つの差に相当するパス式を用いて行う．【００２７】また，前述のように，本発明のデータ管理方法およびシステムは，上述の各分類から，必要に応じて当初のパス式の解集合を合成することができる．この合成は，該パス式の解集合に含まれるとされていた分類の全てと，および，該パス式の各接頭辞にマッチするとされていた各分類中の部分木から，該パス式中で該接頭辞と対になる接尾辞を用いて取り出した部分木の集合との，これら全ての和集合を取ることによって行う．
【発明の効果】
【００２８】解の一部が重複する複数の検索式が同時に与えられた場合には，上述のような方法でデータを取り出すことによって，従来のｒｅｍｉｎｄｅｒ  ｑｕｅｒｙの手法では対応できないような場合においても，重複を含まない形でデータを取り出すことが可能となり，従来の方法やシステムに比べて，データの取出しや送信の処理コストの軽減，データの保存のための記憶容量の節減，データを呈示されたユーザの閲覧利便性向上を実現することができる．【００２９】また，木構造データを管理する場合に生じる，ある解が，他の解の一部をなす部分木としても出現するという種類の重複についても，これを取り除いた状態でデータの取出し，送信，呈示，保存を行うことができ，従来の方法やシステムに比べて，木構造データを扱う場合の，データの取出しや送信の処理コストの軽減，データの保存のための記憶容量の節減，データを呈示されたユーザの閲覧利便性向上を実現することができる．【００３０】また，本発明のデータ管理方法またはシステムは，重複を取り除いた状態のデータから，当初の要求通りのデータを合成する機能を有するため，例えば，重複を取り除いた状態でネットワーク等を介してデータを送信し，これを受信した側で，当初の取出し要求で要求されていたデータを合成することによって，ユーザに呈示する内容を当初の要求通りの物に維持しつつ，ネットワークの送信コストを節減することができる．同様に，重複を取り除いた状態でデータを保存し，後に必要になった時点で，当初の取出し要求で要求されていたデータを合成することによって，ユーザに呈示する内容を当初の要求通りの物に維持しつつ，データの保存のための記憶容量を節減することができる．
【発明を実施するための最良の形態】
【００３１】（第一の実施の形態）
次に，本発明の第一の実施の形態の詳細について，詳しく説明する．本説明においては，本発明を，ＪＩＳ規格であるＳＱＬ検索式によってデータの取出し要求を行う関係データベースに適用する場合の一実施形態について説明する．本実施形態においては，与えられた複数検索式の解集合が互いに重複する要素を含みうる．よって，システムは，与えられた複数検索式のうちのいずれかの検索式の解集合に含まれるような全データを，そのデータがどの検索式の解には含まれどの検索式の解には含まれないかに基づいて分類したものを作成する．これにより，同じデータが複数の取出し要求の解集合に重複して現れるという冗長性を除去することができ，さらに，後述のように，これらの分類から，必要に応じて，当初の検索式の解を合成することができる．一方，扱うデータは木構造データではないので，解集合中のある要素が，同じまたは別の解集合中の別の要素の部分木として重複して出現するような種類の重複は，当実施形態においては考慮する必要はない．【００３２】図２に，本実施形態におけるシステムの全体構成図を示す．本実施形態におけるシステムは，関係データを格納する格納装置４と，ユーザからＳＱＬで記述された検索式を受け取る入力装置１と，入力装置１が受け取った一つまたは複数の検索式を受け取り，各検索式について，格納装置４中の関係データから，その検索式の解となるデータの集合を取り出す検索装置３と，検索装置３が取り出したデータを受け取って，これらのデータから，上述の各分類を生成する重複除去装置１０と，重複除去装置が生成したデータを受け取って出力する出力装置６からなる．【００３３】以下，本実施形態において，入力装置が検索式の集合を受け取った際の処理手順について説明する．例として，入力装置に三つの検索式が与えられた場合を考える．この場合，これらの検索式の解集合は互いに重複する要素を含みうる．一般には，三つの検索式が与えられた場合，それらの解集合をＡ１，Ａ２，Ａ３とすると，それら三つの集合の関係は，図３に示すベン図のようになる．そこて，本システムでは，重複除去装置はＡ１，Ａ２，Ａ３を受け取ると，これらに含まれるデータを，図３に示すベン図中の７つの領域に対応する７つのグループに分類したもの，すなわち，以下の式で定義される７つの集合を生成する．
Ａ１∩Ａ２∩Ａ３
（Ａ１∩Ａ２）  −  Ａ３
（Ａ１∩Ａ３）  −  Ａ２
（Ａ２∩Ａ３）  −  Ａ１
Ａ１  −  （Ａ２∪Ａ３）
Ａ２  −  （Ａ１∪Ａ３）
Ａ３  −  （Ａ１∪Ａ２）
ただし，ここで，∩は集合の積演算，∪は集合の和演算，−は集合の差演算を表わすものとする．これら７つのグループが互いに重複する要素を含まないことは，図３に示すベン図より明らかである．【００３４】より一般には，ｎ個の検索式を受け取った場合，それらの解集合をＡ１，…，Ａｎとすると，Ｓ＝｛Ａ１，…，Ａｎ｝の空でない任意の部分集合Ｔに対して，
【数１】
0004623446.tif 000002
で定義される集合を求めていけばよい．これは，別の言い方で言えば，Ａ１，…，Ａｎのいずれかに含まれる全データを，それがＡ１，…，Ａｎのうちのどれには含まれ，どれには含まれないかに基づいて分類していることに相当する．【００３５】ユーザが，当初の検索式のいずれかの解集合中に含まれる全データを閲覧することさえできれば良い場合は，このようにして重複を除去した分類を出力することによって，ユーザは当初の三つの検索式の解そのものを閲覧する場合に比べて，同一のデータを複数回見ないですむことになり，閲覧の利便性が向上する．【００３６】また，このようにして生成された分類から，あとで必要に応じて，当初の検索式の解集合を合成することも可能である．例えば，前述の三つの検索式の解集合Ａ１，Ａ２，Ａ３の例では，一つ目の検索式の解集合Ａ１は，以下の四つの解集合
Ａ１∩Ａ２∩Ａ３
（Ａ１∩Ａ２）−Ａ３
（Ａ１∩Ａ３）−Ａ２
Ａ１−（Ａ２ＵＡ３）
の集合和を求めればよい．Ａ２，Ａ３についても同様である．この点も，図３から容易に確認できる．【００３７】より一般には，ある解集合Ａｉを合成するには，以下の式を用いればよい．
【数２】
0004623446.tif 000003
これは別の言い方で言えば，Ａｉに含まれるとされていた分類の全ての和集合を取ることに相当する．上式が成り立つことについては，複数の集合をベン図で表わした際の，ベン図中の各領域と各集合の間の関係に関する一般的に知られている数学的性質より明らかである．【００３８】よって，上述の方法で生成した重複を含まない各分類を，ディスクに保存したり，ネットワーク等を介して他の計算機へ送信したりし，その後に，当初の検索式の解集合を合成してユーザに呈示することによって，ユーザに呈示される内容を当初の検索式の解集合から変えることなく，データの保存のための記憶領域やデータの送信のための通信コストを低減することができる．【００３９】（第二の実施の形態）
次に，本発明の第二の実施の形態の詳細について，詳しく説明する．本実施形態では，第一の実施の形態同様，取出し要求をＳＱＬによって行う関係データベースに本発明を適用する場合の一実施形態について説明する．第一の実施形態との違いは，データを取り出した後に上述のような分類を生成するのではなく，与えられた検索式をもとに合成した検索式を用いることで，直接，上述の分類に当たるデータを取り出す点である．【００４０】図４に，本実施形態におけるシステムの全体構成図を示す．本実施形態におけるシステムは，関係データを格納する格納装置４と，ユーザからＳＱＬで記述された検索式の入力を受け取る入力装置１と，入力装置１が受け取った一つまたは複数の検索式をもとに新たな検索式を合成する検索式合成装置２と，検索式合成装置２が生成した一つまたは複数の検索式を受け取って，各検索式について，格納装置４中の関係データから，その検索式の解となるデータの集合を取り出す検索装置３と，検索装置３が取り出したデータを受け取って，当初の検索式の解を合成する検索解合成装置５と，検索解合成装置５が生成したデータを受け取って出力する出力装置６からなる．【００４１】これらの構成要素は全て同じ計算機上にあってもよいし，あるいは，図４に示すように，格納装置４と検索装置３のみが，サーバとなる計算機７の上にあって，入力装置１，検索式合成装置２，検索解合成装置５，出力装置６は，サーバ７とネットワーク８を介して接続されたクライアント計算機９の上にあるという配置でもよい．【００４２】以下，本実施形態において，入力装置が検索式の集合を受け取った際の処理手順について説明する．例として，以下の三つの検索式が与えられた場合を考える．
ＳＥＬＥＣＴ  氏名  ＦＲＯＭ  社員  ＷＨＥＲＥ  年齢＞５０
ＳＥＬＥＣＴ  氏名  ＦＲＯＭ  社員  ＷＨＥＲＥ  年齢＞４０  ＡＮＤ  所属＝経理
ＳＥＬＥＣＴ  氏名  ＦＲＯＭ  社員  ＷＨＥＲＥ  年齢＞３０  ＡＮＤ  所属＝営業
一つ目の検索式は，社員データの一覧から，年齢が５０を超える全社員の氏名を取り出す要求を表わしている．また，二つ目の検索式は，社員データの一覧から，年齢が４０を超え，かつ所属が経理であるような全社員の氏名を取り出す要求を表わしている．同様に，三つ目の検索式は，社員データの一覧から，年齢が３０を超え，かつ所属が営業であるような全社員の氏名を取り出す要求を表わしている．【００４３】この場合，これらの検索式の解集合は，互いに重複する要素を含みうる．例えば，年齢が５０を超える経理所属の社員の氏名は，一つ目の検索式の解集合と二つ目の検索式の解集合の双方に，要素として現れる．同様に，年齢が５０を超える営業所属の社員の氏名は，一つ目の検索式の解集合と三つ目の検索式の解集合の双方に，要素として現れる．【００４４】よって，本システムでは，検索式合成装置がこれらの検索式から，以下の式で表現されるような解集合を取り出す検索式を合成して格納装置へと送り，これらを用いて重複を取り除いた形でデータの取り出しを行う．
Ａ１∩Ａ２∩Ａ３
（Ａ１∩Ａ２）  −  Ａ３
（Ａ１∩Ａ３）  −  Ａ２
（Ａ２∩Ａ３）  −  Ａ１
Ａ１  −  （Ａ２∪Ａ３）
Ａ２  −  （Ａ１∪Ａ３）
Ａ３  −  （Ａ１∪Ａ２）
ただし，ここで，Ａ１，Ａ２，Ａ３は，それぞれ上の三つの検索式の解集合を表わし，∩は集合の積演算，∪は集合の和演算，−は集合の差演算を表わすものとする．このような解集合を取り出すＳＱＬ検索式は，ＳＱＬのＩＮＴＥＲＳＥＣＴ構文とＵＮＩＯＮ構文とＤＩＦＦＥＲＥＮＣＥ構文を用いて作成可能で，例えば，集合（Ａ１∩Ａ２）−Ａ３を取り出す検索式は，以下のようになる．
（ＳＥＬＥＣＴ  氏名  ＦＲＯＭ  社員  ＷＨＥＲＥ  年齢＞５０
ＩＮＴＥＲＳＥＣＴ
ＳＥＬＥＣＴ  氏名  ＦＲＯＭ  社員  ＷＨＥＲＥ  年齢＞４０  ＡＮＤ  所属＝経理）ＤＩＦＦＥＲＥＮＣＥ
ＳＥＬＥＣＴ  氏名  ＦＲＯＭ  社員  ＷＨＥＲＥ  年齢＞３０  ＡＮＤ  所属＝営業【００４５】同様に，集合Ａ１−（Ａ２∪Ａ３）を取り出す検索式は以下のようになる．
ＳＥＬＥＣＴ  氏名  ＦＲＯＭ  社員  ＷＨＥＲＥ  年齢＞５０
ＤＩＦＦＥＲＥＮＣＥ
（ＳＥＬＥＣＴ  氏名  ＦＲＯＭ  社員  ＷＨＥＲＥ  年齢＞４０  ＡＮＤ  所属＝経理  ＵＮＩＯＮ
ＳＥＬＥＣＴ  氏名  ＦＲＯＭ  社員  ＷＨＥＲＥ  年齢＞３０  ＡＮＤ  所属＝営業）
他の６つについても同様である．【００４６】実は，上の（Ａ１∩Ａ２）−Ａ３に対応する検索式は，以下のようなより簡単なＳＱＬに等価変形することも可能である．
ＳＥＬＥＣＴ  氏名  ＦＲＯＭ  社員  ＷＨＥＲＥ  年齢＞５０  ＡＮＤ  所属＝経理また，同じ社員データの所属の項目の値が，経理でもあり同時に営業でもあることはありえないことを考えれば，Ａ１∩Ａ２∩Ａ３や（Ａ２∩Ａ３）−Ａ１に対応する検索式は，解集合が常に空集合であるため，必要ないことがわかる．しかし，このような，与えられた検索式の簡単化や解が常に空集合となる検索式の判定の技術は，先行技術が存在する，当発明とは独立した技術であるので，ここでは詳しくは述べない．【００４７】上述のようにして作成した７つの検索式の解集合が，互いに重複する要素を含まないことは，第一の実施形態の説明の中でも述べたように，直感的には，これらの７つの検索式が図３に示す，Ａ１，Ａ２，Ａ３の関係を表わすベン図中の７つの領域に対応する集合を解集合とする検索式であることから容易にわかる．【００４８】上の７つの検索式の解を受け取った検索解合成装置は，これらを用いて，当初の三つの検索式の解集合Ａ１，Ａ２，Ａ３を合成する．例えば，一つ目の検索式の解集合Ａ１は，以下の四つの解集合
Ａ１∩Ａ２∩Ａ３
（Ａ１∩Ａ２）−Ａ３
（Ａ１∩Ａ３）−Ａ２
Ａ１−（Ａ２∪Ａ３）
の集合和を求めればよい．Ａ２，Ａ３についても同様である．この点も，図３から容易に確認できる．【００４９】このようにして合成した検索式を用いてデータの取り出しを行うことで，検索装置が格納装置から同じデータを複数回取り出すことを避けることができ，検索装置の部分の処理の効率を向上することができる．例えば，単純に，与えられた三つの検索式を順番に実行した場合，年齢が５０を超えていて所属が経理であるような社員の氏名のデータは，一つ目の検索式の実行の際と，二つ目の検索式の実行の際の，二回取り出されることになるが，上述の７つの検索式を用いてデータの取り出しを行った場合，いかなるデータも，二回以上，検索装置によって取り出されることはない．【００５０】また，検索式合成装置や検索解合成装置がネットワーク等を介して接続されたクライアント上にある場合には，サーバからクライアントへは重複を取り除いたデータが送信され，クライアント上で，重複を含む当初の検索式の解集合を合成するため，ネットワークの通信コストを軽減することができる．【００５１】また，ユーザが，当初の検索式の解集合中に含まれる全データを閲覧することさえできれば，必ずしも当初の検索式の解集合の形に合成する必要がない場合は，検索解合成装置の機能をオフにし，合成された検索式の解をそのまま出力装置に送って出力してもよい．これにより，ユーザは，当初の三つの検索式の解を閲覧する場合に比べて，同一のデータを複数回見ないですむことになり，閲覧の利便性が向上する．【００５２】ここまでは検索式が三つの場合の例を用いて説明したが，一般的には以下のような手順で検索式の合成を行う．まず，検索式の集合Ｓ＝｛Ｑ１，…，Ｑｎ｝が与えられたとする．その場合，Ｓの空でない任意の部分集合Ｔに対して，Ｔに含まれる全ての検索式の積（すなわち，全ての検索式の条件を満たすデータを取り出す検索式）と，Ｔに含まれない全ての検索式の和（すなわち，いずれかの検索式の条件を満たすデータを取り出す検索式）との，これら二つの検索式の差（すなわち，前者の検索式の条件は満たすが，後者の検索式の条件は満たさないデータを取り出す検索式）にあたる検索式を作成する．すなわち，Ｓの空でない任意の部分集合Ｔに対して，
【数３】
0004623446.tif 000004
で定義される検索式Ｑ（Ｔ）を求める．ここでは，∩，∪，−はそれぞれ，検索式の積演算，和演算，差演算を表わし，ＳＱＬでは，前述のように，各々，ＩＮＴＥＲＳＥＣＴ構文，ＵＮＩＯＮ構文，ＤＩＦＦＥＲＥＮＣＥ構文で表現できる．ここでは，取出し要求の記述にＳＱＬ検索式を用いる場合を例にとっているが，他の多くの取出し要求記述言語においても，同様の積，和，差にあたる取出し要求の合成が容易に可能である．そして，全ての空集合でない部分集合Ｔに対するＱ（Ｔ）を使って，データを取り出す．上の式は，複数の集合をベン図で表わした際の，ベン図中の各領域に対応する集合を表わす式を，そのまま検索式の式に置き換えたものであり，よって，この式で定義される各検索式の解集合が重複を含まないことは明らかである．【００５３】そして，それらの解から当初の検索式Ｑｉの解を合成するには，データの取出しに用いた全ての検索式のうち，Ｑｉを含むＴを用いて作成された検索式の全ての解集合の和集合を取ればよい．すなわち，Ｑｉの解集合をＡｉ，Ｑ（Ｔ）の解集合をＡ（Ｔ）と書くことにすると，
【数４】
0004623446.tif 000005
である．上記の式が成り立つことについても，複数の集合をベン図で表わした際の，各領域と，各集合の間の関係に関する，一般的に知られている数学的性質より明らかである．【００５４】また，ここで，前述のような検索式の簡単化や不要な検索式の除外を行った場合は，検索解合成装置は，Ｑｉの解の合成については，Ｑｉを含むＴを用いて作成された検索式，またはそれを簡単化した検索式のうち，除外されなかったもの全てに対する解集合の和集合を取ることで，これを行う．【００５５】（第三の実施の形態）
次に，本発明の第三の実施の形態の詳細について，詳しく説明する．本説明においては，本発明を，木構造で表現できるデータの一種であるＸＭＬデータを格納して，これに対するデータ取出し要求の記述にＸＰａｔｈと呼ばれるパス式の一種（より詳しくは，下記非特許文献３参照）を用いる，ＸＭＬデータベースシステムに適用する場合の一実施形態について説明する．
【非特許文献３】Ｊ．Ｃｌａｒｋ，Ｓ．ＤｅＲｏｓｅ著  ”ＸＭＬ  Ｐａｔｈ  Ｌａｎｇｕａｇｅ  ＸＰａｔｈ  Ｖｅｒｓｉｏｎ  ２．０  −  Ｗ３Ｃ  Ｗｏｒｋｉｎｇ  Ｄｒａｆｔ”  ｈｔｔｐ：／／ｗｗｗ．ｗ３．ｏｒｇ／ＴＲ／ｘｐａｔｈ２０
【００５６】ＸＰａｔｈは，ＸＭＬの木構造中の任意の深さのノードを根とする部分木の集合を取り出す要求を記述する言語であり，よって，この実施形態においては，第一，第二の実施形態で生じたような，同じデータが複数の検索式の解集合に重複して現れるという種類の重複に加えて，取り出し要求が取り出すある部分木が，その取り出し要求自身または同時に与えられた別の取り出し要求が取り出す別の部分木の，その一部をなす部分木として重複して出現するという種類の重複も起こりうる．よって，本実施形態においては，このような重複についても取り除く処理を行う．本実施形態においては，これらの重複を，取り出したデータを調べることによって発見する．【００５７】本実施形態におけるＸＭＬデータベースシステムの全体構成図は，第一の実施形態の場合と同様，図２に示すようになる．本実施形態におけるＸＭＬデータベースシステムは，大きなＸＭＬデータの木構造を格納する格納装置４と，ユーザからＸＰａｔｈで記述された検索式の入力を受け取る入力装置１と，入力装置１が受け取った一つまたは複数の検索式を受け取り，各検索式について，格納装置４中のＸＭＬデータから，その検索式の解となる部分木の集合を取り出す検索装置３と，検索装置３が取り出したデータを受け取って，このデータを調べて発見した重複を取り除く重複除去装置１０と，重複除去装置がが生成したデータを受け取って出力する出力装置６からなる．【００５８】以下，本実施形態において，入力装置が検索式または検索式の集合を受け取った際の処理手順について説明する．例えば，入力装置が以下の三つのＸＰａｔｈ検索式の集合を受け取ったとする．
／ａ／ｂ
／ａ／ｃ／＊
／ａ／＊／ｄ
一つ目の／ａ／ｂは，格納されているＸＭＬデータの木構造の根からスタートして，その子供のａというタグ名を持つノードの，さらにその子供のｂというタグ名を持つノードを取り出せという要求を表わす．一方，二つ目の検索式の中の＊は「任意のタグ名」を表わし，／ａ／ｃ／＊は，根からスタートして，その子供のａというタグ名を持つノードの，さらにその子供のｃというタグ名を持つノードの，さらにその子供の任意のタグ名を持つノードを取り出せという要求を表わす．同様に，三つ目の／ａ／＊／ｄは，根からスタートして，その子供のａというタグ名を持つノードの，さらにその子供の任意のタグ名を持つノードの，さらにその子供のｄというタグ名を持つノードを取り出せという要求を表わす．【００５９】よって，これら三つの検索式の解集合は，互いに重複して現れる要素を含みうる．具体的には，まず，／ａ／ｃ／ｄという検索式にマッチするようなノードは，全て／ａ／ｃ／＊と／ａ／＊／ｄの双方の解集合の要素として重複して現れる．また，／ａ／＊／ｄの解集合中の要素のうち，／ａ／ｂ／ｄという検索式にマッチするようなノードは，／ａ／ｂの解集合中のある要素の部分木としても重複して現れる．【００６０】例えば，図５に示す木構造で表現されるようなＸＭＬデータに対して上の三つの検索式を評価した場合，それぞれの検索式に対する解集合は，図６に示したようになる．ここで，／ａ／ｃ／＊の解集合中の二つの部分木のうち，左の物は，／ａ／＊／ｄの解集合中にも重複して現れている．また，／ａ／＊／ｄの解集合中の三つの部分木のうち，一番左の物は，／ａ／ｂの解集合中の部分木の，その一部をなす部分木としても重複して出現している．【００６１】よって，この場合は，入力装置が前述の三つの検索式を検索装置に送って，検索装置がこれらに対する解集合を取り出し，これを重複除去装置に送った後，重複除去装置は送られた解集合を調べて，これらの重複のいずれか一方を除去し，例えば，図７に示す結果を出力装置へと送り，これを出力装置が出力する．【００６２】このように，同じ部分木が複数の解集合中に要素として現れるような重複や，ある解集合中のある要素が，別のあるいは同じ解集合中のある要素の部分木として現れるような重複を取り除いて出力することによって，ユーザが同じデータを複数回見ることがなくなり，ユーザの閲覧の利便性を増すことができる．【００６３】上の例では，複数の検索式を受け取って，ある検索式の解が，別の検索式の解，またはその一部をなす部分木として重複して出現する例を示したが，ＸＰａｔｈで用いられる構文「｜」や「／／」を含む検索式が与えられた場合には，ある一つの検索式の解集合中のある部分木が，同じ解集合中の別の部分木の一部をなす部分木として重複して出現する場合もある．例えば，以下の検索式が与えられたとする．
／ａ／ｂ  ｜  ／ａ／＊／ｄ
「｜」は，二つの検索式の「和」を表わし，上の検索式の場合，／ａ／ｂと／ａ／＊／ｄの二つの検索式の解集合の和集合が，解集合となる．すなわち，図６中の左端の集合と右端の集合の和集合が解集合となる．よって，右端の集合の一番左の部分木は，他の解である，左端の集合中の部分木の，その一部をなす部分木としても重複して出現することになる．よって，重複除去装置は，このような一つの解集合中の重複についても，これを除去する．【００６４】同様に，「／／」を含む検索式の例として以下の検索式を考える．
／ａ／ｂ／／＊
「／／」は，直感的には「その下の任意の深さの子孫の」という意味を表わし，上の検索式は，根からスタートして，その子供のａというタグ名を持つノードの，その子供のｂというタグ名を持つノードの，その下の任意の深さの子孫の，任意のタグ名を持つノードを取り出せという要求を表わす．よって，この検索式を図５に示したデータに対して評価した場合，図８に示す部分木集合が解集合となる．この解集合中の右に示した解は，左に示した解の部分木としても重複して出現する．よって，重複除去装置は，このような重複についても，これを除去する．【００６５】（第四の実施の形態）
次に，本発明の第四の実施の形態の詳細について，詳しく説明する．本説明においては，本発明を，第三の実施形態と同様に，木構造で表現できるデータの一種であるＸＭＬデータを格納して，これに対するデータ取出し要求の記述にＸＰａｔｈと呼ばれるパス式の一種（より詳しくは，上記非特許文献３参照）を用いる，ＸＭＬデータベースシステムに適用する場合の一実施形態について説明する．【００６６】第三の実施の形態の場合と同様，この実施形態においては，第一，第二の実施形態で生じたような，同じデータが複数の検索式の解集合に重複して現れるという種類の重複に加えて，取り出し要求が取り出すある部分木が，その取り出し要求自身または同時に与えられた別の取り出し要求が取り出す別の部分木の，その一部をなす部分木として重複して出現するという種類の重複も起こりうる．よって，本実施形態においては，これら双方の種類の重複を取り除く処理を行う．また，本実施形態においては，与えられた検索式をもとに合成した検索式を用いてデータを取り出すことで，これらの重複を取り除いた形でデータを取り出す．【００６７】図９に，本実施形態におけるＸＭＬデータベースシステムの全体構成図を示す．本実施形態におけるＸＭＬデータベースシステムは，大きなＸＭＬデータの木構造を格納する格納装置４と，ユーザからＸＰａｔｈで記述された検索式の入力を受け取る入力装置１と，入力装置１が受け取った一つまたは複数の検索式をもとに新たな検索式を合成する検索式合成装置２と，検索式合成装置２が生成した一つまたは複数の検索式を受け取って，各検索式について，格納装置４中のＸＭＬデータから，その検索式の解となる部分木の集合を取り出す検索装置３と，検索装置３が取り出したデータを受け取って出力する出力装置６からなる．【００６８】以下，本実施形態において，入力装置が検索式または検索式の集合を受け取った際の処理手順について説明する．例として，入力装置が前述の第三の実施の形態の場合と同様，以下の三つのＸＰａｔｈ検索式の集合を受け取ったとする．
／ａ／ｂ
／ａ／ｃ／＊
／ａ／＊／ｄ【００６９】この場合，検索式合成装置は，まず，異なる検索式の解集合間のデータの重複を取り除くため，上記の三つの検索式を，以下のように変形する．
／ａ／ｂ
／ａ／ｃ／＊  −  ／ａ／ｂ
／ａ／＊／ｄ  −  ／ａ／ｂ  −  ／ａ／ｃ／＊
より一般には，全検索式に適当な順番を決め，各検索式の末尾に，その検索式より順番の若い検索式全てを「−」でつないで並べれば良い．このようにして生成された検索式を，さらに，ある解が他の解の部分木として現れるような重複を取り除くため，以下のように変形する．
／ａ／ｂ−／ａ／ｂ／／＊−／ａ／ｃ／＊／／＊−／ａ／＊／ｄ／／＊
／ａ／ｃ／＊  −  ／ａ／ｂ
−  ／ａ／ｂ／／＊  −  ／ａ／ｃ／＊／／＊  −  ／ａ／＊／ｄ／／＊
／ａ／＊／ｄ  −  ／ａ／ｂ  −  ／ａ／ｃ／＊
−／ａ／ｂ／／＊−／ａ／ｃ／＊／／＊−／ａ／＊／ｄ／／＊
より一般には，各検索式の後ろに，全検索式の末尾に／／＊を追加したものを，−でつないで並べる．このように変形した検索式を用いてデータを取り出すことで，重複を除去した状態でデータを取り出すことができ，データの取り出し処理のコストの低減や，ユーザの閲覧の利便性の向上が期待できる．【００７０】ここで，上に示した変形後の検索式に対しては，簡単化や，解集合が常に空集合となる検索式の除去が可能である．しかし，前述の通り，これらは本発明とは独立した技術であるので，ここでは詳しくは述べない．また，ここでは，木構造データからの部分木集合の取出し要求の記述にＸＰａｔｈを用いる場合を例にとって，検索式の合成方法について説明したが，他の多くの取出し要求記述言語においても，同様の合成が可能である．【００７１】（第五の実施の形態）
次に，本発明の第五の実施の形態の詳細について，詳しく説明する．本説明においては，本発明を，第三，第四の実施形態と同様に，木構造で表現できるデータの一種であるＸＭＬデータを格納して，これに対するデータ取出し要求の記述にＸＰａｔｈと呼ばれるパス式の一種（より詳しくは，上記非特許文献３参照）を用いる，ＸＭＬデータベースシステムに適用する場合の一実施形態について説明する．【００７２】この実施形態においても，第一，第二の実施形態で生じたような，同じデータが複数の検索式の解集合に重複して現れるという種類の重複に加えて，第三，第四の実施の形態で生じたような，取り出し要求が取り出すある部分木が，その取り出し要求自身または同時に与えられた別の取り出し要求が取り出す別の部分木の，その一部をなす部分木として重複して出現するという種類の重複が起こりうる．よって，本実施形態においては，これら双方の種類の重複を取り除く処理を行う．また，本実施形態においては，与えられた検索式をもとに合成した検索式を用いてデータを取り出すことで，これらの重複を取り除いた形でデータを取り出す．さらに，本実施形態では，そのようにして重複を取り除いたデータから，必要に応じて，当初の検索式の解集合を合成することが可能である．【００７３】図１に，本実施形態におけるＸＭＬデータベースシステムの全体構成図を示す．本実施形態におけるＸＭＬデータベースシステムは，大きなＸＭＬデータの木構造を格納する格納装置４と，ユーザからＸＰａｔｈで記述された検索式の入力を受け取る入力装置１と，入力装置１が受け取った一つまたは複数の検索式をもとに新たな検索式を合成し，それと同時に，合成された検索式の解からの，当初の検索式の解の取出し方法を指示する記述を生成する検索式合成装置２と，検索式合成装置２が生成した一つまたは複数の検索式を受け取って，各検索式について，格納装置４中のＸＭＬデータから，その検索式の解となる部分木の集合を取り出す検索装置３と，検索装置３が取り出したデータ，および，検索式合成装置２が生成した，当初の検索式の解の取出し方法を指示する記述を受け取って，当初の検索式の解を合成する検索解合成装置５と，検索解合成装置５が生成したデータを受け取って出力する出力装置６からなる．【００７４】これらの構成要素は全て同じ計算機上にあってもよいし，あるいは，格納装置４と検索装置３のみが，サーバとなる計算機７の上にあって，入力装置１，検索式合成装置２，検索解合成装置５，出力装置６は，サーバ７とネットワーク８を介して接続されたクライアント計算機９の上にあるという配置でもよい．【００７５】以下，本実施形態において，入力装置が検索式または検索式の集合を受け取った際の処理手順について説明するが，ここでは，これを理解の容易さを考えて，三つの場合に分けて説明する．まず最初に，受け取ったＸＰａｔｈ検索式が，前述の「／／」という構文を含まず，かつ，全ての検索式がＸＭＬデータの木構造中の同じ深さのノードを取り出す要求である場合の処理手順について説明する．この場合の処理手順は，当発明を第一の実施形態のように木構造データ以外のデータ管理システムに適用している場合など，ある解が別の解の部分木として重複する場合を考慮しない場合の処理手順と同様のものになる．二番目に，検索式が「／／」を含まないが，各検索式が取り出すノードの深さは全て同じではない場合の処理手順について説明する．最後に，検索式が「／／」を含む場合の処理手順について説明する．以上，理解の容易さのために三つの場合にわけて説明するが，実際には，最後に説明する処理手順が，全ての場合に対応する最も一般的な処理手順になっており，この処理手順を，一番目，二番目に取り上げるような特殊な場合に適用すれば，一番目，二番目に説明する処理手順と同等の最終結果を得ることができる．【００７６】受け取ったＸＰａｔｈ検索式が「／／」を含まず，検索式全てが同じ深さのデータを取り出す場合の処理手順は，以下のようになる．例えば，入力装置が以下の三つのＸＰａｔｈ検索式の集合を受け取ったとする．
／ａ／ｂ
／ａ／＊
／ａ／＊［ｃ／ｄ］
一つ目の／ａ／ｂは，格納されているＸＭＬデータの木構造の根からスタートして，その子供のａというタグ名を持つノードの，さらにその子供のｂというタグ名を持つノードを取り出せという要求を表わす．一方，二つ目の／ａ／＊は，根からスタートして，その子供のａというタグ名を持つノードの，さらにその子供の任意のタグ名を持つノードを取り出せという要求を表わす．また，三つ目の検索式の中の［ｃ／ｄ］は「その下に，ｃ／ｄというパスを持つ」という条件を表わしており，／ａ／＊［ｃ／ｄ］という検索式は，根からスタートして，その子供のａというタグ名を持つノードの，さらにその子供の任意のタグ名を持つノードであって，しかも，その下にｃという子ノードを持ち，さらに，そのｃという子ノードがｄという子ノードを持っているようなものを取り出せという要求を表わす．【００７７】よって，これら三つの検索式の解集合は，互いに重複して現れる要素を含みうる．具体的には，／ａ／ｂまたは／ａ／＊［ｃ／ｄ］の解集合の要素となるノードは，全て／ａ／＊の解集合の要素としても現れる．また，／ａ／ｂと／ａ／＊［ｃ／ｄ］の解集合は，同じ要素を重複して持ちうる．一方，この例の場合は，三つの検索式とも木構造中の深さ２のノードを取り出すため，一つの解集合のある要素が，同じまたは他の解集合の要素の部分木として重複して出現することはありえない．【００７８】よって，本システムではこの場合，与えられた検索式集合の任意の空でない部分集合，すなわちこの場合で言うと
｛／ａ／ｂ，／ａ／＊，／ａ／＊［ｃ／ｄ］｝
｛／ａ／ｂ，／ａ／＊｝
｛／ａ／ｂ，／ａ／＊「ｃ／ｄ］｝
｛／ａ／＊，／ａ／＊［ｃ／ｄ］｝
｛／ａ／ｂ｝
｛／ａ／＊｝
｛／ａ／＊［ｃ／ｄ］｝
という七つの部分集合の各々に対して，該部分集合中の全検索式の積と，該部分集合に含まれない検索式の集合である
｛｝
｛／ａ／＊［ｃ／ｄ］｝
｛／ａ／＊｝
｛／ａ／ｂ｝
｛／ａ／＊，／ａ／＊「ｃ／ｄ］｝
｛／ａ／ｂ，／ａ／＊［ｃ／ｄ］｝
｛／ａ／ｂ，／ａ／＊｝
に含まれる全検索式の和との，両者の差に相当する七つの検索式
／ａ／ｂ  ∩  ／ａ／＊  ∩  ／ａ／＊「ｃ／ｄ］                （検索式１）
（／ａ／ｂ  ∩  ／ａ／＊）  −  ／ａ／＊［ｃ／ｄ］              （検索式２）
（／ａ／ｂ  ∩  ／ａ／＊「ｃ／ｄ］）  −  ／ａ／＊              （検索式３）
（／ａ／＊  ∩  ／ａ／＊［ｃ／ｄ］）  −  ／ａ／ｂ              （検索式４）
／ａ／ｂ  −  （／ａ／＊  ∪  ／ａ／＊［ｃ／ｄ］）            （検索式５）
／ａ／＊  −  （／ａ／ｂ  ∪  ／ａ／＊［ｃ／ｄ］）            （検索式６）
／ａ／＊［ｃ／ｄ］  −  （／ａ／ｂ  ∪  ／ａ／＊）            （検索式７）
を検索式合成装置が求め，これら七つの検索式を検索装置に送って検索を行う．これは，前述の第二の実施の形態の場合と同様の手順である．【００７９】ここで，∩は二つの検索式の積，すなわち，二つの検索式双方の条件を満たすノードを取り出す要求を表わす．同様に，∪は二つの検索式の和，すなわち，二つの検索式双方の条件のいずれかを満たすノードを取り出す要求を表わし，また―は二つの検索式の差，すなわち，前者の検索式の条件は満たすが，後者の検索式の条件は満たさないノードを取り出す要求を表わす．これらの記法は，実際のＸＰａｔｈでの記法とは異なる（例えば，∪は実際のＸＰａｔｈでは，前述のように「｜」と記述される）が，ここでは説明のわかりやすさのため，このような記法を用いることにする．上の式１〜７に対する解集合が，互いに重複する要素を含まないことは，第二の実施の形態の場合とほぼ同様である．このように合成した検索式を用いてデータを取り出すことにより，重複したデータの取り出し，あるいは重複したデータのネットワークを介しての送信を避けることができる．【００８０】検索装置は，上のような合成された検索式を受け取ってその解を検索し，検索解合成装置へ対応する七つの解集合を送る．検索解合成装置は，これらの解集合のうち，／ａ／ｂを含む部分集合を用いて作成された，検索式１，２，３，５に対する解集合の集合和を取ることによって，当初の検索式である／ａ／ｂに対する解集合を生成する．また，／ａ／＊の解は，検索式１，２，４，６に対する解集合の集合和を，／ａ／＊［ｃ／ｄ］の解については，検索式１，３，４，７に対する解集合の和集合を取ることによって生成する．【００８１】また，この例の場合，式１は，より単純な検索式／ａ／ｂ［ｃ／ｄ］と等価であり，式３は解集合が常に空集合となる検索式である．他の式についても，同様な簡単化が可能なものや，解が常に空となるものがある．よって，検索式合成装置は，このような検索式の簡単化や，解が空となる検索式の除外を行ってもよい．このような，パス式の形で記述されている検索式の簡単化や，解集合が常に空集合となる検索式の判定のための技術については，下記非特許文献４，５に示されているものなど，様々な先行技術があり，当発明とは独立した技術であるので，ここでは，詳しくは述べない．
【非特許文献４】Ｇ．Ｍｉｋｌａｕ，Ｄ．Ｓｕｃｉｕ著  ”Ｃｏｎｔａｉｎｍｅｎｔ  ａｎｄ  Ｅｑｕｉｖａｌｅｎｃｅ  ｆｏｒ  ａｎ  ＸＰａｔｈ  Ｆｒａｇｍｅｎｔ”  ＡＣＭ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｐｒｉｎｃｉｐｌｅｓ  ｏｆ  Ｄａｔａｂａｓｅ  Ｓｙｓｔｅｍｓ（ＰＯＤＳ）予稿集，頁６５−７６，２００２
【非特許文献５】Ｍ．Ｂｅｎｅｄｉｋｔ他著  ”Ｓｔｒｕｃｔｕｒａｌ  Ｐｒｏｐｅｒｔｉｅｓ  ｏｆ  ＸＰａｔｈ  Ｆｒａｇｍｅｎｔｓ”  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｄａｔａｂａｓｅ  Ｔｈｅｏｒｙ（ＩＣＤＴ）予稿集，頁７９−９５，２００３
【００８２】上述のような検索式の簡単化や除外を行った場合は，検索解合成装置は，／ａ／ｂを含む部分集合をもとに生成された検索式の簡単化によって得られ，かつ除外されなかったものの全ての解集合の和集合を求めて／ａ／ｂの解を生成する．他の検索式の解についても同様である．これについても，前述の第二の実施形態の場合と同様である．【００８３】ここまでは，特定の例を用いて手順を説明したが，より一般的には，第二の実施の形態の場合と同様，与えられた検索式集合の部分集合で空でないもの全てに対して，該部分集合をＴとして数式３で定義される検索式を生成し，これら全ての検索式によってデータの取出しを行う．また，取り出したデータからの当初検索式の解の合成も，第二の実施の形態の場合と同様，数式４に基づいて合成を行う．【００８４】次に，検索式が「／／」を含まないが，全ての検索式が同じ深さのノードの取出し要求ではない場合の処理手順について説明する．この場合，検索式合成装置は，以下の手順で検索式の合成を行う．
（１）まず，与えられた検索式全てにＱ１，Ｑ２，…という識別子を割り当て，さらに与えられた検索式全てをパスの長さでグループに分類する．
（２）上の（１）で得られたグループ各々について以下の処理を行う．
（３）そのグループに含まれる全検索式の集合をＳとし，Ｓの空でない全ての部分集合の各々をＴとして，以下の処理を行う．
（４）そのグループより長い検索式全てから，現在考えているグループの長さの接頭辞を取り出し，これらの接頭辞の集合をＰとし，Ｐの全ての部分集合の各々をＲとして，以下の処理を行う．
（５）現在のグループより短い検索式全てについて，その末尾に／＊／…／＊を追加して現在のグループと同じ長さにした検索式を作成し，これら全ての和をＥとする．以上を用いて以下の式
【数５】
0004623446.tif 000006
にあたるパス式を作成する．また，このようにして生成された各パス式に対して，順に，Ｖ１，Ｖ２…という識別子を割り当てていく．
（６）また，それと同時に，Ｔに含まれる検索式Ｑｘ，Ｑｙ，…の各々について，今，作成したＶａの解となる部分木が，そのまま，Ｑｘ，Ｑｙ，…の解として取り出されるべきであることを表わす，
Ｑｘ←（Ｖａ，＊）
Ｑｙ←（Ｖａ，＊）
：
：
という項を生成する．同様に，Ｒに含まれる接頭辞ｐの各々について，その接頭辞を取り出した検索式をＱｘ，また，Ｑｘからその接頭辞ｐを取り除いた残りの部分にあたる接尾辞をｐｐとして，Ｖａの解となる部分木の根からパス＊／ｐｐにしたがってたどって到達するノードが，Ｑｘの解として取り出されるべきであることを表わす，
Ｑｘ←（Ｖａ，＊／ｐｐ）
：
：
という項を生成する．【００８５】例として，以下の三つの検索式が与えられた場合について説明する．
／ａ／ｂ／ｃ
／ａ／＊／ｃ／ｄ
／ａ／ｂ／ｃ［ｄ］／＊
一つ目の検索式は，根からスタートして，ａというタグ名を持つ子ノードの，その子供でｂというタグ名を持つノードの，その子供でｃというタグ名を持つノードを取り出す．二つ目の検索式は，根からスタートして，ａというタグ名を持つ子ノードの，その任意の子ノードの，その子供でｃというタグ名を持つノードの，その子供でｄというタグ名を持つノードを取り出す．また，三つ目の検索式は，根からスタートして，ａというタグ名を持つ子ノードの，その子供でｂというタグ名を持つノードの，その子供でｃというタグ名を持ち，かつ，ｄというタグ名の子供を持つノードの，その任意の子ノードを取り出す．【００８６】これら三つの検索式の解集合は，以下のようなデータの重複を含みうる．まず，二つ目の検索式の解集合と三つ目の検索式の解集合とには，同じ要素が重複して出現しうる．さらに，二つ目と三つ目の検索式の解集合中の一部の要素は，一つ目の検索式の解集合中のある解の部分木として出現しうる．例えば，システムに現在格納されているＸＭＬデータ中に，／ａ／ｂ／ｃ／ｄという検索式にマッチするようなノードがあった場合，このノードは二つ目の検索式の解となるが，一方で，そのノードの親ノードは一つ目の検索式の解となるので，このノードは二つ目の検索式の解集合中の要素として出現すると同時に，一つ目の検索式の解集合中のある要素の部分木としても重複して出現することになる．【００８７】そこで，検索式合成装置は以下の手順で検索式の合成を行う．まず，これらの検索式に対して，識別子Ｑ１，Ｑ２，Ｑ３を割り当てる．次に，これらの検索式を，長さ３のグループ｛Ｑ１｝と長さ４のグループ｛Ｑ２，Ｑ３｝に分類する．まず，長さ３のグループについて考えると，その空でない部分集合は｛Ｑ１｝のみなので，これをＴとして（４）以下の処理を行う．次の（４）において，このグループより長い全ての検索式から長さ３の接頭辞を取り出した集合Ｐは｛／ａ／＊／ｃ，／ａ／ｂ／ｃ［ｄ］｝となるので，これの部分集合
｛／ａ／＊／ｃ，／ａ／ｂ／ｃ［ｄ］｝
｛／ａ／＊／ｃ｝
｛／ａ／ｂ／ｃ［ｄ］｝
｛｝
の各々をＲとする四通りの場合について（５）を行う．今の場合，現在のグループより短い検索式はなく，Ｅに該当する検索式は存在しない．よって，Ｒとして｛／ａ／＊／ｃ，／ａ／ｂ／ｃ［ｄ］｝を選んだ場合は，以下のパス式が作成される．
／ａ／ｂ／ｃ  ∩  ／ａ／＊／ｃ  ∩  ／ａ／ｂ／ｃ［ｄ］
同時に，この検索式にＶ１という識別子を割り当てる．また，この検索式は検索式生成に用いるＴとしては｛Ｑ１｝を用いていたので，Ｖ１の解が，そのままＱ１の解としても取り出されるべきであることを表わす項である
Ｑ１←（Ｖ１，＊）
が生成される．さらに，この検索式は，検索式生成に用いるＲとしては，Ｑ２から取り出した接頭辞である／ａ／＊／ｃとＱ３から取り出した接頭辞である／ａ／ｂ／ｃ［ｄ］がらなる集合を用いていたので，Ｖ１の解となる部分木の根から，／ａ／＊／ｃに対応する接尾辞であるｄというパスをたどって到達する要素もＱ２の解として取り出すべきであることを表わす項である
Ｑ２←（Ｖ１，＊／ｄ）
と，Ｖ１の解となる部分木の根から，／ａ／ｂ／ｃ［ｄ］に対応する接尾辞である＊というパスをたどって到達する要素もＱ３の解として取り出すべきであることを表わす項の
Ｑ３←（Ｖ１，＊／＊）
が生成される．【００８８】また，ここで，Ｖ１は／ａ／ｂ／ｃ［ｄ］へと簡単化可能であるので，検索式合成装置はそのような簡単化を行ってもよいが，既に述べたように，簡単化や不要な検索式の除外の具体的な手法については，当発明とは独立した技術なので，ここでは詳しく述べない．【００８９】同様に，手順（４）で残りの三通りのＲの選び方，すなわち，
Ｒ＝｛／ａ／＊／ｃ｝
Ｒ＝｛／ａ／ｂ／ｃ［ｄ］｝
Ｒ＝｛｝
として（５）を実行した場合，それぞれ，
Ｖ２：  ／ａ／ｂ／ｃ  ∩  ／ａ／＊／ｃ  −  ／ａ／ｂ／ｃ［ｄ］
Ｑ１←（Ｖ２，＊）
Ｑ２←（Ｖ２，＊／ｄ）
Ｖ３：  ／ａ／ｂ／ｃ  ∩  ／ａ／ｂ／ｃ［ｄ］  −  ／ａ／＊／ｃ
Ｑ１←（Ｖ３，＊）
Ｑ３←（Ｖ３，＊／＊）
Ｖ４：  ／ａ／ｂ／ｃ  −  ／ａ／＊／ｃ  −  ／ａ／ｂ／ｃ［ｄ］
Ｑ１←（Ｖ４，＊）
という検索式Ｖ２，Ｖ３，Ｖ４，および，それらからの当初の検索式の解の取出し方法を指示する項が生成される．【００９０】次に，長さ４の検索式のグループ｛／ａ／＊／ｃ／ｄ，／ａ／ｂ／ｃ［ｄ］／＊｝について考える．このグループの空でない部分集合は，
｛／ａ／＊／ｃ／ｄ，／ａ／ｂ／ｃ［ｄ］／＊｝
｛／ａ／＊／ｃ／ｄ｝
｛／ａ／ｂ／ｃ［ｄ］／＊｝
である．よって，これらの各々をＴとして（４）を行う．このグループより長い検索式はないので，接頭辞の集合Ｐは空集合となり，その部分集合は空集合のみである．よって，いずれをＴとした場合についても，Ｒを空集合として（５）を行う．Ｅについては，現在のグループより短い検索式は，長さが３の／ａ／ｂ／ｃのみなので，これの長さを４とするために，末尾に／＊を追加して／ａ／ｂ／ｃ／＊とする．その結果，上の三つの集合のうちの｛／ａ／＊／ｃ／ｄ，／ａ／ｂ／ｃ［ｄ］／＊｝をＴとした場合は，
Ｖ５：  ／ａ／＊／ｃ／ｄ  ∩  ／ａ／ｂ／ｃ［ｄ］／＊  −  ／ａ／ｂ／ｃ／＊
という検索式Ｖ５，および，
Ｑ２←（Ｖ５，＊）
Ｑ３←（Ｖ５，＊）
という，Ｖ５からの当初の検索式の解の取出し方法を指示する項が生成される．同様にして，｛／ａ／＊／ｃ／ｄ｝および｛／ａ／ｂ／ｃ［ｄ］／＊｝をＴとした場合は，
Ｖ６：  ／ａ／＊／ｃ／ｄ  −  ／ａ／ｂ／ｃ［ｄ］／＊  −  ／ａ／ｂ／ｃ／＊
Ｑ２←（Ｖ６，＊）
Ｖ７：  ／ａ／ｂ／ｃ［ｄ］／＊  −  ／ａ／＊／ｃ／ｄ  −  ／ａ／ｂ／ｃ／＊
Ｑ３←（Ｖ７，＊）
という検索式Ｖ６，Ｖ７，および，それらからの当初の検索式の解の取出し方法を指示する項が生成される．【００９１】以上から，当初与えられた三つの検索式に対して，七つの検索式と，その解からの当初の検索式の解の取出し方が生成される．これら七つの検索式の解集合は，互いに重複する要素を含まず，またある解集合中のある要素が，同じまたは別の解集合中のある要素の部分木として重複して出現することもない．一方で，これら七つの検索式の解集合は，当初の三つの検索式の解集合の合成に必要な全てのデータを含んでおり，これら七つの検索式の解集合から，上で示された取出し方法にしたがって，当初の三つの検索式の解集合を合成することができる．【００９２】任意の検索式集合に対して，前述の手順で作成された検索式が，上のような性質を満たす理由については，以下のように説明できる．まず，これらの検索式の解が互いに重複する要素を含まない点について説明する．解集合中に重複する解を含みうるのは，長さが同じ検索式同士のみである．一方，検索式の生成に用いられる数式５中の
【数６】
0004623446.tif 000007
の部分は，長さが同じ検索式のグループについて，前述の第二の実施形態の場合や，与えられた検索式が全て同じ長さだった場合において行ったのと同様の，ベン図の各領域に対応する解集合への分類を行っていることになる．よって，数式５によって作成された各検索式は，その解集合中に重複する要素を含まない．【００９３】次に，ある検索式の解集合中のある要素が，同じ検索式または別の検索式の解集合中の別の要素の部分木として出現しないという点について説明する．ある検索式のある解が，ある検索式のある解の部分木として重複して出現しうるのは，前者の検索式が，後者の検索式より長い場合である．しかし，数式５においては，Ｔに含まれる当初検索式より短い全ての検索式について，その後に＊／…／＊を加えて同じ長さにした物の和をＥとして，これに含まれる物を−Ｅによって取り除いており，よって，より短い検索式の解の部分木として現れている物は必ず取り除かれることになる．【００９４】次に，当初検索式の解となるノードは，必ずいずれかの合成検索式の解集合中に出現しているという点について説明する．これは，そのノードの先祖ノードの中に，いずれかの当初検索式の解となるものがある場合と，そのような先祖ノードが全くない場合の二通りに分けられる．そのような先祖ノードがある場合は，それらの先祖ノードの中で最も根に近いノードが，ある一つの合成検索式の解集合中に含まれる．よって，現在問題にしているノードは，その解の一部をなす部分木として出現する．なお，その先祖ノードが解として出現する合成検索式は，その先祖ノードにマッチする検索式全ての集合をＴとし，Ｔ中の検索式より長い検索式の接頭辞のうち，その先祖ノードとマッチするもの全ての集合をＲとして生成された検索式である．一方，そのような先祖ノードが全くない場合は，現在問題としているノード自身が，ある一つの合成検索式の解集合中に出現する．その合成検索式は，その部分木にマッチする全ての検索式の集合をＴとし，Ｔ中の検索式より長い検索式の接頭辞のうち，そのノードとマッチするもの全ての集合をＲとして生成された検索式である．【００９５】次に，上述の方法で生成された各検索式の解から，上述の手法によって，正しく当初検索式の解を合成できる点について説明する．合成に用いる数式５のうちの数式６の部分は，当初検索式のうちのいずれかの解となるノード全てを，そのノードが当初検索式のうちのどれの解集合には含まれどれの解集合には含まれないかに基づいて分類していることに相当する．同様に，数式５中の
【数７】
0004623446.tif 000008
の部分は，これらのノードを，そのノードを根とする部分木からは，他の，より長い検索式のうちのどれとどれの解を，どんなパス式に基づいて取り出せばよいかという観点から分類していることに相当する．よって，数式５は，必要な全ノードを，それをどの検索式の解とすればよいか，そこからどのような部分木を他の解として抜き出せば良いかに基づいて，分類していることに相当し，よって，正しく当初検索式の解を取り出すことができる．【００９６】次に，検索式が「／／」という構文を含む場合の処理手順について説明する．ＸＰａｔｈにおける「／／」という構文は「その下の任意の深さの」という条件を表しており，例えば，／ａ／／ｂはデータの根からスタートして，ａというタグ名を持つ子ノードの，その下の任意の深さの子孫で，ｂというタグ名を持つノードを取り出せという要求を表す．また，／／ａ／ｂは，データ中の任意の深さにあるａというタグ名を持つノードの，その子ノードでｂというタグ名を持つものを取り出せという要求を表す．【００９７】このような「／／」という構文を含む検索式が与えられた場合の処理手順を記述するために，まず，検索式のｉ−接頭辞という概念を以下のように定義する．今，与えられた検索式が
／１  ｐ１  ／２  ｐ２  …  ／ｍｐｍ
という形をしていたとする．ここで，／１，…，／ｍは，それぞれ／であるか，または，／／であるかのいずれかであり，ｐ１，…，ｐｍは，それぞれ，それらの間に挟まれた，／と／／を含まない部分である．この時，０≦ｉ≦ｍ−１であるｉに対して，この検索式のｉ−接頭辞は以下のように定義される．
（１）ｉ≠０で／ｉ＋１が／である場合：
／１  ｐ１  …  ／ｉｐｉ
（２）ｉ≠０で／ｉ＋１が／／である場合：
／１  ｐ１  …  ／ｉｐｉ  ∪  ／１  ｐ１  …  ／ｉ  ｐｉ／／＊
（３）ｉ＝０で／１が／である場合：
φ  （いかなるノードにもマッチしない特別なパス式）
（４）ｉ＝０で／１が／／である場合：
／／＊
例えば，／／ａという長さ１の検索式に対しては，０≦ｉ≦１−１であるｉ，すなわち，ｉ＝０のみについてｉ−接頭辞が定義され，この検索式の０−接頭辞は／／＊である．また，／ｂ／／ｃという長さが２である検索式に対しては，０≦ｉ≦２−１であるｉ，すなわち，ｉ＝０とｉ＝１についてｉ−接頭辞が定義され，この検索式の０−接頭辞はφであり，１−接頭辞は／ｂ∪／ｂ／／＊である．【００９８】上のｉ−接頭辞の定義は，構文「／／」が「／，または，／＊／，または，／＊／＊／，または，…」という無限個の場合を表現するものであることを考慮して，通常のパスの接頭辞の概念を自然に拡張した物になっている．【００９９】上のように，ｉ−接頭辞を定義すると，構文「／／」を含む検索式に対する処理手順は，以下のようになる．
（１）まず，与えられた検索式全てに，Ｑ１，Ｑ２，…という識別子を割り当てる．
（２）与えられた全検索式の集合をＳとし，Ｓの空でない全ての部分集合の各々をＴとして，以下の処理を行う．
（３）与えられた各検索式に対して定義される全てのｉ−接頭辞の集合をＰとし，Ｐの全ての部分集合の各々をＲとして，以下の処理を行う．
（４）全ての検索式について，その末尾に／／＊を追加した検索式を作成し，これら全ての和をＥとして，以下の式
【数８】
0004623446.tif 000009
にあたるパス式を作成する．また，このようにして作成された各パス式に対して，順に，Ｖ１，Ｖ２，…という識別子を割り当てていく．
（５）また，それと同時に，Ｔに含まれる検索式Ｑｘ，Ｑｙ，…の各々について，今，作成したＶａの解となる部分木が，そのまま，Ｑｘ，Ｑｙ，…の解として取り出されるべきであることを表わす，
Ｑｘ←（Ｖａ，＊）
Ｑｙ←（Ｖａ，＊）
：
：
という項を生成する．同様に，Ｒに含まれるｉ−接頭辞ｐの各々について，その接頭辞を取り出した検索式をＱｘ，また，Ｑｘからその接頭辞ｐを取り除いた残りの部分にあたる接尾辞をｐｐとして，Ｖａの解となる部分木の根からパス＊ｐｐにしたがってたどって到達するノードが，Ｑｘの解として取り出されるべきであることを表わす，
Ｑｘ←（Ｖａ，＊ｐｐ）
：
：
という項を生成する．【０１００】上の手順は，構文「／／」を含む検索式はその長さ，すなわち取り出す部分木の現れる深さが可変になる点を考慮して，前述の「／／」を含まない検索式集合に対する手順を自然に拡張した物になっている．また，上の手順は，別の言い方をすると，与えられたパス式のいずれかの解となる部分木のうちで，他の解の一部をなす部分木とはならない物の全てを，それがどのパス式の解集合には含まれどのパス式の解集合には含まれないかという点と，それがどのパス式のどの接頭辞にはマッチしどのパス式のどの接頭辞にはマッチしないかという点の，以上の二点に基づいて分類し，この各分類を取り出すパス式を生成していることに相当する．【０１０１】例として，以下の二つの検索式が与えられた場合について説明する．
／／ａ
／ｂ／／＊
一つ目の検索式は，任意の深さにあるノードでａというタグ名を持つものを根とする部分木を取り出す．二つ目の検索式は，データの根からスタートして，ｂというタグ名を持つ子ノードの，その下の任意の深さにある任意のタグ名を持つノードを根とする部分木を取り出す．この二つの検索式は，以下のようなデータの重複を含みうる．まず，／ｂ／／ａという検索式にマッチするようなノードがあった場合，そのノードは上の二つの検索式の双方の解集合中に要素として含まれる．また，／ｂ／／＊／／ａという検索式にマッチするようなノードがあった場合，そのノードは一つ目の検索式の解集合中の要素として出現すると同時に，二つ目の検索式の解集合中のある要素の部分木としても重複して出現することになる．同様に，／ｂ／／ａ／／＊という検索式にマッチするようなノードがあった場合，そのノードは二つ目の検索式の解集合中の要素として出現すると同時に，一つ目の検索式の解集合中のある要素の部分木としても重複して出現することになる．【０１０２】そこで，検索式合成装置は，以下の手順で検索式の合成を行う．まず，これらの検索式にＱ１，Ｑ２という識別子を割り当てる．次に，検索式の集合｛／／ａ，／ｂ／／＊｝の空でない部分集合
｛／／ａ，／ｂ／／＊｝
｛／／ａ｝
｛／ｂ／／＊｝
の各々に対して，これをＴとして（３）以下の処理を行う．与えられた検索式に対して定義される全てのｉ−接頭辞の集合は
｛／／＊，φ，／ｂ∪／ｂ／／＊｝
であるので，これの全ての部分集合に対して，その各々をＲとして（４）以下の処理を行う．例えば｛／／ａ，／ｂ／／＊｝をＴ，｛／／＊，φ，／ｂ∪／ｂ／／＊｝をＲとした場合，
Ｖ：  ／／ａ  ∩  ／ｂ／／＊  ∩  ／／＊  ∩  φ  ∩  （／ｂ∪／ｂ／／＊）
−  （／／ａ／／＊  ∪  ／ｂ／／＊／／＊）
という検索式Ｖと，Ｖからの当初の検索式の解の取出し方法を表す項の，
Ｑ１←（Ｖ，＊）
Ｑ２←（Ｖ，＊）
Ｑ１←（Ｖ，＊／／ａ）
Ｑ２←（Ｖ，＊／ｂ／／＊）
Ｑ２←（Ｖ，＊／／＊）
が生成される．ここで，／／ａはＱ１の０−接頭辞に対する接尾辞，／ｂ／／＊はＱ２の０−接頭辞に対する接尾辞，／／＊はＱ２の１−接頭辞に対する接尾辞である．【０１０３】ただし，上のＶは，全てのノードにマッチしないφを積の成分として含んでいるため，常に解集合が空集合となる検索式である．よって，このようにφを積の成分として含んでいて，解集合が空集合となることが容易に判定可能なものについては，検索式合成装置で取り除くことにしてもよい．同様に，／／＊が負の成分として含まれる検索式も，常に解集合が空集合となることが容易に判定可能なので，検索式合成装置が取り除くことにしてもよい．さらには「∩／／＊」と「−φ」は省略しても検索式全体の意味が変わらないことが容易にわかるため，これらを省略することによる検索式の簡単化を，検索式合成装置が行うことにしてもよい．ここでは，これらの特に容易な検索式の除去と簡単化については検索式合成装置が行うものとする．その場合，Ｒとしては｛／／＊，／ｂ∪／ｂ／／＊｝と｛／／＊｝の場合のみを考えればよい．結果として，三通りのＴと二通りのＲの組み合わせで，以下の六つの検索式が生成される．
Ｖ１１：  ／／ａ  ∩  ／ｂ／／＊  ∩  （／ｂ∪／ｂ／／＊）
−  （／／ａ／／＊  ∪  ／ｂ／／＊／／＊）
Ｖ１２：  ／／ａ  ∩  ／ｂ／／＊  −  （／ｂ∪／ｂ／／＊）
−  （／／ａ／／＊  ∪  ／ｂ／／＊／／＊）
Ｖ１３：  ／／ａ  ∩  （／ｂ  ∪  ／ｂ／／＊）  −  ／ｂ／／＊
−  （／／ａ／／＊  ∪  ／ｂ／／＊／／＊）
Ｖ１４：  ／／ａ  −  ／ｂ／／＊  −  （／ｂ  ∪  ／ｂ／／＊）
−  （／／ａ／／＊  ∪  ／ｂ／／＊／／＊）
Ｖ１５：  ／ｂ／／＊  ∩  （／ｂ  ∪  ／ｂ／／＊）  −  ／／ａ
−  （／／ａ／／＊  ∪  ／ｂ／／＊／／＊）
Ｖ１６：  ／ｂ／／＊  −  ／／ａ  −  （／ｂ  ∪  ／ｂ／／＊）
−  （／／ａ／／＊  ∪  ／ｂ／／＊／／＊）
さらに，これらから当初のＱ１とＱ２の解の取出し方法を表す項として，
Ｑ１←（Ｖｉ，＊）          ただし  ｉ＝１１，１２，１３，１４
Ｑ２←（Ｖｉ，＊）          ただし  ｉ＝１１，１２，１５，１６
Ｑ１←（Ｖｉ，＊／／ａ）    ただし  ｉ＝１１，１２，１３，１４，１５，１６
Ｑ２←（Ｖｉ，＊／／＊）    ただし  ｉ＝１１，１３，１５
が生成される．ここで，／／ａはＱ１の０−接頭辞である／／＊に対する接尾辞，／／＊はＱ２の１−接頭辞である／ｂ∪／ｂ／／＊に対する接尾辞である．【０１０４】実は，ここで，上のＶ１１〜Ｖ１６は以下のようにさらに簡単化可能である．
Ｖ１１：  ／ｂ／ａ
Ｖ１２：  φ
Ｖ１３：  φ
Ｖ１４：  ／／ａ  −  ／ｂ／／＊  −  ／／ａ／／＊
Ｖ１５：  ／ｂ／＊  −  ／／ａ  −  ／／ａ／／＊
Ｖ１６：  φ
よって，検索式合成装置は，このようなさらなる簡単化を行ってもよい．しかし，前述の通り，このような簡単化のための具体的な技術については，ここでは詳しくは述べない．【０１０５】以上の合成された検索式を用いてデータの取出しを行うことで，重複したデータの取出しを排除することができる．この点について，以下に具体的なデータの例を使って示す．図１０に示したデータに対して，／／ａと／ｂ／／＊を実行した場合の解は，図１１に示す通りになる．図１１からわかるように，これらの解は多くのデータの重複を含み，非常に冗長である．一方，図１０に示したデータに対してＶ１１〜Ｖ１６を実行した場合には，Ｖ１２，Ｖ１３，Ｖ１４，Ｖ１６の解は空集合となり，Ｖ１１，Ｖ１５の解は図１２に示すようになる．そして，これらの解から上述の項に従って，／／ａと／ｂ／／＊の解を取り出すと，正しく図１１と同じ解が取り出せることがわかる．【０１０６】同様の重複の問題は，検索式が「／／」を含む場合には，検索式が一つだけ与えられた場合にも生じる．例として，図１３に示すデータに対して，
／／ａ／＊／＊
という検索式が与えられたとする．この場合の解は，図１４に示すようになる．しかし，この図からわかるように，この解にはｆを根とする部分木が，一度は解として，一度は他の解の一部をなす部分木として，重複して現れている．【０１０７】そこで，上述の手順によって検索式の合成を行うことを考える．まず，上の検索式をＱ１とする．検索式が一つしかないため，Ｔの選び方はＴ＝｛Ｑ１｝のみである．接頭辞の集合は，｛／／＊，／／ａ，／／ａ／＊｝であり，この部分集合の選び方は８通りある．しかし，／／＊については，前述の例の場合と同じように，これをＲに含めない時に生成される検索式は必ず解が空集合となる．よって，Ｒについては，
Ｒ＝｛／／＊，／／ａ，／／ａ／＊｝
Ｒ＝｛／／＊，／／ａ｝
Ｒ＝｛／／＊，／／ａ／＊｝
Ｒ＝｛／／＊｝
の四通りを考えればよく，以下の四つの検索式が生成される。
Ｖ２１：／／ａ／＊／＊∩／／＊∩／／ａ∩／／ａ／＊−／／ａ／＊／＊／／＊
Ｖ２２：／／ａ／＊／＊∩／／＊∩／／ａ−／／ａ／＊−／／ａ／＊／＊／／＊
Ｖ２３：／／ａ／＊／＊∩／／＊∩／／ａ／＊−／／ａ−／／ａ／＊／＊／／＊
Ｖ２４：／／ａ／＊／＊∩／／＊−／／ａ−／／ａ／＊−／／ａ／＊／＊／／＊
さらに，これらから当初のＱ１の解の取出し方法を表す項として，
Ｑ１←（Ｖｉ，＊）              ただし  ｉ＝２１，２２，２３，２４
Ｑ１←（Ｖｉ，＊／／ａ／＊／＊）ただし  ｉ＝２１，２２，２３，２４
Ｑ１←（Ｖｉ，＊／＊／＊）      ただし  ｉ＝２１，２２
Ｑ１←（Ｖｉ，＊／＊）          ただし  ｉ＝２１，２３
が生成される．二番目の項中の／／ａ／＊／＊は，０−接頭辞／／＊に対応する接尾辞であり，同様に，三番目と四番目の項中の／＊／＊と／＊は，１−接頭辞と２−接頭辞に対する接尾辞である．【０１０８】実は，Ｖ２１〜Ｖ２４の検索式は以下のようにさらに簡単化できるので，検索式合成装置はそのような簡単化を行ってもよいが，前述の通り，ここでは詳しくは述べない．
Ｖ２１：／／ａ／ａ／ａ  −  ／／ａ／＊／＊／／＊
Ｖ２２：／／ａ／＊／ａ  −  ／／ａ／＊  −  ／／ａ／＊／＊／／＊
Ｖ２３：／／ａ／ａ／＊  −  ／／ａ  −  ／／ａ／＊／＊／／＊
Ｖ２４：／／ａ／＊／＊  −  ／／ａ  −  ／／ａ／＊  −  ／／ａ／＊／＊／／＊
これらの検索式を図１３に示すデータに対して実行した場合，Ｖ２１，Ｖ２２の解は空集合となり，Ｖ２３，Ｖ２４の解は図１５に示した通りになる．図１５からわかるように，これらの解集合は，全くデータの重複を含まない．そして，これらの結果に対して，上述の取り出し方法を表わす各項を実行すると，正しくＱ１の解を取り出すことができる．【０１０９】以上のように，当初与えられた一つの検索式に対して，四つの検索式と，その解からの当初の検索式の解の取出し方が生成され，これら四つの検索式の解集合は，互いに重複する要素を含まず，またある解集合中のある要素が，同じまたは別の解集合中のある要素の部分木として重複して出現することもない，一方で，これら四つの検索式の解集合は，当初の検索式の解集合の合成に必要な全てのデータを含んでおり，これら四つの検索式の解集合から，上で示された取出し方法にしたがって，当初の検索式の解集合を合成することができる．【０１１０】任意の検索式集合に対して，前述の手順で作成された検索式が，上のような性質を満たす理由については，前述の「／／」を含まない場合の手順に対する説明とほぼ同様にして説明できる．【０１１１】この明細書で示した実施形態では，木構造データから部分木の集合を取り出すシステムに本発明を適用する際の処理に関しては，パス式の形で検索式が与えられる場合を例にとって説明したが，本発明は，その他のさまざまな形で取り出し要求が与えられる場合においても，同様の考え方に基づいて適用可能である．【０１１２】（第六の実施の形態）
次に，本発明の第六の実施の形態について，説明する．本説明では，本発明を，インターネット上で公開されているＸＭＬデータ連続問い合わせシステムのためのプロクシーサーバに適用する場合の一実施形態について説明する．【０１１３】図１６に，本実施形態におけるＸＭＬデータ連続問い合わせシステムとプロクシーサーバの全体構成図を示す．本実施形態においては，ＸＭＬデータ連続問い合わせシステム１１がインターネット１２の上に公開されているものとする．ＸＭＬデータ連続問い合わせシステムとは，ＸＭＬデータを格納し，ユーザからの検索式登録要求を受けるとその検索式を永続的に登録し，ユーザから登録されたこれらの検索式を，定期的に（例えば一定時間毎に）評価し，検索式が評価される度に，評価結果をその問い合わせを登録したユーザに送信するシステムであり，ニュース情報通知サービスや，株価情報通知システム等に利用される，さらに，インターネット１２に接続された社内ネットワーク等のローカルネットワーク１３上に，このＸＭＬデータ連続問い合わせシステム１１を利用するユーザ１４が複数存在するものとする．【０１１４】このような環境において，当実施形態では，このローカルネットワーク１３上に，プロクシーサーバ１５を置き，このローカルネット１３上の各ユーザ１４は，直接，ＸＭＬデータ連続問い合わせシステム１１に自分の検索式を登録する代わりに，このプロクシーサーバ１５に対して検索式を登録する．そして，プロクシーサーバ１５は，複数のユーザ１４から登録された複数の検索式をもとに，第五の実施形態と同様の方法で新たな検索式を合成し，この合成した検索式をＸＭＬデータ連続問い合わせシステム１１に登録する．そして，ＸＭＬデータ連続問い合わせシステムから定期的に結果を受け取る度に，その結果を用いて，各ユーザ１４が登録した検索式の解を合成し，これを各ユーザ１４に送信する．【０１１５】このようにすると，複数のユーザが，解が一部重複するような多数の検索式を登録した場合には，これらの検索式はプロクシーサーバ１５によって，解に重複を含まない問い合わせに置き換えられて連続問い合わせシステム１１に登録され，その結果がインターネット１２を介してプロクシーサーバ１５に送信され，プロクシーサーバ１５において一部重複を含む当初の検索式の解が合成されて，これがローカルネット１３を介して各ユーザ１４に送信されるので，各ユーザ１４が直接，それらの検索式を連続問い合わせシステム１１に登録する場合に比べ，インターネット１２上での重複するデータの送信を排除し，インターネット１２上の通信コストを軽減することができる．
【図面の簡単な説明】
【０１１６】
【図１】第五の実施形態におけるシステムの全体構成図
【図２】第一，第三の実施形態におけるシステムの全体構成図
【図３】三つの解集合Ａ１，Ａ２，Ａ３の間の関係を表わすベン図
【図４】第二の実施形態におけるシステムの全体構成図
【図５】ＸＭＬデータの例（その１）
【図６】／ａ／ｂ，／ａ／ｃ／＊，／ａ／＊／ｄに対する解集合
【図７】図６の解集合から重複を取り除いた状態のデータ
【図８】／ａ／ｂ／／＊に対する解集合
【図９】第四の実施形態におけるシステムの全体構成図
【図１０】ＸＭＬデータの例（その２）
【図１１】／／ａ，／ｂ／／＊に対する解集合
【図１２】Ｖ１１，Ｖ１５に対する解集合
【図１３】ＸＭＬデータの例（その３）
【図１４】／／ａ／＊／＊に対する解集合
【図１５】Ｖ２３，Ｖ２４に対する解集合
【図１６】第六の実施形態におけるシステム環境全体の構成図
【符合の説明】
【０１１７】１  入力装置，    ２  検索式合成装置，    ３  検索装置，    ４  格納装置，
５  検索解合成装置，    ６  出力装置，    ７  サーバ，    ８  ネットワーク，９  クライアント，    １０  重複除去装置，
１１  ＸＭＬデータ連続問い合わせシステム，    １２  インターネット，
１３  ローカルネットワーク，    １４  ユーザ，    １５  プロクシーサーバ
【図１】
0004623446.tif 000010
【図２】
0004623446.tif 000011
【図３】
0004623446.tif 000012
【図４】
0004623446.tif 000013
【図５】
0004623446.tif 000014
【図６】
0004623446.tif 000015
【図７】
0004623446.tif 000016
【図８】
0004623446.tif 000017
【図９】
0004623446.tif 000018
【図１０】
0004623446.tif 000019
【図１１】
0004623446.tif 000020
【図１２】
0004623446.tif 000021
【図１３】
0004623446.tif 000022
【図１４】
0004623446.tif 000023
【図１５】
0004623446.tif 000024
【図１６】
0004623446.tif 000025