鍵(數(shù)據(jù)庫)

時間：2022-12-29 00:30:01 | 來源：信息時代

時間：2022-12-29 00:30:01 來源：信息時代

    鍵 : 關(guān)系模式的一種特殊子集,關(guān)系中的每個對象在其上取的值都是該對象的唯一標(biāo)識。
如果X是函數(shù)依賴模式(R,∑)中R的一個子集,它滿足∑⊧X→R,但對任何一個X的真子集X′都有∑⊧/X′→R,則稱X為(R,∑)的鍵。 由于∑⊧X→R,所以,從函數(shù)依賴的定義知每個元組u在鍵X上的取值u[X]都是每個元組的唯一標(biāo)識。鍵是Codd首先提出的。
一個函數(shù)依賴模式可能有多個鍵。包含在任何一個鍵中的屬性都稱為主屬性,不屬于任何鍵的屬性都稱為非主屬性。
例如,關(guān)系模式CSL{學(xué)號,課程號,課程名,學(xué)習(xí)期限,成績,獎學(xué)金},CSL上的函數(shù)依賴集合∑={課程號→學(xué)習(xí)期限,{學(xué)號,課程號}→成績,成績→獎學(xué)金,課程號→課程名,課程名→課程號}。對于函數(shù)依賴模式(CSL,∑),由Armstrong公理系統(tǒng)(Armstrong公理系統(tǒng)請見函數(shù)依賴條目)可以知:
∑⊧{學(xué)號, 課程號}→成績
∑⊧{學(xué)號, 課程號}→獎學(xué)金
∑⊧{學(xué)號, 課程號}→學(xué)習(xí)期限
∑⊧{學(xué)號, 課程號}→課程名
∑⊧{學(xué)號, 課程號}→課程號
∑⊧{學(xué)號, 課程號}→學(xué)號
以∑⊧{學(xué)號,課程號}→CSL(反復(fù)應(yīng)用Armstrong公理的F4)。
然而∑⊧/學(xué)號→成績及∑⊧/課程號→成績,所以,∑⊧/學(xué)號→CSL及∑⊧/課程號→CSL,所以,{學(xué)號,課程號}是一個鍵。同理,從Armstrong公理系統(tǒng)可知,{學(xué)號,課程名}也是(CSL,∑)的一個鍵,而且容易驗證(CSL,∑)再沒有其他鍵了。于是對于(CSL,∑)有:鍵是{學(xué)號,課程號}及{學(xué)號,課程名},主屬性是: 學(xué)號,課程號,課程名; 非主屬性是: 學(xué)習(xí)期限,成績,獎學(xué)金。
顯然計算鍵可從R的一元子集開始,按子集元素個數(shù)遞增(寬度優(yōu)先)來進行,當(dāng)檢驗出一個X是鍵后,它的超集就不再做檢驗,即可用最少的計算次數(shù)而求得所有鍵。
求函數(shù)依賴模式(R,∑)全部鍵的問題可多項式地歸約為一個圖覆蓋問題。因為眾所周知圖覆蓋問題是NP完全問題,所以求函數(shù)依賴模式(R,∑)全部鍵的問題是NP完全問題。
設(shè)Ω={R₁,R₂,…,R_n}是一個數(shù)據(jù)庫模式,∑₁,∑₂,…,∑_n分別是R₁,R₂,…,R_n上的函數(shù)依賴集合,X_i是函數(shù)依賴模式(R_i,∑_i)上的鍵, 若X_iR_j,1≤i,j≤n,i≠j,則稱X_i是函數(shù)依賴模式(R_i,∑_i)上的外部鍵。外部鍵主要用于各關(guān)系模式之間的連接。