资源目录
压缩包内文档预览:
编号:211097282
类型:共享资源
大小:12.43MB
格式:ZIP
上传时间:2022-05-05
上传人:考****
认证信息
个人认证
武**(实名认证)
山西
IP属地:山西
30
积分
- 关 键 词:
-
数据库系统概念第六版
数据库
系统
概念
第六
配套
课后
习题
答案
- 资源描述:
-
《数据库系统概念第六版》配套课后习题答案,数据库系统概念第六版,数据库,系统,概念,第六,配套,课后,习题,答案
- 内容简介:
-
CHAPTER8Relational Database DesignExercises8.1Suppose that we decompose the schema R = (A, B, C, D, E) into(A, B, C)(A, D, E).Show that this decomposition is a lossless-join decomposition if thefollowing set F of functional dependencies holds:A BCCD EB DE AAnswer: A decomposition R1, R2 is a lossless-join decomposition ifR1 R2R1or R1 R2R2. Let R1=(A, B, C), R2=(A, D, E), and R1 R2= A. Since A is a candidate key (see PracticeExercise 8.6), Therefore R1 R2 R1.8.2List all functional dependencies satisfied by the relation of Figure 8.17.Answer:The nontrivial functional dependencies are: AB andC B, and a dependency they logically imply: AC B. There are19 trivial functional dependencies of the form a b, where b a. CdoesnotfunctionallydetermineAbecausethefirstandthirdtupleshavethe same C but different A values. The same tuples also show B does notfunctionally determine A. Likewise, A does not functionally determineC because the first two tuples have the same A value and different Cvalues. The same tuples also show B does not functionally determine C.8.3Explain how functional dependencies can be used to indicate the fol-lowing:910Chapter 8Relational Database Design A one-to-one relationship set exists between entity sets student andinstructor. A many-to-one relationship set exists between entity sets studentand instructor.Answer: Let Pk(r) denote the primary key attribute of relation r. The functional dependencies Pk(student) Pk (instructor) andPk(instructor) Pk(student) indicate a one-to-one relationshipbecause any two tuples with the same value for student must havethe same value for instructor, and any two tuples agreeing oninstructor must have the same value for student. The functional dependency Pk(student) Pk(instructor) indicates amany-to-one relationship since any student value which is repeatedwill have the same instructor value, but many student values mayhave the same instructor value.8.4UseArmstrongsaxiomstoprovethesoundnessoftheunionrule.(Hint:Usetheaugmentationruletoshowthat,ifab,thenaab.Applytheaugmentation rule again, using a g, and then apply the transitivityrule.)Answer: To prove that:if a b and a g then a bgFollowing the hint, we derive:a bgivenaa abaugmentation rulea abunion of identical setsa ggivenab g baugmentation rulea bgtransitivity rule and set union commutativity8.5Use Armstrongs axioms to prove the soundness of the pseudotransitiv-ity rule.Answer: ProofusingArmstrongsaxiomsofthePseudotransitivityRule:if a b and g b d, then ag d.a bgivenag g baugmentation rule and set union commutativityg b dgivenag dtransitivity rule8.6Compute the closure of the following set F of functional dependenciesfor relation schema R = (A, B, C, D, E).Exercises11A BCCD EB DE AList the candidate keys for R.Answer: Note: It is not reasonable to expect students to enumerate allof F+. Some shorthand representation of the result should be acceptableas long as the nontrivial members of F+are found.Starting with A BC, we can conclude: A B and A C.Since A B and B D, A D(decomposition,transitive)Since A CDandCD E, A E(union,decom-position,transi-tive)Since A A, we have(reflexive)A ABCDE from the above steps(union)Since E A, E ABCDE(transitive)Since CD E, CD ABCDE(transitive)Since B D and BC CD, BC ABCDE(augmentative,transitive)Also, C C, D D, BD D, etc.Therefore, any functional dependency with A, E, BC, or CD on the lefthand side of the arrow is in F+, no matter which other attributes appearin the FD. Allow * to represent any set of attributes in R, then F+isBD B, BD D, C C, D D, BD BD, BD,B B, B BD, and all FDs of the form A a, BC a,CD a, E a where a is any subset of A, B, C, D, E. Thecandidate keys are A, BC, CD, and E.8.7Using the functional dependencies of Practice Exercise 8.6, compute thecanonicalcover Fc.Answer: The given set of FDs F is:-A BCCD EB DE AThe left side of each FD in F is unique. Also none of the attributes inthe left side or right side of any of the FDs is extraneous. Therefore thecanonical cover Fcis equal to F.12Chapter 8Relational Database Design8.8Consider the algorithm in Figure 8.18 to compute a+. Show that thisalgorithm is more efficient than the one presented in Figure 8.8 (Sec-tion 8.4.2) and that it computes a+correctly.Answer: The algorithm is correct because: If Ais added to result then there is a proof that a A. To see this,observe that a a trivially so a is correctly part of result. IfA 6 a is added to result there must be some FD b g such thatA g and b is already a subset of result. (Otherwise f dcountwould be nonzero and the if condition would be false.) A full proofcan be given by induction on the depth of recursion for an executionof addin, but such a proof can be expected only from students witha good mathematical background. If A a+, then Ais eventually added to result. We prove this byinduction on the length of the proof of a Ausing Armstrongsaxioms. First observe that if procedure addin is called with someargument b, all the attributes in b will be added to result. Also if aparticular FDs fdcount becomes 0, all the attributes in its tail willdefinitely be added to result. The base case of the proof,A a A a+, is obviously true because the first call to addinhas the argument a. The inductive hypotheses is that if a Acanbe proved in n steps or less then A result. If there is a proof inn + 1 steps that a A, then the last step was an application ofeither reflexivity, augmentation or transitivity on a fact a bproved in n or fewer steps. If reflexivity or augmentation was usedin the (n + 1)ststep, Amust have been in result by the end of the nthstep itself. Otherwise, by the inductive hypothesis b result.Therefore the dependency used in proving b g, A g willhave f dcount set to 0 by the end of the nthstep. Hence Awill beadded to result.To see that this algorithm is more efficient than the one presented inthe chapter note that we scan each FD once in the main program. Theresulting array appears has size proportional to the size of the givenFDs. The recursive calls to addin result in processing linear in the sizeof appears. Hence the algorithm has time complexity which is linear inthe size of the given FDs. On the other hand, the algorithm given in thetext has quadratic time complexity, as it may perform the loop as manytimes as the number of FDs, in each loop scanning all of them once.8.9Given the database schema R(a,b,c), and a relation r on the schema R,write anSQLquery to test whether the functional dependency b cholds on relation r. Also write anSQLassertion that enforces the func-tional dependency. Assume that no null values are present. (Althoughpart of theSQLstandard, such assertions are not supported by anydatabase implementation currently.)Answer:Exercises13a. The query is given below. Its result is non-empty if and only ifb c does not hold on r.select bfrom rgroup by bhaving count(distinct c) 1b.create assertion b to c check(not exists(select bfrom rgroup by bhaving count(distinct c) 1)8.10Our discussion of lossless-join decomposition implicitly assumed thatattributes on the left-hand side of a functional dependency cannot takeon null values. What could go wrong on decomposition, if this propertyis violated?Answer:The natural join operator is defined in terms of the cartesianproductandtheselectionoperator.Theselectionoperator,givesunknownfor any query on a null value. Thus, the natural join excludes all tupleswith null values on the common attributes from the final result. Thus,the decomposition would be lossy (in a manner different from the usualcase of lossy decomposition), if null values occur in the left-hand side ofthe functional dependency used to decompose the relation. (Null valuesin attributes that occur only in the right-hand side of the functionaldependency do not cause any problems.)8.11In theBCNFdecomposition algorithm, suppose you use a functional de-pendency a b to decompose a relation schema r(a,b,g) into r1(a,b)and r2(a,g).a. What primary and foreign-key constraint do you expect to holdon the decomposed relations?b. Give an example of an inconsistency that can arise due to anerroneous update, if the foreign-key constraint were not enforcedon the decomposed relations above.c. When a relation is decomposed into3NFusing the algorithm inSection 8.5.2, what primary and foreign key dependencies wouldyou expect will hold on the decomposed schema?14Chapter 8Relational Database DesignAnswer:a. a should be a primary key for r1, and a should be the foreign keyfrom r2, referencing r1.b. If the foreign key constraint is not enforced, then a deletion of atuple from r1would not have a corresponding deletion from thereferencing tuples in r2. Instead of deleting a tuple from r, thiswould amount to simply setting the value of a to null in sometuples.c. For every schema ri(ab) added to the schema because of a rulea b,ashouldbemadetheprimarykey.Also,acandidatekeygfor the original relation is located in some newly created relationrk, and is a primary key for that relation.Foreign key constraints are created as follows: for each relationricreated above, if the primary key attributes of rialso occur inany other relationrj, then a foreign key constraint is created fromthose attributes in rj, referencing (the primary key of) ri.8.12Let R1, R2,., Rnbe a decomposition of schema U. Let u(U) be a rela-tion, and let ri= 5RI(u). Show thatu r11 r21 1 rnAnswer: Consider some tuple t in u.Note that ri= 5Ri(u) implies that tRi ri, 1 i n. Thus,tR1 1 tR2 1 . 1 tRn r11 r21 . 1 rnBy the definition of natural join,tR1 1 tR2 1 . 1 tRn = 5a(sb(tR1 tR2 . tRn)where the condition b is satisfied if values of attributes with the samename in a tuple are equal and where a = U. The cartesian productof single tuples generates one tuple. The selection process is satisfiedbecause all attributes with the same name must have the same valuesince they are projections from the same tuple. Finally, the projectionclause removes duplicate attribute names.By the definition of decomposition,U = R1 R2. Rn, which meansthat all attributes of t are in tR1 1 tR2 1 . 1 tRn. That is, t is equalto the result of this join.Since t is any arbitrary tuple in u,u r11 r21 . 1 rn8.13ShowthatthedecompositioninPracticeExercise8.1isnotadependency-preserving decomposition.Answer: The dependency B D is not preserved. F1, the restrictionof F to (A, B, C) is A ABC, A AB, A AC, A BC,Exercises15A B, A C, A A, B B,C C, AB AC, AB ABC,AB BC, AB AB, AB A, AB B, AB C, AC (sameas AB), BC (same as AB), ABC (same as AB). F2, the restriction of F to(C, D, E) is A ADE, A AD, A AE, A DE, A A,A D, A E, D D, E (same as A), AD, AE, DE, ADE (sameas A). (F1 F2)+is easily seen not to contain B D since the onlyFDin F1 F2with B as the left side is B B, a trivialFD. We shall see inPractice Exercise 8.15 that B D is indeed in F+. Thus B D is notpreserved. Note that CD ABCDE is also not preserved.A simpler argument is as follows: F1contains no dependencies with Don the right sideof the arrow. F2contains no dependencieswith B on theleft side of the arrow. Therefore for B D to be preserved there mustbe anFDB a in F+1and a D in F+2(so B D would followby transitivity). Since the intersection of the two schemes is A, a = A.Observe that B Ais not in F+1since B+= BD.8.14Show that it is possible to ensure that a dependency-preserving decom-positioninto3NFisalossless-joindecompositionbyguaranteeingthatatleast one schema contains a candidate key for the schema being decom-posed.(Hint:Showthatthe joinof alltheprojectionsontotheschemas ofthe decomposition cannot have more tuples than the original relation.)Answer: Let F beasetoffunctionaldependenciesthatholdonaschemaR. Let s = R1, R2,., Rn be a dependency-preserving3NFdecompo-sition of R. Let X be a candidate key for R.Consider a legal instance r of R. Let j = 5X(r) 1 5R1(r) 1 5R2(r). 15Rn(r). We want to prove that r = j.We claim that if t1and t2are two tuples in j such that t1X = t2X, thent1= t2. To prove this claim, we use the following inductive argument Let F= F1 F2 . Fn, where each Fiis the restriction of F to theschema Riin s. Consider the use of the algorithm given in Figure 8.8 tocompute the closure of X under F. We use induction on the number oftimes that the f or loop in this algorithm is executed. Basis : In the first step of the algorithm, result is assigned to X, andhence given that t1X = t2X, we know that t1result = t2resultis true. Induction Step : Let t1result = t2result be true at the end of thek th execution of the f or loop.Suppose the functional dependency considered in the k + 1 thexecution of the f or loop is b g, and that b result. b resultimplies that t1b = t2b is true. The facts that b g holds forsome attribute set Riin s, and that t1Ri and t2Ri are in 5Ri(r)imply that t1g = t2g is also true. Since g is now added to resultby the algorithm, we know that t1result = t2result is true at theend of the k + 1 th execution of the f or loop.16Chapter 8Relational Database DesignSinces is dependency-preservingand Xisakeyfor R,all attributesin Rare in result when the algorithm terminates. Thus, t1R = t2R is true,that is, t1= t2 as claimed earlier.Our claim implies that the size of 5X(j) is equal to the size of j. Notealso that 5X(j) = 5X(r) = r (since X is a key for R). Thus we haveproved that the size of j equals that of r. Using the result of PracticeExercise 8.12, we know that r j. Hence we conclude that r = j.Note that since X is trivially in3NF, s X is a dependency-preservinglossless-join decomposition into3NF.8.15Give an example of a relation schema Rand set Fof functional depen-dencies such that there are at least three distinct lossless-join decompo-sitions of RintoBCNF.Answer: Given the relation R= (A, B, C, D) the set of functionaldependencies F= A B, C D, B C allows three distinctBCNFdecompositions.R1= (A, B), (C, D), (B, C)is inBCNFas isR2= (A, B), (C, D), (A, C)R2= (A, B), (C, D), (A, C)R3= (B, C), (A, D), (A, B)8.16Let a prime attribute be one that appears in at least one candidate key.Let a and b be sets of attributes such that a b holds, but b adoes not hold. Let A be an attribute that is not in a, is not in b, and forwhich b A holds. We say that A is transitively dependent on a. Wecan restate our definition of3NFas follows: A relation schema R is in3NFwith respect to a set F of functional dependencies if there are nononprime attributes A in R for which A is transitively dependent on akey for R.Show that this new definition is equivalent to the original one.Answer: Suppose R is in3NFaccording to the textbook definition. Weshow that it is in3NFaccording to the definition in the exercise. Let Abea nonprime attribute in R that is transitively dependent on a key a forR. Then there exists b R such that b A, a b, A 6 a, A 6b, and b a does not hold. But then b A violates the textbookdefinition of3NFsince A 6 b implies b Ais nontrivial Since b a does not hold, b is not a superkey Ais not any candidate key, since Ais nonprimeExercises17Now we show that if R is in3NFaccording to the exercise definition, itis in3NFaccording to the textbook definition. Suppose R is not in3NFaccording the the textbook definition. Then there is anFDa b thatfails all three conditions. Thus a b is nontrivial. a is not a superkey for R. Some Ain b a is not in any candidate key.This implies that Ais nonprime and a A. Let g be a candidate keyfor R. Then g a, a g does not hold (since a is not a superkey),A6a, and A6g (since A is nonprime). Thus A is transitivelydependent on g, violating the exercise definition.8.17A functional dependency a b is called a partial dependency if thereis a proper subset g of a such that g b. We say that b is partiallydependent on a. A relation schema R is in second normal form (2NF) ifeach attribute A in R meets one of the following criteria: It appears in a candidate key. It is not partially dependent on a candidate key.Show that every3NFschema is in2NF. (Hint: Show that every partialdependency is a transitive dependency.)Answer: Referring to the definitions in Practice Exercise 8.16, a relationschema R is said to be in3NFif there is no non-prime attribute A in Rfor which Ais transitively dependent on a key for R.We ca
- 温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

人人文库网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。