分布式数据库试题及答案(6)

111

假设其中C0=0, C=1；

计算选择度：

ρ1（S?R）=Val(R,B)/Val(S,B)=1000/2000=0.5。

其中Val(S,B)是在关系S中属性B的不同值的个数也就是本题剖视图中的Val相的值,在这里是2000。

同理Val(R,B)也是如此。

ρ2（S?T）=Val(T,C)/Val(S,C)=50/100=0.5。

其中Val(S,C)是在关系S中属性C的不同值的个数也就是本题剖视图中的Val相的值,这里是100。

同理Val(T,C)也是如此。

ρ3（R?S）=Val(S,B)/Val(R,B)=2000/1000=2?1。

注意：当ρ>1时使ρ=1； 同理：ρ4(T?S)=1;

计算收益：

Benefit1(S?R)=(1-ρ1)*Size(S)*Card(S)*C1=(1-0.5)*30*1000=15000； 其中Size(S)是关系S的宽度又称为元组的大小，Size(S)的值是S 的各个属性大小的和，这里是30。

其中Card(S)是关系S的所有元组的个数又称序数,这里是1000。

Benefit2(S?T)= (1-ρ2)*Size(S)*Card(S)*C1=(1-0.5)*30*1000=15000； Benefit3(E?G)=0； Benefit4(J?G)=0；

计算代价(或称费用)：

Cost1(S?R)=C0+ C*Size(R,B)*Val(R,B)=10*1000=10000;

其中Size(R,B)是属性B的大小,这里是10。

其中Val(R,B)是属性B在关系R中的不同值的个数,这里是1000。 Cost2(S?T)= C0+ C*Size(T,C)*Val(T,C)=5*50=250

Cost3(R?S)= +?(无穷大) Cost4(T?S)= +?(无穷大)

因为收益为0，所以代价很大，以至于不能计算，故视为+?(无穷大)。

根据以上计算得到初始利益代价表，如下： R?S 选择性 收益 费用 1000/2000=0.5 (1-0.5)*30*1000=15000 10*1000=10000 P1:S SJR ENO根据R选择S的元组的比例 由于没选择S的部分的大小不用浪费通信代价,就是收益 传递R的部分的大小 P2:SSJT JNO50/100=0.5 2000/1000=2?1 100/50=2?1 (1-0.5)*30*1000=15000 0 0 5*50=250 +? +? P3:RSJS ENOP4:TSJS JNO

1

根据初始的利益代价表，得到受益半连接集P={P1,P2} 第三， 选择半连接 1) 循环1

从受益半连接集P中选择代价最小的P2 令S'= S?T,得到关系S'{B,C}

连接图（R ? S' ? T）

R ------------------ S'------------------- T B C

S1 S2 S3

A) 重新计算S'的概要图：

Card(S')=ρ2*Card(S)=0.5*4000=2000; 计算Val(S',B) ? B不属于选择谓词 Val(S,B)=2000

Val(S,B)/2=

故Val(S',B)=( Card(S')+ Val(S,B))/3=4000/3=1333 计算Val(S',C)

? C属于选择谓词

Val(S',C)= ρ2* Val(S,C)=50 因此，概要图如下：

Card(S')=2000 B C Size 10 5 Val 1333 50 B) 重新求可能的半连接 P1= S'?R

(因为，P2=S?T已经处理过，无需作P2= S'?T的半连接) P3= R? S' P4= T? S'

C) 重新计算利益代价

P1= S'?R

ρ1=Val(R,B)/Val(S',B)= 1000/1333=0.75

Benefit1=(1-0.75)*Card(S')*Size(S') = 0.25*2000*15=7500

Cost3(S'?R) = C*Size(R,B)*Val(R,B)=10*1000=10000 P3= R? S'

ρ3= Val(S',B)/Val(R,B)=1000/1000=1 Benefit3=(1-ρ

3)*Card(R)*Size(R)=0

Cost3(S'?T) = +? P4= T? S'

ρ4= Val(S',C)/Val(T,C)=50/50=1; Benefit4=(1-1)* Card(T)*Size(T)=0;

Cost4(T? S') = +?

1

利益代价表： 半连接? 选择度ρ 利益Benefit 代价Cost 10000 P1 0.75 7500 +? P3 1 0 +? P4 1 0 所以受益的半连接集P={P1} 2) 循环2

从受益半连接集P中选择代价最小的P1 S''= S'?R得：S''{B,C}

连接图 ( R ? S'' ? T )

R------------------ S''------------------- T B C

S1 S2 S3

A) 重新计算 的概要图

Card(S'')=ρ1*Card(S')=0.75*2000=1500 计算Val(S'',B)

因为B属于选择谓词，所以

Val(S'',B)= ρ3*Val(S',B)=0.75*1000=750

计算Val(S'',C) ?C不属于选择谓词 Val(S',C)=50

Card(S'')>2* Val(S',C)=100 故Val(S'',C)= Val(S',C)=50 因此，概要图如下

Card(S'')=1500 B C Size 10 5 Val 750 50 B) 重新求可能的半连接 (因为，P1= S'?R已经处理过，无需作P1= S''?R的半连接) (因为，P2= S?T已经处理过，无需作P2= S''?T的半连接) P3=R? S'' P4=T? S''

C) 重新计算利益代价 P3= R? S''

ρ3=Val(S'',B)/Val(R,B)=750/1000=0.75

Benefit= Benefit3=(1-ρ

3)*Card(R)*Size(R)=0.25*1000*30=7500；

Cost3(R? S'')=C*Size(S'',B)*Val(S'',B)=10*750=7500； P4= T? S''

ρ4= Val(S'',C)/Val(T,C)=50/50=1; Benefit4=0;

Cost4(T? S'')= +?

利益代价表： 半连接? 选择度ρ 利益Benefit 代价Cost 7500 P3 0.75 7500 +? P4 1 0 3) 循环3 从受益半连接集P中选择代价最小的P3 R'= R? S''得：R'{A,B}

连接图 ( R' ? S'' ? T )

R'------------------ S''------------------- T B C

S1 S2 S3

A) 重新计算 的概要图

Card(R')=ρ3*Card(R)=0.75*1000=750 计算Val(R',A)

因为A不属于选择谓词，又Val(R,A)=1000 Val(R,A)/2=< Card(R')<=2* Val(R,A) 所以

Val(R',A)=( Card(R')+ Val(R,A))/3=583 计算Val(R',B) ?,B属于选择谓词

故Val(R',B)= ρ3* Val(R,B)=0.75*1000=750

因此，概要图如下

Card(R')=750 A B Size 20 10 Val 583 750

B) 重新求可能的半连接 P1= S''?R'

(因为，R'与T没有连接关系，故不用作P2 ) P3= R'? S''

(P4=T? S''已经做过，不用再作。) C) 重新计算利益代价 P1= S''?R'

ρ1=Val(R',B)/Val(S'',B)=750/750=1；

Benefit= Benefit3=(1-ρ1)*Card(R)*Size(R)=0; Cost3(S''?R')=+?； P3= R'? S''

ρ3= Val(S'',B)/Val(R',B)=750/750=1;

Benefit4=0;

Cost4(T? S'')= +? 利益代价表： 半连接? 选择度ρ 利益Benefit 代价Cost +? P3 1 0 +? P4 1 0 可知：无受益半连接，循环结束。 第四，计算执行场地 已知连接图：

R'------------------ S''------------------- T B C

S1 S2 S3

概要图:

Card(R')=750 A Size 20 Val 583

Card(S'')=1500 B Size 10 Val 750

Card(T) = 50 at 场地 S3

C Length 5 Val 50 根据连接图及概要图，代价计算: Cost(S1)=Cost(S'')+Cost(T)

=Card(S'')*Size(S'')+Card(T)*Size(T) =1500*15+50*5=22750=22.75K Cost(S2)=Cost(R')+Cost(T)

=Card(R')*Size(R')+Card(T)*Size(T) =750*30+50*5=22750=22.75K Cost(S3)=Cost(R')+ Cost(S'')

= Card(R')*Size(R')+Card(S'')*Size(S'') =750*30+1500*15=45,000=45K

对比以上各执行场地的代价，可知：场地1,2的代价Cost(S1),Cost(S2)最小。 所以，最后执行场地选S1,S2都可以。 3.3.2.对以上结果做相应的优化处理。

C 5 50 B 10 750

在执行策略集中，消去用于缩减处于执行场地上的关系的半连接操作。 执行策略集P'={P1,P2,P3},其中P1,P2,P3分别为：

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库分布式数据库试题及答案(6)在线全文阅读。