數(shù)據(jù)庫原理第6章

2023/2/11數(shù)據(jù)庫系統(tǒng)概論AnIntroductiontoDatabaseSystem第六章關(guān)系數(shù)據(jù)理論2023/2/12第六章關(guān)系數(shù)據(jù)理論6.1問題的提出6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)*6.4模式的分解6.5小結(jié)2023/2/136.1問題的提出關(guān)系數(shù)據(jù)庫邏輯設(shè)計(jì)針對(duì)具體問題，如何構(gòu)造一個(gè)適合于它的數(shù)據(jù)模式數(shù)據(jù)庫邏輯設(shè)計(jì)的工具──關(guān)系數(shù)據(jù)庫的規(guī)范化理論2023/2/14

問題的提出一、概念回顧二、關(guān)系模式的形式化定義三、什么是數(shù)據(jù)依賴四、關(guān)系模式的簡(jiǎn)化定義五、數(shù)據(jù)依賴對(duì)關(guān)系模式影響2023/2/15一、概念回顧關(guān)系：描述實(shí)體、屬性、實(shí)體間的聯(lián)系。從形式上看，它是一張二維表，是所涉及屬性的笛卡爾積的一個(gè)子集。關(guān)系模式：用來定義關(guān)系。關(guān)系數(shù)據(jù)庫：基于關(guān)系模型的數(shù)據(jù)庫，利用關(guān)系來描述現(xiàn)實(shí)世界。從形式上看，它由一組關(guān)系組成。關(guān)系數(shù)據(jù)庫的模式：定義這組關(guān)系的關(guān)系模式的全體。2023/2/16二、關(guān)系模式的形式化定義關(guān)系模式由五部分組成，即它是一個(gè)五元組：

R(U,D,DOM,F)R：關(guān)系名U：組成該關(guān)系的屬性名集合D：屬性組U中屬性所來自的域DOM：屬性向域的映象集合F：屬性間數(shù)據(jù)的依賴關(guān)系集合2023/2/17三、什么是數(shù)據(jù)依賴1.完整性約束的表現(xiàn)形式限定屬性取值范圍：例如學(xué)生成績(jī)必須在0-100之間定義屬性值間的相互關(guān)連（主要體現(xiàn)于值的相等與否），這就是數(shù)據(jù)依賴，它是數(shù)據(jù)庫模式設(shè)計(jì)的關(guān)鍵2023/2/18什么是數(shù)據(jù)依賴（續(xù)）2.數(shù)據(jù)依賴是通過一個(gè)關(guān)系中屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間的相互關(guān)系是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象是數(shù)據(jù)內(nèi)在的性質(zhì)是語義的體現(xiàn)2023/2/19什么是數(shù)據(jù)依賴（續(xù)）3.數(shù)據(jù)依賴的類型函數(shù)依賴（FunctionalDependency，簡(jiǎn)記為FD）多值依賴（MultivaluedDependency，簡(jiǎn)記為MVD）其他2023/2/110四、關(guān)系模式的簡(jiǎn)化表示關(guān)系模式R（U,D,DOM,F）簡(jiǎn)化為一個(gè)三元組：

R（U,F）當(dāng)且僅當(dāng)U上的一個(gè)關(guān)系r滿足F時(shí)，r稱為關(guān)系模式R（U,F）的一個(gè)關(guān)系2023/2/111五、數(shù)據(jù)依賴對(duì)關(guān)系模式的影響例：描述學(xué)校的數(shù)據(jù)庫：

學(xué)生的學(xué)號(hào)（Sno）、所在系（Sdept） 系主任姓名（Mname）、課程名（Cname） 成績(jī)（Grade）單一的關(guān)系模式：Student<U、F>U＝｛Sno,Sdept,Mname,Cname,Grade｝2023/2/112數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)）學(xué)校數(shù)據(jù)庫的語義：

⒈一個(gè)系有若干學(xué)生，一個(gè)學(xué)生只屬于一個(gè)系；⒉一個(gè)系只有一名主任；⒊一個(gè)學(xué)生可以選修多門課程，每門課程有若干學(xué)生選修；⒋每個(gè)學(xué)生所學(xué)的每門課程都有一個(gè)成績(jī)。

2023/2/113數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)）

屬性組U上的一組函數(shù)依賴F：

F＝｛Sno→Sdept,Sdept→Mname,(Sno,Cname)→Grade｝

SnoCnameSdeptMnameGrade2023/2/114關(guān)系模式Student<U,F>中存在的問題⒈數(shù)據(jù)冗余太大浪費(fèi)大量的存儲(chǔ)空間

例：每一個(gè)系主任的姓名重復(fù)出現(xiàn)⒉更新異常（UpdateAnomalies）數(shù)據(jù)冗余，更新數(shù)據(jù)時(shí)，維護(hù)數(shù)據(jù)完整性代價(jià)大。 例：某系更換系主任后，系統(tǒng)必須修改與該系學(xué)生有關(guān)的每一個(gè)元組2023/2/115關(guān)系模式Student<U,F>中存在的問題⒊插入異常（InsertionAnomalies）該插的數(shù)據(jù)插不進(jìn)去例，如果一個(gè)系剛成立，尚無學(xué)生，我們就無法把這個(gè)系及其系主任的信息存入數(shù)據(jù)庫。⒋刪除異常（DeletionAnomalies）不該刪除的數(shù)據(jù)不得不刪 例，如果某個(gè)系的學(xué)生全部畢業(yè)了，我們?cè)趧h除該系學(xué)生信息的同時(shí)，把這個(gè)系及其系主任的信息也丟掉了。2023/2/116數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)）結(jié)論：Student關(guān)系模式不是一個(gè)好的模式?！昂谩钡哪Ｊ剑翰粫?huì)發(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應(yīng)盡可能少。原因：由存在于模式中的某些數(shù)據(jù)依賴引起的解決方法：通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴。2023/2/1176.2規(guī)范化

規(guī)范化理論正是用來改造關(guān)系模式，通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。2023/2/1186.2.1函數(shù)依賴一、函數(shù)依賴二、平凡函數(shù)依賴與非平凡函數(shù)依賴三、完全函數(shù)依賴與部分函數(shù)依賴四、傳遞函數(shù)依賴2023/2/119一、函數(shù)依賴定義5.1設(shè)R(U)是一個(gè)屬性集U上的關(guān)系模式，X和Y是U的子集。若對(duì)于R(U)的任意一個(gè)可能的關(guān)系r，r中不可能存在兩個(gè)元組在X上的屬性值相等，而在Y上的屬性值不等，則稱“X函數(shù)確定Y”或“Y函數(shù)依賴于X”，記作X→Y。

X稱為這個(gè)函數(shù)依賴的決定屬性集(Determinant)。

Y=f(x)2023/2/120說明：

1.函數(shù)依賴不是指關(guān)系模式R的某個(gè)或某些關(guān)系實(shí)例滿足的約束條件，而是指R的所有關(guān)系實(shí)例均要滿足的約束條件。2.函數(shù)依賴是語義范疇的概念。只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴。例如“姓名→年齡”這個(gè)函數(shù)依賴只有在不允許有同名人的條件下成立3.數(shù)據(jù)庫設(shè)計(jì)者可以對(duì)現(xiàn)實(shí)世界作強(qiáng)制的規(guī)定。例如規(guī)定不允許同名人出現(xiàn)，函數(shù)依賴“姓名→年齡”成立。所插入的元組必須滿足規(guī)定的函數(shù)依賴，若發(fā)現(xiàn)有同名人存在，則拒絕裝入該元組。2023/2/121函數(shù)依賴（續(xù)）例:Student(Sno,Sname,Ssex,Sage,Sdept)

假設(shè)不允許重名，則有:Sno→Ssex，Sno→Sage,Sno→Sdept，Sno←→Sname,

Sname→Ssex，Sname→SageSname→Sdept但Ssex→Sage若X→Y，并且Y→X,則記為X←→Y。若Y不函數(shù)依賴于X,則記為X─→Y。2023/2/122二、平凡函數(shù)依賴與非平凡函數(shù)依賴在關(guān)系模式R(U)中，對(duì)于U的子集X和Y，如果X→Y，但YX，則稱X→Y是非平凡的函數(shù)依賴若X→Y，但YX,則稱X→Y是平凡的函數(shù)依賴?yán)涸陉P(guān)系SC(Sno,Cno,Grade)中，非平凡函數(shù)依賴：(Sno,Cno)→

Grade

平凡函數(shù)依賴：(Sno,Cno)→

Sno

(Sno,Cno)→Cno2023/2/123平凡函數(shù)依賴與非平凡函數(shù)依賴（續(xù)）任一關(guān)系模式，平凡函數(shù)依賴都是必然成立的，它不反映新的語義，因此若不特別聲明，我們總是討論非平凡函數(shù)依賴。2023/2/124三、完全函數(shù)依賴與部分函數(shù)依賴定義6.2在關(guān)系模式R(U)中，如果X→Y，并且對(duì)于X的任何一個(gè)真子集X’，都有

X’Y,則稱Y完全函數(shù)依賴于X，記作Xｆ

Y。若X→Y，但Y不完全函數(shù)依賴于X，則稱Y部分函數(shù)依賴于X，記作XPY。

2023/2/125完全函數(shù)依賴與部分函數(shù)依賴（續(xù)）例:在關(guān)系SC(Sno,Cno,Grade)中，由于：Sno→Grade，Cno→Grade，因此：(Sno,Cno)ｆGrade

2023/2/126四、傳遞函數(shù)依賴定義6.3在關(guān)系模式R(U)中，如果X→Y，Y→Z，且YX，Y→X，則稱Z傳遞函數(shù)依賴于X。注:如果Y→X，即X←→Y，則Z直接依賴于X。例:在關(guān)系Std(Sno,Sdept,Sloc)中，有：

Sno→Sdept，Sdept→Sloc

Sloc傳遞函數(shù)依賴于Sno2023/2/1276.2.2碼

定義6.4設(shè)K為關(guān)系模式R<U,F>中的屬性或?qū)傩越M合。若KｆU，則K稱為R的一個(gè)侯選碼（CandidateKey）。若關(guān)系模式R有多個(gè)候選碼，則選定其中的一個(gè)做為主碼（Primarykey）。主屬性與非主屬性ALLKEY2023/2/128外部碼

定義6.5關(guān)系模式R中屬性或?qū)傩越MX并非R的碼，但X是另一個(gè)關(guān)系模式的碼，則稱X是R的外部碼（Foreignkey）也稱外碼。主碼又和外部碼一起提供了表示關(guān)系間聯(lián)系的手段。2023/2/1296.2.3范式范式是符合某一種級(jí)別的關(guān)系模式的集合。關(guān)系數(shù)據(jù)庫中的關(guān)系必須滿足一定的要求。滿足不同程度要求的為不同范式。范式的種類：

第一范式(1NF)

第二范式(2NF)

第三范式(3NF) BC范式(BCNF)

第四范式(4NF)

第五范式(5NF)2023/2/1306.2.3范式各種范式之間存在聯(lián)系：某一關(guān)系模式R為第n范式，可簡(jiǎn)記為R∈nNF。2023/2/1316.2.42NF1NF的定義 如果一個(gè)關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項(xiàng)，則R∈1NF。第一范式是對(duì)關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫模式不能稱為關(guān)系數(shù)據(jù)庫。但是滿足第一范式的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式。2023/2/1322NF例:關(guān)系模式SLC(Sno,Sdept,Sloc,Cno,Grade)

Sloc為學(xué)生住處，假設(shè)每個(gè)系的學(xué)生住在同一個(gè)地方。函數(shù)依賴包括：

(Sno,Cno)fGrade

Sno→Sdept(Sno,Cno)P

Sdept

Sno→Sloc(Sno,Cno)P

Sloc

Sdept→Sloc2023/2/1332NFSLC的碼為(Sno,Cno)SLC滿足第一范式。非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno,Cno)SnoCnoGradeSdeptSlocSLC2023/2/134SLC不是一個(gè)好的關(guān)系模式(1)插入異常 假設(shè)Sno＝95102，Sdept＝IS，Sloc＝N的學(xué)生還未選課，因課程號(hào)是主屬性，因此該學(xué)生的信息無法插入SLC。(2)刪除異常假定某個(gè)學(xué)生本來只選修了3號(hào)課程這一門課?，F(xiàn)在因身體不適，他連3號(hào)課程也不選修了。因課程號(hào)是主屬性，此操作將導(dǎo)致該學(xué)生信息的整個(gè)元組都要?jiǎng)h除。2023/2/135SLC不是一個(gè)好的關(guān)系模式(3)數(shù)據(jù)冗余度大如果一個(gè)學(xué)生選修了10門課程，那么他的Sdept和Sloc值就要重復(fù)存儲(chǔ)了10次。(4)修改復(fù)雜例如學(xué)生轉(zhuǎn)系，在修改此學(xué)生元組的Sdept值的同時(shí)，還可能需要修改住處（Sloc）。如果這個(gè)學(xué)生選修了K門課，則必須無遺漏地修改K個(gè)元組中全部Sdept、Sloc信息。2023/2/1362NF原因

Sdept、Sloc部分函數(shù)依賴于碼。解決方法

SLC分解為兩個(gè)關(guān)系模式，以消除這些部分函數(shù)依賴

SC（Sno，Cno，Grade）

SL（Sno，Sdept，Sloc）2023/2/1372NFSLC的碼為(Sno,Cno)SLC滿足第一范式。非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno,Cno)SnoCnoGradeSdeptSlocSLC2023/2/1382NF函數(shù)依賴圖：SnoCnoGradeSCSLSnoSdeptSloc2023/2/1392NF2NF的定義 定義5.6若關(guān)系模式R∈1NF，并且每一個(gè)非主屬性都完全函數(shù)依賴于R的碼，則R∈2NF。 例：SLC(Sno,Sdept,Sloc,Cno,Grade)∈1NF

SLC(Sno,Sdept,Sloc,Cno,Grade)∈2NF SC（Sno，Cno，Grade）∈2NFSL（Sno，Sdept，Sloc）∈2NF2023/2/140

第二范式（續(xù)）采用投影分解法將一個(gè)1NF的關(guān)系分解為多個(gè)2NF的關(guān)系，可以在一定程度上減輕原1NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。將一個(gè)1NF關(guān)系分解為多個(gè)2NF的關(guān)系，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。2023/2/1416.2.53NF例：2NF關(guān)系模式SL(Sno,Sdept,Sloc)中函數(shù)依賴：

Sno→Sdept

Sdept→Sloc

Sno→Sloc

Sloc傳遞函數(shù)依賴于Sno，即SL中存在非主屬性對(duì)碼的傳遞函數(shù)依賴。2023/2/1423NF函數(shù)依賴圖：SLSnoSdeptSloc2023/2/1433NF解決方法采用投影分解法，把SL分解為兩個(gè)關(guān)系模式，以消除傳遞函數(shù)依賴：SD（Sno，Sdept）

DL（Sdept，Sloc）SD的碼為Sno，DL的碼為Sdept。2023/2/1443NFSD的碼為Sno，DL的碼為Sdept。SnoSdeptSDSdeptSlocDL2023/2/1453NF3NF的定義 定義5.8關(guān)系模式R<U，F(xiàn)>

中若不存在這樣的碼X、屬性組Y及非主屬性Z（ZY）,使得X→Y，Y→X，Y→Z，成立，則稱R<U，F(xiàn)>∈3NF。例，SL(Sno,Sdept,Sloc)∈2NFSL(Sno,Sdept,Sloc)∈3NFSD（Sno，Sdept）∈3NFDL（Sdept，Sloc）∈3NF2023/2/1463NF若R∈3NF，則R的每一個(gè)非主屬性既不部分函數(shù)依賴于候選碼也不傳遞函數(shù)依賴于候選碼。如果R∈3NF，則R也是2NF。采用投影分解法將一個(gè)2NF的關(guān)系分解為多個(gè)3NF的關(guān)系，可以在一定程度上解決原2NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。將一個(gè)2NF關(guān)系分解為多個(gè)3NF的關(guān)系后，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。2023/2/1476.2.6BC范式（BCNF）定義6.9設(shè)關(guān)系模式R<U，F(xiàn)>∈1NF，如果對(duì)于R的每個(gè)函數(shù)依賴X→Y，若Y不屬于X，則X必含有候選碼，那么R∈BCNF。若R∈BCNF每一個(gè)決定屬性集（因素）都包含（候選）碼R中的所有屬性（主，非主屬性）都完全函數(shù)依賴于碼R∈3NF（證明）若R∈3NF則R不一定∈BCNF2023/2/148BCNF例：在關(guān)系模式STJ（S，T，J）中，S表示學(xué)生，T表示教師，J表示課程。每一教師只教一門課。每門課由若干教師教，某一學(xué)生選定某門課，就確定了一個(gè)固定的教師。某個(gè)學(xué)生選修某個(gè)教師的課就確定了所選課的名稱：(S，J)→T，(S，T)→J，T→J2023/2/1496.2.6BCNF

SJTSTJSTJ2023/2/150BCNFSTJ∈3NF

(S，J)和(S，T)都可以作為候選碼

S、T、J都是主屬性STJ∈BCNFT→J，T是決定屬性集，T不是候選碼2023/2/151BCNF

解決方法：將STJ分解為二個(gè)關(guān)系模式：

SJ(S，J)∈BCNF，TJ(T，J)∈BCNF

沒有任何屬性對(duì)碼的部分函數(shù)依賴和傳遞函數(shù)依賴SJSTTJTJ2023/2/1523NF與BCNF的關(guān)系如果關(guān)系模式R∈BCNF，必定有R∈3NF如果R∈3NF，且R只有一個(gè)候選碼，則R必屬于BCNF。2023/2/153BCNF的關(guān)系模式所具有的性質(zhì)⒈所有非主屬性都完全函數(shù)依賴于每個(gè)候選碼⒉所有主屬性都完全函數(shù)依賴于每個(gè)不包含它的候選碼⒊沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性2023/2/1546.2.5多值依賴與第四范式（4NF）例:學(xué)校中某一門課程由多個(gè)教師講授，他們使用相同的一套參考書。 關(guān)系模式Teaching(C,T,B)

課程C、教師T和參考書B2023/2/155………課程C教員T參考書B

物理

數(shù)學(xué)

計(jì)算數(shù)學(xué)李勇王軍

李勇張平

張平周峰

普通物理學(xué)光學(xué)原理物理習(xí)題集

數(shù)學(xué)分析微分方程高等代數(shù)

數(shù)學(xué)分析

表6.12023/2/156普通物理學(xué)光學(xué)原理物理習(xí)題集普通物理學(xué)光學(xué)原理物理習(xí)題集數(shù)學(xué)分析微分方程高等代數(shù)數(shù)學(xué)分析微分方程高等代數(shù)…李勇李勇李勇王軍王軍王軍李勇李勇李勇張平張平張平

…物理物理物理物理物理物理數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)

…參考書B教員T課程C用二維表表示Teaching

2023/2/157多值依賴與第四范式（續(xù)）Teaching∈BCNF:Teach具有唯一候選碼(C，T，B)，即全碼Teaching模式中存在的問題

(1)數(shù)據(jù)冗余度大：有多少名任課教師，參考書就要存儲(chǔ)多少次

2023/2/158多值依賴與第四范式（續(xù)）

(2)插入操作復(fù)雜：當(dāng)某一課程增加一名任課教師時(shí)，該課程有多少本參照書，就必須插入多少個(gè)元組例如物理課增加一名教師劉關(guān)，需要插入兩個(gè)元組：（物理，劉關(guān)，普通物理學(xué)）（物理，劉關(guān)，光學(xué)原理）2023/2/159多值依賴與第四范式（續(xù)）(3)刪除操作復(fù)雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個(gè)元組(4)修改操作復(fù)雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個(gè)元組產(chǎn)生原因 存在多值依賴2023/2/160一、多值依賴定義6.10

設(shè)R(U)是一個(gè)屬性集U上的一個(gè)關(guān)系模式，X、Y和Z是U的子集，并且Z＝U－X－Y，多值依賴X→→Y成立當(dāng)且僅當(dāng)對(duì)R的任一關(guān)系r，r在（X，Z）上的每個(gè)值對(duì)應(yīng)一組Y的值，這組值僅僅決定于X值而與Z值無關(guān) 例Teaching（C,T,B）對(duì)于C的每一個(gè)值，T有一組值與之對(duì)應(yīng)，而不論B取何值2023/2/161一、多值依賴在R（U）的任一關(guān)系r中，如果存在元組t，s使得t[X]=s[X]，那么就必然存在元組w，vr，（w，v可以與s，t相同），使得w[X]=v[X]=t[X]，而w[Y]=t[Y]，w[Z]=s[Z]，v[Y]=s[Y]，v[Z]=t[Z]（即交換s，t元組的Y值所得的兩個(gè)新元組必在r中），則Y多值依賴于X，記為X→→Y。這里，X，Y是U的子集，Z=U-X-Y。

txy1z2sxy2z1wxy1z1vxy2z22023/2/162多值依賴（續(xù)）平凡多值依賴和非平凡的多值依賴

若X→→Y，而Z＝φ，則稱

X→→Y為平凡的多值依賴 否則稱X→→Y為非平凡的多值依賴2023/2/163多值依賴的性質(zhì)（1）多值依賴具有對(duì)稱性若X→→Y，則X→→Z，其中Z＝U－X－Y

多值依賴的對(duì)稱性可以用完全二分圖直觀地表示出來。（2）多值依賴具有傳遞性若X→→Y，Y→→Z，則X→→Z-Y2023/2/164多值依賴的對(duì)稱性

XiZi1Zi2…ZimYi1Yi2…Yin2023/2/165多值依賴的對(duì)稱性

物理普通物理學(xué)光學(xué)原理物理習(xí)題集李勇王軍2023/2/166多值依賴（續(xù)）（3）函數(shù)依賴是多值依賴的特殊情況。 若X→Y，則X→→Y。（4）若X→→Y，X→→Z，則X→→YZ。（5）若X→→Y，X→→Z，則X→→Y∩Z。（6）若X→→Y，X→→Z，則X→→Y-Z， X→→Z-Y。2023/2/167多值依賴與函數(shù)依賴的區(qū)別(1)有效性多值依賴的有效性與屬性集的范圍有關(guān)若X→→Y在U上成立，則在W（XYWU）上一定成立；反之則不然，即X→→Y在W（WU）上成立，在U上并不一定成立多值依賴的定義中不僅涉及屬性組X和Y，而且涉及U中其余屬性Z。一般地，在R（U）上若有X→→Y在W（WU）上成立，則稱X→→Y為R（U）的嵌入型多值依賴2023/2/168多值依賴與函數(shù)依賴的區(qū)別只要在R（U）的任何一個(gè)關(guān)系r中，元組在X和Y上的值滿足定義5.l（函數(shù)依賴），則函數(shù)依賴X→Y在任何屬性集W（XYWU）上成立。2023/2/169多值依賴（續(xù)）(2)若函數(shù)依賴X→Y在R（U）上成立，則對(duì)于任何Y'Y均有X→Y'成立多值依賴X→→Y若在R(U)上成立，不能斷言對(duì)于任何Y'Y有X→→Y'成立2023/2/170二、第四范式（4NF）定義6.10關(guān)系模式R<U，F(xiàn)>∈1NF，如果對(duì)于R的每個(gè)非平凡多值依賴X→→Y（YX），X都含有候選碼，則R∈4NF。如果R∈4NF，則R∈BCNF

不允許有非平凡且非函數(shù)依賴的多值依賴

允許的是函數(shù)依賴（是非平凡多值依賴）2023/2/171第四范式（續(xù)）例：Teach(C,T,B)∈4NF

存在非平凡的多值依賴C→→T，且C不是候選碼用投影分解法把Teach分解為如下兩個(gè)關(guān)系模式：

CT(C,T)∈4NF CB(C,B)∈4NF

C→→T，C→→B是平凡多值依賴

2023/2/1726.2規(guī)范化6.2.1第一范式（1NF）6.2.2第二范式（2NF）6.2.3第三范式（3NF）6.2.4BC范式（BCNF）6.2.5多值依賴與第四范式（4NF）5.2.6規(guī)范化2023/2/1736.2.6規(guī)范化關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計(jì)的工具。一個(gè)關(guān)系只要其分量都是不可分的數(shù)據(jù)項(xiàng)，它就是規(guī)范化的關(guān)系，但這只是最基本的規(guī)范化。規(guī)范化程度可以有多個(gè)不同的級(jí)別2023/2/174規(guī)范化（續(xù)）規(guī)范化程度過低的關(guān)系不一定能夠很好地描述現(xiàn)實(shí)世界，可能會(huì)存在插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題一個(gè)低一級(jí)范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式集合，這種過程就叫關(guān)系模式的規(guī)范化2023/2/175規(guī)范化（續(xù)）關(guān)系模式規(guī)范化的基本步驟

1NF ↓消除非主屬性對(duì)碼的部分函數(shù)依賴消除決定屬性2NF集非碼的非平↓消除非主屬性對(duì)碼的傳遞函數(shù)依賴凡函數(shù)依賴3NF ↓消除主屬性對(duì)碼的部分和傳遞函數(shù)依 賴

BCNF ↓消除非平凡且非函數(shù)依賴的多值依賴

4NF2023/2/176規(guī)范化的基本思想消除不合適的數(shù)據(jù)依賴的各關(guān)系模式達(dá)到某種程度的“分離”采用“一事一地”的模式設(shè)計(jì)原則讓一個(gè)關(guān)系描述一個(gè)概念、一個(gè)實(shí)體或者實(shí)體間的一種聯(lián)系。若多于一個(gè)概念就把它“分離”出去所謂規(guī)范化實(shí)質(zhì)上是概念的單一化2023/2/177規(guī)范化（續(xù)）不能說規(guī)范化程度越高的關(guān)系模式就越好在設(shè)計(jì)數(shù)據(jù)庫模式結(jié)構(gòu)時(shí)，必須對(duì)現(xiàn)實(shí)世界的實(shí)際情況和用戶應(yīng)用需求作進(jìn)一步分析，確定一個(gè)合適的、能夠反映現(xiàn)實(shí)世界的模式上面的規(guī)范化步驟可以在其中任何一步終止2023/2/178

設(shè)W（C,P,S,G,T,R）其中C為課程，P為教師，S為學(xué)生，G為成績(jī)，T為時(shí)間，R為教室。存在有如下函數(shù)依賴集

{(S,C)->G,(T,R)->C,(T,P)->R,(T,S)->R}

關(guān)系模式W的候選碼

1，W的規(guī)范化程度最高達(dá)到

2。若將W分解為3個(gè)關(guān)系模式W1(C,P)，W2(S,C,G)和W3(S,T,R,C)則W1規(guī)范化程度最高達(dá)到

3，W2規(guī)范化程度

4，W3規(guī)范化程度

5。2NFBCNFBCNF1NFT，S，P2023/2/179設(shè)關(guān)系模式R(A,B,C,D,E,P)，其中F={A->B,C->P,E->A,CE->D}求R的候選碼。CE設(shè)R(C,T,S,N,G)，其中F={C->T,CS->G,S->N}求R的候選碼。CS2023/2/180第六章關(guān)系數(shù)據(jù)理論6.1數(shù)據(jù)依賴6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)6.4模式的分解2023/2/1816.3數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊(yùn)含 定義5.11對(duì)于滿足一組函數(shù)依賴F的關(guān)系模式R<U，F(xiàn)>，其任何一個(gè)關(guān)系r，若函數(shù)依賴X→Y都成立,則稱

F邏輯蘊(yùn)含X→Y2023/2/182Armstrong公理系統(tǒng)一套推理規(guī)則，是模式分解算法的理論基礎(chǔ)用途求給定關(guān)系模式的碼從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴2023/2/1831.Armstrong公理系統(tǒng)

關(guān)系模式R<U，F(xiàn)>來說有以下的推理規(guī)則：Al.自反律（Reflexivity）：若Y

X

U，則X→Y為F所蘊(yùn)含。A2.增廣律（Augmentation）：若X→Y為F所蘊(yùn)含，且Z

U，則XZ→YZ為F所蘊(yùn)含。A3.傳遞律（Transitivity）：若X→Y及Y→Z為F所蘊(yùn)含，則X→Z為F所蘊(yùn)含。

注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F2023/2/184定理6.lArmstrong推理規(guī)則是正確的（l）自反律:若Y

X

U，則X→Y為F所蘊(yùn)含證:設(shè)Y

X

U

對(duì)R<U，F(xiàn)>

的任一關(guān)系r中的任意兩個(gè)元組t，s：若t[X]=s[X]，由于Y

X，有t[y]=s[y]，所以X→Y成立.自反律得證2023/2/185定理6.l(2)增廣律:若X→Y為F所蘊(yùn)含，且Z

U，則XZ→YZ為F所蘊(yùn)含。證：設(shè)X→Y為F所蘊(yùn)含，且Z

U。設(shè)R<U，F(xiàn)>

的任一關(guān)系r中任意的兩個(gè)元組t，s；若t[XZ]=s[XZ]，則有t[X]=s[X]和t[Z]=s[Z]；由X→Y，于是有t[Y]=s[Y]，所以t[YZ]=s[YZ]，所以XZ→YZ為F所蘊(yùn)含.增廣律得證。2023/2/186定理6.l(3)傳遞律：若X→Y及Y→Z為F所蘊(yùn)含，則

X→Z為F所蘊(yùn)含。證：設(shè)X→Y及Y→Z為F所蘊(yùn)含。對(duì)R<U，F(xiàn)>

的任一關(guān)系r中的任意兩個(gè)元組t，s。若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]；再由Y→Z，有t[Z]=s[Z]，所以X→Z為F所蘊(yùn)含.傳遞律得證。2023/2/1872.導(dǎo)出規(guī)則1.根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條推理規(guī)則：

合并規(guī)則：由X→Y，X→Z，有X→YZ。（A2，A3）

偽傳遞規(guī)則：由X→Y，WY→Z，有XW→Z。（A2，A3）

分解規(guī)則：由X→Y及ZY，有X→Z。（A1，A3）2023/2/188導(dǎo)出規(guī)則2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理5.1

引理6.lX→A1A2…Ak成立的充分必要條件是X→Ai成立（i=l，2，…，k）。2023/2/1893.函數(shù)依賴閉包定義6.l2在關(guān)系模式R<U，F(xiàn)>中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作F的閉包，記為F+。定義6.13設(shè)F為屬性集U上的一組函數(shù)依賴，X

U，XF+={A|X→A能由F根據(jù)Armstrong公理導(dǎo)出}，XF+稱為屬性集X關(guān)于函數(shù)依賴集F的閉包。2023/2/190F的閉包F={XY,YZ},F+計(jì)算是NP完全問題，XA1A2...An

F+={Xφ,Yφ,Zφ,XYφ,XZφ,YZφ,XYZφ,XX,YY,ZZ,XYX,XZX,YZY,XYZX,XY,YZ,XYY,XZY,YZZ,XYZY,XZ,YYZ,XYZ,XZZ,YZYZ,XYZZ,XXY,XYXY,XZXY,XYZXY,XXZ,XYYZ,XZXZ,XYZYZXYZ,XYXZ,XZXY,XYZXZ,XZYZ,XYXYZ,XZXYZ,XYZXYZ}2023/2/191關(guān)于閉包的引理引理6.2

設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y

U，X→Y能由F根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y

XF+用途將判定X→Y是否能由F根據(jù)Armstrong公理導(dǎo)出的問題，就轉(zhuǎn)化為求出XF+

，判定Y是否為XF+的子集的問題。2023/2/192求閉包的算法算法6.l求屬性集X（X

U）關(guān)于U上的函數(shù)依賴集F的閉包XF+

輸入：X，F(xiàn)輸出：XF+步驟：（1）令X（0）=X，i=0（2）求B，這里B={A|(

V)(

W)(V→WF∧VX（i）∧A

W)}；（3）X（i+1）=B∪X（i）

2023/2/193算法6.l（4）判斷X（i+1）=X

（i）嗎?（5）若相等或X（i）=U,則X（i）就是XF+,算法終止。（6）若否，則i=i+l，返回第（2）步。 對(duì)于算法6.l，令ai=|X（i）|，{ai

}形成一個(gè)步長(zhǎng)大于1的嚴(yán)格遞增的序列，序列的上界是|U|，因此該算法最多|U|-|X|次循環(huán)就會(huì)終止。2023/2/194函數(shù)依賴閉包[例]已知關(guān)系模式R<U，F(xiàn)>，其中U={A，B，C，D，E}；F={AB→C，B→D，C→E，EC→B，AC→B}。求（AB）F+

。解設(shè)X（0）=AB；(1)計(jì)算X（1）:逐一的掃描F集合中各個(gè)函數(shù)依賴，找左部為A，B或AB的函數(shù)依賴。得到兩個(gè)：

AB→C，B→D。于是X（1）=AB∪CD=ABCD。2023/2/195函數(shù)依賴閉包(2)因?yàn)閄（0）≠X（1），所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到AB→C，B→D，C→E，AC→B，于是X（2）=X（1）∪BCDE=ABCDE。(3)因?yàn)閄（2）=U，算法終止所以（AB）F+=ABCDE。2023/2/196設(shè)R（U，F(xiàn)），其中U={A,B,C,D,E,G}，F(xiàn)={AB->C,C->A,BC->D,ACD->B,D->EG,BE->C,CG->BD,CE->AG}求(BD)+(BD)+=U2023/2/1975.函數(shù)依賴集等價(jià)

定義6.14如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。2023/2/198函數(shù)依賴集等價(jià)的充要條件

引理6.3F+=G+的充分必要條件是

F

G+，和G

F+證:必要性顯然，只證充分性。（1）若FG+，則XF+

XG++。（2）任取X→YF+則有Y

XF+

XG++。 所以X→Y(G+）+=G+。即F+

G+。（3）同理可證G+

F+，所以F+=G+。2023/2/199函數(shù)依賴集等價(jià)要判定F

G+，只須逐一對(duì)F中的函數(shù)依賴X→Y，考察Y是否屬于XG++

就行了。因此引理6.3給出了判斷兩個(gè)函數(shù)依賴集等價(jià)的可行算法。2023/2/11006.最小依賴集

定義6.15如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。

(1)F中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性。

(2)F中不存在這樣的函數(shù)依賴X→A，使得F與F-{X→A}等價(jià)。

(3)F中不存在這樣的函數(shù)依賴X→A，X有真子集Z使得F-{X→A}∪{Z→A}與F等價(jià)?；?jiǎn)函數(shù)依賴除去冗余函數(shù)依賴除去冗余的決定因子2023/2/1101最小依賴集[例]對(duì)于6.l節(jié)中的關(guān)系模式S<U，F(xiàn)>，其中：

U={SNO，SDEPT，MN，CNAME，G}，

F={SNO→SDEPT，SDEPT→MN，（SNO，CNAME）→G}

設(shè)F’={SNO→SDEPT，SNO→MN，SDEPT→MN，(SNO，CNAME)→G，(SNO，SDEPT)→SDEPT}F是最小覆蓋，而F’不是。因?yàn)椋篎’-{SNO→MN}與F’等價(jià)

F’-{(SNO，SDEPT)→SDEPT}也與F’等價(jià)

F’-{(SNO，SDEPT)→SDEPT}∪{SNO→SDEPT}也與F’等價(jià)2023/2/11027.極小化過程定理6.3每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小函數(shù)依賴集Fm。此Fm稱為F的最小依賴集證:構(gòu)造性證明，依據(jù)定義分三步對(duì)F進(jìn)行“極小化處理”，找出F的一個(gè)最小依賴集。(1)逐一檢查F中各函數(shù)依賴FDi：X→Y，若Y=A1A2…Ak，k>2，則用{X→Aj

|j=1，2，…，k}來取代X→Y。

引理6.1保證了F變換前后的等價(jià)性。2023/2/1103極小化過程(2)逐一檢查F中各函數(shù)依賴FDi：X→A，令G=F-{X→A}，若AXG+，則從F中去掉此函數(shù)依賴。由于F與G=F-{X→A}等價(jià)的充要條件是AXG+

因此F變換前后是等價(jià)的。2023/2/1104極小化過程(3)逐一取出F中各函數(shù)依賴FDi：X→A，設(shè)X=B1B2…Bm，逐一考查Bi

（i=l，2，…，m），若A（X-Bi

）F+，則以X-Bi

取代X。由于F與F-{X→A}∪{Z→A}等價(jià)的充要條件是AZF+，其中Z=X-Bi

因此F變換前后是等價(jià)的。2023/2/1105極小化過程

由定義，最后剩下的F就一定是極小依賴集。因?yàn)閷?duì)F的每一次“改造”都保證了改造前后的兩個(gè)函數(shù)依賴集等價(jià)，因此剩下的F與原來的F等價(jià)。證畢定理6.3的證明過程也是求F極小依賴集的過程2023/2/1106極小化過程[例]F={A→B，B→A，B→C，A→C，C→A}Fm1、Fm2都是F的最小依賴集：

Fm1={A→B，B→C，C→A}

Fm2={A→B，B→A，A→C，C→A}F的最小依賴集Fm不一定是唯一的它與對(duì)各函數(shù)依賴FDi

及X→A中X各屬性的處置順序有關(guān)2023/2/1107極小化過程極小化過程(定理6.3的證明)也是檢驗(yàn)F是否為極小依賴集的一個(gè)算法若改造后的F與原來的F相同，說明F本身就是一個(gè)最小依賴集2023/2/1108極小化過程在R<U，F(xiàn)>中可以用與F等價(jià)的依賴集G來取代F原因：兩個(gè)關(guān)系模式R1<U，F(xiàn)>，R2<U，G>，如果F與G等價(jià)，那么R1的關(guān)系一定是R2的關(guān)系。反過來，R2的關(guān)系也一定是R1的關(guān)系。

2023/2/1109設(shè)有R(A,B,C,D),F={A->C,C->A,B->AC,D->AC}1.計(jì)算（AD）+2.求F的最小等價(jià)依賴集Fm（AD）+=ADCFm={A->C,C->A,B->C,D->C}2023/2/1110第六章關(guān)系數(shù)據(jù)理論6.1數(shù)據(jù)依賴6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)6.4模式的分解2023/2/11116.4模式的分解把低一級(jí)的關(guān)系模式分解為若干個(gè)高一級(jí)的關(guān)系模式的方法并不是唯一的只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義2023/2/1112關(guān)系模式分解的標(biāo)準(zhǔn)三種模式分解的等價(jià)定義⒈分解具有無損連接性⒉分解要保持函數(shù)依賴⒊分解既要保持函數(shù)依賴，又要具有無損連接性2023/2/1113模式的分解（續(xù)）定義6.16關(guān)系模式R<U,F>的一個(gè)分解：ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}U=U1∪U2∪…∪Un，且不存在Ui

Uj，F(xiàn)i

為F在Ui

上的投影定義6.17

函數(shù)依賴集合{X→Y|X→Y

F+∧XY

Ui}的一個(gè)覆蓋

Fi

叫作F在屬性Ui

上的投影2023/2/1114模式的分解（續(xù)）例:SL（Sno，Sdept，Sloc）

F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}SL∈2NF存在插入異常、刪除異常、冗余度大和修改復(fù)雜等問題分解方法可以有多種2023/2/1115模式的分解（續(xù)）SL──────────────────

Sno

Sdept

Sloc

──────────────────95001CSA95002ISB95003MAC95004ISB95005 PH B──────────────────2023/2/1116模式的分解（續(xù)）1.SL分解為下面三個(gè)關(guān)系模式：

SN(Sno)

SD(Sdept)

SO(Sloc)2023/2/1117分解后的關(guān)系為：

SN──────SD──────SO──────

Sno

Sdept

Sloc

──────────────────95001CSA95002ISB95003MAC95004PH─────95005────────────2023/2/1118模式的分解（續(xù)）

分解后的數(shù)據(jù)庫丟失了許多信息例如無法查詢95001學(xué)生所在系或所在宿舍。如果分解后的關(guān)系可以通過自然連接恢復(fù)為原來的關(guān)系，那么這種分解就沒有丟失信息2023/2/1119模式的分解（續(xù)）2.SL分解為下面二個(gè)關(guān)系模式：

NL(Sno,Sloc)

DL(Sdept,Sloc)分解后的關(guān)系為：

NL────────────DL────────────

Sno

Sloc

Sdept

Sloc

────────────────────────95001A CSA95002B ISB95003CMAC95004B PHB95005B──────────────────────2023/2/1120模式的分解（續(xù)）NLDL─────────────

Sno

Sloc

Sdept

─────────────95001ACS95002BIS95002BPH95003CMA95004BIS95004BPH95005BIS95005BPH2023/2/1121模式的分解（續(xù)） NLDL比原來的SL關(guān)系多了3個(gè)元組

無法知道95002、95004、95005

究竟是哪個(gè)系的學(xué)生

元組增加了，信息丟失了2023/2/1122第三種分解方法3.將SL分解為下面二個(gè)關(guān)系模式：

ND(Sno,Sdept)

NL(Sno,Sloc)

分解后的關(guān)系為：

2023/2/1123模式的分解（續(xù)）ND────────────NL──────────

Sno

Sdept

Sno

Sloc

──────────────────────95001CS95001A95002IS95002B95003MA95003C95004IS95004B95005PH95005B

───────────────────────2023/2/1124模式的分解（續(xù)）NDNL──────────────

Sno

Sdept

Sloc──────────────

95001CSA95002ISB95003MAC95004CSA95005PHB──────────────與SL關(guān)系一樣，因此沒有丟失信息2023/2/1125具有無損連接性的模式分解關(guān)系模式R<U,F>的一個(gè)分解ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}若R與R1、R2、…、Rn自然連接的結(jié)果相等，則稱關(guān)系模式R的這個(gè)分解ρ具有無損連接性（Losslessjoin）具有無損連接性的分解保證不丟失信息無損連接性不一定能解決插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題2023/2/1126模式的分解（續(xù)）

第三種分解方法具有無損連接性

問題:

這種分解方法沒有保持原關(guān)系中的函數(shù)依賴

SL中的函數(shù)依賴Sdept→Sloc

沒有投影到關(guān)系模式ND、NL上

2023/2/1127保持函數(shù)依賴的模式分解設(shè)關(guān)系模式R<U,F>被分解為若干個(gè)關(guān)系模式R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>（其中U=U1∪U2∪…∪Un，且不存在Ui

Uj，F(xiàn)i為F在Ui上的投影），若F所邏輯蘊(yùn)含的函數(shù)依賴一定也由分解得到的某個(gè)關(guān)系模式中的函數(shù)依賴Fi所邏輯蘊(yùn)含，則稱關(guān)系模式R的這個(gè)分解是保持函數(shù)依賴的（Preservedependency）。2023/2/1128第四種分解方法

將SL分解為下面二個(gè)關(guān)系模式：

ND(Sno,Sdept)

DL(Sdept,Sloc)

這種分解方法就保持了函數(shù)依賴。2023/2/1129模式的分解（續(xù)）如果一個(gè)分解具有無損連接性，則它能夠保證不丟失信息。如果一個(gè)分解保持了函數(shù)依賴，則它可以減輕或解決各種異常情況。分解具有無損連接性和分解保持函數(shù)依賴是兩個(gè)互相獨(dú)立的標(biāo)準(zhǔn)。具有無損連接性的分解不一定能夠保持函數(shù)依賴。同樣，保持函數(shù)依賴的分解也不一定具有無損連接性。2023/2/1130模式的分解（續(xù)）第一種分解方法既不具有無損連接性，也未保持函數(shù)依賴，它不是原關(guān)系模式的一個(gè)等價(jià)分解第二種分解方法保持了函數(shù)依賴，但不具有無損連接性第三種分解方法具有無損連接性，但未持函數(shù)依賴第四種分解方法既具有無損連接性，又保持了函數(shù)依賴2023/2/1131分解算法算法6.2判別一個(gè)分解的無損連接性算法6.3（合成法）轉(zhuǎn)換為3NF的保持函數(shù)依賴的分解。算法6.4轉(zhuǎn)換為3NF既有無損連接性又保持函數(shù)依賴的分解算法6.5轉(zhuǎn)換為BCNF的無損連接分解（分解法）算法6.6達(dá)到4NF的具有無損連接性的分解2023/2/1132算法6.2判別一個(gè)分解的無損連接性建立一個(gè)n列k行的表。填入ai，或bij。對(duì)每個(gè)函數(shù)依賴做下列操作：找到Xi所對(duì)應(yīng)的列中具有相同符號(hào)那些行，若其中有ai

，則全部改成ai

；否則全部行號(hào)最小的bij

。若某個(gè)bij被更改，那么該表中其它相同bij均做相同的更改。比較掃描后有無變化，無變化則終止。若表中有全a行，則分解具有無損連接性。2023/2/1133例：R(A,B,C)F={A->B,C->B}ρ1=(AB,BC)ρ1分解不具有無損連接性ρ2=(AC,BC)ρ2分解具有無損連接性ρ3=(AC,AB)ρ3分解具有無損連接性2023/2/1134例：R<U,F>,U={A,B,C,D,E},F={AB->C,C->D,D->E}ρ={R1(ABC),R2(CD),R3(DE)}具有無損連接性2023/2/1135判別一個(gè)分解的函數(shù)依賴保持性輸入：關(guān)系模式R上的函數(shù)依賴集F，

R的一個(gè)分解：ρ={R1，R2···Rk}輸出：確定ρ是否具有依賴保持性方法：1.計(jì)算F到每一個(gè)Ri上的投影（i=1…k）2.FOR每一個(gè)X-〉Y∈FDOZ1=X；Z0=Φ；

DOWHILEZ1≠Z0Z0=Z1；

FORi=1TOkDOZ1=Z1∪((Z1∩Ri)+

∩Ri)ENDFORENDDO

IFY-Z1=Φ

RETU