数据库系统工程师复习资料

1、 数据库系统工程师复习资料 答案(1)A，(4)D，(5)D，(6)D，(7)D，(9)D，（10）C，（13）B，（17）B（18）A（20）B（21）A（25）D（26）D（27）A（30）C（31）A（33）C（36）C（37）D（38）B（39）C（41）D（43）D（44）C（46）C（47）B（48）D（51）C（52）C（62）B（63）C（64）A（66）C（67）A（68）B（69）D（70）A（71）A（72）C（73）B（74）D（75）B58 C 59 A 60 D 61 B 63 D 64 C 66 A 67 B 68 C 69 A 70 D 71 D 72 D 73

2、 B 74 C 75 A1(1)primary key(col1,col2) (2)primary key(col1) primary key(col2) (3)constraint c1 primary key(col1,col2)两个属性组合为码，标准SQL中一般采用第一种形式。constraint 在ORACLE中用得多，表示某种约束，在这里是主键约束，在标准SQL中一般不用。2(1)references 表名(列名) (2)references 表名考试时该用那一种. *用前一种，更明确指出了要引用的列。3一般的格式是： creat view 要创建的视图名称as select 查询子

3、句with check option其中表示可选。with check option表示在执行UPDATE、INSERTER、DELETE等操作时保证更新、插入或删除的行满足视图定义中查询子句中的条件表达式。4各本书上不同，是因为它们基于不同的数据库软件而编写的。标准SQL似乎没有严格规定数据类型。各数据库软件的数据类型一般都很类似，比如int 只是integer前三个字母而已，一般情况下，阅卷老师都认识这些符号，所以不必过于担心。5求关键路径：以考点分析与真题详解书P117例题4为例首先应该搞清楚概念。在AOE网络中，顶点代表事件（实际上就是该顶点的所有入边所表示的活动均已完成），弧代表活动

4、。从源点到某顶点的最长路径长度为该顶点所代表事件的最早发生时间，该题中，从源点V1到顶点V6只有一条路径V1-V3-V6，于是事件V6的最早开始时间为2+3=5。在不推迟整个工程完成的前提下，一个事件允许的最迟发生时间称为该事件的最迟发生时间，p27提供的求它的递推式的要义有两点：一是汇点的最迟发生时间等于其最早发生时间，亦即整个工程关键路径的长度；二是某点的最迟发生时间等于关键路径长度减去从该点出发至汇点的最长路径长度。比如，从V2到V7有两条路径：V2-V5-V7、V2-V4-V5-V7,路径长度最长的是前者，长度为4+3=7，又易求得关键路径长度为10，于是事件V2的最迟发生时间为10-

5、7=3。初学者在这个地方最易疑惑。某活动的最早开始时间等于该活动对应的弧的起点的最早开始时间。该题中，活动a6的最早开始时间等于事件V3的最早开始时间，亦即2。某活动的最迟发生时间等于该活动对应的弧的终点的最迟发生时间减去该活动持续的时间。该题中，活动a6的终点为V4，易求得其最迟发生时间为10-3-1=6，继而求得a6的最迟发生时间为6-1=5。用某活动的最迟开始时间减去该活动的最早发生时间便得到该活动的松弛时间。该题中，a6的松弛时间即为5-2=3。6。段管理的主要优点是：可以实现动态链接。所谓段的动态链接，是指在程序运行一开始，只将作业的主程序段调入内存，其他各段是在作业运行过程中逐步被

6、调入内存的。7在一个多道程序设计系统中,不采用移动技术的可变分区方式管理主存.设用户空间为100K,主存空间采用最先适应分配算法,采用计算时间短的作业优先算法管理作业,今有如下所示的作业序列.作业名,进入输入井时间,需计算时间,主存需求量JOB1 8.0小时 1小时 20KJOB2 8.2小时 0.6小时 60KJOB3 8.4小时 0.5小时 25KJOB4 8.6小时 0.4小时 20K若忽略系统开销,则JOB2的开始执行时间为(),JOB3的完成时间为(),JOB4的周转时间为().请问:什么是最先适应分配算法,还有其他什么算法吗?最好能说得详细些.此题怎么解?所谓最先适应分配算法,就是

7、指使用第一次找到的那块合适的内存区域分给作业。该题并不是考最先适应分配算法，而是考察短作业优先调度算法。（1），所谓短作业优先，是说在各作业同时到达或都在等待时，优先选择执行时间短的。（2），作业的周转时间包括所有等待时间和自己的执行时间。发现我们两个都犯了个错误。错误在于忽略了最先适应分配算法以及题目所说的“不可移动”分配内存。在JOB1从输入井进入内存之后，内存还剩余80K，8.2时刻JOB2赶到，申请60K内存，批准，还剩余20K，但不能立即执行，因为JOB1还没执行完。8.4时刻JOB3也赶到，申请25K内存，内存不够，不批准，让JOB3在输入井中等待。8.6时刻JOB4赶到，申请20

8、K，刚好有20K，批准，此时内存中有三个作业JOB1、JOB2、JOB4。9时刻，JOB1执行完成，释放出20K内存，但是不满足JOB3的25K需要，所以此时JOB3被排斥在内存之外，于是下一步只能选择JOB4，执行JOB4之后也释放20K内存。此时，注意，在JOB2上面和下面各有20K内存区域，又因为分配后的内存不可移动，不能把60K移动到某一头，让这两个20K连成连续的40K空间。这导致JOB3一直被排斥在内存之外，直到JOB2执行完之后，这个时候已经是时刻10，也就是那个参考答案表中的JOB3的开始时间是10了。8设有一个关系模式R（A,B,C,D),F=A-B,B-C,C-D,D-A，

9、求R的侯选码及可达到的最高范式。只要能推导出整个属性组U，况且没有多余元素就是候选码。在这个关系模式中，A、B、C、D都能推导出U，况且只有自身一个元素无多余元素，所有都是候选码。因为R没有非主属性，R是3NF.但是R是否属于BCNF呢？按照BCNF的定义：如果每一个决定因素都含有码，即是BCNF，当然此题满足这个条件，从这个条件看，R是属于BCNF。但是R又存在传递依赖（A-B-C得出A-C），好像又不是BCNF，这到底应该怎么理解？这里应该是BCNF。你所例举的传递依赖是不成立的，它不符合传递依赖的定义，你错就错在这里。对于传递依赖X-Y-Z，要求：1，Y不是X的子集；2，Y-X不成立；3

10、，Z不是Y的子集。你例举的“A-B-C”，根据函数依赖集中的“B-C,C-D,D-A”及Armstrong推理系统中的传递律（注意，不是传递依赖，不要把两者搞混了），可得B-A。这显然不满足条件2。因此不属于传递依赖。但是它是成立的，只是不符合传递依赖的定义罢了。9有只与一个实体相当的联系吗？如果只有一个实体，还需要什么联系？你狭隘地理解了实体间的联系。在E-R中，可以将实体理解为一个集合。一个实体可以自己跟自己联系，比如职工实体集中有领导和被领导的联系，也就是说职工当中某一员来领导所有职工，那么“领导”这个联系两端都连接在实体“职工”上。10元组比较操作（a1,a2) (b1,b2)的意义是

11、_。老师，本题我觉得不理解，首先，元组中某一分量是可以用来比较的,如a1i b1j，但是元组之间也能比较的吗？通俗点说，a1,a2,b1,b2都是表中的一行记录吧，如果有一选课关系模式（学号，课程号，成绩）。数据为（张三，c001,67),(李四，c002,78)，难道这二条记录有可比性？当然不是你说的这种情况的操作，这种元组比较一般用于字符或者数字比较。比如比较（10，11）和（10，12），那么根据上述法则有（10，11）（10，66）。又如（a，6）和（b，1），则有（a，6）（b，1）。优先考虑第1个，元素比较，在第一个相等的情况下才考虑第2个。对（39）我还是不明白，如果是字符串比较

12、“abc;234 bbc;234或者abc;324 abc;434那我理解。还有（58）、（59）的试题分析，其中有A = 18？“abc;234 和bbc;234比较，取第1个字母a、b比较，发现a b,于是abc;234 PB-PA.的顺序推进时，执行正确；但进程执行顺序是不定的，如果按PA-PA-PB-.的顺序推进时，即PA连续执行两次或以上时，执行不正确。该如何解决？在这里，因为只有两个进程，所以不必要设置互斥访问信号量，只需要设置两个同步信号量即可：empty，表示空管道个数，初值显然为1；full，表示满管道个数，初值显然为0.其过程如下：PA进程：while (true)P(em

13、pty)；写数据到管道；V(full)； PB进程：while(true)P(full)； 从管道读数据；/进入临界区读数据V(empty) 现在如果PA要连续两次写数据，第一次之后empty=0，第二次再执行P(empty)；使得empty=-1，于是被阻塞在临界区这个地方，将PA置入阻塞在empty的等待队列。它必须等到执行PB中的V(empty)才可以第2次写入，因为执行V(empty)之后，empty=0，表明有进程被阻塞在empty信号量上，系统查询empty信号量的等待队列，发现PA，于是调入PA执行临界区操作，注意，因为临界区在P(empty)；语句之后，继续执行PA时不能再执行

14、“P(empty)；”，而是直接从临界区“写数据到管道；”开始继续执行。怎样区分确定的有限状态自动机和非确定的有限自动机？一套模拟题里的分析中有。但我还是不理解。可以唯一确定一个状态是什么意思？能举例说明吗？ 所谓的唯一确定性，是指，对任何状态k，和输入的符号a,能唯一地确定下一个状态。也就是说转换函数是个单值函数。而非确定有限自动机，却不一样，对任何状态k，和输入的符号a,可能有多个下一个状态。比如某DFA中，有两个状态1、2，1状态接受字符a，就从状态1跃迁到2，那么转换函数为f(a, 1)=2.而在NFA（不确定自动机）中，有三个状态1、2、3，1状态接受字符a，就可以跃迁到状态2，也可

15、以跃迁到状态3，即f(a, 1)=2, 3。14. 老师,电子教材中关于海明码的有一个问题:校验位:r3=I8I7I6I5是怎么得来的? 代替异或运算符 比如r3，n=3，信息位I8 对应的第十二位12=23+22，式子右边含有2n=23，类似地I7、I6、I5也含有2n=23，所以r3=I8I7I6I5.其中表示方幂。r3是表示在所有校验位中排第3地那个校验位，I8表示在所有信息位中排第8的那个信息位，而I8却在整个编码中排第12位。15. 开发部有4000台微机该公司只有若干个C 类IP地址,无AB两类那么要_个C类网络才能组建开发部的子网.答案是16首先要搞清楚C类地址的格式。C类地址中

16、前3位是110，左数第4位到左数24位为网络地址，从左数第25位到最后的32位共32-25+1=8位是主机地址。2的8次方就是256，去掉两个特殊的地址（主机号全为1或0）得254，表示一个C类网络能容纳254台主机，再用4000/254.16. 首先注意前提，关系模式是全码，既然是全码的话，如果存在主属性对码的部分依赖，那么该关系不可能是全码，如果存在主属性对码的传递依赖，那么实际上是直接依赖。我们来举例说明，比如R（A，B，C）是全码，有主属性B对码的部分依赖即，AC-B。显然此是B是多余的，因为通过AC就可以推导出ABC，因此跟全码矛盾。如果存在对全码的传递依赖，比如ABC-X-Y，其中

17、X、Y是某一属性。显然X、Y是ABC的真子集，而根据Armstrong公理系统可知，任何属性组都能直接推导出自己的真子集，可见上面的ABC-X-Y并非传递依赖。基本上是明白了，如果是全码则不存在主属性的传递依赖及部分依赖，如果不是全码，有多个候选码，判断BCNF，则需判断主属性的传递依赖及部分依赖是否存在们将某一关系是全码等同于某一关系的属性都是主属性了。事实并非如此。由于一个关系可能有多个候选码，而包含在任一候选码中的属性都是主属性。当所有候选码的中的属性的并集等于总属性集U时，所有的属性都是主属性，但这个时候关系模式可能不是全码。可见二者并不是等价的。你回答说一定是3NF，也没有错，因为它

18、一定是BCNF，那么必定是3NF。如果将问题改成：如果一个关系模式的属性都是主属性，那么该关系模式最高一定可达到第几范式？那么就答：3NF。17. 数据结构多看二叉树和图，软件工程多看UML和软件测试，个人建议。18、关系模式R（U，F），U=A,B,C,D,E，F=ABC,BCDE,BD,AD,EA,如何分解成BCNF,请写出详细分析过程。 U=A,B,C,D,E，F=ABC,BCDE,BD,AD,EA，则R的主码为A，其中D和E传递依赖于A，故可分解为R1=A，D，R2=A，E和R2=A，B，C，此时都为BCNF。19、在复习时，建议你边看边注意总结，个人觉得像全球信心化、数据仓库、电子商

19、务等叙述性的知识点容易出这种题型的题。下午试题一般为4道题目，第一道题为数据流程设计，第2-4道为数据库设计题，包括E-R图设计，E-R图向关系模式的转换，范式、SQL语言等知识点。 23设关系模式R（ABCDE）上的函数依赖集F=A-BC,BCD-E,B-D,A-D,E-A,将R分解成两个关系模式：R1= (ABD),R2=(ACE),则R1 和R2的最高范式分别是：？R2上函数依赖集为A-E,E-A,A-C，A、E都是候选键，亦即每个函数依赖的决定因素都是码，故为BCNF。A-E是否如下可以推出：A-BC,BCD-E所有AD-E,又A-D,所以有A-E.21、设有关系模式 W ( C，P，

20、S，G，T，R )，其中各属性的含义是：C课程，P教师，S学生，G成绩，T时间，R教室，根据语义有如下数据依赖集：D= CP，(S，C)G，(T，R)C，(T，P)R，(T，S)R 关系模式 W 的一个码( 关键字 )是 ？如果函数XU在R上成立，且不存在任何X的真子集X，使得XU也成立，则称X是R的一个候选码。题目中有：(T，S)R，(T，R)C，(S，C)G，CP，(T，P)R，又因为U= C，P，S，G，T，R ，所以(T，S) U，(T，S)为W的码。简单地说，候选码决定了所有其它属性，标识了整个元组，同时也不含多余元素，比如上例中，(T，S，R)U，但（T，S，R）不是候选码，因为它

21、有多余属性R，不满足“如果函数XU在R上成立，且不存在任何X的真子集X，使得XU也成立”，因为（T，S，R）中有真子集（T，S）使得(T，S) U。22、“在W3中，C传递依赖于键，所以规范化程序最高达到2NF”，在W3中的关系为：（T，R）C，（T，S）R，没什么传递依赖吧？解：存在。由题目的(T,S)-R和(T,R)-C可以得到(T,S)-C，我们选取(T,S)作主码，则每一个非主属性都完全函数依赖于码，W属于2NF。接下来判断W是否属于3NF，由于(T,S)-R、(T,R)-C、(T,S)-C中已有传递函数依赖，所以W不属于3NF，所以W最高为2NF。在判断是否是3NF时，所谓的传递依赖

22、是指非主属性对码的传递依赖。23、我每次做“关于判断一个分解是否为保持函数依赖”的时候，我都选是，我也不知道什么情况下不是，你能不能举一个不保持函数依赖的关系模式R（U，F）的例子,并说明为什么不是？谢谢解：例如：关系模式R=A，B，C，其FD=A-B，A-C，把R分解为R1=A，B，R2=B，C，则该分解就不保持函数依赖。因为在R中的A-C丢失了。操作系统中,关于p,v 操作问题,s信号量若是负值,表示等待进程的个数.怎么理解?若s的初值为1,执行一个p 操作,s=s-1;(相当于加锁),难道还可以继续接受别的进程执行p 操作吗? 能否举一例,透彻解释一下p,v操作详细过程.谢谢!解：例如，

23、系统有1台打印机，首先s=1，当一个使用前，执行P操作，s=0，如果另一个进程申请使用，则执行P操作，s=-1，但这时已经没有资源，该进程必须等待，依次类推，再来一个进程申请，执行P操作，s=-2，等待。设度为1的结点数为N1，设度为2的结点数为N2，设度为0的结点（叶子）数为N0，则根据二叉树的公式：N0+N2=2N2+1，即N0=N2+1。SNMP的设计是基于IP之上的无连接的用户数据报协议，即UDP/IP协议。海明码是奇偶校验的一种扩充。它采用多位校验码的方式，在这些校验位中的每一位都对不同的信息数据位进行奇偶校验，通过合理地安排每个校验位对原始数据进行校验位组合，可以达到发现错误，纠正

24、错误的目的。假设数据位有m痊，如何设定校验位k的长度才能满足纠正一位错误的要求呢？K位的校验码可以有2k个值。显然，其中一个值表示数据是正确的，而剩下的2k-1个值意味着数据中存在错误，如果能够满足：2k-1m+k（m+k为编码后的总长度），在理论上k个校验码就可以判断是哪一位（包括信息码和校验码）出现问题。编码步骤如下：根据信息位数，确定校验位数，2r=k+r+1，其中，k为信息位数，r为校验位数。求出满足不等式的最小r，即为校验位数。计算机校验位公式如下：表1-3其实可以当成一个公式来套用,如有已经编码的数据1100 1001 0111.我们只需把这些数据填充一校验公式,即可得到信息位与校

25、验位.填充的方法是这样的,首先看数据的最低位(即右边第一位),最低位为1,把1填充在公式表的r0位置,接着取出数据的次低位数据(即右边的第2位),把它填充到r1位置,把右边第3位数填充到I1位置.依此类推,我们可以得到表1-4:表中第二行数据为1100 0011，这就是数据1100 1001 0111的编码信息，而表格第三行是1011，这便是校验位。注意：校验位r所在位数为2n,其余由信息位填充；信息位下标从1开始，而校验位下标从0开始。例如：I8对应的第十二位12=23+22,I7，对应的第十一位11=23+2+20,I6对应的第十位10=23+21,I5对应的第九位9=23+20，一直写到

26、I1对应的第三位。校验位r由前面位数写成2的幂之和中包含2n的位数对应的信息位之和构成。例如：r3=I8I7I6I5（其中的1代表加号）注意：其中“”异或运算。（3）求校验位。根据上面我们所说的计算公式可以求出校验位。（4）求海明码。2纠错步骤（1）根据海明码的信息位和校验位的分布规则，找出接收到的数据的信息位以及校验位。如有已经编码的数据1100 1001 0111，则可以根据上表得到编码的信息为：1100 0011；校验位为：1011，接收端对校验位进行验证S=r(校验)+r(接收)判断校正因子是否有错，并改正。Sn Sn-1 Sn-2S0二进制对应的是那位就是那位出错，将其改正完成纠错。

27、如1001为第九位，将第九位1变0（或0变1）即可。例题1求信息1011的海明码。解答：（1）2r=4+r+1,确定校验位为3位23=4+3+1.（2）列出公式表格。7=4+2+1，6=4+2，5=4+1，3=2+1r2=I4+I3+I2 r1=I4+I3+I1 r0=I4 +I2+I1根据公式得r2=0,r1=0,r0=1加入表格则海明码为1010101 P-V操作理解析疑（1）定义：P原语的主要操作是：（1）sem减1；（2）若sem减1后仍大于或等于零，则该进程继续执行；（3）若sem减1后小于零，则该进程被阻塞，在相应队列中排队，然后转向系统的进程调度。V原语的主要操作是：（1）sem

28、加1；（2）若相加结果大于零，则该进程继续执行；（3）若相加结果小于或等于零，则唤醒一阻塞在该信号量上的进程，然后再返回原进程继续执行或转进程调度。典型理解偏差：1。以V原语的1、2步来做，Sem不就永远大于0，那进程不就一起循环执行成为死循环了？2Sem大于0那就表示有临界资源可供使用，为什么不唤醒进程？3Sem小于0应该是说没有临界资源可供使用，为什么还要唤醒进程？4如果是互斥信号量的话，应该设置信号量Sen=1，但是当有5个进程都访问的话，最后在该信号量的链表里会有4个等待，也是说S=4，那么第一个进程执行了V操作使S加1，释放了资源，下一个应该能够执行，但唤醒的这个进程在执行P操作时因

29、S0，也还是执行不了，这是怎么回事呢？5Sem的绝对值表示等待的进程数，同时又表示临界资源，这到底是怎么回事？析疑1。P操作对Sem减1的。P、V原语必须成对使用！从而不会造成死循环。2Sem大于0的确表示有临界资源可供使用，而且这个时候没有进程被阻塞在这个资源上，也就是说没有进程因为得不到这类资源而阻塞，所以没有被阻塞的进程，自然不需要唤醒。3V原语操作的本质在于：一个进程使用完临界资源后，释放临界资源，使Sem加强，以通知其它的进程，这个时候如果Sem0，表明有进程阻塞在该类资源上，因此要从阻塞队列里唤醒一个进程来“转手”该类资源。比如，有2个某类资源，三个进程A、B、C、D要用该类资源，

30、最开始Sem=2，当A进入，Sem=1，当B进入Sem=0，表明该类资源刚好用完，当C进入时Sem=1，表明有一个进程被阻塞了，D进入，Sem=2。当A用完该类资源时，进行V操作，Sem=1，释放该类资源，而这时SemSN,S#-SD。 下面我们先通过一个例子来说明设计不好的关系模式会存在什么问题，分析这些问题产生的原因，从中寻找出设计一个好的关系模式方法。 当我们要建立一个数据库来描述学校中的情况时，所面临描述对象有学生（用学号S#描述），系（用系名SD描述），系负责人（用系负责人姓名DM描述），课程（用课程名CN描述）和成绩（用G描述），于是我们得到了这样一组属性：U=S#,SD,DM,C

31、N,G. 现实世界的已知事实告诉我们：（1）一个系有若干学生，但每个学生只能属于一个系；（2）一个系只有一名负责人；（3）一个学生可以选修多门课程，而每门课程又可被若干学生同时选修；（4）每个学生学习每门课程只有一个成绩；于是，我们得到了属性组U上的一组函数依赖：F=S#-SD,SD-DM,(S#,CN)-G。因此一个关系模式应当描述为：R(U,D,DOM,F)。这其中：（1)R是关系名；（2）U是一组属性，即组成R的全部属性的集合；（3）D为域的集合，即属性取值范围的集合；（4）DOM为U与D之间的映象；（5）F是属性组U上的一组函数依赖。 由于域的定义对关系模式设计关系不大，（3）和（4）

32、往往可以忽略，于是我们得到了学校数据库模式：S（U，F）。这个模式有下述3个缺点：（1）有较大的冗余度。比如，每个系的负责人姓名，要与该系每个学生学习每一门课程的成绩出现的次数一样多，同一数据的重复存贮，不仅仅多占用了存贮空间，同时也为数据库的修改带来困难。例如某系的负责人更换了，那就必须逐一修改有关这个系的每一个元组；（2）插入异常。如果一个系刚刚成立，尚没有学生，那么我们就无法把这个系及其负责人的信息存入到某个元组中去，可能有人会这样想，先存入系及负责人的信息，放一空值在这个元组的其他项上，但由于S#和CN是这个关系的关键字，就要用到带空值的关键字对元组的查找，而关键字为空值的元组是通常都

33、是不容许在关系中存在的。（3）删除异常。如果一个系的学生全部毕业了，我们在删除该系学生选修课程的信息的同时，也把这个系及其负责人的信息也丢了。 上述这些缺点非常不利于数据库的维护和应用，所以我们说，它是一个不好的数据库模式，一个好的模式应当不会发生插入和删除异常，而且冗余要尽可能少，在操作过程中不致产生信息的丢失和造成数据的不一致。 产生插入和删除异常的原因可以从对关键字的定义看出，一个关系中的两个元组，如果关键字相同，那么别的属性值也一定相同，也就是说这两个元组一定是同一元组，因而关键字是一个元组区别于其它元组的依据，同时也是一个元组赖以生存的依据，因为任何事物只有当它能区别于别的事物时，谈

34、到它的存在才是有意义的，因而关键字或关键字的一部分为空值的元组是不可能在关系中存在的。 消除插入异常和删除异常的办法就是进行模式分离，例如，把上述关系模式分解成以下三个关系模式：SD（S#，SD，S#-SD）,SG（S#，CN，G，（S#，CN）-G，D（SD，DM，SD-DM）。这时，一个关系只用来描述一个实体或实体之间的一种联系，下面介绍的规范化理论就是基于这一简单概念的。 在1.4.5中我们曾提过：关系中的每一个分量必须是不可再分的数据项，这就是一种最基本的规范化(也称第一范式)，并非这一简单的规范化关系都能很好的描述现实世界，必须作进一步的分析以确定如何设计一个好的、反映现实世界的模式

35、。 通常是根据一个关系所具有属性之间的依赖情况来判定其是否具有某些不合适的性质，按属性间依赖情况区分关系规范化的程度为第一范式，第二范式，第三范式，第四范式等，其中第一、二、三范式是Codd最早定义的。后来人员又陆续提出了BC范式、第四范式和第五范式。1.5.2 函数依赖 函数依赖是关系数据库设计中的一个重要概念，下面我们给出函数依赖的定义。 定义1。设R（U）是属性集U上的一个关系模式，X，Y是U的子集。若对于R（U）中任意可能关系r（即对于每一时刻的数据库中对应于关系模式R的内容)，r中不可能有两个元组在X的属性分量相等，而同时在Y的属性分量值却不等，则称“X函数决定Y”，或称Y函数依赖于

36、X。记作X-Y。 将上述定义说得更明确一些，就是对于r中的属性或属性组X的每一个值，r中Y只有一个值与之对应。例如，若X是R的关键字的属性集合，则对于这一关系的所有属性子集Y，都有X-Y成立，这是因为关键字唯一地决定一个元组。当两个元组的关键字相等时，这两个元组内容也必相等，即它们所有的属性值都相等，因此不可能存在这样两个元组，它们在X关键字属性值上相等，而在Y值上却不等。又如姓名和年龄，在没有同名的情况下，姓名-年龄，这里年龄对于姓名的函数依赖关系，必须是在没有同名的条件下成立，如果有相同的姓名，则年龄就不再函数依赖于姓名了。 对于函数依赖，必须说明几点的是：（1）当我们在确定关系模式R中的

37、某个函数依赖时，是指R的所有可能关系r都必须满足这个函数依赖；反之，如果R中只要有一个关系r不满足这个函数依赖，我们就认为R不存在这个函数依赖；（2）一个关系模式R上的函数依赖的确定，只能从属性的含义上来说明，而不能从数学上来说明，它仅是一个语义范畴的概念；（3）只有数据库的设计者才能确定是否存在函数依赖，例如，一旦确定SN-SD，则实际上规定一个学生只能在一个系中，排斥了他处在两个系的可能性。 若X-Y，而且，则称X-Y是非平凡函数依赖，下面的讨论均基于此定义。（1）若X-Y，X称作决定因素；（2）若X-Y,Y-X,则记作XY；（3）若Y不依赖于X，则记作。 下面讨论函数依赖的一些性质。假设

38、R（A，B，C）是一个关系模式，A，B，C为属性，若在R中有A-B和B-C，则在R中必定有A-C。关于这一点，可以用反证法来说明，假定在R的某一关系r中满足A-B，B-C，但不能满足A-C；即在r中存在两个元组u，v，它们在属性A的分量上取值相等，而在C的分量上取值不相等，u，v在属性B的分量上的值有两种可能，若相等，则违反了B-C；若不相等；则违反了A-B；这与假设矛盾，也就说明了在r中必满足A-C。从这个例子中，我们可以看出函数依赖A-B，B-C逻辑蕴涵了函数依赖A-C。 定义2。在R（U）中，若属性集合Y函数依赖于属性集合X，但Y函数不依赖于X的任一子集，则称Y对X完全函数依赖，记作，反

39、之，若Y依赖于X的某一个真子集，则称Y对X部分函数依赖，记作。这里举一个简单的例子，在关系S（S#，SN，SD，SA）中，S#-SD，S#-SA，S#-SN；而在关系SC（S#，C#，G）中，。 定义3。在R（U）中，如果，Y-X，X-Z，则称Z对Y传递依赖。这里加上条件，是因为如果X-Y，则YX，实际上是Y-Z，而不是传递函数依赖. 定义4。在R（U）中。K为U的属性或属性组，若有，则称K为R的一个候选关键字，若候选关键字多于一个，则选择其中之一为主关键字（Primary Key）. 包含在一个候选关键字中的属性叫做主属性，不包含在任何一个候选关键字中的属性称为非主属性，最简单的情况，单个属

40、性是关键字，最极端的情况，整个属性组是关键字，如在关系模式S（S#，SN，SD，SA）中，S#是关键字，如在关系模式SC（S#，C#，G）中，属性组（S#，C#）是关键字。 定义5。在R（U）中，属性或属性组集合X并非它的关键字，但X是另一个关系模式的关键字，则称X是R的外部关键字。 例如SC（S#，C#，G）中，S#不是关键字，但S#是关系S（S#，SN，SD，SA）的关键字，则S#对于关系模式SC来说是外部关键字，主关键字与外部关键字提供了一条关系之间相互联系的途径，例如关系模式S与关系模式SC的联系就是通过S#。1.5.3 范式的定义 关系数据库中的关系是要满足一定要求的，满足不同要求为

41、不同范式，满足最低要求的叫第一范式，简称1NF，在第一范式基础上进一步满足一些要求的为第二范式，其余以此类推。 对于各种范式之间的联系有。一个低一级范式的关系模式，通过投影运算可以转化为若干个高一级的关系模式集合，这种过程就叫规范化。我们经常把某一关系模式R为第几范式记为。以下我们着重介绍常用的第一范式、第二范式和第三范式的定义，以及设计这些范式的基本方法。【1】1NF 定义6.如果一个关系模式R的所有属性都是基本的、不可分的，则R是第一范式。S#STATUSCITYP#QTYS120LONDONP1300S120LONDONP2200S120LONDONP3400S120LONDONP420

42、0S120LONDONP5100S120LONDONP6100S210PARISP1300S210PARISP2400S310PARISP2200S420LONDONP2200S420LONDONP4300S420LONDONP5400图1.13 FIRST关系表 关系模式FIRST（S#，STATUS，CITY，P#，QTY），该关系内容如图1.13所示，其函数依赖集为：,，。显然FIRST关系模式是第一范式。此关系模式的关键字为（S#，P#），属性STATUS和CITY不完全函数依赖于（S#，P#），QTY是完全函数依赖于（S#，P#）。并且STATUS和CITY也不是相互独立的，而是也存

43、在着函数依赖，这使得关系FIRST在插入，删除，修改三种存贮操作出现异常。在供应商未供应零件时，我们不能登记某供应商位于某一城市的信息，例如不能登记供应商位于ATHENS这样一个信息，其原因是关键字的值在P#出现了空值。 当我们删除某一供应商时，若该供应商仅出现在一个元组中，那么我们不仅删除了该供应商该供应零件的信息，而且也删除了该供应商位于某一城市的信息。例如我们删除了关键字为（S3，P2）的元组，则我们也删除了S3位于PARIS的信息。 如果要修改某一供应商的城市值，通常需要修改多个元组，这就容易产生不一致。例如供应商S1从LONDON迁移到AMSTERDAM，就需要修改6个元组。【2】2

44、NF 为了解决上述问题，我们把关系模式FIRST分解成两个关系模式SECOND（S#，STATUS，CITY）和SP（S#，P#，QTY），如图1.14所示。S#STATUSCITYS120LONDONS210PARISS310PARISS4120LONDONS530ATHENSSECONDS#P#QTYS1P1300S1P2200S1P3400S1P4200S1P5100S1P6100S2P1300S2P2400S3P2200S4P2200S4P4300S4P5400SP图1.14 SECOND和SP关系表 这样处理后的结构，克服了S#和CITY存贮操作中的问题。例如，我们可以把S5位于AT

45、HENS的信息插入到SECOND关系中，即使S5没有提供任何零件。 如果我们在关系SP中删除（S3，P2）为关键字的元组，也不会丢失供应商S3位于PARIS的信息，当供应商S1从LONDON迁移到AMSTERDAM，只要对SECOND关系S1为关键字的元组作修改就可以了，仅仅修改一次，不会出现上述的不一致了。 将图1.13与图1.14作比较，在关系模式下FIRST中属性STATUS和CITY是非关键字属性，它们只依赖于（S#，P#）的一部分，即只依赖于S#，也就是说关系模式FIRST中非关键字属性并不完全函数依赖于关键字属性；而改进之后，关系模式SECOND中，非关键属性完全依赖于关键字属性；

46、 定义7.如果关系模式R是1NF，而且非关键的属性完全函数依赖于关键字的属性，那么，关系模式R是第二范式。 按照定义7，关系模式SECOND和SP都是2NF，如果一个关系模式是1NF而不是2NF，总可以通过适当投影化为一组等价的2NF关系模式集合，这种投影后的关系等价于原关系，即原关系能够通过这种投影关系的适当连接而恢复。在上面的例子中，关系SECOND和SP是关系FIRST的投影，而关系FIRST可通过SECOND和SP连接得到。可以看到，若一个关系模式是1NF，而不是2NF，则该关系模式的关键字一定由多于一个属性组成。 由于这种分解过程不丢失信息，故原关系中的任何信息能从这个新的关系中导出

47、，但新的关系中包含了原关系中无法表示的某种信息。例如S5位于ATHENS的信息。从这个意义上来说，新的关系更好的反应了现实世界。【3】3NF 关系模式SECOND在存贮操作上还存在异常现象，例如，我们不能把某个城市具有某一状态信息存入SECOND关系中，原因和上述一样，也没有恰当的关键字值。在删除操作中，例如我们删去了SECOND关系中关键字为S5的元组，则我们也就失去了ATHENS状态为30的信息，在修改时，例如把LONDON的状态值由20修改为30，则要对元组S4和S1都作修改，否则可能出现不一致性。 出现上述问题的原因是属性STATUS关于属性S#的依赖性，它具有传递性，即，。 为了解决上述问题，我们再将关系模式SECOND投影成两个关系模式，SC（S#，CITY）和CS（CITY，STATUS），关系模式SC和CS中的函数依赖上面我们已给出了。图1.15表示了关系SC和CS。显然，通过分解消除了非关键字的属性传递依赖于关