A first course in database systems(3).ppt

1、3 The Relational Data Model,What are relational data models? How to convert E/R models into relational data models? How to assure(保证) certain form condition by decomposing(分解) relational model?,3.1 Basics of the Relational Model,Relation: A two-dimensional table called a relation.,Movies,3.1 Basics

2、of the Relational Model,Stars-in,3.1.1 Attributes,Attribute(属性): Names for the columns of the relation, describe the meaning of entries in the column below. Such as length of Movies. An attribute have a name. Any two attributes of a relation cant have same name.,3.1.2 Schemas(模式),Relation schema = r

3、elation name and set of attributes. Example: Movies ( title, year, length, filmtype) or Movies ( title: string, year: int, length: int, filmtype: string) Database = collection of relations. Database schema = set of all relation schemas in the database.,3.1.3 Tuples,Tuples(元组): The rows of a relation

4、, other than the header row containing the attributes, are called tuples. There may be no tuple in a relation. A tuple has one component(分量) for each attribute of the relation. How to describe a tuple? Use commas to separate components, and use parentheses(圆括号) to surround the tuple. Example: (Star

5、Wars, 1977, 124, color) We should always use the order in which the attributes were listed in the relation schema.,3.1.3 Tuples,The mapping of tuples and objects: A relation a class A tuple a object A component of a tuple a property of a object The difference of tuples and objects: Objects have iden

6、tities(标识), while tuples have not. A class could have two different objects with the same values in all attributes, but a tuple cant appear more than once in a relation.,3.1.4 Domains,Domains: A domain is an elementary(基本的) type, such as integer, char(n), date, time. Each attribute of a relation is

7、a domain, that is, a particular elementary type. Each component of any tuple must be atomic(原子的). Atomic: Can not be broken into smaller components,3.1.5 Equivalent Representations of a Relation,We can reorder the attributes of a relation, without changing the relation. We can reorder the tuples of

8、a relation, without changing the relation.,3.1.6 Relation Instances,The relationship between schema and tuples: The schema of a relation is relatively static, while the tuples change over time. Relation instances(实例): A set of tuples for a relation is an instance of the relation. The instance of a r

9、elation changes over time. The set of tuples that are in the relation “now” is “current instance(当前实例)”.,3.1 Basics of the Relational Model,Exercises: p64 3.1.1,3.2 From E/R Diagrams to Relational Designs,How to convert an E/R diagram to a relation? Main idea: Conversion from entity sets to relation

10、s Conversion from relationships to relations Handling weak entity sets,3.2.1 From Entity Sets to Relations,Entity set - relation. Attributes - attributes.,Movies (title, year, length, filmType) Stars (name, address) Studios (name, address),3.2.2 From E/R Relationships to Relations,How to convert mul

11、tiway relationships to relations? Convert multiway(多元) relationships to binary(二元) relationships firstly.,How to convert binary relationships to relations? According to multiplicity of the relationship: A many-many relationship R from E1 to E2 Convert R to a relation whose attributes are composed of

12、 the attributes of R and the key attributes of E1 and E2. Example: Enrollment(注册) between Students and Courses Enrollment(Sno, Cno, score),3.2.2 From E/R Relationships to Relations,Movies (title, year, length, filmType) Stars (name, address) Studios (name, address),Stars-in (title, year, starName),3

13、.2.2 From E/R Relationships to Relations,2. A many-one relationship R from E1 to E2 R can be converted to a relation, but not must be. Add the key attributes of E2 to the relation E1. Example: Belong between Departments and Employees,Employees(EmpID, name, . ) Departments(DeptID, name) Belong(EmpID,

14、 DeptID), DeptID,3.2.2 From E/R Relationships to Relations,Movies (title, year, length, filmType) Stars (name, address) Studios (name, address),Stars-in (title, year, starName),Movies (title, year, length, filmType, studiosName),3.2.2 From E/R Relationships to Relations,3. A one-one relationship R f

15、rom E1 to E2 R can be converted to a relation, but usually not. There are two ways: Add the key attributes of E2 to the relation E1. Add the key attributes of E1 to the relation E2. An one-one relationships may be merged into another. Example: Header between Departments and Employees,Employees(EmpID

16、, name, . , leadDept) Departments(DeptID, name),Employees(EmpID, name, . ) Departments(DeptID, name, leaderID),3.2.4 Handling Weak Entity Sets,Conversion from weak entity sets to relations ： Convert weak entity set E to a relation whose attributes are composed of the attributes of E and the key attr

17、ibutes of F. Can not convert R to a relation.,3.2.4 Handling Weak Entity Sets,Studios (name, address) Crews (studioName, number),Crews,number,Unit-of,Studios,name,address,3.2.4 Handling Weak Entity Sets,Contracts (starName, studioName, title, year, salary, signdate),3.3 Converting Subclass structure

18、s to Relations,Subclasses: Three Approaches Object-oriented : One relation per subset of subclasses, with all relevant attributes. Use nulls : One relation; entities have NULL in attributes that dont belong to them. E/R style : One relation for each subclass: Key attribute(s). Attributes of that sub

19、class.,3.3 Converting Subclass structures to Relations,Example:,3.3 Converting Subclass structures to Relations,Object-oriented movies ( title, year, length, FilmType) Murder-Mysteries (title, year, length, FilmType, weapon) Use nulls movies (title, year, length, FilmType, weapon) E/R style movies (

20、 title, year, length, FilmType) Murder-Mysteries (title, year, weapon),convert to relations,A marketing management system Customer (custid, name, prov, city, phone, unit) Product (prodid, factory, type, spec, price, desc) Salesman (empid, idno, name, gender, phone, deptid) Department (deptid, name,

21、headerid) Salesorder (orderno, signdate, empid, custid) Salesitem (orderno, lineno, prodid, singlecost, quantity),3.2 From E/R Diagrams to Relational Designs,Exercises: P75 3.2.1 3.2.2,3.4 Functional Dependencies(函数依赖),用形式化方法研究一个关系中各属性之间的语义关系。 Main idea: Meaning of FDs Keys Superkeys Find keys from

22、E/R diagrams,3.4.1 Definition of Functional Dependency,X - A is an assertion(断言) about a relation R that whenever two tuples of R agree on all the attributes of X, then they must also agree on the attribute A. Say “X - A holds(成立) in R.” Say “X functionally determine A. ”,3.4.1 Definition of Functio

23、nal Dependency,若关系R的任意两个元组在属性A1、A2、An上的值一致(即有相同分量值)，则这两个元组在属性B上的值必也一致，称属性A1A2An函数决定B，或称属性B函数依赖于A1A2An。 记为：A1A2An B Example：In Students(sno, sname, gender) sno sname sno gender consider：sname gender ？,3.4.1 Definition of Functional Dependency,Let us consider the relation students(sno, sname, cno, sco

24、re) sno sname ？ and：sno score ？ or： sno cno score ?,3.4.1 Definition of Functional Dependency,Corollary(推论) 1: A1A2An B1 A1A2An B2 A1A2An Bm iff ( if and only if ) A1A2An B1B2Bm Corollary 2: A A,3.4.1 Definition of Functional Dependency,Example 3.12：Let us consider the relation Movies(title, year, l

25、ength, filmType, studioName, starName),title year length filmType studioName consider：title year starName ?,3.4.1 Definition of Functional Dependency,Consider the functional dependencies in relation student ( stuid, name, gender, depid, dorm, courseid, coursename, score ).,stuid courseid score stuid

26、 name gender depid dorm depid dorm , courseid coursename,如何分析一个具体关系中的函数依赖： 根据属性之间的语义关系分析函数依赖。 应考虑所有可能的属性组合。 尽可能使函数依赖式的左面最小化，而右面最大化。 注意：函数依赖是针对关系模式，而不是针对特定实例，故只从关系实例不能确切断定函数依赖。,stuid name gender ？ name gender ? stuid score ? stuid courseid ? stuid courseid score ?,3.4.1 Definition of Functional Depen

27、dency,Three cases of asserting functional dependencies: If two tuples have the same values in their A components, and they also have the same values in their B components, then A B holds. If two tuples have the same values in their A components, but they have not the same values in their B component

28、s, then A B does not hold. If any two tuples cant have the same values in their A components, then A B holds.,3.4.1 Definition of Functional Dependency,常见术语： 部分函数依赖：若X Y，且存在X的真子集X， X Y，则称Y对X部分函数依赖。 完全函数依赖：若X Y，且Y对X不是部分函数依赖，则称Y对X是完全函数依赖。 传递函数依赖：若X Y，Y Z，且Y X不成立，则称Z对X是传递函数依赖。,3.4.2 Keys of Relations,K

29、ey: We say a set of one or more attributes A1, A2, ., An is a key for a relation R if: A1, A2, ., An functionally determine all other attributes of the relation R. (superkey) No proper subset(真子集) of A1, A2, ., An can functionally determine all other attributes of R. (minimal),3.4.2 Keys of Relation

30、s,Key of the relation Movies ( title, year, length, filmtype, studioName, starName ): title, year ? title, year, starName ? If AB holds in R(A,B,C), the keys of R?,3.4.2 Keys of Relations,Primary key: Sometimes a relation has more than one key, and one of the keys is designated as the primary key. C

31、andidate(候选) key: All keys of a relation.,3.4.3 Superkey(超键),Superkeys: Superset(超集) of a key. A set of attributes that contains a key. Those attributes functionally determine all other attributes of the relation. The relationship between keys and superkeys: Keys are superkeys. title, year, starName

32、 Some superkeys are not keys. title, year, length, starName,3.4.4 Discovering Keys for Relations,How to express a key of a relation schema? Underline the attributes of the primary key How to determine the key for the relation coming from an entity set? The key for the relation is the key attributes

33、of this entity set. Example: Movies ( title, year, length, fileType) Stars ( name, address) Studios ( name, address),3.4.4 Discovering Keys for Relations,How to determine the key for the relation R coming from a binary relationship? According to multiplicity(多重性) of the relationship, there are three

34、 cases: many-many: the keys of both connected entity sets are the key attributes for R. many-one from E1 to E2: the key attributes of E1 are key attributes of R, but those of E2 are not. one-one: the key attributes for either of the connected entity sets are key attributes of R. Example: StarsIn ( t

35、itle, year, starName) Owns ( title, year, studioName) can be merged in the relation Movies: Movies ( title, year, length, fileType, studioName),Customer (custid, name, prov, city,phone, unit) Product (prodid, factory, type, spec, price, desc) Salesman (empid, idno, name, gender, phone, deptid) Depar

36、tment (deptid, name, headerid) Salesorder (orderno, signdate, empid, custid) Salesitem (orderno, lineno, prodid, singlecost, quantity),3.5 Rules About Functional Dependencies,What are rules about functional dependencies? Why we need them? Suppose we are told of a set of dependencies that a relation

37、satisfies, we can deduce(演绎出) other dependencies by rules about functional dependencies. The ability to discover additional dependencies is essential when we discuss the design of good relation schemas.,3.5 Rules About Functional Dependencies,Example 3.17: p90 If we are told that a relation R(A, B,

38、C) satisfies the functional dependencies AB and BC, then we can deduce(推论) that R also satisfies the dependency AC. Proof: Set (a,b1,c1) and (a,b2,c2) as the tuples of R. Since AB, then b1=b2 Since BC, then c1=c2 So: AC is hold in R.,3.5 Rules About Functional Dependencies,Some important rules about

39、 functional dependencies: The splitting/combining rule(分解/合并规则) The trivial-dependency rule(平凡依赖规则) The transitive rule(传递规则) Armstrongs axioms (公理),3.5 Rules About Functional Dependencies,两个函数依赖集之间的关系： 设T是关系R上的函数依赖集，若对R的所有实例，函数依赖 X Y 都成立，则称T“逻辑蕴含” X Y。( X Y 可由T推导出来 ) 设S是关系R上的另一函数依赖集，若对R的所有实例，S中的所有函

40、数依赖均成立，则称函数依赖集S“蕴含于”函数依赖集T。( S可由T推导出来 ) 若函数依赖集S“蕴含于” T，同时T“蕴含于”S，则函数依赖集S“等价于”函数依赖集T。,3.5 Rules About Functional Dependencies,The relationship between two sets of functional dependencies: If every relation instance that satisfies all the dependencies in a set of functional dependencies T also satisfi

41、es all the dependencies in a set of functional dependencies S, we say that S follows from(蕴含于) T. If S follows from T and T follows from S, then S and T are equivalent(等价).,3.5 Rules About Functional Dependencies,蕴含和等价关系的作用： 可用等价的更简单的函数依赖集代替复杂的函数依赖集。 可在一个函数依赖集S中增加蕴含其中的其它函数依赖。 可判断一个函数依赖是否蕴含于已知的函数依赖集。

42、,3.5.1 The Splitting/Combining Rule,Splitting/Combining Rule:,There is no splitting rule or combining rule for left sides.,3.5.1 The Splitting/Combining Rule,Example：In Movies title year length filmType studioName is equivalent to： title year length title year fileType title year studioName But，sno

43、cno score can not split the the left side into： sno score cno score,3.5.2 Trivial Dependencies,Trivial dependency(平凡依赖): A functional dependency A1A2.AnB is said to be trivial if B is one of the As. Every trivial dependency holds in every relation. A dependency A1A2.AnB1B2.Bm is Trivial if the Bs ar

44、e a subset of the As. Nontrivial if at least one of the Bs is not among the As. Completely nontrivial(完全非平凡) if none of the Bs is also one of the As. Example: title yearyear length is nontrivial title yearlength is completely nontrivial,3.5.2 Trivial Dependencies,The trivial-dependency rule: We can

45、remove from the right side of a functional dependency those attributes that appear on the left. That is: The functional dependency A1A2.AnB1B2.Bm is equivalent to A1A2.AnC1C2.Ck, where the Cs are all those Bs that are not also As.,3.5.3 Computing the Closure of Attributes,属性的闭包 设S是关系R上的函数依赖集，A=A1, A

46、2, , An是R上的属性集， 则属性集A可函数决定的最大属性集合称做A的闭包，记做：A+ ( 或A+s ) 。 这个集合如何计算？ 这种计算有何用途？,3.5.3 Computing the Closure of Attributes,The closure(闭包) of attributes: Suppose A1,A2,.,An is a set of attributes and S is a set of functional dependencies. The closure of A1,A2,.,An under the dependencies in S is the set

47、of attributes B such that every relation that satisfies all the dependencies in set S also satisfies A1A2.AnB. That is, A1A2.AnB follows from the dependencies of S. We denote(表示) the closure of a set of attributes A1,A2,.,An by A1,A2,.,An+. A1,A2,.,An are always in A1,A2,.,An+. If A1A2.AnX, then XB.

48、,3.5.3 Computing the Closure of Attributes,计算属性的闭包： 对于给定的函数依赖集S，和属性集A=A1,A2,An 设属性集X是A的闭包，将X初始化为A1,A2,An，即为闭包的最小集合。 对于S中的每个函数依赖式：B1B2Bm C。如果B1, B2, , Bm都在X中，而C不在X中，则把C加入X中。 重复第2步，直到遍历完S中所有函数依赖，而没有新属性能加入到X中。 属性集X即为属性集A在函数依赖集S下的闭包A+。,3.5.3 Computing the Closure of Attributes,Example 3.19: p93 Let us c

49、onsider a relation with schema R(A,B,C,D,E,F) and a set of functional dependencies S: ABC, BCAD, DE, CFB Please computer A, B+. Solution： First X(1)=A,B Since AB C，so X(2)=A,B,C Since BC AD，so X(3)=A,B,C,D Since D E，so X(4)=A,B,C,D,E No more dependency can be used, thus A，B+ =A,B,C,D,E,3.5.3 Computi

50、ng the Closure of Attributes,Why we compute the closure of attributes? Suppose we have a relation R with a set of dependencies S, and a dependency A1A2.AnB. We can test whether the dependency follows from the dependencies of S. Computer A1,A2,.,An+ using the set of dependencies S. If B is in A1,A2,.

51、,An+ , then A1A2.AnB follows from S. If B is not in A1,A2,.,An+ , then A1A2.AnB does not follow from S. A1A2.AnB1B2.Bm follows from set of dependencies S iff All of B1, B2, . , Bm are in A1,A2,.,An+ .,3.5.3 Computing the Closure of Attributes,Example 3.20: Let us consider a relation with schema R(A,

52、B,C,D,E,F) and a set of functional dependencies S: ABC, BCAD, DE, CFB Please test whether ABD and DA follow from the dependencies of S?,3.5.3 Computing the Closure of Attributes,Closures and keys: A1,A2,.,An+ is the set of all attributes if and only if A1, A2, . , An is a superkey for the relation.,

53、3.5.5 The Transitive Rule,The transitive(传递) rule: Cascade(级联) two functional dependencies. If A1A2.AnB1B2.Bm and B1B2.BmC1C2.Ck hold in relation R, then A1A2.AnC1C2.Ck also holds in R. Example: MovieStudio ( title, year, length, fileType, studioName, studioAddr) title, year studioName studioName st

54、udioAddr then title, year studioAddr,3.5.6 Closing Sets of Functional Dependencies,We can derive a new set of dependencies from a set of given dependencies using rules about functional dependencies. Any set of given dependencies from which we can infer all the dependencies for a relation will be cal

55、led a basis(基) for that relation. A relation may have several bases. If no proper subset of the dependencies in a basis can also derive the complete set of dependencies, then we say the basis is minimal. A relation may have several minimal bases.,3.5.6 Closing Sets of Functional Dependencies,Example

56、 3.22: p98 Consider a relation with schema R(A,B,C) and a set of dependencies FD: A B, A C, B A, B C, C A, C B Then the minimal bases are: AB, BA, BC, CB, AB, BC, CA and so on.,3.5.6 Closing Sets of Functional Dependencies,Armstrongs axioms: Reflexivity(自反律). If B1,B2,BmA1,A2,An, then A1A2AnB1B2Bm.

57、( trivial ) Augmentation(增长律). If A1A2AnB1B2Bm, then A1A2AnC1C2CkB1B2BmC1C2Ck for any set of attributes C1,C2,Ck. Transitivity(传递律). If A1A2AnB1B2Bm and B1B2BmC1C2Ck, then A1A2AnC1C2Ck.,3.5.7 Projecting Functional Dependencies,Suppose a relation has schema R(U) and a set of dependencies F. If R is d

58、ecomposed into S(U1) and T(U2), then we need find what functional dependencies still hold in S.,3.5.7 Projecting Functional Dependencies,Algorithm: Consider each set of attributes X that is contained in the set of attributes of S. Compute X+. Then for each attribute B such that B is an attribute of

59、S, B is in X+, and B is not in X, the functional dependency XB holds in S.,3.5.7 Projecting Functional Dependencies,Example : Let R have schema R(A,B,C,D), and suppose the functional dependencies AB and BC are given for R. Let S(A,C) be one of the relation in a decomposition of R. Please compute the dependencies that hold in S. S