入れ子型リレーションに対する結合演算問い合わせの最適化アルゴリズムとその評価

概要

論文の詳細を見る
入れ子型リレーショナルモデルはリレーショナルモデルの拡張として提案され,より複雑な構造を持つデータを支援することが可能である.本論文では,入れ子型リレーショナルデータベースに対する結合演算問い合わせの最適化アルゴリズムを提示し,その有効性の評価を行う.本アルゴリズムは,入れ子型リレーションに対する結合演算の一種である入れ子型結合と埋込みの2種類の演算を対象とし,これらの演算からなる問い合わせに対する左連鎖線形処理木を導出する.この左連鎖線形処理木は,ある種の仮定の下で全左連鎖線形処理木のうちで最小コストのものとなる.また,シミュレーション実験により上記の仮定が厳密に成立しない状況下での本アルゴリズムの有効性を検証する.実験結果によれば,本アルゴリズムはこのような状況下でも全左連鎖線形処理木のうち最小コストの処理木,あるいは最小コストに近い低コストの処理木を導出する.また,本アルゴリズムが導出する処理木は,一般の線形処理木全体の中でも低コストのものであることが明らかとなった.
一般社団法人情報処理学会の論文
1994-09-15