函數(shù)依賴(數(shù)據(jù)庫)

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

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

    函數(shù)依賴 : 關(guān)系數(shù)據(jù)庫中的一個(gè)重要的語義約束,它給出了關(guān)系模式中屬性間的語義依賴關(guān)系,它在關(guān)系模式規(guī)范化,關(guān)系模式分解等方面起了巨大的作用。
函數(shù)依賴是Codd在1970年首先提出的。如果R是一個(gè)關(guān)系模式,X,YR, 則表達(dá)式X→Y稱為R上的一個(gè)函數(shù)依賴,讀作Y函數(shù)依賴于X,或X函數(shù)決定Y。如果r是R上的關(guān)系,且使(∀u∈r)(∀v∈r)(u[X]=v[X]⇒u[Y]=v[Y])為真,則稱r適合函數(shù)依賴X→Y,或稱r中存在著函數(shù)依賴X→Y。若∑是R上函數(shù)依賴的集合,r適合∑中的每一個(gè)函數(shù)依賴,則稱r適合∑。如果R是一個(gè)關(guān)系模式,∑是R上函數(shù)依賴的集合,則稱二元組(R,∑)為函數(shù)依賴模式。如果σ是R上的一個(gè)函數(shù)依賴,而R上的任意一個(gè)關(guān)系r只要適合∑就一定適合σ,則稱∑蘊(yùn)涵σ,記作∑⊧σ?！铺N(yùn)涵的所有函數(shù)依賴的集合記作∑^*,即∑^*＝{σ|∑⊧σ}。
函數(shù)依賴的蘊(yùn)涵可用推導(dǎo)公理系統(tǒng)逐步推出。從∑推出σ記作∑⊦σ。這個(gè)公理系統(tǒng)是Armstrong于1974年給出的,它包括以下3個(gè)規(guī)則:
FD1: YXR則∅⊦X→Y;
FD2:若MR,則{X→Y}⊦XM→YM(用XM表示X∪M,余同);
FD3: {X→Y,Y→Z}⊦X→Z。
由這3個(gè)基本規(guī)則還可導(dǎo)出以下的常用規(guī)則:
FD4: {X→Y, Y→Z}⊦X→YZ;
FD5: {X→Y, WY→Z}⊦XW→Z;
FD6: ZY則{X→Y}⊦X→Z。
Armstrong于1974年成功地證明了該系統(tǒng)是有效完備的。有效是指該系統(tǒng)推出的函數(shù)依賴一定都是被蘊(yùn)涵的, 即∑⊦σ⇒∑⊧σ。完備是指被蘊(yùn)涵的函數(shù)依賴一定都可以從該系統(tǒng)推出, 即∑⊧σ⇒∑⊦σ。由于公理系統(tǒng)有效完備,所以在應(yīng)用時(shí)推導(dǎo)規(guī)則中的⊦全可用⊧來代替。
判別函數(shù)依賴蘊(yùn)涵的另一種方法是計(jì)算函數(shù)依賴左部X對(duì)∑的閉包X_∑⁺,x_∑⁺的定義是X_∑⁺＝{A∈U|∑⊦X→A}。X_∑⁺的計(jì)算方法請(qǐng)參看文獻(xiàn)[1]。X_∑⁺的一個(gè)重要性質(zhì)是: 若X→Z可從∑推出,則ZX_∑⁺;若X→Z不能從∑推出,則Z⊈X_∑⁺。因此,由公理系統(tǒng)的有效完備性可知,給定一個(gè)函數(shù)依賴X→Z,只要計(jì)算其左部X對(duì)∑的X_∑⁺,若其右部Z是X_∑⁺的子集,則X→Z被∑蘊(yùn)涵,否則不被蘊(yùn)涵。
兩個(gè)函數(shù)依賴集合∑₁及∑₂,如果∑₁中的每個(gè)函數(shù)依賴σ被∑₂所蘊(yùn)涵則稱∑₂蘊(yùn)涵∑₁; 若∑₂蘊(yùn)涵∑₁且∑₁也蘊(yùn)涵∑₂,則稱∑₁與∑₂等價(jià),也稱∑₂是∑₁的一個(gè)覆蓋(根據(jù)對(duì)稱∑₁也是∑₂的覆蓋)。我們用∑⁺表示從∑出發(fā),用Armstrong公理系統(tǒng)推出的函數(shù)依賴集合,則由Armstrong公理系統(tǒng)的完備性知,當(dāng)且僅當(dāng)X₁⁺＝X₂⁺時(shí)∑₁與∑₂等價(jià)。
例如,∑={A→BC,A→D,DC→E}與∑`={A→BCE,A→ABD,CD→E}等價(jià),它們互為覆蓋,但∑與∑″={A→BCDE}不等價(jià),因?yàn)?CD→E)∉(∑″)⁺。
判定兩個(gè)函數(shù)依賴集合是否等價(jià)的算法可見文獻(xiàn)[1]。
一個(gè)函數(shù)依賴集合可以是無冗余的、既約的、正則的、最小的、最優(yōu)的等等。
設(shè)∑是一個(gè)函數(shù)依賴集合,如果∑的任何真子集都不與∑等價(jià),則稱∑是無冗余的。
例如,∑={AB→C,A→B,A→C},∑′={AB→C,A→B, B→C}, 易知它們等價(jià), 但∑⊂∑,所以∑是冗余的。再令∑″={A→B,B→C},也容易判定∑″與∑′等價(jià), 而∑″⊂∑′, 所以∑′也是冗余的。 由于{A→B}不蘊(yùn)涵B→C,所以{A→B}⁺≠∑″,及{B→C}不蘊(yùn)涵A→B,所以{B→C}⁺≠∑″,這樣可得∑″是無冗余的。
設(shè)(X→Y)∈∑,如果存在一個(gè)屬性A∈X,使得(∑-{X→Y})∪{X→Z}與∑等價(jià),這里Z=X-{A},則稱A是左多余屬性。如果存在一個(gè)屬性B∈Y,使得(∑-{X→Y})∪{X→W}與∑等價(jià),這里W=Y-{B},則稱B是右多余屬性。如果(X₁→Y₁)∈∑,X₁中不含有左多余屬性,則稱X₁→Y₁是左既約的。如果,Y₁中不含有右多余屬性,則稱X₁→Y₁是右既約的。如果X₁→Y₁既是左既約的又是右既約的,則稱X₁→Y₁是既約的。如果∑中每個(gè)函數(shù)依賴都是左既約的(右既約的,既約的),則稱∑是左既約的(右既約的,既約的)。
例如,下列函數(shù)依賴集合∑₁＝{A→BC,B→C,AB→D}既不是左既約的也不是右既約的,∑₂＝{A→B,B→C,A→D}是左既約的,∑₃＝{A→B,B→C,AB→D}是右既約的,∑₄＝{A→B,B→C,A→D}既是左既約的又是右既約的,因此是既約的。
設(shè)∑是一個(gè)函數(shù)依賴集合,如果∑中的函數(shù)依賴右邊都只有一個(gè)屬性,即都是形如X→A的函數(shù)依賴,而且∑是無冗余的,是左既約的(請(qǐng)注意這個(gè)函數(shù)依賴集合中的函數(shù)依賴右部都只有一個(gè)屬性,所以這些函數(shù)依賴也都是右既約的,于是也都是既約的),則稱∑是正則的。又如果∑是∑′的覆蓋而且是正則的,則稱∑是∑′的正則覆蓋。
例如,容易驗(yàn)證∑={A→B,A→C,A→D,A→E,BI→J}是正則的。而且還容易驗(yàn)證∑是∑={A→BCE,AB→DE,BI→J}的正則覆蓋。
正則函數(shù)依賴集合一定也是既約函數(shù)依賴集合。
設(shè)∑是一個(gè)函數(shù)依賴集合,如果任何一個(gè)與∑等價(jià)的函數(shù)依賴集合∑′所包含的函數(shù)依賴個(gè)數(shù)都不少于∑中的函數(shù)依賴個(gè)數(shù),則稱∑是最小的。顯然,任何最小函數(shù)依賴集合一定是無冗余的,因?yàn)槿羝渲杏腥哂嗟暮瘮?shù)依賴,那么把它去掉就會(huì)得到一個(gè)具有更少函數(shù)依賴的等價(jià)的函數(shù)依賴集合,這與該集合的最小性矛盾。但是無冗余函數(shù)依賴集合不一定是最小的。例如∑={A→BC,B→A,AD→E,BD→I}是無冗余的,但仍有∑₁＝{A→BC,B→A,AD→EI}與它等價(jià)。
每個(gè)函數(shù)依賴集合都有與其等價(jià)的正則最小函數(shù)依賴集合。它的計(jì)算方法請(qǐng)見模式分解條目。
設(shè)∑是一個(gè)函數(shù)依賴集合,如果不存在它的覆蓋∑′能使‖∑′‖<‖∑‖,則稱∑是最優(yōu)的。這里‖∑‖是∑中出現(xiàn)的屬性個(gè)數(shù),重復(fù)出現(xiàn),重復(fù)計(jì)算。例如∑={A→B,AB→C},則‖∑‖=5。如果∑是∑₁的覆蓋,而且是最優(yōu)的,則稱∑是∑₁的最優(yōu)覆蓋。
例如,∑={EC→D,AB→E,E→AB},∑₁＝{ABC→D,AB→E,E→AB},這里∑就是∑₁的最優(yōu)覆蓋(注意,‖∑‖=9,‖∑₁‖=10,而且不會(huì)有任何與∑₁等價(jià)的∑,會(huì)使‖∑‖<9)。另外,我們還看到,∑₁是最小的,既約的,但它不是最優(yōu)的。
反之,可以證明若∑是一個(gè)最優(yōu)函數(shù)依賴集合,則∑是既約的,而且也是最小的。
非經(jīng)典關(guān)系數(shù)據(jù)庫中的函數(shù)依賴被發(fā)展成更多的樣式: 時(shí)態(tài)函數(shù)依賴、點(diǎn)態(tài)序函數(shù)依賴、字典序函數(shù)依賴、Fuzzy函數(shù)依賴、粗糙函數(shù)依賴、對(duì)象關(guān)系數(shù)據(jù)庫中的路徑函數(shù)依賴、局部函數(shù)依賴、整體函數(shù)依賴、含空值的函數(shù)依賴、單依賴、函數(shù)依賴的可加性等詳見文獻(xiàn)[2]。