第10章 數(shù)據(jù)依靠和關系模式規(guī)范化

本文格式為Word版，下載可任意編輯——第10章數(shù)據(jù)依靠和關系模式規(guī)范化

數(shù)據(jù)依靠和關系模式規(guī)范化

第10章數(shù)據(jù)依靠和關系模式規(guī)范化10.110.210.310.410.510.6關系模式設計中的數(shù)據(jù)語義問題函數(shù)依靠(FD)多值依靠(MVD)聯(lián)接依靠(JD)*關系模式的分解及其問題關系模式的規(guī)范化

數(shù)據(jù)依靠和關系模式規(guī)范化

10.1關系模式設計中的數(shù)據(jù)語義問題前面我們已經探討了關系數(shù)據(jù)庫的基本概念、關系模型的三個部分以及關系數(shù)據(jù)庫的標準語言SQL。但是還有一個很基本的問題尚未涉及，針對一個具體問題，應當如何構造一個適合于它的數(shù)據(jù)庫模式，即應當構造幾個關系模式，每個關系由哪些屬性組成等。這是數(shù)據(jù)庫設計的問題，確鑿地講是關系數(shù)據(jù)庫規(guī)律設計問題。

數(shù)據(jù)依靠和關系模式規(guī)范化

10.1關系模式設計中的數(shù)據(jù)語義問題下面首先回想一下關系模型的形式化定義。一個關系模式應當是一個五元組。R(U,D,DOM,F)這里：–––––關系名R,它是符號化的元組語義；一組屬性U;屬性組U中屬性所來自的域D;屬性到域的映射DOM;屬性組U上的一組數(shù)據(jù)依靠F

由于D和DOM對模式設計關系不大,因此我們在本章中把關系模式看作是一個三元組：RU,F當且僅當U上的一個關系r滿足F時，稱r為關系模式RU,F的一個關系。

數(shù)據(jù)依靠和關系模式規(guī)范化

10.1關系模式設計中的數(shù)據(jù)語義問題關系作為一張二維表,我們對它有一個最起鍵的要求：每一個分量必需是不可分的數(shù)據(jù)項。滿足了這個條件的關系模式就屬于第一范式(1NF)。我們的任務是研究模式設計，研究設計一個“好〞的(沒有“毛病〞的)關系模式的方法。數(shù)據(jù)依靠是通過一個關系中屬性間值的相等與否表達出來的數(shù)據(jù)間的相互關系。它是現(xiàn)實世界屬性間相互聯(lián)系的抽象，是數(shù)據(jù)內在的性質，是語義的表達?，F(xiàn)在人們已經提出了大量種類型的數(shù)據(jù)依靠，其中最重要的是函數(shù)依靠(FunctionalDependency簡記為FD)和多值依靠(MultivaluedDependency簡記為MVD)。函數(shù)依靠極為普遍地存在于現(xiàn)實生活中。

數(shù)據(jù)依靠和關系模式規(guī)范化

10.1關系模式設計中的數(shù)據(jù)語義問題譬如描述一個學生的關系,可以有學號(SNO),姓名(SNAME),系名(SDEPT)等幾個屬性。由于一個學號只對應一個學生,一個學生只在一個系學習。因而當“學號〞值確定之后,姓名和該生所在系的值也就被唯一地確定了。就象自變量x確定之后,相應的函數(shù)值f(x)也就唯一地確定了一樣，我們說SNO函數(shù)決定SNAME和SDEPT,或者說SNAME,SDEPT函數(shù)依靠于SNO,記為∶SNO→SNAME,SNO→SDEPT。

數(shù)據(jù)依靠和關系模式規(guī)范化

10.1關系模式設計中的數(shù)據(jù)語義問題現(xiàn)在我們要建立一個數(shù)據(jù)庫來描述學生的一些倩況。面臨的對象有：學生(用學號SNO描述),系(用系名SDEPT描述),系負責人(用其姓名MN描述),課程(用課程名CNAME描述)和成績(G)?，F(xiàn)實世界的已知事實

告訴我們∶1)2)3)4)一個系有若干學生,但一個學生只屬于一個系；一個系只有一名(正職)負責人；一個學生可以選修多門課程,每門課程有若干學生選修；每個學生學習每一門課程有一個成績；

假使只考慮函數(shù)依靠這一種數(shù)據(jù)依靠,我們就得到了一個描述學校的數(shù)據(jù)庫模式SU,F,它由一個單一的關系模式構成：U={SNO,SDEPT,MN,CNAME,G}F={SNO→SDEPT,SDEPT→MN,(SNO,CNAME)→G}

數(shù)據(jù)依靠和關系模式規(guī)范化

10.1關系模式設計中的數(shù)據(jù)語義問題這個模式有下述三個“毛病〞:1)插入異常：假使一個系剛成立尚無學生,或者雖然有了學生但尚未安排課程。那么我們就無法把這個系及其負責人的信息存入數(shù)據(jù)庫。刪除異常：反過來,假使某個系的學生全部畢業(yè)了,我們在刪除該系學生選修課程的同時,把這個系及其負責人的信息也丟掉了。更新異常：譬如，某系負責人更換后,就必需逐一修改有關的每一個元組。數(shù)據(jù)冗余：譬如,每一個系負責人的姓名要與該系每一個學生的每一門功課的成績出現(xiàn)的次數(shù)一樣多。

2)

3)

4)

這樣,一方面浪費存儲,另一方面系統(tǒng)耍付出很大的代價來維護數(shù)據(jù)庫的完整性。

數(shù)據(jù)依靠和關系模式規(guī)范化

10.1關系模式設計中的數(shù)據(jù)語義問題為什么會發(fā)生插入異常和刪除異常呢?這是由于這個模式中的函數(shù)依靠存在某些不好的性質。假使我們把這個單一的模式改造一下,分成三個關系模式：SSNO,SDEPT,SNO→SDEPT;SGSNO,CNAME,G,(SNO,CNAME)→G;DEPTSDEPT,MN,SDEPT→MN;這三個模式都不會發(fā)生插入異常、刪除異常的毛病,數(shù)據(jù)的冗佘也得到了控制。一個模式的函數(shù)依靠會有哪些不好的性質,如何改造一個不好的模式,這就是本章要探討的主要內容。

數(shù)據(jù)依靠和關系模式規(guī)范化

10.2函數(shù)依靠定義10.1:設R(U)是屬性集U上的關系模式。X,Y是U的子集。若對于R(U)的任意一個可能的關系r,r中不可能存在兩個元組在X上的屬性值相等，而在Y上的屬性值不等，則稱X函數(shù)確定Y或Y函數(shù)依靠于X,記作X→Y。下面介紹一些術語和記號：–––––X→Y,但YX,則稱X→Y為平凡的函數(shù)依靠。否則，稱X→Y為非平凡的函數(shù)依靠。今后，若不特別聲明，我們總是探討非平凡的函數(shù)依靠。若X→Y,則稱X為決定因素(Determinant)。若X→Y,Y→X,則記作X←→Y。若Y不函數(shù)依靠于X,則記作XY。

數(shù)據(jù)依靠和關系模式規(guī)范化

10.2函數(shù)依靠定義10.2:在R(U)中,假使X→Y,并且對于X的任何一個真子集X',都有X'Y,則稱Y對X完全函數(shù)依靠,記作:XY。若X→Y,但Y不完全函數(shù)依靠于X,則稱Y對X部分函數(shù)依靠,記作XY。定義10.3:在R(U)中,假使X→Y,(YX),YX,Y→Z,則稱Z對X傳遞函數(shù)依靠。加上條件YX,是由于假使Y→X,則X←→Y,實

際上是,是直接函數(shù)依靠而不是傳遞函數(shù)依靠。定義10.4:對于滿足一組函數(shù)依靠F的關系模式RU,F,其任何一個關系r,若函數(shù)依靠X→Y都成立(即r中任意兩元組t,s,若t[X]=s[X],則t[Y]=s[Y]),則稱F規(guī)律蘊含X→Y,記為F|=X→Y

數(shù)據(jù)依靠和關系模式規(guī)范化

10.2函數(shù)依靠Armstrong公理系統(tǒng)為了求得給定關系模式的鍵,為了從一組函數(shù)依靠求得蘊含的函數(shù)依靠，例如，已知函數(shù)依靠集F,要問X→Y是否為F所蘊含，就需要一套推理規(guī)則，這組推理規(guī)則是l974年首先由Armstrong提出來的。設U為屬性集總體，F(xiàn)是U上的一組函數(shù)依靠,于是有關系模式RU,F。對RU,F來說有以下的推理規(guī)則：Al.自反律(Reflexivity):若YXU,則X→Y為F所蘊含。A2.增廣律(Augmentation):若X→Y為F所蘊含，且ZU,則XZ→YZ為F所蘊含。A3.傳遞律(Transitivity):若X→Y及Y→Z為F所蘊含，則X→Z為F所蘊含。注意，由自反律所得到的函數(shù)依靠均是平凡的函數(shù)依靠，自反律的使用并不依靠于F。

數(shù)據(jù)依靠和關系模式規(guī)范化

10.2函數(shù)依靠定理10.l:Armstrong推理規(guī)則是正確(sound)的。證：1)設YXU。對RU,F的任一關系r中的任意兩個元組t,s:若t[X]=s[X],由于YX,有t[y]=s[y],所以X→Y成立，自反律得證。設X→Y為F所蘊含,且ZU。設RU,F的任一關系r中任意的兩個元組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所蘊含，增廣律得證。設X→Y及Y→Z為F所蘊含。對RU,F的任一關系r中的任意兩個元組t,s。若t[X]=s[X],由于X→Y,有t[Y]=s[Y];再由Y→Z,有t[Z]=s[Z],所以X→Z為F所蘊含，傳遞律得證。

2)

3)

數(shù)據(jù)依靠和關系模式規(guī)范化

10.2函數(shù)依靠根據(jù)這三條推理規(guī)則可以得到下面三條很有用的推理規(guī)則:1)2)3)合并規(guī)則:由X→Y,X→Z,有X→YZ。偽傳遞規(guī)則：由X→Y,WY→Z,有XW→Z。分解規(guī)則：由X→Y及ZY,有X→Z。

根據(jù)合并規(guī)則和分解規(guī)則,很簡單得到這樣一個重要事實：引理10.l:X→A1A2...Ak成立的充分必要條件是X→Ai成立(i=l,2,...,k)。

數(shù)據(jù)依靠和關系模式規(guī)范化

10.2函數(shù)依靠定義10.5:在關系模式RU,F中為F所規(guī)律蘊含的函數(shù)依靠的全體叫做F的閉包,記為F+。定義10.6:給定關系模式RU,F,假使能由F根據(jù)Armstrong公理導出X→Y,則稱X→Y是F的規(guī)律導出，記為F=X→Y。人們把自反律,傳遞律和增廣律稱為Armstrong公理系統(tǒng)。Armstrong公理系統(tǒng)是有效的、完備的。Armsttrong公理的有效性指的是：由F出發(fā)根據(jù)Armstrong公理推導出來的每一個函數(shù)依靠一定在F+中；Armsttrong公理的完備性指的是F+中的每一個函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導出來。

數(shù)據(jù)依靠和關系模式規(guī)范化

10.2函數(shù)依靠要證明Armsttrong公理的完備性，就首先要解決如何判定一個函數(shù)依靠是否屬于由F根

據(jù)Armstrong公理推導出來的函數(shù)依靠的集合。當然，假使能求出這個集合，問題就解決了。但不幸的是，這是一個NP完全問題。譬如從F={X→A1...,X→An}出發(fā)，我們至少可以推導出2n個不同的函數(shù)依靠。為此引入下面概念：定義10.7:設F為屬性集U上的一組函數(shù)依靠，XU,XF+={A|X→A能由F根據(jù)Armstrong公理導出},XF+稱為屬性集X關于函數(shù)依靠集F的閉包。

數(shù)據(jù)依靠和關系模式規(guī)范化

10.2函數(shù)依靠由引理10.1簡單得出：引理10.2:設F為屬性集U上的一組函數(shù)依靠，X,YU,X→Y能由F根據(jù)Armstrong公理導出的充分必要條件是YXF+。于是,判定X→Y是否能由F根據(jù)Armstrong公理導出的問題，就轉化為求出XF+,并判定Y是否為XF+的子集的問題。這個問題由算法10.l解決了。

數(shù)據(jù)依靠和關系模式規(guī)范化

10.2函數(shù)依靠算法10.l:求屬性集X(XU)關于U上的函數(shù)依靠集F的閉包XF+。輸入：X,F輸出：XF+步驟：1)2)令X(0)=X,i=0求B,這里B={A|(存在V→W)(V→W∈F∧V∈X(i)∧A∈W)};X(i+1)=X(i)∪B判斷X(i+1)=x(i)嗎?若相等或X(i)=U則X(i)就是XF+,算法終止。若否，則i=i+l,返回第2)步。

3)4)5)6)

數(shù)據(jù)依靠和關系模式規(guī)范化

10.2函數(shù)依靠例1:已知關系模式RU,F,其中U={A,B,C,D,E};F={AB→C,B→D,C→E,EC→B,AC→B}。求(AB)F+。解：由算法5.1,X(0)=AB;計算X(1);逐一的掃描F集合中各個函數(shù)依靠,找左部為A,B,或AB的函數(shù)依靠。得到兩個：AB→C,B→D。于是X(1)=AB∪CD=ABCD。由于X(0)≠X(1),所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到C→E,AC→B,于是X(2)=X(1)∪BE=ABCDE。由于X(2)已等于全部屬性集合,所以(AB)F+=ABCDE。對于算法10.l,令ai=|X(i)|,{ai}形成一個步長大于1的嚴格遞增的序列,序列的上界是|U|,因此該算法最多|U|-|X|次循環(huán)就會終止。

數(shù)據(jù)依靠和關系模式規(guī)范化

10.2函數(shù)依靠定理10.2:Armstrong公理系統(tǒng)是有效的、完備的。Armstrong公理系統(tǒng)的有效性可由定理1