數(shù)據(jù)庫(kù)系統(tǒng)原理DatabaseSystemPrinciples課件

數(shù)據(jù)庫(kù)系統(tǒng)原理Database

System

Principles《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章四川大學(xué)計(jì)算機(jī)學(xué)院段

磊leiduan@2011.9第六章關(guān)系數(shù)據(jù)庫(kù)理論《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章意義提供分析和判斷數(shù)據(jù)庫(kù)模式好壞的準(zhǔn)則指導(dǎo)設(shè)計(jì)好的數(shù)據(jù)庫(kù)模式難易度本章是本書最難的部分之一對(duì)于應(yīng)用設(shè)計(jì)十分有用本章目錄6.1

問題的提出6.2

規(guī)范化6.3

數(shù)據(jù)依賴的公理系統(tǒng)6.4

模式的分解《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2636.1

問題的提出－－什么是不好的數(shù)據(jù)庫(kù)設(shè)計(jì)《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/264我們目前為止掌握的知識(shí)尚無(wú)法解決大量的具體設(shè)計(jì)問題，即關(guān)系模式該如何選擇。應(yīng)用數(shù)據(jù)庫(kù)應(yīng)該由多少個(gè)表組成？每個(gè)表有哪些字段？本章從理論上解決關(guān)系數(shù)據(jù)庫(kù)的邏輯設(shè)計(jì)問題。關(guān)系模式《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/265一個(gè)關(guān)系模式應(yīng)當(dāng)是一個(gè)五元組。R（U,

D,

DOM,

F）F是本章開始引入的數(shù)據(jù)依賴集。由于D和DOM對(duì)模式設(shè)計(jì)關(guān)系不大,因此我們?cè)诒菊轮邪殃P(guā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)系。關(guān)系，作為一張二維表，我們對(duì)它有一個(gè)最起碼的要求：每一個(gè)分量必須是不可分的數(shù)據(jù)項(xiàng)。滿足

了這個(gè)條件的關(guān)系模式就屬于第一范式（1NF）。數(shù)據(jù)依賴我們的任務(wù)是研究模式設(shè)計(jì)，研究設(shè)計(jì)一個(gè)“好”的（沒有“毛病”的）關(guān)系模式的辦法。數(shù)據(jù)依賴是通過一個(gè)關(guān)系中屬性間值的相等與否體現(xiàn)出來(lái)的數(shù)據(jù)間的相互關(guān)系。它是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象，是數(shù)據(jù)內(nèi)在的性質(zhì),是語(yǔ)義的體現(xiàn)。現(xiàn)在人們已經(jīng)提出了許多種類型的數(shù)據(jù)依賴，其中最重要的是函數(shù)依賴(Functional

Dependency,FD)和多值依賴(Multivalued

Dependency,MVD)?！稊?shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/266函數(shù)依賴《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/267函數(shù)依賴極為普遍地存在例如，描述學(xué)生的關(guān)系，可以有學(xué)號(hào)(SNO)，姓名(SNAME)，系名(SDEPT)等幾個(gè)屬性。由于一個(gè)學(xué)號(hào)只對(duì)應(yīng)一個(gè)學(xué)生，一個(gè)學(xué)生只在一個(gè)系學(xué)習(xí)。因而當(dāng)“學(xué)號(hào)”值確定之后，姓名和該生所在系的值也就被唯一地確定了。上述值的確定就象數(shù)學(xué)函數(shù)：自變量x確定之后，相應(yīng)的函數(shù)值f(x)也就唯一地確定。我們說(shuō)SNO函數(shù)決定SNAME和SDEPT，或者說(shuō)SNAME，SDEPT函數(shù)依賴于SNO，記為：SNO→SNAME，SNO→SDEPT。例：學(xué)生選課模型的關(guān)系模式《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/268例如，前面介紹的學(xué)生選課模型，可以用一個(gè)關(guān)系模式表示：SC(Sno,Sname,Sage,Sgendar,Sdept,Cno,Cname,Grade)一個(gè)可能的關(guān)系為：S1

趙一18

男CS

1

C語(yǔ)言80S1

趙一18男CS

2數(shù)據(jù)庫(kù)原理82S2

錢二19

男CS

1

C語(yǔ)言……80可以看出，該模式存在的主要問題是冗余。冗余帶來(lái)的問題《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/269冗余是不可避免的。在一定程度內(nèi)也是合理的。但是，過度的冗余則會(huì)給數(shù)據(jù)庫(kù)帶來(lái)三類大的問題：插入異常（學(xué)生不選課，其基本信息就無(wú)法插入）刪除異常（刪除學(xué)生選課信息，其基本信息也被刪除）修改復(fù)雜（修改某學(xué)生的基本信息，要隨選課多次被修改）解決冗余的方法《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2610解決的方法一個(gè)大關(guān)系分解為若干個(gè)小關(guān)系。感性經(jīng)驗(yàn)：多用小關(guān)系，少用字段。如前面的SC大關(guān)系分解為第三章的Student，SC和Course三個(gè)小關(guān)系，即可消除三類異常。問題的引出為什么小關(guān)系比大關(guān)系好呢？現(xiàn)在我們要討論的就是這個(gè)問題。從上面的分解觀察到：如果在一個(gè)關(guān)系模式內(nèi)，函數(shù)依賴形式上如果只有：碼

→ 非主屬性的形式，冗余就較小，三類異常就沒有了?！稊?shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2611本章目錄6.1

問題的提出6.2

規(guī)范化6.3

數(shù)據(jù)依賴的公理系統(tǒng)6.4

模式的分解《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26126.2

規(guī)范化《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2613目的將具有不合適性質(zhì)的關(guān)系轉(zhuǎn)換為更合適的形式。要求掌握函數(shù)依賴的定義及判定；掌握1NF到BCNF的定義及判定；了解多值依賴，理解4NF的定義。6.2.1

函數(shù)依賴(注意：現(xiàn)在還不能用到碼的概念。)定義6.1

設(shè)R(U)是屬性集U上的關(guān)系模式。X，Y是U的子集。若對(duì)于R的任何一個(gè)可能的關(guān)系r，r中不可能存在兩個(gè)元組在X屬性值上相等而在Y屬性值上不等，則稱X函數(shù)確定Y或Y函數(shù)依賴于X，記作：X→Y。《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26146.2.1

函數(shù)依賴X→Y，且Y

X，則稱X→Y是非平凡的函數(shù)依賴。若不特別聲明，我們總是討論非平凡的函數(shù)依賴。X→Y，但Y

X

則稱X→Y是平凡的函數(shù)依賴。理解為：整體一致，部分一致，沒有特殊意義（過于“平凡”）?！稊?shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26156.2.1

函數(shù)依賴若X→Y，則X叫做決定因素(Determinant)。若X→Y，Y→X，則記作X←→Y。在這種情況下，X和Y在R(U)中地位相同。若Y不函數(shù)依賴于X，則記作X→Y?！稊?shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26166.2.1

函數(shù)依賴定義6.2

(完全函數(shù)依賴和部分函數(shù)依賴的定義)在R(U)中如果X→Y，并且對(duì)X的任何一個(gè)真子集X’，都有X’→Y，則稱Y對(duì)X完全函數(shù)依賴，記作:X

→

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

YFP《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26176.2.1

函數(shù)依賴定義6.3（傳遞函數(shù)依賴）在R(U)中，如果X→Y，(Y

X)，Y→X，Y→Z，則稱Z對(duì)X傳遞函數(shù)依賴。記作：X→

Z傳遞《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26186.2.2

碼定義6.4

設(shè)K為R<U,F>中的屬性或?qū)傩越M，若K→U，則FK為R的候選碼(Candidate

Key)。若候選碼多于一個(gè)，則選定其中一個(gè)作為主碼(PrimaryKey)。主屬性(Prime

attribute)：包含在任何候選碼中的屬性。非主屬性(Nonprime

attribute)：不包含在任何候選碼中的屬性。也稱非碼屬性(Non-key

attribute).《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26196.2.2

碼定義6.5

(外碼的定義)關(guān)系模式R中的屬性或?qū)傩越MX并非R的碼，但

X是另一個(gè)關(guān)系模式的碼，則稱X是R的外部碼，簡(jiǎn)稱外碼?！稊?shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26206.2.3

范式《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2621滿足最低要求的關(guān)系，叫第一范式，簡(jiǎn)稱1NF。關(guān)系表的每一分量是不可分的數(shù)據(jù)項(xiàng)1NF

不允許表中出現(xiàn)嵌套或復(fù)合的屬性5NF

4NF

BCNF

3NF

2NF

1NF6.2.42NF定義6.6

若R

1NF，對(duì)R的每一個(gè)非平凡的函數(shù)依賴X→Y，要么Y是主屬性，要么X不是任何碼的真子集，則R

2NF。2NF

在1NF基礎(chǔ)上消除了非主屬性對(duì)碼的部分函數(shù)依賴?！稊?shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26226.2.42NF《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2623例：前面的大表SC不是2NF的關(guān)系模式。例4：關(guān)系模式S-L-C(Sno,Sdept,Sloc,Cno,Grade)存在函數(shù)依賴Sno

→

SdeptSdept

→

Sloc(Sno,Cno)

→

Grade唯一候選碼(Sno,Cno)。則Sno→Sdept是非主屬性對(duì)碼的部分函數(shù)依賴。6.2.42NF《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2624如果一個(gè)關(guān)系模式不是2NF的，一定存在過度冗余，帶來(lái)3類異常。解決方法：分解為多個(gè)小表。如S-L-C分解為{S-L(Sno,Sdept,Sloc),SC(Sno,Cno,Grade)}2NF僅僅具有歷史意義。6.2.53NF定義6.7

若R

1NF，對(duì)R中的每一個(gè)非平凡的函數(shù)依賴X→Y，要么Y是主屬性，要么X中含有碼，則R

3NF?！稊?shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26256.2.53NF《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26263NF與2NF相比，條件更強(qiáng)。因?yàn)閄中含有碼，則X不會(huì)是任何碼的真子集；而2NF定義中，X不是任何碼的真子集，還可能是非主屬性組。即3NF在2NF的基礎(chǔ)上消除了非主屬性對(duì)碼的傳遞函數(shù)依賴。6.2.53NF判斷3NF例子S-L(Sno,Sdept,Sloc)唯一候選碼Sno函數(shù)依賴Sno

→Sdept,Sdept

→Sloc沒有非主屬性對(duì)碼的部分函數(shù)依賴，滿足2NF。存在非主屬性對(duì)非主屬性的函數(shù)依賴，不滿足3NF。非主屬性非主屬性《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26276.2.53NF《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2628滿足2NF，不滿足3NF，仍有過度冗余及其帶來(lái)的3類異常。S1CSB01S2CSB01S3CSB01S100MAB026.2.53NF《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2629解決方法，分解成小關(guān)系S-D(Sno,

Sdept)D-L(Sdept,

Sloc)6.2.6

BCNF由Boyce和Codd共同提出，屬于修正的3NF。定義6.8

若R

1NF，對(duì)R中的每一個(gè)非平凡的函數(shù)依賴X→Y，X中均含有碼，則R

BCNF。《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26306.2.6

BCNF《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2631BCNF與3NF相比，條件更強(qiáng)。不允許主屬性對(duì)碼的部分和傳遞函數(shù)依賴。到BCNF為止，完全消除了由于函數(shù)依賴帶來(lái)的過度冗余及相應(yīng)的三類異常。6.2.6

BCNF《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2632例7

(BCNF的例子)關(guān)系模式SPJ（學(xué)生，課程，名次）每個(gè)學(xué)生選每門課程有一定名次每門課程中每一名次只有一個(gè)學(xué)生6.2.6

BCNF例7

(BCNF的例子)關(guān)系模式SPJ（學(xué)生，課程，名次）每個(gè)學(xué)生選每門課程有一定名次每門課程中每一名次只有一個(gè)學(xué)生(學(xué)生,課程)->名次《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2633(課程,名次)->學(xué)生6.2.6

BCNF例7

(BCNF的例子)關(guān)系模式SPJ（學(xué)生，課程，名次）每個(gè)學(xué)生選每門課程有一定名次每門課程中每一名次只有一個(gè)學(xué)生(學(xué)生,課程)->名次(課程,名次)->學(xué)生候選碼《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26346.2.6

BCNF《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2635例8(是3NF，但不是BCNF的例子)關(guān)系模式STJ（學(xué)生，教師，課程）每一教師只教一門課一個(gè)學(xué)生選定某門課程，就對(duì)應(yīng)一個(gè)固定的教師6.2.6

BCNF例8(是3NF，但不是BCNF的例子)關(guān)系模式STJ（學(xué)生，教師，名次）每一教師只教一門課一個(gè)學(xué)生選定某門課程，就對(duì)應(yīng)一個(gè)固定的教師教師->課程《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2636(學(xué)生,課程)->教師6.2.6

BCNF例8(是3NF，但不是BCNF的例子)關(guān)系模式STJ（學(xué)生，教師，課程）每一教師只教一門課一個(gè)學(xué)生選定某門課程，就對(duì)應(yīng)一個(gè)固定的教師教師->課程(學(xué)生,課程)->教師候選碼教師,學(xué)生《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26376.2.6

BCNF例8存在的過度冗余教師學(xué)生課程王紅李明數(shù)據(jù)庫(kù)王紅劉晨數(shù)據(jù)庫(kù)王紅王敏數(shù)據(jù)庫(kù)劉軍張立C語(yǔ)言劉軍劉晨C語(yǔ)言“每個(gè)教師上一門課”隨選課學(xué)生的增加而被重復(fù)存儲(chǔ)《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26386.2.6

BCNF《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2639解決方法——還是分解分解為兩個(gè)小關(guān)系模式(都是BCNF的)ST(學(xué)生,教師)TJ(教師,課程)或SJ(學(xué)生,課程)TJ(教師,課程)6.2.6

BCNF解決方法——還是分解分解為兩個(gè)小關(guān)系模式(都是BCNF的)ST(學(xué)生,教師)TJ(教師,課程)或SJ(學(xué)生,課程)TJ(教師,課程)兩種分解都損失了：“一個(gè)學(xué)生選定某門課程，就對(duì)應(yīng)一個(gè)固定的教師”語(yǔ)義《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26406.2.6

BCNF解決方法——還是分解分解為兩個(gè)小關(guān)系模式(都是BCNF的)ST(學(xué)生,教師)TJ(教師,課程)或SJ(學(xué)生,課程)TJ(教師,課程)兩種分解都損失了：“一個(gè)學(xué)生選定某門課程，就對(duì)應(yīng)一個(gè)固定的教師”語(yǔ)義函數(shù)依賴“(學(xué)生,課程)->教師”在分解后沒有保持！《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26416.2.6

BCNF《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2642事實(shí)上，關(guān)系模式即使到了BCNF，還可能存在由于非函數(shù)依賴帶來(lái)的冗余及三類異常。這些數(shù)據(jù)依賴有多值依賴和連接依賴。我們

只簡(jiǎn)單要求多值依賴。在多個(gè)實(shí)體間聯(lián)系為1對(duì)多聯(lián)系時(shí)可能出現(xiàn)多值依賴帶來(lái)的問題。6.2.7

多值依賴多值依賴定義：設(shè)有關(guān)系模式R(U)，X,Y,Z是U的非空子集。對(duì)于R的任一關(guān)系r，給定一對(duì)(x,z)值，就

有一組Y的值與之對(duì)應(yīng)，這組值僅僅決定于x值而與z值無(wú)關(guān)，則稱“Y多值依賴于X”或“X

多值決定Y”。記作X→→Y。或記憶為：設(shè)有關(guān)系模式R(U)，X,Y,Z是U的非空子集。對(duì)R(U)的任一關(guān)系r，任意兩元組s和t，如果s[X]=t[X]，則交換s和t的Y值所得兩個(gè)新元組必在r中?！稊?shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26436.2.7

多值依賴《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2644翻譯情況AB

C（姓名，東方語(yǔ)言，西方語(yǔ)言）—————————————王紅日語(yǔ)法語(yǔ)王紅漢語(yǔ)英語(yǔ)王紅日語(yǔ)英語(yǔ)王紅漢語(yǔ)法語(yǔ)是BCNF

,

其中

只有ABC

才是關(guān)鍵字但有冗余,又有刪除異常例如刪除（王

紅 漢語(yǔ) 法語(yǔ)）6.2.7

多值依賴衣著（姓名，衣服，褲子）類似，可稱為完全搭配依賴（課程,教師,參考書）類似，看書上《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26456.2.7

多值依賴《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2646不是多值依賴的例子：學(xué)生選課表SC（Sno，Cno，G）中一個(gè)Sno（一個(gè)學(xué)生）有一組Cno（選了一組課程）和一組G（有一組成績(jī)），但Cno與G有關(guān)（成績(jī)與課程有關(guān)），所以沒有

Sno→→Cno，以及Sno→→G。也就是說(shuō)一個(gè)學(xué)生選的一組課程和一組成績(jī)沒有形成完全搭配。6.2.7

多值依賴《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2647平凡的多值依賴：若X→→Y，而Z=

；則稱X

→→Y是平凡的多值依賴。多值依賴的性質(zhì)：1、對(duì)稱(互補(bǔ))性：若X→→Y；則X→→Z，其中Z=U-X-Y。2、傳遞性：若X→→Y，Y→→Z；則X→→Z-Y。3、函數(shù)依賴是多值依賴的特殊情況：若X→Y，則X→→Y。4、若X→→Y，X→→Z；則X→→YZ，X→→Z-Y，X→→Y-Z，X

→→Y∩Z。6.2.84NF定義6.10若關(guān)系模式R（U，F(xiàn)）∈1NF，如果對(duì)于R的每個(gè)非平凡多值依賴X→→Y（Y不包含于X），X都含有碼，則稱R（U，F(xiàn)）∈4NF。實(shí)質(zhì)上4NF消除了多值依賴。為什么？《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26486.2.9

規(guī)范化小結(jié)《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26491NF：每個(gè)分量是不可分的數(shù)據(jù)項(xiàng)?！?NF：非主屬性完全函數(shù)依賴于碼。∪

3NF：非主屬性既不部分依賴于碼也不傳遞依賴于碼?！?/p>

BCNF：所有屬性都不部分依賴于碼也不傳遞依賴于碼。所有決定因素(屬性集)都包含碼?！?NF：所有非平凡的多值依賴都是函數(shù)依賴。本章目錄6.1

問題的提出6.2

規(guī)范化6.3

數(shù)據(jù)依賴的公理系統(tǒng)6.4

模式的分解《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2650函數(shù)依賴公理系統(tǒng)的背景《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2651為了求得給定關(guān)系模式的碼，為了從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴，例如已知函數(shù)依賴集F，要問X→Y是否為F所蘊(yùn)含，就需要一套推理規(guī)則，這組推理規(guī)則是1974年首先由Armstrong提出來(lái)的。它是關(guān)系模式分解算法的理論基礎(chǔ)。要求得給定關(guān)系模式的所有候選碼對(duì)于關(guān)系模式的范式級(jí)別判定具有決定作用：范式級(jí)別的判定需要知道關(guān)系模式的所有候選碼；有的范式級(jí)別還需確定主屬性和非主屬性，也需要知道所有候選碼。數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊(yùn)含：定義6.11

對(duì)于關(guān)系模式R<U，F(xiàn)>，其任何一個(gè)關(guān)系r，若函數(shù)依賴X→Y都成立（即r中任意兩元組s，t，若t[X]=s[X]，則t[Y]=s[Y]），則稱函數(shù)依賴集F邏輯蘊(yùn)含X→Y。《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2652Armstrong

公理系統(tǒng)A1

自反律若Y

X

U，則X→Y為F所蘊(yùn)含(給出平凡的函數(shù)依賴)。A2

增廣律若X→Y為F所蘊(yùn)含，且Z

U，則XZ→YZ為F所蘊(yùn)含。A3

傳遞律如X→Y及Y→Z為F

所蘊(yùn)含，則X→Z為F所蘊(yùn)含。證明見定理6.1《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2653Armstrong

公理系統(tǒng)《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2654Armstrong公理的推論：合并規(guī)則：若X→Y，X→Z，有X

→YZ。分解規(guī)則：由X

→Y及Z包含于Y，有X→Z。偽傳遞規(guī)則：若X→Y，WY→Z，有XW→Z。根據(jù)合并規(guī)則和分解規(guī)則，得到一個(gè)重要事實(shí)：X→A1A2…AK成立的充分必要條件是X→Ai(i=1,2,…,k)成立。Armstrong

公理系統(tǒng)《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2655定義6.12

F的閉包：函數(shù)集閉包(找親戚的親戚)在關(guān)系模式R<U，F(xiàn)>中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫做F的閉包，記作F

+。Armstrong公理是有效的，完備的：有效性：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來(lái)的每個(gè)函數(shù)依賴一定在F+中。有效性的證明書上定理6.1“Armstrong推理規(guī)則是正確的”可直接得證。完備性：F

+中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來(lái)。經(jīng)典證明Armstrong

公理系統(tǒng)定義6.13(屬性集閉包)XF

+的定義設(shè)F是屬性集U上的一組函數(shù)依賴集，X

U，XF

+＝{A|X→A能由F根據(jù)Armstrong公理導(dǎo)出}。引理6.2

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

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

XF

+《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2656算法6.1求XF

+的方法--非常重要《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2657計(jì)算

XF

，滾雪球算法+result

:=X;

//從X

開始while

(changes

to

result

)

dofor

each

V

W

in

F

dobeginif

V

result

then

result

:=

result

Wendreturn

result例例1

關(guān)系模式R<U,F>,U={A,B,C,D,E},F={AB→C,B→D,C→E,EC→B,AC→B},求(AC)F+0.初始化令result＝AC1.第一次循環(huán)計(jì)算result

=ACEB=ABCE2.第二次循環(huán)計(jì)算result=ABCDE即得結(jié)果。定義6.13，引理6.2和算法6.1非常重要，可用于求碼。如KF

+=

U,

而K’F

+

!=

U，即求得K為一候選碼?！稊?shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2658求碼方法要點(diǎn)(自己的總結(jié))《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2659找出不出現(xiàn)在非平凡函數(shù)依賴右部的屬性組X，它們一定包含于所有候選碼。求XF

，判斷＝U？成立結(jié)束，否則轉(zhuǎn)3。+(自底向上)擴(kuò)展X的X’’，求X’’F+，判斷＝U？直到所有情況找完為止。例《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2660應(yīng)用舉例，對(duì)書上P184例1，求所有候選碼要點(diǎn)：不出現(xiàn)在任何函數(shù)依賴右部的只有A；求AF+＝A；擴(kuò)展AB，ABF

＝U；+AC，ACF

＝U；+AD，ADF

！＝U；（需再擴(kuò)展）+AE，AEF

?。経；（需再擴(kuò)展）+再擴(kuò)展ADE，ADEF

?。経+6.3

數(shù)據(jù)依賴的公理系統(tǒng)《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2661要證明完備性首先解決如何判定一個(gè)函數(shù)依賴是否屬于由F根據(jù)Armstrong公理推導(dǎo)出來(lái)的函數(shù)依賴的集合。如果能求出這個(gè)集合就很容易判斷，但是求這樣的集合是一個(gè)NP完全問題。所以該判定轉(zhuǎn)換為：任一個(gè)函數(shù)依賴X

→Y是F

+

中成員的充分必要條件是：

Y

XF

+

。證明完備性轉(zhuǎn)換為證明它的逆否命題為真。即若函數(shù)依賴不能由F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)含。證明分3步（略）證明用到了構(gòu)造(特殊的二維表)、反證，十分巧妙。6.3

數(shù)據(jù)依賴的公理系統(tǒng)《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2662完備性證明要證原命題，只需證明其逆否命題：若函數(shù)依賴X→Y不能由F出發(fā)從Armstrong公理導(dǎo)出，則它本身不為F所蘊(yùn)含。（1）若V→W成立，且V

XF

+，則W

XF

+。V

XF

+，則由引理6.2，有X→V。由X→V，V→W，有X→W。再由引理6.2，有W

XF

+。6.3

數(shù)據(jù)依賴的公理系統(tǒng)（2）構(gòu)造如下二維表r，r必是R<U,F>的一個(gè)關(guān)系。用反證法。XF

+U－

XF

+－－－－－－－－－－－－－11…….

111…….

100

…

…

011…

…

1若r不是R<U,F>的關(guān)系，必是由F中的函數(shù)依賴V

→W在r上不成立所致。觀察r，V

XF

+，而W

XF

+。與（1）矛盾?！稊?shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26636.3

數(shù)據(jù)依賴的公理系統(tǒng)《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2664（3）若X→Y不能由Armstrong公理導(dǎo)出則Y不是XF

+的子集，必有Y’

Y，且Y’

U－XF

+。（推）X→Y本身不為F所蘊(yùn)含。（觀察r）得證。6.3

數(shù)據(jù)依賴的公理系統(tǒng)定義6.14

函數(shù)依賴集等價(jià)：如果G

+=F

+，就說(shuō)函數(shù)依賴集F覆蓋G（F是G的覆蓋或G是F的覆蓋），或F與G等價(jià)。有相應(yīng)的判定算法。引理6.3的充分性證明的過程實(shí)際上給出了判斷兩函數(shù)依賴集等價(jià)的方法。引理6.3

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

G+，和G

F+?！稊?shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26656.3

數(shù)據(jù)依賴的公理系統(tǒng)《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2666定義6.15

最小依賴集右部唯一無(wú)多余函數(shù)依賴無(wú)部分函數(shù)依賴定理6.3

每一個(gè)函數(shù)依賴集都等價(jià)于一個(gè)極小函數(shù)依賴集Fm(Fm一定存在，可能不唯一)。定理6.3的證明過程給出了檢驗(yàn)(或構(gòu)造)Fm的方法。求解極小函數(shù)依賴集的過程《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2667用分解規(guī)則將F中每一函數(shù)依賴分解為若干個(gè)右部唯一的函數(shù)依賴，新函數(shù)依賴集仍命名為F。判斷當(dāng)前F中有沒有多余的函數(shù)依賴。注意，檢查X→A，要在G集(其中G=F-{X→A})下考察X→A是否被蘊(yùn)含(G集下計(jì)算XG+，看A是否包含在其中)。處理后的函數(shù)依賴集不妨仍命名為F。判斷當(dāng)前F中每一函數(shù)依賴左部有沒有多余的屬性。注意，檢查AB→Y中B是否多余時(shí)，令G=F-{AB→Y}∪{A→Y},需要考察A→Y是否為F所蘊(yùn)含F(xiàn)(F集下計(jì)算X

+，看Y是否包含在其中)。最后得到F的函數(shù)依賴集Fm。6.3

數(shù)據(jù)依賴的公理系統(tǒng)例子：設(shè)F＝{AB→C，A→B}，求Fm。Fm＝{B→C，A→B}

?對(duì)不對(duì)？為什么？《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26686.3

數(shù)據(jù)依賴的公理系統(tǒng)上面的F與Fm根本不等價(jià)。Fm＝{A→C，A→B}《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2669本章目錄6.1

問題的提出6.2

規(guī)范化6.3

數(shù)據(jù)依賴的公理系統(tǒng)6.4

模式的分解《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26706.4

模式的分解要求了解前面我們?yōu)榱私鉀Q設(shè)計(jì)得不好(范式級(jí)別不夠高)的數(shù)據(jù)庫(kù)模式帶來(lái)的問題，我們采用了大關(guān)系分解為小關(guān)系的方法來(lái)提高范式級(jí)別。本節(jié)給出分解的理論指導(dǎo)。《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26716.4.1

模式分解的三個(gè)定義具有無(wú)損連接性。分解后的(幾個(gè))小模式可自然連接恢復(fù)為原來(lái)的模式。保持函數(shù)依賴分解前后函數(shù)依賴集等價(jià)既保持無(wú)損連接，又保持函數(shù)依賴。(理想情況)《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26726.4.2

分解的無(wú)損連接性和保持函數(shù)依賴性mρ(r)＝πR1(r)

πR2(r)

…

πRk(r)定義5.18

ρ＝{R1<U1,F1>，R2<U2,F2>…Rk<UK,FK>}是R<U,F>上的一個(gè)分解，若對(duì)

于R<U,F>的任一關(guān)系r，均有r＝

mρ(r)成立，則ρ具有無(wú)損連接性。此定義無(wú)法用于判斷，無(wú)損連接性只能通過算法6.2或定理6.5來(lái)判斷?！稊?shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26736.4.2

分解的無(wú)損連接性和保持函數(shù)依賴性算法6.2

要求會(huì)做。(通過例子來(lái)學(xué)習(xí))例1

R(S，A，I，P)分解為R1(S，A)，R2(S，I，P)。F

＝{S→A,

SI→P}S

A

I

Pa1

a2 b13b14a1b22

a3

a4由于有S→A，使第二行第二列變成a2。S

A

I

Pa1

a2 b13b14a1

a2

a3

a4《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/26746.4.2

分解的無(wú)損連接性和保持函數(shù)依賴性補(bǔ)充例R(A，B，C，D，E)，分解R1=AD,R2=AB,

R3=BE,

R4=CDE,

R5=AE F={A→C,

B→C,

C→D,DE→C,

CE→A}A

B

C

D

Ea1b12b13a4b15a1a2b23b24b25b31a2b33b34a5b41b42a3a4a5a1b52b53b54a5《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章2023/10/2675A→C

(b23變b13，b53變b13),B→C

(b33變b13),C→D(b24,b34,b54變a4),DE→C(C列變a3)CE→A(A列變a1)第三行出現(xiàn)了a1到a5.6.4.2

分解的無(wú)損連接性和保持函數(shù)依賴性《數(shù)據(jù)庫(kù)系統(tǒng)概論》-第6章