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

1、第第3 3章章 關(guān)系數(shù)據(jù)模型關(guān)系數(shù)據(jù)模型關(guān)系模型的基礎(chǔ)關(guān)系模型的基礎(chǔ) 關(guān)系模型的核心概念 - 關(guān)系，使用關(guān)系表示實體集及實體集之間的聯(lián)系。屬性屬性 模式模式 關(guān)系名和其屬性集合的組合稱為這個關(guān)系的模式。 movies(title, year, length, filmtype) 數(shù)據(jù)庫模式（關(guān)系數(shù)據(jù)庫模式）數(shù)據(jù)庫模式（關(guān)系數(shù)據(jù)庫模式） - 一個數(shù)據(jù)庫所有關(guān)系的模式集合元組元組 (star wars, 1977, 124, color)域域 - 每個屬性的取值范圍 - 必須滿足原子性關(guān)系的等價描述關(guān)系的等價描述 - 行序無關(guān)、列序無關(guān)關(guān)系實例關(guān)系實例 - 元組的集合（是動態(tài)變化的，但是模式是相對

2、穩(wěn)定的）通常的數(shù)據(jù)庫系統(tǒng)只維護關(guān)系的一個版本，即關(guān)系的“當前”元組集合。這個關(guān)系實例叫做當前實例當前實例。從從e/re/r圖到關(guān)系設(shè)計圖到關(guān)系設(shè)計 先用e/r圖設(shè)計，然后轉(zhuǎn)換成關(guān)系模式。對于一般對于一般e/re/r圖的轉(zhuǎn)換步驟：圖的轉(zhuǎn)換步驟：（1）把每個實體集轉(zhuǎn)化成具有同一屬性集合的關(guān)系；（2）用關(guān)系替換聯(lián)系，關(guān)系的屬性就是聯(lián)系所連接的實體集的鍵集合 - 多角色情況也是一樣多角色情況也是一樣。還有些特殊情況要特殊處理還有些特殊情況要特殊處理stars(name, address)studios(name, address)movies(title, year, length, filmtype

3、)stars-in(title, year, starsname)owns(title, year, studiosname)contracts(starname, title, year, studioofstar, producingstudio)多路聯(lián)系的例子多路聯(lián)系的例子組合關(guān)系組合關(guān)系movies(title, year, length, filmtype)owns(title, year, studiosname)上述兩個關(guān)系最好組合成如下的一個關(guān)系（因為它們之間存在多對一的關(guān)系）：r(title, year, length, filmtype, studioname)studio

4、name 允許空值允許空值這樣做可以帶來好處這樣做可以帶來好處如果不是多對一聯(lián)系，則合成關(guān)系會出現(xiàn)問題如果不是多對一聯(lián)系，則合成關(guān)系會出現(xiàn)問題(造成數(shù)據(jù)冗余造成數(shù)據(jù)冗余) - p41例3.6多對多的聯(lián)系合并會造成冗余多對一的聯(lián)系可以合并處理弱實體集處理弱實體集1. 從弱實體集w得到的關(guān)系不僅要包含w的屬性，還包含有助于形成w鍵的其他實體集的鍵屬性。 - 通過支持聯(lián)系訪問其他實體集。2. 與弱實體集w相連的聯(lián)系，經(jīng)轉(zhuǎn)化后所得的關(guān)系必須把那些和w相連的，以及對w的鍵有用的，實體集的鍵屬性作為w的鍵 普通聯(lián)系3. 從弱實體集w指向其他有有助于形成w的鍵的實體集的支持聯(lián)系r不必轉(zhuǎn)化為關(guān)系。 - 支持聯(lián)

5、系處理弱實體集處理弱實體集studios(name, addr)crews(number, studioname)unit-of(number, studioname, name) 可以去掉可以去掉p42例3.8contracts(starname, studioname, title, year, salary)stars(name, addr)studio(name, addr)movies(title, year, filmtype, length)支持聯(lián)系不需要轉(zhuǎn)化為關(guān)系支持聯(lián)系不需要轉(zhuǎn)化為關(guān)系p44弱實體集轉(zhuǎn)化為關(guān)系的規(guī)則弱實體集轉(zhuǎn)化為關(guān)系的規(guī)則如果w是一個弱實體集，則w轉(zhuǎn)化為關(guān)系后

6、的模式由以下項目組成：（1）w的所有屬性；（2）與w相連的支持聯(lián)系的所有屬性（3）對每一個連接w的支持聯(lián)系，要包含e的所有鍵屬性（e就是與w保持支持聯(lián)系的其他實體集）（4）不要為與w相連的支持聯(lián)系構(gòu)造關(guān)系子類結(jié)構(gòu)到關(guān)系的轉(zhuǎn)化子類結(jié)構(gòu)到關(guān)系的轉(zhuǎn)化直接直接e/re/r 為任一個在層次中的實體集創(chuàng)建一個關(guān)系，它包含根的鍵屬性和實體集自身的屬性。 isa聯(lián)系不需要建立關(guān)系。movies(title, year, length, filmtype)cartoons(title, year)murdermysteries(title, year, weapon)voices(title, year, st

7、arname) - 假設(shè)stars的鍵為starname面向?qū)ο蟮姆椒嫦驅(qū)ο蟮姆椒?為每個包含根的子樹創(chuàng)建一個關(guān)系，這個關(guān)系模式包含子樹中所有實體集的所有屬性。子樹子樹1 1：movies子樹子樹2 2：movies，cartoons子樹子樹3 3：movies，murder-mysteries子樹子樹4 4：movies， cartoons， murder-mysteriesmovies(title, year, length, filmtype)moviesc(title, year, length, filmtype)moviesmm(title, year, length, film

8、type, weapon)moviescmm(title, year, length, filmtype, weapon)voices(title, year, starname)含有相同屬性的關(guān)系可以合并含有相同屬性的關(guān)系可以合并 - 但是會丟失一些信息但是會丟失一些信息使用空值使用空值 創(chuàng)建一個包含層次中所有實體集屬性的關(guān)系。每個實體由一個元組表示，對于實體不具有的屬性，則設(shè)該元組的相應(yīng)分量為空。movies(title, year, filmtype, weapon)各種方法的比較各種方法的比較查詢效率方面關(guān)系數(shù)量方面：2n(面向?qū)ο?信息冗余方面：面向?qū)ο蟆⒖罩?、直接e/r(重復(fù)鍵值)

9、函數(shù)依賴函數(shù)依賴 - - 研究屬性之間的依賴關(guān)系研究屬性之間的依賴關(guān)系設(shè)計不好的關(guān)系例設(shè)計不好的關(guān)系例-1-1冗余、更新、插入、刪除等異常情況冗余、更新、插入、刪除等異常情況設(shè)計不好的關(guān)系例設(shè)計不好的關(guān)系例-2-2函數(shù)依賴的定義函數(shù)依賴的定義 一個關(guān)系r上的函數(shù)依賴(functional dependency, fd)，是指“如果r的兩個元組在屬性a1, a2, , an上一致，那么它們在其他分量b上的值必定也相同。寫為：a1a2anb” a1a2anb1a1a2anb2.a1a2anbm記成：a1a2anb1b2bmmovies(title, year, length, filmtype,

10、studioname, starname)title year lengthtitle year filmtypetitle year studionametitle year starname 可以寫成：title year length filmtype studioname說明： 1. 函數(shù)依賴不是指關(guān)系模式r的某個或某些關(guān)系實例滿足的約束條件，而是指r的所有關(guān)系實例均要滿足的約束條件。2. 函數(shù)依賴是語義范疇的概念。只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴。 例如“姓名年齡”這個函數(shù)依賴只有在不允許有同名人的條件下成立3. 數(shù)據(jù)庫設(shè)計者可以對現(xiàn)實世界作強制的規(guī)定。例如規(guī)定不允許同名人出現(xiàn)，函數(shù)

11、依賴“姓名年齡”成立。所插入的元組必須滿足規(guī)定的函數(shù)依賴，若發(fā)現(xiàn)有同名人存在， 則拒絕裝入該元組。關(guān)系的鍵關(guān)系的鍵 如果下列條件滿足，就認為一個或多個屬性的集合a1, a2, , an是關(guān)系r的鍵：（1）這些屬性決定關(guān)系的所有其他屬性；（2）沒有一個a1, a2, , an的真子集能函數(shù)決定r的其他屬性。例：例：movies(title, year, length, filmtype, studioname, starname)鍵為:title, year, starname可能一個關(guān)系模式有多個鍵，需要指定一個為主鍵。可能一個關(guān)系模式有多個鍵，需要指定一個為主鍵。當顯示關(guān)系模式的時候，在主鍵

12、屬性下劃線。當顯示關(guān)系模式的時候，在主鍵屬性下劃線。超鍵超鍵 一個包含鍵的屬性集就叫做超鍵（鍵本身是特殊的超鍵）。movies(title, year, length, filmtype, studioname, starname)title, year, starname為超鍵。.找出關(guān)系中的鍵找出關(guān)系中的鍵（1）來自e/r圖實體集的關(guān)系，實體集的鍵就是關(guān)系的鍵；（2）對于來自e/r圖聯(lián)系的關(guān)系，則多對多聯(lián)系：聯(lián)系的實體集的鍵的集合多對一的聯(lián)系(e1到e2)：e1的鍵一對一的聯(lián)系(e1到e2)：e1或者e2的鍵movies(title, year, length, filmtype)star

13、s(name, address)上面為實體集得到的關(guān)系owns(title, year, studioname) 電影與公司之間的多對一的聯(lián)系stars-in(title, year, starname) 影星與電影之間的多對多的聯(lián)系鍵為：學號、課程號函數(shù)依賴的規(guī)則函數(shù)依賴的規(guī)則 如何從已知的函數(shù)依賴導(dǎo)出其他必定成立的函數(shù)依賴？如何從已知的函數(shù)依賴導(dǎo)出其他必定成立的函數(shù)依賴？例例3.173.17 如果一個含有屬性a、b、c的關(guān)系r滿足fd：ab和b c，顯然可以導(dǎo)出fd：a c。定義定義1 1 一個關(guān)系模式的兩個函數(shù)依賴集等價定義定義2 2 一個關(guān)系模式的兩個函數(shù)依賴集之間的導(dǎo)出(推斷)關(guān)系存

14、在下列等價規(guī)則：存在下列等價規(guī)則：（1）分解分解/ /結(jié)合規(guī)則結(jié)合規(guī)則 分解：分解： a1a2anb1b2bm 可以分解為： a1a2anb1 a1a2anb2 a1a2anbm結(jié)合：結(jié)合： a1a2anb1 a1a2anb2 a1a2anbm 可以結(jié)合成： a1a2anb1b2bm title year lengthtitle year filmtypetitle year studioname可以結(jié)合成：可以結(jié)合成：title year length filmtype studioname（2 2）平凡函數(shù)依賴）平凡函數(shù)依賴 平凡函數(shù)依賴平凡函數(shù)依賴 非平凡函數(shù)依賴非平凡函數(shù)依賴 完全非平

15、凡函數(shù)依賴完全非平凡函數(shù)依賴 title yearlength (完全非平凡函數(shù)依賴) title year title length (非平凡函數(shù)依賴) title year year length (非平凡函數(shù)依賴) title year title year length (非平凡函數(shù)依賴) title year title (平凡函數(shù)依賴) title year year (平凡函數(shù)依賴) title year title year (平凡函數(shù)依賴) 計算屬性的閉包計算屬性的閉包 1. 屬性集合的閉包 a1, a2, , an+ 2. 計算屬性集合a1, a2, , an閉包的步驟 ：

16、（1）x初始化為a1, a2, , an;（2）在fd集合中查找b1b2.bn c這樣的式子，其中b1，b2 ，. ， bn在x中，而c不在x中，如果找到，則將c加入到x中；（3）重復(fù)第（2）步，直到x不再增大為止。例例3.193.19 考慮含有屬性a，b，c，d，e和f的關(guān)系。假設(shè)此關(guān)系有fd：abc，bc ad，d e和cf b。求a, b+。例例3.203.20 考慮含有屬性a，b，c，d，e和f的關(guān)系。假設(shè)此關(guān)系有fd：abc，bc ad，d e和cf b。ab d是否能導(dǎo)出來？d a是否能推導(dǎo)出來？例例 f = ab c, d eg, c a, be c, bc d, cg bd,

17、acd b, ce ag, 求(bd)+。為什么能用閉包算法？能正確判斷一個fd是否能從給定的fd集合s推斷出來。證明過程（略，一般了解）（3 3）傳遞規(guī)則）傳遞規(guī)則若關(guān)系r中fd a1a2anb1b2bm和b1b2bmc1c2ck都成立，那么a1a2an c1c2ck在r中也成立。例3.21 r(title, year, length, filmtype, studioname, studioaddr)title year studioname (根據(jù)多對一聯(lián)系得到的)studioname studioaddr 所以 title year studioaddr函數(shù)依賴的閉包集合函數(shù)依賴的閉包

18、集合使用哪個fd集合來描述一個關(guān)系的完全fd集合？使用一個fd集合就可以把其他fd集合推出來 - 基本集最小化的基本集例例3.223.22 p57a bc, b ac, c ab能導(dǎo)出的所有函數(shù)依賴關(guān)系最小的函數(shù)依賴集：a b, b a, b c, c ba b, b c, c a最小依賴集 如果函數(shù)依賴集f滿足下列條件，則稱f為一個極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。 (1) f中任一函數(shù)依賴的右部僅含有一個屬性。 (2) f中不存在這樣的函數(shù)依賴xa，使得f與f-xa等價。 (3) f中不存在這樣的函數(shù)依賴xa， x有真 子集z使得f-xaza與f等價。 關(guān)系模式s，其中： u=

19、sno，sdept，mn，cname，g ， f= snosdept，sdeptmn， （sno，cname）g 設(shè)f=snosdept，snomn， sdeptmn，(sno，cname)g， (sno，sdept)sdeptf是最小覆蓋，而f 不是。因為：f -snomn與f 等價 f -(sno，sdept)sdept也與f 等價 f -(sno，sdept)sdept snosdept也與f 等價每一個函數(shù)依賴集f均等價于一個極小函數(shù)依賴集fm。此fm稱為f的最小依賴集證:構(gòu)造性證明，依據(jù)定義分三步對f進行“極小化處理”，找出f的一個最小依賴集。(1)逐一檢查f中各函數(shù)依賴fdi：xy

20、， 若y=a1a2 ak，k 2， 則用 xaj |j=1，2， k 來取代xy。 (2)逐一檢查f中各函數(shù)依賴fdi：xa， 令g=f-xa， 若axg+， 則從f中去掉此函數(shù)依賴。 (3)逐一取出f中各函數(shù)依賴fdi：xa， 設(shè)x=b1b2bm， 逐一考查bi （i=l，2，m）， 若a （x-bi ）f+ ， 則以x-bi 取代x。 f = ab，ba，bc， ac，ca fm1、fm2都是f的最小依賴集： fm1= ab，bc，ca fm2= ab，ba，ac，ca f的最小依賴集fm不一定是唯一的它與對各函數(shù)依賴fdi 及xa中x各屬性的處置順序有關(guān)投影函數(shù)依賴投影函數(shù)依賴關(guān)系的分解

21、關(guān)系的分解 - - 消除異常消除異常 - - 投影運投影運算算投影成： movies1(title, year, length, filmtype, studioname) 和 movies(title, year, starname)例例3.233.23 p58關(guān)系分解后的函數(shù)依賴關(guān)系分解后的函數(shù)依賴關(guān)系r上的函數(shù)依賴集合f，分解（投影成r1和r2)，找r1和r2上成立的函數(shù)依賴集合。（1）從f推導(dǎo)出來；（2）函數(shù)依賴的左右兩側(cè)只是r1（或者r2）的屬性。考慮所有r1（或者r2）屬性集的所有子集的閉包?？梢圆捎脙?yōu)化計算方法（見下面的例子）r(a, b, c, d)，fd: a b, b c,

22、 c d分解成s(a, c, d)，s上成立的fd的計算a+ 包含所有屬性，不用再算其超集的閉包c+d+c, d+模式的分解 把低一級的關(guān)系模式分解為若干個高一級的關(guān)系模式的方法并不是唯一的 只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價，分解方法才有意義關(guān)系模式分解的標準三種模式分解的等價定義 分解具有無損連接性 分解要保持函數(shù)依賴 分解既要保持函數(shù)依賴，又要具有無損連接性例: sl（sno， sdept， sloc） f= snosdept,sdeptsloc,snosloc 存在插入異常、刪除異常、冗余度大和修改復(fù)雜等問題分解方法可以有多種 sl sno sdeptsloc 95001 c

23、s a 95002 is b 95003 ma c 95004 is b 95005 ph b 1. sl分解為下面三個關(guān)系模式： sn(sno) sd(sdept) so(sloc) sn sd so sno sdept sloc 95001 cs a 95002 is b 95003 ma c 95004 ph 95005 分解后的數(shù)據(jù)庫丟失了許多信息 例如無法查詢95001學生所在系或所在宿舍。 如果分解后的關(guān)系可以通過自然連接恢復(fù)為原來的關(guān)系，那么這種分解就沒有丟失信息2. sl分解為下面二個關(guān)系模式： nl(sno, sloc) dl(sdept, sloc)分解后的關(guān)系為： nl

24、dl sno sloc sdept sloc 95001 a cs a 95002 b is b 95003 c ma c 95004 b ph b 95005 b nl dl sno sloc sdept 95001 a cs 95002 b is 95002 b ph 95003 c ma 95004 b is 95004 b ph 95005 b is 95005 b ph nl dl比原來的sl關(guān)系多了3個元組 無法知道95002、95004、95005 究竟是哪個系的學生 元組增加了，信息丟失了3. 將sl分解為下面二個關(guān)系模式： nd(sno, sdept) nl(sno, slo

25、c) 分解后的關(guān)系為： nd nl sno sdept sno sloc 95001 cs 95001 a 95002 is 95002 b 95003 ma 95003 c 95004 is 95004 b 95005 ph 95005 b nd nl sno sdept sloc 95001 cs a 95002 is b 95003 ma c 95004 cs a 95005 ph b 與sl關(guān)系一樣，因此沒有丟失信息 關(guān)系模式r的一個分解 = r1，r2， ，rn若r與r1、r2、rn自然連接的結(jié)果相等，則稱關(guān)系模式r的這個分解具有無損連接性（lossless join） 具有無損連接

26、性的分解保證不丟失信息 無損連接性不一定能解決插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題 第三種分解方法具有無損連接性 問題: 這種分解方法沒有保持原關(guān)系中的函數(shù)依賴 sl中的函數(shù)依賴sdeptsloc 沒有投影到關(guān)系模式nd、nl上 設(shè)關(guān)系模式r被分解為若干個關(guān)系模式r1，r2，rn （其中u=u1u2un，且不存在ui uj，fi為f在ui上的投影），若f所邏輯蘊含的函數(shù)依賴一定也由分解得到的某個關(guān)系模式中的函數(shù)依賴fi所邏輯蘊含，則稱關(guān)系模式r的這個分解是保持函數(shù)依賴的（preserve dependency）。 將sl分解為下面二個關(guān)系模式： nd(sno, sdept) dl(sd

27、ept, sloc) 這種分解方法就保持了函數(shù)依賴。 如果一個分解具有無損連接性，則它能夠保證不丟失信息。 如果一個分解保持了函數(shù)依賴，則它可以減輕或解決各種異常情況。 分解具有無損連接性和分解保持函數(shù)依賴是兩個互相獨立的標準。具有無損連接性的分解不一定能夠保持函數(shù)依賴。同樣，保持函數(shù)依賴的分解也不一定具有無損連接性。第一種分解方法既不具有無損連接性，也未保持函 數(shù)依賴，它不是原關(guān)系模式的一個等價分解第二種分解方法保持了函數(shù)依賴，但不具有無損連 接性第三種分解方法具有無損連接性，但未持函數(shù)依賴第四種分解方法既具有無損連接性，又保持了函數(shù) 依賴關(guān)系數(shù)據(jù)庫模式設(shè)計關(guān)系數(shù)據(jù)庫模式設(shè)計分解關(guān)系分解關(guān)系

28、bcnf范式范式 - 按照什么原則來分解關(guān)系，消除異常？（1）bcnf范式的定義 關(guān)系r滿足bcnf當且僅當：如果r中非平凡fd a1a2anb成立，則a1a2an是關(guān)系的超鍵。（2）判斷是否為bcnf范式的例子（3.25、3.26、3.27）例3.25 r(title, year, length, filmtype, studioname, starname)fd = title yearlength, title yearfilmtype, title yearstudioname，key = title year starname例3.26 movies1(title, year, le

29、ngth, filmtype, studioname) 和 movies(title, year, starname)這兩個關(guān)系模式都是滿足bcnf范式的，因為:對于movies1：title year length, title year filmtype, title year studioname key = title year對于movies2：key = title year starname例3.27 任意的二元關(guān)系都滿足bcnf范式（3）如何將一個不滿bcnf范式的關(guān)系模式分解成若干個滿足bcnf范式的關(guān)系模式？方法：方法：首先尋找違反bcnf條件的非平凡a1a2an b1b2

30、bm，也就是要找a1, a2, an不是超鍵的fd。然后盡可能地往fd的右邊增加足夠多的由a1, a2, an決定的屬性，分解成兩個關(guān)系：其中一個包含了上述fd的所有屬性，另一個包含了位于這個fd左邊的屬性和不屬于這個fd的所有屬性。例3.28 r(title, year, length, filmtype, studioname, starname)fd = title yearlength, title yearfilmtype, title yearstudioname，key = title year starnametitle year length是違反bcnf的非平凡函數(shù)依賴ti

31、tle year length filmtype studioname r1(title, year, length, filmtype, studioname) r2(title, year, starname) 每個都滿足bcnf范式例3.29 r(title, year, filmtype, studioname, studioaddr)fd = title yearlength, title yearfilmtype, title yearstudioname, studionamestudioaddr鍵為 title, year因此，上述關(guān)系模式不滿足bcnf范式。違反bcnf范式的函數(shù)依賴為studionamestudioaddr，因此分解為如下兩個關(guān)系模式：r1(studioname, studioaddr)r2(title, year, length, filmtype, studioname)例3.30 r(title,