《Introduction to Database System》
Solutions to Exercises
Li Ping
Chapter 2 The Entity-Relationship Data Model
Exercise 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.36
Solution:
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:
Exercise 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.44
Solution:
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.53 Solution:
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.58
Solution:
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 Model
Exercise 3.1.1: In Fig. 3.3 are instances of two relations that might constitute part of a banking database. Indicate the following: P.64
Solution:
a) The attribute of each relation.
Accounts: acctNo, type, balance
Customers: firstName, lastName, idNo, account
b) 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:
acctNo string;
type string;
balance real
For Customers:
firstName string;
lastName string;
idNo string;
account string
g) Another equivalent way to present each relation.
For Customers:
Exercise 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!=6
columns: 3!=6
number of presentation is 6*6=36
Exercise 3.2.1: Convert the E/R diagram of Fig. 3.11 to a relational database schema. P.75
Solution:
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, Theship, The sister)
Exercise 3.3.1:convert the diagram of Fig. 3.14 to relational database schema, using each of the following approaches: P.80
a) 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 FD?s would you expect to hold? What are the keys? P.89
Solution:
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 z
ID → vx, vy, vz
x y z → vx, vy, vz
Exercise 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 FD?s AB →C, C →D, and D →A. P.100
a) What are all the nontrivial FD?s that follow from the given FD?s? You should restrict yourself to FD?s 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 FD?s:
a) R(A, B, C, D) with FD?s AB →C, C →D, and D →A.
b) R(A, B, C, D) with FD?s B →C, and B →D.
do the following:
i) Indicate all the BCNF violations. Do not forget to consider FD?s 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 Model
Exercise 4.2.1：In Exercise 2.1.1 was the informal description of a bank database. Render this design in ODL. P.146
Solution:
class Customer {
attribute string name;
attribute string addr;
attribute string phone;
attribute integer ssNo;
relationship Set
inverse Account::ownedBy;
}
class Account {
attribute integer number;
attribute string type;
attribute real balance;
relationship Set
inverse Customer::ownsAccts
}
Exercise 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.146
class Person {
attribute string name;
relationship Person motherOf
inverse Person::childrenOfFemale
relationship Person fatherOf
inverse Person::childrenOfMale
relationship Set
inverse Person::parentsOf
relationship Set
inverse Person::motherOf
relationship Set
inverse Person::fatherOf
relationship Set
inverse Person::children
}
Notice 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.155 Solution:
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
inverse Account::ownedBy;
}
class Account
(extent Accounts key number)
{
attribute integer number;
attribute string type;
attribute real balance;
relationship Set
inverse Customer::ownsAccts
}
Exercise 4.4.1(a)：Convert your ODL designs from the following exercises to relational database schemas. P.164
a) 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.172
Solution:
Customers(name, aderess, phone, SocialSecurityNumber, Accts{*Accounts})
Accounts(type, number, balance, owns{*Customers})
Chapter 5 Relational Algebra
Exercise 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 speed and type of the removable disk (CD or DVD), and the price. The Laptop relation is of similar, except that the screen size (in inches) is recorded in place of information about the removable disk. The Printer relation records for each printer model whether the printer produces color output (true, if so), the process type (laser, ink-jet, or bubble), and the price.
Some sample data for the relation Product is shown in Fig.5.10. Sample data for the other three relations is shown Fig.5.11. Manufacturers and model numbers have been “sanitized”, but the data is typical of products on sale at the beginning of 2001.
Write expressions of relational algebra to answer the following queries. You may use the linear notation of Section 5.2.11 if you wish. For the data of Figs. 5.10 and 5.11, show the result of your query. However, your answer should work for arbitrary data, not just the data of these figures.
a) What PC models have a speed of at least 1000?
d) Find the model numbers of all color laser printers.
f) Find those hard-disk sizes occur in two or more PC?s. P.207
Solution:
a)
πmodel (σspeed≥1000)(PC)
d)
πmodel (σtype=…laser ? and color )(Printer)
f)
The trick is to theta-join PC with itself on the condition that the hard disk sizes are equal. That gives us tuples that have two PC model numbers with the same value of hd. However, these two PC's could in fact be the same, so we must also require in the theta-join that the model numbers be unequal. Finally, we want the hard disk sizes, so we project onto hd.
The expression is easiest to see if we write it using some temporary values. We start by renaming PC twice so we can talk about two occurrences of the same attributes.
R1 = ρPC1(PC) R2 = ρ
R3 =
R1 R2
R4 = πPC1.hd (R3)
Exercise 5.2.7: What is the difference between the natural join
and the theta-join
where the condition C is that R.A=S.A for each attribute A appearing in the schema of both R and S? P.213
Solution:
The relation that results from the natural join has only one attribute from each pair of equated attributes. The theta-join has attributes for both, and their columns are identical.
Exercise 5.3.1: Let PC be the relation of Fig.5.11(a), and suppose we compute the projection
πspeed (PC). What is the value of this expression as a set? As a bag? What is the average value of tuples in this projection, when treated as a set? As a bag? P.220
Solution:
As a bag, the value is {700, 1500, 866, 866, 1000, 1300, 1400, 700, 1200, 750, 1100, 350,733}. Order is unimportant, of course. The average is 958.8.
As a set, the value is {700, 1500, 866, 1000, 1300, 1400, 1200, 750, 1100, 350,733}. The average is 990.8.
Exercise 5.3.4: Certain algebraic laws for relations as sets also hold for relations as bags. Explain why each of the laws below hold for bags as well as sets. P.220 a) The associative law for union: (R ∪S )∪T =R ∪(S ∪T )
Solution:
As sets, an element x is in the left-side expression
(R ∪S) ∪ T
if and only if it is in at least one of R, S, and T. Likewise, it is in the right-side expression
R ∪(S ∪T)
under exactly the same conditions.
Thus, the two expressions have exactly the same members, and the sets are equal.
As bags, an element x is in the left-side expression as many times as the sum of the number of times it is in R, S, and T.
The same holds for the right side.
Thus, as bags the expressions also have the same value.
Exercise 5.4.1: Hear are two relations: R(A, B): {(0,1), (2,3), (0,1), (2, 4), (3,4)}
R S S
S(B, C): {(0,1), (2,4), (2,5), (3,4), (0,2), (3,4)} Compute the following: P.230
a) ()R B A B A 22,,+π projection
c) τB,A (R) sorting
e)
k) left-outjoin
a) Solution:
()R B A
B A 2
2
,,+π={(1,0,1), (5,4,9), (1,0,1), (6, 4, 16), (7, 9, 16)}
c) Solution:
τB,A (R)={ (0,1), (0,1), (2,3), (2,4), (3,4)} e) Solution:
δ(R)={(0,1), (2,3), (2,4), (3,4)} k) Solution: ={(2,3,4), (2,3,4), (0,1,⊥) , (0,1,⊥), (2,4,⊥), (3,4,⊥) }
Exercise 5.4.3: One thing that can be done with an extended projection, but not with the original
version of projection that we defined in Section 5.2.3, is to duplicate columns. For example, if R(A, B) is a relation, then πA,A (R) produces the tuple (a, a) for every tuple (a, b) in R. Can this operation be done using only the classical operations of relation algebra from Section 5.2? Explain your reasoning. P.230
Solution:
The answer is we can use only the classical operations of relation algebra from Section 5.2 to do the operation.
R1(A): = πA (R)
R2(A, A1): = R1×ρS(A1)(R) ANSWER(A, A1): = σA=A1(R2)
Under bag semantics, it is not possible. The intuitive idea behind the proof is that:
1. Focus on the case when R consists only of two tuples, each of which is (0,1). we need to
produce the result {(0,0), (0,0)}.
2. Since joins can be expressed as products, selections, and projections, let us assume that the only
operations used are selection, projection, product, union, intersection, and difference.
3. We can never get a relation with tuples that have two 0's in different components without using
a product. However, then we get at least four identical tuples (or none, if we have eliminated the 0's) with two 0's.
4. No operation can distinguish among them, so they all survive any operation, or none do.
5. Thus, we can never produce a result with exactly two tuples with two 0 components.
Exercise 5.5.1: Express the following constraints about the relations of Exercise 5.2.1, reproduced here:
Product (maker, model, type)
PC (model, speed, ram, hd, rd, price)
Laptop (model, speed, ram, hd, screen, price)
Printer (model, color, type, price)
You may write your constraints either as containments or by equating an expression to the empty set. For the data of Exercise 5.2.1, indicate any violations to your constraints.
a) A PC with a processor speed less than 1000 must not sell for more than $1500.
b) A laptop with a screen size less than 14 inches must have at least a 10 gigabyte hard disk or sell for less than $2000.
a) Solution:
σspeed<1000 and price>1500(PC)=?
πmodel(σspeed<1000(PC))?πmodel(σ price<=1500(PC))
The violations are:
{(1003, 866, 128, 20, 8xDVD, 1999), (1013, 733, 256, 60, 12xDVD, 2499)}
b) Solution:
σscreen<14 and (price>=2000 or hd<10)(Laptop)=?
πmodel(σscreen<14(PC))?πmodel(σ price<=2000 or hd>=10(PC))
The violations are:
{(2005, 600, 64, 6, 12.1, 2399)}
chapter6 The Database Language SQL
Exercise 6.1.1: If a query has a SELECT clause
SELECT A B
How do we know whether A and B are two different attributes or B is an alias of A? P.252
Solution:
Check if there is a comma between A and B, if there is one, B is an attribute, if not, then B is an alias.
If they are two different attributes, there will be a comma between them. Remember, in SQL, two names with no punctuation between them usually indicates that the second is an alias for the first.
Exercise 6.1.2: Write the following queries, based on our running movie database example Movie(title, year, length, inColor, studioName, producerC#)
StarsIn(movieTitle, movieYear, starName)
MovieStar(name, address, gender, birthdate)
MovieExec(name, address, cert#, netWorth)
Studio(name, address, presc#)
in SQL. P.252
a) Find the address of MGM studios
b) Find Sandra Bullock?s birthdate.
c) Find all the stars that appeared either in a movie made in 1980 or a movie with “Love” in the title.
d) Find all executives worth at lease $10,000,000
e)Find all the stars who either are male or live in Malibu (have string Malibu as a part of their address).
a) Solution:
SELECT address
FROM Studio
WHERE name = 'MGM';
b) Solution:
SELECT birthdate
FROM MovieStar
WHERE starName= …Sandra Bullock?
c) Solution:
If you interpret the question as asking only that Love appear as a substring, then the following is OK: SELECT starName
FROM StarsIn
WHERE movieYear = 1980 OR movieTitle LIKE '%Love%';
However, another reasonable interpretation is that we want the word Love as a word by itself. The query above returns stars of a movie like The Cook, the Thief, His Wife, and Her Lover. To identify only titles that have Love as a word by itself, either at the beginning, the middle, the endor as the entire title,
we need to use four patterns. The following query works; notice the judiciously placed blanks in the patterns.
SELECT starName
FROM StarsIn
WHERE movieYear = 1980 OR
movieTitle LIKE 'Love %' OR
movieTitle LIKE '% Love %' OR
movieTitle LIKE '% Love' OR
movieTitle = 'Love';
d) Solution:
SELECT name
FROM MovieExec
WHERE netWorth>=10000000
e) Solution:
SELECT name
FROM MovieStar
WHERE gender= …M? OR address like …%Malibu%?
Exercise 6.1.3: Write the following queries in SQL. They refer to the database schema of Exercise 5.2.1.
Product (maker, model, type)
PC (model, speed, ram, hd, rd, price)
Laptop (model, speed, ram, hd, screen, price)
Printer (model, color, type, price)
Show the result of your queries using the data from Exercise 5.2.1.P.252
a) Find the model number, speed, and hard-disk size for all PC?s whose price is under $1200
b) Do the same as (a), but rename the speed column megahertz and the hd column gigabytes.
e) Find all the tuples in the Printer relation for color printers. Remember that color is a Boolean-valued attribute.
a) Solution:
SELECT model, speed, hd
FROM PC
WHERE price < 1200;
The result:
b) Solution:
SELECT model, speed AS megahertz, hd AS gigabytes
FROM PC
WHERE price < 1200;
The result:
e) Solution:
SELECT *
FROM Printer
WHERE color;
The result:
Exercise 6.2.1: Using the database schema of our running movie example Movie(title, year, length, inColor, studioName, producerC#)
StarsIn(movieTitle, movieYear, starName)
MovieStar(name, address, gender, birthdate)
MovieExec(name, address, cert#, netWorth)
Studio(name, address, presc#)
Write the following queries in SQL. P.262
a) Who were the male stars in Terms of Endearment?
b) Which stars appeared in Movies produced by MGM in 1995?
d) Which movies are longer than Gone With the Wind?
a) Solution: