CS145 Assignment #2
Due Wednesday, Oct 18, 2000
Remember: the rules for deadlines and late homeworks are described in
The First Homework.
For this assignment, everyone needs an Oracle account.
If you signed up for the course through Class
shall send your leland account to the
administrator for the oracle installation at Stanford.
After we send in the list, you will have to deal with
Administrator, Jonathan Pilat, directly.
Step 2 of Your PDA (Personal Database Application)
- Please attach a copy of your E/R schema from the PDA part of
If you have modified your design because of TA feedback (or any other
reason), please hand in the modified design instead; the new design will
not be graded but will be compared with your relational design.
- (20 pts.)
Use the method for translating an E/R diagram to relations described in
class and the text to produce a set of relations from your E/R design.
Specify your relational schema using the notation of Section 3.1.2,
and please be sure to underline key attributes.
- (20 pts.) Are there any flaws in the relational database
schema you get from part (b)?
Are there opportunities to combine relations without introducing
If so, indicate which, and if not, tell us there are none.
Are there examples of non-BCNF relation schemas?
If so, do you want to decompose them?
For each opportunity to combine or decompose
relations, decide whether or not to do
so, and explain your reasoning briefly (e.g., tell us what queries you
expect will be typical for your database, and tell how the design you
pick facilitates them).
Is there anything
you still don't like about the schema (e.g., attribute names, relation
structure, duplicated information, etc.)? If so, modify the relational
schema to something you prefer. You will be working with this schema quite
a bit, so it's worth spending some time to make sure you're happy with
- Login to Oracle, using your Oracle account.
We'll announce on cs145-all when the accounts have been set up,
which should be at least several days before this assignment is due.
Use the Oracle Introductory Guide to see
how to login and change your password.
Try some simple commands, such as help or table (relation) creation.
No credit will be given,
but it is important that people try logging in as soon as there is a good
chance your login will be recognized. We'll need time to handle login
such as someone who thinks they are registered for the class and isn't.
Don't forget to save a copy of your PDA for reference as you
do Step 3 of the PDA.
- (25 pts.)
Suppose that you work for a non-profit organization that needs to keep track of
the political landscape to get its job done. You have been tasked to
design and build a simple database to hold information about some of the
elected politicians in different states.
Here is the type of information your boss wants to maintain:
- The organization plans to be in contact with many politicians. Each
politician has a unique name (assume if there is similarity, they will add
components like "W." to distinguish one politician from
another). We also want to track
each politician's party affiliation and mailing address.
- The two subclasses of politicians that your company is most concerned
with are governors and mayors.
- A governor has a nickname and an annual fiscal budget. They govern
- A mayor has a website address and a cell-phone number. They govern
- We also have insider information on which governors are friendly with
which mayors. These friendship networks are complex and change
daily. However, we can safely assume that the friendships are reciprocal.
- There is exactly one governor in each state, and a governor can only
be the governor of one state. In contrast, mayors can be elected to lead
multiple cities, although each city has only one mayor. It is possible
that a politician can be both a governor and a mayor.
(Admittedly, this information does not conform exactly to the real
For each politician, we would like to track all the states he/she has
We'd also like to track the populations of cities and states, and we can
identify each location by its name (e.g. Palo Alto). City names are not
unique. Two or more states may have a city with the same name although we
can assume that within a single state, all city names are unique.
Draw an E/R diagram that represents, as best you can, the information
Do not forget to indicate keys, possible weak entity sets, and arrows on
relationships where appropriate.
Design a relational database schema for this information, assuming that
the isa hierarchy involving politicians and its subclasses are
translated to relations using the ``object-oriented'' approach.
Please indicate keys in your relation schemas.
Repeat part (b), using the ``E/R'' approach to translating isa
- (20 pts.)
Consider a relation with schema R(A,B,C,D,E) and functional
B->E, C->D, E->A, DA ->B
What are all the nontrivial functional dependencies that follow from the
You need report only those that have singleton right sides and minimal
left sides; e.g., you do not have to report XY->F if X->F is a given or
What are all the keys of R?
How many superkeys for R are there that are not keys? Explain your
reasoning for partial credit.
Which of the 4 given dependencies violate BCNF, if any?
Which of the 4 given dependencies violate 3NF, if any?
Suppose we decompose relation R(A,B,C,D,E) into relation S(A,B,C) and
other relations. Give the nontrivial functional dependencies that
hold in S.
Your answer must include derived dependencies, but as in part (a)
it is sufficient to limit your answer to FD's with singleton right sides
and minimal left sides.
- (15 pts.)
Consider a relation R(A,B,C,D) with multivalued dependency AC ->->D
and functional dependency B->A
Find all 4NF violations. For any that you find, explain why each is a
violation, or explain why none are violations.
Decompose the relations into a collection of relation schemas in 4NF.
Consider the original relation R(A,B,C,D) with multivalued dependency AC
and functional dependency B->A.
Which of the following hold? For each, give reasons why it holds or at
least one counterexample
B ->-> CD
A ->-> D
AC -> D