CS145 Assignment #2

Due Wednesday, Oct 18, 2000

For this assignment, everyone needs an Oracle account. If you signed up for the course through Class Registration, we 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 The Database Administrator, Jonathan Pilat, directly.

Step 2 of Your PDA (Personal Database Application)

(a)

Please attach a copy of your E/R schema from the PDA part of Assignment #1. 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.

(b)

(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.

(c)

(20 pts.) Are there any flaws in the relational database schema you get from part (b)? Are there opportunities to combine relations without introducing redundancy? 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 it.

(d)

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 problems 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.

Problem Set

1. (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 states.

   • A mayor has a website address and a cell-phone number. They govern cities.

   • 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 world.)

   • For each politician, we would like to track all the states he/she has ever lived in.

   • 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.

   (a)

   Draw an E/R diagram that represents, as best you can, the information described above. Do not forget to indicate keys, possible weak entity sets, and arrows on relationships where appropriate.

   (b)

   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.

   (c)

   Repeat part (b), using the ``E/R'' approach to translating isa hierarchies.

2. (20 pts.) Consider a relation with schema R(A,B,C,D,E) and functional dependencies
   B->E, C->D, E->A, DA ->B

   (a)

   What are all the nontrivial functional dependencies that follow from the given dependencies? 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 inferred FD.

   (b)

   What are all the keys of R?

   (c)

   How many superkeys for R are there that are not keys? Explain your reasoning for partial credit.

   (d)

   Which of the 4 given dependencies violate BCNF, if any?

   (e)

   Which of the 4 given dependencies violate 3NF, if any?

   (f)

   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.

3. (15 pts.) Consider a relation R(A,B,C,D) with multivalued dependency AC ->->D and functional dependency B->A

   (a)

   Find all 4NF violations. For any that you find, explain why each is a violation, or explain why none are violations.

   (b)

   Decompose the relations into a collection of relation schemas in 4NF.

   (c)

   Consider the original relation R(A,B,C,D) with multivalued dependency AC ->->D and functional dependency B->A.
   Which of the following hold? For each, give reasons why it holds or at least one counterexample

       i.

   B ->-> CD

       ii.

   A ->-> D

       iii.

   AC -> D