一:大部分是对一个关系模式分解成两个模式的考察,分解为三个以上模式时无损分解和保持依赖的判断比较复杂,考的可能性不大,因此我们只对“一个关系模式分解成两个模式”这种类型的
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
的相关判断做一个总结。
以下的论述都基于这样一个前提:
R是具有函数依赖集F的关系模式,(R1 ,R2)是R的一个分解。
首先我们给出一个看似无关却非常重要的概念:属性集的闭包。
令α为一属性集。我们称在函数依赖集F下由α函数确定的所有属性的集合为F下α的闭包,记为α+ 。
下面给出一个计算α+的算法,该算法的输入是函数依赖集F和属性集α,输出存储在变量result中。
算法一:
result:=α;
while(result发生变化)do
for each 函数依赖β→γ in F do
begin
if β∈result then result:=result∪γ;
end
属性集闭包的计算有以下两个常用用途:
·判断α是否为超码,通过计算α+(α在F下的闭包),看α+ 是否包含了R中的所有属性。若是,则α为R的超码。
·通过检验是否β∈α+,来验证函数依赖是否成立。也就是说,用属性闭包计算α+,看它是否包含β。
(请原谅我用∈符号来
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示两个集合之间的包含关系,那个表示包含的符号我找不到,大家知道是什么意思就行了。)
看一个例子吧,2005年11月系分上午37题:
● 给定关系R(A1,A2,A3,A4)上的函数依赖集F={A1→A2,A3→A2,A2→A3,A2→A4},R的候选关键字为________。
(37)A. A1 B. A1A3 C. A1A3A4 D. A1A2A3
首先我们按照上面的算法计算A1+ 。
result=A1,
由于A1→A2,A1∈result,所以result=result∪A2=A1A2
由于A2→A3,A2∈result,所以result=result∪A3=A1A2A3
由于A2→A4,A2∈result,所以result=result∪A3=A1A2A3A4
由于A3→A2,A3∈result,所以result=result∪A2=A1A2A3A4
通过计算我们看到,A1+ =result={A1A2A3A4},所以A1是R的超码,理所当然是R的候选关键字。此题选A 。
好了,有了前面的铺垫,我们进入正题。
无损分解的判断。
如果R1∩R2是R1或R2的超码,则R上的分解(R1,R2)是无损分解。这是一个充分条件,当所有的约束都是函数依赖时它才是必要条件(例如多值依赖就是一种非函数依赖的约束),不过这已经足够了。
保持依赖的判断。
如果F上的每一个函数依赖都在其分解后的某一个关系上成立,则这个分解是保持依赖的(这是一个充分条件)。
如果上述判断失败,并不能断言分解不是保持依赖的,还要使用下面的通用方法来做进一步判断。
该方法的表述如下:
算法二:
对F上的每一个α→β使用下面的过程:
result:=α;
while(result发生变化)do
for each 分解后的Ri
t=(result∩Ri)+ ∩Ri
result=result∪t
这里的属性闭包是在函数依赖集F下计算出来的。如果result中包含了β的所有属性,则函数依赖α→β。分解是保持依赖的当且仅当上述过程中F的所有依赖都被保持。
下面给出一个例题,2006年5月系分上午43题:
●设关系模式R
,其中U={A, B, C, D, E},F={A→BC,C→D,BC→E,E→A},则分解ρ={R1(ABCE),R2(CD)}满足 (43) 。
(43) A.具有无损连接性、保持函数依赖
B.不具有无损连接性、保持函数依赖
C.具有无损连接性、不保持函数依赖
D.不具有无损连接性、不保持函数依赖
先做无损链接的判断。R1∩R2={C},计算C+。
Result=C
由于C→D,C∈result,所以result=result∪D=CD
可见C是R2的超码,该分解是一个无损分解。
再做保持依赖的判断。
A→BC,BC→E, E→A都在R1上成立(也就是说每一个函数依赖左右两边的属性都在R1中),C→D在R2上成立,因此给分解是保持依赖的。
选A。
再看一个复杂点的例题。2007年5月数工40-41题。
●给定关系模式R,U={A, B, C, D, E},F={B→A,D→A,A→E,AC→B},其候选关键字为
(40) ,则分解ρ={R1(ABCE),R2(CD)}满足 (41) 。
(40) A.ABD
B.ABE
C.ACD
D.CD
(41) A.具有无损连接性、保持函数依赖
B.不具有无损连接性、保持函数依赖
C.具有无损连接性、不保持函数依赖
D.不具有无损连接性、不保持函数依赖
看见了吧,和前面一题多么的相像!
对于第一问,分别计算ABCD四个选项的闭包,
(ABD)+ = { ABDE }
(ABE)+ = { ABE }
(ACD)+ = { ABCDE }
(CD)+ = { ABCDE }
选D。
再看第二问。
先做无损链接的判断。R1∩R2={C},计算C+。
result=C
因此C既不是R1也不是R2的超码,该分解不具有无损分解性。
再做保持依赖的判断。
B→A,A→E,AC→B在R1上成立,D→A在R1和R2上都不成立,因此需做进一步判断。
由于B→A,A→E,AC→B都是被保持的(因为它们的元素都在R1中),因此我们要判断的是D→A是不是也被保持。
对于D→A应用算法二:
result=D
对R1,result∩R1=ф(空集,找不到空集的符号,就用这个表示吧),t=ф,result=D
再对R2,result∩R2=D,D+ =ADE ,t=D+ ∩R2=D,result=D
一个循环后result未发生变化,因此最后result=D,并未包含A,所以D→A未被保持,该分解不是保持依赖的。
选D。
二.关系模式T在使用过程中可能出现以下问题:
假设有教师关系模式:T(TNAME,ADDRESS,CNO,CNAME)
其中,TNAME——教师姓名,ADDRESS——教师地址,CNO——任教课程编号,CNAME——作者课程名。一个教师可以教多门课,一个教师教一门课则对应到关系中的一个元组。
1.数据冗余
数据库中不必要的重复存储就是数据冗余。如果一个教师教几门课程,那么这个教师的地址就要重复几次存储。 2.更新异常
更新异常也称修改异常,由于数据的重复存储,会给更新带来很多麻烦。可能会导致数据不一致,这将直接影响系统的质量。购书请到希赛网第一书店。如果某个教师教5门课,在关系中就会有5个对应的元组。如果这位老师的地址发生变化,这5个元组中的地址都要改变。若有1个元组没有更改,就会造成不一致现象。
3.插入异常
插入元组时出现不能插入的一些不合理现象。如果一个教师刚调来,尚未分派教学任务,那么就无法将教师的姓名和地址存储到关系中去。
4.删除异常
不该删除的数据被删除。如果要取消某个教师的教学任务,在删除该教师教学任务的同时,把该教师及他的地址信息也删除了,这是一种不合适的现象。
由于关系模式存在上述问题,因此这是一个“不好”的关系模式。购书请到希赛网第一书店。一个“好”的关系模式应当不会发生更新异常、插入异常和删除异常,有尽可能少的冗余。那么如何
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
一个“好”的关系模式,从1971年起E.F.Codd提出了
规范
编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载
化理论。
规范化理论最初是针对关系模式的设计问题提出的,它不但对于关系模型数据设计,而且对于其他模型数据库的设计也都有重要的意义。
规范化理论主要包括三个方面的内容:函数依赖、范式和关系模式分解。其中函数依赖起核心作用,是模式分解的基础,而范式则是模式分的标准。
例7.1.1 下列哪一条不是由于关系模式设计不当所引起的问题?[2006年4月 选择题第51题]( )
A.数据冗余 B.插入异常 C.删除异常 D.丢失修改
三.关系模式的分解特性:
1.模式分解中存在的问题
设有关系模式R(U)和R1(U1), R2(U2), …, Rk(Uk),其中U={A1, A2, …, An},Ui包含于U(i=1,2,…, k)且U=U1∪U2∪…Uk。令ρ={R1(U1), R2(U2), …, Rk(Uk)},则称?为R(U)的一个分解,也称为数据库模式,有时也称为模式集。用ρ代替R(U)的过程称为关系模式的分解。
数据库模式ρ的一个具体取值记作σ=(r1, r2, …, rk),称为数据库实例σ。其中ri是ρ中关系模式Ri(Ui)的一个具体关系。
实际上,关系模式的分解,不仅仅是属性集合的分解,它是对关系模式上的函数依赖集,以及关系模式对应的具体关系进行分解的具体表现。
例4.21 设关系模式R(A, B, C),F={A->B,B->C},r是R(U)满足F的一个具体关系,如下表所示。下面,我们将R作出几个不同的分解,看看会出现什么样的问题
⑴ 将R分解为ρ1={R1(A), R2(B), R3(C)},则相应关系r被分解为三个关系,虽然从范式的角度看,关系r1,r2,r3都是4NF,但这样的分解显然是不可取的。因为它不仅不能保持F,即从分解后的?1无法得出A?B,或B?C这种函数依赖,也不能使r得到“恢复”,这里所说的“恢复”意指无法通过对关系r1,r2,r3的连接运算操作得到与r一致的元组,甚至无法回答最简单的查询要求。
⑵ 将R分解为ρ2={R4(A,B), R5(A,C) },对应关系r分解为r4,r5。这样分解后问题虽然少了一些,但由于不保持B->C,仍然存在插入和删除异常等问题。由表4.14可知,r通过 得到恢复,即r= 。这样的分解称为无损连接分解。
⑶ 将R分解为ρ3={R5(A,C),R6(B,C)},对应关系r分解为r5,r6。则函数依赖A->B不被保持,而且r? 。此外,仍然存在插入和删除异常等问题。
⑷ 将R分解为ρ4={R4(A,B),R6(B,C)},对应关系r分解为r4,r6。这是最好的一种分解,既保持了函数依赖F={A->B,B->C} (这样的分解称为保持函数依赖的分解),又可得到r= 。且不存在插入和删除异常等问题。
从上述实例
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
中我们可以看到,一个关系模式的分解可以有几种不同的评判标准:
⑴分解具有无损连接性;{仍然存在插入和删除异常问题}
⑵分解保持函数依赖;{也存在插入和删除异常等问题};
⑶ 分解既保持函数依赖,又具有无损连接性。{最好的}。
关系r的三种分解
2.无损连接
定义4.18 设R(U)是一关系模式,F是R(U)满足的一个函数依赖集,将R(U)分解成关系模式ρ={R1(U1), R2(U2), …, Rk(Uk)},U=U1∪U2∪…∪Uk。如果对R(U)中满足F的每一个具体关系r都有则称这个分解相对于F具有无损连接性(Lossless Join Decomposition),简称ρ为无损连接分解,即r为它自己在Ui上投影的自然连接。r的投影连接表达式 用mρ(r)表示,即 称为关系r的投影连接变换式。在一般情况下,r和mρ(r)不一定相等。对于关系模式R(U)关于F的无损连接条件是:任何满足F的关系r,有r=mρ(r)。
3.无损连接的测试
由于分解不一定具有无损连接性,因此,如何测试一个模式的分解具有无损连接性是一个很重要的问题。
例4.22 设关系模式R(A, B, C)的一个关系为r,将R(A, B, C)分解成两个模式R1(A, B)和R2(B,C)后,关系r相应分解为关系r1,r2,它们是r在相应的模式属性上投影得到。
关系r及其投影
现在利用r1和r2的自然连接运算计算mρ(r),其结果如下表所示,并与上表中关系r比较可以发现r包含于 mρ(r),所以R(A, B, C)分解成R1(A, B),R2(B, C)不是具有无损连接性的分解。
关系r1与关系r2的自然连接
如果一个关系模式的分解不是无损连接分解,那么分解后的关系通过自然连接运算无法恢复到分解前的关系。证关系模式分解具有无损连接性求在对模式进行分解时,必须利用该模式属性间函数依赖的性质,并通过适当的方法判别其分解是否为无损连接分解,以保证最终使用的分解的无损连接性。
算法4.2 无损连接的测试。
输入:关系模式R(U),其中U={A1, A2, …, An},R(U)上成立的函数依赖集F和R(U)的一个分解ρ={R1(U1), R2(U2), …, Rk(Uk)},其中U=U1∪U2∪…∪Uk。
输出:ρ相对于F具有或不具有无损连接性的判断。
计算方法和步骤:
⑴构造一张k行n列的表格,每列对应一个属性Aj(j=1, 2, …, n),每行对应一个模式Ri(Ui) 的属性集合(i=1, 2, …, k)。如果Aj在Ui中,那么在表格的第i行第j列处境上符号aj,否则填上符号bij,
⑵ 反复检查F的每一个函数依赖,并修改表格中的元素,直到表格不能修改为止。其方法如下:
取F中的函数依赖X->Y,如果表格中有两行在X分量上相等,在Y分量上不相等,那么修改Y分量上的值,使这两行在Y分量上也相等,具体修改分两种情况:
①如果Y的分量中有一个是aj,那么另一个也修改成aj,
②如果Y的分量中没有aj,那么用下标i较小的那个bij替换另一个符号。
⑶ 若修改结束后的表格中有一行是全a,即al, a2, …, an,那么?相对于F是无损连接分解,否则,ρ相对于F不是无损连接分解。
定理4.13 如果R(U)的分解为ρ={Rl(U1),R2(U2)},其中U=U1∪U2,F为R(U)所满足的函数依赖集合,则分解ρ是无损连接的充分必要条件为(U1∩U2)->(U1-U2)或者(U1∩U2)->(U2-U1)成立。
此定理表明,当模式R分解成两个关系模式Rl(U1)和R2(U2)时,如果其公共属性能函数决定U1或U2中的其它属性,这样的分解就是无损连接的。
4.保持函数依赖的分解
⑴ 对关系模式分解的无损连接性要求是必要的,因为它保证了关系模式的任何一个具体关系能由它自己的那些投影进行自然连接得到恢复。
⑵ 例4.21说明,仅要求关系模式分解具有无损连接性是不够的。如果关系模式在分解后不能保持函数依赖,那么在数据库中仍然会出现插入和删除等异常现象。因此,保持关系模式分解前后的函数依赖集不变,即从关系模式R(U)到ρ={R1(U1), R2(U2), …, Rk(Uk)}的分解,应使函数依赖集F被所有的所蕴涵,这就是保持函数依赖问题。
设F是属性集U上的函数依赖集,Z是U上的一个子集,F在Z上的一个投影用?Z(F)表示,定义为:πZ(F)={X->Y | (X->Y)∈F+且XY包含于Z}
定义4.19 设关系模式R(U)的一个分解ρ={R1(U1), R2(U2), …, Rk(Uk)},F是R(U)满足的函数依赖集,如果,则称分解ρ保持函数集F,简称ρ保持函数依赖。
由定义可知,检验一个分解是否保持函数依赖,就是检验函数依赖集G=是否覆盖函数依赖集F,即对于任意一个函数依赖X->Y∈F是否由G根据Armstong公理导出,而由定理4.3可知,即是要检验是否有 。
由以上分析可得检验一个分解是否保持函数依赖的算法。
算法4.3 函数依赖测试
输入:R(U,F)和ρ={R1(U1), R2(U2), …, Rk(Uk)}
输出:ρ是否保持F的判断结果。
算法步骤:
⑴ 令G= ,F=F-G,Result=True
⑵ 对于F中的第一个函数依赖X->Y,计算 并令F=F-{X->Y};
⑶ 若 ,则令Result=False,转⑷
否则,若F≠空集,转⑵,否则,转⑷;
⑷ 若Result=True则?保持函数依赖F,否则?不保持函数依赖F。
关于关系模式的分解有以下几个重要事实:
⑴若要求分解保持函数依赖,那么模式分解总可以达到3NF,但不一定能达到BCNF。
⑵若要求分解既保持函数依赖,又具有无损连接性,可以达到3NF,但不一定能达到BCNF。
⑶ 若要求分解具有无损连接性,那一定可达到4NF。