数据库的原理与技术.pptVIP

6.5.2 等价规则 （5） 7. 选择运算在下面两个条件下对theta连接运算具有分配律： a.当选择条件θ0的所有属性只涉及参与连接运算的表达式之一(E1)时： σθ0(E1 || θE2)= (σθ0(E1)) || θE2 b.当选择条件θ1只涉及E1的属性，选择条件θ2只涉及E2的属性时： σ θ1 ∧ θ2(E1 || θE2) = (σ θ1(E1)) || θ(σ θ2(E2)) 6.5.2 等价规则 （6） 8. 投影运算对theta连接运算具有分配律： a.令L1、L2分别是E1、E2的属性。假设连接条件θ只涉及L1∪L2中的属性，则： ∏L1 ∪L2 (E1 || θE2)=(∏ L1(E1)) || θ(∏L2(E2)) b.考虑连接E1 || θE2。令L1、L2分别是E1、E2的属性；令L3是E1中出现在连接条件θ中但不在L1∪L2中的属性；令L4是E2中出现在连接条件θ中但不在L1∪L2中的属性。那么： ∏L1 ∪L2 (E1 || θE2) = ∏L1 ∪L2 ((∏ L1 ∪L3 (E1)) || θ(∏L2∪L4(E2))) 6.5.2 等价规则 （7） 9. 集合运算并与交满足交换律 E1∪E2= E2∪E1 E1∩E2= E2∩E1 集合差运算不满足交换律 10.集合运算并与交满足结合律 (E1∪E2)∪E3= E1∪(E2∪E3) (E1∩E2)∩E3= E1∩(E2∩E3) 集合差运算不满足结合律 6.3.3 连接运算（8） 块嵌套循环连接（续） 一些改进： 连接属性是内层关系的码时，内层循环可中途跳出。 内层循环轮流做正、反向扫描，重用缓冲区中的数据，以减少磁盘读取。 内层循环利用索引。 6.3.3 连接运算（9） 索引嵌套循环连接：在内层循环中利用连接属性上的索引。 for each 元组 tr in r do begin for each与元组tr满足连接条件的索引项 in s关系在连接属性上的索引do begin 利用索引取到相应的ts 把tr ? ts加到结果中 end end 6.3.3 连接运算（10） 索引嵌套循环连接（续） 代价： 最坏情况（缓冲区只能够容纳关系r的一个块和索引的一个块）： br + nr * c 或 bs + ns * c 最好情况不必考虑，因为不必采用索引嵌套循环连接方法。 对关系S使用连接条件利用索引进行选择操作的代价 6.3.3 连接运算（11） 排序-归并连接 类似于外排序的归并算法的思路，进行连接运算。 前提：两个关系的元组都已按连接属性排好序。 适用于自然连接和等值连接。 a 3 b 1 d 8 d 13 f 7 m 5 q 6 a A a G c L d N m B r s a1 a2 a1 a3 在归并连接中使用的已排序关系 r s 6.3.3 连接运算（12） pr := r的第一个元组的地址 ps := s的第一个元组的地址； while (ps≠null and pr≠null) do begin ts := ps所指向的元组； Ss := { ts }； 让ps指向关系s的下一个元组； done := false; while (not done and ps≠null) do begin ts’:= ps所指向的元组； if (ts’[JoinAttrs] = ts[JoinAttrs]) then begin Ss := Ss∪{ ts’}； 让ps指向关系s的下一个元组； end else done := true； end 在连接属性上