JPH0668723B2 - 単一化候補項の選択装置 - Google Patents
単一化候補項の選択装置Info
- Publication number
- JPH0668723B2 JPH0668723B2 JP63296152A JP29615288A JPH0668723B2 JP H0668723 B2 JPH0668723 B2 JP H0668723B2 JP 63296152 A JP63296152 A JP 63296152A JP 29615288 A JP29615288 A JP 29615288A JP H0668723 B2 JPH0668723 B2 JP H0668723B2
- Authority
- JP
- Japan
- Prior art keywords
- term
- index
- variable
- search target
- question
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
- 238000000605 extraction Methods 0.000 claims description 3
- 238000000034 method Methods 0.000 description 18
- 238000010586 diagram Methods 0.000 description 10
- 230000007423 decrease Effects 0.000 description 3
- 238000006243 chemical reaction Methods 0.000 description 2
- 238000001514 detection method Methods 0.000 description 2
- 230000002542 deteriorative effect Effects 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
Landscapes
- Devices For Executing Special Programs (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Description
【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） この発明は、演繹データベース、知識ベース、ファイル
システム等の単一化を伴う検索に際し、項データの集合
から単一化候補項を選択する技術に係わり、特に重ね合
せ符号による項データのインデックスを利用する単一化
候補項の選択装置に関する。
システム等の単一化を伴う検索に際し、項データの集合
から単一化候補項を選択する技術に係わり、特に重ね合
せ符号による項データのインデックスを利用する単一化
候補項の選択装置に関する。
（従来の技術） 演繹データベース、知識ベース等のシステムでは、変数
を含む項データの単一化を伴う検索に際し、検索対象を
絞り込んで検索効率の向上を図るため、予め検索対象と
なる大量の項データの集合から検索項データと単一化可
能性のある単一化候補項を選択することが行われてい
る。この種の選択処理は高速に行われることが重要であ
り、そのため、従来より検索項データ及び被検索項デー
タを高速演算処理に適した形態に変換することが種々行
われている。その一つの方法に、項データをハッシュ値
の重ね合せ符号によるインデックスに変換するＳＳＣＷ
（Structural Superimposed Code Word）方式が知られ
ている。（「ＭＰＰＭを用いた知識ベースマシン
（３）」，森田他，情報処理学会第３５回全国大会，２
Ｃ−７、「知識ベースマシンＭu-Ｘ(4)」，沖瀬他，情
報処理学会第３６回全国大会，５Ｅ−７）。以下、この
方式につい説明する。
を含む項データの単一化を伴う検索に際し、検索対象を
絞り込んで検索効率の向上を図るため、予め検索対象と
なる大量の項データの集合から検索項データと単一化可
能性のある単一化候補項を選択することが行われてい
る。この種の選択処理は高速に行われることが重要であ
り、そのため、従来より検索項データ及び被検索項デー
タを高速演算処理に適した形態に変換することが種々行
われている。その一つの方法に、項データをハッシュ値
の重ね合せ符号によるインデックスに変換するＳＳＣＷ
（Structural Superimposed Code Word）方式が知られ
ている。（「ＭＰＰＭを用いた知識ベースマシン
（３）」，森田他，情報処理学会第３５回全国大会，２
Ｃ−７、「知識ベースマシンＭu-Ｘ(4)」，沖瀬他，情
報処理学会第３６回全国大会，５Ｅ−７）。以下、この
方式につい説明する。
いま、ある項が再帰的に、 項：＝関数子（項１，項２，…，項ｎ） と定義されているとすると、その項のインデックスは、
第９図に示すように、関数値のハッシュ値のビットフィ
ールドで、項１，項２，…，項ｎのＳＳＣＷによるビッ
トフィールドの並びを覆うように配置して、両者を論理
和演算することにより生成される。両者のビットフィー
ルドの長さは、基本的には関数子のハッシュ値のビット
フィールド長が項１〜項ｎのＳＳＣＷの並びにビットフ
ィールド長よりも長くなるように設定される。
第９図に示すように、関数値のハッシュ値のビットフィ
ールドで、項１，項２，…，項ｎのＳＳＣＷによるビッ
トフィールドの並びを覆うように配置して、両者を論理
和演算することにより生成される。両者のビットフィー
ルドの長さは、基本的には関数子のハッシュ値のビット
フィールド長が項１〜項ｎのＳＳＣＷの並びにビットフ
ィールド長よりも長くなるように設定される。
ここで、例えば第１０図に示す（１）〜（５）の検索対
象項と、（６）の質問項との単一化可能性を検証するに
は、次のような処理が行われる。まず、関数子ａ，ｂ，
ｃ，ｄ，ｅの各ハッシュ値ｈ（ａ），ｈ（ｂ），ｈ
（ｃ），ｈ（ｄ），ｈ（ｅ）が第１１図の（１１）〜
（１５）にそれぞれ示す８ビットの値、定数ｆ，ｇの各
ハッシュ値ｈ（ｆ），ｈ（ｇ）が同図（１６）、（１
７）にそれぞれ示した３ビットの値であるとすると、例
えば（１）で示した項ａ（ｆ，ｇ）のインデックスは、
第１２図（ａ）に示すように、 ｈ（ａ） Ｖ ｈ（ｆ）ｈ（ｇ） ＝“01001010”Ｖ“001100” ＝“01001110” と求められる。同様に、（２）〜（５）の各検索対象項
及び（６）の質問項は第１２図（ｂ）〜（ｅ）及び第１
３図のように求められる。ここで、これら検索対象項及
び質問項のインデックスを求める際、変数Ｘ，Ｙのうち
例えば検索対象項に出現する変数については全ビット
“１”、また質問項に出現する変数については全ビット
“０”のハッシュ値を与える。そして、検索対象項をＤ
（Data）、質問項をＱ（Query）とすると、ＤΛＱ≠Ｑ
を満たすＤを持つ項については、明らかにＱを持つ項と
は単一化可能でないと考えて、単一化を試みないことに
より、検索時間の短縮化を図ることができる。第１０図
の例では、検索対象項（２），（３），（５）が上記の
条件を満たすので、結局、検索対象項（１）のａ（ｆ，
ｇ）と（４）のｄ（Ｘ，Ｙ）が質問項ａ（Ｘ，Ｙ）と単
一化可能な候補として選択される。
象項と、（６）の質問項との単一化可能性を検証するに
は、次のような処理が行われる。まず、関数子ａ，ｂ，
ｃ，ｄ，ｅの各ハッシュ値ｈ（ａ），ｈ（ｂ），ｈ
（ｃ），ｈ（ｄ），ｈ（ｅ）が第１１図の（１１）〜
（１５）にそれぞれ示す８ビットの値、定数ｆ，ｇの各
ハッシュ値ｈ（ｆ），ｈ（ｇ）が同図（１６）、（１
７）にそれぞれ示した３ビットの値であるとすると、例
えば（１）で示した項ａ（ｆ，ｇ）のインデックスは、
第１２図（ａ）に示すように、 ｈ（ａ） Ｖ ｈ（ｆ）ｈ（ｇ） ＝“01001010”Ｖ“001100” ＝“01001110” と求められる。同様に、（２）〜（５）の各検索対象項
及び（６）の質問項は第１２図（ｂ）〜（ｅ）及び第１
３図のように求められる。ここで、これら検索対象項及
び質問項のインデックスを求める際、変数Ｘ，Ｙのうち
例えば検索対象項に出現する変数については全ビット
“１”、また質問項に出現する変数については全ビット
“０”のハッシュ値を与える。そして、検索対象項をＤ
（Data）、質問項をＱ（Query）とすると、ＤΛＱ≠Ｑ
を満たすＤを持つ項については、明らかにＱを持つ項と
は単一化可能でないと考えて、単一化を試みないことに
より、検索時間の短縮化を図ることができる。第１０図
の例では、検索対象項（２），（３），（５）が上記の
条件を満たすので、結局、検索対象項（１）のａ（ｆ，
ｇ）と（４）のｄ（Ｘ，Ｙ）が質問項ａ（Ｘ，Ｙ）と単
一化可能な候補として選択される。
以上の例では、検索対象項に現われる変数を全ビット
“１”のハッシュ値、質問項に現われる変数を全ビット
“０”のハッシュ値としたが、検索対象項に現われる変
数を全ビット“０”のハッシュ値、質問項に現われる変
数を全ビット“１”のハッシュ値とするやり方もある。
第１４図にこの方法で検索対象項のインデックスを求め
た例、第１５図にこの方法で質問項のインデックスを求
めた例を示す。この場合には、検索対象項をＤ、質問項
をＱとすると、ＤΛＱ≠Ｄを満たすＤを持つ項について
は、明らかにＱを持つ項とは単一化可能でないと考え
て、単一化を試みない。第１０図の例では、検索対象項
（３），（５）が上記の条件を満たすので、結局、検索
対象項（１）のａ（ｆ，ｇ）と（２）のｂ（ｆ，ｇ）と
（４）のｄ（Ｘ，Ｙ）が質問項ａ（Ｘ，Ｙ）と単一化可
能な候補として選択される。
“１”のハッシュ値、質問項に現われる変数を全ビット
“０”のハッシュ値としたが、検索対象項に現われる変
数を全ビット“０”のハッシュ値、質問項に現われる変
数を全ビット“１”のハッシュ値とするやり方もある。
第１４図にこの方法で検索対象項のインデックスを求め
た例、第１５図にこの方法で質問項のインデックスを求
めた例を示す。この場合には、検索対象項をＤ、質問項
をＱとすると、ＤΛＱ≠Ｄを満たすＤを持つ項について
は、明らかにＱを持つ項とは単一化可能でないと考え
て、単一化を試みない。第１０図の例では、検索対象項
（３），（５）が上記の条件を満たすので、結局、検索
対象項（１）のａ（ｆ，ｇ）と（２）のｂ（ｆ，ｇ）と
（４）のｄ（Ｘ，Ｙ）が質問項ａ（Ｘ，Ｙ）と単一化可
能な候補として選択される。
以上の例から明らかなように、後者の方法では前者の方
法よりも単一化不可能な項の発見確率が低い。これは、
以下の理由による。即ち、前者の場合には、質問項の変
数のハッシュ値を全て“０”としているので、関数子ａ
のハッシュ値ｈ（ａ）が維持され質問項と各検索対象項
との論理演算に反映される。しかし、後者の場合には、
質問項の変数のハッシュ値を全て“１”としているの
で、関数子ａのハッシュ値ｈ（ａ）は一部分しか現われ
ず質問項と各検索対象項との論理演算にあまり反映され
ないからである。逆に、質問項には変数が含まれず、検
索対象項い多くの変数が含まれている場合には、検索対
象項の側の変数のハッシュ値を全ビット“１”にする
と、単一化不可能な項の発見確率は低下するという問題
がある。
法よりも単一化不可能な項の発見確率が低い。これは、
以下の理由による。即ち、前者の場合には、質問項の変
数のハッシュ値を全て“０”としているので、関数子ａ
のハッシュ値ｈ（ａ）が維持され質問項と各検索対象項
との論理演算に反映される。しかし、後者の場合には、
質問項の変数のハッシュ値を全て“１”としているの
で、関数子ａのハッシュ値ｈ（ａ）は一部分しか現われ
ず質問項と各検索対象項との論理演算にあまり反映され
ないからである。逆に、質問項には変数が含まれず、検
索対象項い多くの変数が含まれている場合には、検索対
象項の側の変数のハッシュ値を全ビット“１”にする
と、単一化不可能な項の発見確率は低下するという問題
がある。
（発明が解決しようとする課題） このように、従来のＳＳＣＷ方式を用いた単一化候補項
の選択方法では、変数のハッシュ値のビットフィールト
を全ビット“１”とした側の項（又は項集合）に変数が
多く含まれていると、単一化不可能な項の発見精度が低
下するという問題点があった。
の選択方法では、変数のハッシュ値のビットフィールト
を全ビット“１”とした側の項（又は項集合）に変数が
多く含まれていると、単一化不可能な項の発見精度が低
下するという問題点があった。
本発明は、上記問題に鑑定みなされたもので、変数の出
現度合いによって単一化不可能な項の発見精度が低下す
るのを防止でき、選択性能に優れた単一化候補項の選択
装置を提供することを目的とする。
現度合いによって単一化不可能な項の発見精度が低下す
るのを防止でき、選択性能に優れた単一化候補項の選択
装置を提供することを目的とする。
［発明の構成］ （課題を解決するための手段） 本願第１の発見は、検索対象となる変数を含む項データ
の集合から項データと単一化可能な候補を選択するため
の単一化候補項の選択装置において、検索対象となる変
数を含む述語論理における少なくとも１つの項からなる
検索対象項集合を記憶する検索対象項記憶手段と、この
検索対象項記憶手段に記憶される検索対象項集合から選
択された検索対象項と質問項との間の単一化可能性を判
定する際に、前記検索対象項集合の変数の出現度合いを
計算する変数出現度合計算手段と、この変数出現度合計
算手段で計算された変数の出現度合いが所定値を越える
検索対象項集合については、変数のハッシュ値として全
ビットに“０”を割当て、変数の出現度合いが所定値を
越えない検索対象項集合については、変数のハッシュ値
として全ビットに“１”を割当て前記検索対象項のイン
デックスを作成する検索対象項インデックス作成手段
と、この検索対象項インデックス作成手段で作成された
検索対象項インデックスを検索対象項と対応付けて記憶
する検索対象項インデックス記憶手段と、検索対象項集
合に対して設けられ、前記検索対象項インデックス作成
手段でのハッシュ値に応じてフラグを設定し記憶するフ
ラグ記憶手段と、質問項を記憶する質問項記憶手段と、
この質問項記憶手段に記憶される質問項に含まれる変数
をフラグ記憶手段に記憶されるフラグに応じて、もしフ
ラグが検索対象項集合の変数のハッシュ値が全ビットに
“１”を割当てられていることを示す場合には質問項の
変数のハッシュ値には全ビットに“０”を割当て、フラ
グが検索対象項集合の変数のハッシュ値が全ビットに
“０”を割当てられていることを示す場合には質問項の
変数のハッシュ値には全ビットに“１”を割当てること
により当該質問項のインデックスを作成する質問項イン
デックス作成手段と、この質問項インデックス作成手段
で作成された質問項インデックスを質問項と対応させて
記憶する質問項インデックス記憶手段と、前記検索対象
項インデックス記憶手段と質問項インデックス記憶手段
にそれぞれ記憶される検索対象項インデックスと質問項
インデックスとの論理積を求め、この論理積が検索対象
項又は質問項と異なる場合は単一化可能ではないとみな
すことによって単一化候補項を選択する選択手段とを具
備することを特徴としている。
の集合から項データと単一化可能な候補を選択するため
の単一化候補項の選択装置において、検索対象となる変
数を含む述語論理における少なくとも１つの項からなる
検索対象項集合を記憶する検索対象項記憶手段と、この
検索対象項記憶手段に記憶される検索対象項集合から選
択された検索対象項と質問項との間の単一化可能性を判
定する際に、前記検索対象項集合の変数の出現度合いを
計算する変数出現度合計算手段と、この変数出現度合計
算手段で計算された変数の出現度合いが所定値を越える
検索対象項集合については、変数のハッシュ値として全
ビットに“０”を割当て、変数の出現度合いが所定値を
越えない検索対象項集合については、変数のハッシュ値
として全ビットに“１”を割当て前記検索対象項のイン
デックスを作成する検索対象項インデックス作成手段
と、この検索対象項インデックス作成手段で作成された
検索対象項インデックスを検索対象項と対応付けて記憶
する検索対象項インデックス記憶手段と、検索対象項集
合に対して設けられ、前記検索対象項インデックス作成
手段でのハッシュ値に応じてフラグを設定し記憶するフ
ラグ記憶手段と、質問項を記憶する質問項記憶手段と、
この質問項記憶手段に記憶される質問項に含まれる変数
をフラグ記憶手段に記憶されるフラグに応じて、もしフ
ラグが検索対象項集合の変数のハッシュ値が全ビットに
“１”を割当てられていることを示す場合には質問項の
変数のハッシュ値には全ビットに“０”を割当て、フラ
グが検索対象項集合の変数のハッシュ値が全ビットに
“０”を割当てられていることを示す場合には質問項の
変数のハッシュ値には全ビットに“１”を割当てること
により当該質問項のインデックスを作成する質問項イン
デックス作成手段と、この質問項インデックス作成手段
で作成された質問項インデックスを質問項と対応させて
記憶する質問項インデックス記憶手段と、前記検索対象
項インデックス記憶手段と質問項インデックス記憶手段
にそれぞれ記憶される検索対象項インデックスと質問項
インデックスとの論理積を求め、この論理積が検索対象
項又は質問項と異なる場合は単一化可能ではないとみな
すことによって単一化候補項を選択する選択手段とを具
備することを特徴としている。
また本願第２の発明は、検索対象となる変数を含む項デ
ータの集合から項データと単一化可能な候補を選択する
ための単一化候補項の選択装置において、検索対象とな
る変数を含む述語論理における少なくとも１つの項から
なる検索対象項集合を記憶する検索対象項記憶手段と、
質問項を記憶する質問項記憶手段と、前記検索対象項記
憶手段に記憶される検索対象項と質問項記憶手段に記憶
される質問項との間の単一化可能性を判定する際に、前
記検索対象項に含まれる変数のハッシュ値として全ビッ
トに“０”を割当てた第１のインデックスと、全ビット
に“１”を割当てた第２のインデックスとを作成する検
索対象項インデックス作成手段と、検索対象項インデッ
クス作成手段で作成された第１のインデックスと第２の
インデックスとを検索対象項と対応付けて記憶する検索
対象項インデックス記憶手段と、前記質問項に含まれる
変数のハッシュ値として全ビットに“０”を割当てた第
１のインデックスと、全ビットに“１”を割当てた第２
のインデックスとをそれぞれ作成する質問項インデック
ス作成手段と、この質問項インデックス作成手段で作成
された第１のインデックスと第２のインデックスを質問
項と対応させて記憶する質問項インデックス記憶手段
と、前記検索対象項インデックス記憶手段と質問項イン
デックス記憶手段に記憶される検索対象項の第１のイン
デックスと質問項の第２のインデックスとの論理演算に
よって選択される項と、検索対象項の第２のインデック
スと質問項の第１のインデックスとの論理演算によって
選択される項との共通項を単一化候補項として選択する
選択手段と、この選択手段で選択された項の共通項を抽
出する共通項抽出手段とを具備することを特徴としてい
る。
ータの集合から項データと単一化可能な候補を選択する
ための単一化候補項の選択装置において、検索対象とな
る変数を含む述語論理における少なくとも１つの項から
なる検索対象項集合を記憶する検索対象項記憶手段と、
質問項を記憶する質問項記憶手段と、前記検索対象項記
憶手段に記憶される検索対象項と質問項記憶手段に記憶
される質問項との間の単一化可能性を判定する際に、前
記検索対象項に含まれる変数のハッシュ値として全ビッ
トに“０”を割当てた第１のインデックスと、全ビット
に“１”を割当てた第２のインデックスとを作成する検
索対象項インデックス作成手段と、検索対象項インデッ
クス作成手段で作成された第１のインデックスと第２の
インデックスとを検索対象項と対応付けて記憶する検索
対象項インデックス記憶手段と、前記質問項に含まれる
変数のハッシュ値として全ビットに“０”を割当てた第
１のインデックスと、全ビットに“１”を割当てた第２
のインデックスとをそれぞれ作成する質問項インデック
ス作成手段と、この質問項インデックス作成手段で作成
された第１のインデックスと第２のインデックスを質問
項と対応させて記憶する質問項インデックス記憶手段
と、前記検索対象項インデックス記憶手段と質問項イン
デックス記憶手段に記憶される検索対象項の第１のイン
デックスと質問項の第２のインデックスとの論理演算に
よって選択される項と、検索対象項の第２のインデック
スと質問項の第１のインデックスとの論理演算によって
選択される項との共通項を単一化候補項として選択する
選択手段と、この選択手段で選択された項の共通項を抽
出する共通項抽出手段とを具備することを特徴としてい
る。
（作用） 本発明によれば、第１の項集合と第２の項集合のうち変
数の出現度合いの大きな項集合に含まれる変数のハッシ
ュ値として全ビット“０”を割当て、他の項集合中の変
数のハッシュ値として全ビットに“１”を割当てるよう
にしているので、変数の部分に“１”が割当てられるこ
とに起因する関数子や他の項のハッシュ値の内容の喪失
は、変数があまり含まれていない方の項集合にのみ起こ
る。このため、多くの変数部分については本来のハッシ
ュ値の内容、即ち意味のある内容が残り、高い検出精度
が維持されることになる。
数の出現度合いの大きな項集合に含まれる変数のハッシ
ュ値として全ビット“０”を割当て、他の項集合中の変
数のハッシュ値として全ビットに“１”を割当てるよう
にしているので、変数の部分に“１”が割当てられるこ
とに起因する関数子や他の項のハッシュ値の内容の喪失
は、変数があまり含まれていない方の項集合にのみ起こ
る。このため、多くの変数部分については本来のハッシ
ュ値の内容、即ち意味のある内容が残り、高い検出精度
が維持されることになる。
また、本発明の２種類の方法で選択された項の共通項を
抽出することにより、単一化可能性の確度の高い項のみ
が選択され、両項集合の変数の割合いに拘らず、更に精
度の良い単一化候補項の選択が可能である。
抽出することにより、単一化可能性の確度の高い項のみ
が選択され、両項集合の変数の割合いに拘らず、更に精
度の良い単一化候補項の選択が可能である。
（実施例） 以下、図面を参照しながら本発明の実施例について説明
する。
する。
第１図は本発明の第１の実施例に係る単一化検索システ
ムの構成を示すブロック図である。この実施例では、検
索対象項集合における変数の出現度合いが所定の値以上
のときには検索対象項の変数に全ビット“０”を割当
て、所定の値よりも小さいときには全ビット“１”を割
当てるようにしたものである。
ムの構成を示すブロック図である。この実施例では、検
索対象項集合における変数の出現度合いが所定の値以上
のときには検索対象項の変数に全ビット“０”を割当
て、所定の値よりも小さいときには全ビット“１”を割
当てるようにしたものである。
検索対象項記憶手段１０１は検索対象項の集合を記憶す
る。変数出現度合い計算手段１０２は、上記記憶手段１
０１に記憶されている検索対象項集合から変数の出現度
合いを、例えば、 変数記号／（変数記号＋定数記号） なる式によって計算し、その結果をＳＳＣＷ作成手段１
０３に出力する。第１０図に示した例では、変数の出現
度合いが（２／１５）×１００＝１３％と計算される。
ＳＳＣＷ作成手段１０３は、変数の出現度合いが所定の
値、例えば５０％以上であるかどうかを判定し、５０％
以上である場合には変数の部分に“０”を割当て、５０
％未満である場合には変数の部分に“１”を割当て、各
検索対象項のＳＳＣＷによるインデックスを作成する。
ＳＳＣＷ作成手段１０３で作成されたインデックスは、
各検索対象項と対応付けられて検索対象項・インデック
ス記憶手段１０４に格納される。また、この記憶手段１
０４には、ＳＳＣＷ作成手段１０３での判定結果、つま
り変数の出現度合いが５０％以上である場合には例えば
“１”、５０％未満である場合には例えば“０”となる
フラグ１０４ａを記憶する。一方、質問項は質問項記憶
手段１０５に格納されている。この質問項は、ＳＳＣＷ
作成手段１０６においてＳＳＣＷのインデックスに変換
される。このとき、変数の部分を全ビット“０”にする
か、“１”にするかは検索対象項・インデックス記憶手
段１０４に記憶されているフラグ１０４ａの値によって
決定される。検索対象項の変数を“１”にした場合に
は、質問項の変数は“０”、検索対象項の変数を“０”
にした場合には、質問項の変数は“１”となる。ＳＳＣ
Ｗ作成手段１０６で作成された質問項のインデックス
は、質問項・インデックス記憶手段１０７に質問項と対
応付けられて格納される。
る。変数出現度合い計算手段１０２は、上記記憶手段１
０１に記憶されている検索対象項集合から変数の出現度
合いを、例えば、 変数記号／（変数記号＋定数記号） なる式によって計算し、その結果をＳＳＣＷ作成手段１
０３に出力する。第１０図に示した例では、変数の出現
度合いが（２／１５）×１００＝１３％と計算される。
ＳＳＣＷ作成手段１０３は、変数の出現度合いが所定の
値、例えば５０％以上であるかどうかを判定し、５０％
以上である場合には変数の部分に“０”を割当て、５０
％未満である場合には変数の部分に“１”を割当て、各
検索対象項のＳＳＣＷによるインデックスを作成する。
ＳＳＣＷ作成手段１０３で作成されたインデックスは、
各検索対象項と対応付けられて検索対象項・インデック
ス記憶手段１０４に格納される。また、この記憶手段１
０４には、ＳＳＣＷ作成手段１０３での判定結果、つま
り変数の出現度合いが５０％以上である場合には例えば
“１”、５０％未満である場合には例えば“０”となる
フラグ１０４ａを記憶する。一方、質問項は質問項記憶
手段１０５に格納されている。この質問項は、ＳＳＣＷ
作成手段１０６においてＳＳＣＷのインデックスに変換
される。このとき、変数の部分を全ビット“０”にする
か、“１”にするかは検索対象項・インデックス記憶手
段１０４に記憶されているフラグ１０４ａの値によって
決定される。検索対象項の変数を“１”にした場合に
は、質問項の変数は“０”、検索対象項の変数を“０”
にした場合には、質問項の変数は“１”となる。ＳＳＣ
Ｗ作成手段１０６で作成された質問項のインデックス
は、質問項・インデックス記憶手段１０７に質問項と対
応付けられて格納される。
以上のようにして求められた各検索対象項と質問項の各
インデックスは、単一化可能候補選択手段１０８におい
て前述したＤΛＱ≠Ｑ（又はＤΛＱ≠Ｄ）の条件式に基
づき判定され、単一化候補項が選択される。そして、選
択された単一化候補項は、更に単一化検索手段１０９で
検索され、最終的な検索結果が求められる。この検索結
果は検索結果記憶手段１１０に格納される。
インデックスは、単一化可能候補選択手段１０８におい
て前述したＤΛＱ≠Ｑ（又はＤΛＱ≠Ｄ）の条件式に基
づき判定され、単一化候補項が選択される。そして、選
択された単一化候補項は、更に単一化検索手段１０９で
検索され、最終的な検索結果が求められる。この検索結
果は検索結果記憶手段１１０に格納される。
このように、本実施例によれば、検索対象項集合に含ま
れる変数の度合いによって検索対象項中の変数のビット
を“０”又は“１”にしているので、検索対象項の変数
を無条件に“０”又は“１”にする方法に比べ、格段に
選択性能が向上する。
れる変数の度合いによって検索対象項中の変数のビット
を“０”又は“１”にしているので、検索対象項の変数
を無条件に“０”又は“１”にする方法に比べ、格段に
選択性能が向上する。
第２図は本発明の第２の実施例に係る単一化検索システ
ムの構成を示す図である。この実施例は、検索対象項の
インデックスとして変数部分に全ビット“０”を割当て
た第１のインデックスと変数部分に全ビット“１”を割
当てた第２のインデックスとを用意しておき、検索対象
項集合内の変数出現度合いと質問項内の変数出現度合い
とを比較してその大小によって第１及び第２のインデッ
クスのうちのどちらを採用するかを決定するようにした
ものである。
ムの構成を示す図である。この実施例は、検索対象項の
インデックスとして変数部分に全ビット“０”を割当て
た第１のインデックスと変数部分に全ビット“１”を割
当てた第２のインデックスとを用意しておき、検索対象
項集合内の変数出現度合いと質問項内の変数出現度合い
とを比較してその大小によって第１及び第２のインデッ
クスのうちのどちらを採用するかを決定するようにした
ものである。
検索対象項記憶手段２０１に記憶された検索対象項集合
に含まれる変数の出現度合いは、変数出現度合い計算手
段２０２で計算され、その結果は、検索対象項・インデ
ックス記憶手段２０４の変数度合いフィールド２０４ａ
に格納される。ＳＳＣＷ作成手段２０３は、検索対象項
の変数部分を“０”に割当てた第１のインデックスＩＤ
Ｘ０１，ＩＤＸ０２，…と、変数部分に、“１”を割当
てた第２のインデックスＩＤＸ１１，ＩＤＸ１２，…を
それぞれ作成し、検索対象項・インデックス記憶手段２
０４に格納する。一方、質問項記憶手段２０５に格納さ
れた質問項に含まれる変数の出現度合いは変数出現度合
い計算手段２０６で計算され、ＳＳＣＷ作成手段２０７
において変数度合いフィールド２０４ａに格納された検
索対象項の変数度合いと比較される。ＳＳＣＷ作成手段
２０７は（検索対象項の変数度合い≧質問項の変数度合
い）の場合には、変数部分に“１”を割当てて質問項の
インデックスが作成され、（検索対象項の変数度合い＜
質問項の変数度合い）の場合には、変数部分に“０”を
割当てて質問項のインデックスが作成される。第１０図
の例の場合には、検索対象項の変数度合いが（２／１
５）×１００＝１３％、質問項の変数度合いが（２／
３）×１００＝６７％であるから、質問項の変数に
“０”が割当てられる。こうして作成された質問項のイ
ンデックスは質問項と対応させて質問項・インデックス
記憶手段２０８に格納される。単一化可能候補選択手段
２０９は、質問項の変数部分に“０”が割当てられたか
“１”が割当てられたかに応じて第１及び第２のインデ
ックスのうちのいずれかが選択されて単一化可能の判定
処理が行われる。以後の単一化検索手段２１０及び検索
結果記憶手段２１１の機能は前述した実施例と同様であ
る。
に含まれる変数の出現度合いは、変数出現度合い計算手
段２０２で計算され、その結果は、検索対象項・インデ
ックス記憶手段２０４の変数度合いフィールド２０４ａ
に格納される。ＳＳＣＷ作成手段２０３は、検索対象項
の変数部分を“０”に割当てた第１のインデックスＩＤ
Ｘ０１，ＩＤＸ０２，…と、変数部分に、“１”を割当
てた第２のインデックスＩＤＸ１１，ＩＤＸ１２，…を
それぞれ作成し、検索対象項・インデックス記憶手段２
０４に格納する。一方、質問項記憶手段２０５に格納さ
れた質問項に含まれる変数の出現度合いは変数出現度合
い計算手段２０６で計算され、ＳＳＣＷ作成手段２０７
において変数度合いフィールド２０４ａに格納された検
索対象項の変数度合いと比較される。ＳＳＣＷ作成手段
２０７は（検索対象項の変数度合い≧質問項の変数度合
い）の場合には、変数部分に“１”を割当てて質問項の
インデックスが作成され、（検索対象項の変数度合い＜
質問項の変数度合い）の場合には、変数部分に“０”を
割当てて質問項のインデックスが作成される。第１０図
の例の場合には、検索対象項の変数度合いが（２／１
５）×１００＝１３％、質問項の変数度合いが（２／
３）×１００＝６７％であるから、質問項の変数に
“０”が割当てられる。こうして作成された質問項のイ
ンデックスは質問項と対応させて質問項・インデックス
記憶手段２０８に格納される。単一化可能候補選択手段
２０９は、質問項の変数部分に“０”が割当てられたか
“１”が割当てられたかに応じて第１及び第２のインデ
ックスのうちのいずれかが選択されて単一化可能の判定
処理が行われる。以後の単一化検索手段２１０及び検索
結果記憶手段２１１の機能は前述した実施例と同様であ
る。
この実施例によれば、検索対象項のみならず質問項の変
数度合いも考慮に入れたより精度の高い選択処理を行な
うことができる。
数度合いも考慮に入れたより精度の高い選択処理を行な
うことができる。
第３図は本発明の第３の実施例に係る単一化検索システ
ムの構成を示す図である。この実施例は、検索対象項、
質問項共に変数部分にそれぞれ“０”、“１”を割当て
た２種類のインデックスを用意し、両インデックスでそ
れぞれ求められた単一化候補項の共通項を抽出してこれ
を単一化候補項とするようにしたものである。
ムの構成を示す図である。この実施例は、検索対象項、
質問項共に変数部分にそれぞれ“０”、“１”を割当て
た２種類のインデックスを用意し、両インデックスでそ
れぞれ求められた単一化候補項の共通項を抽出してこれ
を単一化候補項とするようにしたものである。
検索対象項記憶手段３０１に格納された検索対象項の２
種類のインデックスはＳＳＣＷ作成手段３０２で作成さ
れ、検索対象項・インデックス記憶手段３０３に格納さ
れる。一方、質問項記憶手段３０４に格納された質問項
の２種類のインデックスはＳＳＣＷ作成手段３０５で作
成され、質問項・インデックス記憶手段３０６に格納さ
れる。これら記憶手段３０３，３０６に格納されたイン
デックスのうち、ＩＤＸ０１，ＩＤＸ０２，…とＩＤＸ
１とが単一化可能候補選択手段３０７で判定処理され、
ＩＤＸ１１，ＩＤＸ１２，…とＩＤＸ０とが単一化可能
候補選択手段３０８で判定処理される。両選択手段３０
７，３０８で求められた項は、共通項抽出手段３０９に
より例えばＡＮＤ処理されて共通項が抽出される。単一
化検索手段３１０、検索結果記憶手段３１１の機能は前
述した実施例と同様である。
種類のインデックスはＳＳＣＷ作成手段３０２で作成さ
れ、検索対象項・インデックス記憶手段３０３に格納さ
れる。一方、質問項記憶手段３０４に格納された質問項
の２種類のインデックスはＳＳＣＷ作成手段３０５で作
成され、質問項・インデックス記憶手段３０６に格納さ
れる。これら記憶手段３０３，３０６に格納されたイン
デックスのうち、ＩＤＸ０１，ＩＤＸ０２，…とＩＤＸ
１とが単一化可能候補選択手段３０７で判定処理され、
ＩＤＸ１１，ＩＤＸ１２，…とＩＤＸ０とが単一化可能
候補選択手段３０８で判定処理される。両選択手段３０
７，３０８で求められた項は、共通項抽出手段３０９に
より例えばＡＮＤ処理されて共通項が抽出される。単一
化検索手段３１０、検索結果記憶手段３１１の機能は前
述した実施例と同様である。
この実施例によれば、２種類の方法で選択された項のう
ち共通な項を抽出することにより、実質的に精度の高い
方の方法により選択された項が単一化可能候補として抽
出されることになる。
ち共通な項を抽出することにより、実質的に精度の高い
方の方法により選択された項が単一化可能候補として抽
出されることになる。
第４図は本発明の第４の実施例に係る単一化を含むｊｏ
ｉｎを行なうシステムの構成を示す図である。
ｉｎを行なうシステムの構成を示す図である。
単一化を含むｊｏｉｎの対象となる項集合Ａと項集合Ｂ
とは、それぞれ項集合Ａ記憶手段４０１と項集合Ｂ記憶
手段４０５に格納されている。項集合Ａ，Ｂは、それぞ
れ変数出現度合い計算手段４０２，４０６において、そ
の変数度合いが計算され、それぞれＳＳＣＷ作成手段４
０３，４０７で２種類のインデックスが作成される。求
められた各インデックスは各項と対応させて項集合Ａ・
インデックス記憶手段４０４，項集合Ｂ・インデックス
記憶手段４０８にそれぞれ格納される。また各記憶手段
４０４，４０８には、変数度合いフィールド４０４ａ，
４０８ａが設けられており、ここに変数出現度合い計算
手段４０２，４０６で求められた変数度合いが格納され
る。組合わせ選択手段４０９は、各変数度合いフィール
ド４０４ａ，４０８ａに格納された変数度合いの大小に
基づき、各項集合Ａ，Ｂのインデックスを選択する。単
一化可能候補選択手段４１０は、組合わせ選択手段４０
９で選択されたインデックスの組合わせに基づいて単一
化可能候補を選択する。これにより、単一化、ｊｏｉｎ
処理手段４１１は、項集合Ａと項集合Ｂの単一化を含む
ｊｏｉｎを行なう。その結果は、単一化・ｊｏｉｎ結果
記憶手段４１２に格納される。
とは、それぞれ項集合Ａ記憶手段４０１と項集合Ｂ記憶
手段４０５に格納されている。項集合Ａ，Ｂは、それぞ
れ変数出現度合い計算手段４０２，４０６において、そ
の変数度合いが計算され、それぞれＳＳＣＷ作成手段４
０３，４０７で２種類のインデックスが作成される。求
められた各インデックスは各項と対応させて項集合Ａ・
インデックス記憶手段４０４，項集合Ｂ・インデックス
記憶手段４０８にそれぞれ格納される。また各記憶手段
４０４，４０８には、変数度合いフィールド４０４ａ，
４０８ａが設けられており、ここに変数出現度合い計算
手段４０２，４０６で求められた変数度合いが格納され
る。組合わせ選択手段４０９は、各変数度合いフィール
ド４０４ａ，４０８ａに格納された変数度合いの大小に
基づき、各項集合Ａ，Ｂのインデックスを選択する。単
一化可能候補選択手段４１０は、組合わせ選択手段４０
９で選択されたインデックスの組合わせに基づいて単一
化可能候補を選択する。これにより、単一化、ｊｏｉｎ
処理手段４１１は、項集合Ａと項集合Ｂの単一化を含む
ｊｏｉｎを行なう。その結果は、単一化・ｊｏｉｎ結果
記憶手段４１２に格納される。
この実施例によれば、例えば項集合Ａが第１０図に示し
た（１）〜（５）の項、項集合Ｂが第６図（２１）〜
（２５）の項からなるとすると、項集合Ａの変数度合い
は１３％、項集合Ｂの変数度合いは（８／１５）×１０
０＝５３％であるから、項集合Ａの変数に第１２図に示
すように、“１”、項集合Ｂの変数に第７図に示すよう
に“０”が割当てされる。この結果、項集合Ａと項集合
Ｂの単一化可能なペアとして、（１）（２１）、（１）
（２４）、（２）（２２）、（２）（２４）、（３）
（２２）、（３）（２３）、（３）（２４）、（３）
（２５）、（４）（２１）、（４）（２２）、（４）
（２４）、（５）（２５）の１２組が選択される。ちな
みに、項集合Ａの変数に第１４図に示すように“０”、
項集合Ｂの変数に第８図に示すように“１”が割当てる
と、項集合Ａと項集合Ｂの単一化可能なペアとして、
（１）（２１）、（１）（２２）、（１）（２３）、
（２）（２１）、（２）（２２）、（２）（２３）、
（２）（２４）、（３）（２３）、（４）（２１）、
（４）（２２）、（４）（２３）、（４）（２４）、
（５）（２３）、（５）（２５）の１４組が選択され、
前者の方がより選択精度が高いことが明らかである。
た（１）〜（５）の項、項集合Ｂが第６図（２１）〜
（２５）の項からなるとすると、項集合Ａの変数度合い
は１３％、項集合Ｂの変数度合いは（８／１５）×１０
０＝５３％であるから、項集合Ａの変数に第１２図に示
すように、“１”、項集合Ｂの変数に第７図に示すよう
に“０”が割当てされる。この結果、項集合Ａと項集合
Ｂの単一化可能なペアとして、（１）（２１）、（１）
（２４）、（２）（２２）、（２）（２４）、（３）
（２２）、（３）（２３）、（３）（２４）、（３）
（２５）、（４）（２１）、（４）（２２）、（４）
（２４）、（５）（２５）の１２組が選択される。ちな
みに、項集合Ａの変数に第１４図に示すように“０”、
項集合Ｂの変数に第８図に示すように“１”が割当てる
と、項集合Ａと項集合Ｂの単一化可能なペアとして、
（１）（２１）、（１）（２２）、（１）（２３）、
（２）（２１）、（２）（２２）、（２）（２３）、
（２）（２４）、（３）（２３）、（４）（２１）、
（４）（２２）、（４）（２３）、（４）（２４）、
（５）（２３）、（５）（２５）の１４組が選択され、
前者の方がより選択精度が高いことが明らかである。
第５図は本発明の第５の実施例を示す図である。この実
施例は、上述した単一化を含むｊｏｉｎを第３の実施例
と同様にして行なった例である。
施例は、上述した単一化を含むｊｏｉｎを第３の実施例
と同様にして行なった例である。
項集合Ａ記憶手段５０１に格納された項集合Ａの２種類
のインデックスはＳＳＣＷ作成手段５０２で作成され、
項集合Ａ・インデックス記憶手段５０３に格納される。
また、項集合Ｂ記憶手段５０４に格納された項集合Ｂの
２種類のインデックスはＳＳＣＷ作成手段５０５で作成
され、項集合Ｂ・インデックス記憶手段５０６に格納さ
れる。これら記憶手段５０３，５０６に格納されたイン
デックスのうち、ＩＤＸ０１，ＩＤＸ０２，…とＩＤＸ
１Ｉ，ＩＤＸ１II，…とが単一化可能候補選択手段５０
７で判定処理され、ＩＤＸ１１，ＩＤＸ１２，…とＩＤ
Ｘ０Ｉ，ＩＤＸ０II，…とが単一化可能候補選択手段５
０８で判定処理される。両選択手段５０７，５０８で求
められた項は、共通項抽出手段５０９により例えばＡＮ
Ｄ処理されて共通項が抽出される。単一化・ｊｏｉｎ処
理手段５１０、単一化・ｊｏｉｎ処理結果記憶手段５１
１の機能は前述した実施例と同様である。
のインデックスはＳＳＣＷ作成手段５０２で作成され、
項集合Ａ・インデックス記憶手段５０３に格納される。
また、項集合Ｂ記憶手段５０４に格納された項集合Ｂの
２種類のインデックスはＳＳＣＷ作成手段５０５で作成
され、項集合Ｂ・インデックス記憶手段５０６に格納さ
れる。これら記憶手段５０３，５０６に格納されたイン
デックスのうち、ＩＤＸ０１，ＩＤＸ０２，…とＩＤＸ
１Ｉ，ＩＤＸ１II，…とが単一化可能候補選択手段５０
７で判定処理され、ＩＤＸ１１，ＩＤＸ１２，…とＩＤ
Ｘ０Ｉ，ＩＤＸ０II，…とが単一化可能候補選択手段５
０８で判定処理される。両選択手段５０７，５０８で求
められた項は、共通項抽出手段５０９により例えばＡＮ
Ｄ処理されて共通項が抽出される。単一化・ｊｏｉｎ処
理手段５１０、単一化・ｊｏｉｎ処理結果記憶手段５１
１の機能は前述した実施例と同様である。
この実施例によれば、前述した１２組の項と１４組の項
の共通項が抽出され、最終的には（１）（２１）、
（２）（２２）、（２）（２４）、（３）（２３）、
（４）（２１）、（４）（２２）、（４）（２４）、
（５）（５）の８組の共通項が抽出される。このよう
に、この実施例によれば更に精度の高い選択処理を行な
うことができる。
の共通項が抽出され、最終的には（１）（２１）、
（２）（２２）、（２）（２４）、（３）（２３）、
（４）（２１）、（４）（２２）、（４）（２４）、
（５）（５）の８組の共通項が抽出される。このよう
に、この実施例によれば更に精度の高い選択処理を行な
うことができる。
［発明の効果］ このように本発明によれば、第１の項集合と第２の項集
合のうち変数の出現度合いの大きな項集合に含まれる変
数のハッシュ値として全ビット“０”を割当て、他の項
集合中の変数のハッシュ値として全ビットに“１”を割
当てるようにしているので、多くの変数部分については
本来のハッシュ値の内容、即ち意味のある内容が残り、
高い検出精度が維持されることになる。
合のうち変数の出現度合いの大きな項集合に含まれる変
数のハッシュ値として全ビット“０”を割当て、他の項
集合中の変数のハッシュ値として全ビットに“１”を割
当てるようにしているので、多くの変数部分については
本来のハッシュ値の内容、即ち意味のある内容が残り、
高い検出精度が維持されることになる。
また、変数のハッシュ値として“０”を割当てたインデ
ックスと“１”を割当てたインデックスの２種類のイン
デックスを用いた方法によりそれぞれ抽出された２種類
の選択項集合の共通集合を単一化可能な項として選択す
るので、単一化の確度の高い項のみが選択されることに
なる。
ックスと“１”を割当てたインデックスの２種類のイン
デックスを用いた方法によりそれぞれ抽出された２種類
の選択項集合の共通集合を単一化可能な項として選択す
るので、単一化の確度の高い項のみが選択されることに
なる。
このため、本発明によれば変数の出現度合いによって単
一化不可能な項の発見精度が低下するのを防止でき、選
択性能に優れた単一化候補項の選択装置を提供すること
ができる。
一化不可能な項の発見精度が低下するのを防止でき、選
択性能に優れた単一化候補項の選択装置を提供すること
ができる。
第１図は本発明の第１の実施例に係る単一化候補項の選
択装置のブロック図、第２図は本発明の第２の実施例に
係る単一化候補項の選択装置のブロック図、第３図は本
発明の第３の実施例に係る単一化候補項の選択装置のブ
ロック図、第４図は本発明の第４の実施例に係る単一化
候補項の選択装置のブロック図、第５図は本発明の第５
の実施例に係る単一化候補項の選択装置のブロック図、
第６図乃至第８図は上記第４の実施例の選択装置の作用
を説明する為の図、第９図乃至第１５図はＳＳＣＷ方式
を説明するための図である。 １０１，２０１，３０１……検索対象項記憶手段、１０
２，２０２，２０６，４０２，４０６……変数出現度合
い計算手段、１０３，１０６，２０３，２０７，３０
２，３０５，４０３，４０７，５０２，５０５……ＳＳ
ＣＷ作成手段、１０４，２０４，３０３……検索対象項
・インデックス記憶手段、１０５，２０５，３０４……
質問項記憶手段、１０７，２０８，３０６……質問項・
インデックス記憶手段、１０８，２０９，３０７，３０
８，４１０，５０７，５０８……単一化可能候補選択手
段、１０９，２１０，３１０……単一化検索手段、１１
０，２１１，３１１……検索結果記憶手段、３０９，５
０９……共通項抽出手段、４０１，５０１……項集合Ａ
記憶手段、４０４，５０３……項集合Ａ・インデックス
記憶手段、４０５，５０４……項集合Ｂ記憶手段、４０
８，５０６……項集合Ｂ・インデックス記憶手段、４１
１，５１０……単一化・ｊｏｉｎ処理手段、４１２，５
１１……単一化・ｊｏｉｎ結果処理手段。
択装置のブロック図、第２図は本発明の第２の実施例に
係る単一化候補項の選択装置のブロック図、第３図は本
発明の第３の実施例に係る単一化候補項の選択装置のブ
ロック図、第４図は本発明の第４の実施例に係る単一化
候補項の選択装置のブロック図、第５図は本発明の第５
の実施例に係る単一化候補項の選択装置のブロック図、
第６図乃至第８図は上記第４の実施例の選択装置の作用
を説明する為の図、第９図乃至第１５図はＳＳＣＷ方式
を説明するための図である。 １０１，２０１，３０１……検索対象項記憶手段、１０
２，２０２，２０６，４０２，４０６……変数出現度合
い計算手段、１０３，１０６，２０３，２０７，３０
２，３０５，４０３，４０７，５０２，５０５……ＳＳ
ＣＷ作成手段、１０４，２０４，３０３……検索対象項
・インデックス記憶手段、１０５，２０５，３０４……
質問項記憶手段、１０７，２０８，３０６……質問項・
インデックス記憶手段、１０８，２０９，３０７，３０
８，４１０，５０７，５０８……単一化可能候補選択手
段、１０９，２１０，３１０……単一化検索手段、１１
０，２１１，３１１……検索結果記憶手段、３０９，５
０９……共通項抽出手段、４０１，５０１……項集合Ａ
記憶手段、４０４，５０３……項集合Ａ・インデックス
記憶手段、４０５，５０４……項集合Ｂ記憶手段、４０
８，５０６……項集合Ｂ・インデックス記憶手段、４１
１，５１０……単一化・ｊｏｉｎ処理手段、４１２，５
１１……単一化・ｊｏｉｎ結果処理手段。
Claims (2)
- 【請求項１】検索対象となる変数を含む項データの集合
から項データと単一化可能な候補を選択するための単一
化候補項の選択装置において、 検索対象となる変数を含む述語論理における少なくとも
１つの項からなる検索対象項集合を記憶する検索対象項
記憶手段と、 この検索対象項記憶手段に記憶される検索対象項集合か
ら選択された検索対象項と質問項との間の単一化可能性
を判定する際に、前記検索対象項集合の変数の出現度合
いを計算する変数出現度合計算手段と、 この変数出現度合計算手段で計算された変数の出現度合
いが所定値を越える検索対象項集合については、変数の
ハッシュ値として全ビットに“０”を割当て、変数の出
現度合いが所定値を越えない検索対象項集合について
は、変数のハッシュ値として全ビットに“１”を割当て
前記検索対象項のインデックスを作成する検索対象項イ
ンデックス作成手段と、 この検索対象項インデックス作成手段で作成された検索
対象項インデックスを検索対象項と対応付けて記憶する
検索対象項インデックス記憶手段と、 検索対象項集合に対して設けられ、前記検索対象項イン
デックス作成手段でのハッシュ値に応じてフラグを設定
し記憶するフラグ記憶手段と、 質問項を記憶する質問項記憶手段と、 この質問項記憶手段に記憶される質問項に含まれる変数
をフラグ記憶手段に記憶されるフラグに応じて、もしフ
ラグが検索対象項集合の変数のハッシュ値が全ビットに
“１”を割当てられていることを示す場合には質問項の
変数のハッシュ値には全ビットに“０”を割当て、フラ
グが検索対象項集合の変数のハッシュ値が全ビットに
“０”を割当てられていることを示す場合には質問項の
変数のハッシュ値には全ビットに“１”を割当てること
により当該質問項のインデックスを作成する質問項イン
デックス作成手段と、 この質問項インデックス作成手段で作成された質問項イ
ンデックスを質問項と対応させて記憶する質問項インデ
ックス記憶手段と、 前記検索対象項インデックス記憶手段と質問項インデッ
クス記憶手段にそれぞれ記憶される検索対象項インデッ
クスと質問項インデックスとの論理積を求め、この論理
積が検索対象項又は質問項と異なる場合は単一化可能で
はないとみなすことによって単一化候補項を選択する選
択手段と、 を具備することを特徴とする単一化候補項の選択装置。 - 【請求項２】検索対象となる変数を含む項データの集合
から項データと単一化可能な候補を選択するための単一
化候補項の選択装置において、 検索対象となる変数を含む述語論理における少なくとも
１つの項からなる検索対象項集合を記憶する検索対象項
記憶手段と、 質問項を記憶する質問項記憶手段と、 前記検索対象項記憶手段に記憶される検索対象項と質問
項記憶手段に記憶される質問項との間の単一化可能性を
判定する際に、前記検索対象項に含まれる変数のハッシ
ュ値として全ビットに“０”を割当てた第１のインデッ
クスと、全ビットに“１”を割当てた第２のインデック
スとを作成する検索対象項インデックス作成手段と、 検索対象項インデックス作成手段で作成された第１のイ
ンデックスと第２のインデックスとを検索対象項と対応
付けて記憶する検索対象項インデックス記憶手段と、 前記質問項に含まれる変数のハッシュ値として全ビット
に“０”を割当てた第１のインデックスと、全ビットに
“１”を割当てた第２のインデックスとをそれぞれ作成
する質問項インデックス作成手段と、 この質問項インデックス作成手段で作成された第１のイ
ンデックスと第２のインデックスを質問項と対応させて
記憶する質問項インデックス記憶手段と、 前記検索対象項インデックス記憶手段と質問項インデッ
クス記憶手段に記憶される検索対象項の第１のインデッ
クスと質問項の第２のインデックスとの論理演算によっ
て選択される項と、検索対象項の第２のインデックスと
質問項の第１のインデックスとの論理演算によって選択
される項との共通項を単一化候補項として選択する選択
手段と、 この選択手段で選択された項の共通項を抽出する共通項
抽出手段と、 を具備することを特徴とする単一化候補項の選択装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63296152A JPH0668723B2 (ja) | 1988-11-25 | 1988-11-25 | 単一化候補項の選択装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63296152A JPH0668723B2 (ja) | 1988-11-25 | 1988-11-25 | 単一化候補項の選択装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH02143330A JPH02143330A (ja) | 1990-06-01 |
| JPH0668723B2 true JPH0668723B2 (ja) | 1994-08-31 |
Family
ID=17829828
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP63296152A Expired - Lifetime JPH0668723B2 (ja) | 1988-11-25 | 1988-11-25 | 単一化候補項の選択装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0668723B2 (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO1996010227A1 (en) * | 1994-09-28 | 1996-04-04 | Hideki Iwanishi | Method of selecting rule used in bottom-up reasoning in system based on knowledge base |
-
1988
- 1988-11-25 JP JP63296152A patent/JPH0668723B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPH02143330A (ja) | 1990-06-01 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5978794A (en) | Method and system for performing spatial similarity joins on high-dimensional points | |
| US6185557B1 (en) | Merge join process | |
| US5051745A (en) | String searcher, and compressor using same | |
| EP1360616B1 (en) | Database system and query optimiser | |
| US7062499B2 (en) | Enhanced multiway radix tree and related methods | |
| US7194456B2 (en) | Method of querying a structure of compressed data | |
| US5893094A (en) | Method and apparatus using run length encoding to evaluate a database | |
| JPH11212980A (ja) | インデクス作成方法および検索方法 | |
| US5442781A (en) | System for generating a search formula by accessing search terms on the basis of a training set of pertinent and non-pertinent objects | |
| JP2001331509A (ja) | リレーショナルデータベース処理装置、リレーショナルデータベースの処理方法及びリレーショナルデータベースの処理プログラムを記録したコンピュータ読み取り可能な記録媒体 | |
| JPH06223117A (ja) | 検索解収束方法 | |
| JPH02130673A (ja) | データ検索方式 | |
| JPH021059A (ja) | 連想検索システム | |
| JPH0668723B2 (ja) | 単一化候補項の選択装置 | |
| JPH06215044A (ja) | 情報検索処理装置 | |
| JP3018579B2 (ja) | 名前検索処理装置 | |
| JPH04337867A (ja) | データベース検索システム | |
| JPH0452967A (ja) | 集合ファイルに対する論理積演算処理方式 | |
| JPH10320402A (ja) | 検索式作成方法、検索式作成装置、及び記録媒体 | |
| JPH09330322A (ja) | データ検索装置 | |
| KR20020067162A (ko) | 문서 색인 시스템 및 그 방법 | |
| JPH0664534B2 (ja) | 単一化候補項の選択装置 | |
| JP3104893B2 (ja) | 情報検索方式 | |
| JPH03108063A (ja) | 後方一致検索方法および装置 | |
| JPH0738195B2 (ja) | 拡張項のための重ね合わせ符号を用いた検索方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EXPY | Cancellation because of completion of term |