第七章 关系系统及其优化-new

1、第七章: 关系系统及其查询优化 q关系系统的定义和分类 q查询处理 q关系系统中的查询优化 关系系统的定义 q关系系统: 支持关系数据模型的数据库管理系 统(粗略) q关系系统(确切定义): 一个系统可以定义为一 个关系系统, 当且仅当它: 支持关系数据库 支持选择、投影和连接运算(自然连接), 对 这些运算不要求定义任何物理存取路径 关系系统的分类: q许多关系系统的产品 q按E.F.Codd的思想将关系系统分为: 表式系统表式系统(a) 最小关系系统最小关系系统(b) 关系完备的系统关系完备的系统(c) 全关系系统全关系系统(d) S M I S M I S M I S M I abc d

2、 S: Structure I: Integrity M: Manipulation 关系数据模型关系数据模型 集合操作集合操作 关系系统的查询处理: q查询处理的步骤: query Parser 关系代数表示: Q1= sname(Students.Sno=SC.Sno and Cno=2(StudentsSC) Q2= sname(Cno=2(Students SC) Q3= sname( Students Cno=2(SC) q代价计算 Q1代价计算(仅考虑I/O代价) 计算广义笛卡尔积代价 假定: 在内存中, 存放5块Students元组和一 块SC元组, 一块可以装10个Studen

3、ts元组或 100个SC元组. 假定: Students有1000个元组,SC有10000 个元组, 其中选2号课程的有50个元组 数据只有读到内存才能进行连接 Q1= sname( Students.Sno=SC.Sno and Cno=2(Students SC) 10 100 SC Students 5块块 通过读取块数计算I/O代价 读取块数计算方法: Students 1000个元组 SC 10000个元组 读取总块数: 若每秒读写20块, 则花费: 210010020100 100 10000 510 1000 10 1000 10 100 SC Students 5块块 s105

4、 20 2100 Q1= sname( Students.Sno=SC.Sno and Cno=2(Students SC) Student 块数块数 Student 读入内存读入内存 的次数的次数 SC块数块数 条件条件:Students 1000个元组，个元组， SC 10000个元组个元组 迪卡尔集后后的元组个数为: 103 104=107 连接后的中间结果内存放不下, 需暂时写到外存 若每块可装10个完成迪卡尔集后的元组, 则写这些元组需: (107 /10)/20=5 104s 选择操作: 读回需5 104s, 假设选择后剩50个元组,均可放在 内存 投影操作: 查询共花费: 105

5、+2 5 104 105 s 28小时 Q1= sname( Students.Sno=SC.Sno and Cno=2(Students SC) 10 100 SC Students 5块块 每秒读每秒读20块块 Q2= sname( Cno=2(Students SC) Q2代价计算(仅考虑I/O代价) 计算自然连接代价 也要把数据读到内存进行连接, 但连接结果比笛 卡尔积要小得多 读取块数依然为: 花费为2100/20 105s 假设连接结果大小为104个元组, 写到外存需: (104 /10)/20=50s 210010020100 100 10000 510 1000 10 1000

6、 每秒读每秒读20块块 Q2= sname( Cno=2(Students SC) Q3= sname( Students Cno=2(SC) 读取自然连接结果, 执行选择运算, 需50s, 选择结 果均可放在内存 投影运算: 总花费为: 105+50+50=205s 3.4分钟分钟 Q3代价计算(仅考虑I/O代价) 计算对SC做选择运算的代价 需读SC到内存进行选择运算 读SC块数为: 10000/100=100 花费为: 100/20=5s 选择结果为50个SC元组, 均可放在内存 Q3= sname( Students Cno=2(SC) 计算和Students自然连接的 代价 需读St

7、udents到内存进行连 接运算 读Students块数为: 1000/10=100 花费为: 100/20=5s 连接结果为50个元组, 均可放在内存 投影运算: 总花费: 5+5=10s 10 50 SC Students 5块块 关系系统的查询优化: q关系系统的查询优化由系统完成, 而不是由用户完 成 优化器可以从数据字典获取许多统计信息 如果数据库的物理统计信息改变了,优化器可 以对查询进行重新优化以选择适应的执行计划 优化器可以考虑数百种不同的执行计划 优化器包括了许多复杂的技术 q优化目标: 寻求最优的执行计划, 使查询执行开销 尽量小 关系系统的查询优化: q查询优化的一般步骤

8、 将查询转化成内部表示-语法树 根据等价变化规则, 将语法树转化成优化形式 选择低层操作算法 生成查询计划 q查询执行开销主要包括: 总代价=I/O代价+CPU代价 q多用户数据库执行开销: 总代价=I/O代价+CPU代价+内存代价 关系系统的查询优化: q查询优化的一般准则: 下面的优化策略一般能提 高查询效率, 但不一定是最优的 选择运算尽可能先做, 降低中间结果大小 在连接前,对关系适当的进行预处理: 对关系排序 (排序合并连接方法)或在连接属性上建索引(索引 连接方法) 95004 95002. 95003. 95001 . Students 95003 1 95003 2 95004

9、 2 . 95004 3 . 95001 1 . SC 循环嵌套连接循环嵌套连接(不不 做任何预处理做任何预处理): . 关系系统的查询优化: 95001 95002. 95003. 95004 . Students 95001, 1 95003, 1 95003, 2 95004, 2 . 95004, 3 . SC 排序合并连接排序合并连接(连连 接的关系分别排接的关系分别排 序序): . 索引连接索引连接(在在SC 的连接列的连接列Sno上上 建立索引建立索引): Students 95001 95003 95003 95004 95004 . SC索引索引 . 95004 95002.

10、 95003. 95001 . 95003, 1 95003, 2 95004, 2 . 95004, 3 . 95001, 1 . SC 关系系统的查询优化: 把投影运算和选择运算同时进行 sno (cno=2(SC) 把投影和其前或后的双目运算结合起来 Cname(Course SC) 把某些选择同在它前面要执行的笛卡尔积结合起 来成为一个连接运算 Students.Sno=SC.Sno and Cno=2(Students SC) 找出公共子表达式 sname( Students Cno=2(SC) 关系系统的查询优化: q关系代数等价变换规则: 给定 sname(Students.Sn

11、o=SC.Sno and Cno=2(StudentsSC) 如何将上述提到的运算先做, 即得到: sname( Students Cno=2(SC) 规则1: 连接、笛卡尔积的交换律 E1 E2 E2 E1 E1 E2= E2 E1 E1 E2= E2 E1 E: 关系代数表达式 F: 连接条件 规则2: 连接、笛卡尔积的结合律 (E1 E2) E3 = E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) F1 F F F2F1F2 关系系统的查询优化: 规则3: 投影的串接定律 A1,A2,.,An( B1,B2,.,Bn (E)

12、A1,A2,.,An(E) 规则4: 选择的串接定律 F1(F2(E) F1F2(E) 规则5: 选择和投影的交换律 F(A1,A2,.,An(E) A1,A2,.,An(F(E) 特殊情况 A1,A2,.,An( F(E) A1,A2,.,An( F( A1,A2,.,An, B1,B2,.,Bm (E) 规则6: 选择与笛卡尔积的交换律 F(E1 E2) F(E1) E2 F仅和E1有关 F(E1 E2) F1(E1) F2( E2 ) F= F1F2 F(E1 E2) F2(F1(E1)E2 ) F1-E1 F2-E1E2 关系系统的查询优化: 规则7: 选择与并的交换 F(E1 E2)

13、 F(E1) F(E2) 规则8: 选择与差的交换 F(E1- E2) F(E1)- F(E2) 规则9: 投影与笛卡尔积的交换 A1,A2,.,An, B1,B2,.,Bm(E1 E2) A1,A2,.,An(E1) B1,B2,.,Bm(E2) 规则10: 投影与并的交换 A1,A2,.,An (E1 E2) A1,A2,.,An(E1) A1,A2,.,An(E2) 关系系统的查询优化: q关系代数表达式的优化算法: 应用关系代数等价变 换规则来优化关系代数表达式, 使优化后的表达式 能遵循查询优化的一般准则, 在语法树上进行优化 关系代数表达式的优化算法 输入: 语法树 1 利用规则4

14、把形如F1F2Fn(E) 变换成 F1(F2( (Fn(E).) 2 对每一个选择, 利用规则48尽可能移到树的叶端 3 对于每个投影, 利用规则3, 9, 10尽可能移到树 的 叶端 4 利用规则35把选择和投影的串接合并成单个选 择, 单个投影, 或一个选择后跟一个投影 关系系统的查询优化: 5 把处理后的语法树内节点分组: 每一双目运算(, ,)和它的所有直接祖先(,)为一组, 后代直到叶子全是单目运算也并入该组; 若双目运算为,且其后的选择不能与它结合为等值连接时, 这些单目运算单独为一组. 6 生成一个程序, 每组节点的计算是程序中的一步 输出: 计算关系代数表达式的程序 21页页

15、SSP P 不能结不能结 合成等合成等 值连接值连接 S.Sno=SC.Sno SCS 能结合能结合 成等值成等值 连接连接 关系系统的查询优化: q优化的一般步骤: 因DBMS不同 把查询转换成某种内部表示(例如关系代数语法树) 把语法树转化成标准(优化)形式 选择底层的存取路径 生成查询计划, 选择代价最小的 q例子: 设有供应商S, 零件P和供应关系SP三个关系, 其关系模式: S(Snum, Sname, City) P(Pnum, Pname, Weight, Size) SP(Snum, Pnum, Dept, Quan) 关系系统的查询优化: select Sname from

16、S, SP, P where S.Snum=SP.Snum and SP.Pnum=P.Pnum and S.City=NANJING and P.Pname=Bolt and SP.Quan1000; 原始语法树: select-投影 from-笛卡尔积 where-选择 关系系统的查询优化: Sname c S SP P C=S.Snum=SP.Snum and SP.Pnum=P.Pnum and S.City=NANJING and P.Pname=Bolt and SP.Quan1000 Sname c SSP P Sname c SSP P s sp p Sname c SSP P

17、 s sp p Sname SSP P s sp p s p sp c c 优化优化: 练习练习1 查询要求查询要求: l查询信息系学生选修的所有的课程的课程名称查询信息系学生选修的所有的课程的课程名称 l写出关系代数及其原始语法树写出关系代数及其原始语法树,并进行优化处并进行优化处 理理,画出优化后的语法树画出优化后的语法树. SELECT Cname FROM Students,Course,SC WHERE Students.sno=SC.sno and Co=SC.cno and Sdept=IS; 练习练习1: Cname( Sdept=IS(Students SC Course)

18、Cname c Students SC Course 原始语法树原始语法树: Cname c1 Students SCCourse C:Students.sno=Sc.sno SC.cno=Co Sdept=IS C: SC.cno=Co ,C1: Sdept=IS Cname c1 Students SC Course c 练习练习2 查询要求查询要求: l一图书管理数据库，其关系如下：一图书管理数据库，其关系如下： BOOKS(Title,Author, Pname,LC_No) PUBLISHERS(Pname,Paddr,Pcity) BORROWERS(Name,Addr,City,

19、Card_No) LOANS(Card_No,LC_No,Date) 要求：要求： 1. 列出列出1999年年1月月1日前借出的所有书名和借书人姓名日前借出的所有书名和借书人姓名 2. 写出关系代数及其原始语法树写出关系代数及其原始语法树,并进行优化处理并进行优化处理,画出优化画出优化 后的语法树后的语法树. SELECT Title,Name from BOOKS,BORROWERS,LOANS WHERE BOOKS. LC_No = LOANS. LC_No AND BORROWERS. Card_No= LOANS. Card_No AND Date01/01/2003 图书编号图书编

20、号 图书证号图书证号 练习练习2: Title,Name( Date01/01/2003(BOOKS BORROWERS LOANS) Title,Name Date01/01/2003 BOOKS BORROWERS LOANS 原始语法树原始语法树: BOOKS. LC_No = LOANS. LC_No AND BORROWERS. Card_No= LOANS. Card_No Title,Author,Pname,LC_No,Name,Addr,City,Card_No,Date 练习练习2: Title,Name( Date01/01/2003(BOOKS BORROWERS LO

21、ANS) Date01/01/2003(BOOKS BORROWERS LOANS) = BOOKS Date01/01/2003(BORROWERS LOANS) =BOOKS BORROWERS Date01/01/2003(LOANS) Title,Name Date01/01/2003 BOOKS BORROWERS LOANS BOOKS. LC_No = LOANS. LC_No BORROWERS. Card_No= LOANS. Card_No 练习练习2: Title,Name( Date01/01/2003(BOOKS BORROWERS LOANS) 增加两个投影：增加两

22、个投影： Title， ，BOOKS. LC_No Name， ， LOANS. LC_No Title,Name Date01/01/2003 BOOKS BORROWERS LOANS BOOKS. LC_No = LOANS. LC_No BORROWERS. Card_No= LOANS. Card_No Title， ，BOOKS. LC_No Name， ， LOANS. LC_No 练习练习2: Title,Name( Date01/01/2003(BOOKS BORROWERS LOANS) Title,Name Date01/01/2003 BOOKS BORROWERS L

23、OANS BOOKS. LC_No = LOANS. LC_No BORROWERS. Card_No= LOANS. Card_No Title， ，BOOKS. LC_No Name， ， LOANS. LC_No Name， ，BORROWERS. CARD_No LOANS.LC_No,LOANS. Card_No 练习练习2: Title,Name( Date01/01/2003(BOOKS BORROWERS LOANS) Title,Name Date01/01/2003 BOOKS BORROWERS LOANS Title， ，BOOKS. LC_No Name， ， LOANS. LC_No Name， ，BORROWERS. CARD_No LOANS.LC_No,LOANS. Card_No 最后语法树：最后语法树： 关系数据库系统的查询处理关系数据库系统的查询处理 l查询处理步骤查询处理步骤 词法分析词法分析 语法分析语法分析 语义分析语义分析 符号名转换符号名转换 安全性检查安全性检查 完