關系數據庫概述

相關名詞
1、關系：在關系數據庫中，實體以及實體間的聯系都是用關系來表示的。類似于程序設計語言中變量的概念。
2、關系模式：是對關系的描述。類似于程序設計語言中類型定義的概念。
3、關系模型：是由若干個關系模式組成的集合。
4、屬性：用來描述某一個事物的特征。
5、域：每個屬性的取值范圍所對應一個值的集合。
6、候選碼：若關系中的某一屬性或屬性組的值能唯一標識一個元組，則稱該屬性或屬性組為候選碼。
7、主碼：又稱為主鍵，若一個關系有多個候選碼，則選定其中一個為主碼。
8、主屬性：包含在任何候選碼中的各個屬性稱為主屬性。
9、非主屬性：不包含在任何候選碼中的屬性稱為非主屬性。
10、外碼：如果關系模式R中的屬性或屬性組非該關系的碼，但它是其他關系的碼，那么該屬性集對關系模式R而言是外碼。
11、全碼：關系模型的所有屬性組是這個關系模式的候選碼，稱為全碼。
12、元組/記錄：行
13、字段、數據項
14、元數：屬性的個數（列數）
15、基數：記錄的個數（行數）
16、n元關系：元數為幾，就是幾元關系。
例：關系模式：
Student(Sno,Sname,SD,Sex)

關系數據庫模式

? 關系模式可以表示為：
R(U,D,dom,F)
?
R表示關系名，U是組成該關系的屬性名集合；D是屬性的域；dom是屬性向域的映像集合；F為屬性間數據的依賴關系集合。
通常將關系模式簡記為：
R(U)或 R(A1,A2,A3,…,An)
其中，R為關系名，A1,A2,A3,…,An為屬性名或域名。
例：學生關系S有學號Sno、學生姓名Sname、系名SD、年齡SA屬性；課程關系C有課程號Cno、課程名Cname、先修課程號PCno屬性；學生選課關系SC有學號Sno、課程號Cno、成績Grade屬性。定義關系模式及主碼如下（未考慮F，即屬性間的依賴關系）。
（1）學生關系模式S(Sno,Sname,SD,SA)
（2）課程關系模式C(Cno,Cname,PCno),Dom(PCno)=Cno
（3）學生選課關系模式SC(Sno,Cno,Grade)

關系的三種類型

（1）基本關系（基本表或基表）：它是實際存在的表，是實際存儲數據的邏輯表示。
（2）查詢表。查詢結果對應的表。
（3）視圖表。它是一種虛擬表，是由基本表或其他視圖表導出的表。
它本身是不獨立存儲在數據庫的，數據庫只存放它的定義。

關系的完整性約束

? 關系的完整性約束：是對關系的某種約束條件，用來保證用戶對數據庫作出修改時不會破壞數據的一致性，防止對數據的意外破壞。
（1）實體完整性：是指基本關系R的主屬性不能取空值。
（2）參照完整性：
? S(學號,姓名,所屬院系,年齡)
? D(院系編號,學院名稱,學院地址,系主任)
（3）用戶定義完整性：是針對某一具體的關系數據庫的約束條件，反映某一具體應用所涉及到的數據必須滿足的語義要求。

關系運算

基本的關系代數運算
1、并(Union)
? 關系R與S具有相同的關系模式，即R與S的元數相同（結構相同），關系R與S“并”
由屬于R或屬于S的元組構成的集合組成，記作R∪S，其形式定義如下：

2、差
? 關系R與S具有相同的關系模式，關系R與S的差是由屬于R但不屬于S的元組構成的集合，記作R-S，其形式定義如下：

3、廣義笛卡兒積
? 兩個元數分別為n目和m目的關系R和S的廣義笛卡兒積是一個(n+m)列的元組的集合。
元組的前n列是關系R的一個元組，后m列是關系S的一個元組，記作R×S。

4、投影及廣義投影
? 投影是從關系的垂直方向進行運算，在關系R中選擇出若干屬性列A組成新的關系，記作πA?，其
形式定義如下：

5、選擇
? 選擇運算是從關系的水平方向進行運算，是從關系R中選擇滿足給定條件的諸元組，
記作σF?，其形式定義如下：
σF?={t|t?R∧F(T)=True}
? 其中，F中的運算對象是屬性名（或列的序號）或常數，運算符、算術比較符（<、>、?、?、≠）和邏輯運算符（∧、∨、?）。
? 例如，σ1?6?表示選取關系R中第1個屬性值大于等于第6個屬性值的元組；
σ1>'6’?表示選取關系R中第1個屬性值大于6的元組。
注意6和’6’的區別，6是指從左往右數第6個屬性，‘6’是指數字6（數值格式或文本
格式）

擴展的關系運算

1、交
? 關系R與S具有相同的關系模式，關系R與S的交由屬于R同時又屬于S的元組構成，關系R與S的交記作R?S，其形式定義如下：

2、連接
? 分為θ連接、等值連接與自然連接

（2）等值連接

3、除

4、外連接
? 外連接運算是連接運算的擴展，可以處理缺失的信息。
（1）左外連接?（左側為準，右側填充）
? 取出左側關系中所有與右側關系中任一元組都不匹配的元組，用空值NULL填充所有來自右側關系
的屬性，構成新的元組，將其加入自然連接的結果中。

（2）右外連接?（右側為準，左側填充）
取出右側關系中所有與左側關系中任一元組都不匹配的元組，用空值NULL填充所有來自左側關系的
屬性，構成新的元組，將其加入自然連接的結果中。

元組演算、域演算與查詢優化

元組演算

? 元組關系演算是非過程化查詢語言，簡稱元組演算。它只描述所需信息，而不給出獲得該信息的
具體過程。
? 在元組演算中，其元組演算表達式中的變量是以元組為單位的，其一般形式為：
{t|P(t)}
其中，t是元組變量，P(t)是元組演算公式，公式是由原子公式組成。
1、原子公式：
（1）R(t)
R是關系名，t是元組變量，R(t)表示：t是關系R中的一個元組。
（2）t[i] θ C 或 C θ t[i]
t[i]表示元組變量t的第i個分量，C是常量，θ為算術比較運算符。
（3）t[i]θ u[j]
t和u是兩個元組變量。t[i]θ u[j]表示元組變量t的第i個分量與元組變量u的第j個分量之間滿足θ運
算。
2、公式的定義
? 若一個公式的一個元組變量前有全稱量詞?或存在量詞?符號，則稱該變量為約束變量，否則稱之
為自由變量。公式可遞歸定義如下：
（1）原子公式是公式。
（2）如果φ1和φ2是公式，那么，?φ1，φ1∨φ2，φ1∧φ2，φ1?φ2也都是公式。分別表示如下命題：
?φ1表示“φ1不為真”，φ1∨φ2表示“φ1或φ2為真”，φ1∧φ2表示“φ1和φ2都為真”；φ1?φ2表示
“若φ1為真則φ2為真”。
（3）如果是φ1公式，那么，?t(φ1)是公式。?t(φ1)表示這樣一個命題：
“如果有一個t使φ1為真，則?t(φ1)為真，否則?t(φ1)為假”。
（4）如果是φ1公式，那么，?t(φ1)是公式。?t(φ1)表示這樣一個命題：
“如果對所有的t使φ1為真，則?t(φ1)為真，否則?t(φ1)為假”。
? 公式中運算符的優先順序為：
? θ > ?和? > ? > ∧和∨ > ?，加括號時，括號中的運算符優先。

域演算

查詢優化

? 查詢優化是指為查詢選擇最有效的查詢計劃的過程。一個查詢可能會有多種實現方法，關鍵是如何找出一個與之等價的且操作時間又少的表達式，以節省時間、空間，提高查詢效率。
? 在關系代數運算中，笛卡兒積、連接運算是最耗費時間和空間的。
1、優化的準則：
（1）提早執行選取運算。對于有選擇運算的表達式，應優化成盡可能先執行選擇運算的等價表達式，以得到較小的中間結果，減少運算量和從外存讀塊的次數。
（2）合并乘積與其后的選擇運算為連接運算。
（3）將投影運算與其后的其他運算同時進行，以避免重復掃描關系。
（4）將投影運算和其前后的二目運算結合起來，使得沒有必要為去掉某些字段再掃描一遍關系。
（5）在執行連接前對關系適當地預處理，就能快速地找到要連接的元組。方法有兩種：索引連接法、排序合并連接法。
（6）存儲公共子表達式。對于有公共子表達式的結果應存于外存（中間結果），這樣，當從外存讀
出它的時間比計算的時間少時，就可節約操作時間。

關系數據庫設計基礎知識

函數依賴

1、函數依賴
? 定義：設R(U)是屬性集U上的關系模式，X、Y是U的子集。若對R(U)的任何一個可能的關系r，r中不可能存在兩個元組在X上的屬性值相等，而在Y上的屬性值不等，則稱X函數決定Y或Y函數依賴于X，記作：X→Y
? 如果X→Y，那么對于任意兩個相同的X，所對應的Y是一定相同的。
? 如果X→Y，但Y?X，則稱X→Y是非平凡的函數依賴。一般情況下總是討論非平凡的函數依賴。
? 如果X→Y，但Y?X，則稱X→Y是平凡的函數依賴。
? 函數依賴的定義要求關系模式R的任何可能的r都滿足上述條件。因此不能僅考察關系模式R在某一時刻的關系r，就斷定某函數依賴成立。
? 函數依賴是語義范疇的概念，我們只能根據語義來確定函數依賴。
2、完全函數依賴與部分函數依賴
? 定義：在R(U)中，如果X→Y，并且對于X的任何一個真子集X’，都有X’不能決定Y，則稱Y對X完全函數依賴，記作：X→Y。如果X→Y，但Y不完全函數依賴于X，則稱Y對X部分函數依賴，記作：X→Y。部分函數依賴也稱局部函數依賴。
3、傳遞函數依賴
? 定義：在R(U,F)中，如果X→Y，Y→Z，Y?X，Y?X，則稱Z對X傳遞依賴。
例：供應商（Sno,Sname,Status,City,Pno,Qty），及函數依賴集如下，判斷該關系是否存在傳遞函數依賴和部分函數依賴。
F={Sno→Sname, Sno→Status, Status→City,(Sno,Pno)→Qty}

碼

1、候選碼和主碼：設K為R(U,F)中的屬性的組合，若K→U，且對于K的任何一個真子集K’，都有K’不
能決定U，則K為R的候選碼，若有多個候選碼，則選一個作為主碼。
? 候選碼通常也可以稱為候選關鍵字，主碼通常也可以稱為主關鍵字或主鍵。
? 包含在任何一個候選碼中的屬性叫做主屬性，否則叫做非主屬性。
2、外碼：若R(U)中的屬性或屬性組X非R的碼，但X是另一個關系的碼，則稱X是R的外碼（Foreign Key）或稱外鍵。

多值依賴

? 定義：若關系模式R(U)中，X，Y，Z是U的子集，并且Z=U-X-Y。當且僅當對R(U)的
任何一個關系r，給定一對(x,z)值，有一組Y的值，這組值僅僅決定于x值而與z值
無關，則稱“Y多值依賴于X”或“X多值決定Y”成立。記為：
X→→Y
? 多值依賴具有如下6條性質：
1、多值依賴具有對稱性。即若X→→Y,則X→→Z，其中Z=U-X-Y。
2、多值依賴的傳遞性。即若X→→Y,Y→→Z,則X→→Z-Y。
3、函數依賴可以看成是多值依賴的特殊情況。
4、若X→→Y,X→→Z,則X→→YZ。
5、若X→→Y,X→→Z,則X→→Y ? Z。
6、若X→→Y,X→→Z,則X→→Z-Y。

五、規范化

1NF（第一范式）

? 定義：若關系模式R的每一個分量是不可再分的數據項，則關系模式R屬于第一范式。記為R∈1NF。
例：學生(學號,姓名,學院編號,學院名稱,課程號,成績)
F={學號→姓名, 學號→學院編號, 學院編號→學院名稱,(學號,課程號)→成績}
? 存在的問題：
（1）數據冗余。
（2）更新異常(修改操作后數據不一致)。
（3）插入異常。
（4）刪除異常。

2NF（第二范式）

? 定義：若關系模式R∈1NF，且每一個非主屬性完全依賴于碼，則關系模式R∈2NF。
? 換句話說：當1NF消除了非主屬性對碼的部分函數依賴，則稱為2NF。
例：學生(學號,姓名,學院編號,學院名稱,課程號,成績)
F={學號→姓名, 學號→學院編號, 學院編號→學院名稱,(學號,課程號)→成績}
將學生關系分解為：
? 學生1(學號,姓名,學院編號,學院名稱)?2NF
? 學生2(學號,課程號,成績)?2NF

3NF（第三范式）

? 定義：若關系模式R(U,F)中不存在這樣的碼X，屬性組Y及非主屬性Z（Z?Y）使得
X→Y,(Y?X) Y→Z成立，則關系模式R∈3NF。
? 即：當2NF消除了非主屬性對碼的傳遞函數依賴，則稱為3NF。
例：學生1(學號,姓名,學院編號,學院名稱)∈2NF，但?3NF。
將學生1分解為：
? 學生11(學號,姓名,學院編號)∈3NF
? 學生12(學院編號,學院名稱)∈3NF

BCNF（巴克斯范式）

? 定義：關系模式R∈1NF，若X→Y且Y?X時，X必含有碼，則關系模式R∈BCNF。
? 也就是說，當3NF消除了主屬性對碼的部分函數依賴和傳遞函數依賴，則稱為BCNF。
? 結論：一個滿足BCNF的關系模式，應有如下性質：
（1）所有非主屬性對每一個碼都是完全函數依賴；
（2）所有主屬性對每一個不包含它的碼，也是完全函數依賴；
（3）沒有任何屬性完全函數依賴于非碼的任何一組屬性。
例：R(Pno,Pname,Mname)的屬性表示零件號、零件名和廠商名，如果約定，每種零件號只有一個零
件名，但不同的零件號可以有相同的零件名；每種零件可以有多個廠商生產，但每家廠商生產的零
件應有不同的零件名。函數依賴集如下：
(Pname,Mname)→Pno, Pno→Pname
候選碼為(Pname,Mname)或(Pno,Mname)
分解為：R1(Pno,Pname)∈BCNF
R2(Pno,Mname)∈BCNF

4NF（第四范式）

? 定義：關系模式R∈1NF，若對于R的每個非平凡多值依賴X→→Y且Y?X時，X必含有碼，則關系模式R(U,F)∈4NF。
? 4NF是限制關系模式的屬性間不允許有非平凡且非函數依賴的多值依賴。
? 注意：如果只考慮函數依賴，關系模式最高的規范化程度是BCNF，如果考慮多值依賴，關系模式最高的規范化程度是4NF。
例：學生(學號，選修課程，興趣愛好)
? 學生1(學號，選修課程）∈4NF
? 學生2(學號，興趣愛好）∈4NF
書目(ISBN，書名，作者，排名，出版社）
? 書目1(ISBN，作者，排名）∈4NF
? 書目2(ISBN，書名，出版社）∈BCNF

1NF?2NF?3NF?BCNF?4NF?5NF
通過分解，可以將一個低一級范式的關系模式轉換成若干個高一級范式的關系模式，這種過程叫做規范化。

Armstrong公理系統

? Armstrong公理系統（函數依賴的公理系統）：設關系模式R(U,F)，其中U為屬性集，F是U上的一
組函數依賴，那么有如下推理規則：
（1）A1自反律：若Y?X?U，則X→Y為F所蘊涵。
（2）A2增廣律：若X→Y為F所蘊涵，且Z?U，則XZ→YZ為F所蘊涵。
（3）A3傳遞律：若X→Y，Y→Z為F所蘊涵，則X→Z為F所蘊涵。
? 根據上述三條推理規則又可推出下述三條推理規則：
（1）合并規則：若X→Y，X→Z，則X→YZ為F所蘊涵。
（2）偽傳遞律：若X→Y，WY→Z，則XW→Z為F所蘊涵。
（3）分解規則：若X→Y，Z?Y，則X→Z為F所蘊涵。

函數依賴的閉包F+及屬性的閉包XF+

1、函數依賴的閉包F+
? 定義：關系模式R(U,F)中為F所邏輯蘊含的函數依賴的全體稱為F的閉包，記為：F+。
例：R(U,F)，U=（A,B,C,D）,F={A→B,B→C,AC→D}
2、屬性的閉包XF+
? 定義：設F為屬性集U上的一組函數依賴，X?U，XF+={A|X→A能由F根據Armstrong公理導出}，則稱XF+為屬性集X關于函數依賴集F的閉包。
? 即：屬性集X的閉包XF+是指所有能由X決定的屬性集合。
候選碼的求解方法
? 給定一個關系模式R(U,F),U={A1,A2,…,An}，F是R的函數依賴集，那么，可以將屬性分為如下四類：
L：僅出現在函數依賴集F左部的屬性
R：僅出現在函數依賴集F右部的屬性
LR：在函數依賴集F左右部都出現的屬性
NLR：在函數依賴集F左右部都未出現的屬性
? 根據候選碼的特性，對于給定一個關系模式R(U,F)，可以得出如下結論：
結論1：若X(X?U)是L類屬性，則X必為R的任一候選碼的成員。若XF+=U，則X必為R的唯一候選碼。
結論2：若X(X?U)是R類屬性，則X不是R的任一候選碼的成員。
結論3：是X(X?U)是NLR類屬性，則X必為R的任一候選碼的成員。
結論4：若X(X?U)是L類和NLR類屬性組成的屬性集，若XF+=U，則X必為R的唯一候選碼。

候選碼的求解方法

第1步、根據題意，將所有的屬性分類：
? L：只在左邊出現，一定是
? R：只在右邊出現，一定不是
? LR：左右都出現，有可能是，也有可能不是
? NLR：左右都沒出現，一定是
第2步、將所有的L類和NLR類屬性組合起來，設為P，求其閉包PF+，如果是全集U，那么它就是候選碼。
第3步、如果PF+不是全集U，則依次將LR類屬性跟P組合起來求閉包，只要其閉包是全集U，就是候選碼。

最小函數依賴集

? 如果函數依賴集F滿足下列條件，則稱F為一個最小函數依賴集，或稱極小函數依賴集或最小覆蓋。
（1）F中的任一函數依賴的右部僅有一個屬性，即無多余的屬性；
（2）F中不存在這樣的函數依賴X→A，使得F與F-{X→A}等價，即無多余的函數依賴；
（3）F中不存在這樣的函數依賴X→A，X有真子集Z使得F與F-{X→A}?{Z→A}等價，即去掉各函數依
賴左邊的多余屬性。
即：（1）所有函數依賴的右側只有一個屬性。
（2）沒有冗余的函數依賴。
（3）所有函數依賴的左側沒有冗余的屬性。
例：關系模式R(U,F), R(A,B,C,D,E), F={A→BC,A→E,A→D,D→E,AC→D}

模式分解及分解后的特性

無損連接
? 分解及無損連接的定義：略，見教材P288
? 無損連接是指將一個關系模式分解成若干個關系模式后，通過自然連接和投影等運算仍能還原到原來的關系模式，則稱這種分解為無損連接分解。
? 定理：關系模式R(U,F)的一個分解ρ ={ R1(U1,F1),R2(U2,F2)}，具有無損連接的充分必要的條件是：
U1?U2→U1－U2∈F+或U1?U2→U2－U1∈F+。
? 注意：這個定理只適用于分解為兩個子模式的情況，分解為多個子模式的時候不適用。
例：對給定的關系模式R(U,F)，U={A,B,C}，F={A→B}，有兩個分解：ρ1 ={AB,BC}和 ρ2 ={AB,AC}。請判斷這兩個分解是否無損。
? 定義：設關系模式R(U,F)的一個分解 ρ ={R1(U1,F1), R2(U2,F2),…,Rk(Uk,Fk)}，如
果F+=(?Fi)+，則稱分解ρ保持函數依賴。
即：（F1?F2?F3?…?Fk)+ = F+
例：判斷是否保持函數依賴：
(1)關系R(A1，A2，A3)上的函數依賴集F={A1A3→A2,A1A2→A3}，R上的一個分解為ρ={(A1，A2),(A1，A3)}
(2)給定關系模式R(A1，A2，A3，A4)，R上的函數依賴集F = {A1A3→A2，A2→A3}，若將R分解為ρ={(A1，A2，A4)，(A1，A3)}
(3)給定關系模式R(U，F)，U ={A,B,C,D}，F={A→B，BC→D}，對關系R分解為R1(A，B，C)和R2(A，C，D)