[数据结构与算法]函数依赖

前端之家收集整理的这篇文章主要介绍了[数据结构与算法]函数依赖前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

如果我们要设计关系型数据库的表模式,则很有可能会出现冗余,为了避免这种情况,我们需要一些规则,这些规则称为依赖。

函数依赖简单地说就是属性集A推导出属性集B,比如

给定这些规则之后,如果某个关系能够满足给定的函数依赖,则称关系R满足函数依赖F;

在下面我们会介绍一系列的范式以及分解算法;

函数依赖的分解合并规则

是等价的(可以互相转化的),第一个式子替换第二个式子称为合并规则,第二个式子替换第一个式子称为分解规则;

平凡函数依赖:如果A-->B,A是B的超集,则称此函数依赖为平凡的。

平凡依赖规则:如果A-->B,则可以将其变为A-->(B-A∩B),这样可以消除冗余;


键的函数依赖定义:

(1)如果存在某个属性集,能够蕴含全部的属性

(2)这个属性集的任意真子集都不能蕴含全部属性

则称这个属性集为键;

函数依赖习题

平凡依赖规则

举例:name,age --->name,course,根据平凡依赖规则,可以简化为 name,age -->course.

异常

如果一个关系的模式没有设计好,则会出现异常。异常的类型为:

(1)冗余:一个属性的值多次出现,比如:

(2)更新异常:上图的关系就存在更新异常,因为如果需要更新database这门课为database concept,则需要将左边的database全部更新为database concept;

(3)删除异常:上图的关系存在删除异常,因为将Avi、Hank、Sudarshan老师删除,则会出现database这门课消失了,但实际上数据库这门课永远不会消失,而只是老师辞职了。



属性闭包算法

举例:

闭包的应用

1.给定函数依赖集F1,是否可以推断出函数依赖f:A-->B?

只需要求出{A}+是否包含B,如果包含,则说明F1能够推断出f,否则不能;

举例:

2.判断某个属性集是否为键?

如果要证明属性集是超键,则只需要计算此属性集的闭包,看闭包中是否包含全部的属性

但是如果需要证明属性集是候选键,则第一步需要证明是超键,第二步需要证明从属性集中任意去掉一个属性,此属性集就不是超键;

3.给出一些术语.

给定一个函数依赖集A;

A的基本集:和A等价的函数依赖集;

A的最小化基本集:满足(1)函数依赖的右边只有单个属性(2)删除任意一个函数依赖都不将是基本集(3)从函数依赖的左边删除任意一个属性,则不将是基本集;

4.投影函数依赖

给定一个关系和满足的函数依赖F,求对部分属性投影后,哪些函数依赖满足。

比如:原本属性为A,B,C的关系,投影到A,B后,还有哪些函数依赖成立?

简单地说就是:

(1)首先计算单属性的闭包,比如{A}的闭包为{B,C},如果我们的投影为{A,B},则需要包含A-->B,而不包含A-->C;(如果存在某个属性集能够蕴含所有属性,则我们就不需要再求此属性集的闭包)

(2)接着计算双属性,三属性,四属性.....;

(3)在求出的基本集中最小化;

--如果投影后的某个函数依赖能够通过投影后的其他函数依赖推出,则删除

比如:{A-->C,A-->B,B-->C},删除A-->C,因为此函数依赖能够通过其他函数依赖推导;

--如果某个函数依赖A-->B,删除A中某个属性后仍然在投影的函数依赖中成立,则删除

比如:投影后的函数依赖为{AC-->B,A-->B},则把{AC-->B}删除,因为如果删除C即A-->B 能够从投影的函数依赖中推出;

举例:


5.判断无损分解

如果R1∩R2是R1或R2的超码,则R上的分解(R1,R2)是无损分解。



Armstrong公理


下面我们会说到BCNF分解和3NF分解,而分解也是有评判标准的:

(1)消除异常;

(2)无损连接:分解后再连接是否和原来的关系一致;

用chase检验法则;

(3)保持依赖:FD的投影在分解后的关系上成立,但是连接后的关系不满足原始FD;

BCNF满足(1)和(2),3NF满足(1)(2)(3)


Chase检验法则

判断分解后再自然连接是否还是原始的关系;


思想:自然连接后的每个元组都属于原始关系;

如果将关系投影到Si后再进行自然连接,就会得到一个所有分量都不带下标的元组,这个元组不在R中,则连接为无损的;

举例:


保持依赖

思想:FD投影在分解的关系中成立,但是自然连接后不能满足原始的FD

举例:


BCNF

当关系满足如果R中非平凡的函数依赖的左边都是超键,则此关系R属于BCNF;

性质:任何一个二元关系都满足BCNF

证明:如果函数依赖集中存在A-->B,则我们可以说A-->AB,因此A一定是超键;

BCNF分解

注:BCNF分解是无损分解

while(找到违反BCNF的函数依赖){

找出违反BCNF的函数依赖A-->B,先计算A的闭包,且用A的闭包(除去A)替换B,并将其分解为{A+}和{AU(R-(A+)}; //比如A-->B ,而{A}+={A,C},则用A-->BC替换A-->B;

求出分解后的关系满足的投影FD集合;

再看分解后的关系的FD集合是否满足BCNF,如果不满足,则继续分解。

}

举例:



3NF

注:3NF是能够无损连接且保持依赖;

放松了BCNF的要求,多出的一个条件为:如果A-->B,则B-A为候选键的一部分(即使在不同的候选键中),则满足3NF;

这里我们对上句中的红色标注部分进行解释,看一个例子:

比如:存在函数依赖A-->BC,{AB}{AC}分别为候选键,而BC-A={BC},B属于候选键{AB},C属于候选键{AC},但是A-->BC仍然满足3NF;

属性:一个属性属于某个候选键;

比如:{AC}为候选键,则A为主属性,C也为主属性

3NF分解算法

举例:



1NF

每个属性都保持原子性;

2NF

满足1NF,且每一个非主属性都完全函数依赖于R的主码;


多值依赖

引入多值依赖的原因

从上图中可以知道,此关系的候选键为(name,street,city,title,year),因此不存在任何非平凡的函数依赖,因此遵守BCNF,但是我们可以很容易看出,(street、city)和(title、year)是独立的;放在一个关系中是冗余的;

因此多值依赖的产生就是源于此;我们可以将上图的关系根据4NF分解算法分解关系;

多值依赖(MVD)定义

A1A2....An-->-->B1B2....Bm,则说明

(1)给定A1A2...An的值,B1B2...Bm属性独立于(U-A-B)属性

(2)给定R中的两个元组a、b,他们的A属性相同,则必然存在第三个元组c,使得c[A]=a[A]=b[A],c[B]=a[B],c[U-A-B]=b[U-A-B];

多值依赖性质

(0)多值依赖其实就是FD的升级,即如果A-->B成立,则A-->-->B也成立;

(1)平凡MVD:如果B是A的子集,则A-->-->B成立;

(2)附加平凡MVD:如果关系R(A,B),则A-->-->B成立;

(3)传递MVD:如果A-->-->B,B-->-->C,则A-->-->C成立;

(4)MVD不满足分解规则:

(5)如果A-->-->B,则A-->-->(R-A-B)成立;


4NF

应用于MVD,而不是一般的FD;条件和BCNF差不多;

定义:如果存在非平凡的A-->-->B,且A一定是超键,则为4NF;

4NF分解算法

1.找违反4NF的MVD;

2.按照A-->-->B 分解为{AB} {R-A-B};

3.计算投影FD;

4.继续找违反的MVD,分解.....;

总结:


转自:http://blog.csdn.net/xiazdong/article/details/7517438

猜你在找的设计模式相关文章