第７章データベース管理システム７．１データベース管理システムの概要７．２データベースの格納方式７．３問合せ処理７．３問合せ処理１．問合せ処理の概要 (a) 問合せ処理手順 ①問合せを内部表現に展開する。 ②内部表現をより効率良く処理できる形に変形する（最適化） ③効率の良い処理プランを生成し記憶する。 ④処理プランを実行する。 (b) 内部形式の例（問い合わせグラフ） SELECT 業者名 FROM 業者 WHERE 所在地='東京' AND 業者番号 IN (SELECT 業者番号 FROM 取引 project 業者.業者名 WHERE 個数>200) project ：射影 join ：結合 restrict ：制限 join 業者.業者番号=取引.業者番号 restrict 所在地='東京' restrict 個数>200 業者取引関係代数による表現 Proj [業者.業者番号]((Rest [個数>200] 取引） Join [取引.業者番号=業者.業者番号] (Rest [所在地='東京'] 業者)) project 業者.業者名 project ：射影 join ：結合 restrict ：制限 join 業者.業者番号=取引.業者番号 restrict 所在地='東京' restrict 個数>200 業者取引最適化の考え方以下の選択肢の中から最も効率が良いと予測される方法を選択する。 ①制限は結合の後で行うこともできるのでどちらを先にやるか。 ②結合の順序を入れ替えても同じ結果になるのでどちらの結合を先にやるか。 ③どの枝を先に処理するか。 ④関係をアクセスするのに索引を使用するかしないか。２．基本演算の処理方法 (a) 制限の処理方法【例】 SELECT 部品番号 FROM 部品 WHERE 部品名＝'ボルト' AND 大きさ=20 最も簡単な関係スキャン部品のタプルをすべて読み、ひとつひとつ条件をチェックする。表が大きい場合は効率が悪い。ただし、どちらかの検索条件中にキーが含まれている場合や、属性に索引がついていればキー指定呼び出しができる。キー指定呼び出し索引のある属性を用いて、その属性に関する条件を満たすタプルだけを呼び出す。（一部のレコードだけを呼び出す）【両方に索引がある場合】 ①どちらかの索引によりタプルを呼び出し、もう一方の条件をチェックする方法。 ②２つの索引を用いてどのタプルが条件を満たすかを判別してからタプルを呼び出す。複数の属性に索引が付けられている場合どの索引を用いるかによって効率が異なる。複数の処理プランを比較し、コストを比較することが必要 (b) 結合の処理方法 ①入れ子ループ法一方のタプルを１つ読み出し、それと結合できるタプルを他方の関係から読み出して結果を生成し、繰り返す。 ②マージ結合法それぞれの関係を結合対象の属性の値でソートした後、両者を昇順（または降順）に読みながら比較し結合処理を行う。ソート時間がかかるが、結合処理は短い。 ③ハッシュ結合法結合条件が統合の場合にのみ適用可能。それぞれの関係のタプルの結合対象属性値をハッシュし、ハッシュ値が同一のタプルの組合せについて結合可能かを判定して結果を生成する。結合の順序 R join S S join R 結果は同じだが、両者のタプルの数、属性の数の組合せによって処理時間が異なる。３．問合せの最適化 ①一般の問合せでは、基本演算の組合せで処理するので最適化が複雑になる。 ②実際のデータの統計的性質を用いても完全に予測することは難しい。 ③逆に最適化処理のための時間が増大し、逆効果になることもありうる。経験則に照らして、多くの問合せに対して効率がよいとわかっている方法に限定する。制限演算の優先（経験則）制限演算を先に行ってから他の処理を行う。タプルを少なくしてから他の処理をすると処理時間を短縮できる。処理負担の大小（経験則） ①ANDで結ばれたWHERE句では処理木の葉から根元に向けて処理されるので、後に処理負担の軽い条件を記述するほうが効率的。すなわち処理負担の重い条件を先に記述する。 ②ORで結ばれたWHERE句では、並列に並ぶ処理木に変換され、最初の方から処理されるので、ANDとは逆に処理負担が軽い条件から記述する方が効率的。関係代数式の変形複数の式で同一の結果が得られることが多い等価な関係代数式を求めよりコストの小さな表現を選ぶ。変形規則以下のような変形規則を用いて最適な問合せに変形（統計的な処理時間予測が必要） ①結合と直積の可換則（演算対象の入替え） ②結合と直積の結合則（演算順序の入替え） ③射影の吸収（複数の射影を１つの射影に変換） ④制限の可換と複合（複数の制限を１つの複合制限に変換） ⑤制限と射影の交換 ⑥制限の分配（制限と他の演算の交換） ⑦射影と直積の交換 ⑧射影と和の交換 ⑨制限条件と和の交換 ⑩制限条件と積の交換