CS386 Introduction to Databases
Spring 2006 Quarter

Assignment 7 ¨C Transactions and Normalization

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)

T2:    w(A)

T3:        r(B)

 

Question 2 (10 points)

T1:r(A)        w(B)

T2:    w(A)        r(C)

T3:        r(B)

 

Question 3 (10 points)

T1:r(A)    w(B)

T2:    w(A)

T3:            r(B)w(C)

 

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

 

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

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.

 

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.