JPH0378666B2 - - Google Patents
Info
- Publication number
- JPH0378666B2 JPH0378666B2 JP58012332A JP1233283A JPH0378666B2 JP H0378666 B2 JPH0378666 B2 JP H0378666B2 JP 58012332 A JP58012332 A JP 58012332A JP 1233283 A JP1233283 A JP 1233283A JP H0378666 B2 JPH0378666 B2 JP H0378666B2
- Authority
- JP
- Japan
- Prior art keywords
- data
- data group
- group
- hashing
- bit
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9014—Indexing; Data structures therefor; Storage structures hash tables
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Description
【発明の詳細な説明】
〔発明の利用分野〕
本発明は、２つのデータ群について相互にデー
タ内容の一致するデータのみを選別するデータ選
別方式に関するものである。
タ内容の一致するデータのみを選別するデータ選
別方式に関するものである。
データ管理システムの分野では、２つのデータ
群について相互にデータ内容の一致するデータを
抽出して結合する要求がしばしば生じる。この場
合、各々のデータ群のデータ量が多く、結合に長
い時間を要する場合、あらかじめ各々のデータ群
から結合可能性のないデータを除去し、結合時間
を短縮させるデータ選択の操作が用いられる。第
１図は、かゝるデータ選別方式の原理を説明する
図で、１，２はデータ群、４は定められたハツシ
ユ関数を持つハツシユ装置、６は有限のビツトア
レイを持つビツトアレイ装置、８は選別されたデ
ータ群である。操作は、先ずビツトアレイ装置６
のビツトアレイのビツトを全て“０”に設定した
後、操作１１を実行し、データ群１のデータ内容
をハツシユ装置４でハツシングして、ビツトアレ
イ装置６のアドレス空間に対応する値に変換し、
その値を番地とするビツトアレイのビツト位置に
“１”を設定する。次に、この操作１１が終了し
たら操作１３を実行し、データ群２のデータ内容
をハツシユ装置４で同様にハツシングして、その
値を番地とするビツトアレイ装置４のビツト位置
が“１”であるデータのみを選別してデータ８を
得る。第１図では、例えばデータ群１を
“ABDDFG”、データ群２を“AACDEFFH”と
した場合、選別データ群８として“AADFF”が
得られることを示している。第２図は第１図の操
作のタイムチヤートである。
群について相互にデータ内容の一致するデータを
抽出して結合する要求がしばしば生じる。この場
合、各々のデータ群のデータ量が多く、結合に長
い時間を要する場合、あらかじめ各々のデータ群
から結合可能性のないデータを除去し、結合時間
を短縮させるデータ選択の操作が用いられる。第
１図は、かゝるデータ選別方式の原理を説明する
図で、１，２はデータ群、４は定められたハツシ
ユ関数を持つハツシユ装置、６は有限のビツトア
レイを持つビツトアレイ装置、８は選別されたデ
ータ群である。操作は、先ずビツトアレイ装置６
のビツトアレイのビツトを全て“０”に設定した
後、操作１１を実行し、データ群１のデータ内容
をハツシユ装置４でハツシングして、ビツトアレ
イ装置６のアドレス空間に対応する値に変換し、
その値を番地とするビツトアレイのビツト位置に
“１”を設定する。次に、この操作１１が終了し
たら操作１３を実行し、データ群２のデータ内容
をハツシユ装置４で同様にハツシングして、その
値を番地とするビツトアレイ装置４のビツト位置
が“１”であるデータのみを選別してデータ８を
得る。第１図では、例えばデータ群１を
“ABDDFG”、データ群２を“AACDEFFH”と
した場合、選別データ群８として“AADFF”が
得られることを示している。第２図は第１図の操
作のタイムチヤートである。
第１図は一方のデータ群のみの選別データを得
る場合があるが、実際には２つのデータ群１，２
について相互にデータ内容の一致する選別データ
をそれぞれ必要とする場合が多い。このような場
合、従来は第３図に示すデータ選別方式を用いて
いた。
る場合があるが、実際には２つのデータ群１，２
について相互にデータ内容の一致する選別データ
をそれぞれ必要とする場合が多い。このような場
合、従来は第３図に示すデータ選別方式を用いて
いた。
第３図において、１，２はデータ群、３，４は
同じハツシユ関数を持つハツシユ装置、５，６は
有限のビツトアレイを持つビツトアレイ装置、
７，８は選別されたデータ群である。操作は、ビ
ツトアレイ装置３，４の各ビツトアレイのビツト
を全て“０”に設定した後、まず操作１１を実行
し、第１図で説明したようにデータ群１のデータ
内容をハツシユ装置４でハツシングして、その値
を番地とするビツトアレイ装置４のビツト位置に
“１”を設定する。次に、操作１２と操作１３を
同時に実行する。こゝで、操作１２はデータ群２
のデータ内容をハツシユ装置３でハツシングし
て、その値を番地とするビツトアレイ装置３のビ
ツト位置に“１”を設定する操作であり、操作１
３は同データ群２のデータ内容をハツシユ装置４
でハツシングして、その値を番地とするビツトア
レイ装置６のビツト位置が“１”であるデータの
みを選別してデータ８を得る操作である。この操
作１２，１３の終了後、操作１４を実行し、デー
タ群１のデータ内容を再びハツシユ装置３でハツ
シングして、その値を番地とするビツトアレイ装
置５のビツト位置が“１”であるデータのみを選
別してデータ７を得る。第３図では、データ群１
を“ABDDFG”、データ群２を“ACDEFFH”
とした場合、選別データ７では“ADDF”、選択
データ８は“AADFF”になることを示してい
る。
同じハツシユ関数を持つハツシユ装置、５，６は
有限のビツトアレイを持つビツトアレイ装置、
７，８は選別されたデータ群である。操作は、ビ
ツトアレイ装置３，４の各ビツトアレイのビツト
を全て“０”に設定した後、まず操作１１を実行
し、第１図で説明したようにデータ群１のデータ
内容をハツシユ装置４でハツシングして、その値
を番地とするビツトアレイ装置４のビツト位置に
“１”を設定する。次に、操作１２と操作１３を
同時に実行する。こゝで、操作１２はデータ群２
のデータ内容をハツシユ装置３でハツシングし
て、その値を番地とするビツトアレイ装置３のビ
ツト位置に“１”を設定する操作であり、操作１
３は同データ群２のデータ内容をハツシユ装置４
でハツシングして、その値を番地とするビツトア
レイ装置６のビツト位置が“１”であるデータの
みを選別してデータ８を得る操作である。この操
作１２，１３の終了後、操作１４を実行し、デー
タ群１のデータ内容を再びハツシユ装置３でハツ
シングして、その値を番地とするビツトアレイ装
置５のビツト位置が“１”であるデータのみを選
別してデータ７を得る。第３図では、データ群１
を“ABDDFG”、データ群２を“ACDEFFH”
とした場合、選別データ７では“ADDF”、選択
データ８は“AADFF”になることを示してい
る。
第４図に第３図の操作のタイムチヤートを示
す。これから分かるように、第３図に示す従来の
データ選別方式は、処理を３段階で逐次的に行う
ため、処理時間が長くなるという欠点を有してい
る。
す。これから分かるように、第３図に示す従来の
データ選別方式は、処理を３段階で逐次的に行う
ため、処理時間が長くなるという欠点を有してい
る。
本発明の目的は、従来に比べてデータ選別全体
に要する時間を短縮できるデータ選択方式を提供
することにある。
に要する時間を短縮できるデータ選択方式を提供
することにある。
本発明の要点は、第３図に示すデータ選択方式
において、各々のデータ群のビツトアレイに
“１”を設定する操作と、ビツトアレイを参照し
てデータを選別する操作を重ね合わせることによ
り、データ選別全体に要する時間の短縮を図つた
ものである。
において、各々のデータ群のビツトアレイに
“１”を設定する操作と、ビツトアレイを参照し
てデータを選別する操作を重ね合わせることによ
り、データ選別全体に要する時間の短縮を図つた
ものである。
第５図は本発明のデータ選別方式の操作を説明
する図で、基本的には第３図と同じである。本発
明による操作のタイムチヤートを第６図に示す。
こゝで、第６図はデータ群１のデータ量の方がデ
ータ群２のそれよりも小さい場合の例である。以
下、この例の場合について説明する。
する図で、基本的には第３図と同じである。本発
明による操作のタイムチヤートを第６図に示す。
こゝで、第６図はデータ群１のデータ量の方がデ
ータ群２のそれよりも小さい場合の例である。以
下、この例の場合について説明する。
操作は、まずビツトアレイ装置５，６のビツト
アレイの全てのビツトを“０”に設定する。次
に、データ群１，２に対し、各々のデータ群の先
頭のデータから操作１１と操作１２を同時に行
う。操作１１，１２の内容は第３図と同じであ
る。こゝで、データ群１，２のデータ量はデータ
群１の方が小さいとしているため、操作１１が終
了しても操作１２はまだ終了しない。この操作１
１が終了した時点で、操作１２はそのまま続け、
同時に該操作１２で使用しているデータ群２のデ
ータをハツシユ装置４にも入力して操作１３を開
始する。その後、操作１２が終了した時点で、デ
ータ群１に対しては、該データ群１の先頭データ
から操作１４を行うが、データ群２は、先頭デー
タから未だ操作１３の操作が施されていないデー
タまでのものに対して操作１３を行う。操作１
３，１４の内容も第３図と同じである。第５図に
示したように、データ群１を“ABDDFG”、デ
ータ群２を“AACDEFFH”とした場合、選別デ
ータ７，８の内容は第３図に示したものと同じで
あるが、本発明の操作では、選別データ８は
“FAADF”の順で得られる。
アレイの全てのビツトを“０”に設定する。次
に、データ群１，２に対し、各々のデータ群の先
頭のデータから操作１１と操作１２を同時に行
う。操作１１，１２の内容は第３図と同じであ
る。こゝで、データ群１，２のデータ量はデータ
群１の方が小さいとしているため、操作１１が終
了しても操作１２はまだ終了しない。この操作１
１が終了した時点で、操作１２はそのまま続け、
同時に該操作１２で使用しているデータ群２のデ
ータをハツシユ装置４にも入力して操作１３を開
始する。その後、操作１２が終了した時点で、デ
ータ群１に対しては、該データ群１の先頭データ
から操作１４を行うが、データ群２は、先頭デー
タから未だ操作１３の操作が施されていないデー
タまでのものに対して操作１３を行う。操作１
３，１４の内容も第３図と同じである。第５図に
示したように、データ群１を“ABDDFG”、デ
ータ群２を“AACDEFFH”とした場合、選別デ
ータ７，８の内容は第３図に示したものと同じで
あるが、本発明の操作では、選別データ８は
“FAADF”の順で得られる。
ここで、第３図の従来方式と本発明方式とを比
較してみる。今、２つのデータ群１，２のデータ
の数を各々ｎ，ｍ（ｎｍ）とし、１つのデータ
の操作１１，１２に要する時間をds、操作１３，
１４に要する時間をdrとする。第４図より、第３
図の方式での全処理時間は、 dso＋max（ds，dr）ｍ＋dr
較してみる。今、２つのデータ群１，２のデータ
の数を各々ｎ，ｍ（ｎｍ）とし、１つのデータ
の操作１１，１２に要する時間をds、操作１３，
１４に要する時間をdrとする。第４図より、第３
図の方式での全処理時間は、 dso＋max（ds，dr）ｍ＋dr
Claims (1)
- １ ２つのデータ群について相互にデータ内容の
一致するデータを選別するため、ビツトアレイと
ハツシユ装置の組を２組備え、それぞれ、一方の
データ群のデータ内容を他方の組のハツシユ装置
でハツシングして、その値を番地とする当該組の
ビツトアレイのビツト位置に“１”（又は“０”）
を設定して第１操作を行い、他方のデータ群のデ
ータ内容を前記他方の組のハツシユ装置でハツシ
ングして、その値を番地とする当該組のビツトア
レイのビツト位置が“１”（又は“０”）であるデ
ータのみを選別する第２操作を行う方式におい
て、２つのデータ群に対してそれぞれ同時に第１
操作を開始し、一方のデータ群の第１操作が終了
した時点で、他方のデータ群に対し、前記第１操
作を続行すると同時に第２操作を開始し、前記他
方のデータ群の第１操作が終了した時で、一方の
データ群に対して第２操作を行うと共に他方のデ
ータ群の未だ選別していない部分に対する第２操
作を続行することを特徴とするデータ選別方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58012332A JPS59139444A (ja) | 1983-01-28 | 1983-01-28 | デ−タ選択方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58012332A JPS59139444A (ja) | 1983-01-28 | 1983-01-28 | デ−タ選択方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS59139444A JPS59139444A (ja) | 1984-08-10 |
| JPH0378666B2 true JPH0378666B2 (ja) | 1991-12-16 |
Family
ID=11802347
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP58012332A Granted JPS59139444A (ja) | 1983-01-28 | 1983-01-28 | デ−タ選択方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS59139444A (ja) |
-
1983
- 1983-01-28 JP JP58012332A patent/JPS59139444A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS59139444A (ja) | 1984-08-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0531790B2 (ja) | ||
| JPS58222376A (ja) | テ−ブルサ−チ方式 | |
| JP2926803B2 (ja) | ソート処理方法 | |
| JP2853736B2 (ja) | クラスタ番号変換回路 | |
| JPS59139444A (ja) | デ−タ選択方式 | |
| JP2507399B2 (ja) | デ―タベ―ス装置 | |
| JPS60211541A (ja) | デ−タ検索回路 | |
| JPS6346537A (ja) | 検索処理装置における検索条件判定方法 | |
| JPS6266326A (ja) | 日本語デ−タ整列処理方式 | |
| JPS60211542A (ja) | デ−タ検索回路 | |
| JPH02294729A (ja) | ソート処理方式 | |
| JPS6134620A (ja) | 計算機への入力方法 | |
| JP2655410B2 (ja) | 多重化ｎ連一致保護回路 | |
| JPH09330322A (ja) | データ検索装置 | |
| JPH023225B2 (ja) | ||
| JPH0452967A (ja) | 集合ファイルに対する論理積演算処理方式 | |
| JPS6385823A (ja) | マルチキ−・ソ−タ | |
| JPH05151054A (ja) | 文書フアイル管理方式 | |
| JPH0736755A (ja) | 索引ファイルの入出力方法 | |
| JPH0635442A (ja) | データ変換装置 | |
| JPH03216730A (ja) | 電子計算機 | |
| JPS6072023A (ja) | 情報検索装置 | |
| JPH0419570B2 (ja) | ||
| JPH0553886A (ja) | テーブルアクセス管理方式 | |
| JPS63249227A (ja) | 情報検索回路 |