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

查询处理问题 集中式 查询转换为代数表达式 从所有等价表达式中选择最优的代数表达式 分布式 除了集中式问题外，还有 站点之间交换数据的操作 选择最优的执行站点(分布） 数据被传送的方式 例子 S(s#, sname, age, sex) 104 元组 Site A C(c#, cname, teacher) 105 元组 Site B SC(s#, c#, grade) 106 元组 Site A 每个元组长度100bit, 通讯传输速度 104 bit/sec, 通讯延迟 1sec 查询: 所有选修maths 课的男生学号和姓名. SELECT s#, sname FROM S, C, SC WHERE S.s#=SC.s# AND C.c#=SC.c# AND sex=‘男’ AND cname=‘maths’; 代价公式 QC = I/O 代价 + CPU 代价 + 通讯代价 通讯代价 TC = 传输延迟时间C0 + (传输数据量X /数据传输速率C1) =传输次数*1+传输的bit数*104。 传统的集合运算 传统的集合运算 传统的集合运算 广义笛卡尔积 专门的关系运算 选择运算 选择运算 投影运算 连接运算（θ连接） 等值连接 自然连接 半连接 左外连接 右外连接 全外连接 除运算 除运算 关系代数表达式 SQL与代数的等价描述 E1 SELECT sname FROM S, SC WHERE S.s#=SC.s# and SC.c#=‘c03’; 代数描述 ?sname(?s.s#=SC.s# and SC.c#=‘c03’(S×SC)) E2 SELECT sname FROM S WHERE S.s# in ( SELECT SC.s# FROM SC WHER c#=‘c03’); 代数描述 ?sname(?s.s#=SC.s# (S × ? SC.c#=‘c03’ SC)) E3 SELECT sname FROM S , ( SELECT SC.s# FROM SC WHER c#=‘c03’) SCC WHERE S.s# = SCC.s# ; 代数描述 ?sname(S ∞ ? SC.c#=‘c03’ SC) 一元操作：只涉及一个操作对象 ? (SL), ? (PJ) 二元操作：涉及两个操作对象 ∪ (UN), ∩（） , － (DF), × (CP), ∞θ（），∞ (JN), ∝ (SJ), 等价变换规则 空值的变换 R ? ? = R R ? ? = ? R ∞ ? = ? ? ∝ R = ? ? - R = ? R - ? = R R ∞θ ? = ? R × ? = ? ? (?) = ? ? (?) = ? 自身操作的等价 R ? R = R R ? R = R R ∞ R = R 一元操作 ?F1 (?F2(R)) = ?F1and F2(R) ? ? (R) = ?(R) ?A1,…,An(?B1,…,Bm(R)) = ?A1,…,An(R) 交换律 ?1 (?2 (R)) = ?2 (?1 (R)) 条件: ?1 ?2 是 选择操作 时总成立 ?1 ?2 是 投影操作时要求其属性集合相等 ?1 与 ?2 是投影和选择操作时: ? A1,…An(? F(R)) = ? F (? A1,…An (R)) 的条件是 F中的属性是 A1, …. An 的子集 R ∞ S = S ∞ R R × S = S × R R ? S = S ? R R ? S = S ? R R ∝ S ? S ∝ R R - S ? S - R 结合律 R B ( S B T ) = (R B S) B T) B: 二元操作 ∞（JN）, ×（CP）, ∪（UN）, ?