通過E-R圖轉(zhuǎn)換得出一組關(guān)系模式后
**選擇1：**把一些關(guān)系模式合并為更大的關(guān)系 —— 會(huì)產(chǎn)生過多的數(shù)據(jù)冗余

inst_dept(ID, name, salary, dept_name, building, budget)

如果通過E-R模型轉(zhuǎn)換得出如下兩個(gè)關(guān)系模式

sec_class(sec_id, building, room_number) and section(course_id, sec_id, semester, year)

那么在邏輯設(shè)計(jì)中，可以將上述兩個(gè)關(guān)系合并為如下關(guān)系

section(course_id, sec_id, semester, year, building, room_number)

上述關(guān)系模式不會(huì)產(chǎn)生數(shù)據(jù)冗余

設(shè)計(jì)選擇2：更小的模式？
如果通過E-R模型轉(zhuǎn)換得出inst_dept關(guān)系模式，那么在邏輯設(shè)計(jì)中，我們可以將其分解為兩個(gè)關(guān)系模式

instructor(ID, name, salary, dept_name) department(dept_name, building, budget) # 從而避免(building, budget)的數(shù)據(jù)冗余

如何知道該合并或分解關(guān)系模式呢?

可以通過保持如下一條規(guī)則：dept_name確定(building, budget)數(shù)據(jù)，即保持函數(shù)依賴：dept_name → building, budget

由于dept_name在inst_dept關(guān)系中不是主碼，因此需要將其拆分為更小的關(guān)系模式

并不是所有的關(guān)系模式拆分是有益的
將employee(ID, name, street, city, salary)分解為

employee_attr1(ID, name) employee_attr2(name, street, city, salary)

name無法作為employee_attr2關(guān)系的主碼，有可能會(huì)重名
無法通過分解出的employee_attr1和employee_attr2重建（自然連接）得出原始關(guān)系
我們稱無法通過自然連接重建原始關(guān)系元組的分解為有損分解 (lossy decomposition)

無損分解

$R=(A,B,C)$的分解
$R1=(A,B)R2=(B,C)$

KaTeX parse error: Undefined control sequence: \join at position 18: …= \Pi_{A,B}(r) \?j?o?i?n? ?\Pi_{B,C)(r)和$R(A,B,C)$等價(jià)

函數(shù)依賴

假設(shè)$r(R)$是一個(gè)關(guān)系模式,$\alpha ?R$, $\beta ?R$, 模式R上的函數(shù)依賴
$$\alpha \to \beta$$

成立的條件是：如果對(duì)于任意關(guān)系實(shí)例r中任意兩個(gè)元組t1 和t2，如果兩者的屬性(集)$\alpha$取值相同, 那么它們的屬性(集)$\beta$取值也相同。也就是
$$t1[\alpha ]=t2[\alpha ]?t1[\beta ]=t2[\beta ]$$

稱之為$\alpha$函數(shù)確定$\beta$, $\beta$函數(shù)依賴于$\alpha$

假設(shè)r(A,B) 有如下關(guān)系實(shí)例

1 4 1 5 3 7

$A\to B$不成立，反之成立

函數(shù)依賴和碼

? 超碼：在某關(guān)系中，若一個(gè)或多個(gè)屬性的集合$\{A_1,A_2,\dots ,A_n\}$函數(shù)決定該關(guān)系中的其它全部屬性，則稱該屬性為該關(guān)系的超碼
?若屬性組K滿足K → R，則K 是關(guān)系模式R的超碼

? 候選碼：若集合$\{A_1,A_2,\dots ,A_n\}$的任何真子集均不能函數(shù)決定該關(guān)系中的其它屬性，則此時(shí)$\{A_1,A_2,\dots ,A_n\}$是最小的超碼，即候選碼
? K → R 且不存在$\alpha ?K$, 滿足 $\alpha \to R$

? 外碼：若關(guān)系模式R中屬性或?qū)傩越MX是另一關(guān)系模式的主碼，則稱X是R的外碼

S（Sno，Sname，Sdept，Sage） SC（Sno，Cno，G）

函數(shù)依賴允許我們表達(dá)超碼不能表達(dá)的約束。考慮下面的模式：
$$ins{t}_{d}ept(\underline{ID},name,salary,dept\_name,building,budget).$$

超碼函數(shù)依賴：
ID → name, salary, dept_name, building, budget

函數(shù)依賴在關(guān)系實(shí)例和關(guān)系模式上的體現(xiàn)區(qū)別：

如果關(guān)系實(shí)例r在函數(shù)依賴集F上合法，則稱r滿足F

如果模式R上的所有合法關(guān)系實(shí)例都滿足函數(shù)依賴集F，我們說F在關(guān)系模式R上成立

notice：即使函數(shù)依賴并沒有對(duì)關(guān)系模式r?的所有合法實(shí)例成立，這個(gè)關(guān)系模式的其中一個(gè)具體實(shí)例r可能滿足函數(shù)依賴

相關(guān)術(shù)語

有些函數(shù)依賴被稱為平凡(trivial)的，因?yàn)樗鼈冊(cè)谒嘘P(guān)系中都是滿足的
? name → name
? ID, name → ID

如果$\beta ?\alpha$, $\alpha \to \beta$是平凡的函數(shù)依賴
$\beta ?\alpha$, $\alpha \to \beta$則這個(gè)是非平凡的函數(shù)依賴
$\alpha \to \beta$ 則$\alpha$是決定因素

函數(shù)依賴$\alpha \to \beta$ 稱為部分依賴的條件是：存在$\alpha$的真子集γ，
使得$\gamma \to \beta$

閉包

從給定函數(shù)依賴集F能夠推導(dǎo)出的所有函數(shù)依賴的集合，我們稱之為F集合的閉包
$$A\to B,B\to C$$
推出$A\to C$
我們用$F^{+}$來表示函數(shù)依賴集F的閉包,是F的超集

給定關(guān)系模式r( R )，如果r( R ) 的每個(gè)滿足F的 實(shí)例也滿足某個(gè)函數(shù)依賴ｆ，則R上的函數(shù)依賴ｆ邏輯蘊(yùn)含（logically imply）于ｒ上的函數(shù)依賴集F

已知關(guān)系R上的函數(shù)依賴集T、F，如果對(duì)于該關(guān)系中滿足F的每一個(gè)關(guān)系實(shí)例都滿足T，稱函數(shù)依賴集F 邏輯蘊(yùn)含 函數(shù)依賴集T

若F蘊(yùn)含于T，且T蘊(yùn)含于F，則函數(shù)依賴集T和F是等價(jià)的，記為T≡F

推理規(guī)則

Armstrong公理:

如果$\beta ?\alpha$, , 則有 $\alpha \to \beta$ (自反律)

如果 $\alpha \to \beta$, 則有 $\gamma \alpha \to \gamma \beta$ (增補(bǔ)律)

如果 $\alpha \to \beta$及$\beta \to \gamma$, 則有 $\alpha \to \gamma$ (傳遞律)

有效的：它們不會(huì)產(chǎn)生錯(cuò)誤的函數(shù)依賴
完備的：對(duì)一個(gè)給定函數(shù)依賴集F，它們能產(chǎn)生整個(gè)F+

函數(shù)依賴證明(A → H)：
已知A → B，根據(jù)函數(shù)依賴定義，可得：

對(duì)于任意元組t1, t2，如果t1[A] = t2[A]，那么 t1[B]=t2[B] 已知B → H，同理可得：如果t1[B] = t2[B]，那么 t1[H]=t2[H] 綜上可得：如果t1[A] = t2[A]，那么t1[H] = t2[H]，即A → H得證

計(jì)算函數(shù)依賴集F的閉包算法:

repeatfor each F +中的函數(shù)依賴 f在f上應(yīng)用自反律和增補(bǔ)律將結(jié)果加入到F +中for each F +中一對(duì)函數(shù)依賴f1和 f2if f1 和 f2 可以使用傳遞律結(jié)合起來將結(jié)果加入到F +中 until F + 不再發(fā)生變化

附加定理:
若有 $\alpha \to \beta$ 及$\alpha \to \gamma$, 則有 $\alpha \to \gamma \beta$ (合并律)
若有 $\alpha \to \gamma \beta$, 則有$\alpha \to \beta$ 及 $\alpha \to \gamma$ (分解律)
若有 $\alpha \to \beta$及$\beta \gamma \to \delta$, 則有 $\alpha \gamma \to \delta$ (偽傳遞律)

給定屬性集$\alpha$, 我們稱在函數(shù)依賴集F下由$\alpha$函數(shù)確定的所有屬性集合為F下$\alpha$的閉包，記為${\alpha }^{+}$

算法

result := α; while (result發(fā)生變化) dofor each 函數(shù)依賴 β → γ in F dobeginif β ? result then result := result ∪ γend

閉包用途

屬性閉包算法有多個(gè)用途：

超碼的判斷：

• 判斷α 是不是超碼，通過計(jì)算α+，看α+ 是否包含R中的所有屬性

驗(yàn)證函數(shù)依賴：

• 要檢驗(yàn)函數(shù)依賴α → β是否成立 (換句話說，是否在F +中), 只需要檢驗(yàn)是否β ? α+
• 也就是說，我們用屬性閉包計(jì)算α+ ，看它是否包含β
• 是一個(gè)簡單快速的驗(yàn)證方法，但是很有用

計(jì)算F的閉包：

• 對(duì)任意的γ ? R, 我們找出閉包γ+；對(duì)任意的S ? γ+, 我們輸出一個(gè)函數(shù)依賴γ → S

規(guī)范化（Normalization）

一個(gè)數(shù)據(jù)庫的描述對(duì)象包括：學(xué)生（Sno），系（Sdept）、系負(fù)責(zé)人（Name）、課程（Cname）和成績（G）

U ={Sno, Sdept, Name, Cname, G} FD ={ Sno->Sdept,Sdept->Name,(Sno,Cname)->G }建立關(guān)系模式：S(Sno, Sdept, Name, Cname, G)

存在問題：
? 數(shù)據(jù)冗余
? 需要用空值來表示某些信息

可以將S分解為三個(gè)關(guān)系模式：

S(Sno, Sdept)SG(Sno, Cname, G)Dept(Sdept, Name)

假設(shè)R是關(guān)系模式，具有函數(shù)依賴集F
在關(guān)系模式不是“好”的模式的情況下，將其分解成
關(guān)系模式集 $\{A_1,A_2,\dots ,A_n\}$

每個(gè)關(guān)系模式都是好的模式：無數(shù)據(jù)冗余（符合一定范式，例如BCNF）

分解是無損連接分解

最好的是，分解是保持依賴的（p225）

各種范式之間包含關(guān)系如下
$1NF?2NF?3NF?BCNF?4NF?5NF$
某一關(guān)系模式R最高屬于第n范式，可簡記為R∈nNF

第一范式

如果某個(gè)域的元素被認(rèn)為是不可分的單元，那么這個(gè)域就是原子的

?非原子域的例子： ? 復(fù)合屬性（E-R模型） ? 類似于CS101的ID（只要數(shù)據(jù)庫應(yīng)用沒有將CS標(biāo)識(shí)號(hào)拆開并解析為系的縮寫，那么可認(rèn)為是原子的）

如果一個(gè)關(guān)系模式R的所有屬性域都是原子的，我們稱關(guān)系模式R屬于第一范式
非原子的值會(huì)造成復(fù)雜存儲(chǔ)及數(shù)據(jù)冗余

第二范式

例: 關(guān)系模式 SLC(S#, SD, SL, C#, G)
SL為學(xué)生住處，假設(shè)每個(gè)系的學(xué)生住在同一個(gè)地方
SD為學(xué)生所在系，假設(shè)每個(gè)學(xué)生屬于一個(gè)系

若存在如下函數(shù)依賴
$$\{(S\#,C\#)\stackrel{f}{\to }G;(S\#,C\#)\stackrel{P}{\to }SD;SD\to SL;(S\#,C\#)\stackrel{P}{\to }SL\}$$

SLC (S#, SD, SL, C#, G)分解為
兩個(gè)關(guān)系模式:
$$SC（\underline{S\#},\underline{C\#},G）SL（\underline{S\#},SD,SL）$$

2NF的定義
若關(guān)系模式R∈1NF，且在F+中每一個(gè)非主屬性完全函數(shù)依賴于候選碼，則R∈2NF

Boyce-Codd范式 BCNF

具有函數(shù)依賴集F的關(guān)系模式R屬于BCNF的條件是：對(duì)所有F+中形如$\alpha \to \beta$的函數(shù)依賴（ $\beta ?R$且$\alpha ?R$ ），下面至少有一個(gè)成立：

$\alpha \to \beta$是平凡函數(shù)依賴

$\alpha$是模式R的一個(gè)超碼

不屬于BCNF的模式的例子:

$$inst\_dept(\underline{ID},name,salary,dept\_name,building,budget)$$
因?yàn)?dept_name → building, budget 在inst_dept上成立，但是 dept_name 不是超碼

另一個(gè)判定標(biāo)準(zhǔn)：
另一個(gè)判定準(zhǔn)則：在關(guān)系模式R（U, F）中，如果F+中的每一個(gè)非平凡 函數(shù)依賴的 決定屬性集都包含候選碼（即為超碼），則
$$r(R)\in BCNF$$

BCNF范式：排除了任何屬性（包括主屬性和非主屬性）對(duì)候選碼的部分依賴和傳遞依賴，也排除了主屬性之間的傳遞依賴

例子

r( R)=r(A,B,C), F={ A->B,B->C }.
r( R)的候選碼為A
$$r(R)\in /BCNF$$

r( R)=r(A,B,C),F={ AB->C,C->A }.
r( R)的候選碼為AB和BC
$$r(R)\in /BCNF$$

r( R)=r(A,B,C),F={ AB->C,BC->A }.
r( R)的候選碼為AB和BC
$$r(R)\in BCNF$$

假設(shè)有模式R，及其一個(gè)非平凡依賴$\alpha \to \beta$ 不屬于BCNF，那么我們可以將R分解成：
$$(a\cup \beta )和(R?(\beta ?\alpha ))$$
inst_dept的例子中

α = dept_name β = building, budget

inst_dept 被以下兩個(gè)模式取代

( dept_name, building, budget )( ID, name, salary, dept_name )

有可能分解完之后仍有關(guān)系模式不符合BCNF，那么continue

保持依賴

檢查包括各種約束（碼、check子句、函數(shù)依賴、斷言等）的開銷是很大的，但是如果只涉及到單個(gè)關(guān)系，檢查約束的開銷相對(duì)較低

然而，BCNF分解會(huì)妨礙某些函數(shù)依賴的高效檢查

如果F上的每一個(gè)函數(shù)依賴都在其分解后的一個(gè)關(guān)系上成立，那么這個(gè)分解是保持依賴的

因?yàn)橥ǔo法同時(shí)實(shí)現(xiàn)BCNF和保持依賴，因此我們考慮另外一種范式，它比BCNF寬松，允許我們保持依賴，稱為第三范式

第三范式

具有函數(shù)依賴集F的關(guān)系模式R屬于第三范式（3NF）的條件是：對(duì)F+ 中所有形如? → ? 的函數(shù)依賴中，至少有以下之一成立

$\alpha \to \beta$ 是一個(gè)平凡的函數(shù)依賴

α 是R的一個(gè)超碼

β - α 中的每個(gè)屬性A都包含在R的候選碼中
(注意: 每個(gè)屬性也許包含在不同的候選碼中

? 第三個(gè)條件是BCNF的一個(gè)最小放寬：即允許存在主屬性對(duì)候選碼的傳遞依賴和部分依賴，在函數(shù)依賴集F中用來滿足保持某些函數(shù)依賴

等價(jià)定義
關(guān)系模式R(U, F)中，若不存在這樣的碼X、屬性組Y及非主屬性Z($Z?Y$)使得$X\to Y$($Y\to X,Y\to X,Y\to Z$),則稱
$$R(U,F)\in 3NF$$

具有屬性依賴集F的關(guān)系模式R屬于3NF，則R張任何非主屬性A不部份依賴與碼也不傳遞依賴于R的碼

在關(guān)系模式SJP（S，J，P）中，S表示學(xué)生，J表示課程, P表示名次。存在函數(shù)依賴集F：{(S，J)→P，(J，P)→S}
候選碼: (S，J), (J，P)
S, J, P都是主屬性

因?yàn)?#xff1a; 沒有非主屬性部份依賴或傳遞依賴于候選碼 所以： STJ ∈ 3NF因?yàn)?對(duì)于F任意一個(gè) X → Y,X都是候選碼 所以：STJ ∈ BCNF

例：在關(guān)系模式STJ（S，T，J）中，S表示學(xué)生，T表示教師，J表示課程。存在如下函數(shù)依賴：

每一教師只教一門課；某一學(xué)生選定某門課，就確定了一位授課教師；某個(gè)學(xué)生選修某個(gè)教師的課就確定了所選課的名稱（假設(shè)）F={T→J，(S，J)→T，(S，T)→J}

∵ (S，J)和(S，T)都是候選碼 ∴ S、T、J都是主屬性∵ 沒有非主屬性部分依賴或傳遞依賴于候選碼 ∴ STJ∈3NF∵ T→J，T是決定屬性集，T不是候選碼 ∴ STJ \not ∈ BCNF

解決方法：將STJ分解為二個(gè)關(guān)系模式：
TJ(T，J) ∈ BCNF， ST(S，T) ∈ BCNF

原始函數(shù)依賴(S，J)→T，(S，T)→J 在該符合BCNF的關(guān)系模式中無法保持

BCNF足夠優(yōu)秀嗎？

考慮一個(gè)關(guān)系模式
inst_info (ID, child_name, phone)
其中，一個(gè)instructor可以有多個(gè)children和多個(gè)phone
由于該關(guān)系模式中只有平凡的函數(shù)依賴關(guān)系存在，因此其屬于BCNF

然而該BCNF模式仍存在由多值依賴（p238）造成的信息冗余：如果需要為99999教師增加一個(gè)電話號(hào)碼981-992-3443，那么需要增加兩條元組，如下

(99999, David, 981-992-3443) (99999, William, 981-992-3443)

可以將inst_info關(guān)系模式分解為兩個(gè)關(guān)系模式
inst_child(ID, child_name)
inst_phone(ID, phone)

因此，需要更為嚴(yán)格的范式來規(guī)范關(guān)系模式，如4NF

函數(shù)依賴?yán)碚?/h1>

正則覆蓋

函數(shù)依賴集可能存在冗余依賴（這些依賴可以從其他依賴中推導(dǎo)出來）
在 {A → B, B → C, A→C }中A → C是冗余的

函數(shù)依賴集的一部分也可能是冗余的
如: {A → B, B → C, A → CD }
可以簡化成 {A → B, B → C, A → D }
如: {A → B, B → C, AC → D }
可以簡化為 {A → B, B → C, A → D }

直觀上，F的正則覆蓋$F_c$沒有任何冗余依賴或存在冗余部分的依賴
$F_c$具有和F相同的函數(shù)依賴集閉包。其意義在于：驗(yàn)證$F_c$比驗(yàn)證F更加容易、3NF算法必備

無關(guān)屬性

如果去除函數(shù)依賴中的一個(gè)屬性不改變?cè)摵瘮?shù)依賴集的閉包，則稱該屬性是無關(guān)屬性（extraneous）

形式化定義：考慮函數(shù)依賴集F及F中函數(shù)依賴 α → β

• 如果A ∈ α并且F邏輯蘊(yùn)涵(F – {α→ β}) ∪ {(α – A)→β}，則屬性A在α 中是無關(guān)的
• 如果A ∈ β并且函數(shù)依賴集(F – {α→β}) ∪ {α→(β–A)} 邏輯蘊(yùn)涵F，則屬性A在β中是無關(guān)的

eg: 給定 F = {A → C, AB → C}

• B 是AB → C中的無關(guān)屬性，因?yàn)?{A → C, AB → C}邏輯蘊(yùn)涵A → C (即從 AB → C中去掉B后的結(jié)果)

eg: 給定 F = {A → C, AB → CD}

• C是AB → CD中的無關(guān)屬性

驗(yàn)證方法

考慮函數(shù)依賴集F及F中的函數(shù)依賴α → β.
驗(yàn)證屬性A ∈ α 是不是多余的

使用F中的函數(shù)依賴計(jì)算屬性集閉包$(\alpha –A{)}^{+}$

驗(yàn)證$(\alpha –A{)}^{+}$ 是否包含β；如果包含，那么A 是多余屬性

驗(yàn)證屬性A ∈ β 在 β 中是否多余

使用函數(shù)依賴集F’= (F –{α → β}) ∪ {α →(β–A)}計(jì)算${\alpha }^{+}$

驗(yàn)證${\alpha }^{+}$ 是否包含A；如果包含，那么A 在α中是多余屬性

正則覆蓋

計(jì)算F的正則覆蓋算法：首先，初始化Fc= F； repeat使用合并律將Fc中的形如α1 → β1 及 α1 → β2 的依賴替換為 α1 → β1β2在Fc中找出 在α或?中含無關(guān)屬性的函數(shù)依賴α → β/* 注意：使用Fc而不是F檢驗(yàn)無關(guān)屬性*/若發(fā)現(xiàn)無關(guān)屬性則將它從Fc中的α → β中刪除 until Fc 不再發(fā)生變化

注意：在刪除了某些無關(guān)屬性后可能需要使用合并律，因此合并律會(huì)重復(fù)應(yīng)用

F的正則覆蓋Fc是一個(gè)函數(shù)依賴集 ，具有如下特性：

• F 邏輯蘊(yùn)涵Fc中的所有函數(shù)依賴
• Fc邏輯蘊(yùn)涵F中的所有函數(shù)依賴
• Fc中任何函數(shù)依賴都不含無關(guān)屬性
• Fc中函數(shù)依賴的左半部都是不同的

R = (A, B, C) F = { A → BC，B → C，A → B，AB → C }?合并 A → BC 和 A → B ，形成 A → BC修改Fc1為{ A → BC, B → C, AB → C }?A在AB → C中是無關(guān)屬性利用Fc1檢驗(yàn)(AB-A)＋是否包含C包含，則修改Fc2為{ A → BC, B → C }?C在A → BC中是無關(guān)屬性計(jì)算F’｛A → B, B → C｝下A＋閉包是否包含C包含，則修改Fc3為｛A → B, B → C｝

正則覆蓋是
$$\begin{gathered} A\to B \\ B\to C \end{gathered}$$

無損分解

對(duì)于R = (R1, R2), 我們要求模式R上的所有可能關(guān)系r都有
$$r={\Pi }_{R1}(r)?{\Pi }_{R2}(r)$$

如果下面的依賴中至少有一個(gè)屬于$F^{+}$，那么將R分解成 R1 和R2 是無損分解連接:
$$\begin{gathered} R1\cap R2\to R1 \\ R1\cap R2\to R2 \end{gathered}$$
即 R1 ∩ R2 是R1或R2的超碼

上述函數(shù)依賴測(cè)試只是無損連接分解的一個(gè)充分條件；只有當(dāng)所有約束都是函數(shù)依賴時(shí)，它才是必要條件(某些情況下，即使不存在函數(shù)依賴的情況下，仍可保證一個(gè)分解是無損分解)

eg

R = ( A, B, C ) F = { A → B, B → C } // 可以通過兩種方式分解 1.R1 = (A, B), R2 = (B, C) 無損連接分解： R1 ∩ R2 = { B }B→ BC2. R1 = (A, B), R2 = (A, C)無損連接分解： R1 ∩ R2= { A }A → AB

保持依賴

F為模式R上的一個(gè)函數(shù)依賴集，R1,R2, … , Rn為R的一個(gè)分解。F在Ri上的限定是$F^{+}$中所有只包含Ri中屬性的函數(shù)依賴的集合Fi

方法一（圖8-10）：令$F’=F_1\cup F_2\cup \dots \cup F_n$。 F’ 是模式R上的一個(gè)函數(shù)依賴集

• 如果下面的式子成立，那么分解是保持依賴的
  $$(F’{)}^{+}=F^{+}$$
• 稱具有性質(zhì)$(F’{)}^{+}=F^{+}$的分解為保持依賴的分解

方法二（充要條件）：當(dāng)R分解成R1, R2, …, Rn后，應(yīng)用以下算法，驗(yàn)證F中每一個(gè)函數(shù)依賴α → β 是否被保持：

result = α while (result發(fā)生變化) dofor each 分解后的Rit =((result ∩ Ri)^+) ∩ Riresult = result ∪ t

• 如果result 包含β中的所有屬性，那么函數(shù)依賴 α → β 被保持
• 可以將這個(gè)驗(yàn)證應(yīng)用到所有F中的依賴，來驗(yàn)證這個(gè)分解是否保持依賴
• 方法的好處：沒有計(jì)算F在Ri上的限定并使用它計(jì)算result 的屬性閉包，而是使用F上（result ∩ Ri）上的屬性閉包得到一個(gè)相同的結(jié)果`

eg

R = (A, B, C) F = {A → B, B → C} // 可以通過兩種方式分解R1 = (A, B), R2 = (B, C) 無損連接分解： 保持依賴R1 ∩ R2 = {B} and B → BCR1 = (A, B), R2 = (A, C) 無損連接分解： 不保持依賴 R1 ∩ R2 = {A} and A → AB(不計(jì)算R1 \Join R2, 無法驗(yàn)證B →C)

分解算法

對(duì)于$F^{+}$中非平凡依賴$\alpha \to \beta$驗(yàn)證是否違反BC范式

計(jì)算${\alpha }^{+}$

檢驗(yàn)是否包含R的所有屬性，驗(yàn)證是否是R的超碼

檢查R是否屬于BCNF，檢查F的函數(shù)依賴是否違反BCNF（如果F中沒有違反BCNF的函數(shù)依賴，那么F+中也不會(huì)有違反BCNF的函數(shù)依賴）

在檢測(cè)由關(guān)系R分解后的關(guān)系Ri是否滿足BCNF范式時(shí)，只使用F是不正確的

R = (A, B, C, D, E), F = { A → B, BC → D} ? 將R 分解成R1 = (A,B) 和 R2 = (A,C,D, E) ? F中沒有一個(gè)依賴僅包含來自(A,C,D,E)的屬性，所以我們可能誤認(rèn)為R2滿足BCNF ? 事實(shí)上，F+中有一個(gè)函數(shù)依賴AC → D，這表明R2不屬于BCNF

檢查R分解后的關(guān)系Ri是否屬于BCNF

• 使用F在Ri上的限定檢測(cè)$R_i$是否滿足BCNF (即，$F^{+}$中只包含$R_i$中的屬性的FD)
• 使用R中成立的原來的依賴集F 進(jìn)行以下測(cè)試
  • 對(duì)每個(gè)屬性集$\alpha \in R_i$, 確保${\alpha }^{+}$（在F下的）要么不包含$R_i?\alpha$的任何屬性，要么包含$R_i$的所有屬性
  • 如果F中的某些函數(shù)依賴$\alpha \to \beta$違反了該條件，那么
    如下函數(shù)依賴出現(xiàn)在F+中： $\alpha \to ({\alpha }^{+}?\alpha )\cap R_i$則Ri違反了BCNF
    
    我們將關(guān)系模式R分解成：
• $(\alpha \cup \beta )$
• $(R?(\beta ?\alpha ))$

$\alpha$ = dept_name
$\beta$ = building, budget

inst_dept

• $(\alpha \cup \beta )$ = ( dept_name, building, budget )
• $(R?(\beta ?\alpha ))$ = ( ID, name, salary, dept_name )

example

class (course_id, title, dept_name, credits, sec_id, semester, year, building, room_number, capacity, time_slot_id)# 函數(shù)依賴 course_id → title, dept_name, credits building, room_number → capacity course_id, sec_id, semester, year → building, room_number, time_slot_id候選碼{course_id, sec_id, semester, year}.

分析：
course_id→ title, dept_name, credits 不符合BCNF要求
但是 {building, room_number} 不是class-1的超碼
拆成三部分

R = (J, K, L ) F = {JK → L， L → K }

兩個(gè)候選碼：JK 和JL
?R 不滿足BCNF
?R 滿足3NF
?R 的任何分解都不可能保持
$$JK\to L$$
?這意味著要驗(yàn)證 JK → L 需要連接操作

?BCNF分解可能無法做到保持依賴
?能夠有效的驗(yàn)證更新是否違反函數(shù)依賴很重要
解決方法：采用一個(gè)稍弱的范式，第三范式

允許冗余（會(huì)引起問題）

但是函數(shù)依賴可以在不進(jìn)行連接操作的情況下在單個(gè)關(guān)系上檢驗(yàn)

總是能夠在無損連接及保持依賴的情況下分解成3NF

關(guān)系dept_advisor:
dept_advisor (s_ID, i_ID, dept_name)
F = { s_ID, dept_name → i_ID, i_ID → dept_name }

兩個(gè)候選碼: s_ID, dept_name, 和 i_ID, s_ID

R 是3NF

• s_ID, dept_name → i_ID
  • s_ID，dept_name 是超碼
• i_ID → dept_name
  • $\beta ?\alpha$= dept_name 在一個(gè)候選碼中

冗余覆蓋

? 信息重復(fù)

R中( l1, k1)

dept_advisor中(i_ID, dept_name)

? 需要使用空值

R中沒有對(duì)應(yīng)l2, k2的J值.

dept_advisor (s_ID，i_ID, dept_name) 沒有學(xué)生信息時(shí)

cust_banker_branch = (customer_id, employee_id, branch_name, type)函數(shù)依賴是: 1. customer_id, employee_id → branch_name, type 2. employee_id → branch_name 3. customer_id, branch_name → employee_id

計(jì)算正則覆蓋

? 1 st 依賴中是branch_name多余的 ? 沒有其他冗余屬性,所以得到 FC =customer_id, employee_id → typeemployee_id → branch_namecustomer_id, branch_name → employee_id產(chǎn)生下面的3NF模式: (customer_id, employee_id, type) <- primary key(c_id, e_id) (employee_id, branch_name) <- primary key(e_id) (customer_id, branch_name, employee_id)<- primary key(c_id, b_name)

(customer_id, employee_id, type ) 包含了原模式的一個(gè)候選碼，因此沒有其他關(guān)系模式需要添加

檢測(cè)并刪除類似(employee_id, branch_name)的模式，這個(gè)模式是其它模式的子集

由此產(chǎn)生的簡化3NF模式為:

(customer_id, employee_id, type) (customer_id, branch_name, employee_id)

BC和3的比較

BCNF和3NF的比較
? 總能夠把一個(gè)關(guān)系分解為多個(gè)滿足3NF的關(guān)系，并且:
?分解是無損的
?保持依賴
?可能存在信息冗余
? 總能夠把一個(gè)關(guān)系分解為多個(gè)滿足BCNF的關(guān)系，并且:
?分解是無損的
?可能不滿足保持依賴

? 關(guān)系數(shù)據(jù)庫設(shè)計(jì)目標(biāo)：
?BCNF
?無損
?保持依賴
? 如果不能同時(shí)達(dá)到上述三個(gè)目標(biāo)，選擇接受下面的其中一個(gè)
?缺少保持依賴
?使用3NF，可能帶來冗余
? 除了可以通過用主碼外，SQL不提供指定函數(shù)依賴的途徑.
特殊的FD可以使用斷言，但是測(cè)試代價(jià)太高（目前不被大多
數(shù)數(shù)據(jù)庫所支持）
? 即使我們能夠得到保持依賴的分解，使用SQL 還是不能有效
地測(cè)試一個(gè)左邊不是主碼的函數(shù)依賴

review
?什么是有損分解、無損分解？
?什么是原子域和第一范式？
?什么是函數(shù)依賴？
?什么是BCNF和3NF？
?什么是邏輯蘊(yùn)含？函數(shù)依賴集的閉包、屬性集
的閉包、正則覆蓋？
?如何將一個(gè)關(guān)系模式分解為屬于BCNF、3NF
的關(guān)系模式

總結(jié)

以上是生活随笔為你收集整理的数据库理论 05 关系数据库设计——基于《数据库系统概念》第七版的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。