数据库系统原理与实践习题答案第10章.pdf
数据库系统原理与实践习题答案第10章请勿盗版 尊重作者 1 1简述查询优化在关系数据库系统中的重要性和可能性。简述查询优化在关系数据库系统中的重要性和可能性。 答：查询优化在关系数据库系统中有着非常重要的地位。关系数据库系统和非过程化的 SQL之所以能够取得巨大的成功，关键是得益于查询优化技术的发展。关系查询优化是影响关系数据库管理系统性能的关键因素。 优化对关系系统来说既是机遇又是挑战。所谓挑战，是指关系系统为了达到用户可接受的性能必须进行查询优化。由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性。这就为关系系统在性能上接近甚至超过非关系系统提供了机遇。2 2简述关系数据库管理系统查询优化的一般步骤。简述关系数据库管理系统查询优化的一般步骤。答：关系数据库管理系统查询优化一般包含代数优化和物理优化。（1）代数优化：是指SQL 语句经过查询分析、查询检查后变换为查询树，然后基于关系代数表达式等价变换规则对查询树进行优化。（2）物理优化：代数优化改变查询语句中操作的次序和组合，但不涉及底层的存取路径。实际上，对于每一种操作有多种执行这个操作的算法，有多条存取路径，对于一个查询语句有许多存取方案，它们的执行效率不同，其结果会相差很大，因此，仅仅进行代数优化是不够的。物理优化就是要选择高效合理的操作算法或存取路径，求得优化的查询计划，达到查询优化的目标。选择的方法可以是：基于规则的启发式优化、基于代价估算的优化和两者结合的优化方法。3 3假设关系假设关系 R(A,B)R(A,B)和和 S(B,C,D)S(B,C,D)的情况如下：的情况如下：R R 有有 2020 000000 个元组，个元组，S S 有有 1 1 200200 个元组，个元组，一个块能装下一个块能装下 4040 个个 R R 元组，能装下元组，能装下 3030 个个 S S 元组，能装下元组，能装下 2020 个个 R R S S 运算后的元组。估算下列操作需要多少次磁盘块读写。运算后的元组。估算下列操作需要多少次磁盘块读写。 数据库系统原理与实践习题答案第10章请勿盗版 尊重作者 （1 1）R R 上没有索引，上没有索引，SELECTSELECT * * FROMFROM R R。 （2 2）R R 中中 A A 为主码，为主码，A A 上有上有 3 3 层层 R+R+树索引，树索引，SELECTSELECT * * FROMFROM R R WHEREWHERE A=10A=10。 （3 3）嵌套循环）嵌套循环 R R S S。 （4 4）排序合并连接）排序合并连接 R R S S，区分，区分 R R 与与 S S 在属性在属性 B B 上已经有序和无序的两种情况。上已经有序和无序的两种情况。 答：（1）由于R上没有索引，且查询全部数据，需要使用全表扫描：20 000/40=500 次。（2）由于R上有主码索引，使用索引：3（查找索引）+1（取元组） =4次。（3）R的磁盘块数：20 000/40=500 块，S的磁盘块数：1200/30= 40 块。假设连接操作可用内存总块数为K，连接的选择率为Frs。选取S作为外表，使用嵌套循环，读取磁盘次数为：40+500*40/(K-1)+(Frs*40*500)/20（4）R的磁盘块数：20 000/40=500 块，S的磁盘块数：1200/30= 40 块。假设连接操作可用内存总块数为K，连接的选择率为Frs。（a）如果R 与 S 在属性 B 上已经有序，则读写磁盘的次数为：40+500+(Frs*40*500)/20（b）如果R 与 S 在属性 B 上已经无序，则还需加上排序过程中读写磁盘的代价 R排序的代价为：（2*500）+2*500*log2500 S排序的代表为：（2*40）+2*40*log240总读写磁盘次数为：（2*500）+2*500*log2500+（2*40）+2*40*log240+40+500+(Frs*40*500)/204 4查询网上商城（查询网上商城（bookstorebookstore）数据库中已完成订单中包含的理工类图书的名）数据库中已完成订单中包含的理工类图书的名称。称。 SELECTSELECT DISTINCTDISTINCT titletitle FROMFROM book,orderInfo,orderBookbook,orderInfo,orderBook WHEREWHERE book.bookID=orderBook.bookIDbook.bookID=orderBook.bookID ANDAND orderInfo.orderID=orderBook.orderIDorderInfo.orderID=orderBook.orderIDANDAND orderInfo.orderState=orderInfo.orderState=已完成已完成 ANDAND book.categoryID=1book.categoryID=1 数据库系统原理与实践习题答案第10章请勿盗版 尊重作者 试画出用关系代数表示的语法树，并用关系代数表达式优化算法对原始的语法试画出用关系代数表示的语法树，并用关系代数表达式优化算法对原始的语法树进行优树进行优化处理，画出优化后的语法树。化处理，画出优化后的语法树。答：用关系代数表示的语法树优化后的语法树：
