JPH0370826B2 - - Google Patents

Description

【発明の詳細な説明】

〔発明の技術分野〕 本発明は、ソート処理されている２つのリレー
シヨンに対してマージ・ソート処理を基本にした
関係演算により、併合（ジヨイン）演算を高速に
実行し得るデータ処理装置に関する。 〔発明の技術的背景とその問題点〕 大容量記憶装置の進歩に伴い、その大容量記憶
装置上で大規模なデータベースを構築する計算機
システムが増えてきている。ところが、データベ
ースが大規模になる程、該データベースから必要
なデータを検索するに必要な時間が長くなるとい
う問題が生じている。これを解決する方法の１つ
として、検索に必要な処理、つまり関係演算を専
用ハードウエアで実行することが種々提唱されて
いる。 ところで、関係演算の１つに併合（join−
equal）演算がある。この併合演算は、例えば２
つのリレーシヨン｛R1｝｛R2｝

【表】 から、そのキイ（属性Ａと、属性Ｃ）の値が等し
いレコードを、その組合せの数だけ結合して新し
いリレーシヨン｛R3｝を

〔発明の目的〕

本発明はこのような事情を考慮してなされたも
ので、その目的とするところは、２つのリレーシ
ヨン間の併合演算を簡易に、且つ高速に実行する
ことができるデータ処理装置を提供することにあ
る。 〔発明の概要〕 本発明は、所定の規則に従つてソート処理が施
された複数のレコードからなる第１および第２の
リレーシヨンをそれぞれ入力して第１および第２
のレコードバツフアメモリに格納する時、各リレ
ーシヨンにおけるレコードの属性を示すキイの値
の重複を検出して、その重複検出結果を上記各レ
コードに対応させて前記第１および第２のレコー
ドバツフアメモリに格納する。そして関係演算に
必要なレコードを前記第１および第２のレコード
バツフアメモリから順次読み出して比較し、その
比較結果に従つて上記レコードの出力を制御する
とき、前記比較結果と該レコードに付された前記
重複検出結果とに従つて次に読出すレコードを制
御するようにしたものである。そして特にこのレ
コードの読出し制御を 前記比較結果が等しくない場合には前記ソー
ト処理方向に若い値のレコードを格納したレコ
ードバツフアメモリから次のレコードを読出す
と共に、他方のレコードバツフアメモリからは
同じレコードを読出し、 前記比較結果が等しいときであつて、これら
の各レコードが重複レコードでない場合には前
記第１および第２のレコードバツフアメモリか
ら次のレコードをそれぞれ読出し、 前記比較結果が等しいときであつて、一方の
レコードだけが重複レコードとして示される場
合にはそのレコードを格納したレコードバツフ
アメモリから次のレコードを読出すと共に他方
のレコードバツフアメモリからは重複レコード
中の先頭レコードを読出し、 前記比較結果が等しいときであつて、前記各
レコードが共に重複レコードとして示されると
きには前記第１のレコードバツフアメモリから
同じレコードを読出すと共に前記第２のレコー
ドバツフアメモリから次のレコードを読出す ようにしたことを特徴とするものである。 〔発明の効果〕 かくして本発明によれば、２つのリレーシヨン
の各レコードに付された重複検出結果に従つて上
記リレーシヨン中の重複レコードについてのみ、
そのレコードの繰返し読出しを行い、その他のレ
コードについては順にその読出しを行うので、ソ
ート処理された２つのリレーシヨンをそれぞれほ
ぼ１回スキヤンニングするだけで併合演算に必要
なレコードの比較処理の全てを行うことが可能と
なる。従つて、各リレーシヨンにおけるレコード
の重複が殆んどない場合には、その処理に必要な
時間はほぼ （｛R1｝のレコードの数） ＋（｛R2｝のレコードの数） となり、処理所要時間の大幅な短縮化を図ること
が可能となる。しかも各リレーシヨンのレコード
のキイの値の重複を調べておき、そのレコード重
複情報を利用して各レコードの読出し制御を行う
ので、その制御アルゴリズムが簡単であり、構成
の複雑化を招来することなしにデータ処理装置を
構築することができる等の実用上多大なる効果が
奏せられる。 〔発明の実施例〕 以下、図面を参照して本発明の一実施例につき
説明する。 図は、本発明の実施例に係るデータ処理装置の
概略構成図である。データ処理装置は、基本的に
はマージ・ソート処理をベースとした関係演算を
行う演算部と、その関係演算結果の出力制御を行
う出力制御部とにより構成される。 所定の規則に従つてソート処理が施された重複
のレコードからなる第１および第２のリレーシヨ
ンがそれぞれ入力される演算部の入力段には、各
リレーシヨン中のレコードのキイの値の重複を検
出する重複検出回路が設けられている。この重複
検出回路は、順次入力されるレコードの１語をセ
ツトする入力レジスタ１１と、１レコード分の記
憶容量を持ち、かつFIFO（フアーストイン・フア
ストアウト）機能を有するレコードバツフアメモ
リ１２と、このレコードバツフアメモリ１２から
読出されるレコードのキイの値と前記入力レジス
タ１１にセツトされた次のレコードのキイの値と
を比較する比較回路１３と、上記レコードバツフ
アメモリ１２から読出されるレコードを１語分づ
つセツトして次段の回路に転送するデータレジス
タ１４と、前記比較回路１３が出力するイコール
信号Ｅから前記レコードバツフアメモリ１２にセ
ツトされていたレコードのキイの値が、現入力レ
コードのキイの値のと重複しているか否かを判定
し、重複している場合に重複フラグＦをセツトす
るフラグ回路１５とを備えて構成される。 尚、前記各レコードが複数の語によつて構成さ
れる場合、比較回路１３は各語毎に比較処理して
いることから、入力リレーシヨン中の相前後する
レコードのキイ（属性）の値が重複しているか否
かが決定されるタイミングは、そのレコードの最
後の語について処理したときとなる。従つて、前
記重複フラグＦは、前記レコードの最後の１語が
前記データレジスタ１４を介して次段に転送され
るときに有効となる。 しかしてこのような重複検出回路を介して入力
される第１のリレーシヨンの各レコードは、第１
のレコードバツフアメモリ１６に入力されて格納
される。この時、前記重複検出回路にて検出され
た各レコードについての重複検出結果（重複フラ
グＦ）が、そのレコードに対応して該第１のレコ
ードバツフアメモリ１６に格納される。同様にし
て第２のリレーシヨンのレコードが入力されたと
き、そのレコードは前記重複検出回路を介して第
２のレコードバツフアメモリ１７に格納され、各
レコードについて検出された重複検出結果（重複
フラグＦ）が、そのレコードに対応して該第２の
レコードバツフアメモリ１７に格納される。 これらの第１および第２のレコードバツフアメ
モリ１６，１７は、１つのリレーシヨンのレコー
ドを記憶できる容量をそれぞれ持ち、レコード読
出し制御回路１８，１９の制御を受けて格納レコ
ードおよびそのレコードに付加された重複検出結
果の読出しが制御されるようになつている。 尚、上記レコード読出し制御回路１８，１９
は、それぞれ読出し制御用のアドレスレジスタ２
０と、バツクアツプレジスタ２１とを具備して構
成される。バツクアツプレジスタ２１は、後述す
るレコードの比較結果と各レコードに付された重
複検出結果（重複フラグＦ）とに従つて、前記ア
ドレスレジスタ２０の値をセーブしたり、或いは
該バツクアツプレジスタ２１に格納している値を
前記アドレスレジスタ２０にロードするものであ
る。これらのアドレスレジスタ２０およびバツク
アツプレジスタ２１にセツトされる値の、前記比
較結果と重複検出結果（重複フラグＦ）とに基づ
く更新制御によつて、前記第１および第２のレコ
ードバツフアメモリ１６，１７から読出される各
リレーシヨンのレコードが制御される。 この他にも、本発明の要旨とは直接関係しない
ことから図示していないが、レコード読出し制御
回路１８，１９には書き込み用のレジスタや、こ
れらのレジスタを制御する制御回路が設けられて
いることは云うまでもない。 しかして前記第１および第２のレコードバツフ
アメモリ１６，１７からそれぞれ読出されるレコ
ードデータ、およびそのレコードに付された重複
検出結果の情報は、データレジスタ２２，２３に
それぞれセツトされる。 比較回路２４は、上記データレジスタ２２，２
３にそれぞれセツトされたレコードデータを相互
に比較し、その比較結果を前記レコード読出し制
御回路１８，１９に出力すると共に、次段の出力
制御回路２５に出力している。前記レコード読出
し制御回路１８，１９は、このような比較回路２
４によるレコードの比較結果と、上記データレジ
スタ２２，２３にセツトされた重複検出結果の情
報とを入力して、前記各レジスタ２０，２１のセ
ツトデータを更新制御している。 １レコード分の記憶容量を持ち、且つFIFO機
能を有する第３および第４のレコードバツフアメ
モリ２６，２７は、前記データレジスタ２２，２
３を介して前記レコードバツフアメモリ１６，１
７からそれぞれ転送されてきた各レコードを、一
旦格納するものである。これらのレコードバツフ
アメモリ２６，２７は、前記レコードの比較処理
が語単位で行われ、その比較結果が得られるタイ
ミングがレコードの最後の語を処理した時点であ
ることから、該レコードの全ての語に対する比較
処理が終了するまで、そのレコードの各語を保存
する為に設けられるものである。そして、このよ
うにして上記各レコードバツフアメモリ２６，２
７にそれぞれ格納されたレコードは、前記出力制
御回路２５の制御を受けて読出し制御され、選択
回路２８から出力レジスタ２９を介して出力され
るようになつている。 尚、このレコードの出力は、第３のレコードバ
ツフアメモリ２６に格納されたレコードと、第４
のレコードバツフアメモリ２７に格納されたレコ
ードとを結合して行われる。この結合処理は選択
回路２８にて、例えば第３のレコードバツフアメ
モリ２６に格納されているレコードを出力した
後、第４のレコードバツフアメモリ２７に格納さ
れているレコードを出力することによつて行われ
る。ここで、２つのレコードを結合して出力する
場合、前述した比較演算が２つのレコードの語数
の多いレコードの語長分によつて規定されるのに
対し、その出力所要時間は両レコードの語長の
「和」に相当した時間となる。この為、一般にレ
コードの比較演算時間より、レコードの出力処理
時間の方が多くかかる。これに対処するべく、例
えば前記演算部ではその比較演算を１サイクルの
前半で実行し、後半を待ち状態とする等すれば良
い。 この他に、演算部には現在キイ・フイールドを
処理中か否かを出力する回路や、レコードの最後
の１語、つまりサイクルの最後を処理中か否かを
出力する回路等が設けられることは勿論のことで
ある。 次に、実施例装置における併合演算処理の基本
的な流れについて説明する。 （） 先ずリレーシヨン｛Rx｝をそのキイの
値に対し昇順（小さい順）にソート処理し、レ
コードの重複検出を行つて重複フラグＦを付加
した後、第１のレコードバツフアメモリ１６に
格納する。同様にリレーシヨン｛Ry｝をその
キイの値に対し昇順にソート処理し、レコード
の重複検出を行つて重複フラグＦを付加した
後、第２のレコードバツフアメモリ１７に格納
する。 （） 次に上記各リレーシヨン｛Rx｝｛Ry｝
の先頭のレコードに、それぞれポインタ（以
降、これを単にポインタと称する）と、バツク
アツプ用のポインタ（以降、これをバツクアツ
プポインタと称する）を置く。 （） そして上記ポインタの示すレコードをレ
コードバツフアメモリ１６，１７から読出して
そのキイの値を比較する。そして、上記レコー
ドのキイの値が等しければ、併合条件を満すと
して、両レコードを合せて出力し、上記キイの
値が異なる場合にはそのレコードの出力をやめ
る。 しかして、上記キイの値が等しい場合には、
そのレコードに付された重複フラグＦを調べ、
その重複フラグＦに従つた以下の処理を行う。 先ず両レコードの重複フラグＦが共に
“０”ならば、各リレーシヨンのポインタを、
次のレコードに進める。このとき、バツクア
ツプポインタも、上記ポインタの新しい値を
セーブする。 いずれか一方のレコードの重複フラグＦの
みが“１”ならば、重複フラグＦが“１”で
あるレコードを含む側のリレーシヨンのポイ
ンタを次のレコードに進める。この時、バツ
クアツプポインタの値も上記ポインタの値で
同時に更新する。そして重複フラグＦが
“０”であるレコードを含む側のリレーシヨ
ンについては、バツクアツプポインタが指し
ているレコードをポインタとする。この場
合、バツクアツプポインタの値は更新しな
い。 そして両レコードの重複フラグＦが共に
“１”ならば、リレーシヨン｛Ry｝のポイン
タを次のレコードまで進め、そのバツクアツ
プポインタについては更新しない。一方、リ
レーシヨン｛Rx｝については、バツクアツ
プポインタが指しているレコードをポインタ
とする。 また上述したようにキイの値が異なる場合
には、キイの値の小さい方のリレーシヨン、
つまり前記ソート処理方向に若い値のキイを
持つリレーシヨンのポインタを次のレコード
まで進める。このときバツクアツプポインタ
も同時に更新する。尚、この場合には前記重
複フラグＦはポインタの制御には利用されな
い。 （） しかる後、前記各リレーシヨン中に次に
比較するレコードがあれば、前述した（）の
処理に戻り、いずれか一方のリレーシヨンにレ
コードがなくなれば、上述した処理を終了す
る。 ところで上記（）の処理において、２つのレ
コードのキイの値が等しい場合について検討する
と、各リレーシヨンにおけるレコードが重複して
いるか否かにより、４通りの状態が考えられる。
この各状態について、リレーシヨン｛R4｝とリ
レーシヨン｛R5｝を例に、前述したポインタの
制御を説明する。 (1) 両レコードが共に重複していない場合のリレ
ーシヨン｛R4｝｛R5｝は、例えば次のように
示される。

【表】 しかしてこの場合には、サイクルでレコー
ド［２／Ｇ］と［２／ｐ］とを出力する。この
サイクルの最後では、仮にリレーシヨン
｛R4｝あるいはリレーシヨン｛R5｝のポイン
タが指しているレコードを残したとしても、先
に進んだ方のポインタが指すレコードのキイの
値が、残された方のレコードのキイ値より大き
いことが明らかであることから、両リレーシヨ
ンのポインタを同時に更新できる。 次のサイクルでは両リレーシヨン共に、そ
のポインタを次のレコードである［３／Ｔ］と
［５／ｈ］に進めて、その比較処理を行えば良
い。 (2) リレーシヨン｛R4｝のレコードのキイの値
が重複しており、リレーシヨン｛R5｝のレコ
ードのキイの値が重複していない場合の例は、
次のように示される。

【表】 この場合には、サイクルの終りで、リレー
シヨン｛R4｝のポインタを［２／Ｇ］から
［２／Ｑ］へ進ませ、リレーシヨン｛R5｝につ
いてはそのポインタを固定的にレコード［２／
ｐ］を指すようにする。 そしてサイクルでは、レコードの重複フラ
グＦが共に“０”となるので、両レコードのポ
インタを同時更新する。 (3) リレーシヨン｛R4｝のレコードのキイの値
が重複せず、リレーシヨン｛R5｝のレコード
のキイの値だけが重複している場合には、次の
ようになる。

【表】 この場合には、サイクル，では、リレー
シヨン｛R4｝のポインタを固定的にレコード
［２／Ｇ］を指すようにし、リレーシヨン
｛R5｝のポインタを［２／ｐ］から［２／ｔ］
へと先に進ませるようにすればよい。 そしてサイクルでは、レコードの重複フラ
グＦが共に“０”となることから両レコードの
ポインタの同時更新を行えば良い。 (4) 次に、両リレーシヨンのレコードのキイの値
が共に重複している場合には、例えば次のよう
になる。

【表】 この場合には、サイクル，では、リレー
シヨン｛R4｝のポインタを固定的にレコード
［２／Ｇ］を指すようにし、リレーシヨン
｛R5｝のポインタをレコード［２／ｐ］から
［２／ｔ］へと先に進むようにする。但し、リ
レーシヨン｛R5｝のバツクアツプポインタは、
重複しているレコードの先頭のレコード［２／
ｐ］を指したまま固定する。 サイクルでは、リレーシヨン｛R4｝のレ
コードの重複フラグＦだけが“１”になる。そ
こで、リレーシヨン｛R4｝のポインタを次の
レコード［２／Ｚ］に進め、リレーシヨン
｛R5｝のポインタを、上記バツクアツプポイン
タが指すレコード［２／ｐ］に戻す。 そしてサイクル，では、リレーシヨン
｛R4｝のポインタを固定しておき、リレーシヨ
ン｛R5｝のポインタを［２／ｐ］から［２／
ｔ］へと先に進ませる。この時、リレーシヨン
｛R4｝のレコードの重複フラグＦは“０”なの
で、リレーシヨン｛R5｝のバツクアツプポイ
ンタは更新される。 サイクルでは、両レコードの重複フラグＦ
が共に“０”となり、両リレーシヨンのポイン
タを共に次のレコードに進める。 以上(1)〜(4)の処理を行うことにより、両リレー
シヨンにおける［２／α］と［２／β］の全ての
組合せに対する併合演算処理がなされることにな
る。従つて、この処理の後には両リレーシヨンの
ポインタをそれぞれ先頭に戻す必要がなくなる。 次に前述した実施例装置の処理動作につき、リ
レーシヨン｛R1｝｛R2｝を例に挙げて説明する。
尚、ここではリレーシヨン｛R1｝｛R2｝の各属
性の語長が全て１語長であり、２語長で１レコー
ドが構成されるものとする。また、１語の処理時
間を１フエーズとし、１レコードの処理時間（１
サイクル）が２フエーズからなるものとする。 先ず最初に、リレーシヨン｛R1｝を構成する
複数のレコードを、そのキイ（属性Ａ）の値でそ
れぞれ昇順のソート処理を施して、次のようなリ
レーシヨンを得る。

【表】 このリレーシヨン｛R1｝のレコードデータを
順次入力して、先ずそのリレーシヨン中に重複レ
コードがあるか否かを検査し、その検査結果をレ
コードに同期して出力する。この重複レコードの
検出は次のようにして行われる。 即ち、リレーシヨン｛R1｝の各レコードは、
上記したソート処理された順序で入力され、従つ
て第１サイクルではレコード［２／Ｆ］が入力さ
れる。 この第１サイクルの第１フエーズでは、１番目
のレコードの第１の語［２］が入力され、入力レ
ジスタ１１にセツトされ、レコードバツフアメモ
リ１２に格納される。 次の第２フエーズでは、次の第２の語［Ｆ］が
入力レジスタ１１にセツトされ、前記レコードバ
ツフアメモリ１２に格納される。この第１および
第２フエーズの処理によつて最初のレコードの入
力が終了する。 続く第２サイクルでは、つぎの３つの処理が平
行して行われる。 その１つは２番目のレコード［３／Ｕ］を入力
して前記レコードバツフアメモリ１２に格納する
動作であり、２つ目は上記２番目のレコードと前
記レコードバツフアメモリ１２から読出される１
番目のレコード［２／Ｆ］とを比較する動作であ
る。 そして３つ目は前記レコードバツフアメモリ１
２から読出した１番目のレコード［３／Ｕ］を第
１のレコードバツフアメモリ１６に格納する動作
である。 この時、上記１番目のレコードに対して求めら
れた重複フラグＦの値も上記第１のレコードバツ
フアメモリ１６に格納する。 即ち、第１フエーズでの１つ目の処理は第１サ
イクルと同様に、２番目のレコードの先頭の１語
である［３］を入力し、入力レジスタ１１にセツ
トし、同時にレコードバツフアメモリ１２に格納
することにより行われる。 そしてFIFO機能を有しているレコードバツフ
アメモリ１２から、１サイクル前に記憶したレコ
ードの先頭の語［２］を読出し、これをデータレ
ジスタ１４を介して第１のレコードバツフアメモ
リ１６に転送すると共に比較回路１３に与え、前
記入力レジスタ１１にセツトされている２番目の
レコードの最初の語［３］と比較する。この場
合、２つの語が等しくないこと、つまり条件に合
致していないことがわかる。 続く第２フエーズでは、入力レジスタ１１か
ら、２番目のレコードの２語目の値［Ｕ］をレコ
ードバツフアメモリ１２に格納し、このレコード
バツフアメモリ１２から前記１番目のレコードの
次の語である［Ｆ］を読出し、これをデータレジ
スタ１４を経由して第１のデーレコードバツフア
メモリ１６に転送し、同時に前記入力レジスタ１
１にセツトされた語［Ｕ］と比較する。このフエ
ーズはレコードの最後の１語の処理であり、前記
１番目のレコードのキイの値が次のレコードのキ
イの値と重複していないので、比較回路１３のイ
コール信号Ｅ（＝０）を受けてフラグ回路１５は
重複フラグＦ（＝０）を出力する。 以下、同様な処理が各サイクル毎に行われる
が、第３サイクルではレコード［６／Ｄ］が入力
され、続く第４サイクルではレコード［６／Ｐ］
が入力されることから、、上記第３サイクルで入
力されたレコード［６／Ｄ］に対しては、重複フ
ラグＦ（＝１）が付される。 このような重複レコードの検出処理によつて、
第１のレコードバツフアメモリ１６には前記リレ
ーシヨン｛R1｝が次のような形で格納される。

【表】 しかる後、リレーシヨン｛R1｝同様なソート
処理が施されたリレーシヨン｛R2｝ を順次入
力し、同様に重複レコードの検出を行つて第２の
レコードバツフアメモリ１７に次のようなリレー
シヨンを得る。

【表】 以上の処理を経て、各レコードバツフアメモリ
１６，１７に格納されたリレーシヨン間の併合演
算処理を次のようにして行う。 先ず、両リレーシヨンの先頭のレコードにポイ
ンタを置く。つまりレコード読出し制御回路１
８，１９の各アドレスレジスタ２０に前記各リレ
ーシヨンの先頭レコードの１番目の語、つまりレ
コード［２／Ｆ］の［２］と、レコード［１／
ｅ］の［１］を記憶している番地を指すようにポ
インタをそれぞれセツトする。同時に各アドレス
レジスタ２０にセツトされた値を、バツクアツプ
レジスタ２１にそれぞれセーブする。 以上の準備を完了して、併合演算処理を開始す
る。 先ず第１サイクルでは次の３つの処理を平行し
て行う。但し、前述した重複レコードの検出処理
における第１サイクルと、ここでの第１サイクル
とは異なるタイミングである。 即ち、第１に前記第１のレコードバツフアメモ
リ１６から読出したリレーシヨン｛R4｝の１番
目のレコード［２／Ｆ］と、第２のレコードバツ
フアメモリ１７から読出したリレーシヨン｛R5｝
の１番目のレコード［１／ｅ］とを比較する。そ
して第１のレコードバツフアメモリ１６から読出
した１番目のレコード［２／Ｆ］を第３のレコー
ドバツフアメモリ２６に格納し、第２のレコード
バツフアメモリ１７から読出した１番目のレコー
ド［１／ｅ］を第４のレコードバツフアメモリ２
７に格納する。そして次のサイクルで比較するレ
コードを選択するべく前記ポインタの制御を行
う。 具体的には、その第１フエーズでは、第１およ
び第２のレコードバツフアメモリ１６，１７か
ら、前記各アドレスレジスタ２０が指す語［２］
［１］を同時に読出し、ころをデータレジスタ２
２，２３セツトした後、比較回路２４にて比較す
る。この場合、両レコードの各語の値が一致しな
いので、つまりリレーシヨン｛R1｝のキイの値
の方が大きいので、該レコードを出力しないこと
を決定する。そこで、出力制御回路２５に対し
て、次の第２サイクルでレコード［２／Ｆ］
［１／ｒ］を結合して出力しないように通知する。
そして前記各アドレスレジスタ２０をカウントア
ツプする。尚、次のサイクルでは、上記比較され
たキイの値の小さい方のリレーシヨン｛R2｝の
ポインタを進め、リレーシヨン｛R1｝のポイン
タは元に戻す。 この処理と同時に前記各データメモリ２２，２
３に格納されたデータ［２］［１］をそれぞれ読
出して、前記レコードバツフアメモリ２６，２７
にそれぞれ格納する。 続く第２フエーズでは、前記各レコードバツフ
アメモリ１６，１７から、各レコードの２番目の
語［Ｆ］［ｅ］を読出し、データレジスタ２２，
２３を経由して、前記レコードバツフアメモリ２
６，２７にそれぞれ格納する。そして、リレーシ
ヨン｛R2｝のレコードの方がそのキイの値が小
さいので、リレーシヨン｛R2｝のポインタを先
に進め、リレーシヨン｛R1｝のポインタはその
ままにする。即ち、この第２フエーズから次のフ
エーズである第２サイクルの第１フエーズに移る
時、レコード読出し制御回路１８ではそのアドレ
スレジスタ２０に、バツクアツプレジスタ２１の
値をロードし、先頭のレコード［２／Ｆ］をもう
一度読出せるようにする。他方、レコード読出し
制御回路１９では、そのアドレスレジスタ２０を
カウントアツプし、次のレコード［２／ｋ］を読
出せるようにする。そして、次の第２サイクルの
最初で、上記バツクアツプレジスタ２１に上記ア
ドレスレジスタ２０の値をセーブする。 続く第２サイクルでは、第１のレコードバツフ
アメモリ１６から読出したリレーシヨン｛R4｝
の１番目のレコード［２／Ｆ］と、第２のレコー
ドバツフアメモリ１７から読出したリレーシヨン
｛R5｝の２番目のレコード［２／ｑ］とを比較す
る。 そして上記各レコードバツフアメモリ１６，１
７からそれぞれ読出したレコード［２／Ｆ］
［２／ｑ］を、前記レコードバツフアメモリ２６，
２７にそれぞれ格納し、次のサイクルで比較する
レコードを選択する。 以上の各処理は、第１サイクルでの処理と同様
に行われるが、この場合、読出したレコードが
［２／Ｆ］［２／ｋ］であることから、そのキイの
値が一致する。そこで次の第３サイクルでは、出
力制御回路２５の出力制御によつて、前記第３お
よび第４のレコードバツフアメモリ２６，２７か
らそれぞれ読出されるレコード［２／Ｆ］［２／
ｋ］が結合して出力される。 またこのとき第２フエーズの終りで、その比較
結果が同値であることから、前記各レコードにそ
れぞれ付された重複フラグＦが前記レコード読出
し制御回路１８，１９に入力される。この場合、
両レコードに付された重複フラグＦが共に“０”
であることから、両リレーシヨンに対するポイン
タがそれぞれ先に進められる。つまり、各アドレ
スレジスタ２０がそれぞれカウントアツプされ、
次の第３サイクルの先頭でその値が前記各バツク
アツプレジスタ２１にそれぞれセーブされる。 次の第３サイクルでは、前述した第１および第
２サイクルで行われる３つの処理に加えて、レコ
ードの結合出力動作が行われる。 即ち、第３サイクルではリレーシヨン｛R4｝
の２番目のレコード［３／Ｕ］と、リレーシヨン
｛R5｝の２番目のレコード［２／ｋ］とが比較さ
れ、同時に上記各レコード［３／Ｕ］［２／ｋ］
が前記各レコードバツフアメモリ２６，２７にそ
れぞれ転送して格納され、更に次のサイクルで比
較するレコードを選択する為のポインタ制御が行
われる。 これに加えて前記レコードバツフアメモリ２
６，２７にそれぞれ格納され、そのキイの値が等
しいと判定された、前記リレーシヨン｛R1｝の
１番目のレコード［２／Ｆ］と、リレーシヨン
｛R2｝の２番目のレコード［２／ｋ］が選択回路
２８を介して読出され、結合して出力される。 このレコードの結合出力動作を更に詳しく説明
すると、その第１フエーズで第３のレコードバツ
フアメモリ２６からレコードの先頭の語［２］を
読出し、選択回路２８を経由して出力レジスタ２
９にセツトし、これを出力する。続く第２フエー
ズでは次の語［Ｆ］を読出し、同様に出力する。
しかる後、第３フエーズと第４フエーズでは、第
２のレコードバツフアメモリ２７からリレーシヨ
ン｛R2｝のレコードの語［２］［ｑ］を順に読出
し、前記選択回路２８を経由して出力レジスタ２
９にセツトして出力する。 この結果、出力レジスタ２９の出力としてリレ
ーシヨン｛R3｝の第１番目のレコード［２／
Ｆ／２／ｑ］が得られる。 これ以降のサイクルでは、上記第３サイクルと
同様な処理が行われる。 しかして第４サイクルでは、第３サイクルで比
較されたレコードが［３／Ｕ］と［２／ｋ］であ
り、そのキイの値が異なることから、そのレコー
ドの結合出力は行われない。 このようなサイクルが同様にて繰返されて、第
４サイクルにてレコード［６／Ｄ］［６／ｓ］が
比較された場合、キイの値が等しいことが検出さ
れる。この場合にも上記レコード［６／Ｄ］
［６／ｓ］が結合して出力される。しかしてこの
時、上記各レコードにそれぞれ付された重複フラ
グＦが共に“１”なので、前述したようにリレー
シヨン｛R1｝の読出しを制御するレコード読出
し制御回路１８のアドレスレジスタ２０には、そ
のバツクアツプレジスタ２１の値がロードされ、
再度前記レコード［６／Ｄ］が読出されるように
ポインタ制御がなされる。一方このとき、レコー
ド読出し制御回路１９のアドレスレジスタ２０は
カウントアツプされ、次のレコード［６／ｗ］を
読出すようにポインタ制御される。しかし、レコ
ード読出し制御回路１９のバツクアツプレジスタ
２１の値はそのまま維持され、そのリレーシヨン
における重複レコードの最初、つまりレコード
［６／ｓ］に戻れるようにしておく。 第５サイクルでも、レコードのキイの値が共に
［６］として一致する。従つてこの場合のレコー
ド［６／Ｄ］［６／ｗ］が結合されて出力される。
しかしこの場合、リレーシヨン｛R1｝の重複フ
ラグＦだけが“１”であることから、このサイク
ルの最後で、レコード読出し制御回路１８のアド
レスレジスタ２０の値がカウントアツプされて次
のレコード［６／Ｐ］が読出されるようにされ、
且つそのバツクアツプレジスタ２１の値が上記ア
ドレスレジスタ２０の値に更新される。つまり、
このレコード［６／Ｐ］が再度読出せるようにバ
ツクアツプポインタが制御される。 そして、レコード読出し制御回路１９のアドレ
スレジスタ２０には、そのバツクアツプレジスタ
２１に格納された値がロードされ、そのリレーシ
ヨンの重複しているレコードの先頭であるレコー
ド［６／ｓ］が読出されるようにポインタ制御が
なされる。 次の第６サイクルでは、レコード［６／Ｐ］
［６／ｓ］が比較され、そのキイの値が一致する
ことから該レコードの結合出力が行われる。そし
て、リレーシヨン｛R2｝側の重複フラグＦだけ
が“１”であることから、レコード読出し制御回
路１８のポインタ更新は行われず、レコード読出
し制御回路１９のアドレスレジスタ２０の値がカ
ウントアツプされ、且つそのバツクアツプレジス
タ２１の値が上記アドレスレジスタ２０の値に更
新される。 そして第７サイクルでは、レコード［６／Ｐ］
［６／ｗ］が比較され、結合出力される。そして
この場合、上記各レコードの重複フラグＦが共に
“０”であるので、そのリレーシヨンのポインタ
は共に次のレコードを指すように制御される。 然し乍ら、この場合には両リレーシヨンに次の
レコードがないことから、このサイクルでレコー
ドの比較処理が終了する。 以上に説明したように、本装置によればリレー
シヨン｛R1｝｛R2｝に対して、その先頭のレコ
ードから末尾のレコードへと、重複するレコード
を除いて１回のスキヤンによつて併合演算に必要
なレコードの比較処理を行い得る。従つて、リレ
ーシヨン中に重複するレコードが無いか、或いは
無視できる程度の重複レコード量ならば、併合演
算に必要な実行時間は、リレーシヨン｛R1｝の
レコードの数とリレーシヨン｛R2｝のレコード
の数との和に相当したサイクル時間となる。 つまり従来例では、その実行時間が両レコード
数の「積」で決つていたのが、本発明によればそ
の「和」で決まるようになる。従つて、効率良く
短時間に併合演算処理を実行することが可能とな
る。また以上の処理を、相前後して入力するレコ
ードの間でそのキイの値を比較し、その比較結果
に従つて各レコードに重複フラグＦを付して行つ
ているので、簡単なアルゴリズムで効率良く併合
演算を行い得る。 尚、本発明は上述した実施例に限定されるもの
ではない。例えば各レコードを構成するキイ（属
性）の数や、そのキイ（属性）の語長、またリレ
ーシヨンを構成するリコードの数等は仕様に応じ
て定めれば良いものである。また併合条件につい
ても。特に限定されるものではない。要するに本
発明は、その要旨を逸脱しない範囲で種々変形し
て実施することができる。

【図面の簡単な説明】

図は本発明の一実施例に係るデータ処理装置の
要部概略構成図である。 １１……入力レジスタ、１２……レコードバツ
フアメモリ、１３……比較回路、１４……データ
レジスタ、１５……フラグ回路、１６……第１の
レコードバツフアメモリ、１７……第２のレコー
ドバツフアメモリ、１８，１９……レコード読出
し制御回路、２０……アドレスレジスタ、２１…
…バツクアツプレジスタ、２２，２３……データ
レジスタ、２４……比較回路、２５……出力制御
回路、２６……第３のレコードバツフアメモリ、
２７……第４のレコードバツフアメモリ、２８…
…選択回路、２９……出力レジスタ。

Claims (1)

【特許請求の範囲】
1. １ 所定の規則に従つてソート処理された複数の
   レコードからなる第１および第２のリレーシヨン
   における上記レコードの属性を示すキイの重複を
   それぞれ検出する手段と、上記第１および第２の
   リレーシヨンのレコードをそれぞれ格納する第１
   および第２のレコードバツフアメモリに上記重複
   検出結果を前記各レコードに対応させて格納する
   手段と、上記第１および第２のレコードバツフア
   メモリからそれぞれ読出されたレコードの前記キ
   イを相互に比較し、その比較結果に従つて上記第
   １のリレーシヨン中のキイに等しい前記第２のリ
   レーシヨン中のレコードを上記第１のリレーシヨ
   ンのレコードと結合して出力する手段と、上記比
   較結果および前記比較処理された各レコードにそ
   れぞれ付された重複検出結果に従つて前記第１お
   よび第２のレコードバツフアメモリから次に読出
   すレコードを制御する手段とを具備し、このレコ
   ードの読出しを制御する手段は、前記比較結果が
   等しくない場合には前記ソート処理の方向に若い
   値を有するレコードを格納したレコードバツフア
   メモリから次のレコードを読出すと共に他方のレ
   コードバツフアメモリからは同じレコードを読出
   し、前記比較結果が等しいときには前記各レコー
   ドに付された重複検出結果を調べ、これらの各レ
   コードが重複レコードでない場合には前記第１お
   よび第２のレコードバツフアメモリから次のレコ
   ードをそれぞれ読出し、一方のレコードだけが重
   複レコードとして示される場合にはそのレコード
   を格納したレコードバツフアメモリから次のレコ
   ードを読出すと共に他方のレコードバツフアメモ
   リからは同じレコードを読出し、前記各レコード
   が共に重複レコードとして示されるときには、前
   記第２のレコードバツフアメモリからのレコード
   をバツクアツプして保存して前記第１のレコード
   バツフアメモリから同じレコードを読出すと共に
   前記第２のレコードバツフアメモリから次に続く
   重複レコードを順次読出し、その後前記第１のレ
   コードバツフアメモリから次のレコードを読出す
   と共に前記第２のレコードバツフアメモリからは
   上記バツクアツプされたレコードを読出し、更に
   その後前記第１のレコードバツフアメモリから同
   じレコードを読出すと共に前記第２のレコードバ
   ツフアメモリからは次のレコードを読出してなる
   ことを特徴とするデータ処理装置。