Projection - Evaluating Relational Operation - Database Management Systems
Database Management Systemsの14章。
マインドマップから再構成したまとめ
Projection の手順
- 不要 attribute を削除
- 重複 tuple の削除
Projection based on Sorting
- Scan して attribute 削除
- tuple を Sort
- sort result を scan して重複を削除
- External sorting 大活躍
Projection based on Hashing
- 前提：データに対して十分大きな Buffer pages が存在する事
- データを入力バッファ 1 page に読み込み、全ての tuple に対して h() を適用し 1 〜 B - 1 のどれかのページに書き込む
- 1 〜 B - 1 を 1 page ずつ読み込み、その中の tuple に対して h2() を適用し重複かどうか調べて書き出す
Hash と Sorting どちらが良いの？
- 基本的には Sorting がよく使われる。うれしい副作用として結果が Sort 済みになるということも。
- Hash は以下の点で不利
- 分布が一様でないと困る
- メモリにフィットしないと困る
- そもそも重複が大量にあると困る
所感
- 次は Join 。Join は手強いぞ。がんばれ。
