database第3章 第1次課

1、Content3.1 Functional Dependencies 函數(shù)依賴3.2 Rules About Functional Dependencies 函數(shù)依賴的規(guī)則Chapter 3 Design Theory for Relational Databases - First3.1 Functional Dependencies There is a design theory for relations that lets us examine a design carefully and make improvements based on a few simple princip

2、les. The theory begins by having us state the constraints that apply to the relation. The most common constraint is the “functional dependency”, a statement of a type that generalizes the idea of a key for a relation, which we introduced in Section 2.5.3. Later in this chapter, we shall see how this

3、 theory gives up simple tools to improve our designs by the process of “decomposition” of relations : the replacement of one relation by several, whose sets of attributes together include all the attributes of the original. 關系的設計理論使人們可以根據(jù)少數(shù)簡單原則來認真檢驗一個設計并做出改進。這一理論首先能夠規(guī)定作用在關系上的約束。最常見的約束是“函數(shù)依賴”，它泛化了關系中

4、“鍵”的概念。本章隨后介紹如何使用關系設計理論給予的一些簡單工具，通過關系的分解過程來改進設計，即用若干關系替代原關系，這些關系的屬性集合包含了原關系的所有屬性。3.1 Functional Dependencies1. Definition of Functional Dependency 函數(shù)依賴的定義 A functional dependency(FD) on a relation R is a statement of the form “If two tuples of R agree on all of the attributes A1,A2,An (i.e., the tup

5、les has the same values in their respective components for each of these attributes), then they must also agree on all of another list of attributes B1,B2,Bm. We write this FD formally as A1,A2,An B1,B2,Bm and say that “A1,A2,An functionally determine B1,B2,Bm” 關系R上的函數(shù)依賴是指如果R的兩個元組在屬性A1,A2,An上一致（即它們對

6、應于這些屬性的分量值都相等），那么它們必定在其他屬性B1,B2,Bm上也一致。該函數(shù)依賴形式地記為A1,A2,An B1,B2,Bm，并稱為A1,A2,An函數(shù)決定B1,B2,Bm。3.1 Functional Dependencies1. Definition of Functional Dependency If we can be sure every instance of a relation R will be one in which a given FD is true, then we say that R satisfies the FD. It is important

7、to remember that when we say that R satisfies an FD f, we are asserting a constraint on R, not just saying something about one particular instance of R. It is common for the right side of an FD to be a single attribute. 如果確定關系R的每個實例都能使一個給定的FD為真，那么稱R滿足函數(shù)依賴f。這是在R上聲明了一個約束，而不是僅僅針對R的一個特殊實例。通常，F(xiàn)D的右邊可能是單個屬

8、性。3.1 Functional DependenciesExample:SIDSNameCIDCNameScore1001JackyT01OS781001JackyK01CE851001JackyT02DS871002RoseT01OS721002RoseK01CE841003FloraK01CE881003FloraK02EC841004JamesK02EC89Relational Schema:SCJ(SID, SName, CID, CName, Score)SID SName CID CName (SID, CID) Score SCJ3.1 Functional Dependenc

9、ies2. Keys of Relations 關系的鍵 We say a set of one or more attributes A1,A2,An is a key for a relation R if : 如果下列條件滿足，就認為一個或多個屬性集A1,A2,An是關系R的鍵： (1) Those attributes functionally determine all other attributes of the relation. That is, it is impossible for two distinct tuples of R to agree on all of

10、A1,A2,An. 這些屬性函數(shù)決定關系的所有其他屬性。即不存在兩個不同的元組，它們具有相同的A1,A2,An值。3.1 Functional Dependencies2. Keys of Relations 關系的鍵 (2) No proper subset of A1,A2,An functionally determines all other attributes of R; i.e., a key must be minimal. 在A1,A2,An的真子集中，沒有一個能函數(shù)決定R的所有其他屬性。也就是說，鍵必須是最小的。 When a key consists of a singl

11、e attribute A, we often say that A (rather than A) is a key. 當鍵只包括一個單獨的屬性A時，稱A（而不是A）是鍵。3.1 Functional Dependencies2. Keys of RelationsExample: Student(ID, Name, Sex, Birth); Now, we must argue that all proper subset of ID, Name, Sex, Birth functionally determines all other attributes. 下面將討論的是ID, Nam

12、e, Sex, Birth 的任一真子集都是否函數(shù)決定其他的屬性。 ID; Name; Sex; Birth; ID, Name; ID, Sex; ID, Birth; Name, Sex; Name, Birth; Sex, Birth ; ID, Name, Sex; ID, Name, Birth; ID, Sex, Birth; Name, Sex, Birth; ID, Name, Sex, Birth3.1 Functional Dependencies2. Keys of Relations Sometimes a relation has more than one key.

13、 If so, it is common to designate one of the keys as the primary key. In commercial database systems, the choice of primary key can influence some implementation issues such as how the relation is stored on disk. However, the theory of FDs gives to special role to “primary key”. 有時一個關系可能會有多個鍵。如果是這樣的

14、話，通常就要指定其中一個為主鍵。在商業(yè)數(shù)據(jù)庫系統(tǒng)中，對主鍵的選擇會影響某些實現(xiàn)問題，例如怎樣在磁盤中存儲關系。然而，函數(shù)依賴理論并未給主鍵以特殊的角色。3.1 Functional Dependencies3. Super key 超鍵 A set of attributes that contains a key is called a super key, short for “super set of a key”. Thus, every key is a super key. However, some super keys are not minimal key. Note tha

15、t every super key satisfies the first condition of a key: it functionally determines all other attributes of the relation. However, a super key need not satisfy the second condition: minimality. 一個包含鍵的屬性集就叫做超鍵，它是鍵的超集的簡寫。因此，每個鍵都是超鍵。然而，某些超鍵不是鍵。注意，每個超鍵都滿足鍵的第一個條件：它函數(shù)決定了關系中所有其他屬性。但超鍵不需要滿足第二個條件：最小化。3.1 Fu

16、nctional Dependencies4. Exercise（1）考慮一個關于美國公民的關系，這個關系的屬性有：姓名、社會保險號、街道地址、城市、州、郵編、地區(qū)代碼和電話號碼（7位數(shù)字）。這個關系有哪些FD？關系的鍵是什么？（假設一個地區(qū)只能用于一個州，一個郵編不能跨越兩個地區(qū)代碼，兩個人不能有相同的社會保險號，但可以有相同的地址和電話號碼） FD: Social Security number Name, Area code, State, City, Street Adrress, Zipcode, Phone Area code State Street address, City,

17、 State zipcode Key: Social Security number Street address, City, Area code, Phone, Name3.1 Functional Dependencies4. Exercise（2）考慮一個表示密封容器中的分子位置的關系，屬性有分子的ID，分子位置的x、y、z方向上的速率，你認為這個關系上有哪些FD？鍵是什么？ FD:ID (x-position, y-position, z-position)ID (x-velocity, y-velocity, z-velocity)(x-position, y-position,

18、z-position) ID Key: IDx-position, y-position, z-position 3.1 Functional Dependencies4. Exercise（3）假設R是含有屬性A1,A2,An的關系。如果給出下列條件，指出R有多少超鍵。 a) A1是僅有的鍵 2n-1 b) A1或A2是鍵 2n-1+2n-2 c) A1,A2或A3,A4是鍵 2n-2+2n-2-2n-4 d) A1,A2 或A1,A3是鍵 2n-2+2n-2-2n-33.2 Rules About Functional Dependencies1. Reasoning About Func

19、tional Dependencies 函數(shù)依賴的規(guī)則 If we are told that a relation R(A, B, C) satisfies the FDs AB and BC, then we can deduce that R also satisfies the FD AC. 如果關系R(A,B,C)滿足FD：AB 和 BC，那么就可以推斷出R也滿足FD：AC。 Example: WAE(ID, Area, Leader, Device, Amount) ID Area Area Leader ID Leader3.2 Rules About Functional De

20、pendencies2. The Splitting / Combining Rule 分解/結合規(guī)則 We can replace an FD A1A2An B1B2Bm by a set of FDs A1A2An Bi (i=1,2,m). This transformation we call the splitting rule. 可以用一個FD的集合A1A2An Bi (i=1,2,m) 替換FD A1A2An B1B2Bm, 這種轉化稱為分解規(guī)則。 We can replace a set of FDs A1A2An Bi (i=1,2,m) by the single FD A

21、1A2An B1B2Bm . We call this transformation the combining rule. 可以用一個FD的集合A1A2An B1B2Bm替換FD A1A2An Bi (i=1,2,m)，這種轉化稱為組合規(guī)則。3.2 Rules About Functional Dependencies2. The Splitting / Combining Rule 分解/結合規(guī)則 Example: Course_Select(ID, Name, CouseID, CourseName, Score) (ID, CouseID) Name (ID, CouseID) Cou

22、rseName (ID, CouseID) Score is equivalent to the single FD: (ID, CouseID) (Name, CourseName, Score)3.2 Rules About Functional Dependencies2. The Splitting / Combining Rule Example: Course_Select(ID, Name, CouseID, CourseName, Score) (ID, CouseID) Name split the FDs into two FDs: ID Name CouseID Name

23、 That is, CouseID does not functionally determine Name. 3.2 Rules About Functional Dependencies3.1 Nontrivial / Trivial Functional Dependencies（非平凡函數(shù)依賴和平凡函數(shù)依賴） 如果R是一個在屬性集合U上的關系模式，X和Y是U的子集，如果X決定Y，并且Y不屬于X，就稱X決定Y是非平凡函數(shù)依賴。如果Y屬于X，就稱X決定Y是平凡函數(shù)依賴。 例： （學號，姓名） 姓名 平凡函數(shù)依賴 學號 姓名 非平凡函數(shù)依賴3.2 Rules About Functional

24、 Dependencies3.2 Full / Partial Functional Dependencies（完全函數(shù)依賴和部分函數(shù)依賴）fp 在R(U)中，如果X決定Y，并且對于X的任何一個真子集X，都有X不能決定Y，那么稱Y完全函數(shù)依賴X。 如果X決定Y，但不完全函數(shù)依賴于X，則稱Y對X部分函數(shù)依賴。3.2 Rules About Functional Dependencies3.3 Transitive Functional Dependencies （傳遞函數(shù)依賴）t 在R(U)中，如果X決定Y，Y決定Z，并Y不屬于 X，Y不決定X，并且對于X的任何一個真子集X，都有X不能決定Y，那

25、么稱Y完全函數(shù)依賴X。3.2 Rules About Functional Dependencies3.2.9 習題1. 考慮模式為R(A, B, C, D)的關系R和FD：ABC，CD和DA。a) 從給定的FD集合能夠推出的非平凡FD是什么？限制FD的右邊只能有一個屬性。b) R的所有鍵是什么？ 從所有FD集觀察，可以發(fā)現(xiàn)屬性B沒有出現(xiàn)在所有FD集的右邊，所以鍵中包括屬性B，再從所有FD集找出推導式左邊式中包含屬性B的集合，有AB，BC，BD，ABC，ABD，BCD，再根據(jù)鍵是最小化的屬性集，所以R的鍵是AB或BC或BD。c) R的所有鍵（不包含鍵）是什么？ 超鍵是ABC、ABD、BCD和A

26、BCD增值依賴： CD，可推導BCD CD，可推導ACD DA，可推導BDA DA，可推導CDA BCD，可推導ABCD ABC，可推導ABDC BDA，可推導BCDA傳遞依賴：ABC和CD，可推導ABD CD和DA，可推導CA CD和BDA，可推導BCA ABC和DA，可推導BDC3.2 Rules About Functional Dependencies3.2.9 習題2. 針對下列模式和FD集合，重做習題3.2.1中的問題：i) 模式為S(A, B, C, D)，F(xiàn)D: AB, BC和BD.(1) FDAC, AD, ABC, ABD, ACB, ACD, ADB, ADB, ABCD

27、, ABDC, ACDB (2) S的鍵是A(3) S的所有鍵（不包含主鍵）:AB、AC、AD、ABC、ABD、ABCDii) 模式為T(A, B, C, D)，F(xiàn)D: ABC, BCD, CDA和ADB.(1) FDABD, ADC, BCA, CDB, ABCD, ABDC, ACDB, BCDA(2) S的鍵是AB或BC或CD或AD(3) S的所有鍵（不包含主鍵）:ABC、ABD、ACD、BCD、ABCDiii) 模式為U(A, B, C, D)，F(xiàn)D: AB, BC, CD和DA.(1) FDAC, BD, CA, ABC, ABD, ACB, ACD, ADB, ADC, BCA,

28、BCD, BDA, BDC, CDA, CDB, ABCD, ABDC, ACDB, BCDA(2) S的鍵是A或B或C或D(3) S的所有鍵（不包含主鍵）:AB、AC、AD、BC、BD、CD、ABC、ABD、ACD、BCD、ABCD3.2 Rules About Functional Dependencies4. Computing the closure of Attributes 計算屬性的閉包 Suppose U(A1,A2,An) is a set of attributes and F is a set of FDs. The closure of U under the FDs

29、in F is the set of attributes B such that every relation that satisfies all the FDs in set F also satisfies UB. That is UB follows from the FDs of F. We denote the closure of a set of attributes U by U+. 假設屬性集合UA1,A2,An和函數(shù)依賴集合F。則F集合下的屬性集合U的閉包是滿足下面條件的屬性集合B，即使得每一個滿足F中所有FD的關系，也同樣滿足U決定B。也就是說，U決定B能由F中的FD

30、推斷出來。屬性集合U的閉包記為U+.3.2 Rules About Functional Dependencies4. Computing the closure of Attributes （計算屬性的閉包）Algorithm 3.7: Closure of a set of Attributes.（屬性集合的閉包）Input: A set of attributes U and a set of FDs F.輸入：屬性集合U=A1,A2,An，F(xiàn)D的集合F。輸入示例：UA,B，F(xiàn)AB C，BC AD，D E，CF BOutput: The closure U+.輸出：屬性A,B的閉包U+。

31、Step1: If necessary, split the FDs of F, so each FD in F has a single attribute on the right.步驟1：如果必要，分解S中的FD，使每個FD的右邊只有一個屬性。步驟1示例：FAB C, BC A, BC D, D E, CF BStep2: Let X be a set of attributes that eventually will become the closure. Initialize X to be U.步驟2：設X是屬性集合，也就是閉包。首先，將X初始化為A1,A2,An。步驟2示例：X

32、A, B。3.2 Rules About Functional Dependencies4. Computing the closure of AttributesStep3: Repeatedly search for some FD: B1B2Bm C, such that all of B1B2Bm are in the set of attributes X, but C is not. Add C to the set X and repeat the search. Since X can only grow, and the number of attributes of any

33、 relation schema must be finite, eventually nothing more can be added to X, and Step 3 ends.步驟3：反復尋找這樣的FD：B1B2Bm C，使得B1,B2,Bm在X中，而C不在X中，若找到，則把C加入X，并重復這個過程。因為集合X只能增長，而任何一個關系模式中的屬性都是有限的，所以最終沒有任何元素能再加入X時，本步驟結束。步驟3示例：(1) 因為AB C，C不在集合X中，所以將屬性C加入X，XA, B, C(2) 因為BC A，但A已經(jīng)在集合X中，所以不用添加，XA, B, C(3) 因為BC D，D不在

34、集合X中，所以將屬性D加入X，XA, B, C, D(4) 因為D E，E不在集合X中，所以將屬性E加入X，XA, B, C, D, E(5) 因為CF B，但F不在集合X中，不能進行函數(shù)依賴，X=A, B, C, D, E3.2 Rules About Functional Dependencies4. Computing the closure of AttributesStep4: The set X, after no more attributes can be added to it ,is the correct value of U+.步驟4：當不能再添加任何屬性時，集合X就是

35、A1,A2,An+步驟4示例：因為所有函數(shù)依賴已經(jīng)完成推導過程，所以集合XA,B,C,D,E就是屬性集合A,B的閉包。3.2 Rules About Functional Dependencies4. Computing the closure of AttributesExample: In R(U,F), U=A,B,C,D,E,F, F=ABC, BCAD, DE, CFB. What is the closure of A,B, that is, A,B+ ? Step 1: Split BCAD into BCA and BCD Step 2: X=A,B Step 3: ABC X

36、=A,B,C BCA because A is in X, so no effect BCD X=A,B,C,D DE X=A,B,C,D,E CFB because C is in X, and F not in X, so cant deduce Step 4: A,B+=A,B,C,D,E3.2 Rules About Functional DependenciesExercise:假設有關系R（A,B,C,D,E)和一些FD集，要把這些FD投影到關系S（A,B）上。根據(jù)下面給出的R中的FD集合，求出在S中屬性A,B的閉包。a) AB DE, C E, D C和E A.b) A D, B

37、D E, AC E和DE B.c) AB D, AC E, BC D, D A和E B.d) A B, B C, C D, D E和E A.a) A,B+=A,B,C,D,E;b) A,B+=A,B,D,E;c) A,B+=A,B,D;d) A,B+=A,B,C,D,E;3.2 Rules About Functional Dependencies4. Computing the closure of AttributesClosures and Keys 閉包和鍵閉包和鍵 Notice that U+(U=A1,A2,An) is the set of all attributes of a

38、 relation and only if U is a super key for the relation. For only then does U functionally determine all the other attributes. We can test if U is a key for a relation by checking first that U+ is all attributes, and then checking that, for no set X formed by removing one attribute from U, is X+ the

39、 set of all attributes. 注意當且僅當U是關系的超鍵時，U+才是這個關系的所有屬性的集合。只有這樣，U才能函數(shù)決定所有其他的屬性。如果要驗證U是否是一個關系的鍵，可以先檢查U+是否包含了該關系的全部屬性，然后再檢查不存在從U中移出一個屬性后的集合X，使得X+包含關系的所有屬性。3.2 Rules About Functional Dependencies7. Closure Sets of Functional Dependencies 函數(shù)依賴的閉包集合 Sometimes we have a choice of which FDs we use to represen

40、t the full set of FDs for a relation. If we are given a set of FDs F(such as the FDs that hold in a given relation), then any set of FDs equivalent to F is said to be a basis for F. To avoid some of the explosion of possible bases, we shall limit ourselves to considering only bases whose FDs have si

41、ngleton right sides. If we have any basis, we can apply the splitting rule to make the right sides be singletons. A minimal basis for a relation is a basis B that satisfies three conditions: （1）All the FDs in B have singleton right sides. B中所有FD的右邊均為單一屬性。 （2）If any FD is removed from B, the result i

42、s no longer a basis. 從B中刪除任何一個FD后，該集合不再是基本集。 （3）If for any FD in B we remove one or more attributes from the left side of F, the result is no longer a basis. 對于B中任何一個FD，如果從其左邊刪除一個或多個屬性，B將不再是基本集。3.2 Rules About Functional DependenciesQuestion:In R(U,F), U=A,B,C,D, F=AB, BCD, AD, judge F is a minimal basis or not ?步驟1：先將F中所有FD的右邊變成單一屬性。即B CD分解為B C和B D步驟2：從F中刪除逐個刪除FD后，看會不會影響F集合。 若刪除A B后，通過剩余FD集無法推導出A B，所以不能刪除。 若刪除B C后，通過剩余FD集也無法推導出B C，所以不能刪除。 若刪除B D后，通過剩余FD集也無法推導出B D，所以不能刪除。 若刪除A D后，通過剩余FD集中A B，而B D，可以推導出A D，所以可以刪除。步驟3：所以F不是關系R的最小基本集。7. Closure Sets o