関係データベースの各種の処理の中で特に2つのリレーションを動的に結合する結合演算は処理負荷が重く,数々のアルゴリズムが開発されてきたが,中でもハッシュ法に基づくアルゴリズムが現時点で最も有望と考えられている.また近年,並列計算機システムが一般化しつつあり,並列アーキテクチャの採用による並列関係データベースシステムの性能向上が注目されている.このような背景から,我々はハッシュに基づく結合演算方式としてGRACEハッシュ結合演算技法を取り上げ,シンメトリS81共有メモリ型マルチプロセッサ上に実装を行い,結合演算の性能評価を詳細に行い,理想的な並列台数効果を確認するとともに,その有効性を明らかにした.本論文ではGRACEハッシュ結合演算技法の並列化手法について検討するとともに,その実装化について考察し,更に実装システムの性能評価により,関係データベースの共有メモリ型並列プロセッサによる性能向上の有効性について明確化する.

"スーパーデータベースコンピュータ(SDC)"は,現在我々が開発中の高並列関係データベースサーバである.SDCは,数台(4~6台)のマイクロプロセッサと磁気ディスク装置とを共有バスで密結合して処理モジュールとし,さらに複数の処理モジュールをネットワークで疎結合したハイブリッドアーキテクチャをとる.また,結合演算に対するアルゴリズムとして,"バケット分散GRACEハッシュ"法を採用し,これをハードウェアで支援するために,"バケット平坦化機能"を有するオメガネットワークの提案がなされている.このネットワークは,各スイッチ素子自体が局所的な履歴に基づいて適応的なルーティングを行ない,競合によるスループットの低下と処理モジュール毎の負荷の偏りに起因する性能向上の限界とを同時に解決することを目指したものであり,その有効性はすでにシミュレーションにより確認されている.また,バケット平坦化機能にはこれまでにいくつかの拡張が施されてきたが,処理モジュール数はネットワークの大きさに等しいと仮定され,ネットワークの性質から2^nに限られてきた.しかし,各処理モジュールの故障に対するロバスト性を向上させ,また, 処理の規模に応じて徐々にシステムを拡張できるようにするには,任意のモジュール数が許されることが望ましい.そこで今回,これまでの制限を除き,ネットワークの大きさと異なる任意数の処理モジュールの間で負荷分散を可能にするアルゴリズムを開発した.本論文では,この新たなアルゴリズムを用いた時のネットワークの動作特性を,シミュレーションによる解析結果に基づいて述べる.