PowerPoint プレゼンテーション

Database System Implementation
データベース論－問合せ最適化編
参考教科書
H. Garcia-Morina, J. D. Ullman, and J. Widom.
Database System Implementation.
Prentice Hall, 2000, ISBN 0-13-040264-8
Chapter 6, 7
森下真一
平成１5年度夏学期
Database System Implementation
問合せの代数
関係
Database System Implementation
name, department, weight
属性
例
レコード
属性の値の線形リスト
(Tom, IS) (Paul, Physics)
関係
レコードの集合
R(name, department)
R(name, department)={ (Tom,IS), (John,IS),(Paul,Physics) }
name
department
Tom
IS
John
IS
Paul
Physics
レコード t=(Tom, IS)
t[name] = Tom
t[name,deparment] = (Tom,IS)
Bags と集合意味論
Database System Implementation
Bags 意味論
name
Tom
Tom
Tom
John
John
score
32
29
32
45
48
集合意味論
name
Tom
Tom
John
John
score
32
29
45
48
{ (Tom,32), (Tom,29), (Tom,32), (John,45), (John48) }
問合せの代数
Database System Implementation
•
•
•
•
•
•
•
•
•
和交わり差
重複削除
選択
射影
積
ジョイン (Natural, Equi-, Theta-)
dangling レコード
セミジョインアウタージョイン
グループ分け
和交わり差
Database System Implementation
おなじ属性をもつ関係 R と S
Bags意味論での定義
和
(Union)
R∪S
交わり
R∩S
(Intersection)
差
(Difference)
RーS
各レコード r は R と S に出現する
回数の和だけ、r は R ∪ S に出現
各レコード r は R と S に出現する回数
で少ない方の回数だけR ∩ S に出現
各レコード r は R と S に出現する
回数の差だけ R － S に出現
R={0,1,1,1,3,3}
S={1,2,2,3,3,3}
R ∪ S = {0,1,1,1,1,2,2,3,3,3,3,3}
R ∩ S = {1,3,3}
R ー S = {0,1,1}
和交わり差
Database System Implementation
Bags 意味論
R={0,1,1,1,3,3} S={1,2,2,3,3,3}
R ∪ S = {0,1,1,1,1,2,2,3,3,3,3,3}
R ∩ S = {1,3,3}
R ー S = {0,1,1}
集合意味論
R={0,1,3} S={1,2,3}
R ∪ S = {0,1,2,3}
R ∩ S = {1,3}
R ー S = {0}
重複削除
Database System Implementation
関係 R 中の重複したレコードを除く演算 δ(R)
R
a
1
2
2
δ(R)
b
2
3
3
a
1
2
b
2
3
SQL では DISTINCT が重複を除去
SQL での UNION, INTERSECT, EXCEPT は集合意味論
R UNION S は δ(R ∪ S) に対応
以降は bags 意味論。必要におうじて重複除去して集合意味論。
選択 (Selection)
Database System Implementation
関係 R から条件 C をみたすレコードを選択 σCR
条件 C の中では、たとえば
(1) 数式演算 (四則など）や文字列処理演算
(2) 比較演算（<,>,等）
(3) 命題論理の結合子（AND, OR, NOT）
a
0
2
2
3
3
b
1
1
1
1
5
σa>1R(a,b)
a
2
2
3
3
b
1
1
1
5
σa>1 AND NOT(a+b>5)R(a,b)
a
2
2
3
b
1
1
1
射影（Projection）
Database System Implementation
関係 R のレコードを属性リスト L へ射影 πLR
L の属性としては
(1) 関係 R の属性そのもの
(2) R の属性から、 a+b → x のように属性をつくってもよい
πa+b→x, a+c→yR(a,b,c)
a
b
c
x
y
1
2
3
3
4
2
1
2
3
4
3
2
5
5
8
5
0
3
5
8
Bags
意味論
積（Product）
Database System Implementation
関係 R、 S からレコードを選択し連結したレコードの全体 R × S
同一名の属性 a が R と S に現れる場合 R.a, S.a と改名
R×S
R
a
1
2
2
S
b
2
3
3
a
4
5
c
5
6
Bags 意味論
R.a
1
1
2
2
2
2
b
2
2
3
3
3
3
S.a
4
5
4
5
4
5
c
5
6
5
6
5
6
ジョイン(Join)
Database System Implementation
複数の関係に、積・選択・射影を適用してつくる関係
Natural (Equi-)Join R wv S = πL(σC(R × S))
条件 C は R と S に共通する属性 a,b,… を等しいとみなす
R.a=S.a AND R.b=S.b AND …
属性リスト L は a,b,…
属性の重複、たとえば R.a と S.a は一つにまとめる
R
a
1
2
2
S
b
2
3
4
a
1
2
R wv S
c
5
6
a
1
2
2
b
2
3
4
c
5
6
6
Natural Join の例
Database System Implementation
R
a
1
2
2
R×S
S
b
2
3
4
a
1
2
c
5
6
R wv S
= πR.a→a,b,c(σR.a=S.a(R × S))
a
1
2
2
b
2
3
4
c
5
6
6
R.a
b
S.a
c
1
2
1
5
1
2
2
6
2
3
1
5
2
3
2
6
2
4
1
5
2
4
2
6
σR.a=S.a(R × S)
R.a
1
2
2
b
2
3
4
S.a
1
2
2
c
5
6
6
ジョイン記号の代用
Database System Implementation
wv
正しいジョイン記号
Windings 3 の wv で代用
Theta Join
Database System Implementation
一般的なジョイン
Theta-Join R wvC S = σC(R × S)
関係 R × S の属性にたいする条件 C をつくる
研究当初は x θ y （ただし θ = >, <, …) の条件だけを
扱ったので Theta- (θ) とよばれる
Theta Join の例
Database System Implementation
R
a
1
2
2
b
2
3
4
a
1
2
c
5
6
σb+c>8(R × S)
R.a
2
2
2
R×S
S
b
3
4
4
S.a
2
1
2
c
6
5
6
R.a
1
1
2
2
2
2
b
2
2
3
3
4
4
S.a
1
2
1
2
1
2
c
5
6
5
6
5
6
dangling レコードとジョイン
Database System Implementation
R
a
1
2
2
S
b
2
3
4
a
3
2
R wv S
c
5
6
a
2
2
b
3
4
c
6
6
R の (1,2) は S の中で属性 a が一致するレコードがない。
dangling レコードと呼ぶ。他の例 (3,5) ∈ S。
R から dangling レコードを除く操作
R wv S に dangling レコードを残す操作
セミジョイン
アウタージョイン
dangling レコードの例
Database System Implementation
遺伝子観測量のデータ
微量に出現しているため観測がむずかしい遺伝子が多い
R
S
遺伝子ID 肝臓
1
0.5
3
0.2
4
0.3
遺伝子ID
肺
2
3
5
0.6
0.2
0.4
R wv S
遺伝子
ID
3
肝臓
0.2
肺
0.2
セミジョイン（semi-join）
Database System Implementation
R wv S で分かる R の dangling レコードを除く操作
R n S ＝ πL (R wv S)
L は R の属性のリスト（n はフォント msbm5 の n）
R
a
1
2
2
S
b
2
3
4
a
3
2
R wv S
c
5
6
a
2
2
b
3
4
RnS
c
6
6
a
2
2
b
3
4
アウタージョイン（outer-join）
Database System Implementation
R wv S に dangling レコードを追加した関係
R wvouter S
dangling レコードに null 記号（⊥）を補うことで情報の欠落をふせぐ
R
a
1
2
2
S
b
2
3
4
a
3
2
R wv S
c
5
6
a
2
2
b
3
4
c
6
6
R wvouter S
a
2
2
1
3
b
3
4
2
⊥
c
6
6
⊥
5
アウタージョインの例
Database System Implementation
R
S
遺伝子ID 肝臓
1
0.5
3
0.2
4
0.3
遺伝子ID
2
3
5
R wvouter S
遺伝子ID
1
肝臓
0.5
肺
⊥
2
3
⊥
0.2
0.6
0.2
4
0.3
⊥
5
⊥
0.4
肺
0.6
0.2
0.4
アウタージョイン記号は…
Database System Implementation
wv
正しい
アウタージョイン記号
代用品
outer
グループ分け（Grouping）と集約(Aggregation)
Database System Implementation
３件以上お店のある地域で、一番安いラーメンの価格は？
name
district
price
1
Tokyo
650
2
Tokyo
550
3
Tokyo
750
4
Tokyo
850
5
Yokohama
850
6
Yokohama
550
7
Yokohama
600
8
Chiba
600
9
Chiba
450
SQL文
SELECT district, MIN(price) AS min
FROM R
GROUP BY district
HAVING COUNT(name) > 2
グループ分けと集約
Database System Implementation
３件以上お店のある地域で、一番安いラーメンの価格は？
name
district
price
1
Tokyo
650
2
Tokyo
550
3
Tokyo
750
4
Tokyo
850
5
Yokohama
850
6
Yokohama
550
7
Yokohama
600
8
Chiba
600
9
Chiba
450
R1=
γdistrict,MIN(price)→min,COUNT(name)→count R
district
min
count
Tokyo
550
4
Yokohama
550
3
Chiba
450
2
πdistrict, min(σcount>2 R1)
district
min
Tokyo
550
Yokohama
550
グループ分けと集約
Database System Implementation
γL R = γdistrict,MIN(price)→min,COUNT(name)→count R
L の元は
• グループ分けの対象となる属性（複数可）
district と soup （スープの種類）でグループ分けなど
• 属性を引数とする集約演算子
MIN(price), MAX(price), AVG(price),
SUM(price), count(name) など
問合せの代数：ソート
Database System Implementation
τa1,a2,a3,…,anR
R の元を属性 a1 の値でソートする。
a1 で同一のレコードは a2 でソートし、an まで使って
辞書式順序でソート。
ソートは問合せの実行スピードを上げるのに利用
τa,b,cR
a
2
b
1
c
3
a
2
b
0
c
5
3
2
1
1
2
4
2
2
1
1
3
4
2
0
5
3
1
2
問合せ木（Expression Tree）
Database System Implementation
πdistrict, min(σcount>2 (γdistrict,MIN(price)→min,COUNT(name)→count R))
πdistrict, min
σcount>2
γdistrict,MIN(price)→min,COUNT(name)→count
R
問合せ木
Database System Implementation
R
a
1
2
2
S
b
2
3
4
a
1
2
σa>1 AND c>5 R wv S
c
5
6
a
2
2
b
3
4
c
6
6
問合せ木
Database System Implementation
a
b
c
2
3
6
2
4
6
a
b
c
1
2
5
2
3
6
2
4
6
σa>1 AND c>5
πR.a→a,b,c
R.a
b
S.a
c
1
2
1
5
1
2
2
6
2
3
1
5
R.a
b
S.a
c
2
3
2
6
1
2
1
5
2
4
1
5
2
3
2
6
2
4
2
6
2
4
2
6
σR.a=S.a
×
R
S
問合せ木の改良
Database System Implementation
a
b
c
2
3
6
2
4
6
πR.a→a,b,c
R.a
b
S.a
c
2
3
2
6
2
4
2
6
R.a
b
S.a
c
2
3
2
6
2
4
2
6
a
b
2
3
2
4
σR.a=S.a
×
a
c
2
6
σa>1 R
σc>5 S
選択を最初に実行
Database System Implementation
問合せの代数の実装
講義順序
Database System Implementation
まず基本演算の実装
∪ ∩ － δ σ
π
wv
γ
つづいて演算を複数組み合わせた問合せの実装
σa>1 AND c>5 R wv S
R(a,b,c) wv R(b,c,d) wv R(b,d,e) wv R(c,d,f)
R(a,b) wv R(b,c) wv R(c,d) wv R(d,a)
πa,e,f(R(a,b,c) wv R(b,c,d) wv R(b,d,e) wv R(c,d,f))
ディスクブロックバッファデータ転送ボトルネック
Database System Implementation
入力バッファ
主記憶
ディスク
例
4kB 平均 15msec
266kB/sec
データ転送量は
３桁以上の差
：
例
RDRAM 1.6GB/sec
IBM Regatta 12.8GB/sec
ブロック 4kB～
CPU
出力バッファ
実装の方針
Database System Implementation
データベース(DB)読み込み回数をへらしたい
• 1回だけDBを走査すればよい容易な場合あり
• 1回目で前処理
データベースをソート
ハッシュ表を生成
インデックスを生成
２回目の読み込みで結果を書き出す
DBは1回だけ走査
選択σ 射影π
Database System Implementation
a
b
c
1
2
3
2
1
2
3
2
5
5
0
3
すべてのブロックを
1回だけ読み込む
πa+b→x, a+c→yR(a,b,c)
CPU
x
y
3
4
3
4
5
8
5
8
：
DBは1回だけ走査
選択σ 射影π
Database System Implementation
：
関係 R は B 個のブロックに
整理して分割
B 個のブロック転送で済む
B=1000 ブロック
1ブロック=4kB 平均 15msec 15秒
DBは1回だけ走査
選択σ 射影π
Database System Implementation
関係 R の T 個のレコードが
バラバラのブロックに点在
最悪 T 個のブロック転送
T=100,000レコード 100,000ブロック
1ブロック=4kB 平均 15msec 1500秒
DBは1回だけ走査
重複削除 δ
Database System Implementation
十分な主記憶があり
既に読んだレコードか
否かの判定を高速に
実行できる場合
a
1
2
2
b
2
3
3
ハッシュ表や
平衡２分木で
管理できる
CPU
すべての
ブロックを
1回だけ
読み込む
a
1
2
b
2
3
：
DBは1回だけ走査
集約δ
Database System Implementation
主記憶に下の
中間計算結果
が入る場合
district
min
count
Tokyo
550
4
Yokohama
550
3
Chiba
450
2
CPU
すべての
ブロックを
1回だけ
読み込む
：
name
district
price
6
Yokohama
550
1
Tokyo
650
9
Chiba
450
3
Tokyo
750
5
Yokohama
850
4
Tokyo
850
district
min
7
Yokohama
600
Tokyo
550
8
Chiba
600
Yokohama
550
2
Tokyo
550
πdistrict, min(σcount>2 (γdistrict,MIN(price)→min,COUNT(name)→count R))
DBは1回だけ走査
和交わり差
Database System Implementation
すべての
ブロックを
1回だけ
読み込む
R ∪ S はブロックを
コピーすればよい
R
R ∩ S、 R － S は？
S
Rのレコードの頻度表
が入る場合
レコード R での
頻度
S での
頻度
0
1
0
1
3
1
3
2
3
R={0,1,1,1,3,3}
S={1,2,2,3,3,3}
CPU
R∩S=
{1,3,3}
DBは1回だけ走査
積
Database System Implementation
R もしくは S が
主記憶に入る場合
すべての
ブロックを
1回だけ
読み込む
R が入る場合、まず
R を主記憶に格納
S
R={0,1,1,1,3,3}
S={1,2,2,3,3,3}
R={0,1,1,1,3,3}
Sの各レコードに対し
Rの各レコードを連結
すればよい
R
CPU
0
1
0
2
0
2
0
3
0
3
0
3
DBは1回だけ走査
Natural Join
Database System Implementation
R か S をすべて
主記憶に格納でき、
属性 a の値をもつ
レコードを高速に
検索できる場合
ハッシュ表や平衡２分木
Sの
ハッシュ表
a
c
1
5
2
6
R
S
a
b
1
2
2
3
2
4
a
c
1
5
2
6
R wv S
R の各レコードを読み、
ハッシュ表を参照
CPU
a
b
c
1
2
5
2
3
6
2
4
6
Nested-Loop Join
Database System Implementation
R、S どちらも主記憶に
格納できない場合
R(a,b)
for s ∈ S do
for r ∈ R do
r と s が属性 a で一致
するならば、r と s を
融合したレコードを出力
RとSのブロック数 B(R),B(S)
B(R)×B(S)個のブロックが
読み出される
S(a,c)
CPU
R wv S
ブロックを考慮した Nested-Loop Join の工夫
Database System Implementation
外のループ
S はブロック単位に
主記憶にできるだけ、
例えば M-1 ブロック読む。
属性 a で高速検索。
内のループ
R もブロック単位に読み、
属性 a が一致する S の
レコードを高速検索
R(a,b)
S(a,c)
ブロック数 B(R),B(S)
ブロック読み出し総回数
B(S)/(M-1) × (M-1 +B(R))
= B(S)+B(S)B(R)/M-1 ≒ B(R)B(S)/M
Database System Implementation
問合せの代数の実装
ＤＢを２回走査することで
より大きな DB を処理できる方法
ソートをつかう場合
DB を２回走査する方法ソート
Database System Implementation
主記憶に入らないDB のソート
Two-Phase Multiway Merge Sort
•ブロックを M 個
読込む
•主記憶内でソート
ブロックを読込む
時間内に通常は
ソートできる
•ソートされた M 個の
ブロックグループが
複数できる
ソート
CPU
ブロックを
M個
読込む
：
：
Two-Phase Multiway Merge Sort
Database System Implementation
未処理のレコードへのポインタ
2 5 6
1 2 4
1 1 3
未処理の
レコードで
最小値を
選択・出力
：
3 4 4
CPU
ソートされた
グループから
各々1ブロック
主記憶に読む
：
1 1 1
2 2 3
3 4 4
4 5 6
Two-Phase Multiway Merge Sort のデータ量の限界
Database System Implementation
M個
総ブロック数 B
2 5 6
1 2 4
未処理の
レコードで
最小値を
選択・出力
1 1 3
：
B/M 個
：
3 4 4
主記憶にブロックを M 個保持できる場合、B/M ≦ M
B ≦ M2 のデータまでソートできる。入出力は 4B ブロック。
例 4kBのブロックを, 15msec で転送できる場合の合計時間
M = 103, B = 106 主記憶4MBで 4GB を 60,000秒
M = 104, B = 108 主記憶40MBで 400GB を 6,000,000秒 (約70日)
ソートをつかい DB を２回走査して重複除去
Database System Implementation
M 個のブロック毎にソートしておく
2 5 6
1 2 4
未処理の
レコードで
最小値を
重複を除き
出力
：
1 1 3
：
3 4 4
CPU
1 2 3
4 5 6
ソートを使ったグループ分けと集約
Database System Implementation
M 個のブロック毎にグループの対象属性でソートしておく
ソート
CPU
name
district
price
6
Yokohama
550
1
Tokyo
650
9
Chiba
450
3
Tokyo
750
5
Yokohama
850
4
Tokyo
850
7
Yokohama
600
8
Chiba
600
2
Tokyo
550
：
Chiba Tokyo
：
Yoko
hama
ソートを使ったグループ分けと集約
Database System Implementation
district
min
count
Chiba
450
2
Tokyo
550
4
Yokohama
550
3
CPU
同一グルー
プ属性値をも
つデータが順
番に入力
Chiba Tokyo
Yoko
hama
：
：
district
min
Tokyo
550
Yokohama
550
ソートを使ったジョインの実装
Database System Implementation
R(a,b) wv S(a,c)
まず R(a,b) および S(a,c) を属性 a で一気にソートしてしまう
4B(R)+4B(S) 個のブロック転送
２つのソートされ
たリストを merge
属性 a の値が一
致するレコードは
主記憶内に収ま
ると仮定
1
5
1
6
2
7
2
8
1
4
2
5
3
4
3
5
R(a,b)
ソ
ー
ト
済
み
S(a,c)
各々、複数ブロック読込む
B(R)+B(S) 個ブロック転送
ソートを使ったジョインの実装
Database System Implementation
効き目がない最悪のデータ
属性 a の値がすべて同じ
Nested-Loop Join で対応
R(a,b)
S(a,c)
1
1
1
1
1
1
1
1
1
1
1
1
1
2
3
4
5
6
1
2
3
4
5
6
ソートを使ったジョインの実装（改良版）
Database System Implementation
M 個のブロック毎に属性 a でソート (全体をソートしない)
2B(R)+2B(S) 個のブロック転送で済ましておく
2 2 3
R(a,b)
1 2 2
1 1 2
属性 a の値が
最小のレコード
間でジョインを
実行して出力
B(R)+B(S)個
のブロック転送
S(a,c)
：
3 4 5
R(a,b) wv S(a,c)
やはり属性 a の値が一致するレコードは
主記憶内に収まると仮定
ソートを使ったその他の実装
Database System Implementation
∪、∩、－もジョインと同様に実装可能
Database System Implementation
問合せの代数の実装
ＤＢを２回走査することで
より大きな DB を処理できる方法
ハッシュ関数をつかう場合
問合せの並列化
ハッシュ関数をつかって関係を分割
Database System Implementation
各ブロックを読込む
ハッシュ表
各レコードをハッシュ表で
M-1個のバケットに分配
：
バケットは複数のブロック
M-1個
一杯になったブロックは
ディスクへ書き出し、
新しい空のブロックを用意
ほぼ同じサイズの
バケットに分割
できると仮定
M個
CPU
同じバケット毎に整理して
ディスク上に配置
：
M-1個のバケット
ハッシュをつかった重複除去
Database System Implementation
同じ値をもつレコードは必ず
同じバケットにあると仮定
（むろん同じ値をもつレコードがバケット
に入らないほどあれば、この仮定は崩
れる。ソートをつかった方法を利用すべ
き）
バケット毎に独立して
重複除去を実行できる
DBを一回だけ走査する
重複除去を各バケットに
対して実行
R1 R2 R3 R4 R5
M個
：
δ(R1)∪δ(R2)∪
δ(R3)∪δ(R4)∪
δ(R5)
DBは1回だけ走査する重複削除を各バケットに適用
Database System Implementation
R1
十分な主記憶があり
既に読んだレコードか
否かの判定を高速に
実行できる場合
a
1
2
2
b
2
3
3
ハッシュ表や
平衡２分木で
管理できる
CPU
すべての
ブロックを
1回だけ
読み込む
a
1
2
b
2
3
ハッシュをつかったグループ分けと集約
Database System Implementation
γL(R)
グループ分けの対象となる属性 L の値をつかい
ハッシュ関数で分割しておく
R1 R2 R3 R4 R5
L が同じ値をもつレコードは
必ず同じバケットと仮定
M個
：
バケット毎に独立してグループ分け
と集約を実行できる
DBを一回だけ走査するグループ分
けを各バケットに対して実行
district
min
Tokyo
550
Yokohama
550
ハッシュ・ジョイン
Database System Implementation
R(a,b) wv S(a,c)
まず R(a,b) および S(a,c) を属性 a の値によりハッシュで分割
2B(R)+2B(S) 個のブロック転送
属性 a が同じ値をもつレコードは
必ず同じバケットと仮定
R1 R2 R3 R4 R5
R(a,b)
バケット毎に独立してジョインを実行
DBを一回だけ走査するジョインを
Ri と Si の組に対して実行し和をとる
S(a,c)
S1 S2 S3 S4 S5
R1(a,b) wv S1(a,c) ∪
R2(a,b) wv S2(a,c) ∪
:
R5(a,b) wv S5(a,c)
Shared-Nothing 型並列計算機でのハッシュ・ジョイン
Database System Implementation
ＤＢ問合せは、Shared-Nothing 型並列計算機での実行になじむため
Shared-Nothing 型はデータベース用計算機として標準的
Processor
Memory
Disk
Processor
Memory
Disk
Processor
Memory
Disk
Shared-Nothing 型並列計算機でのハッシュ・ジョイン
Database System Implementation
R1 R2 R3 R4 R5
R(a,b)
S(a,c)
S1 S2 S3 S4 S5
Processor
Processor
各プロセッサに均等に
分配し個別にジョインする
Memory
Processor
Memory
Memory
R1
R4
R2
R5
R3
S1
S4
S2
S5
S3
Shared-Nothing 型並列計算機でのハッシュ・ジョイン
Database System Implementation
p 個のディスクへ分配し、入出力を並列化することで性能を向上
均等に分配された後は、各プロセッサは1回の入力で
(B(R)+B(S))/p ブロックだけ転送すればよい
例
B(R)=1000, B(S)=500, プロセッサ数=10
各プロセッサに 150ブロック
Processor
Processor 150*9=1350ブロック転送
Processor
ハッシュ後、9プロセッサに
その後はプロセッサ毎に 150ブロックを入力
Memory
Memory
Memory
R1
R4
R2
R5
R3
S1
S4
S2
S5
S3
Database System Implementation
問合せの代数の実装
インデックスが利用できる場合
インデックス
Database System Implementation
インデックス：属性 a の値が v となるレコードが
どのブロックにあるか、おおよその位置を保持した表
例えば、識別子(ID) の順番にレコードをディスク上に格納
インデックスは各 ID が格納されたブロックのおおよその位置を保持
インデックス
10
10
10
20
90
30
30
170
50
40
250
70
50
60
90
110
130
150
70
80
90
100
ブ
ロ
ッ
ク
その他のインデックス
Database System Implementation
•
•
•
２次的インデックス
複数の属性にインデックス（例名前と電話番号）
B-木 (B-trees)
ハッシュ表
技術的工夫
1. 更新への対応
2. 大量のデータにもアクセス速度を劣化させない
詳しくは参考教科書の４章を参照
H. Garcia-Morina, J. D. Ullman, and J. Widom. Database System Implementation.
Prentice Hall, 2000, ISBN 0-13-040264-8
インデックスを利用した問合せの高速化
Database System Implementation
σa=v(R)
属性 a にインデッスクがある場合
⇒ インデックスをつかった高速なアクセス
R(a,b) wv S(a,c)
S(a,c) の属性 a にインデッスクがある場合
⇒ R(a,b) の各レコード毎に
インデックスをつかった問合せを実行
Database System Implementation
問合せの代数の実装
ＤＢを２回より多く走査することで
より大きな DB を処理できる方法
２回より多く DB を走査する Multiway Merge Sort
Database System Implementation
M ブロック
ソート
CPU
２回より多く DB を走査する Multiway Merge Sort
Database System Implementation
ソート
未処理の
レコードで
最小値を
選択・出力
CPU
縦が
M ブロック
２回より多く DB を走査する Multiway Merge Sort
Database System Implementation
ソート
未処理の
レコードで
最小値を
選択・出力
CPU
２回より多く DB を走査する Multiway Merge Sort
Database System Implementation
B 個のブロックからなる関係 R をソート
主記憶中に M ブロック格納する領域を確保できると仮定
ステップ1
• B ≦ M のとき、関係 R をソート
ステップ2
• B > M のとき、関係R を M 個 R1, R2, ..., RM に分割
• 各 Ri を、ステップ1と2によりソート
• 最後にR1, R2, ..., RM を merge sort
ステップ1と2を n 回実行すれば最大 Mn ブロックのデータまでソート可
M が B1/n 個以上で、 B 個のブロックに入ったデータをソート可
入出力されるブロックの総数は 2nB 個
Database System Implementation
問合せ速度を改善する
ための代数的操作
交換律と結合律
Database System Implementation
R×S=S×R
(R × S) × T = R × (S × T)
Natural Join
R wv S = S wv R
(R wv S) wv T = R wv (S wv T)
R∪S=S∪R
(R ∪ S) ∪ T = R ∪ (S ∪ T)
R∩S=S∩R
(R ∩ S) ∩ T = R ∩ (S ∩ T)
∪ と ∩ に関する交換律と結合律は、 bags 意味論と集合意味論
のどちらでも成立
代数的操作がうまくゆかない例
Database System Implementation
集合意味論では成り立つ分配律が bags 意味論だと不成立
• R=S=T={a}
• R ∩ (S ∪ T) = {a} ∩ {a,a} = {a}
(R ∩ S) ∪ (R ∩ T) = {a} ∪ {a} = {a,a}
Theta-Join では結合律が必ずしも成り立たない
R(a,b), S(b,c), T(c,d)
(R wvR.b > S.b S) wva < d T
R wvR.b > S.b (S wva < d T)
a は S と T の属性でない
選択を先行実行して効果がある例
Database System Implementation
R
a
b
c
2
3
6
2
4
6
σa>1 AND c>5 R wv S
πR.a→a,b,c
R.a
b
S.a
c
2
3
2
6
2
4
2
6
R.a
b
S.a
c
2
3
2
6
2
4
2
6
σR.a=S.a
×
S
a
b
1
2
a
b
a
c
a c
2
3
2
3
2
6
1 5
2
4
2
4
2 6
σa>1 R
σc>5 S
選択を先行実行するための操作
AND, OR
Database System Implementation
σC1 AND C2(R) = σC1(σC2(R)) = σC2(σC1(R))
C1 と C2 どちらを先に実行してもよい
R が重複したレコードのない集合である場合
σC1 OR C2(R) = σC1(R) ∪set σC2(R)
ただし ∪set は集合和
R が重複したレコードが存在する場合
σC1 OR C2(R) = σC1(R) ∪ σC2(R)
は必ずしも成り立たない
∪ は bag 意味論であることに注意
選択を先行実行するための操作
AND, OR
Database System Implementation
σC1 OR C2(R) = (σC1(R)) ∪ (σC2(R)) ??
反例
R(a,b) = {(1,2)}
σa>0 OR b>1(R) = {(1,2)}
(σa>0(R)) ∪ (σb>1(R))={(1,2)} ∪ {(1,2)} ＝
{(1,2),(1,2)}
(1,2) が a>0 と b>1 を同時に満たすため
成り立つ場合
σa>0 OR a<0(R) = {(1,2)}
２つの条件 a>0 と a<0 が同時に成り立たない場合
(σ
(R)) ∪ (σ
(R)) = {(1,2)} ∪ {} ＝{(1,2)}
選択を先行実行するための操作
∪、－、×、wv、∩
Database System Implementation
σC(R ∪ S) = σC(R) ∪ σC(S)
σC(R ー S) = σC(R) ー σC(S) = σC(R) ー S
以下、条件 C に現れる属性は、すべて R の属性と仮定
σC(R × S) = σC(R) × S
積 × の場合、R と S は共通の属性を含まない
σC(R wv S) = σC(R) wv S
C が R と S に共通する属性を含む場合でも成立
σC(R ∩ S) = σC(R) ∩ S
選択を先行実行するための操作
∪、－、×、wv、∩
Database System Implementation
例
選択の先行実行
σ(a=1 OR a=3) AND b<c(R(a,b) wv S(b,c))
σC(R wv S) = σC(R) wv S は使えない
条件が R(a,b) の属性以外に属性 c にも作用するから
＝ σa=1 OR a=3 ( σb<c(R(a,b) wv S(b,c)) )
b<c を push
＝ σa=1 OR a=3 (R(a,b) wv
σb<c S(b,c) )
b<c をさらに push
＝ (σa=1 OR a=3 R(a,b)) wv (σb<c S(b,c))
a=1 OR a=3 は R(a,b) のみに作用
射影の先行実行
Database System Implementation
• 選択の先行実行
計算途中で生成されるレコードの数を減らす効果
• 射影の先行実行は、効果的か？
表の幅を狭くするが、レコードの数を減らさない
（bags 意味論の場合）
選択の先行実行ほどの効果はない
• 集合意味論の場合
射影すると重複レコードを除ける場合がある
射影を先行実行するための操作
Database System Implementation
ジョイン等を実行するのに必要な属性と被射影属性を残す
•πL(R wv S) = πL(πMR wv πNS)
M = S もしくは L に現れる R の属性全体
N = R もしくは L に現れる S の属性全体
πa+e→x,b→y(R(a,b,c,d) wv S(c,e,f))
= πa+e→x,b→y(πa,b,cR(a,b,c,d) wv πc,eS(c,e,f))
• πL(R wvC S) = πL(πMR wvC πNS)
M = C もしくは L に現れる R の属性全体
N = C もしくは L に現れる S の属性全体
• πL(R × S) = πL(πMR × πNS)
M = L に現れる R の属性全体
N = L に現れる S の属性全体
射影を先行実行するための操作
Database System Implementation
• πL(R  S) = πL(R)  πL(S)
• πL(R ∩ S) = πL(R)  πL(S) は必ずしも成り立たない
（∩ は bags 意味論）
R(a,b) = {(1,2)}
S(a,b) = {(1,3)}
πa(R(a,b) ∩ S(a,b)) = πa({}) = {}
πaR(a,b) ∩ πaS(a,b) = {(1)} ∩ {(1)} = {(1)}
• πL(σC(R)) = πL(σC(πM(R)))
M は L もしくは C に現れる R の属性
重複除去を先行実行するための操作
Database System Implementation
重複除去によりレコード数が減ることを期待して
重複除去を先行して実行する
δ(R × S)
= δ(R) × δ(S)
δ(R wv S) = δ(R) wv δ(S)
δ(R wvC S)= δ(R) wvC δ(S)
δ(σC(R))
= σC(δ(R))
δ(R ∩ S)
= δ(R) ∩ δ(S)
重複除去を先行実行するための操作
Database System Implementation
成立しない性質
δ(R ∪ S)
= δ(R) ∪ δ(S)
δ(R ー S)
= δ(R) ー δ(S)
反例
R(a)={1,1}, S(a)={1}
δ( πa(R(a,b)) ) = πa( δ(R(a,b)) )
反例
R(a,b) = {(1,2), (1,3)}
尚、集合意味論ではこれらの性質は成立
なぜならレコードの重複を許さない意味論だから
Database System Implementation
SQL 文の構文解析木から
効率的な問合せを合成
簡略化した SQL
Database System Implementation
<Query> ::= <SFW>
<Query> ::= ( <Query> )
<SFW> ::= SELECT <SelList>
FROM <FromList>
WHERE <Condition>
<SelList> ::= <Attribute>, <SelList>
<SelList> ::= <Attribute>
<FromList> ::= <Relation>, <FromList>
<FromList> ::= <Relation>
<Condition> ::=
<Condition> AND <Condition>
<Condition> ::=
<Tuple> IN <Query>
<Condition> ::=
<Attribute> = <Attribute>
<Condition> ::=
<Attribute> LIKE <Pattern>
<Tuple> ::= <Attribute>
StarsIn(title, year, starName)
MovieStar(name, address,
gender, birthdate)
SELECT title
FROM StarsIn
WHERE starName IN (
SELECT name
FROM MovieStar
WHERE birthdate LIKE ‘%1960’
);
SELECT title
FROM StarsIn, MovieStar
WHERE starName = name AND
birthdate LIKE ‘%1960’
SQL文から問合せ木の生成
Database System Implementation
StarsIn(title, year, starName)
MovieStar(name, address,
gender, birthdate)
SELECT title
FROM StarsIn, MovieStar
WHERE starName = name AND
birthdate LIKE ‘%1960’
πtitle
SQL文の問合せ木への変換
（木の下から順番に）
σstarName = name AND
<FromList> の関係の積
birthdate LIKE ‘%1960’
<Condition> を C として
選択 σC を適用
×
StarsIn
MovieStar
<SelList> の属性リスト L で
射影 πL を適用
問合せ木
Database System Implementation
StarsIn(title, year, starName)
MovieStar(name, address,
gender, birthdate)
πtitle
SELECT title
FROM StarsIn
WHERE starName IN (
SELECT name
FROM MovieStar
WHERE birthdate LIKE ‘%1960’
);
σ
StarsIn
<Condition>
<Tuple>
IN
πname
<Attribute>
σbirthdate LIKE ‘%1960’
StarName
MovieStar
部分的問合せを
そのままの構造で表示
問合せ木の変換
Database System Implementation
StarsIn
πtitle
πtitle
σ
σStarName=name
<Condition>
<Tuple>
IN
Πname
×
StarsIn
δ
<Attribute>
σbirthdate LIKE ‘%1960’
πname
StarName
MovieStar
σbirthdate LIKE ‘%1960’
註： ‘<Tuple> IN 関係 R’ で抽出されるレコードは重複しない。 MovieStar
結果を一致させるため、右の問合せ木で πname の後に
重複削除する δ をほどこす。
問合せ木
Database System Implementation
StarsIn(title, year, starName)
MovieStar(name, address,
gender, birthdate)
δ
Πm1.title, m1.year
σ
StarsIn m1
<Condition>
m1.year - 40
<=
SELECT DISTINCT m1.title, m1.year
FROM StarsIn m1
WHERE m1.year - 40 <= (
SELECT AVG(birthdate)
FROM StarsIn m2, MovieStar s
WHERE
m2.starName = s.name AND
m1.title = m2.title AND
m1.year = m2.year
);
γAvg(s.birthdate)
出演した俳優の平均年齢が
４０歳以下の映画の
タイトルと製作年を求めよ
σm1.title = m2.title AND m1.year = m2.year
wv
m2.starName = s.name
StarsIn m2
MovieStar s
問合せ木の変換
Database System Implementation
StarsIn(title, year, starName)
MovieStar(name, address,
gender, birthdate)
δ
δ
πm1.title, m1.year
πm1.title, m1.year
σm1.year-40<=x
実行を遅延
σ
wv
m1.title = m2.title AND m1.year = m2.year
StarsIn m1 <Condition>
StarsIn m1
<=
m1.year-40
γAvg(s.birthdate)
γm２.title, m2.year, Avg(s.birthdate)→x
σm1.title = m2.title AND m1.year = m2.year
m1のレコード
がないと計算が
進まない
wv
m2.starName = s.name
StarsIn m2
MovieStar s
wv
m2.starName = s.name
StarsIn m2
MovieStar s
問合せ木の変換
Database System Implementation
StarsIn(title, year, starName)
MovieStar(name, address,
gender, birthdate)
δ
πm1.title, m1.year
σm1.year-40<=x
δ
m1とm2は
本質的に同じ
wv
m1.title = m2.title AND m1.year = m2.year
πm2.title, m2.year
σm2.year-40<=x
StarsIn m1
γm２.title, m2.year, Avg(s.birthdate)→x
γm２.title, m2.year, Avg(s.birthdate)→x
wv
m2.starName = s.name
wv
m2.starName = s.name
StarsIn m2
MovieStar s
StarsIn m2
MovieStar s
Database System Implementation
問合せコストの近似
問合せコストは中間計算結果の大きさに依存
Database System Implementation
問合せの実行中に生成される中間計算結果
• ブロック転送回数を低減するためにも
ブロックにまとめて保存
• 中間計算結果の大きさ
（レコード数 × レコード長）を近似したい
• したがってレコード数を近似することが重要
中間計算結果のレコード数を近似
Database System Implementation
近似の方法
• 論理的に矛盾がないこと
たとえば (RwvT)wvS と Rwv(TwvS) の
は同じであるべき
• 簡単に計算ができること
近似が実際に計算するのと同程度に重たいと無意味
• 計算が容易なパラメータ（近似は粗くても妥協する）
T(R): 関係 R のレコード数
V(R,a): 属性 a における、異なる値の数
近似値
選択結果のレコード数を近似
Database System Implementation
S=σa=1(R)
a の値が異なるレコード数が同数ならば
（むろん現実には偏りがあるが）
T(S) = T(R) / V(R,a)
T(S), T(R) は S と R のレコード数
S=σa≠1(R) の場合
T(S) = T(R) (V(R,a)-1)/ V(R,a)
選択結果のレコード数を近似
Database System Implementation
S=σC1 OR C2(R)
C1 をみたすレコードの割合 m1/T(R)
C1 をみたさないレコードの割合 1 - m1/T(R)
T(S) = T(R)×(1 - (1 - m1/T(R))×(1 - m2/T(R)))
C1もC2もみたさないレコードの割合
ジョイン結果のレコード数を近似するためのヒューリスティクス
Database System Implementation
R(a,b)
T(R)=1000
V(R,b)=20
S(b,c)
T(S)=2000
V(S,b)=50
仮定１（属性値の包含）
属性 b の異なる値の数は、R が 20 個、S が 50 個
一般に V(R,b) ≦ V(S,b) ならば
R の属性 b の値は、すべて S にも現れると仮定
仮定２（属性値の均等分布）
R のレコードは S のレコードと 1/V(S,b) の確率でジョインする
R(a,b) wv S(b,c) のレコード数:
T(R) × （1 / V(S,b)） × T(S) = T(R)T(S) / V(S,b)
属性値の包含性
一般に
T(R)T(S) / max{V(R,b), V(S,b)}
ジョイン結果のレコード数を近似
Database System Implementation
R(a,b)
T(R)=1,000
V(R,b)=20
S(b,c)
T(S)=2,000
V(S,b)=50
V(S,c)=100
U(c,d)
T(U)=5,000
V(U,c)=500
R(a,b) wv S(b,c)
T(R)T(S) / max{V(R,b),V(S,b)} = 40,000
(R(a,b) wv S(b,c)) wv U(c,d)
T(RwvS)T(U) / max{V(RwvS,c),V(U,c)}
仮定 3 （属性値の保存）
RwvS で属性 c の値はジョイン後もすべて残ると仮定
つまり V(RwvS,c) = V(S,c)
＝ 40,000×5,000 / max{100,500} = 400,000
近似値がジョイン順序に依存しないこと
Database System Implementation
R(a,b)
T(R)=1,000
V(R,b)=20
S(b,c)
T(S)=2,000
V(S,b)=50
V(S,c)=100
U(c,d)
T(U)=5,000
V(U,c)=500
S(b,c) wv U(c,d)
T(S)T(U) / max{V(S,c),V(U,c)} = 20,000
R(a,b) wv (S(b,c) wv U(c,d))
T(R)T(SwvU) / max{V(R,b),V(SwvU,b)}
属性値は保存されると仮定 V(SwvU,b)=V(S,b)
＝ 1,000×20,000 / max{20,50} = 400,000
複数属性上の Natural Join のレコード数を近似
Database System Implementation
R(a,b1,b2)
wv
S(b1,b2,c) のレコード数
T(R)T(S)
max{V(R,b1), V(S,b1)} max{V(R,b2), V(S,b2)}
R の属性 b1 の値が、S のレコードに現れる確率:
属性値の包含と、均等分布を仮定すると
• V(R,b1) ≧ V(S,b1) の場合
(V(S,b1) / V(R,b1)) × (1 / V(S,b1)) = 1 / V(R,b1)
• V(R,b1) < V(S,b1) の場合: 1 / V(S,b1)
• つまり 1 / max{V(R,b1), V(S,b1)}
b2 の場合も同様に、確率は
1 / max{V(R,b2), V(S,b2)}
最後に b1 と b2 の値は独立に分布すると仮定
複数属性上の Natural Join のレコード数を近似
Database System Implementation
例
R(a,b1,b2)
T(R)=1000
V(R,b1)=20
V(R,b2)=100
R(a,b1,b2)
wv
S(b1,b2,c)
T(S)=2000
V(S,b1)=50
V(S,b2)=50
S(b1,b2,c) のレコード数
T(R)T(S)
max{V(R,b1), V(S,b1)} max{V(R,b2), V(S,b2)}
= 1000×2000 / 50×100
= 400
近似値がジョイン順序に依存しないこと
Database System Implementation
R(a,b)
T(R)=1,000
V(R,b)=20
R(a,b)
wv
(R(a,b)
S(b,c)
T(S)=2,000
V(S,b)=50
V(S,c)=100
U(c,d)
T(U)=5,000
V(U,c)=500
U(c,d) T(R)T(U) = 5,000,000
wv
U(c,d))
wv
S(b,c)
T(RwvU) T(S)
max{V(RwvU,b),V(S,b)} max{V(RwvU,c),V(S,c)}
V(RwvU,b)=V(R,b), V(RwvU,c)=V(U,c) 属性値の保存より
= (5,000,000×2,000) / (max{20,50} max{500,100})
= 400,000
n個の関係をジョインした結果のレコード数を近似
Database System Implementation
S = R1 wv R2 wv R3 wv ... wv Rn
属性 a が k 個の関係 R1, R2, R3, ..., Rk に現れ、しかも
V(R1,a) ≦ V(R2,a) ≦ V(R3,a) ≦ ... ≦ V(Rk,a)
であると、ジョインの交換律より、一般性を失わず仮定
R1, R2, R3, ..., Rk から各々レコードを選択したとき、
属性 a の値が一致する確率 P(a) は
1
V(R2,a) V(R3,a) ... V(Rk,a)
ただし属性値の包含と、均等分布を仮定
S の大きさは
T(R1)T(R2)... T(Rn) × Π{P(aj) | aj は複数回出現する属性}
この近似値はジョインの順序に依存しない
n個のジョイン結果のレコード数を近似
Database System Implementation
R(a,b,c)
T(R)=1000
V(R,a)=100
V(R,b)=20
V(R,c)=200
S(b,c,d)
T(S)=2000
U(b,e)
T(U)=5000
V(S,b)=50
V(S,c)=100
V(S,d)=400
V(U,b)=200
V(U,e)=500
1
1
1000×2000×5000×
×
200
50×200
=5000
属性b
属性c
問合せコスト近似用のパラメータ
Database System Implementation
• 計算が容易なパラメータ
T(R): 関係 R のレコード数
V(R,a): 属性 a における、異なる値の数
• V(R,a)の数が少数の場合、
値ごとに頻度分布をとることで、より正確に近似可能
頻度分布を利用してジョインのレコード数を近似
Database System Implementation
R(a,b)
R(a,b) wv S(b,c)
S(b,c)
b の値
頻度
b の値
頻度
b の値
頻度
0
150
0
100
0
150×100 = 15,000
1
200
1
80
1
200×80 = 16,000
5
100
2
70
2
50×70 = 3,500
その他
550
その他
250
5
100×25 = 2,500
合計
1,000
合計
500
V(R,b) = 14
他の値の数は11個
V(S,b) = 13
他の値の数は10個
b の値
頻度
b の値
頻度
2
550/11=50
5
250/10=25
0, 1, 2, 5 以外に現れる異なる b の値の数は、
R が10個、Sが9個。両方に現れるのは９個。
その他 50×25×９ = 11,250
合計
48,250
頻度分布が均一と
考える従来の近似では
1,000×500/14=35,714
ヒストグラムを利用した近似
Database System Implementation
過去10年間で、最高気温が同一の３月と７月の日を列挙せよ
March(day, temp)
July(day, temp)
SELECT March.day, July.day
FROM March, July
WHERE March.temp = July.temp
15-19 度
20-24 度
20×5/5 = 20 レコード
10×20/5 = 40 レコード
合計 60 レコード
均等な頻度分布を仮定して近似すると
310×310 / 40 = 2402.5
最高気温
（摂氏）
3月の
日数
7月の
日数
0-4
50
0
5-9
130
0
10-14
100
0
15-19
20
5
20-24
10
20
25-29
0
110
30-34
0
160
35-39
0
15
合計
310
310
問合せ木の代数的変換と最終結果の近似
Database System Implementation
R(a,b)
S(b,c)
T(R)=5,000
T(S)=2,000
V(R,a)=50
V(R,b)=100
V(S,b)=200
V(S,c)=100
σa=10(R(a,b) wv S(b,c))
50,000/50
=1,000
σa=10
100×2,000/200 wv
=1,000
5,000×2,000/200 wv
=50,000
R
(σa=10R(a,b)) wv S(b,c)
5,000/50
=100
S
σa=10
R
S
Database System Implementation
複数ジョインの問合せ戦略
復習：２つの関係をジョインする戦略
Database System Implementation
R(a,b) wv S(b,c)
R(a,b) が S(b,c) より大きいと仮定
S(b,c) が主記憶に入る場合 (One-pass Join)
S(b,c) のレコードを属性 b の値でハッシュ
R(a,b) をディスクからブロックごとに転送
入らない場合
Nested-Loop Join
インデックスを利用したジョイン
R(a,b) を外側、S(b,c) を内側のループ
ジョイン戦略の例
Database System Implementation
StarsIn(title, year, starName)
MovieStar(name, address,
gender, birthdate)
SELECT title
FROM StarsIn, MovieStar
WHERE starName = name AND
birthdate LIKE ‘%1960’
πtitle
wv
starName = name
StarsIn
σbirthdate LIKE ‘%1960’
MovieStar
これら２つの関係の
大きさに応じて
ジョイン戦略を
適切に利用
３個以上の関係をジョインする表現：ジョイン木
Database System Implementation
R wv S wv T wv U
wv
U
wv
T
wv
R
wv
wv
wv
R
S T
S
左線形木
右の子は葉ノード
R
wv
U
wv
S
wv
T
bushy 木
（低木）
U
右線形木
左の子は葉ノード
さらに各ジョイン木の骨格ごとに関係の順列は 4! 個
ジョイン木の骨格の数
Database System Implementation
T (n)　: n 個の関係からなるジョイン木の骨格の数
T (1)  1
n1
T (n)  T (i) T (n  i) (  2T (n 1)  2n2 )
i 1
T (1)  1
T (2)  1
T (3)  2
T (4)  5
T (5)  14
T (6)  42

T(n)
wv
T(n-i)
T(i)
各 i = 1, 2, ..., n-1 について
左線形木を One-pass Join で実装
Database System Implementation
利点： One-pass Join を実行し、中間結果は１つだけ保持
中間結果は主記憶に格納できると仮定
中間結果を小さくする工夫：
関係の大きさを昇順 R ≦ S ≦ T ≦ U で選ぶ
1. R を読込み、ジョインする属性でハッシュ
wv
2. S を読込み、Sは外側ループで
R wv S を計算
wv
U
3. R を削除し、R wv S をジョインする
属性でハッシュ
4. T を読込み、Tは外側ループで
wv
T
(R wv S) wv T を計算
：
R
S
bushy 木を One-pass Join で実装
Database System Implementation
wv
wv
R
wv
S T
複数の中間結果を管理する必要性
U
主記憶に格納するか、
ディスクに退避するか
動的計画法による最良ジョイン木の選択
Database System Implementation
• レコード数T(R)、異なる値の数 V(R,a) をつかい
中間結果のレコード数を近似
• 中間結果のレコード数の和を、
ジョイン木の計算コストと考える
• 最小コストの最良ジョイン木を動的計画法で計算
• 全ジョイン木を対象にするか？
左線形木に限定するか？
動的計画法の例
Database System Implementation
R(a,b)
レコード数
S(b,c)
1,000
T(c,d)
1,000
U(d,a)
1,000
異なる値の数 V(R,a)=100
V(R,b)=200
V(U,a)=50
V(S,b)=100
V(S,c)=500
V(T,c)=20
V(T,d)=50
ジョインする関係
レコード数
最良ジョイン木
ジョインする関係
レコード数
最良ジョイン木
評価値
{R, S}
{R, T}
5,000
1M
RwvS
1,000
RwvT
{R, S, T}
10,000
(SwvT)wvR
2,000
{R, U}
10,000
RwvU
{R, S, U}
50,000
(RwvS)wvU
5,000
{S, T}
V(U,d)=1,000
{S, U}
2,000
SwvT
1M
SwvU
{R, T, U}
10,000
(TwvU)wvR
1,000
{T, U}
1,000
TwvU
{S, T, U}
2,000
(TwvU)wvS
1,000
{R, S, T} の計算例
Database System Implementation
R(a,b)
S(b,c)
1,000
レコード数
異なる値の数 V(R,b)=200
T(c,d)
1,000
V(S,b)=100
V(S,c)=500
関係の集合
{R, S}
{R, T}
レコード数
5,000
1M
最良ジョイン木
5,000×1,000/500
=10,000
wv
5000 wv
R
V(T,c)=20
{R, U}
RwvT
{S, T}
10,000
2,000
RwvU
1M×1,000/(200×500)
=10,000
SwvT
2,000×1,000/200
=10,000
wv
T
S
RwvS
1,000
1M wv
R
S
T
wv
2000 wv
S
R
T
R wv T wv S wv U のレコード数
Database System Implementation
R(a,b)
レコード数
S(b,c)
1,000
T(c,d)
1,000
1,000
異なる値の数 V(R,a)=100
V(R,b)=200
V(S,b)=100
V(T,c)=20
V(T,d)=50
レコード数
最良ジョイン木
コスト
1,000
V(U,a)=50
V(S,c)=500
ジョインする関係
U(d,a)
{R, S, T}
10,000
(SwvT)wvR
2,000
{R, S, U}
50,000
(RwvS)wvU
5,000
V(U,d)=1,000
{R, T, U}
{S, T, U}
10,000
(TwvU)wvR
2,000
(TwvU)wvS
1,000
((S wv T) wv R) wv U
10,000×1,000/(100×1,000)=100
1,000
R wv T wv S wv U の最良ジョイン木
Database System Implementation
ジョインする関係
レコード数
最良ジョイン木
{R, S}
5,000
RwvS
1M
RwvT
{R, S, T}
ジョインする関係
10,000
レコード数
最良ジョイン木
{R, T}
(SwvT)wvR
コスト
ジョイン木
2,000
{R, U}
10,000
RwvU
{R, S, U}
50,000
(RwvS)wvU
5,000
{S, T}
{S, U}
2,000
{T, U}
1M
SwvT
SwvU
{R, T, U}
10,000
(TwvU)wvR
1,000
1,000
TwvU
{S, T, U}
2,000
(TwvU)wvS
1,000
コスト（中間結果のレコード数の総和）
((SwvT)wvR)wvU
2,000+10,000 = 12,000
((RwvS)wvU)wvT
5,000+50,000 = 55,000
((TwvU)wvR)wvS
1,000+10,000 = 11,000
((TwvU)wvS)wvR
1,000+2,000 = 3,000 全ジョイン木
(RwvS)wv(TwvU)
5,000+1,000 = 6,000 での最良木
(RwvT)wv(SwvU)
1M+1M = 2,000,000 (bushy 木を含)
(RwvU)wv(SwvT)
10,000+2,000 = 12,000
計算コストについての注意
Database System Implementation
中間結果のレコード数の和を、
ジョイン木の計算コストとするのが不正確な場合
R(a,b) wv S(b,c)
• R(a,b) に１つのレコード、S(b,c) の b にインデックスがある
ほとんど計算時間がかからない
• R(a,b) に１つのレコード、S(b,c) にインデックスが無い
S(b,c) の全ブロックを読込む手間
• これらの要素を取りこむのは容易
現実の DBシステムでは実行されている
貪欲(greedy)アルゴリズム
Database System Implementation
• 動的計画法では i 個の関係からなる全部分集合の
最良ジョイン木を生成
n -1 個の
C
+
C
+
C
+
...
+
C
=
2
n 1
n 2
n 3
n n
部分集合を考慮
• 計算時間を減らすため貪欲アルゴリズムでは
ジョイン木の計算コストが最小の部分集合だけを
各段階で残す
貪欲(greedy)アルゴリズム
Database System Implementation
R(a,b)
S(b,c)
1,000
レコード数
異なる値の数
T(c,d)
1,000
U(d,a)
1,000
V(R,a)=100
V(U,a)=50
V(R,b)=200
V(S,b)=100
V(S,c)=500
V(T,c)=20
V(T,d)=50
ジョインする関係
レコード数
最良ジョイン木
ジョインする関係
{R, S}
{R, T}
5,000
1M
RwvS
RwvT
{R, S, T}
10,000
レコード数
最良ジョイン木
(SwvT)wvR
評価値
ジョイン木
1,000
{R, U}
10,000
RwvU
{R, S, U}
50,000
(RwvS)wvU
計算しない
2,000
5,000
V(U,d)=1,000
{S, T}
{S, U}
2,000
SwvT
1M
SwvU
{R, T, U}
1,000
TwvU
{S, T, U}
10,000
(TwvU)wvR
{T, U}
2,000
(TwvU)wvS
1,000
評価値（中間結果のレコード数の総
和）
1,000
Database System Implementation
ジョイン無矛盾
Acyclic Hypergraph
Jeffrey D. Ullman: Principles of Database and Knowledge-base Systems,
Volume II, The New Technologies, Computer Science Press (1989)
ISBN 0-7167-8162X, Chapter 11
動機
Database System Implementation
ジョインを実行する前に無駄なレコードを減らせないか？
無駄がない状態とは？
関係 R(V1), R(V2), ..., R(Vn) Vi は属性のリスト
大域的ジョイン無矛盾 (globally join consistent)
πVi (R(V1) wv R(V2) wv ... wv R(Vn))=R(Vi)
すべてのレコードが最終的に使われる
局所的ジョイン無矛盾 (locally join consistent)
πVi (R(Vi) wv R(Vj))=R(Vi) 任意の i, j について
局所的には無駄がない
ジョイン無矛盾は集合意味論を前提とする
Database System Implementation
R(a,b) = πa,b(R(a,b)wv R(b,c)) ??
R(a,b)
0 0
1 1
R(b,c)
0 0
1 1
1 2
bags 意味論
0
1
1
R(a,b)wvR(b,c)
0
1
1
0
1
1
0
1
2
πa,b(R(a,b)
wv R(b,c))
集合意味論
以後、集合意味論を仮定する
0
1
1
πa,b(R(a,b)
wv R(b,c))
0
1
0
1
局所的だが、大域的ジョイン無矛盾でない例
Database System Implementation
R(a,b)
0 0
1 1
2 2
R(b,c)
0 0
1 1
2 2
R(c,a)
0 1
1 0
2 2
R(a,b) wv R(b,c) wv R(c,a) ={(2,2,2)}
R(Vi) に出現し、
πVi (R(V1) wv R(V2) wv ... wv R(Vn))
に出現しないレコードを dangling（宙ぶらり）レコード
局所的だが、大域的ジョイン無矛盾でない例
Database System Implementation
R(ai , ai+1)
R(ai, ai+1) wv R(ai+1, ai+2)
1
2
1
2
1
1
4
1
2
3
2
1
1
4
1
2
3
1
4
3
3
2
2
1
2
3
4
2
1
4
4
1
2
3
2
4
3
:
:
:
R(a1,a2) wv R(a2,a3) wv R(a3,a1) = {}
奇偶
偶奇
奇偶
偶奇
奇偶
偶奇
16個の
レコード
すべて
dangling
dangling レコードの除去
Database System Implementation
dangling レコードをジョインを計算する前に
除去できないか？
計算中に生成されるレコードも無駄がなくなる
性質
大域的ジョイン無矛盾の場合は{V1, V2,..., Vn} の
任意の部分集合{W1, W2, ..., Wk} について
πW1 ∪ W2 ∪ ... ∪ Wk(R(V1) wv R(V2) wv ...
=R(W1) wv R(W2) wv ... wv R(Wk)
wv
R(Vn))
セミジョイン（semi-join）
Database System Implementation
R(a,b) n R(a,c)
R(a,b)
a
1
2
2
b
2
3
4
= πa,b(R(a,b) wv R(a,c))
= R(a,b) wv πaR(a,c)
R(a,b)wvR(a,c)
a
2
2
b
3
4
πaR(a,c)
R(a,c)
a
3
2
c
5
6
a
3
2
c
6
6
R(a,b)nR(a,c)
a
2
2
b
3
4
セミジョインを使った dangling レコード除去
Database System Implementation
効果がある場合
R(a,b,c)
R(c,d,e)
0
1
0
0
1
0
:
:
:
:
:
:
0
n
0
0
n
0
1
1
1
:
:
:
1
n
1
R(a,b,c)nR(c,d,e)
0
1
0
:
:
:
0
n
0
R(a,b,c) wv R(c,d,e)
において宙ぶらり
セミジョインを使った dangling レコード除去
Database System Implementation
R(a,b)
R(b,c)
R(c,d)
R(b,c) := R(b,c)nR(c,d)
1
2
1
2
1
2
R(a,b)
2
4
2
4
2
4
1
2
3
6
3
6
3
6
2
4
4
8
4
8
4
8
3
6
4
8
R(a,b)oR(b,c) ⇒ R(b,c)
1
2
2
4
3
6
4
8
2
4
4
8
1
2
2
4
3
6
4
8
R(b,c)oR(c,d) ⇒ R(c,d)
1
2
2
4
3
6
4
8
2
4
2
R(c,d)
4
4
4
8
8
R(a,b) := R(a,b)nR(b,c)
R(a,b)
1
R(b,c)
R(c,d)
2
2
4
4
4
8
R(b,c)
8
R(a,b) wv R(b,c) wv R(c,d)
={ (1,2,4,8) }
セミジョインを使った dangling レコード除去
Database System Implementation
dangling レコードを除去できない局所的ジョイン無矛盾な関係
dangling
レコード
R(a,b)
0 0
1 1
2 2
R(b,c)
0 0
1 1
2 2
R(a,b) n R(b,c)
= πa,b(R(a,b) wv R(b,c))
= R(a,b)
R(c,a)
0 1
1 0
2 2
セミジョインの定義
局所的ジョイン無矛盾
セミジョインを使った宙ぶらりレコード除去方法は
どこまで一般化できるか？
データベーススキームとハイパーグラフ
Database System Implementation
a
関係の集合 { R(V1), R(V2), ..., R(Vn) }
データベーススキーム { V1, V2, ..., Vn }
例
{R(a,d,e),R(b,d,f),R(c,e,f),R(d,e,f)}
{ade, bdf, cef, def}
註：属性の集合 {a,d,e} は
簡潔に ade と記述
d
b
e
f
c
{ade, bdf, cef, def}を
２通りのハイパーグラフで表現
d
データベーススキームの各属性をノード、
各要素（集合）をハイパー辺
（属性を線で囲んで表現）とするグラフ
a
e
b
c
f
GYOのハイパーグラフ簡略化
Database System Implementation
(Graham-Yu-Ozsoyoglu)
ハイパー辺 V に対して、あるハイパー辺 W が存在し
V の各属性は
(1) V にだけ現れるか、
(2) W にも現れる
のどちらかである場合、V は（W の）耳と呼ぶ
V
a
例
ade は def の耳
bdf は def の耳
：
d
b
W
e
f
c
GYOのハイパーグラフ簡略化
Database System Implementation
GYO のハイパーグラフ簡略化
• 耳は存在する限り削除する
d
a
d
b
b
e
f
空の
グラフ
註：def は耳
e
f
c
c
d
e
f
d
e
f
c
Acyclic Hyper-graph / Full Reducer
Database System Implementation
GYO の簡略化で空になるハイパーグラフを Acyclic と呼ぶ
データベーススキームが Acyclic のとき、dangling レコードを
完全に除去するプログラム（Full Reducer）を次のように作成
複数のハイパー辺を含む Acyclic hyper-graph G から
ハイパー辺 V1 が V2 の耳になり削除され、
V1
hypergraph G－{V1} が生成された場合
R(V2) := R(V2) n R(V1)
G－{V1} に本手続きを適用
R(V1) := R(V1) n R(V2)
V2
G－{V1}が1つのハイパー辺だけの場合は、何も生成しない
Full Reducer の例
Database System Implementation
abe, bdf, cef, def
ハイパー辺が削除された順番
R(d,e,f) := R(d,e,f) n R(a,d,e)
R(d,e,f) := R(d,e,f) n R(b,d,f)
R(d,e,f) := R(d,e,f) n R(c,e,f)
R(c,e,f) := R(c,e,f) n R(d,e,f)
R(b,d,f) := R(b,d,f) n R(d,e,f)
R(a,d,e) := R(a,d,e) n R(d,e,f)
R(a,d,e)
R(b,d,f)
a
d
b
e
f
R(c,e,f)
0
2
1
0
1
3
0
2
3
0
3
1
0
3
2
0
1
3
削除
R(d,e,f)
1
2
3
2
1
3
3
1
2
削除
削除
c
性質
Database System Implementation
定理
関係の集合 { R(V1), R(V2), ..., R(Vn) } の
データベーススキーム { V1, V2, ..., Vn } に対応する
ハイパーグラフが Acyclic の場合
Full Reducer により、すべての dangling レコードを除去できる
なお、Acyclic データベースが局所的ジョイン無矛盾ならば、
Full Reducer は何も除かない。
つまり dangling レコードは既に存在しないので、
大域的ジョイン無矛盾である
証明
Database System Implementation
Full Reducer
R(V2) := R(V2) n R(V1)
G－{V1} の Full Reducer
R(V1) := R(V1) n R(V2)
r1
r2
V1
帰納法
• R(Vj) ⊇ πVj (R(V1) wv R(V2) wv
rj
r
r1’
V2
Vj
... wv R(Vn)) は自明。逆を証明。
• 最後のセミジョイン R(V1) := R(V1)nR(V2)は、任意の r1 ∈R(V1) に対し、
ある r2 ∈R(V2) が存在し、 r1 と r2 は V1∩V2 上で一致することを保証
• 帰納法の仮定より r2 ∈πV2(R(V2) wv ... wv R(Vn))
r1 と r2 は V1∩V2 で一致し、V1 は V2 の耳だから、
r1 ∈πV1(R(V1) wv R(V2) wv ... wv R(Vn))
• 帰納法の仮定より、任意の rj∈R(Vj) を拡張した r ∈R(V2)wv...wvR(Vn)
が存在。最初のセミジョイン R(V2) := R(V2)nR(V1) は、あるr1’∈R(V1)
と r が V1∩V2 上で一致することを保証。したがって
rj ∈πVj (R(V1) wv R(V2) wv ... wv R(Vn))
Database System Implementation
ジョインの射影を
Acyclic Hypergraph
で効率的に計算
Jeffrey D. Ullman: Principles of Database and Knowledge-base Systems,
Volume II, The New Technologies, Computer Science Press (1989)
ISBN 0-7167-8162X, Chapter 11
GYOの簡略化プロセスを木構造化
Database System Implementation
GYO簡略化で V を W の
耳として削除するとき、
V を子、W を親ノードとする
{ade, bdf, cef,
def, cg, ci}
a
e
d
b
def
f
c
g
i
ade
bdf
cef
cg
ci
ジョインの射影
Database System Implementation
πX1, X2, ..., Xk (R(V1)
wv
R(V2)
wv
...
wv
R(Vn))
集合意味論を仮定（bags意味論でない）
ジョイン R(V1) wv R(V2) wv ... wv R(Vn)
を計算してから射影するのではなく、
射影を実行しつつジョインを計算することで
効率をあげられないか？
データベーススキームのハイパーグラフが Acyclic だと
効果的な方法がある
Yannakakis のアルゴリズム
Database System Implementation
πX (R(V1) wv R(V2) wv
... wv R(Vn))
{ V1, V2, ..., Vn } のハイパーグラフは Acyclic
X の属性は「被射影属性」とよぶ
ステップ1
Full Reducer で dangling レコードをすべて除去
ステップ２
GYO簡略化プロセスを木構造化し、ボトムアップに走査
（すべての子ノードの後に親ノードを訪問する順番）
ノード V を訪問しているときの親ノードを W
W に加え V にあり W にない被射影属性上に射影した
πW ∪ (X ∩ (V － W))(R(W) wv R(V))
を親ノード W の関係として置き換える
ステップ３
根ノードに計算された関係を X 上に射影
Yannakakis のアルゴリズムの実行例
Database System Implementation
被射影属性は {a,g}
R(d,e,f)
1
1
1
1
2
2
R(a,d,e)
R(b,d,f)
R(c,e,f)
1
1
1
1
1
1
1
1
1
1
1
2
1
1
2
2
2
2
2
1
1
2
1
2
R(c,g)
R(c,i)
1
1
1
1
2
1
2
2
Yannakakis のアルゴリズムの実行例
Database System Implementation
R(d,e,f)
1
1
1
1
2
2
{c,e,f}∪({a,g}∩({c,g}－{c,e,f}))
= {c,e,f,g}
R(c,e,f,g)
R(a,d,e)
R(b,d,f)
R(c,e,f)
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
2
2
2
2
2
2
2
1
2
1
1
2
1
2
πc,e,f,g(R(c,e,f)wvR(c,g))
R(c,g)
R(c,i)
1
1
1
1
2
1
2
2
Yannakakis のアルゴリズムの実行例
Database System Implementation
R(d,e,f)
1
1
1
1
2
2
{c,e,f,g}∪({a,g}∩({c,i}－{c,e,f,g}))
= {c,e,f,g}
R(c,e,f,g)
R(a,d,e)
R(b,d,f)
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
2
2
2
2
1
2
1
1
2
1
2
変化なし
πc,e,f,g(R(c,e,f,g)wvR(c,i))
R(c,i)
1
1
2
2
Yannakakis のアルゴリズムの実行例
Database System Implementation
{d,e,f}∪({a,g}∩({c,e,f,g}－{d,e,f})) = {d,e,f,g}
R(d,e,f)
R(d,e,f,g)
1
1
1
1
1
1
1
1
2
2
1
2
2
1
πd,e,f,g(R(d,e,f)wvR(c,e,f,g))
R(c,e,f,g)
R(a,d,e)
R(b,d,f)
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
2
2
2
2
1
2
1
1
2
1
2
Yannakakis のアルゴリズムの実行例
Database System Implementation
{d,e,f,g}∪({a,g}∩({b,d,f}－{d,e,f,g})) = {d,e,f,g}
R(d,e,f,g)
1
1
1
1
1
2
2
1
R(a,d,e)
R(b,d,f)
1
1
1
1
1
1
1
1
2
1
1
2
2
1
1
2
1
2
R(b,d,e,f,g)
1
1
1
1
1
1
1
2
2
1
2
1
1
1
1
2
1
2
2
1
R(d,e,f,g)wvR(b,d,f)
R(d,e,f,g)
1
1
1
1
1
2
2
1
πd,e,f,g(R(d,e,f,g)wvR(b,d,f))
集合意味論をとっているので
Yannakakis のアルゴリズムの実行例
Database System Implementation
{d,e,f,g}∪({a,g}∩({a,d,e}－{d,e,f,g})) = {a,d,e,f,g}
R(d,e,f,g)
R(a,d,e,f,g)
1
1
1
1
1
1
1
1
1
1
2
2
1
1
1
2
2
1
πa,d,e,f,g(R(d,e,f,g)wvR(a,d,e))
R(a,d,e)
1
1
1
1
1
2
R(a,g
)
1
1
被射影属性 a,g 上に
射影しておしまい
Yannakakis のアルゴリズムの正当性
Database System Implementation
ステップ２の各ノード V で以下の性質が成り立つことを、
ノードの訪問順序に関する帰納法で証明できる
• πW ∪ (X ∩ (V － W))(R(W) wv R(V)) =
πW ∪ (X ∩ (V － W))(R(V1) wv R(V2) wv ... wv R(Vn))
中間の計算結果のレコード数は、
すべての関係のジョインのレコード数を超えない
• W ∪ (X ∩ (V － W)) は V を根とする部分木に現れる
すべての被射影属性を含む
従って根ノードで最終的に計算される関係 R(U) は
• R(U) = πU(R(V1) wv R(V2) wv ... wv R(Vn))
•X⊆U
よって R(U) を X 上に射影すれば
πx(R(V1) wv R(V2) wv ... wv R(Vn)) を計算できる
Yannakakis のアルゴリズムの計算効率
Database System Implementation
ステップ２でノード V を訪問時に親ノードW（あるVi に一致）に
計算される関係は
πW ∪ (X ∩
(V － W))(R(V1)
⊆ R(W) × πX ∩
R(Vn))
wv R(V2) wv
(V － W)(R(V1)
... wv R(Vn))
wv R(V2) wv
... wv
W と X ∩ (V － W) に共通する属性がないから
|πX ∩ (V － W)(R(V1) wv R(V2) wv ... wv R(Vn))| ≦
|πX (R(V1) wv R(V2) wv ... wv R(Vn))|
つまり中間の関係のレコード数は、ある入力の関係 Vi (=W)のレ
コード数と、最終計算結果の関係のレコード数の積で抑えられる

Download Report