Ukeoppgaver INF3100, uke 5 

Oppgaver fra læreboken:

Kap. 3:

3.1.1, 3.1.2(a), 3.1.3
3.2.1, 3.2.3, 3.2.7, 3.2.9(a)

Siden læreboken ikke har kommet til Akademika enda, følger oppgavetekstene her:

3.1.1: Consider a relation about people in the United States, including their name, Social Security number, street address, city, state, ZIP code, area code, and phone number (7 digits). What FD's would you expect to hold? What are the keys for the relation? To answer this question, you need to know something about the way these numbers are assigned. For instance, can an area code straddle two states? Can a ZIP code straddle two area codes? Can two people have the same Social Security number? Can they have the same address or phone number?

3.1.2: Suppose R is a relation with attributes A1, A2, ..., An. As a function of n, tell how many superkeys R has, if:

    a) The only key is A1.

3.1.3: Consider a relation representing the present position of molecules in a closed container. The attributes are an ID for the molecule, the u, v, and w coordinates of the molecule, and its velocity in the u, v, and w dimensions. What FD's would you expect to hold? What are the keys?

3.2.1: Consider a relation with schema R(A,B,C,D) and FD's BC → D, D → A, and A → B.

    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 superkeys for R that are not keys?

3.2.3: Show that the following rules hold, by using the closure test of Section 3.2.4.

    a) Augmenting left sides. If A1 A2 ... An → B is an FD, and C is another attribute, then A1 A2 ... An C → B follows.

    b) Full augmentation. If A1 A2 ... An → B is an FD, and C is another attribute, then A1 A2 ... An C → B C follows. Note: from this rule, the "augmentation" rule mentioned in the box of Section 3.2.7 on "A Complete Set of Inference Rules" can easily be proved.

    c) Pseudotransitivity. Suppose FD's A1 A2 ... An → B1 B2 ... Bm and C1 C2 ... Ck → D hold, and the B's are each among the C's. Then A1 A2 ... An E1 E2 ... Ej → D holds, where the E's are all those of the C's that are not found among the B's.

    d) Addition. If FD's A1 A2 ... An → B1 B2 ... Bm and C1 C2 ... Ck → D1 D2 ... Dj hold, then FD A1 A2 ... An C1 C2 ... Ck → B1 B2 ... Bm D1 D2 ... Dj also holds. In the above, we should remove one copy of any attribute that appears among both the A's and C's or among both the B's and D's.

3.2.7: Show that if a relation has no attribute that is functionally determined by all the other attributes, then the relation has no nontrivial FD's at all.

3.2.9: Suppose we have a relation R(A,B,C,D,E), with some set of FD's, and we wish to project those FD's onto relation S(A,B,C). Give the FD's that hold in S if the FD's for R are:

    a) A → C, C → B, B → D, D → E, and E → A.
 

It is sufficient to give a minimal basis for the full set of FD's of S.