(软考软件设计师)模式分解的无损连接性之深入剖析

(软考软件设计师)模式分解的无损连接性之深入剖析

ID:12751633

大小:82.00 KB

页数:6页

时间:2018-07-18

(软考软件设计师)模式分解的无损连接性之深入剖析_第1页
(软考软件设计师)模式分解的无损连接性之深入剖析_第2页
(软考软件设计师)模式分解的无损连接性之深入剖析_第3页
(软考软件设计师)模式分解的无损连接性之深入剖析_第4页
(软考软件设计师)模式分解的无损连接性之深入剖析_第5页
资源描述:

《(软考软件设计师)模式分解的无损连接性之深入剖析》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、书山有路勤为径模式分解的无损连接性之深入剖析1.无损连接分解的形式定义  无损连接分解的形式定义如下:设R是一个关系模式,F是R上的一个函数依赖(FD)集。R分解成数据库模式δ={R1,……,Rk}。如果对R中每一个满足F的关系r都有下式成立:  那么称分解δ相对于F是“无损连接分解”,否则称为“损失连接分解”。其中表示自然连接。  从上述形式定义中可知,若直接根据定义来判断某个分解是否具有无损连接性,那么就得“对R中每一个满足F的关系r”进行测试,看是否满足上面的等式,这显然不可操作,因为“对R中每一个满足F的关系r

2、”进行测试就意味着“对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

3、)把表格看成模式R的一个关系,反复检查F中每个FD在表格中是否成立,若不成立,则修改表格中的元素。修改方法如下:对于F中一个FD:X→Y,如果表格中有两行在X分量上相等,在Y分量上不相等,那么把这两行在Y分量上改成相等。如果Y的分量中有一个是aj,那么另一个也改成aj;如果没有aj,那么用其中的一个bij替换另一个(尽量把ij改成较小的数,亦即取i值较小的那个)。FROM:及时雨书山有路勤为径  若在修改的过程中,发现表格中有一行全是a,即a1,a2,…,an,那么可立即断定p相对于F是无损连接分解,此时不必再继续修改

4、。若经过多次修改直到表格不能修改之后,发现表格中不存在有一行全是a的情况,那么分解就是有损的。特别要注意,这里有个循环反复修改的过程,因为一次修改可能导致表格能继续修改。  修改过程中要特别注意,若某个bij被改动,那么它所在列的所有bij都需要做相应的改动。为了明确这一点,举例说明。例如,我们根据FD“H→I”、“K→L”来修改表格之前时的表格如表1所示(已经过多次修改,非初始表,空的单元表示省略):  表1 HIJKLR1 b12  b35R2a1a2 a4b25R3a1b12 a4b35R4 b12  b35  

5、R2、R3所在行的H分量都为a1,根据FD“H→I”,需要修改这两行对应的I分量,而R2所在行的I分量为a2,因此,要将R3所在行的I分量b12修改为a2,注意到,R1、R4所在行的H分量也为b12,因此,这两行对应的I分量也必须修改为a2。R2、R3所在行的K分量都为a4,根据FD“K→L”,需要修改这两行对应的L分量,于是将R3所在行的L分量b35修改为较小的b25,同时注意到,R1、R4所在行的L分量也为b35,因此,这两行对应的L分量也必须修改为b25。修改后的表格如表2所示:  表2 HIJKLR1 a2  

6、b25R2a1a2 a4b25R3a1a2 a4b25R4 a2  b25  【例题】(软件设计师2002年上午试题38)FROM:及时雨书山有路勤为径  设关系模式R为R(H,I,J,K,L),R上的一个函数依赖集为F={H→J,J→K,I→J,JL→H},分解(38)是无损连接的。  供选择的答案:  (38)A.p={HK,HI,IJ,JKL,HL}B.p={HIL,IKL,IJL}  C.p={HJ,IK,HL}D.p={HI,JK,HL}  试题分析:  根据上述判断方法,我们列出选项B(分解成三个关系模式R

7、1(HIL)、R2(IKL)、R3(IJL))的初始表如表3所示:  表3选项B的初始表 HIJKLHILa1a2b13b14a5IKLb21a2b23a4a5IJLb31a2a3b34a5  对于函数依赖集中的H→J、J→K对表3进行处理,由于属性列H和属性列J上无相同的元素,所以无法修改。但对于I→J在属性列I上对应的1、2、3行上全为a2元素,所以,将属性列J的第一行b13和第二行b23改为a3。修改后如表4所示:【例题】(表4选项B的中间表 HIJKLHILa1a2a3b14a5IKLb21a2a3a4a5IJ

8、Lb31a2a3b34a5  对于函数依赖集中的JL→H在属性列J和L上对应的1、2、3行上为a3、a5元素,所以,将属性列H的第二行b21和第三行b31改为a1。修改后如表5所示:  表5选项B的结果表FROM:及时雨书山有路勤为径 HIJKLHILa1a2a3b14a5IKLa1a2a3a4a5IJLa1a2a3b34a5  

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。