判断模式分解是否具有无损连接性的算法

计算机技术及软件资格考试真题一、选择题1.设关系模式R，其中U={A,B,C,D,E}，F={A→BC，C→D，BC→E，E→A}，则分解p={R1(ABCE)，R2(CD)}满足（）A. 具有无损连接性、保持函数依赖B. 不具有无损连接性、保持函数依赖C. 具有无损连接性、不保持函数依赖D. 不具有无损连接性、不保持函数依赖解析：这是一道数据库理论题，需要判断给定的分解是否满足无损连接性和函数依赖保持性。

通过详细分析，可以确定分解是否满足这两个条件。

2.企业应用集成是一个战略意义上的方法，它从服务和信息的角度将多个信息系统绑定在一起，提供实时交换信息和影响流程的能力。

空白（2）处应选择（）A. API集成B. 数据集成C. 界面集成D. 过程集成解析：这是一道关于企业应用集成的选择题。

根据企业应用集成的定义和特性，可以判断哪个选项最符合题目描述。

在这个例子中，界面集成是指从用户使用角度能够对集成系统产生一个“整体”的感觉，因此C是正确答案。

3.多媒体数据量巨大，为了在有限的信道中并行开通更多业务，应该对多媒体数据进行（）压缩。

A. 时间域B. 频率域C. 空间域D. 能量域解析：这是一道关于多媒体数据压缩的选择题。

根据多媒体数据压缩的原理和方法，可以判断哪个选项最符合题目描述。

在这个例子中，空间域压缩是常用的多媒体数据压缩方法，因此C是正确答案。

4.（）可以帮助人们简单方便地重用已经成功的设计或体系结构。

A. 商业构件B. 设计模式C. 遗留系统D. 需求规格说明解析：这是一道关于软件工程和重用技术的选择题。

根据软件工程和重用技术的原理和方法，可以判断哪个选项最符合题目描述。

在这个例子中，设计模式是一种可重用的、针对特定问题的解决方案，因此B是正确答案。

二、简答题1.简述静电防护的基本原则。

解析：这是一道关于静电防护的简答题。

需要回答静电防护的基本原则和方法。

可能的答案包括：抑制静电的产生、限制静电的积累和消除静电的危害等方面。

大学的注册办公室维护关于以下实体的数据：（a）课程，包括编号、名称、学分、课程提纲和选修条件；（b）课程提供，包括课程编号、年、学期、节数、教师（可能多个）、时间和教室；（c）学生，包括学生标识、名字和计划；（d）教师，包括标识号、名字、系和职称。

此外，学生课程的登记和学生所选的每门课的成绩评定都要适当地建模。

请画出该系统的E-R图，将E-R图转化为关系模式并进行必要的模式合并个（courseofferings实体集，应用双矩形表示）Student(sid, name, program)Course(courseno, title, credits, syllabus)Instructor(iid, name, dept, title)Courseofferings(courseno, year, semester, secno, room, time)Enrols(sid, courseno, year, semester, secno, grade)Teaches(iid, courseno, year, semester, secno)Requires(maincourse_courseno, prerequisite_courseno)Compute the closure of the following set F of functional dependenciesfor relation schema R = (A, B, C, D, E).A→BCCD→EB→DE→AList the candidate keys for R.Starting with A → BC, we can conclude: A → B and A → C.Since A → B and B → D, A → D (decomposition, transitive)Since A → CD and CD → E, A → E (union, decomposition, transitive)Since A → A, we have (reflexive)A → ABCDE from the above steps (union)Since E → A, E → ABCDE (transitive)Since CD → E, CD → ABCDE (transitive)Since B → D and BC → CD, BC → ABCDE (augmentative, transitive).Therefore, any functional dependency with A, E, BC, or CD on the left hand side of the arrow is in F+, no matter which other attributes appear in the FD.Allow * to represent any set of attributes in R, then F+ is BD → B, BD → D,C → C,D → D, BD → BD, B → D, B → B, B → BD, and all FDs ofthe form A∗→ α, BC∗→ α, CD∗→ α, E∗→ αwhere α is any subset of {A, B, C, D, E}. The candidate keys are A, BC, CD, and E.a B+ = { BDACE}b A->BCD, A->ABCD,BC->DE, ABCD->ABCDEA->ABCDEAF->ABCDEF所以c A->BCD中D无关属性BC->DE中C无关D无关A->BCB->DB->ED->AA->BCB->DED->AD (ABC) (BDE)(DA)(AF)E (ABCD)(AF)(AE)正则覆盖定义和计算方法•定义5.11正则覆盖(canonical cover)F c是一个依赖集，使得F逻辑蕴涵Fc 中的所有依赖，Fc逻辑蕴涵F中的所有依赖，而且必须具有下列特性：–F c中的任何函数依赖都不包含无关属性；–F c中函数依赖的左半部都是唯一的，即F c中不存在两个依赖α1→β1和α2→β2，且α1＝α2。

求最小函数依赖集分三步:1.将F中的所有依赖右边化为单一元素此题fd={abd->e,ab->g,b->f,c->j,cj->i,g->h};已经满足2.去掉F中的所有依赖左边的冗余属性.作法是属性中去掉其中的一个,看看是否依然可以推导此题:abd->e,去掉a,则(bd)+不含e,故不能去掉,同理b,d都不是冗余属性ab->g,也没有cj->i,因为c+={c,j,i}其中包含i所以j是冗余的.cj->i将成为c->iF={abd->e,ab->g,b->f,c->j,c->i,g->h};3.去掉F中所有冗余依赖关系.做法为从F中去掉某关系,如去掉(X->Y),然后在F中求X+,如果Y在X+中,则表明x->是多余的.需要去掉.此题如果F去掉abd->e,F将等于{ab->g,b->f,c->j,c->i,g->h},而(abd)+={a,d,b,f,g,h},其中不包含e.所有不是多余的.同理(ab)+={a,b,f}也不包含g,故不是多余的.b+={b}不多余,c+={c,i}不多余c->i,g->h多不能去掉.所以所求最小函数依赖集为F={abd->e,ab->g,b->f,c->j,c->i,g->h};转换为3NF既具有无损连接性又保持函数依赖的分解算法：第一步：首先用算法1求出R的保持函数依赖的3NF分解，设为q={R1,R2,…,Rk}（这步完成后分解已经是保持函数依赖，但不一定具有保持无损连接）第二步：设X是R的码，求出p=q {R(X)}第三步：若X是q中某个Ri的子集，则在p中去掉R(X)第四步：得到的p就是最终结果例题：R(S#,SN,P,C,S,Z)F={S#→SN,S#→P,S#→C,S#→S,S#→Z,{P,C,S}→Z,Z→P,Z→C}•第一步:求出最小FD集：F={S# →SN, S# →P,S# →C, S#→S, {P,C,S→Z, Z →P,Z →C} // S# →Z冗余，FD：最小函数依赖按具有相同左部分组：q={R1(S#,SN,P,C,S), R2(P,C,S,Z), R3(Z,P,C)}R3是R2的子集，所以去掉R3q={R1(S#,SN,P,C,S), R2(P,C,S,Z)}•第二步:R的主码为S＃，于是p=q {R(X)}={R1(S#,SN,P,C,S), R2(P,C,S,Z), R(S#)}•第三步:因为{S＃}是R1的子集，所以从p中去掉R(S#)•第四步:p ={R1(S#,SN,P,C,S), R2(P,C,S,Z)}即最终结果判别一个分解的无损连接性举例2：已知R<U,F>，U={A,B,C,D,E}，F={A→C,B→C,C→D,DE→C,CE→A}，R的一个分解为R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，判断这个分解是否具有无损连接性。

函数依赖的公理系统：设有关系模式R(U)，X，Y，Z，W均是U的子集，F是R上只涉及到U 中属性的函数依赖集，推理规则如下：•自反律：如果Y X U,则X→Y在R上成立。

•增广律：如果X→Y为F所蕴涵，Z U，则XZ→YZ在R上成立。

(XZ表示X∪Z，下同)•传递律：如果X→Y和Y→Z在R上成立，则X→Z在R上成立。

以上三条为Armstrong公理系统•合并律：如果X→Y和X→Z成立，那么X→YZ成立。

•伪传递律：如果X→Y和WY→Z成立，那么WX→Z成立。

•分解律：如果X→Y和Z Y成立，那么X→Z成立。

这三条为引理注意：•函数依赖推理规则系统(自反律、增广律和传递律)是完备的。

•由自反律所得到的函数依赖均是平凡的函数依赖。

模式分解的几个重要事实：•若只要求分解具有“无损连接性”，一定可以达到4NF；•若要求分解要“保持函数依赖”，可以达到3NF，但不一定能达到BCNF；•若要求分解既要“保持函数依赖”，又要具有“无损连接性”，可以达到3NF，但不一定能达到BCNF；试分析下列分解是否具有无损联接和保持函数依赖的特点：设R(ABC)，F1={A→B} 在R上成立，ρ1={AB,AC}。

首先，检查是否具有无损联接特点：第1种解法--算法4.2:(1) 构造表(2)根据A→B进行处理结果第二行全是a行，因此分解是无损联接分解。

第2种解法:(定理4.8)R1(AB)∩R2(AC)=AR2- R1=B∵A→B,∴该分解是无损联接分解。

然后，检查分解是否保持函数依赖πR1（F1）={A→B，以及按自反率推出的一些函数依赖}πR2（F1）={按自反率推出的一些函数依赖}F1被πR1（F1）所蕴涵，∴所以该分解保持函数依赖。

保持函数依赖的模式分解一、转换成3NF的保持函数依赖的分解算法：ρ={R1<U1,F1>,R2<U2,F2>,...,Rk<Uk,Fk>}是关系模式R<U,F>的一个分解，U={A1,A2,...,An}，F={FD1,FD2,...,FDp}，并设F是一个最小依赖集，记FDi为X i →Alj，其步骤如下：① 对R<U,F>的函数依赖集F进行极小化处理（处理后的结果仍记为F）；② 找出不在F中出现的属性，将这样的属性构成一个关系模式。

1.R(X, Y, Z) F={Y→Z, XZ→Y},R的码是？R是第几范式？R候选关键字为XY和XZ，R中所有属性都是主属性，不存在非主属性对候选关键字的传递依赖。

根据F可以知道，这个关系模式的码为XZ，Y为非主属性，且有XZ---->Y，则此关系模式符合第二范式，再来看，根据第三范式的定义：对于关系模式R（U，F）中若不存在这样的码X，属性组Y及分主属性Z（Z不含于Y）使得X---->Y,Y----->Z成立，X不函数依赖于Y，这成R符合第三范式。

此题中因为XZ---->Y，Y---->Z ,XZ----->Z ，但是Z是主属性中的，故此模式也符合第三范式。

2.R(X, Y, Z) F={XY→Z},R的码是？R是第几范式？3.考虑关系模式CTHRSG，其中C代表课程，T代表教师，H代表上课时间，R代表上课地点（教室），S代表学生，而G代表成绩。

CTHRSG的函数依赖集为{C→T, HR→C, HT→R, CS→G, HS→R }。

求关系模式CTHRSG具有无损连接性的3NF分解4.R(X, Y, Z) F={Y→Z, Y→X, X→YZ}，R的码是？R是第几范式？Y,X 皆是关键字三个函数依赖的左边都包含侯选键故为BC范式5.设有关系模式R（A,B,C,D,E）,其上的函数依赖集：F={A→BC, CD→E, B→D, E→A} (1) 计算B+ ，(2) 求出R的所有关键字。

(1)B+=BD关键字：A+=ABCDE 所以A是关键字B+=BD,C+=CD+=DE+=AEB+=ABCDEAC+=ABCEDAD+=ABCDEAE+=ABCDEBC+=BCDEA 关键字BD+=BDBE+=BDEABC 关键字CD+=CDEAB 关键字CE+=ABCED 关键字DE+=DEABC 关键字5.设有关系模式R（ABCDEF），F={ A→BC，CD→E，B→DA }1）求R的所有候选码。

模式分解的无损连接性之深入剖析1. 无损连接分解的形式定义无损连接分解的形式定义如下：设R是一个关系模式，F是R上的一个函数依赖(FD)集。

R分解成数据库模式δ={R1,……,Rk}。

如果对R中每一个满足F的关系r都有下式成立：那么称分解δ相对于F是“无损连接分解”，否则称为“损失连接分解”。

其中表示自然连接。

从上述形式定义中可知，若直接根据定义来判断某个分解是否具有无损连接性，那么就得“对R中每一个满足F的关系r”进行测试，看是否满足上面的等式，这显然不可操作，因为“对R中每一个满足F的关系r”进行测试就意味着“对R中所有满足F的关系r”进行测试，显然是不可能的。

这里所说的“关系”就是指一张具体的表。

因此，必须寻求其它的可操作性方法来判别分解的无损连接性。

2. 无损连接分解的普通判别方法——表格法设关系模式R=A1,…,An，R上成立的FD集F，R的一个分解p={R1,…,Rk}。

无损连接分解的判断步骤如下：(1)构造一张k行n列的表格，每列对应一个属性Aj(1≤j≤n)，每行对应一个模式Ri(1≤i≤k)。

如果Aj在Ri中，那么在表格的第i行第j列处填上符号aj，否则填上符号bij。

(2)把表格看成模式R的一个关系，反复检查F中每个FD在表格中是否成立，若不成立，则修改表格中的元素。

修改方法如下：对于F中一个FD：X→Y，如果表格中有两行在X分量上相等，在Y分量上不相等，那么把这两行在Y分量上改成相等。

如果Y的分量中有一个是aj，那么另一个也改成aj;如果没有aj，那么用其中的一个bij替换另一个(尽量把ij改成较小的数，亦即取i值较小的那个)。

若在修改的过程中，发现表格中有一行全是a，即a1,a2,…,an，那么可立即断定p相对于F是无损连接分解，此时不必再继续修改。

若经过多次修改直到表格不能修改之后，发现表格中不存在有一行全是a的情况，那么分解就是有损的。

特别要注意，这里有个循环反复修改的过程，因为一次修改可能导致表格能继续修改。

1.说白话一点：闭包就是由一个属性直接或间接推导出的所有属性的集合。

例（1）：设有关系模式R(U，F)，其中U={A，B，C，D，E，I}，F={A→D，AB→E，BI→E，CD→I，E→C}，计算(AE)+解: (1) 令X={AE}，X(0)=AE(2)在F中寻找尚未使用过的左边是AE的子集的函数依赖，结果是: A→D，E→C；所以X(1)=X(0)DC=ACDE，显然X(1)≠X(0).(3) 在F中寻找尚未使用过的左边是ACDE的子集的函数依赖，结果是: CD→I；所以X(2)=X(1)I=ACDEI。

虽然X（2）≠X(1)，但F中寻找尚未使用过函数依赖的左边已经没有X（2）的子集，所以不必再计算下去，即(AE)+=ACDEI。

例如：f={a->b，b->c，a->d，e->f}；由a可直接得到b和d，间接得到c，则a的闭包就是{a，b，c，d}2.候选码的求解理论和算法对于给定的关系R（A1，A2，…An）和函数依赖集F，可将其属性分为4类：L类仅出现在函数依赖左部的属性。

R 类仅出现在函数依赖右部的属性。

N 类在函数依赖左右两边均未出现的属性。

LR类在函数依赖左右两边均出现的属性。

定理：对于给定的关系模式R及其函数依赖集F，若X（X∈R）是L类属性，则X必为R的任一候选码的成员。

推论：对于给定的关系模式R及其函数依赖集F，若X（X∈R）是L类属性，且X+包含了R的全部属性；则X必为R的唯一候选码。

例（2）：设有关系模式R（A，B，C，D），其函数依赖集F={D→B，B →D，AD →B，AC →D}，求R的所有候选码。

解：考察F发现，A，C两属性是L类属性，所以AC必是R的候选码成员，又因为（AC）+=ABCD，所以AC是R的唯一候选码。

定理：对于给定的关系模式R及其函数依赖集F，若X（X∈R）是R类属性，则X不在任何候选码中。

定理：对于给定的关系模式R及其函数依赖集F，若X（X∈R）是N类属性，则X必包含在R的任一候选码中。

函数依赖的公理系统：设有关系模式R(U)，X，Y，Z，W均是U的子集，F是R上只涉及到U中属性的函数依赖集，推理规则如下：∙自反律：如果Y X U,则X→Y在R上成立。

∙增广律：如果X→Y为F所蕴涵，Z U，则XZ→YZ在R上成立。

(XZ表示X∪Z，下同)∙传递律：如果X→Y和Y→Z在R上成立，则X→Z在R上成立。

以上三条为Armstrong公理系统∙合并律：如果X→Y和X→Z成立，那么X→YZ成立。

∙伪传递律：如果X→Y和WY→Z成立，那么WX→Z成立。

∙分解律：如果X→Y和Z Y成立，那么X→Z成立。

这三条为引理注意：∙函数依赖推理规则系统(自反律、增广律和传递律)是完备的。

∙由自反律所得到的函数依赖均是平凡的函数依赖。

模式分解的几个重要事实：∙若只要求分解具有“无损连接性”，一定可以达到4NF；∙若要求分解要“保持函数依赖”，可以达到3NF，但不一定能达到BCNF；∙若要求分解既要“保持函数依赖”，又要具有“无损连接性”，可以达到3NF，但不一定能达到BCNF；试分析下列分解是否具有无损联接和保持函数依赖的特点：设R(ABC)，F1={A→B} 在R上成立，ρ1={AB,AC}。

首先，检查是否具有无损联接特点：第1种解法--算法4.2:(1) 构造表(2)根据A→B进行处理结果第二行全是a行，因此分解是无损联接分解。

第2种解法:(定理4.8)R1(AB)∩R2(AC)=AR2- R1=B∵A→B,∴该分解是无损联接分解。

然后，检查分解是否保持函数依赖πR1（F1）={A→B，以及按自反率推出的一些函数依赖}πR2（F1）={按自反率推出的一些函数依赖}F1被πR1（F1）所蕴涵，∴所以该分解保持函数依赖。

保持函数依赖的模式分解一、转换成3NF的保持函数依赖的分解算法：ρ={R1<U1,F1>,R2<U2,F2>,...,R k<U k,F k>}是关系模式R<U,F>的一个分解，U={A1,A2,...,An}，F={FD1,FD2,...,FDp}，并设F是一个最小依赖集，记FDi为X i →Alj，其步骤如下：① 对R<U,F>的函数依赖集F进行极小化处理（处理后的结果仍记为F）；② 找出不在F中出现的属性，将这样的属性构成一个关系模式。