多值依賴(數(shù)據(jù)庫)

時(shí)間：2022-12-21 02:30:01 | 來源：信息時(shí)代

時(shí)間：2022-12-21 02:30:01 來源：信息時(shí)代

    多值依賴 : 關(guān)系數(shù)據(jù)庫中的一個(gè)重要的數(shù)據(jù)約束。它給出關(guān)系模式屬性間多值語義的函數(shù)依賴關(guān)系。多值依賴是在1976～1978年間由Zaniolo、Fagin、Delobel等分別獨(dú)立地提出的。多值依賴也存在著蘊(yùn)涵及等價(jià)問題。受函數(shù)依賴的啟發(fā),在多值依賴?yán)碚撗芯康囊婚_始(1977年),Beeri就給出了有效完備的蘊(yùn)涵推導(dǎo)公理系統(tǒng)。而且Beeri還發(fā)現(xiàn)多值依賴存在著一種依賴基。依賴基的理論研究加深了人們對多值依賴的認(rèn)識。針對多值依賴,人們還提出了第4范式,并證明了存在著多值依賴的數(shù)據(jù)庫只有屬于第4范式才能沒有弊病。Fagin(1977年)、Delobel(1978年)、Tanaka(1978年)等研究了嵌入的多值依賴的很多理論問題,這種多值依賴不是對整個(gè)關(guān)系模式,而只是對它的一個(gè)子集的。他們研究出了很多理論成果。不過在研究嵌入多值依賴的推導(dǎo)公理系統(tǒng)時(shí),卻發(fā)現(xiàn)無論如何也給不出完備的公理系統(tǒng)。1982年,Sagiv及Walecka提出了一種子集依賴,借助子集依賴,證明了嵌入的多值依賴不存在完備的公理系統(tǒng)。
設(shè)R是一個(gè)關(guān)系模式,X,YR, 記號X→→Y表示R上的一個(gè)多值依賴,讀作“Y多值依賴于X”或“X多值地決定Y”。r是R上的一個(gè)關(guān)系,如果對任何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。
根據(jù)這個(gè)定義容易看出,若關(guān)系r適合函數(shù)依賴X→Y(函數(shù)依賴請參看函數(shù)依賴條目),令w₁＝v,w₂＝u則r也適合多值依賴X→→Y,所以函數(shù)依賴是多值依賴的特殊情況。
若R是一個(gè)關(guān)系模式,∑是R上的函數(shù)依賴及多值依賴的集合,則稱二元組(R,∑)為一個(gè)多值依賴模式; 若r是R上的關(guān)系,而且r適合∑中的每一個(gè)依賴,則稱r適合∑,并稱r是(R,∑)的一個(gè)實(shí)例; 若X,YR, 而(R,∑)中的每一個(gè)實(shí)例r都適合X→→Y, 則稱蘊(yùn)涵X→→Y, 記作∑⊧X→→Y?！铺N(yùn)涵的所有函數(shù)依賴及多值依賴的集合記作∑^*。∑^*中的函數(shù)依賴與多值依賴可用推導(dǎo)公理系統(tǒng)逐步推出。 從∑推出σ記作∑⊦σ。函數(shù)依賴與多值依賴的蘊(yùn)涵推導(dǎo)公理系統(tǒng)如下:
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。
該系統(tǒng)是有效完備的。有效是指該系統(tǒng)推出的函數(shù)依賴與多值依賴一定都是被蘊(yùn)涵的, 即∑⊦σ⇒∑⊧σ,完備是指被蘊(yùn)涵的函數(shù)依賴與多值依賴一定都可以從該系統(tǒng)推出, 即∑⊧σ⇒∑⊦σ。
如果(R,∑)是一個(gè)多值依賴模式,X={A₁,…,A_n}R,則存在R—X的一個(gè)劃分Y₁, …,Y_k,使得當(dāng)且僅當(dāng)Y是{Y₁,…,Y_k,{A₁},…,{A_n}}中某些集合的并集時(shí),∑X→→Y。我們稱{Y₁,…,Y_k,{A₁},…,{A_n}}為X(相對于(R,∑))的依賴基。依賴基可用算法求出,已證明,該算法是多項(xiàng)式的。
若R`⊂R, X, YR`, 令Z=R`—X—Y, 則記號X→→Y|Z,表示R上一個(gè)嵌入的多值依賴。若r是R上的一個(gè)關(guān)系,r[R`]作為R`上的關(guān)系,適合R`上的多值依賴X→→Y(從而X→→Z),則稱r適合R上的嵌入的多值依賴X→→Y|Z。
設(shè)∑是R上的嵌入的多值依賴的集合,X→→Y|Z是R上的嵌入的多值依賴。如果R的每一個(gè)適合∑的關(guān)系全適合X→→Y|Z,則稱∑蘊(yùn)涵X→→Y|Z。嵌入的多值依賴有以下的蘊(yùn)涵推導(dǎo)公理系統(tǒng): 設(shè)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
這個(gè)公理系統(tǒng)是有效的,但不完備。借助子集依賴可證明嵌入的多值依賴不存在完備的公理系統(tǒng)。