JPH01232436A - 単一化候補項の選択装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ルシステムなどの単一化を伴う検索に際し、項データの
集合から単一化候補を選択する単一化候補項の選択装置
に関する。

（従来の技術） 演鐸データベース、知識データベース等のデータベース
システムでは、変数を含む項データのｑｔ−化を伴う検
索に際し、検索対象を絞り込んで検索処理の効率を高め
るために、予め検索対象となる類データ集合の中から検
索項データと単一化可能性のあるｔドー化候補項を選択
することが前処理として行われる。この種の単一化候補
の選択方式としては、従来より、人前、■中等による１
１ツシユ＆ソート法が知られている（情報処理学会第３
３口金国大会、５Ｌ−６，人前、田中「単一化バタン検
索の最適化」）。この方式では、検歯頂データと被検歯
頂データとを、予め設定された木構造に基づいてベクト
ルデータに展開し、この展開されたベクトルデータの各
要素を１組ずつ比較し、両要素が定数で且つ異なる定数
である場合にか割当てられたハツシュベクトルの形態で
取扱われる。これにより検索効率の向上化が図られてい
る。

第８図乃至第１５図を用いてこの方式を更に詳細に説明
する。いま、第８図の（Ａ）で示す検歯頂データと単一
化可能な類データを、類データ（Ｂ）、（Ｃ）、（Ｄ）
からなる項データ集合から選択するものとする。なお、
ここで類データの表記は、ＤＢＣ１０−Ｐｒｏｌｏｇの
表記法に準拠している。

従って、小文字で始まるシンボルは定数、人文字で始ま
るシンボルは変数である。第９図はこれら類データの展
開方法を示す木構造である。この木構造の各ノードに付
された番号は、類データをベクトルデータに変換する際
の要素番号を示す。今、類データ（Ａ）、（Ｂ）、（Ｃ
）、（Ｄ）を第９図の本構造に括づいてベクトルデータ
に展開すると、第１０図の（−Ａ）、（Ｂ）、（Ｃ）、
　　（Ｄ）のような形になる。本構造の下位のノードは
、その上位のノードの引き数となっている。各要素をで
示している。これらベクトルデータは、実際には計算機
内部においてはハツシュベクトルの形態で取扱われる。

即ち、各類データは、変数要素及び空き要素については
Ｏ１小文字で始まる定数要素については０以外のハツシ
ュ値が割当てられられた第１２図に示すような形態で扱
われる。

なお、ここで、ｈはハツシュ関数を示しており、ｈ　（
ａｌ）、ｈ　（ａ２）は、それぞれａｌ、ａ２をハツシ
ュした数値を示す。

次にハツシュベクトルに展開された被検歯頂データ（Ｂ
）、（Ｃ）、（Ｄ）が検歯頂データ（Ａ）と単一化可能
であるかどうかがチエツクされる。

即ち、検歯頂データのハツシュベクトルをＰｌそのｌ（
番目の要素をＰｋ、彼検歯頂データのハツシュベクトル
をＱｌそのに番目の要素をＱｋとすると、ハツシュベク
トルＰ、Ｑの先頭要素から順に全ての要素について比較
したとき、Ｐｋ−Ｑｋ≠０で且つＰｋ≠Ｑｋとなる要素
が存在しなければ、ハツシュベクトルＰとＱとは単一化
可能であると一化候補が外され、他の類データ（Ｂ）、
（Ｄ）についてはζドー化可能であると判定される。

ところが、上記の方式においては、ハツシュベクトルの
各要素のハツシュ値に衝突が発生した場合、単一化可能
でないものが単一化可能であるとして選択されてしまう
という問題があった。

例えば被検索データが第１３図に示す類データ（Ｅ）、
（Ｆ）であるとする。これら類データ（Ｅ）、（Ｆ）と
類データ（Ａ）とを比較すると、類データ（Ａ）の検索
ａ２と類データ（Ｅ）の検索ａ７、及び類データ（Ａ）
の要素Ｃ１と類データ（Ｆ）の要素ｅ１は、それぞれ引
き数が異なっているので、本来単一化の可能性はない。

類データ（Ｅ）、（Ｆ）を前述した木構造に当はめて展
開した形態は第１４図に示される。これら類データ（Ｅ
）、（Ｆ）がハツシュベクトルに展開されると第１５図
のようになる。このとき、ハツシュ値の衝突が発生し、
本来異なるべき筈のｈ（ａ２）とｈ（ａ７）が等しくな
ったり、ｈ（ｃｌ）と可能であると判定するミスを犯す
。このような判定ミスは、項データの空き要素や変数要
素が多ければ多い程発生し易くなる。

（発明が解決しようとする課題） このように、従来の単一化候補の選択方式においては、
ハツシュ値の衝突が起こった場合に、単一化不可能な項
データを単一化可能な項データであると誤って判定して
しまい、検索紋補を正確に抽出することができないとい
う問題があった。

特に従来の１１１．−化候補の選択方式では、ハツシュ
ベクトルの空き要素及び変数要素にハツシュ値“０”を
与えていることから、類データ中に空き要素や変数値が
多く含まれる程、この種のミスが発生し易いという問題
があった。

本発明は、ハツシュ値の衝突が起こった場合でも、単一
化候補を正しく選択できる単一化候補項の選択装置を［
（３４することを目的とする。

［発明の構成］ （課題を解決するための手段） 本発明は、変数及び／又は定数の要素から構夕と被検歯
頂データとを比較して両頂データの単、−化ｎ１能性を
判定する判定手段とを備えた単一化・候補項の選択装置
において、上記展開手段と判定手段とを次のような機能
を持たせたことを特徴としている。

即ち、展開手段は、ベクトルデータを構成する要素が前
記本構造における変数要素の下位の空き要素であるとき
は第１の識別子を割当て、該要素が変数要素であるとき
は第２の識別子を割当て、該要素が前記本構造における
定数要素の下位の空き要素であるときは第３の識別子を
割当て、該要素が定数要素であるときは上記第１乃至第
３の識別子とは異なるハツシュ値を割当てる。

また、判定手段は前記検歯頂データと被検歯頂データと
を比較したとき、一方の項データの要素が第３の識別子
で他方の項データの要素が前記第１及び第３の識別子以
外である場合、又は上記両要素が前記第１乃至第３の識
別子とは異なり且つ互いに異なるハツシュ値である場合
に、両頂データは単一化不［Ｉ）能であると判定する。

−□ ５の空き要素をそれぞれ区別し得るようなハツシュ値を
与えるので、ハツシュベクトルへ展開する際°に引き数
の個数の違う要素のハツシュ値が衝突していた場合でも
、その要素の下位の要素を比較することにより、単一化
可能でないことを容易に判定できる。つまり、比較する
要素の組が“定数。

と“定数の下の要素″、又は“変数”と“定数の下の要
素”である場合、明らかにそれらの要素の上位の要素の
引き数の数が違うので、項同士が単一化可能ではないと
判定することができる。

（実施例） 以下、本発明の一実施例について説明する。

第１図に本実施例に係る単一化候補項の選択装置の構成
を示す。この装置は、展開部１１と、判定部１２とによ
り構成されている。

展開部１１は、図示しないデータベースから単一化可能
性を検証する一対の項データＡ、Ｂを入ニの装置の動作
フローを第２図に示す。先ず、展開部１１において、項
データＡ、ＢのハツシュベクトルＰ、Ｑへの展開が行わ
れる（Ｓｌ）。この展開において各要素には次のような
ハツシュ値が割当てられる。

０・・・変数の下位の空き要素 １・・・変数、 ２・・・定数の下のノード ３以上・・・定数 続いて判定部１２において、ハッシュベクトルＰ、Ｑの
各要素Ｐｋ　、　Ｑｋ　　（ｋ＝１．　２．−・−、ｎ
’）（ｎはハツシュベクトルの要素数）の比較処理が行
われる。判定は、第３図に表で示した基章に従って行わ
れる。なお、この表において、Ｏは単一化可能性有り、
×は単一化可能性無し、Δは両要素同−の条件付きで単
一化の可能性有りを示している。さて、まず始めにｋが
１にセットされると（、Ｓ２）、要素Ｐｋ、Ｑｋが次の
■〜■の条件のいずれか一つにマツチするかが調べられ
る（Ｓ３゜Ｓ４．Ｓ５）。

上記■〜■の条件のいずれか一つにマツチしたら、項デ
ータＡ、Ｂは単一化不可能である旨を判定結果として出
力する（Ｓ６）。一方、上記■〜■のいずれの条件にも
マツチしなければ、ｋをカウントアツプしくＳ７）、同
様の処理をｋがｎを超えるまで続ける（Ｓ８）。ｌ（が
ｎを超えるまで処理が進んだら、項データＡ、Ｂは単一
化可能な候補である旨を判定結果として出力する（Ｓ９
）。

いま、第４図に示す項データ（１）を検歯頂データ、項
データ（２）〜（６）を彼検歯頂データであるとする。

これら項データを第９図の木構造に基づいて展開した状
態を第５図に示す。更に、これら本構造に展開された項
データ（１）〜（６）を、本構造の各ノードの番号に従
ってベクトル化すると、第６図のようになる。更に、こ
のベクトルの各要素に前述した基桑でハツシュ値を割当
てると、第７図のようになる。

項データ（１）のハツシュベクトルをＰ、項データ（２
）〜（６）のハツシュベクトルをＱとすに−２：　Ｐ２
　、　　Ｑ２≧３．Ｐ２−０２に−３：　Ｐ３　、　　
Ｑ３≧３．Ｐ３−０３に−４：Ｐ４寓１．Ｑ４≠２ に＝５：Ｐ５　　≠２．Ｑ５−１ に−［ｉ　　：　　ＰＧ　　、　　Ｑ［ｉ　　≧３．　
ＰＧ　膿Ｑ６に−７：　　Ｐ７　−１．　　Ｑ７　　≠
２また、項データ（１）と（３）とは、ｋ−１〜５にお
いて、以下の比較により単一化不可能であると判定され
る。

ｋ−１７ＰＩ　、　Ｑｌ≧３．ＰＩ　−Ｑｌｋ−２：　
Ｐ２　、　Ｑ２≧３．Ｐ２−Ｑ２に−３：　Ｐ３　、　
Ｑ３≧３．Ｐ３−０３に−４：　Ｐ４−１．Ｑ４≠２ に−５：　Ｐ５　、　Ｑ５≧３．Ｐ５≠Ｑ５（単一化不
可能の条件■を満たした） 次に、項データ（１）と項データ（４）との比較につい
て述べる。いま、項データ（１）の第３要素ｈ（ａ２）
と、項データ（４）の第３要素ｈ（ａ７）との間でハツ
シュ値の衝突が生じてぃたに−２：　　Ｐ２　　、　　
Ｑ２　　≧３．　　Ｐ２　−Ｑ２に−３：　　Ｐ３　　
、　　Ｑ３　　≧３．　　Ｐ３　−Ｑ３に−４二　Ｐ４
　　−１．　　　Ｑ４　　≠　２に−５：Ｐ５　　≠２
．Ｑ５−１ に−８：ＰＧ　　≠０．　２．　　ＱＢ　　−２（単一
化不可能の条件■を満たした） また、項データ（１）と（５）についても、各第１要素
のｈ　（ｃｌ）＝ｈ　（ｅｌ）であるようなハツシュ値
の衝突が生じているとすると、以下の比較により単一化
不可能であると判定される。

ｋ−１：　ＰＩ　、　Ｑｌ≧３．ＰＩ　−Ｑｌｋ−２；
　Ｐ２　、　　Ｑ２≧３．Ｐ２−Ｑ２に園３　：Ｐ３≠
０．２．０３−２ （単一化不可能の条件■を満たした） 更に、項データ（１）と項データ（６）については、ｋ
−１〜７において、以下の比較により単一化可能である
と判定される。

ｋ−１：　ＰＩ　、　Ｑｌ≧３．ＰＩ　−Ｑｌｋ−２：
Ｐ２≠２．Ｑ２−１ に−３：　Ｐ３　、　　Ｑ３≧３．Ｐ３−０３Ｕ＼１ −Ｙ−４：　　Ｐ４　−　１．　　Ｑ、４　　≠２に−
５：Ｐ５　　≠２．　　Ｑ５　−０ｋ−８：　　Ｐ（ｉ
　　、　　ＱＢ　　≧３．　　ＰＱ　　−ＱＢｋ＝７　
　：　　Ｐ７　−１．　　Ｑ７　　≠２このように、本
実施例に係る単一候補項の選択装置を用いることにより
、ハツシュ値が衝突した場合でも、定数の引数の数が合
わないものについては単一化不可能であると判定するこ
とができる。

［発明の効果］ 以上のように、本発明によれば、展開手段によって変数
、定数及びこれらの下位の空き要素を明確に区別して項
データをハツシュベクトルに展開し、判定手段で引数の
異なる要素が存在する項データ同士の単一化可能性を否
定するようにしているので、ハツシュ値の衝突が発生し
ている場合でも正確に単一化候補項を選択することがで
きる。

この結果、本発明によれば、データベースシステムにお
ける単一化処理の効率向上に寄与することができる。

【図面の簡単な説明】

第１図〜第７図は本発明の一実施例に係る単一化候補項
の選択装置を説明するための図で、第１す図、第５図は
同項データを本構造に展開した図、第６図は同項データ
を本構造のノード番号に従ってベクトルデータ化した図
、第７図は同ベクトルデータにハツシュ値を割当てたハ
ツシュベクトルを示す図、第８図〜第１５図は従来の単
一化候補項の選択方式を説明する為の図で、第８図は項
データの例を示す図、第９図は項データの展開基準とな
る木構造を示す図、第１０図は同項データを木構造に展
開した図、第１１図は同項データを木構造のノード番号
に従ってベクトルデータ化した図、第１２図は同ベクト
ルデータにハツシュ値を割当てたハツシュベクトルを示
す図、第１３図は従来判定ミスを犯し易い項データの例
を示す図、第１４図は同項データを本構造に展開した図
、第１５図は同ベクトルデータにハツシュ値を割当てた
ハツシュベクトルを示す図である。 １・・・展開部、２・・・判定部。 出願人　　工業技術院長　飯塚幸三 第１図 ｂ 第３図 第４図 第８図 第９　図 （Ａ）　　　　　　（Ｂ）　　　　　　（Ｃ）　　　　
　　（Ｄ）第１０図

Claims (1)

1. 【特許請求の範囲】 変数及び／又は定数の要素から構成される項データを木
   構造に当てはめてベクトルデータに展開する展開手段と
   、この展開手段によって各々ベクトルデータに展開され
   た検索項データと被検索項データとを比較して両項デー
   タの単一化可能性を判定する判定手段とを備えた単一化
   候補項の選択装置において、 前記展開手段は、ベクトルデータを構成する要素が前記
   木構造における変数要素の下位の空き要素であるときは
   第１の識別子を割当て、該要素が変数要素であるときは
   第２の識別子を割当て、該要素が前記木構造における定
   数要素の下位の空き要素であるときは第３の識別子を割
   当て、該要素が定数要素であるときは上記第１乃至第３
   の識別子とは異なるハッシュ値を割当てるものであり、
   前記判定手段は前記検索項データと被検索項データとを
   比較したとき、一方の項データの要素が第３の識別子で
   他方の項データの要素が前記第１及び第３の識別子以外
   である場合、又は上記両要素が前記第１乃至第３の識別
   子とは異なり且つ互いに異なるハッシュ値である場合に
   、両項データは単一化不可能であると判定するものであ
   ることを特徴とする単一化候補項の選択装置。