CS386 Introduction to Databases
Spring 2006 Quarter

Assignment 7 ¨C Transactions and Normalization ANSWER KEY

Updated several questions 11:30AM, 6 June, to change ¨¤ to ¡ú


Due: Thursday, 8 June 2006 at the beginning of class

You may do this assignment individually or you may work with one partner.  That is, this assignment is to be completed by individuals or by teams of two students.  If you work with a partner, then you should turn in one assignment paper, with both of your names on the paper. You should only talk to the instructor, the TA and your partner about this assignment. You may also post questions to the course mailing list, cs386@cs.pdx.edu.

Please turn in your completed assignments on paper. Put your last name, first name, the assignment number in that order in the first line of your assignment.  List last name and first name for your partner, if you have one, on the second line of your assignment. (If you are working with a partner, turn in one assignment paper.)

Part I: Serializability

Here are three transactions

            T1: r(A), w(B), w(C);              T2: w(A), r(C) ;           T3: r(B), w(C)

For each partial schedule below, say whether it can be completed to give a schedule with no cycles in the precedence graph.  If so, show how.  If not, say why.

 

Question 1 (10 points)

T1:r(A)        w(B)    w(C)

T2:    w(A)                r(C)   

T3:        r(B)    w(C)

The precedence graph for just the partial schedule has edges T1¡úT2 and T3¡úT1. If we complete the schedule as shown above, we add the edge T3¡úT2, but there are no cycles, so the schedule is serializable (equivalent serial order is T3, T1, T2).

 

 

Question 2 (10 points)

T1:r(A)        w(B)

T2:    w(A)        r(C)

T3:        r(B)

The precedence graph for just the partial schedule has edges T1¡úT2 and T3¡úT1 as before. However, we cannot complete this partial schedule into a serializable one. At some point, T1 will have to do w(C), creating the edge T2¡úT1 and hence a cycle.

 

Question 3 (10 points)

T1:r(A)    w(B)

T2:    w(A)

T3:            r(B)w(C)

The precedence graph for just the partial schedule has edges T1¡úT2 and T1¡úT3. However, we cannot complete this partial schedule into a serializable one. At some point, T1 will have to do w(C), creating the edge T3¡úT1 and hence a cycle.

 

Part II: Functional Dependencies

The next three questions concern the following relation:

assigned(  PILOT   FLIGHT   DATE TIME  )

          Cushing   83      9 Aug 10:15a

          Clark     83     11 Aug 10:15a

          Chin      83     13 Aug 10:15a

          Cushing   116     10 Aug 1:25p

          Chin      116     12 Aug 1:25p

          Clark     281      8 Aug 5:50a

          Copley    281      9 Aug 5:50a

          Copley    281     13 Aug 5:50a

          Clark     301     12 Aug 6:35p

          Copley    412     15 Aug 1:25p

 

Question 4 (25 points)
Say whether each of the following FDs is holds for the instance above or not.


Question 5 (15 points)

Find a different instance of the assigned relation that satisfies the FD FLIGHT DATE ¡ú PILOT but violates both of the FDs DATE ¡ú PILOT and FLIGHT ¡ú PILOT (or explain why there is no such instance).

The smallest instance needs at least three tuples. The first FD is obeyed because FLIGHT DATE is a key of this instance. The first two tuples violate the second FD; the second two tuples violate the third FD.

assigned(  PILOT   FLIGHT   DATE TIME  )

          Cushing   83      9 Aug 10:15a

          Clark     83     11 Aug 10:15a

          Chin       77     11 Aug 10:15a

 

 

Question 6 (15 points)

Find a different instance of the assigned relation that satisfies the FDs FLIGHT DATE ¡ú TIME and TIME DATE ¡ú PILOT, but violates of the FD FLIGHT DATE ¡ú PILOT (or explain why there is no such instance).

There is no such instance.  Suppose we had a violation of FLIGHT DATE ¡ú PILOT. Then there must be a pair of tuples that agree on FLIGHT and DATE but have different PILOT values:

assigned(  PILOT   FLIGHT   DATE TIME  )

             P1     F1       D1   T1

             P2     F1       D1   T2

However, because these two tuples agree on FLIGHT and DATE, then from FLIGHT DATE ¡ú TIME, it must actually be the case that T1 = T2:

assigned(  PILOT   FLIGHT   DATE TIME  )

             P1     F1       D1   T1

             P2     F1       D1   T1

Now we have the two tuples agreeing on TIME and DATE, so from TIME DATE ¡ú PILOT we conclude that P1 = P2:

assigned(  PILOT   FLIGHT   DATE TIME  )

             P1     F1       D1   T1

             P1     F1       D1   T1

But this instance is no longer a violation of FLIGHT DATE ¡ú PILOT; we conclude there can be no such instance as described in this question.

 

(An alternative approach is to use rules of inference to prove that the first two FDs imply the third.)

 

Part III: Normalization

The last two questions concern the following relation scheme about breakfast cereals.

cereals(CE SE FA PR TC FI SU OC CA FC)
and the FDs

(Abbreviations: CE = cereal, SE = serving size, FA = fat grams, PR = protein grams, TC = total carb grams, FI = fiber grams, SU = sugar grams, OC = other carb grams, CA = Calories, FC = fat Calories)

Question 7 (5 points)

Describe a specific BCNF violation in cereals. That is, give a functional dependency that causes a violation and explain why it is a violation of BCNF.

Any of the last three FDs causes a BCNF violation, since none of them have a determinant (left-hand side) that is a key.

 

Question 8 (10 points)

Give a lossless decomposition of cereals into two or more relations that removes the specific BCNF violation from Question 7. Explain why the decomposition is lossless and why the violation is removed.

Consider FA PR TC ¡ú CA. We can ¡°lift¡± this FD into its own relation, giving the decomposition:

Cereals1(CE SE FA PR TC FI SU OC FC)

New(FA PR TC CA)

The FD no longer causes a problem: It doesn¡¯t apply to Cereals1, and its determinant is the key for New. The decomposition is lossless because the intersection of the two relation schemes is FA PR TC, which is a key for one of the tables, New.