下载文档原格式
第四章 关系系统及其查询优化 一、选择题： 1、如果一个系统定义为关系系统，则它必须 。 A．支持关系数据库 B．支持选择、投影和连接运算 C．A和B均成立 D．A、B都不需要 2、设E是关系代数表达式，F1、F2是选取条件表达式，则有 。
A．)())((2121EEFFFF B．)())((2121EEFFFF
C．)())((121EEFFF D．)())((221EEFFF 二、填空题： 1、关系系统的查询优化既是关系数据库管理系统实现的关键技术，又是关系系统的优点。因为，用户只要提出 ，不必指出 。 2、在关系代数运算中， 、 运算最费时间和空间。究竟应采用什么样的策略才能节省时间、空间，这就是优化的准则。
三、问答题： 1、为什么要对关系代数表达式进行优化？ 2、查询优化的总目标是什么？ 第四章 答案 一、选择题： 1、C． 2、B．
二、填空题： 1、干什么、怎么干 2、笛卡儿积、连接
三、问答题： 1、为什么要对关系代数表达式进行优化？ 答：关系代数表达式由关系代数操作组合而成。操作中，笛卡儿积和连接操作最费时。如果直接按表达式书写的顺序执行，必将花费很多时间，并生成大量中间结果，效率较低。如果在执行前，由DBMS的查询子系统先对关系代数表达式进行优化，尽可能先执行选择和投影操作，则进行笛卡儿积或连接时可以减少中间结果，并节省时间。优化工作是由DBMS做的，用户在写关系代数表达式时不必关系优化一事，仍以简练的形式书写。 2、查询优化的总目标是什么？ 答：查询优化的总目标是选取有效的存取路径，求得给定关系代数表达式的值。
第4章关系系统及其优化1.试述查询优化在关系数据库系统中的重要性和可能性。
答：查询优化在关系数据库系统中有着非常重要的地位。
关系数据库系统和非过程化的SQL语言能够取得巨大的成功，关键是得益于查询优化技术的发展。
关系查询优化是影响RDBMS性能的关键因素。
优化对关系系统来说既是挑战又是机遇。
所谓挑战是指关系系统为了达到用户可接受的性能必须进行查询优化。
由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性。
这就为关系系统在性能上接近甚至超过非关系系统提供了机遇。
2.对学生-课程数据库有如下的查询：查询信息系学生选修的所有课程名称:SELECT Cname FROM St,Course,SCWHERE St.Sno=SC.Sno AND o=o AND St.Sdept=’IS’试画出用关系代数表示的语法树，并用关系代数表达式优化算法对原始的语法树进行优化处理，画出优化后的标准语法树。
答：关系代数表达式如下：πcname(бSt.sdept=’IS’(бst.sno=sc.Sno(бo=o(ST×SC×COURSE))) 用关系代数表示的语法树如下左图：用关系代数表达式优化算法对原关系代数表达式进行优化，优化后的关系代数表达式如下：πcname(бo=o((бSt.sno=sc.sno(πsno(бSt.sdept=’IS’(ST))×πsno,cno(SC))) ×πcno,cname(Course))优化处理后的标准语法树如上右图。
3.简述查询优化的一般准则。
答:1)选择运算应尽可能先做。
2）在执行连接前对关系适当地预处理。
3）把投影运算和选择运算同时进行。
4）把投影同其前或其后的双目运算结合起来。
5）把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算。
6）找出公共子表达式。
4.试述查询优化的一般步骤。
1. SELECT*FROM Student结果：2. SELECT Sname 姓名,Sage 年龄FROM StudentWHERE Sdept='计算机系'结果：3. SELECT Sno 学号,Cno 课程号,Grade 成绩FROM SCWHERE Grade BETWEEN 70 AND 804. SELECT Sname 姓名,Sage 年龄FROM StudentWHERE Sdept='计算机系'AND Sage>=18 AND Sage<=20 AND Ssex='男'5. SELECT MAX(Grade)最高分数FROM SCWHERE Cno='c01'6. SELECT MAX(Sage)最大年龄,MIN(Sage)最小年龄FROM StudentWHERE Sdept='计算机系'7. SELECT Sdept 系名,COUNT(*)学生人数FROM StudentGROUP BY Sdept8. SELECT Cname 课程名,COUNT(*)选课门数,MAX(Grade)最高分FROM Course,SCGROUP BY Cname9. SELECT Sno 学号,COUNT(*)选课门数,SUM(Grade)总成绩FROM SCGROUP BY SnoORDER BY'选课门数'ASC10. SELECT Sno 学号,SUM(Grade)总成绩FROM SCGROUP BY SnoHAVING SUM(Grade)>20010.CREAT TABLE BOOK（Snobook nchar(6) PRIMARY KEY,Snamebook nvarchar(30) NBOT NULL,Writer char(10) NOT NULL,Time smalldatetime,Price numeric(3,1))CREAT TABLE BOOKSHOP(Snoshop nchar(6) PRIMARY KEY,Snameshop nvarchar(30) NOT NULL,Tel char（8）CHECK(Tel =0 AND Tel <=9),Place nchar(40),Snoemail char(6))CREAT TABLE BOOKSELL（Snobook nchar(6) NOT NULL,Snoshop nchar(6) NOT NULL,Selltime smalltime NOT NULL,Snosell tinyint,PRIMARY KEY (Snobook, Snoshop, Selltime),FOREIGN KEY (Snobook) REFERENCES BOOK(Snobook), FOREIGN KEY (Snoshop) REFERENCES BOOK(BOOKSHOP) )11.ALTER TABLE BOOKADD Nomber intADD CONSTRAINT DF-NomberCHECK (Nomber>1000)12.ALTER TABLE BOOKSHOPDROP COLUMN Tel13.ALTER TABLE BOOKSELLALTER COLUMN Snosell int。
第4章 关系数据库设计理论 习 题 一、选择题 1、C 2、B 3、C 4、C 5、A 6、B 7、A 8、B 9、D 10、B
二、填空题 1、数据依赖主要包括_函数_依赖、_多值_依赖和连接依赖。 2、一个不好的关系模式会存在_插入异常_、_删除异常_和__修改复杂_等弊端。 3、设X→Y为R上的一个函数依赖，若_对任意X的真子集X’,均无X’→Y 存在__，则称Y完全函数依赖于X。 4、设关系模式R上有函数依赖X→Y和Y→Z成立，若_Y不包含于X_且_Y→X不成立_，则称Z传递函数依赖于X。 5、设关系模式R的属性集为U，K为U的子集，若_K→U为完全函数依赖_，则称K为R的候选键。 6、包含R中全部属性的候选键称_主属性_。不在任何候选键中的属性称__非主属性_。 7、Armstrong公理系统是_有效__的和_完备__的。 8、第三范式是基于_函数_依赖的范式，第四范式是基于_多值_依赖的范式。 9、关系数据库中的关系模式至少应属于_第一_范式。 10、规范化过程，是通过投影分解，把_一个范式级别较低的_的关系模式“分解”为_若干个范式级别较高__的关系模式。 数据库原理及应用 112 三、简答题 1、解释下列术语的含义：函数依赖、平凡函数依赖、非平凡函数依赖、部分函数依赖、完全函数依赖、传递函数依赖、范式、无损连接性、依赖保持性。 解： 函数依赖：设关系模式R（U，F），U是属性全集，F是U上的函数依赖集，X和Y 是U的子集，如果对于R（U）的任意一个可能的关系r，对于X的每一个具体值，Y都有唯一的具体的值与之对应，则称X函数决定Y，或Y函数依赖于X，记X→Y。我们称X为决定因素，Y为依赖因素。当Y不函数依赖于X时，记作：XY。当X→Y且Y→X时，则记作：XY。 平凡函数依赖：当属性集Y是属性集X的子集时，则必然存在着函数依赖X→Y，这种类型的函数依赖称为平凡的函数依赖。 非平凡函数依赖：如果Y不是X子集，则称X→Y为非平凡的函数依赖。 完全函数依赖与部分函数依赖：设有关系模式R（U），U是属性全集，X和Y是U的子集，X→Y，并且对于X的任何一个真子集X'，都有X'Y，则称Y对X完全函数依赖（Full
Functional Dependency）,记作XfY。如果对X的某个真子集X'，有X'→Y，则称Y
对X部分函数依赖（Partial Functional Dependency）,记作XpY。 传递函数依赖：设有关系模式R（U），U是属性全集，X，Y，Z是U的子集，若X→Y（YX），但YX，又Y→Z，则称Z对X传递函数依赖（Transitive Functional Dependency）,
记作：XtZ。 范式：在关系数据库的规范化过程中，为不同程度的规范化要求设立的不同的标准或准则称为范式（Normal Form）。满足最低要求的叫第一范式,简称1NF。在第一范式中满足进一步要求的为第二范式(2NF),其余以此类推。R为第几范式就可以写成R∈xNF（x表示某范式名）。 当把某范式看成是满足该范式的所有关系模式的集合时，各个范式之间的集合关系可以表示为：5NF4NFBCNF3NF2NF1NF。 一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这种过程就叫规范化。 无损连接性：设R（X，Y，Z），X、Y、Z为不相交的属性集合，如果有X→Y、X→Z，则有R（X，Y，Z）=R[X，Y]∞R[X，Z]，其中R[X，Y]表示关系R在属性（X，Y）上的投影，即R等于两个分别含决定因素X的投影关系（分别是R[X，Y]与R[X，Z]）在X上的自然连接，这样便保证了关系R分解后不会丢失原有的信息，这称作关系分解的无损连接性。 依赖保持性：设有关系模式R（U，F），Z⊆U，则Z所涉及到的F中所有函数依赖为F 在Z上的投影，记为∏Z（F），有∏Z（F）=｛X→Y｜(X→Y)∈F＋且XY⊆Z｝为函数依赖集F在Z上的投影。 设R（U，F）的一个分解ρ＝｛R1，R2，…，Rk｝，如果F等价于∏R1（F）∪∏R2（F）∪…∪∏Rk（F），则称分解ρ具有函数依赖保持性。 检验一个分解是否具有依赖保持性，实际上是检验∏R1（F）∪∏R2（F）∪…∪∏Rk（F）是否覆盖F。
2、给出2NF、3NF、BCNF的形式化定义，并说明它们之间的区别和联系。 解： 1）2NF 如果关系模式R∈1NF，R（U，F）中的所有非主属性都完全函数依赖于任意一个候选关键字，则称关系R 是属于第二范式（Second Normal Form），简称2NF，记作R∈2NF。 2）3NF 如果关系模式R∈2NF，R（U，F）中所有非主属性对任何候选关键字都不存在传递函数依赖，则称R是属于第三范式（Third Normal Form），简称3NF，记作R∈3NF。 3）BCNF 如果关系模式R∈1NF，且所有的函数依赖X→Y（Y不包含于X，即YX），决定因素X都包含了R的一个候选码，则称R属于BC范式（Boyce-Codd Normal Form）,记作R∈BCNF。
4）区别和联系 （1）BCNF3NF2NF （2）BCNF、3NF与2NF均是针对函数依赖而定义划分的。2NF 、3NF和BCNF是在函数依赖的条件下对模式分解所能达到的分离程度的测度。一个模式中的关系模式如果都属于BCNF，那么在函数依赖范畴内，它已实现了彻底的分离，已消除了插入和删除异常。
3、什么叫关系模式分解？为什么要做关系模式分解？模式分解要遵循什么准则？ 解： 1）关系模式分解：一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这种过程就叫关系模式分解又叫关系模式规范化。 2）做关系模式分解是因为：不好的关系往往内容“包罗万象”，内容太杂了。实现了信息的某种程度的分离，必须把“包罗万象”的关系模式，分解为若干内容单一，结合紧密的关系模式，才能使关系表现出更好的操作性能，避免出现各种异常问题的产生。 3）模式分解要按需遵循模式分解的无损连接性或模式分解的依赖保持性。
4、试证明全码的关系必是3NF，也必是BCNF。 证明： 数据库原理及应用 114 1） 设有关系R（U，F），因为R含全码，所以U中的属性均为主属性，即R不含任何非主属性。根据3NF的定义，R中没有非主属性对码有传递函数依赖存在。根据定义可下结论：R∈3NF。证毕。 2） 采用反证法，假设RBCNF。则按照定义R中必含有X→Y（YX），其中XU，Y包含于U，X不含码。在X→Y的两边同时并上U-Y，得：X(U-Y)→U。显然X(U-Y)U 或X(U-Y) U。这与题中已知条件关系R为全码相矛盾。假设RBCNF不成立，本题得证。
5、要建立关于系、学生、班级、研究会等信息的一个关系数据库。规定：一个系有若干专业、每个专业每年只招一个班，每个班有若干学生，一个系的学生住在同一个宿舍区。每个学生可参加若干研究会，每个研究会有若干学生。学生参加某研究会，有一个入会年份。 描述学生的属性有：学号、姓名、出生年月、系名、班号、宿舍区。 描述班级的属性有：班号、专业名、系名、人数、入校年份。 描述系的属性有：系号、系名、系办公室地点、人数。 描述研究会的属性有：研究会名、成立年份、地点、人数。 试给出上述数据库的关系模式；写出每个关系的最小依赖集（即基本的函数依赖集，不是导出的函数依赖）；指出是否存在传递函数依赖；对于函数依赖左部是多属性的情况，讨论其函数依赖是完全函数依赖还是部分函数依赖，指出各关系的候选键、外部键。 解： 1）关系模式为： 系（{系号，系名，系办公室地点，宿舍区，人数}，{系号→系名，系号→系办公室地点，系名→系办公室地点，系号→宿舍区}） 班级（{班号，专业名，系号，人数，入校年份}，{班号→专业名，班号→系号，班号→入校年份，（专业名，入校年份）→班号}） 学生（{学号，姓名，出生年月，系号，班号}，{学号→姓名，学号→出生年月，学号→系号，学号→班号，学号→宿舍区，班号→系号， }） 入会（{学号，研究会名，入会年份}，{（学号，研究会名）→入会年份}） 研究会（{研究会名，成立年份，地点，人数}，{研究会名→成立年份，研究会名→地点}） 说明：人数可以不作为属性，能统计得到；宿舍区应作为系的属性；学生关系中的系号可由班号属性通过班级关系得到，冗余可去。
2）传递函数依赖有：系号→系办公室地点；学号→宿舍区； 3）以上关系模式中没有部分函数依赖。 系关系中候选键为：系号； 外部键为：无 班级关系中候选键为：班号、（专业名，入校年份）； 外部键为：系号 学生关系中候选键为：学号； 外部键为：班号 入会关系中候选键为：（学号，研究会名） 外部键为：学号 或 研究会名 研究会关系中候选键为：研究会名； 外部键为：无
6、设有关系模式R（A，B，C，D，E，F），函数依赖集F={（A，B）→E，（A，C）→F，（A，D）→B，B→C，C→D}，求出R的所有候选关键字。 解： R的候选关键字有：（A、C）、（A、B）、（A、D）
7、设有关系模式R（X，Y，Z），函数依赖集为F={（X，Y）→Z}。请确定SC
的范式等级，并证明。 解： R的候选关键字有：（X，Y） R达到BCNF范式等级，按BCNF定义判定即可，具体略。
8、设有关系模式R（A，B，C，D，E，F），函数依赖集F={A→（B，C），（B，C）→A，（B，C，D）→（E，F），E→C}。试问：关系模式R是否为BCNF范式，并证明结论。 解： R达不到BCNF范式。R的候选关键字有：（A，D）、（B，C，D）、（B，E，D） 按BCNF定义判定即可，具体略。
9、设有关系模式R（E，F，G，H），函数依赖F={E→G，G→E，F→（E，G），H→（E，G），（F，H）→E} （1）求出R的所有候选关键字； （2）根据函数依赖关系，确定关系模式R属于第几范式； （3）将R分解为3NF，并保持无损连接性和函数依赖保持性； （4）求出F的最小函数依赖集。 解： （1）R的候选关键字为：（F，H） （2）R为：1NF （3）分解为： （{E，G}，{E→G，G→E }）、（{F，E}，{F→E}）、（{H，G}，{H→G}）、（{F，H}，{}） （4）最小函数依赖集为：{ E→G，G→E，F→G，H→G } 按定理4.3,求最小函数依赖集步骤： F={E→G，G→E，F→（E，G），H→（E，G），（F，H）→E} ={E→G，G→E，F→G，H→E，H→G，（F，H）→E}
