COS 425, Spring 2003 - Problem Set 7

Due at 11am, Thurs. April 24, 2003.

Collaboration Policy

You may discuss problems with other students in the class. However, each student must write up his or her own solution to each problem independently. That is, while you may formulate the solutions to problems in collaboration with classmates, you must be able to articulate the solutions on your own.


1. In Database Management Systems by Ramakrishnan and Gehrke, Chapter 18, pg. 599-600, Exercise 18.4.

2. Consider the following execution log:

LSN    log entry
0      T1 update Pg1  - prevLSN=null
1      T2 update Pg2  - prevLSN=null
2      begin checkpoint
3      end checkpoint
4      T3 update Pg3 - prevLSN=null
5      T1 update Pg4 - prevLSN=0
6      T3 update Pg5 - prevLSN=4
7      T1 commit - prevLSN=5
8      T1 end - prevLSN=7
9      T2 commit - prevLSN=1
Part a: Fill in the contents of the transaction table and the dirty page table saved at the checkpoint.

Part b: Suppose a crash occurs after LSN 9 and again during crash recovery after the first CLR record is written. Describe the actions of the crash recovery phases and show any additions to the log, including undoNextLSN values.

3. Consider a relation with 5 attributes A, B, C, D, and E. Answer the following questions given the functional dependences A -> B, B -> C, AE -> C.

Part a What is the closure of the given set of functional dependencies? List only the dependencies in the closure whose right sides are single attributes and whose left sides have no subset that can determine the same right side. (For example, given we have A->B, do not list AC->B.)

Part b What are the candidate keys for the relation?

Part c What is the minimal cover for the given set of functional dependencies?

Part d Is the relation is BCNF? Justify your answer.

Part e Is the relation is 3NF? Justify your answer. Also, if the relation is not in 3NF, give a lossless-join, dependency-preserving decomposition into a collection of 3NF relations.