JPH02143330A - 単一化候補項の選択装置 - Google Patents
単一化候補項の選択装置Info
- Publication number
- JPH02143330A JPH02143330A JP63296152A JP29615288A JPH02143330A JP H02143330 A JPH02143330 A JP H02143330A JP 63296152 A JP63296152 A JP 63296152A JP 29615288 A JP29615288 A JP 29615288A JP H02143330 A JPH02143330 A JP H02143330A
- Authority
- JP
- Japan
- Prior art keywords
- term
- variable
- index
- unification
- terms
- 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.)
- Granted
Links
- 238000001514 detection method Methods 0.000 abstract description 4
- 238000000034 method Methods 0.000 description 13
- 238000010586 diagram Methods 0.000 description 11
- 230000007423 decrease Effects 0.000 description 2
- 238000000605 extraction Methods 0.000 description 2
- 230000010365 information processing Effects 0.000 description 2
- 241000255925 Diptera Species 0.000 description 1
- 239000000428 dust Substances 0.000 description 1
- 210000003127 knee Anatomy 0.000 description 1
- 238000010187 selection method Methods 0.000 description 1
Landscapes
- Devices For Executing Special Programs (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
［発明の目的］
（産業上の利用分野）
この発明は、演鐸データベース、知識ベース、ファイル
システム等の単一化を伴う検索に際し、項データの集合
から単一化候補項を選択する技術に係わり、特に重ね合
せ符号による項データのインデックスを利用する単一化
候補項の選択装置に関する。
システム等の単一化を伴う検索に際し、項データの集合
から単一化候補項を選択する技術に係わり、特に重ね合
せ符号による項データのインデックスを利用する単一化
候補項の選択装置に関する。
（従来の技術）
演鐸データベース、知識ベース等のシステムでは、変数
を含む項データの単一化を伴う検索に用いた知識ベース
マシン（３） Ｊ 、森田他、情報処理学会第３５回全
国大会、２Ｃ−７、「知識ベースマシンＭｕ−Ｘ （４
） Ｊ 、仲瀬他、情報処理学会第３６回全国大会、５
Ｅ−７）。以下、この方式につい説明する。
を含む項データの単一化を伴う検索に用いた知識ベース
マシン（３） Ｊ 、森田他、情報処理学会第３５回全
国大会、２Ｃ−７、「知識ベースマシンＭｕ−Ｘ （４
） Ｊ 、仲瀬他、情報処理学会第３６回全国大会、５
Ｅ−７）。以下、この方式につい説明する。
いま、ある項が再帰的に、
類ニー関数子（項１２項２．・・・１項ｎ）と定義され
ているとすると、その項のインデックスは、第９図に示
すように、関数値のノ１ツシュ値のビットフィールドで
、項１１項２．・・・１項ｎのｓｓｃｗによるビットフ
ィールドの並びを覆うように配置して、両者を論理和演
算することにより生成される。両者のビットフィールド
の長さは、基本的には関数子のハツシュ値のビットフィ
ールド長が項１〜項ｎのｓｓｃｗの並びのビットフィー
ルド長よりも長くなるように設定される。
ているとすると、その項のインデックスは、第９図に示
すように、関数値のノ１ツシュ値のビットフィールドで
、項１１項２．・・・１項ｎのｓｓｃｗによるビットフ
ィールドの並びを覆うように配置して、両者を論理和演
算することにより生成される。両者のビットフィールド
の長さは、基本的には関数子のハツシュ値のビットフィ
ールド長が項１〜項ｎのｓｓｃｗの並びのビットフィー
ルド長よりも長くなるように設定される。
ここで、例えば第１０図に示す（１）〜（５）の検索対
象項と、（６）の質問順との単一化可能性を検証するに
は、次のような処理が行われる。
象項と、（６）の質問順との単一化可能性を検証するに
は、次のような処理が行われる。
まず、関数子ａ、ｂ、ｃ、ｄ、ｅの各ハツシュ値ｈ （
ｆ） 、 ｈ （ｇ）が同図（１６）、（１７）にそ
れぞれ示した３ビツトの値であるとすると、例えば（１
）で示した項ａ （ｆ、ｇ）のインデックスは、第１２
図（ａ）に示すように、 ｈ （ａ） Ｖ ｈ （ｆ） ｈ （
ｇ）−’ｏｉｏｏｉｏｔ、ｏ” Ｖ “００１１． Ｏ
Ｏ“−”０１００１１１０” と求められる。同様に、（２）〜（５）の各検索対象項
及び（６）の質問順は第１２図（ｂ）〜（ｅ）及び第１
３図のように求められる。ここで、これら検索対象項及
び質問順のインデックスを求める際、変数Ｘ、Ｙのうち
例えば検索対象項に出現する変数については全ビット“
１＃ また質問順に出現する変数については全ビット′
０＃のハツシュ値を与える。そして、検索対象項をＤ
（Ｄａｔａ） 、質問順をＱ （Ｑｕｅｒｙ ）とする
と、ＤΔＱ≠Ｑを満たすＤを持つ項については、明らか
にＱを持つ項とは単一化可能でないと考えて、と（４）
のｄ （Ｘ、Ｙ）が質問順ａ （Ｘ、Ｙ）と単一化可能
な候補として選択される。
ｆ） 、 ｈ （ｇ）が同図（１６）、（１７）にそ
れぞれ示した３ビツトの値であるとすると、例えば（１
）で示した項ａ （ｆ、ｇ）のインデックスは、第１２
図（ａ）に示すように、 ｈ （ａ） Ｖ ｈ （ｆ） ｈ （
ｇ）−’ｏｉｏｏｉｏｔ、ｏ” Ｖ “００１１． Ｏ
Ｏ“−”０１００１１１０” と求められる。同様に、（２）〜（５）の各検索対象項
及び（６）の質問順は第１２図（ｂ）〜（ｅ）及び第１
３図のように求められる。ここで、これら検索対象項及
び質問順のインデックスを求める際、変数Ｘ、Ｙのうち
例えば検索対象項に出現する変数については全ビット“
１＃ また質問順に出現する変数については全ビット′
０＃のハツシュ値を与える。そして、検索対象項をＤ
（Ｄａｔａ） 、質問順をＱ （Ｑｕｅｒｙ ）とする
と、ＤΔＱ≠Ｑを満たすＤを持つ項については、明らか
にＱを持つ項とは単一化可能でないと考えて、と（４）
のｄ （Ｘ、Ｙ）が質問順ａ （Ｘ、Ｙ）と単一化可能
な候補として選択される。
以」二の例では、検索対象類に現われる変数を全ビット
“１”のハツシュ値、質問順に現われる変数を全ビット
“０°のノ＼ツシュ値としたが、検索対象類に現われる
変数を全ビット″０°の／１ツシュ値、質問順に現われ
る変数を全ビット“１″のハツシュ値とするやり方もあ
る。第１４図にこの方法で検索対象類のインデックスを
求めた例、第１５図にこの方法で質問順のインデックス
を求めた例を示す。この場合には、検索対象類をＤ１質
問項をＱとすると、ＤＡＱ≠Ｄを満たすＤを持つ項につ
いては、明らかにＱを持つ項とは単一化可能でないと考
えて、単一化を試みない。第１０図の例では、検索対象
類（３）、（５）が上記の条件を満たすので、結局、検
索対象類（１）のａ（ｆ、 ｇ）と（２） ノｂ （ｆ
、 ｇ）と（４） ノｄ（Ｘ、Ｙ）が質問順ａ （Ｘ、
Ｙ）と単一化可能な候補として選択される。
“１”のハツシュ値、質問順に現われる変数を全ビット
“０°のノ＼ツシュ値としたが、検索対象類に現われる
変数を全ビット″０°の／１ツシュ値、質問順に現われ
る変数を全ビット“１″のハツシュ値とするやり方もあ
る。第１４図にこの方法で検索対象類のインデックスを
求めた例、第１５図にこの方法で質問順のインデックス
を求めた例を示す。この場合には、検索対象類をＤ１質
問項をＱとすると、ＤＡＱ≠Ｄを満たすＤを持つ項につ
いては、明らかにＱを持つ項とは単一化可能でないと考
えて、単一化を試みない。第１０図の例では、検索対象
類（３）、（５）が上記の条件を満たすので、結局、検
索対象類（１）のａ（ｆ、 ｇ）と（２） ノｂ （ｆ
、 ｇ）と（４） ノｄ（Ｘ、Ｙ）が質問順ａ （Ｘ、
Ｙ）と単一化可能な候補として選択される。
以上の例から明らかなように、後者の方法ではとしてい
るので、関数子ａのハツシュ値ｈ （ａ）が維持され質
問順と各検索対象類との論理演算に反映・される。しか
し、後者の場合には、質問順の変数のハツシュ値を全て
“１“とじているので、関数子ａのハツシュ値ｈ （ａ
）は一部分しか現われず質問順と各検索対象類との論理
演算にあまり反映されないからである。逆に、質問順に
は変数が含まれず、検索対象類に多くの変数が含まれて
いる場合には、検索対象類の側の変数のハツシュ値を全
ビット“１″にすると、単一化不可能な項の発見確率は
低下するという問題がある。
るので、関数子ａのハツシュ値ｈ （ａ）が維持され質
問順と各検索対象類との論理演算に反映・される。しか
し、後者の場合には、質問順の変数のハツシュ値を全て
“１“とじているので、関数子ａのハツシュ値ｈ （ａ
）は一部分しか現われず質問順と各検索対象類との論理
演算にあまり反映されないからである。逆に、質問順に
は変数が含まれず、検索対象類に多くの変数が含まれて
いる場合には、検索対象類の側の変数のハツシュ値を全
ビット“１″にすると、単一化不可能な項の発見確率は
低下するという問題がある。
（発明が解決しようとする課題）
このように、従来のｓｓｃｗ方式を用いた単一化候補項
の選択方式では、変数のハツシュ値のビットフィールド
を全ビット″】″とした側の項（又は項集合）に変数が
多く含まれていると、単一化不可能な項の発見精度が低
下するという問題点があった。
の選択方式では、変数のハツシュ値のビットフィールド
を全ビット″】″とした側の項（又は項集合）に変数が
多く含まれていると、単一化不可能な項の発見精度が低
下するという問題点があった。
本発明は、上記問題に鑑みなされたもので、変数の出現
度合いによって単一化不可能な項の発見（課題を解決す
るための手段） 本発明は、述語論理における少なくとも１つの項からな
る第１、第２の項集合からそれぞれ選択された第１、第
２の項の間の単一化可能性を判定する単一化岐捕項の選
択装置において、前記第１、第２の項が関数子とその引
数とからなる場合、上記引数の並びと、この引数の並び
よりもビット数の大きな関数子のハツシュ値とを論理演
算して前記３項のインデックスを生成する手段と、この
手段で生成された前記各項のインデックス同士の論理演
算結果によって両項が単一化可能かどうかを判定する手
段とを具備し、前記インデックスを生成する手段が、前
記第１及び第２の項集合のうち変数の出現度合いの大き
な項集合に含まれる変数のハツシュ値として全ビットに
“０″を割当て、他の項集合中の変数のノ１ツシュ値と
して全ビットに１゛を割当てるものであることを特徴と
じている。
度合いによって単一化不可能な項の発見（課題を解決す
るための手段） 本発明は、述語論理における少なくとも１つの項からな
る第１、第２の項集合からそれぞれ選択された第１、第
２の項の間の単一化可能性を判定する単一化岐捕項の選
択装置において、前記第１、第２の項が関数子とその引
数とからなる場合、上記引数の並びと、この引数の並び
よりもビット数の大きな関数子のハツシュ値とを論理演
算して前記３項のインデックスを生成する手段と、この
手段で生成された前記各項のインデックス同士の論理演
算結果によって両項が単一化可能かどうかを判定する手
段とを具備し、前記インデックスを生成する手段が、前
記第１及び第２の項集合のうち変数の出現度合いの大き
な項集合に含まれる変数のハツシュ値として全ビットに
“０″を割当て、他の項集合中の変数のノ１ツシュ値と
して全ビットに１゛を割当てるものであることを特徴と
じている。
また、本発明は、前記インデックスを生成する手段が、
前記第１及び第２の項集合に含まれる前記判定する手段
が、前記第１の項集合の第］のインデックスと前記第２
の項集合の第２のインデックスとの論理演算によって選
択される項と、前記第１の項集合の第２のインデックス
と前記第２の項集合の第１のインデックスとの論理演算
によって選択される項との共通項をｌｊ、−化候補項と
して選択するものであることを特徴と１．ている。
前記第１及び第２の項集合に含まれる前記判定する手段
が、前記第１の項集合の第］のインデックスと前記第２
の項集合の第２のインデックスとの論理演算によって選
択される項と、前記第１の項集合の第２のインデックス
と前記第２の項集合の第１のインデックスとの論理演算
によって選択される項との共通項をｌｊ、−化候補項と
して選択するものであることを特徴と１．ている。
（作用）
本発明によれば、第１の項集合と第２の項集合のうち変
数の出現度合いの大きな項集合に含まれる変数のハツシ
ュ値として全ビット“Ｏ゛を割当て、他の項集合中の変
数のハツシュ値として全ビットに“１″を割当てるよう
にしているので、変数の部分に１″が割当てられること
に起因する関数子や他の項のハツシュ値の内容の喪失は
、変数があまり含まれていない方の項集合にのみ起こる
。このため、多くの変数部分については本来のハツシュ
値の内容、即ち意味のある内容が残り、高い検出精度が
維持されることになる。
数の出現度合いの大きな項集合に含まれる変数のハツシ
ュ値として全ビット“Ｏ゛を割当て、他の項集合中の変
数のハツシュ値として全ビットに“１″を割当てるよう
にしているので、変数の部分に１″が割当てられること
に起因する関数子や他の項のハツシュ値の内容の喪失は
、変数があまり含まれていない方の項集合にのみ起こる
。このため、多くの変数部分については本来のハツシュ
値の内容、即ち意味のある内容が残り、高い検出精度が
維持されることになる。
また、本発明は２種類の方法で選択された項の（実施例
） 以下、図面を参照しながら本発明の実施例について説明
する。
） 以下、図面を参照しながら本発明の実施例について説明
する。
第１図は本発明の第１の実施例に係る単一化検索システ
ムの構成を示すブロック図である。この実施例では、検
索対象類集合における変数の出現度合いが所定の値以上
のときには検索対象類の変数に全ビット“θ′を割当て
、所定の値よりも小さいときには全ビット″１″を割当
てるようにしたものである。
ムの構成を示すブロック図である。この実施例では、検
索対象類集合における変数の出現度合いが所定の値以上
のときには検索対象類の変数に全ビット“θ′を割当て
、所定の値よりも小さいときには全ビット″１″を割当
てるようにしたものである。
検索結果記憶手段１０］−は検索対象類の集合を記憶す
る。変数出現度合い計算手段１０２は、↓記記憶手段１
０〕に記憶されている検索対象類集合から変数の出現度
合いを、例えば、変数記号／（変数記号十定数記号） なる式によって計算し、その結果をｓｓｃｗ作成手段１
０３に出力する。第１０図に示した例では、変数の出現
度合いが（２／１５）Ｘ１００−１３％と計算される。
る。変数出現度合い計算手段１０２は、↓記記憶手段１
０〕に記憶されている検索対象類集合から変数の出現度
合いを、例えば、変数記号／（変数記号十定数記号） なる式によって計算し、その結果をｓｓｃｗ作成手段１
０３に出力する。第１０図に示した例では、変数の出現
度合いが（２／１５）Ｘ１００−１３％と計算される。
ｓｓｃｗ作成手段１０３は、変数の出現度合いが所定の
値、例えば５０％以上で対象類のｓｓｃｗによるインデ
ックスを作成する。
値、例えば５０％以上で対象類のｓｓｃｗによるインデ
ックスを作成する。
ｓｓｃｗ作成手段１０３で作成されたインデックスは、
各検索対象類と対応付けられて検索対象類・インデック
ス記憶手段１０４に格納される。また、この記憶手段１
０４には、ｓｓｃｗ作成手段１０３での判定結果、つま
り変数の出現度合いが５０％以上である場合には例えば
１” ５０％未満である場合には例えば′Ｏ０となるフ
ラグ１、 （’） ４ ａを記憶する。一方、質問順は
質問順記憶手段１０５に格納されている。この質問順は
、ｓｓｃｗ作成手段１０６において５ＳＣＷのインデッ
クスに変換される。このとき、変数の部分を全ビット“
０゛にするか、“１゛にするかは検索対象類・インデッ
クス記憶手段１０４に記憶されているフラグ】０４ａの
値によって決定される。
各検索対象類と対応付けられて検索対象類・インデック
ス記憶手段１０４に格納される。また、この記憶手段１
０４には、ｓｓｃｗ作成手段１０３での判定結果、つま
り変数の出現度合いが５０％以上である場合には例えば
１” ５０％未満である場合には例えば′Ｏ０となるフ
ラグ１、 （’） ４ ａを記憶する。一方、質問順は
質問順記憶手段１０５に格納されている。この質問順は
、ｓｓｃｗ作成手段１０６において５ＳＣＷのインデッ
クスに変換される。このとき、変数の部分を全ビット“
０゛にするか、“１゛にするかは検索対象類・インデッ
クス記憶手段１０４に記憶されているフラグ】０４ａの
値によって決定される。
検索対象類の変数を１′にした場合には、質問順の変数
は“［］″、検索対象類の変数を“０″にした場合には
、質問順の変数は“１″となる。
は“［］″、検索対象類の変数を“０″にした場合には
、質問順の変数は“１″となる。
ｓｓｃｗ作成手段１０６で作成された質問順のインデッ
クスは、質問順・インデックス記憶手段ＤＡＱ４−Ｄ）
の条件式に基づき判定され、単一化挨補項が選択される
。そして、選択された単一化候補項は、更に単一化検索
手段１０９で検索され、最終的な検索結果が求められる
。この検索結果は検索結果記憶手段１１０に格納される
。
クスは、質問順・インデックス記憶手段ＤＡＱ４−Ｄ）
の条件式に基づき判定され、単一化挨補項が選択される
。そして、選択された単一化候補項は、更に単一化検索
手段１０９で検索され、最終的な検索結果が求められる
。この検索結果は検索結果記憶手段１１０に格納される
。
このように、本実施例によれば、検索対象類集合に含ま
れる変数の度合いによって検索対象項中の変数のビット
を“０″又は“１′にしているので、検索対象類の変数
を無条件に０″又は“１′にする方法に比べ、格段に選
択性能が向上する。
れる変数の度合いによって検索対象項中の変数のビット
を“０″又は“１′にしているので、検索対象類の変数
を無条件に０″又は“１′にする方法に比べ、格段に選
択性能が向上する。
第２図は本発明の第２の実施例に係る単一化検索システ
ムの構成を示す図である。この実施例は、検索対象類の
インデックスとして変数部分に全ビット“０″を割当て
た第１のインデックスと変数部分に全ビット“１′を割
当てた第２のインデックスとを用意しておき、検索対象
項集合内の変数出現度合いと質問項内の変数出現度合い
とを比較してその大小によって第１及び第２のインデッ
クスのうちのどちらを採用するかを決定するようにした
ものである。
ムの構成を示す図である。この実施例は、検索対象類の
インデックスとして変数部分に全ビット“０″を割当て
た第１のインデックスと変数部分に全ビット“１′を割
当てた第２のインデックスとを用意しておき、検索対象
項集合内の変数出現度合いと質問項内の変数出現度合い
とを比較してその大小によって第１及び第２のインデッ
クスのうちのどちらを採用するかを決定するようにした
ものである。
・ｊＩ１項集合に含まれる変数の出現度合いは、変数出
現度合い計算手段２０２で計算され、その結果は、検索
対象項・インデックス記憶手段２０４の変数度合いフィ
ールド２０４ａに格納される。５ＳＣＷ作成手段２０３
は、検索対象項の変数部分を０′に割当てた第１のイン
デックスＩ ＤＸＯ１゜ＩＤＸＯ２，・・・と、変数部
分に１′を割当てた第２のインデックスＩＤＸＩＩ、Ｉ
ＤＸ１２． ・・・をそれぞれ作成し、検索対象項・イ
ンデックス記憶手段２０４に格納する。一方、質問順記
憶手段２（］５に格納された質問順に含まれる変数の出
現度合いは変数出現度合い計算手段２０６で計算され、
ｓｓｃｗ作成手段２０７において変数度合いフィールド
２０４ａに格納された検索対象項の変数度合いと比較さ
れる。ｓｓｃｗ作成手段２０７は（検索対象項の変数度
合い≧質問順の変数度合い）の場合には、変数部分に“
１″を割当てて質問順のインデックスが作成され、（検
索対象項の変数度合いく質問順の変数度合い）の場合に
は、変数部分に“０′を割当てて質問順のインデックス
が作成される。第１０図の例の場合には、検ンデックス
は質問順と対応させて質問順・インデックス記憶手段２
０８に格納される。単一化可能候補選択手段２０９は、
質問順の変数部分に“０“が割当てられたか“１′が割
当てられたかに応じて第１及び第２のインデックスのう
ちのいずれかが選択されて単一化可能の判定処理が行わ
れる。
現度合い計算手段２０２で計算され、その結果は、検索
対象項・インデックス記憶手段２０４の変数度合いフィ
ールド２０４ａに格納される。５ＳＣＷ作成手段２０３
は、検索対象項の変数部分を０′に割当てた第１のイン
デックスＩ ＤＸＯ１゜ＩＤＸＯ２，・・・と、変数部
分に１′を割当てた第２のインデックスＩＤＸＩＩ、Ｉ
ＤＸ１２． ・・・をそれぞれ作成し、検索対象項・イ
ンデックス記憶手段２０４に格納する。一方、質問順記
憶手段２（］５に格納された質問順に含まれる変数の出
現度合いは変数出現度合い計算手段２０６で計算され、
ｓｓｃｗ作成手段２０７において変数度合いフィールド
２０４ａに格納された検索対象項の変数度合いと比較さ
れる。ｓｓｃｗ作成手段２０７は（検索対象項の変数度
合い≧質問順の変数度合い）の場合には、変数部分に“
１″を割当てて質問順のインデックスが作成され、（検
索対象項の変数度合いく質問順の変数度合い）の場合に
は、変数部分に“０′を割当てて質問順のインデックス
が作成される。第１０図の例の場合には、検ンデックス
は質問順と対応させて質問順・インデックス記憶手段２
０８に格納される。単一化可能候補選択手段２０９は、
質問順の変数部分に“０“が割当てられたか“１′が割
当てられたかに応じて第１及び第２のインデックスのう
ちのいずれかが選択されて単一化可能の判定処理が行わ
れる。
以後の単一化検索手段２１０及び検索結果記憶手段２１
１の機能は前述した実施例と同様である。
１の機能は前述した実施例と同様である。
この実施例によれば、検索対象項のみならず質問順の変
数度合いも考慮に入れたより精度の高い選択処理を行な
うことができる。
数度合いも考慮に入れたより精度の高い選択処理を行な
うことができる。
第３図は本発明の第３の実施例に係る単一化検索システ
ムの構成を示す図である。この実施例は、検索対象項、
質問順共に変数部分にそれぞれ０′ “１″を割当て
た２種類のインデックスを用意し、両インデックスでそ
れぞれ求められた単一化候補項の共通項を抽出してこれ
を単一化候補項とするようにしたものである。
ムの構成を示す図である。この実施例は、検索対象項、
質問順共に変数部分にそれぞれ０′ “１″を割当て
た２種類のインデックスを用意し、両インデックスでそ
れぞれ求められた単一化候補項の共通項を抽出してこれ
を単一化候補項とするようにしたものである。
検索結果記憶手段３０１に格納された検索対象項の２種
類のインデックスはｓｓｃｗ作成手段クスはりｓｃｗ作
成手段３０５で作成され、質問順・インデックス記憶手
段３０６に格納される。
類のインデックスはｓｓｃｗ作成手段クスはりｓｃｗ作
成手段３０５で作成され、質問順・インデックス記憶手
段３０６に格納される。
これら記憶手段３０３，３０６に格納されたインデック
スのうち、ＩＤＸ０Ｉ、ＩＤＸＯ２，・・・とＩＤＸＩ
とが単一化可能候補選択手段３０７で判定処理され、Ｉ
ＤＸＩＩ、ＩＤＸ１２．・・・とＩＤＸ０とが単一化可
能蚊捕選択手段３０８で判定処理される。両選択手段３
０７，３０８で求められた項は、共通項抽出手段３０９
により例えばＡＮＤ処理されて共通項が抽出される。単
一化検索手段３１０、検索結果記憶手段３１１の機能は
前述した実施例と同様である。
スのうち、ＩＤＸ０Ｉ、ＩＤＸＯ２，・・・とＩＤＸＩ
とが単一化可能候補選択手段３０７で判定処理され、Ｉ
ＤＸＩＩ、ＩＤＸ１２．・・・とＩＤＸ０とが単一化可
能蚊捕選択手段３０８で判定処理される。両選択手段３
０７，３０８で求められた項は、共通項抽出手段３０９
により例えばＡＮＤ処理されて共通項が抽出される。単
一化検索手段３１０、検索結果記憶手段３１１の機能は
前述した実施例と同様である。
この実施例によれば、２種類の方法で選択された項のう
ち共通な項を抽出することにより、実質的に精度の高い
方の方法により選択された項が単一化可能候補として抽
出されることになる。
ち共通な項を抽出することにより、実質的に精度の高い
方の方法により選択された項が単一化可能候補として抽
出されることになる。
第４図は本発明の第４の実施例に係る単一化を含むｊｏ
ｉｎを行なうシステムの構成を示す図である。
ｉｎを行なうシステムの構成を示す図である。
単一化を含むｊｏｉｎの対象となる項集合Ａとで２種類
のインデックスが作成される。求められた各インデック
スは各項と対応させて項集合Ａ・インデックス記憶手段
４０４１項集合Ｂ・インデックス記憶手段４０８にそれ
ぞれ格納される。また各記憶手段４０４，４０８には、
変数度合いフィールド４０４ａ、、４０８ａが設けられ
ており、ここに変数出現度合い計算手段４０２，４０６
で求められた変数度合いが格納される。組合わせ選択手
段４０９は、各変数塵合いフィールド４０４ａ、４０８
ａに格納された変数度合いの大小に基づき、各項集合Ａ
、Ｂのインデックスを選択する。単一化可能候補選択手
段４１０は、組合イ）せ選択手段４０９で選択されたイ
ンデックスの組合わせに基づいて単一化可能候補を選択
する。
のインデックスが作成される。求められた各インデック
スは各項と対応させて項集合Ａ・インデックス記憶手段
４０４１項集合Ｂ・インデックス記憶手段４０８にそれ
ぞれ格納される。また各記憶手段４０４，４０８には、
変数度合いフィールド４０４ａ、、４０８ａが設けられ
ており、ここに変数出現度合い計算手段４０２，４０６
で求められた変数度合いが格納される。組合わせ選択手
段４０９は、各変数塵合いフィールド４０４ａ、４０８
ａに格納された変数度合いの大小に基づき、各項集合Ａ
、Ｂのインデックスを選択する。単一化可能候補選択手
段４１０は、組合イ）せ選択手段４０９で選択されたイ
ンデックスの組合わせに基づいて単一化可能候補を選択
する。
これにより、単一化・ｊｏｉｎ処理手段４１１は、項集
合Ａと項集合Ｂの単一化を含むｊｏｉｎを行なう。その
結果は、単一化・ｊｏｉｎ結果記憶手段４１２に格納さ
れる。
合Ａと項集合Ｂの単一化を含むｊｏｉｎを行なう。その
結果は、単一化・ｊｏｉｎ結果記憶手段４１２に格納さ
れる。
合いは（８／１５）Ｘ １．００−５３％であるから、
項集合Ａの変数に第１２図に示すように“１”項集合Ｂ
の変数に第７図に示すように０″が割当てされる。この
結果、項集合Ａと項集合Ｂの単一化可能なベアとして、
（１）（２１）、（１）（２４）、 （２） （２２
） 、 （２） （２４） 、（２４）、 （３
） （２５） 、 （４）（２１，） 、（４）
（２２） 、 （４） （２４） 、 （５
） （２５）の１２組が選択される。ちなみに、項集
合への変数に第１４図に示すように“Ｏ”、項集合Ｂの
変数に第８図に示すように“１″が割当てると、項集合
Ａと項集合Ｂの単一化可能なペアとして、（１）（２１
）、（１）（２２）、（１）（２３）、（２）（２１）
、（２）（２２）、（２）（２３） （２）（２４
＞ （３）（２３）、（４）（２１）、（４）（２
２）、（２３）、（５）（２５）の１４組が選択され、
前者の方がより選択精度が高いことが明らかであ項集合
Ａ記憶手段５０１に格納された項集合Ａの２種類のイン
デックスはｓｓｃｗ作成手段５０２で作成され、項集合
Ａ・インデックス記憶１段５０３に格納される。また、
項集合Ｂ記憶手段５０４に格納された項集合Ｂの２種類
のインデックスはｓｓｃｗ作成手段５０５で作成され、
項集合Ｂ・インデックス記憶手段５０６に格納される。
項集合Ａの変数に第１２図に示すように“１”項集合Ｂ
の変数に第７図に示すように０″が割当てされる。この
結果、項集合Ａと項集合Ｂの単一化可能なベアとして、
（１）（２１）、（１）（２４）、 （２） （２２
） 、 （２） （２４） 、（２４）、 （３
） （２５） 、 （４）（２１，） 、（４）
（２２） 、 （４） （２４） 、 （５
） （２５）の１２組が選択される。ちなみに、項集
合への変数に第１４図に示すように“Ｏ”、項集合Ｂの
変数に第８図に示すように“１″が割当てると、項集合
Ａと項集合Ｂの単一化可能なペアとして、（１）（２１
）、（１）（２２）、（１）（２３）、（２）（２１）
、（２）（２２）、（２）（２３） （２）（２４
＞ （３）（２３）、（４）（２１）、（４）（２
２）、（２３）、（５）（２５）の１４組が選択され、
前者の方がより選択精度が高いことが明らかであ項集合
Ａ記憶手段５０１に格納された項集合Ａの２種類のイン
デックスはｓｓｃｗ作成手段５０２で作成され、項集合
Ａ・インデックス記憶１段５０３に格納される。また、
項集合Ｂ記憶手段５０４に格納された項集合Ｂの２種類
のインデックスはｓｓｃｗ作成手段５０５で作成され、
項集合Ｂ・インデックス記憶手段５０６に格納される。
これら記憶手段５０３，５０６に格納されたインデック
スのうち、ＩＤＸ０Ｉ、ＩＤＸＯ２゜・・・とＩＤＸＩ
Ｉ、ＩＤＸＩＩＩ、・・・とが単一化可能候補選択手段
５０７で判定処理され、ＩＤＸＩＩ。
スのうち、ＩＤＸ０Ｉ、ＩＤＸＯ２゜・・・とＩＤＸＩ
Ｉ、ＩＤＸＩＩＩ、・・・とが単一化可能候補選択手段
５０７で判定処理され、ＩＤＸＩＩ。
ＩＤＸ１２．・・・とＩＤＸ０Ｉ、ＩＤＸ０ＩＩ、・・
・とが屯−化ｉｊＪ能候補選択手段５０８で判定処理さ
れる。両選択手段５０７，５０８で求められた項は、Ｊ
（通項抽出手段５０９により例えばＡＮＤ処理されて共
通項が抽出される。単一化・ｊｏｉｎ処理手段５１０、
単一化・ｊｏｉｎ処理結果記憶手段５１１の機能は前述
した実施例と同様である。
・とが屯−化ｉｊＪ能候補選択手段５０８で判定処理さ
れる。両選択手段５０７，５０８で求められた項は、Ｊ
（通項抽出手段５０９により例えばＡＮＤ処理されて共
通項が抽出される。単一化・ｊｏｉｎ処理手段５１０、
単一化・ｊｏｉｎ処理結果記憶手段５１１の機能は前述
した実施例と同様である。
この実施例によれば、前述した１２組の項とα３）（２
３） （４）（２１，） （４）（２２）、（
４）（２４）、（５）（５）の８組の共通項が抽出され
る。このように、この実施例によれば更に精度の高い選
択処理を行なうことができる。
３） （４）（２１，） （４）（２２）、（
４）（２４）、（５）（５）の８組の共通項が抽出され
る。このように、この実施例によれば更に精度の高い選
択処理を行なうことができる。
［発明の効果コ
このように本発明によれば、第１の項集合と第２の項集
合のうち変数の出現度合いの大きな項集合に含まれる変
数のハツシュ値として全ビット″０”を割当て、他の項
集合中の変数のハツシュ値として全ビットに“１″を割
当てるようにしているので、多くの変数部分については
本来のハツシュ値の内容、即ち意味のある内容が残り、
高い検出精度が維持されることになる。
合のうち変数の出現度合いの大きな項集合に含まれる変
数のハツシュ値として全ビット″０”を割当て、他の項
集合中の変数のハツシュ値として全ビットに“１″を割
当てるようにしているので、多くの変数部分については
本来のハツシュ値の内容、即ち意味のある内容が残り、
高い検出精度が維持されることになる。
また、変数のハツシュ値として０″を割当てたインデッ
クスと“１″を割当てたインデックスの２種類のインデ
ックスを用いた方法によりそれぞれ抽出された２種類の
選択順集合の共通集合を単一化可能な項として選択する
ので、単一化の確度の高い項のみが選択されることにな
る。
クスと“１″を割当てたインデックスの２種類のインデ
ックスを用いた方法によりそれぞれ抽出された２種類の
選択順集合の共通集合を単一化可能な項として選択する
ので、単一化の確度の高い項のみが選択されることにな
る。
このため、本発明によれば変数の出現度合いに
第１図は本発明の第１の実施例に係る単一化候補項の選
択装置のブロック図、第２図は本発明の第２の実施例に
係る単一化候補項の選択装置のブロック図、第３図は本
発明の第３の実施例に係る１１１−化候補項の選択装置
のブロック図、第４図は本発明の第４の実施例に係る単
一化候補項の選択装置のブロック図、第５図は本発明の
第５の実施例に係る単一化候補項の選択装置のブロック
図、第６図乃至第８図は上記第４の実施例の選択装置の
作用を説明する為の図、第９図乃至第１５図はｓｓｃｗ
方式を説明するための図である。 １．０１，２０１．３０１・・・検索対象項記憶手段、
１０２．２０２，２０６，４０２，４０６・・・変数出
現度合い計算手段、１０３，１０６，２０３゜２０７．
３０２，３０５，４０３，４０７゜５０２．５０５・・
・ｓｓｃｗ作成手段、１０４゜２０４．３０３・・・検
索対象項・インデックス記憶手段、１０５，２０５，３
０４・・・質問項記憶手段、１０７．２０８，３０６・
・・質問項・インデックス３０９．５０９・・・共通項
抽出手段、４０１゜５０１・・・項集合Ａ記憶手段、４
０４，５０３・・・項集合Ａ・インデックス記憶手段、
４０５５０４・・・項集合Ｂ記憶手段、４０８，５０６
・・・項集合Ｂ・インデックス記憶手段、４１１５１０
・・・単一化・ｊｏｉｎ処理手段、４１２５１１・・・
単一化・ｊｏｉｎ結果処理手段。 出願人 工業技術院長 飯塚幸二 云；５１０ ｒ、； ２□−ｊ （ａ） （ｂ） （ｃ） 第 ８図 （ｄ） （ａ） （ｄ） （ｂ） （ｅ） （Ｃ） ；、′； １２・１・」 ｒ″）１３ワ］ （ａ） （ｄ） （ｂ＞ （ｅ） τ；ｉｓ、Ｉ］
択装置のブロック図、第２図は本発明の第２の実施例に
係る単一化候補項の選択装置のブロック図、第３図は本
発明の第３の実施例に係る１１１−化候補項の選択装置
のブロック図、第４図は本発明の第４の実施例に係る単
一化候補項の選択装置のブロック図、第５図は本発明の
第５の実施例に係る単一化候補項の選択装置のブロック
図、第６図乃至第８図は上記第４の実施例の選択装置の
作用を説明する為の図、第９図乃至第１５図はｓｓｃｗ
方式を説明するための図である。 １．０１，２０１．３０１・・・検索対象項記憶手段、
１０２．２０２，２０６，４０２，４０６・・・変数出
現度合い計算手段、１０３，１０６，２０３゜２０７．
３０２，３０５，４０３，４０７゜５０２．５０５・・
・ｓｓｃｗ作成手段、１０４゜２０４．３０３・・・検
索対象項・インデックス記憶手段、１０５，２０５，３
０４・・・質問項記憶手段、１０７．２０８，３０６・
・・質問項・インデックス３０９．５０９・・・共通項
抽出手段、４０１゜５０１・・・項集合Ａ記憶手段、４
０４，５０３・・・項集合Ａ・インデックス記憶手段、
４０５５０４・・・項集合Ｂ記憶手段、４０８，５０６
・・・項集合Ｂ・インデックス記憶手段、４１１５１０
・・・単一化・ｊｏｉｎ処理手段、４１２５１１・・・
単一化・ｊｏｉｎ結果処理手段。 出願人 工業技術院長 飯塚幸二 云；５１０ ｒ、； ２□−ｊ （ａ） （ｂ） （ｃ） 第 ８図 （ｄ） （ａ） （ｄ） （ｂ） （ｅ） （Ｃ） ；、′； １２・１・」 ｒ″）１３ワ］ （ａ） （ｄ） （ｂ＞ （ｅ） τ；ｉｓ、Ｉ］
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 true JPH02143330A (ja) | 1990-06-01 |
| JPH0668723B2 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) |
Cited By (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
Cited By (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 |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH0668723B2 (ja) | 1994-08-31 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US7631012B2 (en) | System and method of operating a database | |
| US5978794A (en) | Method and system for performing spatial similarity joins on high-dimensional points | |
| US6968330B2 (en) | Database query optimization apparatus and method | |
| JP3849279B2 (ja) | インデクス作成方法および検索方法 | |
| US5893094A (en) | Method and apparatus using run length encoding to evaluate a database | |
| US20040093329A1 (en) | Database system and query optimiser | |
| US6675160B2 (en) | Database processing method, apparatus for carrying out the same and medium storing processing program | |
| JP2002163290A (ja) | クエリ最適化のためのコストに基づく具体化ビューの選択 | |
| CN110442584B (zh) | 一种基于异步加载的树形结构资源检索的方法 | |
| GB2368929A (en) | System for storing and retrieving data | |
| CN108681603B (zh) | 数据库中快速搜索树形结构数据的方法、存储介质 | |
| US5307445A (en) | Query optimization by type lattices in object-oriented logic programs and deductive databases | |
| 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 | |
| US7277892B2 (en) | Database processing system, method, program and program storage device | |
| JP2004520633A (ja) | 属性又はキー値を選択的に利用することによりクエリ生成を最適化する方法と装置 | |
| US5943665A (en) | Method and system for performing conceptual joins across fields of a database | |
| Li et al. | Mining the smallest association rule set for predictions | |
| US7010539B1 (en) | System and method for schema method | |
| JPH06223117A (ja) | 検索解収束方法 | |
| JPH02143330A (ja) | 単一化候補項の選択装置 | |
| JPH06215037A (ja) | インデックスの自動更新装置 | |
| EP1384169B1 (en) | System and method of optimising queries in a database | |
| JPH08320879A (ja) | 適合フィードバック装置 | |
| JP2001147936A (ja) | 文書検索システム、方法及び記録媒体 | |
| KR101714985B1 (ko) | 분산 병렬 데이터베이스의 중첩 질의 병렬성 검사 방법 및 장치 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EXPY | Cancellation because of completion of term |