JPS60134945A

JPS60134945A - データベース処理方法

Info

Publication number: JPS60134945A
Application number: JP58242024A
Authority: JP
Inventors: Keiji Kojima; 啓二小島; Shunichi Torii; 俊一鳥居
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1983-12-23
Filing date: 1983-12-23
Publication date: 1985-07-18
Anticipated expiration: 2010-03-15
Also published as: US4644471A; JPH0724036B2; US4785400A

Abstract

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

Description

【発明の詳細な説明】〔発明の利用分野〕本発明は、データベース処理方式に係り、特に大規模リ
レーショナル・データベースにおける検索要求の処理に
好適なデータベース処理方式に関する。

〔発明の背景〕

大量データの効率的管理を目的とするデータベース技術
が急速に発展している。データベースの大きな利点は、
データベース利用者が、データの物理的記憶構造を全く
慧識せずに、データ操作用言語を通じてデータにアクセ
スすることが可能である点にある。

データベース罠格納されているデータ（以下レコードと
呼ぶ）の、物理的な格納形式は、レコードの挿入・削除
等の操作に対する柔軟性の確保、レコードの格納効率の
向上、などを実現するために一般にかなυ複雑な形式と
なっている。

従って、ユーザによって論理的にポイントされたレコー
ドに対し、その物理的な格納位置をめる処理（この処理
をデータベース処理におけるアドレス変換と呼ぶ）も、
レコードの物理的な格納形式の複雑さに対応して、かな
り制負荷の処理となっている。

従来金データベース管理システム（以１”ＤＢＭＳとい
う）では、レコードへのアクセスをルコード単位で行な
っていた。すなわち、あるレコードのデータベースから
の取り出しが必要となった時点毎に、アドレス変換を行
なってレコードの物理アドレスをめてそのレコードヲ取
り出していた。

しかし、かかるデータベース処理方式には、以下の様な
問題点かめる。

第一の問題点は、大量レコードの一括処理を要求された
場合の性能上の問題である。

最近の、特ニリレーショナル・モデルにもとづく高水準
のデータ操作用言語は、１コマンドによって複数のレコ
ードの処理を行なうことができる。

一方、近年のいわゆるスーパー・コンピュータの発達に
示されるよ２に、大量データの一括処理の高速化には、
パイプライン方式などによるベクトル処理が非常に効果
的であることが仰られている。

しかし、ルコード毎にアドレス変換を行なう従来のＤＢ
ＭＳでは、前述の様にアドレス変換処理が複雑なため、
複数レコード処理のベクトル化が極めて困難である。

第二の問題点は、同一のレコードに対して複数回のアク
セスを行なう場合には、本質的には１度のアドレス変換
で済むはずであるが、従来方式では、レコードに対する
アクセス回数に等しい回数のアドレス変換を常に必要と
するという欠点がある。

〔発明の目的〕

本発明の目的は、上記問題点に対処するために、アドレ
ス変換回数が少なく、かつ検索処理のベクトル化を可能
とするデータベース処理方式を提供することにある。

〔発明の概要〕

上記目的を達成するだめに、本発明は、参照が予想され
るレコード群を予測し、そのレコード群に対するアドレ
ス変換を一括１．て行ない、この変換結果を用いてレコ
ード群を記憶装置上にベクトル形式で展開し、以後の処
理をこのベクトルに対して行なうことを特徴とする。

〔発明の実施例〕

以下、本発明の一実施例を図面罠従って詳細に説明する
。第１図は、本発明をリレーショナル・データベースの
処理に適用した場合の一実施例を示すブロック図である
。

第１図において、１０１は主記憶、１０８は二次記憶、
１１０は中央処理装置である。主記憶１０１には、デー
タベース処理グログラム（ＤＢＰ）１０２が格納されて
いる。また、主記憶１０１には、データベース処理のた
めの作業領域１０６および■１０バッファ領域４０１が
確保されている。

データベース処理プログラム１０２は、ベクトル展開部
１０３と、検索処理制御部１０４と、ベクトル処理部１
０５とから成る。二次記憶１０８にはデータベース１０
９が格納される。中央処理装置１１０はヌカ２命令とベ
クトル命令の両方を処理できるベクトル計算機の中央処
理装置である。

データベース１０９は、テーブルとインデックスとから
成り、テーブルのだて一欄をカラム、横−欄をローと呼
ぶ。

テーブル、インデックスともに、ページと呼ばれる単位
に分割して二次記憶１０８に格納される。

テーブルを格納しているページをデータベージ、インデ
ックスを格納しているページをインデックスベージと呼
ぶ。

まず、データベージの構造の例を第２図を用いて説明す
る。

データベージ２０４内には、スロット２０５と変位部２
０７とがあシ、変位部２０７には、スロット２０５の先
頭アドレスと、データベージ２０４の先頭アドレスの差
が格納される。データベージには複数のスロットが存在
するので、それに対応して変位部も複数存在する。変位
部はデータベージの終わ９から順に配置され終わシに近
い順から番号がつけられる。以下この命号をスロット番
号２０３と呼ぶ。

テーブルのローは、スロット２０５に格納される。従っ
て、テーブルのローは、そのローが格納されているスロ
ット２０５が存在するデータページの二次記憶１０８中
でのページ番号２０２と、そのローが格納されているス
ロット２０５のスロツ）８号２０３とのベア２０１（以
下これをローＩＤと呼ぶ）によって二次記憶中で一意に
指定される。スロット２０５はさらに、複数のカラム値
から成る。

次に、インデックスの構造について述べる。゛インデッ
クスには平衡木（以下Ｂ−ｔｒｅｅ　という）という木
構造が良く用いられ、本実施例でも、Ｂ−ｔｒｅｅをイ
ンデックスの構造として１更用する。

Ｂ−４ｒｅｅの各ノードが１インデツクス・ページに対
応する。

Ｂ−ｆ；ｒｅｅのルートに対応するページをルート・ペ
ージ、リーフに対応するページをリーフ・ページと呼ぶ
。

以下、インデックス・ページの溝道例Ｖこついて第３図
を用いて説明する。

インデックス・ページの構造は、リーフ・ページとリー
フ以外のページとで異なる。

第３図において、３０１ｖｊ、リーフでないインデック
ス・ページであり、３０８はリーフであるインデックス
・ページ（リーフ・ページ）でおる。

インデックス・ページには、複数のインデックスエント
リ（以下エントリという）が存在する。

インデックス・ページ３０１内のエントリのうち、最も
小さいキー値をもつエントリ３０４を、そのページの先
頭エントリと呼ぶ。各エントリの最後部には、インデッ
クス・ベージ３０１内で次に大きなキー値をもつエント
リへのポインタが格納され、インデックス・ベージ３０
１内の最後のエントリ、すなわち、そのページ中で最も
大きなキー値をもつエントリの最後部３０５には、シ次
のエントリが存在しないことを示すマークが格納されて
いる。変位部３０６には、インデックス・ページ３０１
の先頭エントリのアドレスと、インデックスページ３０
１の先頭アドレスとの差が格納されている。前方ページ
番号３０７　ＶＣは、インデックス・ページ３０１の前
方のインデックス・ページの番号が格納される。

その前方ページ内の任意エントリのキー値は、インデッ
クス・ベージ３０１内の任意エントリのキー値よシ大き
い。

ここまでで説明したインデックス・ページの構造は、リ
ーフ・ページとリーフ以外のインデックス・ページとに
共通でるる。

リーフ以外のインデックス・ページ３０１のエン）す３
０２のキー値に続く部分３０３には、下方のインデック
ス・ページ（リーフ・ページ）３０８のページ番号が格
納されている。インデックス・ページ（リーフ・ページ
）３０８内の任意のエントリのキー値は、エントリ３０
２のキー値以上の値を有する。

インデックス・ページ（リーフ・ページ）３０８のエン
）す３０９のキー値に続く部分３１０には、そのキー値
に属するローのローＩＤＣすなわち該インデックスがつ
けられているカラムの値がキー値に等しいようなローの
ローＩＤ）が格納される。

エントリ３０９のキー値に属するローが複数個ある場合
、エントリ３０９には複数のローＩＤが格納される。

Ｂ−ｔｒｅｅでは、リーフ・ページの前方ページは必ず
リーフ・ページである。リーフ・ページのうち、他のど
のリーフ・ページからも参照されていないページが唯一
つ存在し、このリーフ・ページを最左リーフ・ページと
呼ぶ。最左リーフ・ページのページ番号ｉｔ：　、ルー
ト・ページカラ、ページの先頭エントリのキー値の直後
に示されている下方ページを、リーフ・ページまでたど
ることによシ得られる。

また、テーブルの任意のローのローＩＤは、いずれかの
リーフ・ページのエントリ内に必ず格納されておシ、ま
た、インデックス中にそのローＩＤが重複して格納され
ることはない。

従って、最左リーフ・ページから次々と前方のリーフ・
ページをたどりながらそのページ内をスキャンしていく
ことによシ、テーブルの全ローのローＩＤを、キー値の
昇ｊ幀に取り出すことができる。

さて、二次記憶１０８に格納されているデータ・ページ
およびインデックス・ページは、主記憶１０１のＩ１０
バッファ領域４０１に読み込まれてからデータベース処
理プログラム１０２によって処理される。

第４図に、Ｉ１０バッファ領域の構成例を示す。

■１０バッファ禎域４０１は、複数のバッファから成る
。各バッファには、■１０バッファ領域４０１の中で一
意な番号づけがなされており、この番号を以下バッファ
奇号と呼ぶ。１１０バツフア憤域４０１内の各バッファ
の主記憶１０１上でのアドレスは、バッフ７番号よシ定
まる。各バッファのサイズは、二次記憶１０８における
ページのサイズに等しい。

二次記憶１０８に格納されているデータ・ページまたは
インデックス・ページが、Ｉ１０バッファ領域４０１の
あるバッファ、例えばバッファ曹号ｌのバッファ４０２
に読み込簸れると、バッファ・ブイレフ）　リ４０３に
は、そのページのページ番号４０４と、そのバッファの
バッファ番号４０５のペアが登録される。

従って、二次記憶１０８のあるページが、ｌ［１０バツ
フア領域４０１に存在するか否かは、バッファ・ディレ
クトリ４０３ｅ探索して、そのページのページ番号が登
録されているか否かによって判定でき、かつ、そのペー
ジ番号とペアになっているバッファ番号からＩ１０バッ
ファ領域４０１中のどのバッファにそのページが読み込
まれたかがわかる。

ところで、■１０バッファ狽域４０１内のバッファに読
み込まれたインデックス・ページまたはデータ・ページ
の中のインデックス・エントリまたはスロットを、デー
タベース処理プログラム１０２が処理するには、エント
リもしくは、スロットの主記憶１０１におけるアドレス
を知る必要がアシ、ローＩＤから、そのローを格納して
いるスロットの主記憶１０１上のアドレスを調べる処理
ケ、ローのアドレス変換と呼ぶ。

また、インデックス・ベージ奎号から、そのインデック
ス・ページ内の先頭エントリのアドレスを調べる処理を
インデックス・ページのアドレス変換と呼ぶ。

まず、ローのアドレス変換処理を第５図のフローチャー
トを用いて説明する。

変数ＰＡＧＥす、５ＬＯＴ＋にそれぞれ変換の対象であ
るローＩＤ中のページ番号、スロット番号を代入する（
ステップ５０１）。

次にバッファ・ディレクトリ４０３を探索して、そのペ
ージ番号が、バッファ・ディレクトリ４０３中に登録さ
れているか否かを調べ（ステップ５０２）、登録されて
いれば、そのページが読み込まれているバッファのバッ
ファ番号から、そのバッファのアドレスを計算してｆ数
ＢＵＩｉ”ＦＡに代入する（ステップ５０４）。

登録されていない場合は、そのページを二次記憶１０８
から主起ｉ：依１０１のＩ１０バッファ領域４０１の適
当なバッファに読み込み、そのページ着号と、そのバッ
ファのバッフ７番号とのペアをバッファ・ディレクトリ
４０３に登録（ステップ５０３）した後、上述のステッ
プ５０４を実行丁Σ。

第２図で説明したデータ・ページの１４造から明らかな
様に、スロット番号（Ｓ　ＬＯＴ＃’）２０９　ＨＥ示
す該データページ２０４中の変位部２０７の内容とバッ
ファ・アドレスＢＵＦＦＡの和を計算することにより該
ローが格納されているスロットの主記憶１０１上のアド
レス変換ロることかできる（ステップ５０５，５０６）
。

一方、インデックス・ページのアドレス変換処理を、第
６図のフローチャートを用いて説明する。

まず、変換の対酸となるインデックス・ページのベージ
命号を変数ＰＡＧＥすに代入する（ステップ６０１）。

ステップ６０２，６０３，６０４は、ローのアドレス変
換におけるステップ５０２゜５０３．５０４と同一であ
り、そのインデックス・ページが読み込まれているバッ
ファの主記憶アドレスをめる処理である。第３図で説明
したインデックス・ページの構造から明らかな様に、イ
ンデックス・ページの変位部３０６の内容とそのインデ
ックス・ページが読み込まれているバッファの主記憶１
０１上のアドレスとの和を計算することによシ、インデ
ックス・ページの先頭エントリのアドレスがわかる（ス
テップ６０５　、６０６）。

以上、本発明の一実施例の構成と、基本となるデータ構
造と、アドレス変換処理の例を説明した。

以下、本発明のデータベース処理プログラム１０２の詳
細な動作例を、ある具体的な検索要求の処理手順を追い
ながら説明する。

本実施例で例題とする検索を第７図に示す。

検索対壕テーブルは、ＴＡＢＬ玖１）７１０．　ＴＡＢ
ＩＪＸ２）７１１の二つである。

ＴＡＢＬＥ（１）７１０は５ＴＵＤＥＮＴとＣＬＡＳＳ
の二つのカラムから、ＴＡＢＬＥ（２）７１１はＣＬＡ
ＳＳとＴＥＡＣＨＥＲの二つのカラムからそれぞれ成っ
ている。

ＴＡＢＬ玖１）７１１の５ＴＵＤＥＮＴカラムと、ＴＡ
ＢＬＥ（２）７１２のＣＬＡＳＳカラムには、それぞれ
インデックスＩＮＤＥＸ（１）７１３、ＩＮＤＥＸ（２
）７１４がつけられている。

検索要求７０１は、ｒＴＡＢＬＥ（１）とＴ　Ａ　Ｂ　
Ｌ　Ｆ、（２）で、それぞれのＣＬＡＳＳカラムの値が
等しいようなローのペアから５ＴＵＤＥＮ’［”カラム
とＴＥＡＣＨＥＲカラムの値のベアをすべて取シ出して
検索結果７０２として出力せよ」というものである。こ
の様な異なるテーブルを結合する処理はリレーショナル
・モデルではジョイン（ｊｏｉｎ）と呼ばれている。

次に検索処理制御部１０４の動作例を第８図のフローチ
ャートを用いて説明する。

検索処理制御部１０４は、検索要求７０１を解析する（
ステップ８００）。検索要求７０１中には、ＴＡＢＬＥ
（１）とＴＡＢＬＦｒ２）の全カラムが引用されている
ので、検索処理制御部１０４はＴＡＢＬＥ（１）とＴＡ
ＢＬ］１１２）の全レコードのベクトル化をベクトル展
開部１０３に指示する（ステップ８０１゜８０２）。

ここでテーブルのベクトル化とは、第２図で示したよう
な構造で、データページ２０４内に格納されている該テ
ーブルの各カラムを一次元配列（ベクトル）の形式〒主
記憶１０１のｆＥ　業領域１０６上に展開することを意
味する。

すなわち、ＴＡＢＬＥ（１）のベクトル化の結果、ＴＡ
ＢＬＥ（１）（７）各ｏ−Ｉ）ＳＴＵＤＥＮＴ　カラム
ｔＤ値ヲベクトル形式で並べたベクトルＤｏおよびＣＬ
ＡＳＳカラムの値をベクトル形式で並べたベクトルＤＩ
が作業領域１０６に格納される。

同様に、ＴＡＢＬＥ（２）のベクトル化の結果、ＴＡＢ
ＩＪ（２）　ノ各０−４１ＣＬＡＳＳ　カラムノ値ノベ
クトルＤ２およびＴＥＡＣＨＥＲカラムの値のベクトル
Ｄ８が作業領域１０６に格納される。

Ｔ　Ａ　Ｂ　Ｌ　Ｅ（１襲よびＴＡＢＬＥＩ２）のベク
トル化が完了すると、検索処理制御部１０４は、ベクト
ル処理部１０５にステップ８０１，８０２で作られたベ
クトルＤｏ　、ＤＢ　を用いてベクトル型の二進探索を
行なうように指示する（ステップ８ｏ３）。

ベクトル処理部１０５における該ベクトル型二進探索が
完了すると、検索処理制御部１０４は、ベクトル処理部
１０５に、ベクトル処理部１０５によって作業領域１０
６に格納された該ベクトル型二進探索結果、およびベク
トルＤｏ　、Ｄｓ　ｆ用いて検索結果を出力するよう指
示する（ステップ８０４）。　。

以上が、検索要求７０１が入力された場合の、検索処理
制御部１０４の動作である。

次に、第９図のフローチャートを参照しながらベクトル
展開部１０３の動作を説明する。

ベクトル展開部１０３は、ＴＡＢＬＥ（１）のベクトル
化を検索処理制御部１０４に指示される（第８図ステッ
プ８０１）と、カウンタｉをリセットし、ＩＮＤＥＸ（
１）の最左リーフ・ページ番号を調べ、変数ＩＸＰＡＧ
Ｅ＋に代入する（ステップ９０１）。

次のステップ９０２で、第６図の７０−チャートで示し
た手順によシ最左リーフ・ページ番号Ｉ’ＸＰＡＧＥ４
−のアドレス変換を行なってその最左リーフ・ページの
先頭エントリの主記憶１０１上のアドレスをめ、変数Ｅ
ＮＴＲＹＡにセットする（ステップ９０２）、次１ｃ　
ＥＮＴＲ，ＹＡ　Ｋよって、ポイントされるエントリの
中か６、ローＩＤを取シ出し、第５図のフローチャート
で示した手順によシそのローＩＤのアドレス菱換を行な
って、そのローが格納されているスロットの主記憶１０
１上のアドレスをめ、定数５ＬＯＴＡに代入しくステッ
プ９０３）、さらに、５ＬＯＴＡでポイントされるスロ
ット力らＴＡＢＬＥ（１）Ｏ８ＴＵＤＥＮＴ　カラムと
ＣＬＡＳ８カラムとの値を取シ出し、それぞれ作業＝ｘ
戦ｉｏＧ上のベクトルＤｏ、ＤＩのｉ番目の要素Ｄｏ　
（ｉ）、　ＤＩ（ｉ）として格納する（ステップ９０４
）。

そして、カウンタｉｆ：＋１１．（ステップ９ｏ５）、
続いてＥＮＴＲＹＡが指すエントリにまだ処理していな
いローＩｆ）が残っているが否がをチェックしくステッ
プ９０６）、残っていればステップ９０３へ戻り、未処
理ローＩＤの処理を開始する。残っていなければ、ＥＮ
ＴＲ，ＹＡが指すエントリの最後の部分を調べて、次の
エントリがらるが否かをチェックする（ステップ９ｏ７
）。もし次エントリがあれば、ＥＮＴＲＹＡに次エント
リの主記憶１０１上のアドレスをセット（ステップ９０
９）した後、ステップ９０３へ戻シ、次エントリの処理
を行なう。次エントリがなければ、現在処理中のインデ
ックス・ページ（ページ番号：　ＩＸＰＡＧＥ＋）の前
方ページがあるか否かをチェックして（ステップ９０８
）、あれば、ＩＸＰＡＧＥ寺に前方ページのページ番号
をセット（ステップ９１０）してから、ステップ９０２
へ戻り、前方ページの処理を開始する。ステップ９０８
の判定の結果、前方インデックス・ページがないと判明
した場合、処理が終了する。

第３図のインデックス・ページの説明において述べたよ
うに、最左リーフページから前方のリーフ・ページを次
々とたどることによシ、テーブルノ全ローを、インデッ
クスのついたカラムの値の昇順にアクセスすることがで
きるので、第９図の処理手順によって、ＴＡＢＬＥ（１
）の全ローの、５ＴＵＤＥＮＴカラム値とＣＬＡＳＳ　
カラム値がそれぞれベクトルＤｏとＤ！に格納される。

また、ＩＮＤＥＸ（１）は５ＴＵＤＥ４’ＪＴカラムに
つけられたインデックスであシ、ベクトルＤＯは、昇順
にソートされている。

検索処理制御部１０４の指示によｐ４　ＴＡＢＬＥ（２
）もＴ　Ａ　Ｂ　Ｌ玖１）と同様に、第９図の処理手順
によってベクトル化される。すなわち、ＩＮＤＥＸ（２
）の最左リーフページ番号をＩＸＰＡＧＥすにステップ
９０１でセットしてからステップ９０２以降を実行する
（但しステップ９０４でｊ＝２．ａとする）ことにより
、ＴＡＢＬＥ（２り全ローのＩｃＬＡｓｓカラム値と、
ＴＩＣＨＥＲ力２ム値とが、それぞれベクトルＤ２とＤ
３に格納される。ＩＮＤＥＸ（２）はＣＬＡ８８カラム
につけられているのでベクトルＤ２は昇順にソートされ
る。

第８図で説明した様に、ベクトル展開部１０３で、ＴＡ
ＢＩＪ（１）　ｋよびＴ　Ａ　Ｂ　Ｌ　Ｅ＜２）が検索
処理制御部１０４の指示によってベクトル化されてベク
トルＤｏ−＝ＤＨが作業領域１０．６上に作られると、
検索処理制御部１０４はＤＩを比較キーベクトルとして
Ｄｚ内をベクトル型二進探索する様、ベクトル処理部１
０５に指示する（ステップ８０３）。

次に、ベクトル処理部１０５におけるベクトル型二進探
索の処理手順を、第１０図のフロー・チャートを参照し
ながら説明する。

まず、第１０図のフローチャートで用いられている変数
の意味を述べる。

Ｎｌは、ＴＡＢＬＥ（１）７）ＣＬＡＳＳカラム値のベ
クトルＤ、の長さであり、Ｎ２はＴＡＢＬ玖２）のＣＬ
ＡＳＳカ２ム値のベクトルＤ２の長さである。

ｉは、実行回数のカウンタである。Ｌ、Ｕ、Ｃはいずれ
も作業領域１０６に置かれる長さＮｌのベクトルであり
、Ｌは探索範囲の下限、Ｕは探索範囲の上限、Ｃは探索
範囲の中央をそれぞれ示す。

Ｍは長さＮ１のビット列であシ、比較結果を格納する（
以下Ｍをマスクと呼ぶ）。

二進探索結果は、ベクトルＵに格納される。

第１０図のベクトル型二進探索プログラムの機能は、ベ
クトルＤ＋の各要素、ＤＩ（ｊ）（ｊ＝０゜・・・・・
・ｔＮＩ−ｘ）ＶＣ対し、ソート済みのベクトルα内に
ＤＩ＜１）と値が等しいようなりｘ（ｋ）かめればｋを
Ｕ（ｊ）に返すことである。但し、ＤＩ（ｊ）に等しい
ようなり２の要素が複数存在する場合、すなわちＤｚ（
ｋｏ）＋−”Ｄｚ（ｋｔ−＋　）がすべてＤＩ（ｊ）に
等しい場合には、Ｕ（ｊ）に”（ｋｏ、・・・・・・ｙ
ｋ’−ｔ）を返すこととする。

第１０図のフローチャートを参照しながら、ベクトル処
理部１０５における、ベクトル型二進探索の手順を説明
する。

実行回数のカウンタｉをリセットしくステップ１００’
ｌ）、探索範囲の下限ベクトルＬと上限ベクトルＵを初
期化する（ステップ１００２．１００３）。

最初の探索（ｉ　＝　Ｏ）では、探索範囲はＤ２全域で
あるので、下限ベクトルＬの全要素はＯでアシ、Ｕの全
要素はＮ２−１である。ステップ１００２゜１００３は
ともに、あるスカラ値をベクトルの全要素に代入するよ
うなベクトル命令によって処理される。

そして、カウンタｉとｔｏｇ１％を比較しくステップ１
００４）　、カウンタｌの値がｌｏｇＮｚ以モであれば
終了し、そうでなければステップ１００５゜１００６お
よび１００７を実行し、カウンタｉを＋１（ステップ１
００８）してステップ１００４に戻る。

すなわち、ステップ１００５〜１００７はｔｏｇＮ２回
実行される。

ステップ１００５で、探索範囲の中での中央の位置の計
算をＤｌの各要素（つまシ比較キー）毎に行なう。ステ
ップ１００５は、下限ベクトルＬと上限ベクトルＵを要
素毎に加算して２で割った商を中央ベクトルＣの対応要
素に格納するベクトル命令により実行される。次にＤＩ
の各要素Ｄｔ（ｊ）＜ｊ＝ｏ、・・・・・・、Ｎ１−１
）と、要素対応にステップ１００５で計算された探索範
囲の中央に位置するＤｌの各要素Ｄ２　（ｃ（ｊ））　
（ｊ＝ｏ、・・・・・・、Ｎ１−１）とを比較し、ＤＩ
（ｊ）すなわち比較キーの方が小さければマスクＭの第
ｊビットを０とし、そうでなければマスクＭの第ｊビッ
トを１とする（１００６）。マスクＭの第ｊビットが０
、すなわち、被比較値Ｄａ　（Ｃ（ｊ））が比較キーＤ
ｔ（ｊ）より小さい時は、各比較キーに対応する新しい
探索下限Ｌ（ｊ）としてＣ（ｊ）の値を格納し、マスク
Ｍの第ｊピットが１、すなわち被比較値Ｄｘ　（Ｃ（Ｊ
））が比較キーＤｇ（Ｊ）と等しいか、又は大きい時は
、その比較キーに対応する探索上限Ｕ（ｊ）としてＣ（
ｊ）の値を格納する（ステップ１００７）、。ステップ
１００６．１００７ともにベクトル命令で実行される。

ベクトルＤ２は昇順にソート済みであるのでステップ１
００７の結果、各比較キ一対応にＵ、Ｌに記憶されてい
る探索範囲は半分となシ、従ってステップ１００５〜１
００７　をｌｏｇｚＮ２　回繰返すことにより、各比較
キーに等しいＤｌの要素を探索することができる。ステ
ップ１００６で、探索範囲の中央のＤｌの要素と、キー
値が等しい時には、ステップ１００７で中央位置を、次
の探索におけるキー値に対応する探索範囲の上限として
いるので、探索終了時には、Ｄｚ内にキー値Ｄ＋（ｊ）
に等しい要素が複数存在する場合にも、その複数要素の
うち、Ｄｚ内で最初に現われる要素を位置が上限ベクト
ルＵ０）として得られる。

ベクトル処理部１０５によって、第１０図の７０−・チ
ャートに示したベクトル型二進探索が行なわれ、作業領
域１０６上のベクトルＵに探索結果が得られると、第８
図の７０−チャートで説明した様に検索処理制御部１０
４はベクトル処理部１０５１ｃ、ベクトルＤｏ　、Ｄｒ
およびＵを用いて検索要求７０１の結果を出力する様に
指示する（ステップ８０４）。

次に、ベクトル処理部１０５におけるジョイン結果の作
成手順を第１１図の７０−・チャートを用いて説明する
。

第１１図において、ｉはＤＩの処理要素を示すポインタ
で６り、ｊはＤｌの処理要素を示すポインタである。ｉ
のリセットを行なった（ステップ１１０１）後、ｊに、
第１０図に示した処理手順によって作成されたベクトル
型二進探索結果のベクトルＵの第１番目の要素Ｕ（ｉ）
を格納する（ステップ１１０２）。次にＤｌ（ｉ）とＤ
ｌ（ｊ）を比較する（ステップ１１０３）。

Ｄｒ　（ｉ）とＤｚ（ｊ）が等しい時、Ｄｔ（ｉ）はＴ
ＡＢＬ玖１）のあるローのＣＬＡＳＳ　カラムの値であ
り、Ｄｌ（ｊ）はＴＡＢＬＥ（２）のめるローのＣＬＡ
ＳＳ　カラムの値である。従ってり。（ｉ）とＤｓ（ｊ
）は、それぞれのＣＬＡＳＳカラム値が等しいようなＴ
ＡＢＬＥ（１）のローの５ＴＵＤＥＮＴカラム値と、Ｔ
ＡＢＬＥ（２）のローの′ＴＥＡＣＨＥＲ，力２ムの値
であシ、検索要求７０１における検索条件を満たしてい
るので検索結果の１つとして出力する（ステップ′１１
ｏ４）。

Ｄｌはソートされておシ、かつ第１０図のベクトル型二
進探索処理で説明したようにｏ２（ｊ）、すなわちＤｌ
　（Ｕ（ｉ））は、ＤＩ（ｉ）に等しいような良の要素
のうち一番最初の要素であるから、ＤＩ　（ｉ）に等し
いＤｌの要素が複数ある場合には、Ｄｌ（Ｕ（ｉ））か
ら始まって、Ｄ２内で連続して並んでいる。

従って、ｊを＋１して（ステップ１１０５）　ｊがＮ以
上となるか（ステップ１１０６）またはＤＩ（ｉ）’Ｆ
Ｄ２（Ｊ）となる（ステップ１１０３）までＤｏ（＋）
とＤｓ（Ｊ）のペアを出力する（ステップ１１０４）こ
とにより、ＤＩ（ＤとＤｌ（ｊ）が等しいようなすべて
のｊ　ｖｃツイて、Ｄｏ　（ｉ）とｏ３（ｊ）を出力す
ることができる。

ＤＩ（ｉ）と０２（ｊ）が等しくない時には、ｆ）＋（
＋）に等しいＤｌの要素が存在しないから、ｉを＋１し
て（ステップ１１０７）　ｉがＮ、よシ小さいならば（
ステップ１１０８）、ステップ１１ｏ２に戻ってＤｌの
次要素の処理を行なう。

判定ステップ１１０８で、カウンタｉがＮ１以上となっ
た時には、ＤＩの全要素の処理を完了し、検索結果の出
力を終了する。

ベクトル処理部１０５での第１１図のフロー・る（ステ
ップ８０５）。

本実施例によれば、第９図で動作を説明したベクトル展
開部１０３によって、テーブルをベクトル形式に変換す
るので、第１０図で示したベクトル型の二進探索のよう
に、ベクトル命令を有効に用いた高速処理が可能となる
。

また、本実施例の処理手順によれば、アクセス単位がテ
ーブルおよびインデックスである、即ち、ローのアドレ
ス変換およびインデックス・ページのアドレス変換をベ
クトル展開部１０３の中で、ローとインデックス・ペー
ジのそれぞれについて一括してただ一度のみ行なうので
、従来のローあるいはインデックスページ単位のアクセ
スによるデータベース方式に比べてアドレス変換回叡を
太幅に削減できる。

本実施例におけるアドレス変換回数の削減効果を示すた
めに、検索費求７０１の従来の処理方式による処理例を
、第１２図を参照しながら説明する。

従来方式では、まずＩＮＤＥＸ（１）を用いてＴＡＢＬ
Ｅ（１）のローのローＩＤを一つ取り出してアドレス変
換を施こし、そのローＩＤを有するローを取り出し、そ
のローのＣＬＡＳＳカラムの値Ｘを調べ（ステップ１２
０１〜１２０４）、次ｌＩ？：Ｘを比較キーとして、Ｉ
　Ｎ　Ｄ　ＥＸ（２）内を、ルートページから順にイン
デックス・ページの変換を行ないながらリーフ・ページ
までＸに従ってたどる（１２０５）ことによって、ＴＡ
ＢＬＥ（２）のローであってそのＣＬＡＳＳカラム１直
がＸに等しいものがあればすべて取り出して検索結果と
して出力する（ステップ１２０６〜１２０８）。

以下、次に処理するＴ　Ａ　Ｂ　Ｌ　Ｅ（１）のローを
取シ出した後（１２０９→１２０３，１２０９→１２１
０→１２１２→１２０３、または１２０９→１２１０→
１２１１→１２１３→１２０２→１２０３）、上記１２
０４〜１２０８の処理をＩＮＩ）ＥＭＩ）の全リーフ・
ページを探索しつくすまで繰シ返していた。

すなわち、アドレス変換は、ローまたはインデックス・
ページ単位に必要になシ次第随時行なわれていた。

第１２図に示した従来方式（レコード単位のアクセス）
と、本実施例（テーブル・インデックス単位の一括アク
セス）との、それぞれにおけるアドレス変換回数の比較
を第１３図に示す。

第１３図において、ＮｌはＴ　Ａ　Ｂ　Ｌ　Ｅ（１）の
ロー数、Ｎ２はＴＡＢＬＥ（２）のロー数、ＭｌはＩ　
Ｎ　Ｄ　ＥＸ（１）のページ数、Ｍ２はＩ　Ｎ　Ｄ　Ｅ
Ｘ（２）のページ数、Ｎ３は検索結果の出力数である。

従って、従えば、一つの学級（ＣＬＡＳＳ）に−人の担
任教師（ＴＥＡＣＨＥＲ）がおり、−学級（ＣＬＡＳＳ
）にＵ３Ｏ人の生徒がいるとすれば、教師の総数ｔ−Ｎ
人とし、さらに１インデツクス・ページには、１０個の
ローＩＤが格納されているとして、Ｎ宜　＝５　ＯＮ、Ｎ２　＝Ｎ、Ｎｓ　＝５　ＯＮとな
る。

従って従来方式では本実施例ではのアドレス変換が必要となシ、これは、Ｎ＝１００では
、従来方式が２６８６０回、本実施例では５３５５回で
必シ、約１１５に削減される。

また、ベクトル展開部１０３で一度ベクトル化したテー
ブルを別の検索に対して用いる時には、該検索に対する
アドレス変換は全く不要となる。

本実施例では、テーブルのベクトル化の際、全てのカラ
ム値のベクトルを作成したが、メモリの効率的利用のた
めに、第９図に示したベクトル展開部１０３のステップ
９０４１Ｃおけるカラム値ベクトル作成の代わシにスロ
ット・アドレスのベクトルを作成して、データ（カラム
値）のベクトルは作成せず、スロット・アドレス・ベク
トルを用いて、ローへのアクセスを行なっても良い。

さらに、検索処理において必要なカラムにインデックス
が付与されている場合も例えば、’Ｉ”ＡＢＬ玖２）の
ＣＩ、Ａｓ　Ｓカラムに対するＩＮＤＥＸ（２）が存在
する場合、第９図のステップ９０３　、９０４を実行せ
ずに、エントリ内のキー値をそのエントリ内のローＩＤ
の個数分だけ連続アドレスに格納していくことによＪ）
、Ｄｚに等しいベクトルを作成でき、ＴＡＢＬＥＸ２）
のベクトル化（ローＩＤの変換）は不要となる。

この時、キー値に属するローＩＤのベクトルも同時に作
成しておけば、ベクトル処理部１０５における第１１図
の処理の中で、ＴＡＢＬＦ＆２）のＴＥＡＣＨＥＲカラ
ム値（Ｄｓの要素）が必要となった時、そのローＩＤを
アドレス変換して該カラム値を取シ出して出力すること
ができる。

この方法によれば、第１３図に示したＴＡＢＬＥ（２）
に対して必要なアドレス変換回数は、Ｎ３回となυ、従
来方式と同一となる。

この方法は検索出力Ｎ３が少ないと予想される時に有効
となる。

また、第９図に示したベクトル展開部１０３の動作では
、テーブルの全ローをベクトル展開したが、検索に全ロ
ーが不要な場合、例えば検索要求７０１で、Ｔ　Ａ　Ｂ
　Ｌ　Ｅ（１）のＣＬＡ８Ｓカラムに対し、ＴＡＢＬ玖
１）のＣＬＡＳＳ　（４という条件が付加されている際
には、ＩＮＤＥＸ（１）のり−７ページのうち、キー値
が４未満のリーフページに格納されているローＩＤのみ
を変換して、ＴＡＢＬＩＩ！１）を部分的にベクトル化
することも容易である。こうすれば、アドレス変換回数
およびメモリ使用量の削減をさらにはかれる。

本実施例では、アドレス変換回数の削減効果について説
明したが、データベース処理システムにおける、レコー
ドへのアクセスに伴なう種々の処理、例えば複数ユーザ
が同一レコードにアクセスする可能性のある場合のレコ
ードのロック処理や、アクセス中のページの主記憶上に
おける位置の固定処理なども、全く同様の一括化により
その回数が削減される。

〔発明の効果〕

以上述べた様に、本発明によれば、複数レコードに対す
るアドレス変換を一括して、各レコードに対しただ１度
行なうので、不要なアドレス変換がなくなシ、アドレス
変換回数が大幅に削減され、また、一括してアドレス変
換したレコード群をベクトル形式に展開しておくので、
ベクトル処理が可能で、処理の高速化が達成されるとい
う効果がらる。

【図面の簡単な説明】

第１図は本発明の一実施例を示すブロック図、第２図お
よび第３図は第１図のデータベースのデータ構造図、第
４図は第１図のＩ１０バッファ領域４０１の詳細な構造
図、第５図はローのアドレス変換手順を示すフローチャ
ート、第６図はインデソクスベージのアドレス変換手順
を示すフローチャート、第７図は第１図の実施例で処理
される検索例を示す説明図、第８図は第７図の検索例を
処理する場合の第１図の検索処理制御部１０４の動作例
を示すフローチャート、第９図は第７図の検索例を処理
する場合の第１図中のベクトル展開部１０３の動作例を
示すフローチャート、第１０図および第１１図は、第７
図の検索例を処理する場合の第１図中のベクトル処理部
１０５の動作例を示すフローチャート、第１２図は、第
７図の検索例を従来方式で処理する場合の処理手順を示
すフローチャート、第１３図は、第７図の検索例の流側
における方式とで比較した説明図である。１０１・・・主記憶、１０２・・・データベース処理プ
ログラム、１０３・・・ベクトル展開部、１０４・・・
検索処理制御部、１０５・・・ベクトル処理部、１０６
・・・作業領域、４Ｏ１・・・Ｉ１０バッファ領域、１
０８・・・二次記憶、１０９・・・データベース、１１
０・・・中第Ｚ口暴３図第４図第６図・纂８０＄７０霞

Claims

【特許請求の範囲】１、主記憶装置と、レコードに対する識別子と、該識別
子を、該レコードの該主記憶装置内での格納アドレスに
変換する手段とを有するデータベース処理システムにお
いて、参照されるレコード群全予測する手段を設け、該
レコード群に対応する識別子群を前記アドレス変換手段
によって一括して前記主記憶装置内での格納アドレス群
に変換することを特徴とするデータベース処理方式。２、上記予測手段により得られた参照が予想されるレコ
ード群または該レコード群の上記主記憶装置内での格納
アドレス群を上記上記ｊ１装置内にベクトル形式で展開
する手段を設け、該ベクトル形式で展開されたレコード
群またはアドレス群を、ベクトル命令により一括処理す
ることを特徴とする特許請求の軛囲第１項記載のデータ
ベース処理方式。