函数依赖(数据库)

时间：2022-12-26 10:30:01 | 来源：信息时代

时间：2022-12-26 10:30:01 来源：信息时代

    函数依赖 : 关系数据库中的一个重要的语义约束,它给出了关系模式中属性间的语义依赖关系,它在关系模式规范化,关系模式分解等方面起了巨大的作用。
函数依赖是Codd在1970年首先提出的。如果R是一个关系模式,X,YR, 则表达式X→Y称为R上的一个函数依赖,读作Y函数依赖于X,或X函数决定Y。如果r是R上的关系,且使(∀u∈r)(∀v∈r)(u[X]=v[X]⇒u[Y]=v[Y])为真,则称r适合函数依赖X→Y,或称r中存在着函数依赖X→Y。若∑是R上函数依赖的集合,r适合∑中的每一个函数依赖,则称r适合∑。如果R是一个关系模式,∑是R上函数依赖的集合,则称二元组(R,∑)为函数依赖模式。如果σ是R上的一个函数依赖,而R上的任意一个关系r只要适合∑就一定适合σ,则称∑蕴涵σ,记作∑⊧σ。∑蕴涵的所有函数依赖的集合记作∑^*,即∑^*＝{σ|∑⊧σ}。
函数依赖的蕴涵可用推导公理系统逐步推出。从∑推出σ记作∑⊦σ。这个公理系统是Armstrong于1974年给出的,它包括以下3个规则:
FD1: YXR则∅⊦X→Y;
FD2:若MR,则{X→Y}⊦XM→YM(用XM表示X∪M,余同);
FD3: {X→Y,Y→Z}⊦X→Z。
由这3个基本规则还可导出以下的常用规则:
FD4: {X→Y, Y→Z}⊦X→YZ;
FD5: {X→Y, WY→Z}⊦XW→Z;
FD6: ZY则{X→Y}⊦X→Z。
Armstrong于1974年成功地证明了该系统是有效完备的。有效是指该系统推出的函数依赖一定都是被蕴涵的, 即∑⊦σ⇒∑⊧σ。完备是指被蕴涵的函数依赖一定都可以从该系统推出, 即∑⊧σ⇒∑⊦σ。由于公理系统有效完备,所以在应用时推导规则中的⊦全可用⊧来代替。
判别函数依赖蕴涵的另一种方法是计算函数依赖左部X对∑的闭包X_∑⁺,x_∑⁺的定义是X_∑⁺＝{A∈U|∑⊦X→A}。X_∑⁺的计算方法请参看文献[1]。X_∑⁺的一个重要性质是: 若X→Z可从∑推出,则ZX_∑⁺;若X→Z不能从∑推出,则Z⊈X_∑⁺。因此,由公理系统的有效完备性可知,给定一个函数依赖X→Z,只要计算其左部X对∑的X_∑⁺,若其右部Z是X_∑⁺的子集,则X→Z被∑蕴涵,否则不被蕴涵。
两个函数依赖集合∑₁及∑₂,如果∑₁中的每个函数依赖σ被∑₂所蕴涵则称∑₂蕴涵∑₁; 若∑₂蕴涵∑₁且∑₁也蕴涵∑₂,则称∑₁与∑₂等价,也称∑₂是∑₁的一个覆盖(根据对称∑₁也是∑₂的覆盖)。我们用∑⁺表示从∑出发,用Armstrong公理系统推出的函数依赖集合,则由Armstrong公理系统的完备性知,当且仅当X₁⁺＝X₂⁺时∑₁与∑₂等价。
例如,∑={A→BC,A→D,DC→E}与∑`={A→BCE,A→ABD,CD→E}等价,它们互为覆盖,但∑与∑″={A→BCDE}不等价,因为(CD→E)∉(∑″)⁺。
判定两个函数依赖集合是否等价的算法可见文献[1]。
一个函数依赖集合可以是无冗余的、既约的、正则的、最小的、最优的等等。
设∑是一个函数依赖集合,如果∑的任何真子集都不与∑等价,则称∑是无冗余的。
例如,∑={AB→C,A→B,A→C},∑′={AB→C,A→B, B→C}, 易知它们等价, 但∑⊂∑,所以∑是冗余的。再令∑″={A→B,B→C},也容易判定∑″与∑′等价, 而∑″⊂∑′, 所以∑′也是冗余的。 由于{A→B}不蕴涵B→C,所以{A→B}⁺≠∑″,及{B→C}不蕴涵A→B,所以{B→C}⁺≠∑″,这样可得∑″是无冗余的。
设(X→Y)∈∑,如果存在一个属性A∈X,使得(∑-{X→Y})∪{X→Z}与∑等价,这里Z=X-{A},则称A是左多余属性。如果存在一个属性B∈Y,使得(∑-{X→Y})∪{X→W}与∑等价,这里W=Y-{B},则称B是右多余属性。如果(X₁→Y₁)∈∑,X₁中不含有左多余属性,则称X₁→Y₁是左既约的。如果,Y₁中不含有右多余属性,则称X₁→Y₁是右既约的。如果X₁→Y₁既是左既约的又是右既约的,则称X₁→Y₁是既约的。如果∑中每个函数依赖都是左既约的(右既约的,既约的),则称∑是左既约的(右既约的,既约的)。
例如,下列函数依赖集合∑₁＝{A→BC,B→C,AB→D}既不是左既约的也不是右既约的,∑₂＝{A→B,B→C,A→D}是左既约的,∑₃＝{A→B,B→C,AB→D}是右既约的,∑₄＝{A→B,B→C,A→D}既是左既约的又是右既约的,因此是既约的。
设∑是一个函数依赖集合,如果∑中的函数依赖右边都只有一个属性,即都是形如X→A的函数依赖,而且∑是无冗余的,是左既约的(请注意这个函数依赖集合中的函数依赖右部都只有一个属性,所以这些函数依赖也都是右既约的,于是也都是既约的),则称∑是正则的。又如果∑是∑′的覆盖而且是正则的,则称∑是∑′的正则覆盖。
例如,容易验证∑={A→B,A→C,A→D,A→E,BI→J}是正则的。而且还容易验证∑是∑={A→BCE,AB→DE,BI→J}的正则覆盖。
正则函数依赖集合一定也是既约函数依赖集合。
设∑是一个函数依赖集合,如果任何一个与∑等价的函数依赖集合∑′所包含的函数依赖个数都不少于∑中的函数依赖个数,则称∑是最小的。显然,任何最小函数依赖集合一定是无冗余的,因为若其中有冗余的函数依赖,那么把它去掉就会得到一个具有更少函数依赖的等价的函数依赖集合,这与该集合的最小性矛盾。但是无冗余函数依赖集合不一定是最小的。例如∑={A→BC,B→A,AD→E,BD→I}是无冗余的,但仍有∑₁＝{A→BC,B→A,AD→EI}与它等价。
每个函数依赖集合都有与其等价的正则最小函数依赖集合。它的计算方法请见模式分解条目。
设∑是一个函数依赖集合,如果不存在它的覆盖∑′能使‖∑′‖<‖∑‖,则称∑是最优的。这里‖∑‖是∑中出现的属性个数,重复出现,重复计算。例如∑={A→B,AB→C},则‖∑‖=5。如果∑是∑₁的覆盖,而且是最优的,则称∑是∑₁的最优覆盖。
例如,∑={EC→D,AB→E,E→AB},∑₁＝{ABC→D,AB→E,E→AB},这里∑就是∑₁的最优覆盖(注意,‖∑‖=9,‖∑₁‖=10,而且不会有任何与∑₁等价的∑,会使‖∑‖<9)。另外,我们还看到,∑₁是最小的,既约的,但它不是最优的。
反之,可以证明若∑是一个最优函数依赖集合,则∑是既约的,而且也是最小的。
非经典关系数据库中的函数依赖被发展成更多的样式: 时态函数依赖、点态序函数依赖、字典序函数依赖、Fuzzy函数依赖、粗糙函数依赖、对象关系数据库中的路径函数依赖、局部函数依赖、整体函数依赖、含空值的函数依赖、单依赖、函数依赖的可加性等详见文献[2]。