資料庫第八章 關系資料庫設計
無損分解&有損分解
一個資料庫的好壞主要取決于ER圖的設計品質
該資料表：
存在資料的備援，且如果一個系沒有教師，則無法表示該系的資訊(dept_name,building,budget)
是以可以考慮将其進行分解：
分解為 teacher(ID,name,salary,dept_name) dept(dept_name,building,budget)
該分解可以解決備援問題，但是否分解總是好的？
考慮将employee(ID, name, street, city, salary) 分解為employee1 (ID, name) 和 employee2 (name, street, city, salary) ，則會産生資料關系的丢失。因為如果存在同名的情況，則自然連接配接兩個表時将導緻部分資料錯誤的連接配接，是以失去了一些資訊。
有損分解 lossy decomposition： 無損分解指的是對關系模式分解時，原關系模型下任一合法的關系值在分解之後不能通過自然聯接運算恢複起來
無損分解 lossless decomposition： 無損分解指的是對關系模式分解時，原關系模型下任一合法的關系值在分解之後應能通過自然聯接運算恢複起來
原子域&第一範式
如果一個域的元素是不可分的單元，則該域是原子的(atomic)
如果一個關系模式R的所有屬性的域都是原子的，則稱該關系模式滿足第一範式(1NF)
函數依賴
R的子集K是r(R )的超碼的條件：在關系r(R )的任意合法執行個體中，對于r的執行個體中的所有元組對t1和t2總滿足：若t1≠t2，則t1[K]≠t2[K] . 也就是說不同元組的K是不同的，即K唯一辨別該元組
考慮一個關系r(R ),令α∈R且β∈R
- 對于r(R )的給定執行個體，該執行個體滿足函數以來α→β的條件是：對執行個體中的所有元組對，若t1[α]=t2[α]，則t1[β]=t2[β]
- 如果在r(R )的每個合法執行個體都滿足α→β，則該函數依賴在r(R )上成立
(想想函數的定義，α→β，也就是說對于相同的α，映射到的β必須相同，當然對于不同的α，映射的β也可以相同，但是不能夠存在相同的α對應的β不同的情況，和函數的定義基本一緻)
對于該關系來說，函數依賴A->B不滿足，函數依賴A->C是滿足的
一些函數依賴是在所有關系中都成立的，稱為平凡的(trivial)，通常，如果β∈α，則形如α→β的函數依賴是平凡的
BCNF:
具有函數依賴集F的關系模式屬于BCNF的條件：對于F+(F的閉包)中所有形如α→β的函數依賴，下面二者至少一項成立：
- α→β是平凡的函數依賴
- α是模式R的一個超碼
前面提到的關系instr_dept (ID, name, salary, dept_name, building, budget ) 不滿足BCNF，因為存在dept_name->budget的函數依賴，而dept_name并不是超碼。
如果R是不屬于BCNF的一個模式，則存在至少一個α→β，其中α不是超碼，則可以用下面兩個模式取代R：
- (α∪β)
- (R-(β-α))
對于instr_dept (ID, name, salary, dept_name, building, budget )，存在α=dept_name,β={building,budget},使得α→β成立，故将其分解為：(α∪β)={dept_name,building,budget},(R-(β-α))={ID,name,salary,dept_name}
第三範式 3NF
具有函數依賴集F的關系模式屬于BCNF的條件：對于F+(F的閉包)中所有形如α→β的函數依賴，下面三者至少一項成立：
- α→β是平凡的函數依賴
- α是模式R的一個超碼
- β-α中的每個屬性A都包含于R的一個候選碼中
很顯然，BCNF是比3NF更嚴格的範式
函數依賴理論
如果給定關系模式r(R )，r(R )的每一個滿足F的執行個體也滿足f，則稱R上的函數依賴f被r上的函數依賴集F邏輯蘊含。(就是說通過現有的函數依賴可以推導出f，則f實際上也是蘊含在該關系模式中的函數依賴)
F的閉包通常記為F+ ,指的是被F邏輯蘊含的所有函數依賴的集合
Armstrong’s 公理：
- 自反律：若α為一屬性集且β∈α，則α→β成立
- 增補律：若α→β成立且γ為一屬性集，則γα→γβ成立
- 傳遞律：若α→β和β→γ成立，則α→γ
Armstrong’s公理的推論：
- 合并律：若α→β和α→γ成立，則α→βγ
- 分解率：若α→βγ成立，則α→β和α→γ成立
- 僞傳遞律：若α→β和γβ→δ，則αγ→δ成立
求屬性集的閉包的例子:
屬性閉包的運用：
- 判斷α是否為超碼，可以計算α的閉包α+,如果α+包含R中所有元素，則為超碼
- 通過檢查是否β∈α+，可以檢查α→β是否成立
正則覆寫 Canonical Cover：
無關屬性：如果去除函數依賴中的一個屬性不改變該函數依賴集的閉包，則稱該屬性為無關的。
無關屬性的形式定義：考慮函數依賴集F及F中的函數依賴α→β
- 如果A∈α并且F邏輯蘊含(F-{α→β})∪{(α-A)→β}，則屬性A在α中是無關的
-
如果A∈β并且函數依賴集(F-{α→β})∪{α→(β→A)}邏輯蘊含F，則屬性A在β中是無關的
(也就是說，把A在該函數依賴中去掉後，F+并不變，則A為無關屬性)
例如：假如F中有AB->C和A->C，則B在AB->C中是無關的，因為A->C可以推出AB->C
檢驗一個屬性在α->β是否無關，通常考慮的是，将該屬性從α->β中去除，然後看剩下的函數依賴是否可以推出原α->β，或者直接檢視去掉該元素後的α或者β的閉包是否可以包含該元素
計算函數依賴集的正則覆寫：
F的正則覆寫Fc與F具有相同的閉包
正則覆寫未必是唯一的
無損分解
R1和R2是R的無損分解，如果以下函數依賴中至少有一個屬于F+:
- R1∩R2->R1
- R1∩R2->R2
也就是R1∩R2是R1或R2的超碼，R上的分解就是無損分解
分解算法
BCNF分解：
檢查是否滿足BCNF分解：
- 檢查非平凡的函數依賴α->β是否違反BCNF，可以計算α的屬性閉包，驗證其是否包含所有屬性，即驗證它是否是R的一個超碼
- 檢查關系模式是否屬于BCNF，僅須檢查給定集合F中的函數依賴是否違反BCNF即可，不用檢查F+中所有的函數依賴，但是如果一個關系分解後，就不能用此方法。
為了檢查R分解後的關系R是否屬于BCNF：
- 對于Ri中屬性的每個子集α，確定α的屬性閉包要麼不包含Ri-α的任何元素，要麼包含Ri的所有元素
BCNF分解算法：需要注意的是這是一個無損分解
3NF分解算法：
多值依賴
令r(R )為一關系模式，并且α∈R且β∈R。多值依賴α->->β在R上成立的條件是，在關系r(R )的任意合法執行個體中，對于r中任意一對滿足t1[α]=t2[α]的元組對t1和t2，r中都存在t3和t4，使得
- t1[α] = t2 [α] = t3 [α] = t4 [α]
- t3[β] = t1 [β]
- t3[R – β] = t2[R – β]
- t4 [β] = t2[β]
- t4[R – β] = t1[R – β]
- 若α->β，則α->->β
- 若α->->β，則α->->R-α-β
第四範4NF
函數依賴和多值依賴集為D的關系模式r(R )屬于第四範式(4NF)的條件是，對D+中所有形如α->->β的多值依賴，下面二者至少一項成立：
- α->->β是一個平凡的多值依賴
- α是R的一個超碼
4NF模式一定屬于BCNF
實際上就4中範式的備援度而言：
4NF<BCNF<3NF<1NF
4NF分解算法：