JPH0658644B2

JPH0658644B2 - 自然結合演算処理装置

Info

Publication number: JPH0658644B2
Application number: JP63284846A
Authority: JP
Inventors: 光教和田; 祥司山下
Original assignee: 工業技術院長
Priority date: 1988-11-12
Filing date: 1988-11-12
Publication date: 1994-08-03
Anticipated expiration: 2009-08-03
Also published as: JPH02132559A

Description

【発明の詳細な説明】（産業上の利用分野）この発明は、データの演算処理装置に関し、特にデータ
として与えられたリレーションの属性、例えば年齢、性
別等についての重ね合わせ符号を作成し、リレーション
について検索する際は、このような重ね合わせ符号によ
り検索できるようにした自然結合(Natural Joint)演算
装置に関する。

（従来の技術）従来、リレーショナル・データベース・システムにおい
ては、各リレーションの属性毎にB⁺ツリー（B⁺tree）等
の索引を用意しておく方法や、ハッシュ関数及びハッシ
ュ・テーブルを用意して置く方法により、リレーション
のタプルについての検索を高速化していた。前者のB⁺ツ
リー等の方法は、検索要求により指定された属性につい
て索引を辿り、最終的に要求を満足するタプルを得るも
のである。一方、後者のハッシュ関数及びハッシュ・テ
ーブルによる方法は、検索要求により指定された属性値
にハッシュ関数を施した結果に基づいてハッシュ・テー
ブルを検索して要求を満足するタプル候補を得るもので
ある。

２つのリレーションについて、B⁺ツリーや、ハッシュ・
テーブルを作成するためには、それぞれが備えているB⁺
ツリー等の検索手段、又はハッシュ関数及びハッシュ・
テーブルを用いた検索手段により、それぞれの属性を組
み合わせる演算、即ち自然結合演算が実行される。又、
その演算結果であるリレーションに対しても検索手段が
必要となる場合は、演算結果により形成されたタプルを
調べ、そのリレーションの全タプルについて、キューと
なる属性の検索レコードを作成するか、又はハッシュ値
を計算する処理を実行してB⁺ツリーやハッシュ・テーブ
ルを作成する。

（発明が解決しようとする課題）しかし、従来の処理方法は、自然結合演算の結果となる
リレーションの属性についての検索や、ハッシュ・テー
ブルを新たに作成しなければならなかった。それにも拘
わらず、演算を適用するリレーションは既に有している
検索や、ハッシュ・テーブルを利用していなかった。

通常、実用に供されるリレーションは数百〜数万項目の
タプルを有するので、１リレーションのキーとなる属性
についての索引や、ハッシュ・テーブルを新規に作成す
ると、膨大な時間を費やすことになる。このように、自
然結合演算の結果となるリレーションについて検索をす
ると、システムはその検索やハッシュ・テーブルの作成
に掛かりきりとなり、システム全体の処理速度を著しく
低下させる欠点があった。

この発明は、リレーション間で実行される自然結合演算
の所要時間を短縮させ、かつリレーションのタプルを高
速に検索することができると共に、その索引を有するリ
レーション間の自然結合演算の実行結果に対する索引が
得られる自然結合演算処理装置を提供することを目的と
する。

（課題を解決するための手段）この発明は、リレーショナルデータベースに格納した同
一の属性を有する２つのリレーションについて所定の論
理処理を実行することにより、前記リレーションについ
て結合した索引を作成するリレーショナルデータベース
の自然結合演算処理装置において、前記２つのリレーシ
ョンのそれぞれについて、その複数の属性をそれぞれ表
すビット群を前記属性の配列順に従って所定のビット数
だけ順次シフトする第１手段と、前記２つのリレーショ
ンのそれぞれについて、前記第１手段によりシフトした
前記属性の各桁のビット間で論理和を取ることにより、
第１及び第２索引テーブルの索引値を作成する第２手段
と、前記２つのリレーションを結合するために選択され
た特定の属性に対応する前記第１及び第２索引テーブル
のビット群において、セットされているビットが互いに
重なり合うように、前記第２索引テーブルのビットをシ
フトする第３手段と、前記第１索引テーブルのビット
と、前記第３手段によりシフトした前記第２索引テーブ
ルのビットとの間で論理和を取り、第３索引テーブルの
ビット群を作成する第４手段とを備え、前記第３索引テ
ーブルのビット群を前記結合させた索引に対応させたも
のである。

（作用）この発明によれば、２つのリレーションのそれぞれの第
１及び第２索引テーブルにより前記リレーションにおけ
るタプルを検索することができると共に、前記２つのリ
レーションを結合させた索引レコードからなる第３索引
テーブルが得られるので、前記２つのリレーションを結
合させたリレーションについても前記第３索引テーブル
により高速に検索することを可能にする。

（実施例）第１図はこの発明の自然結合演算装置によりリレーショ
ンの索引を作成する手順を説明する図である。第２図
は、第１図における人物リレーションの索引値を作成す
る手順の部分を詳細に説明する図である。まず、第２図
を参照して人物リレーションの索引値を作成する手順を
説明する。

ステップSTA1によりリレーションとして複数人物の属性
及びタプル１〜６を設定する。この場合は、属性とし
て、タプル１〜６の横方向に順に示すように、「人
名」、「年齢」及び「性別」を設定する。

ステップSTA2により、「人名」、「年齢」及び「性別」
を２進値に変換してそれぞれ４ビット、４ビット及び２
ビット長のビット群からなる“0100”、「年齢」“001
0”及び“01”を得る。

ステップSTA3により、「人名」“0100”に対して「年
齢」“0010”を１ビットだけ右方向へシフトし、更に
「年齢」“0010”に対して「性別」“01”を１ビットだ
け右方向へシフトし、次いで各桁のビット毎に論理和
(+)を取り、２進値符号“01010”を得る。この２進値符
号“01010”は、タプル１に対する索引レコード１の索
引値となる。

同様に、タプル２〜６についてもタプル１と同一の論理
処理を実行する。この結果、タプル２に対する索引レコ
ード２の索引値は“11101”、タプル３に対する索引レ
コード３の索引値は“10110”、タプル４に対する索引
レコード４の索引値は“10011”、タプル５に対する索
引レコード５の索引値は“01101”、タプル６に対する
索引レコード６の索引値は“00110”となる。

更に、ステップSTA4は、索引レコード１〜６により索引
テーブルを設定し、これによって人物リレーションのタ
プル１〜６をアクセスすることができるように、索引レ
コード１をタプル１、…、索引レコード６をタプル６を
それぞれ矢印により示すポインタに従って対応させる。

第１図は第２図で説明した手順を含む図であり、この発
明により人物リレーションの索引テーブルの作成手順を
説明する図である。

ステップSTB1により、リレーション「人物１」の属性と
して「部門」及び「血液型」、またタプルとしてタプル
１及びタプル２を設定する。

ステップSTB2により、リレーション「人物１」の、例え
ばタプル２の各属性値にハッシュを施し、「人名」“01
001”に対して「部門」“10000”を１ビット左方向にシ
フトし、また「部門」“10000”に対して「血液型」“0
10”を１ビット左方向にシフトし、更に対応する各桁の
ビットについて論理和を取って「索引テーブル１」の索
引レコード２の索引値“0101001”を得る。

索引レコード１についても、索引レコード２と同じよう
な処理により索引値“1100100”を得る。

ステップSTB3により、ステップSTC1と同様に、リレーシ
ョン「人物２」の属性として「人名」及び「年齢」を設
定し、またタプルとしてタプル３〜６を設定する。

ステップSTB4により、ステップSTB2と同様に、リレーシ
ョン「人物２」の各属性にハッシュを施し、２進値を１
ビット左方向にシフトし、対応する各桁のビットについ
て調理和を取って「索引テーブル２」の索引レコード３
〜６の索引値“010011”，“001110”，“101100”及び
“001011”を得る。

ステップSTB5により、「人名」が等しいという条件に基
づいて、リレーション「人物１」及び「人物２」の自然
結合演算を実行し、リレーション「人物３」のタプル７
及び８を得る。

従って、リレーション「人物３」のタプル７及び８に
は、「人物１」のタプル１及び２と、「人物２」のタプ
ル３〜６とに含まれている属性、即ち「人物名」、「年
齢」、「部門」及び「血液型」が全て含まれている。

ステップSTB6により、「索引テーブル１」及び「索引テ
ーブル２」の内容に基づいて自然結合演算を実行して、
リレーション「人物３」に対応する「索引テーブル３」
を作成する。例えば、索引レコード２の索引値“010100
1”、及び索引レコード３の索引値“010011”を取り出
し、結合条件とした属性、即ち「人名」の「野口」を表
す２進値“01001”が互いに重なり合うように、索引レ
コード２の索引値“0101001”に対して索引レコード３
の索引値“010011”を右へ２ビットだけシフトし、対応
するビット間で論理和を取ることにより、２進値“0101
001”を得て、これを索引テーブル３に示すように、索
引レコード７の索引値とする。

同様の処理により、索引テーブル３に示す索引レコード
７の索引値８の“1110110”を得る。

第３図はこの発明による索引レコードにより第１図に示
す人物リレーションを検索する手続を示す図である。ス
テップSTC1により、検索条件として人物リレーションに
おける属性の「年齢」を“17”に、「性別」を「女性」
に設定する。

ステップSTC2により、属性を２進値に変換する手順を実
行して、「年齢」を“1001”にし、「性別」を“10”に
する。この場合に、「人名」は指定されていないため
に、“0000”とする。

ステップSTC3により、２進値の索引を作成したときと同
一の順番によって、これらの属性を配置し、図示のよう
に、次に来る属性のビットを１ビットだけ右方向にシフ
トし、次いで各桁のビットについて論理和を取る。これ
により、キュエリ(query)・マスク“01101”が得られ
る。キュエリ・マスクとは、このような論理処理の結果
をいう。

ステップSTC4により、このキュエリ・マスクと索引レコ
ード１〜６のビット内容とを比較し、ビット１について
一致する索引レコード、この場合は索引レコード２及び
５を、実線の矢印により示すように、選択する。一致し
ない索引レコードは点線の矢印により示されている。

ステップSTC5により、抽出したタプル２及び５のビット
内容を調べて、「年齢」が“17”、かつ「性別」が“1
0”である条件に適合するのは、いずれかを判断する。
この場合は、タプル２が適合すると判断され、検索が終
了する。

第４図は、第１図におけるタプル２及び７の索引値を作
成する手順についてのみに注目して示す図である。第４
図ｂが第１図と異なるのは、ステップSTC8により、タプ
ル７における属性のシフト、及び論理和を取る演算処理
を実行することにより、索引値７と照合する索引値７′
として“01010011”を得ることである。

これによって、索引値７′が索引値７と同一の結果とな
ることが確認される。

（発明の効果）以上、詳細に説明したように、この発明によれば、２つ
のリレーションの属性を結合させた第３リレーションに
ついても、前記２つの索引値の属性を重ね合わせた符号
からなる索引テーブルを作成することにより、リレーシ
ョンについての索引の作成時間を短縮することができ、
またこのような索引によりリレーションの検索時間を高
速化することができる。

【図面の簡単な説明】第１図はこの発明の自然結合演算処理装置によりリレー
ションの索引を作成する手順を示す図、第２図はこの発
明により人物リレーションの索引値の作成手順を示す
図、第３図はこの発明により人物リレーションの索引手
順を説明する図、第４図は第１図における特定のタプル
のみに注目して索引値の作成手順を説明する図である。 STA1〜STA4，STB1〜STB4，STC1〜STC8……ステップ

Claims

【特許請求の範囲】

【請求項１】リレーショナルデータベースに格納した同
一の属性を有する２つのリレーションについて所定の論
理処理を実行することにより、前記リレーションについ
て結合した索引を作成するリレーショナルデータベース
の自然結合演算処理装置において、前記２つのリレーションのそれぞれについて、その複数
の属性をそれぞれ表すビット群を前記属性の配列順に従
って所定のビット数だけ順次シフトする第１手段と、前記２つのリレーションのそれぞれについて、前記第１
手段によりシフトした前記属性の各桁のビット間で論理
和を取ることにより、第１及び第２索引テーブルの索引
値を作成する第２手段と、前記２つのリレーションを結合するために選択された特
定の属性に対応する前記第１及び第２索引テーブルのビ
ット群において、セットされているビットが互いに重な
り合うように、前記第２索引テーブルのビットをシフト
する第３手段と、前記第１索引テーブルのビットと、前記第３手段により
シフトした前記第２索引テーブルのビットとの間で論理
和を取り、第３索引テーブルのビット群を作成する第４
手段と、を備え、前記第３索引テーブルのビット群を前記結合さ
せた索引に対応させることを特徴とするリレーショナル
データベースの自然結合演算処理装置