JPH0373019B2 - - Google Patents

Description

【発明の詳細な説明】

〔発明の技術分野〕 本発明は、ソート処理されたリレーシヨンに対
してマージ・ソート処理を基本にした関係演算に
より射影演算を効率良く実行し得るデータ処理装
置に関する。 〔発明の技術的背景とその問題点〕 大容量記憶装置の進歩に伴い、その大容量記憶
装置上で大規模なデータベースを構築する計算機
システムが増えてきている。ところが、データベ
ースが大規模になる程、該データベースから必要
なデータを検索するに必要な時間が長くなるとい
う問題が生じている。これを解決する方法の１つ
として、検索に必要な処理、つまり関係演算を専
用ハードウエアで実行することが種々提唱されて
いる。 しかして、マージ・ソート処理をベースとした
関係演算を実行する従来のデータ処理装置にあつ
ては、予めソート処理されている２つのリレーシ
ヨン間の各レコードを相互に比較し、その比較結
果に応じて上記２つのリレーシヨンの一方から選
択的にレコードを出力する動作を基体としている
ので、例えば上記データベース検索で必要な射影
演算を行なうことが困難であると云う不具合があ
つた。 即ち、この射影演算（projection）は、例えば
リレーシヨン｛R1｝

【表】 から、そのキイ（属性Ａ、属性Ｂ）の値が等しい
レーコドを取り除いて、新しいリレーシヨン
｛R2｝を

〔発明の目的〕

本発明はこのような事情を考慮してなされたも
ので、その目的とするところは、例えばデータベ
ース検索処理に必要な射影演算を簡易に、且つ高
速に実現することができるデータ処理装置を提供
することにある。 〔発明の概要〕 本発明は、１レコードを処理するためびに反転
されるメモリ選択フラグを演算部に用意し、この
演算部に所定の規則に従つてソート処理が施され
た複数のレコードからなるリレーシヨンを入力す
る時、上記メモリ選択フラグが指定する第１また
は第２のレコードバツフアメモリに上記リレーシ
ヨンのレコードを１レコードづつ交互に格納する
ようにし、且つ前記第１のレコードバツフアメモ
リから読み出される第１のレコードと、前記第２
のレコードバツフアメモリから読み出される第２
のレコードとを比較回路で比較するように上記演
算部を構成し、出力選択部においては前記メモリ
選択フラグに従つて出力対象とするレコードが前
記第１のレコードか、或いは前記第２のレコード
かを選択し、この選択したレコードを出力するか
否かを前記比較回路の比較結果に従つて制御する
ことによつて射影演算を処理可能としたことを特
徴とするものである。 〔発明の効果〕 かくして本発明によれば、入力リレーシヨンの
各レコードを交互に第１および第２のレコードバ
フアメモリに格納して該第１および第２のレコー
ドバツフアメモリに２つのリレーシヨンを作成
し、これらのリレーシヨン間で各レコードの比較
を行いつつ、その比較結果に従つて前記第１およ
び第２のレコードバツフアメモリから交互に読出
されるレコードの出力を制御するので、前記２つ
のリレーシヨン間のレコードの属性を示すキイの
値が等しいとき、そのレコード出力を阻止して重
複レコードのないリレーシヨンを簡易に、且つ効
果的に作成することが可能となる。つまり、入力
リレーシヨンを交互に振分けて作成した２つのリ
レーシヨン間の各レコードの比較結果に従つて、
同一レコードが検出されたとき、そのレコードの
出力を阻止するので、ソフトウエアに頼ることな
しに、入力リレーシヨン中の重複レコードを除去
することができ、上記入力リレーシヨンに対する
射影演算を簡易に高速に実行することが可能とな
る。 〔発明の実施例〕 以下、図面を参照して本発明の一実施例につき
説明する。 図は実施例装置の概略構成図である。データ処
理装置は、基本的にはマージ・ソート処理をベー
スとした関係演算を実行する演算部１と、その関
係演算結果の出力制御を行う出力制御部２とによ
り構成される。 所定の規則に従つてソート処理が施されたリレ
ーシヨンを構成する複数のレコードは、データ処
理装置に順次入力される。演算部１は、入力レコ
ードを１語づつセツトする入力レジスタ１１と、
１レコード分の記憶容量を持ち、且つFIFO（フア
ースト・イン・フアースト・アウト）機能を有す
る第１および第２のレコードバツフアメモリ１
２，１３と、上記第１のレコードバツフアメモリ
１２から読み出される値と第２のレコードバツフ
アメモリ１３から読み出される値とを相互に比較
して、上記各値が相互に等しいときにイコール信
号を出力する比較回路１４と、前記第１および第
２のレコードバツフアメモリ１２，１３を選択制
御するフラグ回路１５とを備えて構成される。 尚、上記フラグ回路１５にセツトされるメモリ
選択フラグＦは、入力された１レコードが処理さ
れる都度、つまり１サイクル毎に反転制御され
る。そして上記メモリ選択フラグＦが“１”のと
きには、前記第１のレコードバツフアメモリ１２
が選択されて、入力レジスタ１１に格納された値
が該第１のレコードバツフアメモリ１２に格納さ
れる。そして上記メモリ選択フラグＦが“０”の
ときには、NOT回路１６を介して前記第２のレ
コードバツフアメモリ１３が選択され、前記入力
レジスタ１１に格納された値が該第２のレコード
バツフアメモリ１３に格納される。このメモリ選
択フラグＦに従つて、前記入力レジスタ１１に順
次入力されるデータ（レコード）が、前記第１お
よび第２のレコードバツフアメモリ１２，１３に
交互に格納される。尚、前記レコードが複数の語
（データ）からなり、語単位で入力レジスタ１１
にデータが入力される場合には、複数の語からな
る１つのレコードが一方のレコードバツフアメモ
リに格納されたのち、前記メモリ選択フラグＦが
反転される。 しかして前記比較回路１４は、上記第１および
第２のレコードバツフアメモリ１２，１３にそれ
ぞれ格納されたデータ（レコード）を相互に比較
し、そのデータ（レコード）が等しいとき、イコ
ール信号Ｅを出力している。尚、比較回路１４
が、前記複数の語からなるレコードを語単位で比
較する場合には、レコードを構成する各語間での
比較結果の全てが等しいときにのみ、当該レコー
ドが等しいことになるので、各レコードの最後の
語の比較結果を得たとき、前記イコール信号Ｅが
有効となる。 ところで処理対象としているレコードが、その
後に続くレコードと重複していることが判明する
タイミングは、該レコードの最後の語の比較結果
を得たときとなる。この為、該レコードを一旦、
バツフアリングする必要がある。出力制御部２に
設けられた第３のレコードバツフアメモリ１７
は、前記第１および第２のレコードバツフアメモ
リ１２，１３から順次読み出される語を、前記メ
モリ選択フラグＦに従つて選択制御される選択回
路１８を介して入力し、これを格納してそのレコ
ードをバツフアリングしている。この結果、第３
のレコードバフアメモリ１７には、処理対象とし
ているレコードが格納されることになる。 しかして出力制御回路１９は前記第３のレコー
ドバツフアメモリ１７に格納されたレコードのキ
イの値が、その後に続くレコードのキイの値と重
複しているか否かを前記イコール信号Ｅから判定
しており、重複していない場合（Ｅ＝０）には、
該第３のレーコドバツフアメモリ１７に格納され
たレコードを出力レジスタ２０を介して出力して
いる。また上記イコール信号Ｅが（Ｅ＝１）の場
合には、該第３のレコードバツフアメモリ１７に
格納されたレコードが後に続くレコードと重複し
ているとして、その出力を阻止している。このよ
うにして、ソート処理されたリレーシヨンの各レ
コードのキイの値が、その後に続くレコードのキ
イ値と等しい場合、そのレコードの出力が阻止さ
れて１つのリレーシヨン中の重複レコードの除
去、つまり射影演算が行われるようになつてい
る。 尚、ここでは本発明の要旨と直接関係していな
いことから図示していないが、演算部１には現在
キイ・フイールドを処理中か否かを示す回路や、
レコードの最後の１語を処理中か否かを示す回路
等が設けられることは云うまでもない。 次に、本装置における射影演算処理の流れを具
体例を挙げて説明する。 本装置における射影演算は、基本的に次のよう
に行われる。 () 先ずリレーシヨン｛Rx｝をそのキイの値
に対して、例えば昇順にソート処理する。例え
ばリレーシヨン｛R1｝の属性Ａと属性Ｂを１
つの属性と看做してソート処理を行う。このソ
ート処理は、ソフトウエア、或るいはソート処
理専用のハードウエア（図示していない）によ
つて行われる。この結果、例えば次のようなリ
レーシヨンが得られる。

【表】 このようなリレーシヨンの各レコードを語単
位で順次入力して、本装置による射影演算が次
のようにして実行される。 () 演算部１では、先ず前記メモリ選択フラグ
Ｆに従つて入力レコードを交互に振分け、前記
第１および第２のレコードバツフアメモリ１
２，１３上で２つのリレーシヨン｛Ｒ×１｝と
｛Ｒ×２｝を作成する。 () しかる後、両リレーシヨン｛Ｒ×１｝｛Ｒ
×２｝の先頭のレコードにポインタを置いて比
較対象とするレコードを特定し、前記メモリ選
択フラグＦを｛Ｒ×１｝側にする（Ｆ＝１）。 () 次に上記ポインタが示すレコード間でその
キイ（属性）の値を比較する。 () そして上記レコード間のキイ（属性）の値
が等しければ、そのレコードが重複していると
して前記メモリ選択フラグＦが示す側のレコー
ドの出力を阻止する。 また上記レコード間のキイ（属性）の値が等
しくなければ、レコードが重複していないとし
て前記メモリ選択フラグＦが示す側のレコード
を出力する。 () その後、前記メモリ選択フラグＦが指す側
のポインタを次のレコードに進め、該メモリ選
択フラグＦを反転する。 () そして次のレコードがあれば、前記（）
の処理に戻り、次のレコードがない場合には、
前記メモリ選択フラグＦが指す側のレコードを
出力してその処理を終了する。 この処理フローにおける前記（）〜（）の
処理について更に詳しく説明する。先ず前記
（）に示す処理によつて前記第１および第２の
レコードバツフアメモリ１２，１３に振分けられ
て作成される２つのリレーシヨン｛Ｒ×１｝｛Ｒ
×２｝は次のようになる。

【表】 ここで、上記丸数字…は１つのレコード
を処理する為の各サイクルを示しており、下線は
上記各サイクルで前記メモリ選択フラグＦが示す
リレーシヨンを表している。 しかして第１サイクルでは［１／ｒ］と
［２／ｑ］とを比較する。この場合、両レコード
は等しくないので、前記メモリ選択フラグＦ（Ｆ
＝１）が選択しているレコード［１／ｒ］出力さ
れ、その後、メモリ選択フラグＦを“０”に反転
する。 次の第２サイクルでは［２／ｑ］と［２／
ｑ］を比較する。この場合、両レコードが等しい
のでメモリ選択フラグ（Ｆ＝０）が選択している
レコード［２／ｑ］の出力が阻止される。つま
り、そのレコードが出力されない。そして前記メ
モリ選択フラグＦが“１”に反転される。 第３サイクル、第４サイクル、第５サイク
ルでは、そのレコードのキイの値が等しくない
ので、前記第１サイクルの場合と同様に、その
レコードが出力される。 以上が、本装置の基本的に射影演算の流れであ
る。 ところで前述したリレーシヨン｛R1｝の各レ
コードは、複数の語（属性）からなる。今、各属
性の語長を、全て１語長とし、各レコードのレコ
ード長が２語長で与えられるものとする。そして
実施例装置では１語を処理する時間を１フエーズ
とし、１レコードを処理する時間を１サイクルと
して、つまり２フエーズを１サイクルとして動作
するものとする。 この場合実施例装置では、ソート処理されたリ
レーシヨンを入力するに際し、先ず前記メモリ選
択フラグＦを“１”初期設定する。 しかして第（−１）サイクルでは、上記リレー
シヨンの１番目のレコード［１／ｒ］を入力し、
第１のレコードバツフアメモリ１２に記憶する。 この第（−１）サイクルでの動作を更に詳しく
説明すると、その第１フエーズで属性Ａのデータ
［１］を入力し、これを入力レジスタ１１にセツ
トする。このとき前記メモリ選択フラグＦが
“１”であることから、上記入力レジスタ１１に
セツトされたデータ［１］を第１のレコードバツ
フアメモリ１２に格納する。 次の第２フエーズでは、［ｒ］を入力レジスタ
１１にセツトし、これを同様にして第１のレコー
ドバツフアメモリ１２に格納する。これによつ
て、最初のレコードの入力が終了する。その後、
前記メモリ選択フラグＦを“０”に反転して第
（−１）サイクルを終え、次の第（０）サイクル
に移る。 第（０）サイクルでは、レコード［２／ｑ］を
入力し、このとき前記メモリ選択フラグＦが
“０”であることから、これを第２のレコードバ
ツフアメモリ１３に記憶する。この処理は上記第
（−１）サイクルと同様にして行われるが、その
サイクルの最後で前記メモリ選択フラグＦを反転
して“１”にする。 続く第１サイクルでは、次の３つの処理が平行
して行われる。 その１つは３番目のレコード［２／ｑ］を入力
し、第１のレコードバツフアメモリ１２に格納す
る動作であり、その処理は前述した第（−１）サ
イクルと同様に行われる。２つ目の動作は、第１
のレコードバツフアメモリ１２から１番目のレコ
ード［１／ｒ］を、また第２のレコードバツフア
メモリ１３から２番目のレコード［２／ｑ］をそ
れぞれ読出し、これらのレコードを比較回路１４
で比較する処理動作である。そして３つ目の動作
は、前記メモリ選択フラグＦに従つて、前記第１
のレコードバツフアメモリ１２から読み出した１
番目のレコードを第３のレコードバツフアメモリ
１７に格納する動作である。 即ち、このサイクルの第１フエーズでは、処理
は、３番目のレコードの先頭の１語である
［２］を入力して入力レジスタ１１にセツトし、
これを第１のレコードバツフアメモリ１２に格納
する第１の動作、FIFO機能を有する第１および
第２のレコードバツフアメモリ１２，１３から、
前に記憶したレコード（＝１番目のレコードと２
番目のレコード）の先頭の各語［１］［２］をそ
れぞれ読み出し、その語を比較する第２の動作、
および上記第１のレコードバツフアメモリ１２か
ら読出した先頭の語［１］を第３のレコードバツ
フアメモリ１７に格納する第３の動作からなる。 そして、その第２フエーズでは、入力した３番
目のレコードの２語目［ｑ］を第１のレコードバ
ツフアメモリ１２に格納する動作、第１および第
２のレコードバツフアメモリ１２，１３から、前
に記憶したレコード（＝１番目のレコードと２番
目のレコード）の２番目の各語［ｒ］［ｑ］をそ
れぞれ読み出して比較する動作、同時に上記第１
のレコードバツフアメモリ１２から読出した２番
目の語［ｒ］を第３のレコードバツフアメモリ１
７に格納する第３の動作からなる。 この第２フエーズは、レコードの最後の１語の
処理なので、前記比較回路１４のイコール信号Ｅ
（Ｅ＝０）を出力する。出力制御回路１９は、こ
のイコール信号Ｅに従つて、次の第２サイクルで
前記第３のレコードバツフアメモリ１７に格納し
たレコード［１／ｒ］の出力を制御する。 しかして第２サイクルでは、前記第１サイクル
におけるレコードの比較結果が、両レコードが異
なることを示しているから、次の４つの処理が平
行に行われる。 この４つの処理のうちの３つは上述した第１サ
イクルと同様であり、これに加えて出力制御部２
におけるレコードの出力制御が前記イコール信号
Ｅに応じて行われる。つまり前記イコール信号Ｅ
が“０”の場合にのみ、次の第４の動作が行われ
る。この第４の動作は、第１フエーズで前記第３
のレコードバツフアメモリ１７から、レコードの
１語目を読み出して出力レジスタ２０にセツトし
て出力し、次の第２フエーズで前記第３のレコー
ドバツフアメモリ１７から、レコードの２語目を
読み出して出力レジスタ２０にセツトして出力す
る。これによりレコード［１／ｒ］が出力され
る。 尚、前記イコール信号Ｅが“１”の場合、前記
その前のサイクルで比較されたレコードが等しい
ことを示すから、そのレコードの出力を阻止する
べく、第４の動作は行われない。 以降のサイクルでは、上述した第２サイクルと
同様な処理が繰返して行われる。 かくして本装置によれば第３のレコードバツフ
アメモリ１７に、比較回路１４のイコール信号Ｅ
を付加した形として、次のようにリレーシヨンを
得る。

【表】 従つてこのリレーシヨン中からイコール信号Ｅ
が“１”であるレコードの出力を阻止、つまり重
複したレコードを取除くことによつて、次のよう
な新しいリレーシヨン｛R2｝を得ることが可能
となる。

【表】 以上のように本装置によれば、メモリ選択フラ
グに従つて第１および第２のレコードバツフアメ
モリ１２，１３に入力レコードを交互に記憶し、
その後各レコードを読み出して比較して、その結
果により該レコードを出力するか否かを決定し、
上記メモリ選択フラグにより示されるレコードの
出力を制御するので、データ処理装置を用いて射
影演算を効果的に、且つ高速に実行することがで
きる。しかも、その処理アルゴリズムが簡単であ
り、ハードウエアにおける実現が容易である。 尚、本発明は上述した実施例に限定されるもの
ではない。例えばレコードを構成する属性の数
や、その語長等は処理対象とするデータベースの
構造等に応じて定めれば良い。またこれに応じて
１サイクルのフエーズ数を定めれば良い。その
他、本発明はその要旨を逸脱しない範囲で種々変
形して実施することができる。

【図面の簡単な説明】

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

Claims (1)

1. 【特許請求の範囲】 １ 所定の規則に従つてソート処理された複数の
   レコードを順次入力すると共に、１つの入力レコ
   ードを処理する都度メモリ選択フラグを反転する
   手段と、この反転制御されるメモリ選択フラグに
   従つて上記入力レコードを交互に記憶する第１お
   よび第２のレコードバツフアメモリと、これらの
   第１および第２の各レコードバツフアメモリにそ
   れぞれ格納された各入力レコードを交互に読出
   し、該レコードの属性を示すキイの値を相互に比
   較する比較回路と、前記メモリ選択フラグに従つ
   て前記第１または第２のレコードバツフアメモリ
   に格納されたレコードを選択し、この選択したレ
   コードを前記比較回路の比較結果が不一致の時に
   出力し、且つ該比較結果が一致した時前記選択し
   たレコードの出力を阻止するよう制御する出力制
   御部とを具備したことを特徴とするデータ処理装
   置。 ２ 第１および第２のレコードバツフアメモリ
   は、それぞれFIFO機能を有するものであること
   を特徴とする特許請求の範囲第１項記載のデータ
   処理装置。