多值依赖(数据库)

时间：2022-12-21 02:30:01 | 来源：信息时代

时间：2022-12-21 02:30:01 来源：信息时代

    多值依赖 : 关系数据库中的一个重要的数据约束。它给出关系模式属性间多值语义的函数依赖关系。多值依赖是在1976～1978年间由Zaniolo、Fagin、Delobel等分别独立地提出的。多值依赖也存在着蕴涵及等价问题。受函数依赖的启发,在多值依赖理论研究的一开始(1977年),Beeri就给出了有效完备的蕴涵推导公理系统。而且Beeri还发现多值依赖存在着一种依赖基。依赖基的理论研究加深了人们对多值依赖的认识。针对多值依赖,人们还提出了第4范式,并证明了存在着多值依赖的数据库只有属于第4范式才能没有弊病。Fagin(1977年)、Delobel(1978年)、Tanaka(1978年)等研究了嵌入的多值依赖的很多理论问题,这种多值依赖不是对整个关系模式,而只是对它的一个子集的。他们研究出了很多理论成果。不过在研究嵌入多值依赖的推导公理系统时,却发现无论如何也给不出完备的公理系统。1982年,Sagiv及Walecka提出了一种子集依赖,借助子集依赖,证明了嵌入的多值依赖不存在完备的公理系统。
设R是一个关系模式,X,YR, 记号X→→Y表示R上的一个多值依赖,读作“Y多值依赖于X”或“X多值地决定Y”。r是R上的一个关系,如果对任何u,v∈r,只要u[X]=v[X],就有w₁,w₂∈r满足:
(1) w₁[X]=w₂[X]=u[X]=v[X]。
(2) w₁[Y]=u[Y]且w₁[Z]=v[Z]。
(3) w₂[Y]=v[Y]且w₂[Z]=u[Z]。
(这里,Z=R-(X∪Y))
则称r适合X→→Y,或称在r中存在着X→→Y。
根据这个定义容易看出,若关系r适合函数依赖X→Y(函数依赖请参看函数依赖条目),令w₁＝v,w₂＝u则r也适合多值依赖X→→Y,所以函数依赖是多值依赖的特殊情况。
若R是一个关系模式,∑是R上的函数依赖及多值依赖的集合,则称二元组(R,∑)为一个多值依赖模式; 若r是R上的关系,而且r适合∑中的每一个依赖,则称r适合∑,并称r是(R,∑)的一个实例; 若X,YR, 而(R,∑)中的每一个实例r都适合X→→Y, 则称蕴涵X→→Y, 记作∑⊧X→→Y。∑蕴涵的所有函数依赖及多值依赖的集合记作∑^*。∑^*中的函数依赖与多值依赖可用推导公理系统逐步推出。 从∑推出σ记作∑⊦σ。函数依赖与多值依赖的蕴涵推导公理系统如下:
MD1:YXR, 则∅⊦X→Y;
MD2:ZR}, 则{X→Y⊦XZ→YZ;
MD3: {X→Y, Y→Z}⊦Y→Z;
MD4: {X→→Y}⊦X→→R—X—Y;
MD5: {X→→Y},NMR⊦XM→→YN;
MD6: {X→→Y, Y→→Z}⊦X→→Z—Y;
MD7: {X→Y}⊦X→→Y;
MD8:{X→→Y,M→Z},ZY,M∩Y=∅⊦Y→Z。
该系统是有效完备的。有效是指该系统推出的函数依赖与多值依赖一定都是被蕴涵的, 即∑⊦σ⇒∑⊧σ,完备是指被蕴涵的函数依赖与多值依赖一定都可以从该系统推出, 即∑⊧σ⇒∑⊦σ。
如果(R,∑)是一个多值依赖模式,X={A₁,…,A_n}R,则存在R—X的一个划分Y₁, …,Y_k,使得当且仅当Y是{Y₁,…,Y_k,{A₁},…,{A_n}}中某些集合的并集时,∑X→→Y。我们称{Y₁,…,Y_k,{A₁},…,{A_n}}为X(相对于(R,∑))的依赖基。依赖基可用算法求出,已证明,该算法是多项式的。
若R`⊂R, X, YR`, 令Z=R`—X—Y, 则记号X→→Y|Z,表示R上一个嵌入的多值依赖。若r是R上的一个关系,r[R`]作为R`上的关系,适合R`上的多值依赖X→→Y(从而X→→Z),则称r适合R上的嵌入的多值依赖X→→Y|Z。
设∑是R上的嵌入的多值依赖的集合,X→→Y|Z是R上的嵌入的多值依赖。如果R的每一个适合∑的关系全适合X→→Y|Z,则称∑蕴涵X→→Y|Z。嵌入的多值依赖有以下的蕴涵推导公理系统: 设X, Y, Z, X₁, Y₁, Z₁R, 则:
MD1:若X→→Y|Z, Y₁Y, Z₁Z,则X→→Y₁|Z₁
MD2: 若X→→Y|Z, YY₁, 且XY→→Z|(Y₁-Y)Z,则X→→Y₁|Z
这个公理系统是有效的,但不完备。借助子集依赖可证明嵌入的多值依赖不存在完备的公理系统。