数据库技术作业和答案（包括习题答案） - 图文

数据库系统原理与设计 3. 查询优化：查询优化（query optimization）

7 首先做了选择运算，然后是投影运算，接下就是能从这许多策略中找出最有效的查询执行计划的一种处理过程。

4． 查询处理代价：查询处理代价是指查询处理过程中每个操作消耗的时间和空间代价，查询处理代价可以通过该查询对各种资源的使用情况进行测量，这些资源包括磁盘存取、执行一个查询所用CPU时间、在分布式数据库系统或并行数据库系统中的通信开销。

5. 查询树：又称为语法分析树（syntax tree），它建立在扩展的关系代数的基础上的。 6. 流水线：通过减少查询执行中产生的临时文件数，可以提高查询执行的效率。减少临时文件数是通过将多个关系运算组合成一个运算的流水线来实现的，即将多个运算的结果传送到下一个运算。这样的运算叫做流水线运算。

7. 等价规则：两个关系表达式是等价的是指在任一种有效数据库实例中它们都会产生相同的元组集。等价规则指出两种不同形式的表达式是等价的。

四. 简述题

1. 查询处理涉及的活动包括：接受用户提交的用高层数据库语言（例如：SQL语句）表示的查询语句，将高层数据库语言查询语句翻译为能在文件系统的物理层上使用的表达式，为优化查询而进行各种转换，以及查询的实际执行。关系查询处理可以分4个步骤，包括：

（1）查询分析和检查； （2）查询翻译； （3）查询优化； （4）查询执行。

2. 答：查询优化的一般准则： （l）选择运算应尽可能先做。

（2）在执行连接前对关系适当地预处理。 （3）把投影运算和选择运算同时进行。 （4）投影同双目运算结合。

（5）选择同某些笛卡尔积结合起来构成一个连接运算。

（6）找出公共子表达式。 3. 答：等价关系代数表达式： Пbranch-name

(σT.assets

>

S.assets((T)

(Пassets(σbranch-city =”Brooklyn” (S)))))

来是连接运算，之后是选择运算，最后是投影运算，高效的原因在于它最大化的减少了中间结果的大小，减少了比较的次数。

五．设计题 初始关系表达式如下： Пcname(σstudent.sdept=”CS”

^

sc.cno=course.cno^

student.sno=sc.sno (course

(sc

student)))，

对应的查询树如图：

Пcname σstudent.sdept=”CS” ^ sc.cno=course.cno^ student.sno=sc.sno course sc student 根据选择运算先执行的原则，首先执行一步选择运算，表达式如下：

Пcname(σsc.cno=course.cno^ student.sno=sc.sno

(course

( sc(σstudent.sdept=”CS” (student)))))，

查询树如图：

Пcname σsc.cno=course.cno^ student.sno=sc.sno course sc σstudent.sdept=”CS” student 依据同样的原则，再执行一步选择运算，表达式如下：

8 Пcname(σsc.cno=course.cno (σstudent.sno=sc.sno (sc数据库系统原理与设计 (course

系必须满足一定的要求，即满足不同的范式。目前关系数据库最重要的范式有五种： 1NF、2NF、(σstudent.sdept=”CS” (student))))))，

查询树如图

Пcname σsc.cno=course.cno course σstudent.sno=sc.sno sc σstudent.sdept=”CS” student 这就是要的最终的查询树。

第6章

一、选择题

1. A 2. B 3. D 4. C

5. B 6.A 7.B 8.A 9.C 10. B

二、填空题 1. 多个值 2. 完全函数

3. 函数依赖，无损连接性

4. 模式分解，将复杂的关系模式分解成若干比较小的关系模式消除冗余

5. 范式，范式 6. 函数依赖 7. 3NF 8. BCNF 9.对称性和传递性 10. 4NF

三、思考题 1. 答：

（1）构造数据库必须遵循一定的规则。在关系数据库中，这种规则就是范式。范式是符合某一种级别的关系模式的集合。关系数据库中的关

3NF、BCNF， 4NF，它们之间的关系是4NF?BCNF? 3NF?2NF?1NF。 满足最低要求的范式是第一范式（1NF）。在第一范式的基础

上进一步满足更多要求的称为第二范式（2NF），其余范式以次类推。一般说来，数据库只需满足第三范式（3NF）就可以了。

（2）没有经过规范化的关系模式通常容易产生诸如数据冗余度高、插入异常、删除异常、更新困难等毛病，这样的关系模式显然是要避免的，

由此而产生了一整套规范化理论。通过对原有的

关系模式进行规范化，使之达到一定级别的范式，便可在一定程度上消除上述毛病。在实际应用中，

并不是规范化程度越高越好，要视实际情况而定。

2. 答：

（1）关系模式规范化一般应遵循的原则如下：

① 将关系模式进行无损连接分解，在关系模式分解的过程中，数据不能丢失或增加，要保持数据的完整性；

② 合理地选择规范化程度。在规范化时，既要考虑到低级范式造成的冗余度高、数据不一致性，又要考虑到高级范式带来的查询效率低的问题；

③ 要考虑正确性和可实现原则，即要保证规范化过程是正确的，并且通过规范化能达到要求。

（2）各范式之间的关系为：4NF?BCNF? 3NF?2NF?1NF，1NF消去非主属性对码的部分函数依赖便得到2NF，2NF消去非主属性对码的传递函数依赖便得到3NF ，3NF消去主属性对码的部分和传递函数依赖便得到BCNF，BCNF消去非平凡且非函数依赖的多值依赖得到4NF。

3. 答：函数依赖：设R（U）是属性集U上的关系模式。?，?是U的子集。若对于R（U）的任意一个可能的关系r，r中不存在两个元组在?上的属性值相等，而在?上的属性值不等，则称?函数决定?或?函数依赖于?，记为

?→?。

函数依赖是一个在语义范畴上的概念，即只

数据库系统原理与设计 9 能根据语义来确定一个函数依赖。例如：员工姓名→性别，这个函数依赖只有在该部门没有同姓名的员工的前提下才成立，然而如果在设计的时候对这种事实作强制规定，如不允许同姓名的人存在，那么该函数依赖是存在的，现实生活中函数依赖是普遍存在的。

4. 答：该关系模式属于BCNF，因为该关系模式存在以下函数依赖：

学号→姓名，学号→年龄，学号→所在系，学号→出生日期

除此之外不存在其他函数依赖，所以该关系模式首先属于2NF（每一个非主属性完全函数依赖于码即学号），又因为所有的非主属性对码非传递依赖，故该关系模式又是属于3NF的，注意到对任意函数依赖，其左部均含有码，因此该关系模式又是属于BCNF的。

5. 答：

该关系模式存在以下函数依赖：

Sno→Sname，Sdept→MN，Sno→Sdept，（Sno，Course）→Grade

显然关系模式的码为Sno，Course。 6. 原关系模式是属于1NF的，非主属性Grade完全按函数依赖于码，而其他非主属性对码的函数依赖均为部分函数依赖，所以不属于2NF。可将该关系模式分解为2NF如下：

Student1（Sno，Sname，Sdept，MN） Student2（Sno，Course，Grade）

7. 6中的关系模式Student1中存在Sno→Sdept ，Sdept→MN，即非主属性MN传递依赖于码Sno，所以Student1可以进一步分解为3NF如下：

Student11（Sno，Sname，Sdept） Student12（Sdept，MN）

而Student2中不存在非主属性对码的传递依赖，故已经属于3NF。

最终原关系模式分解为3NF得到： Student11（Sno，Sname，Sdept） Student12（Sdept，MN） Student2（Sno，Course，Grade）

8. 答：3NF是建立在2NF基础之上的，如

果满足2NF的关系模式中不存在非主属性对传递依赖于码，则该关系模式属于3NF.

BCNF是3NF的改进形式，它建立在1NF的基础上。如果关系模式R属于1NF，只要其每一个决定因素均包含码，则R属于BCNF。

一个关系模式属于BCNF，则它一定属于3NF，BCNF是3NF的一个特例，反之不然。

9. 答：

（1）多值依赖定义：设R(U)是一个属性集U上的一个关系模式，?、?和?分别为U的子集，且有?＝U－?－?，多值依赖 ?→→?（读作 ?多值决定?）成立当且仅当对R的任意一个关系r，r在（?，?）上的每个值对应一组?的值，这组值仅仅由?值决定而与?值无关。

多值依赖（MVD）是两个属性或属性集合之间相互独立的断言。它是广义的函数依赖（或者说函数依赖是多值依赖的一种特殊情况）。

（2）4NF定义：关系模式R（U）?1NF，若对于R的任意非平凡多值依赖?→→?（????）

，?都含有码，则称R（U）?4NF。 4NF就是限制关系模式属性之间不允许有非平凡的且非函数依赖的多值依赖。

10. 答：

（1）Armstrong公理系统：设R为关系模式，其中U为属性集，F是U上的一组函数依赖。对R有三个推理规则：

自反律：若????U，则?→?为F所蕴含；

增广律：若?→?为F所蕴含，且??U，则??→??为F所蕴含；

传递律：若?→?和?→?为F所蕴含，则

?→?为F所蕴含。

（2）Armstrong公理系统的有效性是指：y由F出发根据Armstrong公理系统推导出来的每一个函数依赖一定在F?中。

Armstrong公理系统的完备性是指：F?中的每一个函数依赖必定可以有F根据Armstrong公理系统推导出来。

11. 答：

10 由算法：

（1）令X (0)=BD；

数据库系统原理与设计 E→A， E→B得E→AB（合并律）。

故E→AB∈F+，由定理知?具有无损连接性。

14. R1的码为E，显然R1属于2NF，但R1中存在非主属性对码的传递依赖，故R1不属于3NF。

R2的码为CE，由于函数依赖C →G 中G对码部分依赖，故R2不属于2NF，即R2属于1NF。

（2）计算X (1)，逐一扫描F中的各个函数依赖，找到左部为B、D或BD的函数依赖，得到D→EG，故X (1)=BD∪EG= BDEG。

（3）计算X (2)，逐一扫描F中的各个函数依赖，找到左部为BDEG或BDEG子集的函数依赖，得到BE→C，故X (2)=BDEG∪C= BCDEG。

（4）计算X (3)，逐一扫描F中的各个函数依赖，找到左部为BCDEG或BCDEG子集的函数依赖，得到C →A，CG→BD，ACD→B，CE→AG，故X (3)=BCDEG∪ADBG=U，算法终止。

故最终求得(BD)?F=U。 12. 答：

根据算法：由于F中的任何一个函数依赖的右部已经只含有一个属性。则：

① 设A→B是冗余的，将其从F中去掉，看能否根据Armstrong公理系统的推理规则导出。

显然无法导出。故A→B不能删除。 ② 设B→A是冗余的，将其从F中去掉，看能否根据Armstrong公理系统的推理规则导出。

因为B →C， C→A则根据传递律有B→A成立，可见B→A确是冗余的。将其从F中去掉，得到F1={ A→B， B →C，A→C， C→A }。

③ 显然B →C不是冗余的。

④ 设A→C是冗余的，同样容易得到其也是冗余的，故也应去掉。得到F2={ A→B， B →C，C→A }。

由于F2中已不存在冗余的函数依赖，因此F2就是要求的Fmin。

13. 答：

（1）可以求解得R的码为CE，因为

CE）+=U，并且在CE中不存在一个真子集能决

定R的全体属性U，故R为码。

由于?中只含有两个关系模式，故可使用定理6-6判断?的无损连接性：

ABE∩CDEG=E，ABE—CDEG=AB，CDEG—ABE=CDG

因为E→A，A→B，故E→B（传递律），由

15. 答：

（1）从函数依赖集F中可以看出，E和C两个属性不依赖于其他属性，所以码中必然至少包含E和C，求EC属性的闭包，若包含所有的属性，那么，EC即为码。

令X (0)=EC ，因有E→D，故X (1)=ECD，又D→B，则X (2)=ECDB，由DC→E，得

X (3)=ECDBE，由此EC的闭包包含所有属性，

故EC为码。

（2）判断?是否为无损连接分解，由算法，首先构造矩阵如表所示。

表A-1

A B C D E R1（AB） a1 a2 b13 b14 b15 R2（AE） a1 b22 b23 b24 a5 R3（EC） b31 b32 a3 b34 a5 R4(DBC) b41 a2 a3 a4 b45 R5(AC) a1 b52 a3 b54 b55 依次检查F中的每一个函数依赖，无法修改此表，所以?不是无损连接的分解。

（3）因为F={A→D，E→D，D→B，BC→D ，DC→A }已经是最小的函数依赖集，所以根据算法，设?={ AD，ED，DB，BCD，DCA }

判断?是否为无损连接分解，同样构造二维矩阵，如表A-2所示。

表A-2

A B C D E R1（AD） a1 b12 b13 a4 b15 R2（ED） b21 b22 b23 a4 a5 R3（DB） b31 a2 b33 a4 b35 R4(DBC) b41 a2 a3 a4 b45 R5(DAC) a1 b52 a3 a4 b55 （