JPH01171021A - ソート処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、入力データの大小関係に基づいて高速にソー
トするソート処理装置に関し、より詳細には、入力デー
タ中に大小関係の判定過程で一致と判定される重複デー
タが存在した場合に、重複しているデータの個数をソー
ト処理中に計数する機能を実現したソート処理装置に関
する。

〔従来の技術〕

一般に、データベース処理で扱うデータをレコードと称
しているが、該レコードは複数の異なる属性を持つカラ
ムから構成されている。従って。

データベース処理では、通常、横方向にカラムを縦方向
にレコードを並べた表形式のデータを処理の対象とする
こと−なる。この表形式をしたデータ自体をデータベー
ス（関係データベース）と称している。

データベース処理では、レコードの件数が極めて大きい
データベースや、複数の異なる情報を持つデータベース
を処理の対象とすることから、汎用の電子計算機で処理
すると膨大な時間を必要とする場合が多い。このため、
データベース処理の一部あるいは全体を直接ハードウェ
アで実行し。

高速化する方法が知られている。特に、データベース処
理の高速化に効果があるソート処理装置の開発が盛んに
進められており、専用ハードウェアで構成したソート処
理装置は、例えば特開昭６１−４２０３１号公報に示さ
れている。

この様な専用ソート処理装置を用いて、あらかじめ対象
とするデータベースを所望の規則でソートしておくこと
により、選択、射影、併合等のデータベース処理を大幅
に高速化できる。ニジで。

選択、射影、併合は次のような処理を云う。

選択：入力データベースの特定のカラムの内容が所望の
値を満足するレコードを抽出する。一般に、出力データ
ベースのレコード数は入力レコード数より削減されるが
、各レコードの構成は変わらない。

射影：入力データベースの特定のカラムだけを抽出して
、出力データベースを作成する。

この場合には、各レコードともカラム数が削減されるこ
とから、一般に、出力データベース上に全く同一の内容
を持つ複数のレコードが生成される可能性がある。

同一の内容を持つレコード即ち重複レコードが同一デー
タベース上に存在すると。

選択処理や併合処理で矛盾を生ずることから、一般には
重複レコードは、１個のレコードとして重複除去を行う
。

併合：２種類のデータベースを入力として、所・望のカ
ラムの値が等しいレコードを結合して、新たなレコード
する。従って、新たに生成されるデータベースは、入力
したデータベースよりレコード長が長くなるのが一般的
である。この場合、入力データベースに重複レコードが
存在すると、出力データベース中には、更にたくさんの
重複レコードが生成され、矛盾が生ずる。

これらのデータベース処理では、あらかじめ入力するデ
ータベースを必要なカラムでソートしておくことにより
、全体の処理時間を大幅に短縮できる。特に、併合処理
では、２種類のデータベースをレコード単位で相互に照
合し、対応するカラムの一致を検査することから、あら
かじめソートしておくことによって、格段に処理時間を
短縮できる。

〔発明が解決しようとする問題点〕

従来の専用ソート処理装置を用いて、あらかじめ処理対
象とするデータベースをソートしておくことによって、
処理の高速化が図れる。しかし、特定のカラムに着目し
てレコードを分類する様な処理、例えば１名前、性別、
年齢の３種類のカラムを持つレコードからなるデータベ
ースを入力として、年齢順のヒストグラムを作成するよ
うな処理は、選択処理の繰返しで実現できるが、この場
合には、分類する場合の数だけデータベースを参照する
必要があるため、膨大な処理時間を必要とする問題があ
った。

また、専用のソート処理装置を用いて予め年齢順にソー
トしてから計数処理を行う場合でも、−般のデータベー
ス処理にみられる重複レコードの除去は、計数処理を行
う以前に実行することはできない。このため、対象とす
るレコード数が大きく重複レコードの比率が高い場合で
あっても、ソート処理と計数処理を独立に行う従来の方
法では、入力レコード数と等しい数のレコードを出力し
なければならず、ソート処理装置の入出力時間だけでも
膨大な時間を必要とする問題があった。

さらに１分類する場合の数が対象とするデータに依存す
る場合には、あらかじめ分類する範囲を設定できない為
、あらかじめ対象とするデータベースを重複レコードを
除去しないようにソートした後に、分類する範囲を変え
ながら計数する処理を繰返さなければならず、ヒストグ
ラムを作成する際に必要な計数処理を高速化することが
困難であった。

本発明は、上記従来技術の問題点を除去することを目的
とし、ソート処理実行中に重複レコードの計数処理を行
う高速なソート処理装置を提供することにある。

〔問題点を解決するための手段〕

上記目的は、入力レコードを相互に比較し、レコードの
大小関係に基づいて並べ替えを行い、昇順あるいは降順
にレコードを出力するソート処理手段と、レコード相互
の比較によって、２個以上のレコードが一致しているこ
とをソート処理中に検出して重複と判定する重複検出手
段と、該重複検出手段で重複と判定されたレコードの個
数を計数する計数手段を設け、ソート処理中に重複レコ
ードの検出と該重複レコードの計数とを同時に行うこと
によって達成される。

〔作　用３ ソート処理中に重複レコードの検出と該重複レコードの
計数を同時に実行する。この場合、ソート対象とする個
々のレコードに計数結果を格納する計数カラムをあらか
じめ付加して、重複レコードの計数結果を計数カラムに
格納する。これにより、誤動作することがないように、
ソート処理の実行過程で不要な重複レコードを除去する
ことが出来る。

〔実施例〕

以下、本発明の一実施例について図面により説明する。

第１図は本発明のソート処理装置の一実施例を示す構成
図である。図中、１１は昇順／降順に入力レコードを並
べ替えるソート回路である。１２はソート回路１２から
の出力レコード１個を格納するバッファ回路である。１
３はソート回路１１とバッファ回路１２とから出力され
るレコードを比較する比較回路である。１４は計数回路
であり。

重複レコード数をカウントする。１５はソートされたレ
コードを出力する出力回路である。１６は本ソート処理
装置に入力するレコード或いは出力されるレコードを格
納するためのバッファメモリである。

第２図は本ソート処理装置で扱うレコードの構成例を示
す図であり、外部から入力されたレコード本体２１に、
重複レコードが検出された場合に計数値を格納するため
の計数カラム２２を付加して一つのレコード２０とする
。計数カラム２２を付加する位置は、ソートする際に該
計数カラムの内容によってソート順序に影響がないよう
に、レコード２０の最後部に付与する。

次に、第１図の動作を説明する。ソート回路１１は、バ
ッファメモリ１６にあらかじめ格納されている入力レコ
ードについて、キー人力で示されたソート処理を行い、
昇順或いは降順に整列して出力する。この種ソート回路
自体は周知であるので、その詳細は省略する。ソート回
路１１から出力されるレコードは第２図に示す構成をと
る。このソート回路１１から出力されるレコード２０を
、バッファ回路１２でルコード分保持する６次にソート
回路１１からレコード２０が出力されると。

該レコード２０がバッファ回路１２に保持され、それま
でバッファ回路１２に保持されていたレコード２０はバ
ッファ回路１２から出力される。この時、比較回路１３
は、ソート回路１１から出力されるレコード２０とバッ
ファ回路１２から出力されるレコード２０について、そ
のレコード本体２１を比較し、ソート回路１１から連続
して出力されるレコード本体２１が一致しているか否か
判定し、一致検出信号を出力する。

両者のレコード本体２１が一致している場合、計数回路
１４は、バッファ回路１２から出力されたレコード２０
の計数カラム２２の内容と、ソート回路１１から出力さ
れてバッファ回路１２に格納されるレコード２０の計数
カラム２２の内容とを加算し、該加算結果をバッファ回
路１２内のレコード、即ち、あとにソート回路１１から
出力されたレコード２０の計数カラム２２に設定する。

また、ソート回路１１から出力されるレコード２０のレ
コード本体２１とバッファ回路１２から出力されるレコ
ード２０のレコード本体２１が一致している場合、該重
複レコードの出力を抑止するために、比較回路１３から
の一致検出信号で出力回路１５を制御して、重複レコー
ドを出力しないようにする。

比較回路１３で一致が検出されない場合、バッファ回路
１２から出力されたレコード２０は、出力回路１５を通
り、ソート結果として外部へ出力されるか、あるいは以
後のソート処理のためにバソファメモリ１６に再格納さ
れる。

第３図は２個のレコード列を入力として、計数処理を行
いながら１個のレコード列としてマージして出力する例
を示したものである。マージ処理はソート回路１１で行
う。図中、第１のレコード列は（ＡＡＣ：　１．ＡＢＣ
：　３．ＡＢＤ：　３．・・・）であり、第２のレコー
ド列は（ＡＡＣ：　１．ＡＢＣ：　２．ＡＣＡ：　２．
・・・）であり、出力レコード列は（ＡＡＣ：　２．Ａ
ＢＣ：　３．ＡＢＤ：　５．・・・）である。数字は計
数カラムの内容であり、レコード本体が同一な重複レコ
ードの個数を表している。

第３図の例では、４個のレコードからなる第１のレコー
ド列と、４個のレコードからなる第２のレコード列をマ
ージし、第１および第２のレコード列に共通に含まれて
レコード（ＡＡＣ，ＡＢＤ。

ＡＣＢ）を重複レコードと判定し、各々の計数カラムの
値を加算して、新たな計数値を出力レコード中に設定し
ている。同時に重複レコードの除去を行っており、第１
および第２の８個の入力レコードに対して出力レコード
は５個に削減されている。即ち、ソート回路１１からの
連続的なレコードの出力を阻害しないで、重複レコード
の検出と計数処理を並列して実行できる。

第１図の実施例では、重複レコードの計数結果を出力レ
コードの計数カラムに設定して出力しているが１重複レ
コードの計数値のみが必要な場合には、計数回路１４の
値を直接出力すれば十分であり、レコードを出力するた
めの出力回路１５を省略することも出来る。この場合に
は、第２図に示したレコード２０の構成に於て、計数値
を格納するための計数カラム２２を付与しない構成も採
り得る。

レコードが複数のカラムで構成され、各カラムが昇順／
降順、あるいは非キーの指定が組合わせて指定された場
合であっても、本発明の計数処理機能は実施例と同様に
容易に実現することができる。

［発明の効果〕 以上説明したように、本発明のソート処理装置では、ソ
ート処理と同時に重複レコードの計数処理を実行できる
ことから、従来、繰返しデータベースを参照したり、ソ
ート処理後に計数処理を必要とするヒストグラム作成の
ような、レコードの分類・計数処理を大幅に高速化でき
る。更に、分類する場合の数が対象とするデータに依存
する場合であったも、ソート処理と同時に重複レコード
の計数と重複レコードの除去を行えるため、計数処理時
間を短縮できる利点がある。

【図面の簡単な説明】

第１図は本発明のソート処理装置の一実施例の構成図、
第２図は本発明のソート処理装置で扱うレコードの構成
例を示す図、第３図は本発明による具体的処理例を示す
図である。 １１・・・ソート回路、　　１２・・・バッファ回路、
１３・・・比較回路、　１４・・・計数回路、１５・・
・出力回路、　　１６・・・バッファメモリ。 Ａｉ：　　ｉ　　　　　　ＡＣＢ；　１ＡＢＤ：３　　
　　　ハＣＡ：２ ＡＢＣ＝　　３　　　　　　　八βＤ：２ＡＣβ；２ ＡＣＡ：　２ ＡＢＯ：５ ＡＢｃ：３ 、ＡＡｅ：　２

Claims (2)

【特許請求の範囲】
1. （１）入力データを相互に比較し、データの大小関係に
   基づいて並べ替えを行い、昇順あるいは降順にデータを
   出力するソート手段と、前記データ相互の比較によって
   、２個以上のデータが一致していることを検出して重複
   と判定する重複検出手段と、前記重複と判定されたデー
   タの個数を計数する計数手段とを具備していることを特
   徴とするソート処理装置。
2. （２）ソート処理対象とする個々のデータに計数結果を
   格納する計数カラムをあらかじめ付加しておいて、前記
   計数手段による計数結果を重複と判定されたデータの計
   数カラムに格納することを特徴とする特許請求の範囲第
   １項記載のソート処理装置。