第3章 分布式数据库中的查询处理和优化.ppt

练习1 有关系R，S，T，如图所示 计算连接R ∞ S ∞ T 计算机半连接R∝S，S∝R，S∝T，T∝S，R∝T，T∝R 8 6 2 5 3 5 6 4 3 8 6 1 6 3 5 5 3 2 C B A 4 8 5 6 1 4 6 9 5 3 8 6 9 5 3 6 5 3 D C B 9 8 3 6 5 8 8 7 8 9 6 6 F E D S R T 练习2 在如下R, S的概貌上计算R ∞A=B S Size(R)=50, Card(R)=100, Val(A[R])=50, Size(A)=3 Size(S)=5, Card(S)=50, Val(B[S])=50, Size(B)=3 R ∝A=B S 的选择度 ρ = 0.2 S ∝A=B R 的选择度 ρ = 0.8 C0=0,C1=1 问: 1. 使用 ∝简化程序在R的站点执行∞ 2. 使用 ∝简化程序在S的站点执行∞ 3. 使用直接连接在R站点执行∞ 4. 使用直接连接在S站点执行∞ 那种方案较优? R S 网络 站点1 站点2 总 结 分布式查询优化概述（目标、准则和代价估算） 基础知识 关系代数回顾 等价变换规则 分布式查询分类和层次结构 基于关系代数等价变换的查询优化 基于半连接算法的查询优化处理 基于直接连接算法的查询优化处理（四类算法） 代数操作对关系概貌的影响 选择操作 S= ?F（R） Card(S)= ρ *Card(R) Size(S)=Size(R) Val(B[S])是Val(B[R]), Card(S), Card(R)的函数 并操作 T=R∪S Card(T) ? Card(R)+Card(S) Size(T)=Size(R)=Size(S) Val(A[T]) ? Val(A[R])+Val([AS]) 5.2 半连接表示连接的代价估算 5 基于半连接算法的查询优化处理 代数操作对关系概貌的影响 连接操作 T=R∞S Card(T) =(Card(R)*Card(S))/Val(A[R]) Size(T) = Size(R)+Size(S) Val(A[T]) ? Min(Val(A[R]), Val(B[S])) A 是连接属性 Val(A[T]) ? Val(A[R])+Val(B[S]) A不是连接属性 半连接 T=R∝S ρ =Val(A[S])/Val(Dom(A)) Card(T) = ρ *Card(R) Size(T) = 第一个操作数Size（R） Val(A[T]) = ρ *Val(A[R]) 5.2 半连接表示连接的代价估算 5 基于半连接算法的查询优化处理 代价公式：T=C0+C1*X 在站点2上做投影?B (S) 把?B (S)传到站点1上，代价为： C0+C1* size (B)* val( B[S]) 在站点1上计算半连接，R’=R ∝A=B S 把R’从站点1传到站点2的代价为： C0+C1* size (R’)* card( R’) 在站点2上执行连接操作：R’ ∞A=BS 采用半连接的总代价 T半R= 2C0+C1* (size (R’)* card( R’) +size (B)* val( B[S])) T半S= 2C0+C1* (size (S’)* card( S’) +size (A)* val( A[R])) 比较T半R 与T半S, 取最优者 5.2 半连接表示连接的代价估算 5 基于半连接算法的查询优化处理 基本原理 通常有两次传输 但是传输的数据量和传输整个关系相比，要远远少 一般有：T半T全 半连接的得益：当card（R）card（R’），可减少站点间的数据传输量 半连接的损失：传输?B (S) =C0+C1* size (B)* val( B[S]) 基本原理是在传到另一个站点做连接前，消除与连接无关的数据，减少做连接操作的数据量，从而减小传输代价 采用半连接优化算法的步骤 计算每种半连接方案的代价，并从中选择一种最佳方案 选择传输代价最小的站点，计算采用全连接的方案的代价 比较两种方案，确定最优方案 5.3 半