JPH0333979A - 関係データベースの限定述語処理方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 【産業上の利用分野】

本発明は、関係データベースへの問合せにおける限定述
語処理方法に関し、特に比較演算子が＝限定子がＡＮＹ
である限定述語処理方法に関する。 〔従来の技術］ 関係データベースは、例えばＣ０Ｌ、ＤＡＴＥｒデータ
ベース・システムの概論Ｊｌ（丸善（株）発行）に記載
されているように、行と列の表形式により表現されてい
る論理的なデータ構造を持ったデータベースのことであ
る。また、限定述語とは、関係データベースへの問合せ
の中で、副問合せを含む条件式の中に出現するものであ
り、例えば″列名′　　゛比較演算子″限定子°　　゛
副問合せ゛の形式により表現される。限定子の種類によ
り、副問合せの結果の要素の任意の１つないし全ての値
と主問合せの列の値とを比較して、比較演算子の条件を
満足するか否かを判定するものである。 一例を挙げて説明する。いま、データベース言語５ＱＬ
（ＪＩＳ　　Ｘ　　３００５−１９８７）１’表現する
と、下記のように表わされる。 ５ＥＬＥＣＴ　Ａｌ、Ａ２．Ａ３ ＦＲＯＭ　　　　ＴＩ Ｗ＋−（ＥＲＥ　　Ａ２＝１００　　ＡＮＤＡ３＝ＡＮ
Ｙ（ＳＥＬＥＣＴ　　ＢＩ ＦＲＯＭ　　　　Ｔ２ ＷＨＥＲＥ　　Ｂ３＜５００） なお、上記表現中で、Ｓ　Ｅ　Ｌ　ＥＣＴは出力列を指
定し、ＦＲＯＭはアクセス対象の表を指定し、ＷＨＥＲ
Ｅは検索の条件を示している。また、ＷＨＥ　ＲＥの後
の条件式は、列Ａ２の値が１００に等しく、かつ列Ａ３
の値が副問合せ結果の複数の値の任意の１つの値と等し
い行を返却することを示している。副問合せは、表Ｔ２
の列Ｂ３の値が５００より小さい行の列Ｂｌを返却する
ことを示している。 限定子の種類は、ＡＮＹ／ＳＯＭＥとＡＬＬとがあり、
このうちＡＮＹ／ＳＯＭＥは副問合せの結果の要素値の
任意の１つが比較演算子を満足することを意味しており
、ＡＬＬは副問合せの結果の要素値の全てが比較４１［
算子を満足することを意味する。 第４図は、従来における限定述語の処理システムの機能
ブロック図であり、第５図は第４図における動作フロー
チャートである。 第４図において、４０１は検索の条件を生成するための
プログラムを備えた検索条件作成部、４０２は実際に主
問合せの表の条件式と副問合せの表の条件式を満足する
ものを検索するためのプログラムを備えた検索処理部、
４１０は外部から人力する検索命令、４１１は副問合せ
の表の条件式、４１２は主問合せの表の条件式、４２１
は副問合せで検索する表、４２２は主問合せで検索する
表、４２３は副問合せ結果の要素群、４２４は検索結果
を格納するレジスタである。 次に、限定述語を含む検索処理の動作を、第５図により
述べる。 先ず、検索条件作成部４０１が検索命令４１０から副問
合せで検索する表４２１に対する条件式４１１を作成す
る（ステップ５０１）、次に、検索処理部４０２は、副
問合せで検索する表４２１に対する条件式４１１を評価
して、その結果を副問合せ結果の要素群４２３に格納す
る（ステップ５０２）０次に、検索条件作成部４０１は
検索命令４１０から主問合せで検索する表４２２に対す
る条件式４１２を作成する（ステップ５０３）、次に、
検索処理部４０２は、主問合せで検索する表４２２に対
する条件式４１２のうち、限定述語を除いた条件を評価
する（ステップ５０４）、次に、検索処理部４０２では
、副問合せ結果の要素群から要素を１個取り出し、限定
述語の比較演算子を満足するか否かを判定する（ステッ
プ５０５）、また、検索処理部４０２は、要素が比較演
算子を満足すれば（ステップ５０６）、限定述語の判定
結果を真として限定述語の評価を終了する（ステップ５
０８）０次に、検索処理部４０２は、副問合せ結果の要
素群４２３から全ての要素を順次取り出し、要素がなく
なるまで上記処理を繰り返し行う（ステップ５１０）　
、次に、検索処理部４０２は、全ての要素の比較が終了
した時点で、限定述語の真偽判定を行う（ステップ５１
１）。いずれかの評価が真であれば真、それ以外は偽と
する０次に、検索処理部４０２は、限定述語以外の評価
結果と限定述語の評価結果をまとめて評価し、該当行が
条件を満足するか否かを判定しくステップ５１２）、満
足する行を検索結果レジスタ４２４に格納する（ステッ
プ５１３）、次に、検索処理部４０２は。 表４２２から次の行を取り出し、取り出す行がなくなる
まで、ステップ５０４以降を繰り返し行う（ステップ５
１４）。 このようにして、限定述語を含む検索処理が実行される
。なお、主問合せの検索対象の表４２２からは、全ての
行を取り出す必要がなく、限定述語以外の述語が限定述
語とＡＮＤで結合されている場合には、限定述語以外の
評価結果が真である行のみが限定述語の評価対象となる
。 〔発明が解決しようとする課題］ 第４図および第５図に示すような従来の限定述語処理方
法では、副問合せの結果の要素がＮ個の場合、限定述語
を含む述語の評価は副問合せの結果の各要素に対して比
較演算子が満足するか否かを判定しているので、評価に
かかる時間は副問合せの結果の要素数Ｎに比例して増加
する。すなわち、限定子がＡＮＹ／ＳＯＭＥの場合、平
均Ｎ／２かかることになり、また限定子がＡＬＬの場合
にも、平均Ｎ／２だけかかることになる。その結果、評
価対象の行数がＭの場合には、限定述語の評価時間は、
ＭＸＮ／２だけ必要となるため、全体の処理時間は極め
て長くなってしまう。 本発明の目的は、このような従来の課題を解決し、主問
合せの各行の列と副問合せ結果の要素との比較回数を削
減し、限定述語処理を高速に実行できる関係データベー
スの限定述語処理方法を提供することにある。

【課題を解決するための手段】

上記目的を達成するため１本発明による関係データベー
スの限定述語処理方法は、関係データベースの問合せ中
、列名、比較演算子、限定子および副問合せの形式で表
現され、上記限定子の種類により副問合せの結果の要素
の任意の１つないし全ての４＋（ｉと主問合せ列の値と
比較し、比較演算子の条件を満足するか否かを判定する
限定述語処理システムにおいて、上記比較演算子が＝、
上記限定子がＡＮＹの場合に、副問合せ結果に対して同
じ値を持つ要素の除去とソートを行い、また主問合せの
行に対して副問合せ結果の要素以外の列の値を持つ行の
削除と限定述語で指定された列でのソートを行った後、
主問合せ結果の各行の列の値と副問合せ結果の要素とを
比較することに特徴がある。 【作　　用Ｊ 本発明においては、主問合せの各行の限定述語で指定さ
れた列と、副問合せ結果の要素との比較を行う前に、副
問合せ結果に対して重複して同じ値を持つ要素を除去す
るとともに、ソートを行い、かつ主問合せの行から副問
合せ結果の要素以外の列の値を持つ行を除去し、限定述
語で指定された列でのソートを行う、これにより、主問
合せの各行の列と副問合せ結果の要素との比較回数を削
減することができるので、限定述語処理を高速かつ能率
的に行うことが可能である。 【実施例］ 以下、本発明の実施例を、図面により祥細に説明する。 第１図は、本発明の一実施例を示す関係データベース検
索システムの構成図であり、第３図は第１図における限
定述語処理の動作フローチャートである。 第１図において、１０１は検索条件を作成するためのプ
ログラムを備えた検索条件作成部、１０２は検索処理プ
ログラムを備えた検索処理部、１０３は副問合せ結果に
対して重複して同じ値を持つ要素の除去とソートを行う
プログラムを備えた重複除去・ソート部、１０４は主問
合せの行から副問合せ結果の要素以外の列の値を持つ行
の除去と限定述語で指定された列でのソートを行うプロ
グラムを備えたふるい落とし・ソート部、１０５は限定
述語を判定するプログラムを備えた限定述語判定部、１
１０は検索命令、Ｉｌｌは副問合せの表の条件式、１１
２は主問合せの表の条件式、１’２１は副問合せで検索
する表、１２２は主問合せで検索する表、１２３は副問
合せ結果を格納するスタック、１２４は主問合せ結果を
格納するスタック、１２５は副問合せ結果の重複除去・
ソートした結果を格納するスタック、１２６は主問合せ
結果のふるい落とし・ソートした結果を格納するスタッ
ク、１２７は検索結果を格納するスタックである。 第１図を第５図と比較すれば明らかなように、本発明で
は、新たに重複除去・ソート部１０３とふるい落とし・
ソート部１０４と、それらの結果および対象を格納する
ための副問合せ結果の重複除去・ソート結果格納スタッ
ク１２５と主問合せ結果のふるい落とし・ソート結果格
納スタック１２６と主問合せ結果格納スタック１２４と
、限定述語判定部１０５を設けている。 第３図により、本発明の限定述語処理の手順を説明する
。 先ず、検索条件作成部１０１が検索命令１１０から副問
合せで検索する表１２１に対する条件式Ｉｌｌを作成す
る（ステップ３０１）、次に、検索処理部１０２は、副
問合せで検索する表１２１に対する条件式１１１を評価
して、その結果を副問合せ結果スタック１２３に格納す
る（ステップ３０２）０次に、重複除去・ソート部１０
３において、副問合せ結果スタック１２３から重複して
同じ値を持つ要素を除去し、かつソートを行い、副問合
せ結果の重複除去・ソートした結果スタック１２５に格
納する（ステップ３０３）０次に、検索条件作成部１０
１は、検索命令１１０から主問合せでＭ索する表１２２
に対する条件式（限定述語を除＜）ｌ　ｌ　２を作成す
る（ステップ３０４）、検索処理部１０２は、主問合せ
で検索する表１２２に対する条件式１１２を評価して、
その結果を主問合せ結果スタック１２４に格納する（ス
テップ３０５）、次に、ふるい落とし・ソート部１０４
は、副問合せ結果の重複除去・ソートした結果スタック
１２５を参照して、主問合せ結果スタック１２４から副
問合せ結果の要素以外の列の値を持つ行の除去とソート
を行い、主問合せ結果のふルい落とし・ソートした結果
スタック１２６に格納する（ステップ３０６）、限定述
語判定部１０５は、主問合せ結果のふるい落とし・ソー
トした結果スタック１２６の行の限定述語で指定された
列の値と、副問合せ結果の重複除去・ソートした結果ス
タック１２５の要素を比較することにより、限定述語の
判定を行い（ステップ３０７）、満足するスタック１２
６中の行を検索結果スタック１２７に格納する（ステッ
プ３０８，３０９）。 このようにして、少ない比較回数で限定述３／１処理を
行うことができるので、処理時ｍノの短縮が可能となる
。 第２図は、第１図による限定述語処理の具体例を示す図
である。 第２図において、２０１は検索条件作成部、２０２は検
索処理部、２０３は重複除去・ソート部、２０４はふる
い落とし・ソート部、２０５は限定述語判定部、２１０
は検索命令、２１１は副問合せの表の条件式、２１２は
主問合せの表の条件式、２２１は副問合せが検索する表
、２２２は主問合せが検索する表、２２３は副問合せ結
果、２２４は主問合せ結果、２２５は副問合せ結果の重
複除去・ソート結果、２２６は主問合せ結果のふるい落
とし・ソート結果、２２７は検索結果である。 検索命令は、以下に示すものを用いて行われたものとす
る。 ５ＥＬＥＣＴ本 ＦＲＯＭ　　　　会社 ＷＨＥＲＥ　　　地区＝“東京’　ＡＮＤ社番社格ＮＹ
（ＳＥＬＥＣＴ社番 ＦＲＯ社格　　ｆｆ１１品 ＷＨＥＲＥ　　在車≦５０） この検索命令は、部品表の中から在１ｄｌが５０以下の
部品を仇給する会社に関する情報を会社から返却するこ
とを示している。 限定述語の処理は、第３図に従って、次の順序で行われ
る。 （ｉ）先ず、検索条件作成部２０１では、検索命令２１
０から副問合せで検索する表２２１（部品表）に対する
条件式２１１を作成する（ステップ３１）。 （１ｉ）検索処理部２０２では、副問合せで検索する表
２２１に対する条件式２１１を評価して、その結果を副
問合せ結果スタック２２３に格納する（ステップ３０２
）、すなわち、表２２１で在車が５０以下のもは電池と
ソケットと電球の３種であり、その社番は２と３である
ため、スタック２２３には、社格２．３．２が格納され
る。 （ｉｉｉ）次に、ｆｆｉｆ重複除去−ト部２０３では、
副問合せ結果２２３から重複して同じ値を持つ要素の除
去を行うとともに、ソートを行い（社格２を除去）、副
問合せ結果の重複除去・ソートした結果２２５にこれら
を格納する（ステップ３０３）。 （ｉｖ　）検索条件作成部２０１で、検索命令２１０か
ら主問合せで検索する表２２２に対する条件式（限定述
語を除＜）２１２を作成する（ステップ３０４）、すな
わち、地区が東京の会社を返却する検索条件である。 （ｖ）検索処理ｒｆｒＪ２０２では、主ｒｍ合せで検索
する表２２２に対する条件式２１２を評価して、主問合
せ結果２２４に格納する（ステップ３０５）、すなわち
、格納された会社は１社番が３のＢ社と、社格が４の０
社と、社格が２のＤ社である。 （ｖｉ）ふるい落とし・ソート部２０４では、副問合せ
結果の重複除去・ソートした結果２２５を参照して、主
問合せ結果の表２２４から副問合せ結果の要素以外の列
の値を持つ打の除去（社格４の行の除去）とソートを行
い、その結果を主問合せ結果のふるい落とし・ソートし
た結果２２６に格納する（ステップ３０６）。 （Ｖｉｉ）限定述語判定部２０５では、主問合せ結果の
ふるい落とし・ソートした結果２２６の行の限定述語で
指定された列の値と、副問合せ結果の重複除去・ソート
した結果２２５の要素を比較することにより、限定述語
の判定を行い（ステップ３０７）、満足する行がどれか
を調べ（ステップ３０８）、結果２２６の中の満足する
行（社格２と３）を検索結果２２７に格納する（ステッ
プ３０９）。 このようにして、部品表の中から在庫が５０以下の部品
を供給する会社を検索することができた。 次に、本発明による限定述語の処理において、比較演算
子が＝、限定子がＡＮＹの場合、副問合せ結果の要素数
をＭ１要素の重複度（全要素数と異なる値を持つ要素数
との比≧１）をＤ、主問合せの行数をＮ１ふるい落とし
率（全行数と副問合せ結果の要素と同じ値を持つ行数の
比≧１）をＳとすると、比較回数は次のようになる。 すなわち、従来の方法では、前述のように平均比較回数
Ａ、は、Ａ、＝ＭＸＮ／２であるのに対して、本発明で
は、平均比較回数Ａ１が、Ａ、＝　（Ｍ／Ｄ）＋（Ｎ／
Ｓ）である。 本発明の値が従来の値よりも小さいことを確認するため
に、Ａ、をＡ、で除算すると、次の値になる。 Ａ、ＮＤＭＳ 本発明による比較回数が従来方法の回数よりも少なくな
るのは、Ｄ＝Ｓ＝１の時で、Ｍ、Ｎ）４のときであるが
、−股間にはＭ）１０．Ｎ）１００程度であるため、限
定述語処理時間の短縮が図れる。 〔発明の効果Ｊ 以上説明したように、本発明によれば、主問合せの各行
の限定述語で指定された列と１．副問合せ結果の要素と
を比較する前に、副問合せ結果に対して重複して同じ値
を持つ要素の除去とソート、主問合せの行から副問合せ
結果の要素以外の列の値を持つ行の除去と限定述語で指
定された列でのソートを行うので、主問合せの各行の列
と副問合せ結果の要素との比較回数を削減することがで
き、従って限定述語処理を高速に行うことが可能である
。

【図面の簡単な説明】

ｆｔ５１図は本発明の一実施例を示す関係データベース
検索システムの機能ブロック図、第２図は第１図におけ
る具体例を示す説明図、第３図は第１図における限定述
語処理の動作フローチャート、第４図は従来の関係デー
タベース検索システムの機能ブロック図、第５図は第４
図における限定述語処理の動作フローチャートである。 １０１．２０１，４０１　：検索条件作成部、１’０２
，２０２，４０２　：検索処理部、１０３゜２０３＝重
複除去・ソート部、１０４，２０４：ふるい落とし・ソ
ート部、１０５，２０５：限定述語判定部、１１０，２
１０，４１０：検索命令、Ｉｌ！、２１１，４１１：周
問合せの表の条件式、１１２．２１２，４１２：主問合
せの表の条件式、１２１．２２１，４２１　：副問合せ
で検索する表、１２２．２２２，４２２：主問合せで検
索する表、１２３．２２３，４２３：副問合せ結果の要
素群、１２４．２２４：主問合せ結果スタック、１２５
゜２２５＝副問合せ結果の重複除去・ソート結果スタッ
ク、、１２６，２２６：主問合せ結果のふるい落とし・
ソート結果スタック、１２７，２２７゜４２４：検索結
果スタック。

Claims (1)

【特許請求の範囲】
1. （１）関係データベースの問合せ中、列名、比較演算子
   、限定子および副問合せの形式で表現され、上記限定子
   の種類により副問合せの結果の要素の任意の１つないし
   全ての値と主問合せ列の値と比較し、比較演算子の条件
   を満足するか否かを判定する限定述語処理システムにお
   いて、上記比較演算子が＝、上記限定子がＡＮＹの場合
   に、副問合せ結果に対して同じ値を持つ要素の除去とソ
   ートを行い、また主問合せの行に対して副問合せ結果の
   要素以外の列の値を持つ行の削除と限定述語で指定され
   た列でのソートを行った後、主問合せ結果の各行の列の
   値と副問合せ結果の要素とを比較することを特徴とする
   関係データベースの限定述語処理方法。