database第3章 第1次课

1、Content3.1 Functional Dependencies 函数依赖3.2 Rules About Functional Dependencies 函数依赖的规则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. 关系的设计理论使人们可以根据少数简单原则来认真检验一个设计并做出改进。这一理论首先能够规定作用在关系上的约束。最常见的约束是“函数依赖”，它泛化了关系中

4、“键”的概念。本章随后介绍如何使用关系设计理论给予的一些简单工具，通过关系的分解过程来改进设计，即用若干关系替代原关系，这些关系的属性集合包含了原关系的所有属性。3.1 Functional Dependencies1. Definition of Functional Dependency 函数依赖的定义 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上的函数依赖是指如果R的两个元组在属性A1,A2,An上一致（即它们对

6、应于这些属性的分量值都相等），那么它们必定在其他属性B1,B2,Bm上也一致。该函数依赖形式地记为A1,A2,An B1,B2,Bm，并称为A1,A2,An函数决定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满足函数依赖f。这是在R上声明了一个约束，而不是仅仅针对R的一个特殊实例。通常，FD的右边可能是单个属

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. 这些属性函数决定关系的所有其他属性。即不存在两个不同的元组，它们具有相同的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的真子集中，没有一个能函数决定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 的任一真子集都是否函数决定其他的属性。 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、话，通常就要指定其中一个为主键。在商业数据库系统中，对主键的选择会影响某些实现问题，例如怎样在磁盘中存储关系。然而，函数依赖理论并未给主键以特殊的角色。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. 一个包含键的属性集就叫做超键，它是键的超集的简写。因此，每个键都是超键。然而，某些超键不是键。注意，每个超键都满足键的第一个条件：它函数决定了关系中所有其他属性。但超键不需要满足第二个条件：最小化。3.1 Fu

16、nctional Dependencies4. Exercise（1）考虑一个关于美国公民的关系，这个关系的属性有：姓名、社会保险号、街道地址、城市、州、邮编、地区代码和电话号码（7位数字）。这个关系有哪些FD？关系的键是什么？（假设一个地区只能用于一个州，一个邮编不能跨越两个地区代码，两个人不能有相同的社会保险号，但可以有相同的地址和电话号码） 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 函数依赖的规则 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 分解/结合规则 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, 这种转化称为分解规则。 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)，这种转化称为组合规则。3.2 Rules About Functional Dependencies2. The Splitting / Combining Rule 分解/结合规则 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（非平凡函数依赖和平凡函数依赖） 如果R是一个在属性集合U上的关系模式，X和Y是U的子集，如果X决定Y，并且Y不属于X，就称X决定Y是非平凡函数依赖。如果Y属于X，就称X决定Y是平凡函数依赖。 例： （学号，姓名） 姓名 平凡函数依赖 学号 姓名 非平凡函数依赖3.2 Rules About Functional

24、 Dependencies3.2 Full / Partial Functional Dependencies（完全函数依赖和部分函数依赖）fp 在R(U)中，如果X决定Y，并且对于X的任何一个真子集X，都有X不能决定Y，那么称Y完全函数依赖X。 如果X决定Y，但不完全函数依赖于X，则称Y对X部分函数依赖。3.2 Rules About Functional Dependencies3.3 Transitive Functional Dependencies （传递函数依赖）t 在R(U)中，如果X决定Y，Y决定Z，并Y不属于 X，Y不决定X，并且对于X的任何一个真子集X，都有X不能决定Y，那

25、么称Y完全函数依赖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集观察，可以发现属性B没有出现在所有FD集的右边，所以键中包括属性B，再从所有FD集找出推导式左边式中包含属性B的集合，有AB，BC，BD，ABC，ABD，BCD，再根据键是最小化的属性集，所以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)，FD: 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)，FD: 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)，FD: 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和函数依赖集合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，FD的集合F。输入示例：UA,B，FAB 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已经在集合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中，不能进行函数依赖，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示例：因为所有函数依赖已经完成推导过程，所以集合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）上。根据下面给出的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才能函数决定所有其他的属性。如果要验证U是否是一个关系的键，可以先检查U+是否包含了该关系的全部属性，然后再检查不存在从U中移出一个属性后的集合X，使得X+包含关系的所有属性。3.2 Rules About Functional Dependencies7. Closure Sets of Functional Dependencies 函数依赖的闭包集合 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