Description
Part 1: There’s Nothing Wrong with Being Abnormal Unless you are a Relation
1. Suppose that we decompose the schema R(A, B, C, D, E, F) into R1 = (A, B, C, F) and R2 = (A, D, E).
Given the following functional dependencies hold, is the decomposition lossless? Explain your answer.
F = {A → BC, CD → E, B → D, E → A}
2. List non-trivial functional dependencies satisfied by the following relation. You do not need to find all
dependencies. In other words, please F, but there is no need to find F
+. It is enough to identify a set F of
functional dependencies that imply all functional dependencies satisfied by this relation.
A B C
a1 b1 c2
a1 b1 c2
a2 b1 c1
a2 b1 c3
3. Assume the following set of functional dependencies hold for the relation R(A, B, C, D, E):
F = {A → BC, CD → E, B → D, E → A}
(a) Is E a key for R? Explain your answer.
(b) Is BC a key for R? Explain your answer.
4. Assume the following set of functional dependencies hold for the relation R(A, B, C, D, E, F) : F = {A →
BC, C → E, B → D}
Is R in Boyce-Codd Normal Form (BCNF)? Explain your answer. If it is not, normalize it into a set of
relations in BCNF.
5. Suppose we have a relation R(A, B, C, D) with a multivalued dependency (MVD) A BC. If we know that
the tuples (a, b1, c1, d1),(a, b2, c2, d2),(a, b3, c3, d3) are in the current instance of R, what other tuples do we
know must also be in R?
6. For relation R(A, B, C, D, E, F), suppose a functional dependency AB → E and two multivalued dependencies AB C and A B hold. Is R in 4NF? Explain your answer. If not, normalize it into 4NF.
1
Part 2: Entity-Relationship Status – It’s Complicated
1. You are to design a database that maintains information for producing a weekly television guide for a given
region (such as the Greater Los Angeles region). The data should include information about television shows,
television networks, cities, channels, show times, etc. For starters, you may make the following assumptions:
• A given channel in a given city is associated with one network.
• A given show is either owned by a network (and shown on a channel associated with that network) or
is a local show and may be shown on any channel.
• Not all shows are shown in all cities, and the days and times for a given show may differ from city to
city.
• You may ignore cable channels, which generally are not city-dependent.
Please feel free to make additional assumptions about the real world in your design, as long as the assumptions
are reasonably realistic and are stated clearly as part of your solution.
Specify an entity-relationship diagram for your database. Dont forget to underline key attributes and include arrowheads and double lines.
Note that this question is fairly open-ended and there is no single right answer, but some designs are better
than others.
2. This problem is based on an E/R design for a database used in a manufacturing company shown in Figure
1. This database stores information about parts. Each part has a part number, which uniquely identifies
the part. A part may in fact be an assembly, which consists of some number of one or more subparts. For
example, a bicycle might be described as an assembly consisting of one frame and two wheels; a frame is
just a basic part; a wheel is an assembly consisting of one tire, one rim, and 48 spokes. Each assembly is
also associated with the cost of assembling its subparts.
Convert the E/R diagram to relations. For the translation of subclasses, assume that we generate multiple
tables for specialization and that a subclass does not inherit non-key attributes from its superclass. The text
does not properly discuss the circle: it just means an “attribute of an entity set.”
Part 3: Seeing the Forest for the Trees
Consider the following two B+trees for this problem. You may need to review chapter 11, or the lecture slides.
1. Show the final B+tree structure after we insert 60, 20, and 80 into Figure (a) in the given order.
2. Show the final B+tree structure after we delete 20, 10, and 70 from Figure (b) in the given order.
2