Solutions to rcises.doc

Introduction to Database SystemSolutions to ExercisesLi Ping28Chapter 2 The Entity-Relationship Data ModelExercise 2.1.1: Let us design a database for a bank, including information about customers and their accounts. Information about a customer includes their name, address, phone, and Social Security number. Accounts have numbers, types (e.g., savings, checking) and balances. We also need to record the customer(s) who own an account. Draw the E/R diagram for this database. Be sure to include arrows where appropriate, to indicate the multiplicity of a relationship. P.36Solution:Exercise 2.1.6: Suppose we wish to keep a genealogy. We shall have one entity set, People. The information we wish to record about persons includes their name(an attribute) and the following relationships: mother, father, and children. Given an E/R diagram involving the People entity set and all the relationships in which it is involved. Include relationships for mother, father, and children. Do not forget to indicate roles when an entity set is used more than once in a relationship.Solution:PeoplechildrenOf FemalechildrenOf MalechildrenOf childrenmotherfatherchildrenchildrenparentsExercise 2.2.1: In Fig. 2.14 is an E/R diagram for a bank database involving customers and accounts. Since customers may have several accounts, and accounts may be held joint by several customers, we associate with each customer an “account set”, and accounts are members of one or more account sets. Assuming the meaning of the various relationships and attributes are as expected given their names, criticize the design. What design rules are violated? Why? What modifications would you suggest? P.44Solution:1. The Addresses entity set is nothing but a single address, so we would prefer to make address an attribute of Customers. Were the bank to record several addresses for a customer, then it might make sense to have an Addresses entity set and make Lives-at a many-many relationship. 2. The Acct-Sets entity set is useless. Each customer has a unique account set containing his or her accounts. However, relating customers directly to their accounts in a many-many relationship conveys the same information and eliminates the account-set concept altogether. Exercise 2.2.2: Under what circumstances (regarding the unseen attributes of Studios and Presidents) would you recommend combining the two entity sets and relationship in Fig. 2.3 into a single entity set and attributes?Solution:When there is exactly one Studios and exactly one President, we can combine the two entity sets into a single entity set and the president can be one attribute of entity set Studios.Exercise 2.3.1: For your E/R diagrams of:a) Exercise 2.1.1.(i) Select and specify keys, and (ii) Indicate appropriate referential integrity constraints.P.53Solution:Keys ssNo and number are appropriate for Customers and Accounts, respectively. Also, we think it does not make sense for an account to be related to zero customers, so we should round the edge connecting Owns to Customers. It does not seem inappropriate to have a customer with 0 accounts; they might be a borrower, for example, so we put no constraint on the connection from Owns to Accounts. Here is the E/R diagram, showing underlined keys and the numerocity constraint.Exercise 2.4.1: One way to represent students and the grades they get in courses is to use entity sets corresponding to students, to courses, and to “enrollments”, Enrollment entities form a “connecting” entity set between students and courses and can be used to represent not only the fact that a student is taking a certain course, but the grade of the student in the course. Draw an E/R diagram for this situation, indicating weak entity sets and the keys for the entity sets. Is the grade part of the key for enrollment? P.58Solution:Here is the E/R diagram. We have omitted attributes other than our choice for the key attributes of Students and Courses. Also omitted are names for the relationships. Attribute grade is not part of the key for Enrollments. The key for Enrollements is studID from Students and dept and number from Courses.Chapter 3 The Relational Data ModelExercise 3.1.1: In Fig. 3.3 are instances of two relations that might constitute part of a banking database. Indicate the following: P.64Solution:a) The attribute of each relation.Accounts: acctNo, type, balanceCustomers: firstName, lastName, idNo, accountb) The tuples of each relation.Accounts: (12345, savings, 12000), (23456, checking, 1000), (34567, savings, 25)Customers: (Robbie, Banks, 901-222, 12345), (Lena, Hand, 805-333, 12345), (Lena, Hand, 805-333, 23456)c) The components of one tuple from each relations.The first of the three tuples has three components 12345, savings, and 12000 for attributes acctNo, type, and balance of relation Accounts.The first of the three tuples has four components Robbie, Banks, 901-222, and 12345 for attributes firstName, lastName, idNo, and account of relation Customers.d) The relation schema for each relation.The relation schema for Accounts: Accounts(acctNo, type, balance)The relation schema for Customers: Customers(firstName, lastName, idNo, account)e) The database schema.The database schema is Accounts(acctNo, type, balance), and Customers(firstName, lastName, idNo, account)f) A suitable domain for each attribute.For Accounts: acctNostring;typestring;balancerealFor Customers:firstNamestring;lastNamestring;idNostring;accountstringg) Another equivalent way to present each relation.For Accounts:acctNoTypeBalance12345Savings1200034567savings2523456checking1000For Customers:firstNamelastNameidNoaccountRobbieBanks901-22212345LenaHand805-33323456LenaHand805-33312345Exercise 3.1.2: How many different ways (considering orders of tuples and attributes) are there to represent a relation instance if that instance has three attributes and three tuples.Solution:tuples: 3!=6columns: 3!=6number of presentation is 6*6=36Exercise 3.2.1: Convert the E/R diagram of Fig. 3.11 to a relational database schema. P.75Solution:Customers(ssNo, name, addr, phone)Flights(number, day, aircraft)Bookings(ssNo, number, day, row, seat)Being a weak entity set, Bookings relation has the keys for Customers and Flights and Bookings own attributes.Exercise 3.2.3: The E/R diagram of Fig. 3.12 represents ships. Ships are said to be sisters if they were designed from the same plans. Convert this diagram to a relational database schema.Solution:Ships(name, yearLaunched)SisterOf(name, sister_name)Exercise 3.3.1: convert the diagram of Fig. 3.14 to relational database schema, using each of the following approaches: P.80a) The straight-E/R method.b) The object-oriented method.c) The nulls method.Solution: Since Courses is weak, its key is number and the name of its department. We do not have a relation for GivenBy. In part (a), there is a relation for Courses and a relation for LabCourses that has only the key and the computer-allocation attribute. It looks like: Depts(name, chair) Courses(number, deptName, room) LabCourses(number, deptName, allocation)For part (b), LabCourses gets all the attributes of Courses, as: Depts(name, chair) Courses(number, deptName, room) LabCourses(number, deptName, room, allocation)And for (c), Courses and LabCourses are combined, as: Depts(name, chair) Courses(number, deptName, room, allocation)Exercise 3.4.2: Consider a relation representing the present position of molecules in a closed container. The attributes are an ID for the molecule, the x, y, and z coordinates of the molecule, and its velocity in the x, y, and z dimensions. What FDs would you expect to hold? What are the keys? P.89Solution:Surely ID is a key by itself. However, we think that the attributes x, y, and z together form another key. The reason is that at no time can two molecules occupy the same point.ID x y zID vx, vy, vzx y z vx, vy, vzExercise 3.4.4: In your database schema constructed for Exercise 3.2.1, indicate the keys you would expect for each relation.Solution:The key attributes are indicated by capitalization in the schema below: Customers(SSNO, name, address, phone) Flights(NUMBER, DAY, aircraft) Bookings(SSNO, NUMBER, DAY, row, seat)Exercise 3.5.1: consider a relation with schema R(A, B, C, D) and FDs AB C, C D, and D A. P.100a) What are all the nontrivial FDs that follow from the given FDs? You should restrict yourself to FDs with single attributes on the right side.b) What are all the keys of R?c) What are all the superkey for R that are not keys?Solution:For (a), We could try inference rules to deduce new dependencies until we are satisfied we have them all. A more systematic way is to consider the closures of all 15 nonempty sets of attributes. For the single attributes we have A+ = A, B+ = B, C+ = ACD, and D+ = AD. Thus, the only new dependency we get with a single attribute on the left is C-A. Now consider pairs of attributes: AB+ = ABCD, so we get new dependency AB-D. AC+ = ACD, and AC-D is nontrivial. AD+ = AD, so nothing new. BC+ = ABCD, so we get BC-A, and BC-D. BD+ = ABCD, giving us BD-A and BD-C. CD+ = ACD, giving CD-A. For the triples of attributes, ACD+ = ACD, but the closures of the other sets are each ABCD. Thus, we get new dependencies ABC-D, ABD-C, and BCD-A. Since ABCD+ = ABCD, we get no new dependencies. The collection of 11 new dependencies mentioned above is: C-A, AB-D, AC-D, BC-A, BC-D, BD-A, BD-C, CD-A, ABC-D, ABD-C, and BCD-A. For (b), From the analysis of closures above, we find that AB, BC, and BD are keys. All other sets either do not have ABCD as the closure or contain one of these three sets.For (c), The superkeys are all those that contain one of those three keys. That is, a superkey that is not a key must contain B and more than one of A, C, and D. Thus, the (proper) superkeys are ABC, ABD, BCD, and ABCD.Exercise 3.6.1: For each of the following relation schemas and sets of FDs:a) R(A, B, C, D) with FDs AB C, C D, and D A. b) R(A, B, C, D) with FDs B C, and B D.do the following:i) Indicate all the BCNF violations. Do not forget to consider FDs that are not in the given set, but follow from them. However, it is not necessary to give violations that have more than one attribute on the attribute on the right side.ii) Decompose the relations, as necessary, into collections of relations that are in BCNF.iii) Indicate all the 3NF violations.iv) decompose the relations, as necessary, into collections of relations that are in 3NF.a) Solution:In the solution to Exercise 3.5.1 we found that there are 14 nontrivial dependencies, including the three given ones and 11 derived dependencies. These are: C-A, C-D, D-A, AB-D, AB- C, AC-D, BC-A, BC-D, BD-A, BD-C, CD-A, ABC-D, ABD-C, and BCD-A. We also learned that the three keys were AB, BC, and BD. Thus, any dependency above that does not have one of these pairs on the left is a BCNF violation. These are: C-A, C-D, D-A, AC-D, and CD-A. One choice is to decompose using C-D. That gives us ABC and CD as decomposed relations. CD is surely in BCNF, since any two-attribute relation is. ABC is not in BCNF, since AB and BC are its only keys, but C-A is a dependency that holds in ABCD and therefore holds in ABC. We must further decompose ABC into AC and BC. Thus, the three relations of the decomposition are AC, BC, and CD. Since all attributes are in at least one key of ABCD, that relation is already in 3NF, and no decomposition is necessary. b) Solution:The only key is AB. Thus, B-C and B-D are BCNF violations. These are the only nontrivial BCNF violations. The reason is that the only nontrivial derived dependencies must have A and B on the left, and therefore contain a key. One possible BCNF decomposition is AB and BCD. AB is the only key for AB, and B is the only key for BCD. Since there is only one key for ABCD, the 3NF violations are the same, and so is the decomposition. Chapter 4 Other Data ModelExercise 4.2.1：In Exercise 2.1.1 was the informal description of a bank database. Render this design in ODL. P.146Solution:class Customer attribute string name; attribute string addr; attribute string phone; attribute integer ssNo; relationship Set ownsAccts inverse Account:ownedBy;class Account attribute integer number; attribute string type; attribute real balance; relationship Set ownedBy inverse Customer:ownsAcctsExercise 4.2.4：Suppose we wish to keep a genealogy. We shall have one class, Person. The information we wish to record about persons includes their name (an attribute) and the following relationships: mother, father, and children. Given an ODL design for the Person class. Be sure to indicate the inverses of the relationships that, like mother, father, and children, and also relationships from Person to itself. Is the inverses of the mother relationship the children relationship? Why or why not? Describe each of the relationships and their inverses as sets of pairs. P.146class Person attribute string name; relationship Person motherOf inverse Person:childrenOfFemale relationship Person fatherOf inverse Person:childrenOfMale relationship Set children inverse Person:parentsOf relationship Set childrenOfFemale inverse Person:motherOf relationship Set childrenOfMale inverse Person:fatherOf relationship Set parentsOf inverse Person:childrenNotice that there are six different relationships here. For example, the inverse of the relationship that connects a person to their (unique) mother is a relationship that connects a mother (i.e., a female person) to the set of her children. That relationship, which we call childrenOfFemale, is different from the children relationship, which connects anyone - male or female - to their children. Exercise 4.3.1(a)：Add suitable extents and keys to your ODL schema from Exercise 4.2.1. P.155Solution:We think that Social Security number should be the key for Customer, and account number should be the key for Account. Here is the ODL solution with key declarations. class Customer (extent Customers key ssNo) attribute string name; attribute string addr; attribute string phone; attribute integer ssNo; relationship Set ownsAccts inverse Account:ownedBy;class Account (extent Accounts key number) attribute integer number; attribute string type; attribute real balance; relationship Set ownedBy inverse Customer:ownsAcctsExercise 4.4.1(a)：Convert your ODL designs from the following exercises to relational database schemas. P.164a) Exercise 4.2.1.d) Exercise 4.2.4.a) Solution:We shall represent the relationship between customers and accounts by storing the owned accounts in the Customer relation, as: Customers(ssNo, name, address, phone, acctNumber)Accounts(number, type, balance)Notice that if we had started from the E/R diagram of Exercise 2.1.1, we would separate out the ownership relationship into its own relation, as: Customers(ssNo, name, address, phone)Accounts(number, type, balance)Owns(ssNo, number)Unlike the ODL-to-relation conversion, this approach avoids redundantly saying the address, phone, and so on, of the customers who have more than one account. d) Solution:If we mechanically perform the translation from the solution to Exercise 4.2.4, we get the following, since we must include all six relationships of class Person. Person(name, mother, father, childrenOfFemale, childrenOfMale, children, parentsOf)However, in general, we only need to represent one direction of each pair of inverse relationships, so we should pick one direction only. The natural choice is to pick the simple concepts mother, father, and children. That gives us the preferred relation: Person(name, mother, father, children)Exercise 4.5.2：Represent the banking information of Exercise 2.1.1 in the object-relational model developed in this section. Make sure that it is easy, given the tuple for a customer, to find their account(s) and also easy, given the tuple for an account to find the customer(s) that hold that account. Also, try to avoid redundancy. P.172Solution:Customers(name, aderess, phone, SocialSecurityNumber, Accts*Accounts)Accounts(type, number, balance, owns*Customers)Chapter 5 Relational AlgebraExercise 5.2.1: In this exercise we introduce one of our running examples of a relational database schema and some sample data. The database schema consists of four relations, whose schemas are:Product (maker, model, type)PC (model, speed, ram, hd, rd, price)Laptop (model, speed, ram, hd, screen, price)Printer (model, color, type, price)The Product relation gives the manufacturer, model number and type (PC, laptop, or printer) of various products. We assume for convenience that model numbers are unique over all manufacturers and product types; that assumption is not realistic, and a real database would include a code for the manufacturer as part of the model number. The PC relation gives for each model number that is a PC the speed (of the processor, in megahertz), the amount of RAM (in megabytes), the size of the hard disk (in gigabytes), the