資料模組化與資料庫設計

• 資料模組化之思想與方法
• • E-R模型
  • Chen方法
  • E-R模型表達方法之Crow’s foot方法
• 資料模組化之工程化方法及案例分析
• 函數依賴及其公理/定理
• 關系模式設計之規範形式
• 模式分解存在什麼問題

資料模組化之思想與方法

E-R模型

給出了一組基本概念，用這組概念可以刻畫資訊世界

實體

屬性：單一屬性與複合屬性，單值屬性和多值屬性，可空值屬性和非空值屬性，導出屬性

聯系：一進制聯系（當同一實體的不同執行個體參與一個聯系時，為差別各執行個體參與聯系的方式，需要顯式指明其角色(role)）、二進制聯系和多元聯系。聯系的基數有一對一、 一對多、多對多，完全參與聯系、部分參與聯系

關鍵字/碼

Chen方法

1:1聯系：箭頭直線，由聯系指向實體

1:m聯系：指向1端為箭頭直線，指向多端為無箭頭直線

m:n聯系：無箭頭直線

完全參與聯系：雙直線

部分參與聯系：單直線

E-R模型表達方法之Crow’s foot方法

資料模組化之工程化方法及案例分析

IDEF1x是一種圖示化資料模組化方法，是一種工程化模組化方法

獨立實體：一個實體的執行個體都被唯一的辨別而不決定于它與其他實體的聯系

從屬實體：一個實體的執行個體的唯一辨別需要依賴于該實體與其他實體的聯系

獨立實體用直角方形框，從屬實體用圓角方形框表示。實體用實體名/實體号辨別

獨立實體的主關鍵字沒有外鍵，從屬實體的主關鍵字含有外鍵。從屬實體的執行個體依賴于獨立實體執行個體存在而存在

關鍵字，被區分為主關鍵字和次關鍵字

外來關鍵字：是其他實體的關鍵字

标定聯系：子實體的執行個體都是由它與父實體的聯系而确定。父實體的主關鍵字是子實體主關鍵字的一部分。

非标定聯系：子實體的執行個體能夠被唯一辨別而無需依賴與其實體的聯系。父實體的主關鍵字不是子實體的主關鍵字。

非确定聯系：即實體之間的多對多的聯系。非确定聯系必須分解為若幹個一對多的聯系來表達。非确定聯系通過引入相交實體

(Intersection Entity)或者稱相關實體(Associative Entity)來分解為若幹個一對多的聯系來表達。

确定性聯系通過屬性繼承實作兩實體之間的聯系。非确定性聯系通過引入相交實體實作兩實體的聯系。

分類聯系：一個實體執行個體是由一個一般實體執行個體及多個分類實體執行個體構成的

一個一般實體是若幹具體實體(分類實體)的類

分類實體與一般實體具有相同的主關鍵字

不同分類實體除具有一般實體特征外，各自還可能具有不同的屬性特征

具體化(Specialization)

實體的執行個體集中，某些執行個體子集具有差別于該執行個體集内其它執行個體的特性，可以根據這些差異特性對該執行個體集進行分組/分類，這一分組/分類的過程稱作具體化。自頂向下、逐漸求精。

泛化(Generalization)

若幹個實體根據共有的性質，可以合成一個較高層的實體。泛化是一個高層實體與若幹個低層實體之間的包含關系。自底向上、逐漸合成。

作用/角色(Role)：當一個實體與其父實體有多種聯系時，此時需使用“作用/角色”來區分每一種聯系。

函數依賴及其公理/定理

函數依賴:設R(U)是屬性集合U={A1,A2,…,An}上的一個關系模式，X,Y是U上的兩個子集，若對R(U)的任意一個可能的關系r,r中不可能有兩個元組滿足在X中的屬性值相等而在Y中的屬性值不等，則稱“X函數決定Y”或“Y函數依賴于X”,記作X->Y。

在R(U)中，若X->Y并且對于X的任何真子集X’都有X’不能函數決定Y,則稱Y完全函數依賴于X,否則稱Y部分函數依賴于X。

在R(U)中，若X->Y，Y->Z且Y不屬于X,Z不屬于Y, Z不屬于X,Y不依賴于X,則稱Z傳遞函數依賴于X。

設K為R(U)中的屬性或屬性組合，若U完全函數依賴于K,則稱K為R(U)上的候選鍵(Candidate Key)。可任選一候選鍵作為R的主鍵(Primary Key)；包含在任一候選鍵中的屬性稱主屬性(Prime Attribute),其他屬性稱非主屬性；若K是R的一個候選鍵，S包含K,則稱S為R的一個超鍵(Super Key)。

外來鍵：若R(U)中的屬性或屬性組合X并非R的候選鍵，但X卻是另一關系的候選鍵，則稱X為R的外來鍵(Foreign Key)，簡稱外鍵。

邏輯蘊涵：設F是關系模式R(U)中的一個函數依賴集合，X,Y是R的屬性子集，如果從F中的函數依賴能夠推導出X->Y，則稱F邏輯蘊涵X->Y, 或稱X->Y是F的邏輯蘊涵。

閉包：被F邏輯蘊涵的所有函數依賴集合稱為F的閉包(Closure)，記作 F+。

若F+ = F,則說F是一個全函數依賴族(函數依賴完備集)。

設R(U)是屬性集U={A1,A2,…,An}上的一個關系模式，F為R(U)的一組函數依賴，記為R(U,F),則有如下規則成立：

[A1]自反律(Reflexivity rule)：若Y屬于X屬于U,則X->Y被F邏輯蘊涵。

[A2]增廣律(Augmentation rule)：若X->Y屬于F, 且Z屬于U,則XZ ->YZ被F邏輯蘊涵。

[A3]傳遞律(Transtivity rule)：若X->Y屬于F,且Y->Z,則X->Z被F邏輯蘊涵。

引理：

合并律(Union Rule)：若X->Y且X->Z,則X->YZ

僞傳遞律(Pseudo Transitivity)：若X->Y且WY->Z,則XW->Z

分解律(Decomposition?Rule)：若X->Y且Z屬于Y,則X->Z。

如果 A1,A2,…,An是屬性，則X->A1,A2,…,An當且僅當對每個Ai有X->A(1<= i<=n).

屬性(集)閉包對R(U,F),X屬于U,U={A1,A2,…,An},令：X+F ={Ai|用Armstrong Axiom A1,A2,A3可從F導出X->Ai }稱X+F為X關于F的屬性(集)閉包。注：顯然X屬于 X+F。

引理：

X->Y可從F由Armstrong Axiom導出，當且僅當Y屬于 X+F 。

Armstrong Axiom A1,A2,A3是有效的和完備的。公理的完備性是指被F邏輯蘊涵的所有函數依賴都能由公理A1,A2,A3在F基礎上推出。

覆寫(Cover)對R(U)上的兩個函數依賴集合F、G,如果F+= G+，則稱F和G是等價的，也稱F覆寫G或者G覆寫F。

引理：F+ = G+ 、 F 屬于 G+ 且 G 屬于F+，可以互相推導。

每個函數依賴集F可被一個其右端至多有一個屬性的函數依賴之集G覆寫。

最小覆寫

若F滿足以下條件，則稱F為最小覆寫(minimal Cover)或最小依賴集(minimal set of Functional Depandency)：

1)F中每個函數依賴的右部是單個屬性；

2)對任何X->A屬于F,有F- {X->A}不等價于F；

3)對任何X->A屬于F,Z屬于X,(F-{X->A})并上{Z->A}不等價于F。

[定理]：每個函數依賴集F都有等價的最小覆寫F’

關系模式設計之規範形式

1NF

若關系模式R(U)中關系的每個分量都是不可分的資料項(值、原子)，則稱R(U)屬于第一範式。1NF要求關系中不能有複合屬性、多值屬性及其組合。

2NF

若R(U)滿足1NF且 U中的每一非主屬性完全函數依賴于候選鍵，則稱R(U)屬于第二範式。第二範式消除了非主屬性對候選鍵的部分依賴。

3NF

若R(U，F)滿足2NF 且 R中不存在這樣的情況：候選鍵X，屬性組Y屬于U和非主屬性A,且A不屬于X,A不屬于Y,Y不依賴于X,Y不屬于X，使得X->Y，Y->A成立。滿足以上條件則稱R(U)屬于第三範式。第3範式消除了非主屬性對侯選鍵的傳遞依賴。

BCNF

若R(U，F)屬于1NF,若對于任何X->Y屬于F(或X->A屬于F),當Y屬于X(或A不屬于X)時，X必含有候選鍵，則稱R(U)屬于Boyce-Codd範式。

有不依賴于候選鍵的其他函數依賴不滿足BCNF。

多值依賴

對R(U),設X,Y屬于U,若對于R(U)的任一關系r,若元組t屬于r,s屬于r,t[X]=s[X],則必有u屬于r,v屬于r使得：

(1)u[X]=v[X]=t[X]=s[X]

(2)u[Y]=t[Y]且u[U-X-Y]=s[U-X-Y]

(3)v[Y]=s[Y]且v[U-X-Y]=t[U-X-Y]

均成立，則稱Y多值依賴于X,或說X多值決定Y,記作X->->Y。

多值依賴的特性

1)直覺地，對于X給定值，Y有一組值與之對應(0或n個)且這組Y值不以任何方式與U-X-Y中屬性值相聯系，有X->->Y。

2)若交換t,s的Y值而得到的新元組仍在r中，則X->->Y。

3)X,Y不必不相交，u,v可以與t,s相同。

4)函數依賴是多值依賴的特例。

5)令Z=U-X-Y,有X->->Z,若Z等于空,則必有X->->Y。

4NF

設 R(U)屬于1NF, D是其上的一組依賴 (函數依賴，多值依賴 )，對任意X->->Y 屬于D,若Y不等于空，Y不屬于X,XY不等于U，必有X為超鍵，則稱R(U)滿足第四範式。第四範式消除了非主屬性對候選鍵以外屬性的多值依賴。如果有多值依賴，則一定依賴于候選鍵。

若R上僅存在函數依賴，則若有R屬于BCNF即有R屬于4NF,反之，若R屬于4NF，也有 R屬于BCNF。

W4NF

設 R(U)屬于3NF, 若 R 上 的 任 何 互 補 多 值 依 賴 X->->Y(XY不等于U, Y-X不為空) 和X->->(R-X-Y)中必有一個是函數依賴，則稱R是弱第四範式的。注：W4NF不一定是BCNF,反之亦然。

模式分解存在什麼問題

模式分解

關系模式R(U)的分解是指用R的一組子集p={R1(U1),…,Rk(Uk)}來代替它。其中U= U1并 U2并…并 Uk；Ui=不等于 Uj (i不等于j)。

注：為便于後面叙述，我們用Ri 代替Ri(Ui), R代替R(U)。

對于關系模式R的任一關系r, 它向p的投影連接配接記為mp®：mp® = R1® jion … joinRk®

無損連接配接分解

對于關系模式R(U, F), U是屬性全集，F是函數依賴集合，p={R1,…,Rk}是R的一個分解，如果對于R的任何滿足函數依賴集F的關系r, 有

r= mp®, 則稱p是R相對于F的一個無損連接配接分解。

保持依賴分解

對于關系模式R(U, F), U是屬性全集，F是函數依賴集合，p={R1,…,Rk}是R的一個分解，如在派Ri(F)中的所有依賴之并集(i=1,…,k)邏輯蘊涵F的每個依賴，則稱分解p保持依賴集F。其中派Ri(F)是F在Ri上的投影，即F中的任一投影X->Y，如果X, Y均包含于Ri ,則X->Y屬于Ri(F)。Ri 指Ri的屬性集。

連接配接依賴

設R為一關系模式，p={ R1, … , Rn }為R的一個分解，若對R的任一關系r均有：rn目 = 派R1® 派R2® … 派Rn® , 則稱R滿足n目連接配接依賴，記為JD[ R1,…,Rn], 或記為n-JD。

5NF

當且僅當關系模式R的每個連接配接依賴均按其候選鍵進行連接配接運算時(均由R的候選鍵所隐含)，則稱R是第五範式的。