JPH07105223A - データベース検索装置 - Google Patents

Abstract

(57)【要約】 【目的】 検索条件が複数のキーの論理積を含む場合に
可能な限り検索時間を短縮することができる。 【構成】 データベース作成時に予め同一のキーを持つ
ものの出現回数をキーの内容と対応させて蓄積してお
く。論理積を含む検索条件が入力された場合には、検索
キーについてそれぞれキー数表示部１２を参照し、その
キーの出現件数を調べる。そして、出現件数の少ないキ
ーから順番に検索を行い、早期にデータの絞り込みをす
る。アンド条件を用いて結合されたキーは検索順序を入
れ換えても結果は同じであるから、このように検索命令
を書き換えて検索処理部５によるデータの検索処理を高
速化できる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、情報処理装置を用いて
データベースを検索する場合の検索速度の向上を図った
データベース検索装置に関する。

【０００２】

【従来の技術】多量の情報を蓄積して利用するために、
情報処理装置を用いたデータベース検索装置が広く使用
されている。図２に、一般のデータベース検索装置ブロ
ック図を示す。この装置は、データベース６を検索する
ための検索条件入力部１に、ディスプレイ２と、キーボ
ード３とマウス４を備えている。また、このような検索
条件を用いて検索処理を実行するために検索処理部５が
設けられている。検索対象となるデータベース６はハー
ドディスク等の大容量記憶装置に格納されている。な
お、検索処理部５は具体的にはマイクロプロセッサや入
出力装置等から成るパーソナルコンピュータやワークス
テーションから構成される。

【０００３】このようなデータベース６に蓄積された情
報を利用しようとする場合には、キーボード３やマウス
４を用いてデータを取り出すためのキーを入力し、検索
処理部５はこのキーが一致したデータをデータベース６
から検索し、ディスプレイ２に表示する。上記のような
データベース検索装置の構成として、リレーショナルデ
ータベースシステムが知られており、このシステムでは
検索作業を容易にするためにＳＱＬ言語が採用されてい
る。

【０００４】図３に、上記のようなデータベースの一例
として住所録のデータベース例説明図を示す。データベ
ースは、例えばこの図に示すように、氏名、住所、年
齢、職業、電話番号、性別といった項目（これを属性名
という）に対応する内容を組み合わせて構成される。

【０００５】図４に、データベース検索命令説明図を示
す。ＳＱＬ言語により検索条件を記述すると、例えばこ
の図に示すようになる。即ち、この図では、住所録とい
う表から、住所が東京都で、性別は男で、年齢は３０歳
という条件を満たすデータを読み出し、その氏名と電話
番号を求めるという内容の命令である。図２に示すデー
タベース検索装置は、このような要求を受け入れると、
命令文を先頭から順に解析し、まず住所が東京都である
レコードを選択し、その中で性別が男であるレコードを
選択し、最後に年齢が３０であるレコードを選択する。
その結果、図３に示す住所録の５番目のレコードが出力
として取り出される。

【０００６】

【発明が解決しようとする課題】ところで、上記のよう
な従来のデータベース検索装置には次のような解決すべ
き課題があった。上記のようなＳＱＬ言語によるデータ
ベース検索命令は、図４に示したような形式で記述さ
れ、その記述された順番に検索が実行される。即ち、図
４に示す例では、住所と性別と年齢について順に検索キ
ーが指定されているが、検索はその記述順に住所、性
別、年齢というように実行される。

【０００７】しかしながら、例えば図３に示す住所録の
データベースにおいて、住所が東京都に該当するレコー
ドが極めて多い場合には、最初のキーを用いた検索では
データベース全体の量に比べてあまり絞り込みを行なう
ことができない。即ち、その次のキーである性別による
選択の対象は住所のキーが東京都であるレコード全体と
なる。これには１回目の検索処理とそれほど変わらない
検索時間が必要となる。これは一般にセレクタビリティ
が悪いというように表現され、検索速度が遅くなる原因
となる。

【０００８】例えばデータベース全体の７０パーセント
が、住所が東京都であるというキーに合致したレコード
であり、５０パーセントが性別が男であるというキーに
合致したものであるとすれば、性別が男であるというキ
ーについての検索を先に行なえば、その後の検索対象が
データベース全体の２分の１に絞り込める。また、年齢
が３０というキーを最初に用いて検索を行なえば、更に
十分な絞り込みを１回で行ない、その後の検索時間を短
縮できる場合がある。

【０００９】従って、オペレータは上記のようなアンド
条件、即ち検索条件が複数のキーの論理積を含むような
場合に、どのキーを最初に検索に用いると検索時間が短
縮されるかをある程度予測してＳＱＬ言語を作成するよ
うにすることが好ましい。しかしながら、これでは、デ
ータベースの内容を認識している者と、データベースの
内容を知らない者との検索処理時間が大きく相違してし
まう。

【００１０】本発明は以上の点に着目してなされたもの
で、検索条件が複数のキーの論理積を含む場合に可能な
限り検索時間を短縮することができるデータベース検索
装置を提供することを目的とするものである。

【００１１】

【課題を解決するための手段】本発明のデータベース検
索装置は、データベース中に格納されたデータのうち同
一のキーをもつものの出現件数を、各キーの内容と対応
させて表示するキー数表示部と、前記データベースの検
索条件を入力する検索条件入力部と、前記検索条件が複
数のキーの論理積を含む場合に、前記キー数表示部を参
照して、入力された検索条件中に含まれる複数のキーの
前記出現件数を読み取り、入力された検索条件に従って
検索を実行する場合に、前記出現件数の少ないキーを優
先して検索を実行するように検索順を設定する検索順設
定部を備えたことを特徴とするものである。

【００１２】

【作用】この装置では、データベース作成時に予め同一
のキーを持つものの出現回数をキーの内容と対応させて
蓄積しておく。論理積を含む検索条件が入力された場合
には、検索キーについてそれぞれキー数表示部を参照
し、そのキーの出現件数を調べる。そして、出現件数の
少ないキーから順番に検索を行い、早期にデータの絞り
込みをする。アンド条件を用いて結合されたキーは、検
索順序を入れ換えても結果は同じであるから、このよう
に検索命令を書き換えてデータの検索処理を高速化でき
る。

【００１３】

【実施例】以下、本発明を図の実施例を用いて詳細に説
明する。図１は、本発明のデータベース検索装置実施例
を示すブロック図である。この装置は、従来装置同様
に、ディスプレイ２やキーボード３、マウス４等を用い
て検索条件入力部１を構成する。また、データベース６
を検索するために、キー数解析部１１、キー数表示部１
２、検索順設定部１３及び検索処理部５を設ける。

【００１４】検索条件入力部１は検索条件をＳＱＬ言語
を用いて入力し、検索結果をディスプレイ２に表示する
といった操作を行なう部分である。なお、本発明の装置
は、データベース６を利用するアプリケーションがこの
ような検索用の言語を直接自動的に入力するような構成
としても差し支えない。キー数解析部１１は、データベ
ース６を生成し、蓄積し、あるいは更新する場合等に、
本発明の実施に必要なキー数表示部１２を生成する処理
を行なう部分である。

【００１５】図５に、キー数表示部の内容説明図を示
す。本発明において、例えば図３に示すような住所録の
データベースを生成する場合には、予めその生成の際
に、同一のキーを持つものの出現件数をそのキーの内容
と対応させてキー数表示部に登録する。

【００１６】例えば、この図に示すように、住所録とい
う表では、属性名が住所で属性値が東京都であるもの
は、そのデータ入力累積件数が 9,000というように表示
されている。また、属性名が年齢の場合、その属性値が
２０というものの出現件数は 1,500件というように表示
されている。このような内容のデータをキー数表示部１
２に格納しておく。キー数解析部１１はこのキー数表示
部１２を生成するために、例えば図６に示すような動作
を実行する。

【００１７】図６は、キー数解析部の動作フローチャー
トである。まず、始めにステップＳ１において、入力デ
ータを受け付ける。この入力データは、例えば図１に示
す検索条件入力部１から入力されたり、あるいは他の情
報処理装置から転送されるものとする。

【００１８】ここで、図６のステップＳ２において、キ
ー数表示部の作成が新規であるかどうかを判断する。即
ち、キー数表示部が全く生成されていない場合には、ス
テップＳ３に移り、表の定義を元に図５に示した要領で
キー数表示部の枠組みを作成する。図５に示すような形
式のキー数表示部が既に作成されていれば、ステップＳ
２からステップＳ４に移り、入力データの全ての項目に
ついて処理が終了したかどうかを判断する。

【００１９】まず、入力データの処理の内容について、
ステップＳ５において、そのデータが更新か挿入かを判
断する。更新であれば古いデータに関する件数を減らす
（ステップＳ６）。挿入であれば、直接ステップＳ７に
移り、新データに対応する件数を増やす。

【００２０】即ち、例えば図５に例示した住所録に関す
るキー数表示部のデータで、年齢が２０の入力データを
受け付けた場合に、これが元のデータを更新するような
ものであれば、一旦出現件数 1,500から１を引算する。
そして、ステップＳ７において、新たにこの件数 1,500
に１を加える。一方、新しいデータを追加挿入するよう
な場合には、元の出現件数 1,500に１を加える。以上の
ようにして図１に示すキー数解析部１１はキー数表示部
１２の各出現件数を累積しながら更新する。

【００２１】次に、図１に示す検索順設定部１３の動作
を説明する。この検索順設定部１３はキー数表示部１２
を参照しながら、データベース検索命令の検索キーの順
番を検索速度が最も速くなるように置き換える。図７
に、上記のような検索順設定部１３の動作及びその後の
検索処理部５の動作を説明するフローチャートを図示し
た。

【００２２】まず、ステップＳ１において、検索順設定
部１３が検索条件入力部１から検索条件を受け付ける。
そして、ステップＳ２において、アンドで結ばれた複数
の条件が含まれているかどうかを判断する。本発明にお
いては、検索条件が複数のキーの論理積を含む場合に有
効であって、全てが論理和の場合には効果がない。ステ
ップＳ３において、まず、条件数分の処理を繰り返した
かどうかを判断する。即ち、全てのキーについての処理
を処理を終了したかどうかを判断する。そして、未だ終
了していなければステップＳ４に移り、１つのキーを取
り出し、まずキー数表示部１２を参照してこの条件に合
致するキーの出現件数を求める。

【００２３】次に、ステップＳ３に移り、再び全てのキ
ーについての処理が終了したかを判断する。即ち、この
ステップＳ３、Ｓ４において、全てのキーについて、そ
の出現件数を求めた上で、ステップＳ５に移る。今度
は、ステップＳ５で、出現件数の少ない順にそれぞれの
キーを用いた検索式を並べ換える。即ち、最も出現件数
の少ないキーを最初に検索し、その後その次に出現件数
の多いキーを用いた検索を行なうといった要領で、複数
の検索キーを並べ換える。

【００２４】図８に、書き換えられた検索命令文説明図
を示す。検索順設定部１３は、具体的には、この図に示
すように、図４に示したような検索命令の住所、性別、
年齢といったキー順を、年齢、性別、住所という順番に
置き換えている。その後、この命令文が従来と同様の構
成の検索処理部５に供給され、図７ステップＳ６におい
て、実際の検索が実行される。

【００２５】図９に、本発明の効果の説明図を示す。図
９（ａ）に示したとおり、一定の量のデータベースにつ
いて条件Ａと条件Ｂとがアンド条件で結ばれているよう
な場合、条件Ａに合致する件数が非常に多いと、次の条
件Ｂでの絞り込みはこの条件Ａに合致した件数のレコー
ドが対象となる。これに対し、図９（ｂ）に示すよう
に、条件Ｂに合致するレコード件数が条件Ａに合致する
レコード件数よりも少ない場合には、始めに条件Ｂのキ
ーを用いて検索することにより十分対象件数を絞り込
み、更に条件Ａを用いて検索を実行するため、２回目の
検索対象件数が減少し、検索速度の向上が図られる。

【００２６】例えば、図４や図８の検索式による検索対
象となるデータベースの元データ件数が10,000件であっ
たとする。この場合に、図５に示すように、東京都とい
うキーの出現回数は 9,000件で９０パーセント、性別が
男であるキーの出現件数は５０パーセント、年齢が３０
であるキーの出現件数は１０パーセントとなっている。
従って、図４に示すような検索文で検索を実行すると、
始めの検索で10,000件を検索し、住所が東京都というデ
ータを 9,000件に絞り、次の性別の検索によりこれを
4,500件に絞り、最後に年齢を検索して 450件を抽出す
る。従って、この間のデータベースによる検索処理は1
0,000＋ 9,000＋ 4,500となり、合計23,500件分のキー
比較を行なうことになる。

【００２７】一方、本発明の装置によれば、予め検索順
を入れ換え、最初の検索で10,000件について年齢が３０
のものを抽出し 1,000件に絞り、次の性別の検索により
これを 500件に絞り、最後の住所の検索によって 450件
を抽出する。従って、この場合、10,000＋ 1,000＋ 500
となり、11,500件のキー比較によって検索処理が終了す
る。この結果、検索回数は従来装置による場合と本発明
の装置による場合とでは半分以下となる。しかも、本発
明の装置はキー数表示部を参照することによって検索条
件の最適化を行なうため、データベースの内容をよく知
っているものも、また知らないものも常に自動的に最適
の条件を選択して検索を実行することが可能になる。

【００２８】本発明は以上の実施例に限定されない。上
記実施例では、検索条件入力部とデータベースを１個ず
つ設けたシステムを示したが、複数の検索条件入力部が
存在し、あるいは多数のデータベースが通信回線等を介
して接続された大規模なシステムにも採用が可能であ
る。検索処理は、ディスプレイやキーボード等を用いた
ターミナルによる場合の他、その他のアプリケーション
プログラム等による自動的な処理でも差し支えない。

【００２９】また、検索条件を設定するためのデータベ
ース検索命令文は必ずしもＳＱＬ言語による必要はな
い。キー数表示部の構成は、同一のキーについて何件の
データが存在するかを表すものであればどのような形式
のものであってもよい。また、キー数表示部にはデータ
ベースの全てのキーを格納する必要はなく、検索速度向
上に役立つような比較的頻繁に使用されるキーのみを選
択して登録表示するようにしてもよい。

【００３０】出現件数の少ないキーを優先して検索を実
行する場合に、検索文自体を書き換えなくても、検索文
はそのままにし、検索順のみを最適化するようにしても
よい。更に、順序を入れ換えても検索速度の改善が著し
くないような場合には、必ずしも全ての検索順を最適化
する必要はない。また、出現件数をキー数表示部に登録
する方法は、新たにデータを１件分入力する度に行なう
方法の他、登録済みのデータベースを一定のプログラム
によって検索処理して集計するようにしても構わない。

【００３１】

【発明の効果】以上説明した本発明のデータベース検索
装置は、データベース中に格納されたデータのうち同一
のキーを持つものの出現件数を各キーの内容と対応させ
て表示するキー数表示部と、データベースの検索条件が
複数のキーの論理積を含む場合に、キー数表示部を参照
して入力された検索条件中に含まれる複数のキーの出現
件数を読み取り、出現件数の少ないキーを優先して検索
を実行するように検索順を設定する検索順設定部を設け
るようにしたので、任意に複数のキーをアンド条件で結
んで検索要求をした場合に、自動的に検索順が最適化さ
れ、検索処理時間を短縮することができる。

【図面の簡単な説明】

【図１】本発明のデータベース検索装置実施例を示すブ
ロック図である。

【図２】一般のデータベース検索装置ブロック図であ
る。

【図３】データベース例説明図である。

【図４】データベース検索命令文説明図である。

【図５】キー数表示部の内容説明図である。

【図６】キー数解析部の動作フローチャートである。

【図７】本発明の装置の動作フローチャートである。

【図８】書き換えられた検索命令文説明図である。

【図９】本発明の効果の説明図である。

【符号の説明】

１ 検索条件入力部 ５ 検索処理部 ６ データベース １１ キー数解析部 １２ キー数表示部 １３ 検索順設定部

Claims (1)

【特許請求の範囲】
1. 【請求項１】 データベース中に格納されたデータのう
   ち同一のキーをもつものの出現件数を、各キーの内容と
   対応させて表示するキー数表示部と、 前記データベースの検索条件を入力する検索条件入力部
   と、 前記検索条件が複数のキーの論理積を含む場合に、前記
   キー数表示部を参照して、入力された検索条件中に含ま
   れる複数のキーの前記出現件数を読み取り、入力された
   検索条件に従って検索を実行する場合に、前記出現件数
   の少ないキーを優先して検索を実行するように検索順を
   設定する検索順設定部を備えたことを特徴とするデータ
   ベース検索装置。