习题4一、填空题
1. 高速缓存、内存、磁盘存储器
2. 高速查询圆形轨迹、磁道、柱面、扇区
3. 基于成本、执行计划
4. 启发式、代数优化
5. 查询策略、查询策略、查询策略
6. 优、查询优化器
7. 规则优化、代数优化
8. 物理优化
9. 代价估算优化
10. 关系代数表达式的等价
二、单项选择题
A、B、C、D、A、B、C、D、A、B
三、简答题
1. 试述磁盘存储的物理特性，以及其对数据库系统查询功能的影响。
磁盘存储的物理特性：一个磁盘包括n（n≥1）个连接在转轴上的盘片，盘片随着转轴的转动而旋转。盘片（单面或双面）被涂上磁性介质。每个盘片（更准确说是盘面）通过相对应的读写头（磁头）来访问，读写头可以读写当前所在点的磁极。磁盘臂连接读写头，能够快速地在盘片中心和盘片边缘来回移动。盘片可以随着转轴旋转，这样读写头就能够定位到盘片上的任意一点。当磁盘旋转时，磁头若保持在一个位置上，则每个磁头都会在磁盘表面划出一个圆形轨迹，这些圆形轨迹就叫做磁道。不同盘片相同半径的磁道所组成的圆柱称为柱面。磁盘上的每个磁道被等分为若干个弧段，这些弧段便是磁盘的扇区。在访问某特定扇区之前，读写头必须到达此扇区的开始位置。访问某扇区S的时间可以分为3部分：
(1)    寻道时间：磁盘臂装置移动到包含扇区S的柱面上所需要的时间（注意，不是目标扇区
S，而是目标扇区所在的磁道）。平均寻道时间是硬盘性能至关重要的参数之一，它一定程度上体现硬盘读取数据的能力，是影响硬盘内部数据传输率的重要参数，单位为毫秒（ms）。不同品牌、不同型号的产品其平均寻道时间也不一样，但这个时间越低，则产品越好。
(2)    旋转延迟时间：寻道完成后，让把盘片旋转以让读写头位于扇区S的开始位置所需要的时间。
(3)    传输时间：盘片旋转过扇区S所在的角度范围所需的时间。
寻道时间是这三者中最长的一个。因为寻道过程中不仅有机械运动，而且还要客服启动和停止磁盘臂装置的物理惯性。旋转延迟时间在三者中是第二长。
磁盘存储的物理特性数据库系统查询功能的影响：
(1)    相对CPU来说，磁盘访问速度是极慢的。几乎每一个人知道，近几十年来，计算机变得越来越快，越来越便宜。现在一台不算很贵的计算机的CPU 每秒可以执行十亿条指令（100MIPS）。当然，执行不同的指令花费的时间是不同的，这个速度是对计算机上的一个
标准指令集测出的大致速度，可以看成平均速度。磁盘访问速度是影响数据库系统性能的重要方面。虽然，磁盘的旋转速度和磁盘臂的移动速度在最近五年内翻了一-番，而且随着新产品的问世会不断提高，但是，磁盘访问速度并没有和CPU执行速度一起提高。磁盘访问需要机械操作，在磁盘上随机读取一个扇区数据需要的时间（约0.0125秒）比运行一条计算机指令所需的时间要多得多。所以，在优化数据库性能的过程中，优化主存和磁盘之间的访问速度是很重要的一点；另外，数据库系统利用算法所提升的性能收益相对优化磁盘访问所提升的性能收益来说是微不足道的。
(2)    在同一个数据库应用系统中，处理完记录A1后，下一个被处理的记录很可能是A2，如果包含记录A1和A2的扇区之间的距离小，就可以降低延迟。这样，此应用系统的性能会受到数据在磁盘上的物理存储位置的影响。如，如果一个表被存储在同一磁道或同一柱面上，则可以有效地对这个表进行顺序扫描。
2. 试述查询处理的一般过程。
查询处理的一般过程：首先是查询要求由查询解析器处理，将查询转换成内部格式，生成关系代数语法树；然后，查询优化器根据数据库的统计信息和执行策略生成查询计划；下来，
代码生成器根据查询计划生成执行代码；最后运行处理器执行查询代码得到查询结果。其中，查询解析器执行下列操作：
(1)    翻译SQL语句，验证它是合法的语句，即书写正确；
(2)    实现数据字典的查，以验证是否符合表和列的定义；
(3)    在所要求的对象上获取语法分析锁，使得在语句的语法分析过程中不改变这些对象的定义；
(4)    验证为存取所涉及的模式对象所需的权限是否满足；
(5)    对分布的语句来说，把语句的全部或部分路由到包含所涉及数据的远程节点。
3. 试述查询优化的重要性和可能性
数据库查询优化器是RDBMS的一个重要组成部分。查询优化器如果是采用基于成本的优化策略的话，其任务是产生可供选择的执行计划，到最低估算成本的执行计划，来优化一条SQL语句。查询优化器对SQL语句性能表现有很大的影响。查询优化在关系数据库系统中非
常重要。得益于查询优化技术的发展，关系数据库系统和SQL语言获得了市场的认可。关系查询优化是影响RDBMS性能的关键因素。
由于磁盘访问速度相对内存速度要慢很多，所以查询处理的代价通常取决于查询过程对磁盘的访问操作的多少。通常同一查询请求和结果存在多种实现策略，系统执行这些策略时所付出的代价也可能相差较大，甚至有可能相差好几个数量级。可以通过物理优化、规则优化等技术来进行查询优化。
4. 试述查询优化的一般步骤。
①把形如σF1∧F2∧…∧Fn (E)的表达式变换为σF1(σF2(…(σFn(E))…))；把形如ΠA1 , A2 , … , An (ΠB1 , B2 , … , Bm (E))的表达式变换为ΠA1 , A2 , … , An (E)。这样做的目的是将选择或者投影运算串接成单个选择或者单个投影运算，以方便地和有关二元运算进行交换和分配。
②对每个选择，利用规则使它尽可能靠近树的叶端。
③对每个投影，利用规则使它尽可能靠近树的叶端。
④利用笛卡尔乘积与连接的等价变换规则。如果笛卡尔乘积之后还必须按连接条件进行选择操作，就将两者结合成θ连接或F连接原始。
⑤添加必要的投影运算。对每个叶结点添加必要的投影运算，消除对查询无用的属性。
⑥将关系代数语法树进行整形。将由上述步骤1-5得到的语法树的内结点（非根结点和非叶结点）进行分组。此时内接点要么为一元运算结点，要么为二元运算结点。每个二元运算（×、 、∪、－）和它所有直接祖先为一组（这些直接祖先是σ、Π运算）。如果其后代直到叶子全是一元运算，则也将它们并入该组，但当二元运算是笛卡尔乘积，而且其后的选择不能与它结合成为等值连接时除外。把这些一元运算单独分成一组。
⑦由分组结果得到优化语法树。即一个操作序列，其中每一组结点的计算就是这个操作序列中的一步，各步的顺序是任意的，只要保证任何一组不会在它的后代组之前计算即可。
5. 在数据库{USER、ORDER}中，用户需要查询“所有于2009年5月25日下订单的女顾客姓名”。
(1) 试写出该查询的关系代数表达式。
Q1=ΠUserName(σO.DateCreated <’2009-5-25’ AND U.Sex =’女’AND U.UserID =O.UserID (USER×ORDER))
(2) 画出查询表达式的语法树。
(3) 应用启发式规则，对语法树优化，并画出优化后的语法树。