数据库第七讲lecture

1、Now we have learned:u ConceptualME-Rdiagramu LogicalMrelationalschemau But,Wesaythatrelationalschemamustbeinanappropriatenormalform.In fact:u We want to generate a set of relation schemas that allows us to store information withoutunnecessary redundancy, and to retrieveinformation easily.u Three pro

2、blems of database:u deletion anomaly, insertion anomalyu Data redundancyu Normal Form: relational ms engineeringstandataion: 1NF,2NF,3NF,BCNF,4NFexample根据下面的E-R图,设计教学管理关系数据库模型解一：SCT（sno,cno,tno,sname,grade,cname,tname）解法一问题分析：u 冗余度高u 修改问题u 删除问题u 产生问题的：属性间约束关系(即数据间的依赖关系)太强解二：students（sno，sname）course

3、s （cno，tno，cname）teachers（tno，cno, tname）enrolls （sno，cno，grade）解三：u Students（SNO，Sname）Courses （CNO，Cname）Teachers（TNO, Tname）Enrolls （SNO，CNO，Grade）Teaching（TNO，CNO）u 分解后,解二和解三中的冗余和异常现象基本消除了,但这两个模式是否是最佳?v 什么样的关系模式是最优的,标准是什么,如何实施,都是本章要讨论的问题.v 本章就是研究如何设计好的关系模式,以消除存储冗余和异常问题.Relational Database Design

4、Chapter 8:Relational Database Designu Features of Good Relational Designu Atomic Domains and First Normal Formu Decomposition Using Functional Dependenciesu Functional Dependency Theoryu Algorithms for Functional Dependenciesu Decomposition Using Multivalued Dependenciesu More Normal Formu Database-

5、Design Processu Ming Temporal Data8.1 features of good relational designsDesign alternativeLarger schemasorsmaller schemas?Larger schemas: Combine Schemas?u Suppose we combine instructor and departmentinto instdeptl instructor(ID,name,dept_name,salary)l Department(dept_name, building, budget)u Resul

6、t is possible repetition of informationQuestion: are there any problem in store redundancy,updation, insertionand deletion?What About Smaller Schemas?u Suppose we had started with inst_dept.Howwould we know to split up (decompose) it intoinstructorand department?l Inst_dept(ID,name,salary,dept_name,

7、building,b udget)Functional dependencyu Functional dependencyu Write a rule “if there were a schema (dept_name, building, budget), then dept_name would be a candidate key”u Denote as a functional dependency:dept_name ® building, budget解释：当dept_name确定后，building和budget就被唯一确定.Example of functional

8、 dependencyu 现实世界的已知事实(语义)告诉我们：l 一个系有若干学生，但一个学生只属于一个系l 一个系只有一个系l 一个学生可以选修多门课程，每门课程有若干学生选 修l 每个学生学习每一门课程有一个成绩根据已知事实，得到属性组:U(sno,cname,sdept,mname,grade)上的一组函数依赖F?example1根据已知事实，得到属性组U上的一组函数依赖F：FSnoSdept,SdeptMname,(Sno,Cname)GradeSnoCnameGradeSdeptMnameExample 2u 如果仅仅考虑函数依赖这一种数据依赖，可以得到一个描述学生的关系模式u St

9、udent(U,F),右边是关系模式Student的一个实例数据表u 该关系模式有无问题？Delete,insert,update,storeredundancy.Example 2结论：n Student关系模式不是一个好的模式。n “好”的模式：发生异常、删除异常、更新异常，数据冗余应尽可能少：由存在于模式中的某些数据依赖引起的解决方法：通过分解关系模式来消除其中不合适的数据依赖分解关系模式u 分解的目的在于用几个的关系,如:导致异常的关系来代替原来u 将关系模式Student<U,F>分成三个关系模式:S（Sno，Sdept，SnoSdept）;SC（Sno，Cno，Grad

10、e，（Sno，Cno）Grade）;DEPT（Sdept，Mname，SdeptMname）分解后实例表如下：这三个模式都发生异常、删除异常的毛病，数据的冗余也得到了。问题：u 一个关系被分解为三个关系，是否将问题变得复杂化了？l 但只有这样，才能解决异常、删除异常以及数据冗余问题。u 目前业界普遍采用模式分解的方法来解决数据冗余问题。异常、删除异常和u 关系的增多会带来对操作方面的考虑也要增多，但至少这解决了 三个问题。u 为了有效的分解结果的规模，使得分解所得的关系模式不至于过多，有不少计算机科学工作者对此进行了很多新方法研究。模式分解u 目前业界普遍采用模式分解的方法来解决异常、删除异常

11、、修改或更新异常和数据冗余问题u 一个模式的函数依赖会有哪些不好的性质，如何改造一个不好的模式，是规范化理论讨论的内容What About Smaller Schemas?u Write a rule “if there were a schema (dept_name,building, budget), then deptname would be acandidate key”u Denote as a functional dependency:dept name ® building, budget解释：当dept_name确定后，building和budget就被唯一确定

12、.u In inst_dept, because dept_name is not acandidate key, the building and budget of adepartment may have to be repeated.l This indicates the need to decompose instdeptWhat About Smaller Schemas?u Not all decompositions are good. decomposeSuppose weemployee(ID, name, street, city, salary)intoemploye

13、e1 (ID, name)employee2 (name, street, city, salary)u The next slide shows how we lose information -we cannot reconstruct the original employeerelation - and so, this is a lossy decomposition.A Lossy DecompositionExample of Lossless-Join Decompositionu Lossless join decompositionu Decomposition of R

14、= (A, B, C)R1 = (A, B)R2 = (B, C)rÕA,B(r)ÕB,C(r)Õ(r)Õ(r)ABABCa1Ab2BBC1 A2 BABa1b2ABCa1Ab2B8.2 atomic domains and first normal formatomic domainsu Domain is atomic if its elements are considered to be indivisible unitsl Examples of non-atomic domains: Address: (street, city, state

15、, zip.) Identification numbers like CS001, EE1127 that can be broken up into parts Suppose that students are given roll numbers which are strings of the form CS0012 or EE1127 If the first two characters are extracted to find the department, the domain of roll numbers is not atomic. Doing so is a bad

16、 idea: leads to encoding of information in application program rather than in the database.First Normal Formu A relational schema R is in first normal form if the domains of all attributes of R are atomicGoal Devise a Theory for the Followingu Decide whether a particular relation R is in “good” form

17、.u In the case that a relation R is not in “good” form, decompose it into a set of relations R1, R2,., Rn such thatl each relation is in good forml the decomposition is a lossless-join decompositionu Our theory is based on:l functional dependenciesl multivalued dependencies8.3 decomposition using fu

18、nctional dependenciesFunctional Dependenciesu Constraints on the set of legal relations.u Require that the value for a certain set of attributes determines uniquely the value for another set of attributes.u A functional dependency is a generalization ofthe notion of a key.Notesu In general , we use

19、Greek letters for sets oflike aattributes,u r(R), r means a relation schema,R means allattributes of r.u Example:l student(sid, name, age, grade)l r=studentl R=sid, name, age, gradel a=sid, name or .Functional Dependenciesu Let R be a relation schemaa Í RÍ Randu The functional dependencya

20、® bholds on R if and only if for any legal relations r(R), whenever any two tuples t1 and t2 of r agree on the attributes a, they also agree on the attributes b. That is,Þt1b = t2 b t1a = t2 aFunctional Dependenciesu Example:Consider r(A,B ) with the followinginstance of r.l On this instan

21、ce, A ® B does NOT hold, but® A does hold.BAB113457Functional Dependenciesu 即：若两个元组在属性集X上一致（各对应属性值相同）则在属性集Y上也应该一致。X称为这个函数依赖的决定属性集Y=f(x)u 例：姓名l 这个函数依赖，只有在该部门没有同名人的条件下成立，否则函数依赖不成立。keyu K is a superkey for relation schema R if and only if K ® Ru K is a candidate key for R if and only ifl

22、 K ® R, andl for no a Ì K, a ® Rkey设K为R<U,F>中的属性或属性组合。F若KU,则K称为R的侯选码(CandidateKey)。若候选码多于一个,则选定其中的一个做为主码v 理解： K为U的一个子集，若K能够函数决定U中的每个属性，并且K的任何真子集都不能函数决定U中的每个属性，则称K为关系R的 一个候选码。v 等价定义： 若关系中的一个属性或属性组能够函数决定整个元组，并且它的任何子集都不能函数决定整个元组，则它被称为该关系 的一个候选码exampleu 关系模式S(Sno,Sdept,Sage)l 学号决定系，

23、学号决定模式S的码，因此属性Sno是码关系u 关系模式SC(Sno,Cno,Grade)l 一个学生可以选多门课，一门课可以有多个人选，一 个学生选了一门课只能有一个成绩，因此属性(Sno,Cno)是关系模式SC的码exampleu 关系模式R(P,W,A)l P：演奏者W：A：听众,某一l 一个演奏者可以演奏多个可被多个演奏者演奏,听众可以欣赏不同演奏者的不同l 关系模式R的码是？l 关系模式R的码为(P，W，A),即All-Key(全码)keyu 主属性与非主属性l 包含在任何一个候选码中的属性,称为主属性l 不包含在任何码中的属性称为非主属性或非码属性u 全码l 整个属性组是码,称为全码

24、（All-key）侯选码，主码，主属性，非主属性主码侯选码44主属性非主属性R的所有属性当R中的码为全码时,侯选码就是主码主属性没有非主属性R的所有属性外部码关系模式 R中属性或属性组XR的码，但X并非是另一个关系模式的码，则称 Xkey）也称外码是R的外部码（Foreign如在SC（Sno，Cno，Grade）中，Sno不是码，但Sno是关系模式S（Sno，Sdept，Sage）的码，则Sno是关系模式SC的外部码u 主码与外部码一起提供了表示关系间的候选码性质u 候选码具有以下两个性质：l (1)标识的唯一性：对于关系R<U,F>中的每一个元组，U中的这个K值确定后，该元组也就

25、相应确定了。l (2)无冗余性：当K是属性组的情况下，K的任何一部分都不能唯一地标识该元组。少一个属性不能唯一地确定整个元组，多一个属性就有冗余。 这就是定义中的完全函数依赖的意义。Trivial Functional Dependenciesu A functional dependency is trivial (平凡的)if it issatisfied by all instances of a relationl Example:4 ID, name ® ID4 name ® namel In general, a ® b is trivial if b

26、 Í a平凡函数依赖与非平凡函数依赖在关系模式r中，对于R的子集a 和 b ，如果a ® b ，但b Ía ，则称a b是非平凡的函数依赖若a ®Ía,则称a ，但是平凡的函数依赖u 例：在关系SC(Sno,Cno,Grade)中，非平凡函数依赖：(Sno,Cno) Grade平凡函数依赖：(Sno,Cno) Sno(Sno,Cno)Cno完全函数依赖与部分函数依赖在r中，如果a ® b ，并且对于a的任何一个真子集a ，都b, 则称b对a完全函数依赖，记作有a Fa若a ® b ，但依赖，记作a全函数依赖于a ，则称b对a

27、部分函数P b 。传递函数依赖在r中，如果a ® b ，(b Í a ) , b a，b ， 则称对a传递函数依赖记为： a传递例: 在关系Std(Sno, Sdept, Mname)中，有：Sno Sdept，Sdept MnameMname传递函数依赖于Sno exampleF(Sno,Cno)Grade是完全函数依赖，P(Sno,Cno)Sdept是部分函数依赖因为SnoSdept成立，且Sno是（Sno，Cno）的真子集52 exampleu StudyInfo(Sno,Sname,Deptname,Depthead,Cname,Grade)l 其中Sno表示学号、

28、Sname表示学生l Ddeptname表示所在系名、Depthead表示系l Cname表示课程名、Grade表示成绩。u 找找该关系模式的码，主属性和非主属性：l 候选码：(Sno,Cname)l 主属性有：Sno,Cnamel 非主属性有：Sname,Deptname,Depthead,53Grade找找该关系模式的部分函数依赖、完全函数依赖 以及传递依赖：ü 部分函数依赖:(Sno,Cname)Sname；9(Sno,Cname)Deptname；(Sno,Cname)Depthead；ü 完全函数依赖：SnoSname； SnoDeptname；SnoDepthe

29、ad；DeptnameDepthead； (Sno,Cname)Grade；(Sno,Cname)(Sname,Deptname,Depthead,Grade)；ü 传递依赖：Depthead (通过Deptname)传递依赖于 Sno .practiceu 设有供货关系模式SCP，该关系包含如下属性：供应商编号SNO，零件编号PNO，供货量QTY，供 应商地址CITY。即：l SCP（SNO，PNO，QTY，CITY）l 语义：供应商和零件之间是多对多关系u 问题；请写出它的各种函数依赖，主码，候选码，主属性，非主属性？Answer:u 侯选码和主码都是(SNO,PNO)u 主属性

30、是SNO,PNOu 非主属性是QTY,CITYu 完全函数依赖(sno,pno)QTY,snocityu 部分函数依赖(sno,pno)citypracticeu 假设有关系模式SC1(Sno,Cno,Grade,Credit),l 其中Sno表示学号，Cno表示课程号，Grade表示成绩，Credit表示该课程的学分。l 学生与课程之间是多对多的关系.u 试找出该关系模式的候选码、主码、主属性、非主属性，并写出一些函数依赖，并指出哪些是完全函数依赖，哪些是部分函数依赖。57 Answer:u 侯选码:l (Sno,Cno),u 主码:l (Sno,Cno)u 主属性: Sno,Cno,非主属

31、性: grade,creditu 完全函数依赖l (Sno,Cno)gradel Cno creditu 部分函数依赖l (Sno,Cno)credit思考u 在关系模式S和SC中：l S(Sno,Sdept,Sage)l C(Cno,Cname)l SC(Sno,Cno,grade)u Sno表示学号，Sdept表示该生所在的系，Sage表示该生的。，Cno表示课程号，grade表示成绩u 请分别找出这三个关系的码；找出关系SC的外码；这三个关系所表达的实体之间存在着何种？它们的这种种完整性？在关系的完整性方面对应于哪59for this part范式 normal formu 范式是符合某

32、一种级别的关系模式的集合u 关系数据库中的关系必须满足一定的要求。满足不同程 度要求的为不同范式u 范式的种类：第一范式(1NF)第二范式(2NF)第三范式(3NF) BC范式(BCNF)第四范式(4NF)第五范式(5NF)u 对于各种范式之间的有u 5NFÌ4NFÌBCNF Ì3NF Ì2NF ÌlNF成立，如图5.2所示。范式 noramal formu 所谓“第几范式”，是表示关系的某一种级别。所以经常称某一关系模式R为第几范式。现在把范式这个概念理解成符合某一种级别的关系模式 的集合，则R为第几范式就可以写成RnNF。u 事实上，在设计数据库时，范式级别也往往被指 定为数据库工程的验收标准。也就是说，数据库 设计者所提交的数据型必须达到用户要求的规范 化程度。63范式 normal formu 一个低一级范式的关系模式，通过模式分解可以