数据库系统原理与实践习题答案第10章.docx

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

优化后的语法树：