Database Principles Assignment

1. Let us design a database for an 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. Solution:

2. For your E/R diagram of exercise 1, (i) Select and specify keys, and (ii) Indicate appropriate referential integrity constraints. 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. The E/R diagram below showes underlined keys and the numerocity constraint.

3. The E/R diagram below 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, sisterName)

4. 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? 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.

Consider a relation with schema R(A,B,C,D) and FD’s AB->C, C->D, and D->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. What are all the keys of R?

What are all the superkeys for R that are not keys?
Solutions:
(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. (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. (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.

5. 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 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. Solution:
(a) 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)

(Revised 1/19/02) The only key is AB. Thus, B->C and B->D are both BCNF violations. The derived FD’s BD->C and BC->D are also BCNF violations. However, any other nontrivial, derived FD will have A and B on the left, and therefore will contain a key. One possible BCNF decomposition is AB and BCD. It is obtained starting with any of the four violations mentioned above. 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.

6. What is the difference between the natural join R∞S and the theta-join R∞S where the condition C is that R.A=S.A for each attribute A appearing in the schemas of both R and S? 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.